Krause, Andreas and Gupta, Anupam and Rajagopal, Ram and Guestrin, Carlos (2009) Simultaneous Placement and Scheduling of Sensors. In: Information Processing in Sensor Networks, 2009. IEEE , pp. 181-192. ISBN 978-1-4244-5108-1 http://resolver.caltech.edu/CaltechAUTHORS:20100507-151434408
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100507-151434408
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 selectively 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 from each other; one first decides where to place the sensors, and then when to activate them. In this paper, 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 ldquobalancedrdquo schedules that perform uniformly well over time, rather than only on average. We then extend the algorithm to allow 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).
|Item Type:||Book Section|
|Additional Information:||© 2009 IEEE. Issue Date: 13-16 April 2009; date of current version: 21 August 2009. This work was partially supported by NSF Grants CNS-0509383, CNS-0625518, CCF-0448095, CCF-0729022, ARO MURI W911NF0710287 and a gift from Intel. A. Gupta and C. Guestrin were partly supported by Alfred P. Sloan Fellowships, C. Guestrin by an IBM Faculty Fellowship and ONR Young Investigator Award N00014-08- 1-0752 (2008-2011). A. Krause was partly supported by a Microsoft Research Graduate Fellowship.|
|Subject Keywords:||Sensor networks; approximation algorithms|
|Other Numbering System:|
|Official Citation:||Krause, A.; Rajagopal, R.; Gupta, A.; Guestrin, C.; , "Simultaneous placement and scheduling of sensors," Information Processing in Sensor Networks, 2009. IPSN 2009. International Conference on , vol., no., pp.181-192, 13-16 April 2009 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5211932&isnumber=5211879|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Jason Perez|
|Deposited On:||02 Jun 2010 16:52|
|Last Modified:||26 Dec 2012 12:01|
Repository Staff Only: item control page