Select Lab Publications


Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost (2006)

By: Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg

Abstract: When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental 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 predictive quality of a set of sensor locations (regardless of whether sensors were 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 probabilistic 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. Surprisingly, 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 Placements 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 information. 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.

Download Information
Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg (2006). "Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost." International Symposium on Information Processing in Sensor Networks (IPSN). Winner of the Best Paper Award. pdf   talk        
BibTeX citation

@inproceedings{Krause+Guestrin+Gupta+Kleinberg:ipsn06pspiel,
author = {Andreas Krause and Carlos Guestrin and Anupam Gupta and Jon Kleinberg},
title = {Near-optimal Sensor Placements: Maximizing Information while Minimizing
Communication Cost},
booktitle = {International Symposium on Information Processing
in Sensor Networks (IPSN)},
month = {April},
year = {2006}
wwwfilebase = {ipsn2006-krause-guestrin-gupta-kleinberg},
wwwtopic = {Observation Selection},
wwwaward = {Winner of the Best Paper Award}
}



full list