一种基于地理位置的无线传感器网络服务质量路由算法

上海交通大学学报

JOURNALOFSHANGHAIJIAOTONGUNIVERSITY

Vol.44No.3󰀁Mar.2010󰀁

󰀁󰀁文章编号:1006󰀁2467(2010)03󰀁0413󰀁05

一种基于地理位置的无线传感器

网络服务质量路由算法

程󰀁真,󰀁李腊元

(武汉理工大学计算机科学与技术学院,武汉430063)

摘󰀁要:基于传感器节点的地理位置信息与网络传输路径的能耗模型分析,提出一种无线传感器网络服务质量(QoS)路由算法.将多跳传输路径中的转发节点序列控制在以源节点与汇聚节点连线的一定区域内,尽量拟合源节点与汇聚节点连线传输,有效控制了传输路径.并对QoS路由算法提出改进,转发节点根据当前实时QoS约束动态地调整传输区域的大小以及优化下一跳选择机制,使传输路径最大程度拟合源节点和汇聚节点之间的连线,达到路径传输能耗最优.仿真实验表明,该QoS路由算法在满足网络QoS约束的同时,节省了网络的能耗,延长了网络生存时间.关键词:地理位置信息;无线传感器网络;服务质量;网络能耗中图分类号:TP393󰀁󰀁󰀁文献标志码:A

AQoSRoutingAlgorithmBasedonGeographicalLocationInformation

forWirelessSensorNetworks

CHENGZhen,󰀁LILa󰀁yuan

(CollegeofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430063,China)Abstract:Basedonsensornode󰀂sgeographicallocationinformationandenergyconsumptionmodelanalysisofnetworktransmissionpath,thispaperproposedaQoSroutingalgorithmforwirelesssensornetworks,whichwillcontroltheforwardnodessequenceofmulti󰀁hoptransmissionpathinthesourcenodeandsinknodeconnectionarea,tofitthesourcenodeandsinknodeconnectiontransmission,andeffectivelycontrolthetransmissionpath.ThepaperalsoproposedtoimprovetheQoSroutingalgorithm,bywhichthefor󰀁wardnodescandynamicallyadjustthesizeoftransmissionpathareabasedonthecurrentreal󰀁timeQoSconstraintsandoptimizethenexthopselectionmechanism,sothattheroutingpathcanmaximizethefit󰀁tingofthestraightlinebetweensourcenodeandsinknodetoachievetheoptimalpathtransmissionenergyconsumption.ThesimulationexperimentsshowthattheQoSroutingalgorithmforwirelesssensornet󰀁workscanachievethenetworkQoSconstraints,whilesavethenetworkenergyconsumptionandprolongthenetworklife.

Keywords:geographicallocationinformation;wirelesssenornetworks;qualityofservice;networkenergyconsumption

收稿日期:2009󰀁05󰀁08

基金项目:国家自然科学基金资助项目(60672137,60773211),教育部高等学校博士基金资助项目(20060497015)作者简介:程󰀁真(1982󰀁),男,安徽安庆人,硕士生,主要研究方向为无线传感器网络。

李腊元(联系人),男,教授,博士生导师。电话(Tel.):027󰀁86534381;E󰀁mail:jwtu@public.wh.hb.cn

414

上󰀁海󰀁交󰀁通󰀁大󰀁学󰀁学󰀁报

1.2󰀁网络模型

第44卷󰀁

󰀁󰀁随着无线传感器网络[1](WirelessSenorNet󰀁works,WSNs)应用的深入,WSNs的服务质量(QualityofService,QoS)越来越受到重视.WSNs中QoS路由协议的主要目标一般有3个: 找到满足QoS需求的路由;!尽量提高网络资源利用率;∀节省能量,提高网络生存时间.因此,设计WSNs的QoS路由应考虑: 业务需求,即保证业务提出的延迟、吞吐率、可靠性等QoS要求[2];!网络能耗,即信息传送所消耗的能量最少,以延长网络生存期.

根据WSNs的QoS路由设计目标,基于一定数量传感器节点能满足网络QoS约束前提

[3]

本文的QoS路由算法是基于地理位置,假设n个传感器节点随机均匀地部署在一个二维a∋b监测区域内,并且该WSNs具有以下性质:传感器节

点通过外部设备(如GPS)或相关定位机制[6]获得自身的位置信息;当一个区域存在满足一定数量传感器节点时,则在该区域内能找到一条或多条传输路径满足网络QoS要求;网络只有一个Sink节点,所有传感器节点是同构的,部署后不再移动.

2󰀁QoS路由算法

,提出一

2.1󰀁MTAQoS路由算法

2.1.1󰀁MTA的建立󰀁由前述能耗模型分析得出,数据传输最优路径是源节点到Sink节点连线的等距离多跳路由,这只有在理想情况下(节点的密度无限大)才会存在这样的传输路径.但根据这样的思想可以建立一个以源节点到Sink节点连线为中轴线、两侧截距为I的矩形传输区域,该区域即为MTA,如图1所示.由图可见,从源节点到Sink节点的中间转发节点将控制在MTA内.

种至少包含满足网络QoS需求节点个数的最小传输区域(MinimumTransmissionArea,MTA)QoS路由算法,其核心思想为:基于路径能耗模型分析,在满足QoS条件约束下,建立以源节点到Sink节点之间的矩形MTA,其中所有的中间转发节点都控制在MTA内,并且在数据转发过程中,中间节点根据实时QoS约束动态地调整MTA的大小以及优化下一跳的选择机制,最大程度地使传输路径拟合源节点到Sink节点连线,以达到节约数据传输能耗的目的.

1󰀁传输路径能耗分析与网络模型

1.1󰀁传输路径能耗下界分析

本文使用WSNs能量消耗模型[4󰀁5]中具有代表性的无线电模型[4].根据该模型,其传感器节点发送kbit数据所消耗的能量为

Esend=kEstatic+k󰀁ampd

󰀂

图1󰀁数据路由的MTAFig.1󰀁MTAofdatarouting

󰀁󰀁根据前述网络模型的假设及文献[3]知,只需要在MTA内找出一组满足QoS约束的转发节点.假

设网络QoS需求rQoS和需要节点的个数nQoS存在某一函数关系(该关系函数不是本文讨论的重点):nQoS=f(rQoS)(4)

另外,监测网络中传感器节点为均匀部署,则节点的密度为

=nab

(5)

(1)

式中:Estatic为发送电路能量;󰀁amp为信号放大器放大倍数;d为信号传输距离;󰀂为由无线信道决定的常量.考虑源节点经过N跳将数据包传送到Sink节点,则在整条路径上传输总能耗为

Epath=kNEstatic+k󰀁amp

i=1N

󰀂

d󰀂i

(2)

Sink节点的位置坐标为(x0,y0),源节点的位置坐标为(xs,ys),则可以计算出满足QoS需求MTA的

截距为

IQoS=

f(rQoS)2 (xs-x0)2+(ys-y0)2(6)

构建一条最优传输的路径,并假设所有节点的位置可以任意放置(这种#理想情况∃实际上等效于假设节点密度无限大).根据式(2)可得传输路径的能耗下界为

Emin=

N%{1,2,&}

minkNEstatic+k󰀁amp

DN

󰀂(3)

由此可以建立MTA,即以源节点到Sink节点连线为中轴线、两侧截距为IQoS的矩形传输区域.由式(6)可知,该区域的大小与网络密度 紧密相关.2.1.2󰀁MTAQoS路由算法详述

(1)网络初始化.网络在部署之后,Sink节点通过洪泛的方式将初始化信息(自身的位置坐标、网络式中:D为源节点到Sink节点的直线距离.显而易见,所有节点应该等距离地出现在源节点与目的节点的连线上.󰀁第3期

程󰀁真,等:一种基于地理位置的无线传感器网络服务质量路由算法󰀁󰀁

态地建立MTA.

415

节点密度等)广播出去.每个节点可以通过这个过程,得到自己的邻居节点列表,由此得知自身到Sink节点的最小跳数和邻居节点的位置等信息.洪泛过程中,节点都倾向于使自己的跳数更少,从而得知自己到Sink节点的最小跳数,因此,若某节点先后收到跳数为p和q的2种信息,则认为自己到Sink节点的跳数为p和q中的小者,即min(p,q).

(2)建立数据传输路径.Sink节点向全网发出查询消息和当前网络的基本状态信息(其中包含QoS需求Qinit,网络当前节点密度 ),当某一节点Sn采集的数据与Sink节点的查询信息相匹配时,它就开始向Sink节点发送探测数据,以建立稳定的传输路径.探测数据发送遵循以下流程:

MTA的计算.源节点Sn根据Sink节点发送的当前网络信息,利用式(6)计算出满足QoS约束的MTA的截距IQoS,然后,将Sink节点与源节点的坐标信息、两侧截距IQoS、QoS约束等控制信息发送到下一节点.

!下一转发节点选择策略.源节点Sn从自己邻居节点中找到距离Sink节点跳数最小的作为下一跳节点,如果待选的下一跳节点多于1个,则计算它们到中间轴线L的距离li(i=1,2,3),选取min(li)为下一转发节点.

∀数据路由.中间转发节点将控制信息和数据包依照!中下一转发节点选择策略发送到下一节点,直到数据包到达Sink节点为止.至此,得到了一条MTA内从源节点Sn到Sink节点的满足当前业务QoS需求最小跳数路由.

(3)网络维护.因为网络的节点一旦死亡就会导致网络密度发生变化,所以当一个网络节点能量低于某个能量阀值时,就必须向Sink节点报告自己是失效节点,以便Sink节点正确计算当前网络密度给源节点.另外,即将失效的节点也向自己的邻居通告自己的状态,邻居节点将该节点从自己的邻居节点列表中删除.

2.2󰀁改进的MTAQoS路由算法

2.2.1󰀁MTAQoS改进分析󰀁在网络QoS约束的条件下,对中间转发节点序列的各个节点要求可能不同,在MTAQoS路由算法中建立的MTA宽度是始终保持不变的.但实际情况中由于前序节点的传输状况,由源节点建立的MTA对当前转发节点存在2种情况: MTA的大小可以继续优化,截距I减小;!由源节点建立的MTA不能满足当前节点对网络QoS约束的下一跳选择,截距I需要增大.因此,中间转发节点应根据实时的QoS约束动另外,由式(3)得出的Emin是等距离地出现在源节点与目的节点的连线上.在MTAQoS路由算法的下一跳节点的选择策略上只是在扇形区域内选择距Sink节点最小跳数的节点,在能量上没有达到最大优化,因此有待改进.

2.2.2󰀁具体改进方法

改进1󰀁每个中间转发节点都根据前序节点的QoS消耗重新建立MTA.假定Sink节点在查询信息中赋予源节点Sn的QoS约束为Qinit,当转发到某一节点Si时,Si计算传输过程中所消耗QoS约束Qconsume,得出对当前节点Si的QoS约束Qi,current=Qinit-Qconsume,然后,Si利用式(6)重新计算MTA的两侧截距:

Ii,QoS=

f(Qi,current)2 (xi-x0)2+(yi-y0)2(7)

因此,在数据整个传输过程中,MTA都在动态地改变,也更加适应实际网络状况.如图2所示,从源节点到节点s3的传输过程中,转发节点都以自己为中心,根据式(7)建立适合当前的MTA.

图2󰀁转发节点动态的建立MTA

Fig.2󰀁ForwardnodedynamictoestablishMTA

󰀁󰀁改进2󰀁优化下一跳节点选择的策略.理论上,能量最优的下一跳节点应该是中轴线上等距离位置的节点,但实际中,这种理想情况只可能偶然出现,所以在下一跳选择的节点应尽量靠近中轴线上等距离位置的虚拟节点.假定当前节点为Si,其下一跳为Si-1,下一跳节点选择即对Si-1的确定.由前面分析可知,Si-1的理想位置是Si和Sink节点连线上等距离且与Si最近的坐标位置.

下面参考式(3)来确定Si到Sink节点最优跳数Ni,opt.为使分析简便,仅考虑衰落系数󰀂=2的情形.

令󰀁󰀁E=kNEstatic+kN󰀁amp

则󰀁󰀁E(2k

(NEstatic))N󰀁amp

Di

N

2

DiNDiN

2

2且仅当NEstatic=N󰀁amp时,E取最小值.此时󰀁ampDiEstatic(8)Ni,opt=416

上󰀁海󰀁交󰀁通󰀁大󰀁学󰀁学󰀁报

第44卷󰀁

其中,Di为Si和Sink节点的欧式距离.至此,Si到Sink节点最优跳数Ni,opt已确定,同时Si-1、Si-2的理想位置S∗i-1和S∗i-2也随之确定.

下一跳Si-1的选择方法如下:

(1)由式(8)计算Ni,opt,随之确定Si-1、Si-2的理想位置S∗i-1和S∗i-2;

(2)节点Si在其邻居节点中选择一个节点作为Si-1,使d(Si,Si-1)+d(Si-1,S∗i-2)最小,如图3所示.

2

2

(2)改进的MTAQoS的Eav要比MTAQoS低.原因在于:改进型协议能根据当前QoS约束动态调整MTA的宽度以及优化下一跳选择策略,使传输路径更加接近轴线L.实验1说明了本文的QoS路由算法在网络节点密度 较大时优势比较明显.

图4󰀁节点密度与平均网络能耗关系

Fig.4󰀁Relationshipbetweennodesdensityandaverage

networkenergyconsumption

图3󰀁改进的MTAQoS中的下一跳选择方法Fig.3󰀁Relay󰀁selectionmechanismofadvancedMTAQoS

󰀁󰀁实验2󰀁考察网络的总体能耗、网络生存期及

数据延时.场景如下:在100m∋100m的监测区域均匀部署200个节点,Sink节点位于(0,0),节点初始能量为2J.图5显示了网络的总能量消耗Et和节点存活数量nc随时间t的变化情况.

󰀁󰀁(3)节点Si将数据传输给Si-1节点.

其中,Si-1要求在MTA内,每一次端到端的传输按上述步骤进行.另外,在执行步骤(2)时,若

d(Si,Si-1)+d(Si-1,S∗i-2)>

2

2

Di

2

Ni,opt

2

则说明直接将数据传给节点S∗i-2(虚拟节点),所用能量更少.

3󰀁仿真实验及分析

本文是基于定向扩散[7]扩展的QoS路由算法,下面在网络能耗和节点存活数量2个方面将MTAQoS和改进的MTAQoS同定向扩散进行对比.实验采用NS2网络仿真工具进行仿真.

实验1󰀁考察本文协议节点密度 与单位平均网络能耗Eav的关系.Eav为单位时间内网络单个节点的平均能耗.场景如下:在100m∋100m的监测区域分别均匀地部署50、100、150、200、250、300个节点,Sink节点位于(0,0),节点初始能量为2J.

由图4可见:

(1)随着网络节点增多,Eav越小.这是因为网络节点的 越大,MTA的宽度就越小,传输路径更加拟合中轴线L.根据能耗模型,传输路径的能量消耗将减少,所以Eav就越小.另外,当节点数为200~300时,Eav趋向缓和. 达到一定规模时,传输路径已经非常接近中轴线L,再增加节点数,效果不是很明显.

(b)存活节点

图5󰀁网络的总能耗和生存节点随仿真时间的变化Fig.5󰀁Thetotalenergyconsumptionandsurvivalnodesof

thenetworkchangeswithsimulationtime

[8]

(a)网络能耗

󰀁󰀁由图5(a)可见,本文的QoS路由算法在网络总󰀁第3期

程󰀁真,等:一种基于地理位置的无线传感器网络服务质量路由算法󰀁󰀁

MTA内节点个数已达不到网络QoS要求.

417

能耗上较定向扩散有了一定的改善.其中,MTAQoS和改进的MTAQoS的区别不是很大,因为在 较大时,MTAQoS建立的MTA宽度已经很小,此时改进型根据当前QoS约束动态调整MTA的幅度不是很大,两者之间的传输路径相近,以致于路径的传输能耗改善不大.图5(b)中节点存活数量也反映了这种情况,两者网络存活的节点数较为近似,比定向扩散有了一定的提高.

󰀁󰀁图6反映了MTAQoS与改进的MTAQoS数据延时!的情况.

4󰀁结󰀁语

WSNs中,由于节点能量的有限性,故传感器网络QoS路由设计要在满足QoS约束的前提下,尽最大可能降低网络能耗.仿真实验表明,本文的QoS路由算法在满足QoS约束条件下,降低了网络能耗,延长了网络生存时间.但该路由算法还存在一些不足,如网络能耗的不均衡导致节点非均匀死亡,引起计算QoS需求的节点数量误差;另外,当节点大量死亡时,建立的MTA非常大或无法建立一个与普通路由协议无异的MTA.这些问题都将是笔者进一步研究的内容.参考文献:

[1]󰀁孙利民,李建中,陈󰀁渝,等.无线传感器网络[M].北

京:清华大学出版社.2005.

[2]󰀁ChenD,VarshneyK.QoSsupportinwirelesssensor

networks:Asurvey[C]//ProcofInternationalCon󰀁ferenceonWirelessNetworks.LasVegas:[s.n.],2004:227󰀁233.

[3]󰀁ZhouJJ,MuCD.AkindofapplicationspecificQoS

controlinwirelesssensornetworks[C]//Procee󰀁dingsofthe2006IEEEInternationalConferenceonInforma󰀁tionAcquisition.Weihai,Shandong,China:[s.n.],2006.

[4]󰀁CarleG,BiersackE.Surveyoferrorrecoverytech󰀁

niquesforIPbasedaudio2visualmulticastapplication[J].IEEENetwork,1997,11(6):24󰀁36.[5]󰀁AbouGhazalehN,

LaniganP,

GobrielS,etal.

Dynamicrate󰀁selectionforextendingthelifetimeofen󰀁ergyconstrainednetworks[C]//Proc23rdInternation󰀁alPerformance,ComputingandCommunicationsCon󰀁ference.Phoenix,Arizona:IEEEPress,2004:553󰀁558.

[6]󰀁李晓维.无限传感器网络技术[M].北京:北京理工

大学出版社,2007.

[7]󰀁PatwariN,AshJ.Locatingthenodes:Cooperative

localizationinwirelesssensornetworks[J].

IEEE

SignalProcessingMagazine,2005,22(4):54󰀁69.[8]󰀁于󰀁斌,孙󰀁斌,温󰀁暖,等.NS2与网络模拟[M].

北京:人民邮电出版社,2007.

图6󰀁MTAQoS和改进的MTAQoS的数据延时表现Fig.6󰀁DatadelayofMTAQoSandadvancedMTAQoS

󰀁󰀁由图可见,两者的延时可以分为3个阶段:(1)在0~150s,两者的数据延时不是很明显,

这一阶段两者几乎都是在20~30ms之间振荡.由图5(b)可见,这一阶段还没有发生节点死亡,网络的密度比较大,两者的传输路径基本相似,故延时比较接近.

(2)在150~250s,网络节点已经有相当数量的节点失效,网络节点密度发生明显变化,这一阶段MTAQoS在数据延时方面要优于改进的MTAQoS.因为MTAQoS是在源节点初始建立的MTA内选择最小跳数的下一转发节点,所以传输路径也是整个初始MTA中的最小跳数路径,而改进型因动态调整MTA的宽度及优化的下一跳选择机制,可能导致选择的下一跳节点不是到Sink节点为最小跳数的点.

(3)在250~300s,数据传输延时加大,可能已经达不到某些任务的延时需求.导致这种情况的原因是,在仿真后期大量的节点已经死亡,建立的󰀁󰀁󰀁