張秋霞 何留杰 張來順

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

0 引 言

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

1 相關(guān)研究

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

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

合作博弈是優(yōu)化任務(wù)調(diào)度的另一種博弈形式。文獻(xiàn)[9]提出一種基于QoS需求的云任務(wù)調(diào)度博弈模型，其任務(wù)調(diào)度的QoS問題被形式為合作博弈問題，并求解了滿足QoS需求的帕累托最優(yōu)解。類似地，文獻(xiàn)[10]在任務(wù)調(diào)度中通過建立聯(lián)盟的形式增加個體效用，但所提模型的正確性未得到數(shù)學(xué)理論或?qū)嶒灧矫娴尿炞C，缺乏說服力。

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

2 云任務(wù)調(diào)度模型

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

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

(1)

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

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

(2)

此時，任務(wù)調(diào)度最優(yōu)化問題可形式化為：

Minimizel:T(l)

(3)

約束條件：

(4)

圖1所示為云任務(wù)執(zhí)行的時間示意圖。

圖1 任務(wù)調(diào)度時負(fù)載執(zhí)行示意圖

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

算法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

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

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

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

(5)

當(dāng)所有VMs在相同時間完成執(zhí)行時(系統(tǒng)狀態(tài)最優(yōu))，以上等式可簡化為：

teq=t1l1-τ(1-l1)

(6)

當(dāng)VM1為第一分配負(fù)載的VM時，可通過算法2替代算法1求解式(3)和式(4)定義的最優(yōu)化問題，且其時間復(fù)雜度為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

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

無論使用算法1或算法2，均只優(yōu)化了任務(wù)調(diào)度問題的執(zhí)行時間，即獲得了最小化執(zhí)行跨度的負(fù)載分配方案。接下來，本文將利用聯(lián)盟博弈理論，建立以上的任務(wù)調(diào)度模型，并將模型擴(kuò)展為求解最小化執(zhí)行跨度與VMs執(zhí)行代價之和的負(fù)載分配方案。

3 基于聯(lián)盟博弈的任務(wù)調(diào)度

為了獲得最小的執(zhí)行時間，提交任務(wù)的用戶與資源方(VMs)間需要形成調(diào)度的合作聯(lián)盟，在考慮博弈實體理性的前提下，以相互協(xié)作的方式獲得最優(yōu)的任務(wù)執(zhí)行效率。

令T為需要執(zhí)行的任務(wù)集，T={l1,l2,…,ln}。以下描述任務(wù)調(diào)度的聯(lián)盟博弈模型：

定義1 博弈參與者 聯(lián)盟N中的所有實體定義為博弈參與者，包括任務(wù)T與虛擬機(jī)VM1,VM2,…,VMn。

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

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

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

(7)

式中：mi為VMi初始擁有費用與執(zhí)行任務(wù)后的費用之差。且：

(8)

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

(9)

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

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

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

(10)

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

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

(11)

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

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

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

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

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

(12)

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

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

(13)

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

定理2 聯(lián)盟博弈算法得到的調(diào)度解的核是非空的。

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

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

(14)

如果VMi執(zhí)行負(fù)載，則其代價為liti。VMi得到的支付為mi=liti，以表示執(zhí)行代價的補償。因此，對于li=0時，支付xi=0，此時不產(chǎn)生代價。如果設(shè)mi=0，則VMi的支付為xi=0。

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

根據(jù)定理2，本文所提的聯(lián)盟博弈方法可以產(chǎn)生穩(wěn)定的聯(lián)盟結(jié)構(gòu)形式?；谝陨系慕Y(jié)果，設(shè)計了一種基于聯(lián)盟博弈的任務(wù)調(diào)度算法MIN_COST，可以改進(jìn)R_MIN_TIME算法未考慮任務(wù)調(diào)度與資源分配兩種行為的相互影響，使任務(wù)調(diào)度的代價真正達(dá)到最小。

算法3給出了MIN_COST算法的偽代碼，其時間復(fù)雜度為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

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

4 仿真實驗

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

表1 VMs的相對執(zhí)行時間

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

圖2 總代價

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

圖3 所有聯(lián)盟成員的Shapley值

圖4給出了非合作博弈算法[5]與本文的聯(lián)盟博弈算法得到的執(zhí)行跨度比較情況。本實驗中，擁有更高執(zhí)行性能的Group1選擇為測試資源?？梢钥闯?，無論是否合作，隨著調(diào)度任務(wù)數(shù)量的增加，執(zhí)行跨度將增加，這是因為更多的任務(wù)將導(dǎo)致在固定VMs上執(zhí)行更長的時間。聯(lián)盟博弈算法的執(zhí)行跨度小于非合作博弈算法，這是由于任務(wù)用戶與主機(jī)上的VMs可以形成聯(lián)盟的形式執(zhí)行任務(wù)，以獲得更高的收益，這可以使得兩個博弈實體間進(jìn)行協(xié)作，以更高性能的VMs執(zhí)行任務(wù)。

圖4 執(zhí)行跨度

圖5和圖6觀察了聯(lián)盟形成前后資源方和任務(wù)方的平均效用值變化情況?？梢钥吹?，隨著調(diào)度任務(wù)數(shù)量的增加，無論是否形成聯(lián)盟，資源方的平均效用是增加的，這是因為執(zhí)行更多的任務(wù)可以為資源提供方帶來更多的收益。而形成聯(lián)盟后，無論是資源方平均效用值還是任務(wù)方平均效用值，都得到了提升，原因在于協(xié)作式的任務(wù)調(diào)度方式可以有效提高任務(wù)執(zhí)行的整體收益，而基于Shapley值法的效用分配方式，可以使得各個博弈參與者得到最優(yōu)的收益分配，高于聯(lián)盟形成前的個體收益。

圖5 聯(lián)盟形成前后資源方平均效用值

圖6 聯(lián)盟形成前后任務(wù)方平均效用值

5 結(jié) 語

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