Select Lab Publications

Simultaneous Optimization of Sensor Placements and Balanced Schedules (2011)

By: Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin

Abstract: 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).

Download Information
Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin (2011). "Simultaneous Optimization of Sensor Placements and Balanced Schedules." IEEE Transactions on Automatic Control, 56(10), 2390-2405. pdf            
BibTeX citation

Author = {Andreas Krause and Ram Rajagopal and Anupam Gupta and
Carlos Guestrin},
Journal = {IEEE Transactions on Automatic Control},
Keywords = {submodularity; sensor networks; sensor placement;
algorithms; water distribution systems},
Month = {October},
Number = {10},
Pages = {2390-2405},
Title = {Simultaneous Optimization of Sensor Placements and Balanced
Volume = {56},
Year = {2011},
wwwtopic={Sensor Networks}

full list