An architecture for distributed wavelet analysis and processing in sensor networks

ABSTRACT

Distributed wavelet processing within sensor networks holds promise for reducing communication energy and wireless bandwidth usage at sensor nodes. Local collaboration among nodes de-correlates measurements, yielding a sparser data set with significant values at far fewer nodes. Sparsity can then be leveraged for subsequent processing such as measurement compression, de-noising, and query routing. A number of factors complicate realizing such a transform in real-world deployments, including irregular spatial placement of nodes and a potentially prohibitive energy cost associated with calculating the transform in-network. In this paper, we address these concerns head-on; our contributions are fourfold. First, we propose a simple interpolatory wavelet transform for irregular sampling grids. Second, using ns-2 simulations of network traffic generated by the transform, we establish for a variety of network configurations break-even points in network size beyond which multiscale data processing provides energy savings. Distributed lossy compression of network measurements provides a representative application for this study. Third, we develop a new protocol for extracting approximations given only a vague notion of source statistics and analyze its energy savings over a more intuitive but naïve approach. Finally, we extend the 2-dimensional (2-D) spatial irregular grid transform to a 3-D spatio-temporal transform, demonstrating the substantial gain of distributed 3-D compression over repeated 2-D compression.

REFERENCES

• 1: J. Aćimovićc, R. Cristescu, and B. Beferull-Lozano. Efficient distributed multiresolution processing for data gathering in sensor networks. In Proc. IEEE Int. Conf. on Acoustic and Speech Sig. Proc. (ICASSP), pages 837--840, Mar. 2005.
• 2: S. Amat, F. Aràndiga, A. Cohen, R. Donat, G. Garcia, and M. von Oehsen. Data compression with ENO schemes: A case study. App. and Comp. Harmonic Analysis, 11:273--288, 2001.
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: A. Ciancio and A. Ortega. A distributed wavelet compression algorithm for wireless multihop sensor networks using lifting. In Proc. IEEE Int. Conf. on Acoustic and Speech Sig. Proc. (ICASSP), pages 825--828, Mar. 2005.
• 5: Deepak Ganesan , Ben Greenstein , Deborah Estrin , John Heidemann , Ramesh Govindan, Multiresolution storage and search in sensor networks, ACM Transactions on Storage (TOS), v.1 n.3, p.277-315, August 2005 [doi>10.1145/1084779.1084780]
• 6: Deepak Ganesan , Sylvia Ratnasamy , Hanbiao Wang , Deborah Estrin, Coping with irregular spatio-temporal sampling in sensor networks, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972396]
• 7: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang, Fractionally cascaded information in a sensor network, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984668]
• 8: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 9: S. Servetto. Distributed signal processing algorithms for the sensor broadcast problem. In Proc. Conf. on Information Sciences and Systems (CISS), Mar. 2003.
• 10: J. M. Shapiro. Embedded image coding using zerotrees of wavelet coefficients. IEEE Transactions on Signal Processing, 41:3445--3462, Dec. 1993.
• 11: Wim Sweldens, The lifting scheme: a construction of second generation wavelets, SIAM Journal on Mathematical Analysis, v.29 n.2, p.511-546, March 1998 [doi>10.1137/S0036141095289051]
• 12: R. Wagner, H. Choi, R. Baraniuk, and V. Delouille. Distributed wavlet transform for irregular sensor network grids. In Proc. IEEE Stat. Sig. Proc. Workshop (SSP), Jul. 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Theory

Keywords:
compression, distributed wavelet analysis, irregular grid wavelet analysis, multiscale analysis, sensor networks