Efficient gathering of correlated data in sensor networks

ABSTRACT

In this paper, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network.We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but non-exhaustive) centralized approximation algorithm that returns a solution within O(log n) of the optimal size. Based on the approximation algorithm, we design a class of efficient centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique -- even in dynamic conditions.

REFERENCES

• 1: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 2: Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms, v.17 n.3, p.381-408, Nov. 1994
• 3: A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies. In Proceedings of the IEEE INFOCOM, 2002.
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 5: Yuanzhu Peter Chen , Arthur L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513821]
• 6: J. Chou, D. Petrovic, and K. Ramchandran. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks. In Proceedings of the IEEE INFOCOM, 2003.
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: R. Cristescu, B. Beferull-Lozano, and M. Vetterli. On network correlated data gathering. In Proceedings of the IEEE INFOCOM, 2004.
• 9: Răzvan Cristescu , Martin Vetterli, Power efficient gathering of correlated data: optimization, NP-completeness and heuristics, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961278]
• 10: D. Culler et al. TinyOS. http://www.tinyos.net, 2004.
• 11: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 12: B. Deb, S. Bhatnagar, and B. Nath. Multi-resolution state retrieval in sensor networks. In Proceedings of Intl.\ Workshop on Sensor Network Protocols and Applications, 2003.
• 13: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: M. Enachescu, A. Goel, R. Govindan, and R. Motwani. Scale free aggregation in sensor networks. In Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), 2004.
• 15: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 16: S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 1998.
• 17: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• 18: Himanshu Satishkumar Gupta , Jeffrey D. Ullman, Selection and maintenance of views in a data warehouse, 2000
• 19: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 20: S. M. Kay. Fundamentals of Statistical Signal Processing: Detection Theory, Vol. II. Prentice-Hall, 1998.
• 21: A. Laouiti, A. Qayyum, and L. Viennot. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. In Proc. of the Hawaii Intl. Conf. on System Sciences, 2002.
• 22: D. Marco, E. Duarte-Melo, M. Liu, and D. L. Neuhoff. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In Proceedings of the International Workshop on Information Processing in Sensor Networks (IPSN), 2003.
• 23: National Climatic Data Center. www.ncdc.noaa.gov/cgi-bin/res40.pl?page=gsod.html.
• 24: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 25: Anna Scaglione , Sergio D. Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570663]
• 26: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 27: Pascal von Rickenbach , Roger Wattenhofer, Gathering correlated data in sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022640]
• 28: J. Wu and F. Dai. Broadcasting in ad hoc networks based on self-pruning. In Proceedings of the IEEE INFOCOM, 2003.
• 29: J. Wu and H. Li. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems Journal, 3, 2001.
• 30: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 31: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 32: S. Yoon and C. Shahabi. Exploiting spatial correlation towards an energy efficient clustered aggregation technique (cag). In Proceedings of the International Conference on Communications (ICC), 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance

Keywords:
correlated data, energy efficiency, topology control