董 瑋

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

0 引 言

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

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

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

1 系統(tǒng)模型

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

1.2 云聯(lián)盟模型

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

每個(gè)子集F?I表示一個(gè)聯(lián)盟，若所有云資源提供者構(gòu)成一個(gè)聯(lián)盟，則稱(chēng)之為大聯(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)盟利益最大化問(wèn)題形式化為一個(gè)整數(shù)規(guī)劃問(wèn)題，目標(biāo)函數(shù)即：

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

(8)

式(2)代表v(F)，即聯(lián)盟F中云資源提供者可獲得的利益，等于用戶(hù)支付與資源代價(jià)之差。式(3)確保云資源提供者分配至用戶(hù)的內(nèi)核數(shù)量小于其可用內(nèi)核數(shù)量；式(4)確保云資源提供者分配至用戶(hù)的存儲(chǔ)量小于其可用存儲(chǔ)量；式(5)確保云資源提供者分配至用戶(hù)的每種類(lèi)型VM實(shí)例的內(nèi)核數(shù)量等于用戶(hù)請(qǐng)求該VM實(shí)例的內(nèi)核數(shù)量；式(6)確保云資源提供者分配至用戶(hù)的每種類(lèi)型VM實(shí)例的存儲(chǔ)量等于用戶(hù)請(qǐng)求該VM實(shí)例的存儲(chǔ)量；式(7)確保聯(lián)盟中的每個(gè)云資源提供者至少貢獻(xiàn)一種資源類(lèi)型。以上約束條件使得云資源提供者可以向聯(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)盟無(wú)法形成，即需要形成獨(dú)立且不相互的聯(lián)盟形式。聯(lián)盟博弈形成理論即是研究在大聯(lián)盟無(wú)法形成時(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難問(wèn)題。

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

定義1享樂(lè)博弈[13]。享樂(lè)博弈即為(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)盟形成問(wèn)題建立為享樂(lè)博弈模型，需要定義聯(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ò)合并規(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)盟形成和資源提供過(guò)程。因此，僅當(dāng)至少一個(gè)子聯(lián)盟可嚴(yán)格改進(jìn)其資源提供者的總體利益時(shí)，聯(lián)盟結(jié)構(gòu)可決定進(jìn)行分裂。在這種分裂規(guī)則下，其他子聯(lián)盟的利益可能降低。分裂規(guī)則可視為一種自私的聯(lián)盟決策，并不考慮分裂過(guò)程對(duì)于其他聯(lián)盟形式的影響。

通過(guò)合并/分裂過(guò)程，可能的聯(lián)盟形式被訪(fǎng)問(wèn)，其價(jià)值被計(jì)算。基于該價(jià)值，定義云資源提供者Ci的估計(jì)Banzhaf值為：

(12)

式中：V表示所有可遍歷訪(fǎng)問(wèn)的聯(lián)盟集合；λ表示包含Ci的所訪(fǎng)問(wèn)的聯(lián)盟總數(shù)，λ=2m-1-β，β表示沒(méi)有被訪(fǎng)問(wèn)的聯(lián)盟數(shù)量。估計(jì)Banzhaf值根據(jù)在合并與分裂過(guò)程中已被訪(fǎng)問(wèn)的聯(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)行合并與分裂過(guò)程中，根據(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)度的線(xiàn)性規(guī)劃問(wèn)題，進(jìn)而找到資源分配和聯(lián)盟的利益分配方案。算法定義B&B-VM-ALLOCATION(Fi)為實(shí)現(xiàn)求解聯(lián)盟Fi的線(xiàn)性規(guī)劃問(wèn)題的分支限界法的功能。

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

1. receive requestR

//接收來(lái)自用戶(hù)的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)盟合并過(guò)程開(kāi)始}

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ī)分配問(wèn)題

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

//滿(mǎn)足聯(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)盟分裂過(guò)程開(kāi)始}

29.forallFi∈FSwhere |Fi|>1do

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

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

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

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

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

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

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

33.if{Fj,Fk}ΔsFithen

//滿(mǎn)足聯(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)

//跳出分裂過(guò)程

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í)例的分配與提供

算法開(kāi)始于用戶(hù)發(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中已被訪(fǎng)問(wèn)的合并過(guò)程中的所有聯(lián)盟對(duì)。通過(guò)該矩陣，F(xiàn)S中所有可能的兩個(gè)聯(lián)盟組合在合并過(guò)程中均可被訪(fǎng)問(wèn)到。合并過(guò)程開(kāi)始于隨機(jī)選擇FS中的兩個(gè)未訪(fǎng)問(wèn)聯(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。合并過(guò)程再次試圖找到另一個(gè)未被訪(fǎng)問(wèn)適合于合并的聯(lián)盟對(duì)。如果所有聯(lián)盟均被測(cè)試，合并過(guò)程沒(méi)有發(fā)生，大聯(lián)盟得以形成，則合并過(guò)程終止。

通過(guò)合并過(guò)程得到的聯(lián)盟結(jié)構(gòu)FS接下來(lái)需要進(jìn)行分裂過(guò)程。在分裂過(guò)程中，所有擁有一個(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)分配方案。由于分裂過(guò)程是自私?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)盟合并過(guò)程重新開(kāi)始，為此，stop標(biāo)識(shí)符補(bǔ)充設(shè)置為false。連續(xù)多次的合并和分裂過(guò)程重復(fù)進(jìn)行直到算法終止，終止即表明此時(shí)對(duì)于在FS中的所有已有聯(lián)盟不會(huì)再選擇進(jìn)行聯(lián)盟合并或分裂過(guò)程。考慮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)盟將分配和提供給用戶(hù)任務(wù)相應(yīng)請(qǐng)求的VM實(shí)例。

2.3 算法性能分析

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

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

3) 算法時(shí)間復(fù)雜度分析。理論上，求解使得聯(lián)盟總體利益最大化的最優(yōu)聯(lián)盟結(jié)構(gòu)問(wèn)題與在所有云資源提供者上窮舉出所有聯(lián)盟分割結(jié)構(gòu)問(wèn)題具有同樣的時(shí)間復(fù)雜度。然而，本文算法設(shè)計(jì)了聯(lián)盟的合并與分裂機(jī)制，這樣在尋優(yōu)過(guò)程中是不需要列舉出所有的聯(lián)盟結(jié)構(gòu)形式的，大大地降低了算法搜索的時(shí)間復(fù)雜度。同時(shí)，本文算法的時(shí)間復(fù)雜性主要由聯(lián)盟進(jìn)行的合并與分裂次數(shù)以及子聯(lián)盟的規(guī)模(內(nèi)部擁有的云資源提供者的數(shù)量)相關(guān)。首先，考慮搜索過(guò)程中的最壞情況。在聯(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次合并的嘗試，依此類(lèi)推。則最壞的合并時(shí)間復(fù)雜度為O(m3)。此外，最壞情況下，聯(lián)盟F分裂過(guò)程的時(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è)云資源提供者提供四種類(lèi)型的VM實(shí)例的云資源提供環(huán)境，八個(gè)云資源提供者是實(shí)際環(huán)境中云資源間可以組建聯(lián)盟的合理估算。四種VM實(shí)例類(lèi)型VM={VM1,VM2,VM3,VM4}，分別代表small、medium、large、extra large的VM實(shí)例，VM實(shí)例的相關(guān)參數(shù)描述如表1所示。VM實(shí)例類(lèi)型和定價(jià)機(jī)制與Microsoft Azure相似。

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

3.2 結(jié)果分析

本文選取最優(yōu)云聯(lián)盟算法和隨機(jī)云聯(lián)盟算法作為對(duì)比算法。最優(yōu)云聯(lián)盟算法通過(guò)求解線(xiàn)性規(guī)劃問(wèn)題中式(7)所代表的松弛問(wèn)題尋找最優(yōu)的云資源提供者的分配方案。換言之，該算法尋找能夠使其收益達(dá)到最大化的聯(lián)盟結(jié)構(gòu)，即通過(guò)窮舉方法得到所有可能的聯(lián)盟結(jié)構(gòu)，并在這些聯(lián)盟結(jié)構(gòu)上求解所有的最優(yōu)化問(wèn)題的線(xiàn)性規(guī)劃最優(yōu)解。因此，該算法中并非所有云資源提供者都必須提供資源來(lái)完成請(qǐng)求。隨機(jī)云聯(lián)盟算法隨機(jī)選擇若干個(gè)云資源提供者組建一個(gè)聯(lián)盟。以上三種算法均采用分支限界法求解最優(yōu)化問(wèn)題中的線(xiàn)性規(guī)劃問(wèn)題?？紤]四種不同類(lèi)型的用戶(hù)請(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)求無(wú)法由單個(gè)云資源提供者完成，需要形成云資源提供者聯(lián)盟才能滿(mǎn)足用戶(hù)需求。本實(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à)格為用戶(hù)向資源支付的費(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è)試。平均來(lái)說(shuō)，本文算法需要搜索48個(gè)聯(lián)盟才能找到最終的聯(lián)盟結(jié)構(gòu)。因此，本文算法的執(zhí)行時(shí)間是遠(yuǎn)小于最優(yōu)云聯(lián)盟算法的，后者是一種窮舉式方法，需要搜索所有的聯(lián)盟形式。對(duì)于每個(gè)聯(lián)盟，兩種算法僅需要求解線(xiàn)性規(guī)劃問(wèn)題一次。對(duì)于large型VM請(qǐng)求，求解線(xiàn)性規(guī)劃需要更多時(shí)間，兩種算法的執(zhí)行時(shí)間也將相應(yīng)增加。隨機(jī)云聯(lián)盟算法的執(zhí)行時(shí)間接近于0，因?yàn)樗趩蝹€(gè)聯(lián)盟上執(zhí)行一次線(xiàn)性規(guī)劃求解過(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)滿(mǎn)足用戶(hù)需求。此外，還設(shè)計(jì)了一種基于標(biāo)準(zhǔn)化估計(jì)Banshaf值法的總體利益在個(gè)體成員間的收益分割機(jī)制，不僅可以保證利益分配的公平性，而且還可以使得聯(lián)盟成員不會(huì)產(chǎn)生脫離聯(lián)盟結(jié)構(gòu)的動(dòng)機(jī)。