無人機群輔助邊緣計算系統的任務卸載和資源分配聯合優化

劉世豪, 黃仰超, 胡 航,*, 司江勃, 韓蕙竹, 安 琪

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077;2. 西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室, 陜西 西安 710071)

0 引 言

隨著移動設備的日益增多,各種新型的移動應用不斷涌現,如導航、圖像和視頻處理、增強虛擬現實、人臉識別、實時在線游戲和無人駕駛,這些應用大多具有計算密集性和時延敏感性等特點,對傳統網絡性能提出了巨大的挑戰[1-2]。為了解決該問題,移動邊緣計算(mobile edge computing,MEC)通過部署設備在用戶附近提供高效的服務來緩解用戶設備的計算壓力[3-4]。但是該方案在部署邊緣計算服務器(edge computing server,ECS)時受地理環境制約。由于無人機的靈活性和機動性,通過無人機平臺搭載ECS為用戶提供計算服務,是降低時延和能耗的一種很有前景的方案[5-11]。

單個無人機由于能耗和負載的約束,計算性能難以適應日益增長的需求,制約了無人機的應用場景[12-13],因此關于無人機群的研究越來越多。目前關于無人機群輔助邊緣計算的研究包括:文獻[14]在研究無人機部署時,通過引入差分進化機制,最小化平均時延來平衡無人機的負載。文獻[15]研究了多無人機中繼系統的應用,其中地面終端至少被一個無人機服務,目標是最大限度地減少提供無線覆蓋的無人機數量。文獻[16]研究了無人機的部署優化問題,在確定區域內用最少的無人機取得最大的覆蓋范圍,使無人機覆蓋時間最大化。文獻[17]在用戶需求約束下,通過進化算法聯合優化了多架無人機的部署和任務調度,以最小化系統的能耗。文獻[18]通過聯合優化無人機的軌跡和資源分配,以最小化系統能耗,而且在軌跡優化時增加了無人機之間的防撞策略。文獻[19]針對用戶關聯性,提出基于壓縮感知優化算法以最小化系統的功耗。文獻[20]考慮將多個無人機進行角色劃分和用戶分組,以便最大限度地利用通信和計算資源。文獻[21]通過聯合優化多架無人機的軌跡和計算資源,最小化無人機與用戶能耗加權和以確保用戶卸載公平性。然而,文獻[21]并沒有考慮時延的影響,文獻[22]僅考慮了在單無人機情況下,通過聯合優化計算資源和任務調度,最小化無人機能耗和時延加權和,以增強無人機服務的性能,但在多無人機條件下并沒有得到充足的研究。文獻[23]研究了多個無人機輔助用戶卸載和軌跡聯合優化以最小化用戶最大時延。文獻[24]討論了無人機群作為用戶需要邊緣計算服務條件下,優化了各個無人機的3D位置以最小化服務時延。

以上的無人機群系統研究大多關注無人機的機動性,并沒有充分利用無人機與無人機之間的通信優勢。文獻[14]雖然利用了無人機的機動性動態選擇其服務的用戶來均衡無人機的負載,但是當無人機的機動性受到制約時(例如,無人機管控政策制約無人機的飛行范圍),無人機服務的區域相對固定,區域內用戶只能選擇區域相關的無人機進行卸載[12-13,25]。由于單個無人機計算性能有限,用戶數據存在隨機性,當無人機的機動性受限時,導致無人機負載不均衡、計算資源利用不足等問題。而無人機群可以通過無人機之間傳輸數據來完成各種任務[26-28],因此可以從全新的角度來解決無人機負載均衡問題。

對于無人機群空中協作場景的研究尚未成熟,文獻[28]討論了了無人機群在邊緣計算的潛力和挑戰,文獻[29]中通過將無人機分類,以滿足不同時延受限的服務。文獻[30]在無人機群輔助邊緣計算條件下,通過控制無人機計算器件的開關,決定計算數據是否卸載到其他無人機計算數據。但是以上文獻只考慮數據的二元卸載方案,并沒有考慮協作卸載方案以及計算資源優化問題。

本文討論了一種新的MEC網絡結構,充分利用了無人機通信資源和無人機之間視距鏈路的優勢。在該系統中,無人機之間可以卸載數據為用戶提供服務。為取得系統時延和能耗的加權和最小,聯合優化了多架無人機的部署、任務調度和資源分配。本文工作的主要貢獻如下:

(1) 針對無人機群輔助邊緣計算系統存在的負載均衡問題,構建一種新的網絡結構,在該網絡中無人機充當ECS和中繼,無人機通過數據的相互卸載緩解負載均衡問題。同時考慮系統的能耗和時延,構建能耗和時延加權和最小的優化問題。

(2) 為解決上述非凸問題,提出了雙層優化方法——啟發最優評價算法(heuristic optimal evaluation algorithm, HOEA)。上層使用粒子群優化 (particle swarm optimization, PSO) 算法優化無人機的位置,下層在給定的位置下優化無人機的數據卸載和資源分配。在實際操作中,將下層問題分解成兩個子問題并使用塊坐標下降(block coordinate descent, BCD)算法進行求解。

(3) 與其他方案相比,所提策略在無人機計算資源不均衡或者數據不均衡的情況下能取得更低的系統成本,尤其是負載不均衡程度加劇時,效果更為明顯。說明可以通過無人機群邊緣計算提高無人機的計算資源利用率,減少系統成本。

1 系統模型與問題描述

無人機群輔助邊緣計算模型如圖1所示。

圖1 系統模型Fig.1 system mode

圖1中每個陰影部分代表一個區域,并且每個區域都配備有一個無人機,稱為本地無人機,每架無人機可以為本區域內的用戶提供計算服務,受無人機管控政策約束,本地無人機只能在對應區域的上空飛行,禁止跨區域飛行,無人機在空中可以進行通信,并且配備多根天線。系統不考慮用戶間的通信干擾。具體而言,部署R個無人機對應R個區域,每個區域地面用戶有L個,其中區域的劃分r∈R={1,2,…,R},R表示區域集合。無人機使用對應的區域進行編號,區域的范圍集合為O={O1,O2,…,OR},Or表示無人機r能機動的范圍,各區域的用戶集合為Lr={1,2,…,L},Lr表示區域r內的用戶集合。假設每個無人機都裝備有MEC服務器,并且具有通信中繼功能。

矩陣A表示無人機之間的連接方案,矩陣元素ars表示無人機r到無人機s之間的連接狀態,ars=1表示無人機r卸載數據到無人機s,ars=0表示無人機r未卸載數據到無人機s,并且asr和ars含義并不相同。

(1)

1.1 通信模型

(2)

式中:α0表示發送功率為1 W、距離為1 m處的信道增益;||·||為歐式范數。那么,地面區域r中第i個用戶到本地無人機的傳輸速率為

(3)

同理,無人機r與無人機s之間的通信速率為

(4)

1.2 時延模型

假設地面用戶k的任務記為{ck,ik},ik為用戶k計算數據大小(bit),ck表示用戶k計算任務執行1位數據時所需ECS的中央處理器(central processing unit, CPU)周期數(cycles/bit)。用戶在向本地無人機進行卸載時,采用全卸載方案,無人機向無人機卸載數據時,采取協作式卸載方案。

時延主要有3個方面,地面用戶到無人機的傳輸時延,無人機本地計算需要的時間,以及無人機卸載到其他無人機傳輸數據的時延和數據計算的時延,其中無人機計算數據和卸載數據可以同時進行。在本文中忽略結果回傳所需的時延和能耗。區域r內i用戶卸載數據到本地無人機的時延為

(5)

本地無人機計算時延為

(6)

第s個無人機卸載i用戶數據到第r個無人機的傳輸時延為

(7)

為簡化問題,無人機向目標區域分配的計算資源被目標區域內用戶平均占用。第r個無人機計算s區域i用戶卸載數據的時延為

(8)

(9)

1.3 功率模型

無人機r與其他無人機通信所消耗的能量為

(10)

無人機的計算功耗包含兩部分,計算本地數據能耗以及計算其他無人機卸載的數據能耗。本文中使用文獻[31]中的能量計算模型,無人機r的計算能耗為

(11)

式中:K為CPU架構的有效開關電容。

系統中用戶傳輸數據的總能量為

(12)

無人機計算能耗和通信能耗的總和為

(13)

1.4 問題描述

假設地面用戶位置和計算任務量已知,無人機的部署、資源分配、數據卸載比例和連接方案分別為Q,f,β,A。為提升無人機群邊緣計算系統在負載不均衡場景下的效果,通過聯合優化用戶卸載比例、無人機的部署和計算資源分配最小化系統成本。優化問題表示為

(14)

2 優化問題求解

原優化問題為非凸問題,一般的優化算法不容易解決。啟發式算法由于和梯度無關,有利于解決該問題。由于無人機的位置和任務分配是緊密耦合的,因此單獨使用啟發式算法不太合適。受文獻[17]啟發,本文采用分層優化算法,上層使用PSO算法優化無人機的位置,而下層以最優資源分配方式對該位置進行評價。對于無人機之間的連接方案,考慮實際情況的限制,可以很明顯地減少備選連接方案。

2.1 連接方式

如果對上層的連接方式直接進行遍歷,若有R個無人機,則有2R×(R-1)種連接方式,當無人機數量很多時,該方式不合理。但是通過觀察發現一些無人機連接情況是不可能出現的,通過消除這些不可能出現的連接能很大程度縮小可行域。在實際場景中,當無人機提供向其他無人機卸載數據時,便不再向其他無人機提供計算服務。在本文中無人機的連接方式使用矩陣A中元素ars表示,當無人機ars=1,表示無人機r向無人機s卸載數據,則此時所有的無人機都不會向無人機r卸載數據,則無人機之間卸載約束為

(15)

(16)

(17)

計算資源占用大的向計算資源占用小的卸載,反之則不會,即在Gr>Gs,r,s∈R條件下,無人機r到無人機s可以選擇卸載和不卸載數據兩種狀態,但是無人機s卻不能卸載數據到無人機r,可表示為

(18)

通過上述分析可以很大程度上縮減尋找最優連接方式的范圍,如算法1所示。

算法 1 連接方式篩選算法1 初始化矩陣(R-1)×(R-1),每個元素值只有{0,1}可以選擇;2 計算輔助變量Gi,i∈R;3 通過式(15)～式(18)選擇符合條件的矩陣,總計為Nmax;4 輸出符合條件的矩陣A和總數Nmax。

2.2 HOEA

多無人機的位置優化是一個非凸的問題,并且各個無人機之間位置選擇是相互耦合的,這對優化有非常大的影響,導致一般的優化方法很難解決,因此考慮使用啟發式算法求解。本文采用標準PSO算法[33],但是傳統的PSO算法很難解決無人機位置與任務調度緊密相關的問題,為此以PSO算法為基礎,將PSO和凸優化方法結合,解決無人機位置和任務調度的緊密相關的問題。將原問題分解成兩層問題,上層算法使用PSO算法尋找多個無人機的部署,下層算法在給定無人機部署情況下,以最優任務調度評估多無人機的部署,用以粒子的更新。

給定無人機部署Q和連接方式A條件下,下層的問題可以表述為

(19)

(20)

式中:C9和C10保證了將服務延遲線性化后和原問題等價,但是線性化之后,問題依然非凸,則在本文中采用BCD算法將其分成兩個子問題。

子問題1:計算資源分配優化

(21)

式中:變量χ={f};C2,C7,C8表示每個無人機計算資源受限并且分配的資源非負。由于目標函數為凸的,約束為凸,則該問題為凸優化問題,使用CVX工具箱進行求解。

子問題2:數據分配優化

(22)

式中:變量χ={β};約束C1,C5和C6表示全部數據被計算以及數據分配非負。該目標函數對變量β是仿射的,并且約束為凸,所以該問題為凸優化問題,使用CVX工具箱進行求解。

BCD資源分配算法展示如算法2所示。

算法 2 BCD資源分配算法輸入 無人機連接方式AN,位置Q和任務分配β0,ξ=10-3; Repeat (1) 輸入AN,Q,β(k),計算P3得出f(k); (2) 輸入AN,Q,f(k),計算P3得出β(k),并計算對應的值U(k); (3) 更新k=k+1; (4) 如果|U(k+1)-U(k)|≤ξ跳出循環,輸出{β,f},并且輸出此時的系統成本值U=U(k+1); 輸出 {β,f,U}。

(23)

(24)

對粒子的邊界進行處理,使用算法2計算效用函數,更新每個粒子的全局最優值和局部最優值,直至達到最大迭代次數Smax。

本文提出了無人機部署、卸載方案和計算資源聯合優化解決方案,在給定無人機連接情況下,通過PSO算法進行無人機位置部署,使用BCD算法進行任務卸載和計算資源分配。HOEA算法的偽代碼展示如算法3,圖2展示了該算法的流程圖。類似文獻[34]分析,整個算法的復雜度主要受PSO算法和BCD算法影響。PSO算法的復雜度取決于粒子維度大小Np和最大迭代次數Smax,在最壞的情況下復雜度為O(NpSmax)。計算資源分配和任務調度優化算法使用BCD算法,該算法最大復雜度約為O((N+M)Gmax),其中Gmax為迭代的最大次數,N和M分別為計算資源優化的變量數和任務分配的變量數,則整個算法的復雜度為O(NmaxNp(N+M)GmaxSmax)。

3 仿真結果分析

本節中仿真環境為配置英特爾i7-12700H,2.3 GHz和32 G RAM的計算機,以驗證系統的可行性和所提策略的有效性。該場景下區域數量R=4,無人機數量R=4,每個區域內的地面用戶數量L=5,水平位置分布在邊長為4 000 m的正方形區域,該區域被平均分成4個區域。區域分布和編號如圖3所示,用戶隨機分布在區域內。表1為仿真參數。

表1 仿真參數

3.1 位置優化的優勢

圖3展示了無人機的移動方向和無人機連接情況。無人機1會把本地的數據向其他的3個無人機進行卸載,使用矩陣A表述為[0111;0000;0000;0000]。圖4展示了所提算法與PSO算法在矩陣A=[0111;0000;0000;0000]條件下的性能對比,所提算法和PSO有類似的收斂速度。但是所提算法相比PSO能取得更小的系統成本,因此所提算法優于PSO算法。

圖3 無人機位置變化和連接圖Fig.3 Unmanned aerial vehicle position change and connection map

圖4 算法收斂性Fig.4 Algorithm convergence

表2展示了有無位置優化下的系統成本。無人機位置部署優化受到地面用戶和卸載無人機的影響,具體來說用戶將數據卸載到本地無人機時,無人機的部署會影響用戶傳輸能耗和傳輸時延,當無人機向其他無人機卸載數據時,無人機之間的距離同樣會影響無人機傳輸能耗和傳輸時延。當無人機隨機部署時,對用戶和無人機能耗和傳輸時延造成影響,因此無人機部署是有必要的,表2仿真數據證明了無人機部署優化的必要性。

表2 有無位置優化對比

3.2 所提策略優勢

為探究所提策略的優勢,將與以下兩個方案進行對比。方案1:多個無人機共同服務用戶,用戶只能將數據卸載到本地無人機,無人機之間不相互卸載數據,且本地無人機都在最優的位置提供計算服務,且使用HOEA。方案2:無人機之間可以相互卸載數據,但是每個無人機最多只能向一個無人機卸載數據,并且在最優的位置卸載數據,且使用HOEA。

3.2.1 數據變化的影響

圖5 系統成本隨區域1數據量的變化Fig.5 System cost variation with region 1 data volume

圖6 各區域卸載比例隨區域1數據量的變化Fig.6 Variation of offloading ratio of each region with the amount of data in region 1

圖7展示了在所提策略下無人機隨區域數據變化的軌跡。無人機部署隨著區域數據的變化而變化,尤其隨著數據不平衡程度的加深,無人機位置變化劇烈,無人機會相互靠近以此來減少數據傳輸所帶來的時延和能耗。

圖7 無人機位置隨著計算性能的變化Fig.7 Variation of unmanned aerial vehicle position with computational performance

3.2.2 計算性能變化的影響

圖8比較了3種策略在不同計算性能下系統成本的大小,所有策略下系統成本都隨著無人機1計算頻率的增大而減小。隨著無人機1計算性能的增加,所提策略相比其他策略就越有優勢。

圖8 3種策略系統成本隨無人機1計算資源的變化Fig.8 Variation of system cost with unmanned aerial vehicle 1 computing resources for three strategies

從圖9(b)～圖9(d)中可以看到,隨著無人機1計算性能的增大,其他無人機卸載到無人機1上的比例也越大。圖9(a)說明,當無人機 1計算性能強于其他無人機時,區域1內的用戶數據全部被本地無人機所計算。當無人機之間計算性能相同時,無人機全部采用本地計算的方式,此時所提方案、方案1和方案2三者相同。當無人機之間計算性能差異增大時,計算性能強的無人機所在的區域會選擇全部本地計算,計算性能弱的無人機會向其他無人機卸載數據。從圖10中可以看到,無人機計算性能的變化對整個無人機的位置并沒有明顯的影響。

圖9 各區域卸載比例隨無人機1計算性能的變化Fig.9 Variation of unloading ratio of each region with the computational performance of unmanned aerial vehicle 1

圖10 無人機位置隨著計算性能的變化Fig.10 Variation of unmanned aerial vehicle position with computational performance

4 結束語

本文構建了無人機群輔助邊緣計算的網絡模型,通過設計無人機和無人機之間、無人機和用戶之間的信息交互以實現在數據或計算能力不均衡的情況下,緩解無人機計算負擔,實現整個系統的成本最小化。所提HOEA以PSO為基礎,聯合優化了多無人機卸載、部署和資源分配方案,并通過仿真驗證了所提算法的有效性。此外,文中提出的優化方法可以適用于無人機輔助通信場景下,無人機位置部署和資源分配問題變量耦合的相關問題。在后續的研究中,考慮引入動態多無人機場景,設計無人機的軌跡和任務分配策略,以取得更好的系統性能。此外,無人機群輔助邊緣計算場景下數據卸載的安全性也需要格外重視。