一种中继无人机快速部署策略

张小孟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