Almost sure convergence of a randomized algorithm for relative localization in sensor networks
Authors:
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4778-4783
Abstract
This paper regards the relative localization problem in sensor networks. We study a randomized algorithm, which is based on input-driven consensus dynamics and involves pairwise “gossip” communications and updates. Due to the randomness of the updates, the state of this algorithm ergodically oscillates around a limit value. Exploiting the ergodicity of the dynamics, we show that the time-average of the state almost surely converges to the least-squares solution of the localization problem. Remarkably, the computation of the time-average does not require the sensors to share any common clock. Hence, the proposed algorithm is fully distributed and asynchronous.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Opinion Fluctuations and Disagreement in Social NetworksMathematics of Operations Research, 2013
- Fast distributed smoothing of relative measurements2012
- PageRank computation via a distributed randomized approach with lossy communicationSystems & Control Letters, 2012
- A Web Aggregation Approach for Distributed Randomized PageRank AlgorithmsIEEE Transactions on Automatic Control, 2012
- Scaling limits for continuous opinion dynamics systemsThe Annals of Applied Probability, 2011
- Asynchronous Broadcast-Based Convex Optimization Over a NetworkIEEE Transactions on Automatic Control, 2010
- Distributed Randomized Algorithms for the PageRank ComputationIEEE Transactions on Automatic Control, 2010
- Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis2006
- Randomized Algorithms for Analysis and Control of Uncertain Systems2005
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951