On the Efficiency of CSMA-CA Scheduling in Wireless Multihop Networks

This paper establishes that random access scheduling schemes, and more specifically CSMA-CA, yield exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms that grossly underutilize the available capacity that random access provides. To establish our thesis, we first compare the achievable rate region of CSMA-CA and optimal in a number of carefully constructed multihop topologies and find that CSMA-CA is always within 48% of the optimal. Motivated by this result, we next characterize the worst-case performance of CSMA-CA in neighborhood topologies representing the congested regions of larger multihop topologies by deriving the neighborhood topology that yields the worst-case throughput ratio for CSMA-CA and find that in neighborhood topologies with less than 20 edges: 1) CSMA-CA is never worse than 16% of the optimal when ignoring physical-layer constraints; and 2) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst-case bounds, CSMA-CA is surprisingly efficient.