Universal distributed sensing via random projections

ABSTRACT

This paper develops a new framework for distributed coding and compression in sensor networks based on distributed compressed sensing (DCS). DCS exploits both intra-signal and inter-signal correlations through the concept of joint sparsity; just a few measurements of a jointly sparse signal ensemble contain enough information for reconstruction. DCS is well-suited for sensor network applications, thanks to its simplicity, universality, computational asymmetry, tolerance to quantization and noise, robustness to measurement loss, and scalability. It also requires absolutely no inter-sensor collaboration. We apply our framework to several real world datasets to validate the framework.

REFERENCES

• 1: Deborah Estrin , David Culler , Kris Pister , Gaurav Sukhatme, Connecting the Physical World with Pervasive Networks, IEEE Pervasive Computing, v.1 n.1, p.59-69, January 2002 [doi>10.1109/MPRV.2002.993145]
• 2: D. Slepian and J. K. Wolf, "Noiseless coding of correlated information sources," IEEE Trans. Inform. Theory, vol. 19, pp. 471--480, July 1973.
• 3: S. Pradhan and K. Ramchandran, "Distributed source coding using syndromes (DISCUS): Design and construction," IEEE Trans. Inform. Theory, vol. 49, pp. 626--643, Mar. 2003.
• 4: Zixiang Xiong , Javier Garcia-Frias , Bernd Girod, Call for papers: special issue on distributed source coding, Signal Processing, v.84 n.9, p.1729-1729, September 2004 [doi>10.1016/j.sigpro.2004.06.006]
• 5: H. Luo and G. Pottie, "Routing explicit side information for data compression in wireless sensor networks," in Int. Conf. Distirbuted Computing in Sensor Systems (DCOSS), Marina Del Rey, CA, June 2005.
• 6: M. Gastpar, P. L. Dragotti, and M. Vetterli, "The distributed Karhunen-Loeve transform," IEEE Trans. Inform. Theory, Nov. 2004, Submitted.
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: T. Uyematsu, "Universal coding for correlated sources with memory," in Canadian Workshop Inform. Theory, Vancouver, Canada, June 2001.
• 9: E. Candès and T. Tao, "Near optimal signal recovery from random projections and universal encoding strategies," IEEE Trans. Inform. Theory, 2004, Submitted.
• 10: D. Donoho, "Compressed sensing," 2004, Submitted.
• 11: J. Tropp and A. C. Gilbert, "Signal recovery from partial information via orthogonal matching pursuit," Apr. 2005, Submitted.
• 12: D. Baron, M. B. Wakin, M. F. Duarte, S. Sarvotham, and R. G. Baraniuk, "Distributed compressed sensing," 2005, Available at dsp.rice.edu/cs.
• 13: D. Ganesan, D. Estrin, and J. Heidemann, "DIMENSIONS: Why do we need a new data handling architecture for sensor networks?," in Proc. ACM Workshop on Hot Topics in Networks, Princeton, NJ, Oct. 2002, pp. 143--148, ACM.
• 14: 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]
• 15: A. Kashyap, L. A. Lastras-Montano, C. Xia, and Z. Liu, "Distributed source coding in dense sensor networks," in Proc. Data Compression Conference (DCC), Snowbird, UT, Mar. 2005.
• 16: 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]
• 17: D. Li, K. D. Wong, Y. H. Hu, and A. M. Sayeed, "Detection, classification, and tracking of targets," IEEE Signal Processing Mag, vol. 19, no. 2, pp. 17--29, 2002.
• 18: Marco F. Duarte , Yu Hen Hu, Vehicle classification in distributed sensor networks, Journal of Parallel and Distributed Computing, v.64 n.7, p.826-838, July 2004 [doi>10.1016/j.jpdc.2004.03.020]
• 19: A. Sayeed, "A statistical signal modeling framework for wireless sensor networks," Tech. Rep., Univ. of Wisconsin - Madison, Feb 2004.
• 20: P. Ishwar, R. Puri, K. Ramchandran, and S. S. Pradhan, "On rate-constrained distributed estimation in unreliable sensor networks," IEEE J. Select. Areas Commun., vol. 23, no. 4, pp. 765--775, 2005.
• 21: J. Haupt and R. Nowak, "Signal reconstruction from noisy random projections," IEEE Trans. Inform. Theory, 2005, Submitted.
• 22: Waheed Bajwa , Akbar Sayeed , Robert Nowak, Matched source-channel communication for field estimation in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 23: J. Tropp, A. C. Gilbert, and M. J. Strauss, "Simulataneous sparse approximation via greedy pursuit," in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Philadelphia, PA, Mar. 2005.
• 24: E. Candès, J. Romberg, and T. Tao, "Stable signal recovery from incomplete and inaccurate measurements," Comm. Pure and Applied Mathematics, 2005, Submitted.
• 25: J. A. Tropp, M. B. Wakin, M. F. Duarte, D. Baron, and R. G. Baraniuk, "Random filters for compressive sampling and reconstruction," in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), May 2006.
• 26: D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, S. Sarvotham, D. Baron, K. F. Kelly, and R. G. Baraniuk, "A compressed sensing camera: New theory and an implementation using digital micromirrors," in Proc. Computational Imaging IV at SPIE Electronic Imaging, San Jose, CA, January 2006.
• 27: S. PalChaudhuri, S. Du, A. K. Saha, and D. B. Johnson, "TreeCast: A stateless addressing and routing architecture for sensor networks," in Proc. International Parallel and Distributed Processing Symposium (IPDPS), Santa Fe, NM, Apr. 2004, pp. 221--228.
• 28: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 29: S. D. Servetto, K. Ramchandran, V. A. Vaishampayan, and K. Nahrstedt, "Multiple Description Wavelet Based Image Coding," IEEE Trans. Image Processing, vol. 9, no. 5, pp. 813--826, 2000.
• 30: Y. Wang, M. T. Orchard, and A. Reibman, "Multiple description image coding for noisy channels by pairing transform coefficients," in Proc. Workshop Multimedia Signal Processing (MMSP), Princeton, NJ, 1997.
• 31: S. N. Diggavi and V. A. Vaishampayan, "On multiple description source coding with decoder side information," in Proc. Information Theory Workshop (ITW), Oct. 2004, pp. 88--93.
• 32: S. D. Rane, A. Aaron, and B. Girod, "Systematic lossy forward error protection for error-resilient digital video broadcasting," in Proc. Security, Steganography, and Watermarking of Multimedia Contents VI at SPIE Electronic Imaging, Jan. 2004, pp. 588--595.
• 33: R. Grivonbal, R. M. Figueras i Ventura, and P. Vandergheynst, "A simple test to check the optimality of sparse signal approximations," in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Philadelphia, PA, Mar. 2005.
• 34: M. F. Duarte, M. Davenport, M. B. Wakin, and R. G. Baraniuk, "Sparse signal detection from incoherent projections," in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Toulouse, France, May 2006.
• 35: F. Koushanfar, N. Taft, and M. Potkonjak, "Sleeping coordination for comprehensive sensing using isotonic regressiond and domatic partitions," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Security, Theory

Keywords:
compressed sensing, correlation, greedy algorithms, linear programming, sensor networks, sparsity