When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a funda- mental task. Not only should the sensors be informative, but they should also be able to communicate efficiently. In this paper, we present a data-driven approach that addresses the three central aspects of this problem: measuring the predic- tive quality of a set of sensor locations (regardless of whether sensors are ever placed at these locations), predicting the communication cost involved with these placements, and designing an algorithm with provable quality guarantees that optimizes the NP-hard tradeoff. Specifically, we use data from a pilot deployment to build non-parametric probabilis- tic models called Gaussian Processes (GPs) both for the spatial phenomena of interest and for the spatial variability of link qualities, which allows us to estimate predictive power and communication cost of unsensed locations. Sur- prisingly, uncertainty in the representation of link qualities plays an important role in estimating communication costs. Using these models, we present a novel, polynomial-time, data-driven algorithm, pSPIEL, which selects Sensor Place- ments at Informative and cost-Effective Locations. Our approach exploits two important properties of this problem: submodularity, formalizing the intuition that adding a node to a small deployment can help more than adding a node to a large deployment; and locality, under which nodes that are far from each other provide almost independent in- formation. Exploiting these properties, we prove strong approximation guarantees for our pSPIEL approach. We also provide extensive experimental validation of this practical approach on several real-world placement problems, and built a complete system implementation on 46 Tmote Sky motes, demonstrating significant advantages over existing methods.

@inproceedings{krause06near,
	author = {Andreas Krause and Carlos Guestrin and Anupam Gupta and Jon Kleinberg},
	booktitle = {Proc. of Information Processing in Sensor Networks (IPSN)},
	title = {Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost},
	year = {2006}}