馬小龍（1.上海財經大學　信息管理與工程學院，上海　200433；2．湖州師范學院　商學院，浙江　湖州　313000）

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

馬小龍1，2
（1.上海財經大學信息管理與工程學院，上海200433；2．湖州師范學院商學院，浙江湖州313000）

在混合云計算環(huán)境下，如何合理地劃分工作量是每個理性的用戶所需要考慮的問題。構建了混合云計算工作量分解博弈模型，在用戶通?？紤]響應時間的情況下把花費也納入考慮，即將以響應時間和花費為變量的函數作為效用函數，通過求解納什均衡的方法分析用戶的策略行為，從而決定用戶的最優(yōu)策略。通過仿真給出了不同響應時間和花費比率對用戶均衡策略的影響并做出了比較分析。

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

0　引言

云計算服務作為一種新型的商業(yè)計算服務逐漸成為企業(yè)和個人用戶計算應用的主要方式，如亞馬遜的EC2、谷歌的AppEngine及微軟的Azure等云平臺［1］。隨著云計算的興起，近幾年來云計算用戶穩(wěn)定增長。根據美國國家標準與技術研究院（NIST）的定義，云計算服務模式可分為基礎設施即服務（IaaS）、平臺即服務（PaaS）及軟件即服務（SaaS）［2］。云計算發(fā)展至今，云服務方式出現(xiàn)了公有云、私有云、混合云等，混合云是由公有云和私有云組成的。公有云平臺是整合自己的資源為第三方提供服務的計算平臺，私有云平臺則是整合企業(yè)內部的資源為企業(yè)自己服務的云計算平臺，而混合云平臺則是指整合公有云和私有云共同為用戶提供服務［3］。隨著云計算技術的發(fā)展，由公有云和私有云共同組成的混合云是未來發(fā)展的趨勢。在Ganter對全球270家企業(yè)的調查中，有46％的企業(yè)決策者考慮基于現(xiàn)有自建方案進行云協(xié)作應用的延伸部署計劃，這說明混合云將成為相當一段時間內的主流模式。

目前云計算一般有兩種類型的分析：性能類型分析和市場類型分析［4］。性能類型分析以“最優(yōu)化”執(zhí)行性能為目標，例如針對響應時間性能，通常不會考慮花費；而市場類型分析就要考慮花費的因素。用戶通過提交工作量到公有云上能很好地降低工作量的響應時間，從響應時間角度能夠提高用戶的效用水平，但同時公有云是按用戶的消費量收費的，從用戶的花費角度降低了用戶的效用水平。當用戶急需縮短處理任務的響應時間時，用戶愿意繳納費用來獲得更好的效用水平，而隨著響應時間的逐步縮短，用戶對執(zhí)行單位工作量愿意的花費逐漸減小，因此在考慮響應時間和花費的情況下，用戶如何做出合理的工作量分解決策正是本文研究的問題。

本文把響應時間和花費納入考慮，建立了混合云工作量分解博弈模型，通過求解納什均衡的方法給出用戶的最優(yōu)任務分解決策。本文首先對相關工作進行了綜述；然后建立了混合云計算工作量分解問題博弈模型；接著對用戶策略均衡分析，得出納什均衡策略向量，并針對不同參數進行了仿真比較分析。

1　相關工作

［5］介紹了云計算產生的時代背景以及為什么會成為當下熱點的課題，并以谷歌的云計算技術為例，歸納了云計算關鍵技術，如數據存儲技術、數據管理技術等。參考文獻［6］介紹了云計算是一種新型的計算模式，用戶的任務被分配到一個混合云的服務器和設備上，相當于為私有云構建了一個外加的計算方式，使得用戶能夠執(zhí)行工作量，也就是說，如何分流用戶的工作量負載到公有云和私有云上。參考文獻［7］從用戶目前采用公有云的服務可靠性、安全性等疑慮出發(fā)，提出了混合云的解決方案，能夠充分利用公有云資源以補充本地私有云資源的不足。

博弈論的思想建模能夠很好地分析每個參與者的策略，隨著云計算的興起，越來越多的學者開始著手從博弈論的視角去分析工作量分解［8］。參考文獻［9］建議在非合作的參與者共享資源時，以最壞可能的納什均衡和社會最優(yōu)之間的比率作為衡量系統(tǒng)的效率標準。參考文獻［10］提出了一個具體的新型的云服務提供視頻點播系統(tǒng)，介紹了劃分用戶的點播視頻需求量到云計算服務上以及尋求最優(yōu)的劃分策略。參考文獻［11］給出了在混和云環(huán)境下，求解大任務和小任務兩類用戶的納什均衡的方法，并通過仿真給出了在不同參數情況下云用戶的最優(yōu)策略。綜上所述，對于在綜合考慮用戶的響應時間和花費的情況下，用戶如何決定工作量分解的最優(yōu)策略問題尚未研究，這也是本文的主要工作。

2　模型

在混合云計算環(huán)境下存在的用戶博弈是一個三元組：G=＜N，（si），（μi）＞，其中N=｛1，2，…，n｝為參與者的集合，表示有n個用戶。用戶i策略集表示為Si，Si=｛σi|σi∈［0，1］｝，其中σi表示用戶i劃分到公有云計算上執(zhí)行的任務量占總任務量的比例，從而1-σi表示為用戶i劃分到私有云上執(zhí)行的任務量占總任務量的比例。ui=f（ti，ci）表示用戶i的效用，它是關于任務的響應時間ti和花費ci的函數。私有云一般是在企業(yè)內部部署的，對企業(yè)用戶不收取費用。工作量執(zhí)行的時間是取公有云和私有云上執(zhí)行時間較大者，即ti=max｛TL（），｝，其中TL（）表示工作量劃分到私有云上執(zhí)行的時間，為工作量劃分到公有云上執(zhí)行的時間。本文對建立的混合云計算工作量分解模型有如下假設：（1）公有云計算資源無限，私有云計算資源有限，即公有云的處理速度遠大于私有云；（2）每個用戶工作量相同且表示為ω。因為對于用戶i來說私有云執(zhí)行時間大于公有云執(zhí)行時間，所以用戶i的工作量執(zhí)行的時間可以表示為：ti=max。本文和參考文獻［4］處理連續(xù)的任務時間一樣，，其中μL表示私有云上執(zhí)行任務的速度。因為還有其他用戶提交工作量到私有云上執(zhí)行，所以私有云上執(zhí)行時間應該是所有用戶任務在私有云上的執(zhí)行時間，可以表示為：。對于用戶來說，隨著工作量劃分任務量比例的增大，花費增大效用會變小，但時間逐漸減少，使得效用因為時間減小而帶來效用增大，因此有＜0，＜0。

3　均衡分析和模擬仿真

3.1均衡分析

參照參考文獻［9］中效用函數的形式并更一般化，選擇用戶i的效用函數為：其中，α是花費前的系數；β是響應時間前的系數；γ是花費和響應時間的冪，可以表明時間和花費是可以互相轉換的；θ是表達式的冪；a是表達式比例系數。

性質1式（1）有花費和時間的無差異曲線滿足凹函數關系。

證明：

令：

通過對式（3）累加可以求得：

這是一個同時行動的完全信息靜態(tài)博弈，所以有：

3.2模擬分析

ui（）＞ui（1，）時用戶納什均衡策略為：=，可知用戶均衡策略與單位任務量的價格、響應時間和花費有關。

圖1有3條曲線，分別表示用戶數為100、1 000和10 000三種不同的情形；橫坐標為單位流量價格，在0到10之間取值；其他參數已設定。當n=100時，隨著公有云提供商定價的提高，用戶放在公有云上的比例就越少。當用戶的總數n增加到1 000時，隨著定價從0到10變化，用戶提交到公有云上的工作任務明顯提高了許多，也就是說當用戶數量增大時，本地資源很難滿足用戶的需求，用戶將更多的任務提交到公有云上。當用戶的總數增加到10 000時，可以看到用戶的均衡策略是幾乎把所有的任務量都劃分到公有云上，這體現(xiàn)出公有云處理多用戶多任務的必要性和優(yōu)越性。

圖1　混合云用戶數變化工作量分解圖

圖2和圖3分別為參數α∶β=10∶1和β∶α=1∶10下呈現(xiàn)出的對應關系，表明時間和花費比率對用戶效用的影響程度，隨著單位任務量價格p的變化，在不同α和β下用戶的均衡策略也發(fā)生了變化。從圖2可以看到，用戶隨著價格增加，因為花費多，更快地降低了用戶效用，用戶就不愿意把更多工作量放到公有云執(zhí)行；而從圖3可以看到，隨著單位任務量的價格變化，用戶的均衡策略變化較緩，也就是說花費相對少，使得用戶效用降低的速率較慢。

圖2　時間和花費變化工作量分解圖

圖3　混合云工作量分解圖

4　結論

本文提出了混合云環(huán)境下云用戶在公有云和私有云之間如何進行工作量分解的問題，把響應時間和花費納入考慮，建立了混合云工作量分解博弈模型，通過求解納什均衡的方法給出用戶的最優(yōu)任務分解決策。根據相關研究選用花費和時間的效用函數進行了仿真模擬，分析了在不同參數情況下用戶均衡策略隨著價格的變化情況，為用戶更好地決策提供了理論依據。對于給定不同用戶工作量的分析更加復雜，這些問題將是下一步研究的方向。

參考文獻

［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，F(xiàn)eng 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）；上海財經大學研究生創(chuàng)新基金（CXJJ-2014-434）；湖州自然科學技術基金（2014YZ10）