Distributed Spectral Radius Estimation in Wireless Sensor Networks

A distributed algorithm to compute the spectral radius of the graph in the presence of additive channel noise is proposed. The spectral radius of the graph is the eigenvalue with the largest magnitude of the adjacency matrix, and is a useful characterization of the network graph. Conventionally, centralized methods are used to compute the spectral radius, which involves eigenvalue decomposition of the adjacency matrix of the underlying graph. We devise an algorithm to reach consensus on the spectral radius of the graph using only local neighbor communications, both in the presence and absence of additive channel noise. The algorithm uses a distributed max update to compute the growth rate in the node state values and then performs a specific update to converge on the logarithm of the spectral radius. The algorithm works for any connected graph structure. Simulation results supporting the theory are also presented.