董 瑋

(吉林開放大學 吉林 長春 130022)

0 引 言

云計算技術的目標是通過利用虛擬化技術(Virtualized Technology)將分布于互聯(lián)網(wǎng)上的各種類型的IT資源最終整合為可擴展的大規(guī)模資源池，然后利用互聯(lián)網(wǎng)作為載體向用戶方提供軟件服務、平臺服務及基礎設施服務[1-2]。鑒于廣大云用戶的需求擁有很強的動態(tài)可變性，尤其針對特定型的數(shù)據(jù)密集的計算需求，這類任務對于計算資源的需求量的激增會導致單個云資源提供者的資源提供環(huán)境無法滿足用戶需求，導致資源提供方不得不改變現(xiàn)有的服務提供商業(yè)模式，進而尋找改善其動態(tài)資源服務能力的可擴展方法。當前，操作性較強的適用方法是多個云資源提供者之間可以建立合作關系，通過建立資源提供方聯(lián)盟的模式，進一步完善異構資源在用戶需求上的優(yōu)化配置。

文獻[3-4]較早地研究了多個云資源提供者之間建立云間聯(lián)盟的需求，但是沒有設計云間聯(lián)盟的有效形成機制。文獻[5]建立了一種局部云與遠程云的聯(lián)盟構建模型，其運用場景是當局部云無法滿足用戶需求時，代理可以向遠程云租購資源，但該聯(lián)盟構建機制沒有論證資源方的聯(lián)盟形成動機。文獻[6]設計了一種基于聯(lián)盟個體利益最大化的聯(lián)盟形成決策方法，單個云資源提供者可以對是否與公有云提供者形成聯(lián)盟給出依據(jù)，但該方法并沒有考慮不同類型不同利益共同體的云資源對聯(lián)盟形成決策的影響，同時也沒有考慮不同類型的虛擬機實例需求和異構資源間的映射與調(diào)度問題。文獻[7]基于公有云與私有云的混合環(huán)境，設計了一種基于二進制整數(shù)規(guī)劃的最小化代價任務調(diào)度算法，但算法僅優(yōu)化了私有云的資源利用率，沒有給出混合云的最優(yōu)解。文獻[8]設計一種基于博弈式博弈的云資源調(diào)與分配方法，通過建立資源提供商之間的合作關系，能夠?qū)崿F(xiàn)合作各方的總體利益最大化。文獻[9]基于效益博弈理論，設計了一種動態(tài)且可調(diào)合的云計算資源分配算法，構建了一種效益博弈模型，并利用時間矩陣和費用矩陣作為衡量指標，同時求解了博弈解。文獻[10]基于服務質(zhì)量需求設計了一種資源分配博弈方法，方法將云資源分配過程中的服務質(zhì)量保證問題建模為合作博弈，同時證明了該問題存在帕累托最優(yōu)解。然而，上述研究工作都忽視了以協(xié)作方式產(chǎn)生資源聯(lián)盟的穩(wěn)定性。

本文將所有參與的云資源提供者的決策動機都考慮進來，綜合所有因素對是否形成聯(lián)盟資源作出決策，為了實現(xiàn)資源聯(lián)盟的總體利益最大化，提出了一種云聯(lián)盟形成博弈算法。

1 系統(tǒng)模型

1.1 云資源提供系統(tǒng)模型

1.2 云聯(lián)盟模型

將云聯(lián)盟形成問題建立為一個聯(lián)盟博弈模型[11]，可將聯(lián)盟博弈定義為(I,v)，其中：I表示博弈者集合，即云資源提供者；v表示在F?I上的聯(lián)盟博弈的特征函數(shù)，特征函數(shù)為一個實數(shù)值函數(shù)，滿足v:F→R+，v(?)=0。

每個子集F?I表示一個聯(lián)盟，若所有云資源提供者構成一個聯(lián)盟，則稱之為大聯(lián)盟。一個聯(lián)盟F擁有一個價值，該價值由特征函數(shù)v(F)定義。同時，v(F)代表的是當F中的云資源提供者協(xié)作組成集群時所能獲得的利益，定義為：

(1)

由于對于給定的聯(lián)盟F而言，其目標是最大化其利益，可將云聯(lián)盟利益最大化問題形式化為一個整數(shù)規(guī)劃問題，目標函數(shù)即：

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

(8)

式(2)代表v(F)，即聯(lián)盟F中云資源提供者可獲得的利益，等于用戶支付與資源代價之差。式(3)確保云資源提供者分配至用戶的內(nèi)核數(shù)量小于其可用內(nèi)核數(shù)量；式(4)確保云資源提供者分配至用戶的存儲量小于其可用存儲量；式(5)確保云資源提供者分配至用戶的每種類型VM實例的內(nèi)核數(shù)量等于用戶請求該VM實例的內(nèi)核數(shù)量；式(6)確保云資源提供者分配至用戶的每種類型VM實例的存儲量等于用戶請求該VM實例的存儲量；式(7)確保聯(lián)盟中的每個云資源提供者至少貢獻一種資源類型。以上約束條件使得云資源提供者可以向聯(lián)盟貢獻資源。式(8)代表決策變量是整數(shù)。

定義ψCi(F)為聯(lián)盟F中云資源提供者Ci所能獲得的利益分配量，該值為標準化Banzhaf值給出。Banzhaf值[12]是在考慮博弈者能力的條件對于聯(lián)盟利益的一種分割方式。本文將這種博弈者能力定義為云資源提供者的市場占有率。若在所有可能聯(lián)盟中，一個云資源提供者可貢獻的資源越多，則其利益分配也將越多。

2 云聯(lián)盟形成機制

2.1 云聯(lián)盟形成模型

云聯(lián)盟博弈的核心可能為空。若大聯(lián)盟無法形成，即需要形成獨立且不相互的聯(lián)盟形式。聯(lián)盟博弈形成理論即是研究在大聯(lián)盟無法形成時博弈中聯(lián)盟結構的理論。聯(lián)盟形成討論的即是將所有博弈參與者分割為不相交的集合。一種聯(lián)盟結構FS={F1,F2,…,Fh}構成對于云資源提供者集合I的一種分割形式，每個云資源提供者準確地成為一個聯(lián)盟中的成員，即對于所有的i和j，當i≠j時，有Fi∩Fj=?，且∪Fi=I。定義Q為所有可能聯(lián)盟結構的集合，尋找最優(yōu)聯(lián)盟結構為NP難問題。

將云聯(lián)盟形成問題建模為云資源提供者在聯(lián)盟結構上擁有偏好的享樂博弈。

定義1享樂博弈[13]。享樂博弈即為(I,≥)，≥i表示在Qi上的反射完全可傳遞二進制關系，Qi表示包含Ci的聯(lián)盟I的集合。

定義≥i表示云資源提供者Ci的聯(lián)盟偏好關系，該關系允許Ci比較兩個聯(lián)盟結構，并指出該云資源提供者對成為其中一個聯(lián)盟成員的偏好。若A≥iB，則表明Ci偏好于成為聯(lián)盟A的一個成員，而不偏好于成為聯(lián)盟B的成員，或至少對于兩個聯(lián)盟擁有相同偏好。此外，若A>iB表明Ci嚴格偏好于成員聯(lián)盟A的一個成員，而不成為B的成員。

為了將云聯(lián)盟形成問題建立為享樂博弈模型，需要定義聯(lián)盟的偏好關系。對于所有的Ci∈I和所有F，F(xiàn)′∈Qi，定義≥i為：

F≥iF′?v(F)≥v(F′)

(9)

式(9)表明一個云資源提供者將偏好于選擇給予更高利益分配的聯(lián)盟結構。利用這種偏好關系，每個云資源提供者可以在所有可能形成的聯(lián)盟結構中評估其成為其中一個聯(lián)盟成員的偏好。

為了找到一個相比其他聯(lián)盟結構更加偏好的聯(lián)盟，定義兩種比較關系分別為合并關系Δm和分裂比較Δs，具體如下：

{F∪F′}Δm{F,F′}?

{?Ci∈F;{F∪F′}>iFand

?Cj∈F′;{F∪F′}>jF′}

(10)

{F,F′}Δs{F∪F′}?

{?Ci∈F;F≥i{F∪F′} or

(11)

式(10)表明若聯(lián)盟{F∪F′}獲得的利益大于F和F′獲得的利益，聯(lián)盟{F∪F′}比較兩個不相互的聯(lián)盟{F,F′}將獲得選擇偏好，如此所有資源提供者可以改進其總利益。式(11)表明如果至少一個聯(lián)盟可以在不影響其他博弈者的情況下維持相同利益或增加其成員的利益，則{F,F′}將獲得比{F∪F′}更大的選擇偏好。

利用定義的比較關系，可以提出基于以下兩種規(guī)則進行云資源聯(lián)盟形成機制[14]：

合并規(guī)則：若{F∪F′}Δm{F,F′}，則需合并聯(lián)盟集合{F,F′}；

分裂規(guī)則：若{F,F′}Δs{F∪F′}，則需分裂聯(lián)盟{F∪F′}。

如果所有云資源提供者可以通過合并規(guī)則嚴格改進其總利益，則聯(lián)盟決定合并。因此，若對于參與者是有利的，合并將在云資源提供者間達成共識。

如前所述，最終所形成的聯(lián)盟才提供請求的VM實例。因此，其他的聯(lián)盟形式并不重要。原因在于不在最終聯(lián)盟結構中的其他云資源提供者可再次參與其他請求的聯(lián)盟形成和資源提供過程。因此，僅當至少一個子聯(lián)盟可嚴格改進其資源提供者的總體利益時，聯(lián)盟結構可決定進行分裂。在這種分裂規(guī)則下，其他子聯(lián)盟的利益可能降低。分裂規(guī)則可視為一種自私的聯(lián)盟決策，并不考慮分裂過程對于其他聯(lián)盟形式的影響。

通過合并/分裂過程，可能的聯(lián)盟形式被訪問，其價值被計算?；谠搩r值，定義云資源提供者Ci的估計Banzhaf值為：

(12)

式中：V表示所有可遍歷訪問的聯(lián)盟集合；λ表示包含Ci的所訪問的聯(lián)盟總數(shù)，λ=2m-1-β，β表示沒有被訪問的聯(lián)盟數(shù)量。估計Banzhaf值根據(jù)在合并與分裂過程中已被訪問的聯(lián)盟的價值進行計算，其標準化估計Banzhaf值為：

(13)

每個成員Ci可從大聯(lián)盟結構中獲得的利益計算為：

ψCi(I)=ξCi(I)v(I)

(14)

支付向量ψ(I)=(ψC1(I),ψC2(I),…,ψCm(I))給出大聯(lián)盟的利益分割方式。定義對于云資源提供者Ci∈F獲得的利益ψCi(F)為：

(15)

在聯(lián)盟進行合并與分裂過程中，根據(jù)聯(lián)盟形式估計每個云資源提供者的Banzhaf值，即聯(lián)盟所獲利益將依據(jù)聯(lián)盟中成員的能力在所參與的資源提供者間進行正比例分配。

2.2 云聯(lián)盟形成算法

算法1給出了云聯(lián)盟形成算法CFFM。算法利用分支限界法求解每個聯(lián)盟中任務調(diào)度的線性規(guī)劃問題，進而找到資源分配和聯(lián)盟的利益分配方案。算法定義B&B-VM-ALLOCATION(Fi)為實現(xiàn)求解聯(lián)盟Fi的線性規(guī)劃問題的分支限界法的功能。

算法1云聯(lián)盟形成算法

1. receive requestR

//接收來自用戶的VM服務請求

2.FS={{C1},{C2},…,{Cm}}

//初始聯(lián)盟結構設置

3. calculatev(Fi) forFi∈FS

//計算聯(lián)盟價值

4.repeat

5.stop←TURE

6.forallFi,Fj∈FS,i≠j,do

7.visited[Fi][Fj]←FALSE

//初始化聯(lián)盟對為未遍歷

8.endfor

9. {聯(lián)盟合并過程開始}

10. repeat

11.flag←TURE

12. randomly selectFi,Fj∈FSfor whichvisited[Fi][Fj]=FALSE,i≠j

//隨機選擇聯(lián)盟對進行合并嘗試

13.visited[Fi][Fj]←TRUE

//設置聯(lián)盟對已被遍歷

14. B&B-VM-ALLOCATION(Fi∪Fj){Allocate VMs usingFi∪Fj}

//分支限界法求解該聯(lián)盟上的虛擬機分配問題

15.ifFi∪FjΔm{Fi,Fj} then

//滿足聯(lián)盟合并規(guī)則

16.Fi←Fi∪Fj{mergeFiandFj}

//聯(lián)盟合并

17.Fj←? {Fjis removed fromFS}

//更新聯(lián)盟

18.forallFk∈FS,k≠i,do

19.visited[Fi][Fk]←FALSE

20.endfor

21.endif

22.forallFi,Fj∈FS,i≠j,do

//在聯(lián)盟結構中的所有聯(lián)盟對上進行遍歷

23.ifnotvisited[Fi][Fj]then

24.flag←FALSE

//設置終止標識

25.endif

26.endfor

27.until(|FS|=1) or (flag=TRUE)

//合并終止條件

28. {聯(lián)盟分裂過程開始}

29.forallFi∈FSwhere |Fi|>1do

//在所成員數(shù)大于1的聯(lián)盟上進行遍歷

30.forallpartitions{Fi,Fk} ofFi,whereFi=Fi∪Fk,Fi∩Fk=?do

//對所有沒有交集的聯(lián)盟分裂形式進行遍歷

31. B&B-VM-ALLOCATION(Fj){Allocate VMs useFj}

//分支限界法求解該聯(lián)盟上的虛擬機分配問題

32. B&B-VM-ALLOCATION(Fk){AllocateVMs useFk}

//分支限界法求解該聯(lián)盟上的虛擬機分配問題

33.if{Fj,Fk}ΔsFithen

//滿足聯(lián)盟分裂規(guī)則

34.Fi←Fj{that isFS=FSFi}

//更新聯(lián)盟

35.FS=FS∪Fk

//更新聯(lián)盟結構

36.stop←FALSE

//設置終止標識

37. break(one split occurs; not check other splits)

//跳出分裂過程

38.endif

39.endfor

40.endfor

41.untilstop=TRUE

42. findFk=argmaxFi∈FS{v{Fi}}

//尋找得到總利益最大的聯(lián)盟進行虛擬機資源的分配

43. calculateψCi(Fk),Ci∈Fk

//計算所得聯(lián)盟中云資源提供者的利益分割

44.Fkallocates and provides the requested VM instances

//完成VM實例的分配與提供

算法開始于用戶發(fā)送的請求。聯(lián)盟結構FS由單個Ci∈I構成一個聯(lián)盟Fi的形式構成。然后，算法計算v(Fi)，利用矩陣visited記錄FS中已被訪問的合并過程中的所有聯(lián)盟對。通過該矩陣，F(xiàn)S中所有可能的兩個聯(lián)盟組合在合并過程中均可被訪問到。合并過程開始于隨機選擇FS中的兩個未訪問聯(lián)盟，即Fi和Fj。調(diào)用B&B-VM-ALLOCATION可以找到在Fi∪Fj上的最優(yōu)VM分配方案。如果Fi∪FjΔm{Fi,Fj}，則聯(lián)盟Fi和Fj決定合并。Fi∪Fj被保存于Fi中，而Fj則從FS中移除。由于Fi發(fā)生改變，在下一輪合并步驟中該聯(lián)盟依然可被選擇。因此，對于所有的Fk∈FS，k≠i,visited[Fi][Fk]均設置為false。合并過程再次試圖找到另一個未被訪問適合于合并的聯(lián)盟對。如果所有聯(lián)盟均被測試，合并過程沒有發(fā)生，大聯(lián)盟得以形成，則合并過程終止。

通過合并過程得到的聯(lián)盟結構FS接下來需要進行分裂過程。在分裂過程中，所有擁有一個以上成員的聯(lián)盟均需要進行分裂測試。算法將擁有一個以上成員的聯(lián)盟Fi分裂為兩個不相交的聯(lián)盟Fj和Fk，F(xiàn)j∪Fk=Fi。B&B-VM-ALLOCATION被調(diào)用兩次以找到在Fj和Fk上的最優(yōu)分配方案。由于分裂過程是自私?jīng)Q策，只有當聯(lián)盟Fj或Fk的成員之一可以改進其利益時才會發(fā)生聯(lián)盟分裂行為，因此，擁有更高個體利益的聯(lián)盟才是分裂行為的決策者。

如果一個或多個聯(lián)盟分裂，則聯(lián)盟合并過程重新開始，為此，stop標識符補充設置為false。連續(xù)多次的合并和分裂過程重復進行直到算法終止，終止即表明此時對于在FS中的所有已有聯(lián)盟不會再選擇進行聯(lián)盟合并或分裂過程?？紤]FSfinal作為算法得到的最終的聯(lián)盟結構，算法將選擇FSfinal中的一個可以得到最高總體利益的聯(lián)盟作為任務調(diào)度的目標資源集合。算法利用標準化估計Banzhaf值計算聯(lián)盟中參與的云資源提供者的個體利益，所選擇的聯(lián)盟將分配和提供給用戶任務相應請求的VM實例。

2.3 算法性能分析

1) 算法收斂性能分析。根據(jù)聯(lián)盟偏好關系Δm的定義可知，每一次迭代中，經(jīng)過兩個聯(lián)盟合并后得到的聯(lián)盟結構肯定優(yōu)于聯(lián)盟合并前的兩個聯(lián)盟。同理，根據(jù)聯(lián)盟偏好關系Δs定義可知，經(jīng)過單個聯(lián)盟分裂后得到的聯(lián)盟結構肯定優(yōu)于分裂前的兩個聯(lián)盟結構。因此，如果經(jīng)過聯(lián)盟的合并與分裂迭代操作后得到了一個聯(lián)盟結構，那么算法肯定無法在后續(xù)的聯(lián)盟合并與分裂過程再次得到該聯(lián)盟結構，即同樣的聯(lián)盟在合并與分裂過程中是不可逆的。同時，對于固定數(shù)量的云資源提供者而言，其能夠得到的可能的聯(lián)盟結構形式是有上限值的，聯(lián)盟的合并和分裂迭代過程務必在一定的聯(lián)盟數(shù)量上停止。綜上所述，本文算法最終得到的聯(lián)盟結構將是一個無法進一步合并與分裂的聯(lián)盟結構，即算法肯定是收斂的。

2) 算法穩(wěn)定性能分析。只要沒有任意一個聯(lián)盟中的云資源提供者在不降低至少一個其他聯(lián)盟成員收益的情況下可以脫離聯(lián)盟，則可以認為該聯(lián)盟結構是具有穩(wěn)定性的。在聯(lián)盟分裂過程中，本文算法在當前聯(lián)盟中的每個云資源提供者上遍歷分裂出聯(lián)盟的可能性。如果找到這一云資源提供者，則可以應用分裂規(guī)則。那么在最終的聯(lián)盟結構中，沒有一個云資源提供者會選擇脫離聯(lián)盟，即此時的聯(lián)盟一定具有穩(wěn)定性。云資源提供者組成的資源聯(lián)盟一旦具有穩(wěn)定性，就可以向用戶方的任務提供請求的虛擬機實例。

3) 算法時間復雜度分析。理論上，求解使得聯(lián)盟總體利益最大化的最優(yōu)聯(lián)盟結構問題與在所有云資源提供者上窮舉出所有聯(lián)盟分割結構問題具有同樣的時間復雜度。然而，本文算法設計了聯(lián)盟的合并與分裂機制，這樣在尋優(yōu)過程中是不需要列舉出所有的聯(lián)盟結構形式的，大大地降低了算法搜索的時間復雜度。同時，本文算法的時間復雜性主要由聯(lián)盟進行的合并與分裂次數(shù)以及子聯(lián)盟的規(guī)模(內(nèi)部擁有的云資源提供者的數(shù)量)相關。首先，考慮搜索過程中的最壞情況。在聯(lián)盟結構FS中，其每一個聯(lián)盟均需要與其他所有聯(lián)盟形式嘗試合并。初始聯(lián)盟結構中，單個云資源提供者均單獨構成一個聯(lián)盟，那么最壞的情形下，一共需要進行m(m-1)/2次嘗試后，將進行第一次的聯(lián)盟合并。而第二次合并則要求進行(m-1)(m-2)/2次合并的嘗試，依此類推。則最壞的合并時間復雜度為O(m3)。此外，最壞情況下，聯(lián)盟F分裂過程的時間復雜度為O(2|F|)，即需要將其分裂為所有可能形式的聯(lián)盟對。因此，本文算法的實際時間復雜度應該遠小于O(m3+2|F|)。

3 仿真實驗

3.1 實驗配置

在仿真平臺CloudSim[15]中對算法進行性能驗證。考慮由八個云資源提供者提供四種類型的VM實例的云資源提供環(huán)境，八個云資源提供者是實際環(huán)境中云資源間可以組建聯(lián)盟的合理估算。四種VM實例類型VM={VM1,VM2,VM3,VM4}，分別代表small、medium、large、extra large的VM實例，VM實例的相關參數(shù)描述如表1所示。VM實例類型和定價機制與Microsoft Azure相似。

表1 可用的VM實例屬性

3.2 結果分析

本文選取最優(yōu)云聯(lián)盟算法和隨機云聯(lián)盟算法作為對比算法。最優(yōu)云聯(lián)盟算法通過求解線性規(guī)劃問題中式(7)所代表的松弛問題尋找最優(yōu)的云資源提供者的分配方案。換言之，該算法尋找能夠使其收益達到最大化的聯(lián)盟結構，即通過窮舉方法得到所有可能的聯(lián)盟結構，并在這些聯(lián)盟結構上求解所有的最優(yōu)化問題的線性規(guī)劃最優(yōu)解。因此，該算法中并非所有云資源提供者都必須提供資源來完成請求。隨機云聯(lián)盟算法隨機選擇若干個云資源提供者組建一個聯(lián)盟。以上三種算法均采用分支限界法求解最優(yōu)化問題中的線性規(guī)劃問題。考慮四種不同類型的用戶請求為(10,0,0,0)、(10,10,0,0)、(10,10,10,0)、(10,10,10,10)，分別代表small、medium、large、extra large的VM請求。所有請求無法由單個云資源提供者完成，需要形成云資源提供者聯(lián)盟才能滿足用戶需求。本實驗執(zhí)行了10次仿真，并以得到的平均值進行性能分析。

圖1比較了本文算法與兩個對比算法得到的總體利益情況，在所有測試場景中，本文算法均得到了與最優(yōu)云聯(lián)盟算法一樣最高的利益。實驗結果證明隨機云聯(lián)盟算法在聯(lián)盟利益上并非是一種有效算法，例如：對于small型VM請求，本文算法和最優(yōu)云聯(lián)盟算法獲得的總利益為＄6.81，而隨機云聯(lián)盟算法的總利益僅為＄4.8。

圖1 云聯(lián)盟的總體利益

圖2是medium型VM請求時得到的聯(lián)盟中每個參與云資源提供者的個體利益值的情況，比較了三種不同的利益分割方式。本文算法采用的是標準化估計Banzhaf值的利益分割方式，兩種最優(yōu)云聯(lián)盟算法，一種利用標準化Banzhaf值進行利益分割，一種利用正比例利益方式進行利益在個體成員間的分配，而不使用Banzhaf值方式。這里，正比例利益分割方式意味著聯(lián)盟中每個參與的云資源提供者得到了與其價格一樣的利益分割，該價格為用戶向資源支付的費用與云資源提供者的資源代價之差。本文算法和最優(yōu)云聯(lián)盟算法(標準化Banzhaf值)獲得的總體利益為＄9.75，而兩種算法找到的聯(lián)盟規(guī)模為4，即{C2,C3,C4,C6}。本文算法搜索了53個聯(lián)盟才找到最終的聯(lián)盟結構，可以看出，本文算法與最優(yōu)云聯(lián)盟算法得到的聯(lián)盟個體成員的利益分割是非常接近的。

圖2 聯(lián)盟中個體云資源提供者的利益

圖3是三種算法的執(zhí)行時間比較，該結果是從3.00 GHz Intel quad-core PC 4 GB內(nèi)存的機器上運行得到的結果。對于8個云資源提供者可能形成的所有255個聯(lián)盟中，本文算法根據(jù)提出的聯(lián)盟合并和分裂規(guī)則僅僅考慮了其中部分聯(lián)盟結構的測試。平均來說，本文算法需要搜索48個聯(lián)盟才能找到最終的聯(lián)盟結構。因此，本文算法的執(zhí)行時間是遠小于最優(yōu)云聯(lián)盟算法的，后者是一種窮舉式方法，需要搜索所有的聯(lián)盟形式。對于每個聯(lián)盟，兩種算法僅需要求解線性規(guī)劃問題一次。對于large型VM請求，求解線性規(guī)劃需要更多時間，兩種算法的執(zhí)行時間也將相應增加。隨機云聯(lián)盟算法的執(zhí)行時間接近于0，因為它在單個聯(lián)盟上執(zhí)行一次線性規(guī)劃求解過程的時間花費僅為3.3微秒。

圖3 算法的執(zhí)行時間

4 結 語

為了實現(xiàn)資源聯(lián)盟的總體利益最大化，本文提出了一種云聯(lián)盟形成博弈算法。利用高效的聯(lián)盟合并與分裂機制，使云資源提供者能以穩(wěn)定的聯(lián)盟結構形態(tài)滿足用戶需求。此外，還設計了一種基于標準化估計Banshaf值法的總體利益在個體成員間的收益分割機制，不僅可以保證利益分配的公平性，而且還可以使得聯(lián)盟成員不會產(chǎn)生脫離聯(lián)盟結構的動機。