###
Journal of Software:2011.22(9):2089-2103

移动无线传感器网络k-栅栏覆盖构建算法
班冬松,温俊,蒋杰,窦文华
(国防科学技术大学 计算机学院,湖南 长沙 410073;解放军理工大学 总参第63 研究所,江苏 南京 210007)
Constructing k-Barrier Coverage in Mobile Wireless Sensor Networks
BAN Dong-Song,WEN Jun,JIANG Jie,DOU Wen-Hua
(College of Computer, National University of Defense Technology, Changsha 410073, China;The 63rd Research Institute of General Staff, PLA University of Science and Technology, Nanjing 210007, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4199   Download 3732
Received:October 14, 2009    Revised:January 20, 2010
> 中文摘要: 研究了节点无移动能力的静态传感器网络中的栅栏覆盖问题.考虑在传感器节点具有有限移动能力时,如何构建k-栅栏覆盖的问题:首先定义了1-栅栏覆盖最小移动距离和问题(1-barrier coverage min-sum of movingdistance,简称1-BCMS).在网格划分模型情况下,将1-BCMS 问题近似为1-网格栅栏最小移动距离和问题(1-gridbarrier min-sum of moving distance,简称1-GBMS).给出了1-GBMS 问题的整数线性规划描述,
Abstract:This paper focuses on the energy efficient construction of a k-barrier coverage in mobile sensor networks. First, this paper formulates 1-BCMS (1-barrier coverage min-sum of moving distance) problem for constructing 1-barrier coverage energy efficiently, reduces the 1-BCMS problem to 1-GBMS (1-grid barrier min-sum of moving distance) problem based on grid model, and present the reduced problem’s Linear Programming Model and prove it to be NP-hard. Secondly, this paper presents a CBGB (constructing baseline grid barrier) algorithm to construct 1-barrier coverage energy efficiently. CBGB is an approximation algorithm for 1-GBMS problem and the solution of CBGB is close to the optimal solution. Finally, a Divide-and-Conquer algorithm is proposed to construct k-barrier coverage. This algorithm significantly reduces communication overhead and computation cost compared to other algorithms. Simulation demonstrates the effectiveness of the proposed algorithm in constructing k-barrier coverage.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60603061, 60603064, 60903223) 国家自然科学基金(60603061, 60603064, 60903223)
Foundation items:
Reference text:

班冬松,温俊,蒋杰,窦文华.移动无线传感器网络k-栅栏覆盖构建算法.软件学报,2011,22(9):2089-2103

BAN Dong-Song,WEN Jun,JIANG Jie,DOU Wen-Hua.Constructing k-Barrier Coverage in Mobile Wireless Sensor Networks.Journal of Software,2011,22(9):2089-2103