Minimizing the maximum sensor movement for barrier coverage in the plane

Shuangjuan Li, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

48 Citations (Scopus)

Abstract

Border surveillance for intrusion detection is an important application of wireless sensor networks. Given a set of mobile sensors and their initial positions, how to move these sensors to a region border to achieve barrier coverage energy-efficiently is challenging. In this paper, we study the 2-D MinMax barrier coverage problem of moving n sensors in a two-dimensional plane to form a barrier coverage of a specified line segment in the plane while minimizing the maximum sensor movement for the sake of balancing battery power consumption. Previously, this problem was shown to be NP-hard for the general case. It was an open problem whether the problem is polynomial-time solvable for the case when sensors have a fixed number of sensing ranges. We study a special case of great practical significance that the sensors have the same sensing range and present an O(n3 log n) time algorithm. Our algorithm computes a permutation of the left and right endpoints of the moving ranges of all the sensors forming a barrier coverage and minimizes the maximum sensor movement distance by characterizing permutation switches that are critical. To the best of our knowledge, this is the first result for solving the 2-D MinMax barrier coverage problem for the case that all sensors have a uniform sensing range.

Original languageEnglish
Title of host publication2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages244-252
Number of pages9
ISBN (Electronic)9781479983810
DOIs
Publication statusPublished - 21 Aug 2015
Externally publishedYes
Event34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015 - Hong Kong, Hong Kong
Duration: 26 Apr 20151 May 2015

Publication series

NameProceedings - IEEE INFOCOM
Volume26
ISSN (Print)0743-166X

Conference

Conference34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015
Country/TerritoryHong Kong
CityHong Kong
Period26/04/151/05/15

Fingerprint

Dive into the research topics of 'Minimizing the maximum sensor movement for barrier coverage in the plane'. Together they form a unique fingerprint.

Cite this