基于Voronoi圖-麻雀算法的中繼無人機(jī)任務(wù)規(guī)劃

譚 威， 胡永江， 張小孟， 趙月飛， 李文廣

(1.陸軍工程大學(xué)石家莊校區(qū)，石家莊 050000； 2.中國人民解放軍31700部隊，遼寧 遼陽 111000)

0 引言

復(fù)雜的戰(zhàn)場環(huán)境中，戰(zhàn)機(jī)稍縱即逝，因此在完成“情報偵察-摧毀打擊”任務(wù)時，就需要快速銜接好偵察無人機(jī)(Surveillance UAV，SUAV)、打擊無人機(jī)(Combat UAV，CUAV)及地面控制站(Ground Control Station,GCS)，實(shí)現(xiàn)作戰(zhàn)節(jié)點(diǎn)間信息的及時交互[1-2]。在現(xiàn)代戰(zhàn)爭中，單無人機(jī)、單類型無人機(jī)作戰(zhàn)能力有限，且容易被敵方摧毀，因此多無人機(jī)協(xié)同作戰(zhàn)已成為趨勢。為有效擴(kuò)大多無人機(jī)作戰(zhàn)范圍，加強(qiáng)多無人機(jī)作戰(zhàn)能力，協(xié)調(diào)好空空、空地、地地作戰(zhàn)進(jìn)程，就需要信息情報交流，以整體戰(zhàn)場態(tài)勢為重點(diǎn)、通盤考慮戰(zhàn)場全局，利用高效的縱深情報，突出我方優(yōu)勢，擊敵劣勢，我方能夠相互依靠、相互支援、共同進(jìn)退，從而使得多無人機(jī)作戰(zhàn)發(fā)揮出“1+1>2”的作戰(zhàn)效能。

中繼無人機(jī)任務(wù)規(guī)劃指的是通過在作戰(zhàn)區(qū)域部署中繼無人機(jī)，作為各類型的無人機(jī)及無人機(jī)與地面控制站的信息交互中心，實(shí)現(xiàn)戰(zhàn)場空間內(nèi)多維作戰(zhàn)力量的實(shí)時通信[3-4]。任務(wù)規(guī)劃是多無人機(jī)相互協(xié)同完成任務(wù)的關(guān)鍵技術(shù)，主要分為任務(wù)分配和航跡規(guī)劃[5-7]。中繼無人機(jī)任務(wù)規(guī)劃需要根據(jù)中繼無人機(jī)與重點(diǎn)目標(biāo)的距離約束及地面測控站與無人機(jī)基地的位置信息，以部署最少中繼無人機(jī)數(shù)量及中繼無人機(jī)安全為目標(biāo)，完成中繼無人機(jī)任務(wù)分配及部署。

現(xiàn)階段，國內(nèi)外對中繼無人機(jī)部署問題已經(jīng)有了一定的研究。文獻(xiàn)[8]研究了戰(zhàn)場緊急情況下的全局通信問題，可有效部署中繼無人機(jī)通信節(jié)點(diǎn)并滿足戰(zhàn)場通信需求；文獻(xiàn)[9]提出了一種基于貪婪算法和粒子群算法的任務(wù)關(guān)鍵型構(gòu)建算法，該算法能通過將多個任務(wù)分配給一定數(shù)量的中繼無人機(jī)，從而確定中繼節(jié)點(diǎn)的位置，但在部署通信節(jié)點(diǎn)時，未考慮最少化中繼無人機(jī)數(shù)量和中繼無人機(jī)安全需求；文獻(xiàn)[10]研究了多速率通信系統(tǒng)中中繼節(jié)點(diǎn)的最佳位置，驗(yàn)證了根據(jù)地面節(jié)點(diǎn)與中繼無人機(jī)高度之間的距離，可以選擇比中心位置更好的位置來實(shí)現(xiàn)最大吞吐量；文獻(xiàn)[11]研究了中繼無人機(jī)充當(dāng)移動中繼節(jié)點(diǎn)的無人機(jī)部署問題，主要分析了系統(tǒng)的吞吐量最大化及無人機(jī)中繼網(wǎng)絡(luò)部署的可靠性；文獻(xiàn)[12]提出了一種中繼無人機(jī)快速部署策略，能夠得到最少中繼無人機(jī)節(jié)點(diǎn)的部署方案，但沒有結(jié)合戰(zhàn)場實(shí)際威脅，需要加強(qiáng)中繼無人機(jī)自身的安全防護(hù)。現(xiàn)有的規(guī)劃方法中，在構(gòu)建全局中繼通信網(wǎng)絡(luò)時，對中繼無人機(jī)安全部署方面研究不多，且求解精度有待提高。在實(shí)際戰(zhàn)場運(yùn)用時，應(yīng)注重中繼節(jié)點(diǎn)的安全部署并提高部署效率?，F(xiàn)有方法大多都是單地面控制站基地，在實(shí)際運(yùn)用中，控制站應(yīng)隨著戰(zhàn)場態(tài)勢有適當(dāng)?shù)淖兓?yīng)考慮備選地面控制站基地情況，注重結(jié)合戰(zhàn)場實(shí)際進(jìn)行中繼節(jié)點(diǎn)的安全部署問題。

本文主要研究了一種基于Voronoi圖-麻雀(Voronoi- Sparrow Search Algorithm，V-SSA)算法的中繼無人機(jī)安全有效的分配部署策略。為實(shí)現(xiàn)中繼無人機(jī)的科學(xué)部署，以最少中繼節(jié)點(diǎn)數(shù)量和距離重要目標(biāo)最遠(yuǎn)為目標(biāo)函數(shù)，建立最優(yōu)化模型，采用V-SSA算法來實(shí)現(xiàn)問題的求解，優(yōu)化調(diào)整中繼節(jié)點(diǎn)部署位置。仿真結(jié)果表明，V-SSA算法得到了滿足目標(biāo)函數(shù)的最優(yōu)中繼無人機(jī)部署方案，相比于V-GA算法和V-PSO算法，在性能上有了一定的提升。

1 中繼無人機(jī)安全部署建模

1.1 問題描述

在作戰(zhàn)區(qū)域內(nèi)，存在若干個敵目標(biāo)及敵雷達(dá)等威脅點(diǎn)，需要完成對敵目標(biāo)進(jìn)行先偵察、再精確打擊摧毀任務(wù)。而在執(zhí)行任務(wù)時，因?yàn)榇嬖谟行ㄐ啪嚯x限制，故需要有效、合理地部署通信中繼無人機(jī)進(jìn)行輔助通信，將地面控制站和整個作戰(zhàn)區(qū)域內(nèi)執(zhí)行任務(wù)的無人機(jī)進(jìn)行有效聯(lián)通。在圖1中展示了中繼無人機(jī)部署的任務(wù)場景。

圖1 任務(wù)場景圖Fig.1 Mission scenario graph

表1匯總了3類節(jié)點(diǎn)的相關(guān)信息。

表1 3類節(jié)點(diǎn)信息Table 1 Information of three types of nodes

本次任務(wù)可分為兩大類無人機(jī)，即中繼無人機(jī)(Relay Unmanned Aerial Vehicle，RUAV)和任務(wù)無人機(jī)(Mission UAV，MUAV)。主要有CUAV，SUAV，中繼無人機(jī)的通信半徑為d0，數(shù)量為NR。

本文所建立模型的前提及假設(shè)如下：1) 中繼無人機(jī)性能良好,均在航程內(nèi)飛行;2) 在假設(shè)的中繼范圍內(nèi)均認(rèn)為可以建立通信聯(lián)絡(luò)。

1.2 Voronoi圖

Voronoi圖[13-14]以幾何學(xué)方法為依據(jù)，能夠有效將地理信息中點(diǎn)對象和區(qū)域以拓?fù)浣Y(jié)構(gòu)表示出來。在中繼無人機(jī)領(lǐng)域應(yīng)用時，因其具有很好的全局規(guī)劃特性而被廣泛用于相關(guān)問題的求解，因此，本文采用Voronoi圖來生成任務(wù)環(huán)境空間。中繼無人機(jī)的位置被限制于Voronoi圖的邊界上，以降低問題復(fù)雜度，提高求解速度和求解精度。

采用Voronoi圖后可以獲得點(diǎn)與邊的集合，這些集合可以被表示為

(1)

式中：T為目標(biāo)集合;P為威脅源的集合;V為Voronoi圖的頂點(diǎn)集合；E為Voronoi圖邊集。從V中的節(jié)點(diǎn)指向T中的節(jié)點(diǎn)，表示所有可能的路徑。

1.3 決策變量

本文中的決策變量為NR架無人機(jī)中，表示每架無人機(jī)是否被部署的Zi，Zi∈{1,0}，其部署的位置為(xi,yi)，其中，i∈{1,2，…，NR}，中繼無人機(jī)所在的節(jié)點(diǎn)為Y={Y1,Y2，…，YNR}。

1.4 約束條件

設(shè)本文考慮的有以下約束。

無人機(jī)僅能部署在Voronoi圖生成的邊上。對于第i架中繼無人機(jī)，有且僅能部署在一條邊上。令A(yù)i j表示第i架中繼無人機(jī)是否部署在第j條邊上，則應(yīng)滿足約束

(2)

最多僅有N架中繼無人機(jī)被使用，即

(3)

滿足中繼無人機(jī)的通信范圍限制，為確保各中繼無人機(jī)能夠中繼通信，直接相互聯(lián)通的通信中繼節(jié)點(diǎn)之間的距離應(yīng)符合

(4)

式中：d(Yi,Yj)為節(jié)點(diǎn)i和j之間的歐氏距離;d0是無人機(jī)的覆蓋范圍，即通信半徑。

為確保無人機(jī)飛行的安全，無人機(jī)之間需限定一定的安全間隔，所以，中繼節(jié)點(diǎn)之間的最小安全距離為

mind(Yi,Yj)≥dsf

(5)

式中,dsf為無人機(jī)間的最小安全距離，安全距離dsf必須遠(yuǎn)小于d0。

當(dāng)然，重要目標(biāo)點(diǎn)必須在覆蓋中繼無人機(jī)的通信范圍內(nèi)，即

mind(Y,Pi)≤d0。

(6)

1.5 目標(biāo)函數(shù)

在使用無人機(jī)作戰(zhàn)時，通過部署最佳的無人機(jī)數(shù)目，降低無人機(jī)的總通信能耗，單次任務(wù)中出動的無人機(jī)數(shù)量越少，行動的效費(fèi)比就越高。本文的中繼無人機(jī)部署模型有兩個目標(biāo)，分別為以中繼無人機(jī)數(shù)量最少以及距離重點(diǎn)目標(biāo)的距離最遠(yuǎn)(即總距離最大)。

為了保證安全，中繼無人機(jī)需要在覆蓋重要目標(biāo)的同時使自身與目標(biāo)的距離最遠(yuǎn)。該目標(biāo)J1可以表示為

(7)

式中，W(Yi,Pj)表示無人機(jī)i是否覆蓋了節(jié)點(diǎn)j，如是則為1，否則為0。此外，有效中繼無人機(jī)數(shù)量n可表示為

(8)

綜上所述，結(jié)合有效通信距離約束、安全距離約束等條件，基于最少中繼節(jié)點(diǎn)的部署模型的目標(biāo)函數(shù)為

(9)

其約束條件為

(10)

2 Voronoi圖-麻雀算法基本原理

2.1 基本麻雀搜索算法

麻雀搜索算法(SSA)[15-16]由薛建凱于2020年提出，具有收斂速度快、調(diào)整參數(shù)少等特點(diǎn)。

設(shè)麻雀集合矩陣為

(11)

式中:N是麻雀的規(guī)模；i=1,2,…,N;d是變量的維數(shù)。

麻雀的適應(yīng)度值矩陣表示為

Fx=(f(x1)f(x2)…f(xN))T

(12)

f(xi)=(f(xi,1)f(xi,2)…f(xi,d))

(13)

其中，F(xiàn)x為個體的適應(yīng)度值。適應(yīng)度值更優(yōu)的麻雀能夠率先得到食物，并作為發(fā)現(xiàn)者，引領(lǐng)其他麻雀靠近食物源。發(fā)現(xiàn)者位置的更新算式為

(14)

(15)

偵察預(yù)警行為：種群覓食時，會選取部分麻雀負(fù)責(zé)偵察，隨機(jī)選取SSD(一般取10%～20%)只麻雀進(jìn)行預(yù)警行為。其位置更新算式為

(16)

2.2 基于Voronoi圖的編碼方式

Voronoi圖能夠有效地將地理信息中的點(diǎn)、對象和區(qū)域以拓?fù)浣Y(jié)構(gòu)表示出來，并能通過這些拓?fù)潢P(guān)系表示自然語言中的定性關(guān)系和模糊地理信息[17]。在通過衛(wèi)星確定了危險區(qū)域后，根據(jù)危險區(qū)域，在平面內(nèi)就可以劃分成距離各個點(diǎn)或者實(shí)體一定距離的凸網(wǎng)，其距離可以根據(jù)具體情況設(shè)置。這個凸網(wǎng)稱為Voronoi圖，Voronoi圖各邊即為UAV可通行的安全路徑。

本文編碼方式為實(shí)數(shù)編碼，由兩部分構(gòu)成，分別是Voronoi圖生成的每個可通行路徑的優(yōu)先級Pr以及中繼點(diǎn)位置系數(shù)R，即

(17)

式中，NP為可通行路徑的數(shù)量。該編碼方式可以將約束的處理從初始解生成，轉(zhuǎn)移到解碼流程中，避免在新解生成時的約束處理以及錯誤修正。這種方法可以有效降低算法設(shè)計和運(yùn)行的復(fù)雜度，同時避免錯誤修正時造成的信息損失。

2.3 基于Voronoi圖的解碼方式

由于本文并未直接決策變量作為編碼，需要通過解碼，將編碼轉(zhuǎn)化為決策變量并計算適應(yīng)度函數(shù)值。解碼流程如下。

1) 根據(jù)優(yōu)先級，將所有Voronoi圖生成的每個可通行路徑進(jìn)行排序，按照排序后的順序S依次操作。

2) 令i=1。

3) 對于第S(i)條子路徑，設(shè)當(dāng)前子路徑的兩個端點(diǎn)為N1，N2，則中繼點(diǎn)位置為

Nz=R(N1-N2)+N2

(18)

4) 計算當(dāng)前中繼點(diǎn)和其他目標(biāo)點(diǎn)的距離，判斷其可覆蓋的目標(biāo)點(diǎn)數(shù)量。

5) 如果新設(shè)中繼點(diǎn)在當(dāng)前位置，可以增加可覆蓋的目標(biāo)點(diǎn)數(shù)量，則該中繼點(diǎn)位置保存。

6) 如果所有目標(biāo)點(diǎn)均被覆蓋，則前往7)，否則i=i+1，并前往3)。

7) 計算目標(biāo)函數(shù)。

2.4 算法流程

本文所研究的V-SSA算法流程如圖2所示。

圖2 V-SSA算法流程圖Fig.2 Flow chart of V-SSA algorithm

1) 初始化種群參數(shù)，如種群數(shù)量N，最大迭代次數(shù)，發(fā)現(xiàn)者比例PPD，偵察者比例SSD等。

2) 求解個體適應(yīng)度值，從中選取最優(yōu)、最差適應(yīng)度值，并得到其所對應(yīng)的位置。

3) 在適應(yīng)度值較優(yōu)的麻雀中，選擇部分麻雀作為發(fā)現(xiàn)者，并按照式(14)更新位置。

4) 剩余麻雀作為跟隨者，并按照式(15)更新位置。

5) 隨機(jī)選擇部分麻雀作為偵察者，并按式(16)進(jìn)行位置更新。

6) 判斷，若滿足結(jié)束條件，則進(jìn)行7)，否則跳轉(zhuǎn)到2)。

7) 結(jié)束，輸出最優(yōu)結(jié)果。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)平臺為AMD Ryzen 5 3500U/8 GiB/64位Windows10操作系統(tǒng)的華為榮耀MagicBook2019筆記本電腦。編程工具為MatlabR2016b(64位)。

3.1 仿真參數(shù)設(shè)置

仿真實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置Table 2 Experimental parameters setting

3.2 仿真內(nèi)容及結(jié)果分析

為了驗(yàn)證本文所提算法，設(shè)置了2個仿真實(shí)驗(yàn)。實(shí)驗(yàn)1主要驗(yàn)證本文算法有效性，能否得到覆蓋目標(biāo)的中繼無人機(jī)部署方案；實(shí)驗(yàn)2進(jìn)行對比實(shí)驗(yàn)，驗(yàn)證本文算法的性能情況。

3.2.1 實(shí)驗(yàn)1

本文假設(shè)有3個重要目標(biāo)、8個安全陣地(中繼無人機(jī)基地、GCS基地)、57個敵威脅點(diǎn)，均需要被中繼無人機(jī)通信網(wǎng)絡(luò)覆蓋，以便執(zhí)行任務(wù)時各任務(wù)小組互聯(lián)互通。圖3中仿真了中繼節(jié)點(diǎn)部署情況。表3中列出需要被通信覆蓋的位置坐標(biāo)，其中，類型1為重要目標(biāo)，類型2為安全陣地，類型3為敵威脅點(diǎn)。

圖3 中繼節(jié)點(diǎn)部署圖Fig.3 Deployment of relay nodes

表3 任務(wù)節(jié)點(diǎn)位置坐標(biāo)Table 3 Coordinates of mission nodes

現(xiàn)將實(shí)驗(yàn)結(jié)果分析如下。

1) 由圖3可知，3個重要目標(biāo)、8個安全陣地(中繼無人機(jī)基地、GCS基地)、57個敵威脅點(diǎn)都在RUAV的有效通信覆蓋范圍內(nèi)，并且每個RUAV節(jié)點(diǎn)都可以直接或間接地與GCS及備用GCS基地進(jìn)行數(shù)據(jù)鏈路通信，說明了本文算法的有效性。

2) 利用本文的SSA算法能夠?qū)χ欣^節(jié)點(diǎn)的安全部署問題進(jìn)行有效求解，并可得到最小中繼無人機(jī)的數(shù)量及其對應(yīng)位置信息，能夠滿足戰(zhàn)場全局通信要求，說明了本文算法的可行性。

3.2.2 實(shí)驗(yàn)2

在相同目標(biāo)和測控系統(tǒng)屬性的情況下，對比V-GA算法、V-PSO算法和V-SSA算法中繼節(jié)點(diǎn)部署情況。在V-PSO算法中，將種群規(guī)模設(shè)為100，最大迭代次數(shù)設(shè)為100，認(rèn)知參數(shù)和社會參數(shù)分別設(shè)0.7和1.4；V-GA算法中，將種群規(guī)模設(shè)為100，最大迭代次數(shù)設(shè)為100，交叉和變異概率分別設(shè)0.85和0.2。

假設(shè)作戰(zhàn)區(qū)域內(nèi)有68個需要通聯(lián)的不同類型目標(biāo)(如表3所示)，在相同目標(biāo)規(guī)模下，用V-GA算法、V-PSO算法和V-SSA算法各進(jìn)行仿真實(shí)驗(yàn)100次，記錄中繼節(jié)點(diǎn)數(shù)量并取其平均值，統(tǒng)計結(jié)果如表4所示，并各記錄一次中繼節(jié)點(diǎn)部署結(jié)果，分別見圖4～6。

表4 中繼節(jié)點(diǎn)平均數(shù)量表Table 4 Average number of relay nodes

圖4 V-GA算法中繼節(jié)點(diǎn)部署圖Fig.4 Relay node deployment diagram of V-GA algorithm

圖5 V-PSO算法中繼節(jié)點(diǎn)部署圖Fig.5 Relay node deployment diagram of V-PSO algorithm

圖6 V-SSA算法中繼節(jié)點(diǎn)部署圖Fig.6 Relay node deployment diagram of V-SSA algorithm

結(jié)果分析如下。

1) 由圖4～6可得，所有的TUAV節(jié)點(diǎn)都在RUAV節(jié)點(diǎn)的有效通信覆蓋范圍之內(nèi)，并且每個RUAV節(jié)點(diǎn)都可以直接或通過別的RUAV節(jié)點(diǎn)與GCS進(jìn)行數(shù)據(jù)鏈路通信，說明3種算法都能夠建立有效的鏈路通信。

2) 由表4可知:在建立有效全局通信網(wǎng)絡(luò)的情況下，V-GA算法求解得到的中繼無人機(jī)數(shù)量平均為13，V-PSO算法求解得到的中繼無人機(jī)數(shù)量為12，V-SSA算法求解得到的中繼無人機(jī)數(shù)量為11;在重點(diǎn)目標(biāo)總距離上，V-SSA算法為957.614 7 km，比V-GA算法提升了7%，比V-PSO算法提升了4%，說明V-SSA算法得到的中繼無人機(jī)部署位置離重點(diǎn)目標(biāo)更遠(yuǎn)，受到的威脅相對更小，中繼無人機(jī)安全性更高。

4 總結(jié)

本文提出了一種基于V-SSA算法的中繼無人機(jī)有效安全部署策略，并驗(yàn)證了所提出的航跡規(guī)劃算法能夠有效解決中繼無人機(jī)部署方案無法滿足最少數(shù)量要求及中繼無人機(jī)安全性等問題，主要得到以下結(jié)論：本文提出的V-SSA算法實(shí)現(xiàn)了節(jié)點(diǎn)間可行鏈路的有效搜索，能夠得到覆蓋所有目標(biāo)的中繼無人機(jī)部署方案；V-SSA算法相比于V-GA算法和V-PSO算法解得的部署方案中繼無人機(jī)數(shù)量最少，距離重點(diǎn)目標(biāo)的距離最遠(yuǎn)，中繼無人機(jī)安全性更高。