计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (11): 114-119.DOI: 10.3778/j.issn.1002-8331.1512-0368

• 网络、通信与安全 • 上一篇    下一篇

基于重叠感知比的强栅栏覆盖构建算法

肖玉杰,降爱莲,冯秀芳   

  1. 太原理工大学 计算机科学与技术学院,山西 晋中 030619
  • 出版日期:2017-06-01 发布日期:2017-06-13

Strong barrier coverage construction algorithm based on overlap-sense ratio

XIAO Yujie, JIANG Ailian, FENG Xiufang   

  1. College of Computer Science and Technology, Taiyuan University of Technology, Jinzhong, Shanxi 030619, China
  • Online:2017-06-01 Published:2017-06-13

摘要: 研究了有向传感器网络中强栅栏覆盖问题。分析如何高效地利用可移动传感器填充栅栏间隙并与固定传感器形成强栅栏。引入重叠感知比OSR(Overlap-Sense Ratio)概念,基于OSR对随机部署后形成的强连通簇内节点进行调节。采用有向栅栏图DBG(Directional Barrier Graph)对栅栏覆盖问题建模,将可移动传感器填充栅栏间隙问题转化为二部图赋权匹配问题。提出基于重叠感知比的强栅栏覆盖构建OSR-SBC(Strong Barrier Construction algorithm based on OSR)算法。仿真实验验证了OSR-SBC算法的高效性。

关键词: 有向传感器网络, 强栅栏覆盖, 重叠感知比, 可移动传感器, 有向栅栏图

Abstract: The problem of strong barrier coverage in directional sensor networks is studied. How to efficiently use mobile sensors to fill in gaps and form a barrier with stationary sensors is analyzed. Firstly, the concept of Overlap-Sense Ratio(OSR) is introduced. The sensors in strongly connected clusters after random deployment are adjusted based on OSR. Secondly, the notion of Directional Barrier Graph(DBG) is introduced to model the barrier coverage formation problem. The matter of using mobile sensors to fill in barrier gaps is transformed to the matching problem of weighted bipartite graph. Finally, the OSR-SBC(Strong Barrier Construction algorithm based on OSR) algorithm is proposed. Simulation demonstrates the effectiveness of the proposed algorithm.

Key words: directional sensor networks, strong barrier coverage, overlap-sense ratio, mobile sensors, directional barrier graph