Efficient Algorithm for K-Barrier Coverage Based on Integer Linear Programming  

作　　者：Yanhua Zhang Xingming Sun Baowei Wang 

机构地区：[1]Nanjing University of Information Science&Technology,Nanjing,China [2]Jiangsu Lightning Protection Center,Nanjing,China

出　　处：《China Communications》2016年第7期16-23,共8页中国通信（英文版）

基　　金：supported by the NSFC(U1536206,61232016,U1405254,61373133,61502242,71401176);BK20150925;the PAPD fund

摘　　要：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.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.

关 键 词：k-barrier coverage linear programming wireless sensor networks 

分 类 号：TN929.5[电子电信—通信与信息系统] TP212.9[电子电信—信息与通信工程] O221.4[自动化与计算机技术—检测技术与自动化装置]