2013/09/30 by Paolo Di Lorenzo, Sergio Barbarossa · 75 citations
Computer Science · Mathematics · #Algebraic connectivity #Algebraic graph theory #Computer network #Computer science #Connectivity #Cooperative Communication and Network Coding #Distributed Control Multi-Agent Systems #Graph #Graph theory #Laplacian matrix #Line graph #Mathematics #Mobile Ad Hoc Networks #Network topology #Node (physics) #Random geometric graph #Random graph #Robustness (evolution) #Stochastic process #Theoretical computer science #Topology (electrical circuits) #Wireless #Wireless ad hoc network #Wireless network #cs.DC
paper · pdf · doi:10.1109/tsp.2014.2355778
published in IEEE Transactions on Signal Processing 62(21), 5615-5628 (Institute of Electrical and Electronics Engineers) · To appear in IEEE Transactions on Signal Processing
arxiv created 2014/09/03 · openalex publication_date 2014/09/17 · arxiv updated 2015/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.