Decentralized compression and predistribution via randomized gossiping

ABSTRACT

Developing energy efficient strategies for the extraction, transmission, and dissemination of information is a core theme in wireless sensor network research. In this paper we present a novel system for decentralized data compression and predistribution. The system simultaneously computes random projections of the sensor data and disseminates them throughout the network using a simple gossiping algorithm. These summary statistics are stored in an efficient manner and can be extracted from a small subset of nodes anywhere in the network. From these measurements one can reconstruct an accurate approximation of the data at all nodes in the network, provided the original data is compressible in a certain sense which need not be known to the nodes ahead of time. The system provides a practical and universal approach to decentralized compression and content distribution in wireless sensor networks. Two example applications, network health monitoring and field estimation, demonstrate the utility of our method.

REFERENCES

• 1: S. Acedański, S. Deb, M. Médard, and R. Koetter. How good is random linear coding based distributed networked storage? In Proc. Netcod, Italy, April 2005.
• 2: D. Baron, M. Duarte, S. Sarvotham, M. Wakin, and R. Baraniuk. An information-theoretic approach to distributed compressed sensing. In Allerton Conf. on Comm., Control, and Computing, Sept. 2005.
• 3: A. R. Barron. Complexity regularization with application to artificial neural networks. Nonparametric Functional Estimation and Related Topics, pages 561--576, 1991.
• 4: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: Design, analysis and applications. In Proc. IEEE Infocom, Miami, FL, March 2005.
• 5: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Mixing times for random walks on geometric random graphs. In Proc. SIAM Workshop on Analytic Algorithms and Combinatorics, Vancouver, B.C., Canada, January 2005.
• 6: E. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. Preprint, June, 2004.
• 7: E. Candès and T. Tao. The dantzig selector: statistical estimation when p is much larger than n. Preprint. May, 2005.
• 8: E. Candès and T. Tao. Near optimal signal recovery from random projections: Universal encoding strategies? Preprint, October, 2004.
• 9: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 10: Alexandros G. Dimakis , Anand D. Sarwate , Martin J. Wainwright, Geographic gossip: efficient aggregation for sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127791]
• 11: Alexandros G. Dimakis , Vinod Prabhakaran , Kannan Ramchandran, Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 12: D. L. Donoho. Compressed sensing. Preprint, September, 2004.
• 13: M. Gastpar, P. L. Dragotti, and M. Vetterli. The distributed Karhunen-Loeve transform. Submitted to IEEE Trans. on Info. Theory, Nov., 2004.
• 14: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46:388--404, 2000.
• 15: J. Haupt and R. Nowak. Signal reconstruction from noisy random projections. Submitted to IEEE Trans. on Info. Theory, March, 2005.
• 16: J. Haupt and R. Nowak. Signal reconstruction from noisy random projections with applications to wireless sensing. In Proc. IEEE Wkshp. on Stat. Sig. Proc., Bordeaux, France, July 2005.
• 17: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 18: J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
• 19: R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. on Auto. Control, 49(9):1520--1533, Sept. 2004.
• 20: M. D. Penrose. Rand. Geometric Graphs. Oxford Press, 2003.
• 21: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 22: S. S. Pradhan, J. Kusuma, and K. Ramchandran. Distributed compression in a dense microsensor network. IEEE Signal Processing Magazine, 19(2):51--60, March 2002.
• 23: M. G. Rabbat, R. D. Nowak, and J. A. Bucklew. Generalized consensus algorithms in networked systems with erasure links. In Proc. IEEE Wkshp. on Signal Proc. Advances in Wireless Comm., New York, NY, June 2005.
• 24: V. Saligrama, M. Alanyali, and O. Savas. Distributed detection in sensor networks with packet losses and finite capacity links. IEEE Trans. on Sig. Proc., to appear, 2006.
• 25: Dzulkifli S. Scherber , Haralabos C. Papadopoulos, Locally constructed algorithms for distributed computations in ad-hoc networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984625]
• 26: S. D. Servetto. On the feasibility of large-scale wireless sensor networks. Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, 2002.
• 27: R. Szewczyk, J. Polastre, A. Mainwaring, and D. Culler. Lessons from a sensor network expedition. In Proc. First European Workshop on Wireless Sensor Networks, Berlin, Germany, January 2004.
• 28: Lin Xiao , Stephen Boyd , Sanjay Lall, A scheme for robust distributed sensor fusion based on average consensus, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Theory

Keywords:
decentralized compression, predistribution in sensor networks, random projections