对抗环境下无人机协同中继网络快速构建方法和系统

摘要

本发明提供了一种对抗环境下无人机协同中继网络快速构建方法和系统，基于构建的无向图获取从源节点到目标节点的所有最短路径；再计算所有可用无人机从初始位置到达备选布置点的飞行时长集合，并获取其中的最小值以及对应的可用无人机，重复执行上述步骤，得到最小值集合，确定最大值对应的备选布置点和可用无人机；对最短路径中的备选布置点和无人机集合进行更新，再重复执行，得到最短路径对应的无人机选择方案，并获取该无人机选择方案中无人机对应的最大飞行时长，将可用无人机集合恢复初始化后，重复执行上述步骤，得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络。实现无人机使用数量最少，用时最短。

权利要求

1.一种对抗环境下无人机协同中继网络快速构建方法，其特征在于，该方法包括：S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；所述通信链接关系矩阵C为：C＝[cij](|X|+2)×(|X|+2)(0≤i,j≤|X|+1)其中，|X|表示可行布置点集合X中可行布置点数目；x0表示源节点s，x|X|+1表示目标节点t，cij＝1时，表示xi和xj之间存在视线路径且距离小于等于无人机最大通信距离dmax；

S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除，以对最短路径pi和可用无人机集合U进行更新；

S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

S8、使可用无人机集合U恢复初始化；

S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

2.如权利要求1所述的一种对抗环境下无人机协同中继网络快速构建方法，其特征在于，所述基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X包括：S1‑1、获取源节点s、目标节点t、战场区域D、无人机最大通信距离dmax、地形障碍覆盖区域Y、敌方防空威胁覆盖区域Z、无人机初始位置S1‑2、基于无人机最大通信距离dmax将战场区域D离散化，得到离散点集合 其中离散点的间距γ≤dmax；

S1‑3、基于地形障碍覆盖区域Y计算离散化的地形障碍覆盖区域Y′＝Y∩D′，再基于敌方防空威胁覆盖区域Z，计算离散化的敌方防空威胁覆盖区域Z′＝Z∩D′；

S1‑4、基于离散化的地形障碍覆盖区域Y′、离散化的敌方防空威胁覆盖区域Z′以及离散点集合D′，得到可行布置点集合X＝{xi}＝D'‑Y'∪Z'(1≤i≤|X|)。

3.如权利要求1所述的一种对抗环境下无人机协同中继网络快速构建方法，其特征在于，所述S3中，无向图G＝(V,E,W)中的V＝X∪{s,t}，E＝{eij|cij＝1}(0≤i,j≤|X|+1)，W＝{wij＝1|cij＝1}。

4.如权利要求1所述的一种对抗环境下无人机协同中继网络快速构建方法，其特征在于，所述S4中获取所有最短路径的算法采用基于Dijkstra算法改进的多条最短路径算法。

5.如权利要求1所述的一种对抗环境下无人机协同中继网络快速构建方法，其特征在于，所述S5中计算所有可用无人机从初始位置到达备选布置点 的飞行时长，包括：若满足 且 即可用无人机初始位置 到备选布置点

间存在视线路径，则 其中， 为从 到 的欧式距离， 表示

到 的视线路径，v为无人机的飞行速度；

若不满足 且 即可用无人机初始位置 到备选布置

点 间不存在视线路径，则通过Floyd算法计算可用无人机初始位置 到备选布置点 间的最短到达时间作为无人机的飞行时间

6.一种对抗环境下无人机协同中继网络快速构建系统，其特征在于，所述系统包括计算机，所述计算机包括：至少一个存储单元；

至少一个处理单元；

其中，所述至少一个存储单元中存储有至少一条指令，所述至少一条指令由所述至少一个处理单元加载并执行以实现以下步骤：S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；所述通信链接关系矩阵C为：C＝[cij](|X|+2)×(|X|+2)(0≤i,j≤|X|+1)其中，|X|表示可行布置点集合X中可行布置点数目；x0表示源节点s，x|X|+1表示目标节点t，cij＝1时，表示xi和xj之间存在视线路径且距离小于等于无人机最大通信距离dmax；

S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除，以对最短路径pi和可用无人机集合U进行更新；

S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

S8、使可用无人机集合U恢复初始化；

S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

说明书

对抗环境下无人机协同中继网络快速构建方法和系统

技术领域

[0001] 本发明涉及无人机技术领域，具体涉及一种对抗环境下无人机协同中继网络快速构建方法和系统。

背景技术

[0002] 为了满足信息战的需求，在战场的对抗环境下，需要使用无人机作为中继节点，在源节点s和目标节点t之间构建有效的中继网络。

[0003] 航空学报,2017,38(11):236‑248，公开了《一种基于多无人机的中继节点布置问题建模与优化方法》，该方法先基于中继无人机安全性约束、通信链路有效性约束、中继无人机唯一性约束对问题进行建模，并通过对待搜索的空间进行离散化处理，使得问题由连续的混合整数规划问题变为可解的离散整数规划问题，并对于上述模型对应的问题的求解设计了求解算法，在求解算法的第一步中，先基于广度优先搜索算法从所有可行布置点中选择出满足最少中继无人机数量要求的所有可能的布置点，在第二步中，在第一步得到的所有可能的布置点的基础上，再计算出所有唯一布置点，最后通过贪婪策略优先满足最难以到达的布置点来减小构建中继网络花费的时间。最终在能够通信的前提下，达到了构建中继网络中使用的无人机数量尽可能少，同时构建花费的时间尽可能短的目的。

[0004] 但现有的方案在实际应用时，经算法计算得到的中继网络是局部最优解，存在中继网络构建时长较长的问题。

发明内容

[0005] (一)解决的技术问题

[0006] 针对现有技术的不足，本发明提供了一种对抗环境下无人机协同中继网络快速构建方法和系统，解决了通过现有技术得到的中继网络构建时长较长的问题，实现了中继网络中使用的无人机数量尽可能少，同时构建花费的时间尽可能短的目的。

[0007] (二)技术方案

[0008] 为实现以上目的，本发明通过以下技术方案予以实现：

[0009] 一种对抗环境下无人机协同中继网络快速构建方法，该方法包括：

[0010] S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

[0011] S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；

[0012] S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

[0013] S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

[0014] S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

[0015] S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除；

[0016] S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

[0017] S8、使可用无人机集合U恢复初始化；

[0018] S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

[0019] 进一步的，所述基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X包括：

[0020] S1‑1、获取源节点s、目标节点t、战场区域D、无人机最大通信距离dmax、地形障碍覆盖区域Y、敌方防空威胁覆盖区域Z、无人机初始位置

[0021] S1‑2、基于无人机最大通信距离dmax将战场区域D离散化，得到离散点集合其中离散点的间距γ≤dmax；

[0022] S1‑3、基于地形障碍覆盖区域Y计算离散化的地形障碍覆盖区域Y′＝Y∩D′，再基于敌方防空威胁覆盖区域Z，计算离散化的敌方防空威胁覆盖区域Z′＝Z∩D′；

[0023] S1‑4、基于离散化的地形障碍覆盖区域Y′、离散化的敌方防空威胁覆盖区域Z′以及离散点集合D′，得到可行布置点集合X＝{xi}＝D'‑Y'∪Z'(1≤i≤|X|)。

[0024] 进一步的，所述S2中通信链接关系矩阵C为：

[0025]

[0026] 其中，|X|表示可行布置点集合X中可行布置点数目；x0表示源节点s，x|X|+1表示目标节点t，cij＝1时，表示xi和xj之间存在视线路径且距离小于等于无人机最大通信距离dmax。

[0027] 进一步的，所述S3中，无向图G＝(V,E,W)中的V＝X∪{s,t}，E＝{eij|cij＝1}(0≤i,j≤|X|+1)，W＝{wij＝1|cij＝1}。

[0028] 进一步的，所述S4中获取所有最短路径的算法采用基于Dijkstra算法改进的多条最短路径算法。

[0029] 进一步的，所述S5中计算所有可用无人机从初始位置到达备选布置点 的飞行时长，包括：

[0030] 若满足 且 即可用无人机初始位置 到备选布置点 间存在视线路径，则 其中， 为从 到 的欧式距离， 表
示 到 的视线路径，v为无人机的飞行速度；

[0031] 若不满足 且 即可用无人机初始位置 到备选布置点 间不存在视线路径，则通过Floyd算法计算可用无人机初始位置 到备选布置点间的最短到达时间作为无人机的飞行时间

[0032] 一种对抗环境下无人机协同中继网络快速构建系统，所述系统包括计算机，所述计算机包括：

[0033] 至少一个存储单元；

[0034] 至少一个处理单元；

[0035] 其中，所述至少一个存储单元中存储有至少一条指令，所述至少一条指令由所述至少一个处理单元加载并执行以实现以下步骤：

[0036] S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

[0037] S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；

[0038] S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

[0039] S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

[0040] S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

[0041] S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除；

[0042] S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

[0043] S8、使可用无人机集合U恢复初始化；

[0044] S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

[0045] (三)有益效果

[0046] 本发明提供了一种对抗环境下无人机协同中继网络快速构建方法和系统。与现有技术相比，具备以下有益效果：

[0047] 本发明基于构建的无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径，以得到所有满足使用最少无人机要求的最短路径；再计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值以及对应的可用无人机，重复执行上述步骤，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，可得到最短路径对应的最难到达布置点以及对应的最优选的无人机和飞行时间；对最短路径中的备选布置点和无人机集合进行更新，再重复执行，为下一个备选布置点分配可用无人机，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 将可用无人机集合U恢复初始化后，重复执行上述步骤，对下一个最短路径的无人机选择方案以及对应的网络构建时长进行确定，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，该最短路径对应有一个无人机选择方案，该最短路径对应的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案中的无人机作为中继无人机，该无人机选择方案中的无人机的飞行时间最大值即为中继网络搭建所需的时间。最终构建的中继网络即能满足构建中继网络的无人机使用数量最少，又保证了构建中继网络的用时最短。

附图说明

[0048] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0049] 图1为本发明实施例的流程图；

[0050] 图2为本发明实施例中实验1中使用现有技术的算法得到的计算结果示意图；

[0051] 图3为本发明实施例中实验1中使用本发明的算法得到的计算结果示意图；

[0052] 图4为本发明实施例中实验2中使用现有技术的算法得到的计算结果示意图；

[0053] 图5为本发明实施例中实验2中使用本发明的算法得到的计算结果示意图；

[0054] 图6为本发明实施例中实验3中使用现有技术的算法得到的计算结果示意图；

[0055] 图7为本发明实施例中实验3中使用本发明的算法得到的计算结果示意图。

具体实施方式

[0056] 为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0057] 本申请实施例通过提供一种对抗环境下无人机协同中继网络快速构建方法和系统，解决了通过现有技术得到的中继网络构建时长较长的问题，实现了中继网络中使用的无人机数量尽可能少，同时构建花费的时间尽可能短的目的。

[0058] 本申请实施例中的技术方案为解决上述技术问题，总体思路如下：

[0059] 基于构建的无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径，以得到所有满足使用最少无人机要求的最短路径；再计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值以及对应的可用无人机，重复执行上述步骤，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，可得到最短路径对应的最难到达布置点以及对应的最优选的无人机和飞行时间；对最短路径中的备选布置点和无人机集合进行更新，再重复执行，为下一个备选布置点分配可用无人机，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 将可用无人机集合U恢复初始化后，重复执行上述步骤，对下一个最短路径的无人机选择方案以及对应的网络构建时长进行确定，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，该最短路径对应有一个无人机选择方案，该最短路径对应的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案中的无人机作为中继无人机，该无人机选择方案中的无人机的飞行时间最大值即为中继网络搭建所需的时间。最终构建的中继网络即能满足构建中继网络的无人机使用数量最少，又保证了构建中继网络的用时最短。

[0060] 为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

[0061] 实施例1：

[0062] 如图1所示，一种对抗环境下无人机协同中继网络快速构建方法，该方法由计算机执行，该方法包括：

[0063] S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

[0064] S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；

[0065] S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

[0066] S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

[0067] S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

[0068] S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除；

[0069] S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

[0070] S8、使可用无人机集合U恢复初始化；

[0071] S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

[0072] 本发明实施例有益效果为：

[0073] 本发明基于构建的无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径，以得到所有满足使用最少无人机要求的最短路径；再计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值以及对应的可用无人机，重复执行上述步骤，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，可得到最短路径对应的最难到达布置点以及对应的最优选的无人机和飞行时间；对最短路径中的备选布置点和无人机集合进行更新，再重复执行，为下一个备选布置点分配可用无人机，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 将可用无人机集合U恢复初始化后，重复执行上述步骤，对下一个最短路径的无人机选择方案以及对应的网络构建时长进行确定，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，该最短路径对应有一个无人机选择方案，该最短路径对应的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案中的无人机作为中继无人机，该无人机选择方案中的无人机的飞行时间最大值即为中继网络搭建所需的时间。最终构建的中继网络即能满足构建中继网络的无人机使用数量最少，又保证了构建中继网络的用时最短。

[0074] 下面对本发明实施例的详细实现方法进行说明：

[0075] S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；具体包括如下步骤：

[0076] S1‑1、获取源节点s、目标节点t、战场区域D、无人机最大通信距离dmax、地形障碍覆盖区域Y、敌方防空威胁覆盖区域Z、无人机初始位置

[0077] 无人机最大通信距离约束：假设无人机的通信能力相同，且最大通信距离有限，记为dmax，令||xi,xj||表示可行布置点xi和可行布置点xj之间的欧式距离，则有：

[0078] ||xi,xj||≤dmax；

[0079] S1‑2、基于无人机最大通信距离dmax将战场区域D离散化，得到离散点集合其中离散点的间距γ≤dmax，例如γ≤0.25dmax；

[0080] 地形障碍约束和敌方防空威胁约束：为了保证无人机安全，同时也是为了保证中继网络持续可靠工作，首先要求可行布置点避开地形障碍和敌方防空威胁覆盖区域，即：

[0081]

[0082]

[0083] S1‑3、基于地形障碍覆盖区域Y计算离散化的地形障碍覆盖区域Y′＝Y∩D′，再基于敌方防空威胁覆盖区域Z，计算离散化的敌方防空威胁覆盖区域Z′＝Z∩D′；

[0084] S1‑4、基于离散化的地形障碍覆盖区域Y′、离散化的敌方防空威胁覆盖区域Z′以及离散点集合D′，得到可行布置点集合X＝{xi}＝D'‑Y'∪Z'(1≤i≤|X|)，从1开始编号。

[0085] S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；

[0086] 具体的，用矩阵 表示可行布置点间通信链接关系，即：

[0087]

[0088] 特别地，令x0表示源节点s，则s与可行布置点xi(1≤i≤|X|)之间的通信链接关系为：

[0089]

[0090] 类似地，令x|X|+1表示目标节点t，则t与可行布置点xi(1≤i≤|X|)之间的通信链接关系为：

[0091]

[0092] 因此，可行布置点xi(1≤i≤|X|)、源节点s和目标节点t之间的通信链接关系可以表示为：

[0093]

[0094] 其中，|X|表示可行布置点集合X中可行布置点数目；x0表示源节点s，x|X|+1表示目标节点t，cij＝1时，表示xi和xj之间存在视线路径且距离小于等于无人机最大通信距离dmax。

[0095] S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；其中V＝X∪{s,t}，E＝{eij|cij＝1}(0≤i,j≤|X|+1)，W＝{wij＝1|cij＝1}。

[0096] S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

[0097] 其中，获取所有最短路径采用现有的基于Dijkstra算法改进的多条最短路径算法；具体可参考：哈尔滨工业大学学报，2010年9月，第42卷，第9期《，具有多条最短路径的最短路问题》。

[0098] S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；例如可用无人机共有N个，对于最短路径pi中的第一个备选布置点 飞行时长集合 中记录有所有可用无人机飞行至第一个备选布置点的飞行时长，例如，若N＝5， 则最小值为44s，表示该备选布置点为中继节点时，最优选的可用无人机为第5个可用无人机，且该最优选的可用无人机到从初始位置到达该备选布置点所需的时间为44s。

[0099] 其中，为了降低计算 的难度和不失研究重点，假设无人机飞行速度相同且不考虑无人机动力学特性基础上，从无人机初始位置 到备选布置点 的最短飞行路径包括两种情形：

[0100] ①从 到 不穿越任何类型障碍和威胁覆盖区域的视线路径；

[0101] ②由于 到 的视线路径上存在地形障碍或敌方防空威胁而进过其他可行布置点的折线路径。

[0102] 令 则所有可用无人机从初始位置到达备选布置点 的飞行时长的具体计算步骤如下：

[0103] 若满足 且 即可用无人机初始位置 到备选布置点 间存在视线路径，则 其中， 为从 到 的欧式距离，
表示 到 的视线路径，v为无人机的飞行速度；

[0104] 若不满足 且 即可用无人机初始位置 到备选布置点 间不存在视线路径，则通过Floyd算法计算可用无人机初始位置 到备选布置点间的最短到达时间作为无人机的飞行时间

[0105] S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，考虑到中继网络构建的时间由最后到达的无人机决定，因此需要满足最难到达布置点优先规则，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，此时得到备选布置点即为最难到达布置点以及对应的最优选的无人机和飞行时间。并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除，对最短路径pi和可用无人机集合U进行更新。

[0106] S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 Rpi即为该最短路径对应的最优选无人机，考虑到中继网络构建的时间由最后到达的无人机决定，因此需要满足最难到达布置点优先规则，因此获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；完成一个最短路径的无人机选择方案的确定。

[0107] S8、使可用无人机集合U恢复初始化；

[0108] S9、重复执行S5‑S8，对下一个最短路径的无人机选择方案进行确定，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，该最短路径对应的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案中的无人机作为中继无人机。

[0109] 通过进行多组仿真实验来验证本发明实施例的计算结果与现有计算的计算结果的差异：

[0110] 电脑配置：

[0111] Lenovo ThinkPadX1 Carbon 5th Signature Edition

[0112] CPU：intel i7‑7500U主频2.7Ghz

[0113] RAM：8GB

[0114] 操作系统：Win1064位操作系统

[0115] 软件：Visual Studio 2013

[0116] 实验条件：

[0117] 仿真区域长度：30000m

[0118] 仿真区域宽度：30000m

[0119] 可行布置点间距：2000m

[0120] 无人机通信范围：8000m

[0121] 地形障碍数量：2

[0122] 防空威胁数量：1

[0123] 无人机数量：10

[0124] 无人机飞行速度：50m/s

[0125] 待中继源节点的x、y：s(0,0)

[0126] 待中继目标节点的x、y：t(30000,30000)

[0127] 可用无人机的初始位置(x、y)：

[0128] u1(6000,6000),

[0129] u2(16000,4000),

[0130] u3(2000,16000),

[0131] u4(24000,6000),

[0132] u5(10000,8000),

[0133] u6(12000,2000),

[0134] u7(12000,18000),

[0135] u8(2000,30000),

[0136] u9(2000,26000),

[0137] u10(6000,2000),

[0138] 如表1‑表6所示，圆形区域表示地形障碍和防空威胁具体范围和位置。如图2‑图7所示，“×”符号表示可用无人机的初始位置，“+”表示选取的中继布置点，中继布置点与可用无人机之间的虚线段表示飞行路径，且该可用无人机被选取为中继无人机。

[0139] 实验1：

[0140] 表1

[0141]

[0142] 表2

[0143]

[0144] 实验结果：如图2‑图3

[0145] 现有技术的算法：中继无人机数量为5，从s至t依次选择的可用无人机为u10、u5、u1、u3、u7，构建中继网络所需的时间为341.76秒。

[0146] 本发明实施例的算法：中继无人机数量为5，选取的可用无人机为u1、u3、u5、u4、u7，构建中继网络所需的时间为291.415秒。

[0147] 实验2：

[0148] 表3

[0149]

[0150] 表4

[0151]

[0152] 实验结果：如图4‑图5

[0153] 现有技术的算法：中继无人机数量为5，从s至t依次选择的可用无人机为u1、u6、u2、u5、u7，构建中继网络所需的时间为312.41秒。

[0154] 本发明实施例的算法：中继无人机数量为5，从s至t依次选择的可用无人机为u1、u2、u5、u4、u7，构建中继网络花费的时间为291.415秒。

[0155] 实验3：

[0156] 表5

[0157]

[0158]

[0159] 表6

[0160]

[0161] 实验结果：如图6‑图7

[0162] 现有技术的算法：中继无人机数量为5，从s至t依次选择的可用无人机为u10、u1、u2、u5、u7；构建中继网络花费的时间为312.41秒。

[0163] 本发明实施例的算法：中继无人机数量为5，从s至t依次选择的可用无人机为u10、u1、u5、u4、u7；构建中继网络花费的时间为292.982秒。

[0164] 综上所述，相比于现有技术，本发明实施例的有益效果：

[0165] 本发明基于构建的无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径，以得到所有满足使用最少无人机要求的最短路径；再计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值以及对应的可用无人机，重复执行上述步骤，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，可得到最短路径对应的最难到达布置点以及对应的最优选的无人机和飞行时间；对最短路径中的备选布置点和无人机集合进行更新，再重复执行，为下一个备选布置点分配可用无人机，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 将可用无人机集合U恢复初始化后，重复执行上述步骤，对下一个最短路径的无人机选择方案以及对应的网络构建时长进行确定，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，该最短路径对应有一个无人机选择方案，该最短路径对应的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案中的无人机作为中继无人机，该无人机选择方案中的无人机的飞行时间最大值即为中继网络搭建所需的时间。相比与现有技术中的算法，构建计算得到的中继网络所需的时间更短，且使用的无人机数量相同，即能满足构建中继网络的无人机使用数量最少，又保证了构建中继网络的用时最短。

[0166] 实施例2

[0167] 本发明还提出一种对抗环境下无人机协同中继网络快速构建系统，所述系统包括计算机，所述计算机包括：

[0168] 至少一个存储单元；

[0169] 至少一个处理单元；

[0170] 其中，所述至少一个存储单元中存储有至少一条指令，所述至少一条指令由所述至少一个处理单元加载并执行以实现以下步骤：

[0171] S1、基于无人机最大通信距离约束对战场区域进行离散化处理，并基于地形障碍约束和敌方防空威胁约束得到所有可行布置点集合X＝{x1,…,xi,xj,…xk}；其中xi、xj表示相邻的两个可行布置点，k表示可行布置点的数量；

[0172] S2、基于源节点s、目标节点t、无人机最大通信距离约束以及可行布置点集合X得到通信链接关系矩阵C；

[0173] S3、基于通信链接关系矩阵C构建无向图G＝(V,E,W)；

[0174] S4、基于无向图G＝(V,E,W)获取从源节点s到目标节点t的所有最短路径的集合P＝{p1,…,pi,…,pn}；其中，n表示最短路径的总数，pi表示第i个最短路径，表示第i个最短路径中第j个备选布置点，m表示最短路径pi中备选布置点的数量；

[0175] S5、对于任意最短路径pi中的备选布置点 计算所有可用无人机从初始位置到达备选布置点 的飞行时长集合 并获取 中的最小值；

[0176] S6、重复执行S5，直至得到最短路径pi中所有备选布置点对应的最小值集合，从中筛选出最大值，确定最大值对应的备选布置点和可用无人机，并将该备选布置点从最短路径pi中删除，将该可用无人机从可用无人机集合U中删除；

[0177] S7、重复执行S5‑S6，直至最短路径pi中所有备选布置点均分配有一个可用无人机，得到最短路径pi对应的无人机选择方案 并获取该无人机选择方案中无人机对应的最大飞行时长 作为最短路径pi的网络构建时长；

[0178] S8、使可用无人机集合U恢复初始化；

[0179] S9、重复执行S5‑S8，直至得到所有最短路径的网络构建时长；并将网络构建时长最小的最短路径作为中继网络，并将该最短路径中的备选布置点作为中继布置点，以及该最短路径对应的无人机选择方案 中的可用无人机作为中继无人机。

[0180] 可理解的是，本发明实施例提供的对抗环境下无人机协同中继网络快速构建系统与上述对抗环境下无人机协同中继网络快速构建方法相对应，其有关内容的解释、举例、有益效果等部分可以参考对抗环境下无人机协同中继网络快速构建方法中的相应内容，此处不再赘述。

[0181] 需要说明的是，通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

[0182] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0183] 以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。