Match!

Max Consensus in the Presence of Additive Noise

Published on Oct 1, 2018
· DOI :10.1109/acssc.2018.8645297
Gowtham Muniraju3
Estimated H-index: 3
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
(ASU: Arizona State University)
+ 2 AuthorsMahesh K. Banavar14
Estimated H-index: 14
(Clarkson University)
Abstract
The analysis of a distributed consensus algorithm for estimating the maximum of the node initial state values in a network is considered in the presence of communication noise. Conventionally, the maximum is estimated by updating the node state value with the largest received measurements in every iteration at each node. However, due to additive channel noise, the estimate of the maximum at each node has a positive drift at each iteration and this results in nodes diverging from the true max value. Max-plus algebra is used to study this ergodic process, wherein, at each iteration, the state values are multiplied by a random matrix characterized by the noise distribution. The growth rate of the state values due to noise is studied by analyzing the Lyapunov exponent of the product of noise matrices in a max-plus semiring. The growth rate of the state values is bounded by a constant which depends on the spectral radius of the network and the noise variance. Simulation results supporting the theory are also presented.
  • References (10)
  • Citations (1)
📖 Papers frequently viewed together
2003
3 Authors (P.I. Hubscher, ..., J.C.M. Bermudez)
7 Citations
9 Citations
78% of Scinapse members use related papers. After signing in, all features are FREE.
References10
Newest
#1Xue ZhangH-Index: 7
Last. Gowtham MunirajuH-Index: 3
view all 5 authors...
In this paper, localization using narrowband communication signals are considered in the presence of fading channels with time of arrival measurements. When narrowband signals are used for localization, due to existing hardware constraints, fading channels play a crucial role in localization accuracy. In a location estimation formulation, the Cramer-Rao lower bound for localization error is derived under different assumptions on fading coefficients. For the same level of localization accuracy, t...
1 Citations
#1Sai Zhang (Qualcomm)H-Index: 2
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 26
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 28
view all 3 authors...
A fully distributed algorithm for estimating the center and the radius of the smallest sphere that contains a wireless sensor network is proposed. The center finding problem is formulated as a convex optimization problem in summation form by using a soft-max approximation to the maximum function. Diffusion adaptation method is used where states of nodes converge to the estimated center distributively. Then, distributed max consensus is used to compute the radius. The proposed algorithm is fully ...
3 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 3
#2Sai Zhang (ASU: Arizona State University)H-Index: 5
view all 7 authors...
A distributed spectral clustering algorithm to group sensors based on their location in a wireless sensor network (WSN) is proposed. For machine learning and data mining applications in WSN's, gathering data at a fusion center is vulnerable to attacks and creates data congestion. To avoid this, we propose a robust distributed clustering method without a fusion center. The algorithm combines distributed eigenvector computation and distributed K-means clustering. A distributed power iteration meth...
5 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 3
#2Sunil Rao (ASU: Arizona State University)H-Index: 4
Last. Devarajan SrinivasanH-Index: 5
view all 8 authors...
5 CitationsSource
#1Xue Zhang (ASU: Arizona State University)H-Index: 7
Last. Mahesh K. Banavar (Clarkson University)H-Index: 14
view all 3 authors...
In sensor network applications, measured data are often meaningful only when the location is accurately known. In this booklet, we study research problems associated with node localization in wireless sensor networks. We describe sensor network localization problems in terms of a detection and estimation framework and we emphasize specifically a cooperative process where sensors with known locations are used to localize nodes at unknown locations. In this class of problems, even if the location ...
15 Citations
#1Sai Zhang (ASU: Arizona State University)H-Index: 5
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 26
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 28
view all 4 authors...
A distributed consensus algorithm for estimating the maximum value of the initial measurements in a sensor network with communication noise is proposed. In the absence of communication noise, max estimation can be done by updating the state value with the largest received measurements in every iteration at each sensor. In the presence of communication noise, however, the maximum estimate will incorrectly drift and the estimate at each sensor will diverge. As a result, a soft-max approximation to...
20 CitationsSource
This paper deals with the analysis of the convergence properties of the max-consensus protocol in presence of asynchronous updates and bounded time delays on directed static networks. The work is motivated by real-world applications in distributed decision-making systems, for which max-consensus is an effective paradigm. The main result of this paper is that the strongly connectedness of the directed communication network is a sufficient condition for the asynchronous max-consensus protocol to l...
19 CitationsSource
#1Franck Iutzeler (ENST: Télécom ParisTech)H-Index: 9
#2Philippe Ciblat (ENST: Télécom ParisTech)H-Index: 27
Last. J. Jakubowicz (Telecom SudParis)H-Index: 2
view all 3 authors...
In this paper, we address the problem of estimating the maximal value over a sensor network using wireless links between them. We introduce two heuristic algorithms and analyze their theoretical performance. More precisely, i) we prove that their convergence time is finite with probability one, ii) we derive an upper-bound on their mean convergence time, and iii) we exhibit a bound on their convergence time dispersion.
66 CitationsSource
#1Reza Olfati (Dartmouth College)H-Index: 33
#2J. Alexander FaxH-Index: 5
Last. Richard M. Murray (California Institute of Technology)H-Index: 83
view all 3 authors...
This paper provides a theoretical framework for analysis of consensus algorithms for multi-agent networked systems with an emphasis on the role of directed information flow, robustness to changes in network topology due to link/node failures, time-delays, and performance guarantees. An overview of basic concepts of information consensus in networks and methods of convergence and performance analysis for the algorithms are provided. Our analysis framework is based on tools from matrix theory, alg...
6,422 CitationsSource
#1Bernd HeidergottH-Index: 14
Max-Plus Algebra.- Max-Plus Linear Stochastic Systems.- Ergodic Theory.- Perturbation Analysis.- A Max-Plus Differential Calculus.- Higher-Order D-Derivatives.- Taylor Series Expansions.
47 CitationsSource
Cited By1
Newest
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 3
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 26
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 28
view all 3 authors...
A distributed algorithm to compute the spectral radius of the graph in the presence of additive channel noise is proposed. The spectral radius of the graph is the eigenvalue with the largest magnitude of the adjacency matrix, and is a useful characterization of the network graph. Conventionally, centralized methods are used to compute the spectral radius, which involves eigenvalue decomposition of the adjacency matrix of the underlying graph. We devise an algorithm to reach consensus on the spec...
Source
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 3
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 26
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 28
view all 3 authors...
A novel distributed algorithm for estimating the maximum of the node initial state values in a network, in the presence of additive communication noise is proposed. Conventionally, the maximum is estimated locally at each node by updating the node state value with the largest received measurements in every iteration. However, due to the additive channel noise, the estimate of the maximum at each node drifts at each iteration and this results in nodes diverging from the true max value. Max-plus a...