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...

Full description

Saved in:
Bibliographic Details
Published in:China communications 2016-07, Vol.13 (7), p.16-23
Main Authors: Yanhua Zhang, Sun, Xingming, Baowei Wang
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Computational modeling
ILP
k-barrier coverage
K覆盖
Linear programming
Mathematical model
Mobile communication
Sensors
Wireless sensor networks
区域检测
多传感器
整数线性规划
无线传感器网络
系数矩阵
覆盖算法
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1673-5447
DOI:10.1109/CC.2016.7559071