Max Consensus in Sensor Networks: Non-Linear Bounded Transmission and Additive Noise

Published on Dec 15, 2016in IEEE Sensors Journal3.073
· DOI :10.1109/JSEN.2016.2612642
Sai Zhang7
Estimated H-index: 7
(ASU: Arizona State University),
Cihan Tepedelenlioglu28
Estimated H-index: 28
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias32
Estimated H-index: 32
(ASU: Arizona State University)
Sources
Abstract
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 together with a non-linear consensus algorithm is introduced herein. A design parameter controls the tradeoff between the soft-max error and convergence speed. An analysis of this tradeoff gives a guideline toward how to choose the design parameter for the max estimate. We also show that if some prior knowledge of the initial measurements is available, the consensus process can converge faster by using an optimal step size in the iterative algorithm. A shifted non-linear bounded transmit function is also introduced for faster convergence when sensor nodes have some prior knowledge of the initial measurements. Simulation results corroborating the theory are also provided.
📖 Papers frequently viewed together
6,422 Citations
87 Citations
2009
46 Citations
References27
Newest
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...
26 CitationsSource
Nov 1, 2014 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
#1Mojtaba Shirazi (UCF: University of Central Florida)H-Index: 6
#2Azadeh Vosoughi (UCF: University of Central Florida)H-Index: 14
In this paper we study the problem of distributed estimation of a random vector in wireless sensor networks (WSNs) with non-linear observation model. Sensors transmit their binary modulated quantized observations over orthogonal erroneous wireless channels (subject to fading and noise) to a fusion center, which is tasked with estimating the unknown vector. We derive the Bayesian Cramer-Rao Bound (CRB) matrix and study the behavior of its trace (through analysis and simulations), with respect to ...
10 CitationsSource
#1Sivaraman Dasarathan (ASU: Arizona State University)H-Index: 4
#2Cihan Tepedelenliolu (ASU: Arizona State University)H-Index: 1
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 4 authors...
A distributed average consensus algorithm in which every sensor transmits with bounded peak power is proposed. In the presence of communication noise, it is shown that the nodes reach consensus asymptotically to a finite random variable whose expectation is the desired sample average of the initial observations with a variance that depends on the step size of the algorithm and the variance of the communication noise. The asymptotic performance is characterized by deriving the asymptotic covarian...
17 CitationsSource
Wireless sensor network applications often involve the computation of pre-defined functions of the measurements such as for example the arithmetic mean or maximum value. Standard approaches to this problem separate communication from computation: digitized sensor readings are transmitted interference-free to a fusion center that reconstructs each sensor reading and subsequently computes the sought function value. Such separation-based computation schemes are generally highly inefficient as a com...
97 CitationsSource
#1Guodong ShiH-Index: 26
In this paper, we formulate and investigate a generalized consensus algorithm which makes an attempt to unify distributed averaging and maximizing algorithms considered in the literature. Each node iteratively updates its state as a time-varying weighted average of its own state, the minimal state, and the maximal state of its neighbors. In Part I of the paper, time-dependent graphs are studied. This part of the paper focuses on state-dependent graphs. We use a μ-nearest-neighbor rule, where eac...
9 CitationsSource
#1Zhao Dengchang (CAS: Chinese Academy of Sciences)H-Index: 1
#2An Zhulin (CAS: Chinese Academy of Sciences)H-Index: 1
Last. Xu Yongjun (CAS: Chinese Academy of Sciences)H-Index: 5
view all 3 authors...
This paper proposes a novel distributed time synchronization scheme for wireless sensor networks, which uses max consensus to compensate for clock drift and average consensus to compensate for clock offset. The main idea is to achieve a global synchronization just using local information. The proposed protocol has the advantage of being totally distributed, asynchronous, and robust to packet drop and sensor node failure. Finally, the protocol has been implemented in MATLAB. Through several simul...
31 CitationsSource
Jan 1, 2013 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 4 authors...
A distributed consensus algorithm for estimating the maximum and the minimum of the initial measurements in a sensor network is proposed. Estimating extrema is useful in many applications such as temperature control. 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 may incorrectly drift to a larger value at ea...
12 CitationsSource
#1Franck Iutzeler (ENST: Télécom ParisTech)H-Index: 13
#2Philippe Ciblat (ENST: Télécom ParisTech)H-Index: 30
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.
87 CitationsSource
#1Matias Korman (UPC: Polytechnic University of Catalonia)H-Index: 13
We consider a topology control problem in which we are given a set of sensors in R^d and we would like to assign a communication radius to each of them so that they generate a connected network and have low receiver-based interference (defined as the largest in-degree of the network). We show that any radii assignment that generates a connected network can be modified so that interference is (asymptotically) unaffected and no sensor is assigned communication radius larger than R"m"i"n, where R"m...
9 CitationsSource
#1Antonis Papachristodoulou (University of Oxford)H-Index: 45
#2Ali Jadbabaie (UPenn: University of Pennsylvania)H-Index: 65
Last. Ulrich Münz (University of Stuttgart)H-Index: 18
view all 3 authors...
The coordinated motion of multi-agent systems and oscillator synchronization are two important examples of networked control systems. In this technical note, we consider what effect multiple, non-commensurate (heterogeneous) communication delays can have on the consensus properties of large-scale multi-agent systems endowed with nonlinear dynamics. We show that the structure of the delayed dynamics allows functionality to be retained for arbitrary communication delays, even for switching topolog...
201 CitationsSource
Cited By27
Newest
#1Yu Wu (Chongqing University)H-Index: 8
#2Jinzhan Gou (Chongqing University)H-Index: 1
Last. Yanting Huang (Beihang University)H-Index: 1
view all 4 authors...
Abstract Unmanned aerial vehicle (UAV) formation has a wide range of applications as it can increase the success rate of task and improve the reliability of system. Formation control and obstacle avoidance are two related key problems and are studied based on the consensus theory in this paper. First, two forms of kinetic models for UAV are described, and the standard model and the model with autopilot are deployed to apply in obstacle avoidance and formation control respectively. The constraint...
1 CitationsSource
#1Diego Deplano (University of Cagliari)H-Index: 3
#2Mauro Franceschelli (University of Cagliari)H-Index: 16
Last. Alessandro Giua (University of Cagliari)H-Index: 53
view all 3 authors...
In this paper we propose a novel consensus protocol for discrete-time multi-agent systems (MAS), which solves the dynamic consensus problem on the max value, i.e., the dynamic max-consensus problem. In the dynamic max-consensus problem to each agent is fed a an exogenous reference signal, the objective of each agent is to estimate the instantaneous and time-varying value of the maximum among the signals fed to the network, by exploiting only local and anonymous interactions among the agents. The...
1 Citations
#1Ehsan FayaziBarjini (Shahid Beheshti University)H-Index: 1
#2Davood Gharavian (Shahid Beheshti University)H-Index: 9
Last. Mohammadbagher Shahgholian (Shahid Beheshti University)H-Index: 2
view all 3 authors...
In this paper, we present a new method for tracking moving target in a wireless sensor network based on the combination of Non-dominated Sorting Genetic Algorithm II (NSGA-II) and Generalized Extended Kalman Filter (GEKF) (NGEKF). GEKF is one of the best positioning algorithm but using all sensors in target tracking and high energy consumption are its drawbacks. To overcome these drawbacks, the sensor scheduling problem is considered as finding the optimal sequence of the sensors to estimate the...
2 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 6
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
view all 3 authors...
A consensus based distributed algorithm to compute the spectral radius of a network is proposed. The spectral radius of the graph is the largest eigenvalue 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. Our distributed algorithm uses a simple update rule to reach consensus on the spectral radius, usi...
3 CitationsSource
#1Martin Kenyeres (SAV: Slovak Academy of Sciences)H-Index: 3
#2Jozef KenyeresH-Index: 4
Finding the extrema in a distributed fashion over multi-agent systems poses an important part of many real-life applications. In this paper, we analyze the robustness of synchronous distributed consensus algorithms for extrema finding to random communication breakdowns between entities forming multi-agent systems. We analyze the impact of communication breakdowns with a varying probability of the occurrence on the precision of the algorithms and the convergence rate expressed as the number of th...
Source
#1Xiaoying Shi (THU: Tsinghua University)H-Index: 2
#2Yinliang Xu (THU: Tsinghua University)H-Index: 26
Last. Hongbin Sun (THU: Tsinghua University)H-Index: 43
view all 3 authors...
The advent of distributed energy resources encourages the direct energy transaction among grid subscribers, who may play interchangeable roles as energy producers and consumers (prosumers). Since microgrids integrated with distributed energy resources can offer diverse options, it is desirable to design a proper energy transaction protocol to minimize the cost of prosumers. This paper proposes a discrete biased min-consensus algorithm to discover the best supply candidate with minimum power loss...
12 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 6
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
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...
4 CitationsSource
#1Gowtham Muniraju (ASU: Arizona State University)H-Index: 6
#2Cihan Tepedelenlioglu (ASU: Arizona State University)H-Index: 28
Last. Andreas Spanias (ASU: Arizona State University)H-Index: 32
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...
2 CitationsSource
#1Qian Cui (Chongqing University)H-Index: 3
#2Jiangshuai Huang (Chongqing University)H-Index: 1
Last. Tingting GaoH-Index: 2
view all 3 authors...
This paper investigates the distributed min-consensus for second-order nonlinear multi-agent systems with external disturbances. A discontinuous integral sliding mode (ISM) protocol combined with finite-time stability theory is applied and a novel min-consensus algorithm is proposed in this paper. To eliminate the chattering phenomenon due to the discontinuous control, a continuous ISM consensus protocol is proposed. It is shown that output of the agents reach a common min-consensus of their ini...
Source
#1Amirhosein Golfar (IUT: Isfahan University of Technology)H-Index: 1
#2Jafar Ghaisari (IUT: Isfahan University of Technology)H-Index: 12
ABSTRACTIn the presence of probabilistic communication networks between agents, the convergence analysis of max-consensus algorithm (MCA) is addressed in this paper. It is considered that at each iteration of MCA, all agents share their measurements with adjacent agents via local communication networks which is applicable in many multi-agent systems (MASs). It is assumed that the communication networks have Bernoulli dropouts, i.e. the information exchanged between agents may be lost with Bernou...
1 CitationsSource