Random Access is Good Enough to Build Wireless Multi-Hop Networks

Static multi-hop networks are an emerging network architecture that provides community networking, wireless city-wide Internet access as well as Internet access in locations like airports, convention centers educational facilities etc, distributed sensing, and support for medical applications. Building the stack for these networks is an important open research problem.

We consider the problem of scheduling in these networks. Two plausible solutions are: (i) use distributed approximations of optimal scheduling, (ii) or use existing CSMA-CA random access schemes like IEEE 802.11. Deriving the optimal schedule is an NP-hard problem, and its not clear if its possible to design low-overhead and efficient approximations for it. Further these approximations will also require the design of new hardware. Hence, the second choice seems more practical. However, different researchers have noted the poor performance of TCP over IEEE 802.11 in multi-hop networks. These observations lead to the following fundamental question. Is it even possible to achieve fair and efficient throughput performance with CSMA-CA random access schemes in multi-hop networks.

We show that it is possible to achieve the same degree of performance with IEEE 802.11 as the state-of-the-art approximations to optimal scheduling in multi-hop networks. We solve this problem in the following three steps.

1. Characterize the achievable rate region of IEEE 802.11-scheduled multi-hop networks: A central question in the study of multi-hop networks is the following. Given an arbitrary multi-hop topology and a collection of source-destination pairs, what is the achievable rate region of this arbitrary multi-hop networks. Researchers have studied this problem under the assumption of optimal scheduling. We are the first to characterize the feasible rate region of a multi-hop network with IEEE 802.11 scheduling.
2. Derive the worst case performance bounds on IEEE 802.11 in multi-hop networks: In multi-hop topologies which do not have neighborhoods larger than 20 edges, for the max-min fair rate allocation, we formally establish the following - (i) IEEE 802.11 achieves more than 16% of the optimal throughput, (ii) In any real system where the physical layer model imposes geometrical constraints on the topology, IEEE 802.11 achieves more than 30% of the optimal throughput, and (iii) In typical topologies, IEEE 802.11 attains more than 55% of the optimal throughput. Note that these bounds are comparable to the ones achieves by the state-of-the-art distributed approximations to optimal scheduling.
3. Implement distributed rate control schemes to achieve this good performance: To ensure that the complexity of scheduling has not been shifted to the rate allocation scheme, and it is possible to build a distributed rate control scheme to achieve this good performance, we build one. The proposed scheme is called WCP-CAP. Each intermediate node sends explicit and precise feedback to the sources informing them of the maximum allowable rate. We colloborated with Prof. Ramesh Govindan, Sumit Rangwala and Ki-Young Jang of the Embedded Networks Laboratory at USC on this project.

1. Apoorva Jindal and Konstantinos Psounis: Achievable Rate Region of Wireless Multi-hop Networks with 802.11 Scheduling , to appear at IEEE/ACM Transactions on Networking. (extended version)
2. Sumit Rangwala, Apoorva Jindal, Ki-Young Jang, Konstantinos Psounis, and Ramesh Govindan: Understanding Congestion Control in Multi-hop Wireless Mesh Networks, In the Proceedings of ACM MOBICOM, September 2008.