賈哲松，王高才

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

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

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

本文主要貢獻(xiàn)總結(jié)如下：

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

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

1 相關(guān)研究

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

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

2 系統(tǒng)模型

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

圖1 多UAV通信系統(tǒng)模型

圖2 多UAV通信系統(tǒng)水平投影

2.1 相關(guān)數(shù)學(xué)模型

2.1.1 信息傳輸模型

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

(1)

其中，x′n(t)，y′n(t)， 分別表示xn(t)，yn(t) 關(guān)于t的一階導(dǎo)數(shù)，tn，m，tn，m-1分別表示n從自身巡航路線第m個(gè)以及從第m-1個(gè)節(jié)點(diǎn)出發(fā)的時(shí)刻。

在UAV和設(shè)備共享同一信道的一對(duì)多場(chǎng)景中，干擾模型始終是一個(gè)重要問題。在文獻(xiàn)[16]中，UAV通過時(shí)分多址(TDMA)從其相關(guān)節(jié)點(diǎn)收集數(shù)據(jù)，其中每個(gè)傳感器節(jié)點(diǎn)僅在計(jì)劃進(jìn)行數(shù)據(jù)傳輸時(shí)喚醒。在這種情況下，UAV順序地與通信節(jié)點(diǎn)，并且節(jié)點(diǎn)之間不存在干擾。此外，文獻(xiàn)[17]中研究了支持無人機(jī)的正交頻分多址(OFDMA)網(wǎng)絡(luò)，其中無人機(jī)作為移動(dòng)基站(BS)進(jìn)行調(diào)度，為一組地面用戶提供服務(wù)。除去信號(hào)干擾外，一對(duì)多和多對(duì)多傳輸模式還會(huì)面臨信道選擇，任務(wù)調(diào)度等問題[18，19]，這不是討論的范圍。因?yàn)檠芯恐胁捎靡粚?duì)一傳輸模式，即UAVs在同一時(shí)刻僅為一個(gè)任務(wù)節(jié)點(diǎn)提供服務(wù)，n對(duì)第m個(gè)任務(wù)節(jié)點(diǎn)的傳輸速率公式為

(2)

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

(3)

其中

(4)

2.1.2 采集數(shù)據(jù)的延遲模型

在t=0時(shí)刻n從起止點(diǎn)出發(fā)，按順序?yàn)橹付ㄓ脩籼峁┩ㄐ欧?wù)，最終在t=Tn時(shí)刻返回起止點(diǎn)。結(jié)合式(4)可知，n在t=tn，m-1時(shí)開始負(fù)責(zé)收集任務(wù)節(jié)點(diǎn)m的數(shù)據(jù)，那么m的數(shù)據(jù)通信延遲公式為

(5)

2.1.3 速度模型

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

(6)

其中，P0和Pi是兩個(gè)常數(shù)，表示懸停狀態(tài)下的葉片剖面功率和感應(yīng)功率；Utip表示轉(zhuǎn)子的尖端速度；v0為懸停狀態(tài)下的平均旋翼誘導(dǎo)速度，d0和s分別為機(jī)身阻力比和旋翼固體度，p和A表示空氣密度和旋翼盤面積[20]。

UAV存在兩種基本類型的速度，即最大續(xù)航速度VME和最大航程速度VMR。VME確保在移動(dòng)期間移動(dòng)功率最小。VMR可以實(shí)現(xiàn)UAV的最長行駛距離，兩者與UAV的最大速度Vmax的關(guān)系為：VME

(7)

(8)

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

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

(9)

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

2.2 問題分解和重組

2.2.1 UAV巡航軌跡重構(gòu)

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

圖3 使用轉(zhuǎn)折點(diǎn)優(yōu)化UAV飛行軌跡示例

這里補(bǔ)充定義n所經(jīng)歷的懸停點(diǎn)的坐標(biāo)可表示為 (xn，m，yn，m)， 在引入轉(zhuǎn)折點(diǎn)之后為了方便歸類，將懸停點(diǎn)改寫為 (xn，m，0，yn，m，0)， 那么n的懸停點(diǎn)集合、轉(zhuǎn)折點(diǎ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起止點(diǎn)表述為 (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條轉(zhuǎn)折線的長度公式為

(10)

那么n一個(gè)工作周期的計(jì)算公式

(11)

(12)

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

(13)

可知n在工作周期對(duì)節(jié)點(diǎn)m的數(shù)據(jù)收集量公式可改寫為

(14)

其中

2.2.2 通信延遲

最小化所有任務(wù)的通信延遲可表述為min{T1，…，TM}， 假設(shè)它們對(duì)應(yīng)的大小關(guān)系為：TM≥，…，≥T1事實(shí)上必定存在n′遵從如下的等式關(guān)系

(15)

可知在引入轉(zhuǎn)折點(diǎn)來量化UAV的單軌跡之后，通信延遲的優(yōu)化實(shí)際上涉及到了任務(wù)節(jié)點(diǎn)的分配、排序以及相鄰節(jié)點(diǎn)之間轉(zhuǎn)折點(diǎn)的求解，共計(jì)3個(gè)問題，因此接下來可以統(tǒng)一對(duì)其進(jìn)行數(shù)學(xué)建模。

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

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包含了起止點(diǎn)，而UAVs在返航過程中不再收集數(shù)據(jù)，所以e不包含起止點(diǎn)。Q′e則表示需要在任務(wù)節(jié)點(diǎn)e收集到的最小的數(shù)據(jù)量。(16b)，(16c)表示每個(gè)UAV只訪問一次起止點(diǎn)，(16d)，(16e)，(16f)表示每個(gè)懸停點(diǎn)只允許一臺(tái)UAV到達(dá)和離開一次，(16g)是MTZ(miller-tucker-zemlin)約束，用來消除子路徑，(16h)表明優(yōu)化目標(biāo)是N個(gè)UAVs中用時(shí)最長的個(gè)體。

這是一個(gè)MTSP的變種，具有很強(qiáng)的NP-hard性，它表明系統(tǒng)滿足每個(gè)任務(wù)節(jié)點(diǎn)的數(shù)據(jù)收集需求的同時(shí)，還需要最小化UAVs的最大工作周期。

3 基于模因算法框架的鯨魚退火優(yōu)化算法

多無人機(jī)軌跡規(guī)劃問題面臨著兩個(gè)難點(diǎn)，一個(gè)是任務(wù)節(jié)點(diǎn)的分組，另一個(gè)就是無人機(jī)軌跡中的懸停點(diǎn)排序優(yōu)化，同時(shí)還需選擇合適的轉(zhuǎn)折點(diǎn)來控制無人機(jī)的飛行軌跡，以此滿足每一個(gè)節(jié)點(diǎn)的通信要求，接下來將圍繞這些問題來探討優(yōu)化方法。

3.1 多無人機(jī)的任務(wù)分組及通信節(jié)點(diǎn)排序

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

3.1.1 鯨魚優(yōu)化算法

(2)適應(yīng)度函數(shù)step3 and step6：算法利用適應(yīng)度值來評(píng)價(jià)種群，以及淘汰沒有希望的種群。在這里的優(yōu)化目標(biāo)是一個(gè)種群中工作周期最長的任務(wù)分組，因此利用式(11)構(gòu)建適應(yīng)度函數(shù)，首先計(jì)算出種群內(nèi)不同分組所需的飛行時(shí)間Tn， 最后選取其中而最大值作為該種群的適應(yīng)度值，則種群的適應(yīng)度公式為

(17)

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

(18)

其中

(19)

C1=2γ2

(20)

A1=2αγ1-α

(21)

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

(22)

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

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

3.1.2 SA(simulated annealing algorithm)

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

3.2 UAV飛行軌跡優(yōu)化

經(jīng)由P1所得結(jié)果T′max需滿足如下條件

(23)

其中

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

很明顯這是一個(gè)非線性優(yōu)化問題，主要目的為尋找最優(yōu)的轉(zhuǎn)折點(diǎn)及懸停時(shí)間，使得UAV既能滿足數(shù)據(jù)收集的要求，又能使得UAV為目標(biāo)節(jié)點(diǎn)提供服務(wù)的耗時(shí)最短。P2的求解難度相對(duì)簡(jiǎn)單，接下來利用式(14)來提前研究最優(yōu)解的可能取值。

負(fù)責(zé)通信服務(wù)的UAV的最優(yōu)工作方式，是以額定的速度在相鄰懸停點(diǎn)之間沿直線行駛，并最終在懸停點(diǎn)上方完成對(duì)應(yīng)任務(wù)節(jié)點(diǎn)剩余的通信任務(wù)。

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

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

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

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

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

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

(5) 對(duì) {Π1,…,ΠS} 執(zhí)行包圍獵物, 泡沫網(wǎng)攻擊和搜索捕食以產(chǎn)生新的種群 {Π1′,…,ΠS′} 并進(jìn)行優(yōu)化; 該過程的詳細(xì)描述在3.1.1節(jié)中(3)～(6)

(7)If種群的最大適應(yīng)度發(fā)生改變:

(8) 重新確定Π*;

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

(10)endwhile

4 模擬和實(shí)驗(yàn)

4.1 模擬環(huán)境設(shè)置

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

圖4 初始通信節(jié)點(diǎn)分布情況

圖5 通信節(jié)點(diǎn)分組展示

4.2 懸停點(diǎn)排序及軌跡優(yōu)化

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

圖6 優(yōu)化過后的訪問通信節(jié)點(diǎn)排序

圖7 求解P2后對(duì)巡航路徑的進(jìn)一步優(yōu)化結(jié)果

4.3 速度和任務(wù)節(jié)點(diǎn)數(shù)量的影響

圖8反映了當(dāng)無人機(jī)數(shù)量取N=3， 巡航速度Vf分別取15，12，9，6，3 (m/s)時(shí)，經(jīng)求解P2優(yōu)化飛行軌跡后UAVs工作周期的變化情況。其中索引為1，2，3的UAV所訪問的任務(wù)節(jié)點(diǎn)數(shù)分別為12，10，8?？梢钥闯鲭S著速度的下降，每一臺(tái)UAV工作周期的縮短幅度越來越大，由此可以得出結(jié)論：將UAVs在相鄰兩個(gè)節(jié)點(diǎn)之間的飛行軌跡優(yōu)化為一條直線的方法能夠有效降低其輔助的無線網(wǎng)絡(luò)的通信延遲，并且在UAVs使用低巡航速度的通信模型中更能發(fā)揮效果。

圖8 求解P2后所優(yōu)化的巡航時(shí)間

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

4.4 多UAV軌跡規(guī)劃算法性能對(duì)比

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

圖9 UAVs在不同通信節(jié)點(diǎn)數(shù)量下的最大巡航時(shí)間

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

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

通過觀察可知K-WAOA相對(duì)SA總是擁有用時(shí)較低的起點(diǎn)，這是因?yàn)镵-means可以為算法提供更加優(yōu)秀的初始親代種群。同時(shí)，盡管M的值在變換，K-WAOA總是能夠在限定的50個(gè)周期內(nèi)相對(duì)平穩(wěn)地收斂到最優(yōu)的結(jié)果，而趨勢(shì)線顯示SA的收斂速度則會(huì)隨著M值的增加而減小。

5 結(jié)束語

本文研究了最小化由多UAVs支持的數(shù)據(jù)傳輸模型的通信延遲，將優(yōu)化問題分為任務(wù)節(jié)點(diǎn)的分組、訪問排序和飛行軌跡的轉(zhuǎn)折點(diǎn)求解共3個(gè)子問題，并提出了一種元啟發(fā)式算法K-WAOA來實(shí)現(xiàn)優(yōu)化目標(biāo)。最后通過各種實(shí)驗(yàn)方法驗(yàn)證了K-WAOA相比傳統(tǒng)算法能夠更加快速的收斂到最優(yōu)解，它是一種穩(wěn)定且高效的算法。

在未來的研究工作中，可以通過改變通信方式來進(jìn)一步優(yōu)化UAVs的性能。例如，將一對(duì)一通信方式改變?yōu)橐粚?duì)多甚至多對(duì)多的通信方式，此時(shí)懸停點(diǎn)位置的確定將是一個(gè)復(fù)雜的問題，同時(shí)UAVs還需要使用合適的任務(wù)調(diào)度策略來滿足系統(tǒng)吞吐量最大化的要求。