Restricted coverage in wireless networks
Xiaohua Xu, Min Song · 2014
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 aboutK-coverage, i.e., how to deploy wireless nodes such that each target is covered by at leastKwireless 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 isK-covered. We propose a 3-approximation for this problem by exploring geometric properties. The second problem is calledK-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 beK-covered. We will reduce the problem toK-coverage and apply the algorithmic results forK-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 + ε).