On the Reconstruction of a Quality Virtual Backbone in a Wireless Sensor Network With Faulty Links
- 3 October 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 11 (1) , 1277-1292
Abstract
The work of routing and topological control for a wireless sensor network (WSN) is often undertaken by means of its virtual backbone (VB). Usually, a WSN and its VB can be modeled as a unit disk graph (UDG) and a corresponding connected dominating set (CDS), respectively. A smaller CDS in a UDG is preferred because it will lead to less overhead. In practical applications, sensor nodes or their links in a WSN may fail due to obstacles or accidental damage. Thus, it is desirable to either construct a robust VB or be able to reconstruct a new VB. In this paper, the problem of reconstructing CDSs for UDGs with faulty links is considered. First, we propose a centralized approximation algorithm for the problem. We theoretically show that for a given UDG, the size of the CDS constructed by our algorithm does not exceed $\xi \cdot opt+\gamma +2m$ , where $\xi \cdot opt+\gamma$ is the upper bound on the original CDS size, $opt$ is the minimum CDS size in the UDG, $\xi$ and $\gamma$ are two positive constants, and $m$ is the number of faulty links. Next, we design a distributed approximation algorithm on the basis of our centralized approximation algorithm and analyze its time and message complexity. Related simulation experiments are presented to compare our algorithm with other state-of-the-art algorithms for solving this problem, and the results show that our algorithm outperforms its competitors.Keywords
Funding Information
- National Natural Science Foundation of China (61862003, 62261003)
- Natural Science Foundation of the Guangxi Zhuang Autonomous Region of China (2018GXNSFDA281052)
This publication has 34 references indexed in Scilit:
- A New Constant Factor Approximation to Construct Highly Fault-Tolerant Connected Dominating Set in Unit Disk GraphIEEE/ACM Transactions on Networking, 2016
- A greedy algorithm for the minimum $2$ 2 -connected $m$ m -fold dominating set problemJournal of Combinatorial Optimization, 2014
- A new bound on maximum independent set and minimum connected dominating set in unit disk graphsJournal of Combinatorial Optimization, 2013
- On minimum m-connected k-dominating set problem in unit disc graphsJournal of Combinatorial Optimization, 2007
- Distributed Construction of Connected Dominating Set in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004
- A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networksNetworks, 2003
- Routing in ad-hoc networks using minimum connected dominating sets2002
- Message-optimal connected dominating sets in mobile ad hoc networks2002
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Propagation and leader election in a multihop broadcast environment1998