一种基于LEACH的能量高效分簇路由协议

段圆圆，陈桂芬

（长春理工大学 电子信息工程学院，长春 130022）

随着微电子技术，无线通信与传感技术的发展，无线传感器网络引起了人们的的广泛关注［1］。无线传感器网络是由大量的微型传感器节点组成［2］，然而这些传感器节点能量和生存周期均有限，节点的数据处理能力和通信范围同样有局限性［3］。无线传感器网络一般部署于恶劣的环境之中，节点一旦失效网络的应用便受到限制［4］。因此如何减少节点的能量消耗，延长无线传感器网络的生存周期，一直是研究的热点问题［5］。无线传感器网络的路由协议作为无线传感器网络的关键技术之一，可以在传感器节点和基站之间建立高效的传输路径，提高整个网络的传输效率，有效地延长网络的生存周期。

在现有的路由协议中，LEACH（Low Energy Adaptive Clustering Hierarchy）协议作为第一个分层路由协议［6］，它的应用优化了平面路由协议在建立路由时能量开销较大的缺点。其在易于管理和良好的扩展性以及在平衡能耗方面的优势，使得分簇路由协议成为关注的焦点。PEGASIS由LEACH发展而来，在平衡节点能耗方面具有相当优势，所以国内外学者提出了依据PEGASIS（Power Efficient Gathering in Sensor Information System）来改进LEACH的方法。如文献［7］借鉴PEGASIS成链方法，只将簇首节点成链，虽然减少能耗和时延，但是簇内簇首轮换由基站负责，当簇首剩余能量不是簇内节点剩余能量的最大值时进行簇首轮换，频繁的簇首选取会带来不必要的能量开销。文献［8］中，除簇首节点成链之外，在簇内节点至簇首也采取形成节点链的方式传输数据。如果在成链过程中有节点失效，那么频繁地重新成链同样会带来巨大能耗。

本文基于LEACH协议提出了一种改进的协议—EEPBL，将PEGASIS协议的节点成链思想应用于LEACH协议的分簇结构之中，只将LEACH协议中的簇头节点成链。这样既可以解决PEGASIS时延问题，同时也改进LEACH的单跳传输方式，平衡节点之间的能耗。同时利用动态能量阈值来减少簇内簇首轮换过程中的能耗。

1 无线传感器网络路由协议相关研究

路由协议对于提高无线传感器网络的数据传输效率以及延长网络生命周期有着至关重要的作用，目前已是国内外研究的热点之一。分簇路由协议作为无线传感器网络路由协议中的一种，它的应用优化了平面路由协议在建立路由时能量开销较大的缺点。其在易于管理和良好的扩展性以及在平衡能耗方面的优势，使得分簇路由协议成为关注的焦点。

1.1 LEACH协议

LEACH协议由麻省理工学院Wendi Rabiner Heinzelman等三人提出［9］。主要运作过程是将网络中的节点分成多个簇，通过节点产生的随机数与某个阈值进行比较，随机数小于阈值的节点担任簇首节点。簇内成员节点依次把数据发送给簇首，簇首将接收到的数据和自身感知的数据融合后，发送给汇聚节点，由于簇首承担任务较重，能量消耗较大，为了平衡节点间的能量消耗，簇内节点会轮换着成为簇首。LEACH协议是周期性的路由协议，在实际运行过程按照一定周期性，每一个周期称为一轮，每一轮又由簇首形成阶段和稳定传输阶段组成。LEACH协议的拓扑结构如图1所示：

图1 LEACH协议的拓扑结构

在簇首形成阶段，节点是否能成为簇首的条件主要取决于簇首数占整个网络节点数的百分比p和上次成为簇首的轮数。这时节点n将产生一个随机数，位于0-1之间。如果这个随机数小于阈值，则该节点在这轮成为簇首，阈值公式如下：

其中，p=k/n；n表示传感器网络中任一节点，k表示传感器网络中的簇首数量，p簇头占总结点的百分比，r表示为当前轮数，G表示在最近1p轮中还没有当选簇首的集合。

LEACH协议虽然较一般平面路由协议在一定程度上延长了网络寿命，但是协议中没有考虑到节点的剩余能量因素，无论节点的剩余能量多少，被选为簇首节点的概率相同。每一轮结束之后，就会重新选择簇首节点，频繁选取簇首会带来额外的能耗。而且LEACH协议在进行数据传输时，没有考虑到节点与簇首节点和簇首与基站之间的距离因素。无论是簇内成员节点传送数据到簇首还是簇首节点传送数据到基站均是采用单跳的通信方式，这会加速进行长距离数据传输的节点死亡，缩短网络寿命。

1.2 PEGASIS协议

PEGASIS协议是基于LEACH协议的改进版本。该协议的核心思想是利用贪婪算法从基站最远端形成一条由所有节点组成的单链。然后通过随机方式选取一个节点成为链首节点负责与基站通信。除端节点之外，每个节点将接收到的数据与自身的采集的数据进行融合，从两端沿着链传送给链首节点，最后由链首节点将接收到的数据融合后传送至基站。在协议运行过程中，每当有节点失效，剩余节点就会重新形成一条链，直至所有节点失效，通信结束［10］。

相比于LEACH中无论节点间距离远近，簇成员节点与簇首节点均采用单跳方式传输数据。在PEGASIS中节点只需与距自己最近的节点通信，平衡了节点之间的能耗。但是数据从链路的远端传输到链首会引起过多的延迟，并且每次链路中单个节点的死亡都要重新成链，如此拓扑结构的调整会带来巨大的能量开销，特别是对于高度利用的网络，这种协议会加速网络的死亡。

2 改进的EEPBL协议

综合LEACH和PEGASIS的优缺点，从簇首选择、簇间路由和簇内簇首轮换三个方面改进LEACH协议。提出了一个基于LEACH的能量高效路由协议EEPBL。EEPBL协议基本思想：首先将网络中的节点进行分簇，然后采用集中控制的方式由基站选取簇首节点，借鉴PEGASIS的链式结构，依据贪婪算法将选取的簇首节点在距基站的最远端形成一条节点链，并且在所有簇首节点之中选择一个剩余能量最多且离基站最近的簇首节点担任链首节点，链首节点负责与基站通信。

2.1 EEPBL算法描述

2.1.1 簇首选择

采用集中控制的方式通过基站选取簇首，由于基站具有能量充足计算能力强等优点，将簇首的选择工作通过基站来完成，可以达到节约能耗的目的。首先网络中的所有传感器节点将自己的能量和位置信息发送给基站。在初始阶段网络中传感器节点的能量相同，所以基站随机选取簇首节点即可。随着网络的不断运行，各节点的剩余能量会有差异，所以基站根据收到的信息，选择剩余能量最多的节点作为簇首节点，当簇首节点选定之后，向周围邻居节点广播自己成为簇首的消息，等待邻居节点加入簇。

2.1.2 能量模型

本文采用一阶无线电模型的能量模型，无线信号强度所产生的能量损耗与传输的距离有关。该能量模型中规定了两种信道模型—自由空间模型和多径衰落模型。当传输距离超过阈值d0时采用多径衰落模型，否则采用自由空间模型。在此模型中节点经过长度为d的路径，发送Lbit的数据所消耗的能量可由下式计算：

其中，Eelec表示发送单位比特数据电路所需消耗的能量，εfs，εmp为功率放大器在不同信道模型的参数，其中；在此能量模型中，将Lbit的数据在长度为d的路径上传输，所消耗的能量为：

式中，ET(l,d)为发送时所消耗的能量，有两部分组成，其一是发送电路消耗的能量ET-elec(l,d)，其二是发送放大器所消耗的能量ET-amp(l,d)。

将发送电路和发送放大器这两部分能耗代入（3）中可得出

ER(l)是接受电路所消耗的能量，主要由接收电路产生

于是综合（3）（4）（5）（6）可以得出

2.1.3 簇间路由

在LEACH协议中，无论是簇首节点传输数据到基站，还是簇内成员节点传输数据至簇首，均采用单跳方式传输，当簇首节点距离基站距离较远时或成员节点距离簇首较远时都会造成不必要的能量消耗。PEGASIS协议通过将网络中的节点形成节点链［4］，以多跳方式将采集的数据传送至基站［11］，但当网络规模较大时，会导致较大时延。所以本文综合两者优点，提出一种改进的簇间路由算法，仅将簇首节点依据贪婪算法从基站的最远端成链，成链之后由基站选择具有最多的剩余能量且距离基站最近的簇首节点作为整条链的链首节点。簇内成员节点将采集的数据传送到簇首节点后，簇首节点将接收到的数据信息沿着这条链路传输至基站。EEPBL的簇间路由如图2所示。

图2 EEPBL的簇间路由

2.1.4 簇内簇首轮换

由于LEACH协议每经过一轮就要进行全网的簇首选举，然后当选的簇首节点广播当选信息重新成簇，这样对簇首节点的剩余能量并没有准确的估计。若剩余的能量还可以继续支撑数据传输，簇首节点就没有必要进行更换。因此EEPBL中设置动态能量阈值Eeff来避免频繁地更换簇首造成的能量消耗。

动态阈值Eeff的值会随着簇内节点剩余能量的变化而变化，簇首节点根据簇成员节点发送过来的能量信息计算簇内剩余节点的平均值Eaverage：

其中，符号Ei为节点i的剩余能量，N为簇内存活节点的总数，本文将能量阈值设置为簇内节点剩余能量平均值的一半：

当簇首能量小于此阈值时进行簇内的簇首轮换，选择簇内能量第二多的节点成为簇首，如此循环往复，直至簇内节点剩余能量均小于阈值。

2.2 改进算法流程图

图3 EEPBL协议流程图

3 仿真结果及分析

3.1 参数设置

使用MATLAB仿真平台对改进的能量高效路由协议EEPBL和LEACH协议在性能方面进行对比分析。仿真参数如表1所示：

表1 仿真参数

3.2 结果分析

如图4所示，反映了死亡的节点总数和存活节点随着时间的变化关系。仿真结果表明，LEACH协议约在1100轮的时候开始出现死亡节点，在1500轮的时候，LEACH协议约有一半节传感器节点失效，在2250轮的时候全网所有的节点失效。

而本文提出的EEPBL算法大约在1400轮的时候开始出现死亡节点，在2100轮的时候约有一半的节点失效，到2750轮的时候全网的节点失效。EEPBL半数节点的失效时间是LEACH的1.4倍；EEPBL全部节点的失效时间是LEACH的1.31倍。这是由于EEPBL协议在簇间路由的选择方面借鉴PEGASIS的链式结构，将簇首节点组成一条链，减少了LEACH协议中以单跳方式传输数据至基站的能耗。

图4 死亡节点随时间的变化

图5对数据的传输量将LEACH和EEPBL进行仿真对比，从仿真结果可以看出，EEPBL的数据传输总量大大超过LEACH的数据传输总量，当全网的节点失效之时，LEACH协议的数据传输总量约为1.8×104bit；而EEPBL协议在全网失效之时数据传输总量约为7×104bit。改进后的EEPBL协议，数据传输总量约为LEACH的3.9倍。因此从总体来看EEPBL协议的性能优于LEACH协议。

图5 LEACH和EEPBL的数据传输对比

4 结论

EEPBL协议综合了LEACH和PEGASIS协议的优点，通过将簇首节点成链的方式，传递全网数据信息，既改善了PEGASIS中因成链过长而降低数据传输速率，同时又解决了LEACH协议中节点能耗不均的问题。由仿真结果可知，EEPBL协议能够有效减少节点能耗，延长网络寿命，提高数据传输效率。

［1］杨阳，刘智，项力领，等.栅格型无线传感器网络的状态空间建模［J］.长春理工大学学报：自然科学版，2013，36（06）：129-132.

［2］边晶，杜威.基于ZigBee的智能公交系统无线传感器网络拓扑结构探究［J］.长春理工大学学报：自然科学版，2016，39（04）：135-137.

［3］余恒，王刚亮.无线传感器网络路由协议研究进展［J］.科技传播，2011，15（02）：173-175.

［4］姚向华.无线传感器网络原理与应用［M］.北京：高等教育出版社，2012：36-52.

［5］刘文进，周天明，李新春.一种能量均衡的WSN多级分簇路由算法［J］.计算机工程与应用，2016，52（16）：126-131.

［6］庄琴清.无线传感器网络分簇路由协议研究［D］.南京：南京邮电大学，2013.

［7］Abdul Razaque，Musbah Abdulgader，Chaitrali Joshi.P-LEACH：Energy efficientrouting protocolfor wirelesssensornetworks［C］.Systems，Applications and Technology Conference，2016，4（3）：77-81.

［8］赵凌，李盛.基于无线传感器网络PEGASIS算法的一种改进方案［J］.四川兵工报，2013，34（04）：107-110.

［9］Wassim.Jerb，iAbderrahmen Guermazi，Hafedh Trabelsi.O-LEACH ofrouting protocolforwireless sensor networks［C］.Intelligent Systems and Control（ISCO），2016.，38（4）：393-396.

［10］刘兴文.基于无线传感器网络的节能路由算法研究［D］.北京：北京交通大学，2015.

［11］Abdul.Razaque，Satwic，Mudigulam，KiranGavini.H-LEACH：Hybrid-low energy adaptive clustering hierarchy for wireless sensor networks［C］.Systems，ApplicationsandTechnologyConference，2016，4（3）：20-24.