TY - GEN
T1 - Restricted coverage in wireless networks
AU - Xu, Xiaohua
AU - Song, Min
PY - 2014
Y1 - 2014
N2 - 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-A'-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 A'-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 + ε).
AB - 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-A'-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 A'-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 + ε).
UR - http://www.scopus.com/inward/record.url?scp=84904408598&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904408598&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2014.6847980
DO - 10.1109/INFOCOM.2014.6847980
M3 - Conference contribution
AN - SCOPUS:84904408598
SN - 9781479933600
T3 - Proceedings - IEEE INFOCOM
SP - 558
EP - 564
BT - IEEE INFOCOM 2014 - IEEE Conference on Computer Communications
T2 - 33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
Y2 - 27 April 2014 through 2 May 2014
ER -