無人機邊緣計算高能效任務完成率最大化方案

劉伯陽，王怡心，楊寧樂，黨儒鴿，萬奕堯

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

信息與通信技術(Information and Communications Technology，ICT)的快速發展激發越來越多對復雜度與時延要求高的新應用與新業務，如增強現實(Augmented Reality，AR)、虛擬現實(Virtual Reality，VR)及超清直播等。然而，目前大部分移動終端受限于其成本、尺寸、算力以及有限的電池電量，難以長期穩定運行上述業務，部分低成本設備甚至無法獨立運行。為緩解此類問題，移動邊緣計算(Mobile Edge Computing，MEC)技術被提出[1-2]。在MEC網絡中，MEC服務器部署于網絡基站處，為地面用戶提供計算服務?？紤]服務器部署位置固定，網絡中與基站之間無線鏈路遮擋嚴重的用戶不能獲得高質量計算服務。另外，網絡中固有的MEC服務器計算能力在滿足一些大型賽事、演唱會及集會等突發計算任務密集產生場景的要求時易出現問題。因此，需要一種更為靈活的MEC網絡服務架構。

無人機(Unmanned Aerial Vehicle，UAV)具有高機動性與靈活性，易避開建筑物等遮擋與地面用戶建立高質量視距鏈路，且可隨時部署于突發的密集計算任務產生區域[3]。因此，MEC與UAV的結合得到廣泛關注。文獻[3]對用戶的CPU頻率、任務卸載時間長度以及UAV發送功率與飛行軌跡進行聯合優化，最大化UAV-MEC網絡計算速率。文獻[4]對計算任務分配比例、上下行通信資源調度參數以及UAV飛行軌跡進行優化設計以最小化網絡能耗。還有關于UAV-MEC網絡中地面用戶能耗最小化問題的研究，對UAV部署位置、工作時隙分配以及任務分割比例進行優化設計[5]；通過優化UAV三維空間軌跡、用戶通信帶寬以及UAV發送功率最大化計算效率[6]；利用多智能體深度強化學習算法對UAV軌跡等參數進行設計，對用戶部署公平性、UAV之間的負載公平性以及用戶整體能耗進行優化[7]；通過一種認知UAV-MEC網絡架構，將認知技術引入UAV-MEC網絡中，在提升網絡頻譜效率的同時最小化網絡能耗[8]。文獻[9-10]將UAV作為移動中繼，利用UAV在地面用戶和遠端基站之間搭建起高質量視距信道，在任務高發階段，UAV可以將無法及時處理的任務進一步卸載到遠端基站進行處理。以地面用戶服務時延以及UAV的飛行能耗加權和最小化為目標，聯合優化UAV的飛行軌跡、計算資源分配以及任務卸載決策，降低了物聯網系統中傳感器時延，并提升了UAV的續航時間[11]。為了進一步降低地面終端的任務時延，文獻[12]將UAV作為空中基站收集地面傳感器的信息，以全部地面終端時延之和最小化為目標，聯合優化了UAV的飛行軌跡和資源調度。同時，文獻[13]考慮了基于多UAV協同的MEC網絡，聯合優化了各UAV飛行軌跡及用戶調度，實現了用戶吞吐量最大化。上述研究均基于相同的假設，即UAV可以完成全部地面用戶的計算需求。但是，UAV搭載與續航能力有限，其可搭載的服務器性能有限，在地面用戶計算任務量較大或用戶數量較多時，UAV很難獨立完成地面用戶全部的計算任務。

針對UAV算力與能量有限情況下的MEC網絡服務覆蓋范圍不足問題，擬提出一種UAV算力、UAV軌跡、用戶卸載任務量與UAV卸載任務量的聯合優化方案。該方案利用分塊迭代、拉格朗日對偶以及連續凸近似(Successive Convex Approximation,SCA)算法對所建立的數學優化問題進行求解，并優化設計網絡參數。通過在不同網絡參數下對所提方案性能進行仿真與分析，驗證所提方案的有效性，以期實現在最小化UAV-MEC網絡能耗的同時最大化地面用戶任務完成率。

1 系統模型

所提方案是由一個地面基站、一個UAV與K個地面用戶構成的UAV-MEC網絡架構，具體的系統模型如圖1所示。

圖1 系統模型

令集合QK={1,2,…,K}表示地面用戶集合，地面基站與UAV均搭載了移動邊緣計算服務器。假設地面用戶與基站之間由于遮擋等原因不存在直接鏈路，如果地面用戶計算能力弱，則其無法單獨進行任務計算。為此，可將待計算任務上傳至UAV，UAV再通過本地計算與將待計算任務轉發至地面基站進行用戶任務計算。

1.1 坐標與信道模型

考慮笛卡爾三維坐標系、基站與地面用戶高度為0 m，基站水平坐標為wb=(xb,yb)，第k個地面用戶水平坐標為wk=(xk,yk)，UAV飛行高度設置為H，此高度為避開障礙物并與地面基站用戶建立直接鏈路的最低安全高度。UAV從起始水平位置qI飛往終點位置qF，最大飛行時延為Δs。為了方便分析與優化系統參數，將總時延均分為N個時隙，每個時隙長度表示為T=Δ/N，令QN={1,2,…,N}表示時隙集合，令q[n]表示UAV第n個時隙的水平坐標。

由于UAV與基站以及地面用戶有直接鏈路的場景，第n個時隙UAV與基站以及第k個地面用戶之間的信道功率增益分別建模為[3]

(1)

(2)

式中：βk(k=0,1,…,K)表示參考距離為1 m時的信道功率增益；?k∈QK,?n∈QN。

1.2 計算與能耗模型

每個地面用戶均具有待計算任務。用二元組(Lk,Ck)描述第k個地面用戶的任務，其中Lk表示待計算任務量，Ck表示計算1 bit任務需要耗費的CPU周期數。地面用戶通過頻分多址(Frequency Division Multiple Access,FDMA)的方式將任務上傳至UAV處，上傳帶寬為BU。令lk[n]表示第k個地面用戶在第n個時隙上傳給UAV的計算比特數，則其第n個時隙上傳能耗為

(3)

令fk[n]表示UAV在第n個時隙分配給第k個地面用戶的算力，則UAV在第n個時隙的計算能耗為

(4)

式中，γ為能耗因子。

采用文獻[14]中的模型，UAV飛行功率為

(5)

其中，

式中：v[n]為速度矢量；P0與PH分別與無人機螺旋槳旋翼功率與誘導功率有關的常數；Utip表示無人機旋翼尖端的轉速；v0為無人機懸停時的平均旋翼誘導速度；ρ0、A、d0和s分別表示空氣密度、無人機旋翼面積、無人機機身阻力比以及旋翼實度[14]。

UAV將部分任務在本地計算后，采用時分多址(Time Division Multiple Access，TDMA)的方式將其余任務卸載至基站進行計算。每個用戶的任務在其對應的子時隙內進行卸載，子時隙長度為δ=T/K。令rk[n]表示UAV在第n個時隙卸載的第k個地面用戶的任務量，則UAV在第n個時隙總能耗為

(6)

1.3 問題建立

為最大化用戶任務計算率、用戶能耗與UAV能耗加權和，優化問題建立如下。

(7)

C4:fk[1]=0,rk[1]=0

C5:lk[n]≤lk,max[n]

C6:rk[n]≤rk,max[n]

C8:μk∈[0,1]

C9:q[0]=qI,q[N]=qF

C10:‖q[n]-q[n-1]‖2≤(VmaxT)2

其中，

(8)

(9)

2 問題求解

問題P1為非凸問題，為方便求解，可將約束C1與約束C3進行等價替換，將原問題變為

(10)

C2,C4-C7,C9,C10

考慮問題P2仍為非凸問題，采用分塊迭代算法進行計算。首先，給定一個滿足約束條件的UAV軌跡q，對優化問題進行求解，對變量f、l與r進行優化。其次，設定f、l與r為優化后的變量值，優化UAV軌跡q。最后，返回第一步進行循環直到算法收斂。

2.1 給定UAV軌跡q的問題求解

給定q后，問題變為

(11)

s.t. C1-C7

該問題為凸問題，在不考慮問題求解時間限制，可以用求解效率較低但功能強大的凸優化工具包進行求解。但是，在實際應用中，需考慮問題求解的時間效率，提供一種適用于工程領域的拉格朗日對偶算法對上述問題進行快速迭代求解。

問題P3的拉格朗日對偶函數為

(12)

其中，

式中：λ、β、χ和φ均表示對偶矩陣。

P3對應的對偶函數為

(13)

s.t. C4-C6

則P3的對偶問題為

(14)

s.t.λ,β,χ,φ0

利用對偶分解理論，對偶函數計算可分解為3KN個子問題。對應任意k、n，子問題為

(15)

利用KKT(Karush-Kuhn-Tucker)條件[15]，可得lk[n]的最優解為

(16)

其中，

對于rk[n]，子問題為

(17)

同理，利用KKT條件，可得rk[n]的最優解為

(18)

其中，

(19)

對于fk[n]，子問題為

(20)

得最優解為

(21)

(22)

(23)

(24)

(25)

2.2 優化UAV軌跡

UAV軌跡優化子問題如下。

(26)

s.t. C5,C6,C9,C10

(27)

利用SCA算法，給定v1[n]和v2[n]的任意可行解v1,j[n]和v2,j[n]，非凸約束用凸約束近似為

(28)

其中，

(29)

因此，非凸項由凸項近似代替為

(30)

(31)

在式(31)中，

(32)

其中，

同理，將非凸約束C6替換為凸約束

(33)

在式(33)中，

(34)

通過上述分析，問題P7轉換為

(35)

C9,C10

步驟1初始化。選擇合適步長r[n]∈(0,1]，輸入初始可行點矢量為

Ωj[n]=(q(j)[n],v1,j[n],v2,j[n])

n∈QN，令j=0

步驟3根據P8計算Ω*(Ωj[n])。

步驟4令Ωj+1[n]=

Ωj[n]+rj[Ω*(Qj[n])-Wj[n]]。

步驟5j←j+1，返回步驟2。

3 實驗結果與分析

3.1 仿真的環境和參數設置

對所提的算法進行仿真驗證，地面用戶隨機分布在50 m×35 m范圍內，所用其余仿真參數[17]如表1所示。

表1 仿真參數

3.2 仿真結果

UAV軌跡與UAV能耗權值ωUAV的關系如圖2所示。為測試UAV軌跡與ωUAV的關系，仿真過程中將地面用戶集中部署于較為密集的區域。隨著ωUAV的增大，系統越來越重視UAV的飛行與計算能耗。因此，UAV會沿著盡可能短的軌跡從起點飛往終點。

圖2 UAV軌跡與UAV能耗權值ωUAV的關系

由圖2可以看出，隨著ωUAV的減小，系統越來越看重地面用戶的能耗與任務計算率。ωUAV是UAV能耗權重，ωUAV越大，系統在網絡參數優化過程中對UAV能耗的減少更看重。反之，ωUAV減小，則系統在網絡參數優化過程中會更看重用戶的能耗。因此，ωUAV減小時，UAV會更靠近地面用戶所在區域，減少與地面用戶的距離，與其建立更好的地空鏈路，從而減少地面用戶能耗。

UAV上行帶寬BU與下行帶寬BD對系統性能的影響如圖3所示。

圖3 UAV上行帶寬BU與下行帶寬BD對系統性能的影響

隨著上行帶寬BU與下行帶寬BD的增加，系統目標函數值增加。上行帶寬BU增加，地面用戶可以卸載更多的數據給UAV。下行帶寬BD增加，UAV可以給地面基站卸載更多的數據，提升任務計算率。且由香農公式可知，由于帶寬增加，地面用戶與UAV在功率方面有更多的決策空間，能耗減少。由圖3可以看出，由于受到下行帶寬BD的限制，單純地增加BU并不能無限增加系統性能。在系統設計時需對上行與下行帶寬進行綜合考慮。

UAV最大飛行速率Vmax與飛行時隙個數N對系統性能的影響如圖4所示。

圖4 UAV最大飛行速率Vmax與飛行時隙個數N對系統性能的影響

由圖4可以看出，隨著UAV最大飛行速率Vmax的增加，系統目標函數值增加。由UAV飛行功率表達式可知，UAV功耗與飛行速度有直接關系，懸停或以最快速度飛行并不能獲得最低功耗。同時，考慮UAV必須在規定時間內由起點飛往終點，UAV不能以任意速度飛行。Vmax增加，UAV將具有更大的決策空間，從而提升系統性能。飛行時隙個數N越大，UAV具有更多的時間進行飛行與任務計算、卸載，亦可提升系統性能。

4 結語

針對UAV-MEC網絡中由于UAV計算能力與能量有限導致其難以完成所有地面用戶計算任務的實際情況，研究了一種UAV-MEC網絡中地面用戶任務完成率與網絡能耗加權和最大的系統優化方案。所提方案利用分塊迭代、拉格朗日對偶以及SCA算法對所建立的非凸優化問題進行求解，對UAV算力、UAV軌跡、用戶卸載任務量與UAV卸載任務量進行聯合優化。為了驗證所提方案的有效性，通過對所提方案在UAV能耗權重、上下行帶寬以及最大飛行速率等不同網絡參數下的性能進行仿真測試，當UAV權重減小時，拉近UAV和地面用戶的距離，能夠更好的優化目標函數。其次，單獨增加上行帶寬并不能無限增加系統性能，故所提方案綜合考慮UAV的上行與下行帶寬，能夠更好的優化系統性能。最后，更高的UAV的飛行速度與更多的飛行時隙數能夠進一步提升UAV-MEC網絡系統性能。在下一步研究中將引入人工智能技術對UAV-MEC網絡智能資源調度。