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

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

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

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

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

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

0　引言

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

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

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

1　相關(guān)工作

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

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

2　模型

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

3　均衡分析和模擬仿真

3.1均衡分析

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

性質(zhì)1式（1）有花費和時間的無差異曲線滿足凹函數(shù)關(guān)系。

證明：

令：

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

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

3.2模擬分析

ui（）＞ui（1，）時用戶納什均衡策略為：=，可知用戶均衡策略與單位任務(wù)量的價格、響應(yīng)時間和花費有關(guān)。

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

圖1　混合云用戶數(shù)變化工作量分解圖

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

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

圖3　混合云工作量分解圖

4　結(jié)論

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

參考文獻(xiàn)

［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］陶杰，吳小紅.基于博弈的云計算任務(wù)分解研究［J］.科學(xué)技術(shù)與工程，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］.微型機(jī)與應(yīng)用，2015，34（16）：58-61.

2015-03-28）

馬小龍（1976-），通信作者，男，博士研究生，講師，主要研究方向：網(wǎng)絡(luò)機(jī)制設(shè)計。E-mail：lxm2007@sohu.com。

國家自然科學(xué)基金項目（61170029，61103051）；浙江省教育廳科研項目（Y201430451）；浙江省科技計劃公益技術(shù)應(yīng)用研究項目（2013C31097）；上海財經(jīng)大學(xué)研究生創(chuàng)新基金（CXJJ-2014-434）；湖州自然科學(xué)技術(shù)基金（2014YZ10）