基于L E A C H协议的无线传感器网络路由算法的改进与仿真

赵芳芳，高媛

(中北大学 电子与计算机科学技术学院，山西 太原，030051)

0 引言

无线传感器网络(Wireless Sensor Networks,WSN)[1]可应用于军事、商业、医疗救护、环境监测等诸多领域，目前已成为计算机和通信领域中的研究热点之一。

无线传感器网络是由大量的微小节点通过无线通信技术组成的自组织网络。传感器节点依靠电池供给能量，而又不能对数量众多的节点更换电池，因此网络生命周期就成为了无线传感器网络的关键性能指标之一。在目前的研究中，分簇算法被认为是进行高效的能量管理、延长网络生命周期的最有效的途径之一。本文对经典的无线传感器网络分簇协议LEACH（低功耗自适应分簇协议）[2]进行了深入的研究，簇的形成方法是LEACH协议研究的主要内容，而簇头选择算法又是簇形成的核心，在LEACH协议中簇头选择算法不能做到最优，无法保证簇头处于恰当的位置，这导致簇头过早耗尽能量，缩短了网络的生命周期[3]。针对LEACH协议中簇头选择算法存在的不足，本文提出了改进的协议。

1 LEACH协议

1.1 LEACH协议算法

LEACH算法是一种周期性执行的低功耗自适应分簇拓扑算法[4]，在运行过程中,通过不断随机选取簇首达到能耗均匀分布的目的。LEACH定义了“轮”(round)的概念，每一轮分为两个阶段:簇的建立阶段和稳定工作阶段。在簇的建立阶段,首先需要选举簇首节点，簇首节点的选取是由每个节点自主决定的。对于每个节点n产生一个0~1的随机数，如果该随机数小于阈值T(n)，则节点当选为本轮簇首。T(n)定义如下:

式中:p为簇首节点占总节点数的百分比； r为当前的簇首选举轮数；G为过去轮中未当选簇首的节点集。在r=0时,节点以p的概率选取簇首；对于在前r(r<1/p)轮之内当过簇首的节点取消其再次当选的资格，从而保证其他节点以相同的概率当选簇首。当分簇过程完成后便可以进行数据的传输,进入稳定工作阶段。

1.2 LEACH协议的优缺点

LEACH协议具有很多优点，比如分层的簇型结构、本地数据联合处理和簇头节点动态分配，特别是在处理具有高度相关性的数据时，由于数据融合力度大，冗余数据被大量消除，因此在能耗方面性能较好，但LEACH仍有不足之处：

(1) 在LEACH算法中,分布式簇首选取机制能够均匀网络中节点能耗,但随机选取的簇首节点无法保证簇头节点在空间上均匀分布，在某些情况下，算法所选择的簇头节点可能集中在某一个小范围之内，使得一部分成员节点无法加入任何簇或者成员节点与簇头节点进行数据传输时消耗过多的能量[5-6]。

(2) LEACH算法假定所有节点都能直接与Sink节点进行通信，这显然限制了LEACH算法在较大区域内无线传感器网络的应用。

2 改进后的LEACH协议

针对LEACH路由协议的上述缺点，本文对簇头选择算法进行了改进，以平衡总的能量消耗、延长网络的存活时间为主要设计目标，提出了一种改进的LEACH路由协议。

在簇头选择阶段，LEACH协议是在整个区域中随机地选择簇头，这种方式简单，但是无法保证簇头节点在空间上的均匀分布，在某些情况下，算法所选择的簇头节点可能集中在某一个小范围之内，使得一部分成员节点无法加入任何簇或者与簇头节点进行数据传输时消耗过多的能量。改进后的协议充分考虑了簇头节点在空间上的分布，首先将整个网络划分成若干个小的区域，如图1所示。

图1 区域的划分

根据网络的大小、节点的传输范围和节点的分布密度决定区域的半径R。在标志为ZONE0的第1个区域中，传感器节点与Sink节点的距离小于区域半径R。在标志为ZONE1的第2个区域中，传感器节点与Sink节点的距离大于R，但小于2R。依此类推，在标志为ZONEi的第i个区域中，传感器节点与Sink节点的距离大于i×R，但是小于(i+1)×R。最后一个区域包含了超过上一个区域范围的所有剩余节点。因此，区域的总数为：

其中，N_ZONE为网络中区域的个数；NETWORK_ RANGE为网络的大小。

区域划分完后，Sink节点广播区域信息给每一个传感器节点，使它们知道自己属于哪个区域。每个区域中的簇头数目是根据每个区域的面积决定的。在ZONE0中由于包含Sink节点，因此不需要为该区域分配簇头节点。在ZONE1中，仅仅为它分配一个簇头节点。在ZONE2中，簇头的数目根据ZONE2区域的面积决定。如果ZONE2的区域面积是ZONE1的2倍，那么ZONE2应该有2个簇头。每个区域中的簇头数目为：

其中，N_Chi为区域ZONEi中的簇头数目。在区域范围内随机选择指定数目的簇头，可使簇头的分布更加均匀。

3 仿真实验及分析

3.1 仿真模型

实验中以NS-2 (Network SimulatorVersion-2) 作为仿真平台[7]，版本为2.28。，目前LEACH原协议仿真代码包mit.tar.gz可以从互联网上获得，脚本文件中对网络的一些设置参数如表1所示[8]。

表1 仿真参数

为了简化实验进程，本仿真实验进行的参数设定为：在100×100的方形区域内，随机分布100个节点，Sink节点位于(15,15)处，数据包的大小为2 000 bit，簇头的数据压缩率为0.7，即有2 000 bit数据发送到簇头，经簇头处理之后，将1 400 bit传给簇头中继。区域的半径R设置为20 m。节点的初始能量为2J，数据融合消耗的能量为5 nJ/bit/message，传输的能量为50 nJ/bit。

3.2 性能指标

在实验中，对于无线传感器网络的仿真，根据不同的要求需要不同的指标参数，改进的协议是以平衡所有节点总的能量消耗、延长网络的存活时间为主要设计目标，因此，从以下2个指标衡量改进后协议的性能：

(1)节点总的消耗能量：不同时刻所有节点消耗能量的总和。

(2)网络的存活时间：LEACH协议中假设节点不知其地理位置，且节点随机部署，为保证采集数据的精确性，选择从网络开始运行到第1个死亡节点出现的时间为网络的生存期(FND)。

3.3 仿真结果分析

图2所示的是改进前后LEACH协议在生命期结束时的能量消耗，改进后协议的能量消耗比改进前的减少21.46%。

图2 能量消耗对比

假设节点总能量的一部分专门为传感器供能，考察传感器耗能对改进前后协议运行的影响如图3所示，考察指标为网络的生存期，其中0代表不考虑传感器耗能的情况。

图3 网络生存期对比

图3显示当传感器耗能小于0.9 J(占总能量45%)时，协议的改进使网络生存期增加明显，0.9 J~1.2 J(占总能量60%)之间时生存期增加不多，而当传感器耗能增加为总能量的60%以及更多时，协议的改进对网络生存期的增加已经没有效果。这说明单纯从通信协议的角度为网络节能是在传感器耗能在一定范围时才起作用的，因此，在实际应用中降低网络的功耗还必须要结合所采用的传感器的耗能情况来设计节能措施。

由实验可知，无论是网络的存活时间还是所有节点总的能量消耗，改进后的协议都优于原LEACH协议。这说明在改进协议中，区域范围内进行簇头选择使得簇头节点在网络中的分布更加均匀，成员节点与簇头节点的通信将消耗更少的能量，延长了网络的存活时间。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless Sensor Networks:A Survey[J].Computer Networks,2002,38(4):393-422.

[2] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc.of HICSS’00.Los Alamitos,CA,USA:IEEE Press,2000.

[3] Mhater V,Rosenberg C.Homogeneous VS Heterogeneous Clustered Sensor Networks: A Comparative Study[C]//Proc.of IEEE Intel Conference on Communications.[S.l.]:IEEE Press,2004.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H. A application-specific protocol architecturefor wireless sensor networks [J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[5] Zhou Z, Zhou S, Cui S,et al. Energy-efficient cooperative communication in a clustered wireless sensor network [J]. IEEE Transactions on Vehicular Technology, 2008,57(6):3618-3628.

[6] 乐世成,王培康.无线传感器网络中的节能路由算法[J].计算机工程,2008,34(7):113-117.

[7] 徐雷鸣,庞博,赵耀.NS与网络模拟[M].北京:人民邮电出版社,2008.

[8] Varadhan F K.The NS Manual[Z].(2007-04-03).http:// www.isi.edunsnam/ns/ns-documentation.