一种基于LEACH协议的节能型分簇路由算法

文章编号:100622475(2009)1220133204

计算机与现代化

JISUANJIYUXIANDAIHUA

总第172期

一种基于LEACH协议的节能型分簇路由算法

张　源

(北京交大微联科技有限公司,北京100044)

摘要:LEACH协议中最高级簇头与基站之间采用单跳通信方式,消耗能量较多。为了降低无线传感器网络的能量消耗,

提出了一种基于LEACH协议的节能型分簇路由算法。该算法采用平面路由机制建立簇头与基站之间的通信路径,所有簇头与基站之间都采用多跳路由方式。与LEACH协议相比,该算法明显改善了网络能量消耗和网络生存时间,并使网络规模不再受到簇头通信半径的。

关键词:无线传感器网络;分簇路由协议;平面路由协议;DD2LEACH中图分类号:TP393　　　文献标识码:A　　　doi:10.3969/j.issn.100622475.2009.12.037

AnEnergy2savingClusteringRoutingAlgorithmBasedonLEACH

ZHANGYuan

(BeijingJiaodaMicrounionTech.Co.,Ltd.,Beijing100044,China)

Abstract:One2hoproutingisusedinLEACHtoestablishdatatransferpathbetweenfirstlevelcluster2headsandthebasestation,whichconsumesmuchenergy.Inordertosaveenergyforwirelesssensornetworks(WSN),anenergy2savingclusteringroutingalgorithm(DD2LEACH)basedonLEACHisproposed.DD2LEACHestablishesdatatransferpathbetweenallcluster2headsandthebasestationbasedonplaneandmulti2hoproutingalgorithms.tionrange.

Keywords:wirelesssensornetworks;clusteringroutingprotocols;planeroutingprotocols;DD2LEACH

IncomparisonwithLEACH,DD2LEACHperformsbetterin

termsofenergydissipationandlifetimeofnetworks,andeliminatestherestrictionofthescaleofthecluster2head’scommunica2

0　引　言

综合了传感器技术、无线通信技术、嵌入式计算技术及微机电系统技术的无线传感器网络(WirelessSensorNetworks)是由部署在监测区域内的大量微型传感器节点,通过无线通信方式形成的一个多跳自组织网络,其目的是协作地感知、采集和处理网络覆盖

[1]

区域中感知对象的信息,并发送给观察者。由于无线传感器网络具有低功耗、自组织等特点,可广泛应用于军事、工业、交通、环境监测、空间探索、医疗护理等领域。

路由协议负责将数据由源节点传送至目的节点,是无线传感器网络的重要核心技术之一。路由协议的性能和整个网络的性能密切相关。依照网络的拓扑结构,路由协议可以分为平面路由协议和分簇路由协议。平面路由协议中,节点间地位平等,通过局部

图1　LEACH协议拓扑结构

操作和反馈信息来生成路由

[3]

[2]

。典型的平面路由协

[4]

[5]

[6]

议有:SPIN、DirectedDiffusion、Rumor、SAR等。分簇路由协议实际上是一种分层结构的路由协议,该协议中网络通常被划分为簇(Cluster),每个簇由一个簇头(Cluster2head)和多个簇内节点组成,这些簇头进一步形成高一级的网络,低一级网络的簇头是高一级网络的簇内成员。簇头负责管理簇内节点,

收稿日期:2009202219

作者简介:张源(19742),男,云南建水人,北京交大微联科技有限公司工程师,本科,研究方向:计算机联锁系统及无线传感器网络。

134　计　算　机　与　现　代　化2009年第12期

并完成簇内节点数据的收集和融合,然后将融合结果

[7]

发送给基站。典型的分簇路由协议有:LEACH、

[8][9][10][11]

TEEN、PEGASIS、CEFL、DAEA等。LEACH协议的拓扑结构如图1所示。

无线传感器网络多应用于布线和电源供给困难的区域(如环境恶劣、受到污染或敌对的区域),且传感器能量有限,因此降低能耗是无线传感器网络协议设计的重要目标。

簇头负责转发全簇的数据,且一般距离基站较远,但是在LEACH协议中最高级簇头与基站采用单跳通信方式,导致能耗较大,因此本文提出了一种新的节能分簇路由算法DD2LEACH,该算法使用平面路由机制建立全体簇头与基站之间的多跳通信路径,有效降低了能量消耗。本文首先详细介绍分簇路由协议和平面路由协议,然后说明无线通信能量模型,最后描述算法的工作机制。

其中,p是簇头占所有节点的百分比,r是目前循环进行的轮数,G是最近1/p轮中还未当选过簇头的节点集合。

(2)数据传输阶段。

簇内节点按照TDMA时隙向簇头发送采集的数据,然后簇头对相关数据进行融合,最后将融合结果传送给基站。

数据传输持续一段时间后,将重新进行下一轮的簇头选取并重新成簇。LEACH协议的缺陷之一是在数据传输阶段,最高级簇头与基站之间采用单跳路由方式,消耗能量较大,同时也使网络规模受限于簇头节点的通信距离。1.2TEEN协议

TEEN(ThresholdSensitiveEnergyEfficientSensorNetworkProtocol)采用类似LEACH的分簇算法,只是

1　分簇路由协议

分簇路由协议主要具有以下几个优点:

(1)簇内节点大部分时间可以关闭通信模块,由簇头负责数据的长距离路由转发。这样既保证了覆盖范围内的数据通信,也在很大程度上节省了网络能量。

(2)簇头融合了簇内节点的数据之后再进行转发,减少了数据通信量,从而节省了网络能量。

(3)分簇拓扑结构便于管理,有利于分布式算法的应用,可以对系统变化作出快速反应,具有较好的可扩展性,适合大规模网络。1.1LEACH协议

LEACH(Low2EnergyAdaptiveClusteringHierar2chy)是由MIT的Chandrakasan等人为WSN设计的低功耗自适应路由协议,其基本思想是周期性地等概率随机选取簇头,其他非簇头节点以就近原则加入相应的簇,形成虚拟簇,以将整个网络的能量负载平均分配到每个传感器节点,从而达到降低网络能量消耗、

[1,12]

依据响应型网络的特点对LEACH的数据传输机制进行了改进。TEEN协议的基本思想是在簇的建立过程中,簇头向簇内节点广播硬阈值(HardThresh2old)和软阈值(SoftThreshold)。当节点首次检测到数据超过硬阈值时,节点将其发送给簇头,同时将该值存入节点内部变量SV中。如果当前监测数据大于硬阈值且与SV的差异大于等于软阈值时,节点才再次进行数据传送。

通过调整两个阈值,可以在传送数据的精度和网络能耗之间取得合理的平衡。但TEEN存在两个缺陷:一是不能周期性地采集数据。二是监测数据一旦满足阈值要求,节点立即传送,容易造成信号干扰,如果采用TDMA,则会引入传输延迟。

2　平面路由协议

平面路由协议的优点是简单、具有较好的健壮性,原则上不存在瓶颈问题,但扩展性较差,且缺乏对资源的优化管理。2.1SPIN协议

SPIN(SensorProtocolsforInformationviaNegotia2tion)协议是一种基于信息协商的自适应路由协议。

延长网络生命周期的目的。LEACH的每轮循环分为

簇的建立阶段和稳定的数据传输阶段。

(1)簇的建立阶段。

每个传感器节点选择[0,1]之间的一个随机数,如果选定的值小于阈值T(n),则该节点向周围节点广播自己成为簇头的消息,网络中的非簇头节点根据接收信号的强度决定加入哪个簇,并通知相关簇头。T(n)的计算公式为:

p,n∈G

p×[rmod(1/p)]T(n)=12

　　　0,　　　　　其它

(1)

其基本思想是:任何两个节点在传输数据前都要进行

协商,节点只传送其它节点没有的数据以减少冗余数据,从而有效减少能量消耗。SPIN协议提出了元数据(Meta2data)的概念,元数据包含了原始数据的一些关键信息,比原始数据要小。SPIN使用三种数据报文,即ADV、REQ和DATA。当某个节点有数据可以共享时,先发送包含元数据的ADV,邻居节点根据其中的元数据判断是否需要发送REQ请求原始数据包DATA。

　2009年第12期张源:一种基于LEACH协议的节能型分簇路由算法135　

2.2DirectedDiffusion协议

定向扩散协议(DirectedDiffusion)是一种以数据

为中心的平面路由协议,其用属性值来标示采集到的数据。DD协议建立路由的过程分为3个阶段:兴趣扩散、梯度建立和路径加强。

(1)兴趣扩散:基站周期性地通过洪泛方式向全网广播一种称为“兴趣”的数据包。

(2)梯度建立:在兴趣扩散过程中,协议逐跳地建立反向的从源节点到基站的梯度场。节点将与兴趣匹配的数据沿着反向路径传送到基站。

(3)路径加强:收到数据后,基站会选择一条最优路径作为加强路径,后续的数据沿着该路径传输。传递路径中的每个节点都会进行数据融合,并将融合结果发送给下一跳节点。定向扩散协议如图2所示。

协议的设计思想。

基于以上分析,本文提出了DD2LEACH算法。因为定向扩散协议和LEACH协议都适用于查询性无线传感器网络,两个协议可以很好地结合,因此DD2LEACH算法依据定向扩散协议的工作机制对LEACH协议进行了改进,有效延长了网络生存时间。该算法主要分为选取簇头、建立簇头与基站之间的传输路径、数据传输三个阶段。4.1成簇算法DD2LEACH算法先采用LEACH协议的工作机制周期性地选取簇头,广播成簇消息,并最终建立簇。4.2数据传输路径建立算法图2　定向扩散协议

3　无线通信能量模型

根据文献[13],在无线通信中传感器节点向距

离d的邻居节点发送kbit数据的能耗为:

n

ETx(k,d)=Eelec3k+εamp3d3k

(2)(3)

传感器节点接收kbit数据的能耗为:

ERx(k)=Eelec3k

其中,Eelec为发射器对1bit信息进行编码调制等处理消耗的能量;εamp为在传送阶段消耗的能量系

n

数;εampd是发送1bit信息时放大器消耗的能量,由通信距离和误码率等共同决定。n与传感器网络的应用环境密切相关,通常在2到4之间,但由于传感器网络中节点通常贴近地面,应用环境中可能有较多的障碍物,接收天线的能力也有限,因此n常常接近4。所以,在无线传感器网络中要减少单跳通信距离,使用多跳短距离无线通信方式。

在每个成簇周期中,DD2LEACH算法分三个阶段建立簇头与基站之间数据传输路径,即“簇头路由”消息扩散阶段、梯度建立阶段和路径加强阶段。

(1)“簇头路由”消息扩散阶段。基站将“簇头路由”消息发送到网络中,但是只有簇头接收该消息后进行转发,而不是采用类似DD协议的全网洪泛。

(2)梯度建立阶段。在“簇头路由”消息的传播过程中,算法逐跳地在每个簇头节点上建立反向的从簇头到基站之间的数据传输路径。然后,簇头沿着该路径向基站发送带有簇头节点ID的“簇头反馈”消息,该消息也只由簇头接收后进行转发,簇内节点不转发该消息。

(3)路径加强阶段。

基站会收到从不同路径传送过来的“簇头反馈”消息,收到这些数据后,基站选择最先收集到所有“簇头反馈”消息的路径作为强化的最优路径(因为该路径的传输时延最短),之后簇头将沿着该路径向基站发送数据。4.3数据传输

4　DD2LEACH算法

如前所述,协议的节能性能对无线传感器网络非常重要,而根据无线通信能量模型,LEACH协议中最高级簇头与基站之间采用单跳通信的方式是较为浪费能量的,而且网络范围也受限于簇头节点的通信半径。因此,成簇后应继续建立所有簇头与基站之间的多跳传输路径。

平面路由协议可以建立无等级节点到基站之间的多跳路径,同样可以用于建立簇头与基站之间的多跳路由,所以,在分簇路由协议中可以借鉴平面路由

簇头与基站之间的数据传输路径建立之后,簇内节点采集数据并发送给各自的簇头,簇头对收集的信息进行融合,并将融合结果沿着之前建立的多跳路径发送给基站。

4.4簇与数据传输路径的维护

DD2LEACH算法采用LEACH协议的工作机制维护簇的结构,采用与定向扩散协议类似的方式维护

簇头与基站之间的数据传输路径。

5　结束语

为了解决LEACH协议中簇头与基站通信之间通信能量消耗较大的问题,通过借鉴平面路由协议的工作机制,本文提出了一种新的节能型分簇路由算法

136　计　算　机　与　现　代　化2009年第12期

DD2LEACH。该算法首先采用LEACH协议的工作机制建立并维护簇,然后采用类似定向扩散协议的方式

crosensornetworks[J].IEEETransactionsonWirelessCommunications(S153621276),2002,1(4):6602670.[8]　ManjeshwarA,AgrawalDP.TEEN:Aroutingprotocolfor

enhancedEefficiencyinwirelesssensornetworks[C]//Proceedingsofthe15thInternationalParallelandDistribu2tedProcessingSymposium.SanFrancisco,USA:IEEECom2puterSociety,2001:200922015.

[9]　LindseyS,RaghavendraCS.PEGASIS:Power2efficient

gatheringinsensorinformationsystems[C]//ProceedingsoftheIEEEAerospaceConference.2002:112521130.[10]GuptaI,RiordanD,SampalliS.Cluster2headelectionusing

fuzzylogicforwirelesssensornetworks[C]//Proceedingsofthe3rdAnnualCommunicationNetworksandServicesResearchConference.Halifax:IEEEComputerSociety,2005:2552260.

[11]Al2KarakiJN,Ul2MustafaR,KamalAE.Dataaggregation

inwirelesssensornetworks:Exactandapproximatealgo2rithms[C]//ProceedingsoftheIEEEWorkshoponHighPerformanceSwitchingandRouting.2004:2412245.[12]Al2KarakiJN,KamalAE.Routingtechniquesinwireless

sensornetworks:Asurvey[J].IEEEWirelessCommunica2tions,2004,11(6):6228.

[13]HeinzelmanWR,ChandrakasanA,BalakrishnanH.Ener2

gy2efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//Proceedingsofthe33rdAnnualHawaiiIn2ternationalConferenceonSystemSciences.Hawaii,USA:IEEEComputerSociety,2000:1210.

建立所有簇头与基站之间的多跳数据传输路径。根

据无线通信能量模型,DD2LEACH算法能够有效节省网络能量,延长网络生命周期,并且使网络规模不再受限于簇头节点的通信距离。

参考文献:

[1]　AkyildizIF,SuW,SankarasubramaniamY,etal.Asurvey

onsensornetworks[J].IEEECommunicationsMagazine,2002,40(8):1022114.[2]　于海斌,曾鹏,王忠锋,等.分布式无线传感器网络通信协议研究[J].通信学报,2004,25(10):1022110.[3]　KulikJ,HeinzelmanWR,BalakrishnanH.Negotiation2basedprotocolsfordisseminatinginformationinwirelesssensornet2works[J].WirelessNetworks,2002,8(223):1692185.[4]　IntanagonwiwatC,GovindanR,EstrinD,etal.Directeddif2

fusionforwirelesssensornetworking[J].IEEE/ACMTransactionsonNetworking,2003,11(1):2216.

[5]　BraginskyD,EstrinD.Rumorroutingalgorithmforsensor

networks[C]//Proceedingsofthe1stWorkshoponSensorNetworksandApplications.2002:22231.[6]　SohrabiK,GaoJ,AilawadhiV,etal.Protocolsforself2or2

ganizationofawirelesssensornetwork[J].IEEEPersonalCommunications,2000,7(5):16227.

[7]　HeinzelmanWR,ChandrakasanAP,BalakrishnanH.An

application2specificprotocolarchitectureforwirelessmi2

(上接第132页)

参考文献:

[1]　邵旻.CAN总线综述[DB/OL].http://bbs.21ic.com/

upfiles/img/20097/2009726102917716.pdf,2002212206.[2]　广州周立功单片机发展有限公司.CAN2BUS规范2.0版

本[DB/OL].http://www.zlgmcu.com,2002204226.[3]　张雄伟,等.DSP芯片原理与应用[M].北京:机械工业

出版社,2005.[4]　姜香菊,任恩恩.CAN总线技术在车站信号系统中的应

用[J].微计算机信息,2008,24(20):76277.[5]　阳宪惠.现场总线技术及其应用[M].北京:清华大学出

版社,1996.[6]　姚晓峰,陈晓侠,等.工业以太网和CAN总线系统的通

信软件设计[J].控制工程,2006,13(3):2682270,273.[7]　StevensWRichard.TCP/IP详解(卷1):协议[M].北京:

机械工业出版社,2000.[8]　张凤登,应启戛.一种可用于现场总线的连接管理方法

及其证明[J].上海理工大学学报,2000,22(4):

2992303.

[9]　TexasInstrumentsInc.TMS320x24xDSPReferenceSet,

Volume1:CPUandPeripherals[S].TexasInstrumentsInc.,2001.

[10]TexasInstrumentsInc.TMS320Lf2407Fixed2pointDigital

SignalProcessorDataSheet[DB/OL].http://www.Ti.com,2001212211.

[11]周霖.DSP控制工程技术应用[M].北京:国防工业出版

社,2005.

[12]TexasInstrumentsInc.TMS320x24xAssemblyLanguage

ToolsUser’sGuide[S].TexasInstrumentsInc.,2001.[13]王学伟,王彦硕.基于以太网的数据采集及监控系统的

数据通信研究[J].北京化工大学学报(自然科学版),2006,33(2):1092111.

[14]姚光开,于永棠,等.微型TCP/IP协议栈的设计与实现

[J].计算机应用,2003,23(9):82284.