Differential nested lattice encoding for consensus problems

ABSTRACT

In this paper we consider the problem of transmitting quantized data while performing an average consensus algorithm. Average consensus algorithms are protocols to compute the average value of all sensor measurements via near neighbors communications. The main motivation for our work is the observation that consensus algorithms offer the perfect example of network communications where there is an increasing correlation between the data exchanged, as the system updates its computations. Henceforth, it is possible to utilize previously exchanged data and current side information to reduce significantly the demands of quantization bit rate for a certain precision. We analyze the case of a network with a topology built as that of a random geometric graph and with links that are assumed to be reliable at a constant bit rate. Numerically we show that in consensus algorithms, increasing number of iterations does not have the effect of increasing the error variance. Thus, we conclude that noisy recursions lead to a consensus if the data correlation is exploited in the messages source encoders and decoders. We briefly state the theoretical results which are parallel to our numerical experiments.

REFERENCES

• 1: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Mixing times for random walks on geometric random graphs. In Workshop on Analytic Algorithms and Combinatorics Proc., January 2005.
• 2: M. Feder and N. Shulman. Source broadcasting with unknown amount of receiver side information. In IEEE Proc. of Information Theory Workshop Proc., pages 127--130, Banglore,India, 2005.
• 3: Zhixin Liu , Samuel Cheng , Angelos D. Liveris , Zixiang Xiong, Slepian-Wolf Coded Nested Quantization (SWC-NQ) for Wyner-Ziv Coding: Performance Analysis and Code Design, Proceedings of the Conference on Data Compression, p.322, March 23-25, 2004
• 4: S. Sandeep Pradhan , Kannan Ramchandran, Distributed Source Coding Using Syndromes (DISCUS): Design and Construction, Proceedings of the Conference on Data Compression, p.158, March 29-31, 1999
• 5: M. Rabbat, R. Nowak, and J. Bucklew. Generalized consensus computation in networked systems with erasure links. In IEEE Workshop on Signal Processing Advances in Wireless Communications Proc., pages 1088--1092, June 2005.
• 6: W. Ren, R.W. Beard, and D.B. Kingston. Multi-agentkalman consensus with relative uncertanity. In American Control Conference Proc., pages 1865--1870, OR, USA, June 2005.
• 7: R.O. Saber and R.M. Murray. Agreement problems in networks with directed graphs and switching topology. California Institute of Technology Technical Report, CIT-CDS 03-005, 2003.
• 8: D. Slepian and J.K. Wolf. Noiseless coding of correlated information sources. IEEE Trans. Inform. Theory, IT-19:471--480, July 1973.
• 9: A. Vosughi and A. Scaglione. Precoding and decoding paradigms for distributed data compression,. IEEE Transactions on Signal Processing, 2007.
• 10: A.D. Wyner and J. Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Trans. Inform. Theory, IT-22:1--10, Jan 1976.
• 11: L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems and Control Letters, 53:65--78, 2004.
• 12: L. Xiao, S. Boyd, and S. Kim. Distributed average consensus with least-mean-square deviation. In Mathematical Theory of Networks and Systems Proc., pages 158--167, Kyoto,Japan, July 2006.
• 13: M.E. Yildiz and A. Scaglione. Practical coding algorithms for consensus problems with zero asymptotic rate. Submitted to IEEE Trans. on Signal Processing, 2007.
• 14: R. Zamir and S. Shamai. Nested linear/lattice codes for wyner-ziv encoding. In IEEE Inform. Theory Workshop Proc., pages 158--167, Killarney,Ireland, 1998.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
average consensus, coding with side information, consensus, nested lattice coding, predictive coding