Convergence Analysis for Regular Wireless Consensus Networks

Average consensus algorithms can be implemented over wireless sensor networks (WSN), where global statistics can be computed using the communications among sensor nodes locally. Simple execution, robustness to global topology changes due to frequent node failures, and underlying distributed philosophy have made consensus algorithms more suitable to WSNs. Since these algorithms are iterative in nature, it is very difficult to predict the convergence time of the average consensus algorithm on WSNs. We study the convergence of the average consensus algorithms for WSNs using distance regular graphs. We have obtained the analytical expressions for optimal consensus parameter and optimal convergence parameter, which estimates the convergence time for r-nearest neighbor cycle and torus networks. We have also derived the generalized expression for optimal consensus parameter and optimal convergence parameter for m-dimensional r-nearest neighbor torus networks. The obtained analytical results agree with the simulation results and show the effect of network dimension, number of nodes, and nearest neighbors on convergence time. This paper provides the basic analytical tools for managing and controlling the performance of average consensus algorithms over finite-sized practical WSNs.