Adaptive consensus and algebraic connectivity estimation in sensor networks with chebyshev polynomials

Abstract — In the recent years a lot of effort has been devoted to the problem of finding distributed algorithms that achieve a fast consensus. The distributed evaluation of polynomials improves the convergence speed to the consensus keeping the good properties of standard methods. The drawback about using polynomials is that they usually require some knowledge about the network in order to have good convergence prop-erties. In this paper we consider the consensus method using Chebyshev polynomials and present an algorithm to compute, in a distributed way, the parameters that make the method get the optimal convergence rate. One of the parameters coincides with the second largest eigenvalue of the weight matrix, i.e., the algebraic connectivity, and we prove the convergence of the algorithm to it. We also present three variants of the algorithm to converge to this parameter in a faster way and to consider changes in the communication topology. We evaluate our algorithm in a simulated environment showing its performance in a wide set of networks