一种基于LEACH-C改进的能量有效分簇协议

王春梅

(滨州学院 信息工程系,山东 滨州 256603)

摘　要：针对LEACH-C协议周期性地簇重构会造成额外开销以及簇头节点和普通节点间能耗不均的缺陷，提出了改进的能量有效分簇协议(Improved Energy-Efficient Clustering Hierarchy,IEECH)。在IEECH中，由簇中所选出的发送节点分担簇头节点的高能量负载，因此不再需要进行全局的簇重构。网络节点的能耗由于发送节点的轮转进一步得到了均衡。因此，该算法和LEACH以及LEACH-C相比，可以有效地延长网络的寿命。最后，通过NS2仿真实验也得到了验证。

关键词：无线传感器网络；分簇协议；能量有效；网络寿命

doi:10.3969/j.issn.1002-0802.2015.06.016

一种基于LEACH-C改进的能量有效分簇协议

王春梅

(滨州学院 信息工程系,山东 滨州 256603)

摘要：针对LEACH-C协议周期性地簇重构会造成额外开销以及簇头节点和普通节点间能耗不均的缺陷，提出了改进的能量有效分簇协议(Improved Energy-Efficient Clustering Hierarchy,IEECH)。在IEECH中，由簇中所选出的发送节点分担簇头节点的高能量负载，因此不再需要进行全局的簇重构。网络节点的能耗由于发送节点的轮转进一步得到了均衡。因此，该算法和LEACH以及LEACH-C相比，可以有效地延长网络的寿命。最后，通过NS2仿真实验也得到了验证。

关键词：无线传感器网络；分簇协议；能量有效；网络寿命

doi:10.3969/j.issn.1002-0802.2015.06.016

收稿日期：2015-01-01；修回日期：2015-04-01Received date:2015-01-01；Revised date：2015-04-01

基金项目：山东省自然科学基金(No.2014ZRB019)Foundation Item:Research on the Fractional Chaos Characteristics and Synchronization(No.2014ZRB019)

中图分类号：TP393

文献标志码：码：A

文章编号：号：1002-0802(2015)06-0710-04

Abstract：Aiming at LEACH-C for its extra overhead in cluster reconstruction and imbalanced energy consumption between cluster heads and common nodes, IEECH (Improved Energy-Efficient Clustering Hierarchy Protocol) is proposed. In this protocol the sending nodes selected from clusters share the high load of cluster heads, thus it is unnecessary for these nodes to implement the re-clustering of global network. The energy consumption of each cluster member can be balanced via rotation of sending nodes. Therefore, IEECH can prolong the network life-time significantly as compared with LEACH and LEACH-C. Finally, NS2 simulation indicates this result.

作者简介：

An Energy-Efficient Clustering Protocol based on LEACH-C

WANG Chun-mei

(Information Engineering Department, Binzhou University, Binzhou Shandong 256603, China)

Key words：wireless sensor networks; clustering protocol; energy effectiveness; WSN lifetime

0引言

路由协议是无线传感器网络(WSN)的关键技术之一[1-2]。目前，无线传感器网络中主导的路由协议是低功耗自适应分簇协议(Low Energy Adaptive Clustering Hierarchy,LEACH)为代表的层次化路由[3-4]。LEACH-C协议由Heinzelman等人在LEACH协议的基础上加以改进提出的基于基站控制的协议[1]。但是该算法需要构造一个组织数据发送的环结构，提高了算法的复杂度。针对LEACH-C协议的缺陷，本文提出了改进的能量有效分簇协议 (the Improved Energy-Efficient Clustering Hierarchy,IEECH)，主要目标是网络系统的能量消耗被大大降低，网络的生命周期有效地延长，并对该方案进行了理论分析和实验仿真，仿真结果也验证了该协议的有效性。

1IEECH协议

1.1网络模型

对网络模型进行较通用的假设：

(1)基站位于正方形监测区域外部;

(2)每个传感器节点都有全网内唯一的id标志;

(3)每个传感器节点的发射功率可控，其可以将数据发送给任意其他节点或者可以直接发送到基站;

(4)节点一旦部署不再移动;

(5)传感器节点可感知其位置，即为每个节点配备GPS等定位系统。

1.2能量模型

采用的能量模型同LEACH[5-6]。若传输l-bit的信息经过距离d，此时发送端的能量消耗为：

(1)

式中，Eelec表示的是发射电路所要消耗的能量。如果数据的传输距离小于阈值d0，那么功率放大消耗就采用自由空间模型；但当数据的传输距离大于等于阈值d0时，就应采用多路径衰减模型。εfs、εmp分别是这两种模型中放大功率所需的能量。同时，假设传感器节点进行监测的能耗为：Esen，簇头融合数据的能耗为：Ecom,Eelec表示的是发射电路所要消耗的能量。

1.3IEECH协议细节

IEECH协议是一个优化的集中式分簇算法，分簇过程被划分为两个部分：成簇阶段和发送节点的循环阶段。

(1)成簇阶段

该成簇过程包括两个部分：划分簇阶段和发送节点的选择阶段。

1)划分簇阶段

每个传感器节点在本阶段会将位置和能量信息发送到基站。基站收到所有节点的数据信息后，分簇过程如下：

①由基站计算网络中所有节点的平均剩余能量Eave和最佳的簇头数目Kopt。

②若节点的剩余能量≥平均剩余能量Eave，则该节点被选择为簇头节点，否则节点则为非簇头节点。

③基站对选出的簇头集合能量和执行模拟退火算法[7]，对网络进行分簇。

④簇头找出后，基站将选出的簇头和簇成员节点的信息向网络中所有节点广播，根据此广播信息，每个节点确定自己的角色，每个簇由被选出来的簇头来管理。

此阶段结束后，网络中会存在两类节点：簇头和簇成员节点。在下一阶段，将会通过一定的规则选出每个簇中的发送节点。

2)发送节点的选择阶段

在本阶段，每个簇头都负责从本簇内选出一个节点来充当本轮的发送节点。选择过程如下。

算法2:发送节点的选择及成员节点调度算法：

①每个簇头统计成员节点的信息，按照式(1)计算出本簇中所有成员节点的平均剩余能量。

②簇头负责从这些节点中选出所有剩余能量高于此平均剩余能量的节点，作为候选发送节点。

③簇头将第②步选出的候选发送节点按照节点和自己的距离对其按照非递减方式排序，并从这些节点中选出距离簇头最近的节点充当发送节点。其余候选节点重新变为普通成员节点。

④簇头为簇内成员节点计算出TDMA调度表，调度原则是：剩余能量越低的节点发送数据的时隙安排地越靠前，因而可以避免能量较低的节点在等待时隙到来的过程中又耗费掉一部分能量。

簇头将当选的发送节点的id标识和生成的成员节点调度表在簇范围内进行广播，成员节点在收到此消息后确定本簇内发送节点的位置，并只在自己所属的发送时隙内将收集的数据传送至发送节点，发送节点将收到的数据进行融合处理，然后传送至基站。

为了选出发送节点，每个簇头需要计算每个节点会被当选的能量阈值，即所有成员节点的平均剩余能量。计算公式如下：

(2)

式中，n是簇i内的成员节点数目。Ej-cur是指节点j当前剩余能量。高于此平均能量且距离簇头最近的节点更容易被选为发送节点。

如果节点j的当前剩余能量Ej-cur是不小于簇内节点平均能量Ei-ave的，则节点j被选入候选发送节点集合SSi：

Ej-cur≥Ei-ave,j∈SSi

(3)

集合SSi确定后，簇头节点就根据自己和节点的距离，从该集合中选出本簇内这一轮的发送节点，即平均剩余能量较多，且距离簇头的距离越小的节点被选为发送节点的概率越大。

本阶段结束时，网络中存在3种节点：簇头节点，发送节点和普通成员节点。

簇头节点：负责本簇内发送节点的选择以及调度簇内普通成员节点的发送时隙。

发送节点：负责收集成员节点发送的数据，并将其经过融合处理后发送到基站。

普通成员节点：负责感知收集数据，并将数据按照调度时隙发送给发送节点。

(2)循环阶段

在本阶段，簇头根据掌握的成员节点信息创建TDMA调度表，为每个成员节点分配一个发送时隙，节点只在这个时隙内发送数据，其余时间就可以进入休眠状态，由此来节省能量。簇头将此调度表和本轮选出的发送节点的id标识和地理位置信息一起广播发送给成员节点。成员节点确定本簇内的发送节点，并在自己的发送时隙内将数据传送至发送节点，由发送节点发送至基站。为了均衡发送节点和成员节点间的能耗，每个成员节点轮流担任发送节点。即一轮完成以后，簇头会按照发送节点的选择规则从成员节点中选出下一轮要担任发送节点的节点，此时前一轮的发送节点又重新变成了普通成员节点。簇头将本轮重新建立的TDMA调度表和本轮选出的发送节点的相关信息广播发送给簇内成员节点，由此开始下一轮的数据传输。发送节点在簇内轮转可以有效均衡簇内节点间的能耗。

2IEECH协议分析

(1)IEECH协议不再在网络全局内频繁的簇重构，避免了簇重构带来的大量额外开销。

(2)IEECH协议在成簇阶段按照一定规则生成了最优的簇头数目和分簇拓扑，在之后的过程中，维持这个最优的拓扑，由簇头在本簇中选出本轮中用来融合和发送数据的发送节点，从而分担簇头的能耗，使簇头能量缓慢消耗。由于发送节点的负担仍然较重，因此算法只是在每个局部簇中进行发送节点的轮转来均衡簇中每个成员节点的能耗，充分利用每个节点的能量，避免浪费。

(3)在簇头生成TDMA调度时，同样考虑了节点的剩余能量，使能量较少的节点发送数据的时隙排在调度表的前面，避免节点在等待过程中能量的进一步消耗。因为尽管在这个等待过程中节点是处于休眠状态，但是仍然会有能量消耗。

3IEECH协议仿真

通过仿真实验对LEACH，LEACH-C和IEECH的算法性能进行对比分析。要比较的性能指标有：

(1)网络寿命：此指标是指随着算法的运行时间网络中存活节点的数目变化。

(2)数据量：此指标是指监测网络中能够成功传送到基站的数据量的多少。

设置了如下仿真场景对IEECH进行仿真实验：将100个节点随机地分布在100 m×100 m的矩形区域内。基站位于矩形区域外，将其坐标设置为(50,175)。仿真场景图如图1所示。

图1　仿真场景

具体仿真参数设置如表1所示。

表1　仿真参数设置

使用所设置的参数，在上面的仿真场景下分别运行LEACH，LEACH-C和IEECH。图2显示了对3种协议的网络寿命的仿真比较。如图2所示，作为LEACH的改进协议，运行LEACH-C协议的网络中第一个节点死亡的时间是远远缓慢于LEACH协议的。因为在LEACH中，簇头是随机选取的，而在LEACH-C中簇头是事先计算好的最优簇头分布，网络中的节点的能量的消耗比LEACH中要均衡地多，因此可以获得较长的网络寿命。在提出的IEECH协议中，算法除了具备LEACH-C协议的优点外，即在全网范围内计算出最优的簇头分布，针对LEACH-C协议的每个簇内簇头负担过重会过早死亡和需要在全网内进行带来额外开销的簇重构过程，IEECH协议为每个簇挑选了专门用来收集，汇聚和发送数据的发送节点，可以大量分担簇头的能耗，并且为了均衡簇内每个节点的能耗，在每个簇中轮转发送节点的角色，而不需要在全网内进行簇重构。因此，运行IEECH的网络中第一个节点死亡的时间是长于LEACH和LEACH-C的，并且IEECH网络中第一个节点死亡之后，网络很快就死亡了，即绝大多数节点的能量都得到了充分的利用。为了进一步体现IEECH协议性能的优越性，提取的三种协议中网络中数据传输量，结果对比如图3所示。在运行时间内，LEACH-C及IEECH发送的数据包比LEACH多，并且在LEACH所有节点全部死亡后，LEACH-C和IEEC仍有发包成功，也就是说，在相同的环境下，LEACH-C和IEECH采集和传输的数据包更多，并且网络中传输的数据量更加稳定。

图2　网络寿命

图3　数据传输量的对比

4结语

提出了一种能量有效的分簇协议，簇头节点的高能量负载被每个簇中选出的发送节点所分担。簇头节点和发送节点的选择分别基于网络中节点的平均剩余能量和每个簇中成员节点的平均能量以及相对距离。由于簇头的能量负载被大大降低，因此不需要进行全局的簇重构，避免了大量能量的额外开销。并且发送节点在簇内的轮转又进一步均衡了每个节点的能耗。因此，算法既可以均衡簇头和普通节点的能耗，又可避免全局簇重构带来的巨大额外开销。理论与仿真实验证明，和LEACH以及LEACH-C相比，IEECH可以延长网络的寿命。

参考文献：

[1]Heinzelman W R. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans, on Wireless Communications, 2002, 1(4): 660-670.

[2]陈昌祥，达维，周洁. 基于RSSI的无线传感器网络距离修正定位算法[J]. 通信技术, 2011, 44(02): 65-69.

CHEN Chang-xiang, DA Wei, ZHOU Jie. RSSI-based Range Collation Localization Algorithm in WSN[J]. Communications Technology, 2011, 44(02): 65-69.

[3]Soro S, Heinzelman W. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[C]. In Proceeding of the 19th IEEE International Parallel and Distributed Processing Symposium, Colorado, USA, 2013(13): 236-243.

[4]Muruganathan S D, Ma DCF, Bhasin PI,et al. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J], IEEE Communications Magazine, 2005, 43 (3): 8-13.

[5]Heinzelman W R, Chandrakasan A, Balkarishnan H. Energy-Efficient Communication Protocol for Wireless Sensor Networks[C]. Proeeedings of the 33rd Annual Hawaii International Conference on System Sciences, Hawaii, USA, 2000:1-10.

[6]Fuad Bajaber. Irfan Awan. EECPL: Energy Effcient Clustering Protocol to Enhance Lifetime of Wireless Sensor Network[J]. J Ambient Intell Human Comput, 2010(1): 239-248.

[7]Kirkpatrick S, Gelati C, Vecchi M. Simulated Annealing. Science, 1983, 220: 671-680.

王春梅(1982—)，女，硕士，讲师，主要研究方向为互联网技术。