Near-optimal sensor placements: maximizing information while minimizing communication cost

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.

REFERENCES

• 1: Baruch Awerbuch , Yossi Azar , Avrim Blum , Santosh Vempala, New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen, SIAM Journal on Computing, v.28 n.1, p.254-262, Feb. 1999 [doi>10.1137/S009753979528826X]
• 2: Alberto Cerpa , Jennifer L. Wong , Louane Kuang , Miodrag Potkonjak , Deborah Estrin, Statistical model of lossy links in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 3: N. A. Cressie. Statistics for Spatial Data. Wiley, 1991.
• 4: L. Csato, E. Fokue, M. Opper, B. Schottky, and O. Winther. Efficient approaches to gaussian process classification. In NIPS, 2000.
• 5: A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In VLDB, 2004.
• 6: S. Funke, A. Kesselman, F. Kuhn, Z. Lotker, and M. Segal. Improved approximation algorithms for connected sensor cover. In ADHOC, 04.
• 7: Naveen Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060650]
• 8: Carlos Guestrin , Peter Bodi , Romain Thibau , Mark Paski , Samuel Madde, Distributed regression: an efficient framework for modeling sensor network data, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984624]
• 9: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 10: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 11: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 12: David S. Johnson , Maria Minkoff , Steven Phillips, The prize collecting Steiner tree problem: theory and practice, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.760-769, January 09-11, 2000, San Francisco, California, United States
• 13: K. Kar and S. Banerjee. Node placement for connected coverage in sensor networks. In WiOpt, 2003.
• 14: A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg. Near-optimal sensor placements: Maximizing information while minimizing communication cost. Technical report, CMU-CALD-05-110, 2005.
• 15: A. Levin. A better approximation algorithm for the budget prize collecting tree problem. Ops. Res. Lett., 32:316--319, 2004.
• 16: G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.
• 17: D. J. Nott and W. T. M. Dunsmuir. Estimation of nonstationary spatial covariance structure. Biometrika, 89:819--829, 2002.
• 18: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 19: M. Widmann and C. S. Bretherton. 50 km resolution daily precipitation for the pacific northwest. http://www.jisao.washington.edu/data sets/widmann/, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Measurement

Keywords:
approximation algorithms, communication cost, gaussian processes, information, link quality, sensor networks, sensor placement, spatial monitoring, theory