Distributed Average Consensus in Sensor Networks with Random Link Failures

摘要

We study the impact of the topology of a sensor network on distributed average consensus algorithms when the network links fail at random. We derive convergence results. In particular, we determine a sufficient condition for mean-square convergence of the distributed average consensus algorithm in terms of a moment of the distribution of the norm of a function of the network graph Laplacian matrix L (which is a random matrix, because the network links are random.) Further, because the computation of this moment involves costly simulations, we relate the mean-square convergence to the second eigenvalue of the mean Laplacian matrix, lambda₂(Lmacr), which is much easier to compute. We derive bounds on the convergence rate of the algorithm, which show that both the expected algebraic connectivity of the network, E[lambda₂(L)], and lambda₂(Lmacr) play an important role in determining the actual convergence rate. Specifically, larger values of E[lambda₂(L)] or lambda₂(Lmacr) lead to better convergence rates. Finally, we provide numerical studies that verify the analytical results