Efficiency of the gossip algorithm for wireless sensor networks

Gossip is a well-known technique for distributed computing in an arbitrarily connected network of nodes. The gossip algorithm, which is very simple to implement, takes into account strong limitations in computational, communication and energy resources that usually characterize nodes in sensor networks. In gossip, the computational burden is distributed among the nodes, and computation and communication are managed in a very quick and efficient way: in essence, each node acquires its own measure and, starting from it, exchanges information with its neighbors, according with a connection probability distribution. In this paper, we study the performance of gossip algorithms, aiming to test the agreement between analytical results on the averaging time and the actual convergence time for specific scenarios, estimated through numerical simulations. Furthermore, we apply an optimization technique, recently appeared in the literature, that theoretically allow to accelerate convergence. Numerical simulations permit to assess the effects of optimization in real cases, thus evaluating the actual improvement in performance it achieves.