本发明涉及无人机集群网络拓扑重构，具体为一种基于多无人机协作的损耗检测和自动替换重构方法。
背景技术：
1、无人机集群是由大量小型无人机，以单平台无人机的作战能力为基础，以无人机之间的协同交互能力为支撑，以群体智能涌现能力为核心，基于开放式体系架构综合集成构建的，具有抗毁性、低成本、功能分布化等优势和智能特征的作战体系。无人机集群作战将在未来战争中得到广泛应用，成为未来战争的核心，对未来战争产生重要影响。
2、所谓拓扑重构，是指通过控制网络中的移动节点或链路的方法改变网络的拓扑结构，从而使网络具有较高的性能，更好地为用户提供服务。拓扑重构是恢复网络连通性的有效手段，即当网络出现故障导致网络出现分区，连通性遭到破坏，使性能下降显著时，运行拓扑重构算法，通过补充新的网络节点或移动网络中的冗余节点恢复网络的连通性。
3、现有的连通性优化和拓扑重构技术的研究多集中在无线传感器网络领域，专门针对无人机集群通信网络的拓扑重构技术的相关研究较少。大规模无人机集群拓扑网络中重构算法的研究仍存在着如算法复杂度高、不符合应用场景等问题，同时，在传统adhoc网络中，节点的移动性较弱，直接将这些算法应用在高移动性的无人机自组网中是不合理的，因此移动性较强、实时性要求更高、工作环境复杂的无人机自组网中的拓扑容错及重构问题，是一个亟待研究和完善的领域。
4、因此我们提出了一种基于多无人机协作的损耗检测和自动替换重构方法来解决上述问题。
技术实现思路
1、(一)解决的技术问题
2、针对现有技术的不足，本发明提供了一种基于多无人机协作的损耗检测和自动替换重构方法，解决了现有的无人机集群重构方法中存在重构延迟高，修复节点移动距离长，需要集中式控制的问题。
3、(二)技术方案
4、本发明为了实现上述目的具体采用以下技术方案：
5、一种基于多无人机协作的损耗检测和自动替换重构方法，包括以下步骤，
6、步骤1，构建改进鸟群模型：整个无人机集群以改进鸟群模型构建1-连通网络；改进鸟群模型包括传统的引力规则、对齐规则、斥力规则以及符合无人机运动规则的惯性规则和趋避规则；多无人机系统利用无线通信模式，即用户数据报协议；
7、步骤2，局部割点检测：在步骤1中构建的单连通网络中各节点的3跳网络进行k-tarjan割点检测，检测网络中的割点并在邻居信息交换时进行标记为关键节点，这些节点在自动替换步骤中不可作为移动节点；
8、步骤3，冗余节点标记：在无人机集群中，冗余性指无人节点之间提供的信息具有相关性和重复性，结合冗余度期望和考虑边界效应的期望覆盖值相结合来进行节点冗余性判断，即为步骤5中的自动替换准备移动节点；
9、步骤4，无人机丢包检测：该检测协议由两个任务组成；任务1的目的是找到疑似丢失的无人机节点，任务2是记录任务1的结果；另一个由两个任务管理的局部变量是一个定时器，用于确定无人机节点是否丢失；
10、步骤5，无人机自动替换：在接收到一组丢失的无人机后，无人机将根据提出的自动替换协议来决定是否需要进行自动替换，并且提出相应的竞争方案来判断最优的替换无人机节点。
11、进一步地，所述步骤1中无人机集群中单个节点的通信感知范围根据通信距离以及引力规则、对齐规则和斥力规则可以划分为引力感知区域(rs≤|vivj|≤ra)、稳定感知区域(rr≤|vivj|≤rs)和斥力感知区域(|vkvi|≤rr)，其中ra为单个无人机节点的最大通信距离；
12、此外，根据无人机集群移动的特性增加了惯性规则和趋避规则以使其更适应无人机集群中节点的运动特征；
13、(1)惯性规则
14、在现实场景中，无人机个体速度的变化受到物理惯性约束，不会在短时内发生剧烈改变；改进鸟群模型将当前时刻无人机个体速度的单位方向矢量直接作为下一时刻速度的惯性分量，即下式：
15、
16、(2)引力规则
17、引力规则模拟无人机集群个体间的内聚性的特点；改进鸟群模型中无人机个体尽量靠近其感知范围内所有邻居无人机的几何中心，即下式：
18、
19、其中，vi＝(xi，yi，zi)是目标节点i于n时刻的坐标；假设在无人机i的引力感知区域内有n架邻居无人机，且用vj＝(xi，yi，zi)表示邻居无人机个体j的当前坐标，那么所有邻节点的几何中心坐标vo＝(xi，yi，zi)可以表示为下式：
20、
21、(3)斥力规则
22、斥力规则模拟真实场景中集群无人机个体间的避撞行为；当无人机个体感知到距邻居无人机过近，即距离小于斥力半径时，产生斥力效果进行调节；
23、
24、其中，vi＝(xi，yi，zi)是目标个体于n时刻的坐标；vk＝(xk，yk，zk)表示n时刻个体斥力感知域内邻居无人机k的坐标；
25、(4)对齐规则
26、对齐规则的目的是使集群中所有无人机个体形成统一的运动趋势；改进鸟群模型中每个无人机个体与周围距离小于感知半径ra的无人机运动方向趋于一致，即下式
27、
28、其中m为邻居无人机节点的个数；
29、(5)趋避规则
30、趋避规则用于模拟无人机集群个体躲避威胁源，以及发现和靠近任务，如侦察、打击目标的行为；
31、
32、其中，vr为目标对象或者威胁对象的坐标；当目标为任务目标时，上式等号后符号取正，当目标为威胁对象时，符号取负。
33、进一步地，所述步骤3中冗余节点标记将节点冗余度期望与考虑边界效应的期望覆盖质量值相结合来进行冗余节点判断；
34、网络中单个节点的冗余度用下式表示：
35、
36、式中依据单个节点的概率感知模型，用sdi来标记无人机集群网络中单个节点vi的感知范围，表示节点vi所有的一跳邻居节点集合；节点vi的冗余度定义为节点自身的通信感知区域和邻节点传感区域重合部分与节点自身传感区域的比值；
37、所有无人机节点部署在区域s中，任一节点随机部署在区域s中的概率为(s表示抛撒无人机区域的面积)；为了贴近实际情况，将无人机节点的传感半径设置为服从n(r0,δ2)分布；对于传感半径分别为ri和rj的两个无人机节点vi和vj，如果拓扑结构上存在重合的感知区域，适用pij来表示两个节点存在感知重叠区域的概率，则可以用下式来表示：
38、
39、令e(pij)为pij的数学期望，计算可得e(pij)用下式计算：
40、
41、用来具体表示集群中节点vi和vj得不存在重叠区域得概率，表示为1-pij；如果节点vi有k个邻居，用pik来表示此节点与任意一个邻节点存在重叠区域的概率，可以得出与任意邻节点不存在重叠的传感区域的概率则可以用下式表示：
42、
43、由上式可将表示为下式：
44、
45、如果节点的冗余度期望值大于edq，即节点vi的冗余度ξ(i)的期望值满足下式，也就说明节点vi；与其邻居节点重叠的比例大于edq值，即让网络中任意节点vi；工作在最小功率状态网络连通度也会达到edq值；
46、e(ξ(i))≥eedq#式中eedq为edq值如下式所示：
47、
48、综合以上公式，若节点vi，的邻居节点数目k满足下式，即认为节点vi:符合成为冗余节点的基本条件；
49、
50、除节点自身作为修复节点进行拓扑重构的情况外,剩余情况需在冗余节点中选择修复节点进行不连通区域修复，即无人机集群网络拓扑重构；当选择出网络中的冗余节点后需在冗余节点中进行修复节点依据冗余节点的权值ρ，计算如下式:
51、
52、式中erest为节点剩余能量，d为冗余节点与不连通区域位置的欧式距离；
53、选取权值最大的冗余节点作为修复节点进行无人机集群网络拓扑重构；在冗余度值大的节点中选择修复节点意味着该节点的重叠区域最多，它的移动对于无人机集群网络的拓扑结构影响最小；从上式得出，剩余能量越大，距离越近的冗余节点被选做修复节点的概率越大，这可以确保该节点在完成拓扑重构后能够维持较长的剩余工作时间，与修复区域距离近的冗余节点易被选为修复节点，意味着选择移动距离小的节点，这样可以减少节点在移动中的能量损耗。
54、进一步地，所述步骤5无人机自动替换方法，在接收到一组丢失的无人机后，无人机将决定是否需要进行自动替换，选择一架无人机执行该任务的标准是：
55、1.它目前占据的目标优先级必须低于丢失的无人机，否则它不会被分配到任何目标位置
56、2.它到丢失无人机的位置路径最短
57、每架无人机周期性地执行这一过程，同时在节点信息报文中广播自身的成本，并通过信息报文获得其他无人机的成本；在竞争方案下，每架无人机将决定是否占用空出的目标。
58、自动替换协议中，为了达到竞争成功，该uav节点必须是最低优先级的节点，且必须不存在比当前目标点优先级更高的未分配目标点，同时它必须是所有未分配的更高优先级目标点中最近的一个。
59、每个uav都会将自己与所有具有相同目标点优先级的其他uav进行距离比较，以确保自己是所选择的目标点最近的；
60、当我们有许多无人机处于最低优先级位置时，将保证至少有一架无人机最接近未分配目标；当自己的无人机发现自己离未分配的目标位置最近时，协议进入任务竞争方案，该方案保证无论何时存在未分配的目标点，即使存在通信延迟时，至少有一架无人机被分配到目标点；
61、当无人机i在k+1时刻更新其距离时，到目标的距离di(k+1)有两种情况；
62、情形1：di(k+1)≥costi(k)，此时，无人机i在时刻k+1的成本为下式
63、costi(k+1)＝min{costi(k)，di(k+1)}
64、＝costi(k)#
65、情形2：di(k+1)≤costi(k)；此时，无人机i在k+1时刻的成本为下式
66、costi(k+1)＝min{costi(k)，di(k+1)}
67、＝di(k+1)
68、≤costi(k)#
69、当存在通信延迟时，执行上述方法时若只有一架无人机进入争用方案，该无人机将根据该方案将其分配给空出的目标；
70、当又有一架无人机进入争用方案，它们在时刻k的成本分别为costi(k)和costj(k)，假设costi(k)>costj(k)，由于通信延迟，min{costi(k)，costj(k)}在时间k不是每个无人机都可用，无人机i和j都使用包含其他无人机成本的信息进行成本评估；
71、以下考虑无人机的成本评估的所有可能性：
72、3.如果无人机i发现costi(k)>costj(k-tl)，其中tl为通信延迟，无人机i在这种情况下撤退；同样，无人机j发现costj(k)≤costi(k-tl)，无人机j将被分配到空出的目标上；
73、4.如果无人机发现了costi(k)≤costj(k-tl)将分配无人机i到目标；同样，无人机j发现costj(k)≤costi(k-tl)这是因为不可能有costj(k)>costi(k-tl)；因此，无人机j也将被分配；
74、有可能有多架无人机满足竞争方案的条件，从而同时飞向未分配的目标点；为了防止其发生，我们引入了另一种机制，即冲突预防机制；该机制的核心是在无人机飞向未分配目标之前，按无人机id从小到大分配n秒的延迟。
75、此外，所提出的自动替换方法是一个动态过程，它会不断地进行自动替换，直到被替换的无人机到达未分配的目标。
76、进一步地，防止多个无人机节点同时满足竞争方案产生的冲突，提出的冲突预防机制，根据冲突预防机制，无人机i和j有n＝time_interval秒的延迟；这意味着无人机i在时刻k立即前往未分配目标，而无人机j则停留在当前位置，直到时间＝k+time_interval；无人机i在k时刻的成本重置为costi(k)＝di(k).
77、经过一次迭代时间更新后，无人机i在k+1时刻离目标的距离为下式：
78、di(k+1)＝di(k)-v×time_interval#
79、由于速度v＞0，这就意味着di(k+1)<di(k)且得出下式
80、costi(k+1)＝min{costi(k)，di(k+1)}
81、＝di(k+1)
82、<di(k+1)
83、＝costi(k)#
84、然而，在k+1时刻，由于冲突预防机制，无人机j停在k时刻的位置；这意味着dj(k+1)＝dj(k)；重置无人机j的成本，可以得出下式
85、costj(k+1)＝min{costj(k)，dj(k+1)}
86、＝costj(k)#
87、由于在k时刻costj(k)＝costi(k)，这就意味着在k+1时刻，我们有costj(k+1)>costi(k+1)
88、即使许多无人机到达目标点的路径相同，但在其他无人机中，只有id最小的无人机的成本小于其他无人机的成本；这将保证在有限时间内只有一架无人机将自动替换到未分配的目标位置。
89、(三)有益效果
90、与现有技术相比，本发明提供了一种基于多无人机协作的损耗检测和自动替换重构方法，具备以下有益效果：
91、1、在节点的局部拓扑中进行割点检测，避免了全局割点检测大量且低效的信息交换，在难以获取全局信息的无人机集群网络中降低了通信开销，解决了大规模动态网络中割点检测时间复杂度较高的问题。
92、2、在拓扑重构算法中引入了冗余节点判断策略，使用冗余度较高的节点作为拓扑重构过程的修复节点，减少了对网络整体结构的影响，使原网络中的无效信息交换次数降低。
93、3、提出了一种基于多无人机协作的损耗检测和自动替换机制，并进行理论证明，提高了无人机节点失效后的快速检测和重构效率。
1.一种基于多无人机协作的损耗检测和自动替换重构方法，其特征在于：包括以下步骤，
2.根据权利要求1所述的一种基于多无人机协作的损耗检测和自动替换重构方法，其特征在于：所述步骤1中无人机集群中单个节点的通信感知范围根据通信距离以及引力规则、对齐规则和斥力规则可以划分为引力感知区域(rs≤|vivj|≤ra)、稳定感知区域(rr≤|vivj|≤rs)和斥力感知区域(|vkvi|≤rr)，其中ra为单个无人机节点的最大通信距离；
3.根据权利要求1所述的一种基于多无人机协作的损耗检测和自动替换重构方法，其特征在于：所述步骤3中冗余节点标记将节点冗余度期望与考虑边界效应的期望覆盖质量值相结合来进行冗余节点判断；
4.根据权利要求1所述的一种基于多无人机协作的损耗检测和自动替换重构方法，其特征在于：所述步骤5无人机自动替换方法，在接收到一组丢失的无人机后，无人机将决定是否需要进行自动替换，选择一架无人机执行该任务的标准是：
5.根据权利要求1所述的一种基于多无人机协作的损耗检测和自动替换重构方法，其特征在于：防止多个无人机节点同时满足竞争方案产生的冲突，提出的冲突预防机制，根据冲突预防机制，无人机i和j有n＝time_interval秒的延迟；这意味着无人机i在时刻k立即前往未分配目标，而无人机j则停留在当前位置，直到时间＝k+time_interval；无人机i在k时刻的成本重置为costi(k)＝di(k).
