Almost sure convergence of a randomized algorithm for relative localization in sensor networks

Chiara Ravazzi; Paolo Frasca; Roberto Tempo; Hideaki Ishii

Almost sure convergence of a randomized algorithm for relative localization in sensor networks

Chiara Ravazzi
, Paolo Frasca
, Roberto Tempo
, Hideaki Ishii

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	Undefined
Title of host publication	Proceedings of the 52nd IEEE Conference on Decision and Control
Place of Publication	USA
Publisher	IEEE
Pages	4778-4783
Number of pages	6
ISBN (Print)	978-1-4673-5716-6
Publication status	Published - Dec 2013
Event	52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy Duration: 10 Dec 2013 → 13 Dec 2013 Conference number: 52

Publication series

Name
Publisher	IEEE Control Systems Society

Conference

Conference	52nd IEEE Conference on Decision and Control, CDC 2013
Abbreviated title	CDC
Country/Territory	Italy
City	Florence
Period	10/12/13 → 13/12/13

Keywords

EWI-24172
METIS-300254
IR-88318

Access to Document

http://eprints.eemcs.utwente.nl/secure2/24172/01/RFTI_cdc13.pdf

Cite this

@inproceedings{c09e02eba9924364985e7e6ae5e7948a,

title = "Almost sure convergence of a randomized algorithm for relative localization in sensor networks",

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 = "EWI-24172, METIS-300254, IR-88318",

author = "Chiara Ravazzi and Paolo Frasca and Roberto Tempo and Hideaki Ishii",

year = "2013",

month = dec,

language = "Undefined",

isbn = "978-1-4673-5716-6",

publisher = "IEEE",

pages = "4778--4783",

booktitle = "Proceedings of the 52nd IEEE Conference on Decision and Control",

address = "United States",

note = "52nd IEEE Conference on Decision and Control, CDC 2013 ; Conference date: 10-12-2013 Through 13-12-2013",

}

Ravazzi, C, Frasca, P, Tempo, R & Ishii, H 2013, Almost sure convergence of a randomized algorithm for relative localization in sensor networks. in Proceedings of the 52nd IEEE Conference on Decision and Control. IEEE, USA, pp. 4778-4783, 52nd IEEE Conference on Decision and Control, CDC 2013, Florence, Italy, 10/12/13. <http://eprints.eemcs.utwente.nl/secure2/24172/01/RFTI_cdc13.pdf>

TY - GEN

T1 - Almost sure convergence of a randomized algorithm for relative localization in sensor networks

AU - Ravazzi, Chiara

AU - Frasca, Paolo

AU - Tempo, Roberto

AU - Ishii, Hideaki

N1 - Conference code: 52

PY - 2013/12

Y1 - 2013/12

N2 - 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.

AB - 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.

KW - EWI-24172

KW - METIS-300254

KW - IR-88318

M3 - Conference contribution

SN - 978-1-4673-5716-6

SP - 4778

EP - 4783

BT - Proceedings of the 52nd IEEE Conference on Decision and Control

PB - IEEE

CY - USA

T2 - 52nd IEEE Conference on Decision and Control, CDC 2013

Y2 - 10 December 2013 through 13 December 2013

ER -