Restricted coverage in wireless networks

For wireless networks, coverage with different restrictions that can capture the practical requirements have received great research interests. We will study several restricted coverage problems. The first problem is about K-coverage, i.e., how to deploy wireless nodes such that each target is covered by at least K wireless nodes. We study the problem restricted to linear-K-coverage where there is a line, all targets lie in one side of this line and all wireless nodes lie in the other side. Assume each wireless node is associated with a weight, the objective is to select a minimum weighted subset of nodes such that each target is K-covered. We propose a 3-approximation for this problem by exploring geometric properties. The second problem is called K-road-coverage. Given a road map in a two-dimensional area which contains a set of paths and a set of wireless nodes, the locations of nodes can either be arbitrary or fixed, the objective is to select a minimum number of wireless nodes such that each path can be K-covered. We will reduce the problem to K-coverage and apply the algorithmic results for K-coverage to solve it. Another line of this work is to investigate a well-motivated problem called strongly dominating set, which is intrinsically related to coverage. Given a wireless networking system represented by a digraph G = (V, E⃗). Each wireless node u has a covering disk centering at u with its radius equal to the transmission range of u. We then draw a directed edge uv⃗ in G if u´s corresponding covering disk contains v. A subset U ⊆ V of wireless nodes is a strongly dominating set if every wireless node in V U has both an in-neighbor in U and an out-neighbor in U. The objective is to find a minimum size strongly dominating set. Our method can achieve an approximation factor of (2 + ε).