低能耗无线传感器网络路由算法

传感技术学报

CHINESEJOURNALOFSENSORSANDACTUATORS

Vol.20　No.5May.2007

LowEnergyRouterAlgorithminWirelessSensorNetworks

YINGBi2di,CHENHui2fang

3

,ZHAOWen2dao,QIUPei2liang

(Dept.ofInformationScienceandElectronicEngineering,ZhejiangUniv.,Hangzhou310027,China)

Abstract:Duetotheconstrainedenergyofnodesinwirelesssensornetworks,howtoreduceenergycon2sumptionofnodesbecomestheimportanttargetofroutingalgorithms.AnEnergy2basedTwo2TierDataDisseminationModel(E2TTDD)wasproposed.Thisalgorithmadoptedthediagonalstructures,adoptedlocal2electiontoquerythedisseminationnodeintherangeoftwoparallelsthatwereinthecenterofalineconnectingsourcenodetothedisseminationnodenearestthesinknode.Finally,theperformancesoftheE2TTDDalgorithmweresimulatedinMatlab.TheresultsshowthatE2TTDDalgorithmhaslowerenergyconsumptionsandlongerlifetimethantheseoftheoriginalTTDD.Otherwise,thescalabilityoftheE2TTDDalgorithmisgood.

Keywords:wirelesssensornetwork;router;twotier;energyconsumption;sinknodeEEACC:6150P

低能耗无线传感器网络路由算法应必娣,陈惠芳3,赵问道,仇佩亮

(浙江大学信息学院信电系,杭州310027)

摘　要:由于传感器网络中的节点能量受限,因此如何减少节点的能量开销成为路由协议的研究目标.文中提出了一种低能

耗的双层数据分发(AnEnergy2basedTwoTierDataDisseminationModel,E2TTDD)算法.该算法采用斜格组建单元,把源节点和汇聚节点附近的转发节点连接成一条直线,然后在以这条直线为中心以一定间隔的两条平行线之间搜索转发节点,从而使查询路径的能量开销降低.最后用Matlab进行性能仿真.结果表明,E2TTDD算法与原有TTDD算法相比,能量开销降低了3倍,同时延长了网络生存周期.

关键词:无线传感器网络;路由;双层;功耗;汇聚节点中图分类号:TP393　　文献标识码:A　　文章编号:100421699(2007)0521109205　　无线传感器网络是由大量集成了传感、数据收集、处理和无线通信能力的小体积、低成本的传感器节点构成的自组织网络[122].在无线传感器网络中,由于节点的能量受限,因此延长整个网络的生存周期成为传感器网络协议设计的重要目标.

在大规模的无线传感器网络中,汇聚节点的位置信息不停的改变,以便于网络节点及时更新数据发送的方向.但是,频繁的更新消息会增大网络负担,消耗过多能量,并且会造成通信冲突.因此,如何解决汇聚节点的移动性问题的路由协议研究已成为一个研究热点,许多学者提出了多种无线传感器网络的路由算法[425,8210].如KimH.S.等人[3]提出了基

收稿日期:2006207210　　修改日期:2006210210

于树状通信结构的路由机制,该算法从汇聚节点移动性入手,但由于移动节点只能访问树中的特殊节点,扩展性较差.WangZ.M.等人[6]从能量受限的汇聚节点出发,解决了在不同时间停留位置和不同的运动位置的节点间的汇接问题.YeF.等人[7]针对汇聚节点移动性提出一种双层数据分发模型,该模型中源节点不是被动等待汇聚节点的查询消息,而是主动建立单元,搜索汇聚节点的查询消息.由于该算法在查询信息时沿单元边长走,从而导致路径长度的增加,致使节点的能量开销增大.因此,本文提出了一种基于能量的双层数据分发算法.该算法采用斜格组建单元,把源节点和汇聚节点附近的转

1110传　感　技　术　学　报2007年

发节点连接成一条直线;然后在以这条直线为中心以一定间隔的两条平行线之间,根据本地竞选机制

选举转发节点,只有转发节点保持活动,其他节点进入睡眠状态,从而使查询路径的能量开销降低.仿真结果分析与比较表明,采用E2TTDD算法提高了网络生存周期,降低了功耗,并且该算法具有较好的可扩展性.

所有单元的顶点坐标,其中距离顶点最近的网络节点称之为转发节点.

TTDD算法的工作原理如下:①汇聚节点需要数据信息时,通过洪泛方式查询离本地单元最近的转发节点.当转发节点收到查询命令时,按照单元边长搜索方法对其他单元的转发节点进行查询,直到查询源节点.②源节点建立方格结构,等待相邻转发节点的查询消息.当收到相邻转发节点的查询消息时,沿着查询的来时路径反向发送数据信息.当数据到达汇聚节点所在单元的转发节点后,把数据从转发节点传送到汇聚节点.2.2　E2TTDD算法

2.2.1　E2TTDD算法的结构组建原理

1　传感器网络拓扑结构和模型假设

在无线传感器网络中,汇聚节点的位置信息需要不停的改变,以便于网络节点及时更新数据发送的方向.图1给出了E2TTDD算法的传感器网络拓扑图.从图1中可知,汇聚节点发送查询消息经转发节点传给源节点,然后源节点把数据消息沿着来时路径反方向经转发节点传给汇聚节点.

图2给出了E2TTDD算法的结构组建原理图.从图2中可知,源节点和汇聚节点分别位于不同的方位,把源节点和汇聚节点附近的转发节点连接一条直线,然后在以这条直线为中心的以一定间隔的两条平行线之间根据本地竞选机制选举转发节点.其中,β为两条平行线的虚拟间距,α为一个单元的边长,0<βΦ2α.2.2.2　转发节点的选举原理

(1)节点组成

图1　E2TTDD算法的传感器网络拓扑图E2TTDD算法的模型假设如下:

①具有相同属性的传感器节点分布在一个区域内,传感器节点之间进行短距离无线通信,远距离节点通过中间节点采用多跳进行转发数据;②每个传感器节点知道自己的位置信息,但是汇聚节点可能不知道自己的位置信息;

③一旦有事件出现,周围的传感器节点会收集并处理信息,然后由其中的一个作为源节点发送报告;

④汇聚节点通过查询网络收集数据.在区域中,汇聚节点的位置和数目是可变的.

在无线传感器网络中,以源节点和汇聚节点附近的转发节点连接的一条直线为中心,以β间距的两条平行线范围内的所有节点可以分成三种类型.

图2　E2TTDD算法的结构组建原理图

2　无线传感器网络的改进路由算法

2.1　原有的TTDD算法

YeF.等人[7]提出的TTDD算法中,网络节点

①普通节点:发现查询消息分组,可以参与本

地竞选转发节点.一旦竞选结束,该节点没有竞选为leader节点,就处于休眠状态,等待下一个时段.②leader节点:转发节点的候选者.③转发节点:距离

分布在一个二维平面区域内,根据源节点位置,把平

α的单元.假设一个源节点位置Ls面分割成一个α×

=(x,y),则单元的其它顶点坐标为Lp=(xu,yv),

本单元顶点最近的leader节点.一旦明确本身是转

发节点,该节点处于活动状态,等待其他查询消息或者数据传输.

(2)节点结构在无线传感器网络中,节点所传递和处理的分组包含数据分组和控制分组两种类型:

①数据分组从上层接收到的数据转发给下层

α,yv=y+v×α,u,v=0,±1,其中:{xu=x+u×±2,…}

根据源节点位置Ls和单元边长α,计算出其它

第5期应必娣,陈惠芳等:低能耗无线传感器网络路由算法

2.2.3　E2TTDD算法的工作原理

1111

节点.②控制分组包含查询消息分组、投票分组以及位置信息分组.其中查询消息分组发送公告声明要传送数据分组;投票分组包含参加本地竞选转发节点的剩余能量和标识符号;位置信息分组包含节点的位置信息.

(3)竞选机制

节点周期性的进入睡眠和工作状态,从睡眠状态唤醒之后与本地通信范围内其他节点交换信息,根据本地竞选机制来判断是否需要成为leader节点.每个节点可以处于发现、活动及睡眠三种状态.

竞选机制过程如下:以源节点和汇聚节点附近的转发节点连接的一条直线为中心以β间距的两条平行线范围内,节点i在某一时间内发现查询消息,首先查看节点i附近是否有转发节点.如果没有,节点i广播当前的剩余能量给本地邻居节点.邻居节点将本身的剩余能量与节点i的剩余能量相比,如果邻居节点的剩余能量均小于节点i的剩余能量,则节点i当选为leader节点,否则节点i处于睡眠状态.

发送节点i包括以下4个步骤.

①节点i发现查询消息时,查看节点i附近是否有转发节点,如果没有转发节点,则节点i参与本地竞选leader节点;②节点i发送当前的剩余能量给本地邻居节点;③节点i等待邻居节点的回复.如果邻居节点的剩余能量小于节点i的剩余能量,则节点i被选为leader节点.否则,节点i处于休眠状态;④节点i把当前的剩余能量和选为leader节点事件告诉本地邻居节点.

接收邻居节点j包括以下3个步骤.

①接收邻居节点j核查它本身剩余能量与节点i的剩余能量大小;②如果接收邻居节点j的剩余能量大于节点i的剩余能量,接收邻居节点j被选为leader节点,接收邻居节点j处于活动状态,等待其他分组到来;③接收邻居节点j把本身的剩余能量和当选为leader节点事件告诉邻居节点.

(4)转发节点产生在一个本地单元格内,由本地竞选机制所产生的leader节点中根据距离最短来搜索转发节点.

假设由本地竞选机制所产生的leader节点Lf

位置坐标为(xi,yj),i,j=0,±1,±2,…,本地单元格内的顶点坐标为Lp=(xu,yv),则节点Lf和顶点

Lp的距离dfp=

allf,p

源节点根据本身所在位置,把平面分割成一个

α×α的单元,等待汇聚节点的查询消息分组.

当汇聚节点需要数据时,则在本地单元内洪泛一个查询消息分组,这个消息分组到达最近转发节点.然后转发节点在源节点和汇聚节点连接而成的这条直线为中心以β为间距两条平行线之间根据本地竞选机制选举转发节点.当转发节点传到数据来源的转发节点时,这个节点在本地单元内洪泛查询消息分组,直至查询消息分组到达源节点.

由于采用单元格式,汇聚节点的查询消息可以通过两层查询到达源节点,其中,较低一层是单元内的查询,较高一层是转发节点的查询,因此E2TTDD算法具有良好的可扩展性.2.2.4　E2TTDD算法性能分析

假设面积为a的平面区域内均匀分布了n个传感器节点,区域的每个边上分布了n个传感器节点.假设网络有k个汇聚节点,在T时间内接收了d个数据包,数据包大小为l.

令Ctrans是源节点到汇聚节点传输数据包的能量开销,则假设每个汇聚节点位置更新为m次,连续两次更新期间接收到了为:

dCtrans=km×(c×n)×m

(2)

d个数据包,因此Ctransm

其中,c为权重系数,且c∈[0,2].

令Cquery是源节点到汇聚节点传输查询消息的能量开销,则源节点到k个汇聚节点的Cquery定义如下:

Cquery=km×βα-n×(2a

2

β

)×l2+(c×n)×l

(3)

其中,

2ββα-)×ln×(22a

是局部洪泛的能量开销,

(c×n)×l是查询路径节点的能量开销.

令Crenew是更新网络任务的能量开销,则

Crenew=n×l

(4)

(xi-xu)2+(yj-yv)2.因此最

α的单元,每个单元中源节点把区域分割成α×

2αn有个节点,和4个源节点.令Csetup建立方格的单

a

佳转发节点Lb到顶点Lp的距离为

dbp=min{dfp}

f,p=0

元结构的能量开销,则

(1)

Csetup=

4α

an×l(5)

1112传　感　技　术　学　报2007年

因此,E2TTDD算法的能量开销CE2TTDD如下:

CE2TTDD=Ctrans+Cquery+Crenew+Csetup=

km×2

ββα-)×ln×(220.05168J,验证了E2TTDD算法的路径能量开销

比TTDD算法的路径能量开销少.

a

+kmc×n×

(6)

　　　　(1+

d4an)+n×l+×l

αm

而对于TTDD算法中,由于查询是沿单元边长,因

此能量开销CTTDD如下[7]:

2αn×CTTDD=km××l+kc(ml+d)2n+n×l

a

+

4α

an图4　虚拟间距β对网络性能的影响曲线图

×l(7)

比较式(6)和式(7)可知,在大规模的无线传感器网络中,随着网络规模n、汇聚节点数目k和汇聚节点的位置更新次数m的增大,E2TTDD的通信开销要小于TTDD的通信开销.

3　仿真结果及性能分析

文中仿真过程出现的参数、网络拓扑如下:①在2000×2000的区域内随机分布了200个传感器节点;②传感器节点的初始能量均为5J;③Eelec=50nJ/bit,表示接收机电路和发射机电路每ε处理1bit数据的能耗;④m-2表amp=100pJ/bit・示发射放大器向单位面积发射1bit数据的能耗.

图3表示单元边长α对网络性能的影响曲线图.从图3可知,当α=140时,TTDD算法的能量开销最小,这是由于α决定了整个网络的单元数目.

图5　TTDD和E2TTDD的路径搜索图

图6表示TTDD算法和E2TTDD算法的网络生存周期图.其中,x轴表示节点搜索路径的遍历次数,y轴表示经过数次搜索路径后所剩余的节点数目.由图6可知,在TTDD算法和E2TTDD算法中,剩余节点数目随着遍历次数的增加而减少,到一定遍历次数,剩余节点数目迅速下降.这主要由于到一定遍历次数,节点出现死亡,节点之间通信需要经过多跳通信,从而能量消耗快速增大,导致剩余节点数目急剧下降.在TTDD算法中,在遍历次数60左右开始出现节点的死亡,在遍历次数180左右,几乎所有节点都死亡.E2TTDD算法在遍历次数410左右开始出现节点的死亡,在遍历次数850左右,几乎所有节点都死亡.这是由于E2TTDD算法在路径搜索中,采用斜格组建单元,通过本地竞选机制搜索转发节点,从而提高了网络的生存周期.

图3　单元边长对网络性能的影响曲线图

图4表示虚拟间距β对网络性能的影响曲线图.从图4可知,当β=130时,E2TTDD算法的能量开销最小,这是由于β决定了搜索网络数据转发节点的步长,因此对网络性能影响很大.

对于相同的源节点和汇聚节点,TTDD和E2TTDD两种算法搜索的路径不同,因此所用的功耗也不相同.图5给出了TTDD和E2TTDD的路径搜索图.从图5可知,TTDD算法搜索路径的功耗为0.1631J,而E2TTDD算法进行路径搜索的功耗为

图6　TTDD和E2TTDD的网络生存周期

第5期应必娣,陈惠芳等:低能耗无线传感器网络路由算法

2003,LosAngeles,CA,pp.1932204,Nov.,2003.

1113

4　结论

目前,传感器网络的路由协议是一个研究热点.本文针对原有TTDD算法中搜索路径问题的不足提出改进的TTDD算法.该算法采用斜格组建单元,把源节点和汇聚节点附近的转发节点连接一条直线,然后以这条直线为中心以β间距的两条平行线范围内搜索转发节点.只有转发节点保持活动状态,其他节点处于休眠状态,从而使查询路径的能量开销得以降低.最后从传输路径、虚拟间距、网络生存周期等方面进行仿真.结果表明,E2TTDD算法在能量消耗方面降低了3倍,网络生存周期延长了6.7倍具,同时,该算法具有良好的可扩展性.

[4]　YuY,GovindanRandEstrinD.GeographicalandEnergyA2

wareRouting:ARecursiveDataDisseminationProtocolforWirelessSensorNetworks[R].UCLAComputerScienceDe2partmentTechnicalReportUCLA/CSD2TR20120023,May2001.

[5]　IntanagonwiwatC,GovindanRandEstrinD.DirectedDiffu2

sionforWirelessSensorNetworking[J].IEEE/ACMTrans2actionsonNetworking,Feb.2003,11(1):2216.

[6]　WangZM,BasagniSandMelachrinoudisE.ExploitingSink

MobilityforMaximizingSensorNetworksLifetime[C]//Pro2ceedingsofthe38thAnnualHawaiiInternationalConferenceonSystemSciences,pp.287a2287a,Jan.,2005.

[7]　YeF,LuoHandChengJ.ATwo2TierDataDissemination

ModelforLargeScaleWirelessSensorNetworks[C]//Pro2ceedingsofthe8thACMAnnualInternationalConferenceonMobileComputingandNetworking,2002,Atlanta,GA,pp.1482159,Sept.,2002.

[8]　YingBD,ChenHFandZhaoWD.ADiagonal2BasedTTDD

inWirelessSensorNetworks[C].Proceedingsofthe6thWorldCongressonIntelligentControlandAutomation,2006,Dalian,vol.1,pp.2572260.Jun.,2006.

[9]　覃伯平、周贤伟、杨军等.无线传感器网络的安全路由技术研

参考文献:

[1]　VermuriATandPolycarpouMM.RobustNonlinearFault

DiagnosisinInputSystem[J].InternationalJournalofCon2trol,1997,68(2):3432360.

[2]　YuDandShieldsND.ABilinearFaultDetectionObserver

[J].Automatic,1996,32(11):157921602.

[3]　KimHS,AbdelzaherTFandKwonWH.MinimumEnergyAsynchronousDisseminationtoMobileSinksinWirelessSen2sorNetworks[C]//Proceedingsofthe1stInternationalCon2ferenceonEmbeddedNetworkedSensorSystems,SenSys

究[J].传感技术学报,2006,19(1):16219.

[10]　吴臻和、金心宇.无线传感器网络的LEACH算法的改进

[J].传感技术学报,2006,19(1):34236.

应必娣(19812),女,浙江大学信电系,博士生,研究方向为计算机网络QoS,无线传感网络路由,拓扑理论和信息安全,biddy@zj.com.

陈惠芳(19712),女,浙江大学信息与电子工程学系,副教授,主要研究计算机网络、覆盖网络、无线传感器网络等,目前在日本攻读博士后,chenhf@zju.

edu.cn.