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

　　(19)国家知识产权局 (12)发明专利申请 (10)申请公布号 CN 116400725 A (43)申请公布日 2023.07.07 (21)申请号 3.1 (22)申请日 2023.03.05 (71)申请人 西北工业大学 地址 710072 陕西省西安市友谊西路127号 申请人 水禾科技有限公司 (72)发明人 陈旿朱家易田莎刘旭 (74)专利代理机构 西安凯多思知识产权代理事 务所(普通合伙) 61290 专利代理师 刘涛 (51)Int.Cl. G05D 1/10 (2006.01) 权利要求书2页 说明书8页 附图3页 (54)发明名称 一种无人机集群合并和分群方法 (57)摘要 本发明公开了一种无人机集群合并和分群 方法，首先针对多集群合并问题，通过给每个无 人机引入集群标号和活跃次数两个变量，使来自 不同集群的无人机可以有序地根据任务的要求 完成融合；针对无人机集群划分为多个子集群的 问题，引入遗传算法对无人机集群的邻接矩阵进 行处理，寻找割边最少的节点划分序列，断开割 边两端的无人机之间的连接，即可以把集群划分 为任务要求的数个子集群，随后根据每个集群中 无人机的度中心性指标确定关键节点，并选其作 为每个集群的新领导者无人机；本发明能够高效 实现大规模无人机集群的合并与分群。 A 5 2 7 0 0 4 6 1 1 N C CN 116400725 A 权利要求书 1/2页 1.一种无人机集群合并和分群方法，其特征在于，包括以下步骤： 步骤1：构建无人机集群模型； 无人机集群是由相同的无人机组成，且无人机能够相互通信，因此无人机集群的拓扑 结构用无向图G＝(V,E)来表示，其中V＝{v ,v ,…,v }表示集群中所有无人机的集合， 1 2 n 表示无人机之间连接的集合；令 表示与无向图G相关联的邻接矩 阵，当a 为1时，表示无人机i和无人机j能够相互通信；当a 为0时，表示无人机j在无人机i ij ij 的通信范围之外；每个无人机集群包括一个领导者和若干跟随无人机； 集群中每架无人机的状态表示为： n 其中x (t)表示各种与飞行状态相关的值； 如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则判定无人机 集群实现有外部控制的协同状态，即满足下式： 其中，x (t)表示领导者无人机的状态信息，由控制中心决定； L 步骤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：将邻接矩阵对应的节点排列表示为一个向量 通过对该向量 的变换来变换邻接矩阵，使用遗传算法求解最优节点排列； 2 2 CN 116400725 A 权利要求书 2/2页 步骤3‑3：确定割边最少时的适应度函数， EC为割边集，即无向图G 在划分之后两个不在同一个子集中的节点之间的连线的集合，定义如下： EC＝{e s∈V,t∈V ,1≤i,j≤k,i≠j} s,t 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所述的一种无人机集群合并和分群方法，其特征在于，所述飞行状态 包括无人机的速度、位置和加速度信息。 3 3 CN 116400725 A 说明书 1/8页 一种无人机集群合并和分群方法 技术领域 [0001] 本发明属于无人机技术领域，具体涉及一种无人机集群合并和分群方法。 背景技术 [0002] 随着人工智能、机器人技术和数据融合技术的进步，无人机集群被广泛应用在军 事和民事领域。并且随着技术的发展，无人机集群有着小型化、智能化、大规模化的趋势。尽 管完全自主的大规模无人机集群是未来的发展方向，但目前人工智能技术发展有限，人机 协同完全被人工智能所取代在短时间内很难发生。目前人工智能可以通过机器学习、深度 学习等手段在部分领域实现无人参与。但涉及到创造性、无法给出明确定义和边界、缺乏数 字化知识经验的任务，人工智能就无能为力，所以在今后一段时间里，智能机器在任务执行 过程中更多起到辅助作用，最终决策依然离不开人类。对于无人机集群来说，因为其任务的 复杂性和多变性，目前仍然需要有人参与决策，通过外部指令对集群进行控制，才能保证成 功完成任务。对于大规模无人机集群来说，常见的工作模式是“领导者‑跟随者”模式，即选 择集群中的某架无人机作为领导者直接接收控制中心的指令，集群中其他的无人机则接收 领导者的指令，实现整个集群在外部指令的控制下执行协同任务。 [0003] 对于大规模无人机集群来说，因为其规模较大，在实际应用中往往无法做到同时、 同地起飞。一种常见的工作方式是根据任务的需求，多个不同的小规模无人机集群异地起 飞，到达指定任务地点后合并为一个大规模无人机集群开始执行任务。当任务完成之后需 要返航时，或者根据任务要求需要少量无人机执行其他任务时，大规模无人机集群需要进 行分群，形成多个小规模无人机集群完成降落或者继续执行其他任务。为了保证在整个过 程中集群都是受外部指令控制的，合并和分群之后的集群仍然能够快速实现状态的收敛并 执行协同任务，需要考虑如下问题： [0004] 在多个集群合并为大规模无人机集群时，由于多个领导者无人机是直接由控制中 心调度，可以很快识别新的领导者并完成合并。但是集群中的跟随者无人机不具备决策能 力，只能跟随领导者无人机进行行动，因此跟随者无人机并不知晓合并任务的具体要求，如 果两个集群的跟随者无人机直接进行相互交互，难免会造成协同状态混乱。所以如何保证 多个集群在合并时无人机状态的稳定，并快速完成合并以及状态的收敛是一个重要的问 题。 [0005] 在大规模无人机集群分成多个子集群的过程中，如何根据任务的需要并通过最少 的操作、最小的能耗完成分群，具有非常重要的意义。在完成分群之后，多个不同的子集群 需要快速选取出各自的新领导者，才能保证大规模集群在分群之后，各子集群仍然能够快 速完成协同状态的收敛，继续执行不同的任务。 发明内容 [0006] 为了克服现有技术的不足，本发明提供了一种无人机集群合并和分群方法，首先 针对多集群合并问题，通过给每个无人机引入集群标号和活跃次数两个变量，使来自不同 4 4 CN 116400725 A 说明书 2/8页 集群的无人机可以有序地根据任务的要求完成融合；针对无人机集群划分为多个子集群的 问题，引入遗传算法对无人机集群的邻接矩阵进行处理，寻找割边最少的节点划分序列，断 开割边两端的无人机之间的连接，即可以把集群划分为任务要求的数个子集群，随后根据 每个集群中无人机的度中心性指标确定关键节点，并选其作为每个集群的新领导者无人 机；本发明能够高效实现大规模无人机集群的合并与分群。 [0007] 本发明解决其技术问题所采用的技术方案包括如下步骤： [0008] 步骤1：构建无人机集群模型； [0009] 无人机集群是由相同的无人机组成，且无人机能够相互通信，因此无人机集群的 拓扑结构用无向图G＝(V,E)来表示，其中V＝{v,v ,…,v }表示集群中所有无人机的集合， 1 2 n 表示无人机之间连接的集合；令 表示与无向图G相关联的邻接矩 阵，当a 为1时，表示无人机i和无人机j能够相互通信；当a 为0时，表示无人机j在无人机i ij ij 的通信范围之外；每个无人机集群包括一个领导者和若干跟随无人机； [0010] 集群中每架无人机的状态表示为： [0011] [0012] n 其中x (t)表示各种与飞行状态相关的值； [0013] 如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则判定无 人机集群实现有外部控制的协同状态，即满足下式： [0014] [0015] 其中，x (t)表示领导者无人机的状态信息，由控制中心决定； L [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的合并 5 5 CN 116400725 A 说明书 3/8页 过程； [0026] 步骤3：无人机集群分群； [0027] 步骤3‑1：根据任务的要求，确定所需要的子集群的个数k以及每个集群的无人机 数目限制； [0028] 步骤3‑2：将邻接矩阵对应的节点排列表示为一个向量 通过对该 向量的变换来变换邻接矩阵，使用遗传算法求解最优节点排列； [0029] 步骤3‑3：确定割边最少时的适应度函数， EC为割边集，即无 向图G在划分之后两个不在同一个子集中的节点之间的连线的集合，定义如下： [0030] EC＝{e s∈V,t∈V ,1≤i,j≤k,i≠j} s,t i j [0031] 其中，e 表示位于两个不同集群的无人机的连边，s和t分别表示位于不同无人机 s,t 集群的无人机，V表示一个无人机集群的无人机集合； j [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)表 6 6 CN 116400725 A 说明书 4/8页 示无人机集群初始拓扑和初始节点序列对应的邻接矩阵，图3(b)表示无人机集群分群之后 的拓扑和重排节点序列后对应的邻接矩阵。 [0046] 图4是本发明无人机集群分群算法流程示意图。 具体实施方式 [0047] 下面结合附图和实施例对本发明进一步说明。 [0048] 本发明旨在提出一种大规模无人机集群合并和分群方法，使无人机集群能够根据 不同的任务需要，灵活地调整集群的规模，以应对起飞、降落以及其他特殊任务的需求。并 通过合适的方法完成合并和分群过程中新领导者的确定，使集群在合并和分群之后仍然能 够快速达成协同状态的收敛，能够继续在受外部指令控制的条件下执行协同任务。 [0049] 为实现上述发明目的，本发明提出的技术方案如下： [0050] 首先对相关概念进行介绍： [0051] 通常情况下，大规模无人机集群是由相同的小型无人机组成，且无人机可以相互 通信，因此无人机集群的拓扑结构可以用无向图G＝(V,E)来表示，其中V＝{v,v ,…,v }表 1 2 n 示集群中所有无人机的集合， 表示无人机之间连接的集合。令 表 示与无向图G相关联的邻接矩阵，当a 为1时，表示无人机i和无人机j能够相互通信；当a ij ij 为0时，表示无人机j在无人机i的通信范围之外。集群中每架无人机的状态可表示为： [0052] [0053] n 其中x (t)表示各种与飞行状态相关的值，可以是速度、位置、加速度等标量或矢 量信息。如果对于一个集群中所有无人机的状态都收敛到领导者无人机的状态，则可以认 为无人机集群实现有外部控制的协同状态，即满足下式： [0054] [0055] 其中，x (t)表示领导者无人机的状态信息，由控制中心直接决定。 L [0056] 1、集群合并方法，如图2所示； [0057] 每个集群都有受地面基站直接控制的领导者无人机，因此地面基站可以根据不同 的任务需求，选取合适的数个无人机集群进行合并，执行协同任务。同时，因为合并之后的 集群仍然需要在外部指令的控制下执行任务，因此集群合并的过程可以总结为：地面基站 根据任务要求选取合适的集群并给集群的领导者无人机下达合并指令。不同集群的领导者 在接收到指令后开始先在各自集群达成协同状态，然后向指定区域汇聚。集群汇聚之后，地 面控制中心根据任务的需求、剩余续航时间、所在集群中无人机数目等评判指标在这几个 领导者无人机中选取一个作为合并后集群的新领导者。选择出新的领导者之后，其他集群 加入到新领导者所在的集群中，实现多个集群的合并。 [0058] 然而，在两个无人机集群执行合并指令的过程，只有两个领导者能够收到指令消 息并带领两个集群相互靠近，直到抵达相互可以通信的位置，然后合并为一个新的无人机 集群。在整个过程中，除了领导者无人机，集群中其他无人机并不知道任何关于合并的信 息，而集群中的无人机是通过与领导者的状态保持一致而实现集群的状态收敛。当两个集 群开始合并时，某个集群中的无人机既能够接收到另外一个集群的状态信息，又能够接收 7 7 CN 116400725 A 说明书 5/8页 到当前集群中来自领导者的状态信息，而无人机自身并不知道合并后的集群以哪边为主， 因此不知道该选取哪个状态作为自身的目标状态信息，这会造成集群合并过程的混乱，影 响集群系统的稳定性。 [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的领导者无人机Leader一 m 旦接收到来自集群n的消息，无论该消息是来自集群n的领导者Leader 还是集群n内的其他 n 跟随无人机，Leader 均执行合并指令，更改自身的领导者身份，变为集群n的跟随者，并以 m 所接收消息的来源无人机作为自身的父节点，加入到集群n所维护的生成树中。此时，集群m 的无人机变为了无领导者状态，在经过3次迭代之后，集群内生成树仍然无法更新，HB降为 0，集群m中的无人机将g_num置为0，表示为无集群状态，并可以接收来自任何集群的信息。 随后，原属于集群m的无人机接收到了集群n中的消息，更新并加入到集群n中的生成树中， 完成集群合并的过程。整个合并过程通过领导者先加入，跟随者变为无集群状态，随后再加 入新的集群，保证了集群合并的有序进行，对被加入集群的状态不造成影响，新加无人机的 状态也能够很快地与新集群保持一致，实现整个合并过程的协同状态稳定收敛。 [0061] 2、集群分群方法，如图4所示； [0062] 假设任务要求了需要划分的子集群的个数为n，那么如何快速根据现有的大规模 无人机集群的拓扑结构划分为n个子集群，快速确定新集群中的新领导者，并且整个过程开 销不能过大，保证整个集群在划分之后各个集群仍然能够维持协同工作的状态，是需要解 决的问题。 [0063] 为了解决集群划分的问题，引入割边集的概念，即图在划分之后两个不在同一个 子集中的节点之间的连线的集合，定义如下： [0064] EC＝{e s∈V,t∈V ,1≤i,j≤n,i≠j}                 (2) s,t i j [0065] 由于无人机集群的拓扑图是一个无权无向图，因此无人机集群的划分就可以看作 将一个连通的无向图划分为多个不连通的拓扑图，所以为了使划分最简单和快速，则需要 找到一种划分方法，使划分之后的拓扑图包含的割边数目最少，即min(EC)。 [0066] 遗传算法(GA)是一种高效实用的启发式算法，该算法是根据大自然中生物体进化 规律而设计的，是一种通过模拟自然进化过程搜索最优解的方法，它适用于并行过程处理 大规模优化问题。使用遗传算法解决最优序列问题，需要完成包括染色体表示、适应度函 数、交叉算子和变异算子四个内容的设计。 8 8 CN 116400725 A 说明书 6/8页 [0067] (1)染色体设计：在序列寻优问题中，节点排列的向量 可以用来表 示为染色体，该向量是节点编号的一个排列，也是最终的解集。同时，为了防止划分之后的 某个子集群为空，用向量 表示k个子集群中每个子集群所含节点的数量。 [0068] (2)适应度函数：由于前面的分析，最优的节点排列对应的邻接矩阵存在最少的割 边数目，又因为一个拓扑图中所有的边的个数是确定的，因此适应度函数可以记为： [0069] [0070] 只需找到适应度函数最大值时的节点序列，就是最优的划分节点序列。 [0071] (3)交叉算子：交叉算子需要两个父代染色体来进行结构重组，对两个父代染色体 进行特征合并，生成新的子染色体。重组的方法是：保留一个父染色体的主体部分，用另一 个父染色体中不重复的部分填补剩下的空白。如下例所示： [0072] [0073] [0074] [0075] [0076] 首先，随机选取两个由“”表示的交叉点，截取 的两个交叉点之间的元素并把这 些元素放到 的相同位置。接着，从交叉点位置开始，如果子代还没有相同的元素，取 的元素值并将其插入 的交叉点位置之后的第一个零元素所在位置。如果取值过程达到 的尾部或者插值过程达到 的尾部，就从向量的头部从头开始遍历。 [0077] (4)变异算子：变异算子可以增加染色体的多样性，为种群引入新的信息。这里通 过引入一个交换操作来实现变异。例如，随机选取父代中的两个元素3和7为变异点，然后这 两个元素交换位置，如下所示，即完成变异。 [0078] [0079] [0080] 完成上述操作后，对节点序列进行足够迭代次数的计算，求得最优的节点划分序 列。通过遗传算法，不再需要对节点排序使用暴力算法进行求解，而是把多个可能的序列作 为一代种群中的个体，然后通过执行交叉、变异等操作对种群进行更新，并重复上述操作， 同时记录每代种群中最大适应度的个体。当重复迭代达到一定次数时，就可得到最优的个 体，即最优的集群划分序列。 [0081] 在寻找到最优集群划分序列之后，断开割边两端无人机的通信，一个大规模无人 机集群就被划分为多个子集群。而根据任务的要求，划分之后的子集群仍然需要具备执行 协同任务的能力，即新的集群仍然需要具有领导者来接收外部指令信息，通过领导者对新 的集群进行控制，完成协同工作。因此，需要在划分之后的集群中寻找合适的无人机来当作 新的领导者。 [0082] 在一个集群网络中，某些关键节点对于整个网络具有重要的作用，这些关键节点 有时可以决定网络的结构以及功能，可以极大的提高整个网络的鲁棒性。而这些节点一旦 9 9 CN 116400725 A 说明书 7/8页 被攻击失效，将会对整个网络造成巨大的影响。其中，度中心性指标是一个经典的衡量节点 重要性的指标，即通过衡量节点的度数来挑选中网络中的关键节点。当某个无人机的度数 越大，证明与其直接交互的无人机越多，该无人机所处的为位置越重要，因此可通过度中心 性来寻找集群中的关键节点，并选其为领导者无人机。 [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)将邻接矩阵对应的节点排列表示为一个向量 通过对该向量的 变换来变换邻接矩阵，可以通过暴力搜索找到一个使邻接矩阵最接近块对角矩阵的排列 进而由该邻接矩阵和节点排列 可以确定割边集。但是暴力搜索时间复杂度太高， 因此考虑使用遗传算法求解最优节点排列； 10 10 CN 116400725 A 说明书 8/8页 [0097] 3)确定割边最少时的适应度函数， [0098] 4)将一个节点排列的向量 视为一个染色体，初始化固定染色体数目的初始种群； [0099] 5)在初始种群中，记录最大适应度值的个体； [0100] 6)在初始种群中随机选取个体执行交叉和变异操作，形成新的种群； [0101] 7)重复4)～6)； [0102] 8)达到指定迭代次数，得到最优个体，即最优节点排列； [0103] 9)根据最优节点排列对应的邻接矩阵，确定割边集，断开割边，完成分群； [0104] 10)在分群之后的各个子集群中，根据每个节点的度的大小进行排序，选择各集群 中度最大的节点作为每个集群的新领导者。 11 11 CN 116400725 A 说明书附图 1/3页 图1 图2 12 12 CN 116400725 A 说明书附图 2/3页 图3 13 13 CN 116400725 A 说明书附图 3/3页 图4 14 14

　　2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问加。

　　3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。

　　4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

　　《中小型企业文化建设中的问题研究—以三一重工为例》14000字.doc

　　《中小型企业员工离职原因与对策分析—以江铃汽车为例》10000字.doc

　　《重载机械臂末端负载动力学国内外研究现状的文献综述》6700字.docx

　　数字广告—新媒体广告创意、策划、执行与数字整合营销课件 第2章 数字广告媒体创意技术类型和应用.pptx

　　JB-TG-JF999 火灾报警控制器消防联动控制器使用说明书.pdf

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者PG电子手机版PG电子手机版