Distributed detecting of critical nodes for maximization of connected components in wireless multi-hop networks

dc.authoridDagdeviren, Orhan/0000-0001-8789-5086
dc.authoridAygul, Yesim/0000-0003-0605-9604
dc.contributor.authorUğurlu, Onur
dc.contributor.authorAkram, Nusin
dc.contributor.authorAygul, Yesim
dc.contributor.authorAkram, Vahid Khalilpour
dc.contributor.authorDagdeviren, Orhan
dc.date.accessioned2025-03-20T09:51:13Z
dc.date.available2025-03-20T09:51:13Z
dc.date.issued2025
dc.departmentİzmir Bakırçay Üniversitesi
dc.description.abstractIn Wireless Multi-hop Networks (WMhNs), nodes whose absence significantly weakens network connectivity or partitions the network into disconnected components are called critical nodes. This paper focuses on a critical node problem, the Maximizing the Number of Connected Components (MaxNum) problem, which aims to identify critical nodes whose removal maximizes the number of connected components. Although the MaxNum problem is a well-known NP-Hard problem with various real-world applications, no distributed algorithm has been proposed to solve it. To address this gap, we propose an efficient distributed algorithm for the MaxNum problem in WMhNs. The algorithm uses a distributed depth-first search tree to identify critical nodes, requiring a bit complexity of ( x x log2 ) and a space complexity of ( + ), where denotes the maximum node degree. We evaluated the proposed algorithm through simulations and testbed networks, comparing it to the Linear Programming (LP) approach. Our findings show that the proposed distributed algorithm achieves promising outcomes, reaching nearly 90% of the optimal solution while reducing data transmission to half of that required by the centralized LP.
dc.description.sponsorshipTUBITAK (Scientific and Technical Research Council of Turkey) [121F092]
dc.description.sponsorshipThis research was supported by the TUBITAK (Scientific and Techni-cal Research Council of Turkey) [Project number 121F092] . N. Akram and Y. Aygul thank TUBITAK for their scholarship support under the BIDEB 2211-C and BIDEB 2211-A programs, respectively. We also would like to thank two anonymous reviewers for their constructive comments.
dc.identifier.doi10.1016/j.adhoc.2024.103744
dc.identifier.issn1570-8705
dc.identifier.issn1570-8713
dc.identifier.scopus2-s2.0-85213265648
dc.identifier.scopusqualityQ1
dc.identifier.urihttps://doi.org/10.1016/j.adhoc.2024.103744
dc.identifier.urihttps://hdl.handle.net/20.500.14034/2475
dc.identifier.volume169
dc.identifier.wosWOS:001397609000001
dc.identifier.wosqualityQ1
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherElsevier
dc.relation.ispartofAd Hoc Networks
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/closedAccess
dc.snmzKA_WOS_20250319
dc.subjectWireless networks
dc.subjectReliability
dc.subjectDistributed algorithms
dc.subjectCritical nodes
dc.subjectConnected components
dc.titleDistributed detecting of critical nodes for maximization of connected components in wireless multi-hop networks
dc.typeArticle

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
[ X ]
İsim:
Tam Metin / Full Text
Boyut:
2.03 MB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text