On the Computation of Virtual Backbones With Fault Tolerance in Heterogeneous Wireless Sensor Networks

In the context of wireless sensor networks (WSNs), the problem of virtual backbones (VBs) for undertaking routing tasks to alleviate broadcast storms has been extensively studied. In practical applications, different nodes in a WSN may have different transmission ranges because of differences in power control or functionality, among other reasons. In such a situation, a disk graph (DG) can be used as a mathematical model of the WSN, and a strongly connected dominating and absorbent set (SCDAS) in the DG can be treated as a VB in the corresponding WSN. In a WSN with faulty nodes, a fault-tolerant VB is superior to a traditional one. Thus, it is desirable to construct a
$ k$
-strongly connected
$ m$
-dominating and absorbent set (
$ (k,m)$
-SCDAS) in the DG to serve as a fault-tolerant VB in the corresponding WSN. In this article, to enable the construction of a high-quality
$ (k,m)$
-SCDAS in a DG, a constant approximation algorithm with a performance ratio of
$(2k(5^{k-1}-1)+1)(R+m+4(\frac{R}{m}+1))$
is proposed, where
$ k$
and
$ m$
are constants (
$ 2 \;\leqslant\; k \;\leqslant\; m$
) and
$ R$
is the maximum number of independent nodes within the transmission range of a node in the DG. A theoretical analysis and simulation results show that our work is superior to previous approaches.