基于非完全信息博弈的云资源分配模型

苑　迎　王翠荣　王　聪　任婷婷　刘冰玉

1(东北大学信息科学与工程学院　沈阳　110819)2　　　(东北大学秦皇岛分校　河北秦皇岛　066004)(yuanying1121@gmail.com)



基于非完全信息博弈的云资源分配模型

苑迎1,2王翠荣2王聪2任婷婷2刘冰玉2

1(东北大学信息科学与工程学院沈阳110819)2(东北大学秦皇岛分校河北秦皇岛066004)(yuanying1121@gmail.com)

摘要针对云环境下相互竞争的多租赁市场运营模式，以提高资源供求双方利益及资源能效为目标，提出了一种基于非完全信息博弈的云资源分配模型.首先利用隐Markov理论根据服务提供商(service provider, SP)的历史资源需求情况预测其当前出价，以预测值为基础构建动态博弈定价模型，激励服务提供商选择符合整体利益的最优购买出价策略，从而实现利益最大化；然后设计了支持多服务提供商、多种资源同时分配，以分类资源单位价格进行分配的资源分配模型，保证了基础设施提供商(infrastructure provider, INP)的收益最优.仿真实验表明：在博弈定价模型中，预测价格与实际交易价格相近且交易价格低于实际估值，能够保障服务提供商的利益；基于不同种类资源单价的分配模型能够增加基础设施提供商的收益.

关键词云计算；虚拟化；资源分配；非完全信息博弈；隐马尔可夫预测

近年来，云计算技术的兴起为整个IT行业带来了划时代意义的变革，使得人们可以直接通过网络获得服务和计算资源.云计算带来的最大好处就是IT资源的按需分配，这将极大提高资源利用率并降低IT行业的运营成本.这样灵活使用资源的前提就是虚拟化技术的应用，包括CPU、内存、存储、网络等一系列IT硬件资源的虚拟化[1].在网络虚拟化环境下，传统的互联网服务提供商(Internet service provider, ISP)被划分为基础设施提供商(infrastructure provider, INP)和服务提供商(service provider, SP)[2].

因此，虚拟资源的高效、合理租赁问题是云计算研究的关键问题，在硬件虚拟化技术成熟后开始受到越来越多的关注.现有的虚拟资源管理研究内容主要集中在虚拟资源的部署和租赁交易方式2个方面.前者以硬件资源利用率为目标，研究如何在有限的硬件资源上尽可能满足更多的用户，为用户直接进行资源分配并创建虚拟网络，属于虚拟网络映射问题(virtual network embedding, VNE)[3]；后者更加宏观研究云市场竞争的多租赁环境下INP和SP之间的供求关系，以最大化社会整体利益为目标，并保证公平、高效的竞争环境.目前已有的研究方法通常借鉴经济学领域内的拍卖理论模拟云环境下的资源租赁市场，激励参与者选择合理的成交价格以获得符合最优整体利益的均衡策略.但是云环境下的资源是多样化的，包括处理器、存储、带宽等，这样包含多维资源的拍卖特别是组合拍卖的净胜标问题通常属于NP-Hard问题.另外，拍卖中采用的统一资源定价方案简单地将用户出价除以全部资源需求量以获得平均单位资源价格，这样的机制在激励效果和公平性上存在问题.

本文提出了1种基于非完全信息博弈的云资源分配模型.考虑到云市场多租赁环境下服务提供商之间存在竞争关系，他们不可能公开自己的实际出价，因此利用隐Markov模型，根据服务提供商的历史资源需求情况预测其当前出价.根据预测的出价构建动态博弈定价模型以激励服务提供商选择符合整体利益的最优购买出价策略，从而实现利益最大化.然后设计支持多服务提供商、多种资源同时分配的分配算法，根据不同种类资源分别出价进行资源的分配以最大化基础设施提供商的利益.

1相关工作

资源分配问题是当前Internet面临的重要挑战，特别是在云计算这样的大规模分布式环境下，资源的合理、高效分配问题在近2年成为研究者关注的重点问题[4].因此，当前云资源特别是作为云基础设施的数据中心资源的利用率低下问题，一直是研究界和业界致力于解决的重点问题.

云资源分配问题的研究可划分为2个方向：1)以最大化资源利用率为目标，根据用户具体需求(每个虚拟网络所需要的CPU、带宽、存储等资源)的描述，将基础设施提供商的硬件资源尽可能多地分配以提高资源利用率[5-6]，这样的解决方式是集中式的，需要完整全局信息才能实现.2)以最大化收益为目标，这部分的研究内容细分为最大化整体收益和最大化基础设施提供商收益等不同目标.研究方法通常借鉴经济学领域的拍卖和博弈理论构建模型.第1个方向属于虚拟网络映射问题，第2个方向是从宏观角度考虑的资源分配问题.考虑到云市场的运营机制，在服务提供商和基础设施提供商之间的分配应更侧重经济利益，而服务提供商及其用户之间的分配应更侧重于效率.

Fig. 1　Structure of the cloud resources allocation model based on uncompleted information game.图1　非完全信息博弈的云资源分配模型结构图

文献[7]提出了一种基于拍卖的公平资源分配框架，但是该框架是以单个服务提供商的最小花费为目标的，应用到多服务提供商竞争的环境下不能获得全局最优的资源分配策略.文献[8]引入博弈论解决网络资源分配，该分配方案中未考虑基础设施提供商提供资源的有限性问题且仅考虑了带宽资源并未考虑计算资源的分配.文献[9]基于随机整数规划设计了云资源优化分配模型，将整体分配问题拆分成可以并行解决的若干子问题以提高求解效率，模型考虑了价格不确定性问题，用样本均值逼近方法进行解决，但由于采用集中式算法，该模型在用户规模较大时效率不高.文献[10]针对多基础设施提供商和多服务提供商竞争环境中虚拟网络资源分配的特点，从服务管理的角度基于组合双向拍卖理论提出了多个基础设施提供商和多服务提供商竞争的虚拟网资源分配模型，但是在传统组合拍卖中，根据均价进行排序的方式在不同种资源价格差异较大时无法获得最优方案.文献[4]基于反向拍卖设计了3种云资源交易模型：C-DSIC，C-BIC和C-OPT.其中，C-DSIC也是基于Vickrey拍卖的，具有分配效率和个人理性，但不是预算平衡的；C-BIC不是个人理性的，但是具有分配效率和预算平衡且购买开销也小于D-DSIC；C-OPT模型在净胜标确定和支付规则上不同于前两者，而是采用了虚拟动态定价机制，这点在云资源分配中非常重要，它使得C-OPT更适用于云资源分配时用户需求分布不同的情况，更符合实际情况.在传统资源分配方式中，由资源提供者定价的机制只关注资源提供者的利益，忽略了用户的收益[11]，而动态定价可以提高用户收益，加速资源提供者竞争的健康性并且可以提高云资源利用率[12]，因此在资源分配模型中加入动态定价机制是很有必要的.

上述研究存在4点不足： 1)部分研究仅解决单个服务提供商向基础设施服务商申请资源时如何创建公平的交易环境并得到较高的经济收益和效用，在用户规模过大时每次仅与一个服务提供商的交易模式效率过低；2)部分算法只针对单种资源进行分配，云环境下的资源种类更加多样化，并且服务提供商对于每种资源的估价、用量存在差异，能够同时分配多种资源的算法才更符合实际需求；3)已有的能够支持多服务提供商资源分配技术的研究大都基于组合拍卖，致力于提高市场竞争公平性和最大化收益等，但忽略了服务提供商自身客观存在的非合作的行为，另外，组合拍卖中根据不同种资源均价排序分配的方式在价格差异较大时缺乏公平性；4)在资源分配中使用动态定价机制有助于构建更合理、高效的交易机制，但采用集中式的定价算法效率不高，需设计更加高效的定价机制.

2基于非完全信息博弈定价模型

2.1基于HMM的服务提供商单位资源出价预测

如图2所示，隐Markov模型是在Markov的基础上发展起来的，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由1个具有相应概率密度分布的状态序列产生，因此隐Markov模型是1个双重随机过程：系统状态变化的随机过程和由状态决定输出的随机过程.当系统中表层事件可能是由低层事件引发而产生时，隐Markov模型能够有效地解决这类问题，因此本文将HMM理论应用到SP单位资源出价的预测上，利用已知的任意SP的历史资源请求序列(观测值)，预测下一轮分配中该SP对于单位资源的出价(隐含状态).

Fig. 2　Structure of HMM model.图2　隐Markov模型结构

SP根据观测到其他竞争者资源请求的记录以及下一时刻的资源请求数量vt+1，预测出其最有可能的出价,即首先计算条件概率p(Xt+1=qj|Ot+1=vt+1).

由贝叶斯公式可知：

p(Xt+1=qj|Ot+1=vt+1)=

(1)

(2)

令p{Xt+1=qj,Ot+1=vt+1}=αt+1(qj,vt+1)，则

(3)

由已知：

p(Xt+1=qj|Xt=qi)=aqiqj，

p(Ot+1=vt+1|Xt=qi)=bqivt+1，

代入式(3):

(4)

根据式(4)可以计算出αt+1(qj,vt+1)，将结果代入到式(1)可以得到SP所有可能的出价的概率，选取出概率最大的qj进行竞价.

目前，尚未有研究将隐Markov模型应用于云资源分配，而隐Markov模型在语音识别、基因关联分析和基因识别、文字识别及股市预测等领域取得了重大成功.因此，本文将其应用到对SP出价的预测上，进而在预测价格的基础上构建非完全信息动态博弈定价模型，根据当前市场状态迅速、灵活地确定价格使其达到利益的最优化，获得纳什均衡解.

2.2服务提供商博弈定价模型

当SP采用HMM获得其他SP所请求的CPU、带宽和存储资源的预测价格后，本文采用动态博弈定价的方法获得其自身稳定均衡的出价.在动态博弈定价中SP采用文献[14]提出的方法确定投标策略，即极大化Cobb-Douglas效用函数：

(5)

(6)

(7)

(8)

(9)

将式(7)(8)(9)代入式(6)得任意SP的期望收益即效用函数,化简得：

(10)

定理1. 当

时，各服务提供商的期望收益在合理的策略集上可以达到最优，系统存在纳什均衡解.可进一步放宽约束：如果SP对于商品出价的策略集合为大于1的有限正整数集合时，系统存在纳什均衡解.

D=E=F=0.

根据文献[15]关于3元函数极值的充分条件：当

(11)

时，式(6)存在极大值.进一步放宽约束，令SP对于所请求资源出价的策略集合为大于1的有限正整数集合时，系统此时存在纳什均衡且其均衡解落于给定的SP策略集合中，是合理可行的均衡策略，因此式(6)给出的SP之间的博弈存在纳什均衡解.

证毕.

定理2. 本文提出的基于预测定价的博弈系统是激励相容且个人理性的.

证明.

1) 激励相容性.在SP个人理性出价且其个人利益不受到损失的同时，使得其他SP的收益也有所增加，各SP出价能够达到一种均衡出价状态s*.

2) 个人理性.每个SP的出价行为也要符合个人理性约束，即效用都为正.

对于获得资源量为0的SP来说(在本文的分配算法中，资源紧张时有可能有些SP无法获得资源)，其收益可看作是0.对于参与交易(即分得资源)的SP来说，讨论式(6)的可能取值范围，以CPU资源为例，其实际估值与交易价格之差为

因为对于交易价格来说，实际估值和预测价格不可能为负值，显然有

证毕.

由上面的推导和证明可以看出使用HMM预测价格为最终的博弈提供了合理的理论依据；非完全信息博弈理论也使本模型可以形成稳定的纳什均衡解，且本文提出的基于预测定价的博弈系统是激励相容且个人理性的最优化系统收益.

3基于各类资源分别定价的云资源分配模型

本节主要介绍图1下半部分的云资源分配模型，首先举例说明传统云资源分配模型中，基于各类资源均价的净胜标确定手段[10]缺乏公平性，然后对资源分配问题进行建模，进而给出基于贪心算法的资源分配算法.

3.1传统云资源分配净胜标确定问题分析

以1个简单的例子来分析组合资源分配过程中以各类资源的平均价格作为SP排序依据进行资源分配所产生的错误激励机制.设请求资源包括CPU、带宽和存储3类资源，2个SP申请资源分配的数据如下：

SP1所请求的组合资源包为o1=1,2,4，组合资源包的单价为x1=15,3,5，由o1和x1得到组合资源包的平均价格为

SP2所请求的组合资源包为o2=2,1,4，组合资源包的单价为x2=12,2,4，由o2和x2得到组合资源包的平均价格为

很明显，SP1各类资源的单价都比SP2高，从经济学角度分析，SP1应比SP2更具有竞争力；但是由于SP1的平均价格要比SP2的平均价格低，这样在传统的组合资源分配中SP1就排在了SP2的后面.由此可见，传统云资源分配模型中基于各类资源均价的净胜标确定手段缺乏公平性，将导致INP收益无法达到最优，其激励效果有可提高的空间.

3.2云资源分配模型及求解算法

本文考虑的资源分配环境是1个INP可以同时满足多个SP需求的情况，SP为1组资源的组合与INP进行交易.将云资源分配模型形式化为1个四元组A=K,X,O,C，其中K为S个SP的集合，K={k1,k2,…,kS}；X={x1,x2,…,xS}为SP所提交的价格集合，∀xi，xi=表示服务提供商SPi对CPU、带宽和存储资源的出价；O={o1,o2,…,oS}为SP所请求的各类资源的组合需求，∀oi,oi=表示服务提供商SPi对各类资源的需求量；C=cCPU,cBW,cStorage为INP所拥有的CPU、带宽和存储的资源.以最大化INP收益为目标，资源分配模型可以表示为

(12)

其中，δi∈{0，1}.

尤其需要注意的是：为了保证更好的公平性，应当在资源分配的过程中采用各类资源分别定价、统一判断净胜标的机制，以提高激励效果；另外，在动态定价之后的资源分配步骤中也需要着重考虑效率问题，因此INP应一次性将可分配的资源分配给获胜的若干SP，而不是为单独的资源进行多次分配.

考虑到上述2点，本文利用贪心算法对云资源分配模型进行求解，设计了CVSA-UPV算法.该算法以分类单位资源价格向量的长度作为贪心选择标准，按分类单位资源价格向量的长度对SP进行排序，并采用贪心算法分配资源以达到最大化INP收益的目的.这样有效地避免了传统的组合资源分配过程中以各类资源的平均价格为SP进行排序所产生的定价误差和形成错误的激励机制且资源分配结束后系统收益最大.下面对CVSA-UPV算法进行详细介绍.

算法1. CVSA-UPV资源分配算法.

输入：SP定价策略及资源需求、INP最低价格；

输出：资源分配方案.

①S个SP将通过非合作动态博弈定价策略获得的自身对组合资源包中各类资源的竞拍出价xi=和自身的资源需求oi=提交给拍卖代理；

② INP将各类资源交易的最低价格提交给拍卖代理；

③ 拍卖代理根据INP提交的最低价格确定参与资源分配的SP；

⑥ 从排列好的SP列表中第1个SP开始，计算其各类资源需求量，如果均满足则分配资源；

⑦ 当出现1个组合包内的3类资源需求不能同时被满足时，从列表中选取下一个SP进行分配，直到INP中的1类资源数为0或者SP列表被完全遍历.

4性能分析与评估

模拟实验首先对资源分配算法中隐Markov预测的可行性以及适用性进行了分析,然后分别对本文提出的CVSA-UPV算法和传统的各类资源不分别定价的分配算法进行比较.实验在Matlab仿真环境下实现，思路是通过编写仿真程序模拟拍卖过程，通过拍卖样本数据对HMM模型进行训练从而获得收敛的模型；然后在后续模拟拍卖过程中测试本文提出的算法在资源估价准确度、基础设施提供商收益及资源单价定价方案等方面的性能.

实验 1. 首先对SP的实际估值、交易价格与预测价格进行比较.本文假设SP请求的组合资源包括CPU、带宽和存储3类资源，价格的单位采用vrc(virtual resource currency)表示，CPU的单位资源价格在2～20 vrc之间，带宽的单位资源价格在8～40 vrc之间，存储的单位资源价格在1～10 vrc之间.本文使用式(13)～(15)来描述SP对基础设施供应商资源的实际估值[16]：

(13)

(14)

(15)

Fig. 3　Comparison of actual price, auction price andpredicted price by HMM for CPU, bandwidth and storage.图3　CPU、带宽和存储资源的实际估值、交易价格与预测价格的比较

从图3可以看出，在本文提出的非合作博弈定价模型中，SP的交易价格与其实际估值趋势相同，在实际估值的下方波动且波动幅度较小.根据收益计算公式，显然每个SP的收益非负，因此该博弈模型是符合个人理性的并能反映市场实际情况.另外，通过隐Markov模型获得的预测价格围绕着交易价格波动且幅度较小，充分说明隐Markov预测模型的有效性且具有较好的适应性.

实验2. CPU、带宽和存储的各个参数设置与实验1相同，实验中INP拥有各类资源数量分别设定为10，20，30，40，50，60，70，80，90，100，SP的个数S=15，30，50.比较了本文提出的CVSA-UPV算法与传统组合拍卖中根据均值进行分配2种方式的收益情况，结果如图4所示.从图4可以看到当SP个数相同时，基于CVSA-UPV算法比传统组合拍卖中根据均值进行分配的算法CVSA-MV的收益要高；随着SP数量的增多，2种分配算法的收益都逐步增加，说明算法符合实际市场规律；随着INP所拥有的资源数的增加，基于CVSA-UPV算法比传统组合拍卖中根据均值进行分配的算法的收益增加得明显，这说明本文的算法有较好的激励机制，使得INP的单位资源效用增大.

实验3. CPU、带宽和存储的各个参数除单位资源价格外设置与实验1相同，实验中共有30个SP，进行20次实验.图5中的实验结果为所有SP各类单位资源价格方差的均值取0，0.66，43.8，91.02，203.58时，本文提出的CVSA-UPV算法与传统组合拍卖中根据均值分配的算法CVSA-MV对INP单位资源的效用进行比较.实验中假定CPU和存储的价格保持在6～10之间，逐步提高带宽的价格.当各类资源的单价均相同分别取8，9，10时，分配资源的单价的平均值为第1簇柱状图.从图5可以清楚地看出采用2种算法得到的各类资源单价是相同的.当各类资源的单价相差很小且均匀分布在8～10时，分配各类资源的单价的平均值为第2簇柱状图.2种算法得到的各类资源单价的差值较小.随着各类单位资源价格方差的增大，采用CVSA-UPV算法获得的带宽的单价明显高于采用传统组合拍卖中根据均值进行分配的算法，且2种算法获得单价的差值逐步增大.从实验数据可以看出，当INP的资源有限且各类资源单价相差很大时，采用CVSA-UPV能有效提高INP单位资源的价格，使其获得较高的收益，能够使出价高的SP更具有竞争力，因此更符合市场的竞争规律.

Fig. 4　Profit of infrastructure provider.图4　基础设施提供商的收益

Fig. 5　Comparison of the unit price of different kinds ofresources.图5　基础设施提供商销售各类资源单价的比较

5结束语

本文针对云环境下相互竞争的多租赁市场运营模式，提出了1种基于非完全信息博弈的云资源分配模型.考虑到云市场多租赁环境下SP之间存在竞争关系，他们不可能完全信息共享，因此将隐Markov模型应用到对SP出价的预测上，根据SP的历史资源需求情况预测其当前出价.在预测价格的基础上构建非完全信息动态博弈定价模型，根据当前市场状态迅速、灵活地确定价格使其达到利益的最优化，获得纳什均衡解，从而实现利益最大化.设计了支持多SP、多种资源同时分配，以分类单位资源价格进行分配的资源分配模型，保证了INP的收益最优.仿真实验表明：在博弈定价模型中，预测价格与实际交易价格相近且交易价格低于实际估值，能够保障SP的利益；基于各类资源分别定价的分配模型能够增加INP的收益.

参考文献

[1]Zhang Sheng, Qian Zhuzhong, Wu Jie, et al. Virtual network embedding with opportunistic resource sharing[J]. Parallel and Distributed Systems, 2014, 25(3): 816-827

[2]Rahman M R, Aib I, Boutaba R. Survivable virtual network embedding[G] //LNCS 6091: Proc of the 9th Int Networking Conf on IFIP TC 6. Berlin: Springer, 2010: 40-52

[3]Yu Minlan, Yi Yung, Rexford J, et al. Rethinking virtual network embedding: Substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29

[4]Prasad A S, Rao S. A mechanism design approach to resource procurement in cloud computing[J]. IEEE Trans on Computers, 2014, 63(1): 17-30

[5]Ghazar T, Samaan N. Pricing utility-based virtual networks[J]. IEEE Trans on Network and Service Management, 2013, 10(2): 119-132

[6]Rahman M R, Boutaba R. SVNE: Survivable virtual network embedding algorithms for network virtualization[J]. IEEE Trans on Network and Service Management, 2013, 10(2): 105-118

[7]Zaheer F E, Jin Xiao, Boutaba R. Multi-provider service negotiation and contracting in network virtualization[C] //Proc of Network Operations and Management Symp (NOMS). Piscataway, NJ: IEEE, 2011: 471-478

[8]Trinh T, Esaki H, Aswakul C. Quality of service using careful overbooking for optimal virtual network resource allocation[C] //Proc of the 8th IEEE Int Conf on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON). Piscataway, NJ: IEEE, 2011: 296-299

[9]Chaisiri S, Lee B S, Niyato D. Optimization of resource provisioning cost in cloud computing[J]. IEEE Trans on Services Computing, 2012, 5(2): 164-177

[10]Zhang Shunli, Qiu Xuesong, Cheng Dongdong, et al. A virtual network resource allocation mechanism for network virtualization[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(6): 24-27(张顺利, 邱雪松, 陈东东, 等. 网络虚拟化环境中虚拟网资源分配机制[J]. 北京邮电大学学报, 2011, 34(6):24-27)

[11]Ridder F, Bona A. Four risky issues when contracting for cloud services, 1543314[R/OL]. 2011[2015-01-12]. http://www. gartner. com/id

[12]Mihailescu M, Teo Y M. Dynamic resource pricing on federated clouds[C] //Proc of the 10th IEEE/ACM Int Conf on Cluster, Cloud and Grid Computing (CCGrid). Piscataway, NJ: IEEE, 2010: 513-517

[13]Rabiner L. A tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE, 1989, 77(2): 257-286

[14]Liu Shulin, Wang Mingxi. Sealed-bid auctions based on Cobb-Douglas utility function[J]. Economics Letters, 2010, 107(1): 1-3

[15]Meng Yiping. Sufficient condition for extreme value of three variables function[J]. Jounal of Jiangsu of Science and Technologe: Natural Science Edition, 2010, 24(5): 511-513 (in Chinese)(孟义平. 三元函数极值的一个充分条件[J]. 江苏科技大学学报: 自然科学版, 2010, 24(5): 511-513)

[16]Li Mingchu, Xu Lei, Sun Weifeng. Grid resource allocation model based on incomplete information game[J]. Journal of Software, 2012, 23(2): 428-438 (in Chinese)(李明楚, 许雷, 孙伟峰. 基于非完全信息博弈的网格资源分配模型[J]. 软件学报, 2012, 23(2): 428-438)

Yuan Ying, born in 1981. PhD, lecturer in the School of Computer Center, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include virtual network embedding, virtual resource allocation in cloud computing.

Wang Cuirong, born in 1963. PhD, professor in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include routing protocol, network security and sensor networks (wcr@mail.neuq.edu.cn).

Wang Cong, born in 1981. PhD. Lecturer in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Member of China Computer Federation. His main research interests include virtual network embedding, resource allocation in data center (congw1981@163.com).

Ren Tingting, born in 1984. PhD candidate. Lecturer in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Her main research interests include investment efficiency of cultural industry and the governance effect of non-efficiency investment (358568169@163.com).

Liu Bingyu, born in 1978. PhD candidate. Lecturer in the School of Economies and Business, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include data mining and community discovery (liuby78@163.com).

An Uncompleted Information Game Based Resources Allocation Model for Cloud Computing

Yuan Ying1,2, Wang Cuirong2, Wang Cong2, Ren Tingting2, and Liu Bingyu2

1(CollegeofInformationScience&Engineering,NortheasternUniversity,Shenyang110819)2(NortheasternUniversityatQinhuangdao,Qinhuangdao,Hebei066004)

AbstractConsidering the competing characteristics under multi-tenant environment in cloud computing and aiming to improve the profit of both the resource supply and demand sides, an uncompleted information game based cloud resource allocation model is proposed. Firstly, a hidden Markov model (HMM) is introduced to predict the current bid of service providers based on the historical resource demand. Then a game model for dynamical pricing is established base on the predicted bid value. It can motivate service providers to choose the optimal bidding strategy in accordance with overall interests and so as to achieve maximum benefits. Finally, a resource allocation model on the basis of unit prices of different types of resources is put forward to guarantee optimal gains for infrastructure provider (INP). The allocation model can support synchronous allocation for both multi service providers and various resources. Simulation results show that, in the pricing game model, the predicted price is close to the actual transaction price which is lower than the actual valuation, so it can guarantee the profit of service providers; the resource allocation model can simultaneously increase infrastructure provider’s revenue.

Key wordscloud computing; virtualization; resource allocation; uncompleted information game; hidden Markov prediction

收稿日期：2015-01-22；修回日期：2015-05-21

基金项目：国家自然科学基金项目(61300195,61402094)；河北省自然科学基金项目(F2014501078, F2016501079)；辽宁省教育厅科学研究一般项目(L2013099);河北省科技计划项目(15210146)；秦皇岛市科技计划项目(201401A028)；东北大学秦皇岛分校校内基金项目(XNB201607)

中图法分类号TP393.02

This work was supported by the National Natural Science Foundation of China (61300195,61402094), the Natural Science Foundation of Heibei Province of China (F2014501078,F2016501079), the General Project of Liaoning Province Department of Education Science Research (L2013099), the Technology Planning Project of Hebei Province (15210146), the Science and Technology Research Project of Qinhuangdao (201401A0289), and the School Foundation of Northeastern University at Qinhuangdao (XNB201607).