Controlled Hopwise Averaging: Bandwidth/Energy-Efficient Asynchronous Distributed Averaging for Wireless Networks

This paper addresses the problem of averaging numbers across a wireless network from an important, but largely neglected, viewpoint: bandwidth/energy efficiency. We show that existing distributed averaging schemes are inefficient, producing networked dynamical systems that evolve with wasteful communications. To improve efficiency, we develop Controlled Hopwise Averaging (CHA), a distributed asynchronous algorithm that attempts to "make the most" out of each transmission. Unlike the existing schemes, CHA fully exploits the broadcast nature of wireless medium and enables greedy, decentralized, feedback control of when to initiate an iteration. We show that CHA admits a common quadratic Lyapunov function for analysis and control, establish its exponential convergence, and characterize its worst-case convergence rate. Finally, through extensive simulation on random geometric graphs, we show that CHA is substantially more efficient than several existing schemes, requiring far fewer transmissions to complete an averaging task.