Distributed wireless sensor networks are an essential part of modern Internet-of-Things (IoT) and sensor fusion systems. In such networks, all the distributed agents have to reach consensus on a value of interest. The spectral radius of the graph is the largest eigenvalue of the adjacency matrix, and is a useful characterization of the network graph. Knowledge of spectral radius is needed to study graph coloring methods, properties of Hamiltonian paths in distributed networks, and to understand the convergence properties of belief propagation algorithms. Conventional systems for estimating the spectral radius of the graph include distributed power iteration. This can be done in a two-step process, by first computing the principal eigenvector and then estimating the spectral radius. This iterative method is computationally expensive, as the norm of the state value vector needs to be computed using consensus methods between iterations.
Researchers at Arizona State University have developed a distributed algorithm to more efficiently compute the spectral radius of a network. The method relies on local updates from neighboring nodes in a network to iteratively update state values of each node in a network and estimate a spectral radius of the network with guaranteed convergence. The method is a distributed method that efficiently converges to an invertible function of the spectral radius based only on local communications for digital communication models in the presence and/or absence of packet loss. Furthermore, insights on convergence are provided by proving that the convergence error is a function of the principal eigenvector of the adjacency matrix. Packet loss and imperfect communications are modeled as time-varying graphs, and convergence is analyzed accordingly.
Related publication: Consensus Based Distributed Spectral Radius Estimation
Potential Applications:
- Wireless sensor networks
- Internet-of-Things (IoT)
- Solar array monitoring systems
- Cyber-physical systems (CPS)
Benefits and Advantages:
- Algorithm converges to the correct value in the presence of packet loss
- Restricts state values within the dynamic range
- Requires only local communications