基于恢复域的传感器网络路由保障算法研究

《基于恢复域的传感器网络路由保障算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文章编号：1007-5321（2005）04-0000-00基于恢复域的传感器网络路由保障算法研究摘要:由于无线传感器网络通常采用多跳路由传输数据，且能量受限，极易在传输过程中因为链路失效而导致传输失败。针对以上问题，采用恢复域模型，对传输路径按区域进行恢复。首先，证明了使用恢复域模型并且最小化传输时延是一个NP完全问题；其次，通过整数线性规划(ILP)计算出网络中恢复域大小的最优值并且将整个网络按照最优值进行划分；最后，当网络中节点或链路发生故障时，在恢复域内采用备用路径进行恢复。实验表明，采用的恢复域模型能够有效降低传输时延，同时

2、只消耗较少的能量，达到了传输时延与能量消耗之间的均衡。关键词:无线传感器网络;路由;恢复域;能量;延迟中图分类号:TP393文献标识码:ARecoveryDomain-BasedGuaranteedRoutingAlgorithminWSNsAbstract:WirelessSensorNetworksusuallytransmitdatausingmulti-hoprouting,it'senergyislimitedaswell,thereforethetransmissionisinterruptedeasilyduetothe

3、linkfailure.Inaccordancewiththeabovequestions,thepaperadoptstherecoverydomainmodel,whichdividestransmissionpathintoseveralregionstoberecovered.ThepaperprovesthatusingrecoverydomainmodelwhileminimizingthetransmissiondelayisanNP-completeprobleminthefirstinstance.Thencalcu

4、latetheoptimalvalueoftherecoverydomaininthenetworkwithIntegerLinearProgramming(ILP).Inaddition,thepaperdividethenetworkintoseveralrecoverydomainsbasedonthecalculatedoptimalvalue.Finally,thebackuppathintherecoverydomainwhichtorecoverthefaultynodesorlinksinthenetworkisado

5、pted.Simulationresultsshowthattheemployedrecoverydomainmodelcaneffectivelyreducethetransmissiondelaywhileonlyconsuminglittleenergy,whichmakesagoodbalancebetweenenergyconsumptionandtransmissiondelay.Keywords:WirelessSensorNetworks;routing;recoverydomain;energy;delay在有线网络

6、中，针对某条主路径，可以找到一条固定的备用路径，当主路径发生拥塞时，采用备用路径进行传输。但是在无线传感器网络中，由于拓扑的动态性，导致无法为主路径找到一条固定的备用路径。需要根据网络实时变化，在传输链路或节点失效的情况下，动态的找到一条新的备用路径，对传输失败路径进行路由恢复。收稿日期:2014-07-21基金项目：作者简介:本文采用的恢复域模型能够根据网络当前状态，对备用路径进行定时更新。恢复域的选取是根据在主路径上给定恢复参考节点，两个或多个恢复参考节点之间构成的区域称为恢复域[2]，恢复域能够对其范围内的传输提供保护。如图1所

7、示，对于某条主路径，给定节点1、2、3、4作为4个恢复参考节点，构成3个恢复域，图中实线表示主路径，虚线表示备用路径，当节点2、3之间的主路径发生故障后，在恢复域2内进行恢复，采用备用路径继续进行传输。需要注意的是节点2、3并没有在恢复域中，所以这些节点称为恢复域覆盖盲点。图1给出的恢复域均由两个相邻参考节点构成，称之为标准恢复域。由多个参考节点构成的恢复域称为嵌套恢复域。如图2所示，恢复域1和恢复域2嵌套于恢复域3中。通过恢复域嵌套的方法可以有效解决恢复域覆盖盲点的问题，图2中节点2对于恢复域1和恢复域2来说是覆盖盲点，但是由于恢复

8、域嵌套，可以被恢复域3保护。图1采用恢复域的多跳传输图2嵌套恢复域对于路由恢复问题，选定合适的恢复域大小至关重要。当恢复域范围设定较小时（例如为1），需要对主路径上的每一条链路都找到一条备用路径，这样需要较大的能量消耗，