Convergence Rate Analysis for Periodic Gossip Algorithms in Wireless Sensor Networks.

Periodic gossip algorithms have generated a lot of interest due to their ability to compute the global statistics by using local pair wise communications among nodes. Simple execution, robustness to topology changes, and distributed nature make these algorithms quite suitable to wireless sensor networks (WSN). However, these algorithms converge to the global statistics after certain rounds of pair-wise communications among sensor nodes. A major challenge for periodic gossip algorithms is difficulty to predict the convergence rate for large scale networks. To facilitate the convergence rate evaluation, we study a onedimensional lattice network model. In this scenario, in order to derive the explicit formula for convergence rate, we have to obtain a closed form expression for second largest eigenvalue of perturbed pentadiagonal matrices. In our approach, we derive the explicit expressions of eigenvalues by exploiting the theory of recurrent sequences. Unlike the existing approaches in literature, this is a direct method which avoids theory of orthogonal polynomials. Finally, we derive the explicit expressions for convergence rates of average periodic gossip algorithm in one-dimensional WSNs. Further, we extend our analysis by considering the linear weight updating approach and investigate the impact of link weights on the convergence rates for different number of nodes.