Research On Gossip Algorithms For Distributed Average Consensus Problem

The distributed average consensus problem is very important for wirelesssensor networks. It aims to make distributed nodes in the network reach a state ofagreement which is the initial average of local state. The distributed averageconsensus problem has many relevant applications in wireless sensor networks, forexample, parameter estimation, location, synchronization and so on. It may cause alot of overhead on routing and bottleneck problem if we just aggregationinformation to a selected node. Gossip algorithm takes advantage of the node’slocal computing capability to make nodes reach the state of consensus only byexchanging information between neighbor nodes which are randomly selected inthe network, thus avoiding the overhead on routing and bottleneck problem. Itattracts much attention for its excellent properties in distributed informationprocessing.In this paper, we firstly establish the model of distributed average consensusproblem and network topology, and then analyze the convergence and convergencerate of several typical Gossip algorithms. It shows that pair-wise gossip canconverge to the initial average of local state, but the convergence rate is very slow.However, broadcast-based gossip algorithms converge much faster but there is nobroadcast-based gossip algorithm can be proved to converge to the averageconsensus state. In order to overcome the drawbacks of broadcast-based Gossipalgorithms, we present an Eavesdropping-based broadcast gossip algorithm. Thealgorithm combines the main idea of using the broadcast nature of wirelesschannel in broadcast-based gossip algorithms with the update model of pair-wiserandomly selected neighbors in pair-wise gossip algorithms. The convergence ofthe algorithm has been proved by using the method of ergodicity coefficients.Although the mathematical expressions of convergence rate is still unknown due tothe node’s wakeup probability affected by the specific network topology but theconvergence rate is compared with several existing algorithms by simulations.Simulation results show that the proposed algorithm has the best normalized meansquare error (N-MSE) performance in geometric random graph. As the number ofnodes increases the convergence rate become slower but the overall performance isstill good considering the unknown topology of the network. The algorithm is alsorobust to packet loss during communication which improves the practical value. Atlast, we introduces the implement of the proposed algorithm on ARM and makessome test on convergence performance.