Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm

ABSTRACT

We address the problem of energy consumption reduction for wireless sensor networks, where each of the sensors has limited power and acquires data that should be transmitted to a central node. The final goal is to have a reconstructed version of the data measurements at the central node, with the sensors spending as little energy as possible, for a given data reconstruction accuracy. In our scenario, sensors in the network have a choice of different coding schemes to achieve varying levels of compression. The compression algorithms considered are based on the lifting factorization of the wavelet transform, and exploit the natural data flow in the network to aggregate data by computing partial wavelet coefficients that are refined as data flows towards the central node. The proposed algorithm operates by first selecting a routing strategy through the network. Then, for each route, an optimal combination of data representation algorithms i.e. assignment at each node, is selected. A simple heuristic is used to determine the data representation technique to use once path merges are taken into consideration. We demonstrate that by optimizing the coding algorithm selection the overall energy consumption can be significantly reduced when compared to the case when data is just quantized and forwarded to the central node. Moreover, the proposed algorithm provides a tool to compare different routing techniques and identify those that are most efficient overall, for given node locations. We evaluate the algorithm using both a second-order autoregressive (AR) model and empirical data from a real wireless sensor network deployment.

REFERENCES

• 1: C. Chong and S. P. Kumar. Sensor networks: Evolution, opportunities, and challenges. Proceedings of the IEEE, 91(8):1247--1256, August 2003.
• 2: A. Ciancio and A. Ortega. A distributed wavelet compression algorithm for wireless sensor networks using lifting. In International Conference on Acoustics, Speech and Signal Processing - ICASSP04, Montreal, Canada, May 2004.
• 3: A. Ciancio and A. Ortega. A distributed wavelet compression algorithm for wireless multihop sensor networks using lifting. In International Conference on Acoustics, Speech and Signal Processing - ICASSP05, Philadelphia, USA, March 2005.
• 4: A. Ciancio and A. Ortega. A dynamic programming approach to distortion-energy optimization for distributed wavelet compression with applications to data gathering in wireless sensor networks. International Conference on Acoustics, Speech and Signal Processing - ICASSP06, 2006.
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: R. Cristescu, B. Beferull-Lozano, and M. Vetterli. Networked Slepian-Wolf: Theory and algorithms. 1st European Workshop on Sensor Networks EWSN 2004, 2004. Berlin, Germany.
• 7: M. Gastpar, P. Dragotti, and M. Vetterli. The distributed Karhunen-Loève transform. In International Workshop on Multimedia Signal Processing, St. Thomas, US Virgin Islands, December 2002.
• 8: 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
• 9: B. B.-L. J. Acimovic and R. Cristescu. Adaptive distributed algorithms for power-efficient data gathering in sensor networks. In Under Submission.
• 10: H. M. on Great Duck Island. Online data-set located at http://www.greatduckisland.net.
• 11: S. Pattem, B. Krishnamachari, and R. Govindan. The impact of spatial correlation on routing with compression in wireless sensor networks. Journal version, Under Submission, 2005.
• 12: S. S. Pradhan, J. Kusuma, and K. Ramchandran. Distributed compression in a dense microsensor network. IEEE Signal Processing Magazine, pages 51--60, March 2002.
• 13: B. B.-L. R. Cristescu and M. Vetterli. Networked Slepian-Wolf: Theory, algorithms and scaling laws. To appear in IEEE Transactions on Information Theory, 2005.
• 14: Razvan Cristescu , Baltasar Beferull-Lozano , Martin Vetterli , Roger Wattenhofer, Network correlated data gathering with explicit communication: NP-completeness and algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.41-54, February 2006 [doi>10.1109/TNET.2005.863711]
• 15: 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]
• 16: 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]
• 17: S. D. Servetto. Sensing Lena - massively distributed compression of sensor images. ICIP - International Conference on Image Compression, September 2003.
• 18: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 19: K. S. Y. Zhu and R. Sivakumar. Practical limits on achievable energy improvements and useable delay tolerance in correlation aware data gathering in wireless sensor networks. In IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), Santa Clara, California, USA,, September 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance

Keywords:
distributed wavelets, energy optimization, wireless sensor networks