CN102662764B - 一种基于smdp的动态云计算资源优化分配方法 - Google Patents

Abstract

本发明公开了一种基于SMDP的动态云计算资源优化分配方法，属于计算机通信技术领域。本方法为：1)云计算服务域系统将用户满意度划分为N类；2)终端用户发送服务请求给云计算服务域，申请使用云计算服务；3)云计算服务域系统根据接收的服务请求和当前云计算服务域状态建立一行动集合；4)针对行动集合中的每一行动，计算云计算服务域的长期收益；5)云计算服务域系统根据计算的长期收益确定是否接受当前服务请求，如果接受则选取长期收益最大的行动对应的VM资源分配方案为云计算服务请求分配VM。与现有技术相比，本发明大大提高了移动终端的用户满意度和服务质量。

Description

一种基于SMDP的动态云计算资源优化分配方法

技术领域

本发明属于计算机通信技术领域，涉及云计算系统的资源优化分配方法，尤其涉及移动云计算系统中对云计算服务域的云计算资源的优化配置方法。

背景技术

云计算是一种以资源按需分配，pay-as-you-go，效能计算为特征的新的计算服务模式(Armbrust，M.，Fox，A.，Griffith，R.，Joseph，A.，Katz，R.，Konwinski，A.，Lee，G.，Patterson，D.，Rabkin，A.，Stoica，I.，et al.“Above the clouds：A berkeley view of cloud computing”.EECSDepartment，University of California，Berkeley，Tech.Rep.UCB/EECS-2009-28(2009))。云计算不仅为云计算服务商同时也为个人用户提供了一种新的计算模式，它可以被广义的分为infrastructure-as-a-service(IaaS)，platform-as-a-service(PaaS)以及software-as-a-service(SaaS)三大类。随着无线通信技术以及互联网技术的发展，移动终端将逐渐取代PC机成为全球最主要的互联网接入设备。由于移动终端(MD)与传统有线终端相比具有更多的优势(例如移动性，灵活性以及感知能力等)，因此将移动计算和云计算技术结合在一起自然就成为构建移动应用的新方法，目前无论在学术界还是工业界也吸引了越来越多的关注。因而，一个新的研究领域-移动云计算(Mobile Cloud Computing)也就应运而生。

在以前关于移动云计算的研究中，主要的研究方向集中在计算任务的上传下载、远程运行以及动态组织等。作者在(X.Li，H.Z，and Y.Zhang，“Deploying Mobile Computation in CloudService”in Proceedings of the First International Conference for Cloud Computing(CloudCom)，2009，p.301.)中提出了一个在移动终端和云端都能运行移动应用的移动云计算模型，从而资源有限的移动终端能将计算、传输以及存储任务上传到云端运行。作者在(B.Chun and P.Maniatis，“Augmented Smartphone Applications Through Clone Cloud Execution，”in Proceedings ofUSENIX HotOS XII，2009.)中通过增加执行次数来配置CloneCloud云资源，但是没有考虑到用户终端的实际运行状态。移动终端通过云计算网络对弹性应用服务的资源分配在(X.Zhang，J.Schiffman，S.Gibbs，A.Kunjithapatham，and S.Jeong，“Securing elastic applications on mobiledevices for cloud computing，”in Proceedings of the 2009 ACM workshop on Cloud computingsecurity，2009，pp.127-134.)里面做了一些初步的研究。在文献(D.Huang，X.Zhang，M.Kang，and J.Luo，“Mobicloud：A secure mobile cloud framework for pervasive mobile computing andcommunication，”in Proceedings of 5th IEEE International Symposium on Service-OrientedSystem Engineering，2010.)里，Huang等人提出了移动云计算架构，该模型允许移动终端将相关应用上传到云端的虚拟机(VM-Virtual Machine)运行。作者在(X.Meng，V.Pappas，and L.Zhang，“Improving the scalability of data center networks with trafficaware virtual machineplacement，”in IEEE INFOCOM，San Diego，CA，USA，March 2010.)中提出了一种根据不同地域的不同流量来配置虚拟机，通过优化配置虚拟机的放置位置来提高网络的利用率的新方法。实际上，由于这些关于移动云计算的架构设施的研究探讨已经比较充分，因此，移动云计算的资源分配自然将成为下一个的主要研究方向。

在移动云计算网络中，基于服务器族群在地理位置上的分布式放置，系统的云计算资源(例如CPU，内存以及存储等)分别由多个移动云计算服务域来负责分配。每一个移动云计算服务域由多个虚拟机(VM-Virtual Machine)组成，而每一个虚拟机(VM)则由能处理一个云计算服务的最小云计算资源组成。尽管与移动终端相比，移动云计算网络的云计算资源通常被认为是无限的，但是仍然非常有必要充分利用移动云计算服务域中的云计算资源来实现移动云计算网络的低成本运行。

目前对云计算尤其是移动云计算的资源优化分配进行的研究还比较少。文献(H.Liang，D.Huang，and D.Peng，“On Economic Mobile Cloud Computing Model，”in in Proceedings of theInternational Workshop on Mobile Computing and Clouds(MobiCloud in conjunction withMobiCASE)，2010.)提出了一个经济型的移动云计算资源分配模型，该模型能在给定系统配置的情况下，通过在云端和移动终端之间优化分配移动应用来获得移动云计算网络的最大收益。文献(G.Wei，A.V.Vasilakos，Y.Zheng，and N.Xiong，“A game-theoretic method of fairresource allocation for cloud computing services，”2009.)提出了一个基于博弈论的云计算资源分配模型，该模型能根据移动终端对用户服务质量(QoS)的需求来分配云计算资源。另外，还有一些文献对云计算网络如何通过虚拟机或者是数据中心的服务器来优化分配云计算资源进行了研究。在(K.Lorincz，B.r.Chen，J.Waterman，G.Werner-Allen，and M.Welsh，“Resource awareprogramming in the pixie os，”in SenSys’08，Raleigh，North Carolina，USA，November 2008.)中，作者提出了一个新的云计算操作模型，该操作模型不仅能使用户在掌握云计算资源的情况下进行编程，同时也能实现云计算网络中，云计算服务重用云计算资源的分配模式。文献(K.Lorincz，B.Chen，J.Waterman，G.Werner-Allen，and M.Welsh，“A stratified approach forsupporting high throughput event processing applications，”in DEB S’09，Nashville，TN，USA，July2009.)对云计算网络中事件应用的云计算资源分配进行了研究。在(G.Tesauro，N.K.Jong，R.Das，and M.N.Bennani，“A hybrid reinforcement learning approach to autonomic resourceallocation，”in Proc.of ICAC-06，Dublin，Ireland，June 2006.)中，作者提出了一个基于增强型自学习系统的资源分配模型来对云计算网络中的服务器进行动态分配，从而提高云计算网络的收益。在(K.Boloor，R.Chirkova，Y.Viniotis，and T.Salo，“Dynamic request allocation andscheduling for context aware applications subject to a percentile response time sla in a distributedcloud，”in 2^nd IEEE International Conference on Cloud Computing Technology and Science，Indianapolis，Indiana，USA，November 2010.)中，作者提出了一个通用的对云计算服务请求进行分配和规划的方案，该方案在获得用户指定的服务质量的同时，提高了云计算服务提供商的收益。

针对云计算资源的优化分配，国内也提出了一些解决方案。比如在专利申请201110097395.8(一种管理控制云计算网络技术系统)中，作者(曹雪竹)提出了一种管理控制云计算网络技术系统的发明；在专利申请201110138021.6(一种云计算资源管理系统及方法)中，作者(季昕华，聂颂，杜海和马强)提出了一种云计算资源管理系统及方法的发明；在专利申请201110075410.9(云计算操作系统中配置信息的管理方法和系统)中，作者(张立强和张海涛)提出了一种云计算操作系统中配置信息的管理方法和系统的发明；在专利申请201080005003.4(用于在云计算环境中自动管理虚拟资源的系统和方法)中，作者(S·M·尤姆伯豪克)提出了一种用于在云计算环境中管理虚拟资源的系统的发明；在专利申请201110222073.1(一种基于虚拟化资源的云计算管理系统)中，作者(沈凌云，阮敏慧和周永丰)提出了一种基于虚拟化资源的云计算管理系统(C2MS)的发明。移动云计算网络的一个主要优势是允许移动终端在云端运行他们的移动应用服务。而一个云计算服务还可以被分配多个VM的云计算资源来使移动终端获得更高的计算和存储能力。当移动云计算服务域收到一个从移动终端发送过来的云计算服务请求时，系统需要分析当前可用的云计算资源，并基于分析结果决定是否接收该云计算服务请求；如果决定是接收，那么系统还需要进一步判决具体为该移动终端的云计算服务请求分配多少云计算资源(即VM的个数)。如果移动云计算服务域中所有的云计算资源已经被占用，那么由于云计算资源的不足，系统会拒绝该移动终端的云计算服务请求(我们假设在移动云计算中，没有队列缓冲)。对移动终端云计算服务请求的拒绝不仅对移动终端的用户满意度和服务质量带来了负面的影响，而且也极大地降低了系统的净收益。

移动云计算服务域的系统收入通常随着被接收的云计算服务请求数量的增加而增加。但另一方面，随着系统接收的云计算服务请求越多，那么分配给每一个云计算服务的云计算资源也就越少，从而降低了正在接受服务的移动终端的用户满意度以及移动云计算服务域的系统性能。而现有关于云计算资源分配方法大部分只考虑了系统的收入，没有考虑到云计算资源被占用所带来的支出，也没有考虑到移动终端的用户满意度和服务质量(QoS)。因此，为了能得到移动云计算服务域全面的系统收益，在计算移动云计算服务域的系统收益时，不仅需要考虑移动云计算网络的收入，也需要考虑云计算资源被占用所带来的支出以及移动终端的用户满意度和服务质量(QoS)。

发明内容

针对移动云计算网络云计算服务域的云计算资源的优化分配问题，本发明的目的在于提供一种基于SMDP的动态云计算资源优化方法。本发明新提出了基于半马氏决策过程(SMDP)的移动云计算服务域动态云计算资源优化分配模型，通过该模型来获得移动云计算服务域的云计算资源的优化分配决策策略，并得到移动云计算服务域的最大收益，该收益不仅考虑了接收云计算服务请求所带来的收入，同时也考虑了因云计算服务占用云计算资源所带来的支出，以及移动终端的用户满意度和服务质量(QoS)。因此，该发明对移动云计算系统的整体收益以及移动终端客户对移动云计算网络的满意度的提高都具有非常重要的作用，这也是本发明的实际价值所在。

本发明的技术方案为：

一种基于SMDP的动态云计算资源优化分配方法，其步骤为：

1)云计算服务域系统将用户满意度划分为N类，满意度类别为i的用户对应分配的虚拟机VM数为k_i；其中，1≤k_i≤K，K为云计算服务域中的VM总数；

2)终端用户发送服务请求给云计算服务域，申请使用云计算服务；

3)云计算服务域系统根据接收的服务请求和当前云计算服务域状态建立一行动集合；

4)针对所述行动集合中的每一行动，计算云计算服务域的长期收益；

5)云计算服务域系统根据计算的长期收益确定是否接受当前服务请求，如果接受则选取长期收益最大的行动对应的VM资源分配方案为云计算服务请求分配VM。

进一步的，云计算服务域的状态s表示为s＝<n₁，n₂，...，n_N，e>；其中，n_i为云计算服务域中满意度类别为i的用户数，e为云计算服务域内的事件，e∈{R，D₁，D₂，D_i....，D_N}，R为云计算服务请求，D_i为满意度类别为i的云计算服务完成并释放了其所占用的VM数。

进一步的，所述行动集合为 $A\left(s\right)=\left\{\begin{array}{cc}-1& e\&Element;\{D_1,D_2,...,D_N\}\\ \{\mathrm{0,1},...,N\},& e=R.\end{array}\right.;$ 其中，A(s)＝-1表示云计算服务结束运行并释放所占用云计算资源的状态，A(s)＝0表示云计算服务域拒绝云计算服务请求，A(s)＝i表示云计算服务域接收云计算服务请求并分配给这个云计算服务请求的云计算资源为k_i个VM；s表示云计算服务域的当前状态。

进一步的，利用公式z(s，a)＝x(s，a)-τ(s，a)y(s，a)计算针对每一行动a的收益z(s，a)；其中，x(s，a)是状态为s、选择的行动为a时，云计算服务域所获得的总收入，τ(s，a)表示在状态为s、选取的行动为a时，转移到下一个状态j所预期的服务时间；y(s，a)表示在状态为s、选取的行动为a时云计算服务域的支出。

进一步的，利用公式 $x(s,a)=\left\{\begin{array}{cc}-1,& e=R,a=0\\ U\left(k_i\right),& e=R,a=i\end{array}\right.$ 计算云计算服务域所获得的总收入，U(k_i)为效能函数。

进一步的，利用公式计算云计算服务域由当前状态转移到下一个状态所预期的服务时间；其中，α为两决策点之间连续时间下的折扣率，决策点是指任何一个事件e发生的时间点，τ₁是指从当前状态到下一个事件发生的状态所经历的时间。

进一步的，两个决策点之间的时间τ(s，a)服从指数分布，事件发生的平均速率γ(s，a)＝τ(s，a)^-1。

进一步的，云计算服务域系统利用公式 $v\left(s\right)=z(s,a)+\mathrm{\&eta;}\underset{j\&Element;S}{\mathrm{\&Sigma;}}p\left(j\right|s,a)v\left(j\right),$ 计算所述行动集合中的每一行动a时云计算服务域的长期收益v(s)；其中，p(j|s，a)为状态转移概率，j为移动云计算服务域的下一状态，γ(s，a)为事件发生的平均速率，α为两决策点之间连续时间下的折扣率，决策点是指任何一个事件e发生的时间点，S为云计算服务域所有的可能状态，v(j)表示下一状态j时所获得的整体长期收益。

进一步的，采用一效能函数来度量云计算用户的满意度，将用户满意度划分为N类。

与现有技术相比，本发明的积极效果为：

本发明基于半马氏决策过程(SMDP)，首先提出了一个新的移动云计算服务域动态云计算资源优化分配模型，通过该模型获得的动态云计算资源优化分配决策策略不仅能使移动云计算服务域的系统收益最大，同时也能提高移动云计算服务域云计算资源的利用率以及移动终端的用户满意度和服务质量(QoS)。与传统的贪婪算法对网络资源的分配方案相比，根据我们所提出的移动云计算服务域动态云计算资源优化分配模型得到的优化策略，其系统收益及性能均有了大幅的提高。由图5和图6可知，随着云计算服务请求到达率的增长，尤其是当云计算服务请求的到达率超过5时，本发明的效能收益与传统贪婪算法相比提高了至少50％以上(如图5所示)，同时本发明的阻塞率与传统贪婪算法相比则至少降低了50％以上(如图6所示)。

本发明主要的贡献体现在如下三个方面：

1)基于半马氏决策过程(SMDP)推导出了移动云计算服务域的动态云计算资源优化分配决策策略。

2)该模型能基于移动云计算服务域当前可用的云计算资源，为云计算服务请求自适应地分配不同的云计算资源，通过充分利用该移动云计算服务域的云计算资源来提高云计算资源利用率，并获得移动云计算服务域的最大整体收益。

3)该模型获得的移动云计算服务域的最大系统收益，既考虑了该移动云计算服务域接收云计算服务请求所带来的收入，也考虑了因云计算资源被占用所带来的支出，还考虑了移动终端的用户满意度和服务质量(QoS)。因此，通过该模型得到的系统收益是全面的整体收益。

本发明所提出的移动云计算服务域动态云计算资源优化分配模型，不仅可以提高移动云计算网络云计算服务域的云计算资源的利用率，同时也能提高移动用户的服务质量(QoS)。为了验证本发明所提出的移动云计算服务域动态云计算资源优化分配模型的性能，我们通过实验将其与传统贪婪算法(Greedy Algorithm)的性能进行了比较(R.Ramjee，D.Towsley，and R.Nagarajan，“On optimal call admission control in cellular networks，”Wireless Networks，vol.3，no.1，pp.29-41，1997)。我们的实验结果表明，应用本发明提出的移动云计算服务域动态云计算资源优化分配模型，移动云计算网络的系统整体收益与贪婪算法相比提高了50％以上，而其云计算服务请求被拒绝的概率与贪婪算法相比则减少了50％以上，也即本发明所提出的移动云计算服务域动态云计算资源优化分配模型的性能以及服务质量(QoS)与贪婪算法相比均提高了50％以上。

附图说明

图1为移动云计算网络的服务模型；

图2为本发明的方法流程图；

图3为多媒体业务的效能函数；

图4为状态转移图(N＝2)，其中，连接两个状态的箭头线上第一项(例如a＝0)表示在当前状态下所采取的行动，连接两个状态的箭头线上第二项(例如)表示在当前状态下，采取相应行动后，转移到下一个状态的转移概率；

图5本发明的效能收益与传统贪婪算法对比图；

图6本发明的阻塞率与传统贪婪算法对比图。

具体实施方式

下面结合附图对本发明进行进一步详细描述。

1.移动云计算服务域动态云计算资源优化分配模型的算法描述：

移动云计算网络与传统的Client-Server服务模式相比的一个主要优势是：当移动终端将他们的应用服务上传到云端进行运算时，移动终端能获得更多的容量以及更好的性能(例如更少的处理时间，移动终端电池电量的节约等)。移动终端弹性应用任务的上传可以通过连接云端和移动终端的Weblet来实现。一个Weblet可以使用独立于平台的Java或者.Net或者Python语言，也可以使用平台编程语言。在(B.Chun and P.Maniatis，“Augmented SmartphoneApplications Through Clone Cloud Execution，”in Proceedings of USENIX HotOS XII，2009.)中研究了将Weblet从移动终端上传到云端运行的算法。通过Weblet上传弹性应用服务到云端运行，移动终端可以大幅提高自身的计算能力、存储能力以及网络带宽等。通常，移动终端决定是否将任务上传到云端运行取决于移动终端自身的状态(例如，移动终端的CPU处理能力、电池的电量、网络连接质量以及移动终端对安全的考虑等因素)。在本发明中，当移动终端决定将任务上传到云端运行时，它会首先给云端发送一个服务请求，如果云端接受了移动终端的服务请求，那么移动终端随后就会将任务上传到云端运行，运行结束后，云端会将运行结果返回给移动终端。

在本发明中，移动云计算网络中的计算资源和通信资源(包括服务器中的CPU，存储设备，内存等，以及其他路由设备和通信设备等)都是由虚拟机(VM)来统一管理。如图1所示，一个VM负责管理Weblet在移动云计算网络中的上传、卸载以及处理。如前所述，在本发明所提出的移动云计算服务域动态云计算资源优化分配模型中，一个VM是移动云计算服务域中处理一个云计算服务所需的最小云计算资源(CPU，内存以及存储等)，每一个VM所分配到的云计算资源一次只能处理一个云计算服务请求。虽然我们可以认为移动云计算网络中的云计算资源是无限的，但是在移动云计算网络中，某个具体的移动云计算服务域以VM数量来计数的云计算资源又是有限的。因此，在移动云计算服务域中，如果到达的云计算服务请求的数量超过了该服务域中可用的云计算资源VM个数，则随后到来的云计算服务请求将会被该服务域拒绝。另一方面，如果到达的云计算服务请求的数量远低于该服务域中可用的云计算资源VM个数，那么该服务域就可以为每个云计算服务请求分配更多的VM个数来充分利用该服务域的云计算资源，以此来提高该移动云计算服务域的云计算资源利用率以及移动终端的用户满意度和服务质量(QoS)。

因此，本发明所提出的移动云计算服务域动态云计算资源优化分配模型的目标就是通过充分利用云计算资源，使得移动云计算服务域既能获得最大整体系统收益，也能提高该服务域的云计算资源利用率以及用户满意度和服务质量(QoS)。

在本发明中，我们考虑一个只包含一个云计算服务域的移动云计算网络，设其云计算资源总共为K个虚拟机(VM)。用k表示分配给一个移动终端的云计算资源的VM个数，其中k是一个正整数，并且满足条件1≤k≤K。此外，我们可以用不同的效能函数(J.W.Lee，R.R.Mazumdar，and N.B.Shroff，“Non-convex optimization and rate control for multi-class services inthe Internet，”IEEE/ACM Transactions on Networking，2005，vol.13，no.4，pp.827-840.)来度量移动云计算用户的满意度。例如，可以用类似Sigmoidal函数来描述移动云计算移动终端的用户满意度，

$U\left(r\right)=1-\exp (-\frac{{\mathrm{\&omega;}}_2{r}^2}{{\mathrm{\&omega;}}_1+r}),---\left(1\right)$

其中U(r)表示移动云计算网络的用户满意度，r是移动云计算服务域分配给移动终端的云计算资源，ω₁和ω₂是用来调节U(r)波形的参数，其函数的波形如图3所示。

通常来讲，参数ω₁和ω₂的选择是由移动云计算服务和最终用户对服务质量(QoS)的需求来决定的，有效的指数选择对移动云计算服务域的云计算资源分配具有显著的影响。从公式(1)可知，为了提高移动云计算网络的用户满意度，需要给移动终端用户分配尽可能多的云计算资源。但是，从另一方面来讲，为了提高移动云计算网络的总体系统收益，根据该移动云计算服务域总的可用云计算资源和移动用户使用云计算服务对云计算资源的需求，系统又不可能单独给每一个移动终端用户都分配最大的云计算资源。为了能对移动云计算网络的云计算服务的动态需求建立优化模型，我们假设移动终端请求接入移动云计算网络并使用云计算服务的过程服从泊松分布(Poisson)，其均值为λ，同时也假设移动云计算终端用户的在网时间服从指数分布，其均值为λ表示以泊松分布达到云计算网络的云计算请求的速率，而μ表示结束服务的用户离开云计算网络服从指数分布的速率。

2.如图2所示，建立移动云计算服务域动态云计算资源优化分配模型的步骤如下：

1)设置系统状态

为了能使用半马氏决策过程来表征移动云计算服务域云计算资源的优化分配模型，由于用户对移动云计算网络的满意度与其服务请求被处理的时间成反比，即用户的服务请求被处理的时间越短则用户对系统的满意度越高，显然，如果分配给该用户的云计算资源(即VM个数)越多，则该用户所请求的服务被处理的时间则越短(通常来说，云计算服务可以由多个VM的云计算资源来并行处理，从而提高运行速度)。由此可知，用户对移动云计算网络的满意度与分配给该用户的云计算资源成正比，即分配给用户的云计算资源越多，则该用户的满意度越高。我们将移动云计算网络的用户满意度分为N类。因此我们定义本发明基于半马氏过程的移动云计算服务域动态云计算资源优化分配模型的系统状态是每一个用户满意度下所具有的云计算服务数量以及在该移动云计算服务域中所发生的事件的集合。我们还定义k_i为分配给用户满意度为i的用户的云计算资源的VM个数，这里i＝1，2，...，N，并且0＜k₁＜…＜k_N≤K。用n_i表示移动云计算服务域中用户满意度为i的所有用户数量。满意度为i的用户应分配k_i个VM的云计算资源。

在移动云计算服务域中，总共有两种类型的事件：

1)一个新到的云计算服务请求，用R来表示；

2)一个用户满意度为i的云计算服务完成了运行，并释放了其所占用的云计算资源，用D_i来表示。

因此在该移动云计算服务域内任何事件e都可以用e∈{R，D₁，D₂，....，D_N}来表示，系统的所有的可能状态用S来表示，从而移动云计算服务域的系统状态可用如下公式来表示：

S＝{s|s＝<n₁，n₂，...，n_N，e>}.

                                                                    (2)

2)设置行动集合

当一个终端用户请求接入移动云计算服务域并申请使用云计算服务时(e＝R)，该移动云计算服务域需要决定是否接受这个用户请求，如果接受的话，那么应该给这个请求服务的用户分配多少个VM的云计算资源。为简单计，我们用A(s)＝0表示该移动云计算服务域拒绝一个云计算服务请求；用A(s)＝i表示移动云计算服务域接收了该云计算服务请求，并且分配给这个云计算服务请求的云计算资源为k_i个VM，以期能使终端用户对该云计算服务的满意度达到i，这里s表示当前的系统状态。而另一方面，我们用A(s)＝-1来表示在一个云计算服务结束运行并释放所占用云计算资源的状态(这里事件e＝D_i)下的行动，即统计现有可用的云计算资源的VM个数并等待下一个事件的发生。因此，该模型的行动集合总结如下：

$A\left(s\right)=\left\{\begin{array}{cc}-1& e\&Element;\{D_1,D_2,...,D_N\}\\ \{\mathrm{0,1},...,N\},& e=R.\end{array}\right.---\left(3\right)$

3)设置收益模型

基于系统状态和对应的行动，我们可以预估一个移动云计算服务域能获得的收益(用z(s，a)来表示，a是系统对每一个事件所采取的行动，包括拒绝云计算服务请求或者为云计算服务请求分配i个VM的云计算资源。在云计算服务请求的到达状态下，a也可以理解为分配给每个用户的云计算资源的VM个数；但是在云计算服务结束后移动用户离开的状态下，a＝-1表示统计现有可用的云计算资源。)，这个收益由两部分组成，一是系统的收入，另一部分是系统的支出，可以用下式来表示，

z(s，a)＝x(s，a)-τ(s，a)y(s，a)    (4)

x(s，a)是系统在状态为s，选择的行动为a时，系统所获得的总收入，可以表示为，

$x(s,a)=\left\{\begin{array}{cc}-1,& e=R,a=0\\ U\left(k_i\right),& e=R,a=i\end{array}\right.---\left(5\right)$

其中，U(k_i)为效能函数，如公式(1)所示。τ(s，a)表示在当前系统状态为s，当选取的行动为a时，转移到下一个系统状态j所预期的服务时间；y(s，a)表示在当前系统状态为s，选取的行动为a时的支出，y(s，a)可以用正在运行的云计算服务所占用的云计算资源VM的总个数来度量，由下式表示为：

$y(s,a)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}{n}_i{k}_i.---\left(6\right)$

本发明根据收益模型得到的长期期望收益来决定是否决定该请求。本发明的长期收益模型会根据收益模型分别得到接收、拒绝的长期收益，然后选长期收益最大的那个行动a(接收或者是拒绝)；如果接收了当前请求，会更新系统状态。同时会等待下一个事件，然后在那个事件决定行动，并重新更新系统状态，这样周而复始的运行下去。

4)解出状态转移概率

决策点是指当任何一个事件发生的时间点，例如一个云计算服务请求到达移动云计算服务域，或者是一个已经完成使用云计算服务的移动终端用户离开该云计算服务域并且释放所占用的云计算资源。在我们的系统模型中，由于在两个决策点之间的时间τ(s，a)均服从指数分布，因此，所有事件发生的平均速率γ(s，a)可以表示为，

$\mathrm{\&gamma;}(s,a)=\mathrm{\&tau;}{(s,a)}^{-1}$

$=\left\{\begin{array}{cc}\mathrm{\&lambda;}+\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}{n}_i\mathrm{\&mu;},& e=R,a=0\\ & \mathrm{ore}=D_i\\ \mathrm{\&lambda;}+(\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}{n}_i+1)\mathrm{\&mu;},& e=R,a=i\end{array}\right.---\left(7\right)$

由此，在时间τ(s，a)之间的期望折扣收益z(s，a)可表示为，

$z(s,a)=x(s,a)-y(s,a)E_s^a\left\{{\&Integral;}_0^{{\mathrm{\&tau;}}_1}{\exp }^{-\mathrm{\&alpha;t}}\mathrm{dt}\right\}$

$=x(s,a)-y(s,a)E_s^a\left\{\frac{1-{\exp }^{-{\mathrm{\&alpha;\&tau;}}_1}}{\mathrm{\&alpha;}}\right\}---\left(8\right)$

$=x(s,a)-\frac{y(s,a)}{\mathrm{\&alpha;}+\mathrm{\&gamma;}(s,a)}$

其中，E是在状态s下，当采取行动a时，到下一个事件发生的平均期望时间，τ₁是指从当前状态到下一个事件发生的状态所经历的时间。x(s，a)和y(s，a)分别在公式(5)和(6)已经定义，由于在两个事件之间的时间是连续的，而我们在做决策的时间点是离散的，需要通过对连续时间的收益进行转换才能得到离散时间的收益，因此我们用α表示连续时间下的折扣率。我们让p(j|s，a)表示系统在状态s，当选取的行动为a，系统转移到状态j的转移概率。由此我们可以推导出所有的状态转移概率。为了简化书写，我们定义如下的符号，

${\hat{n}}_1=<n_1,n_2,..,n_i,..,n_N>$

${\hat{n}}_{2,i}=<n_1,..,n_i-1,..,n_N>$

${\hat{n}}_{3,i}=<n_1,..,n_i+1,..,n_N>$

${\hat{n}}_{4,i,m}=<n_1,..,n_i+1,..,n_m-1,..,n_N>.---\left(9\right)$

当一个新的云计算服务请求到达移动云计算服务域时，如果这时系统的决策是拒绝，那么有同时有a＝0；或者当一个用户满意度为i的云计算服务结束运行，该移动终端用户离开此移动云计算服务域并释放云计算资源时，这时系统里面正在接受云计算服务的用户数量减少并且可用云计算资源增加，因此有在这两种情况下，我们可以得到转移概率为，

$p\left(j\right|s,a)=\left\{\begin{array}{cc}\frac{\mathrm{\&lambda;}}{\mathrm{\&gamma;}(s,a)},& j=<{\hat{n}}_1,R>\\ \frac{n_{i,\mathrm{\&mu;}}}{\mathrm{\&gamma;}(s,a)},& j=<{\hat{n}}_{2,i},D_i>,n_i\&GreaterEqual;1.\end{array}\right.---\left(10\right)$

当一个新的云计算服务请求到达移动云计算服务域时，如果系统这时的决策是同意接入并且准备为该云计算服务请求分配的云计算资源为k_i个VM，那么此时同时有a＝i，i＝1，2，...，N，在这种情况下，我们可以得到转移概率为，

$p\left(j\right|s,a)=\left\{\begin{array}{cc}\frac{(n_i+1)\mathrm{\&mu;}}{\mathrm{\&gamma;}(s,a)},& j=<{\hat{n}}_1,D_i>\\ \frac{\mathrm{\&lambda;}}{\mathrm{\&gamma;}(s,a)},& j=<{\hat{n}}_{3,i},R>\\ \frac{n_{m,\mathrm{\&mu;}}}{\mathrm{\&gamma;}(s,a)},& j=<{\hat{n}}_{4,i,m},D_m>,n_m\&GreaterEqual;1,m\&NotEqual;i.\end{array}\right.---\left(11\right)$

图4给出了基于我们所提出的移动云计算网络动态云计算资源优化分配决策模型，N＝2时的状态转移图。

5)解出最大化的系统整体长期收益

由此，根据半马氏决策过程的定义(SMDP)，我们可以得到本发明所提出的基于SMDP的移动云计算服务域动态云计算资源优化分配模型的最大长期折扣收益为，

$v\left(s\right)=\underset{a\&Element;A\left(s\right)}{\max }\{z(s,a)+\mathrm{\&eta;}\underset{j\&Element;S}{\mathrm{\&Sigma;}}p\left(j\right|s,a)v\left(j\right)\}---\left(12\right)$

其中z(s，a)和p(j|s，a)已经分别在公式(8)，(10)与(11)中得到，v(j)表示系统在下一个状态j时所获得的整体长期收益。

6)找到最优化的决策

根据公式(12)所得到的最大系统收益，我们可以很容易的找到与该最大收益相对应的系统决策，该决策即为对当前移动云计算服务域动态云计算资源进行优化分配的最优化决策，而由所有移动云计算服务域动态云计算资源优化分配的最优化决策所组成的策略即为移动云计算服务域动态云计算资源优化分配模型的最优化决策策略。

根据步骤5)对事件采取每个行动后分别得到对应的长期收益，然后在这些长期收益里面，选择最大的那个长期收益相对应的行动(即拒绝云计算服务请求，或者为云计算服务请求分配云计算资源的VM个数)。

Claims (3)

1.一种基于SMDP的动态云计算资源优化分配方法，其步骤为：

1)云计算服务域系统将用户满意度划分为N类，满意度类别为i的用户对应分配的虚拟机VM数为k_i；其中，1≤k_i≤K，K为云计算服务域中的VM总数；

2)终端用户发送服务请求给云计算服务域，申请使用云计算服务；

3)云计算服务域系统根据接收的服务请求和当前云计算服务域状态建立一行动集合；其中，云计算服务域的状态s为s＝<n₁,n₂,…n_i,…n_N,e>，n_i为云计算服务域中满意度类别为i的用户数，e为云计算服务域内的事件，e∈{R,D₁,D₂,D_i….,D_N}，R为云计算服务请求，D_i为满意度类别为i的云计算服务完成并释放了其所占用的VM数；所述行动集合为 $A\left(s\right)=\left\{\begin{array}{c}-1,e\&Element;\{D_1,D_2,...,D_N\}\\ \{\mathrm{0,1},...i,...,N\},e=R\end{array}\right.,$ A(s)＝-1表示云计算服务结束运行并释放所占用云计算资源的状态，A(s)＝0表示云计算服务域拒绝云计算服务请求，A(s)＝i表示云计算服务域接收云计算服务请求并分配给这个云计算服务请求的云计算资源为k_i个VM；s表示云计算服务域的当前状态；

4)针对所述行动集合中的每一行动，计算云计算服务域的长期收益；

5)云计算服务域系统根据计算的长期收益确定是否接受当前服务请求，如果接受则选取长期收益最大的行动对应的VM资源分配方案为云计算服务请求分配VM；

其中，利用公式z(s,a)＝x(s,a)-τ(s,a)y(s,a)计算针对每一行动a的收益z(s，a)，x(s,a)是状态为s、选择的行动为a时，云计算服务域所获得的总收入，τ(s,a)表示在状态为s、选取的行动为a时，转移到下一个状态j所预期的服务时间；y(s,a)表示在状态为s、选取的行动为a时云计算服务域的支出； $x(s,a)=\left\{\begin{array}{cc}-1,& e=R,a=0\\ U\left(k_i\right),& e=R,a=i\end{array}\right.,$ U(k_i)为效能函数；β为两决策点之间连续时间下的折扣率，决策点是指任何一个事件e发生的时间点，τ₁是指从当前状态到下一个事件发生的状态所经历的时间；利用公式计算所述行动集合中的每一行动a时云计算服务域的长期收益ν(s)，p(j|s,a)为状态转移概率，j为移动云计算服务域的下一状态，γ(s,a)为事件发生的平均速率，S为云计算服务域所有的可能状态，v(j)表示下一状态j时所获得的整体长期收益。

2.如权利要求1所述的方法，其特征在于两个决策点之间的时间τ(s,a)服从指数分布，事件发生的平均速率γ(s,a)＝τ(s,a)^-1。

3.如权利要求1所述的方法，其特征在于采用一效能函数来度量云计算用户的满意度，将用户满意度划分为N类。