Distributed computation of averages over ad hoc networks

In this paper, we develop algorithms for distributed computation of averages of the node data over networks with arbitrary but fixed connectivity. The algorithms we develop are linear dynamical systems that generate sequences of improving approximations to the desired computation at each node, via iterative processing and broadcasting. The algorithms are locally constructed at each node by exploiting only locally available and macroscopic information about the network topology. We present methods for optimizing the convergence rates of these algorithms to the desired computation, and evaluate their performance characteristics in the context of a problem of signal estimation from multinode noisy observations. By conducting simulations based on simple power-loss propagation models, we perform a preliminary comparison of the algorithms we develop against other types of distributed algorithms for computing averages, and identify transmit-power optimized algorithmic implementations as a function of the size and density of the sensor network.