This work formally establishes that IEEE 802.11 yields exceptionally good performance in the context of wireless multi-hop networks. A common misconception is that existing CSMA-CA random access schemes like IEEE 802.11 yield unfair and inefficient rates in wireless multi-hop networks. This misconception is based on works which study IEEE 802.11-scheduled multi-hop networks with TCP or in saturation conditions both of which grossly underutilize the available capacity that IEEE 802.11 provides, or use topologies which cannot occur in practice due to physical layer limitations.
To formally establish our thesis, we will derive worst case performance bounds on IEEE 802.11 in multi-hop networks. We first characterize the achievable rate region for any IEEE 802.11-scheduled multi-hop network. To do so, we first characterize the achievable edge-rate region, that is, the set of edge rates that are achievable on a given topology. This requires a careful consideration of the inter-dependence among edges, since neighboring edges collide with and affect the idle time perceived by the edge under study. We approach this problem in two steps. First, we consider two-edge topologies and study the fundamental ways by which they interact. Then, we consider arbitrary multi-hop topologies, compute the effect that each neighboring edge has on the edge under study in isolation, and combine to get the aggregate effect.
We then use the characterization of the set of feasible rates to compare the max-min rate allocation achieved by IEEE 802.11 and optimal, and find that: (i) IEEE 802.11 is never worse than 16% of the optimal when ignoring physical layer constraints, (ii) in any realistic topology with geometric constraints due to the physical layer, IEEE 802.11 is never worse than 30% of the optimal, and (iii) in typical topologies IEEE 802.11 attains more than 55% of the optimal throughput. Considering that the state-of-the-art distributed approximations to optimal scheduling achieve lower worst case bounds than the above, IEEE 802.11 is surprisingly efficient.
To ensure that this good performance is achievable with a distributed rate controller, we propose WCP-CAP. It provides explicit and precise rate feedback to sources while exchanging control information only amongst the neighbors. WCP-CAP achieves max-min rates within 15% of the optimal for all the topologies considered in this paper.
|Commitee:||Govindan, Ramesh, Krishnamachari, Bhaskar|
|School:||University of Southern California|
|School Location:||United States -- California|
|Source:||DAI-B 70/05, Dissertation Abstracts International|
|Keywords:||IEEE 802.11, Multihop networks, Optimality, Wireless multihop networks|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be