Computing the Capacity Region of a Wireless Network
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 n2 dimensional unicast capacity region of such a wireless network. Equivalently,...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61976 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811085864017592320 |
|---|---|
| author | Gummadi, Ramakrishna Jung, Kyomin Shah, Devavrat Sreenivas, Ramavarapu |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gummadi, Ramakrishna Jung, Kyomin Shah, Devavrat Sreenivas, Ramavarapu |
| author_sort | Gummadi, Ramakrishna |
| collection | MIT |
| description | 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 n2 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)[superscript 1-o1] factor for general graphs. In this paper, we first show that the whole n2 [superscript 2] dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor 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. |
| first_indexed | 2024-09-23T13:16:45Z |
| format | Article |
| id | mit-1721.1/61976 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:16:45Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/619762022-09-28T13:06:01Z Computing the Capacity Region of a Wireless Network Gummadi, Ramakrishna Jung, Kyomin Shah, Devavrat Sreenivas, Ramavarapu Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Shah, Devavrat Jung, Kyomin Shah, Devavrat 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 n2 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)[superscript 1-o1] factor for general graphs. In this paper, we first show that the whole n2 [superscript 2] dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor 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. National Science Foundation (U.S.) (Grant NSF CNS-0437415) (Grant NSF ECCS-0426831) (Grant NSF CNS-0834409) (CAREER grant NSF CNS-0546590) (Grant NSF CCF-0728554) 2011-03-25T20:22:24Z 2011-03-25T20:22:24Z 2009-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-3512-8 0743-166X INSPEC Accession Number: 10685543 http://hdl.handle.net/1721.1/61976 Shah, D., and R. Sreenivas, with Gummadi, R., Kyomin Jung. “Computing the Capacity Region Of a Wireless Network.” Infocom 2009, Ieee. 2009. 1341-1349. Copyright © 2009, IEEE https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/INFCOM.2009.5062049 IEEE INFOCOM Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Gummadi, Ramakrishna Jung, Kyomin Shah, Devavrat Sreenivas, Ramavarapu Computing the Capacity Region of a Wireless Network |
| title | Computing the Capacity Region of a Wireless Network |
| title_full | Computing the Capacity Region of a Wireless Network |
| title_fullStr | Computing the Capacity Region of a Wireless Network |
| title_full_unstemmed | Computing the Capacity Region of a Wireless Network |
| title_short | Computing the Capacity Region of a Wireless Network |
| title_sort | computing the capacity region of a wireless network |
| url | http://hdl.handle.net/1721.1/61976 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT gummadiramakrishna computingthecapacityregionofawirelessnetwork AT jungkyomin computingthecapacityregionofawirelessnetwork AT shahdevavrat computingthecapacityregionofawirelessnetwork AT sreenivasramavarapu computingthecapacityregionofawirelessnetwork |