Distributed Average Consensus With Dithered Quantization
- 13 June 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 56 (10), 4905-4918
- https://doi.org/10.1109/tsp.2008.927071
Abstract
In this paper, we develop algorithms for distributed computation of averages of the node data over networks with bandwidth/power constraints or large volumes of data. Distributed averaging algorithms fail to achieve consensus when deterministic uniform quantization is adopted. We propose a distributed algorithm in which the nodes utilize probabilistically quantized information, i.e., dithered quantization, to communicate with each other. The algorithm we develop is a dynamical system that generates sequences achieving a consensus at one of the quantization values almost surely. In addition, we show that the expected value of the consensus is equal to the average of the original sensor data. We derive an upper bound on the mean-square-error performance of the probabilistically quantized distributed averaging (PQDA). Moreover, we show that the convergence of the PQDA is monotonic by studying the evolution of the minimum-length interval containing the node values. We reveal that the length of this interval is a monotonically nonincreasing function with limit zero. We also demonstrate that all the node values, in the worst case, converge to the final two quantization bins at the same rate as standard unquantized consensus. Finally, we report the results of simulations conducted to evaluate the behavior and the effectiveness of the proposed algorithm in various scenarios.Keywords
This publication has 23 references indexed in Scilit:
- Distributed average consensus with least-mean-square deviationJournal of Parallel and Distributed Computing, 2007
- Robust Decentralized Source Localization via AveragingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Decentralized compression and predistribution via randomized gossipingPublished by Association for Computing Machinery (ACM) ,2006
- Decentralized Estimation in an Inhomogeneous Sensing EnvironmentIEEE Transactions on Information Theory, 2005
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Robust aggregation protocols for large-scale overlay networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Computing aggregates for monitoring wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Supporting aggregate queries over ad-hoc wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Local divergence of Markov chains and the analysis of iterative load-balancing schemesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Directed diffusionPublished by Association for Computing Machinery (ACM) ,2000