Distributed Estimation and Control of Algebraic Connectivity Over Random Graphs

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

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2014-11, Vol.62 (21), p.5615-5628
Main Authors: Di Lorenzo, Paolo, Barbarossa, Sergio
Format: Article
Language:English
Subjects:
Algebra
Algebraic connectivity
Algorithms
Distributed algorithms
distributed computation
Eigenvalues and eigenfunctions
Estimates
Failure
Fiedler vector
Graphs
Laplace equations
Network topology
Networks
random graph
Signal processing algorithms
spectral graph theory
stochastic approximation
stochastic power iteration
Stochasticity
Topology
topology control
Vectors
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2014.2355778