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 towards grid points for barrier coverage
Author: Li, S.
Shen, H.
Citation: Proceedings - International Symposium on Parallel Architectures, Algorithms and Programming, PAAP, 2016 / Shen, H., Sang, Y., Huang, H. (ed./s), vol.2016-January, pp.116-121
Publisher: IEEE
Issue Date: 2016
ISBN: 9781467391177
ISSN: 2168-3034
Conference Name: Seventh International Symposium on Parallel Architectures, Algorithms and Programming (12 Dec 2015 - 14 Dec 2015 : Nanjing, China)
Editor: Shen, H.
Sang, Y.
Huang, H.
Statement of
Shuangjuan Li and Hong Shen
Abstract: Barrier coverage has important applications in military and homeland security. Given a set of mobile sensors and their initial positions, how to move these sensors to achieve the required barrier coverage while maintaining balanced battery consumption across all sensors is a challenging problem of great significance in both theory and applications. Given a set of grid points on the barrier line, a set of sensors located on the plane containing the barrier line, we study the MinMax problem of relocating the sensors to the grid points such that the maximum sensor movement is minimized. In this paper we present an O(n2logn) time algorithm for this problem, which improves the previously known result of O(n3logl) time. Our algorithm deploys a novel decision algorithm that determines whether each grid point can be occupied by a sensor within a given maximum moving distance, and then finds the minimum among these distances using binary search
Rights: © 2015 IEEE
DOI: 10.1109/PAAP.2015.31
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access187.67 kBAdobe PDFView/Open

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