无线传感器网络中分簇算法综述

何枭宇 姚彦鑫

摘要：在无线传感器网络领域中分簇算法是十分典型的算法，并在其中起着非常重要的作用。文章从能量消耗和网络生命周期的角度出发，根据在成簇时是否随机选择簇头，将分簇方法分为两大类。随后，文章列举了当前常见的分簇算法，并以近年来出现DCEM（Delay-Constrained Energy-Efficient Cluster-based Multi-Hop Routing）算法为例，详细描述了其分簇过程，该方法相对于其他方法降低了网络能量损耗，同时延长了网络生命周期。最后，结合现阶段该领域的科研现状，展望了这一研究方向在未来的发展趋势。

关键词： 无线传感器网络； 分簇算法； 能耗均衡； 网络生命周期； 簇首选择机制

中图分类号：TN92 文献标识码：A

文章编号：1009-3044（2019）09-0028-03

Abstract：Clustering algorithms are very typical algorithms in the field of wireless sensor networks and play an important role in them. From the perspective of energy consumption and network life cycle， the paper divides the clustering method into two categories according to whether cluster heads are randomly selected at the time of clustering. Subsequently， the article lists the current common clustering algorithm， and takes the DCEM （Delay-Constrained Energy-Efficient Cluster-based Multi-Hop Routing） algorithm in recent years as an example to describe its clustering process in detail. Other methods reduce network energy consumption while extending the network life cycle. Finally， combined with the current research status in this field， the future development trend of this research direction is forecasted.

Key words：wireless sensor network； clustering algorithm； balanced energy consumption； network life cycle； cluster head selection mechanism

1 引言

无线传感器网络（Wireless Sensor Network，即WSN）是由很多廉价的并具有传感、计算、数据处理和通信能力的微型传感器节点组成的网络。WSN无论在任何条件下都能够通过节点间的通信，来完成对所需信息的采集和处理工作，逐渐广泛应用于需要进行感知监测的各领域，如军事领域、工业领域和环境领域等。

在WSN中如果每一个节点都单独进行数据传送，这样就会导致网络中数据过于庞大，而且还会发生信息碰撞，从而使能量无端地被浪费掉。为了避免这种情况的发生，节点被分为很多小的集合，称为簇，这个把单个节点集合成群的过程称为分簇。这种思想首次被提出是在分组无线网中，每个簇内需要选举出一個簇头（Cluster head），它是用来采集本簇中其他节点的信息的，汇总后发送到汇聚节点（sink）或基站（BS），簇内除了簇头的其他节点被称为成员节点（Cluster menber），如图1所示。文章将WSN中的分簇算法按照选取簇头时是否随机选取分为两大类，并对这两类算法进行了总结，在此基础上具体描述了近年来新出现的DCEM算法中的分簇方法。

2 典型的分簇算法

本章节按照在分簇过程中簇头的选取是否随机，将分簇算法归结为两大类，其中第一类随机选取簇头的分簇方法主要包括LEACH（Low-Energy Adaptive Clustering Hierarchy）[1-5]和TEEN（Threshold sensitive Energy Efficient sensor Network protocol）[6-8]算法，另一类根据节点信息选取簇头的分簇方法主要包括HEED（Hybrid Energy Efficient Distributed Clustering） [9-10]、EEUC（Energy Efficient Unequal Clustering）[11-14]、UCFIA（Unequal Clustering Algorithm for WSN based on Fuzzy Logic and Improved ACO）[15] 和近年来提出的DCEM[16]算法。

2.1 随机选取簇头的分簇方法

WSN的分簇算法中，LEACH 和TEEN算法是较为传统的分簇算法。两种方法在选择簇头的过程中都是节点随机生成0-1的随机数，只要该值大于阈值就可以被选为簇头，设定值是根据簇头被选择的几率和网络在此刻运行的轮数计算出来的。

LEACH中，在簇开始成立的阶段，每个节点根据系统给节点分配的随机数和阈值的大小关系来判断自己是否能够成为簇头；接着，每个节点在收到簇头信息的同时，依据这个信号的强度来判断被选入到哪个簇，而且每经过一段时间网络便会重复以上过程。在数据传输阶段，簇内节点按照时分复用（TDMA）方式向簇头发送信息。

TEEN与LEACH十分类似，两者的不同之处在于数据传送阶段，TEEN中有硬、软阈值，通过合理的调节这对值的大小可以降低系统能耗。

随机选取簇头方法的缺点为簇头的选择完全是不确定的，选取的簇头不一定最为合适，因为没有考虑到节点自身的信息，同时，所选数量也很有可能不适合这个网络。相比这两种经典的算法，下面我们将介绍的几种在簇头选择时考虑节点的能量值和位置信息等因素的算法。

2.2 根据节点信息选取簇头的分簇方法

HEED 算法分簇时，节点归属于哪个簇是根据它自身接收到的簇头信息中携带的AMRP（Average Minimum Reachability Power）平均最小可达能量来进行判断的，一个节点同时入选两个或者多个簇的情况则可以避免。如果一个节点没有接收到任何一个簇头的信息，它便被判断为“孤立节点”从而自成一簇，这种方法会导致网络稳定性不好，原因是没有把邻居节点到簇头节点的距离考虑进去，这样形成的簇很不均匀，在出现大簇的同时还会出现一些孤立节点，使得的某些节点生命周期变短，从而导致网络不稳定。HEED算法是依据节点的剩余能量，进行多次迭代来选择簇头，這就导致了在这个过程中能量消耗的代价过大。

EEUC算法分簇时，采用大小不同的竞争簇半径，使得与Sink节点距离小的节点成簇半径较小，这样节点可节省一部分能量从而有更多的能量去帮助转发数据。由于簇半径有差异，网络被分成多个不均匀的簇。数据传输过程中，该算法分为单跳和多跳情况，若簇头到 Sink节点的距离小于预先设定的最大值，则以单跳的方式完成簇头与Sink节点的信息交换；否则采用多跳方式，其中在挑选下一跳节点时，若有比自身到Sink距离更近的多个簇头，挑选本轮次拥有能量相对多的作为下一跳。该算法的优点是距Sink节点较近的簇较小，反之较大，这种非均匀成簇的方式很大程度上缓解了一些节点过度使用的问题，但是由于数据传输阶段，未将簇规模和其参与转发次数考虑进来，还是没有尽可能地到达网络能耗的均衡。

UCFIA算法在分簇时利用包括节点剩余能量，与Sink节点的距离等信息，来判断试探性簇头成为簇头的可能性及其成簇半径，采用模糊逻辑模块来处理选择簇首和确定簇大小的不确定性。在传输数据的过程中，使用自适应最大—最小蚁群优化算法来找到从簇头到Sink节点的最高效路径，并且在这个过程中考虑了簇间流量的特征来平衡簇头能耗。该算法中的许多参数，比如最大局部密度、最大竞争半径等还可以进一步进行优化，以提高网络的性能。

2016年提出的DCEM分簇多跳路由算法相比经典分簇路由算法，在能量损耗，生存节点等指标有所提高。下一章节将对DCEM算法中的分簇过程进行具体说明。

3 DCEM算法中的分簇方法

分析发现：按照上述过程会使得能量大的节点先发出信息，能量小的节点接收到能量大的节点信息后会自动变为其簇内节点。（4）变成备选的簇头节点有两种情况，一种是节点向外广播了ADV信息，但并未收到其他节点的ADV信息，则该节点成为簇头备选节点；另一种则是节点向外广播了ADV信息，虽然收到其他节点的ADV信息，但是自身能量更高，该节点也成为簇头备选节点。（5）有一种情况需要特别处理，即当两个簇头备选节点能量大小一样，并且可以通信，那么每个备选簇头节点需要经过等待时间后收到最终簇头节点发送的信息，然后簇头备选节点取消其计时器，成为当前轮的簇内节点。

DCEM算法在分簇的过程中，能量较大的簇头节点形成相对较大的簇，反之形成较小的簇，充分发挥了节点的能量优势，使得能量得到合理的利用。同时，相比其他算法由于考虑到了簇相交部分节点的归属问题，使得节点的归属更加明确，划分更加合理。

4 结论

无线传感器网络在我们生活中起到了不可或缺的作用，逐渐广泛应用于需要进行感知监测的各领域，如军事领域、工业领域和环境领域等，给人们生活带来方便的同时也给技术带来了挑战。其中的分簇算法引起了学术界的极大关注，文章通过总结WSN中的主要分簇算法，并对常见的相关算法进行了归纳和比较，为今后对分簇算法的研究打下了基础。希望在不久的将来，可以提出更完善的分簇算法并应用到实际生活中。

参考文献：

[1] Huynh T T， Dinh-Duc A V， Tran C H. Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks[J]. Journal of Communications & Networks， 2016， 18（4）：580-588.

[2] Kaur J， Sahni V. Survey on Hierarchical Cluster Routing Protocols of WSN[J]. International Journal of Computer Applications， 2015， 130（17）：18-22.

[3] Yadav S， Yadav R S. A review on energy efficient protocols in wireless sensor networks[J]. Wireless Networks， 2015， 22（1）：1-16.

[4] 任智，姚玉坤，曹建玲.无线自组织网络路由协议及应用[M].北京：电子工业出版社，2015：82-83.

[5] Yang L， Lu Y Z， Zhong Y C， et al. A hybrid， game theory based， and distributed clustering protocol for wireless sensor networks[J]. Wireless Networks， 2016， 22（3）：1007-1021.

[6] Rao P C S， Jana P K， Banka H. A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks[J]. Wireless Networks， 2017， 23（7）：2005-2020.

[7] Manjeshwar A， Agrawal D P. TEEN： A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]. Parallel and Distributed Processing Symposium. Proceedings， International. IEEE， 2002：189.

[8] Manjeshwar A， Agrawal D P. APTEEN： a hybrid protocol for efficient routing and comprehensive information retrieval in wireless[C]. Parallel and Distributed Processing Symposium. Proceedings International， IPDPS 2002， Abstracts and CD-ROM. IEEE， 2002：8 pp.

[9] 楊彩霞. 基于无线传感器网络的集中式分簇算法研究[D]. 兰州交通大学， 2016.

[10] Younis O， Fahmy S. HEED： A Hybrid， Energy-Efficient， Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2004， 3（4）：366-379.

[11] Krishnamoorthy S. Enhanced Adaptive Clustering Mechanism for Effective Cluster Formation in WSN[J]. Social Science Electronic Publishing， 2017.

[12] Li C， Ye M， Chen G， et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference. IEEE， 2005：8 pp.-604.

[13] Lv Y， Miao Z， Zhang D， et al. A Low Energy Uneven Clustering Topology Control Algorithm for Wireless Networks[C]. International Conference on Information Science and Control Engineering. IEEE， 2016：1203-1207.

[14] Jiang C， Ren Y， Zhou Y， et al. Low-Energy Consumption Uneven Clustering Routing Protocol for Wireless Sensor Networks[C]. International Conference on Intelligent Human-Machine Systems and Cybernetics. IEEE， 2016.

[15] 蒋畅江. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报， 2012， 34（5）：1222-1232.

[16] Song M. Unequal clustering algorithm for WSN based on fuzzy logic and improved ACO[J]. The Journal of China Universities of Posts and Telecommunications， 2011， 18（6）：89-97.

【通联编辑：代影】