趙庶旭，韋萍，王小龍

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

0 引言

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

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

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

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

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

啟發(fā)式算法求解最優(yōu)聯(lián)盟結(jié)構(gòu)生成問題因其簡單直接并能在可接受的時間范圍內(nèi)找到一個相對較優(yōu)的解而受到廣泛關(guān)注。對于求解聯(lián)盟結(jié)構(gòu)，Sen 等[11]首先引入了遺傳算法，并采用一維積分編碼來搜索最優(yōu)聯(lián)盟結(jié)構(gòu)。Yang[12]在Sen 等[11]工作的基礎(chǔ)上，提出了一種基于二維二進制染色體編碼及交叉和變異算子的不相交聯(lián)盟形成算法。Contreras等[13]使用改進編碼的遺傳算法求解聯(lián)盟結(jié)構(gòu)生成問題，其能夠在一個合理的計算時間內(nèi)獲得高質(zhì)量的解。蔣建國等[14]引入蟻群算法解決多任務(wù)聯(lián)盟問題。蟻群基于信息正反饋機制選擇協(xié)作性能較好的智能體組成聯(lián)盟，有效減少了聯(lián)盟生成的時間以及計算量，但該算法只適用于多任務(wù)串行計算場景。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é)構(gòu)進行研究方面，Zhang 等[16]開發(fā)了一種一維二進制編碼方案，在每次迭代過程中使用編碼修復策略確保每個編碼都是近似有效的。許金友[17]對傳統(tǒng)的基于多任務(wù)并發(fā)的聯(lián)盟問題進行了分析，指出聯(lián)盟資源利用方面的不足，并使用離散粒子群優(yōu)化算法求解多任務(wù)聯(lián)盟結(jié)構(gòu)生成問題。Hu 等[18]借鑒堆智能離散粒子群優(yōu)化算法解決資源分配問題的思想[19]，構(gòu)造了一種描述資源調(diào)度方案的聯(lián)盟結(jié)構(gòu)表達式。將邊緣計算環(huán)境中的資源調(diào)度問題轉(zhuǎn)化為優(yōu)化問題模型，設(shè)計了適應(yīng)聯(lián)盟結(jié)構(gòu)編碼方式的多進制離散粒子群優(yōu)化算法。Zhang等[20]在Hu等[18]的基礎(chǔ)上結(jié)合合作博弈與啟發(fā)式算法的優(yōu)點，引入討價還價集的概念。通過判斷非討價還價聯(lián)盟來消除一部分不滿足條件的聯(lián)盟結(jié)構(gòu)，從而達到縮小搜索策略空間的目的。最后使用改進的多進制離散粒子群優(yōu)化（MDPSO,m-ary discrete particle swarm optimization）算法進行聯(lián)盟結(jié)構(gòu)的搜索，找到近似最優(yōu)的聯(lián)盟結(jié)構(gòu)解。

綜上所述，PSO 算法[21]在求解邊緣計算環(huán)境下的多任務(wù)并發(fā)問題上已經(jīng)取得了一定的成果。但在任務(wù)數(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é)構(gòu)來表示節(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é)構(gòu)的搜索。

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

1 問題描述

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

圖1 本文方法的工作流程

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

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

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

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

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

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

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

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

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

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

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

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

1.1 問題建模

1.1.1 時間約束

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

1.1.2 效用函數(shù)

聯(lián)盟完成任務(wù)后會獲得一定的收益，定義Ei為聯(lián)盟Ai完成任務(wù)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)盟完成任務(wù)mi的利潤可以用聯(lián)盟的收益與成本進行計算。設(shè)P(Ci)表示一個聯(lián)盟完成任務(wù)mi的利潤，其計算方式為收益-成本-額外損耗，即

1.1.3 均衡性

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

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

1.2 解法模型

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

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

權(quán)重系數(shù)會影響最優(yōu)解的求解結(jié)果，ω1是任務(wù)完成時間的權(quán)重系數(shù)，會使算法傾向于搜索更高效的聯(lián)盟結(jié)構(gòu)；ω2是效用權(quán)重系數(shù)，會使算法傾向于搜索效用值較大的聯(lián)盟結(jié)構(gòu)；ω3是性價比權(quán)重系數(shù)，會使算法傾向于搜索滿足所有節(jié)點性價比的聯(lián)盟結(jié)構(gòu)。由于大多數(shù)場景更關(guān)注時延和能耗，因此本文在實驗中弱化性價比權(quán)重系數(shù)ω3，并設(shè)置ω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é)構(gòu)

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

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

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

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

圖3 聯(lián)盟與聯(lián)盟的結(jié)構(gòu)關(guān)系

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

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

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

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

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

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

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

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ù)成員當前得到的適應(yīng)度值與前一次適應(yīng)度值確定選擇式(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)，相關(guān)參數(shù)的范圍為，算法決策變量的更新范圍為。

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

位置更新式為

其中，s=0，e為

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

位置更新式為

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

位置更新式為

對于式(8)的C2，有

位置更新式為

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

算法1MDPSO-DRPPUS 算法

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

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

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

2) 計算每一個粒子的適應(yīng)度；

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

5) 如果g≤G；

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

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

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

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

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

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

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

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

3) 根據(jù)式(3)～式(5)，聯(lián)盟結(jié)構(gòu)均衡性的計算次數(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 顯示了任務(wù)工作量、計劃完成時間和任務(wù)報酬，表3 顯示了環(huán)境參數(shù)。

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

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

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

3.2 MDPSO-RPPUS 算法的性能實驗

本節(jié)在不同迭代次數(shù)條件下比較了3 種算法（MDPSO-RPPUS、MDPSO 和GA）在16 個邊緣節(jié)點上完成4 個任務(wù)（M1、M2、M3和M4）時的算法平均運行時間、最優(yōu)聯(lián)盟結(jié)構(gòu)效益、均衡性和節(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é)構(gòu)的效益隨迭代次數(shù)增加變化較小，且結(jié)果不穩(wěn)定。由此看來，通過增加迭代次數(shù)使3 種算法獲得較好結(jié)果的做法意義不大。由圖6(c)可知，與MDPSO 和GA 相比，MDPSO-DRPPUS 聯(lián)盟結(jié)構(gòu)均衡性較優(yōu)，且GA 最不穩(wěn)定。由圖6(d)可知，MDPSO-DRPPUS 算法的節(jié)點調(diào)度策略對運算量較大的任務(wù)分配多個邊緣節(jié)點進行計算，能夠避免多個節(jié)點很快完成計算量小的任務(wù)，但仍需等待并發(fā)任務(wù)中計算量較大任務(wù)的完成。該算法使用最少數(shù)量的節(jié)點完成任務(wù)，提高了任務(wù)完成效率。

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

針對不同粒子數(shù)，比較3 種算法在16 個邊緣節(jié)點上完成4 個任務(wù)（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é)構(gòu)效益增長較快，這是因為DRPPUS 極大地提高了算法的開發(fā)能力。因此本文推測可以通過大幅度提高算法的粒子數(shù)來避免MDPSO-DRPPUS 陷入局部最優(yōu)解的可能。

在迭代次數(shù)為10 的情況下大規(guī)模增加粒子數(shù)，比較3 種算法在16 個邊緣節(jié)點完成4 個任務(wù)（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é)構(gòu)效益增長較快，進一步證明了之前的推斷。

圖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 種標準下的性能。為了避免任務(wù)量過大導致任何聯(lián)盟結(jié)構(gòu)都無法完成任務(wù)的情況，選擇4 個計算量最小的任務(wù)（M1、M2、M3和M4）進行9 組實驗（每增加一個邊緣節(jié)點進行一組實驗，每組實驗進行5 次，最終結(jié)果取平均值）。設(shè)置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é)構(gòu)特征值都有了明顯的提升，這是因為添加了計算能力較強的VM8和VM4，可以使其他節(jié)點提供更多的資源去處理運算量較大的任務(wù)。

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

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

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

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

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

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

4 結(jié)束語

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

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