一種云間合作博弈資源提供方法

董 瑋

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

0 引 言

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

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

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

1 系統模型

1.1 云資源提供系統模型

1.2 云聯盟模型

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

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

(1)

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

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

(8)

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

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

2 云聯盟形成機制

2.1 云聯盟形成模型

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

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

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

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

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

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

(9)

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

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

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

合并規則：若{F∪F′}Δm{F,F′}，則需合并聯盟集合{F,F′}；

分裂規則：若{F,F′}Δs{F∪F′}，則需分裂聯盟{F∪F′}。

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

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

通過合并/分裂過程，可能的聯盟形式被訪問，其價值被計算。基于該價值，定義云資源提供者Ci的估計Banzhaf值為：

(12)

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

(13)

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

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

(14)

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

(15)

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

2.2 云聯盟形成算法

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

算法1云聯盟形成算法

1. receive requestR

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

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

//初始聯盟結構設置

3. calculatev(Fi) forFi∈FS

//計算聯盟價值

4.repeat

5.stop←TURE

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

7.visited[Fi][Fj]←FALSE

//初始化聯盟對為未遍歷

8.endfor

9. {聯盟合并過程開始}

10. repeat

11.flag←TURE

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

//隨機選擇聯盟對進行合并嘗試

13.visited[Fi][Fj]←TRUE

//設置聯盟對已被遍歷

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

//分支限界法求解該聯盟上的虛擬機分配問題

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

//滿足聯盟合并規則

16.Fi←Fi∪Fj{mergeFiandFj}

//聯盟合并

17.Fj←? {Fjis removed fromFS}

//更新聯盟

18.forallFk∈FS,k≠i,do

19.visited[Fi][Fk]←FALSE

20.endfor

21.endif

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

//在聯盟結構中的所有聯盟對上進行遍歷

23.ifnotvisited[Fi][Fj]then

24.flag←FALSE

//設置終止標識

25.endif

26.endfor

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

//合并終止條件

28. {聯盟分裂過程開始}

29.forallFi∈FSwhere |Fi|>1do

//在所成員數大于1的聯盟上進行遍歷

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

//對所有沒有交集的聯盟分裂形式進行遍歷

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

//分支限界法求解該聯盟上的虛擬機分配問題

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

//分支限界法求解該聯盟上的虛擬機分配問題

33.if{Fj,Fk}ΔsFithen

//滿足聯盟分裂規則

34.Fi←Fj{that isFS=FSFi}

//更新聯盟

35.FS=FS∪Fk

//更新聯盟結構

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}}

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

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

//計算所得聯盟中云資源提供者的利益分割

44.Fkallocates and provides the requested VM instances

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

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

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

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

2.3 算法性能分析

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

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

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

3 仿真實驗

3.1 實驗配置

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

表1 可用的VM實例屬性

3.2 結果分析

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

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

圖1 云聯盟的總體利益

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

圖2 聯盟中個體云資源提供者的利益

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

圖3 算法的執行時間

4 結 語

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