Wireless Mesh Network Capacity Achievable Over the CSMA/CA MAC

Abstract—This paper presents a theoretical analysis of the max-imum throughput of a wireless mesh backhaul network that is achievable over a practical carrier sense multiple access with col-lision avoidance (CSMA/CA) medium access control (MAC) pro-tocol. We resort to the multicommodity flow (MCF) formulation augmented with the conflict-graph constraints, whereas we use a novel approach to take into account the collision overhead in the distributed CSMA/CA MAC. Such overhead due to random access has been ignored by existing MCF-based capacity studies, which assume impractical centralized scheduling and result in aggressive capacity planning, which is unachievable over the CSMA/CA MAC. This paper makes the following three main contributions: 1) we develop a generic method of integrating the CSMA/CA MAC analysis with the MCF formulation for optimal network capacity analysis, which readily generates an upper bound of the network throughput; 2) we define a new concept of CSMA/CA clique and theoretically study its relationship to a CSMA/CA area in terms of throughput; and 3) using the CSMA/CA clique as a tool, we derive a lower bound of the network throughput achievable over the CSMA/CA MAC by clique-based MCF formulation. NS-2 simulation results are presented to demonstrate the tightness of the upper and lower bounds that are newly developed, compared to those based on the MCF formulation assuming a slotted system and centralized scheduling. Index Terms—Carrier sense multiple access with collision avoidance (CSMA/CA), conflict graph, multicommodity flow (MCF), network capacity, wireless mesh network. I