Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (14): 93-95.DOI: 10.3778/j.issn.1002-8331.2009.14.028

• 网络、通信、安全 • Previous Articles     Next Articles

Heuristic algorithm to identifying lossy links in sensor networks

ZHAO Zuo,CAI Wan-dong   

  1. School of Computer Science,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2008-03-17 Revised:2008-06-10 Online:2009-05-11 Published:2009-05-11
  • Contact: ZHAO Zuo

无线传感器网络启发式失效链路推断算法

赵 佐,蔡皖东   

  1. 西北工业大学 计算机学院,西安 710072
  • 通讯作者: 赵 佐

Abstract: The technology of wireless sensor network has matured and has been built actual applications such as environment monitoring,surveillance etc.The experiences have demonstrated the obvious need for network failure managing tools.Lossy links use in a sensor network affect network performance,and hence need to be detected and repaired.Sensor nodes are restrained by limited resources,so inference technique based on network tomography is introduced by passive end-to-end measurement.Through the problem of lossy links inference is mapped to minimal set-cover problem,the algorithm based on heuristic strategy is proposed.The performance of inference algorithm is evaluated by simulation,and the simulation results indicate feasibility and efficiency of the method.

Key words: lossy link inference, network tomography, set-cover problem, heuristic strategy

摘要: 无线传感器网络的实际应用产生了对网络故障管理的迫切需求。严重报文丢失的失效链路影响无线传感器网络的性能,需加以发现并修复。受有限资源的约束,采用被动端到端测量的方法,利用网络断层扫描技术推断失效链路。通过将失效链路推断问题映射为最小集合覆盖问题,提出了一种基于启发策略的失效链路推断算法。仿真实验结果表明该算法具有可行性和有效性。

关键词: 失效链路推断, 网络断层扫描, 最小集合覆盖问题, 启发式策略