張小孟 楊森 宋曉 胡永江 李文廣

(1. 陸軍工程大學 無人機工程系, 石家莊 050003;2. 北京航空航天大學 網(wǎng)絡空間安全學院, 北京 100083; 3. 中國人民解放軍 31700 部隊, 遼陽 111000)

隨著無人作戰(zhàn)區(qū)域范圍的擴展,單架無人機的有效通信范圍逐漸成為制約其作戰(zhàn)半徑的主要矛盾。 通過構建中繼無人機網(wǎng)絡,進行數(shù)據(jù)鏈路的“接力” 傳輸,可有效擴展無人機的作戰(zhàn)半徑[1-3]。 中繼無人機用作無線通信的中繼節(jié)點,使得任務機在一定距離下仍可實時與地面測控系統(tǒng)保持信息交互[4-5]。

中繼無人機部署問題就是在作戰(zhàn)目標和地面測控系統(tǒng)位置已知的條件下,如何根據(jù)無人機作戰(zhàn)鏈路需求及中繼無人機的性能,以最少數(shù)量的中繼無人機完成整個無人機通信鏈路中繼節(jié)點的設置問題[6-9]。 文獻[10]針對中繼無人機部署問題,建立了中繼節(jié)點布置問題模型,提出了一種兩階段多項式中繼節(jié)點布置算法,可有效滿足戰(zhàn)場無人機中繼通信需求。 但是該算法的中繼節(jié)點布置范圍只能在等間距的離散位置點上選取,不具有普適性。 文獻[11-12]采用了粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法將一定數(shù)量的中繼無人機分配給多個任務,以此來確定中繼無人機的位置,這只能解決在中繼無人機數(shù)量一定的情況下,其有效部署的問題,但無法以最少的中繼無人機數(shù)量來有效完成中繼無人機的部署。 文獻[13]將中繼部署問題歸結為單源最短路徑問題,在考慮到中繼節(jié)點數(shù)量有限的情況下,使用了一種基于Bellman-ford 算法的AHOP 算法,可以得出最小化路徑代價和跳數(shù)的Pareto 解。 文獻[14]提出了一種雙層中繼節(jié)點布局問題模型,利用基于最小生成樹的多項式時間近似算法,來求解最少數(shù)量中繼節(jié)點的部署位置。

上述方法雖然在一定程度上能夠解決中繼無人機的部署問題,但仍存在以下不足:在求解前要求預先對任務區(qū)域進行離散化處理,但離散化程度對于求解效率及求解精度均有一定影響;以最小生成樹的方式求解中繼無人機部署問題,可有效約束路徑代價的總和最小,但僅考慮在邊上部署中繼節(jié)點,求解結果存在一定冗余。

針對以上問題,本文提出了一種中繼無人機快速部署策略。 通過建立基于最少中繼節(jié)點的部署模型和采用基于快速深度優(yōu)先搜索的人工蜂群算法,來實現(xiàn)問題的求解。 在模型求解過程中,不需要預先對任務區(qū)域進行離散化,而是在可行域內隨機生成可以滿足連通性的節(jié)點,以最少中繼節(jié)點數(shù)量為目標函數(shù),使用群智能算法,優(yōu)化調整有效節(jié)點部署位置,得到最少中繼無人機部署方案。

1 基于最少中繼節(jié)點的部署模型

1.1 問題描述

在無人機中繼通信網(wǎng)絡中地面測控系統(tǒng)(Ground Control System,GCS)、待執(zhí)行任務無人機(Task UAV,TU)和中繼無人機(Relay UAV,RU)均視為無人機中繼通信網(wǎng)絡中的通信節(jié)點,且假設所有的節(jié)點均處于同樣的海拔高度。 用G=g表示地面測控系統(tǒng)(g為無人機的地面控制系統(tǒng)的位置)、集合T={t1,t2,…,tNt}表示待執(zhí)行任務無人機、集合R={r1,r2,…,rNr}表示中繼無人機。其中Nt為待執(zhí)行任務機數(shù)量,Nr為中繼無人機數(shù)量。 對應可將GCS、RU 和TU 的位置以集合的形式表示為

式中:xv∈R2為節(jié)點v的位置。

由于GCS 的位置是已知固定的,每個TU 的位置是根據(jù)作戰(zhàn)目標確定的,所以中繼節(jié)點的部署位置可根據(jù)GCS、TU 的位置信息來進行合理設計。 TU 與GCS 的通信模式是端到端通信,假設將一個可行的無人機中繼網(wǎng)絡視為一個數(shù)學函數(shù),以所有節(jié)點的位置信息為輸入,每個TU 與GCS 之間的一組中繼鏈路節(jié)點為輸出,則這個中繼網(wǎng)絡可表示為

1.2 約束條件

式中:dsf為防止無人機之間碰撞的最小安全距離。 安全距離dsf必須遠小于通信距離d0,并且假定TU 之間的距離是保持安全的。

1.3 目標函數(shù)

在戰(zhàn)場環(huán)境中,無人機數(shù)量越多,越容易被敵雷達探測到,將會增加無人機被敵打擊的概率,進而可能會影響整體作戰(zhàn)計劃。 因此為了盡可能的降低被敵雷達探測到的概率,應盡可能的減少中繼無人機的數(shù)量,來保證更安全地完成作戰(zhàn)任務。同時,在空域中,無人機的數(shù)量越少,也越有利于無人機的飛行安全。 所以,對于中繼無人機的部署要在滿足通信要求和安全性能的前提下,以最少數(shù)量的中繼無人機來保證所有任務機與測控系統(tǒng)可進行實時通信。

由此,有效中繼無人機數(shù)量可表示為

式中:f為中繼網(wǎng)絡中無人機的計數(shù)函數(shù)。

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

式中:X?R2為無人機的二維可展開空間。

2 快速深度優(yōu)先搜索

深度優(yōu)先搜索算法[15](Depth First Search,DFS)屬于圖算法的一種,是一種針對圖和樹遍歷的經(jīng)典算法,利用DFS 算法可以產(chǎn)生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多圖論問題。 但是經(jīng)典的DFS 算法存在隨著節(jié)點數(shù)量的增加,其計算復雜度成階次提高的缺點,這將嚴重影響算法的求解效率。

對于在任務空間中事先隨機生成一定數(shù)量滿足連通性的中繼節(jié)點RU 的位置中,如何快速找到測控系統(tǒng)GCS 通過中繼節(jié)點RU 與所有TU 節(jié)點之間的可行鏈路問題,就屬于圖論問題。 為有效保證求解效率,對DFS 算法的搜索方式進行了優(yōu)化,提出了一種快速深度優(yōu)先搜索(Rapidly Depth First Search,RDFS)算法,即在每次搜索節(jié)點TU 的過程中,搜索到一條可行路徑便結束當前搜索,因為不必遍歷所有的節(jié)點,去尋找其他較短鏈路,所以搜索過程耗時明顯減少,尤其是在節(jié)點數(shù)目較多的情況下,平均時間復雜度可以減少為原來的一半。

在節(jié)點間搜索可行鏈路時,將依據(jù)以下步驟:

步驟1 將GCS 作為第一個被訪問的頂點,TU 作為未被訪問過的頂點。

步驟2 對訪問過的頂點作已訪問過的標志。

步驟3 依次從頂點未被訪問過的第1, 2,…,n個鄰接頂點出發(fā),對其進行深度優(yōu)先搜索,至訪問到TU 即停止訪問,記錄訪問鏈路,無需再繼續(xù)訪問其余頂點。

步驟4 如果頂點TU 未被訪問,說明GCS和TU 沒有可行鏈路,則結束。

通過以上優(yōu)化的搜索方式,可有效降低算法求解的時間復雜度,同時仍能找到可行解。

3 基于RDFS 的人工蜂群算法

人工蜂群(Artificial Bee Colony, ABC)算法是由Karaboga 于2005 年提出的一種基于群智能的全局優(yōu)化算法[16]。 其通過不同分工的蜜蜂間的交流與協(xié)作實現(xiàn)群體智能,具有參數(shù)設置少、收斂速度快且收斂精度高等優(yōu)點。 但同樣在求解中繼無人機部署問題時,受限于節(jié)點規(guī)模,求解效率不高。 所以,采用一種基于RDFS 的人工蜂群(RDFS-ABC)算法來實現(xiàn)中繼無人機部署問題的快速求解。

3.1 種群初始化

種群初始化即初始化蜜源位置,每一個蜜源位置代表一個可行解。 對于中繼無人機的部署問題,可行解即代表一組中繼節(jié)點,且該組中繼節(jié)點滿足安全性和連通性的要求。

首先,在任務區(qū)域內隨機生成D個位置點作為中繼無人機RU 的節(jié)點位置,D為蜜源維度。然后,使用RDFS 算法判斷中繼節(jié)點的可行性,即所有任務節(jié)點TU 可否通過中繼節(jié)點搜索到測控系統(tǒng)節(jié)點GCS 間的可行通信鏈路。 在每次搜索過程中,假設測控系統(tǒng)節(jié)點的序號為1,而任務節(jié)點的序號為2,其余中繼節(jié)點的序號為3 至(D+2),從節(jié)點1 搜索與節(jié)點2 的聯(lián)通序列,如果存在聯(lián)通序列則記錄聯(lián)通序列并停止,進行下一個任務節(jié)點的搜索。 如果不存在聯(lián)通序列,說明有任務節(jié)點不能和測控系統(tǒng)節(jié)點聯(lián)通,生成的節(jié)點位置不滿足可行性條件,立即結束搜索,重新在任務區(qū)域內隨機生成D個位置點作為蜜源位置并判斷其鏈路可行性,直到生成NP 個滿足條件的蜜源,NP 為種群規(guī)模。 以此,完成種群初始化。

3.2 引領蜂階段

引領蜂通常在蜜源附近進行鄰域搜索。 為了表示鄰域搜索的行為,引入變異算子操作,其操作過程如圖1 所示。

圖1 變異算子操作Fig.1 Mutation operator operation

步驟1 從1 ～D之間隨機生成2 個整數(shù)r1和r2。

步驟2 將所選蜜源中序列碼在r1和r2位置中間的幾個位置變?yōu)殡S機生成可行域內的位置點。

步驟3 利用RDFS 算法檢驗新的中繼位置點是否滿足對所有TU 節(jié)點的聯(lián)通性要求,若滿足則使用新的位置點作為新的蜜源,并計算出所使用的中繼節(jié)點RU 的數(shù)量,若不滿足則轉至步驟1。

使用變異算子操作對引領蜂進行鄰域搜索,采用RDFS 算法計算出每個引領蜂的目標函數(shù),并在當前蜜源和新的鄰近蜜源之間進行貪婪選擇,以保證更好的蜜源被保留下來供進一步進化。 貪婪選擇是基于蜜源的適應度值,計算方法如下:

式中:fiti為適應度函數(shù);fi為模型的目標函數(shù),即在第i個蜜源中所有的TU 與GCS 聯(lián)通中所用到的中繼節(jié)點RU 的數(shù)量。

3.3 跟隨蜂階段

跟隨蜂是按輪盤賭方式在引領蜂種群中選擇的較優(yōu)種群,計算如下:

式中:pi為收益率,SN為蜜源個數(shù)。 跟隨蜂階段根據(jù)收益率大小來選擇蜜源位置,使用變異算子操作來進行鄰域搜索產(chǎn)生新的蜜源,收益率通過適應度值來表示。 同引領蜂階段一樣,使用貪婪選擇保留更優(yōu)蜜源。

3.4 偵察蜂階段

如果在有限的迭代次數(shù)內,引領蜂和跟隨蜂鄰域搜索沒有找到更優(yōu)蜜源,則將其作為偵察蜂。在任務區(qū)域內隨機生成D個位置點作為偵察蜂并根據(jù)快速DFS 算法判斷其鏈路可行性,如果不可行則重新生成。

在以上基于RDFS 的人工蜂群算法的4 個階段,RDFS 算法可有效地判斷種群可行性,也可快速搜索可用的中繼節(jié)點位置,求解目標函數(shù)。

4 方法步驟

針對中繼無人機部署問題,采用基于RDFS的人工蜂群算法求解的步驟如圖2 所示。

圖2 RDFS-ABC 算法流程Fig.2 RDFS-ABC algorithm flowchart

步驟1 種群初始化。 設置初始化參數(shù):種群規(guī)模NP、蜜源維度D、一個蜜源的最大搜索次數(shù)l及最大迭代次數(shù)c隨機生成SN個蜜源,每個蜜源是任務區(qū)域內D個隨機點位置,并且每個蜜源均經(jīng)過RDFS 算法搜索驗證為任務區(qū)域內的可行解。

步驟2 引領蜂階段。 使用變異算子操作對每個引領蜂進行鄰域搜索,根據(jù)RDFS 算法驗證其可行性,計算出每個可行解目標函數(shù)的解。 使用貪婪選擇保留更好的解。

步驟3 選擇產(chǎn)生跟隨蜂。 按輪盤賭方式選擇較優(yōu)種群作為跟隨蜂種群。

步驟4 跟隨蜂階段。 同引領蜂一樣,使用變異算子操作對每個引領蜂進行鄰域搜索,根據(jù)RDFS 算法驗證其可行性,計算出每個可行解目標函數(shù)的解。 使用貪婪選擇保留更好的解。

步驟5 判斷是否產(chǎn)生偵察蜂。 如果產(chǎn)生,在任務區(qū)域內隨機生成一組包含D個位置點的中繼網(wǎng)絡作為一個偵察蜂,并通過RDFS 算法判斷其鏈路可行性,計算其目標函數(shù)值,進行全局搜索。

步驟6 判斷是否滿足終止條件,若滿足則輸出最優(yōu)解,否則轉至步驟2。

5 仿真實驗

仿真實驗平臺為Inter Core i5-7300HQ CPU,8 GB, 64 位Win10 操作系統(tǒng)。 編程工具為MATLAB R2017b(64 位)。

5.1 參數(shù)設置

對仿真實驗參數(shù)設置如表1 所示,其中包括約束參數(shù)、測控系統(tǒng)位置及人工蜂群算法參數(shù)。

表1 實驗參數(shù)設置Table 1 Experimental parameter setting

5.2 實驗結果及分析

5.2.1 實驗1

實驗1 為在作戰(zhàn)區(qū)域內設置數(shù)個目標,驗證算法的有效性。

假設作戰(zhàn)區(qū)域有30 個目標需要進行偵察或者攻擊,目標點位置坐標如表2 所示,進行仿真實驗,可得中繼節(jié)點部署結果如圖3 所示,圖中:小點表示中繼無人機RU 的位置,圈表示RU 的有效通信范圍,大點表示目標位置。

表2 任務節(jié)點位置坐標Table 2 Task node location coordinates

現(xiàn)將實驗結果分析如下:

1) 由圖3 可得,所有的TU 節(jié)點都在RU 節(jié)點的有效通信覆蓋范圍之內,并且每個RU 節(jié)點都可以與GCS 進行數(shù)據(jù)鏈路通信,則說明所有的TU 節(jié)點都可以通過RU 節(jié)點與GCS 進行數(shù)據(jù)鏈路通信,說明了算法的有效性。

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

2) 在一定任務背景下,利用RDFS-ABC 算法可有效求解得到中繼無人機的數(shù)量及其對應位置信息,說明了算法的可行性。

5.2.2 實驗2

實驗2 為在同一目標和測控系統(tǒng)屬性的情況下,對比DFS-ABC 算法和RDFS-ABC 算法的運行時間,驗證RDFS-ABC 算法的求解效率。

設置作戰(zhàn)區(qū)域內的目標規(guī)模為5、10、15、20、25、30,分別進行仿真實驗。 在不同目標規(guī)模下,算法各運行100 次,記錄算法運行求解時間,取其平均值,可得到統(tǒng)計結果如表3 和圖4 所示。

表3 兩種算法運行的平均時間Table 3 Average schedule of two algorithms

圖4 運行時間對比圖Fig.4 Run time comparison chart

現(xiàn)將實驗結果分析如下:

1) 由表3 和圖4 數(shù)據(jù)可知,在相同目標規(guī)模條件下,RDFS-ABC 算法的求解時間均小于DFSABC 算法的運行時間,平均降低了53.56%,說明了RDFS-ABC 算法的求解效率更高,算法實用性更強。

2) RDFS-ABC 算法的求解效率更高,表明RDFS 算法在搜索2 點之間可行鏈路問題上相比于DFS 算法更具有一定優(yōu)越性。

5.2.3 實驗3

實驗3 為在同一目標和測控系統(tǒng)屬性的情況下,對比RDFS-ABC 算法、PSO 算法和文獻[13]所提的AHOP 算法求解精度及收斂性。

設置PSO 算法中種群規(guī)模為100,最大迭代次數(shù)為60,認知參數(shù)和社會參數(shù)分別為0. 7 和1.4;AHOP 算法中設置任務區(qū)域內離散化步長為10。 假設作戰(zhàn)區(qū)域內有15 個目標,在相同目標規(guī)模下,用3 種算法各進行仿真實驗100 次,記錄中繼節(jié)點數(shù)量,取其平均值,可得統(tǒng)計結果如表4 所示,并記錄一次仿真結果如圖5 ～圖7 所示。

結果分析如下:

1) 由圖5 ～圖7 可得,所有的TU 節(jié)點都在RU 節(jié)點的有效通信覆蓋范圍之內,并且每個RU節(jié)點都可以與GCS 進行數(shù)據(jù)鏈路通信,說明3 種算法都可以實現(xiàn)GCS 節(jié)點與所有TU 節(jié)點進行有效鏈路通信,滿足中繼節(jié)點部署要求。

圖7 AHOP 算法中繼節(jié)點部署圖Fig.7 Relay node deployment diagram with AHOP algorithm

2) 由表4 可得,在相同條件下,RDFS-ABC算法求解得到的中繼節(jié)點數(shù)量平均為7.05 架,PSO算法求解得到的中繼無人機數(shù)量平均為8.34 架,相對于前者中繼無人機數(shù)量增加了15.47%。 AHOP 算法求解得到的中繼無人機數(shù)量平均為8 架,相對于RDFS-ABC 算法的求解結果增加了11.88%,說明RDFS-ABC 算法的求解精度更高。

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

圖6 RDFS-ABC 算法中繼節(jié)點部署圖Fig.6 Relay node deployment diagram with RDFS-ABC algorithm

6 結 論

為解決中繼無人機部署效率低、部署方案無法滿足最少數(shù)量要求等問題,提出了一種快速中繼無人機部署策略,通過仿真驗證了所提出航跡規(guī)劃算法的有效性及收斂性,主要得到以下結論:

1) 本文提出的中繼無人機部署策略可有效解決中繼無人機部署問題,且求解得到部署方案實用性更強、效率更高。

2) RDFS 算法優(yōu)化了DFS 算法的搜索方式,實現(xiàn)了節(jié)點間可行鏈路的快速搜索,可為解決其他圖論問題提供參考。

3) 在ABC 算法中引入RDFS 算法,并用于求解中繼無人機部署問題,可有效提高求解效率。

4) 在后續(xù)工作中,可將中繼無人機部署問題同無人機集群通信問題相互關聯(lián)研究。