On the Throughput-Optimality of CSMA Policies in Multihop Wireless Networks

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 ap-propriate 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 ap-proximate 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