基于聯盟博弈的云任務調度及Shapley值法的收益分配模型

張秋霞 何留杰 張來順

1 (黃河科技學院現代教育技術中心 鄭州 河南 450063)2 (中國人民解放軍信息工程大學電子技術學院 鄭州 河南 450004)

0 引 言

云計算系統擁有大量的服務器和公共用戶，可以頻繁調度和管理各種類型的應用任務。因此，為了獲得在相對平衡狀態下的系統中更好的調度結果，如何完成高效的任務調度與執行是系統面臨的核心問題[1]。云環境中的任務調度需要充分利用調度于數據中心中虛擬機上的任務特征。通常情況下，為了利用數據并行性，調度任務是可分割的。調度任務的負載以大數據集合為特征，集合中的每個元素需要一種特定類型的資源進行執行[2]。集合可劃分為多個小部分，每個部分需要進行一個調度決策。為了處理任務，任務集合的分割將最終被調度至云數據中心的虛擬機上。這些虛擬機被物理主機所擁有和運行，以獲得最大化利益為目標，而物理主機與提交任務的用戶可形成聯盟形式。

1 相關研究

關于云任務調度，智能算法是常見的一種方法。文獻[3]提出一種基于改進粒子群的調度算法，可以降低任務平均運行時間，以更高的搜索速度和收斂效率提高資源可用性。除了考慮任務調度時間，文獻[4]考慮了負載均衡，提出了一種多目標遺傳算法，以解決任務調度問題。以上方法的問題在于：僅從任務執行需求最大滿足度上考慮任務調度問題，而未考慮資源實際的使用狀態。文獻[4]將復雜大型任務劃分為多個小任務，并在虛擬機上進行映射。算法利用不同目標的權重決定采用的適應度函數，得到優化的云任務調度解。然而，該方法忽略了多任務執行間的相互影響，即任務執行在資源間的競爭關系。可見，智能算法優化任務調度時多集中于可行解間的尋優，而沒有考慮任務執行方與資源提供方之間的相互影響。

另外，博弈理論[5]是解決任務調度的另一種經濟學方法。相關工作中，文獻[6]設計了一種確保QoS的云任務調度博弈框架，可以利用Nash均衡得到最優的調度解。文獻[7]提出了一種基于負載均衡的任務調度博弈算法，其聯合了集中式算法的效率與分布式算法的容錯能力，將負載均衡問題定義為非合作博弈模型，并證明了任務調度存在Nash均衡解。以上兩種方法的不足之處在于都沒有驗證得到的任務調度的Nash均衡解是否收斂于唯一解上，這決定了調度算法的收斂性。文獻[8]基于非完全多代理動態博弈的行為分析模型，提出了一種博弈算法，可基于博弈者的當前行為和歷史信息，利用網絡發現方法改進任務調度效率。以上方法均以非合作博弈對云任務調度問題進行建模，其目標是以相互最優的方式獲得個體收益最優解，忽略了追求利益的共同體之間組建用戶聯盟競爭虛擬資源的可能性，可能使得實際獲得的收益并非最優。

合作博弈是優化任務調度的另一種博弈形式。文獻[9]提出一種基于QoS需求的云任務調度博弈模型，其任務調度的QoS問題被形式為合作博弈問題，并求解了滿足QoS需求的帕累托最優解。類似地，文獻[10]在任務調度中通過建立聯盟的形式增加個體效用，但所提模型的正確性未得到數學理論或實驗方面的驗證，缺乏說服力。

本文的研究不同于以上工作。在云環境中，寄宿于物理主機上的虛擬機VMs與任務用戶可以聯合起來以增加其收益。本文利用合作式博弈代替非合作式博弈。聯盟博弈是合作式博弈的一種形式，可以對群體決策者間的相互影響進行建模，能夠更好地獲得最小化代價或最大化任務調度收益的決策制定。

2 云任務調度模型

令云資源集為R={H,VM1,VM2,…,VMn}，其中，H為云數據中心的主機。部署于主機H上的每個虛擬機VMi具有屬性ti，表示VMi處理云任務單位負載的所需時間。li表示分配于VMi的負載劃分，liti表示VMi執行其分配負載的總時間。接收任務后，主機H需要將負載傳送至虛擬機。假設負載單元li從主機H傳送至VMi花費時間為liτ，τ為主機與任意虛擬機傳送單位負載的時間。

Ti(l)表示VMi執行負載l的完成時間，定義為從H發送負載li至VMi的時間與VMi上執行負載時間之和，即：

(1)

云任務調度問題的目標是得到一種負載分配l={l1,l2,…,ln}，使得最小化總執行時間T(l)，且：

T(l)=max{T1(l),T2(l),…,Tn(l)}

(2)

此時，任務調度最優化問題可形式化為：

Minimizel:T(l)

(3)

約束條件：

(4)

圖1所示為云任務執行的時間示意圖。

圖1 任務調度時負載執行示意圖

式(3)和式(4)定義的問題可通過算法1給出的常規調度算法MIN_TIME算法計算得到，該算法的主要特征是以貪婪的方式得到執行時間達到最小的任務調度解。

算法1 MIN_TIME

1. Input:ti,i=1,2,…,n,τ

2. Output:lj,j=1,2,…,n

3. Initializeti,τ

4. Forj=1,2,…,n-1

5.kj←tj/(tj+τ+1)

6. End For

8. Fori=2,3,…,n

10. End For

11. Returnlj

算法詳細說明：算法輸入為虛擬機處理單位負載的所需時間和單位負載的傳送時間，算法輸出為最終分配給虛擬機的負載分配解，即步驟1-步驟2；步驟3對輸入參數進行初始化操作；步驟4-步驟6計算每個擬部署虛擬機的處理負載時間的占比；步驟7計算第一個虛擬機的負載分配；步驟8-步驟10依次為其他虛擬機進行負載分配；最后在步驟11返回任務的調度情況。

對于式(3)和式(4)定義的問題，計算分配的另一種方法是遞歸地將虛擬機替換為單個等價虛擬機。一個等價VM擁有與其構成VMs的相同能力。為了計算對于VM1,VM2,…,VMk的等價執行時間，可以將Ti(l)中的最長完成時間減去通信時間，即可得到等價執行時間teq：

teq=max(T1(l),T2(l),…,Tk(l))-τ

(5)

當所有VMs在相同時間完成執行時(系統狀態最優)，以上等式可簡化為：

teq=t1l1-τ(1-l1)

(6)

當VM1為第一分配負載的VM時，可通過算法2替代算法1求解式(3)和式(4)定義的最優化問題，且其時間復雜度為O(n)。

算法2 R_MIN_TIME

1. Input:ti,i=1,2,…,n,τ

2. Output:lj,j=1,2,…,n

3. Initializeti,τ

4.l1←1

5.teq←t1

6. Forj=2,3,...,n

7.leq,lj←MIN_TIME(teq,tj,τ)

8.teq←teqleq-τ(1-leq)

9. End For

10. Forj=n-1,n-2,…,1

11.lj←1-lj+1

12. End For

13. Returnlj

算法詳細說明：算法輸入為虛擬機處理單位負載的所需時間和單位負載的傳送時間，算法輸出為最終分配給虛擬機的負載分配解，即步驟1-步驟2；步驟3對輸入參數進行初始化操作；步驟4-步驟5分別設置初始負載和為虛擬機設置初始的等價執行時間；步驟6-步驟9利用算法1計算在等價執行時間下得到的各虛擬機的負載分配，并對新分配下的等價執行時間作出更新；步驟10-步驟12正式為各個虛擬機進行負載分配；最后在步驟13返回最終的負載分配解。

無論使用算法1或算法2，均只優化了任務調度問題的執行時間，即獲得了最小化執行跨度的負載分配方案。接下來，本文將利用聯盟博弈理論，建立以上的任務調度模型，并將模型擴展為求解最小化執行跨度與VMs執行代價之和的負載分配方案。

3 基于聯盟博弈的任務調度

為了獲得最小的執行時間，提交任務的用戶與資源方(VMs)間需要形成調度的合作聯盟，在考慮博弈實體理性的前提下，以相互協作的方式獲得最優的任務執行效率。

令T為需要執行的任務集，T={l1,l2,…,ln}。以下描述任務調度的聯盟博弈模型：

定義1 博弈參與者 聯盟N中的所有實體定義為博弈參與者，包括任務T與虛擬機VM1,VM2,…,VMn。

定義2 博弈策略 由T和k個VMs組成的聯盟S?N的策略集合為T至S中VMs的所有分割負載分配集合。

定義3 效用函數 聯盟博弈中的博弈參考者的偏好表達為效用。作為博弈實體，VMi的偏好可表示為以下效用函數：

Ui=mi-liti?i=1,2,…,n

(7)

式中：mi為VMi初始擁有費用與執行任務后的費用之差。且：

(8)

對于另一博弈實體，任務T的偏好可表示為：

(9)

式中：CT為常量，表示如果T能即刻執行時得到的報酬，T為執行CT花費的時間，mT與mi定義類似。

那么，基于聯盟博弈的任務調度模型[{T,VMi},{li},{UT,Ui}]可標識為maxl(UT+Ui),i=1,2,…,n。在聯盟博弈方法中，對于理性的博弈參考者，他們將選擇確定的博弈策略，獲得最大化效用。

定義4 Shapley值 Shapley值定義為φ=(φ1,φ2,…,φn)，對于i=1,2,…,n，有：

(10)

式中：P(N)為N的冪集。

VMi的效用可以反映隨著其負載分配大小的增加，在其執行代價上的相應增加情況。VMi的效用同時考慮了執行代價與費用改變之和。T的效用則同時考慮了執行跨度與執行代價。

(11)

如果v(S)=0，無須執行任務，且參與者的效用保持不變。當效用發生改變時主要包括以下兩種情況：

1) 對于任意博弈參與者i,i∈S, 如果i的效用為負(Ui<0)，則i必須向其他參與者支付費用，因此，mi<0。博弈者i可以不向任意博弈者支付費用下增加其效用，導致Ui=0。

如果v(S)>0，則執行T至其完成。換言之，特征函數表明負載將被分配并得到最小化的執行跨度和執行代價。

證明：通過MIN-TIME算法，可以得到最小化執行跨度的負載分配l。從VM1和VM2開始，如果T在VM2上減少δ個單元分配，并將其分配至VM1，則總代價的變化c′為：

c′=δ(2t1-t2+τ)

(12)

如果t2>2t1+τ，則空閑VM2并分配其負載至VM1將降低代價l2(t2-2t1-τ)。將VM3,VM4,…,VMn置為空閑因為這些VMs較VM2擁有相等或更大的執行時間。否則，需要將VM1和VM2替換為VMeq，執行代價為ceq=l1t1+l2t2，執行時間為teq=T(l)-τ。現在比較VM3和VMeq的執行時間。如果T分配δ單元負載從VM3至VMeq上，則總代價變化為：

c′=δ(T(l)+pceq-t3)

(13)

定理1表明：如果較慢的VMs的執行時間大于執行代價、通信參數和由更慢VMs構成的等價VM的執行時間之和，則執行時間等于或大于較慢VM執行時間的所有VMs均應是空閑的，以降低總代價。實際上，如一個較慢VM超過對于單一快VM的約束，則必須將慢VMs設置為空閑以降低總代價。

定理2 聯盟博弈算法得到的調度解的核是非空的。

證明：對于聯盟博弈形式，令x=(x1,x2,…,xn)為支付矢量，xi為博弈者i的支付。支付xi可量化i的效用變化。imputation為一個滿足群體理性和個體理性的支付矢量，定義為：

xi≥v({i}) for alli∈N}

(14)

如果VMi執行負載，則其代價為liti。VMi得到的支付為mi=liti，以表示執行代價的補償。因此，對于li=0時，支付xi=0，此時不產生代價。如果設mi=0，則VMi的支付為xi=0。

定理2表明：核是穩定imputations的集合，表明對大聯盟N的穩定性度量。如果核是非空的，則存在imputations，在其中比較其他聯盟組成，博弈參與者將更加偏好大聯盟形式。如果核是空的，則相反。

根據定理2，本文所提的聯盟博弈方法可以產生穩定的聯盟結構形式。基于以上的結果，設計了一種基于聯盟博弈的任務調度算法MIN_COST，可以改進R_MIN_TIME算法未考慮任務調度與資源分配兩種行為的相互影響，使任務調度的代價真正達到最小。

算法3給出了MIN_COST算法的偽代碼，其時間復雜度為O(nlgn)。

算法3 MIN_COST

1. Input:ti,i=1,2,…,n,τ

2. Output:lj,j=1,2,…,n

3. Initializeti,τ

4. Sort the VMs in non-decreasing order ofti

5.l1←1

6.teq←t1

7.pceq←t1

8. Forj=2,3,…,n

9. Iftj>pceq+teq+τ

10. Break

11. End If

12.leq,lj←MIN_TIME(teq,tj,τ)

13.pceq←leqteq+ljtj

14.teq←teqleq-τ(1-leq)

15. End For

16. Fori=j-2,j-3,…,1

17.li←li+1

18. End For

19. Fori=j,j+1,…,m

20.li←0

21. End For

22. Returnlj

算法詳細說明：算法輸入為虛擬機處理單位負載的所需時間和單位負載的傳送時間，算法輸出為最終分配給虛擬機的負載分配解，即步驟1-步驟2；步驟3對輸入參數進行初始化操作；步驟4根據單位負載執行時間的非降序排列對所有虛擬機進行排序；步驟5-步驟7分別設置初始負載和為虛擬機設置初始的等價執行時間；步驟8-步驟15為各個虛擬機計算替換為等價虛擬機時得到的等價時間；步驟16-步驟18在以上基礎上計算新的負載分配；步驟19-步驟21將完全空閑的虛擬機分配零負載；最后在步驟22返回最終的負載分配解。

4 仿真實驗

利用CloudSim平臺[11]進行仿真實驗，評估本文的基于聯盟博弈理論的任務調度算法的性能。實驗環境中設置兩個物理主機，每臺主機配置十臺虛擬機，表示為R= {H,VM1,VM2,…,VM10}。兩組虛擬機VMs的計算特征以相對計算能力MIPS進行度量，表1給出了兩組VMs的執行時間的相對值。

表1 VMs的相對執行時間

圖2表示兩組VMs下任務調度總代價情況。圖中橫軸表示空閑VMs的數量(即其上不分配任務負載)。由于Group1中的所有VMs擁有更高的執行性能(更少的執行時間)，在所有VMs均分配負載時擁有更小的總代價。而由于VMs的空閑，執行跨度將增加，這相應地會導致總代價增加。對于擁有更高性能的Group 2中的VMs而言，可以看出，當VM6-VM10空閑時，總代價是最小的。同時，當空閑VMs數量為5時，兩條曲線聚焦于一點上，由于此時VM6-VM10為空閑。換言之，此時兩組VMs中VM1-VM5擁有相同的執行跨度。

圖2 總代價

圖3給出聯盟博弈算法的Shapley值情況，它表示所有聯盟成員的支付。可以看出，對于Group2中的VMs，VMs性能在降低，任務對其支付也將降低。同時，VMs得到的支付是非零的，這表明VMs可以得到報酬。擁有相同執行時間的VMs會得到相同的支付，這是Shapley值的對稱條件得到的結果。由于Group2中的VMs擁有更高的執行性能，所以會得到比Group1更高的支付。

圖3 所有聯盟成員的Shapley值

圖4給出了非合作博弈算法[5]與本文的聯盟博弈算法得到的執行跨度比較情況。本實驗中，擁有更高執行性能的Group1選擇為測試資源。可以看出，無論是否合作，隨著調度任務數量的增加，執行跨度將增加，這是因為更多的任務將導致在固定VMs上執行更長的時間。聯盟博弈算法的執行跨度小于非合作博弈算法，這是由于任務用戶與主機上的VMs可以形成聯盟的形式執行任務，以獲得更高的收益，這可以使得兩個博弈實體間進行協作，以更高性能的VMs執行任務。

圖4 執行跨度

圖5和圖6觀察了聯盟形成前后資源方和任務方的平均效用值變化情況。可以看到，隨著調度任務數量的增加，無論是否形成聯盟，資源方的平均效用是增加的，這是因為執行更多的任務可以為資源提供方帶來更多的收益。而形成聯盟后，無論是資源方平均效用值還是任務方平均效用值，都得到了提升，原因在于協作式的任務調度方式可以有效提高任務執行的整體收益，而基于Shapley值法的效用分配方式，可以使得各個博弈參與者得到最優的收益分配，高于聯盟形成前的個體收益。

圖5 聯盟形成前后資源方平均效用值

圖6 聯盟形成前后任務方平均效用值

5 結 語

本文提出了一種云計算環境中基于聯盟博弈的任務調度算法。不同于先前工作，該算法的目標是最小化由于執行跨度與資源方執行任務帶來的代價構成的總體代價。該聯盟博弈算法存在非空的核，這表明任務方與虛擬機資源方不會脫離聯盟組織，即聯盟結構將一直保持穩定。實驗結果表明，聯盟博弈算法能夠降低執行任務的總體代價，且聯盟博弈中基于Shapley值的聯盟成員間支付分配方法是公平合理的。