一種中繼無人機快速部署策略

2021-09-11 09:02:34張小孟楊森宋曉胡永江李文廣

北京航空航天大學學報 2021年8期

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

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

隨著無人作戰區域范圍的擴展,單架無人機的有效通信范圍逐漸成為制約其作戰半徑的主要矛盾。通過構建中繼無人機網絡,進行數據鏈路的“接力” 傳輸,可有效擴展無人機的作戰半徑[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 即停止訪問,記錄訪問鏈路,無需再繼續訪問其余頂點。

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

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

3 基于RDFS 的人工蜂群算法

人工蜂群(Artificial Bee Colony, ABC)算法是由Karaboga 于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 節點進行有效鏈路通信,滿足中繼節點部署要求。

圖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 算法的求解精度更高。