Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Minimizing the maximum sensor movement for barrier coverage in the plane
Author: Li, S.
Shen, H.
Citation: IEEE Infocom, 2015, vol.26, pp.244-252
Publisher: IEEE
Issue Date: 2015
Series/Report no.: IEEE INFOCOM
ISBN: 9781479983810
ISSN: 0743-166X
Conference Name: 34th IEEE Conference on Computer Communications (INFOCOM) (26 Apr 2015 - 1 May 2015 : Kowloon)
Statement of
Shuangjuan Li and Hong Shen
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.
Rights: © 2015 IEEE
DOI: 10.1109/INFOCOM.2015.7218388
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access178.84 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.