基于Voronoi图-麻雀算法的中继无人机任务规划

谭 威， 胡永江， 张小孟， 赵月飞， 李文广

(1.陆军工程大学石家庄校区，石家庄 050000； 2.中国人民解放军31700部队，辽宁 辽阳 111000)

0 引言

复杂的战场环境中，战机稍纵即逝，因此在完成“情报侦察-摧毁打击”任务时，就需要快速衔接好侦察无人机(Surveillance UAV，SUAV)、打击无人机(Combat UAV，CUAV)及地面控制站(Ground Control Station,GCS)，实现作战节点间信息的及时交互[1-2]。在现代战争中，单无人机、单类型无人机作战能力有限，且容易被敌方摧毁，因此多无人机协同作战已成为趋势。为有效扩大多无人机作战范围，加强多无人机作战能力，协调好空空、空地、地地作战进程，就需要信息情报交流，以整体战场态势为重点、通盘考虑战场全局，利用高效的纵深情报，突出我方优势，击敌劣势，我方能够相互依靠、相互支援、共同进退，从而使得多无人机作战发挥出“1+1>2”的作战效能。

中继无人机任务规划指的是通过在作战区域部署中继无人机，作为各类型的无人机及无人机与地面控制站的信息交互中心，实现战场空间内多维作战力量的实时通信[3-4]。任务规划是多无人机相互协同完成任务的关键技术，主要分为任务分配和航迹规划[5-7]。中继无人机任务规划需要根据中继无人机与重点目标的距离约束及地面测控站与无人机基地的位置信息，以部署最少中继无人机数量及中继无人机安全为目标，完成中继无人机任务分配及部署。

现阶段，国内外对中继无人机部署问题已经有了一定的研究。文献[8]研究了战场紧急情况下的全局通信问题，可有效部署中继无人机通信节点并满足战场通信需求；文献[9]提出了一种基于贪婪算法和粒子群算法的任务关键型构建算法，该算法能通过将多个任务分配给一定数量的中继无人机，从而确定中继节点的位置，但在部署通信节点时，未考虑最少化中继无人机数量和中继无人机安全需求；文献[10]研究了多速率通信系统中中继节点的最佳位置，验证了根据地面节点与中继无人机高度之间的距离，可以选择比中心位置更好的位置来实现最大吞吐量；文献[11]研究了中继无人机充当移动中继节点的无人机部署问题，主要分析了系统的吞吐量最大化及无人机中继网络部署的可靠性；文献[12]提出了一种中继无人机快速部署策略，能够得到最少中继无人机节点的部署方案，但没有结合战场实际威胁，需要加强中继无人机自身的安全防护。现有的规划方法中，在构建全局中继通信网络时，对中继无人机安全部署方面研究不多，且求解精度有待提高。在实际战场运用时，应注重中继节点的安全部署并提高部署效率。现有方法大多都是单地面控制站基地，在实际运用中，控制站应随着战场态势有适当的变化，并应考虑备选地面控制站基地情况，注重结合战场实际进行中继节点的安全部署问题。

本文主要研究了一种基于Voronoi图-麻雀(Voronoi- Sparrow Search Algorithm，V-SSA)算法的中继无人机安全有效的分配部署策略。为实现中继无人机的科学部署，以最少中继节点数量和距离重要目标最远为目标函数，建立最优化模型，采用V-SSA算法来实现问题的求解，优化调整中继节点部署位置。仿真结果表明，V-SSA算法得到了满足目标函数的最优中继无人机部署方案，相比于V-GA算法和V-PSO算法，在性能上有了一定的提升。

1 中继无人机安全部署建模

1.1 问题描述

在作战区域内，存在若干个敌目标及敌雷达等威胁点，需要完成对敌目标进行先侦察、再精确打击摧毁任务。而在执行任务时，因为存在有效通信距离限制，故需要有效、合理地部署通信中继无人机进行辅助通信，将地面控制站和整个作战区域内执行任务的无人机进行有效联通。在图1中展示了中继无人机部署的任务场景。

图1 任务场景图Fig.1 Mission scenario graph

表1汇总了3类节点的相关信息。

表1 3类节点信息Table 1 Information of three types of nodes

本次任务可分为两大类无人机，即中继无人机(Relay Unmanned Aerial Vehicle，RUAV)和任务无人机(Mission UAV，MUAV)。主要有CUAV，SUAV，中继无人机的通信半径为d0，数量为NR。

本文所建立模型的前提及假设如下：1) 中继无人机性能良好,均在航程内飞行;2) 在假设的中继范围内均认为可以建立通信联络。

1.2 Voronoi图

Voronoi图[13-14]以几何学方法为依据，能够有效将地理信息中点对象和区域以拓扑结构表示出来。在中继无人机领域应用时，因其具有很好的全局规划特性而被广泛用于相关问题的求解，因此，本文采用Voronoi图来生成任务环境空间。中继无人机的位置被限制于Voronoi图的边界上，以降低问题复杂度，提高求解速度和求解精度。

采用Voronoi图后可以获得点与边的集合，这些集合可以被表示为

(1)

式中：T为目标集合;P为威胁源的集合;V为Voronoi图的顶点集合；E为Voronoi图边集。从V中的节点指向T中的节点，表示所有可能的路径。

1.3 决策变量

本文中的决策变量为NR架无人机中，表示每架无人机是否被部署的Zi，Zi∈{1,0}，其部署的位置为(xi,yi)，其中，i∈{1,2，…，NR}，中继无人机所在的节点为Y={Y1,Y2，…，YNR}。

1.4 约束条件

设本文考虑的有以下约束。

无人机仅能部署在Voronoi图生成的边上。对于第i架中继无人机，有且仅能部署在一条边上。令Ai j表示第i架中继无人机是否部署在第j条边上，则应满足约束

(2)

最多仅有N架中继无人机被使用，即

(3)

满足中继无人机的通信范围限制，为确保各中继无人机能够中继通信，直接相互联通的通信中继节点之间的距离应符合

(4)

式中：d(Yi,Yj)为节点i和j之间的欧氏距离;d0是无人机的覆盖范围，即通信半径。

为确保无人机飞行的安全，无人机之间需限定一定的安全间隔，所以，中继节点之间的最小安全距离为

mind(Yi,Yj)≥dsf

(5)

式中,dsf为无人机间的最小安全距离，安全距离dsf必须远小于d0。

当然，重要目标点必须在覆盖中继无人机的通信范围内，即

mind(Y,Pi)≤d0。

(6)

1.5 目标函数

在使用无人机作战时，通过部署最佳的无人机数目，降低无人机的总通信能耗，单次任务中出动的无人机数量越少，行动的效费比就越高。本文的中继无人机部署模型有两个目标，分别为以中继无人机数量最少以及距离重点目标的距离最远(即总距离最大)。

为了保证安全，中继无人机需要在覆盖重要目标的同时使自身与目标的距离最远。该目标J1可以表示为

(7)

式中，W(Yi,Pj)表示无人机i是否覆盖了节点j，如是则为1，否则为0。此外，有效中继无人机数量n可表示为

(8)

综上所述，结合有效通信距离约束、安全距离约束等条件，基于最少中继节点的部署模型的目标函数为

(9)

其约束条件为

(10)

2 Voronoi图-麻雀算法基本原理

2.1 基本麻雀搜索算法

麻雀搜索算法(SSA)[15-16]由薛建凯于2020年提出，具有收敛速度快、调整参数少等特点。

设麻雀集合矩阵为

(11)

式中:N是麻雀的规模；i=1,2,…,N;d是变量的维数。

麻雀的适应度值矩阵表示为

Fx=(f(x1)f(x2)…f(xN))T

(12)

f(xi)=(f(xi,1)f(xi,2)…f(xi,d))

(13)

其中，Fx为个体的适应度值。适应度值更优的麻雀能够率先得到食物，并作为发现者，引领其他麻雀靠近食物源。发现者位置的更新算式为

(14)

(15)

侦察预警行为：种群觅食时，会选取部分麻雀负责侦察，随机选取SSD(一般取10%～20%)只麻雀进行预警行为。其位置更新算式为

(16)

2.2 基于Voronoi图的编码方式

Voronoi图能够有效地将地理信息中的点、对象和区域以拓扑结构表示出来，并能通过这些拓扑关系表示自然语言中的定性关系和模糊地理信息[17]。在通过卫星确定了危险区域后，根据危险区域，在平面内就可以划分成距离各个点或者实体一定距离的凸网，其距离可以根据具体情况设置。这个凸网称为Voronoi图，Voronoi图各边即为UAV可通行的安全路径。

本文编码方式为实数编码，由两部分构成，分别是Voronoi图生成的每个可通行路径的优先级Pr以及中继点位置系数R，即

(17)

式中，NP为可通行路径的数量。该编码方式可以将约束的处理从初始解生成，转移到解码流程中，避免在新解生成时的约束处理以及错误修正。这种方法可以有效降低算法设计和运行的复杂度，同时避免错误修正时造成的信息损失。

2.3 基于Voronoi图的解码方式

由于本文并未直接决策变量作为编码，需要通过解码，将编码转化为决策变量并计算适应度函数值。解码流程如下。

1) 根据优先级，将所有Voronoi图生成的每个可通行路径进行排序，按照排序后的顺序S依次操作。

2) 令i=1。

3) 对于第S(i)条子路径，设当前子路径的两个端点为N1，N2，则中继点位置为

Nz=R(N1-N2)+N2

(18)

4) 计算当前中继点和其他目标点的距离，判断其可覆盖的目标点数量。

5) 如果新设中继点在当前位置，可以增加可覆盖的目标点数量，则该中继点位置保存。

6) 如果所有目标点均被覆盖，则前往7)，否则i=i+1，并前往3)。

7) 计算目标函数。

2.4 算法流程

本文所研究的V-SSA算法流程如图2所示。

图2 V-SSA算法流程图Fig.2 Flow chart of V-SSA algorithm

1) 初始化种群参数，如种群数量N，最大迭代次数，发现者比例PPD，侦察者比例SSD等。

2) 求解个体适应度值，从中选取最优、最差适应度值，并得到其所对应的位置。

3) 在适应度值较优的麻雀中，选择部分麻雀作为发现者，并按照式(14)更新位置。

4) 剩余麻雀作为跟随者，并按照式(15)更新位置。

5) 随机选择部分麻雀作为侦察者，并按式(16)进行位置更新。

6) 判断，若满足结束条件，则进行7)，否则跳转到2)。

7) 结束，输出最优结果。

3 仿真实验

仿真实验平台为AMD Ryzen 5 3500U/8 GiB/64位Windows10操作系统的华为荣耀MagicBook2019笔记本电脑。编程工具为MatlabR2016b(64位)。

3.1 仿真参数设置

仿真实验参数设置如表2所示。

表2 实验参数设置Table 2 Experimental parameters setting

3.2 仿真内容及结果分析

为了验证本文所提算法，设置了2个仿真实验。实验1主要验证本文算法有效性，能否得到覆盖目标的中继无人机部署方案；实验2进行对比实验，验证本文算法的性能情况。

3.2.1 实验1

本文假设有3个重要目标、8个安全阵地(中继无人机基地、GCS基地)、57个敌威胁点，均需要被中继无人机通信网络覆盖，以便执行任务时各任务小组互联互通。图3中仿真了中继节点部署情况。表3中列出需要被通信覆盖的位置坐标，其中，类型1为重要目标，类型2为安全阵地，类型3为敌威胁点。

图3 中继节点部署图Fig.3 Deployment of relay nodes

表3 任务节点位置坐标Table 3 Coordinates of mission nodes

现将实验结果分析如下。

1) 由图3可知，3个重要目标、8个安全阵地(中继无人机基地、GCS基地)、57个敌威胁点都在RUAV的有效通信覆盖范围内，并且每个RUAV节点都可以直接或间接地与GCS及备用GCS基地进行数据链路通信，说明了本文算法的有效性。

2) 利用本文的SSA算法能够对中继节点的安全部署问题进行有效求解，并可得到最小中继无人机的数量及其对应位置信息，能够满足战场全局通信要求，说明了本文算法的可行性。

3.2.2 实验2

在相同目标和测控系统属性的情况下，对比V-GA算法、V-PSO算法和V-SSA算法中继节点部署情况。在V-PSO算法中，将种群规模设为100，最大迭代次数设为100，认知参数和社会参数分别设0.7和1.4；V-GA算法中，将种群规模设为100，最大迭代次数设为100，交叉和变异概率分别设0.85和0.2。

假设作战区域内有68个需要通联的不同类型目标(如表3所示)，在相同目标规模下，用V-GA算法、V-PSO算法和V-SSA算法各进行仿真实验100次，记录中继节点数量并取其平均值，统计结果如表4所示，并各记录一次中继节点部署结果，分别见图4～6。

表4 中继节点平均数量表Table 4 Average number of relay nodes

图4 V-GA算法中继节点部署图Fig.4 Relay node deployment diagram of V-GA algorithm

图5 V-PSO算法中继节点部署图Fig.5 Relay node deployment diagram of V-PSO algorithm

图6 V-SSA算法中继节点部署图Fig.6 Relay node deployment diagram of V-SSA algorithm

结果分析如下。

1) 由图4～6可得，所有的TUAV节点都在RUAV节点的有效通信覆盖范围之内，并且每个RUAV节点都可以直接或通过别的RUAV节点与GCS进行数据链路通信，说明3种算法都能够建立有效的链路通信。

2) 由表4可知:在建立有效全局通信网络的情况下，V-GA算法求解得到的中继无人机数量平均为13，V-PSO算法求解得到的中继无人机数量为12，V-SSA算法求解得到的中继无人机数量为11;在重点目标总距离上，V-SSA算法为957.614 7 km，比V-GA算法提升了7%，比V-PSO算法提升了4%，说明V-SSA算法得到的中继无人机部署位置离重点目标更远，受到的威胁相对更小，中继无人机安全性更高。

4 总结

本文提出了一种基于V-SSA算法的中继无人机有效安全部署策略，并验证了所提出的航迹规划算法能够有效解决中继无人机部署方案无法满足最少数量要求及中继无人机安全性等问题，主要得到以下结论：本文提出的V-SSA算法实现了节点间可行链路的有效搜索，能够得到覆盖所有目标的中继无人机部署方案；V-SSA算法相比于V-GA算法和V-PSO算法解得的部署方案中继无人机数量最少，距离重点目标的距离最远，中继无人机安全性更高。