Robust sensor placements at informative and communication-efficient locations

Andreas Krause, Carlos Guestrin, Anupam Gupta, Jon Kleinberg

Research output: Contribution to journalArticlepeer-review


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 article, 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 trade-off. Specifically, we use data from a pilot deployment to build nonparametric 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 communication-Efficient 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. In addition, we show how our placements can be made robust against changes in the environment, and how PSPIEL can be used to plan informative paths for information gathering using mobile robots. 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.

Original languageEnglish (US)
Article number31
JournalACM Transactions on Sensor Networks
Issue number4
StatePublished - Feb 2011


  • Approximation algorithms
  • Communication cost
  • Gaussian processes
  • Information theory
  • Link quality
  • Sensor networks
  • Sensor placement
  • Spatial monitoring

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Robust sensor placements at informative and communication-efficient locations'. Together they form a unique fingerprint.

Cite this