Journal
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Volume 56, Issue 10, Pages 2390-2405Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2011.2164010
Keywords
Approximation algorithms; information theory; sensor networks; sensor placement; sensor scheduling; sensor tasking; spatial monitoring
Funding
- National Science Foundation (NSF) [CNS-0509383, CNS-0625518, CNS-0932392, CCF-0448095, CCF-0729022, IIS-0953413]
- ONR [N000140911044, N00014-08-1-0752]
- Alfred P. Sloan Fellowships
- IBM
- Microsoft
- ARO-MURI [UCSC-W911NF-05-1-0246-VA-09/05]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1016799] Funding Source: National Science Foundation
Ask authors/readers for more resources
We consider the problem of monitoring spatial phenomena, such as road speeds on a highway, using wireless sensors with limited battery life. A central question is to decide where to locate these sensors to best predict the phenomenon at the unsensed locations. However, given the power constraints, we also need to determine when to activate these sensors in order to maximize the performance while satisfying lifetime requirements. Traditionally, these two problems of sensor placement and scheduling have been considered separately; one first decides where to place the sensors, and then when to activate them. We present an efficient algorithm, ESPASS, that simultaneously optimizes the placement and the schedule. We prove that ESPASS provides a constant-factor approximation to the optimal solution of this NP-hard optimization problem. A salient feature of our approach is that it obtains balanced schedules that perform uniformly well over time, rather than only on average. We also develop MCSPASS, an extension to our algorithm that allows for a smooth power-accuracy tradeoff. Our algorithm applies to complex settings where the sensing quality of a set of sensors is measured, e. g., in the improvement of prediction accuracy (more formally, to situations where the sensing quality function is submodular). We present extensive empirical studies on several sensing tasks, and our results show that simultaneously placing and scheduling gives drastically improved performance compared to separate placement and scheduling (e.g., a 33% improvement in network lifetime on the traffic prediction task).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available