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

文章编号：1007-5321（2005）04-0000-00 基于恢复域的传感器网络路由保障算法研究 摘要: 由于无线传感器网络通常采用多跳路由传输数据，且能量受限，极易在传输过程中因为链路失效而导致传输失败。针对以上问题，采用恢复域模型，对传输路径按区域进行恢复。首先，证明了使用恢复域模型并且最小化传输时延是一个NP完全问题；其次，通过整数线性规划(ILP)计算出网络中恢复域大小的最优值并且将整个网络按照最优值进行划分；最后，当网络中节点或链路发生故障时，在恢复域内采用备用路径进行恢复。实验表明，采用的恢复域模型能够有效降低传输时延，同时只消耗较少的能量，达到了传输时延与能量消耗之间的均衡。 关 键 词: 无线传感器网络; 路由; 恢复域; 能量; 延迟 中图分类号: TP393 文献标识码: A Recovery Domain-Based Guaranteed Routing Algorithm in WSNs Abstract: Wireless Sensor Networks usually transmit data using multi-hop routing, its energy is limited as well, therefore the transmission is interrupted easily due to the link failure. In accordance with the above questions, the paper adopts the recovery domain model, which divides transmission path into several regions to be recovered. The paper proves that using recovery domain model while minimizing the transmission delay is an NP-complete problem in the first instance. Then calculate the optimal value of the recovery domain in the network with Integer Linear Programming (ILP). In addition, the paper divide the network into several recovery domains based on the calculated optimal value. Finally, the backup path in the recovery domain which to recover the faulty nodes or links in the network is adopted. Simulation results show that the employed recovery domain model can effectively reduce the transmission delay while only consuming little energy, which makes a good balance between energy consumption and transmission delay. Key words: Wireless Sensor Networks; routing; recovery domain; energy; delay 在有线网络中，针对某条主路径，可以找到一条固定的备用路径，当主路径发生拥塞时，采用备用路径进行传输。但是在无线传感器网络中，由于拓扑的动态性，导致无法为主路径找到一条固定的备用路径。需要根据网络实时变化，在传输链路或节点失效的情况下，动态的找到一条新的备用路径，对传输失败路径进行路由恢复。 收稿日期: 2014-07-21基金项目： 作者简介: 本文采用的恢复域模型能够根据网络当前状态，对备用路径进行定时更新。恢复域的选取是根据在主路径上给定恢复参考节点，两个或多个恢复参考节点之间构成的区域称为恢复域[2]，恢复域能够对其范围内的传输提供保护。如图1所示，对于某条主路径，给定节点1、2、3、4作为4 收稿日期: 2014-07-21 基金项目： 作者简介: 图1给出的恢复域均由两个相邻参考节点构成，称之为标准恢复域。由多个参考节点构成的恢复域称为嵌套恢复域。如图2所示，恢复域1和恢复域2嵌套于恢复域3中。通过恢复域嵌套的方法可以有效解决恢复域覆盖盲点的问题，图2中节点2对于恢复域1和恢复域2来说是覆盖盲点