Distributed Averaging With Random Network Graphs and Noises

We consider a discrete-time distributed averaging algorithm over multi-agent networks with measurement noises and time-varying random graphs. Each agent updates its state by a weighted sum of pairwise state differences between its neighbors and itself with both additive and multiplicative measurement noises. The network structure is modeled by a sequence of time-varying random digraphs, which may be spatially and temporally dependent. By stochastic Lyapunov method and the combination of algebraic graph theory and martingale convergence theory, we obtain sufficient conditions for stochastic approximation type algorithms to achieve mean square and almost sure average consensus. We prove that all states of the agents converge to a common random variable, whose mathematical expectation is the average of initial values, in mean square and almost surely if the sequence of digraphs is conditionally balanced and uniformly conditionally jointly connected. An upper bound of the variance of the limit random variable, that is, the mean square steady-state error for stochastic average consensus is given quantitatively related to the weights, the algorithm gain and the energy level of the noises.