Icons / Logo / Facebook Created with Sketch. Icons / Logo / Google Created with Sketch. Icons / Logo / ORCID Created with Sketch. Branding/Logomark minus Citation Combined Shape Icon/Bookmark-empty Icon/Copy Icon/Collection Icon/Close Copy 7 no author result Created with Sketch. Icon/Back Created with Sketch. Match!

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

Published on Sep 1, 2016
· DOI :10.1109/SSPD.2016.7590591
Sai Zhang4
Estimated H-index: 4
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
+ 2 AuthorsAndreas Spanias25
Estimated H-index: 25
(ASU: Arizona State University)
Cite
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.
  • References (24)
  • Citations (2)
Cite
References24
Newest
Published on Nov 1, 2015 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
Sai Zhang4
Estimated H-index: 4
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
(ASU: Arizona State University)
+ 1 AuthorsMahesh K. Banavar12
Estimated H-index: 12
(Clarkson University)
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...
Published on Jun 1, 2015 in ICC (International Conference on Communications)
Jongmin Lee3
Estimated H-index: 3
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias25
Estimated H-index: 25
(ASU: Arizona State University)
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...
Published on Apr 1, 2015in IEEE Transactions on Signal Processing 5.23
Sivaraman Dasarathan4
Estimated H-index: 4
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias25
Estimated H-index: 25
(ASU: Arizona State University)
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...
Published on Mar 1, 2014in IEEE Transactions on Automatic Control 5.09
Damiano Varagnolo13
Estimated H-index: 13
,
Gianluigi Pillonetto26
Estimated H-index: 26
(UNIPD: University of Padua),
Luca Schenato34
Estimated H-index: 34
(UNIPD: University of Padua)
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...
Published on Jan 1, 2014in IEEE Transactions on Information Theory 3.21
Sudeep Kamath11
Estimated H-index: 11
(University of California, Berkeley),
D. Manjunath16
Estimated H-index: 16
(IITB: Indian Institute of Technology Bombay),
Ravi R. Mazumdar27
Estimated H-index: 27
(UW: University of Waterloo)
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 ...
Published on Dec 1, 2013in IEEE Transactions on Signal Processing 5.23
Sivaraman Dasarathan4
Estimated H-index: 4
(ASU: Arizona State University),
Cihan Tepedelenliolu1
Estimated H-index: 1
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias25
Estimated H-index: 25
(ASU: Arizona State University)
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...
Published on Nov 1, 2013 in ASILOMAR (Asilomar Conference on Signals, Systems and Computers)
Sai Zhang4
Estimated H-index: 4
(ASU: Arizona State University),
Cihan Tepedelenlioglu26
Estimated H-index: 26
(ASU: Arizona State University)
+ 1 AuthorsAndreas Spanias25
Estimated H-index: 25
(ASU: Arizona State University)
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...
Published on Nov 1, 2012in IEEE Transactions on Signal Processing 5.23
Franck Iutzeler7
Estimated H-index: 7
(ENST: Télécom ParisTech),
Philippe Ciblat25
Estimated H-index: 25
(ENST: Télécom ParisTech),
Jérémie Jakubowicz10
Estimated H-index: 10
(Telecom SudParis)
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.
Published on Jan 1, 2012
Xue Zhang6
Estimated H-index: 6
(ASU: Arizona State University),
Mahesh K. Banavar12
Estimated H-index: 12
(ASU: Arizona State University)
+ 6 AuthorsAnthony G. Constantinides25
Estimated H-index: 25
(Imperial College London)
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 ...
Published on Dec 1, 2010 in CDC (Conference on Decision and Control)
Damiano Varagnolo13
Estimated H-index: 13
(UNIPD: University of Padua),
Gianluigi Pillonetto26
Estimated H-index: 26
(UNIPD: University of Padua),
Luca Schenato34
Estimated H-index: 34
(UNIPD: University of Padua)
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...
Cited By2
Newest
Published on Mar 1, 2019
Marcin Kardas3
Estimated H-index: 3
,
Marek Klonowski12
Estimated H-index: 12
,
Piotr Syga3
Estimated H-index: 3
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...