分簇技术的研究综述*

孙一凡，米志超，王 海，芦方旭，赵 宁

（1.陆军工程大学 电子与信息工程学院，江苏 南京 210007；2.中国电子科技集团公司第二十八研究所，江苏 南京 210007）

0 引言

近些年来，小型无人机在军事作战中显示出极大的优越性，“无人、分布、协同”是其三大显著特征[1]。在战场上，无人机配合重型武器常能达到出其不意、攻其不备的效果。通过无人机蜂群的灵活性，精准打击，降低我方伤亡风险。但如何控制数量众多的无人机一直是研究的重点。不仅是在军事作战中，使用分簇算法去管理大规模的网络一直是有效可行的方法。在分簇结构下网络规模是不受限制的，具有更好的可扩充性，并且路由开销会相对小一些。网络中节点被划分为多个簇，每个簇里都有簇首和簇成员，簇首维护和管理自己簇内的节点，负责簇内节点的通信，并为簇群之间的通信提供路由信息和寻找合适的路径。

1 拓扑结构分类

Ad Hoc 网络的拓扑结构有不同的分类，研究者们习惯于将其分为平面结构和分级结构[2]。如图1 所示，平面结构的网络复杂度较低，其中的网络节点具有相同的地位和功能，各节点之间相互协同合作完成通信，所以又称为对等式平面结构。

图1 平面结构的Ad Hoc 网络

如今，因为不同的任务需求，网络不断的开发，规模也越来越大，网络中的节点数量也随着越来越多。每个节点都互相交互信息去维护网络里所有的拓扑信息，无疑会增加网络开销。但是在网络复杂度更高的分级结构中，根据分簇算法将网络中的节点划分进不同的簇，每个簇由一个簇首、多个簇成员和网关节点组成，不同节点被赋予不同的功能。簇首形成高一级网络，分别负责不同簇内节点之间的通信，并提供路由信息和发现合适的路径，方便簇间节点通信。分级结构又可以被继续划分为单频分级结构网络和多频分级结构网络，如图2 所示。在单频分级结构网络中，所有节点都使用相同的频率通信，通过网关节点能够实现簇首节点之间的通信。与单频分级结构网络不同，在多频分级结构网络中，节点级别决定了节点的通信频率，级别不同的节点采用不同的通信频率，高级节点的通信范围大于低级节点，簇首节点可以使用两种不同的频率，一个用来维持与其他簇首节点之间的通信，另一个频率用来与本簇内的簇成员通信。

对等式平面结构和分级结构都不是完美的，各有优缺点：对等式平面结构网络的优势是其相对而言比较简单，网络中所有节点的地位都相同，没有上下级之分。在通信时，源节点与目的节点之间的通信路径有很多，可以避免网络瓶颈拥塞的问题，网络的安全系数也相对较高。就网络规模来看，对等式平面结构网络规模较小，且当网络规模扩大时无法解决路由维护开销和带宽消耗之间的矛盾。相对而言，分级结构网络的复杂度更高，网络规模不受限，具有良好的可扩展性，在对网络节点分簇的情况下，可以相对降低网络路由的开销。

图2 分级结构网络

当下Ad Hoc 网络正逐渐呈现出分级化的趋势，许多网络路由算法也基于分级结构的网络模式被提出和改进。为了更清晰地理解这两种分类各自的特点，将平面路由和分簇路由的特点进行宏观比较，见表1。

2 不同分簇方案

分簇是将移动节点划分为不同的虚拟群组的过程[3]。如图3 所示，分簇方案需要考虑多个方面，如网络的用途、所处的环境、规模等各个方面。分簇的过程可分为主动、反应式和两者兼而有之的混合分簇。簇内的节点也根据其功能进行分类，如簇首、簇成员和网关节点。簇首的职责是管理簇成员，处理簇间的通信和向基站的数据传输。同时处在多个簇首传输范围内的节点，我们将其称为网关节点。网关节点的用处是帮助相邻簇之间转发数据。除了网关和簇首之外的任何其他节点都是成员节点，也称为普通节点。在簇首选择过程中，确定了网络节点的剩余能量、相对移动性、可靠性、通信工作量等重要参数[4]。

表1 平面路由与分簇路由特点比较

图3 分簇方案

3 在无线传感器网络中的应用

在无线传感器网络（Wireless Sensor Networks，WSN）中，基于分簇的模型具有较好的节能效果。然而，在动态环境中管理簇内的节点是一个开放的挑战。选择簇首（Cluster Head，CH）无疑是分簇过程中的要点和难点，要考虑诸多因素是否会影响网络性能。虽然已有一些研究提出了CH 选择方法，但大多数都不适合动态分簇环境。针对这一问题，有的研究员提出了基于模糊逻辑、遗传算法和神经网络的智能算法。然而，这些算法在单跳分簇模型框架中工作得更好，在多跳分簇环境中，网络生存期是一个大问题。文献[5]提出了一种基于遗传算法的单跳和多跳分簇模型的CH 选择方法。该方法旨在满足动态环境的要求，基于六个主要特征选举CH，即剩余的能量、消耗能量、附近的邻居的数量、能量感知距离、节点的鲁棒性和节点迁移度。文章提出的算法经实验结果表明，大大延长了网络寿命。

文献[6]提出的是一个基于网格结构的无线传感器网络分簇路由算法。根据面积大小和传输范围，计算出合适的网格大小，构造出虚拟网格结构。在每个网格中，根据到网格中点的最近距离选择一个簇首。为了在网格中转发数据，遵循局部单通路策略。为了将数据从簇首转发到接收点，实现了基于角的倾向的组合路由模型。在数据收集、目标监控以及应用在无线传感器网络等方面，蜂群无人机得到了越来越广泛的应用。在无线传感器领域，无人机被用来创建一个更灵活的数据收集平台。这种集成通过优化能量预算，使WSN 的寿命最大化。在文献[7]中，作者利用无人机的这些优点，提出了一种最优簇首选择策略来最大化WSNs 的生存期。该方法利用无人机各传感器节点的平均剩余能量、信道条件和欧氏距离来确定一组CHs。与现有的解决方案相比，该方法能够最大限度地提高无线传感器网络的寿命。

4 在自组织网络中的应用

分簇算法在车载自组网中一样得到了应用。文献[8]选择最接近集群中心地理位置的车辆作为簇首，从簇首的一跳邻居集中选择向同一方向移动的节点作为簇成员。

由于节点的移动性，MANET 中的网络拓扑变化十分频繁。当一个节点的迁移信息被共享给网络中的所有节点时，拓扑维护会产生额外的开销。为了解决MANET 中的拓扑维护开销问题，研究人员提出了不同的基于簇群的算法来减小路由表的大小。簇的形成是为了局部地调整簇内的拓扑变化。如果一个节点希望与簇群外部的节点通信，那么它只与自己的簇首通信。CH 与其他CHs 通信，将数据传输到目的地。为了有效地利用MANET 中的分簇机制，需要稳定、均衡的簇群。一些度量指标有助于优化且形成质量良好的簇群，如相对移动性（节点速度、方向等）、节点度、剩余能量、通信工作量和邻居节点的性能。文献[9]总结了近年来MANET 的分簇情况，还介绍了最近研究的目的、目标和贡献。同时，对研究结果、面临的挑战和未来的发展方向进行了阐述。

传统的Ad Hoc 路由协议在机载网络中由于飞机的运动而面临挑战，经常导致链路中断，链路重新建立的过程不可避免地会引起拓扑结构的变化。针对这些问题，文献[10]中作者利用了能够安装在无人机上或悬停的飞机上的网状路由器。由于这些网格点之间通常具有相对稳定的连接，所以它们起到簇首的作用，形成分层的路由结构。在分簇管理中引入一个简单的自组织规则来限制簇群控制开销和路由发现洪泛。此外，路由协议中还可以部署容错机制（Dynamic Turn Management，DTM），提高对临时链路或节点故障的弹性。

文献[11]提出了一种新的基于全球定位系统（Global Positioning System，GPS）的自组网路由协议——基于区域的分层链路状态（zone-based two-level link state，ZHLS）路由协议。在该协议中，网络被划分为多个区域而且每个区域之间互不重叠。每个节点只知道其区域内的节点连接和整个网络的区域连接。链路状态路由在本地节点和全局区域两个级别上执行。与其他分层协议不同的是，这个协议中没有簇首节点。区域级拓扑信息分布到所有节点。这种点对点方式缓解了流量瓶颈，避免了单点故障，简化了移动管理。由于只需要目的地的区域ID 和节点ID 进行路由，因此从源到目的地的路由可以适应不断变化的拓扑结构。通过向每个区域发送一个位置请求，就可以找到目的地的区域ID。位置搜索方案比基于洪泛的方案产生更少的开销。在该协议中创建和维护拓扑的通信开销要小于平面LSR 协议。这种新的路由协议提供了一种灵活、高效和有效的方法来适应无线网络环境中不断变化的拓扑结构。

最近的研究活动已经认识到节点移动性对于在移动自组网中创建性能良好的、稳定的、可伸缩和自适应群的重要性。文献[12]提出了一种基于群迁移率的分布式分簇算法（Group mobility based clustering），并根据节点的瞬时速度和方向推导出一种修正的群迁移率度量。我们的动态分布式分簇方法使用高斯马尔可夫群迁移率模型进行迁移率预测，使每个节点能够预测其相对于邻居的迁移率。簇首具有相对较低的迁移率、较大的能量储备和较高的连通性。特别适用于反映移动群体普遍存在的群组分离和融合行为的群体移动模式。我们还考虑了节点的剩余能量以及相邻节点的数目，提出的聚类方案旨在通过减少分簇迭代来形成稳定的簇群。仿真结果表明，比较平均簇首变化数时，该框架的性能优于两种著名的聚类方法MOBIC和DGMA。

节点的动态网络拓扑结构和移动特性可能会对连通性和路由造成挑战。针对大型的移动自组网，各种各样的分簇方案是可以根据网络拓扑变化来重新优化组织网络的有效方法之一。在文献[13]中，作者提出了一种基于区域群移动性的自组织分簇（Self-Organization Based Clustering）方案来提高整个网络的可扩展性和稳定性。该算法利用鸟类群集的生物启发行为研究，以形成和维持MANET 的分群。提出了一种动态的考虑簇大小的管理机制，以减少网络拥塞，提高MANET 在群组移动性能方面的性能。为了合理利用资源，降低额外的能耗，提出了一种合理处理孤立节点的算法。根据节点接收信号的强弱将节点进行分区，簇内结构被分为三种不同类型的区域：簇首、节点吸引区域和节点排斥区域。算法流程包括节点状态识别、簇首选择以及孤立节点处理。仿真结果表明，文献中提出的改进算法有效降低了网络的能耗开销，提高了网络中节点的生存时间，使网络结构更加稳定具有较强的鲁棒性。

近年来，就小型无人机广泛应用的优势来说，基于通信网络的合作可以有效地扩大无人机的工作范围。虽然无人机网络与传统的移动自组织网络非常相似，但是相关文献中并没有考虑到无人机应用场景的特殊性。针对无人机网络的应用特点，文献[14]提出了一种适用动态网络的分布式网关选择算法。该算法通过将网络划分成多个子区域来减弱信息不对称现象对无人机拓扑控制的影响。在网络运行过程中，即使无人机移动速度较快，也可以通过自适应调整网络的分区来保持整个网络拓扑结构的稳定。同时，可以完全控制网关的数量，每个子区域的大小可以根据目标的分布进行调整。特别是定义了无人机网络的稳定性，建立了网络划分模型，设计了分布式网关选择算法。仿真结果表明，在该方案中，不管节点移动速度变慢或变快，拓扑结构都能相对保持稳定，所以这个方案十分适用于无人机组成的移动自组网。

随着无人机的广泛应用，迫切需要构建无人机组网网络以提高整体作战效率，其中应采用移动自组网架构。在文献[15]中，作者提出一种新的路由协议来解决无人机编队网络中的路由问题，称为基于簇群的位置辅助动态源路由协议（Cluster-Based Location-Aided Routing Protocol，CBLADSR）。CBLADSR 以形成稳定的无人机机群集群结构为基础，利用无人机的地理位置进行航路发现和航路维护。分簇过程采用节点权重启发式算法选择簇首，形成簇。路由过程是由簇内路由和簇间路由的组合而成，分别采用短程传输和远程传输。CBLADSR 采用基于斜率的转发策略，在邻居节点中，选择其中斜率最小的作为下一跳转发节点。仿真结果表明，CBLADSR 在成功交付率、平均端到端时延、可扩展性和动态性能等方面明显优于DSR 和GRP，更适合应用于无人机编队网络。

5 结语

如今，因为不同的任务需求，网络规模在逐渐扩大，网络中的节点数量也会随着不断增加。节点需要维护网络里所有的拓扑信息，无疑会增加网络开销。但是在分级结构中，根据分簇算法将网络中的节点划分成为相应的簇，每个簇由一个簇首、多个簇成员和网关节点组成，不同节点被赋予不同的功能。当下Ad Hoc 网络正逐渐呈现出分级化的趋势，基于分簇技术，越来越多的网络路由算法被提出和优化改进。