Back to Search
Start Over
Construction of node- and link-fault-tolerant virtual backbones in wireless networks.
- Source :
-
Journal of Supercomputing . Aug2023, Vol. 79 Issue 12, p13050-13074. 25p. - Publication Year :
- 2023
-
Abstract
- In wireless sensor networks (WSNs), the virtual backbone (VB) consists of a subset of nodes, which are responsible for routing tasks. Fault-tolerant VBs are desirable for overcoming the effects of node or link failure in WSNs. Usually, a homogeneous WSN (VB) is abstracted as a unit disk graph (UDG) (connected dominating set(CDS)). This paper introduces the concept of a fault-tolerant CDS in a UDG called a ((2, 2), m)-CDS, which is different from a traditional fault-tolerant CDS ((k, m)-CDS). A ((2, 2), m)-CDS can still function even if one edge or one node fails, which implies that it possesses fault-tolerant properties for both nodes and edges, in contrast to traditional (k, m)-CDSs, which possess fault tolerance only for nodes. Then, we propose a 5 α -approximation algorithm for computing a ((2, 2), m)-CDS, where α is the performance ratio for computing a (2, m) -CDS, and analyze its time complexity. In simulations, we compare our algorithm with an existing algorithm for fault-tolerant CDS construction based on CDS size. From the simulations, we find that our algorithm outperforms its competitor in constructing a quality VB. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09208542
- Volume :
- 79
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Journal of Supercomputing
- Publication Type :
- Academic Journal
- Accession number :
- 164419741
- Full Text :
- https://doi.org/10.1007/s11227-023-05180-9