Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy @math using @math radio transmissions, which reduces the energy consumption by a @math factor over standard gossip algorithms.
@cite_14: Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.
@cite_10: We study the distributed averaging problem on an arbitrary network with a gossip constraint, which means that no node communicates with more than one neighbour in every time slot. We consider algorithms which are linear iterations, where each iteration is described by a random matrix picked i.i.d. from some distribution. We derive conditions that this distribution must satisfy so that the sequence of iterations converges to the vector of averages in different senses. We then analyze a simple asynchronous randomized gossip algorithm for averaging, and show that the problem of optimizing the parameters of this algorithm for fastest convergence is a semi-definite program. Finally we study the relation between Markov chains and the averaging problem, and relate the averaging time of the algorithm to the mixing time of a related Markov chain on the graph.
In a series of papers @cite_14 @cite_10 , have analyzed the performance of standard gossip algorithms. Their fastest standard gossip algorithm for the ensemble of random geometric graphs @math has a @math -averaging time @cite_14 This quantity is computed in section IV.A of @cite_14 but the result is expressed in terms of absolute time units which needs to be multiplied by @math to become clock ticks. @math . For the @math in this paper this averaging time is @math . For @math scaling like @math for any @math , this averaging time scales likes @math . Note that in standard gossip, each gossip round corresponds to communication with only one-hop neighbor and hence costs only one radio transmission which means that the fastest standard gossip algorithm will have a total cost @math radio transmissions for @math . Therefore, our proposed algorithm saves a factor of @math in communication energy by exploiting geographic information.