張夢琳，江沸菠，董 莉，高 穎

1.湖南師范大學(xué) 智能計算與語言信息處理湖南省重點實驗室，長沙 410081

2.湖南工商大學(xué) 新零售虛擬現(xiàn)實技術(shù)湖南省重點實驗室，長沙 410205

1 引言

在萬物互聯(lián)的時代，越來越多的計算密集，延遲敏感和能耗高的新型應(yīng)用不斷涌現(xiàn)，例如自動駕駛、虛擬現(xiàn)實、體感網(wǎng)絡(luò)等。由于用戶設(shè)備（UE）的計算資源和電池容量有限，使得這些新興應(yīng)用無法在用戶端有效執(zhí)行[1]。移動邊緣計算（MEC）被廣泛認為是用于實現(xiàn)下一代物聯(lián)網(wǎng)的關(guān)鍵技術(shù)[2]。MEC 是一種新型的移動計算方法，它打破傳統(tǒng)云計算方式，不斷提高用戶服務(wù)質(zhì)量（QoS）。與移動云計算相比，MEC減少了因數(shù)據(jù)中心網(wǎng)絡(luò)堵塞而可能導(dǎo)致的延遲，通過將服務(wù)器部署到網(wǎng)絡(luò)邊緣（如接入點，小型基站等）使得云計算能力和IT 服務(wù)接近用戶端[3]，這一技術(shù)不僅滿足UE低延遲的要求，同時也降低了能耗，延長了設(shè)備的使用壽命。

在MEC 系統(tǒng)中，服務(wù)器的位置部署和計算卸載是實現(xiàn)能耗優(yōu)化的關(guān)鍵點。由于服務(wù)器與UE是端到端的通信模式，所以它們之間相對較短的距離將消耗更少的傳輸時間和能量[4]。計算卸載包括數(shù)據(jù)傳輸、資源分配、MEC 執(zhí)行計算和結(jié)果返回。雖然MEC 系統(tǒng)可以提供給UE 云計算的功能，但是也無法同時為所有UE 提供計算資源。所以，通過優(yōu)化MEC 系統(tǒng)中服務(wù)器的位置部署和UE的計算卸載來平衡計算任務(wù)并提高系統(tǒng)能效至關(guān)重要。

目前，在MEC 系統(tǒng)中服務(wù)器的位置部署和任務(wù)卸載領(lǐng)域均已有較多專門的研究[5-12]，但很少有文獻同時優(yōu)化服務(wù)器位置和計算卸載來減少系統(tǒng)能耗。本文在無人機（UAV）上加載了3C 資源即緩存（Cache）、計算（Compute）和通信（Communication）資源，把無人機作為移動邊緣服務(wù)器，為地面用戶提供靈活的計算和通信服務(wù)，最大限度地減少服務(wù)時延，提高服務(wù)質(zhì)量?；谝陨戏治?，將MEC 服務(wù)器集成到UAV 上，并對UAV 的位置部署，計算卸載和資源分配進行聯(lián)合優(yōu)化。

考慮一種多用戶-多無人機的移動邊緣計算系統(tǒng)。通過重點優(yōu)化UAV 的位置部署、計算卸載來減少能量消耗。特別是，UE 不僅需要決定是否卸載而且還需要確定卸載位置。本文提出了一種雙層優(yōu)化方法，上層利用h-SOM 神經(jīng)網(wǎng)絡(luò)根據(jù)信道增益作為判別依據(jù)對UE進行實時聚類得到UAV 的最佳位置，下層通過IDE 算法優(yōu)化得到卸載矩陣。本文的主要貢獻如下：

（1）研究了一種基于多用戶-多無人機的移動邊緣計算系統(tǒng)模型，依據(jù)此系統(tǒng)設(shè)計了一種具有時延約束的最小能耗計算問題，并針對該問題設(shè)計了一種雙層優(yōu)化方法對無人機軌跡和任務(wù)卸載決策進行聯(lián)合優(yōu)化。

（2）雙層優(yōu)化方法的上層采用無監(jiān)督學(xué)習(xí)的h-SOM神經(jīng)網(wǎng)絡(luò)，對于網(wǎng)絡(luò)的輸入即每個UE 的坐標以信道增益作為判別指標，SOM網(wǎng)絡(luò)能夠自動找出UE之間的類似度，達到對UE 進行實時聚類的效果，從而得到UAV的最佳位置。

（3）雙層優(yōu)化方法的下層用一種改進的差分進化算法求解任務(wù)卸載決策和計算資源分配。首先將上層UE的聚類結(jié)果轉(zhuǎn)化為一組可行解作為IDE 算法的初始解之一，然后利用帶有精英初始策略和自適應(yīng)雙變異策略的差分進化算法對目標函數(shù)進行全局搜索，得到任務(wù)卸載決策和計算資源分配的全局次優(yōu)解。

（4）針對本文所提方法，考慮了一個大規(guī)模場景，包含上百個UE 和多個UAV。研究了聯(lián)合雙層優(yōu)化方法的可行性，并與傳統(tǒng)算法進行了比較，驗證了該方法的有效性。

2 相關(guān)工作

UAV的軌跡優(yōu)化和計算任務(wù)卸載都是MEC系統(tǒng)中的研究熱點。

在UAV的軌跡優(yōu)化領(lǐng)域：Mozaffari等人[5]使用圓填充理論（Circle packing theory）設(shè)計將多個UAV有效的部署為無線基站，使UAV 的總覆蓋面積和覆蓋壽命最大化；Liu 等人[6]將塊坐標下降法和連續(xù)凸逼近算法（Successive Convex Approximation）相結(jié)合提出一種新的SCA 算法來優(yōu)化UAV 位置和無線回程容量的分配；Chen 等人[7]以誤碼率作為可靠指標，研究了基于最大可靠性的中繼UAV 的最佳位置部署。Mozaffari等人[8]還研究了UAV的3D放置和移動性，以便最大化從地面接受物聯(lián)網(wǎng)設(shè)備的數(shù)據(jù)等。

在計算卸載和資源分配領(lǐng)域：Wang等人[9]將深度學(xué)習(xí)技術(shù)和聯(lián)合學(xué)習(xí)框架與移動邊緣系統(tǒng)相結(jié)合，設(shè)計了“邊緣AI框架”以優(yōu)化移動邊緣計算系統(tǒng)中的緩存和通信；Huang 等人[10]提出了一個基于深度強化學(xué)習(xí)的在線卸載DROO算法，該框架采用了深度強化學(xué)習(xí)來生成卸載決策；Chen 等人[11]研究了UAV 的最佳位置和UAV上緩存的內(nèi)容，提出了一種基于概念的回聲狀態(tài)網(wǎng)絡(luò)（Echo State Networks）的機器學(xué)習(xí)新算法；Wang等人[12]提出了帶有移動云計算（MCC）的C-RAN 網(wǎng)絡(luò)，研究了在給定任務(wù)時間約束下，MCC在C-RAN網(wǎng)絡(luò)中的能量最小化和最優(yōu)資源分配等。

與上述工作不同，研究了一個大規(guī)模場景下的聯(lián)合優(yōu)化方案，考慮到任務(wù)的時延約束和系統(tǒng)能耗，提出聯(lián)合優(yōu)化UAV的位置部署和計算任務(wù)卸載決策的雙層優(yōu)化方法。上述文獻UAV的位置部署大多采用凸優(yōu)化或分支界定法的方法來求解問題，雖然降低了問題的復(fù)雜性，但隨著系統(tǒng)變量的增多，求解復(fù)雜度急劇增加，因此不適合大規(guī)模應(yīng)用場景的問題。計算卸載用AI算法固然可以縮短時間，但算法中的神經(jīng)網(wǎng)絡(luò)需要大量樣本，這在實際系統(tǒng)應(yīng)用中難以獲得。綜合以上特點，本文考慮了一個多用戶-多無人機的實際場景。針對該場景建立系統(tǒng)模型，并提出了一種雙層優(yōu)化方法，首先用一種無監(jiān)督學(xué)習(xí)的h-SOM 神經(jīng)網(wǎng)絡(luò)對UE 進行實時聚類從而得到UAV 的最佳位置部署。該方法無需樣本，并且可以在相對較短時間內(nèi)得到UE的聚類結(jié)果。然后根據(jù)UE 的聚類結(jié)果，得到UAV 的最佳部署。最后采用IDE算法求解計算任務(wù)卸載決策。

3 系統(tǒng)模型

3.1 基于無人機的移動邊緣計算系統(tǒng)

考慮由i∈I={1 ,2,…,I}個UE和j∈J={1,2,…,J}個UAV組成的MEC系統(tǒng)，如圖1所示。UE隨機分布在規(guī)定區(qū)域內(nèi)。每個UE 有一個計算密集型任務(wù)要執(zhí)行，該任務(wù)采用二進制卸載策略。和文獻[13]相似，計算任務(wù)可以用數(shù)學(xué)模型描述為Ui=(Fi,Di,T),?i∈I。其中Fi是完成任務(wù)Ui所需的CPU 周期總數(shù)，Di是任務(wù)Ui的卸載數(shù)據(jù)量，T是時間約束或用戶的QoS要求。

圖1 系統(tǒng)模型

計算卸載包含三個部分：（1）數(shù)據(jù)傳輸，（2）執(zhí)行計算，（3）結(jié)果返回。本文參考文獻[14]，只關(guān)心前兩個部分，忽略結(jié)果返回。

3.2 通信模型

本節(jié)所述的通信模型體現(xiàn)在上行鏈路的傳輸。將aij={0 ,1},?i∈I,?j∈J表示UE的卸載決策。當(dāng)aij=1時，表示第i個UE將計算卸載到第j個UAV上，當(dāng)aij=0時，在本地執(zhí)行計算。同時上述決策滿足?i=I，該公式意味著每個任務(wù)最多只能在一個UAV上執(zhí)行。

假設(shè)UE 在數(shù)據(jù)傳輸中保持靜止[15]。當(dāng)UEi滿足aij=1 時，第i個UE 卸載到第j個UAV 的傳輸速率rij可以用下式表示：

其中，B是信道帶寬，是發(fā)射功率，hij是信道增益表示為是第j個 UAV 的高度，Rij是第i個UE和第j個UAV的水平距離，α是小尺度衰落分量。本文中設(shè)置UAV在相同的高度。

3.3 計算模型

本節(jié)介紹計算模型，主要描述計算任務(wù)在本地和UAV上執(zhí)行的計算時間和能量消耗。

（1）本地執(zhí)行。假設(shè)每個UE 在本地的計算能力為fiL，任務(wù)Ui所需的CPU 總周期表示為Fi，那么，第i個UE在本地計算所需時間為：

因此，第i個UE在本地執(zhí)行所需要的功率PiE為：

式中，ki=10-27是有效開關(guān)電容，vi=3 是正常數(shù)[16]。

（2）UAV上執(zhí)行。當(dāng)UE決定將任務(wù)卸載到UAV上時，首先需要確定UE 是否在UAV 覆蓋范圍內(nèi)，然后定義傳輸時間和UAV 上的計算時間，最后定義計算卸載所需能耗。根據(jù)下式判斷第i個UE 是否符合第j個UAV的覆蓋范圍：

T為總時間?？紤]到UAV 資源有限，所以fij必須滿足以下約束這意味著每個UAV分配給UE的計算資源不能超過自身總計算資源。和文獻[18]一樣，忽略無人機懸停和計算所消耗的能量，第i個UE卸載到第j個UAV的能量消耗表示如下：

4 問題擬定與分析

4.1 問題擬定

基于以上系統(tǒng)模型分析，給出目標函數(shù)Q1如下：

式中，變量uav、a、f分別是UAV 位置矩陣、任務(wù)卸載矩陣和資源分配矩陣。約束條件的意義如下：C1 確保所有任務(wù)在UAV 或者本地執(zhí)行；C2 表示如果任務(wù)選擇卸載，則每個任務(wù)只能在一個UAV上卸載；C3是時延約束；C4 表示UAV 分配給UE 的資源不得超過自身總計算資源；C5表示UAV的覆蓋范圍約束。

4.2 問題分析

上述問題可以描述為一個混合整數(shù)非線性規(guī)劃問題（MINLP）。針對該問題，提出了一種雙層優(yōu)化方法對無人機軌跡和任務(wù)卸載決策進行聯(lián)合優(yōu)化。首先，用一種無監(jiān)督學(xué)習(xí)的h-SOM神經(jīng)網(wǎng)絡(luò)獲得上層的部署。該網(wǎng)絡(luò)是一種無導(dǎo)師學(xué)習(xí)方法，具有良好的自組織、可視化特性。網(wǎng)絡(luò)根據(jù)輸入的UE坐標自適應(yīng)地調(diào)整權(quán)值達到聚類效果，當(dāng)網(wǎng)絡(luò)完成聚類后可以對新的UE 直接進行聚類無需重新訓(xùn)練。該方法相對于一般的算法減少了優(yōu)化時間，因為如果增加大量UE，一般的算法需要再次迭代求解，而h-SOM 網(wǎng)絡(luò)直接輸入可以得到聚類結(jié)果，能夠?qū)崟r地分析UE 與UAV 的關(guān)系，從而得到UAV最優(yōu)位置部署。然后，對于下層的計算卸載，使用啟發(fā)式算法，即用于求解整數(shù)優(yōu)化問題的IDE算法。因為在計算卸載中，包含大量的變量、參數(shù)、約束條件，運用啟發(fā)式算法可以降低該部分的計算復(fù)雜度，迭代得到最佳卸載矩陣使得系統(tǒng)能耗最小。資源分配矩陣f的求解，則參考文獻[16]，根據(jù)時間約束公式（6）令T取最大時延求每個UE分配的最小資源。此時上述雙層優(yōu)化方法，上層打開了下層的可行性，下層提高了上層性能評估的準確性，為解決MEC 系統(tǒng)的優(yōu)化問題提供了一種新思路。

5 自組織特征映射網(wǎng)絡(luò)和改進差分進化算法

本文所提出的雙層優(yōu)化方法如圖2 所示。首先介紹聯(lián)合雙層優(yōu)化方法的算法流程，然后具體介紹h-SOM網(wǎng)絡(luò)和IDE算法在該問題中的應(yīng)用，最后分析了算法的特點與優(yōu)勢。

5.1 算法流程

如圖2 所示聯(lián)合雙層優(yōu)化方法。首先用h-SOM 網(wǎng)絡(luò)對UE 進行實時聚類從而得到UAV 的最優(yōu)位置。然后利用IDE 算法迭代優(yōu)化直到收斂或者達到最大迭代次數(shù)獲得最終最優(yōu)解。下面詳細介紹h-SOM 網(wǎng)絡(luò)和IDE算法。

5.2 改進自組織特征映射網(wǎng)絡(luò)

自組織特征映射網(wǎng)絡(luò)（Self-Organizing Feature Map，SOM）也稱Kohonen網(wǎng)絡(luò)。該網(wǎng)絡(luò)是一個由全連接的神經(jīng)元陣列組成的無導(dǎo)師、自組織、自學(xué)習(xí)網(wǎng)絡(luò)。SOM網(wǎng)絡(luò)能夠以自適應(yīng)的方式實現(xiàn)任意維度輸入信號的聚類[19]。在本研究中使用SOM網(wǎng)絡(luò)描述如下。

圖2 算法流程

5.2.1 SOM神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

SOM 網(wǎng)絡(luò)結(jié)構(gòu)如圖3 所示，由輸入層和輸出層（競爭層）組成。輸入層神經(jīng)元個數(shù)為n，輸出層由m個神經(jīng)元組成的二維平面陣列，輸入層與輸出層各神經(jīng)元之間實現(xiàn)全連接。SOM網(wǎng)絡(luò)能將任意維度的輸入模式在輸出層映射成二維圖形，并保持其拓撲結(jié)構(gòu)不變。網(wǎng)絡(luò)通過反復(fù)學(xué)習(xí)輸入向量使權(quán)重向量與輸入向量分布趨于一致。

5.2.2 h-SOM神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

本文針對Q1 問題，對SOM 網(wǎng)絡(luò)進行改進，利用信道質(zhì)量h來衡量樣本與網(wǎng)絡(luò)權(quán)值之間的匹配程度。首先用矢量(xi,yi) 表示輸入數(shù)據(jù)即UE 的坐標，i∈{1,2,…,k}表示數(shù)據(jù)個數(shù)，輸入數(shù)據(jù)的維度與輸入層的神經(jīng)元一一對應(yīng)。然后隨機初始化輸入層與競爭層神經(jīng)元之間的權(quán)值Wm，Wm即為第m個UAV 的平面坐標。計算第i個輸入樣本zi=(xi,yi)與第m個神經(jīng)元的權(quán)值Wm=(Wm1,Wm2)的匹配程度：

其中，α是小尺度衰落分量，H是無人機的高度，dim=取具有最大值h(zi,Wm)的神經(jīng)元即為勝出神經(jīng)元m*，然后根據(jù)下式修正輸出神經(jīng)元m*的權(quán)值，而其他神經(jīng)元權(quán)值不變。

式中，0 ＜η＜1 為常數(shù)，隨著時間t的變化逐漸下降。這種權(quán)值更新規(guī)則通過學(xué)習(xí)輸入樣本讓最靠近輸入樣本的神經(jīng)元權(quán)值向量被修正，使之更靠近，使得獲勝的神經(jīng)元在下一次相似的輸入向量出現(xiàn)時，獲勝的可能性會更大；而對于相差很遠的輸入向量，獲勝的可能性將變得很小。

最后，輸出網(wǎng)絡(luò)h(zi,Wm)的權(quán)值Wm即為UAV 的最佳坐標。

5.3 改進差分進化算法

5.3.1 標準差分進化算法

差分進化算法（DE）主要用于求解整數(shù)優(yōu)化問題。在DE 算法尋優(yōu)的過程中分為變異、交叉和選擇三個過程。其中，差分變異是DE算法的核心。首先，從父代個體間選擇兩個個體進行向量做差生成差分矢量；其次，選擇另外一個個體與差分矢量求和生成實驗個體；然后，對父代個體與相應(yīng)的實驗個體進行變異操作，生成新的子代個體；最后在父代個體和子代個體之間進行選擇操作，將符合要求的個體保存到下一代群體中去[20]。

本工作中使用的算法詳細表述如下。為簡單起見，使用實數(shù)編碼。在算法中，每個個體是一個卸載矩陣，個體的維度即為UE 個數(shù)，每個個體維度的范圍即為J。為進一步提高DE 算法解的精度以及收斂速度，做了如下兩種改進。

5.3.2 精英初始策略

精英初始策略就是把h-SOM網(wǎng)絡(luò)聚類結(jié)果轉(zhuǎn)化成一組符合約束條件的可行解代入IDE 算法中作為初始解之一。其轉(zhuǎn)化思想是把h-SOM網(wǎng)絡(luò)聚類結(jié)果依次代入公式（8）中的約束條件，若符合所有約束條件，則保留當(dāng)前聚類結(jié)果，若不符合約束條件，則給定在本地執(zhí)行。在IDE算法中，運用精英初始策略為算法提供了優(yōu)秀的初始解。

5.3.3 自適應(yīng)雙變異策略

在群智能算法中，種群的搜索范圍與收斂速度是兩個相互制約的因素。比如，如果只擴大搜索閾值，雖然提高了種群的多樣性，但在面對復(fù)雜問題時勢必會影響算法的收斂速度；反之，如果單方面提高收斂速度，雖然能快速找到最優(yōu)解，但算法易陷入“早熟”階段，穩(wěn)定性差?；谏鲜鲈颍贒E算法中，通常從變異策略來解決，這樣既增加算法種群多樣性還增加了收斂速度。本文中，使用兩種變異策略，但是，如何平衡這兩個變異策略，本文引入自適應(yīng)算子。公式如下：

其中，F(xiàn)是變異因子；是第k代變異產(chǎn)生的新向量；分別是第k代種群中互不相同的三個向量；是第k代種群中最優(yōu)適應(yīng)度的向量；隨機數(shù)r∈(0-1)；ω為自適應(yīng)權(quán)重，公式如下：

式中，k為迭代次數(shù)，Tmax為最大迭代次數(shù)，式（12）中，ω前期變化較慢，取值較大，結(jié)合公式（11），有大的概率采用第一個式子進行變異，增加了種群的多樣性，維持了算法的全局搜索能力；隨著迭代的進行，ω逐漸減小，有大的概率使用第二個式子能夠進行精確搜索，極大地提高了算法的局部尋優(yōu)能力[21]。通過這種ω權(quán)重的變化函數(shù)，能夠使算法在迭代過程中不易陷入早熟收斂，這樣在整個搜索過程中既高效又不失精確性。

5.4 算法的特點與優(yōu)勢

在移動邊緣計算中，目標函數(shù)往往是一個大規(guī)模動態(tài)場景的優(yōu)化問題，本文所用的聯(lián)合優(yōu)化算法優(yōu)于傳統(tǒng)的方法，具體表現(xiàn)在：（1）針對動態(tài)場景的優(yōu)化問題，算法的上層h-SOM 網(wǎng)絡(luò)是基于分類的神經(jīng)網(wǎng)絡(luò)，訓(xùn)練好以后能夠?qū)崟r進行定位和分類。傳統(tǒng)的聚類算法例如k-means 或FCM 則需要經(jīng)過迭代才能夠?qū)AV 進行定位，不利于快速變化的動態(tài)場景。（2）在大規(guī)模應(yīng)用場景下，傳統(tǒng)的凸優(yōu)化或分支界定法隨著系統(tǒng)變量的增多，求解復(fù)雜度急劇增加，而IDE 算法的計算復(fù)雜度相對較低且具有高效的全局搜索能力，經(jīng)過變異、交叉和選擇三種操作同時配合h-SOM 網(wǎng)絡(luò)聚類的初始解能夠快速地迭代找到更優(yōu)的任務(wù)卸載矩陣達到能耗最小。

6 仿真實驗及分析

6.1 模型設(shè)置

本實驗中，設(shè)定實驗區(qū)域100 m×100 m，用戶在該區(qū)域內(nèi)隨機分布。仿真平臺為MATLAB R2012a，CPU為酷睿i5-7200U，內(nèi)存大小為4 GB。首先給出了h-SOM網(wǎng)絡(luò)的聚類結(jié)果圖，同時與在UAV 軌跡優(yōu)化中的其他經(jīng)典機器學(xué)習(xí)算法進行了對比，然后評估了IDE算法的收斂性，同時與其他傳統(tǒng)算法進行比較。通信參數(shù)設(shè)置于表1。

表1 參數(shù)設(shè)置

6.2 結(jié)果分析

本節(jié)中，首先給出了h-SOM 網(wǎng)絡(luò)拓撲圖與聚類結(jié)果。在h-SOM 網(wǎng)絡(luò)中，設(shè)定樣本數(shù)量為100，輸入神經(jīng)元個數(shù)為2。如圖4（a）所示為神經(jīng)元輸出情況。圖中小正六邊形代表神經(jīng)元，可以看出輸出層神經(jīng)元有2×2=4個，本研究中輸出神經(jīng)元的個數(shù)即為UAV 數(shù)量。圖中的橫縱坐標為六角形拓撲結(jié)構(gòu)坐標。每個菱形中的線代表神經(jīng)元之間直接連接，菱形中的顏色表示神經(jīng)元之間距離的遠近，從黃色到黑色，顏色越深說明神經(jīng)元之間的距離越遠。圖4（b）為網(wǎng)絡(luò)的聚類結(jié)果，圖中神經(jīng)元中間的數(shù)字表示每個神經(jīng)元包含UE 的個數(shù)，相對來說數(shù)字越大神經(jīng)元面積越大，數(shù)字越小神經(jīng)元面積越小，但不會改變原始神經(jīng)元的拓撲結(jié)構(gòu)。

圖4 h-SOM網(wǎng)絡(luò)拓撲圖與分類結(jié)果

表2 將本文算法與UAV 定位中的經(jīng)典算法模糊C均值聚類（FCM）算法[22]和K-Means 算法[23]進行了能耗的比較，每個表格中有三個指標，分別是Best、Mean 和SD，用來描述算法在多次執(zhí)行時的穩(wěn)定性。Best 表示相同迭代次數(shù)下算法的最優(yōu)解；Mean 表示相同迭代次數(shù)下所有解的平均值；SD 表示相同迭代次數(shù)下解的方差?？梢钥闯鰄-SOM網(wǎng)絡(luò)相對于其他兩種算法的結(jié)果略優(yōu)一些，具有最低的能耗和方差。

表2 不同算法所得UAV位置的能耗結(jié)果

基于上述相對最優(yōu)UAV的部署和初始用戶的聚類結(jié)果，接下來首先研究上述結(jié)果對本問題精確度的影響，如表3 所示；然后研究IDE 算法中不同參數(shù)對該算法收斂性的影響，如表4～表6所示。最后研究不同自適應(yīng)算子對該算法收斂性的影響，如表7 所示。表3 所示為加入精英初始策略和不加精英初始策略的IDE 算法迭代結(jié)果。從表中可以看出，加入精英初始策略的IDE算法最優(yōu)解優(yōu)于不加精英初始策略最優(yōu)解。因為h-SOM 網(wǎng)絡(luò)本身是基于聚類的神經(jīng)網(wǎng)絡(luò)，在此基礎(chǔ)上用IDE算法尋優(yōu)，為算法提供了優(yōu)質(zhì)的初始解。

表3 不同初始值的IDE算法結(jié)果

表4 IDE算法中不同種群數(shù)量的能量消耗

表5 IDE算法中不同F(xiàn) 值的能量消耗

表6 IDE算法中不同CR值的能量消耗

表7 IDE算法中不同ω 值的能量消耗

然后，針對不同參數(shù)對IDE算法的影響如表4～表6所示，本實驗中設(shè)置相同的初始值。在IDE 算法中，有三個重要的基本參數(shù)，即種群大小P、差分放大系數(shù)F和交叉因子CR。從表4 可以看出，所提出的算法在P=20 時保持最佳。這是因為當(dāng)P很大時，小的差分放大系數(shù)會阻礙它得到最優(yōu)解，同時增加迭代次數(shù)才能收斂；當(dāng)P很小時，種群多樣性減小。如表5 所示，能量消耗隨著F的減小而變化，并且當(dāng)F=1 時，收斂效果最好。這是因為小的差分系數(shù)對群體多樣性的貢獻比較小，而大的差分方法系數(shù)可能導(dǎo)致問題無解。因此，適當(dāng)?shù)牟罘址糯笙禂?shù)很重要。如表6 所示，所提算法的性能隨著CR的增長而下降，原因為交叉是隨機的，不涉及任何已知的信息，例如最優(yōu)解。設(shè)計交叉因子的目的是增加種群的多樣性，而在本問題中太大反而影響結(jié)果。因此，本文對IDE算法設(shè)定P=20，F(xiàn)=1和CR=0.1。

接著，為了評估自適應(yīng)算子對算法性能的影響，比較了固定算子與自適應(yīng)算子的性能，分別取ω值0.2、0.5、0.8。如表7所示，明顯看出自適應(yīng)算子的優(yōu)化效果較好。這是因為在迭代初期，自適應(yīng)算子值大于隨機數(shù)，增加種群多樣性，增加全局搜索能力；后期，自適應(yīng)算子隨著迭代次數(shù)的增加而逐漸減小，進行局部搜索已達到迭代次數(shù)或者最優(yōu)值，這種自適應(yīng)算子平衡了算法全局與局部搜索提高了搜索效率。

為了驗證算法的有效性，還將本文算法與貪婪算法、隨機算法以及標準的DE 算法進行比較。本文所用的貪婪算法依據(jù)貪婪原則即每個UE隨機將任務(wù)卸載到就近的UAV，如果就近的UAV 計算資源不足，則UE 在本地執(zhí)行計算。所用的隨機算法是UE隨機將任務(wù)卸載到某個UAV 上，如果分配的UAV 計算資源不足，UE 將在本地執(zhí)行計算。

如圖5 所示，繪制了不同算法具有5 個UAV 的100到300個UE數(shù)量的能量消耗。從圖5可以看出，能量的消耗隨著UE的數(shù)量而增加，原因是任務(wù)數(shù)量增加，能耗增加。當(dāng)用戶數(shù)量分別為100、200 和300 時，圖中IDE算法的能耗分別是51.241 1、140.915 6、239.262 5，同比貪婪算法降低了約10.95%、3.82%和2.24%，同比隨機算法降低了約38.39%、19.87%和7.96%，同比DE算法降低了約6.98%、3.34%和1.83%。由此可以看出在UAV 數(shù)量和時延一定的情況下，圖中IDE 算法的能耗最低，比最高隨機算法降低了約38.39%。

圖5 貪婪、隨機、DE和IDE算法在不同UE數(shù)量下的能耗圖

圖6 展示了不同算法具有 100 個 UE 的 2～8 個 UAV數(shù)量的能量消耗。從圖6可以看出，貪婪算法、DE算法和IDE算法實現(xiàn)了能量消耗隨著UAV數(shù)量的增加而明顯下降，然而對于傳統(tǒng)的隨機算法，由于卸載是隨機分配的，因此無法確保其性能，所以下降幅度不明顯。當(dāng)UAV 數(shù)量分別為 2、5 和 8 時，圖中 IDE 算法的能耗分別是79.462 9、50.144 1、36.525 8，同比貪婪算法降低了約5.73%、9.32%和10.47%，同比隨機算法降低了約12.31%、42.45%和54.33%，同比DE 算法降低了約3.37%、7.61%和6.93%。由此可以看出在UE數(shù)量和時延一定的情況下，圖中依然是IDE 算法的能耗最低，隨機算法的能耗最高?？梢钥闯鲎罡吣芎暮妥畹湍芎南鄬τ趫D5 的能耗還要降低得多，因為圖6 實驗中無人機數(shù)量相對較多，可以將更多的任務(wù)合理地在無人機上進行卸載。

圖6 貪婪、隨機、DE和IDE算法在不同UAV數(shù)量下的能耗圖

圖7 展示了不同算法具有 100 個 UE，5 個 UAV 的2～6 s時間延遲的能量消耗。在圖7中，可以明顯看到隨著延遲的增大，系統(tǒng)的能耗只做出了微小的改變，但是本文所提的IDE 算法仍然保持最低能耗。這是因為該算法在搜索方面功能強大，不易陷入局部最優(yōu)點，進而獲得更優(yōu)的解。當(dāng)時延分別為2 s、4 s 和6 s 時，圖中IDE 算法的能耗分別是50.456 9、45.243 2、40.925 8，同比貪婪算法降低了約8.91%、7.13%和9.51%，同比隨機算法降低了約42.49%、46.17%和50.67%，同比DE 算法降低了約6.92%、4.22%和5.38%?？梢钥闯鲈赨AV 數(shù)量和UE 數(shù)量一定的情況下，圖中能耗最低的依然是IDE算法，最高是隨機算法，而貪婪算法和DE算法的能耗相對于IDE算法的能耗略高些。

圖7 貪婪、隨機、DE和IDE算法在不同時延T下的能耗圖

從圖5、圖6 和圖7 中可以看出，本文所提的聯(lián)合雙層優(yōu)化方法即h-SOM 網(wǎng)絡(luò)和IDE算法的性能優(yōu)于其他兩種傳統(tǒng)算法。對于傳統(tǒng)的隨機算法，UE 隨機做出決定，可能導(dǎo)致UE 卸載到距離自己較遠的UAV 上，在這種情況下，傳輸能量消耗就變得異常大，同時對于卸載UE 有可能變得無效，因此它保持最高的能量消耗。貪婪算法、標準DE算法和IDE算法執(zhí)行計算分配，可以控制UE的卸載數(shù)量，從而為UE節(jié)省能量，所以這三種算法的表現(xiàn)優(yōu)于隨機算法。貪婪算法在求解該問題時基于一定的貪婪策略即每個UE把任務(wù)卸載到離自己最近的UAV 上，這樣雖然減少了UE 在傳輸過程中的能耗，但并未全局考慮UAV 的計算資源限制。DE 算法是一種基于全局搜索的群智能算法，它將差分操作迭代地應(yīng)用于群體，直到達到最優(yōu)解，所以標準DE算法比貪婪算法有更好的性能。在DE算法的基礎(chǔ)上引入精英初始策略和自適應(yīng)雙變異策略，每次迭代產(chǎn)生隨機數(shù)與自適應(yīng)算子進行比較采取不同的變異策略，使得算法在迭代初期保持解的多樣性，在迭代后期局部搜索更加準確，提高算法的精確度。因此，IDE算法比其他三種算法的性能優(yōu)越。

6.3 復(fù)雜度分析

表8比較了h-SOM網(wǎng)絡(luò)和FCM及K-Means算法的計算時間。從表8 可以看出，本文所用的h-SOM 網(wǎng)絡(luò)由于初始時需要進行迭代訓(xùn)練，訓(xùn)練時間高于FCM 和K-Means算法，但是訓(xùn)練好后的h-SOM只需要執(zhí)行神經(jīng)網(wǎng)絡(luò)的前向計算就可以得到分類結(jié)果，其計算復(fù)雜度遠低于FCM 及K-Means 算法，適合求解實時的動態(tài)優(yōu)化問題。

表8 不同算法的時間消耗s

圖8展示了IDE算法與貪婪算法、隨機算法以及標準的DE算法在不同UE數(shù)目下計算時間的對比圖。從圖8中可以看出，貪婪算法和隨機算法的計算復(fù)雜度相對較低，但是根據(jù)前面的實驗結(jié)果，兩種方法解的質(zhì)量均不高。DE算法和IDE算法均具有較好的全局搜索能力，計算復(fù)雜度相當(dāng)，但是由于IDE 算法引入了精英初始策略和自適應(yīng)雙變異策略，所以IDE算法能夠較快收斂，計算時間更少，結(jié)果更優(yōu)。因此，相對來說，本文所用的算法整體性能更優(yōu)。

圖8 貪婪、隨機、DE和IDE算法不同UE下的時間消耗圖

7 結(jié)論

本文研究了多用戶-多無人機MEC 系統(tǒng)的計算卸載方案，通過用多個UAV 提高傳統(tǒng)MEC 系統(tǒng)的性能。在該系統(tǒng)中需要聯(lián)合優(yōu)化UAV 的位置部署和計算卸載。一般方法來解決這一聯(lián)合優(yōu)化問題時，將面臨兩個問題：混合決策變量和解空間較大，同時忽略了UAV的部署和任務(wù)卸載之間的關(guān)系。本文提出的這種雙層優(yōu)化方法，以UAV的部署為上層優(yōu)化問題，任務(wù)卸載為下層優(yōu)化問題的兩層優(yōu)化方法。在上層中，用h-SOM 神經(jīng)網(wǎng)絡(luò)，根據(jù)UE的位置求解UAV的最佳部署。該方法不僅減少了計算時間，而且針對新用戶能夠快速聚類，無需重新求解。接著，IDE 作為下層優(yōu)化算法，針對多變量，多目標優(yōu)化問題能夠提高全局搜索能力，自適應(yīng)地調(diào)整卸載策略達到最優(yōu)。

最后，針對本文所提算法性能進行了仿真實驗，并通過各種性能指標驗證了本文算法的有效性。