Mean square performance of consensus-based distributed estimation over regular geometric graphs
Résumé
Average-consensus algorithms allow one to compute the average of some agents' data in a distributed way, and they are used as a basic building block in many algorithms for distributed estimation, load balancing, formation, and distributed control. Traditional analysis of such algorithms studies, for a given communication graph, the convergence rate (second largest eigenvalue of the transition matrix) and predicts that, for many graph families, performance degrades when the number of agents grows, because of the longer time required to spread information. However, in estimation problems, a growing number of sensor nodes improves the quality of the estimate. To understand whether such an improvement is possible also with distributed algorithms, it is important to specify a suitable performance metric, depending on the specific estimation problem in which the consensus algorithm is used, and to study how performance scales when both the number of iterations and the number of agents grow to infinity. Here, we propose a simple example of a distributed estimation problem solved by average-consensus, and a performance index naturally arising in this context (mean square estimation error, MSE). To understand the performance limitations of sensor networks with limited-range communications, we consider graphs describing local interactions. We give analytic results for some families of such graphs whose symmetries allow the use of suitable mathematical tools. However, simulations indicate that a similar behavior occurs also for random geometric graphs. This suggests that the performance limitations of regular lattices are mainly due to the geometrically local interactions and not to the symmetries.