基于LEACH的WSN路由算法研究

马箫雯，余 翔，许 未

(重庆邮电大学电信增值业务研究所，重庆400065)

0 引言

随着无线通信技术以及传感器技术的飞速发展，由具有感知能力、计算能力和通信能力节点组成的无线传感器网络［1-2］的研究越来越受到研究人员的重视。组成传感器网络的节点包括数据汇聚节点(sink)和普通的传感器节点。由于传感器节点能量有限，在进行传感器网络路由研究的时候，降低能耗使得无线传感器网络的整体存活时间延长是需要考虑的［3］。

低功耗自适应聚类路由协议［4］(Low Energy Adaptive Clustering Hierarchy，LEACH)是无线传感器网络中一种经典的分层次路由协议，算法通过循环随机地选取簇首节点来提高网络的能量利用率和延长系统的生命周期。相对于无线传感器网络的传统平面静态路由协议，LEACH可以将网络生存时间延长接近15%［5］。但是，LEACH协议在簇首选择采用的是各个节点等概率随机成为簇首的方式，没有考虑到节点的能量以及簇首与基站的距离等因素，而这些因素恰恰可能导致所选择的簇首不是最优，从而影响到整个网络的性能。针对LEACH协议存在的一些不足，提出一些改进建议，并针对其中的部分建议做了仿真验证，所采取的措施有效地提高了节点的能量利用率同时也延长了整个网络的生命周期。

1 LEACH协议

LEACH路由协议是Heinzelman(MIT，电子与计算系)于2000年为WSN设计的基于分层的低功耗自适应聚类路由算法。LEACH协议的工作过程被划分为周期性的“轮”，每轮包括成簇和数据传输两个阶段。在成簇阶段，节点之间首先按照一定的策略进行簇首选举，等到簇首节点确定之后，将向全网广播自身本轮担任簇首的消息，其他节点根据接收到的广播信号的强度来决定本轮所要加入的簇，最后，簇首节点接收加入请求消息并创建TDMA和CDMA编码机制。在数据传输阶段，簇首节点首先接收簇内成员节点采集的监测数据，然后对接收到的数据和自身的数据进行数据融合，最终将融合后的数据发送给基站［6］。

簇首节点的选取是LEACH算法的核心组成部分，这部分在整个LEACH协议中占有很重要的位置，其具体的选择策略描述如下:在成簇阶段，每个传感器节点产生一个［0，1］之间的随机数，如若该数小于某一个阀值Pi(t)，则向全网通告自己本轮担任簇首的消息;若该节点之前已经担任过簇首，则将阀值Pi(t)设置为0，表明本轮不再担任簇首;反之，如果节点之前没有担任过簇首，则在本轮中以阀值Pi(t)为概率竞选簇首;当网络中只剩下一个节点没有担任过簇首时，该节点将把阀值Pi(t)设为1，表明自己本轮无条件的成为簇首。其中Pi(t)的计算公式如下:

式中，Ci(t)表示节点i在最近rmod(N/k)轮是否担当过簇首节点，若担当过簇首，则Ci(t)=0，否则Ci(t)=1;k表示网络中簇首节点的个数，在一个已知的目标区域内，面积为M×M，传感器节点总数为N，节点均匀分布在检测区域中，即 ρ=(1/(M2/k))。可以通过下面公式推导出网络中最优的分簇个数:

式(2)、式(3)、式(4)中:εfs和 εmp表示无线能量模型中的参数;dtoCH是簇内成员节点到簇首节点的距离;Etotal表示总共消耗的能量;dtoBS表示簇首节点到基站之间的距离;Eelec表示发射电路和接收电路所消耗的能量;EDA表示节点进行数据融合所消耗的能量。

在每轮的稳定阶段，传感器节点将采集的数据传送到簇首节点。簇首节点对采集的数据进行数据融合后再将信息传送给汇聚中心，汇聚中心将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间之后，网络重新进行簇的建立阶段，也就是进行下一轮的簇重建，这样不断地循环。

2 LEACH协议的不足及改进方案

2.1 LEACH协议的不足

LEACH的不足在于，每轮进行都要选择簇头并划分簇，并且簇头需要一直处于醒着的状态以接收数据，这样系统开销较大，离散式区域算法对节点位置等要求不高，虽然能够通过公式推导出可能的分簇数目，但无法确定最优的簇数目。LEACH采用TDMA的MAC层机制，而事实上，在分配给节点的每个时隙，节点并不是都有数据要发送给簇头，这样的通信机制不能有效利用带宽，浪费了能量。LEACH还要求节点之间以及节点与sink之间都可以直接通信，因此局限了网络的可扩展性［7，8］。

LEACH以循环的方式随机选取簇首，将整个网络的能量负载平均分配到每个传感器节点中，从而降低能源消耗，提高网络整体生存时间。由于冗余数据被大量消除，因而在能耗方面有较好的性能。但LEACH仍存在如下不足之处。首先，LEACH算法是由网络中的传感器节点自组织的形成簇，簇首的选择具有极大的随机性。在该算法中进行簇首选择时没有考虑节点的剩余能量、周围邻节点的数目以及已经担任过簇首的次数等因素，这样会加重簇首的负担，使能耗不均［9］。当一个节点做簇首的次数过多时，不但自身的能量消耗加大，而且会使得距离自身较远的节点消耗较多的能量，不利于整个网络中节点能量的均衡和网络寿命的延长;其次，不同的簇首数目也会影响到整个网络的生存时间，LEACH算法簇首选择的随机性导致簇首数目的不确定。

基于以上LEACH算法在簇首选择过程中的不足，对算法进行改进，改进后的算法跟LEACH算法采用相同的网络要求。

2.2 改进算法LEACH_NEW描述

2.2.1 LEACH_NEW设计思路

根据上文中所指出的LEACH算法在簇首选择方面存在的问题，对LEACH算法做如下改进:

①静态分簇，在第一轮簇首选择之前根据节点位置情况进行静态分簇，并且之后不再重新分簇，只在该簇内选择最佳节点成为本簇的簇首节点，簇首节点在广播自己成为簇首的信息时也只是向本簇内的成员节点广播，不需要全网广播，大大减小了节点的能量消耗;

②在簇首选择过程中，将节点的剩余能量和网络的平均能量作为参数考虑，对阀值的计算公式进行改进，使得选出的簇首节点更加有利于网络能耗的均衡以及整个网络的生存;

③在数据传输阶段，利用参数记录簇头节点的邻簇头节点的数目、簇头到基站的最佳跳数和剩余能量，以便在多跳传输时簇头节点能够选择更合适的下一跳节点并且减小节点的能耗。

2.2.2 LEACH_NEW的工作过程

LEACH_NEW的工作过程与LEACH一样，也分为3个阶段。即簇首的选择阶段、簇形成阶段和数据传输阶段。

首先由于考虑到每一轮重新建立簇过程中所有节点消耗的能量，本文算法在算法执行开始时先采用静态分簇方式，在初始过程中节点就将簇分好，并进行相应的优化。之后簇内的节点不再发生变化，每一轮簇首的选择更新都在原簇内进行，这样减少了每一轮之前分簇时节点所消耗的不必要的能量。

①在第一轮簇首选择阶段，若按照式(1)得到的阀值选择簇首，就会出现簇首选择不当的问题。所以改进算法利用新的阀值计算公式如下:

式中，Ecurrent表示节点的当前能量，Einitial为节点的初始能量，Nneighbour表示节点的邻节点数目，CHtime表示节点在之前的轮中被选为簇首的次数。

②簇形成阶段，经过簇首选择阶段已经选出了网络中担任簇首的节点，随后每个簇首节点利用CSMA协议向自己管辖范围内的所有剩余节点以相同的传输能量发送自己是簇首的消息，通过该消息广播告知本簇内的成员节点自己成为簇首;接着簇内的剩余节点将会接受到来自簇首的消息，不过簇内节点可能会在一定间隔内收到多个这种消息，应为邻簇间存在干扰，在这种情况下节点根据接收消息的强度来选择簇首，然后再决定加入哪个簇。

每个节点加入相应的簇的同时，同样采用非持续CSMA协议向相应的簇首发送入簇消息，包括自身的ID号。当簇首接收所有簇内节点发来的该消息时，根据成员节点的数目，采用TDMA方式为每个簇成员分配发送数据的时隙。每个节点只在属于自己的时间内发送数据，在其他时间处于休眠状态，这样做也是为了减少节点的总能耗。

③数据传输阶段，采用多跳和单跳相结合的方式。在簇内采用单跳方式传输，在簇首与基站之间则分情况决定采用哪种传输方式。利用参数记录簇头节点的邻簇头节点的数目和剩余能量，若距离基站较近时就要避免多跳的路由机制，以减少路由的开销。当传输距离较大时，通过记录的邻簇头数目、跳数以及邻簇首的剩余能量选择最佳的一个下一跳节点，采用多跳传输机制，减少网络中簇头节点能耗，同时由于考虑了跳数因素，尽量减少簇首到基站的跳数，以节约中间节点的能耗。

3 仿真与分析

3.1 仿真环境

本文仿真工具采用网络仿真工具 NS2［10，11］进行仿真。NS2是一种可扩展的、容易配置的和可编程的时间驱动网络仿真工具，是由美国加州的LNBL网络研究组于1989年开始研究开发的软件。NS2源代码全部公开，提供开放的网络接口。本文的仿真环境:节点为100个并且随机分布在100 m×100 m的监测区域内，Sink节点的位置(50，100)，消息长度为500 byte，信息包的长度为25 byte，每一轮的时间为20 s，即节点每隔20 s的时间更换一次簇首，时间片的大小为0.023 s，每个节点的初始能量相同并且为2 J，网络带宽为2 M/s。

3.2 性能分析

通过对整个网络总的能耗以及网络中存活节点数目在LEACH和LEACH-NEW不同算法之下两个指标的对比，由图1可以看出在相同时间内，LEACH-NEW算法的能量消耗少，提高了网络的能量利用率，有效地延长了网络的生命周期。

图1 网络中的总的耗能情况比较

由图2可以明显地看出改进算法有效地延长了网络的生命周期，LEACH算法在150 s已经开始出现节点死亡，而LEACH-NEW算法在350 s才开始出现第一个节点的死亡，本文算法减少了簇头节点在建立簇时能量的消耗，同时数据传输阶段的单跳和多跳相结合也是减少了网络中节点的总的能耗。

图2 网络中存活节点数目

4 结束语

无线传感器网络的路由算法一直都是研究的热点，在对传统的LEACH算法深入研究的基础上，指出存在的不足，提出改进的算法，并利用NS2仿真工具进行了仿真实验。实验结果表明改进算法减少了网络的总能耗，有效地延长了整个网络的生存时间。

［1］ AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，etal.Wireless Sensor Networks:A Survey［J］.Computer Networks，2002，38(4):393-422.

［2］ 孙建民.无线传感器网络［M］.北京:清华大学出版社，2006.

［3］ KHAMFOROOSH K，KHAMFOROUSH H.A New Rounting Algorithm for Energy Reduction in Wireless Sensor Networks［J］.IEEE，2009:505-509.

［4］ 马祖长，孙怡宁，梅涛.无线传感器网络综述［J］.通信学报，2004，25(4):114-124.

［5］ 陈志奎，倪晶晶，姜国海，等.WSN中一种基于剩余能量级别的负载均衡路由协议［J］.微电子学与计算机，2010，27(12):82-86.

［6］ ZHANG Z，ZHANG X.Research of Improved Clustering Routing Algorithm Based on Load Balance in Wireless Sensor Networks［C］∥IET International Communication Conference on Wireless Mobile and Computing，2009:661-664.

［7］ HEINZELMANW R，CHANDRAKASANA，BALAKRISHNAN H.Energy Efficient Communication Protocol for Wireless Microsensor Networks ［C］∥ Proc.of HICSS＇00.Los Alamitos，CA，USA:IEEE Press，2000:3005-3014.

［8］ 沈波，张世永，钟亦平.无线传感网络分簇路由协议［J］.软件学报，2006，17(7):1588-1600.

［9］ 王磊，施荣华.无线传感器网络路由算法的仿真研究［J］.计算机仿真，2010，28(3):170-174.

［10］ UCB/LBNL/VINT Network Simulator-ns(Version 2)，http://www.isi.edu/nsnam/ns/，2011.

［11］徐雷鸣，庞博，赵耀.NS与网络模拟［M］.北京:人民邮电出版社，2008.