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.

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 mdominating 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. Very recently, Shi et. al. and Fukunaga separately introduced constant factor approximation algorithms for the problem with m ≥ k ≥ 1. However, we found the structures of the algorithms are extremely complicated, and thus it would be difficult to implement and use them in practice. Motivated by such observation, this paper introduces a novel approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is based on our new technique which first computes a 1-connected m-dominating set D and repeatedly (a) decomposes D into an i-connected block tree, with i = 2, 3, ··· , k, and (b) use this graph structure to improve the connectivity of D, until D becomes k-connected. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant. We compare the structure of our algorithm against the existing ones and show our algorithm is much simpler to understand and implement.

This paper identifies a new security problem of existing scheduling algorithms for barrier-coverage of sensors, which never considered before. A barrier-cover of wireless sensors is a subset of sensors seamlessly spanning between two opposite sides such that no intruder can move from one side to the other without being detected. The goal of the scheduling algorithms is to find a sleep-wakeup schedule of sensors such that the time to protect an area of interest using a series of alternating barrier-covers can be maximized. We introduce a new security problem which may exist when two barrier-covers, whose covered areas are not completely disjoint, alternate. We show how an intruder can utilize a set of points, namely “barrier-breaches”, to penetrate the alternating barrier-covers. We also propose two remedies for this problem for existing scheduling algorithms. Our analysis shows that depending on the input graph, one of our approaches works better than the other. Given that such scheduling algorithms only need to run during the initialization phase of a sensor network, we suggest to apply both approaches and pick the better schedule rather than relying solely on the approach which works well on average.