董 瑋

(吉林開放大學(xué) 吉林 長(zhǎng)春 130022)

0 引 言

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

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

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

1 系統(tǒng)模型

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

1.2 云聯(lián)盟模型

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

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

(1)

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

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

(8)

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

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

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

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

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

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

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

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

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

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

(9)

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

為了找到一個(gè)相比其他聯(lián)盟結(jié)構(gòu)更加偏好的聯(lián)盟，定義兩種比較關(guān)系分別為合并關(guā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)盟{(lán)F∪F′}獲得的利益大于F和F′獲得的利益，聯(lián)盟{(lán)F∪F′}比較兩個(gè)不相互的聯(lián)盟{(lán)F,F′}將獲得選擇偏好，如此所有資源提供者可以改進(jìn)其總利益。式(11)表明如果至少一個(gè)聯(lián)盟可以在不影響其他博弈者的情況下維持相同利益或增加其成員的利益，則{F,F′}將獲得比{F∪F′}更大的選擇偏好。

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

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

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

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

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

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

(12)

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

(13)

每個(gè)成員Ci可從大聯(lián)盟結(jié)構(gòu)中獲得的利益計(jì)算為：

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

(14)

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

(15)

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

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

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

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

1. receive requestR

//接收來自用戶的VM服務(wù)請(qǐng)求

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

//初始聯(lián)盟結(jié)構(gòu)設(shè)置

3. calculatev(Fi) forFi∈FS

//計(jì)算聯(lián)盟價(jià)值

4.repeat

5.stop←TURE

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

7.visited[Fi][Fj]←FALSE

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

8.endfor

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

10. repeat

11.flag←TURE

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

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

13.visited[Fi][Fj]←TRUE

//設(shè)置聯(lián)盟對(duì)已被遍歷

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

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

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)盟結(jié)構(gòu)中的所有聯(lián)盟對(duì)上進(jìn)行遍歷

23.ifnotvisited[Fi][Fj]then

24.flag←FALSE

//設(shè)置終止標(biāo)識(shí)

25.endif

26.endfor

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

//合并終止條件

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

29.forallFi∈FSwhere |Fi|>1do

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

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

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

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

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

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

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

33.if{Fj,Fk}ΔsFithen

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

34.Fi←Fj{that isFS=FSFi}

//更新聯(lián)盟

35.FS=FS∪Fk

//更新聯(lián)盟結(jié)構(gòu)

36.stop←FALSE

//設(shè)置終止標(biāo)識(shí)

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)盟進(jìn)行虛擬機(jī)資源的分配

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

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

44.Fkallocates and provides the requested VM instances

//完成VM實(shí)例的分配與提供

算法開始于用戶發(fā)送的請(qǐng)求。聯(lián)盟結(jié)構(gòu)FS由單個(gè)Ci∈I構(gòu)成一個(gè)聯(lián)盟Fi的形式構(gòu)成。然后，算法計(jì)算v(Fi)，利用矩陣visited記錄FS中已被訪問的合并過程中的所有聯(lián)盟對(duì)。通過該矩陣，F(xiàn)S中所有可能的兩個(gè)聯(lián)盟組合在合并過程中均可被訪問到。合并過程開始于隨機(jī)選擇FS中的兩個(gè)未訪問聯(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)盟依然可被選擇。因此，對(duì)于所有的Fk∈FS，k≠i,visited[Fi][Fk]均設(shè)置為false。合并過程再次試圖找到另一個(gè)未被訪問適合于合并的聯(lián)盟對(duì)。如果所有聯(lián)盟均被測(cè)試，合并過程沒有發(fā)生，大聯(lián)盟得以形成，則合并過程終止。

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

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

2.3 算法性能分析

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

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置

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

表1 可用的VM實(shí)例屬性

3.2 結(jié)果分析

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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