对无线传感器网络的LEACH算法的改进研究

马红艳，邹学玉

(长江大学电子信息学院，湖北 荆州 430023)

对无线传感器网络的LEACH算法的改进研究

马红艳，邹学玉

(长江大学电子信息学院，湖北 荆州 430023)

无线传感器网络是一种能源受限网络，因而降低能耗并提高网络生存周期成为重要的研究目标。以分层路由协议LEACH为研究基础，针对其不足，在簇首选举、簇首对Sink节点的通信方式2方面进行改进，并利用 OPNET对LEACH算法及其改进算法进行仿真试验。结果表明，改进算法有利于提高网络性能，明显延长网络生存时间。

无线传感器网络；分层路由协议；LEACH协议算法；网络生存时间

无线传感器网络(Wireless Sensor Networks,WSN)是由微电子机械系统、计算机、通信、自动控制和人工智能等技术发展起来的一种新型测控网络，其具有自组织、自治、自适应等智能属性，在军事、医疗监测、空间探索等领域有广泛用途[1]。无线传感器网络路由协议主要分为平面路由协议和分层路由协议。由于平面路由协议中网络内各节点功能地位相同，没有引入管理分层机制，其可扩张性小，缺乏对通信资源的优化管理，限制了网络规模，而分层路由协议在一定程度上可解决上述问题[2]。低功耗自适应聚类路由协议LEACH是比较典型的分层路由算法，但其对簇首的选择具有随机性，而簇首对Sink节点采用单跳传输方式不能有效提高网络生存时间[3]。为此，笔者对(Low Energy Adaptive Clustering Hierarchy，LEACH)算法进行改进以降低无线传感器网络功耗来延长其生命周期。

1 LEACH算法

1.1LEACH算法原理

图1 分簇路由协议的数据传输流程简图

无线传感器网络的路由协议中，通常有不带分簇的单跳路由和多跳路由协议、带分簇的单跳路由和多跳路由协议[4-5]。在分簇路由通信协议中数据常按“轮”进行，每1轮可分2阶段，即成簇阶段和数据传输阶段。图1所示为LEACH分簇路由协议的简单数据传输时间流程[6]。

在数据传输阶段，簇首在1帧内收集簇内所有活动节点的监测数据，经簇内处理后转发至BS节点，上述过程可重复多次，但若重复次数过多，通信协议将由动态分簇路由退化为静态分簇路由，易于导致簇首节点能量过度消耗而死亡，因而在每1轮内，簇首一般工作1～2个帧。

在LEACH的成簇阶段，簇首的选举方法是每个传感器节点随机选择0～1之间的一个值，如果选择的值小于某个阈值T(n),那么该节点就成为簇首节点。T(n)的计算公式如下：

(1)

式中，p为网络中簇首数量与节点总数的百分比；r为当前选举的轮数；G为最近1/p轮不是簇首的节点集。

选定簇首节点后，通过广播告知整个网络。网络中的其他节点根据接收信号的强弱决定从属哪个簇，并通知相应的簇首节点，完成簇的建立。最后，簇首节点采用TDMA方法为簇中每个节点分配向其传送数据的时间片。

在 LEACH的传输阶段，传感器节点将采集到的数据传送到簇首节点。簇首节点对簇中所有节点采集的数据进行信息融合后再传送给汇聚点，这是一种减小通信业务的合理模式。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一回合的簇重构，如此不断循环。每个簇采用不同的CDMA代码进行通信来减少其他簇内节点的干扰。

1.2LEACH协议的网络模型及数据传输

图2 LEACH协议及改进后的数据传输图

LEACH协议的网络模型存在如下特点：①网络中有固定基站(sink节点),其具有充足的能源，故研究中不考虑其能耗，且具传感器节点均较远。②网络中所有传感器节点同构并具有相等的有限起始能量。③节点处于静止状态且总有数据需要传输。④节点能改变发射功率并感知其剩余节点能量。

LEACH协议数据传输如图2(a)所示。由图2(a)可知，从图簇内节点通过一跳通信将数据传送给簇首，簇首也通过一跳通信将聚合后的数据传送给sink节点。

1.3LEACH算法的不足

LEACH以循环的方式随机选取簇首，将整个网络的能量负载平均分配到每个传感器节点中，从而降低能源消耗，提高网络整体生存时间。由于冗余数据被大量消除，因而在能耗方面有较好的性能。但LEACH仍有如下不足之处：①LEACH算法是由网络中的节点自组织地形成簇，簇首是随机产生的。由于簇首的选择未考虑节点的剩余能量，周围邻节点数及已经担任过簇首的次数会加重簇首负担，使能耗不均。节点做簇首次数过多时，不但自身能耗大，而且会使离自身较远的节点消耗较多能量，不利于节点能量的均衡和网络寿命的延长。②簇首在传输数据时采用单跳传输方式，直接将数据包传送给sink节点，距离sink较远的簇首因此会消耗较大能量，部分簇首会过早死亡。

2 对LEACH算法的改进

针对LEACH算法的不足，可以在簇首选择及簇间数据传输2方面进行改进(见图2(b))，以平衡总的能量消耗来延长网络生存寿命。

2.1簇首的选择

由于LEACH的簇首竞争门限引起了区域性能量消耗不均衡等问题，因而可以充分考虑节点剩余能量、节点临近数目(通信半径内节点)及节点有未充当簇首的次数，根据文献[7]，将式(1)改进如下：

(2)

式中，Ecurrent表示节点的当前能量；Emax表示节点的初始能量；Nx表示节点在最近连续几轮中未充当簇首节点的次数；Nneighbor表示节点的邻居节点的数目。

改进算法中除阈值算法不同外，簇首选择的其他过程与LEACH算法相同。

2.2簇间数据传输

在进行簇间数据传输时，簇首收到所属成员的传感数据后先做初步的数据融合，然后将新的融合数据通过多跳算法发往基站。

传感器节点总能量消耗E与距离d的关系为[8]：

E(d)=kdα+γ

(3)

式中，k=wΔt,w为系数常量，Δt为数据包发送的时间；γ为额外功率消耗，是不随距离d变化的常数，在不依赖于距离变化的任何功率消耗都可以加到γ上去。

图3 簇首中继节点选择图

由于传感节点的能量消耗与通信距离成指数关系，当中继节点i(0

假设簇首与基站的传输距离小于自由空间传播与多径传播的临界距离，由式(3)可得簇首与基站直接通信的能耗：

(4)

式中，d0为簇首0到基站的距离。

假设传感器节点额外功率消耗γ相同，当通过簇首i中继通信后，簇首0的通信能耗为：

(5)

式中，ci为簇首节点0到簇首节点i的距离；di为簇首节点i到基站的距离。

由于能量消耗主要涉及无线通信链路，而γ在整个节点能耗中所占的比例很小，若忽略γ，则：

(6)

在图3中，当中继节点处于以基站和簇首节点0的连线为直径的圆O上时，通过中继节点消耗的能量等同于簇首节点直接传输的能量消耗。由平面几何知识证明如下不等式成立，即：

(7)

由此可得：

(8)

即：

E1(d1,c1)

(9)

图4 中继节点选择流程图

3 仿真试验

为了评价改进算法的性能，利用网络仿真工具OPNET对相同状态下的LEACH算法和改进算法在网络生存时间方面进行仿真比较，使用的网络模型配置如下，在200m×200m的平面区域使用500个无线传感器节点和1个固定位置的sink节点，且sink节点远离该感知区域。每个无线传感器节点的初始能源为2J，数据包大小为500byte,元数据大小为25byte。簇首节点剩余能量比较图如图5所示。由图5可知，在相同时间内使用改进算法的簇首能耗比使用LEACH算法的簇首能耗要低。网络生存时间比较图如图6所示。由图6可知，在簇首数相同时，使用改进算法的网络生存时间比使用LEACH算法的网络生存时间更长。

图5 簇首节点剩余能量比较图 图6 网络生存时间比较图

4 结 语

阐述了LEACH算法的基本原理，针对该算法的不足，在簇首选择及簇间数据传输2方面进行改进。改进簇首选择机制可平衡节点的剩余能量，采用单跳与多跳相结合的簇间数据传输方式可平衡每个簇间的能量消耗。因此，对LEACH算法的改进有利于提高网络性能，明显延长网络生存时间。

[1]于海斌，曾鹏.智能无线传感器网络系统[M].北京：科技出版社，2006.

[2] 李善仓，张克旺.无线传感器网络原理与应用[M].北京：机械工业出版社，2008.

[3] Heinzelman W,Chandrakasan A, Balakrishman H. An application-specific protocol architecture for wireless micro-sensor networks [J]. Wireless Communications,2002,1:660-670 .

[4] Kalaki J N,Kamal A E. Routing techniques in wireless sensor networks: A Survey [J]. Wireless communications 2004，11:6-28.

[5] Younis O, Fahmy S. HEED: A Hybrid, energy-efficient, distributed clustering approach for Ad Hoc sensor networks [J]. Transactions on mobile computing，2004，3:366-379.

[6] 顾明霞.无线传感器网络的LEACH算法改进与仿真研究[J].计算机仿真，2010,27(9)：139-185.

[7] Handy M J, Haase M D.Timmermann low energy adaptive clustering hierarchy with deterministic cluster-head selection[J]. Mobile and wireless communications networks,2002,9:368-372.

[8] 姜华，王沛.无线传感网络中的OPNET仿真模型的研究[J].计算机工程，2007，33(4)：73-78.

[编辑] 李启栋

10.3969/j.issn.1673-1409.2011.08.030

TP751

A

1673-1409(2011)08-0094-04