## 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 <inline-formula><tex-math notation="LaTeX">$\xi \cdot opt+\gamma +2m$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\xi \cdot opt+\gamma$</tex-math></inline-formula> is the upper bound on the original CDS size, <inline-formula><tex-math notation="LaTeX">$opt$</tex-math></inline-formula> is the minimum CDS size in the UDG, <inline-formula><tex-math notation="LaTeX">$\xi$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\gamma$</tex-math></inline-formula> are two positive constants, and <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula> 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.

Original language | English |
---|---|

Pages (from-to) | 1-15 |

Number of pages | 15 |

Journal | IEEE Transactions on Network Science and Engineering |

DOIs | |

State | Accepted/In press - 2023 |

## Keywords

- approximation algorithm
- Approximation algorithms
- connected dominating set
- distributed algorithm
- Fault tolerance
- Fault tolerant systems
- faulty links
- reconstruction
- Routing
- Storms
- Task analysis
- Wireless sensor network
- Wireless sensor networks