Modeling media access in embedded two-flow topologies of multi-hop wireless networks

In this paper, we decompose a large- or small-scale multi-hop wireless network into embedded subgraphs, each consisting of four nodes and two flow pairs. We systematically study all twelve possible topologies that arise according to whether the different nodes are in radio range of each other. We show that under both a random spatial distribution of nodes and random waypoint mobility with shortest-path routing, a critical and highly probable scenario is a class in which the channel state shared by the two flows is not only incomplete (i.e., the graph is not fully connected), but there is also asymmetry in the state between the two flows. We develop an accurate analytical model validated by simulations to characterize the long-term unfairness that naturally arises when CSMA with two- or four-way handshake is employed as a random access protocol. Moreover, we show that another key class of topologies consists of incomplete but symmetric shared state. We show via modeling and simulations that in this case, the system achieves long-term fairness, yet endures significant durations in which one flow dominates channel access with many repeated transmissions before relinquishing the channel. The model predicts the time-scales of this unfairness as a function of system parameters such as the maximum retransmission limit.