MELEACH一个高效节能的WSN路由协议

传感技术学报

CHINESEJOURNALOFSENSORSANDACTUATORS

Vol.20　No.9Sep.2007

MELEACHAnEnergy2EfficientRoutingProtocolforWSNs3

CHENJing,SHENHong

3

(DepartmentofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027,China)

Abstract:WirelessSensorNetworks(WSNs)areseverelyresourceconstrained,especiallyintheaspectofpowersupply.HowtoeffectivelymanagepowerconsumptionsothatthelifetimeofaWSNcanbemaxi2mizedisacentraltopicforresearchinWSNroutingprotocols.AsanattractiveWSNroutingprotocol,LEACH[1～2]hasbeenwidelyacceptedforitsenergyefficiencyandsimplicity.BasedonLEACH,wepro2poseanewroutingprotocolMELEACH(MoreEnergy2efficientLEACH),whichhasabetterperformanceonenergyefficiencywithoutlosingtheadvantagesofLEACH.MELEACHimprovesLEACHbyfurtherreducingthemeantransmissiondistanceandimprovingtheloadbalancebetweensensornodes,Ouranaly2sisandsimulationresultshaveshownthatthelifetimeofaWSNrunninginMELEACHisatleast50%longerthanthatrunninginLEACH.

Keywords:wirelesssensornetwork;energyefficiency;distance;loadbalance;routingprotocol;LEACHEEACC:6150P;7230

MELEACH一个高效节能的WSN路由协议3

陈　静,沈　鸿3

(中国科学技术大学计算机科学与技术系,合肥230027)

摘　要:无线传感器网络(简称WSN)一种资源严重受限的网络,特别是在供能方面.因此,如何有效地使用传感器节点的能

量以延长WSN的生存时间,一直是WSN路由协议研究所关注的焦点.LEACH[122]作为一种WSN路由协议,以其优秀的节能效果和简单的规程而得到广泛的认可.本文基于LEACH提出了一个新的路由协议MELEACH(MoreEnergy2efficient

LEACH).通过进一步缩短无线通信的平均距离并进一步改善节点间的负载平衡,MELEACH在保持LEACH原有优点的

基础上实现了更好的节能效果.分析和实验表明,一个WSN在MELEACH下的生存时间要比在LEACH中长50%以上.

关键词:无线传感器网络;节能;距离;负载平衡;路由协议;LEACH

中图分类号:TP393　　文献标识码:A　　文章编号:100421699(2007)09220206　　无线传感器网络(简称WSN)是由一个基站,以及大量集成了传感和无线通信能力的传感器节点所组成的分布式系统.传感器节点一般由传感模块、通信模块、处理模块和供能模块组成,此外还可能带有定位模块和运动模块等.这些传感器节点,探测所在环境的物理信息,并最终把相应的数据上传给基站.作为一种新型的信息收集和处理技术,它有广泛的应用价值,例如,医疗中的病患监护,军事中的指挥、控制、通信、智能计算、监视、侦查和目标识别系统,工商业中的存货管理、产品质量监控和事故监控

基金项目:中国科学院“百人计划”资助收稿日期:2007201221　　修改日期:2007204203

等[3].传感器网络的分布式特性和传感器节点微小

的体积决定了它一般只能由小型电池提供电源.在目前的技术条件下,电池容量平均每十年只能提高20%左右,受制于这种,单位重量的电池容量很难在短期内有大幅度的提高[4].因此,传感器网络在供能上不可避免受到很大.而且,在许多应用场景中,更换电池或给电池充电是高代价的,甚至是不现实的.例如,NASA就计划把传感器网络部署到火星上的某些令人感兴趣的区域[5].同时,在传感器网络中,无线通信所消耗的能量要远大于计算和传

2090传　感　技　术　学　报2007年

感所消耗的能量[6].所有这些因素都表明,为了降低传感器网络的部署和维护成本,开发高效的路由协

议和拓扑控制协议以使传感器网络得以更节能的通信方式工作是很有必要的.其中传感器网络中节能的路由协议作为节能通信协议的重要组成部分,已成为一个研究热点,受到研究者的广泛关注.

目前,无线传感器网络中的节能路由算法的设计思想按照其优化目标大致可以分为两类:最小化总能量消耗和最大化系统生存时间.前者从宏观的角度考虑节能的问题,把传统有线网络中的节能措施与无线电辐射模型相结合,可以概括为尽可能减少不必要的数据发送,尽可能减少单位数据的传输总耗能(如SPIN[728],DirectedDiffusion[9]等).后者则是把宏观与微观相结合———在尽可能降低在耗能的基础上,寻求系统的负载平衡,防止局部节点耗尽能量而损害系统的整体功能,从而延长系统的生存时间(如LEACH[122],PEGASIS[10],FA[11],EN2CAST[12],DEER[13]等).对WSN中节能路由和数据收集方法和技术我们也已有若干研究成果,例如文献[14]、[15]和[16].实际上,对于基站的处理程序来说,WSN在许多应用场景中所直接收集的数据太多或太粗糙.人们希望,WSN能够把这些冗余的信息先聚合成少量真正有意义的信息,再提交给上层处理.简单的聚合操作可以是sum、average、min、max、count等,复杂的聚合可以是信号整形等[2].LEACH协议是第一个提出数据聚合的层次路由协议.为了平衡网络各节点的能耗,簇首是周期性按轮并按照给定概率随机选举的.成为簇首的节点在无线信道中广播这一消息,其余节点选择加入信号最强的簇首.节点通过一跳通信将数据传送给簇首,簇首也通过一跳通信将聚合后的数据传送给基站.该协议采用随机选举簇首的方式避免簇首过分消耗能量,提高了网络生存时间;数据聚合能有效减少通信量.LEACH也以其优秀的节能效果和简单的规程而得到广泛的认可,并被作为许多进一步研究工作的基础[17218].本文提出的MELEACH(MoreEnergy2efficientLEACH)是对LEACH的进一步改进,在保持LEACH原有优点的基础上实现了更好的节能效

1　网络模型和能量消耗模型

本文所讨论的WSN由一个基站(BS)和N个传感器节点组成.BS被安置在远离传感器节点的地方;所有传感器节点都是同构的并且能量受限.每个节点能够通过相应机制(如GPS等[19])获悉自身的位置,及周围一定距离内其它节点的位置信息.节点能够监测自身的能量水平,并且其无线天线的发射功率是可控的(只要调整到一定功率就能与BS直接通信).把长度为l比特的消息发给相距d的节点所消耗的能量是[1]:

2

ETx(l,d)=lEelec+εlampd接收这样的一个消息所消耗的能量为:

ERx(l)=lEelec由于传感器中其它模块的功率远小于通信模块的功率,相对而言可以忽略,我们只考虑收发数据的能耗.2　MELEACH

MELEACH的执行过程是由多个轮构成的.每

轮分为3个阶段———簇首选举、生成树构造和数据收集.数据收集阶段有多个帧构成,每个帧由若干个收发数据的时间片组成.MELEACH的时间图如图1所示.其中簇首选举和生成树构造对应于LEACH的Set2up阶段,数据收集对应于LEACH的Steady2state阶段.以下将对MELEACH的各个阶段做详细阐述.

图1　MELEACH的时间图

2.1　簇首选举

为了使簇首节点比较均匀地分布在网络中,并

防止剩余能量少的节点成为簇首,促进负载平衡,MELEACH通过以下过程选举簇首:

①传感器节点i设置一个定时器Ti;

②若Ti超时,则i成为簇首节点,并通过CSMA协议向整个WSN广播ADV消息(消息中包含i坐标),若i是第一个发送ADV消息的结点,则i成为根簇首节点;

若i收到j广播的ADV且|ij|≤Dcluster,则i取消Ti并成为非簇首节点;

若i收到k个节点的ADV,则i取消Ti并成为非簇首节点.

其中

果.

本文的其余部分是这样组织的:第1节给出我们所使用的网络模型和能量消耗模型;第2节阐述MELEACH的具体细节;第3节是对LEACH和MELEACH的能量消耗情况的分析;第4节是模拟

实验的结果;最后,第5节总结本文.

第9期

Ti=α陈　静,沈　鸿:MELEACH:一个高效节能的WSN路由协议

Estart-Eresidual.i)[random](0,1)・δ+(1-α

Estart

2091

节点最近的节点,则i选择簇首节点为自己的父节点;否则i在附近的簇成员节点中选择一个比自身更靠近簇首且距离自身最近的节点j,若i与j的距离小于i与簇首节点的距离,则取j为i的父节点,否则取簇首节点为i的父节点.

各成员节点把自己的选择结果发送给簇首节点.簇首节点完成拓扑排序后,为各个成员节点分配收发数据的TDMA时间片.2.3　数据收集

该阶段的每一帧分为两个过程:

首先进行簇内收集和聚合:各成员节点根据既定的时间片收集并聚合子节点和自身的数据,再向父节点发送处理过的数据.

然后进行簇首间的收集和聚合:各簇首节点根据既定的时间片收集并聚合子节点和自身的数据,再向父节点发送处理过的数据.在根簇首节点收集聚合了所有数据后,把结果发送给远处的BS.在LEACH中,成员节点直接向簇首节点发送数据,簇首节点直接向远处的BS发送数据.这样的远距离通信是很耗费能量的.在2.2小节所述的生成树构造过程中,簇内生成树中的节点基本都是选择距离自身最近的簇成员节点为自己的父节点,簇

Estart为节点的初始能量,Eresidual.i为节点i当前的剩

余能量,α为一常数(本文中取α=0.1),δ为簇首选举阶段的总时间.选举过程中,Dcluster满足:

πDcluster=M4k

2

M为WSN部署区域的面积,k为WSN中簇首个数.2.2　生成树构造

图2给出了生成树构过程的示意图.其中,方形区域为WSN的部署区域,区域中的小圆圈(点)代表传感器节点,其中黑色圆点代表簇首节点;部署区域外的圆圈代表基站(BS);图中的箭头都是从子节点指向父节点.在该过程中,簇首节点将构造以根簇首节点为树根的簇首生成树(图2(b)),而每个簇中的传感器节点将组成以簇首节点为树根的簇内生成树(图2(c)).

2

2

图2　生成树构造示意图

在构造簇首生成树时,每个簇首节点将这样选择自己的父节点:根簇首节点选择BS作为自己的父节点;若本簇首节点i是距离根簇首节点最近的非根的簇首节点(利用地理坐标信息确定距离),则i选择根簇首节点为自己的父节点;否则i在比自身更接近根簇首的非根的簇首节点中,找出与i距离最近的簇首节点j,若i与j的距离小于i与根簇首节点的距离,则取j为i的父节点,否则取根簇首节点为i的父节点.

各簇首节点在选择了自己的父节点之后,把选择结果发送给根簇首节点.根簇首节点按照该父子

关系,对簇首节点进行拓扑排序(线性复杂度),使父节点排列在子节点之后.根簇首节点根据该顺序为各个簇首节点分配收发数据的时间片,并把该TD2MA调度发送给相应簇首节点.

首生成树中的簇首节点基本都是选择距离自身最近的簇首为父节点.所以,MELEACH的数据收集中,各个节点都基本上与距离自身最近的节点通信,由第1节的能量消耗模型可知,这将大大节省能耗,而且没有增加LEACH的时延(不像PEGASIS[10]).此外,MELEACH在数据收集过程中,不仅在簇内收集中,而且在簇首间收集中都采用了TDMA方式.一方面,这使得各节点只需要在指定的时间片上收发数据,在其它时间片可以使所有模块中耗能最大的通讯模块进入休眠状态,从而节省能量.另一方面,由于采用TDMA方式(时间片和频段的分配如2.2小节所述),避免了各节点间的通信干扰,提高了数据传输的可靠性,也避免了因重发数据而引起的能量浪费.

3　能耗分析

LEACH和MELEACH都是在多个周而复始

在构造了簇首节点生成树后,各个簇采用与LEACH协议相同的方式集簇和为各个簇分配不同

的频段,并在各自的频段下采用与以上类似的规程构造簇内生成树.

各簇成员节点将这样选择自己的父节点:与附近一定距离内的节点相比,若本节点i是距离簇首

的帧中完成数据收集的.这里,我们在本文给出的网络模型和能量消耗模型基础上,参考文献[2]的方法,对两个协议在每一帧中消耗的能量进行分析和比较.我们假设WSN中的N个节点均匀分布在M×M的方型区域中,LEACH中各传感器节点在每次簇首选举中成为簇首的概率是k/N,k个簇首均

2092传　感　技　术　学　报

于是,WSN在每帧中消耗的总能量为

EMELEACH

2007年

匀分布.

在LEACH的每一帧中,每个簇首节点要接收本簇其它成员节点直接发来的数据,把它们聚合后发送给BS:

ECH=

N-1・ERx(l)+ETx(l,dtoBS)k

N2

+εlampdtoBSk

=ERec+ETran-in-cluster+ETran-between-CHs+ETran-rootCH

在初始状态相同的情况下,使用MELEACH的WSN的生存时间TMELEACH与使用LEACH的WSN的生存时间TLEACH的关系用下式估计

TMELEACHEtotal/EMELEACHELEACH==

TLEACHEtotal/ELEACHEMELEACH

=lEelec

由于各个传感器节点是均匀分布的,故我们可

以估计d2toBS的均值为

MM

1222

()EdtoBS=[(x-xBS)+(y-yBS)]2dxdy

4　模拟结果及分析

本节用C语言模拟了直接传输(Direct)、LEACH和MELEACH这三种协议的工作情况.模

∫∫

0

0

M

每个非簇首节点,在每一帧中,只要向簇首节点发送自己的数据

2

Enon-CH=ETx(l,dtoBS)=lEelec+εlampdtoCH

根据文献[2]对dtoCH的期望的估计

E[d

2

toCH

拟实验中,参考文献[1]和文献[2]取如下参数:

表1　模拟实验参数参数

电池Estart

Eelec

]=

πk2

N-1Enon-CHkM2

取值1J

50nJ/bit100pJ/(bit・m-2)

100100m2000bit

5(50,175)

在每一帧中,一个簇的能耗为Ecluster=ECH+

εamp

NMlk

则整个WSN在一帧中的总能耗为ELEACH=kEcluster

amp=l(2N-k)Eelec+(N-k)ε

BS坐标

πk2

在MELEACH的生成树中,父子关系主要表现为子节点发送数据,父节点接受并聚合数据,所以每一帧整个WSN消耗在接收数据上的能量为

ERec=(N-1)ERx(l)=l(N-1)Eelec

非簇首节点消耗在发送数据上的能量为

ETran-in-cluster=(N-k)E[ETx(l,dtoParent)]

2

=(N-k)[lEelec+εlfriss-ampE(dtoParent)]

M2

2

+εkampE(dtoBS)

　　根据表1的参数,可以估计

TMELEACH≈1.54

TLEACH

图3给出了3种协议的存活节点数目随时间(帧)的变化情况.

因为各传感器节点是均匀分布的,且个节点都选择尽可能近的节点作为自己的父节点,则可有

π即

E(dtoParent)=

2

E(dtoParent)2

4

・N=M2

图3　实验结果

πN

Eelec+εamp

4M2

Direct(曲线a)中,各个传感器节点由于直接向

故

ETran-in-cluster=l(N-k)

πN

4M2通过类似于以上的推导可得,每一帧中,簇首节点向

父簇首节点发送数据所消耗的总能量为

24MampETran-between-CHs=l(k-1)Eelec+επk根簇首节点向BS发送数据所消耗的能量为

2

ETran-rootCH=lEelec+εlampdtoBS

远处的BS发送数据,很快耗尽了电池的能量:在

152frame之后存活节点数量就急剧下降,到192frame存活节点数目降到80以下,到253frame存活节点数目降到60以下.

LEACH(曲线b)协议中,由于大多数节点只进行近距离传输(相对于BS),只有少数簇首节点进行高耗能的远程通信,而且通过轮转的办法防止簇首节点过早死亡,所以其性能远优于Direct:到799frame之后才开始有节点死亡(5倍于Direct),到

第9期陈　静,沈　鸿:MELEACH:一个高效节能的WSN路由协议2093

1004frame存活节点数降到96,然后存活节点数急

好的节能效果,MELEACH在节能上又有更优秀的表现,但是它们也有其局限性.考虑到传感器节点

的处理能力有限,LEACH/MELEACH主要针对数据在聚合后尺寸不膨胀或仅少量膨胀的数据聚合操作[2].对于需要大量原始数据上传、聚合过程复杂或聚合后数据尺寸急剧膨胀的应用场景,LEACH/MELEACH就不太适用.由于LEACH/ME2LEACH协议中要求WSN中的每个节点都有能力

剧减少.

MELEACH(曲线c)中,到2971frame才开始有节点死亡,到3470frame存活节点数降到95,然后存活节点数急剧减少.MELEACH不仅如所估计的,比LEACH显示出更好的节能效果,而且超出了预期.主要有3个原因.第一,如第2.3小节和第3节分析所示,在每一帧中MELEACH的能耗少于LEACH.第二,在选举簇首时,由于LEACH使用的是完全随机的方式,簇首的分布可能过于集中,从而出现过大的簇.在这些过大的簇中,远在簇边缘的成员节点向簇首节点发送数据时会过分消耗能量而过早死亡.在MELEACH中,我们利用地理信息防止簇首过分集中,故不会出现这种情况.第三,虽然LEACH利用轮转策略防止簇首过度消耗,但由于使用的是几乎完全随机的方式,难免选择一些能量较低的节点为簇首,反而不利于节点的生存.MELEACH中,各节点根据自身的能量水平竞选簇首,保证由剩余能量水平较高的节点担任簇首.

与BS直接通讯,因此,鉴于节点通讯能力的,LEACH/MELEACH只适用于中小型WSN.对于

大型网络,只能选择普通的多跳路由协议.为了延长大型WSN的生存时间,研究者们也在普通多跳路由协议基础上提出了一系列节能路由协议,如FA[11],ENCAST[12],DEER[13]等.这些协议在节省

总能耗和改善负载平衡方面都提出了许多巧妙的策略.针对大型WSN的节能路由协议也将是我们下一步的研究方向.

致谢:感谢国家高性能计算中心(合肥)陈国良院士和中国科学技术大学计算机系黄刘生教授对本工作的支持和帮助.参考文献:

[1]　HeinzelmanW,ChandrakasanA,BalakrishnanH.Energy2

EfficientCommunicationProtocolforWirelessMicrosensorNetworks[C]//Proc.ofthe33rdAnnualHawaiiInt’lConf.onSystemSciences.Maui:IEEEComputerSociety,2000.300523014.

[2]　HeinzelmanW.Application2SpecificProtocolArchitecturesfor

WirelessNetworks[D].MIT.2000.

[3]　AkyildizIF,SuW,SankarasubramaniamY,CayirciE.Wire2

lesssensornetworks:ASurvey[J].ComputerNetworks,2002,38(4):3932422.

[4]　王鲲.无线自组网中节能策略的研究[D].合肥:中国科学技

5　结束语

相对于LEACH,在本文所提出的MELEACH中,大多数节点的传输距离更短,簇首分布更加均

匀,而且进一步减少了了剩余能量相对较少的节点成为簇首的可能性.理论分析和模拟实验都证明我们的策略具有很好的节能效果,大大延长了WSN的生存时间.

正如文献[1]所述,LEACH/MELEACH这类节能路由协议的突出优点是,LEACH/MELEACH能够把网络的负载较均匀地分散到整个WSN,从而大大缩小了网络中节点的生存时间之间的方差.因此,整个WSN只有在绝大多数节点的能量水平都接近零时才会有节点死亡,并在死亡的节点数和分布达到一定程度时丧失有效功能(即结束WSN的生存时间).而在普通的多跳路由协议中,离BS较近的节点不可避免地要比远处的节点承担更多的转发任务.这容易导致,当近处的节点耗尽能量时,远处还有大量的节点处于高能量水平.由于近处节点的大量死亡,将导致数据失真,而且由远处的节点所采集的数据也将难以上传,进而造成WSN在较高能量水平上就终止有效生存时间.

不同于Internet,WSN的设计与构造总是同特定的应用场景结合在一起的,处理不同的实际问题需要相应地设计不同的WSN.一类WSN路由协议不可能适用于所有的应用.虽然LEACH协议有很

术大学,2005.

[5]　DongQF.MaximizingSystemLifetimeinWirelessSensor

Networks[C]//IPSN,April,2005:13219.

[6]　NiculescuD,CommunicationParadigmsforSensorNetworks

[J].CommunicationsMagazine,IEEE,2005,43(3):1162122.

[7]　HeinzelmanW,KulikJ,andBalakrishnanH,AdaptivePro2

tocolsforInformationDisseminationinWirelessSensorNet2works[C]//Proc.5thACM/IEEEMobicom,Seattle,WA.August1999:1742185.

[8]　KulikJ,HeinzelmanWR,andBalakrishnanH,Negotiation2

BasedProtocolsforDisseminatingInformationinWirelessSensorNetworks[J].WirelessNetworks,2002,8:1692185.[9]　IntanagonwiwatC,GovindanR,EstrinD,HeidemannJ.Di2

rectedDiffusionforWirelessSensorNetworking[J].IEEE/ACMTransonNetworking,2003,11(1):2216.

2094传　感　技　术　学　报2007年

[10]　LindseyS,RaghavendraCS.PEGASIS:Power2Efficient

GatheringinSensorInformationSystems[C]//Proc.oftheIEEEAerospaceConf.Montana:IEEEAerospaceandE2lectronicSystemsSociety,2002.112521130.

[11]　ChangJH,TassiulasL.MaximumLifetimeRoutinginWire2

lessSensorNetworks[J].IEEE/ACMTransonNetwor2king,2004,12(4):6092619.

[12]　ZouS,NikolaidisI,JanelleJ.Harms,ENCAST:Energy2

criticalNodeAwareSpanningTreeforSensorNetworks[C]//CommunicationNetworksandServicesResearchCon2ference,2005.Proceedingsofthe3rdAnnual:2492254.

[13]　WangY,WuH,NelavelliR,TzengNF,Balance2BasedEn2

ergy2EfficientCommunicationProtocolsforWirelessSensorNetworks[C]//26thIEEEInternationalConferenceonDis2tributedComputingSystemsWorkshops(ICDCSW’06),2006:85.

[14]　ZhangHB,ShenH.DistributedTuningAttemptProbability

forDataGatheringinRandomAccessWirelessSensorNet2works[C]//AINA(1)2006:328.

[15]　ZhangHB,ShenH,HaibinKan.Reliability2Latency

TradeoffsforDataGatheringinRandom2AccessWirelessSensorNetworks[C]//GCC2005:7012712.

[16]　TianH,ShenH,andTeruoMatsuzawa.RandomWalk

RoutinginWSNswithRegularTopologies[J].JournalofComputerScienceandTechnology,2006,21(4):4962502.

[17]　吴臻,金心宇.无线传感器网络的LEACH算法的改进[J].

传感技术学报,2006,19(1):34.

[18]　孙天一,陈涤.无线传感器网络LEACH协议的探讨及改进

[J].传感器世界2005.1:32.

[19]　曾子维,苏啸,韩鹏,毛迪林.一个基于类的无线传感器网络

并发事件的路由协议[J].计算机应用与软件,2006,23

(3):73.

陈　静(19822),于2005年在厦门大学计算机科学技术系取得学士学位,同年被免试推荐进入中国科学技术大学计算机科学与技术系攻读硕士研究生.他目前是“百人计划”教授沈鸿所主持的“服务计算与应用实验室”的成员,主要研究方向是计算机系统结构、无线传感

器网络,jch@mail.ustc.edu.cn.

沈　鸿,博士,中国科学技术大学计算机科学与技术系(中国

)教授、科学院“百人计划”博士生导师.曾在澳大利亚和日本

主要大学任教授多年.主要研究方向是并行与分布式计算、高性能网络、算法、数据挖掘等,目前已发表学术论文200余篇,其中100余篇发表在IEEE/ACMTransactions等国际期刊上.他曾获1991年国家教育部科技进步奖,1992年中国科学院自然科学奖,hongshen@ustc.edu.cn.