Near-Optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost

Carlos Guestrin, CMU

Tuesday, October 24
Noon - SENSQ 5317
Free pizza for attendees starting at 11:45 a.m.

Hosted by Jose' Brustoloni

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 talk, I will present our 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. Using these models, we present a novel efficient algorithm, pSPIEL, which selects Sensor Placements at Informative and cost-Effective Locations. Exploiting two important properties of this problem -- submodularity and locality -- 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, demonstrating significant advantages over existing methods.

This talk includes joint work with Andreas Krause, Anupam Gupta, Jon Kleinberg and Ajit Singh

Biography of Speaker

Carlos Guestrin is an assistant professor in the Machine Learning and in the Computer Science Departments at Carnegie Mellon University. Previously, he was a senior researcher at the Intel Research Lab in Berkeley. Carlos Guestrin received his MSc and PhD in Computer Science from Stanford University in 2000 and 2003, respectively, and a Mechatronics Engineer degree from the Polytechnic School of the University of São Paulo, Brazil, in 1998. His current research spans the areas of planning, reasoning and learning in uncertain dynamic environments, focusing on applications in sensor networks. Carlos Guestrin received best paper awards at the Information Processing in Sensor Networks (IPSN) in 2005 and 2006, Very Large Data Bases (VLDB-2004), and Neural Information Processing Systems (NIPS-2003) conferences, and runner-up best paper awards at the Uncertainty in Artificial Intelligence (UAI-2005) and Machine Learning (ICML-2005) conferences. He is also a recipient of the Alfred P. Sloan Fellowship, IBM Faculty Fellowship, the Siebel Scholarship and the Stanford Centennial Teaching Assistant Award.