摘 要： 在混合云計算環境下，如何合理地劃分工作量是每個理性的用戶所需要考慮的問題。構建了混合云計算工作量分解博弈模型，在用戶通?？紤]響應時間的情況下把花費也納入考慮，即將以響應時間和花費為變量的函數作為效用函數，通過求解納什均衡的方法分析用戶的策略行為，從而決定用戶的最優策略。通過仿真給出了不同響應時間和花費比率對用戶均衡策略的影響并做出了比較分析。
關鍵詞： 混合云；工作量分解；博弈；納什均衡
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的函數。私有云一般是在企業內部部署的，對企業用戶不收取費用。工作量執行的時間是取公有云和私有云上執行時間較大者，即
，其中 
表示工作量劃分到私有云上執行的時間，TiP為工作量劃分到公有云上執行的時間。本文對建立的混合云計算工作量分解模型有如下假設：（1）公有云計算資源無限，私有云計算資源有限，即公有云的處理速度遠大于私有云；（2）每個用戶工作量相同且表示為?棕。因為對于用戶i來說私有云執行時間大于公有云執行時間，所以用戶i的工作量執行的時間可以表示為：ti=max
。本文和參考文獻[4]處理連續的任務時間一樣，
，其中
L表示私有云上執行任務的速度。因為還有其他用戶提交工作量到私有云上執行，所以私有云上執行時間應該是所有用戶任務在私有云上的執行時間，可以表示為：
。對于用戶來說，隨著工作量劃分任務量比例的增大，花費增大效用會變小，但時間逐漸減少，使得效用因為時間減小而帶來效用增大，因此有
。
3 均衡分析和模擬仿真
3.1 均衡分析
每個用戶的效用都和其他用戶提交到公有云的策略有關，如果把每個用戶視為理性的參與者，用戶i的策略為
i，ti和ci都為
i的函數，用戶i的效用就可表示為ui（
i，
-i），即f（ti，ci）=ui（
i，
-i），用戶策略的范圍為
i∈[0，1）。由于所有用戶同時行動，因此這個博弈是一個完全信息靜態博弈。用戶的效用分別為u1（
1，
-1），…，ui（
i，
-i），…，un（
n，
-n），隨著
i的增大，用戶的邊際效用遞減。ui（
i，
-i）是凹函數，即：
。
0，即當其他用戶是最優時，用戶i的策略也是它的最優策略，即互為最優反應策略，那么（
i*，
*-i）就是該博弈的納什均衡。
參照參考文獻[9]中效用函數的形式并更一般化，選擇用戶i的效用函數為：
其中，![({8}@I(Z6EVFGN]4J[G865E.jpg](http://files.chinaaet.com/images/2016/02/08/6359055946708500004606502.jpg "({8}@I(Z6EVFGN]4J[G865E.jpg")
是花費前的系數；![863L%1Q}Y~5){{NSXQ`V9]L.jpg](http://files.chinaaet.com/images/2016/02/08/6359055947460900007861237.jpg "863L%1Q}Y~5){{NSXQ`V9]L.jpg")
是響應時間前的系數；![O79~1YI$195[DU$~)`UVO]9.jpg](http://files.chinaaet.com/images/2016/02/08/6359055948293200009635433.jpg "O79~1YI$195[DU$~)`UVO]9.jpg")
是花費和響應時間的冪，可以表明時間和花費是可以互相轉換的；?茲是表達式的冪；a是表達式比例系數。
性質1 式（1）有花費和時間的無差異曲線滿足凹函數關系。
證明：
當效用是一個給定的正常數時，式（2）為一正常數，設![Z1%$]A@KKVGJ4JO8{VI)NQQ.png](http://files.chinaaet.com/images/2016/02/08/6359055995819300005290860.png "Z1%$]A@KKVGJ4JO8{VI)NQQ.png")
，則：
![FT~`F[FTO0D1A~(N~OT$4]U.png](http://files.chinaaet.com/images/2016/02/08/6359055951071500009051068.png "FT~`F[FTO0D1A~(N~OT$4]U.png")
在實際應用中會經?？紤]到邊際效用遞減規律，在混合云計算環境下，用戶如何合理地劃分工作量比例是每個理性的云用戶關心的問題。由前面云用戶的效用表達式ui=f（ti，ci），其中用戶i花費的函數為ci=p?滓i?棕，可得用戶i執行工作量分解響應時間的表達式為：
。在用戶混合云工作量分解博弈模型中，用戶之間存在的博弈是一個完全信息靜態博弈，
，可以得到用戶i反應函數![}AEN`N6ZZ(8B`W371(L]}6M.jpg](http://files.chinaaet.com/images/2016/02/08/6359055963792400005216655.jpg "}AEN`N6ZZ(8B`W371(L]}6M.jpg")
。在完全信息靜態博弈中，因考慮用戶所有任務量相同時，最終可得一致性的策略結果。當
i∈[0，1）時，
3.2 模擬分析
價格、響應時間和花費有關。
圖1有3條曲線，分別表示用戶數為100、1 000和10 000三種不同的情形；橫坐標為單位流量價格，在0到10之間取值；其他參數已設定。當n=100時，隨著公有云提供商定價的提高，用戶放在公有云上的比例就越少。當用戶的總數n增加到1 000時，隨著定價從0到10變化，用戶提交到公有云上的工作任務明顯提高了許多，也就是說當用戶數量增大時，本地資源很難滿足用戶的需求，用戶將更多的任務提交到公有云上。當用戶的總數增加到10 000時，可以看到用戶的均衡策略是幾乎把所有的任務量都劃分到公有云上，這體現出公有云處理多用戶多任務的必要性和優越性。
圖2和圖3分別為參數
下呈現出的對應關系，表明時間和花費比率對用戶效用的影響程度，隨著單位任務量價格p的變化，在不同![({8}@I(Z6EVFGN]4J[G865E.jpg](http://files.chinaaet.com/images/2016/02/08/6359055987449100007298317.jpg "({8}@I(Z6EVFGN]4J[G865E.jpg")
和![863L%1Q}Y~5){{NSXQ`V9]L.jpg](http://files.chinaaet.com/images/2016/02/08/6359055988099600008206470.jpg "863L%1Q}Y~5){{NSXQ`V9]L.jpg")
下用戶的均衡策略也發生了變化。從圖2可以看到，用戶隨著價格增加，因為花費多，更快地降低了用戶效用，用戶就不愿意把更多工作量放到公有云執行；而從圖3可以看到，隨著單位任務量的價格變化，用戶的均衡策略變化較緩，也就是說花費相對少，使得用戶效用降低的速率較慢。
4 結論
本文提出了混合云環境下云用戶在公有云和私有云之間如何進行工作量分解的問題，把響應時間和花費納入考慮，建立了混合云工作量分解博弈模型，通過求解納什均衡的方法給出用戶的最優任務分解決策。根據相關研究選用花費和時間的效用函數進行了仿真模擬，分析了在不同參數情況下用戶均衡策略隨著價格的變化情況，為用戶更好地決策提供了理論依據。對于給定不同用戶工作量的分析更加復雜，這些問題將是下一步研究的方向。
參考文獻
[1] Wang Xu， Wang Beizhan， Huang Jing. Cloud computing and its key techniques[C]. 2011 IEEE International Conference on Computer Science 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 game-theoretic 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.