Abstract
IEEE J. Select. Topics Signal Processing, vol. 7, no. 2, pp.
284-295, Apr. 2013 We carry out a comprehensive study of the resource cost of averaging
consensus in wireless networks. Most previous approaches suppose a graphical
network, which abstracts away crucial features of the wireless medium, and
measure resource consumption only in terms of the total number of transmissions
required to achieve consensus. Under a path-loss dominated model, we study the
resource requirements of consensus with respect to three wireless-appropriate
metrics: total transmit energy, elapsed time, and time-bandwidth product. First
we characterize the performance of several popular gossip algorithms, showing
that they may be order-optimal with respect to transmit energy but are strictly
suboptimal with respect to elapsed time and time-bandwidth product. Further, we
propose a new consensus scheme, termed hierarchical averaging, and show that it
is nearly order-optimal with respect to all three metrics. Finally, we examine
the effects of quantization, showing that hierarchical averaging provides a
nearly order-optimal tradeoff between resource consumption and quantization
error.