多任務并發(fā)邊緣計算環(huán)境中最優(yōu)聯(lián)盟結(jié)構生成策略

趙庶旭，韋萍，王小龍

（蘭州交通大學電子與信息工程學院，甘肅 蘭州 730071）

0 引言

隨著物聯(lián)網(wǎng)的快速發(fā)展，其設備數(shù)量的爆炸性增長所產(chǎn)生的大量數(shù)據(jù)發(fā)送至云端處理會導致高時延、低帶寬等一系列問題。移動邊緣計算（MEC,mobile edge computing）[1]提供了一種新的計算范式：在更接近用戶或數(shù)據(jù)源的物理位置上處理和分析數(shù)據(jù)，以此來降低時延、節(jié)省帶寬。然而在此環(huán)境下，資源受限的邊緣節(jié)點在面對多任務并發(fā)場景時存在以下問題。

1) 單個邊緣節(jié)點由于自身資源受限無法獨立完成任務，或無法滿足時延敏感型任務需求。

2) 邊緣資源有限且高度分布，現(xiàn)有的資源調(diào)度方案并不能最大化其資源利用率。

聯(lián)盟結(jié)構（CS,coalition structure）作為一種用來求解合作問題的模型，廣泛應用于傳感器融合[2]、無線通信網(wǎng)絡融合[3]、蜂窩網(wǎng)絡協(xié)作[4]和資源協(xié)同調(diào)度[5]等領域。邊緣計算環(huán)境中邊緣節(jié)點資源受限條件下的多任務并發(fā)資源調(diào)度問題[6]可以轉(zhuǎn)化為最優(yōu)聯(lián)盟結(jié)構生成問題。聯(lián)盟結(jié)構在多任務并發(fā)條件下是所有邊緣節(jié)點集合的劃分。其中，邊緣聯(lián)盟是一組平等且通過合作共同完成任務的邊緣節(jié)點集合。在多任務并發(fā)情況下，邊緣節(jié)點為完成一組并發(fā)任務所產(chǎn)生的一組聯(lián)盟稱為聯(lián)盟結(jié)構，其最終目的是通過生成最優(yōu)聯(lián)盟結(jié)構使社會福利（效用）最大化。然而在邊緣計算環(huán)境中由于并發(fā)任務數(shù)量、邊緣節(jié)點密度、節(jié)點計算能力、優(yōu)化目標和約束條件等因素的影響，最優(yōu)聯(lián)盟結(jié)構的生成問題較復雜，已成為邊緣計算領域的一大挑戰(zhàn)。

在有n個智能體的系統(tǒng)中，可能的聯(lián)盟結(jié)構的總數(shù)為貝爾數(shù)，因此無法使用窮盡法搜索得到最優(yōu)的聯(lián)盟結(jié)構解。胡山立等[7]在最壞條件下提出了一種新的分組方法和給定限界的聯(lián)盟結(jié)構生成算法。Rahwan[8]將所有潛在聯(lián)盟結(jié)構空間劃分為包含相似聯(lián)盟結(jié)構的子空間，從而使用分支限界法高效地搜索所選子空間。張新良等[9]針對聯(lián)盟數(shù)量是智能體個數(shù)的指數(shù)倍的問題，基于智能體合作收益獨立性，提出聯(lián)盟快速動態(tài)生成算法，并對聯(lián)盟結(jié)構圖進行剪枝，降低了搜索空間大小。徐廣斌等[10]利用動態(tài)規(guī)劃原理針對聯(lián)盟個數(shù)約束的特殊性，設計了聯(lián)盟約束動態(tài)規(guī)劃算法，并證明其算法時間復雜度為O(3n)。以上算法往往適用于求解小型實例下的聯(lián)盟結(jié)構生成問題。但由于邊緣計算環(huán)境的特殊性，邊緣節(jié)點密度相對較高，使用上述算法解決邊緣計算環(huán)境下的聯(lián)盟結(jié)構生成問題存在一定的局限性。

啟發(fā)式算法求解最優(yōu)聯(lián)盟結(jié)構生成問題因其簡單直接并能在可接受的時間范圍內(nèi)找到一個相對較優(yōu)的解而受到廣泛關注。對于求解聯(lián)盟結(jié)構，Sen 等[11]首先引入了遺傳算法，并采用一維積分編碼來搜索最優(yōu)聯(lián)盟結(jié)構。Yang[12]在Sen 等[11]工作的基礎上，提出了一種基于二維二進制染色體編碼及交叉和變異算子的不相交聯(lián)盟形成算法。Contreras等[13]使用改進編碼的遺傳算法求解聯(lián)盟結(jié)構生成問題，其能夠在一個合理的計算時間內(nèi)獲得高質(zhì)量的解。蔣建國等[14]引入蟻群算法解決多任務聯(lián)盟問題。蟻群基于信息正反饋機制選擇協(xié)作性能較好的智能體組成聯(lián)盟，有效減少了聯(lián)盟生成的時間以及計算量，但該算法只適用于多任務串行計算場景。Lin等[15]將二進制粒子群優(yōu)化（BPSO,binary particle swarm optimization）算法擴展為二維二進制編碼，并討論了如何修復無效編碼使其有效，但該編碼方案效率不高。據(jù)Zhang 等[16]所述，在文獻[11-15]的方法中，粒子群優(yōu)化（PSO,particle swarm optimization）算法可以得到與遺傳算法（GA,genetic algorithm）和蟻群優(yōu)化（ACO,ant clony optimization）算法相似的結(jié)果，但計算時間明顯快于GA與ACO，尤其在解決較大規(guī)模實例方面。與遺傳算法相比，粒子群算法沒有交叉和變異算子，且算法所需調(diào)整的參數(shù)少。基于此，本文對性能更優(yōu)的粒子群算法進行了改進。

在利用粒子群算法對聯(lián)盟結(jié)構進行研究方面，Zhang 等[16]開發(fā)了一種一維二進制編碼方案，在每次迭代過程中使用編碼修復策略確保每個編碼都是近似有效的。許金友[17]對傳統(tǒng)的基于多任務并發(fā)的聯(lián)盟問題進行了分析，指出聯(lián)盟資源利用方面的不足，并使用離散粒子群優(yōu)化算法求解多任務聯(lián)盟結(jié)構生成問題。Hu 等[18]借鑒堆智能離散粒子群優(yōu)化算法解決資源分配問題的思想[19]，構造了一種描述資源調(diào)度方案的聯(lián)盟結(jié)構表達式。將邊緣計算環(huán)境中的資源調(diào)度問題轉(zhuǎn)化為優(yōu)化問題模型，設計了適應聯(lián)盟結(jié)構編碼方式的多進制離散粒子群優(yōu)化算法。Zhang等[20]在Hu等[18]的基礎上結(jié)合合作博弈與啟發(fā)式算法的優(yōu)點，引入討價還價集的概念。通過判斷非討價還價聯(lián)盟來消除一部分不滿足條件的聯(lián)盟結(jié)構，從而達到縮小搜索策略空間的目的。最后使用改進的多進制離散粒子群優(yōu)化（MDPSO,m-ary discrete particle swarm optimization）算法進行聯(lián)盟結(jié)構的搜索，找到近似最優(yōu)的聯(lián)盟結(jié)構解。

綜上所述，PSO 算法[21]在求解邊緣計算環(huán)境下的多任務并發(fā)問題上已經(jīng)取得了一定的成果。但在任務數(shù)和邊緣節(jié)點數(shù)量多的情況下，算法運行時間較長、穩(wěn)定性不能保證且容易陷入局部最優(yōu)解。為了解決上述問題，本文從多進制離散粒子群的位置更新部分出發(fā)，提出一種新的位置更新方式——基于離散最近過去的位置更新策略（DRPPUS,discrete recent past-based position updating strategy）。在每一次迭代過程中，將粒子的更新區(qū)域確定到一個可能出現(xiàn)最優(yōu)解的區(qū)域，以此來提高搜索效率。

本文主要研究工作及貢獻如下。

1) 將資源受限邊緣計算環(huán)境下的節(jié)點調(diào)度問題轉(zhuǎn)化為優(yōu)化問題模型，并使用聯(lián)盟結(jié)構來表示節(jié)點的資源調(diào)度方案。

2) 為優(yōu)化粒子群算法，提出一種新的更新策略——基于離散最近過去的位置更新策略，并使用改進的基于離散最近過去位置更新策略的多進制粒子群優(yōu)化（MDPSO-DRPPUS,m-ary discrete particle swarm optimization discrete recent past-based position updating strategy）算法進行最優(yōu)聯(lián)盟結(jié)構的搜索。

3) 通過將MDPSO-DRPPUS 與MDPSO 和GA進行比較可知，與MDPSO 相比，MDPSO-DRPPUS的優(yōu)化速度與最優(yōu)解質(zhì)量都得到了提高；與GA 相比，MDPSO-DRPPUS 的運行時間大幅度降低，聯(lián)盟結(jié)構效益、均衡性和節(jié)點完成任務效率都有所提高。

1 問題描述

在邊緣計算環(huán)境中，當多個大規(guī)?？茖W計算任務同時到達時，邊緣節(jié)點由于自身資源受限無法獨立完成任務或無法滿足時延敏感型任務需求。為高效完成大規(guī)模科學計算的并發(fā)任務，邊緣節(jié)點選擇相互協(xié)作組成聯(lián)盟結(jié)構處理這批任務成為一種有效的解決方案。本文方法的工作流程如圖1 所示。

圖1 本文方法的工作流程

首先，邊緣節(jié)點生成能夠處理并發(fā)任務的聯(lián)盟結(jié)構，并使用基于索引的編碼方式將其編碼，形成策略空間。

其次，分析多目標函數(shù)，通過指定不同權重，將多目標問題轉(zhuǎn)化為單目標函數(shù)。

最后，使用MDPSO-DRPPUS 搜索策略空間，找到目標函數(shù)的高質(zhì)量解。

設邊緣節(jié)點的集合為N= {n1,n2,n3,…,ni,…,nN}，并發(fā)任務的集合為M={m1,m2,m3,…,mi,…,mM}。邊緣節(jié)點可以自發(fā)地組成聯(lián)盟來處理一個任務，當多個任務同時到達時，所有邊緣節(jié)點組成多個聯(lián)盟同時完成任務，即聯(lián)盟結(jié)構 CS= {A1,A2,A3,…,Ai,…,ACS}。在聯(lián)盟結(jié)構生成（CSG,coalition structure generation）問題中，聯(lián)盟Ai定義為集合N的任意一個子集，CS 為集合N的一個完全劃分。，對于所有的，當i≠j時，。

典型的聯(lián)盟生成方法是基于特征值函數(shù)[22]的聯(lián)盟生成，即一個聯(lián)盟的值由一個特征函數(shù)給出，其表示聯(lián)盟中成員的完成任務所能獲得的最大收益。CSG考慮非超加性環(huán)境，隨著聯(lián)盟新成員的加入，聯(lián)盟的成本也隨之增加。當系統(tǒng)中多個任務并行處理時，求解目標就是尋找使系統(tǒng)總效益最大的聯(lián)盟結(jié)構。該場景需同時滿足以下3 個條件。

1) 參與任務的邊緣節(jié)點數(shù)不小于任務數(shù)。

2) 每個邊緣節(jié)點在相同的時間里只能參與完成一個任務，或者不參與完成任務。

3) 聯(lián)盟產(chǎn)生正利潤。

用集合分割的方法分析聯(lián)盟結(jié)構，聯(lián)盟結(jié)構其實是系統(tǒng)內(nèi)集合的一個劃分。Hart 等[23]證明了聯(lián)盟結(jié)構的準確數(shù)量為，其中，Z(n,i)是由i個聯(lián)盟所能組成的所有聯(lián)盟結(jié)構的數(shù)量。Z(n,i)的數(shù)量也稱為第二類斯特林數(shù)（聯(lián)盟結(jié)構計算復雜性的具體證明參考文獻[24]），其值為

其中，Z(n,n) =Z(n,1)=1。式(1)右邊第一項表示新成員加入現(xiàn)有的聯(lián)盟形成的聯(lián)盟結(jié)構的數(shù)量；式(1)右邊第二項表示將新的成員加入自己的聯(lián)盟中。

例如，在邊緣節(jié)點集合n= {1,2,3,4}中，聯(lián)盟的個數(shù)為2n-1（不包含空集），共計15 個聯(lián)盟，所以聯(lián)盟結(jié)構的個數(shù)為15。4 個智能體（Agent）的聯(lián)盟結(jié)構如圖2 所示。

圖2 4 個Agent 的聯(lián)盟結(jié)構

1.1 問題建模

1.1.1 時間約束

記任務完成的截止時間為DLi，要求聯(lián)盟Ai完成各任務的時間ti必須小于或等于各任務完成的截止時間，即ti≤ DLi。聯(lián)盟結(jié)構中的所有聯(lián)盟都按時完成任務，形成一個有效的聯(lián)盟結(jié)構。由木桶效應可知，聯(lián)盟結(jié)構的任務完成時間取決于有效聯(lián)盟結(jié)構中完成任務時間最長的聯(lián)盟，即t(CSi)=max(t(Ai))。

1.1.2 效用函數(shù)

聯(lián)盟完成任務后會獲得一定的收益，定義Ei為聯(lián)盟Ai完成任務mi的收益，CPi為邊緣節(jié)點ni的計算能力。聯(lián)盟的計算能力支出即組成聯(lián)盟的邊緣節(jié)點的計算能力支出總和，即。定義各邊緣節(jié)點組成聯(lián)盟的損耗函數(shù)為L(Ai)，損耗函數(shù)是指節(jié)點之間組成聯(lián)盟引起的開銷，其包括聯(lián)盟間的通信損耗、計算冗余等。由于損耗是由節(jié)點之間協(xié)同組成聯(lián)盟所造成的，因此為單調(diào)遞增函數(shù)，且隨著聯(lián)盟內(nèi)成員的增加而增加，即

一個聯(lián)盟完成任務mi的利潤可以用聯(lián)盟的收益與成本進行計算。設P(Ci)表示一個聯(lián)盟完成任務mi的利潤，其計算方式為收益-成本-額外損耗，即

1.1.3 均衡性

基于個體理性原則，成員所做出的決策都是明智且理性的。節(jié)點期望加入支出最小、效益最大的聯(lián)盟，其可以通過性價比衡量。聯(lián)盟的性價比函數(shù)定義為

為保證聯(lián)盟結(jié)構中各聯(lián)盟的均衡性，即要求聯(lián)盟結(jié)構中各聯(lián)盟間的性價比差異最小。因此，使用方差來度量其均衡性，即

1.2 解法模型

為了解決該多目標優(yōu)化問題，本文使用線性加權法將多目標優(yōu)化問題轉(zhuǎn)化為一個綜合的目標函數(shù)。對于P1、P2 和P3，其權重分別為ω1、ω2和ω3，且ω1+ω2+ω3=1。

聯(lián)盟結(jié)構的特征值函數(shù)為組成聯(lián)盟結(jié)構聯(lián)盟的特征值總和，即

權重系數(shù)會影響最優(yōu)解的求解結(jié)果，ω1是任務完成時間的權重系數(shù)，會使算法傾向于搜索更高效的聯(lián)盟結(jié)構；ω2是效用權重系數(shù)，會使算法傾向于搜索效用值較大的聯(lián)盟結(jié)構；ω3是性價比權重系數(shù)，會使算法傾向于搜索滿足所有節(jié)點性價比的聯(lián)盟結(jié)構。由于大多數(shù)場景更關注時延和能耗，因此本文在實驗中弱化性價比權重系數(shù)ω3，并設置ω3=0.1。分析不同ω1和ω2條件下優(yōu)化速度和最優(yōu)解質(zhì)量的影響，重復進行多次實驗，實驗結(jié)果表明，ω1對算法的平均運行時間影響不大，同樣需弱化ω1，令ω1=0.1。因此，ω2=0.8。

2 尋找最優(yōu)聯(lián)盟結(jié)構

啟發(fā)式算法在求解聯(lián)盟結(jié)構生成這類復雜的組合優(yōu)化問題時，其共同點是從隨機的可行解開始，經(jīng)過不斷的迭代、改進、變異，最終無限趨近于問題的最優(yōu)解。但是面對大規(guī)模的聯(lián)盟結(jié)構搜索空間，原始啟發(fā)式算法因其運行時間長、易陷入局部最優(yōu)解等缺點并不能獲得較優(yōu)的解。因此，本文提出了基于離散最近過去位置更新策略的多進制粒子群優(yōu)化算法。

尋找一種適用于該場景下聯(lián)盟結(jié)構的編碼方式是使用啟發(fā)式算法求解該問題的第一步。因此，首先使用基于索引的聯(lián)盟結(jié)構編碼方式對聯(lián)盟結(jié)構進行編碼，將編碼粒子的長度與參與任務的邊緣節(jié)點數(shù)對應起來，并將粒子每個維度的索引與任務編號對應起來，用以滿足本場景下的約束條件。其次，本文對原始粒子群算法的更新方式進行改進，引入政治優(yōu)化器（PO,political optimizer）中的更新策略——基于最近過去的位置更新策略。再次，為了使其適用于本文場景下聯(lián)盟結(jié)構的編碼方式，對該更新策略進行離散化改進。最后，對所提算法的復雜度進行分析。

2.1 聯(lián)盟結(jié)構的編碼方式

任何一個有效的聯(lián)盟結(jié)構都以任務的完成為前提，聯(lián)盟結(jié)構中聯(lián)盟的數(shù)量就等于其所要完成任務的數(shù)量，即。聯(lián)盟與聯(lián)盟的結(jié)構關系如圖3 所示。

圖3 聯(lián)盟與聯(lián)盟的結(jié)構關系

在該場景中，所要搜索的最優(yōu)聯(lián)盟結(jié)構需同時滿足以下4 個約束條件。

1) 聯(lián)盟實際完成各任務的時間應小于或等于各任務的計劃完成時間。

2) 參與聯(lián)盟結(jié)構節(jié)點的數(shù)量不應超過邊緣節(jié)點的總數(shù)。

3) 每個節(jié)點最多只能參與完成一個任務。

4) 每個任務至少需要一個邊緣節(jié)點完成。

為了使聯(lián)盟結(jié)構的編碼能夠滿足約束2)～約束4)，本文選用基于索引的聯(lián)盟結(jié)構編碼方式。定義Di代表節(jié)點ni參與任務，且。聯(lián)盟結(jié)構的編碼方式可記為。

圖4 基于索引的聯(lián)盟結(jié)構編碼方式

2.2 基于改進更新策略的MDPSO

原始的粒子群算法存在過早收斂、容易陷入局部最優(yōu)值、收斂速度慢等缺點。因此，本文提出一種改進的DRPPUS 的MDPSO 算法。

2.2.1 DRPPUS

該更新策略是Askari[25]在2020 年提出的政治優(yōu)化器中的更新機制[26]。

基于最近過去更新策略保存了前一次迭代時算法所學習到的信息，更新每一個成員當前最優(yōu)解的位置來尋找下一次可能的最優(yōu)解位置。算法使用式(7)和式(8)來更新其可能的最優(yōu)解位置，根據(jù)成員當前得到的適應度值與前一次適應度值確定選擇式(7)或式(8)進行位置更新。若特征值函數(shù)有所提高，則使用式(7)；反之，則使用式(8)。在這2 種情況中，位置的更新依據(jù)當前可能的最優(yōu)解、變量r和可能的參考解，其中，隨機數(shù)r的取值范圍為[0,1] 。

RPPUS 表示如圖5 所示，圖5(a)～圖5(c)說明了式(7)的3 種情況，圖5(d)～圖5(f)說明了式(8)的3 種情況，主要目的就是找到最有可能產(chǎn)生最優(yōu)解的區(qū)域。

情況1如圖5(a)所示，成員的當前位置位于可能的參考解和前一次位置之間，可能產(chǎn)生最優(yōu)解的區(qū)域用灰色標出，其范圍為。

情況2當成員的參考解位置位于當前位置和前一次位置之間時，可能產(chǎn)生最優(yōu)解的區(qū)域如圖5(b)所示，其范圍為。

情況3成員的前一個位置位于參考解與當前位置之間，如圖5(c)所示，可能產(chǎn)生最優(yōu)解的區(qū)域在參考解附近，同理，因為。

圖5 RPPUS 表示

2.2.2 MDPSO-DRPPUS

針對最近過去位置更新策略的離散化改進如式(9)～式(22)所示。該更新策略在一個可能產(chǎn)生最優(yōu)解的區(qū)域內(nèi)進行更新，實際更新有可能超出該區(qū)域。所以定義一個整型函數(shù)R(s,e)，相關參數(shù)的范圍為，算法決策變量的更新范圍為。

若式(7)的C1 成立，則有

位置更新式為

其中，s=0，e為

針對式(7)的C2 和C3，有

位置更新式為

對于式(8)的C1 和C3，有

位置更新式為

對于式(8)的C2，有

位置更新式為

MDPSO-DRPPUS 算法的偽代碼如算法1 所示。

算法1MDPSO-DRPPUS 算法

輸入聯(lián)盟結(jié)構信息（聯(lián)盟結(jié)構編碼、完成任務所獲利潤、任務截止時間、成本支出等，該列表構成策略空間），MDPSO-DRPPUS 信息（粒子信息，包括粒子更新位置、適應度值、粒子的全局最優(yōu)位置），參數(shù)設置（種群個數(shù)NP、迭代次數(shù)G、編碼長度（節(jié)點數(shù)N）、隨機數(shù)r、決策變量上限、決策變量下限）

輸出全局最優(yōu)解（最優(yōu)聯(lián)盟結(jié)構）

1) 初始化每一個粒子的隨機位置；

2) 計算每一個粒子的適應度；

4) 設迭代次數(shù)g=1；

5) 如果g≤G；

6) 判斷粒子前一次適應度值與這次適應度值的大小，若適應度值有所提高，則使用式(7)的3 種情況進行判斷，并按照情況選擇相應離散化的位置更新式來更新粒子位置，反之亦然；

8) 判斷粒子適應度值是否提高，若不提高則結(jié)束迭代，否則轉(zhuǎn)步驟9)；

9)g=g+1，轉(zhuǎn)步驟6)；

10) 輸出粒子的最優(yōu)解及對應粒子位置。

2.3 MDPSO-DRPPUS 的算法復雜度分析

MDPSO-DRPPUS 算法的最大計算量是粒子數(shù)與迭代次數(shù)的乘積，增加粒子數(shù)可以擴大搜索范圍，降低算法陷入局部最優(yōu)解的可能性，增加迭代次數(shù)則可以提高最優(yōu)解質(zhì)量。算法的計算量是算法對特征值函數(shù)的求解，在一次算法執(zhí)行過程中，特征值函數(shù)的計算分為3 個階段。

1) 計算任務完成時間最長的節(jié)點，計算次數(shù)為N。

2) 根據(jù)式(2)，將所有形成聯(lián)盟結(jié)構聯(lián)盟的利潤加起來，聯(lián)盟結(jié)構的利潤計算次數(shù)為(M+1)(N+1)。

3) 根據(jù)式(3)～式(5)，聯(lián)盟結(jié)構均衡性的計算次數(shù)為 (M+1)2(N+1)。

綜上，MDPSO-DRPPUS 的計算復雜度最低，計算量最大為sum= NPG((M+2)(N+1)(M+1) +N)。

3 實驗與分析

本文的仿真實驗是在內(nèi)存為16 GB、處理器為Inter Core i5-4460、頻率為3.2 GHz 的Windows10 操作系統(tǒng)環(huán)境下使用Python3.7 實現(xiàn)的。通過模擬和仿真，對本文所提算法和對比實驗的各項指標進行評估。

3.1 實驗準備以及實驗數(shù)據(jù)

創(chuàng)建虛擬機來模擬邊緣節(jié)點，表1 給出了實驗環(huán)境中虛擬機配置，表2 顯示了任務工作量、計劃完成時間和任務報酬，表3 顯示了環(huán)境參數(shù)。

表1 實驗環(huán)境中虛擬機配置

表2 任務工作量、計劃完成時間和任務報酬

表3 環(huán)境參數(shù)

3.2 MDPSO-RPPUS 算法的性能實驗

本節(jié)在不同迭代次數(shù)條件下比較了3 種算法（MDPSO-RPPUS、MDPSO 和GA）在16 個邊緣節(jié)點上完成4 個任務（M1、M2、M3和M4）時的算法平均運行時間、最優(yōu)聯(lián)盟結(jié)構效益、均衡性和節(jié)點使用率，并分析了不同迭代次數(shù)對算法性能的影響。針對粒子數(shù)為100 個、不同迭代次數(shù)進行10 組實驗，迭代次數(shù)從50 增加到500（每增加100 次進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。圖6 是不同迭代次數(shù)下3 種算法性能比較。

由圖6(a)可知，MDPSO 和GA 的運行時間都隨著迭代次數(shù)的增加而增加，這是啟發(fā)式算法求解問題的特點。而MDPSO-DRPPUS 算法的運行時間隨迭代次數(shù)的增加變化不大，且算法運行時間在毫秒級，這是因為該算法往往能在迭代10 次以內(nèi)收斂。由圖6(b)可知，3 種算法聯(lián)盟結(jié)構的效益隨迭代次數(shù)增加變化較小，且結(jié)果不穩(wěn)定。由此看來，通過增加迭代次數(shù)使3 種算法獲得較好結(jié)果的做法意義不大。由圖6(c)可知，與MDPSO 和GA 相比，MDPSO-DRPPUS 聯(lián)盟結(jié)構均衡性較優(yōu)，且GA 最不穩(wěn)定。由圖6(d)可知，MDPSO-DRPPUS 算法的節(jié)點調(diào)度策略對運算量較大的任務分配多個邊緣節(jié)點進行計算，能夠避免多個節(jié)點很快完成計算量小的任務，但仍需等待并發(fā)任務中計算量較大任務的完成。該算法使用最少數(shù)量的節(jié)點完成任務，提高了任務完成效率。

圖6 不同迭代次數(shù)下3 種算法性能比較

針對不同粒子數(shù)，比較3 種算法在16 個邊緣節(jié)點上完成4 個任務（M1、M2、M3和M4）時在4 種標準下分析不同粒子數(shù)對算法性能的影響。針對迭代次數(shù)為500、不同粒子數(shù)進行10組實驗，粒子數(shù)從10 個增加到100 個（每次增加10 個進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。圖7 是不同粒子數(shù)下3 種算法性能比較。

圖7 不同粒子數(shù)下3 種算法性能比較

圖7(a)、圖7(c)、圖7(d)所示結(jié)果與圖6(a)、圖6(c)、圖6(d)相同，此處不再贅述。由圖7(b)可知，MDPSO-DRPPUS 算法隨著粒子數(shù)的增多聯(lián)盟結(jié)構效益增長較快，這是因為DRPPUS 極大地提高了算法的開發(fā)能力。因此本文推測可以通過大幅度提高算法的粒子數(shù)來避免MDPSO-DRPPUS 陷入局部最優(yōu)解的可能。

在迭代次數(shù)為10 的情況下大規(guī)模增加粒子數(shù)，比較3 種算法在16 個邊緣節(jié)點完成4 個任務（M1、M2、M3和M4）時在4 種標準下的算法性能。針對不同粒子數(shù)進行6 組實驗，粒子數(shù)從200 個增加到1 200 個（每次增加200 個進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。圖8 是迭代次數(shù)為10 時不同粒子數(shù)下3 種算法性能比較。

圖8(c)和圖8(d)與圖6(c)和圖6(d)結(jié)果類似。由圖8(a)可知，在迭代次數(shù)為10 的情況下，大規(guī)模增加算法的粒子數(shù)（GA 大規(guī)模增加其基因數(shù)），當粒子數(shù)增加到1 200 時，MDPSO-DRPPUS 算法平均運行時間為2 s 左右；MDPSO 算法平均運行時間為6 s 左右；GA 平均運行時間已達到257 s。由圖8(b)可知，MDPSO-DRPPUS 算法隨著粒子數(shù)的大規(guī)模增加聯(lián)盟結(jié)構效益增長較快，進一步證明了之前的推斷。

圖8 迭代次數(shù)為10 時不同粒子數(shù)下3 種算法性能比較

在不同邊緣節(jié)點（VM9-VM16、VM8-VM16、VM7-VM16、VM6-VM16、VM5-VM16、VM4-VM16、VM3-VM16、VM2-VM16、VM1-VM16）條件下測試3 種算法在4 種標準下的性能。為了避免任務量過大導致任何聯(lián)盟結(jié)構都無法完成任務的情況，選擇4 個計算量最小的任務（M1、M2、M3和M4）進行9 組實驗（每增加一個邊緣節(jié)點進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。設置3 種算法（MDPSO-RPPUS、MDPSO 和GA）的最大迭代次數(shù)G=50，最大粒子數(shù)NP=500。圖9 顯示了不同節(jié)點數(shù)下3 種算法性能比較。

圖9(a)、圖9(c)、圖9(d)與圖6(a)、圖6(c)、圖6(d)結(jié)果類似，此處不再贅述。由圖9(b)可知，當邊緣節(jié)點數(shù)為9 和13 時，3 種算法的最優(yōu)聯(lián)盟結(jié)構特征值都有了明顯的提升，這是因為添加了計算能力較強的VM8和VM4，可以使其他節(jié)點提供更多的資源去處理運算量較大的任務。

圖9 不同節(jié)點數(shù)下3 種算法性能比較

在不同任務數(shù)的性能實驗中，設置所有節(jié)點參與任務，當任務數(shù)小于4（M＜ 4）時，策略數(shù)小于 4.29 ×109。實驗最小任務數(shù)設置為4（每增加一個任務進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。設置3 種算法的最大迭代次數(shù)G=50，最大粒子數(shù)NP=500。圖10 顯示了不同任務數(shù)下3 種算法性能比較。

圖10 不同任務數(shù)下3 種算法性能比較

由圖10 可知，當任務數(shù)為8 個時，由于添加了任務量過大的M8，3 種算法在當前條件下均不能完成任務，這是因為M8的計算負載過大，從而導致邊緣節(jié)點無法按時完成任務。

綜上所述，相較于MDPSO 和GA，本文提出的MDPSO-DRPPUS 算法運行時間大幅度降低，開發(fā)能力也得到了極大提高。在面對此類復雜的組合優(yōu)化問題時，MDPSO 和GA 依舊面臨陷入局部最優(yōu)解的困境，但所提算法可以通過大幅度增加粒子數(shù)避免這一缺陷。實驗結(jié)果表明，MDPSO-DRPPUS 的粒子數(shù)增加到5 000 個時算法運行時間為10 s 左右。增加粒子數(shù)后，聯(lián)盟結(jié)構效益也隨之得到提升。此外，MDPSO-DRPPUS 所得聯(lián)盟結(jié)構的均衡性和節(jié)點使用率均優(yōu)于MDPSO 和GA。

因此，與MDPSO 和GA 相比，MDPSO-DRPPUS在優(yōu)化速度及最優(yōu)解質(zhì)量方面都得到了較好的提升。

4 結(jié)束語

本文提出了MDPSO-DRPPUS 算法進行最優(yōu)聯(lián)盟結(jié)構搜索，很好地解決了多任務并發(fā)邊緣計算環(huán)境中的最優(yōu)聯(lián)盟結(jié)構搜索問題。實驗結(jié)果表明，MDPSO-RPPUS 算法有很強的搜索能力，收斂速度很快（能在迭代10 次以內(nèi)收斂），運行時間相對于MDPSO 和GA 而言大幅度降低，搜索到的最優(yōu)聯(lián)盟結(jié)構效益和聯(lián)盟結(jié)構均衡性也相對較優(yōu)。

在本文場景中，聯(lián)盟結(jié)構的數(shù)量隨著任務數(shù)和邊緣節(jié)點數(shù)的增加呈指數(shù)級增長。雖然智能算法對聯(lián)盟結(jié)構的搜索已經(jīng)取得了一定的成果，但由于策略空間巨大，下一步可否先將龐大的策略空間處理后再進行搜索成為一個值得研究的課題。