On practical construction of quality fault-Tolerant virtual backbone in homogeneous wireless networks

Over years, many efforts are made for the problem of constructing quality fault-Tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g., with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum k -connected m -dominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers k and m satisfying m ≥ k ≥ 1 and k ≤ 3. This paper introduces an approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is simple to implement; it connects the components by adding a bounded number of paths, which first computes a 1-connected m -dominating set D and repeats the following steps: (a) search the separators arbitrarily in (i-1,m) -CDS with i = 2, 3, ⋯, k , (b) add a bounded number of paths connecting the components separated by separators in (i-1,m) -CDS to improve the connectivity of (i-1,m) -CDS, until it becomes k -connected, and (c) remove redundant paths if there exist at every iteration. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant, for any fixed k.