中继无人机部署问题就是在作战目标和地面测控系统位置已知的条件下，如何根据无人机作战链路需求及中继无人机的性能，以最少数量的中继无人机完成整个无人机通信链路中继节点的设置问题[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的位置以集合的形式表示为
 | (1) |
式中：xv∈R2为节点v的位置。
由于GCS的位置是已知固定的，每个TU的位置是根据作战目标确定的，所以中继节点的部署位置可根据GCS、TU的位置信息来进行合理设计。TU与GCS的通信模式是端到端通信，假设将一个可行的无人机中继网络视为一个数学函数，以所有节点的位置信息为输入，每个TU与GCS之间的一组中继链路节点为输出，则这个中继网络可表示为
 | (2) |
式中：ρt为一个TU和GCS之间的中继网络节点的有序集合形成的一个通信链路，其第k个元素由ρtk表示，则第一个元素ρt1和最后一个元素ρtρt应分别为T和G，其余元素ρti(i=2, …, ρt－1)均为中继无人机R。
1.2 约束条件 由于无线信号的平均功率随传播距离呈指数衰减，当2个节点在一定的通信范围d0内时，即认为它们可有效地通信。所以，为了确保所有TU与GCS之间可有效通信，每个通信链路中相邻2个通信节点之间的距离不得大于d0。因此，中继节点之间的有效通信距离约束可表示为
 | (3) |
式中：d(u, v)为节点u和v之间的欧氏距离。
此外，考虑无人机的空域飞行安全，须限定各无人机之间的安全间隔，即中继无人机之间以及中继无人机和任务无人机之间的安全距离。因此，节点之间的安全距离约束可表示为
 | (4) |
式中：dsf为防止无人机之间碰撞的最小安全距离。安全距离dsf必须远小于通信距离d0，并且假定TU之间的距离是保持安全的。
1.3 目标函数 在战场环境中，无人机数量越多，越容易被敌雷达探测到，将会增加无人机被敌打击的概率，进而可能会影响整体作战计划。因此为了尽可能的降低被敌雷达探测到的概率，应尽可能的减少中继无人机的数量，来保证更安全地完成作战任务。同时，在空域中，无人机的数量越少，也越有利于无人机的飞行安全。所以，对于中继无人机的部署要在满足通信要求和安全性能的前提下，以最少数量的中继无人机来保证所有任务机与测控系统可进行实时通信。
由此，有效中继无人机数量可表示为
 | (5) |
式中：f为中继网络中无人机的计数函数。
综上所述，结合有效通信距离约束、安全距离约束等条件，基于最少中继节点的部署模型的目标函数可表示为
 | (6) |
式中：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算法计算出每个引领蜂的目标函数，并在当前蜜源和新的邻近蜜源之间进行贪婪选择，以保证更好的蜜源被保留下来供进一步进化。贪婪选择是基于蜜源的适应度值，计算方法如下：
 | (7) |
式中：fiti为适应度函数；fi为模型的目标函数，即在第i个蜜源中所有的TU与GCS联通中所用到的中继节点RU的数量。
3.3 跟随蜂阶段 跟随蜂是按轮盘赌方式在引领蜂种群中选择的较优种群，计算如下：
 | (8) |
式中：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
| 参数 | 数值 |
| 有效通信距离d0/m | 500 |
| 安全距离dsf/m | 20 |
| 测控系统位置g(x, y)/m | (350, 300) |
| 种群规模NP | 100 |
| 蜜源维度D | 28 |
| 最大搜索次数l | 5 |
| 最大迭代次数c | 60 |
表选项
5.2 实验结果及分析
5.2.1 实验1 实验1为在作战区域内设置数个目标，验证算法的有效性。
假设作战区域有30个目标需要进行侦察或者攻击，目标点位置坐标如表 2所示，进行仿真实验，可得中继节点部署结果如图 3所示，图中：小点表示中继无人机RU的位置，圈表示RU的有效通信范围，大点表示目标位置。
表 2 任务节点位置坐标 Table 2 Task node location coordinates
| 目标 | 位置(x, y)/m | 目标 | 位置(x, y)/m | |
| 1 | (1 150, 1 176) | 16 | (1 280, 1 200) | |
| 2 | (630, 1 660) | 17 | (230, 590) | |
| 3 | (40, 2 090) | 18 | (460, 860) | |
| 4 | (750, 1 100) | 19 | (1 040, 950) | |
| 5 | (750, 2 030) | 20 | (590, 1 390) | |
| 6 | (1 030, 2 070) | 21 | (830, 1 770) | |
| 7 | (1 650, 650) | 22 | (490, 500) | |
| 8 | (1 490, 1 630) | 23 | (1 840, 1 240) | |
| 9 | (790, 2 260) | 24 | (1 260, 1 500) | |
| 10 | (710, 1 310) | 25 | (1 280, 790) | |
| 11 | (840, 550) | 26 | (490, 2 130) | |
| 12 | (1 170, 2 300) | 27 | (1 460, 1 420) | |
| 13 | (970, 1 340) | 28 | (1 260, 1 910) | |
| 14 | (510, 700) | 29 | (360, 1 980) | |
| 15 | (750, 900) | 30 | (110, 900) |
表选项
 |
| 图 3 中继节点部署图 Fig. 3 Deployment diagram of relay nodes |
| 图选项 |
现将实验结果分析如下：
1) 由图 3可得，所有的TU节点都在RU节点的有效通信覆盖范围之内，并且每个RU节点都可以与GCS进行数据链路通信，则说明所有的TU节点都可以通过RU节点与GCS进行数据链路通信，说明了算法的有效性。
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
| 目标数量 | 平均时间/s | 降低比例/% | |
| RDFS-ABC算法 | DFS-ABC算法 | ||
| 5 | 5.59 | 13.05 | 57.16 |
| 10 | 13.31 | 27.19 | 51.05 |
| 15 | 18.12 | 40.07 | 54.78 |
| 20 | 21.62 | 47.10 | 54.10 |
| 25 | 26.67 | 57.09 | 53.28 |
| 30 | 33.56 | 68.43 | 50.96 |
表选项
 |
| 图 4 运行时间对比图 Fig. 4 Run time comparison chart |
| 图选项 |
现将实验结果分析如下：
1) 由表 3和图 4数据可知，在相同目标规模条件下，RDFS-ABC算法的求解时间均小于DFS-ABC算法的运行时间，平均降低了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所示。
表 4 中继节点平均数量 Table 4 Average number of relay nodes
| 算法 | 中继节点个数 | 增加率/% |
| RDFS-ABC | 7.05 | 0 |
| PSO | 8.34 | 15.47 |
| AHOP | 8.00 | 11.88 |
表选项
 |
| 图 5 PSO算法中继节点部署图 Fig. 5 Relay node deployment diagram with PSO algorithm |
| 图选项 |
 |
| 图 6 RDFS-ABC算法中继节点部署图 Fig. 6 Relay node deployment diagram with RDFS-ABC algorithm |
| 图选项 |
 |
| 图 7 AHOP算法中继节点部署图 Fig. 7 Relay node deployment diagram with AHOP algorithm |
| 图选项 |
结果分析如下：
1) 由图 5~图 7可得，所有的TU节点都在RU节点的有效通信覆盖范围之内，并且每个RU节点都可以与GCS进行数据链路通信，说明3种算法都可以实现GCS节点与所有TU节点进行有效链路通信，满足中继节点部署要求。
2) 由表 4可得，在相同条件下，RDFS-ABC算法求解得到的中继节点数量平均为7.05架，PSO算法求解得到的中继无人机数量平均为8.34架，相对于前者中继无人机数量增加了15.47%。AHOP算法求解得到的中继无人机数量平均为8架，相对于RDFS-ABC算法的求解结果增加了11.88%，说明RDFS-ABC算法的求解精度更高。
6 结论 为解决中继无人机部署效率低、部署方案无法满足最少数量要求等问题，提出了一种快速中继无人机部署策略，通过仿真验证了所提出航迹规划算法的有效性及收敛性，主要得到以下结论：
1) 本文提出的中继无人机部署策略可有效解决中继无人机部署问题，且求解得到部署方案实用性更强、效率更高。
2) RDFS算法优化了DFS算法的搜索方式，实现了节点间可行链路的快速搜索，可为解决其他图论问题提供参考。
3) 在ABC算法中引入RDFS算法，并用于求解中继无人机部署问题，可有效提高求解效率。
4) 在后续工作中，可将中继无人机部署问题同无人机集群通信问题相互关联研究。
参考文献
| [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. DOI:10.1016/j.vehcom.2017.10.003 |
| [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. DOI:10.1109/ACCESS.2019.2923840 |
| [3] | BEKMEZCI, SAHINGOZ O K, TEMEL ?. Flying ad-hoc networks (FANETs): A survey[J]. Ad Hoc Networks, 2013, 11(3): 1254-1270. DOI:10.1016/j.adhoc.2012.12.004 |
| [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. DOI:10.3969/j.issn.1001-506X.2018.10.27 (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. DOI:10.1007/s11277-018-5321-5 |
| [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. DOI:10.1109/ACCESS.2018.2875679 |
| [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. DOI:10.1007/s10898-010-9526-8 |
| [14] | LLOYD E L, XUE G L. Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers, 2007, 56(1): 134-138. DOI:10.1109/TC.2007.250629 |
| [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] | KARABOGA D. An idea based on honey bee swarm for numerical optimization[C]//2013 International Conference on Computing, Management and Tececommunications, 2013: 49-54. |
