A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Finite-Time Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks
Tekijät: Atman, Made Widhi Surya; Gusrialdi, Azwirman
Kustantaja: Institute of Electrical and Electronics Engineers (IEEE)
Julkaisuvuosi: 2022
Journal: IEEE transactions on network science and engineering
Tietokannassa oleva lehden nimi: IEEE Transactions on Network Science and Engineering
Vuosikerta: 9
Numero: 6
Aloitussivu: 4379
Lopetussivu: 4392
ISSN: 2327-4697
eISSN: 2334-329X
DOI: https://doi.org/10.1109/TNSE.2022.3200466
Verkko-osoite: https://doi.org/10.1109/tnse.2022.3200466
Tiivistelmä
The strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed estimation/control/optimization algorithms. However, the assumption on the network's strong connectivity may not always be satisfied in practice. In addition, information on the overall network topology is often not available, e.g., due to privacy concerns or geographical constraints which calls for a distributed algorithm. This paper aims to fill a crucial gap in the literature due to the absence of a fully distributed algorithm to verify and ensure in finite-time the strong connectivity of a directed network. Specifically, inspired by the maximum consensus algorithm we propose distributed algorithms that enable individual node in a networked system to verify the strong connectivity of a directed graph and further, if necessary, augment a minimum number of new links to ensure the directed graph's strong connectivity. The proposed distributed algorithms are implemented without requiring information of the overall network topology and are scalable as they only require finite storage and converge in finite number of steps. Furthermore, the algorithms also preserve the privacy in terms of the overall network's topology. Finally, the proposed distributed algorithms are demonstrated and evaluated via numerical results.
The strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed estimation/control/optimization algorithms. However, the assumption on the network's strong connectivity may not always be satisfied in practice. In addition, information on the overall network topology is often not available, e.g., due to privacy concerns or geographical constraints which calls for a distributed algorithm. This paper aims to fill a crucial gap in the literature due to the absence of a fully distributed algorithm to verify and ensure in finite-time the strong connectivity of a directed network. Specifically, inspired by the maximum consensus algorithm we propose distributed algorithms that enable individual node in a networked system to verify the strong connectivity of a directed graph and further, if necessary, augment a minimum number of new links to ensure the directed graph's strong connectivity. The proposed distributed algorithms are implemented without requiring information of the overall network topology and are scalable as they only require finite storage and converge in finite number of steps. Furthermore, the algorithms also preserve the privacy in terms of the overall network's topology. Finally, the proposed distributed algorithms are demonstrated and evaluated via numerical results.
Turun yliopiston Tutkimustietojärjestelmän portaali