Efficient algorithm for k-barrier coverage based on integer linear programming
Efficient algorithm for k-barrier coverage based on integer linear programming
复制标题
DOI：
10.1109/cc.2016.7559071
复制
发表时间：
2016-09
影响因子：
4.1
通讯作者：
Yanhua Zhang;Xingming Sun;Baowei Wang
中科院分区：
文献类型：
--
作者：
Yanhua Zhang;Xingming Sun;Baowei Wang
无线传感器网络的屏障覆盖是检测试图穿越感兴趣区域的入侵者的一个重要问题。然而，在某些应用中，在随机部署之后不能满足屏障覆盖。在本文中，我们研究如何移动的传感器可以有效地重新定位，以实现k-障碍覆盖。特别是，两个问题进行了研究：最小数量的移动的传感器和形成的k-障碍覆盖的最小能量成本的传感器的重新定位。将这两个问题转化为0-1整数线性规划问题。由于积分性和复杂的约束条件，该公式在计算上是困难的。因此，我们放松的完整性和复杂的约束的制定和构造一个特殊的模型称为RELAX-RSMN与一个完全么模约束系数矩阵，以解决放松0-1 ILP快速通过线性规划。理论分析和仿真验证了该方法的有效性。
Barrier coverage of wireless sensor networks is an important issue in the detection of intruders who are attempting to cross a region of interest. However, in certain applications, barrier coverage cannot be satisfied after random deployment. In this paper, we study how mobile sensors can be efficiently relocated to achieve k-barrier coverage. In particular, two problems are studied: relocation of sensors with minimum number of mobile sensors and formation of k-barrier coverage with minimum energy cost. These two problems were formulated as 0-1 integer linear programming (ILP). The formulation is computationally intractable because of integrality and complicated constraints. Therefore, we relax the integrality and complicated constraints of the formulation and construct a special model known as RELAX-RSMN with a totally unimodular constraint coefficient matrix to solve the relaxed 0-1 ILP rapidly through linear programming. Theoretical analysis and simulation were performed to verify the effectiveness of our approach.