博弈式移动云服务协作资源管理模型研究

王小辉　李圣普　吕海莲

(平顶山学院计算机科学与技术学院　河南 平顶山 467000)



博弈式移动云服务协作资源管理模型研究

王小辉李圣普吕海莲

(平顶山学院计算机科学与技术学院河南 平顶山 467000)

对于实时要求高的移动云计算应用服务，高效的带宽和计算资源管理尤为重要, 而移动程序服务提供商们因各自拥有的资源有限，导致能够支持的程序实例的数量受限，其收入也不能有效提高。为了让移动程序服务提供商进行资源协作并有效提高收入，提出一种资源分配与合作博弈理论相结合的协作资源管理模型，由资源分配、收益管理、协作形成子模型构成。资源分配指导服务提供商投入合作的资源数量；结合了合作博弈理论的收益管理和协作形成模型用于公平划分合作所得收入与形成稳定的联盟。实验表明，服务提供商资源协作使用之后，合作联盟能够更加有效地利用现有资源，服务商的收入可提高5%以上。

移动云计算随机规划资源分配模型协作形成模型夏普利值纳什均衡

0　引　言

移动云计算成为融合智能手机、平板电脑和云计算的一个快速增长的新领域。移动云计算，继承了云计算技术到移动计算领域，为移动用户提供了一种新的技术。移动云计算通过减轻从移动设备到服务器之间的数据处理工作量，提高程序服务的性能，而程序服务是移动云服务提供商所提供的应用，运行在云端的数据中心服务器上，既可减少移动应用程序服务的执行时间，又能减少移动设备的能耗[1]。然而,移动应用程序的运行需要带宽和计算资源,并对其进行有效的管理，高效的资源管理方法必须最大限度地利用资源,从而达到移动云服务提供商的收入最大化[2-4]。

多个移动云服务提供商进行合作并创建一个资源池分享他们的资源。移动云计算资源共享问题，不仅要考虑可以提供无线访问的带宽，还要考虑提供数据处理功能的服务器计算资源[5,6]。移动云服务提供商进行合作，一个服务提供商不使用的资源, 在需要时,可被其他服务提供商使用，因此,资源利用率大幅度提高[7,8]，同时也增加移动云服务提供商的收入。然而,还存在一些资源管理相关的主要技术难题：

(1) 在移动应用程序池中，什么是最优的资源分配，能够达到收入的最大化并满足移动用户的需求?

(2) 移动云服务提供商合作后，如何公平合理地分享从资源池中获得的收入?

(3) 移动云服务提供商如果参加合作创建资源池, 每个服务提供商又应该向资源池中投入多少资源?

为确保实现高效的资源管理，综合研究移动云计算、资源管理和合作博弈理论[9,10]，提出一种移动云计算环境下的协作资源管理模型。

1　移动应用程序资源分配模型

该部分在简介移动云计算(MCC)基础上，首先提出线性规划(LP)资源分配模型，给供应商合作联盟的资源池中的移动应用程序合理地分配资源，但只能应用在系统参数确定的情况下。考虑系统参数的不确定性，接着提出随机规划(SP)模型，能够将相应的不确定情况转化为等价的确定性模型。

1.1移动云计算

移动云计算(MCC)的移动应用程序分为两个部分，即本地计算模块和远程计算模块。本地计算模块运行在移动设备上，远程计算模块运行在数据中心的计算服务器上。本地和远程计算模块间移动应用程序的数据传输的需要一个无线或有线的网络。无线网络提供移动设备、无线基站、应用程序服务器和计算资源(内存、CPU)之间的通信。在MCC环境中，当用户想要运行移动应用程序时，将通过无线和有线网络发送一个请求到应用服务器，应用程序服务器联系基站和数据中心获取带宽和计算资源。如果有足够可用的无线电和计算资源，用户就可以运行移动应用程。

MCC中的数据表示：假设一个服务地区MCC由无线基站覆盖，无线基站的覆盖的多个区域用集合A={1,2,…,A}表示，其中A是无线基站所覆盖的区域总数。基站的集合用B{1,2,…,B}表示,B是无线基站的总数。数据中心的集合用D{1,2,…,D}表示，D是数据中心的总数。应用程序的集合表示为P{1,2,…,P}，P是可用的移动应用程序总数。αa,b代表基站对用户的可用性，如果αa,b=1表示服务区域a的用户可以访问基站b，若αa,b=0，则相反。βa,d,p代表数据中心对用户的可访问性，如果βa,d,p=1表示服务区域a中使用应用程序p的用户可以访问数据中心d中的服务器，若βa,d,p=0，则相反。

1.2线性规划资源分配模型

该部分首先提出线性规划(LP)资源分配模型，给供应商合作联盟的资源池中的移动应用程序合理地分配资源，但只能应用在系统参数确定的情况下。考虑系统参数的不确定性，接着提出随机规划(SP)模型，能够将相应的不确定情况转化为等价的确定性模型。

线性规划模型可以用式(1)-式(7) 表示：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

xa,b,d,p≥0a∈Ab∈Bd∈Dp∈P

(7)

目标函数如式(1), 计算收益最大化时所能支持的应用程序实例的数量，支持所有地区所有基站和数据中心的用户应用程序，C是总收入、联盟的价值。式(1)的xa,b,d,p是区域a中用户，使用应用程序p连接到基站b，访问数据中心d的应用程序实例的数量，Vp是应用程序p的每个实例的收入。

式(5)确保区域a的用户可以访问基站b，αa,b是一个二进制常数表示区域a的用户是否可以访问基站b。在这种情况下,如果αa,b= 0，假定没有用户从区域a访问基站b。 M是应用程序实例的最大数量。同样,式(6)确保区域a中正在运行的应用程序p的程序实例能访问数据中心d的服务器。式(7)确保xa,b,d,p为非负数。

式(1)-式(7)中定义的线性规划模型的优化解决方案，用xa,b,d,p求解资源池中应用程序实例的最优数量，从提供这些应用程序的联盟的总收益最大化。注意，如果参数是随机的，可以将它们的实际值代入模型中。

1.3随机规划资源分配模型

(8)

其中：

(9)

受约束于：式(10)-式(14)：

(10)

(11)

(12)

xa,b,d,p≥ya,b,d,p,ϖa∈Ab∈ωBd∈Dp∈P

(13)

xa,b,d,p,ya,b,d,p,ϖ≥0a∈Ab∈Bd∈Dp∈P

(14)

类似于式(4)，式(12)确保应用程序实例的数量不超过用户的需求。式(13)确保xa,b,d,p必须大于或等于ya,b,d,p,ϖ。式(14)的确保决策变量是非负数。

为了获得SP模型的资源配置最优解，必须将式(8)-式(14)中原来的问题转换成等价的确定性问题。

确定性问题的形成：SP模型式(8)-式(14)中所涉及的随机变量ϖ可以转化为等价的式(15)-式(20)所表示确定性问题。

(15)

受约束于式(16)-式(20)：

(16)

(17)

(18)

xa,b,d,p≥ya,b,d,p,ωa∈Ab∈Bd∈Dp∈Pω∈Ω

(19)

xa,b,d,p,ya,b,d,p,ω≥0a∈Ab∈Bd∈Dp∈Pω∈Ω

(20)

约束式(16)-式(20)类似于式(10)-式(14)，唯一的区别是，随机变量,ϖ被场景ω所取代。

2　收益共享模型

当使用上一部分的线性规划模型、随机规划模型将资源分配到移动应用程序后，合作供应商联盟中的所有供应商将分享所支持应用程序实例产生的收入。在本节中，引入收益管理，应用合作博弈理论的核心和夏普利值理论来确定每个合作提供者应该得到的收入份额。

2.1基于核心理论的收益模型

首先定义共享收益的核心，c表示供应商的收入，核心可以定义如下:

(21)

然而，核心解决方案有许多局限性。核心集合可能是空的或者无限的。因此，夏普利值方案是优化的解决方案。

2.2基于夏普利值的收益划分

应用夏普利的相关理论，为联盟中的供应商们提供公平的利润划分，给定式(1)、式(15)、式(21)中的特征函数v(·)，根据资源分配模型中的方法，可得提供商的夏普利值如下:

(22)

从根本上讲，夏普利值φs(υ)决定了提供商S将能分享到的收入。夏普利值适用于合作供应商的收益管理是因为以下几点:

1) 效率：因为∑S∈Cφs(υ)-υ()，所有的合作供应商的收入的总和将达到最大化。

4) 不贡献，收获将为零：如果条件υ(S)=υ(S∪{s})适用于所有合作联盟⊆，则φs(υ)=0。也就是说：如果提供商S没有为联盟作出任何贡献，那么这个提供商能分享到的收入将是零。

3　协作形成模型

假定供应商是理性和自私的，通过组建合作联盟并创建资源池最大化自己的利益。此外，供应商可以决定投入资源池的资源容量(即产能扩张)。为了获得稳定的合作方案和，本节提出协作形成算法。

服务提供商协作形成的过程可描述为使用如下设定的不合作游戏。选手即服务提供商的集合是N，要参加协作联盟C要满足协议要求C⊆N。C代表相互协作的提供商所组成的集合。每个供应商的策略是建立与其他供应商的合作，该合作可表示为一个二进制变量cs,l。当cs,l=1时，则供应商间有合作，反之，cs,l=0，供应商间没有合作。因此，供应商S与其他所有供应商间的合作可以定义成式(23)。合作联盟C定义为式(24)。

Cs={(cs,1,…,cs,l-1,cs,l,cs,l+1,…,c)|

cs,l∈{0,1},l∈{s}}

(23)

(24)

提供商们合作形成的纳什均衡可以定义如下:

(25)

供应商之间的合作形成的纳什均衡可以从基于获得最好的反应动力学的算法得到。提供商将决定合作形成的迭代。ρ表示迭代序号，即ρ=1,2,3,…。cs(ρ)表示供应商S在迭代ρ中的策略。c-s(ρ-1)除了S的所有供应商在迭代ρ-1中的策略。在每个迭代中，提供商评估新战略，并选择新战略以实现最高收入。供应商S在迭代ρ中的策略cs(ρ)如下:

(26)

式中，在已知晓前面迭代中其他提供商策略c-s(ρ-1)的情况下，提供商S选择最好的新策略，即近视最好的回应。然而，在没有完整信息等情况下，会发生小概率的事件：提供商可能犯错或做出非理性的决定。

合作形成过程中的策略适应使用一个离散时间马尔可夫链[10]。A=∏s∈Ncs=c1×…×c|N|表示基于所有供应商所有可能合作的马尔可夫链有限状态空间。因其对称性，cs,l和cl,s是相等的。式(26)中cs(·)包含的合作供应商S的合作策略的，是状态κ的一部分，即κ∈A。让κ=(c1,1,…,cs,l,…,c|N|,|N|)，κ∈A成为当前状态。让κ=(c1,1,…,cs,l,…,c|N|,|N|)，κ′∈A成为下一个状态。提供商S由κ变化到κ′的合作状态集合可以定义如下:

(27)

状态κ到κ′的转移概率可以表示如下:

(28)

其中，λ表示提供商在一次迭代中更新自己策略的概率。提供商S在一次迭代中改变自己策略的概率定义如下:

(29)

其中，ψs(κ)为所有供应商策略函数中定义的收入。式(29)中，提供商可以选择能够产生更高收益的策略，即ψs(κ′)>ψs(κ)。然而，提供商有κ概率是非理性地改变其策略。

当提供商只有极少数非理性决策，即μ接近零，将会有一个随机的合作形成的稳定状态。让κ*和πκ*分别表示随机的稳定状态和状态κ*的固定概率，其中πκ*>0。随机的稳定状态也是马尔可夫链吸收的状态。因此，在随机的稳定状态下，供应商不能单方面选择达到更高收入的合作策略，这就是纳什均衡[10]。

4　实验仿真与性能评估

4.1实验思路和参数设置

协作资源管理模型应用于云服务提供商合作的3个环节：合作共建资源池、划分公共收益和调整资源投入。具体的实验思路与步骤如下：

步骤1应用程序资源分配模型子模型，应用在移动云服务提供商参加合作并共同创建资源池后， 其功能是解决资源池中资源的最优分配问题。即如何分配资源共享池中的带宽和计算资源，才能既满足用户的服务请求又达到资源池的收入最大化。此步运行在MCC环境的数据中心和服务器。

步骤2收益共享子模型，应用于共建资源池已产生收益后，其功能是把共建资源池所产生的收入如何公平合理的划分给参加共建的服务商。

步骤3协作形成子模型，应用于服务商共建资源池并已划分收益后。其功能是检验现在的合作联盟结构是否稳定，若稳定，就形成了商家对自己收益满意的联盟并持续下去，实验即可结束；若不稳定，就会有商家退出(或加入)联盟，或商家追加(或减少)资源投入，转至步骤1，重新对新的联盟结构进行运行(程序资源分配、收益划分、资源投入调整)。

因此，3个子模型是随着合作的向下推进而依次应用的过程。每个子模型解决一个合作环节中的问题，3个子模型合起来构成一个完整的合作过程的模拟。从合作共建资源池、划分公共收益、调整资源投入等环节可见，合作主要是以资源为主线的合作，实验重点在于分析合作过程中的3个子模型。

实验采用CloudSim平台，它是著名的云计算基础设施与应用服务的建模和实验工具。

根据1.1节中阐述的移动云计算环境的组成，实验所使用的移动云计算环境，假定有服务区域3个、供应商3个、移动云服务程序3个。如图1所示，3个服务提供商分别在3个服务区域(基站)提供3个移动应用程序服务。3个移动云服务程序，即语音识别、图像后期应用和视频应用。服务提供商需要在3个服务区域的基站和数据中心预定一定数量的带宽和服务器资源，才能保证移动服务程序的正常运行，设定移动云服务供应商1、2和3分别在每个基站预定的带宽为7、8、9 Mbps，同时分别在每个数据中心预定20、10、10台服务器。

图1　移动云计算环境

语音、图像和视频移动服务的带宽占用比例分析：运行3个移动云服务的合适带宽分别为3、2、4 Mbps。考虑到视频应用占用带宽连续时间较长，运行时要独占不小于4 Mbps的带宽；相对来说，语音识别和图像后期应用服务运行时，用户与服务器每次交互占用带宽时间较短，可相互交替使用带宽即共享带宽。这两个服务运行所需带宽不小于二者中较大的带宽3 Mbps即可，因此，对于服务商预定的7 Mbps带宽，视频服务独占4 Mbps才能满足运行需求，占总带宽的4/7。而语音与图像服务共享3 Mbps带宽即可满足运行需求，占总带宽的3/7。当然，服务商也可预定比7 Mbps更多的带宽，来满足更多的用户请求。

3个移动云服务的资源需求与收益分别是：语音识别应用程序需要平均带宽3 Mbps，服务器利用率22%，运行该应用程序每个实例的收入为5货币单位(MUs)。图像后期应用程序需要平均带宽2 Mbps和服务器利用率28%，并产生收入6 MUs，视频应用程序需要平均带宽4 Mbps和服务器利用率45%，并产生收入8 MUs。应用程序响应失败的惩罚成本分别是5.1、6.1和8.1 MUs。

4.2仿真结果与分析

实验结果与分析主要包含两部分内容：

第一部分：资源分配与收益管理模型的实验分析。主要分析可用带宽和服务器资源的变化对服务提供商收入的影响，如图2-图4所示。

图2　不同带宽条件下的LP、SP模型中服务提供商合作前后的收入对比

图3　不同计算资源条件下LP、SP模型中服务商合作前后的收入对比

图4　SP模型中3个服务提供商协作前后的收入(含罚金)对比

第二部分：协作形成模型的实验分析。分析和计算不同联盟结构中的供应商收入，并最终确定稳定的联盟结构。

4.2.1资源分配与收益管理模型的实验分析

根据不同的带宽资源分配情况，图2显示应用了LP、SP模型的供应商合作前后的收入对比，主要是由于供应商间的协作，提高了收入5%以上，原因是供应商可以彼此有效利用对方的可用资源，从而提高了资源利用率。如图2所示,当供应商2的带宽增加,不仅是提供商1将受益于访问提供商2的额外带宽，相互地，提供商2也可以利用提供者1的计算资源。另一方面,如果没有合作,这样的资源共享将是不可能的。因此, 当供应商2可用带宽的增加时供应商1的收入不受影响；同时，供应商2由于计算资源的大量使用，收入增长很快。

根据不同的服务器资源分配情况，图3显示应用了LP、SP模型的供应商合作前后的收入对比。在图3中，没有合作时，随着可用服务器数量的增加，提供商1的收入保持不变,而供应商2的收入增加；参加合作后，供应商1和供应商2收入都增加,同样的原因，供应商2收入的增加源于利用提供商1的空闲服务器资源，供应商1收入的增加源于分享资源池中的收入。

图4是视频应用服务基于SP模型的资源分配过程的处罚实例。当因不能及时响应所支持应用程序实例而罚金增加时，供应商的收入减少,因为他们必须在没有可用资源的完整数据时做出决定。然而,供应商们相互协作后的收入要高于没有合作时的收入。

4.2.2协作形成过程的实验分析

表1　不同联盟结构中服务商的收入情况

5　结　语

在移动云计算环境中，运行程序服务的手机、平板等移动设备和服务器之间的通信需要无线带宽和服务器端的计算资源，而提供资源的服务提供商资源有限，必须相互协作以达到收益最大。经过实验仿真表明，本文提出的移动云计算环境下的服务提供商协作资源管理模型，应用于程序服务运行资源分配、收益划分、协作形成环节可使服务商形成稳定的合作联盟并有效提高收入。

[1] Kumar K,Lu Y.Cloud computing for mobile users:Can offloading computation save energy?[J].IEEE Comput,2010,43(4):51-56.

[2] Aljabari G,Eren E.Virtualization of wireless LAN infrastruc-tures[J].Intelligent Data Acquisition and Advanced Computing Systems(IDAACS),2011,9(1):837-841.

[3] Kumar K,Liu J B.A Survey of Computation Offloading for Mobile Systems[J].Mobile Networks and Applications,2013,18(1):129-140.

[4] Rahimi M R,Ren J.A Survey,State of Art and Future Directions[J].Mobile Networks and Applications,2014,19(2):133-143.

[5] Kemp R,Palmer N.A Computation Offloading Framework for Smartphones[J].Mobile Computing,Applications,and Services,2012,76(1):59-79.

[6] Shiraz M,Gani A.A lightweight active service migration framework for computational offloading in mobile cloud computing[J].The Journal of Supercomputing,2014,68(2):978-995.

[7] Zhang X W,Kunjithapatham A.Towards an Elastic Application Model for Augmenting the Computing Capabilities of Mobile Devices with Cloud Computing[J].Mobile Networks and Applications,2011,16(3):270-284.

[8] Wei G,Vasilakos A V.A game-theoretic method of fair resource allocation for cloud computing services[J].The Journal of Supercomputing,2010,54(2):252-269.

[9] 严翔,李洪波,王立德,等.基于粒子群优化算法和博弈论的网络学习控制系统带宽调度[J].北京科技大学学报,2014,36(7):979-985.

[10] 解亚男,马斌,王长涛,等.基于合作博弈的CPS通信资源分配算法[J].现代电子技术,2014,36(20):20-24.

RESEARCH ON COLLABORATIVE RESOURCE MANAGEMENT MODEL IN MOBILE CLOUD COMPUTING BASED ON GAME THEORY

Wang XiaohuiLi ShengpuLü Hailian

(SchoolofComputerScienceandTechnology,PingdingshanUniversity,Pingdingshan467000,Henan,China)

For mobile cloud computing application services with high real-time requirement, the efficient bandwidth and computing resources management are particularly important. While the number of application examples capably supported by the mobile application services providers is limited because of the limited resources possessed by them respectively, their revenue cannot increase effectively either. In order to make the these providers be available in resources collaboration and effectively increase their revenue, we propose a collaborative resources management model which combines the resource allocation and the cooperative game theory, it consists of the sub-models of resource allocation, income management and collaboration formation. The resources allocation provides guidance to service providers for the number of resources invested into cooperation; the model combines the income management of cooperation game theory and the collaboration formation model and uses them in fairly dividing the revenues of cooperative earnings and forming stable coalition. Experiment indicates that with the use of resources collaboration between services providers, the cooperation coalition can more effectively utilise the existing resources and the income of them increases 5% and higher.

Mobile cloud computingStochastic planningResources allocation modelCollaboration formation modelShapley valueNash equilibrium

2014-10-29。河南省重点科技攻关项目(142102210 225)。王小辉，讲师，主研领域：人工智能及应用。李圣普，讲师。吕海莲，教授。

TP393

A

10.3969/j.issn.1000-386x.2016.08.072