Restricted coverage in wireless networks

Xiaohua Xu, Min Song

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations

Abstract

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 + ε).

Original languageEnglish
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
Pages558-564
Number of pages7
DOIs
StatePublished - 2014
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada
Duration: 27 Apr 20142 May 2014

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Conference

Conference33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
Country/TerritoryCanada
CityToronto, ON
Period27/04/142/05/14

Fingerprint

Dive into the research topics of 'Restricted coverage in wireless networks'. Together they form a unique fingerprint.

Cite this