Abstract

We analyze the class of Carrier Sense Multiple Access (CSMA) policies for scheduling packet transmissions in multihop wireless networks with primary interference constraints. Our main result is to establish that, in an appropriate limiting regime of large networks with a small sensing period, CSMA policies are capacity-achieving. While such efficiency characteristics of CSMA policies has been well-established in the special case of single-hop networks, their analysis for general multihop networks has been an open problem due to the complexity of the interaction among coupled interference constraints. To answer this problem, we first introduce a novel fixed point equation to approximate the CSMA policy performance, and prove that the approximation becomes accurate for large networks with a small sensing period. Then, we use this approximation to characterize the achievable rate region of static CSMA schedulers, and show that the achievable rate region asymptotically converges to the capacity region of the network under primary interference constraints. This work reveals that random access schemes, which can operate asynchronously, can be used in large networks to serve many flows efficiently. Our empirical investigations also indicate that the accuracy of our fixed point formulation is achieved even for moderately sized networks. This result has important implications for network algorithm design for ad hoc networks in that it reveals for the first time that random channel access schemes with attractive complexity, overhead, distributiveness, and asynchronism characteristics can achieve maximum throughput in large multihop networks.

 

Manuscript

 

Bibtex