无人机自组网的动态双簇首分簇算法研究

范 淼，谭小波，徐 琪

(沈阳理工大学信息科学与工程学院，沈阳 110159)

近年来，随着无人机技术研究的不断深入，无人机在军事场景和民用领域的应用越来越广泛，比如情报侦查与监测[1]、精准农业播种[2]、灾害的预测与管理[3]、环境状况监测[4]、空中临时基站[5]、国土安全[6-7]、互联网交互[8]、运输货物[9]和建筑监督[10]等。 无人机受到自身电量、飞行能力以及载荷等硬件因素的限制，通常难以完成复杂的工作任务，因此弹性的无人机集群[11]协同作业成为趋势。

由于无人机工作时自身的高移动性[12]、位置分布不均匀[13]等不确定的因素，无人机集群有时会遇到通信中断、节点失效等紧急情况[14]。 因此，面对未来各种恶劣环境条件[15]和复杂的应用需求，确保在复杂、变化的环境中能够迅速完成组网和保证良好的通信，合理的分簇算法和高抗毁性的路由协议[16]是研究的关键。 无人机自组网是一种临时多跳无中心的自组织网络，不依赖于地面控制站或卫星等基础通信设施，而是将无人机作为网络节点，各节点间能够相互转发指令，交换感知态势、健康情况和情报数据等。 常用分簇算法有基于身份(ID)认证的分簇算法、基于连接度的分簇算法和基于节点权重启发式的分簇算法和链路分簇算法(Link Clustering Algorithm，LCA)等。 但是现有的分簇算法在面对频繁的网络拓扑变化、节点快速移动等极端情况下并不能保证较好的网络性能，网络的通信能力略显不足，网络的抗毁性差。 本文针对单簇首抗毁性低的问题，提出双簇首的结构，设计动态双簇首(Dynamic Double Cluster Head，DDCH)分簇算法，以使网络形成更为合理、有效的拓扑结构。

1 动态分簇算法设计

1.1 动态分簇算法的提出

针对前文提到的传统分簇算法单簇首抗毁性不足和不能合理分簇的问题，本文设计双簇首结构提高抗毁性，使用动态分簇算法进行合理分簇。

传统分簇算法的改进方向是减少孤立节点的产生，而动态分簇算法的设计原则是只要满足分簇条件，就会产生孤立节点。

对于整个网络来说，按照动态分簇的原则，部分节点采用分簇结构，没有选择分簇的孤立节点采用平面结构。 对于某个局部网络，是否分簇是通过比对同一个局部网络分簇结构与平面结构下相同属性的优劣程度来决定。

由基于链路过期时间的网络拓扑图分别计算以发起分簇选择的节点为中心的星型网络结构和拓扑图最大生成树结构，当该星型网络的边集与最大生成树的边集重叠度满足k值，即网络节点分簇比例时，说明星型网络的部分结构属于该局部网络的最优通信结构，选择分簇。 如果重叠度不满足k值，则不选择分簇，网络不再进行后续的分簇操作。

1.2 Prime 算法

在无人机自组网中，节点的高移动性会导致节点间链路不稳定和通信时间过短的问题，选取的路由链路过期时间越短，路由的可靠性和有效性越低。 所以，在动态分簇的决策阶段采用以节点间的边为优先选取原则的Prime 算法，算法描述如下。

1)通过计算节点间的链路过期时间、节点的位置与移动信息得出局部网络的拓扑图，其中顶点，即无人机自组网节点集合为V，边集合为E，权值为边所连接的两节点的链路过期时间。

2)设Vnew＝{VM，VN}，Enew＝{ ＜VM，VN＞}，其中Vnew是目标最大生成树的顶点集，Enew是目标最大生成树的边集，VM为发起Prime 算法的节点集，VN为VM邻居节点集。

3)重复下列操作，直到Vnew＝V。

①在集合E中选取权值最大的边＜u，v＞，其中u∈Vnew，v∈V且v∉Vnew。 如果存在多条满足前述条件，即具有相同权值的边，则任取其中之一。

经过10天的现场检查，在20日召开的督导反馈会上，督导组充分肯定了曲靖供电局工作，并从现状和总体评价、存在的问题及对策、投资成效评估等五个方面，对曲靖供电局配电网规划建设和运营情况进行了分析，总结了经验，提出了要求。曲靖供电局局长施勇、云南电网公司规划建设研究中心副主任莫海峰等先后发言。

②将v加入集合Vnew中，将＜u，v＞边加入集合Enew中。

4)输出顶点集Vnew、边集Enew。

1.3 链路过期时间

为后续给动态拓扑图的边赋值，需要计算两节点间链路过期时间，即计算节点间剩余的有效通信时间ECT，原理如图1 所示。 假设存在节点i与j在初始时间处于通信范围之内，链路过期时间后两节点相距最长通信距离，则有

图1 ECT 计算

式中:(Xi，Yi)、(Xj，Yj)为节点i与j的坐标；DISc为节点通信范围；DISx为节点i与j在x轴方向的通信范围；DISy为节点i与j在y轴方向的通信范围；ECT为节点间剩余的有效通信时间为节点i与j在x轴方向移动的速度为节点i与j在y轴方向移动的速度；VX、VY为节点i与j之间分别在x与y轴方向上的速度。

1.4 动态分簇算法描述

1)网络初始化，无人机节点i通过GPS 获得其节点信息，包括节点坐标Xi和Yi、节点的速度信息和，规定以东和北方向为x轴与y轴移动的正方向。

2)网络各个节点广播自己的节点信息。

3)当节点收到邻居广播的信息后，计算出与邻居节点剩余有效通信时间ECT。 设TMINT为最小通信时间阈值，其中ECT＜TMINT的邻居节点不计入是否成簇的计算。

4)如果节点i的节点度di≤3，则不进行后续分簇计算，等待接受成簇消息。di＞3 的节点向邻居节点中ECT最大的节点j发送自己的邻居表信息。

5)当节点j接收到邻居节点i发送的邻居表信息，先对局部网络成簇或不成簇进行最优选择的计算，如果收到多个邻居节点的邻居表信息，只计算最先收到的信息。 取两节点邻居集的交集VNei，加上发送与接受信息的两节点，得出局部网络拓扑图，拓扑图中两节点之间存在边，代表连接边的两个节点处于通信范围之内，边的权值为两节点最长链路过期时间。 通过该拓扑图计算两个生成树，其中生成树T1 为局部网络拓扑图最大生成树，采用prime 算法生成，且初始生成树子集包含发送与接收邻居表的两节点；生成树T2 为以发起分簇选择的节点为中心的星型网络结构，以进行分簇计算的节点从邻居表接收节点，向剩余节点取边集，最后得到边集ET1和ET2。 若两边集满足

即满足网络节点分簇比例k，则进行分簇，向周边节点发送成簇信息。 节点i和j中节点度大的一个成为副簇首，另一个成为主簇首；否则选择不成簇，将节点设置为孤立节点。

6)当孤立节点收到多个成簇信息时，选取k最大的节点，返回确认成簇信息。 当簇首节点收到成簇通知时，优先以收到的簇为准。

7)当节点在一定时间内没有收到任何成簇通知，则成为孤立节点，孤立节点从结构上同时兼职主副簇首，形成簇节点数只有一个的特殊簇，运行纯平面路由协议。

2 簇结构的维护机制

2.1 簇信息的维护和优化

在双簇首结构中，主簇首负责簇内节点间的通信，副簇首负责簇间节点的通信，双簇首都需要定期广播报文以维护簇内节点以及邻居节点信息，簇的维护机制如图2 所示。

图2 簇的维护机制

对于双簇首结构，只有当簇内的某个节点同时处于两个簇首的通信范围内时，认为该节点存在该簇内。 同时，为保证双簇首的抗毁机制，双簇首需要高频消息交互维持联系。 所以，节点没必要同时对两个簇首都进行回复。 如果节点在接收时间限制内可以收到双簇首的广播簇维护消息，则只需要对主簇首进行回复即可以维护簇结构，并将标记位设置为001，报文级别设置为一级；如果没有收到另一个簇首的消息，则对发送方进行正常的路由回复，优化后的簇维护机制如图3 所示。 当主簇首收到标记位为001 的节点的回复报文时，将节点加到簇信息表中，主簇首定期与副簇首通信时发送该表，副簇首通过接收主簇首发送的簇信息表维护簇内节点信息。

图3 优化后的双簇首簇维护机制

2.2 节点的加入

当一个孤立节点收到两个簇首的广播时，分别计算与双簇首的链路过期时间。 如果两个时间中较短值依然大于入簇时间阈值，该节点对主簇首发送路由回复消息，标记位设置为010，即可加入簇，主簇首收到标记位为010 的回复消息时，将节点信息加入到簇表，并发送给副簇首。 如果是簇首节点移动到另外的双簇首的通信范围内，并且计算与双簇首的最长链路过期时间均大于与自身簇的另一个簇首的链路过期时间，则选择解散该簇首节点所在的簇，并且加入新的簇。

2.3 节点的离开

在无人机自组网中，节点位置是会改变的。当簇内节点收到额外的双簇首的广播信息时，将其信息加入备用簇信息。 当节点不能收到原双簇首的簇维护消息时，或者收到簇首发送的簇解散消息，则代表节点不属于原簇。 此时，如果节点保存了备用的簇信息，则直接向备用簇的主簇首返回入簇消息，加入备用的簇；如果节点没有保存备用的簇，则代表此时节点并不处于任何一个簇的双簇首的通信范围，不能采用簇的通信机制，节点将自己的簇属性重置，并设置自身为孤立节点。

2.4 簇的毁伤检测与重组

在普通的单簇首结构中，维护簇的功能主要在簇首节点上，单簇首通过频繁的广播信息让簇内节点和骨干网络中的邻居簇首获取簇首信息。因节点对该簇首的感知只能来自簇首本身的广播信息，当出现簇内节点接收不到簇首的广播信息时，不能判断原因。

在动态分簇阶段，可以成为双簇首的两个节点必定是在局部网络中链路过期时间最长的两个节点，而当双簇首都离开有效通信范围时，代表该簇已经到达了不稳定的时候，簇内其他节点也不足够稳定，此时没有必要继续维持该簇。 当双簇首收到了毁伤的消息时，双簇首广播簇解散消息以解散该簇，并将自己设置为孤立节点。 毁伤检测机制如图4 所示。

图4 毁伤检测机制

当没有节点可以同时收到两个簇首的毁伤检测消息时，可能因为某个簇首已经受到来自外部的攻击，无法广播毁伤检测，也可能是因为短时间移动距离过大，在双簇首的通信范围交集内不存在节点。 当簇首节点在一定时间内只能接收到毁伤消息，则证明另一个簇首因为高移动性或者外部毁伤而离开通信范围。

如果簇首因为自己的高移动性离开了原始的簇，其原因多出于临时状况，或者因为受到攻击导致丧失性能，此种由于节点本身原因而导致簇首结构的解散，对簇本身并没有影响，说明簇本身依然具备构成成簇的条件。 为保证簇的稳定性以及发挥双簇首高抗毁性的优势，进行簇的重组，单簇首变成传统的单簇首结构，并进行新的双簇首选举。

2.5 簇的解散

当需要进行簇的解散时，如果双簇首仍处在通信状态，则解散发起者向另一方簇首发送簇解散请求，同时广播簇解散消息。 当另一个簇首收到解散请求时，停止广播簇维护报文并广播簇解散消息。 簇内节点在一定时间内没有收到双簇首的维护消息，并且收到簇解散消息，则代表该簇已经解散。 如果双簇首不在通信范围之内，则各自广播簇解散消息，收到簇解散消息的节点如果没有备用簇，则直接将自己设为孤立节点，该簇解散。

如果双簇首维护的簇内节点少于两个时，为了维护簇组织结构需要两个簇首频繁广播维护消息，但为了维护少于两个成员的簇而增大两个簇首的维护开销是不合适的，说明该簇已没有存在的必要，则由主簇首主动发起簇解散，直接广播簇解散消息，并将节点属性设置为孤立节点。

3 仿真与验证

3.1 仿真场景与参数设置

采用NS-2 平台对提出的动态双簇首分簇算法进行仿真，仿真场景的大小设置为1 000 m×1 000 m，采用随机移动模型。 节点通信半径设置为250 m，业务流采用恒定比特率业务(CBR)。为测试不同变量对分簇算法的影响，本文设定节点数量与k值作为变量，固定移动速度为20 m/s。仿真平台配置与参数设置见表1。

表1 仿真平台配置与参数设置

3.2 仿真结果分析

本文的仿真实验将DDCH 算法与传统的LCA 算法相对比以验证DDCH 算法的可行性与优越性。 对动态分簇算法，着重评估算法对网络的划分能力。 对比k值分别为0.25、0.33、0.5 时的DDCH 与LCA 分簇算法，考虑分簇算法对网络分簇率(CR)、平均每个簇的节点数量(NNSC)的影响。 仿真结果如图5、图6 所示。

图5 不同节点数量的CR

图6 不同节点数量的NNSC

由图5 可见，影响DDCH 算法分簇率最明显的属性是k值，因为k值是直接决定分簇与否的阈值；其次，随着节点数量的增加，分簇率有不同程度的减少，因为当节点数量增加，拓扑结构中的边也随之增加，使星状拓扑较难覆盖最大生成树。传统的LCA 算法一直保持极高的分簇率，但由图6 可见，尽管LCA 算法分簇率高，但由于是低效分簇，传统的LCA 算法对于簇节点的管理不如DDCH 动态分簇算法，DDCH 用更少的簇首管理了更多的节点，平均每个簇的节点数量更高，分簇更为合理。

4 结论

本文设计了动态双簇首分簇算法DDCH，DDCH 可以有效解决局部网络分簇不合理的问题，通过动态的分簇，可以让无人机自组网在不同的局部网络形成不同的网络结构。 双簇首结构可以有效解决单簇首抗毁性不足以及过多的簇首导致路由开销过大的问题。 双簇首分别处理簇内与簇间的通信，可以有效降低单簇首的负载；针对双簇首结构特点，设计了相应的簇维护机制，优化了簇的维护成本，加入了关于毁伤检测的机制，增大了簇的抗毁性。