基于聯(lián)盟博弈的云任務(wù)調(diào)度及Shapley值法的收益分配模型

張秋霞 何留杰 張來(lái)順

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

0 引 言

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

1 相關(guān)研究

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

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

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

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

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

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

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

(1)

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

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

(2)

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

Minimizel:T(l)

(3)

約束條件：

(4)

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

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

式(3)和式(4)定義的問(wèn)題可通過(guò)算法1給出的常規(guī)調(diào)度算法MIN_TIME算法計(jì)算得到，該算法的主要特征是以貪婪的方式得到執(zhí)行時(shí)間達(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ì)說(shuō)明：算法輸入為虛擬機(jī)處理單位負(fù)載的所需時(shí)間和單位負(fù)載的傳送時(shí)間，算法輸出為最終分配給虛擬機(jī)的負(fù)載分配解，即步驟1-步驟2；步驟3對(duì)輸入?yún)?shù)進(jìn)行初始化操作；步驟4-步驟6計(jì)算每個(gè)擬部署虛擬機(jī)的處理負(fù)載時(shí)間的占比；步驟7計(jì)算第一個(gè)虛擬機(jī)的負(fù)載分配；步驟8-步驟10依次為其他虛擬機(jī)進(jìn)行負(fù)載分配；最后在步驟11返回任務(wù)的調(diào)度情況。

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

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

(5)

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

teq=t1l1-τ(1-l1)

(6)

當(dāng)VM1為第一分配負(fù)載的VM時(shí)，可通過(guò)算法2替代算法1求解式(3)和式(4)定義的最優(yōu)化問(wèn)題，且其時(shí)間復(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ì)說(shuō)明：算法輸入為虛擬機(jī)處理單位負(fù)載的所需時(shí)間和單位負(fù)載的傳送時(shí)間，算法輸出為最終分配給虛擬機(jī)的負(fù)載分配解，即步驟1-步驟2；步驟3對(duì)輸入?yún)?shù)進(jìn)行初始化操作；步驟4-步驟5分別設(shè)置初始負(fù)載和為虛擬機(jī)設(shè)置初始的等價(jià)執(zhí)行時(shí)間；步驟6-步驟9利用算法1計(jì)算在等價(jià)執(zhí)行時(shí)間下得到的各虛擬機(jī)的負(fù)載分配，并對(duì)新分配下的等價(jià)執(zhí)行時(shí)間作出更新；步驟10-步驟12正式為各個(gè)虛擬機(jī)進(jìn)行負(fù)載分配；最后在步驟13返回最終的負(fù)載分配解。

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

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

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

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

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

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

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

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

(7)

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

(8)

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

(9)

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

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

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

(10)

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

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

(11)

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

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

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

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

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

(12)

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

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

(13)

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

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

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

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

(14)

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

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

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

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

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

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

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

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

圖2 總代價(jià)

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

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

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

圖4 執(zhí)行跨度

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

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

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

5 結(jié) 語(yǔ)

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