@inproceedings{47ef32a1905e4f65aaf164a521c359b2,
title = "Minimizing the Maximum Sensor Movement towards Grid Points for Barrier Coverage",
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.",
keywords = "barrier coverage, minimum maximum sensor movement, mobile sensor network",
author = "Shuangjuan Li and Hong Shen",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 7th International Symposium on Parallel Architectures, Algorithms, and Programming, PAAP 2015 ; Conference date: 12-12-2015 Through 14-12-2015",
year = "2016",
month = jan,
day = "19",
doi = "10.1109/PAAP.2015.31",
language = "English",
series = "Proceedings - International Symposium on Parallel Architectures, Algorithms and Programming, PAAP",
publisher = "IEEE Computer Society",
pages = "116--121",
editor = "Hong Shen and Hong Shen and Yingpeng Sang and Haiping Huang",
booktitle = "Proceedings - 7th International Symposium on Parallel Architectures, Algorithms, and Programming, PAAP 2015",
address = "United States",
}