張夢(mèng)琳，江沸菠，董 莉，高 穎

1.湖南師范大學(xué) 智能計(jì)算與語言信息處理湖南省重點(diǎn)實(shí)驗(yàn)室，長沙 410081

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 系統(tǒng)模型

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

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

圖1 系統(tǒng)模型

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

3.2 通信模型

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

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

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

3.3 計(jì)算模型

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

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

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

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

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

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

4 問題擬定與分析

4.1 問題擬定

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

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

4.2 問題分析

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

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

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

5.1 算法流程

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

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

自組織特征映射網(wǎng)絡(luò)（Self-Organizing Feature Map，SOM）也稱Kohonen網(wǎng)絡(luò)。該網(wǎng)絡(luò)是一個(gè)由全連接的神經(jīng)元陣列組成的無導(dǎo)師、自組織、自學(xué)習(xí)網(wǎng)絡(luò)。SOM網(wǎng)絡(luò)能夠以自適應(yīng)的方式實(shí)現(xiàn)任意維度輸入信號(hào)的聚類[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)爭(zhēng)層）組成。輸入層神經(jīng)元個(gè)數(shù)為n，輸出層由m個(gè)神經(jīng)元組成的二維平面陣列，輸入層與輸出層各神經(jīng)元之間實(shí)現(xiàn)全連接。SOM網(wǎng)絡(luò)能將任意維度的輸入模式在輸出層映射成二維圖形，并保持其拓?fù)浣Y(jié)構(gòu)不變。網(wǎng)絡(luò)通過反復(fù)學(xué)習(xí)輸入向量使權(quán)重向量與輸入向量分布趨于一致。

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

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

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

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

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

5.3 改進(jìn)差分進(jìn)化算法

5.3.1 標(biāo)準(zhǔn)差分進(jìn)化算法

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

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

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ùn)用精英初始策略為算法提供了優(yōu)秀的初始解。

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

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

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

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

5.4 算法的特點(diǎn)與優(yōu)勢(shì)

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

6 仿真實(shí)驗(yàn)及分析

6.1 模型設(shè)置

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

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

6.2 結(jié)果分析

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

圖4 h-SOM網(wǎng)絡(luò)拓?fù)鋱D與分類結(jié)果

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

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

基于上述相對(duì)最優(yōu)UAV的部署和初始用戶的聚類結(jié)果，接下來首先研究上述結(jié)果對(duì)本問題精確度的影響，如表3 所示；然后研究IDE 算法中不同參數(shù)對(duì)該算法收斂性的影響，如表4～表6所示。最后研究不同自適應(yīng)算子對(duì)該算法收斂性的影響，如表7 所示。表3 所示為加入精英初始策略和不加精英初始策略的IDE 算法迭代結(jié)果。從表中可以看出，加入精英初始策略的IDE算法最優(yōu)解優(yōu)于不加精英初始策略最優(yōu)解。因?yàn)閔-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算法中不同ω 值的能量消耗

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

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

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

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

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

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

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

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

圖7 貪婪、隨機(jī)、DE和IDE算法在不同時(shí)延T下的能耗圖

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

6.3 復(fù)雜度分析

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

表8 不同算法的時(shí)間消耗s

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

圖8 貪婪、隨機(jī)、DE和IDE算法不同UE下的時(shí)間消耗圖

7 結(jié)論

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

最后，針對(duì)本文所提算法性能進(jìn)行了仿真實(shí)驗(yàn)，并通過各種性能指標(biāo)驗(yàn)證了本文算法的有效性。