On the Reconstruction of a Quality Virtual Backbone in a Wireless Sensor Network With Faulty Links

Jiarong Liang, Feng He, Dajin Wang, Qingnian Li

Research output: Contribution to journalArticlepeer-review


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 article, 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 ξ · opt+γ +2m, where ξ · opt+γ is the upper bound on the original CDS size, opt is the minimum CDS size in the UDG, ξ and γ 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.

Original languageEnglish
Pages (from-to)1277-1292
Number of pages16
JournalIEEE Transactions on Network Science and Engineering
Issue number1
StatePublished - 1 Jan 2024


  • Wireless sensor network
  • approximation algorithm
  • connected dominating set
  • distributed algorithm
  • faulty links
  • reconstruction


Dive into the research topics of 'On the Reconstruction of a Quality Virtual Backbone in a Wireless Sensor Network With Faulty Links'. Together they form a unique fingerprint.

Cite this