Sensor Networks With Random Links: Topology Design for Distributed Consensus

By Soummya Kar, José M. F. Moura. 2007

273 citations recorded by the source corpus.

In a sensor network, in practice, the communication among sensors is subject to: 1) errors that can cause failures of links among sensors at random times; 2) costs; and 3) constraints, such as power, data rate, or communication, since sensors and networks operate under scarce resources. The paper studies the problem of designing the topology, i.e., assigning the probabilities of reliable communication among sensors (or of link failures) to maximize the rate of convergence of average consensus, when the link communication costs are taken into account, and there is an overall communication budget constraint. We model the network as a Bernoulli random topology and establish necessary and sufficient conditions for mean square sense (mss) and almost sure (a.s.) convergence of average consensus when network links fail. In particular, a necessary and sufficient condition is for the algebraic connectivity of the mean graph topology to be strictly positive. With these results, we show that the topology design with random link failures, link communication costs, and a communication cost constraint is a constrained convex optimization problem that can be efficiently solved for large networks by semidefinite programming techniques. Simulations demonstrate that the optimal design improves significantly the convergence speed of the consensus algorithm and can achieve the performance of a non-random network at a fraction of the communication cost.

Subfields: Computer Networks and Communications

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

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “A common practice is to use an equal weight mixing matrix as [5, 10, 29]: where j L j denotes the graph Laplacian at the k -th iteration.”
Decentralized Consensus Optimization With Asynchrony and Delays (2016, background): “Gossip [15], [16] Reduced No Yes Average Consensus Yes Randomized Consensus [17], [18] Reduced No Yes Average Consensus Yes Randomized DGD [19], [26] Reduced No Yes Aggregate Optimization No Asynchronous Diffusion [27]–[29] Reduced No Yes Aggregate stochastic Optimization No Randomized ADMM [20], [2”
Broadcast Gossip Algorithms for Consensus (2009, background): “A fundamental problem in decentralized networked systems is that of having nodes reach a state of agreement [3]–[9].”
Adaptation, Learning, and Optimization over Networks (2014, background): “There exist several studies in the literature on the performance of consensus and gossip-type strategies in response to asynchronous events or changing topologies [43, 124, 134, 135, 137, 138, 196, 227, 243].”
Decentralized consensus optimization with asynchrony and delays (2016, background): “Likewise, our setting is different from randomized multi-activation such as [17], [18] for consensus averaging, and [19]–[22] for consensus optimization, which activate multiple edges each time and still do not allow any delay.”
Excess-Risk of Distributed Stochastic Learners (2013, methodology): “Following the approach of [14], [32], [34], the diffusion strategy for evaluating distributed estimates wk,i for wo in (4) takes the following form: ψk,i=wk,i−1−µ(i)∇wQ(wk,i−1,xk,i) [adaptation] (10) wk,i= N∑ `=1 a`kψ`,i [aggregation] (11) where xk,i denotes the current data sample available at…”
Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication (2008, methodology): “The LU algorithm can be regarded as a generalization of consensus algorithms (se e, for example, [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17]), the latter being a specific cas e of theLU with no innovations.”
Gossip Algorithms for Distributed Signal Processing (2010, background): “) and correlated models, symmetric and asymmetric] [56]– [65].”
Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise (2007, methodology): “IT ] 8 The paper studies average consensus with random topologies(int rmittent links)andnoisy channels.”