混合云用户计算工作量分解的博弈分析研究*

马小龙（1.上海财经大学　信息管理与工程学院，上海　200433；2．湖州师范学院　商学院，浙江　湖州　313000）

混合云用户计算工作量分解的博弈分析研究*

马小龙1，2
（1.上海财经大学信息管理与工程学院，上海200433；2．湖州师范学院商学院，浙江湖州313000）

在混合云计算环境下，如何合理地划分工作量是每个理性的用户所需要考虑的问题。构建了混合云计算工作量分解博弈模型，在用户通常考虑响应时间的情况下把花费也纳入考虑，即将以响应时间和花费为变量的函数作为效用函数，通过求解纳什均衡的方法分析用户的策略行为，从而决定用户的最优策略。通过仿真给出了不同响应时间和花费比率对用户均衡策略的影响并做出了比较分析。

混合云；工作量分解；博弈；纳什均衡

0　引言

云计算服务作为一种新型的商业计算服务逐渐成为企业和个人用户计算应用的主要方式，如亚马逊的EC2、谷歌的AppEngine及微软的Azure等云平台［1］。随着云计算的兴起，近几年来云计算用户稳定增长。根据美国国家标准与技术研究院（NIST）的定义，云计算服务模式可分为基础设施即服务（IaaS）、平台即服务（PaaS）及软件即服务（SaaS）［2］。云计算发展至今，云服务方式出现了公有云、私有云、混合云等，混合云是由公有云和私有云组成的。公有云平台是整合自己的资源为第三方提供服务的计算平台，私有云平台则是整合企业内部的资源为企业自己服务的云计算平台，而混合云平台则是指整合公有云和私有云共同为用户提供服务［3］。随着云计算技术的发展，由公有云和私有云共同组成的混合云是未来发展的趋势。在Ganter对全球270家企业的调查中，有46％的企业决策者考虑基于现有自建方案进行云协作应用的延伸部署计划，这说明混合云将成为相当一段时间内的主流模式。

目前云计算一般有两种类型的分析：性能类型分析和市场类型分析［4］。性能类型分析以“最优化”执行性能为目标，例如针对响应时间性能，通常不会考虑花费；而市场类型分析就要考虑花费的因素。用户通过提交工作量到公有云上能很好地降低工作量的响应时间，从响应时间角度能够提高用户的效用水平，但同时公有云是按用户的消费量收费的，从用户的花费角度降低了用户的效用水平。当用户急需缩短处理任务的响应时间时，用户愿意缴纳费用来获得更好的效用水平，而随着响应时间的逐步缩短，用户对执行单位工作量愿意的花费逐渐减小，因此在考虑响应时间和花费的情况下，用户如何做出合理的工作量分解决策正是本文研究的问题。

本文把响应时间和花费纳入考虑，建立了混合云工作量分解博弈模型，通过求解纳什均衡的方法给出用户的最优任务分解决策。本文首先对相关工作进行了综述；然后建立了混合云计算工作量分解问题博弈模型；接着对用户策略均衡分析，得出纳什均衡策略向量，并针对不同参数进行了仿真比较分析。

1　相关工作

［5］介绍了云计算产生的时代背景以及为什么会成为当下热点的课题，并以谷歌的云计算技术为例，归纳了云计算关键技术，如数据存储技术、数据管理技术等。参考文献［6］介绍了云计算是一种新型的计算模式，用户的任务被分配到一个混合云的服务器和设备上，相当于为私有云构建了一个外加的计算方式，使得用户能够执行工作量，也就是说，如何分流用户的工作量负载到公有云和私有云上。参考文献［7］从用户目前采用公有云的服务可靠性、安全性等疑虑出发，提出了混合云的解决方案，能够充分利用公有云资源以补充本地私有云资源的不足。

博弈论的思想建模能够很好地分析每个参与者的策略，随着云计算的兴起，越来越多的学者开始着手从博弈论的视角去分析工作量分解［8］。参考文献［9］建议在非合作的参与者共享资源时，以最坏可能的纳什均衡和社会最优之间的比率作为衡量系统的效率标准。参考文献［10］提出了一个具体的新型的云服务提供视频点播系统，介绍了划分用户的点播视频需求量到云计算服务上以及寻求最优的划分策略。参考文献［11］给出了在混和云环境下，求解大任务和小任务两类用户的纳什均衡的方法，并通过仿真给出了在不同参数情况下云用户的最优策略。综上所述，对于在综合考虑用户的响应时间和花费的情况下，用户如何决定工作量分解的最优策略问题尚未研究，这也是本文的主要工作。

2　模型

在混合云计算环境下存在的用户博弈是一个三元组：G=＜N，（si），（μi）＞，其中N=｛1，2，…，n｝为参与者的集合，表示有n个用户。用户i策略集表示为Si，Si=｛σi|σi∈［0，1］｝，其中σi表示用户i划分到公有云计算上执行的任务量占总任务量的比例，从而1-σi表示为用户i划分到私有云上执行的任务量占总任务量的比例。ui=f（ti，ci）表示用户i的效用，它是关于任务的响应时间ti和花费ci的函数。私有云一般是在企业内部部署的，对企业用户不收取费用。工作量执行的时间是取公有云和私有云上执行时间较大者，即ti=max｛TL（），｝，其中TL（）表示工作量划分到私有云上执行的时间，为工作量划分到公有云上执行的时间。本文对建立的混合云计算工作量分解模型有如下假设：（1）公有云计算资源无限，私有云计算资源有限，即公有云的处理速度远大于私有云；（2）每个用户工作量相同且表示为ω。因为对于用户i来说私有云执行时间大于公有云执行时间，所以用户i的工作量执行的时间可以表示为：ti=max。本文和参考文献［4］处理连续的任务时间一样，，其中μL表示私有云上执行任务的速度。因为还有其他用户提交工作量到私有云上执行，所以私有云上执行时间应该是所有用户任务在私有云上的执行时间，可以表示为：。对于用户来说，随着工作量划分任务量比例的增大，花费增大效用会变小，但时间逐渐减少，使得效用因为时间减小而带来效用增大，因此有＜0，＜0。

3　均衡分析和模拟仿真

3.1均衡分析

参照参考文献［9］中效用函数的形式并更一般化，选择用户i的效用函数为：其中，α是花费前的系数；β是响应时间前的系数；γ是花费和响应时间的幂，可以表明时间和花费是可以互相转换的；θ是表达式的幂；a是表达式比例系数。

性质1式（1）有花费和时间的无差异曲线满足凹函数关系。

证明：

令：

通过对式（3）累加可以求得：

这是一个同时行动的完全信息静态博弈，所以有：

3.2模拟分析

ui（）＞ui（1，）时用户纳什均衡策略为：=，可知用户均衡策略与单位任务量的价格、响应时间和花费有关。

图1有3条曲线，分别表示用户数为100、1 000和10 000三种不同的情形；横坐标为单位流量价格，在0到10之间取值；其他参数已设定。当n=100时，随着公有云提供商定价的提高，用户放在公有云上的比例就越少。当用户的总数n增加到1 000时，随着定价从0到10变化，用户提交到公有云上的工作任务明显提高了许多，也就是说当用户数量增大时，本地资源很难满足用户的需求，用户将更多的任务提交到公有云上。当用户的总数增加到10 000时，可以看到用户的均衡策略是几乎把所有的任务量都划分到公有云上，这体现出公有云处理多用户多任务的必要性和优越性。

图1　混合云用户数变化工作量分解图

图2和图3分别为参数α∶β=10∶1和β∶α=1∶10下呈现出的对应关系，表明时间和花费比率对用户效用的影响程度，随着单位任务量价格p的变化，在不同α和β下用户的均衡策略也发生了变化。从图2可以看到，用户随着价格增加，因为花费多，更快地降低了用户效用，用户就不愿意把更多工作量放到公有云执行；而从图3可以看到，随着单位任务量的价格变化，用户的均衡策略变化较缓，也就是说花费相对少，使得用户效用降低的速率较慢。

图2　时间和花费变化工作量分解图

图3　混合云工作量分解图

4　结论

本文提出了混合云环境下云用户在公有云和私有云之间如何进行工作量分解的问题，把响应时间和花费纳入考虑，建立了混合云工作量分解博弈模型，通过求解纳什均衡的方法给出用户的最优任务分解决策。根据相关研究选用花费和时间的效用函数进行了仿真模拟，分析了在不同参数情况下用户均衡策略随着价格的变化情况，为用户更好地决策提供了理论依据。对于给定不同用户工作量的分析更加复杂，这些问题将是下一步研究的方向。

参考文献

［1］Wang Xu，Wang Beizhan，Huang Jing.Cloud computing and its key techniques［C］.2011 IEEE International Conference on ComputerScience and Automation Engineering（CSAE），2011：404-410.

［2］BHARDWAJ S，JAIN L，JAIN S.Cloud computing：a study of infrastructure as a service（IAAS）［J］.International Journal of Engineering and Information Technology，2010，2（1）：60-63.

［3］Zhang Hong，Li Bo，Jiang Hongbo，et al.A framework for truthful online auctions in cloud computing with heterogeneous user demands［C］.INFOCOM 2013 Proceedings IEEE，2013：1510-1518.

［4］NAHIR A，ORDA A，RAZ D.Workload Factoring with the cloud：a game-theoretic perspective［C］.INFOCOM，2012 Proceedings IEEE，2012：2566-2570

［5］OSTERMANN S，IOSUP A，YIGITBASI N，et al.A performance analysis of EC2 cloud computing services for scientific computing［C］.Cloud Computing［A］.Berlin Heidelberg Springer，2010，34：115-131.

［6］JAIN N，MENACHE I，NAOR J S，et al.A truthful mechanism for value-based scheduling in cloud computing［C］.Algorithmic Game Theory［A］.Berlin Heidelberg Springer，2011，6982：178-189.

［7］HU Y，WONG J，ISZLAI G，et al.Resource provisioning for cloud Computing［C］.Proceedings of the 2009 Conference of the Center for Advanced Studies on Collaborative Research，ACM，2009：101-111.

［8］Niu Di，Feng Chen，Li Baochun.A theory of cloud bandwidth pricing for video-on-demand providers［C］.INFOCOM，2012 Proceedings IEEE，2012：711-719.

［9］Wei Guiyi，VASILAKOS A V，Zheng Yao，et al.A gametheoretic method of fair resource allocation for cloud computing services［J］.Journal of Supercomputing，2010，54（2）：252-269.

［10］KOUTSOUPIAS E，PAPADIMITRIOU C.Worst-case equilibria［C］.STACS 99，Berlin Heidelberg：Springer，1999，1563：404-413.

［11］陶杰，吴小红.基于博弈的云计算任务分解研究［J］.科学技术与工程，2013，13（5）：87-92.

Research of the game analysis of user computing workload decomposition in hybrid Cloud

Ma Xiaolong1，2
（1.School of Information Management and Engineering，Shanghai University of Finance and Economics，Shanghai 200433，China；2．Business School，Huzhou University，Huzhou 313000，China）

In hybrid Cloud computing environment，how to reasonably divide the workload is essential for every rational user to be considered.The paper presents a hybrid Cloud computing workload factoring game theory model.Except that the response time performance has been usually taken into account in the related literature，the paper takes payment as utility function into account to game analysis and obtains user′s optimal Nash equilibrium strategic.By simulating the equilibrium strategies，it shows the effect on the equilibrium strategies at different response time and payment ratio.

hybrid Cloud；workload factoring；game theory；Nash equilibrium

TP393

A

1674-7720（2015）16-0058-04

马小龙．混合云用户计算工作量分解的博弈分析研究［J］.微型机与应用，2015，34（16）：58-61.

2015-03-28）

马小龙（1976-），通信作者，男，博士研究生，讲师，主要研究方向：网络机制设计。E-mail：lxm2007@sohu.com。

国家自然科学基金项目（61170029，61103051）；浙江省教育厅科研项目（Y201430451）；浙江省科技计划公益技术应用研究项目（2013C31097）；上海财经大学研究生创新基金（CXJJ-2014-434）；湖州自然科学技术基金（2014YZ10）