基于能量平衡的WSN簇头选择机制

摘要：通过对已有的基于簇的自组织路由算法和簇头选择机制的分析比较，发现经典LEACH算法在选取簇头节点时具有不合理性，提出了一种基于PSO模型的簇头选择机制。以网络总体能量消耗最小为原则，综合考虑节点剩余能量和网络当前平均能量，较好地平衡了无线传感器网络中的能量负载，延长了网络的生命周期。

关键词：无线传感器网络；微粒群算法；能量平衡；簇头选择

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）25-5905-04

Cluster Head Selection Mechanism for WSN Based on Energy Balance

ZHENG Lei

（Department of Computer Science， Nanjing University of Science & Technology Zijin College， Nanjing 210046， China）

Abstract： Through analysis and comparison of the existing self-organizing cluster-based routing algorithms and the cluster head selection mechanism， this paper finds that classical LEACH algorithm is unreasonable in the election of cluster head nodes， and proposes a PSO-based cluster head selection mechanism. Following the principle of the overall network energy minimization， and considering both of the residual energy of each node and the average energy of current network， the improved algorithm is better able to balance the energy burden in wireless sensor networks， and extend the network life cycle.

Key words： wireless sensor networks； PSO； energy balance； cluster head selection

1 概述

无线传感器网络是一种自组织网络，网络的形成与运行在很大程度上是由多个传感器节点自主完成的，并不需要人工配置[1]。因此，在网络建立的初始阶段，需要采取一定的拓扑控制机制，自适应地将一定数目的节点组成一个互联网络。

目前，无线传感器网络中拓扑控制可以分为两类：功率控制和层次拓扑结构控制[2]。功率控制机制调整网络中每个节点的发射功率，在均衡节点直接邻居数目（单跳可到达的邻居数目）的同时，可降低节点通信干扰，提高网络吞吐量。层次拓扑控制是利用分簇的思想，按照一定的规则使网络中的部分节点处于激活状态，并且成为簇头节点，这些簇头节点构成一个联通的网络，对网络内的数据进行融合与传输；其他节点则处于休眠状态以降低其能量消耗，并且定期地重新选择簇头节点以均衡网络中节点的能量消耗。与传统的无线自组织网络相比，WSN部署的环境更为复杂，多采用电池供电，能量更为有限，节点数目众多，节点部署更密集，网络拓扑变化更为频繁（由于节点的失效或者是新节点的加入）。因此，对于如何节省网络能耗来说，采用层次型拓扑结构显然是一种较为高效的方法。基于簇的WSN作为一种层次型网络拓扑结构，被认为是一种可以组织大量传感器节点的有效的结构，在很多方面都表现出了其良好的性能，有利于分布式算法的实现，特别适合于部署较大规模的无线传感器网络[3]。由此可见，如何对无线传感器网络进行合理的分簇已成为当前亟待解决的一个重要问题。

2 基于LEACH协议的簇头选择机制

分簇作为层次型拓扑结构的关键技术之一，其核心技术在于簇头的选择。目前，国内外许多学者纷纷对其进行了相关的研究工作。LEACH（Low-Energy Adaptive Clustering Hierarchy）协议[4]是一种低功耗自适应分簇协议，它以循环的方式选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，能够有效地降低网络的能源消耗并提高网络的整体生存时间。

2.1 经典LEACH协议分析

LEACH协议是由MIT的Chandrakasan等人为无线传感器网络设计的一种周期性执行的低功耗自适应分簇拓扑算法，它的基本思想是以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能量消耗、提高网络整体生存时间的目的。在LEACH算法中，相邻的节点动态形成簇，并由簇中的某个节点担任簇头。所有非簇头节点把数据发送到簇头，簇头对接收到的数据进行处理（数据融合）后把结果发送到汇聚节点（例如基站）。

LEACH在运行过程中不断地循环执行簇的重构过程，每一次的执行过程可以用“轮（round）”的概念来描述。每轮可以分为两个阶段：簇的建立阶段（set-up）和传输数据的稳态阶段（stead-state）。在建立阶段，节点被分为若干个簇，并且产生相应的簇头；在稳态阶段，簇内的成员节点将收集到的数据发送给簇头，这些数据在簇头节点上通过处理后，发送到汇聚节点，如图1所示。为了使时间冗余化最小，通常稳态阶段的持续时间要大于建立阶段的持续时间。

图1 LEACH的运行方式

LEACH算法希望在每轮执行过程中形成[k]个簇，如何合理有效地选择簇头节点则成为LEACH算法的关键。一个节点能否成为簇头是由网络中所需要的簇头节点的总数和每个节点已累计成为簇头的次数来决定的。对于每一个传感器节点，为其随机选择一个[0～1]之间的随机值，如果这个选定的值小于某一个阈值[T（n）]，那么这个节点就成为簇头节点。

在节点确定自己成为簇头后，采用非持续CSMA的MAC协议广播一个ADV消息。网络中的其他节点在接收到周围簇头节点的ADV消息后，根据接收信号强度决定从属的簇，并通知相应的簇头节点，完成簇的建立。最后，簇头节点采用TDMA方法为簇中的每个节点分配向其传送数据的时间片。

稳态阶段被分成时间长度相等的时隙，簇内成员节点只能在特定的时隙内向簇头节点发送数据。簇头节点在收到簇内成员节点所采集的数据后，对其进行数据融合，去除冗余数据信息，提取关键信息，然后将结果发送给汇聚节点[5]。稳态阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一轮的簇的重构过程，不断循环。

2.2 LEACH算法的优化

从上一节的分析中可以看出，在簇的建立阶段，LEACH算法在选择簇头节点的时候具有很大的随机性，很容易出现部分节点剩余能量较低但仍被选为簇头节点的情况，这样会导致部分节点因能量被提前耗尽而过早“死亡”，不利于延长整个网络的生命周期。而且，LEACH协议是通过采用数据压缩的方法来减少传输到基站节点的数据量，数据压缩的过程使得节点必须额外消耗较多的能量。另外，LEACH协议是通过随机方式选择簇头节点的，在选择过程中没有考虑到节点自身的剩余能量，一旦剩余能量较少的节点成为簇头，可能会导致这些节点因能量耗尽而过早死亡，降低整个网络的寿命。同时，LEACH协议在选举簇头时不能保证簇头节点均匀分布在监测区域内，可能会造成部分区域簇头分布较密集，部分区域簇头稀疏甚至没有产生任何簇头，从而造成网络的不完全连通。针对LEACH协议的不足之处，该文提出了一种基于能量均衡的簇头选择机制，将微粒群算法（PSO）引入到无线传感器网络簇头选举的优化过程中，综合考虑每个节点的剩余能量和当前网络的平均能量，并且融入了簇头最优个数的解决方案，用以优化网络的拓扑结构。通过对LEACH算法进行改进，较好地平衡了网络之中的能量消耗，有效地避免部分节点的过早死亡，有效地延长了整个网络的生命周期。

3 基于能量均衡的簇头选择机制

针对经典LEACH协议在选举簇头节点时的不足，该文提出了一种新的簇头选择机制，在经典LEACH协议的基础上，运用PSO算法在并行寻优方面的优势，避免使能量低的节点成为簇头，尽量让剩余能量高于当前网络平均能量的节点优先成为簇头节点。

3.1 基于PSO的簇头选择机制

无线传感器网络的生命周期是衡量网络拓扑结构的一个重要指标[6]。通常网络的生命周期取决于网络中第一个节点失效（或者电源耗尽）的时间，因此应产生一个合理的簇头选择机制，将簇头的能量负载平均分布到网络中的所有节点上，避免造成部分节点因成为簇头而过早耗尽能量的情况，从而达到延长网络生命周期的目的。

本文在簇头选择时所采用的思想可描述为：首先，将簇内每个节点的当前剩余能量与网络平均能量进行比较，如若节点的当前剩余能量大于网络平均能量，则将该节点放入候选节点集中，使之成为簇头候选节点。然后，在候选节点集中，运用PSO算法来选取最优簇头，使当前剩余能量最多的节点成为最优簇头。

本文依旧采用LEACH算法中的能量消耗模型[7]。假设无线传感器网络中有[N]个传感器节点，每个节点的初始能量为[Einitial]；节点[i]的当前剩余能量为[Eicurrent]。通过引入判别函数[F（i）]来判断节点[i]能否成为簇头候选节点：如果[F（i）≥0]，则节点[i]能够成为簇头候选节点；反之，则不能。

分析此式可以看出，在网络正常运行期间，节点总是需要消耗能量的。因此，在任何时刻节点的剩余能量总是小于其初始能量的，该判别函数在实际应用时严重缺乏可操作性。针对这一现象，该文对判别函数[F（i）]进行了改进，综合考虑节点剩余能量和网络当前平均能量这两个因素。

其中：[Eavg]表示网络当前平均能量。当[F（i）≥0]时，节点[i]的剩余能量高于网络平均能量，节点[i]成为簇头候选节点；反之，节点[i]的剩余能量低于网络平均能量，为节省能耗，节点[i]只能作为簇内成员节点。这样一来，既保证在每一轮中可以优先选择剩余能量较多的节点成为簇头节点，又降低了剩余能量较少的节点成为簇头节点的可能性。

当簇头候选集产生之后，该文采用PSO算法来选择最优簇头节点。PSO算法是一种群体智能算法，来源于对一个简化社会模型的模拟，在解决最优化问题时具有显著的优势。种群中每一个微粒代表问题的一个可行解，每个微粒根据其自身所经历的最好位置和全局的最优位置，来动态调整其飞行速度和方向，直至找到最优解或者达到最大迭代次数为止[8]。

在选择最优簇头节点的过程中，将簇头候选集中的节点作为种群中的初始微粒，通过适应值函数和迭代搜索，找到种群的全局最优解，该最优解所对应的微粒就是该轮中的最优簇头节点。

此外，在网络的分簇过程中，簇头的数量也是影响网络生命周期的一个重要因素。考虑到与距离较远的簇头节点通信时成本较高，所以没有簇头的操作会降低能量效率。无论增加的簇头会为数据融合带来多少额外的工作，增加几个簇头都会迅速地提高网络整体的能量效率。但是当再进一步增加簇头时，分簇的优点会慢慢消失。在最极端的情况下，每个节点本身就是簇头，没有任何融合的优势。该文采用文献[5]中的方法来确定最优簇头的个数。

[K=SN×εamp2π（N×Estat+εamp×d2adv）] （5）

其中：[S]是无线传感器网络监测区域的面积，[N]是传感器节点的数量，[εamp]是信号放大器的放大倍数，[Estat]是节点每传输1[bit]数据所消耗的能量，[dadv]是簇头节点的最远覆盖距离。

3.2 簇头选择机制的实现过程

基于PSO算法的簇头选择机制的具体实现步骤如下：

1） 在簇的建立阶段，根据最优簇头个数公式（5） ，得到分簇的数目[K]。

2） 计算每个节点的当前剩余能量和网络的平均能量。

3） 分别将每个节点的当前剩余能量与网络平均能量进行比较，如果节点剩余能量高于网络平均能量，则该节点有资格成为簇头候选节点；否则，该节点只能等待簇头广播信息。

4） 在簇头候选集中，通过PSO算法优化簇头选择，使剩余能量最多的节点成为最优簇头，其余节点变为成员节点等待簇头发送广播信息。此时，簇头选择阶段结束。

5） 簇头节点以一定的功率发送簇头广播信息，并等待成员节点的加入。

6） 成员节点根据接收到的ADV消息的信号强弱来选择一个信号强的簇头节点，向其发送一个请求加入的消息，并等待簇头节点分配TDMA时隙，避免成员节点与簇头节点通信时产生冲突。

7） 簇建立好后，无线传感器网络进入稳态运行阶段。成员节点按照给定的规则在自己的TDMA时隙内向簇头节点发送收集到的信息，簇头节点对这些信息进行数据融合，通过簇间通信传送至汇聚节点（或者基站）。当簇头节点的剩余能量低于阈值时，本轮结束，开始下一轮的分簇过程。

具体算法流程如图2所示。

4 结束语

本文首先介绍了拓扑控制的相关知识，指出合理的分簇对于提高WSN生命周期的重要性。然后对经典LEACH分簇协议进行了具体的分析，并针对LEACH协议在选举簇头节点时存在的不足，对LEACH算法进行优化，提出了基于PSO的簇头选择机制。在优化的过程中，以网络总体能量消耗最小为原则，综合考虑节点剩余能量和网络当前平均能量，更好地平衡了无线传感器网络中的能量负载，优化了网络拓扑结构。

参考文献：

[1] 王舒，阎毓杰.无线传感器网络的理论及应用[M].北京：北京航空航天大学出版社，2007：12-13.

[2] Bao L，Garcia-Luna-Aceves J J.Topology Management in Ad Hoc Network[C].In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing，2003：129-140.

[3] 汪学清，杨永田.一种基于虚拟菱形网格的传感器节点布置算法[J].计算机应用，2006，26（7）：1554-1556.

[4] Heinzelman W.Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[5] 周利民，杨科华，周攀.基于鱼群算法的无线传感网络覆盖优化策略[J].计算机应用研究，2010，27（6）：2276-2280.

[6] Efthymiou C，Nikoletseas S，Rolim J.Energy balanced data propagation in wireless sensor networks[C].Proceedings of 18th International Parallel and Distributed Processing Symposium，CA：IEEE Computer Society，2004：225-232.

[7] Li Fangmin，Xv Wenjun，Liu Xinhua，et al.A real-time energy-aware cluster-based routing protocol for wirelsee sensor and actor networks[J].Journal of Computer Research and Development，2008，45（1）：26-33.

[8] 曾建潮，介婧，崔志华.微粒群算法[M].北京：科学出版社，2004：5-8.