張小孟1,2,3, 楊森1,2,?, 宋曉2, 胡永江1, 李文廣1

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

摘 要: 針對任務規劃中中繼無人機部署效率低,部署方案無法滿足最少數量要求等問題,提出了一種中繼無人機快速部署策略。首先,根據最少中繼節點的任務要求,建立了基于最少中繼節點的部署模型。其次,優化了深度優先搜索算法的搜索方式,實現了節點間可行鏈路的快速搜索。最后,在人工蜂群(ABC)算法中引入快速深度優先搜索(DFS)算法,來求解最少中繼節點部署方案。仿真結果表明:在相同任務規模下,所提策略的求解速度相較于改進前提高了53.56%左右,部署的中繼無人機數量相較于現有方法減小了11.88%左右。

關 鍵 詞: 中繼無人機; 部署方案; 深度優先; 最少節點; 人工蜂群(ABC)

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

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

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

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

1 基于最少中繼節點的部署模型

1.1 問題描述

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

 

式中:xv∈R2 為節點v 的位置。

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

 

1.2 約束條件

 

 

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

1.3 目標函數

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

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

 

式中:f 為中繼網絡中無人機的計數函數。

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

 

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

2 快速深度優先搜索

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

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

在節點間搜索可行鏈路時,將依據以下步驟:

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

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

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

⑤縣級建設地下水情信息自動采集站，負責全縣地下水情信息的收集統計和管理決策，并按規定格式傳輸和上報。地下水情信息自動采集站按每個示范鄉鎮1處布設。

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

3 基于RDFS 的人工蜂群算法

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

3.1 種群初始化

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

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

3.2 引領蜂階段

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

   

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

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

步驟2 將所選蜜源中序列碼在r1 和r2 位置中間的幾個位置變為隨機生成可行域內的位置點。

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

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

 

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

3.3 跟隨蜂階段

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

 

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

3.4 偵察蜂階段

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

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

4 方法步驟

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

   

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

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

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

步驟3 選擇產生跟隨蜂。按輪盤賭方式選擇較優種群作為跟隨蜂種群。

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

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

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

5 仿真實驗

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

5.1 參數設置

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

表1 實驗參數設置
Table 1 Experimental parameter setting

     

5.2 實驗結果及分析

5.2.1 實驗1

實驗1 為在作戰區域內設置數個目標,驗證算法的有效性。

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

表2 任務節點位置坐標
Table 2 Task node location coordinates

     

現將實驗結果分析如下:

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

   

圖3 中繼節點部署圖
Fig.3 Deployment diagram of relay nodes

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

5.2.2 實驗2

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

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

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

     

   

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

現將實驗結果分析如下:

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

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

5.2.3 實驗3

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

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

結果分析如下:

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

   

圖5 PSO 算法中繼節點部署圖
Fig.5 Relay node deployment diagram with PSO algorithm

   

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

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

表4 中繼節點平均數量
Table 4 Average number of relay nodes

     

   

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

6 結 論

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

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

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

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

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

參考文獻(References)

[ 1 ] OUBBATI O S,LAKAS A,ZHOU F,et al. A survey on position-based routing protocols for flying ad hoc networks(FANETs)[J].Vehicular Communications,2017,10:29-56.

[ 2 ] OUBBATI O S,ATIQUZZAMAN M,LORENZ P,et al. Routing in flying ad hoc networks:Survey,constraints,and future challenge perspectives[J].IEEE Access,2019,7:81057-81105.

[ 3 ] BEKMEZCI ?I,SAHINGOZ O K,TEMEL ?. Flying ad-hoc networks (FANETs):A survey[J]. Ad Hoc Networks,2013,11(3):1254-1270.

[ 4 ] MARCO M,EDISON F,JOAO L,et al. Using cooperative MIMO technigues wireless sensor networks[C] //2013 International Conference on Computing Management and Teleoommunications,2013.

[ 5 ] 屈鑫祺.無人機中繼的節能部署算法研究[D]. 西安:西安電子科技大學,2019.QU X Q. Research on energy-saving deployment algorithm for UAV relay[D].Xi’an:Xidian University,2019(in Chinese).

[ 6 ] 岳殿武,孟子琦,孫玉,等.大規模MIMO 中繼系統基于LoS的等增益傳輸方案[J]. 系統工程與電子技術,2018,40(10):2340-2347.YUE D W,MENG Z Q,SUN Y,et al. Los-based equal gain transmission scheme for massive MIMO relaying systems[J].Systems Engineering and Electronics,2018,40 (10):2340-2347(in Chinese).

[ 7 ] ZHU L,YAO C H,WANG L.Optimal energy efficiency distributed relay decision in UAV swarms[J].Wireless Personal Communications,2018,102(4):2997-3008.

[ 8 ] KIM D Y,LEE J W. Topology construction for flying ad hoc networks (FANETs)[C]//2017 International Conference on Information and Communication Technology Convergence (ICTC).Piscataway:IEEE Press,2017:153-157.

[ 9 ] KIM D Y,LEE J W. Joint mission assignment and topology management in the mission-critical FANET[C]//IEEE Internet of Things Journal. Piscataway:IEEE Press,2020:2368-2385.

[10] 吳高峰,高曉光,符小衛. 一種基于多無人機的中繼節點布置問題建模與優化方法[J]. 航空學報,2017,38(11):321195.WU G F,GAO X G,FU X W.Modeling and optimization method of relay node placement using multi-UAV[J]. Acta Aeronautica et Astronautica Sinica,2017,38(11):321195(in Chinese).

[11] KIM D Y,LEE J W.Joint mission assignment and location management for UAVs in mission-critical flying ad hoc networks[C]//2018 International Conference on Information and Communication Technology Convergence (ICTC).Piscataway:IEEE Press,2018:323-328.

[12] KIM D Y,LEE J W. Integrated topology management in flying ad hoc networks:Topology construction and adjustment[J].IEEE Access,2018,6:61196-61211.

[13] BURDAKOV O,DOHERTY P,HOLMBERG K,et al. Optimal placement of UV-based communications relay nodes[J]. Journal of Global Optimization,2010,48(4):511-531.

[14] LLOYD E L,XUE G L. Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers,2007,56(1):134-138.

[15] 楊正磊,鐘文冬,席濤,等. 面向應急需求的成像衛星單任務綜合規劃[J].系統工程與電子技術,2018,40(9):2000-2006.YANG Z L,ZHONG W D,XI T,et al. Imaging reconnaissance satellites single mission integrated scheduling for emergency requirements[J]. Systems Engineering and Electronics,2018,40(9):2000-2006(in Chinese).

[16] KARAB OGA D.An idea based on honey bee swarm for numerical optimization[C]//2013 International Conference on Computing,Management and Tececommunications,2013:49-54.

A rapid deployment strategy of relay unmanned aerial vehicle

ZHANG Xiaomeng1,2,3, YANG Sen1,2,?, SONG Xiao2, HU Yongjiang1, LI Wenguang1

(1. Department of Unmanned Aerial Vehicle Engineering, Army Engineering University, Shijiazhuang 050003, China;2. School of Cyber Science and Technology, Beihang University, Beijing 100083;3. Army of 31700 of PLA, Liaoyang 111000, China)

Abstract: In order to solve the problems in mission planning, such as the low deployment efficiency of relay Unmanned Aerial Vehicle (UAV) and the deployment scheme cannot meet the minimum number requirements, a fast relay UAV deployment strategy is proposed. First, according to the task requirements of the least relay nodes, a deployment model based on the least relay nodes is established. Then, the search mode of the depth-first search algorithm is optimized, and the fast search of feasible links between nodes is realized.Finally, the Rapid Depth-First Search (RDFS) algorithm is introduced into the Artificial Bee Colony (ABC)algorithm to solve the deployment scheme of the least relay nodes. The simulation results show that under the same task scale, the solution speed of this strategy is ab out 53.56% higher than that before improvement, and the number of deployed relay UAVs is reduced by ab out 11.88% compared with the existing methods.

Keywords: relay UAV; deployment scheme; depth first; minimum nodes; Artificial Bee Colony (ABC)

中圖分類號: V279

文獻標志碼: A

文章編號: 1001-5965(2021)08-1705-07

http://bhxb.buaa.edu.cn jbuaa@ buaa.edu.cn

DOI: 10.13700/j.bh.1001-5965.2020.0249

收稿日期: 2020-06-07; 錄用日期: 2020-08-01;

網絡出版時間: 2020-08-06 08:13

網絡出版地址: kns.cnki.net/kcms/detail/11.2625.V.20200805.1359.007.html

基金項目: 陸軍工程大學石家莊校區科研創新發展基金(校教(2019)71 號)

?通信作者. E-mail: 568657132@ qq.com

引用格式: 張小孟, 楊森, 宋曉, 等. 一種中繼無人機快速部署策略[J]. 北京航空航天大學學報, 2021, 47(8): 1705- 1711.ZHANG X M, YANG S, SONG X, et al. A rapid deployment strategy of relay unmanned aerial vehicle[J].Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(8): 1705- 1711(in Chinese).

Received: 2020-06-07;

Accepted: 2020-08-01;

Published online: 2020-08-06 08:13

URL: kns.cnki.net/kcms/detail/11.2625.V.20200805.1359.007.html

Foundation item: Scientific Research and Innovation Development Fund of Shijiazhuang Campus of Army Engineering University (School Education (2019) No. 71)

?Corresponding author. E-mail: 568657132@ qq.com