能耗最优的LEACH协议改进

周 萌，陈跃东，陈孟元

安徽工程大学 安徽省电气传动与控制重点实验室，安徽 芜湖 241000

能耗最优的LEACH协议改进

周 萌，陈跃东，陈孟元

安徽工程大学 安徽省电气传动与控制重点实验室，安徽 芜湖 241000

1 引言

无线传感器网络（Wireless Sensor Network，WSN）是一种新兴的信息感知和数据采集网络系统，能够实现人与物理世界的通信和信息交互，在众多领域具有广阔的应用前景[1]。由于网络节点采用电池供电，且往往部署于恶劣的、人类难以到达的环境中，节点电能耗尽后难以及时补充或更换，因此能耗问题是制约无线传感器网络应用和发展的首要问题。

路由协议是组网的基础和数据传输的关键，改进适用于无线传感器网络的路由协议可以有效降低节点的能耗，延长网络生命周期。LEACH协议（低功耗自适应集簇分层型协议，Low Energy Adaptive Clustering Hierarchy）是具有代表性的层次路由，采用区域集中控制的方法，从各区域节点中选出簇头，通过簇头向基站转发簇内信息，与直接传输、最小传输能量等路由相比较，可以有效降低节点能耗[2-3]。

LEACH协议执行过程中，由于部分节点耗能过快、过早死亡会造成网络不完全联通，导致网络性能急剧下降，因此网络能耗不均是LEACH协议急需解决的首要问题。

2 LEACH协议

2.1 协议原理及分析

LEACH协议按“轮”周期执行，每轮包括簇头选取、簇的形成和数据传输三个阶段。在簇头选取阶段，各节点分配一个介于0～1的随机数，若随机数大于本轮的阈值，节点当选为簇头。簇头选取完成后，簇头向周围节点广播通告自身的簇头状态、ID和本簇的分组头。周围节点根据接收信号的强度确定加入最近距离的簇，并将自身和簇头的ID通知相应的簇头节点。在数据传输阶段，簇头以TDMA方式安排簇内节点的时间调度，节点按分配的时隙将数据传送给簇头，簇头将数据包去冗处理后，按照不同的CDMA代码直接发送给基站。

LEACH协议中，簇内节点仅在分配的时隙内开启无线发送装置进行数据传输，其余时间进入休眠状态，大量节省了节点能量；同时，簇头在发送数据前经过去冗处理，减小了发送开销。但LEACH协议的簇头选取没有考虑参选节点自身的因素，仅依靠随机数产生，造成簇头分布不均、簇的规模差异大、簇头能耗不均；数据传输过程中，节点能耗与距离呈指数增长，距离基站远处的簇头需要消耗大量能量将数据直接发送至基站，造成能耗过快、过早死亡。

2.2 协议相关研究

针对LEACH协议的不足，近年来许多学者进行了研究和改进。针对簇头选取、分布不合理，文献[4]结合节点剩余能量和距离因素改进了阈值公式；文献[5]将节点能耗比和度作为簇头选择依据；文献[6]在阈值中考虑了节点密度和剩余能量；文献[7]中的簇头选取概率由局部区域节点的分布数量控制；文献[8]综合考虑了节点能量和位置信息，这些改进方法从一个方面或者多个方面优化了簇头节点的当选条件，但是对影响因子归纳和定量的全面性存在一定不足。在簇的形成阶段，文献[9]提出了簇头竞争半径自适应调节成簇的方法；文献[10]通过减小近基站节点的成簇半径实现非均匀分簇，文献[11]采用神经网络进行分簇；文献[12]采用遗传模拟退火算法进行固定分簇，这些改进与簇头选取方案相适应，共同达到均衡簇头能耗的目的。在数据传输策略上，文献[13]通过最优跳数路径降低网络能耗；文献[14]将簇内节点的高度值形成树，使簇内数据沿树传输；文献[15]利用位置信息选择能耗最小的最优转发簇头，这些成果表明，LEACH协议的数据传输方式应该由单跳改进为多跳或者单多跳结合，转发节点的选择也要以能耗最小为目标。还有一些研究者讨论了多跳路由中距离和能量的关系，文献[16]提出能距比的概念并计算出节点的最佳发送距离，文献[17]推导了单多跳节能的临界距离。

AD-LEACH协议是在以上研究的基础上，综合考虑影响簇头分布的因素，细分了节点的类型，进行阈值的改进。在簇的形成阶段，节点根据自身坐标计算所属簇的矩阵二维值，通过匹配方式将网络分成若干个均匀的网格。数据传输采用单多跳结合的方式，转发节点的选取结合了最佳转发距离和剩余能量，可调转发收敛的速度，较好地解决了簇头分布和网络能耗不均的问题。

3 AD-LEACH协议

3.1 簇头选取过程

影响簇头在网络分布和能耗的因素主要有节点能量、和基站的距离、节点密度等。簇头节点必须具有足够高的能量，用以处理和转发本簇数据，同时簇头的分布需要考虑节点密度和多跳路由引入的“热区”问题。AD-LEACH协议区分出三类特殊节点，包括：I型高能节点；II型“热区”节点；III型密集区域节点，通过提高特殊节点的当选概率，均衡簇头的负担。

网络中非特殊的节点为普通节点，阈值公式与LEACH协议相同，表示为：

对于特殊节点，做出以下定义：

定义1若节点能耗率与网络平均能耗率的商差值∂小于0，满足公式：

定义4若节点满足公式（1）、（2）、（3）中两项或以上，则该节点为交集节点，其阈值公式T4(n)通过加权方式确定。ε、η、θ分别为I、II、III型节点的加权值：

与LEACH簇头选取的目前改进方案相比，AD-LEACH从造成能耗失衡的根源出发，按照节点自身特点进行了分类，并有针对性地改进了簇头当选概率，使簇头选取更合理性、网络能耗更均匀。

3.2 分簇过程

在簇头选取过程中，AD-LEACH已经权衡了节点能量、位置等因素的影响，采用不均匀分簇的方法会造成因素之间影响失衡，并不适用于AD-LEACH。

AD-LEACH协议通过节点位置模糊匹配的方式将网络分成若干个相同大小的网格。矩形网络区域长为L，宽为W，将长边划分为a等分，宽边划分为b等分，网络被等分为a×b个矩形网格。为了保证网格内节点可靠通信，a、b的选值满足约束条件 4(W2a2+L2b2)＜a2b2d2，d为节点的通信半径。如图1所示，按照矩阵排列给所有网格分配一个二维值 (i，j)，i=1，2，…，L/a; j=1，2，…，W/b。

所有节点计算自身所属网格的二维值，满足位置匹配条件的节点划分在同一网格。

3.3 数据传输过程

AD-LEACH协议采用基于最佳转发距离的数据传输方式，包括以下过程：

图1 网格二维值分布示意图

（1）定义距离阈值d_limit，若簇头节点n与基站的距离小于d_limit，节点采用单跳方式，直接与基站通信，完成数据传输。

（2）若簇头节点n与基站的距离大于d_limit，先完成簇内数据处理。网格内的簇头接收本簇节点的数据包，若一个网格包含多个簇头，普通节点的数据包发送至距离最近的簇头。

（3）簇内数据处理完成后，各个网格中的簇头成为待转发节点，进行簇外数据传输，采用多跳方式，选择合适的转发节点，将数据传送至基站。

多跳方式的数据传输流程图如图2所示。

图2 Ad-LEACH协议的数据传输流程图

以簇头节点n为圆心，dc+db和dc-dl为外径和内径作圆环，在圆环区域内选择最佳转发节点，其中，dc为最佳转发距离，当节点选择距离为dc的节点转发数据时，节点的能量利用率最高，dc+db、dc-dl分别为外径和内径的增补量，控制节点搜索面积。

若圆环区域内有N个簇头，剩余能量分别为E1、 E2、…、EN，和基站的距离分别为 d1、d2、…、dN，为了使数据尽快转发到基站，通过距离条件加快收敛，距离条件为 di＜β1d0，其中，d0为待转发节点与基站的距离，β1为距离衰减因子，调节转发收敛的速度。

对于符合距离条件的M个簇头，将它们与基站的距离值从大到小排序，分别计分1、2、…、M ；剩余能量值从小到大排序，分别计分1、2、…、M，定义距离的权重为w1，能量的权重为w2。若节点n的距离计分为Sn，能量计分为 En，则其总得分为Un=Sn×w1+En×w2(i= 1，2，…，M)，总得分最高的候选簇头当选为转发节点。

若圆环中不含簇头或不含满足距离条件的簇头时，选择圆环中的普通节点作为转发节点。为了减少计算开销，加快摆脱圆环无合适簇头的状况，，使当选节点尽量靠近基站，距离条件di＜β2d0中距离衰减因子取得较小些，β2＜β1。在满足距离条件的普通节点中选取能量最高的作为最佳转发节点。

4 仿真结果及分析

4.1 环境模型本文采用NS2平台进行仿真，仿真环境为：节点总数为100，随机分布于100 m×100 m的区域，基站位置为（0，0）（单位：m），节点初始能量均为2 J，最佳簇头百分比为5%，仿真时间为600 s。能量模型与LEACH相同，Eelec=50 nJ/bit，εfs=10 pJ/bit·m2，εmp=0.001 3 pJ/bit·m4，d0=87 m。

4.2 对比协议选择

在对改进前后的LEACH协议仿真的同时，添加了EEUC协议（Energy-Efficient Uneven Clustering，能量高效的非均匀分簇协议）作对比。EEUC在保留LEACH分簇思想的基础上，簇头选取过程中充分考虑到节点自身的能量，同时采用多跳方式解决离基站远的簇头过早死亡的问题，是对LEACH协议很大的改进[18-19]。在仿真平台下对三种协议进行仿真实验并对比分析。

4.3 结果与分析

图3是分别采用三种协议的网络中存活节点数n与时间t关系的仿真结果，图4是网络总能耗e与时间关系t的仿真结果，图5是数据包发送总字节数 p与时间关系t的仿真结果。

由图3可知，LEACH网络中出现第一个死亡节点的时间为400 s左右，EEUC和AD-LEACH网络分别为420 s和430 s左右；LEACH、EEUC和AD-LEACH网络中最后一个节点死亡时间分别为530 s、560 s和590 s左右。从FND的角度，AD-LEACH的性能比LEACH提升了7.5%，比EEUC提升了2.38%；从LND的角度，ADLEACH比LEACH和EEUC分别延长了11.32%和5.36%。

图3 网络存活节点数目与时间关系

图4 网络总能耗与时间关系

图5 数据包发送总数与时间关系

图4中，AD-LEACH的能耗曲线比LEACH和EEUC更为平滑，反映能耗速率比较稳定。对比图3和图4，第400～530 s时间段，AD-LEACH网络的总能耗与另外两种网络的差异并不大，但是AD-LEACH网络中存活节点数目明显高于LEACH网络和EEUC网络，反映了AD-LEACH的节点能耗更加均匀，有效解决了LEACH中部分节点过早死亡，导致网络性能下降的问题。

图5反映AD-LEACH网络的吞吐量也有了较大提高，比LEACH网络提高了约62.5%，比EEUC网络提高了约22.17%。

通过与LEACH、EEUC网络性能的对比，体现了AD-LEACH协议在降低和均衡节点能耗、延长网络寿命方面取得了较好的改进效果。

5 结束语

AD-LEACH协议目的在于降低和均衡网络能耗，实现能耗最优，为此针对LEACH工作机制的不足做出了改进，包括：（1）分析了节点的特点并进行分类，从造成簇头选取不合理的客观原因出发，有针对性地进行阈值的修正。（2）通过节点位置信息，采用匹配方式将网络分为相同大小的网格。（3）在最佳转发距离附近的圆环区域寻找转发的中间节点，兼顾了转发节点的剩余能量和转发效率。

仿真结果表明，改进后的协议有效延长了网络生命周期，均衡了节点能耗，改进效果较为明显，但是对基站所处位置对网络性能的影响以及数据传输的开销分析尚未探究，将作为下一步工作的重点。

[1]郑军，张宝贤.无线传感器网络技术[M].北京：机械工业出版社，2012.

[2]Heinzelman W R，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.[S.1.]：IEEE Computer Society，2000：3005-3014.

[3]Handy M，Haase M，Timmerrnann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proceedingsofthe 4th IEEE Conference on Mobile and Wireless Communications Networks.Washington，DC：IEEE Computer Society，2002：368-372.

[4]刘玉华，赵永峰，许凯华，等.无线传感器网络LEACH协议的改进[J].计算机工程与应用，2010，46（17）：117-120.

[5]樊志平，金政哲，谢冬青.基于能量效率的无线传感器网络分簇算法[J].小型微型计算机系统，2013，34（3）：535-539.

[6]唐甲东，蔡明.基于LEACH协议的能耗均衡路由算法[J].计算机工程，2013，39（7）：134-136.

[7]钱开国，戴祖诚，申时凯.非均匀分布的无线传感器网络分簇路由算法[J].计算机应用，2013，33（12）：3415-3418.

[8]马建乐，杨军.基于位置和剩余能量的局部集中式LEACH算法研究[J].传感技术学报，2013，8（8）：1147-1151.

[9]石为人，柏荡，高鹏，等.无线传感器网络簇头半径自适应调节路由算法[J].仪器仪表学报，2012，33（8）：1779-1785.

[10]蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇协议[J].软件学报，2012，23（5）：1222-1232.

[11]肖婧，郑更生，方勇，等.基于自组织神经网络的分簇成链协议[J].计算机工程，2013，39（7）：148-151.

[12]张世伟，张海涛，张士杰.基于固定分簇和能量均衡的无线传感器网络多跳路由算法[J].传感器与微系统，2013，32（8）：117-124.

[13]柏荡，石为人，高鹏，等.无线传感器网络跳数优化非均衡路由算法[J].计算机工程与应用，2012，48（32）：60-64.

[14]汤玉，汪学明.一种分层路由协议的改进与仿真分析[J].通信技术，2013，46（4）：42-46.

[15]张瑞华，贾智平，程合友.基于非均匀分簇和最小能耗的无线传感网络路由算法[J].上海交通大学学报，2012，46（11）：1774-1778.

[16]郭书诚，卢昱，许定根.基于无线分簇无线传感器网络的路由算法研究[J].通信学报，2010，31（8）：63-69.

[17]王林，赵绍英.无线传感器网络LEACH路由协议的研究与改进[J].计算机工程与应用，2012，48（2）：80-82.

[18]Younis O，Fahmy S.HEED：a hybrid energy-efficient distributed clustering approach for Ad hoc sensornetworks[J].IEEE Transactions on Mobile Computing，2004，3（4）：600-669.

[19]唐加山，王燕.无线传感器网络中改进的EEUC协议[J].重庆邮电大学学报，2013，25（2）：172-177.

ZHOU Meng,CHEN Yuedong,CHEN Mengyuan

Anhui Key Laboratory of Electric Drive and Control,Anhui Polytechnic University,Wuhu,Anhui 241000,China

To overcome the shortage of electing of cluster head and data transmission method in LEACH protocol, AD-LEACH protocol is proposed after improving.Based on different categories of nodes,the probability of being cluster head is modified to balance the influence of energy consumption,distance and node density.WSN is divided into several grids sharing the same size through fuzzy matching node positions.During the course of data transmission,the relaying node is selected with optimum distance and the minimum energy and consumption.The simulation results show that AD-LEACH protocol balances the energy consumption of WSN effectively and achieves the purpose of the optimal energy consumption.

wireless sensor networks;Low Energy Adaptive Clustering Hierarchy（LEACH）protocol;electing of cluster head;fuzzy matching;grids;relaying node;optimal energy consumption

针对LEACH协议在簇头选取、数据通信方面的不足，提出改进后的AD-LEACH协议。根据节点的分类，修正簇头当选概率，使簇头选取均衡了能耗、距离、节点密度的影响。通过节点位置模糊匹配的方法将全网划分为若干个均匀大小的网格。数据传输阶段以能量利用率最高为目的，基于最佳转发距离选择转发节点。仿真结果表明，AD-LEACH协议有效降低和均衡了网络能耗，达到了能耗最优的目的。

无线传感器网络；低功耗自适应集簇分层型（LEACH）协议；簇头选取；模糊匹配；网格；转发节点；能耗最优

A

TP393

10.3778/j.issn.1002-8331.1403-0134

ZHOU Meng,CHEN Yuedong,CHEN Mengyuan.Improvement of LEACH route protocol based on optimal energy consumption.Computer Engineering and Applications,2014,50（23）：82-86.

安徽省自然科学基金（No.11040606M153）；安徽高校省级自然科学研究项目（No.KJ2013A041）。

周萌（1990—），男，硕士在读，研究领域为无线传感器网络；陈跃东（1956—），通讯作者，男，教授，硕导，研究领域为运动控制系统与检测技术；陈孟元（1984—），男，讲师，研究领域为无线传感器网络。E-mail：76920395@qq.com

2014-03-12

2014-04-29

1002-8331（2014）23-0082-05

CNKI网络优先出版：2014-07-11,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0134.html