Fast average consensus in clustered wireless sensor networks by superposition gossiping

In this paper we propose a gossip algorithm for average consensus in clustered wireless sensor networks called superposition gossiping, where the nodes in each cluster exploit the natural superposition property of wireless multiple-access channels to significantly decrease local averaging times. More precisely, the considered network is organized into single-hop clusters and in each cluster average values are computed at a designated cluster head via the wireless channel and subsequently broadcasted to update the entire cluster. Since the clusters are activated randomly in a time division multiple-access fashion, we can apply well-established techniques for analyzing gossip algorithms to prove the convergence of the algorithm to the average consensus in the second moment and almost surely, provided that some connectivity condition between clusters is fulfilled. Finally, we follow a semidefinite programming approach to optimize wake up probabilities of cluster heads that further accelerates convergence.