In this paper, we propose a distributed algorithm for the estimation and control of the connectivity of ad-hoc networks in the presence of a random topology. First, given a generic random graph, we introduce a novel stochastic power iteration method that allows each node to estimate and track the algebraic connectivity of the underlying expected graph. Using results from stochastic approximation theory, we prove that the proposed method converges almost surely (a.s.) to the desired value of connectivity even in the presence of imperfect communication scenarios. The estimation strategy is then used as a basic tool to adapt the power transmitted by each node of a wireless network, in order to maximize the network connectivity in the presence of realistic medium access control (MAC) protocols or simply to drive the connectivity toward a desired target value. Numerical results corroborate our theoretical findings, thus illustrating the main features of the algorithm and its robustness to fluctuations of the network graph due to the presence of random link failures.

Distributed estimation and control of algebraic connectivity over random graphs / DI LORENZO, Paolo; Barbarossa, Sergio. - In: IEEE TRANSACTIONS ON SIGNAL PROCESSING. - ISSN 1053-587X. - 62:21(2014), pp. 5615-5628. [10.1109/tsp.2014.2355778]

Distributed estimation and control of algebraic connectivity over random graphs

DI LORENZO, PAOLO;BARBAROSSA, Sergio
2014

Abstract

In this paper, we propose a distributed algorithm for the estimation and control of the connectivity of ad-hoc networks in the presence of a random topology. First, given a generic random graph, we introduce a novel stochastic power iteration method that allows each node to estimate and track the algebraic connectivity of the underlying expected graph. Using results from stochastic approximation theory, we prove that the proposed method converges almost surely (a.s.) to the desired value of connectivity even in the presence of imperfect communication scenarios. The estimation strategy is then used as a basic tool to adapt the power transmitted by each node of a wireless network, in order to maximize the network connectivity in the presence of realistic medium access control (MAC) protocols or simply to drive the connectivity toward a desired target value. Numerical results corroborate our theoretical findings, thus illustrating the main features of the algorithm and its robustness to fluctuations of the network graph due to the presence of random link failures.
File allegati a questo prodotto
File Dimensione Formato  
DiLorenzo_Distributed-estimation_2014.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 3.57 MB
Formato Adobe PDF
3.57 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/759403
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 55
  • ???jsp.display-item.citation.isi??? 45
social impact