Distributed Consensus Algorithms in Sensor Networks: Quantized Data and Random Link Failures

By Soummya Kar, José M. F. Moura. IEEE Transactions on Signal Processing, 2007

437 citations recorded by the source corpus.

The paper studies the problem of distributed average consensus in sensor networks with quantized data and random link failures. To achieve consensus, dither (small noise) is added to the sensor states before quantization. When the quantizer range is unbounded (countable number of quantizer levels), stochastic approximation shows that consensus is asymptotically achieved with probability one and in mean square to a finite random variable. We show that the mean-squared error (mse) can be made arbitrarily small by tuning the link weight sequence, at a cost of the convergence rate of the algorithm. To study dithered consensus with random links when the range of the quantizer is bounded, we establish uniform boundedness of the sample paths of the unbounded quantizer. This requires characterization of the statistical properties of the supremum taken over the sample paths of the state of the quantizer. This is accomplished by splitting the state vector of the quantizer in two components: one along the consensus subspace and the other along the subspace orthogonal to the consensus subspace. The proofs use maximal inequalities for submartingale and supermartingale sequences. From these, we derive probability bounds on the excursions of the two subsequences, from which probability bounds on the excursions of the quantizer state vector follow. The paper shows how to use these probability bounds to design the quantizer parameters and to explore tradeoffs among the number of quantizer levels, the size of the quantization steps, the desired probability of saturation, and the desired level of accuracy ¿ away from consensus. Finally, the paper illustrates the quantizer design with a numerical study.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/0d0ff1baa4fea4df9a55588fc30f9d51772257a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Asynchronous Gossip-Based Random Projection Algorithms Over Networks (2013, background): “INTRODUCTION A number of important problems that arise in various applica tion domains, including distributed control [6], large-scale machine learning [7], [2 1], wired and wireless networks [9], [10], [22], [23] can be formulated as a distributed convex constra ined minimization problem over a mul”
Performance of a Distributed Stochastic Approximation Algorithm (2012, neutral): “There is a rich literature on distributed estimation and optimization algorithms, see [7],[8], [9], [10], [11], [12], [13] as a non exhaustive list.”
Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication (2008, methodology): “We propose and study two generic recursive distributed iterative estimation algorithms in this paper, namely,NU andNLU for distributed parameter estimation with possibly nonlinear observation models at each sensor.”
Design and analysis of distributed averaging with quantized communication (2014, background): “A number of papers have studied this quantized consensus problem and various probabilistic strategies have been proposed to cause all the agents in a network to reach a quantized consensus with probability one (or at least with high probability) [2], [3], [13], [18]–[20].”
Distributed Average Consensus With Quantization Refinement (2013, background): “A different approach for dealing with the quantization noise and additive white noise in general is proposed in [13] and [14] respectively.”
Distributed Quantized Weight-Balancing and Average Consensus Over Digraphs (2018, background): “While substantially different, the schemes [10]–[13] can only converge (in a deterministic or probabilistic sense) to the quantized average of the initial nodes’ values.”
Gossip consensus algorithms via quantized communication (2009, background): “(9) 2 Elsewhere in the literature [1,8,16] this quantizer has been introduced as a result of dithering, that is the addition of a small random noise before (deterministic) quantization.”
Distributed averaging on digital erasure networks (2011, background): “…the cases of quantized communication (Aysal, Coates, & Rabbat, 2008; Carli, Bullo, & Zampieri, 2010; Frasca, Carli, Fagnani, & Zampieri, 2009; Kar & Moura, 2010; Li, Fu, Xie, & Zhang, in press), or transmission affected by additive noise (Huang & Manton, 2009; Kar & Moura, 2009; Rajagopal &…”
Gossip Algorithms for Distributed Signal Processing (2010, background): “To overcome the fact that not all nodes end up having the same quantized value, a simple variant on the quantized consensus problem that guarantees almost sure convergence to a unique consensus point was proposed concurrently in [74] and [75].”
Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization (2011, background): “More recently, numerous works extended this kind of algorithm to more involved multi-agent scenarios, see [19], [23], [25], [26], [32], and [38] for a non-exhaustive list.”
Distributed Network Optimization With Heuristic Rational Agents (2012, background): “We note that other efforts to lift unrealistic assumptions in distributed network optimization exist.”
Social learning and distributed hypothesis testing (2014, background): “uch as distributed learning [16], [17], general function evaluation [18], stochastic approximations [19]. Message passing protocols may be synchronous or asynchronous (such as the “gossip” model [20]–[24]). This graphical model of the communication, instead of a assuming a detailed physicallayer for”
Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents (2018, background): “The randomness can be attributed to either the randomness of the time-varying graph G t , e.g., random link failures in sensor networks (Kar and Moura, 2010), or the randomness of the consensus algorithms, e.g., randomized gossip schemes (Boyd et al., 2006).”