中文摘要：

研究了节点无移动能力的静态传感器网络中的栅栏覆盖问题．考虑在传感器节点具有有限移动能力时，如何构建如姗栏覆盖的问题：首先定义了1-栅栏覆盖最小移动距离和问题（1-barrier coverage min-sum of moving distance，简称1-BCMS）．在网格划分模型情况下，将1-BCMS问题近似为1-网格栅栏最小移动距离和问题（1-grid barrier rain-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.