移动无线传感器网络k-栅栏覆盖构建算法  

Constructing k-Barrier Coverage in Mobile Wireless Sensor Networks

作　　者：班冬松[1] 温俊[2] 蒋杰[1] 窦文华[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]解放军理工大学总参第63研究所,江苏南京210007

出　　处：《软件学报》2011年第9期2089-2103,共15页Journal of Software

基　　金：国家自然科学基金(60603061;60603064;60903223)

摘　　要：研究了节点无移动能力的静态传感器网络中的栅栏覆盖问题.考虑在传感器节点具有有限移动能力时,如何构建k-栅栏覆盖的问题:首先定义了1-栅栏覆盖最小移动距离和问题(1-barrier coverage min-sum of moving distance,简称1-BCMS).在网格划分模型情况下,将1-BCMS问题近似为1-网格栅栏最小移动距离和问题(1-grid barrier min-sum of moving distance,简称1-GBMS).给出了1-GBMS问题的整数线性规划描述,证明了其是NP-hard的;然后提出了1-GBMS问题的近似算法——CBGB(constructing baseline grid barrier)算法,能量高效地构建1-栅栏覆盖.仿真实验结果表明,CBGB算法的求解结果与最优解接近.最后,提出了一种基于分治策略的k-栅栏覆盖构建算法.该算法极大地降低了通信和计算开销.仿真实验验证了该算法的有效性和可扩展性.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 rain-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.

关 键 词：移动无线传感器网络 栅栏覆盖 重部署 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]