مقاله انگلیسی رایگان در مورد الگوریتم های Gossip بر اساس شنود در شبکه حسگر بی سیم

Abstract

In this paper, we present an eavesdropping-based gossip algorithm (EBGA). In the novel algorithm, when a node unicasts its values to a randomly selected neighboring node, all other nodes, which eavesdrop these values, simultaneously update their state values. By exploiting the broadcast nature of wireless communications, this novel algorithm has similar performance to broadcast gossip algorithms. Although broadcast gossip algorithms have the fastest rate of convergence among all gossip algorithms, they either converge to a random value rather than the average consensus, or need out-degree information available for each node to guarantee convergence to the average consensus. Utilizing non-negative matrix theory and ergodicity coefficient, we have proved that this novel algorithm can converge to the average consensus without any assumption which is difficult to be realized in real networks.

I. INTRODUCTION

For gossip algorithm, each node holds an estimating state value of the network. At the beginning, the initial state value is captured by each node. At one iteration, one node is randomly activated and exchanges state values with one of its randomly selected neighbors. By convex combination, these two nodes can update their state values to the average of their previous state values. By iterating this procedure, all nodes can eventually arrive at the average consensus that is the average of the initial state values at each node Copyright (c) 2012 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. The work was supported by the National Science Foundation of China under grant No. 61201147.

The authors are with the Department of Electronics and Information Engineering, Harbin Institute of Technology, Harbin 150001, China (e-mail: scwu@hit.edu.cn; liubo90113@126.com; x bai@hit.edu.cn; yuguanhou@hit.edu.cn). [1]. The drawback of this gossip algorithm is slow rate of convergence [2]. To accelerate convergence, eavesdropping method was first introduced by Deniz et al. in their greed gossip with eavesdropping (GGE) algorithms [3]. During the operation of GGE, when a node decides to gossip, instead of randomly choosing one of its neighbors, it chooses the node which has the state value most different from its own. Although GGE can accelerate convergence, it is still too slow to converge because only two nodes are allowed to exchange state values at each iteration.

To further accelerate convergence, a more competitive algorithm called broadcast gossip algorithm [4] was proposed. For broadcast gossip algorithms, when a node transmits its state value, all of its neighbors can hear about this state information and simultaneously update their state values. Although broadcast gossip algorithms have been studied for several years, the best trade-off between the rate of convergence and the error of convergence is still an open problem. As our knowledge, only three types of broadcast gossip algorithms have been proposed. One of them (called BGA-1 in the sequel) cannot converge to the average consensus [4]. Although recent research results indicate that the error upon the average in BGA-1 is small on large networks [5], we are more interested to propose a novel algorithm that can converge to the average consensus for any network in this paper. Another broadcast gossip algorithm (called BGA-2 in the sequel) converges more slowly than BGA-1, and no proof of convergence is available [6]. The third one (UBGA) proposed by us in a previous research [7] can converge to the average consensus with companion values and a strong assumption that all nodes should know its out-degree information (the same assumption is also needed for BGA-2), which is somewhat difficult to be satisfied in real networks. In this paper, we also utilize companion values as a compensation rule to preserve average consensus. This kind of compensation rules was firstly proposed for linear gossip algorithms in BGA-2. Then this method was further expanded for digraphs in [7] and [8]. All these algorithms can preserve average at the cost of out-degree information available for each node. All above drawbacks motivate us to propose a novel gossip algorithm that has the same rate of convergence as broadcast gossip algorithms and can be proven convergence to the average consensus without any assumption which is difficult to be realized.