An asynchronous distributed algorithm for minimum s - t cut detection in wireless multi-hop networks
Yükleniyor...
Tarih
2020
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Stable communication is a vital and challenging requirement in wireless multi-hop networks because nodes failure may disconnect other active nodes. Minimum s-t cuts can help to measure the reliability of a network regarding the nodes or links failure. A minimum s-t cut is the smallest subset of links that their failure disconnects all communication paths between nodes s and t. Minimum s-t cuts can also reveal the bottlenecks, bridges, and clusters in the network. This paper proposes an asynchronous distributed algorithm for finding minimum s-t cuts in wireless multi-hop networks. The proposed algorithm iteratively finds link-disjoint paths from s to t and changes the direction of the selected edges to ignore them in the next iteration. After finding all paths, the undiscovered nodes in the last search determine the minimum s-t cut. The comprehensive simulation results on different networks with up to 500 nodes show that the proposed algorithm finds minimum s-t cuts in reasonable time with up to 64% and 39% lower energy consumption than the existing central and distributed algorithms, respectively. (C) 2020 Elsevier B.V. All rights reserved.
Açıklama
Anahtar Kelimeler
Wireless Multi-hop Networks, Minimum s-t Cut, Fault Tolerance, Asynchronous Distributed Algorithms, Cut Edge, Sensor Networks, Lifetime
