TY - GEN

T1 - Computing the capacity region of a wireless network

AU - Gummadi, Ramakrishna

AU - Jung, Kyomin

AU - Shah, Devavrat

AU - Sreenivas, Ramavarapu

N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n 2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1) factor for general graphs. In this paper, we first show that the whole n 2 dimensional unicast capacity region can be approximated to (1 ± ε) actor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

AB - We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n 2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1) factor for general graphs. In this paper, we first show that the whole n 2 dimensional unicast capacity region can be approximated to (1 ± ε) actor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

UR - http://www.scopus.com/inward/record.url?scp=70349668708&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349668708&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2009.5062049

DO - 10.1109/INFCOM.2009.5062049

M3 - Conference contribution

AN - SCOPUS:70349668708

SN - 9781424435135

T3 - Proceedings - IEEE INFOCOM

SP - 1341

EP - 1349

BT - IEEE INFOCOM 2009 - The 28th Conference on Computer Communications

T2 - 28th Conference on Computer Communications, IEEE INFOCOM 2009

Y2 - 19 April 2009 through 25 April 2009

ER -