一种无人机集群合并和分群方法与流程

1.本发明属于无人机技术领域，具体涉及一种无人机集群合并和分群方法。


背景技术：

2.随着人工智能、机器人技术和数据融合技术的进步，无人机集群被广泛应用在军事和民事领域。并且随着技术的发展，无人机集群有着小型化、智能化、大规模化的趋势。尽管完全自主的大规模无人机集群是未来的发展方向，但目前人工智能技术发展有限，人机协同完全被人工智能所取代在短时间内很难发生。目前人工智能可以通过机器学习、深度学习等手段在部分领域实现无人参与。但涉及到创造性、无法给出明确定义和边界、缺乏数字化知识经验的任务，人工智能就无能为力，所以在今后一段时间里，智能机器在任务执行过程中更多起到辅助作用，最终决策依然离不开人类。对于无人机集群来说，因为其任务的复杂性和多变性，目前仍然需要有人参与决策，通过外部指令对集群进行控制，才能保证成功完成任务。对于大规模无人机集群来说，常见的工作模式是“领导者-跟随者”模式，即选择集群中的某架无人机作为领导者直接接收控制中心的指令，集群中其他的无人机则接收领导者的指令，实现整个集群在外部指令的控制下执行协同任务。
3.对于大规模无人机集群来说，因为其规模较大，在实际应用中往往无法做到同时、同地起飞。一种常见的工作方式是根据任务的需求，多个不同的小规模无人机集群异地起飞，到达指定任务地点后合并为一个大规模无人机集群开始执行任务。当任务完成之后需要返航时，或者根据任务要求需要少量无人机执行其他任务时，大规模无人机集群需要进行分群，形成多个小规模无人机集群完成降落或者继续执行其他任务。为了保证在整个过程中集群都是受外部指令控制的，合并和分群之后的集群仍然能够快速实现状态的收敛并执行协同任务，需要考虑如下问题：
4.在多个集群合并为大规模无人机集群时，由于多个领导者无人机是直接由控制中心调度，可以很快识别新的领导者并完成合并。但是集群中的跟随者无人机不具备决策能力，只能跟随领导者无人机进行行动，因此跟随者无人机并不知晓合并任务的具体要求，如果两个集群的跟随者无人机直接进行相互交互，难免会造成协同状态混乱。所以如何保证多个集群在合并时无人机状态的稳定，并快速完成合并以及状态的收敛是一个重要的问题。
5.在大规模无人机集群分成多个子集群的过程中，如何根据任务的需要并通过最少的操作、最小的能耗完成分群，具有非常重要的意义。在完成分群之后，多个不同的子集群需要快速选取出各自的新领导者，才能保证大规模集群在分群之后，各子集群仍然能够快速完成协同状态的收敛，继续执行不同的任务。


技术实现要素：

6.为了克服现有技术的不足，本发明提供了一种无人机集群合并和分群方法，首先针对多集群合并问题，通过给每个无人机引入集群标号和活跃次数两个变量，使来自不同
集群的无人机可以有序地根据任务的要求完成融合；针对无人机集群划分为多个子集群的问题，引入遗传算法对无人机集群的邻接矩阵进行处理，寻找割边最少的节点划分序列，断开割边两端的无人机之间的连接，即可以把集群划分为任务要求的数个子集群，随后根据每个集群中无人机的度中心性指标确定关键节点，并选其作为每个集群的新领导者无人机；本发明能够高效实现大规模无人机集群的合并与分群。
7.本发明解决其技术问题所采用的技术方案包括如下步骤：
8.步骤1：构建无人机集群模型；
9.无人机集群是由相同的无人机组成，且无人机能够相互通信，因此无人机集群的拓扑结构用无向图g＝(v,e)来表示，其中v＝{v1,v2,
…
,vn}表示集群中所有无人机的集合，表示无人机之间连接的集合；令表示与无向图g相关联的邻接矩阵，当a
ij
为1时，表示无人机i和无人机j能够相互通信；当a
ij
为0时，表示无人机j在无人机i的通信范围之外；每个无人机集群包括一个领导者和若干跟随无人机；
10.集群中每架无人机的状态表示为：
[0011][0012]
其中xn(t)表示各种与飞行状态相关的值；
[0013]
如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则判定无人机集群实现有外部控制的协同状态，即满足下式：
[0014][0015]
其中，x
l
(t)表示领导者无人机的状态信息，由控制中心决定；
[0016]
步骤2：无人机集群合并；
[0017]
假设无人机集群m与集群n需要完成合并，并且根据控制中心的决策，合并之后的新集群的领导者为n的领导者，即集群m需要融入到集群n中，具体步骤如下：
[0018]
步骤2-1：对于集群m中的无人机，维护集群编号g_num为m；集群n中的无人机，维护集群编号g_num为n；并且跟随无人机只接收g_num与自身相同的无人机发来的信息；设置无人机初始的活跃次数；
[0019]
步骤2-2：当集群m和集群n的领导者接收到合并指令时，两个集群开始相互接近；
[0020]
步骤2-3：当集群m中的跟随无人机接收到集群n中的无人机发来的消息时，由于集群标号不一致，忽略该消息；
[0021]
步骤2-4：当集群m中的领导者接收到集群n中的无人机发来的合并消息时，改变身份为跟随者，改变g_num为n，并以消息来源的无人机作为自身的父节点，加入集群n；
[0022]
步骤2-5：每轮迭代时，如果集群m中的跟随者接收不到领导者的状态信息，则活跃次数减1；
[0023]
步骤2-6：当集群m中的无人机剩活跃次数降为0时，改变集群编号g_num为0，并改变自身为无领导者模式；
[0024]
步骤2-7：当无领导者模式的无人机接收到集群n的消息时，即改变身份为跟随无人机，改变集群编号g_num为n，并以消息来源的无人机作为自身的父节点，加入集群n；
[0025]
步骤2-8：当所有无领导者无人机都加入集群n之后，即完成集群m到集群n的合并
过程；
[0026]
步骤3：无人机集群分群；
[0027]
步骤3-1：根据任务的要求，确定所需要的子集群的个数k以及每个集群的无人机数目限制；
[0028]
步骤3-2：将邻接矩阵对应的节点排列表示为一个向量通过对该向量的变换来变换邻接矩阵，使用遗传算法求解最优节点排列；
[0029]
步骤3-3：确定割边最少时的适应度函数，ec为割边集，即无向图g在划分之后两个不在同一个子集中的节点之间的连线的集合，定义如下：
[0030]
ec＝{e
s,t
|s∈vi,t∈vj,1≤i,j≤k,i≠j}
[0031]
其中，e
s,t
表示位于两个不同集群的无人机的连边，s和t分别表示位于不同无人机集群的无人机，vj表示一个无人机集群的无人机集合；
[0032]
步骤3-4：将一个节点排列的向量视为一个染色体，初始化固定染色体数目的初始种群；
[0033]
步骤3-5：在初始种群中，记录最大适应度值的个体；
[0034]
步骤3-6：在初始种群中随机选取个体执行交叉和变异操作，形成新的种群；
[0035]
步骤3-7：重复执行步骤3-4～步骤3-6；
[0036]
步骤3-8：达到指定迭代次数，得到最优个体，即最优节点排列；
[0037]
步骤3-9：根据最优节点排列对应的邻接矩阵，确定割边集，断开割边，完成分群；
[0038]
步骤3-10：在分群之后的各个子集群中，根据每个节点的度的大小进行排序，选择各集群中度最大的节点作为每个集群的新领导者。
[0039]
优选地，所述飞行状态包括无人机的速度、位置和加速度信息。
[0040]
本发明的有益效果如下：
[0041]
1、本发明针对多集群合并问题，通过给每个无人机引入集群标号和剩余活跃次数两个变量，使来自不同集群的无人机可以有序地根据任务的要求完成融合，实现一个集群的领导者先融合、跟随者变为无领导者再融入新集群的合并模式，保证不同的无人机集群在合并之后能够快速与新的领导者的状态达成一致，无人机集群的协同工作状态不会收到明显影响。
[0042]
2、针对无人机集群划分为多个子集群的问题，引入遗传算法对无人机集群的邻接矩阵进行处理，寻找割边最少的节点划分序列。断开割边两端的无人机之间的连接，即可以把集群划分为任务要求的数个子集群，随后根据每个集群中无人机的度中心性指标确定关键节点，并选其作为每个集群的新领导者无人机，保证划分之后的数个子集群仍然具备根据外部的指令完成协同工作的能力。
附图说明
[0043]
图1是本发明无人机集群合并过程示意图，其中图1(a)表示集群合并之前，图1(b)表示领导者首先完成合并，图1(c)表示两个集群完成合并。
[0044]
图2是本发明无人机集群合并方法流程示意图。
[0045]
图3是本发明重排节点序列寻找最优无人机集群分群过程示意图，其中图3(a)表
示无人机集群初始拓扑和初始节点序列对应的邻接矩阵，图3(b)表示无人机集群分群之后的拓扑和重排节点序列后对应的邻接矩阵。
[0046]
图4是本发明无人机集群分群算法流程示意图。
具体实施方式
[0047]
下面结合附图和实施例对本发明进一步说明。
[0048]
本发明旨在提出一种大规模无人机集群合并和分群方法，使无人机集群能够根据不同的任务需要，灵活地调整集群的规模，以应对起飞、降落以及其他特殊任务的需求。并通过合适的方法完成合并和分群过程中新领导者的确定，使集群在合并和分群之后仍然能够快速达成协同状态的收敛，能够继续在受外部指令控制的条件下执行协同任务。
[0049]
为实现上述发明目的，本发明提出的技术方案如下：
[0050]
首先对相关概念进行介绍：
[0051]
通常情况下，大规模无人机集群是由相同的小型无人机组成，且无人机可以相互通信，因此无人机集群的拓扑结构可以用无向图g＝(v,e)来表示，其中v＝{v1,v2,
…
,vn}表示集群中所有无人机的集合，表示无人机之间连接的集合。令表示与无向图g相关联的邻接矩阵，当a
ij
为1时，表示无人机i和无人机j能够相互通信；当a
ij
为0时，表示无人机j在无人机i的通信范围之外。集群中每架无人机的状态可表示为：
[0052][0053]
其中xn(t)表示各种与飞行状态相关的值，可以是速度、位置、加速度等标量或矢量信息。如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则可以认为无人机集群实现有外部控制的协同状态，即满足下式：
[0054][0055]
其中，x
l
(t)表示领导者无人机的状态信息，由控制中心直接决定。
[0056]
1、集群合并方法，如图2所示；
[0057]
每个集群都有受地面基站直接控制的领导者无人机，因此地面基站可以根据不同的任务需求，选取合适的数个无人机集群进行合并，执行协同任务。同时，因为合并之后的集群仍然需要在外部指令的控制下执行任务，因此集群合并的过程可以总结为：地面基站根据任务要求选取合适的集群并给集群的领导者无人机下达合并指令。不同集群的领导者在接收到指令后开始先在各自集群达成协同状态，然后向指定区域汇聚。集群汇聚之后，地面控制中心根据任务的需求、剩余续航时间、所在集群中无人机数目等评判指标在这几个领导者无人机中选取一个作为合并后集群的新领导者。选择出新的领导者之后，其他集群加入到新领导者所在的集群中，实现多个集群的合并。
[0058]
然而，在两个无人机集群执行合并指令的过程，只有两个领导者能够收到指令消息并带领两个集群相互靠近，直到抵达相互可以通信的位置，然后合并为一个新的无人机集群。在整个过程中，除了领导者无人机，集群中其他无人机并不知道任何关于合并的信息，而集群中的无人机是通过与领导者的状态保持一致而实现集群的状态收敛。当两个集群开始合并时，某个集群中的无人机既能够接收到另外一个集群的状态信息，又能够接收
到当前集群中来自领导者的状态信息，而无人机自身并不知道合并后的集群以哪边为主，因此不知道该选取哪个状态作为自身的目标状态信息，这会造成集群合并过程的混乱，影响集群系统的稳定性。
[0059]
为了解决上述问题，给每架无人机引入变量g_num来记录其所在的集群编号，并随着状态信息在每次迭代时一同发送给相邻的无人机。每个集群中的非领导者无人机只能接收相同g_num的无人机发来的状态信息，保证了每个无人机只能接收来自同一个集群的消息。同时引入变量hb来记录每个无人机所在离开该集群之后的剩余活跃次数，每个无人机的hb一般设置初值为3，表示无人机在无法收到原集群领导者消息之后还能够维护原本的集群编号g_num进行迭代3个周期。每次迭代周期结束时，如果无人机接收到了父节点的信息，则hb置为3；如果无人机丢失了父节点的信息，则hb减1，直到hb减少为0，说明无人机的已经超过3个迭代周期无法更新原集群的生成树，代表原集群的领导者已经丢失或该无人机已经脱离了原集群，此时该无人机为无集群状态，可以接收来自其他集群的消息。
[0060]
假如集群编号分别为m和n的两个集群需要实现合并，并且合并后的新集群领导者为n集群原来的领导者，即需要实现集群m加入到集群n的过程。其中，两个集群的领导者都直接受控于地面中心，因此对合并信息都已知悉。所以，当集群m的领导者无人机leaderm一旦接收到来自集群n的消息，无论该消息是来自集群n的领导者leadern还是集群n内的其他跟随无人机，leaderm均执行合并指令，更改自身的领导者身份，变为集群n的跟随者，并以所接收消息的来源无人机作为自身的父节点，加入到集群n所维护的生成树中。此时，集群m的无人机变为了无领导者状态，在经过3次迭代之后，集群内生成树仍然无法更新，hb降为0，集群m中的无人机将g_num置为0，表示为无集群状态，并可以接收来自任何集群的信息。随后，原属于集群m的无人机接收到了集群n中的消息，更新并加入到集群n中的生成树中，完成集群合并的过程。整个合并过程通过领导者先加入，跟随者变为无集群状态，随后再加入新的集群，保证了集群合并的有序进行，对被加入集群的状态不造成影响，新加无人机的状态也能够很快地与新集群保持一致，实现整个合并过程的协同状态稳定收敛。
[0061]
2、集群分群方法，如图4所示；
[0062]
假设任务要求了需要划分的子集群的个数为n，那么如何快速根据现有的大规模无人机集群的拓扑结构划分为n个子集群，快速确定新集群中的新领导者，并且整个过程开销不能过大，保证整个集群在划分之后各个集群仍然能够维持协同工作的状态，是需要解决的问题。
[0063]
为了解决集群划分的问题，引入割边集的概念，即图在划分之后两个不在同一个子集中的节点之间的连线的集合，定义如下：
[0064]
ec＝{e
s,t
|s∈vi,t∈vj,1≤i,j≤n,i≠j}
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
[0065]
由于无人机集群的拓扑图是一个无权无向图，因此无人机集群的划分就可以看作将一个连通的无向图划分为多个不连通的拓扑图，所以为了使划分最简单和快速，则需要找到一种划分方法，使划分之后的拓扑图包含的割边数目最少，即min(ec)。
[0066]
遗传算法(ga)是一种高效实用的启发式算法，该算法是根据大自然中生物体进化规律而设计的，是一种通过模拟自然进化过程搜索最优解的方法，它适用于并行过程处理大规模优化问题。使用遗传算法解决最优序列问题，需要完成包括染色体表示、适应度函数、交叉算子和变异算子四个内容的设计。
[0067]
(1)染色体设计：在序列寻优问题中，节点排列的向量可以用来表示为染色体，该向量是节点编号的一个排列，也是最终的解集。同时，为了防止划分之后的某个子集群为空，用向量表示k个子集群中每个子集群所含节点的数量。
[0068]
(2)适应度函数：由于前面的分析，最优的节点排列对应的邻接矩阵存在最少的割边数目，又因为一个拓扑图中所有的边的个数是确定的，因此适应度函数可以记为：
[0069][0070]
只需找到适应度函数最大值时的节点序列，就是最优的划分节点序列。
[0071]
(3)交叉算子：交叉算子需要两个父代染色体来进行结构重组，对两个父代染色体进行特征合并，生成新的子染色体。重组的方法是：保留一个父染色体的主体部分，用另一个父染色体中不重复的部分填补剩下的空白。如下例所示：
[0072][0073][0074][0075][0076]
首先，随机选取两个由“|”表示的交叉点，截取的两个交叉点之间的元素并把这些元素放到的相同位置。接着，从交叉点位置开始，如果子代还没有相同的元素，取的元素值并将其插入的交叉点位置之后的第一个零元素所在位置。如果取值过程达到的尾部或者插值过程达到的尾部，就从向量的头部从头开始遍历。
[0077]
(4)变异算子：变异算子可以增加染色体的多样性，为种群引入新的信息。这里通过引入一个交换操作来实现变异。例如，随机选取父代中的两个元素3和7为变异点，然后这两个元素交换位置，如下所示，即完成变异。
[0078][0079][0080]
完成上述操作后，对节点序列进行足够迭代次数的计算，求得最优的节点划分序列。通过遗传算法，不再需要对节点排序使用暴力算法进行求解，而是把多个可能的序列作为一代种群中的个体，然后通过执行交叉、变异等操作对种群进行更新，并重复上述操作，同时记录每代种群中最大适应度的个体。当重复迭代达到一定次数时，就可得到最优的个体，即最优的集群划分序列。
[0081]
在寻找到最优集群划分序列之后，断开割边两端无人机的通信，一个大规模无人机集群就被划分为多个子集群。而根据任务的要求，划分之后的子集群仍然需要具备执行协同任务的能力，即新的集群仍然需要具有领导者来接收外部指令信息，通过领导者对新的集群进行控制，完成协同工作。因此，需要在划分之后的集群中寻找合适的无人机来当作新的领导者。
[0082]
在一个集群网络中，某些关键节点对于整个网络具有重要的作用，这些关键节点有时可以决定网络的结构以及功能，可以极大的提高整个网络的鲁棒性。而这些节点一旦
被攻击失效，将会对整个网络造成巨大的影响。其中，度中心性指标是一个经典的衡量节点重要性的指标，即通过衡量节点的度数来挑选中网络中的关键节点。当某个无人机的度数越大，证明与其直接交互的无人机越多，该无人机所处的为位置越重要，因此可通过度中心性来寻找集群中的关键节点，并选其为领导者无人机。
[0083]
在大规模无人机集群完成集群划分并确定各个子集群的新领导者之后，各个子集群可以在短时间内达成各个集群的协同状态，然后分别执行新的任务。整个过程迅速且互相不受影响，保证大规模无人机集群能够适应不同的任务要求，具备执行协同任务的能力。
[0084]
具体实施例：
[0085]
如图1所示，假设集群m与集群n需要完成合并。并且根据控制中心的决策，合并之后的新集群的领导者为n的领导者，即集群m需要融入到集群n中。使用集群合并算法完成该过程的描述如下：
[0086]
1)对于m集群中的无人机，维护集群编号g_num为m；集群n中的无人机维护集群编号g_num为n；并且无人机只接收g_num与自身相同的无人机发来的信息；
[0087]
2)当两个集群的领导者接收到合并指令时，两个集群开始相互接近；
[0088]
3)当集群m中的跟随无人机接收到集群n中的无人机发来的消息时，由于集群标号不一致，忽略该消息；
[0089]
4)当集群m中的领导者无人机接收到集群n中的无人机发来的消息时，改变身份为跟随者，改变g_num为n，并以消息来源的无人机作为自身的父节点，加入集群n；
[0090]
5)每轮迭代时，如果集群m中的跟随者接收不到领导者的状态信息，则剩余活跃次数减1；
[0091]
6)当集群m中的无人机剩余活跃次数降为0时，改变集群编号g_num为0，并改变自身为无领导者模式；
[0092]
7)当无领导者模式的无人机接收到集群n的消息时，即可改变身份为跟随者，改变集群编号为n，并以消息来源的无人机作为自身的父节点，加入集群n；
[0093]
8)当所有无领导者无人机都加入集群n之后，即完成集群m到集群n的合并过程；
[0094]
由于邻接矩阵的特点，当节点排列顺序发生变化时，对应的邻接矩阵也不同。通过对邻接矩阵节点序列的调整，可以将邻接矩阵转换为近似的对角矩阵，每个对角块就表示新划分的子集群。对角块之外的边即表示不同子集群之间的割边，断开割边即可完成分群，因此割边越少，划分集群所耗费的能量就越低，因此需要寻找最优的节点序列，使该序列对应的邻接矩阵为对角矩阵且割边最少。如图3所示，当节点序列排序为{1,2,8,4,5,7,9,3,6,10}时，邻接矩阵中的割边最少，节点被分为3个子集群，分别是{1,2,8}、{4,5,7,9}和{3,6,10}，这样划分为最优解。集群分算法的具体描述如下：
[0095]
1)根据任务的要求，确定所需要的子集群的个数n以及每个集群的无人机数目限制；
[0096]
2)将邻接矩阵对应的节点排列表示为一个向量通过对该向量的变换来变换邻接矩阵，可以通过暴力搜索找到一个使邻接矩阵最接近块对角矩阵的排列进而由该邻接矩阵和节点排列可以确定割边集。但是暴力搜索时间复杂度太高，因此考虑使用遗传算法求解最优节点排列；
[0097]
3)确定割边最少时的适应度函数，
[0098]
4)将一个节点排列的向量视为一个染色体，初始化固定染色体数目的初始种群；
[0099]
5)在初始种群中，记录最大适应度值的个体；
[0100]
6)在初始种群中随机选取个体执行交叉和变异操作，形成新的种群；
[0101]
7)重复4)～6)；
[0102]
8)达到指定迭代次数，得到最优个体，即最优节点排列；
[0103]
9)根据最优节点排列对应的邻接矩阵，确定割边集，断开割边，完成分群；
[0104]
10)在分群之后的各个子集群中，根据每个节点的度的大小进行排序，选择各集群中度最大的节点作为每个集群的新领导者。

技术特征：
1.一种无人机集群合并和分群方法，其特征在于，包括以下步骤：步骤1：构建无人机集群模型；无人机集群是由相同的无人机组成，且无人机能够相互通信，因此无人机集群的拓扑结构用无向图g＝(v,e)来表示，其中v＝{v1,v2,
…
,v
n
}表示集群中所有无人机的集合，表示无人机之间连接的集合；令表示与无向图g相关联的邻接矩阵，当a
ij
为1时，表示无人机i和无人机j能够相互通信；当a
ij
为0时，表示无人机j在无人机i的通信范围之外；每个无人机集群包括一个领导者和若干跟随无人机；集群中每架无人机的状态表示为：其中x
n
(t)表示各种与飞行状态相关的值；如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则判定无人机集群实现有外部控制的协同状态，即满足下式：其中，x
l
(t)表示领导者无人机的状态信息，由控制中心决定；步骤2：无人机集群合并；假设无人机集群m与集群n需要完成合并，并且根据控制中心的决策，合并之后的新集群的领导者为n的领导者，即集群m需要融入到集群n中，具体步骤如下：步骤2-1：对于集群m中的无人机，维护集群编号g_num为m；集群n中的无人机，维护集群编号g_num为n；并且跟随无人机只接收g_num与自身相同的无人机发来的信息；设置无人机初始的活跃次数；步骤2-2：当集群m和集群n的领导者接收到合并指令时，两个集群开始相互接近；步骤2-3：当集群m中的跟随无人机接收到集群n中的无人机发来的消息时，由于集群标号不一致，忽略该消息；步骤2-4：当集群m中的领导者接收到集群n中的无人机发来的合并消息时，改变身份为跟随者，改变g_num为n，并以消息来源的无人机作为自身的父节点，加入集群n；步骤2-5：每轮迭代时，如果集群m中的跟随者接收不到领导者的状态信息，则活跃次数减1；步骤2-6：当集群m中的无人机剩活跃次数降为0时，改变集群编号g_num为0，并改变自身为无领导者模式；步骤2-7：当无领导者模式的无人机接收到集群n的消息时，即改变身份为跟随无人机，改变集群编号g_num为n，并以消息来源的无人机作为自身的父节点，加入集群n；步骤2-8：当所有无领导者无人机都加入集群n之后，即完成集群m到集群n的合并过程；步骤3：无人机集群分群；步骤3-1：根据任务的要求，确定所需要的子集群的个数k以及每个集群的无人机数目限制；步骤3-2：将邻接矩阵对应的节点排列表示为一个向量通过对该向量的变换来变换邻接矩阵，使用遗传算法求解最优节点排列；
步骤3-3：确定割边最少时的适应度函数，ec为割边集，即无向图g在划分之后两个不在同一个子集中的节点之间的连线的集合，定义如下：ec＝{e
s,t
|s∈v
i
,t∈v
j
,1≤i,j≤k,i≠j}其中，e
s,t
表示位于两个不同集群的无人机的连边，s和t分别表示位于不同无人机集群的无人机，v
j
表示一个无人机集群的无人机集合；步骤3-4：将一个节点排列的向量视为一个染色体，初始化固定染色体数目的初始种群；步骤3-5：在初始种群中，记录最大适应度值的个体；步骤3-6：在初始种群中随机选取个体执行交叉和变异操作，形成新的种群；步骤3-7：重复执行步骤3-4～步骤3-6；步骤3-8：达到指定迭代次数，得到最优个体，即最优节点排列；步骤3-9：根据最优节点排列对应的邻接矩阵，确定割边集，断开割边，完成分群；步骤3-10：在分群之后的各个子集群中，根据每个节点的度的大小进行排序，选择各集群中度最大的节点作为每个集群的新领导者。2.根据权利要求1所述的一种无人机集群合并和分群方法，其特征在于，所述飞行状态包括无人机的速度、位置和加速度信息。

技术总结
本发明公开了一种无人机集群合并和分群方法，首先针对多集群合并问题，通过给每个无人机引入集群标号和活跃次数两个变量，使来自不同集群的无人机可以有序地根据任务的要求完成融合；针对无人机集群划分为多个子集群的问题，引入遗传算法对无人机集群的邻接矩阵进行处理，寻找割边最少的节点划分序列，断开割边两端的无人机之间的连接，即可以把集群划分为任务要求的数个子集群，随后根据每个集群中无人机的度中心性指标确定关键节点，并选其作为每个集群的新领导者无人机；本发明能够高效实现大规模无人机集群的合并与分群。实现大规模无人机集群的合并与分群。实现大规模无人机集群的合并与分群。


技术研发人员：陈旿 朱家易 田莎 刘旭
受保护的技术使用者：水禾科技有限公司
技术研发日：2023.03.05
技术公布日：2023/7/11