传感器网络中无需地理信息的空洞填补算法  

A Self-Healing Algorithm without Location Information in Sensor Networks

作　　者：苏瀚[1] 汪芸[1] 

机构地区：[1]东南大学计算机科学与工程学院计算机网络与信息集成教育部重点实验室,南京210096

出　　处：《计算机学报》2009年第10期1957-1970,共14页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2009CB320705);航空科学基金(20080769004)资助

摘　　要：传感器网络由大量的节点组成,节点大多使用电池供电.如果某块区域内传感器节点由于能量耗尽、物理损毁而导致空洞的产生,对于空洞区域,传感器网络将无法进行监测.当传感器网络出现空洞时,需要移动传感器节点填补覆盖空洞,实现网络自愈合.现有的空洞填补算法都依赖于精确地理位置信息,且迭代次数较多,收敛时间较长.文中提出了传感器网络中空洞填补的两个准则,即(1)填补节点的引入至少消除一段空洞边缘弧;(2)填补节点的引入不能造成空洞的分裂.文章证明了填补准则的正确性,并基于填补准则提出了在没有地理位置信息条件下传感器网络的自愈合算法CHH.算法通过节点移动辅助定位的方法,实现了相邻节点间距离和方位的计算以及空洞边缘节点间距离的计算.空洞边缘节点根据填补准则,判断是否引入填补节点.算法CHH将空洞填补工作分布到空洞边缘节点上分别执行,并最终实现分布式的空洞填补.仿真实验结果表明,相比现有算法,CHH不仅消除了地理位置信息的假设,并且提升了空洞填补性能和算法收敛速度.Wireless sensor networks （WSN） are composed of many inexpensive sensor nodes which are equipped with limited battery energy. If no sensor node is available in an area due to used up energy or WSN destruction, for example, the area forms a coverage hole where no moni- toring is applied. Mobile sensors are needed in order to heal such coverage holes. Most of the healing algorithms suppose sensors have location informations and it takes many iteration times for these algorithms to execute. This paper discusses the self-healing problem and proposes two principles for self-healing in WSNs. （1） A healing sensor should eliminate at least one Hole Boundary arc during the healing process. （2） The coverage hole should not be partitioned. The authors prove the correctness of the principles. Based on the principles, a novel self-healing algo- rithm CHH without location information is given. The algorithm calculates the distances and di- rections between neighbor sensors by using the method of sensor＇s moving. It also calculates the distances between hole boundary sensors. Hole boundary sensors then determine the positions of healing sensors according to the principles. The algorithm CHH distributes the healing work to different Hole Boundary Sensors and finally eliminates the Coverage Hole in WSN. Compared with some current state-of-the-art algorithms, CHH outperforms in coverage and convergence rate without location information.

关 键 词：传感器网络 覆盖空洞 分布式算法 网络自愈合 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]