Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-20
Computer Science
Data Structures and Algorithms
16 pages, 1 figures (to appear in SODA 2011)
Scientific paper
The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight $\theta(\log n)$-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal $O(\log n + \log \log \Delta)$-approximation to the power control problem using mean power, where $\Delta$ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.
Halldorsson Magnus Mar
Mitra Pradipta
No associations
LandOfFree
Wireless Capacity with Oblivious Power in General Metrics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Wireless Capacity with Oblivious Power in General Metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wireless Capacity with Oblivious Power in General Metrics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-717340