Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise

The paper studies average consensus with random topologies (intermittent links) and noisy channels. Consensus with noise in the network links leads to the bias-variance dilemma-running consensus for long reduces the bias of the final average estimate but increases its variance. We present two different compromises to this tradeoff: the A - ND algorithm modifies conventional consensus by forcing the weights to satisfy a persistence condition (slowly decaying to zero;) and the A - NC algorithm where the weights are constant but consensus is run for a fixed number of iterations (i) over cap, then it is restarted and rerun for a total of (p) over cap runs, and at the end averages the final states of the (p) over cap runs (Monte Carlo averaging). We use controlled Markov processes and stochastic approximation arguments to prove almost sure convergence of A - ND to a finite consensus limit and compute explicitly the mean square error (mse) (variance) of the consensus limit. We show that A - ND represents the best of both worlds-zero bias and low variance-at the cost of a slow convergence rate; rescaling the weights balances the variance versus the rate of bias reduction (convergence rate). In contrast, A - NC, because of its constant weights, converges fast but presents a different bias-variance tradeoff. For the same number of iterations (i) over cap(p) over cap, shorter runs (smaller (i) over cap) lead to high bias but smaller variance (larger number (p) over cap of runs to average over.) For a static nonrandom network with Gaussian noise, we compute the optimal gain for A - NC to reach in the shortest number of iterations (i) over cap(p) over cap, with high probability (1 - delta), (epsilon, delta)-consensus (epsilon residual bias). Our results hold under fairly general assumptions on the random link failures and communication noise.