Cramer-Rao Bounds for Distributed System Size Estimation Using Consensus Algorithms

Published on Sep 1, 2016
· DOI :10.1109/SSPD.2016.7590591
Sai Zhang7
Estimated H-index: 7
(ASU: Arizona State University),
Cihan Tepedelenlioglu28
Estimated H-index: 28
+ 2 AuthorsAndreas Spanias32
Estimated H-index: 32
Sources
Abstract
System size estimation in distributed wireless sensor networks is important in various applications such as network management and maintenance. One popular method for system size estimation is to use distributed consensus algorithms with randomly generated initial values at nodes. In this paper, the performance of such methods is studied and Fisher information and Cramer-Rao bounds (CRBs) for different consensus algorithms are derived. Errors caused by communication noise and lack of convergence is also considered, and their effect on Fisher information and CRB is given. The results provide a lower bound on the variance of the estimator of system size. This in turn, provides guidelines on how to choose consensus algorithms and initial values at the nodes.
📖 Papers frequently viewed together
1 Citations
2006
3 Authors (Paola Bermolen, ..., I. Juva)
12 Citations
22 Citations
References24
Newest
Nov 1, 2015 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. Mahesh K. Banavar (Clarkson University)H-Index: 17
view all 4 authors...
A distributed consensus algorithm for estimating the number of nodes in a wireless sensor network in the presence of communication noise is proposed. The idea is based on estimating the norm of available samples at nodes. Each node generates its own random initial measurements and updates its state by only communicating with its neighbors: the algorithm is fully distributed with no assumptions about the structure of the network. We also show that there is a trade-off between the estimation error...
5 CitationsSource
Jun 8, 2015 in ICC (International Conference on Communications)
#1Jongmin Lee (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 4 authors...
This paper introduces diffusion adaptation strategies over distributed networks with nonlinear transmissions, motivated by the necessity for bounded transmit power. Local information is exchanged in real-time with neighboring nodes in order to estimate a common parameter vector via constrained nonlinear transmissions, using an adaptive learning algorithm. We propose nonlinear diffusion strategies for such an adaptive estimation. We will study convergence properties of the proposed algorithm in t...
4 CitationsSource
#1Sivaraman Dasarathan (ASU: Arizona State University)H-Index: 4
#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 average consensus algorithm robust to a wide range of impulsive channel noise distributions is proposed. This work is the first of its kind in the literature to propose a consensus algorithm which relaxes the requirement of finite moments on the 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 algo...
13 CitationsSource
#1Damiano VaragnoloH-Index: 17
#2Gianluigi Pillonetto (UNIPD: University of Padua)H-Index: 30
Last. Luca Schenato (UNIPD: University of Padua)H-Index: 50
view all 3 authors...
We consider estimation of network cardinality by distributed anonymous strategies relying on statistical inference methods. In particular, we focus on the relative Mean Square Error (MSE) of Maximum Likelihood (ML) estimators based on either the maximum or the average of M-dimensional vectors randomly generated at each node. In the case of continuous probability distributions, we show that the relative MSE achieved by the max-based strategy decreases as 1/M, independently of the used distributio...
40 CitationsSource
#1Sudeep Kamath (University of California, Berkeley)H-Index: 14
#2D. Manjunath (IITB: Indian Institute of Technology Bombay)H-Index: 17
Last. Ravi R. Mazumdar (UW: University of Waterloo)H-Index: 30
view all 3 authors...
We consider in-network computation of MAX and the approximate histogram in an n-node structure-free random multihop wireless network. The key assumption that we make is that the nodes do not know their relative or absolute locations and that they do not have an identity. For the Aloha MAC protocol, we first describe a protocol in which the MAX value becomes available at the origin in O(√{n/logn}) slots (bit-periods) with high probability. This is within a constant factor of that required by the ...
12 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
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
#1Xue Zhang (ASU: Arizona State University)H-Index: 7
#2Mahesh K. Banavar (ASU: Arizona State University)H-Index: 17
Last. Anthony G. Constantinides (Imperial College London)H-Index: 28
view all 9 authors...
In this paper, the performance of different localization algorithms are compared in the context of the sequential Wireless Sensor Network (WSN) discovery problem. Here, all sensor nodes are at unknown locations except for a very small number of so called anchor nodes at known locations. The locations of nodes are sequentially estimated such that when the location of a given node is found, it may be used to localize others. The underlying performance of such an approach is largely dependent upon ...
15 CitationsSource
Dec 1, 2010 in CDC (Conference on Decision and Control)
#1Damiano Varagnolo (UNIPD: University of Padua)H-Index: 17
#2Gianluigi Pillonetto (UNIPD: University of Padua)H-Index: 30
Last. Luca Schenato (UNIPD: University of Padua)H-Index: 50
view all 3 authors...
The distributed estimation of the number of active sensors in a network can be important for estimation and organization purposes. We propose a design methodology based on the following paradigm: some locally randomly generated values are exchanged among the various sensors and thus modified by known consensus-based strategies. Statistical analysis of the a-consensus values allows estimation of the number of participant sensors. The main features of this approach are: algorithms are completely d...
36 CitationsSource
Cited By3
Newest
#1Marcin KardasH-Index: 3
#2Marek KlonowskiH-Index: 14
Last. Piotr SygaH-Index: 4
view all 3 authors...
Abstract We consider an ad hoc radio network in which nodes perform some distributed algorithms. We provide a framework, that at the cost of increasing time complexity, prevents an outer, passive adversary from gaining significant information about the execution of the algorithm. The main idea we utilize is adding some extra obfuscating rounds to conceal the real execution. Despite the fact that we assume a relatively weak model of the adversary, trying to solve the problem, we encounter several...
Source
#1Sai Zhang (ASU: Arizona State University)H-Index: 7
Last. Mahesh K. Banavar (Clarkson University)H-Index: 17
view all 4 authors...
Abstract The area of detection and estimation in a distributed wireless sensor network (WSN) has several applications, including military surveillance, sustainability, health monitoring, and Internet of Things (IoT). Compared with a wired centralized sensor network, a distributed WSN has many advantages including scalability and robustness to sensor node failures. In this book, we address the problem of estimating the structure of distributed WSNs. First, we provide a literature review in: (a) g...
5 Citations
#1Sai ZhangH-Index: 7
1 Citations