多任務并發邊緣計算環境中最優聯盟結構生成策略

趙庶旭，韋萍，王小龍

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

0 引言

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

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

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

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

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

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

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

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

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

1) 將資源受限邊緣計算環境下的節點調度問題轉化為優化問題模型，并使用聯盟結構來表示節點的資源調度方案。

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

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

1 問題描述

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

圖1 本文方法的工作流程

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

其次，分析多目標函數，通過指定不同權重，將多目標問題轉化為單目標函數。

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

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

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

1) 參與任務的邊緣節點數不小于任務數。

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

3) 聯盟產生正利潤。

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

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

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

圖2 4 個Agent 的聯盟結構

1.1 問題建模

1.1.1 時間約束

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

1.1.2 效用函數

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

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

1.1.3 均衡性

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

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

1.2 解法模型

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

聯盟結構的特征值函數為組成聯盟結構聯盟的特征值總和，即

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

2 尋找最優聯盟結構

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

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

2.1 聯盟結構的編碼方式

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

圖3 聯盟與聯盟的結構關系

在該場景中，所要搜索的最優聯盟結構需同時滿足以下4 個約束條件。

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

2) 參與聯盟結構節點的數量不應超過邊緣節點的總數。

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

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

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

圖4 基于索引的聯盟結構編碼方式

2.2 基于改進更新策略的MDPSO

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

2.2.1 DRPPUS

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

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

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

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

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

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

圖5 RPPUS 表示

2.2.2 MDPSO-DRPPUS

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

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

位置更新式為

其中，s=0，e為

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

位置更新式為

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

位置更新式為

對于式(8)的C2，有

位置更新式為

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

算法1MDPSO-DRPPUS 算法

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

輸出全局最優解（最優聯盟結構）

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

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

4) 設迭代次數g=1；

5) 如果g≤G；

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

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

9)g=g+1，轉步驟6)；

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

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

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

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

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

3) 根據式(3)～式(5)，聯盟結構均衡性的計算次數為 (M+1)2(N+1)。

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

3 實驗與分析

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

3.1 實驗準備以及實驗數據

創建虛擬機來模擬邊緣節點，表1 給出了實驗環境中虛擬機配置，表2 顯示了任務工作量、計劃完成時間和任務報酬，表3 顯示了環境參數。

表1 實驗環境中虛擬機配置

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

表3 環境參數

3.2 MDPSO-RPPUS 算法的性能實驗

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

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

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

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

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

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

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

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

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

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

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

圖9 不同節點數下3 種算法性能比較

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

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

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

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

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

4 結束語

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

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