Controlled Hopwise Averaging: Bandwidth/energy-efficient asynchronous distributed averaging for wireless networks
Choon Yik Tang, Jie Lu · 2009
This paper addresses the problem of averaging numbers across a wireless network from an important, but largely neglected, viewpoint:bandwidth/energyefficiency. We show that existing distributed averaging schemes are inefficient, producing networked dynamical systems that evolve with wasteful communications. To improve efficiency, we developcontrolledHopwiseaveraging(CHA), a distributed asynchronous algorithm that attempts to ldquomake the mostrdquo 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.