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 si- multaneously optimizes the placement and the schedule. We prove that ESPASS provides a constant-factor approximation to the opti- mal solution of this NP-hard optimization problem. A salient fea- ture of our approach is that it obtains ``balanced'' 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 sens- ing quality of a set of sensors is measured, e.g., in the improve- ment of prediction accuracy (more formally, to situations where the sensing quality function is submodular). We present extensive em- pirical 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).

@inproceedings{krause09simultaneous,
	author = {Andreas Krause and Ram Rajagopal and Anupam Gupta and Carlos Guestrin},
	booktitle = {Proc. ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)},
	title = {Simultaneous Placement and Scheduling of Sensors},
	year = {2009}}