面向杀伤网构建的多无人节点边缘服务覆盖方法

Multiple Unmanned Nodes Edge Service Coverage Method for Constructing Kill Web

摘要

为应对未来战场无预设战场通信设施条件下为杀伤网构建提供数据采集、通信中继等服务覆盖的问题，基于战场资源分布情况，研究了一种多无人节点边缘服务覆盖方法。首先对通过无人节点为战场资源提供服务覆盖问题进行分析，建立相应的模型；其次对不同资源分布情况下所需无人节点的情况进行分析，设计了一种考虑资源分布情况的近似覆盖算法，重点对算法中孤立点判断、最大团查找、无人节点部署位置确定等问题进行分析；最后通过测试案例对该方法进行测试和验证。结果表明，在资源分布十分分散情况，该方法能够达到最优结果；在资源密集程度较大时，与区域覆盖的结果相当；相较于对比算法，同等情况下该方法所需无人节点数量平均减少了14%到39%，证明该方法可行、有效。

Abstract

To provide data collection and communication relay services for the construction of kill webs in future battlefields without preset communication facilities, a multi-unmanned-nodes edge service coverage method based on resource distribution is studied. Firstly, the problem of providing service coverage for resources via unmanned nodes is analyzed, and a corresponding model is established. Secondly, the situation of unmanned nodes required under different resource distributions is analyzed, and an approximate coverage algorithm considering resource distribution is designed, with foa on isolated points identification maximum, clique searching, unmanned nodes deployment location determination, and soon. Finally, the algorithm is tested and validated by asing test cases. The results obtained indicate that, in cases of highly dispersed resource distribution, the optimal results can be achieved by asing this proposed method. When resource intensity is high, the results are comparable to those of regional coverage. In comparison, the average number of unmanned nodes required in the same situations reduce by 14% to 39%, proving the feasibility and effectiveness of the method.

Graphical abstract

关键词

杀伤网 / 多无人节点 / 服务覆盖 / 最大团

Key words

kill web / multiple unmanned nodes / service coverage / maximum clique

为应对战场上复杂、多变的情况，提升资源生存能力，发挥资源能力优势，“分布式作战”“马赛克战”“杀伤网”等概念被提出，其中一个关键问题是如何将末端资源的数据采集上云，为分散的战场资源提供通信、计算等边缘服务。传统采用有线覆盖、固定基站等方式极大限制了资源的灵活运用，更无法应对无预设基础设施的场景。随着无人机相关技术的发展和突破，通过多无人节点挂载通信、计算等载荷提供边缘服务成为一种可行的方案，如何使用最少的无人节点覆盖所有需要服务的资源点是其关键问题之一。

按照覆盖方式不同，可以分为扫描式覆盖和部署式覆盖^[1]。按照覆盖内容不同，可以分为全域覆盖、目标覆盖、栅栏覆盖^[2]。对于全域覆盖常见方法是使用等边三角形、正方形、正六边形等进行覆盖，如图1所示，其中，正六边形覆盖所需资源最少^[3]。

本文的场景是部署式目标覆盖问题，可等价为固定半径最少圆覆盖（The Minimum Geometric Disk Cover, MGDC）问题^[3]。不同于对整个区域进行覆盖，在面向杀伤网构建中的数据采集、通信中继等场景中^[4]，资源分布较为分散，若对整个区域进行覆盖需要大量无人节点，并且仅部分无人节点发挥作用，会浪费宝贵的资源，问题的核心是对区域内关键资源点进行覆盖。该问题是典型的多项式复杂程度的非确定性（Non-deterministic Polynomial Complete, NPC）问题，无法在多项式时间内给出最优解。文献[3]采用类似区域覆盖的方式来近似求解，先用正六边形对区域进行全域覆盖，再剔除未发挥作用的无人节点。该算法在资源分散时，结果并不理想。文献[5]进一步限定所有待覆盖节点在直线分割平面的同一侧。文献[6-9]则针对不同的具体场景对问题进行了限定和优化。本文针对这一问题，提出了一种考虑待覆盖资源点分布情况的近似覆盖方法，能够在资源分散情况下接近最优的覆盖方案。

1 多无人节点边缘服务覆盖模型

1.1 问题描述

多无人节点边缘服务覆盖，是通过空中多个无人节点为分散的战场资源提供计算、通信等服务覆盖。如图2所示，已知任务区域内分散的资源点位置和无人节点服务覆盖能力范围，问题是通过最少数量的无人节点为所有资源点覆盖提供服务。

1.2 条件假设

为便于问题的理解和求解，首先进行以下合理假设。1）所有需要服务覆盖的资源点位于同一个二维欧式平面；2）所有无人节点携带相同载荷，执行服务覆盖时位于相同高度，其覆盖范围相同；3）无人节点服务覆盖采用二元感知模型^[2]，不考虑其他因素对覆盖能力的影响，将覆盖范围近似为一个圆，如图3所示。

1.3 模型建立

通过上述问题描述和简化假设，可以建立多无人节点边缘服务覆盖问题模型。已知待覆盖资源点和无人节点边缘服务覆盖范围，需要确定使用的无人节点集合（数量及部署位置），为所有资源点提供服务覆盖，无人节点数量尽可能少。据此，可建立该问题的如下模型。

已知待覆盖资源点集合P=\{p_{\mathrm{1}},\cdots ,p_i,\cdots ,p_M\}，i\in \left[\mathrm{1},M\right]。其中：M为资源点数量；p_i=(x_i,y_i)为资源点欧式平面坐标；无人节点边缘服务覆盖范围半径为R。

目标是确定无人节点集合U=\{u_{\mathrm{1}},\cdots ,u_j,\cdots ,u_N\}，

j\in [\mathrm{1},N]。其中：N为无人节点数量；u_j=(x_j,y_j)为无人节点部署位置。

约束条件是要求对于任意资源点p_i，至少存在一个无人节点u_j，使得资源点能够被服务覆盖，即资源点和无人节点之间的欧氏距离：

D_{ij}=\sqrt[]{(x_i-x_j{)}^{\mathrm{2}}+(y_i-y_j{)}^{\mathrm{2}}}\le R

期望的目标是无人节点数量N尽可能小，因此目标函数f=\mathrm{m}\mathrm{i}\mathrm{n}(N)。

2 多无人节点边缘服务覆盖算法

2.1 基本思路

该问题是一个典型的NPC问题，无法在多项式时间内计算其最优解，当问题规模较大时会出现组合爆炸问题。本文近似算法主要基于以下几点考虑。

1）假设资源点1需要服务覆盖，无人节点服务覆盖半径为r，容易发现若要覆盖资源点1，则无人节点需位于以资源点1为圆心、r为半径的圆内（以下简称资源点1的外覆圆），如图4所示。

2）更进一步，假设资源点1、2需要服务覆盖，若资源点1的外覆圆和资源点2的外覆圆相交，如图5所示，则无人节点位于相交区域内时，其服务可同时覆盖资源点1和2；若资源点1和2的外覆圆不相交，则仅用一个无人节点提供服务覆盖，无法同时满足资源点1和2。

3）基于上述考虑，若对所有需服务覆盖资源点作外覆圆，计算其相交情况，则可按照贪心和递归的方法计算得出覆盖所有资源点的最少无人节点数，如图6为5个资源点外覆圆相交情况。

其相交情况见表1。

选择在“1，2，3”相交区部署一个无人节点，则可同时覆盖资源点1、2、3。将已覆盖资源点剔除后如图7所示。

剩余未覆盖资源点相交情况见表2。

剩余资源点4、5，仅需在其相交区域部署一个无人节点，即可完成对所有资源点的服务覆盖。即共需2个无人节点，这也是无人节点最少的方案，如图8所示。

综上，考虑所需覆盖资源点之间的相对位置，能够提升无人节点服务覆盖性价比，据此本文设计了一种多无人节点边缘服务覆盖算法。

2.2 算法流程

算法输入：待覆盖资源点集合（坐标），无人节点覆盖能力范围（覆盖半径）。

算法输出：覆盖所有资源点所需无人节点数量及部署位置。

算法步骤：1）计算所有待覆盖资源点外覆圆之间相交情况，生成相交矩阵；2）查找待覆盖集合中的孤立点，将该点作为覆盖圆心加入集合，并将该点从待覆盖集合中删除；3）以待覆盖集合为点集，外覆圆相交情况作为边，构建连接网络图，并计算最大团；4）根据最大团计算覆盖圆心，将其加入覆盖圆心集合，并将该圆覆盖的资源点从待覆盖集合中删除；5）判断待覆盖集合是否为空，若不为空，则重复步骤2）~步骤4），若为空，则输出覆盖圆心集合作为结果。

详细流程如图9所示。通过算法流程可以发现，算法以所有待覆盖资源点被覆盖作为结束条件，能够保证算法最终收敛。

2.3 算法关键设计

2.3.1 判断相交关系

本文将待覆盖资源点的相交关系定义为：分别以待覆盖的两个资源点位置为圆心、以无人节点覆盖能力范围R为半径作圆，若两圆相交则称待覆盖资源点的外覆圆相交。即已知资源点p_i位置为(x_i,y_i)，p_j位置为(x_j,y_j)，通过计算可得到其欧氏距离：D_{i,j}=\sqrt[]{(x_i-x_j{)}^{\mathrm{2}}+(y_i-y_j{)}^{\mathrm{2}}}，则两点相交情况可根据式（1）判断。

C_{i,j}=\left\{\begin{array}{l}\mathrm{1}, D_{i,j}\le \mathrm{2}r;\\ \mathrm{0}, D_{i,j}>\mathrm{2}r.\end{array}\right.（1）

式中，C_i,j 代表相交情况，取值为1代表外覆圆相交，取值为0代表不相交。

2.3.2 查找孤立点

所谓孤立点是外覆圆与其他所有点的外覆圆都不相交的资源点，如图10中的资源点4。

通过前文分析可知，通过单一的无人节点无法同时为孤立点和其他资源点提供服务覆盖，要为孤立点提供服务覆盖必须新增一个无人节点，据此可以将孤立点进行独立覆盖处理，关键是如何查找发现所有孤立点。

查找孤立点可基于所有资源点外覆圆相交关系来进行，如下式：

S_i={\displaystyle \sum _{j=\mathrm{1}}^M}{C}_{i,j}（2）

式中：M为资源点数量；S_i 表示资源点i与所有资源点（包括自身）相交的情况，若其取值为1，代表与除自身以外的资源点均无相交关系，该点即为孤立点。需要注意的是孤立点会随着覆盖过程而新增。

2.3.3 计算最大团

计算所有资源点外覆圆相交情况，目的是为了找到资源点最密集的区域，在该区域部署无人节点能够服务覆盖尽可能多的资源点。通过计算所有资源点两两之间的距离，容易得出两两之间的相交情况，但要求解3个及以上是否同时相交，则是一个NPC问题。

采用查找最大团（最大两两相交的点集）的方法可近似找到符合要求的资源密集区域，其中，最大团查找可采用Bron-Kerbosch 算法^[10]。

以剩余未覆盖资源点为点集，外覆圆相交关系作为边，构建网络连接图，找出其最大团。图6的网络连接图如图11所示，其包含的两个及以上点构成的团有“1, 2, 3”“3, 4”“4, 5”，最大团是“1, 2, 3”，与图6资源密集情况相符。

2.3.4 确定最大团覆盖圆心

发现资源密集区域后的一个关键问题是确定无人节点部署位置。尝试以最大团中所有点的中心为圆心，即式（3）。

y=\frac{\mathrm{1}}{T}{\displaystyle \sum _{i=\mathrm{1}}^T}{p}_i（3）

式中：T为最大团中资源点的数量；p_i 为资源点i的坐标；y代表需要确定的覆盖圆心坐标。该方法受到资源密度的影响，覆盖圆心向资源点密集处偏移，在部分情况下会导致本可以覆盖的资源点无法被覆盖，如图12所示。

针对上述情况，计算某一点到最大团内所有其他点的距离之和作为权重，越密集的点其权重越小，通过这种方式能够适当提高远距离点的权重，一定程度降低资源密集带来的影响。改进后的圆心计算方法如式（4）。

y={\displaystyle \sum _{i=\mathrm{1}}^T}\left({\displaystyle \sum _{j=\mathrm{1}}^T}{D}_{i,j}\right)/{\displaystyle \sum _{i=\mathrm{1}}^T}{\displaystyle \sum _{j=\mathrm{1}}^T}{D}_{i,j}（4）

式中：D_i,j 为资源点i到资源点j的距离；T为最大团内资源点数量；p_i 为资源点i的坐标。

此外，若如图13所示，所取圆心覆盖资源点为0时，则随机取2个资源点中心为圆心。

3 算法测试

为对设计方法的效果进行测试和验证,在相同条件下，与文献[3]算法进行比较。测试用例使用算法随机生成，设定资源分布的区域范围为700×500（测试数据，无单位），对不同情况下算法运行情况进行统计，测试用例覆盖范围半径为20和40，覆盖资源点个数分别为5，10，30，100,300,500,1 000，5，10，30，100,300,500,1 000。

本文测试中，使用的操作系统为Windows 11，CPU为AMD Ryzen 7 5800H 3.20 GHz，内存16 GB，实现语言为python 3.9.5。无人节点覆盖范围半径为20时的部分运行结果如图14所示。

详细结果数据如表3所示，本文算法所需无人节点占文献[3]算法的比值曲线如图15所示。从结果可以看出，在无人节点覆盖半径为20时，与对比算法相比，除去极端情况，对同一区域相同数量的资源进行服务覆盖，本文方法平均能减少25%到39%的无人节点需求，有较为明显的提升。

无人节点覆盖范围半径为40时的运行结果如表4所示，所需无人节点占比曲线如图16所示。从结果可以看出，在无人节点覆盖半径为40时，与对比算法相比，除去极端情况，对同一区域相同数量的资源进行服务覆盖，本文方法平均能减少14%到40%的无人节点需求，有较为明显的提升。

4 结束语

本文考虑资源点分布情况设计了一种多无人节点边缘服务覆盖的近似方法，相比现有方法更能满足杀伤网中分散资源的服务覆盖需求。结果表明，与对比算法相比，所提方法平均无人节点需求数减少14%到40%；在资源分散时，所提方法能接近或达到最优结果；在资源密集程度高时，所提方法与区域覆盖结果相当。

参考文献

[1] 向庭立，王红军，杨刚，分布式无人机网络覆盖优化算法［J］.空军工程大学学报（自然科学版），2019，20（4）：59-65.

[2] 邓德辉，郭剑东.基于改进平衡优化算法的多无人机网络覆盖技术［J］.机械与电子，2023，41（5）：51-55.

[3] CHANG C Y， CHEN C C， LIU C C. A novel approximation algorithm for minimum geometric disk cover problem with hexagon tessellation［C］∥Advances in Intelligent Systems and Applications-Volume 1. Berlin，Germany：Springer，2013：157-166.

[4] 陈新颖，盛敏，李博，面向6G的无人机通信综述［J］.电子与信息学报，2022，44（3）：781-789.

[5] ACHARYYA R， MANJANNA B， DAS G K. Unit disk cover problem in 2D［C］∥Computational Science and Its Applications. Berlin， Germany： Springer，2013：73-85.

[6] 朱佳琳.考虑无人机抖动的空地网络覆盖与容量分析研究［D］.北京：北京邮电大学，2021.

[7] 丁海霞，曾振东，邓嘉明.基于逾渗理论的无人机网络覆盖性能的研究［J］.火力与指挥控制，2022，47（3）：40-44.

[8] 郭艺轩，贾向东，曹胜男，三维动态无人机网络覆盖性能与信道容量分析［J］.重庆邮电大学学报（自然科学版），2022，34（4）：662-668.

[9] 王巍，梁雅静，刘阳，城市灾区无人机网络自适应覆盖优化算法［J］.计算机工程与应用，2022，58（14）：258-268.

[10] BRON C， KERBOSCH J. Algorithm 457： finding all cliques of an undirected graph［J］. Communications of the ACM， 1973，16（9）：575-577.

基金资助

国家自然科学基金(62222121)

国家自然科学基金(62341110)