無線網絡中具有MEC的多UAV飛行軌跡優化

賈哲松，王高才

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

0 引 言

移動邊緣計算(MEC)將具有計算能力的服務器下沉到距離終端設備較近的網絡邊緣，以達到降低時延、提升效率、節省功耗等目標，從而改善用戶的服務體驗，但同時也帶來了新的挑戰，那就是MEC設備的部署問題。作為對于地面移動邊緣計算的一種補充，由搭載MEC服務器的無人機集群提供的無人機邊緣計算網絡[1]能夠很好解決MEC設備的部署問題。它具有靈活性、智能性和多樣性的優勢，通過對資源的合理分配和UAV軌跡優化，還將有望進一步提高無人機邊緣計算網絡的計算性能[2]。

本文研究了一個以具有MEC功能的UAV為核心的無人機集群，其主要功能是調度多個UAVs前往指定地點收集數據，因此考慮了數據量約束條件下的多UAVs通信延遲問題。其中對飛行軌跡的優化和任務節點的分組排序是改善通信延遲的關鍵因素。為了能夠最大限度地利用UAV資源，還探討了UAV的最佳巡航速度，并驗證了其存在的可能性。

本文主要貢獻總結如下：

(1)研究了UAV的有效巡航軌跡，以確保UAV能夠在規定的服務時間內完成每一個用戶的通信任務。還探討了在UAV巡航速度固定的前提下，通信延遲與多UAV巡航軌跡之間的關系，最終將通信延遲的優化問題簡化為MTSP。

(2)提出一種元啟發式算法K-WAOA，它通過聚類算法K-means來提供初始解集，并使用模因算法來探尋更加優秀的解決方案，其中鯨魚優化算法(WOA)與模擬退火算法(SA)分別作為模因算法框架下的全局搜索策略和局部搜索策略被運用。數值結果表明，所提優化方法具有很好的收斂速度，且在飛行速度受限以及任務密集的工作環境中更能發揮價值，同時還為當UAV數量增加時UAV集群的通信延遲的性能分析提供了實驗分析。

1 相關研究

作為一項很有前景的技術，UAV可以很好地配備MEC設備，以便在地面部署策略受限的場景中提供空中移動邊緣服務，以提高用戶的服務質量(QoS)。MEC服務器則為UAV群帶來了強大的計算能力，成員們可以將復雜的計算任務傳遞給搭載MEC設備的UAV[3-8]，有效地降低整個無人機網絡的延遲，也可以使用更加靈活的部署策略來提高UAV的長期工作效率[9，10]。特別的，文獻[4]將UAV集群聯合調整卸載比和傳輸信道的優化問題表述為卸載博弈，并設計了一種基于并發最佳響應的分布式卸載算法從而有效地減少任務延遲。為了優化UAV網絡的相對延遲，文獻[8]提出了一種基于最短有效作業優先的調度方法。基于調度和資源分配之間的耦合關系，然后聯合優化計算卸載和信道接入問題。考慮到多UAVs需要依靠復雜的充電和重新配置方案才能來實現無縫的長期網絡覆蓋[10]。首先介紹了一種新的UAV能耗模型，其次提出了一種在無縫覆蓋約束下優化的節能可充電無人機部署策略。最后采用一種兩階段聯合優化算法實現了UAV的循環部署策略。

為了提高UAVs信息收集的效率，對其軌跡優化也成為設計的關鍵[11-15]。通過考慮無人機在固定高度飛行，文獻[11]的研究中優化了一維(1D)無人機軌跡，以最大限度地提高無人機支持的WPT網絡的能量傳輸性能。文獻[12]引入了一種高效的聚類算法，以負載平衡的方式將區域劃分為子區域，以最小化無人機的移動次數。對于單無人機和一維無線傳感器網絡的情況，文獻[14]優化了隨時間變化的無人機速度和傳輸間隔，以最小化無人機的飛行時間。在文獻[15]中研究了最大化服務SN數量的時間敏感數據收集任務，其中通過逐次凸近似算法聯合優化無人機的軌跡和無線電資源分配。

2 系統模型

圖1為一個無人機聯盟數據收集系統，該系統包括負責數據收集的N架無人機UAVs，索引由={1，2，…，N} 表示，M個傳感器用戶以及一天搭載有MEC服務器的領導型無人機。在t=0時刻起UAVs被調度從起始點O=(x0，y0) 出發，在航行過程中以及給定區域內的共計M個任務節點上方懸停時收集信息，并最終返回起始點，回收UAVs。為提高任務的成功率，UAVs以某種相對經濟的巡航速度Vf行駛，飛行高度固定為H， 然后UAVs的位置由 (xn，yn，H) 表示，任務節點的地理位置已由領導型無人機收集完成，由于UAVs飛行高度固定，所以主要研究對象為UAVs飛行軌跡在平面上的投影，如圖2所示。記第m個用戶位置為 (xm，ym)， 懸停點位于用戶節點的正上方，即 (xm，ym，H)， 需要收集的數據量為Qm。

圖1 多UAV通信系統模型

圖2 多UAV通信系統水平投影

2.1 相關數學模型

2.1.1 信息傳輸模型

用Tn表示索引為n的UAV的工作周期，在某時刻t的位置為 (xn(t)，yn(t))， 初始時n訪問的任務節點的索引可由n={1，2，…Mn} 表示，因此無人機n的軌跡長度公式

(1)

其中，x′n(t)，y′n(t)， 分別表示xn(t)，yn(t) 關于t的一階導數，tn，m，tn，m-1分別表示n從自身巡航路線第m個以及從第m-1個節點出發的時刻。

在UAV和設備共享同一信道的一對多場景中，干擾模型始終是一個重要問題。在文獻[16]中，UAV通過時分多址(TDMA)從其相關節點收集數據，其中每個傳感器節點僅在計劃進行數據傳輸時喚醒。在這種情況下，UAV順序地與通信節點，并且節點之間不存在干擾。此外，文獻[17]中研究了支持無人機的正交頻分多址(OFDMA)網絡，其中無人機作為移動基站(BS)進行調度，為一組地面用戶提供服務。除去信號干擾外，一對多和多對多傳輸模式還會面臨信道選擇，任務調度等問題[18，19]，這不是討論的范圍。因為研究中采用一對一傳輸模式，即UAVs在同一時刻僅為一個任務節點提供服務，n對第m個任務節點的傳輸速率公式為

(2)

其中，B為帶寬，σ2為高斯白噪聲，β為單位距離下的信道增益，ρ為傳輸功率。

(3)

其中

(4)

2.1.2 采集數據的延遲模型

在t=0時刻n從起止點出發，按順序為指定用戶提供通信服務，最終在t=Tn時刻返回起止點。結合式(4)可知，n在t=tn，m-1時開始負責收集任務節點m的數據，那么m的數據通信延遲公式為

(5)

2.1.3 速度模型

系統中所用到的UAV類型為旋翼無人機(rotary-wing UAV)，這類UAV的工作狀態由推進動力決定，主要為懸停狀態和飛行狀態，因此首先給出UAV的推進功率模型

(6)

其中，P0和Pi是兩個常數，表示懸停狀態下的葉片剖面功率和感應功率；Utip表示轉子的尖端速度；v0為懸停狀態下的平均旋翼誘導速度，d0和s分別為機身阻力比和旋翼固體度，p和A表示空氣密度和旋翼盤面積[20]。

UAV存在兩種基本類型的速度，即最大續航速度VME和最大航程速度VMR。VME確保在移動期間移動功率最小。VMR可以實現UAV的最長行駛距離，兩者與UAV的最大速度Vmax的關系為：VME

(7)

(8)

接下來驗證VMR可以通過式(8)得出。

Proof：不難看出，當式(8)第二項是凸的便能驗證式(8)成立。因此可以對第二項做兩次一階泰勒展開。計算過程如下

(9)

可知展開之后f(V)″≥0， 那么式子第二項為凸，且三項的非負、非零加權和也為凸。當V≥0， 式(8)為凸，式(7)成立。為了提高UAV的能量利用效率，默認后續的研究內容UAV所使用的移動速度始終保持著Vf=VMR。

2.2 問題分解和重組

2.2.1 UAV巡航軌跡重構

以飛行軌跡Dn.m為例，為了更好量化它，在n的第m個懸停點和第m-1個懸停點之間上引入I個轉折點，如圖3所示。可知Dn.m被分割為I+1條轉折線，且I的值越大量化值就越接近于路徑的實際長度。第i個轉折點坐標可表示為 (xn，m-1，i，yn，m-1，i)；i=1，2，…，I。

圖3 使用轉折點優化UAV飛行軌跡示例

這里補充定義n所經歷的懸停點的坐標可表示為 (xn，m，yn，m)， 在引入轉折點之后為了方便歸類，將懸停點改寫為 (xn，m，0，yn，m，0)， 那么n的懸停點集合、轉折點集合分別為

Shov={(xn，1，0，yn，1，0)，(xn，2，0，yn，2，0)，…，(xn，Mn，0，yj，Mn，0)}
Stra={(xn，0，1，yn，0，1)，…，(xn，0，I，yn，0，I)，…，(xn，Mn，1，yn，Mn，1)，…，(xn，Mn，I，yn，Mn，I)}

所有UAVs起止點表述為 (xn，0，0，yn，0，0) 和 (xn，Mn+1，0，yn，Mn+1，0)， 綜上n的路徑可表示為集合Φn=(Xn，Yn)，Xn=(xn，0，0，xn，0，1，…，xn，1，I，xn，2，0，…，xn，Mn，0，…，xn，Mn+1，0)T，Yn的定義與之同理。

定義Dn.m第i條轉折線的長度公式為

(10)

那么n一個工作周期的計算公式

(11)

(12)

上文已經分析出了n的軌跡Φn， 折線段長度Dn.m，i， 以及隨時間t變化的坐標，那么n自t=0時刻起飛，它的巡航軌跡公式為

(13)

可知n在工作周期對節點m的數據收集量公式可改寫為

(14)

其中

2.2.2 通信延遲

最小化所有任務的通信延遲可表述為min{T1，…，TM}， 假設它們對應的大小關系為：TM≥，…，≥T1事實上必定存在n′遵從如下的等式關系

(15)

可知在引入轉折點來量化UAV的單軌跡之后，通信延遲的優化實際上涉及到了任務節點的分配、排序以及相鄰節點之間轉折點的求解，共計3個問題，因此接下來可以統一對其進行數學建模。

定義一個三維變量B={βn，b，e|n≤N，b，e≤M，n∈Ν+，b，e∈Ν} 用來區分不同UAV的弧。其中βn，b，e=1， 表示懸停點b(或起止點)和懸停點e(或起止點)之間的弧是最優軌跡，否則βn，b，e=0。 對于給定的節點分組和UAV數量N， 優化問題可建立為

Qn，b，eβn，b，e≥Q′b，eβn，b，e；b=0，…，M；

e=1，…，M；b≠e；n=1，…，N

(16a)

b≠e；n=1，…，N

(16f)

2≤b≠e≤M

(16g)

βn，b，e={0，1}；

n≤N；b，e≤M；n∈Ν+；b，e∈Ν

(16i)

其中，Tmax表示UAVs中最大的工作周期。(16a)中Qn，b，e是前文Qn，m在P1的映射，注意b包含了起止點，而UAVs在返航過程中不再收集數據，所以e不包含起止點。Q′e則表示需要在任務節點e收集到的最小的數據量。(16b)，(16c)表示每個UAV只訪問一次起止點，(16d)，(16e)，(16f)表示每個懸停點只允許一臺UAV到達和離開一次，(16g)是MTZ(miller-tucker-zemlin)約束，用來消除子路徑，(16h)表明優化目標是N個UAVs中用時最長的個體。

這是一個MTSP的變種，具有很強的NP-hard性，它表明系統滿足每個任務節點的數據收集需求的同時，還需要最小化UAVs的最大工作周期。

3 基于模因算法框架的鯨魚退火優化算法

多無人機軌跡規劃問題面臨著兩個難點，一個是任務節點的分組，另一個就是無人機軌跡中的懸停點排序優化，同時還需選擇合適的轉折點來控制無人機的飛行軌跡，以此滿足每一個節點的通信要求，接下來將圍繞這些問題來探討優化方法。

3.1 多無人機的任務分組及通信節點排序

模因算法，又稱文化基因算法(memetic algorithm)是Pablo Moscato提出的建立在模擬文化進化基礎上的優化算法，它實質上是一種基于種群的全局搜索和基于個體的局部搜索的結合體。模因算法是指全局搜索框架(鯨魚算法，WOA)和局部搜索框架(模擬退火算法，SA)的組合。WOA充當解決方案生成器，利用算法收斂速度的優勢快速得到所有可能的種群，生成有希望的解決方案來擴展搜索空間。而通過SA則可以有效避免陷入局部最優解的情況。綜上所述，基于K-means的WOA與SA的混合算法(K-WAOA)將有望成為一種能夠高速收斂且全局搜索能力優異的路徑規劃算法。K-WAOA的偽代碼在算法Ⅰ中進行描述。

3.1.1 鯨魚優化算法

(2)適應度函數step3 and step6：算法利用適應度值來評價種群，以及淘汰沒有希望的種群。在這里的優化目標是一個種群中工作周期最長的任務分組，因此利用式(11)構建適應度函數，首先計算出種群內不同分組所需的飛行時間Tn， 最后選取其中而最大值作為該種群的適應度值，則種群的適應度公式為

(17)

(3)包圍獵物step5：該行為模仿的是多個鯨魚群體在進行捕食時，處于最佳位置的鯨魚群體會將自身成員的位置信息共享給其它種群，其它種群則根據得到的信息不斷改變自身成員的位置，以確保能夠達到縮小搜索范圍的效果。其數學表達式如下

(18)

其中

(19)

C1=2γ2

(20)

A1=2αγ1-α

(21)

(4)發泡網攻擊step5：在該階段鯨魚種群會有兩種行為模式，一種是以螺旋的方式向當前最佳種群游走，另一種是在游走的過程中繼續進行包圍獵物階段的動作。選擇兩種行為模式的概率各為50%，數學模型如下

(22)

其中，b為對數螺旋形狀常數，-1到1之間的隨機數。該階段包含局部和全局兩種搜索模式，但由于這兩種方式是隨機發生的，所以可能出現種群向當前周期最優種群收斂進度過快，從而陷入局部最優的情況，這也是WOA性能上最大的缺陷，對此可以采用SA算法，通過其特有的Metropolis準則來進一步提升WOA算法的全局搜索能力。

(5)搜索捕食step5：搜索捕食的思想是在進行最終的捕食行為之前，當前鯨魚種群會隨機選取一個目標，并向其靠攏。該過程雖然會導致最終結果與真正的最優值有所偏差，但可以有效地提高算法的全局搜索能力。這一階段的數學模型與包圍獵物階段的數學模型相似，僅將當前最優種群Π*轉變為隨機種群Πrand， 因此不再過多贅述。

3.1.2 SA(simulated annealing algorithm)

SA算法是一種通用的優化算法，其流程分為加溫過程、等溫過程和冷卻過程，其在路徑尋優的問題中已被較為成熟的運用。值得一提的是等溫過程對應算法的Metro-polis抽樣過程能夠一定概率接受惡化解，從而可有效避免陷入局部極小，最終趨于全局最優。當然SA算法本身也有較大缺陷，那就是算法收斂的結果常常受迭代次數的影響，迭代數越多結果越優秀，相應的消耗的搜索周期也就越長。

3.2 UAV飛行軌跡優化

經由P1所得結果T′max需滿足如下條件

(23)

其中

假設βn′，b′，e′=1根據式(14)和約束式(16a)，可將n′在索引為b′和e′之間的飛行軌跡優化問題可建立為

很明顯這是一個非線性優化問題，主要目的為尋找最優的轉折點及懸停時間，使得UAV既能滿足數據收集的要求，又能使得UAV為目標節點提供服務的耗時最短。P2的求解難度相對簡單，接下來利用式(14)來提前研究最優解的可能取值。

負責通信服務的UAV的最優工作方式，是以額定的速度在相鄰懸停點之間沿直線行駛，并最終在懸停點上方完成對應任務節點剩余的通信任務。

Algorithm Ⅰ：K-Whale Annealing Optimization Algorithm(K-WAOA)

Input：初始親代種群數量，S；UAV數量，N；懸停點坐標，(xn，yn)；n=1，2，…，N； 最大迭代次數，τmax；

Output：懸停位置的最優分配和排序 {Φ1，…Φn，…ΦN}；

(2)在上述分組的基礎上隨機打亂組合生成S個初始親代種群, {Π1,…,ΠS};

(3)結合式(11)和式(17)來評估每一個親代種群的適應度, 并選擇具有最大適應度值的種群作為Π*;

(4)whileτ=1;τ<τmax;do:

(5) 對 {Π1,…,ΠS} 執行包圍獵物, 泡沫網攻擊和搜索捕食以產生新的種群 {Π1′,…,ΠS′} 并進行優化; 該過程的詳細描述在3.1.1節中(3)～(6)

(7)If種群的最大適應度發生改變:

(8) 重新確定Π*;

(9) {Π1′,…,ΠS′} 替代 {Π1,…,ΠS},τ++;

(10)endwhile

4 模擬和實驗

4.1 模擬環境設置

在實驗部分，考慮了一個5000m×5000m的矩形區域，其中N臺UAVs從區域的中心出發，飛行高度分別為400 m，信道帶寬B=1 MHz，傳輸功率ρ=0.5 w，高斯白噪聲方差σ2=5×10-15， 信道增益β=ηlos(4πf/c)2，ηlos=1， 是LOS對應的衰減系數，f=2.4 GHz，c是光速。假設初始時UAV共收到了來自區域內隨機的30個任務節點的通信請求，如圖4所示，后續的實驗中任務節點規模將逐步擴大(30到100，每10個間隔)。懸停位置被視為虛擬救援任務節點，UAV的初始巡航速度Vf=15 m/s。所選的點集經過K-means處理前后如圖5所示，其中被調度的UAVs的數量，N=3。其它參數會在后續的模擬實驗中給出。實驗部分基于Windows10，i7-10875HCPU下的Python3.9實現。

圖4 初始通信節點分布情況

圖5 通信節點分組展示

4.2 懸停點排序及軌跡優化

圖6展示了使用K-WAOA算法對多無人機路徑優化的結果，此時使用轉折點I=1時來模擬多UAV飛行軌跡。其中轉折點是在連接兩點直線附近的區域內隨機產生，標記為方塊的虛線是算法最后一次迭代時的優化目標，它的適應度最大，為786 s，該虛線自身軌跡沒有發生重疊或交叉的現象，這符合路徑優化的特征，因此驗證了K-WAOA的可行性。圖7展示了在路徑規劃的基礎上，通過求解P2來進一步優化UAV的飛行軌跡的成果，此時標記為方塊的虛線所代表的適應度為778 s。通過觀察可知，優化過后的轉折點基本上都位于對應懸停點之間的線段上，這也驗證了3.2節最后的推斷。因此在實際工作中，可以通過增加相鄰懸停點之間轉折點的數量I來控制UAVs的飛行軌跡，從而獲得更好的工作效果。

圖6 優化過后的訪問通信節點排序

圖7 求解P2后對巡航路徑的進一步優化結果

4.3 速度和任務節點數量的影響

圖8反映了當無人機數量取N=3， 巡航速度Vf分別取15，12，9，6，3 (m/s)時，經求解P2優化飛行軌跡后UAVs工作周期的變化情況。其中索引為1，2，3的UAV所訪問的任務節點數分別為12，10，8。可以看出隨著速度的下降，每一臺UAV工作周期的縮短幅度越來越大，由此可以得出結論：將UAVs在相鄰兩個節點之間的飛行軌跡優化為一條直線的方法能夠有效降低其輔助的無線網絡的通信延遲，并且在UAVs使用低巡航速度的通信模型中更能發揮效果。

圖8 求解P2后所優化的巡航時間

事實上UAVs為保證任務的成功率，在工作周期內并不是一直維持著最大的推進功率，即最大的飛行速度Vmax會逐漸減小。而且上文已經驗證了最大航程速度VMR的存在，其數值低于Vmax， 所以在將VMR作為UAVs更加經濟的巡航速度之后，經求解P2對UAVs飛行軌跡的進一步優化會更加具有現實意義。同時可以看出隨著訪問節點數的增加，優化過后節省掉的工作周期也更大，這可以理解為UAVs訪問更多的任務節點就會產生更多冗余路徑，因此優化前后的差距也就更明顯。

4.4 多UAV軌跡規劃算法性能對比

本節比較了基于K-means的WOA與SA的混合優化算法(K-WAOA)與其它兩種元啟發式算法，即鯨魚算法(WOA)方案和模擬退火算法(SA)的性能。圖9和10顯示，所有UAVs軌跡中最長的飛行時間和運行周期隨著網絡規模的增加而增加。在3種軌跡優化方法中，由于沒有采用有效的方法來對目標軌跡進一步優化，WOA方法中的Tmax增長速度極快。隨著任務節點的增長，K-WAOA和SA仍然表現出優異的性能Tmax≤2000 s， 但結合兩張圖片可以看出，SA達到相對最好的計算結果所消耗的運行周期逐漸增長到自身的最大周期數，但計算結果依舊遜色于K-WAOA，SA逐漸成為一個低效率的算法。

圖9 UAVs在不同通信節點數量下的最大巡航時間

圖11中，當M=100時，通過改變UAVs的數量(N取3到6)來比較K-WAOA和SA之間的收斂速度。其中SA的迭代次數受冷卻過程對應控制參數的影響，為保證公平，將最大迭代次數設置為50。

圖11 算法在不同數量的UAVs下的性能展示

通過觀察可知K-WAOA相對SA總是擁有用時較低的起點，這是因為K-means可以為算法提供更加優秀的初始親代種群。同時，盡管M的值在變換，K-WAOA總是能夠在限定的50個周期內相對平穩地收斂到最優的結果，而趨勢線顯示SA的收斂速度則會隨著M值的增加而減小。

5 結束語

本文研究了最小化由多UAVs支持的數據傳輸模型的通信延遲，將優化問題分為任務節點的分組、訪問排序和飛行軌跡的轉折點求解共3個子問題，并提出了一種元啟發式算法K-WAOA來實現優化目標。最后通過各種實驗方法驗證了K-WAOA相比傳統算法能夠更加快速的收斂到最優解，它是一種穩定且高效的算法。

在未來的研究工作中，可以通過改變通信方式來進一步優化UAVs的性能。例如，將一對一通信方式改變為一對多甚至多對多的通信方式，此時懸停點位置的確定將是一個復雜的問題，同時UAVs還需要使用合適的任務調度策略來滿足系統吞吐量最大化的要求。