Dynamical behavior, cost and magic number in average consensus

In this paper, we mainly study the influence of the number of links on the convergence rate and the total number of message exchanges, a surrogate for cost, in average consensus problems. For a wireless sensor network with fixed number of nodes, the number of links is effectively determined by the average vertex degree. Therefore the problem is converted to one of analyzing the influence of the average vertex degree on the convergence rate and the total number of message exchanges. To evaluate the convergence rate we use the ratio of two eigenvalues of the Laplacian matrix of the graph, for which we find lower and upper bounds in terms of the average vertex degree in regular networks, i.e. networks for which the associated graph has the same vertex degree for all vertices. Through theoretical analysis, we first observe that, unsurprisingly, the convergence rate will increase with increase in the number of average vertex degree. However the increment in the convergence rate drops dramatically as the number of average vertex degree becomes progressively larger. At the same time the total number of message exchanges in the consensus process will become large. For such a phenomenon we define a kind of Magic Number to help analyze the value or otherwise of adding more links to the network. The Monte Carlo simulation results are consistent with the theoretical analysis and demonstrate the magic number we defined exists not only in regular networks but also in different kinds of networks such as Erdös-Renýi networks and scale-free networks. Further we observe the magic number can be considered as a guide to minimize the total number of message exchanges while achieving a satisfactory convergence rate.