Algorithms for sensor cover problems

• Grant number: 09/03589-0
• Support Opportunities: Scholarships in Brazil - Master
• Start date: August 01, 2009
• End date: February 28, 2011
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Rafael da Ponte Barbosa
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This project addresses the study of algorithms for sensor cover problems.The central problem we plan to investigate, called sensor cover problem, in its general form can be formulated as follows. Suppose we are given a set ${\mathcal S}$ of sensors and a region ${\mathcal R}$ to be covered by these sensors. For each sensor $s\in{\mathcal S}$ we are also given a region $R(s)$ (a subregion of ${\mathcal R}$) and a duration $d_s$ (battery life), interval of time during which the sensor remains working. We wish to find, for each sensor $s$, its beginning time $t(s)$, that is, the moment to turn on the sensor ~$s$, so as to maximize the length of time that the original region remains covered.This problem has been studied by Buchsbaum, Efrat,Jain, Venkatasubramanian and Yi [SODA 2007], who also presented results on some special cases of this problem. The one-dimensionalc case, which will be object of our studies, deals with intervals on the real line. In this case, the given region ${\mathcal R}$ is an interval of the real line, each sensor covers a subinterval of ${\mathcal R}$, and the objective is to decide when each sensor has to be turned on so as to maximize the length of time the original interval remains covered. This case is also known as the restricted strip covering problem. Other related problems have been investigated by Buchsbaum, Karloff, Kenyon, Reingold and Thorup [SIAM J. Comput. 2004], Feige, Halldórsson, Kortsarz and Srinivasan [SIAM J. Comput. 2002], and also by Perillo and Heinzelman [IEEE WCNC2003].The focus of this project is to study, under the algorithmic point of view, the sensor cover problem and its variants. One of our aims is to write an updated and broad survey on this topic. Approximation algorithms and computacional complexity issues will be treated in this survey. If possible, the student will work on some open problems: look for better approximation algorithms and try to settle the question on the existence of a PTAS (polynomial time approximation scheme) for the one-dimensional case.The proposed research, complemented by the courses that the student will take, has the purpose of giving the student a solid background in the area of combinatorial optimization, algorithms and computacional complexity.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BARBOSA, Rafael da Ponte. Algorithms for the sensor cover problem. 2011. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.