張小孟 楊森 宋曉 胡永江 李文廣
(1. 陸軍工程大學(xué) 無人機(jī)工程系, 石家莊 050003;2. 北京航空航天大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京 100083; 3. 中國人民解放軍 31700 部隊(duì), 遼陽 111000)
隨著無人作戰(zhàn)區(qū)域范圍的擴(kuò)展,單架無人機(jī)的有效通信范圍逐漸成為制約其作戰(zhàn)半徑的主要矛盾。 通過構(gòu)建中繼無人機(jī)網(wǎng)絡(luò),進(jìn)行數(shù)據(jù)鏈路的“接力” 傳輸,可有效擴(kuò)展無人機(jī)的作戰(zhàn)半徑[1-3]。 中繼無人機(jī)用作無線通信的中繼節(jié)點(diǎn),使得任務(wù)機(jī)在一定距離下仍可實(shí)時(shí)與地面測控系統(tǒng)保持信息交互[4-5]。
中繼無人機(jī)部署問題就是在作戰(zhàn)目標(biāo)和地面測控系統(tǒng)位置已知的條件下,如何根據(jù)無人機(jī)作戰(zhàn)鏈路需求及中繼無人機(jī)的性能,以最少數(shù)量的中繼無人機(jī)完成整個(gè)無人機(jī)通信鏈路中繼節(jié)點(diǎn)的設(shè)置問題[6-9]。 文獻(xiàn)[10]針對中繼無人機(jī)部署問題,建立了中繼節(jié)點(diǎn)布置問題模型,提出了一種兩階段多項(xiàng)式中繼節(jié)點(diǎn)布置算法,可有效滿足戰(zhàn)場無人機(jī)中繼通信需求。 但是該算法的中繼節(jié)點(diǎn)布置范圍只能在等間距的離散位置點(diǎn)上選取,不具有普適性。 文獻(xiàn)[11-12]采用了粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法將一定數(shù)量的中繼無人機(jī)分配給多個(gè)任務(wù),以此來確定中繼無人機(jī)的位置,這只能解決在中繼無人機(jī)數(shù)量一定的情況下,其有效部署的問題,但無法以最少的中繼無人機(jī)數(shù)量來有效完成中繼無人機(jī)的部署。 文獻(xiàn)[13]將中繼部署問題歸結(jié)為單源最短路徑問題,在考慮到中繼節(jié)點(diǎn)數(shù)量有限的情況下,使用了一種基于Bellman-ford 算法的AHOP 算法,可以得出最小化路徑代價(jià)和跳數(shù)的Pareto 解。 文獻(xiàn)[14]提出了一種雙層中繼節(jié)點(diǎn)布局問題模型,利用基于最小生成樹的多項(xiàng)式時(shí)間近似算法,來求解最少數(shù)量中繼節(jié)點(diǎn)的部署位置。
上述方法雖然在一定程度上能夠解決中繼無人機(jī)的部署問題,但仍存在以下不足:在求解前要求預(yù)先對任務(wù)區(qū)域進(jìn)行離散化處理,但離散化程度對于求解效率及求解精度均有一定影響;以最小生成樹的方式求解中繼無人機(jī)部署問題,可有效約束路徑代價(jià)的總和最小,但僅考慮在邊上部署中繼節(jié)點(diǎn),求解結(jié)果存在一定冗余。
針對以上問題,本文提出了一種中繼無人機(jī)快速部署策略。 通過建立基于最少中繼節(jié)點(diǎn)的部署模型和采用基于快速深度優(yōu)先搜索的人工蜂群算法,來實(shí)現(xiàn)問題的求解。 在模型求解過程中,不需要預(yù)先對任務(wù)區(qū)域進(jìn)行離散化,而是在可行域內(nèi)隨機(jī)生成可以滿足連通性的節(jié)點(diǎn),以最少中繼節(jié)點(diǎn)數(shù)量為目標(biāo)函數(shù),使用群智能算法,優(yōu)化調(diào)整有效節(jié)點(diǎn)部署位置,得到最少中繼無人機(jī)部署方案。
在無人機(jī)中繼通信網(wǎng)絡(luò)中地面測控系統(tǒng)(Ground Control System,GCS)、待執(zhí)行任務(wù)無人機(jī)(Task UAV,TU)和中繼無人機(jī)(Relay UAV,RU)均視為無人機(jī)中繼通信網(wǎng)絡(luò)中的通信節(jié)點(diǎn),且假設(shè)所有的節(jié)點(diǎn)均處于同樣的海拔高度。 用G=g表示地面測控系統(tǒng)(g為無人機(jī)的地面控制系統(tǒng)的位置)、集合T={t1,t2,…,tNt}表示待執(zhí)行任務(wù)無人機(jī)、集合R={r1,r2,…,rNr}表示中繼無人機(jī)。其中Nt為待執(zhí)行任務(wù)機(jī)數(shù)量,Nr為中繼無人機(jī)數(shù)量。 對應(yīng)可將GCS、RU 和TU 的位置以集合的形式表示為

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



式中:dsf為防止無人機(jī)之間碰撞的最小安全距離。 安全距離dsf必須遠(yuǎn)小于通信距離d0,并且假定TU 之間的距離是保持安全的。
在戰(zhàn)場環(huán)境中,無人機(jī)數(shù)量越多,越容易被敵雷達(dá)探測到,將會(huì)增加無人機(jī)被敵打擊的概率,進(jìn)而可能會(huì)影響整體作戰(zhàn)計(jì)劃。 因此為了盡可能的降低被敵雷達(dá)探測到的概率,應(yīng)盡可能的減少中繼無人機(jī)的數(shù)量,來保證更安全地完成作戰(zhàn)任務(wù)。同時(shí),在空域中,無人機(jī)的數(shù)量越少,也越有利于無人機(jī)的飛行安全。 所以,對于中繼無人機(jī)的部署要在滿足通信要求和安全性能的前提下,以最少數(shù)量的中繼無人機(jī)來保證所有任務(wù)機(jī)與測控系統(tǒng)可進(jìn)行實(shí)時(shí)通信。
由此,有效中繼無人機(jī)數(shù)量可表示為

式中:f為中繼網(wǎng)絡(luò)中無人機(jī)的計(jì)數(shù)函數(shù)。
綜上所述,結(jié)合有效通信距離約束、安全距離約束等條件,基于最少中繼節(jié)點(diǎn)的部署模型的目標(biāo)函數(shù)可表示為

式中:X?R2為無人機(jī)的二維可展開空間。
深度優(yōu)先搜索算法[15](Depth First Search,DFS)屬于圖算法的一種,是一種針對圖和樹遍歷的經(jīng)典算法,利用DFS 算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多圖論問題。 但是經(jīng)典的DFS 算法存在隨著節(jié)點(diǎn)數(shù)量的增加,其計(jì)算復(fù)雜度成階次提高的缺點(diǎn),這將嚴(yán)重影響算法的求解效率。
對于在任務(wù)空間中事先隨機(jī)生成一定數(shù)量滿足連通性的中繼節(jié)點(diǎn)RU 的位置中,如何快速找到測控系統(tǒng)GCS 通過中繼節(jié)點(diǎn)RU 與所有TU 節(jié)點(diǎn)之間的可行鏈路問題,就屬于圖論問題。 為有效保證求解效率,對DFS 算法的搜索方式進(jìn)行了優(yōu)化,提出了一種快速深度優(yōu)先搜索(Rapidly Depth First Search,RDFS)算法,即在每次搜索節(jié)點(diǎn)TU 的過程中,搜索到一條可行路徑便結(jié)束當(dāng)前搜索,因?yàn)椴槐乇闅v所有的節(jié)點(diǎn),去尋找其他較短鏈路,所以搜索過程耗時(shí)明顯減少,尤其是在節(jié)點(diǎn)數(shù)目較多的情況下,平均時(shí)間復(fù)雜度可以減少為原來的一半。
在節(jié)點(diǎn)間搜索可行鏈路時(shí),將依據(jù)以下步驟:
步驟1 將GCS 作為第一個(gè)被訪問的頂點(diǎn),TU 作為未被訪問過的頂點(diǎn)。
步驟2 對訪問過的頂點(diǎn)作已訪問過的標(biāo)志。
步驟3 依次從頂點(diǎn)未被訪問過的第1, 2,…,n個(gè)鄰接頂點(diǎn)出發(fā),對其進(jìn)行深度優(yōu)先搜索,至訪問到TU 即停止訪問,記錄訪問鏈路,無需再繼續(xù)訪問其余頂點(diǎn)。
步驟4 如果頂點(diǎn)TU 未被訪問,說明GCS和TU 沒有可行鏈路,則結(jié)束。
通過以上優(yōu)化的搜索方式,可有效降低算法求解的時(shí)間復(fù)雜度,同時(shí)仍能找到可行解。
人工蜂群(Artificial Bee Colony, ABC)算法是由Karaboga 于2005 年提出的一種基于群智能的全局優(yōu)化算法[16]。 其通過不同分工的蜜蜂間的交流與協(xié)作實(shí)現(xiàn)群體智能,具有參數(shù)設(shè)置少、收斂速度快且收斂精度高等優(yōu)點(diǎn)。 但同樣在求解中繼無人機(jī)部署問題時(shí),受限于節(jié)點(diǎn)規(guī)模,求解效率不高。 所以,采用一種基于RDFS 的人工蜂群(RDFS-ABC)算法來實(shí)現(xiàn)中繼無人機(jī)部署問題的快速求解。
種群初始化即初始化蜜源位置,每一個(gè)蜜源位置代表一個(gè)可行解。 對于中繼無人機(jī)的部署問題,可行解即代表一組中繼節(jié)點(diǎn),且該組中繼節(jié)點(diǎn)滿足安全性和連通性的要求。
首先,在任務(wù)區(qū)域內(nèi)隨機(jī)生成D個(gè)位置點(diǎn)作為中繼無人機(jī)RU 的節(jié)點(diǎn)位置,D為蜜源維度。然后,使用RDFS 算法判斷中繼節(jié)點(diǎn)的可行性,即所有任務(wù)節(jié)點(diǎn)TU 可否通過中繼節(jié)點(diǎn)搜索到測控系統(tǒng)節(jié)點(diǎn)GCS 間的可行通信鏈路。 在每次搜索過程中,假設(shè)測控系統(tǒng)節(jié)點(diǎn)的序號為1,而任務(wù)節(jié)點(diǎn)的序號為2,其余中繼節(jié)點(diǎn)的序號為3 至(D+2),從節(jié)點(diǎn)1 搜索與節(jié)點(diǎn)2 的聯(lián)通序列,如果存在聯(lián)通序列則記錄聯(lián)通序列并停止,進(jìn)行下一個(gè)任務(wù)節(jié)點(diǎn)的搜索。 如果不存在聯(lián)通序列,說明有任務(wù)節(jié)點(diǎn)不能和測控系統(tǒng)節(jié)點(diǎn)聯(lián)通,生成的節(jié)點(diǎn)位置不滿足可行性條件,立即結(jié)束搜索,重新在任務(wù)區(qū)域內(nèi)隨機(jī)生成D個(gè)位置點(diǎn)作為蜜源位置并判斷其鏈路可行性,直到生成NP 個(gè)滿足條件的蜜源,NP 為種群規(guī)模。 以此,完成種群初始化。
引領(lǐng)蜂通常在蜜源附近進(jìn)行鄰域搜索。 為了表示鄰域搜索的行為,引入變異算子操作,其操作過程如圖1 所示。

圖1 變異算子操作Fig.1 Mutation operator operation
步驟1 從1 ~D之間隨機(jī)生成2 個(gè)整數(shù)r1和r2。
步驟2 將所選蜜源中序列碼在r1和r2位置中間的幾個(gè)位置變?yōu)殡S機(jī)生成可行域內(nèi)的位置點(diǎn)。
步驟3 利用RDFS 算法檢驗(yàn)新的中繼位置點(diǎn)是否滿足對所有TU 節(jié)點(diǎn)的聯(lián)通性要求,若滿足則使用新的位置點(diǎn)作為新的蜜源,并計(jì)算出所使用的中繼節(jié)點(diǎn)RU 的數(shù)量,若不滿足則轉(zhuǎn)至步驟1。
使用變異算子操作對引領(lǐng)蜂進(jìn)行鄰域搜索,采用RDFS 算法計(jì)算出每個(gè)引領(lǐng)蜂的目標(biāo)函數(shù),并在當(dāng)前蜜源和新的鄰近蜜源之間進(jìn)行貪婪選擇,以保證更好的蜜源被保留下來供進(jìn)一步進(jìn)化。 貪婪選擇是基于蜜源的適應(yīng)度值,計(jì)算方法如下:

式中:fiti為適應(yīng)度函數(shù);fi為模型的目標(biāo)函數(shù),即在第i個(gè)蜜源中所有的TU 與GCS 聯(lián)通中所用到的中繼節(jié)點(diǎn)RU 的數(shù)量。
跟隨蜂是按輪盤賭方式在引領(lǐng)蜂種群中選擇的較優(yōu)種群,計(jì)算如下:

式中:pi為收益率,SN為蜜源個(gè)數(shù)。 跟隨蜂階段根據(jù)收益率大小來選擇蜜源位置,使用變異算子操作來進(jìn)行鄰域搜索產(chǎn)生新的蜜源,收益率通過適應(yīng)度值來表示。 同引領(lǐng)蜂階段一樣,使用貪婪選擇保留更優(yōu)蜜源。
如果在有限的迭代次數(shù)內(nèi),引領(lǐng)蜂和跟隨蜂鄰域搜索沒有找到更優(yōu)蜜源,則將其作為偵察蜂。在任務(wù)區(qū)域內(nèi)隨機(jī)生成D個(gè)位置點(diǎn)作為偵察蜂并根據(jù)快速DFS 算法判斷其鏈路可行性,如果不可行則重新生成。
在以上基于RDFS 的人工蜂群算法的4 個(gè)階段,RDFS 算法可有效地判斷種群可行性,也可快速搜索可用的中繼節(jié)點(diǎn)位置,求解目標(biāo)函數(shù)。
針對中繼無人機(jī)部署問題,采用基于RDFS的人工蜂群算法求解的步驟如圖2 所示。

圖2 RDFS-ABC 算法流程Fig.2 RDFS-ABC algorithm flowchart
步驟1 種群初始化。 設(shè)置初始化參數(shù):種群規(guī)模NP、蜜源維度D、一個(gè)蜜源的最大搜索次數(shù)l及最大迭代次數(shù)c隨機(jī)生成SN個(gè)蜜源,每個(gè)蜜源是任務(wù)區(qū)域內(nèi)D個(gè)隨機(jī)點(diǎn)位置,并且每個(gè)蜜源均經(jīng)過RDFS 算法搜索驗(yàn)證為任務(wù)區(qū)域內(nèi)的可行解。
步驟2 引領(lǐng)蜂階段。 使用變異算子操作對每個(gè)引領(lǐng)蜂進(jìn)行鄰域搜索,根據(jù)RDFS 算法驗(yàn)證其可行性,計(jì)算出每個(gè)可行解目標(biāo)函數(shù)的解。 使用貪婪選擇保留更好的解。
步驟3 選擇產(chǎn)生跟隨蜂。 按輪盤賭方式選擇較優(yōu)種群作為跟隨蜂種群。
步驟4 跟隨蜂階段。 同引領(lǐng)蜂一樣,使用變異算子操作對每個(gè)引領(lǐng)蜂進(jìn)行鄰域搜索,根據(jù)RDFS 算法驗(yàn)證其可行性,計(jì)算出每個(gè)可行解目標(biāo)函數(shù)的解。 使用貪婪選擇保留更好的解。
步驟5 判斷是否產(chǎn)生偵察蜂。 如果產(chǎn)生,在任務(wù)區(qū)域內(nèi)隨機(jī)生成一組包含D個(gè)位置點(diǎn)的中繼網(wǎng)絡(luò)作為一個(gè)偵察蜂,并通過RDFS 算法判斷其鏈路可行性,計(jì)算其目標(biāo)函數(shù)值,進(jìn)行全局搜索。
步驟6 判斷是否滿足終止條件,若滿足則輸出最優(yōu)解,否則轉(zhuǎn)至步驟2。
仿真實(shí)驗(yàn)平臺(tái)為Inter Core i5-7300HQ CPU,8 GB, 64 位Win10 操作系統(tǒng)。 編程工具為MATLAB R2017b(64 位)。
對仿真實(shí)驗(yàn)參數(shù)設(shè)置如表1 所示,其中包括約束參數(shù)、測控系統(tǒng)位置及人工蜂群算法參數(shù)。

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Experimental parameter setting
5.2.1 實(shí)驗(yàn)1
實(shí)驗(yàn)1 為在作戰(zhàn)區(qū)域內(nèi)設(shè)置數(shù)個(gè)目標(biāo),驗(yàn)證算法的有效性。
假設(shè)作戰(zhàn)區(qū)域有30 個(gè)目標(biāo)需要進(jìn)行偵察或者攻擊,目標(biāo)點(diǎn)位置坐標(biāo)如表2 所示,進(jìn)行仿真實(shí)驗(yàn),可得中繼節(jié)點(diǎn)部署結(jié)果如圖3 所示,圖中:小點(diǎn)表示中繼無人機(jī)RU 的位置,圈表示RU 的有效通信范圍,大點(diǎn)表示目標(biāo)位置。

表2 任務(wù)節(jié)點(diǎn)位置坐標(biāo)Table 2 Task node location coordinates
現(xiàn)將實(shí)驗(yàn)結(jié)果分析如下:
1) 由圖3 可得,所有的TU 節(jié)點(diǎn)都在RU 節(jié)點(diǎn)的有效通信覆蓋范圍之內(nèi),并且每個(gè)RU 節(jié)點(diǎn)都可以與GCS 進(jìn)行數(shù)據(jù)鏈路通信,則說明所有的TU 節(jié)點(diǎn)都可以通過RU 節(jié)點(diǎn)與GCS 進(jìn)行數(shù)據(jù)鏈路通信,說明了算法的有效性。

圖3 中繼節(jié)點(diǎn)部署圖Fig.3 Deployment diagram of relay nodes
2) 在一定任務(wù)背景下,利用RDFS-ABC 算法可有效求解得到中繼無人機(jī)的數(shù)量及其對應(yīng)位置信息,說明了算法的可行性。
5.2.2 實(shí)驗(yàn)2
實(shí)驗(yàn)2 為在同一目標(biāo)和測控系統(tǒng)屬性的情況下,對比DFS-ABC 算法和RDFS-ABC 算法的運(yùn)行時(shí)間,驗(yàn)證RDFS-ABC 算法的求解效率。
設(shè)置作戰(zhàn)區(qū)域內(nèi)的目標(biāo)規(guī)模為5、10、15、20、25、30,分別進(jìn)行仿真實(shí)驗(yàn)。 在不同目標(biāo)規(guī)模下,算法各運(yùn)行100 次,記錄算法運(yùn)行求解時(shí)間,取其平均值,可得到統(tǒng)計(jì)結(jié)果如表3 和圖4 所示。

表3 兩種算法運(yùn)行的平均時(shí)間Table 3 Average schedule of two algorithms

圖4 運(yùn)行時(shí)間對比圖Fig.4 Run time comparison chart
現(xiàn)將實(shí)驗(yàn)結(jié)果分析如下:
1) 由表3 和圖4 數(shù)據(jù)可知,在相同目標(biāo)規(guī)模條件下,RDFS-ABC 算法的求解時(shí)間均小于DFSABC 算法的運(yùn)行時(shí)間,平均降低了53.56%,說明了RDFS-ABC 算法的求解效率更高,算法實(shí)用性更強(qiáng)。
2) RDFS-ABC 算法的求解效率更高,表明RDFS 算法在搜索2 點(diǎn)之間可行鏈路問題上相比于DFS 算法更具有一定優(yōu)越性。
5.2.3 實(shí)驗(yàn)3
實(shí)驗(yàn)3 為在同一目標(biāo)和測控系統(tǒng)屬性的情況下,對比RDFS-ABC 算法、PSO 算法和文獻(xiàn)[13]所提的AHOP 算法求解精度及收斂性。
設(shè)置PSO 算法中種群規(guī)模為100,最大迭代次數(shù)為60,認(rèn)知參數(shù)和社會(huì)參數(shù)分別為0. 7 和1.4;AHOP 算法中設(shè)置任務(wù)區(qū)域內(nèi)離散化步長為10。 假設(shè)作戰(zhàn)區(qū)域內(nèi)有15 個(gè)目標(biāo),在相同目標(biāo)規(guī)模下,用3 種算法各進(jìn)行仿真實(shí)驗(yàn)100 次,記錄中繼節(jié)點(diǎn)數(shù)量,取其平均值,可得統(tǒng)計(jì)結(jié)果如表4 所示,并記錄一次仿真結(jié)果如圖5 ~圖7 所示。
結(jié)果分析如下:
1) 由圖5 ~圖7 可得,所有的TU 節(jié)點(diǎn)都在RU 節(jié)點(diǎn)的有效通信覆蓋范圍之內(nèi),并且每個(gè)RU節(jié)點(diǎn)都可以與GCS 進(jìn)行數(shù)據(jù)鏈路通信,說明3 種算法都可以實(shí)現(xiàn)GCS 節(jié)點(diǎn)與所有TU 節(jié)點(diǎn)進(jìn)行有效鏈路通信,滿足中繼節(jié)點(diǎn)部署要求。

圖7 AHOP 算法中繼節(jié)點(diǎn)部署圖Fig.7 Relay node deployment diagram with AHOP algorithm
2) 由表4 可得,在相同條件下,RDFS-ABC算法求解得到的中繼節(jié)點(diǎn)數(shù)量平均為7.05 架,PSO算法求解得到的中繼無人機(jī)數(shù)量平均為8.34 架,相對于前者中繼無人機(jī)數(shù)量增加了15.47%。 AHOP 算法求解得到的中繼無人機(jī)數(shù)量平均為8 架,相對于RDFS-ABC 算法的求解結(jié)果增加了11.88%,說明RDFS-ABC 算法的求解精度更高。

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

圖6 RDFS-ABC 算法中繼節(jié)點(diǎn)部署圖Fig.6 Relay node deployment diagram with RDFS-ABC algorithm
為解決中繼無人機(jī)部署效率低、部署方案無法滿足最少數(shù)量要求等問題,提出了一種快速中繼無人機(jī)部署策略,通過仿真驗(yàn)證了所提出航跡規(guī)劃算法的有效性及收斂性,主要得到以下結(jié)論:
1) 本文提出的中繼無人機(jī)部署策略可有效解決中繼無人機(jī)部署問題,且求解得到部署方案實(shí)用性更強(qiáng)、效率更高。
2) RDFS 算法優(yōu)化了DFS 算法的搜索方式,實(shí)現(xiàn)了節(jié)點(diǎn)間可行鏈路的快速搜索,可為解決其他圖論問題提供參考。
3) 在ABC 算法中引入RDFS 算法,并用于求解中繼無人機(jī)部署問題,可有效提高求解效率。
4) 在后續(xù)工作中,可將中繼無人機(jī)部署問題同無人機(jī)集群通信問題相互關(guān)聯(lián)研究。