Approximation Algorithm for Fault-Tolerant Virtual Backbone in Wireless Sensor Networks

To save energy and alleviate interferences in a wireless sensor network, the usage of virtual backbone was proposed. Because of accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone, which can be modeled as a $k$-connected $m$-fold dominating set (abbreviated as $(k,m)$-CDS) in a graph. A node set $Csubseteq V(G)$ is a $(k,m)$-CDS of graph $G$ if every node in $V(G)backslash C$ is adjacent with at least $m$ nodes in $C$ and the subgraph of $G$ induced by $C$ is $k$-connected. In this paper, we present an approximation algorithm for the minimum $(3,m)$-CDS problem with $mgeq3$. The performance ratio is at most $gamma$, where $gamma=alpha+8+2ln(2alpha-6)$ for $alphageq4$ and $gamma=3alpha+2ln2$ for $alpha<4$, and $alpha$ is the performance ratio for the minimum $(2,m)$-CDS problem. Using currently best known value of $alpha$, the performance ratio is $lndelta+o(lndelta)$, where $delta$ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. This is the first performance-guaranteed algorithm for the minimum $(3,m)$-CDS problem on a general graph. Furthermore, applying our algorithm on a unit disk graph which models a homogeneous wireless sensor network, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the $(3,m)$-CDS problem on a unit disk graph.