Efficient algorithm for k barrier coverage based on integer linear programming
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.
China Communications