Practical Coding Algorithms for Consensus Problems with Zero Asymptotic Rate

Abstract

We consider the average consensus algorithm under the rate constraint communication network. 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 a network communication problem where there is an increasing correlation between the data exchanged, as the algorithm iterates. Henceforth, it is possible to utilize previously exchanged data and current side information to reduce 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. We explore the conditions on the quantization noise which lead to a consensus value whose mean squared distance from the initial average is bounded. We propose two main practical schemes and show that they achieve bounded convergence with zero rate asymptotically. We further investigate the problem under regular grid network assumption and observe that computational complexity of the schemes reduce significantly and global knowledge of the network connectivity assumption can be relaxed. Thus, we conclude that the proposed schemes become scalable under dense networks.