Carrier-sense multiple access collision avoidance networks have often been analyzed using a stylized model that is fully characterized by a vector of back-off rates and a conflict graph. Furthermore, for any achievable throughput vector @math , the existence of a unique vector @math of back-off rates that achieves this throughput vector was proven. Although this unique vector can in principle be computed iteratively, the required time complexity grows exponentially in the network size, making this only feasible for small networks. In this paper, we present an explicit formula for the unique vector of back-off rates @math needed to achieve any achievable throughput vector @math provided that the network has a chordal conflict graph. This class of networks contains a number of special cases of interest such as (inhomogeneous) line networks and networks with an acyclic conflict graph. Moreover, these back-off rates are such that the back-off rate of a node only depends on its own target throughput and the target throughput of its neighbors and can be determined in a distributed manner. We further indicate that back-off rates of this form cannot be obtained in general for networks with non-chordal conflict graphs. For general conflict graphs, we nevertheless show how to adapt the back-off rates when a node is added to the network when its interfering nodes form a clique in the conflict graph. Finally, we introduce a distributed chordal approximation algorithm for general conflict graphs, which is shown (using numerical examples) to be more accurate than the Bethe approximation.
Decentralized medium access control schemes for wireless networks based on CSMA CA, such as the IEEE 802.11 protocol, are known to be unfair. In multihop networks, they can even favor some links to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood. We find that the capture effect and the relative values of the receive and carrier sensing ranges play a crucial role in the performance of these protocols. Using a simple Markovian model, we show that an idealized CSMA CA protocol suffers from starvation when the receiving and sensing ranges are equal, but quite surprisingly that this unfairness is reduced or even disappears when these two ranges are sufficiently different. We also show that starvation has a positive counterpart, namely organization. When its access intensity is large the protocol organizes the transmissions in space in such a way that it maximizes the number of concurrent successful transmissions. We obtain exact formula for the so-called spatial reuse of the protocol on large line networks. Random-access algorithms such as CSMA provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years, tractable stochastic models have been shown to yield accurate throughput estimates for CSMA networks. We consider a saturated random-access network on a general conflict graph, and prove that for every feasible combination of throughputs, there exists a unique vector of back-off rates that achieves this throughput vector. This result entails proving global invertibility of the non-linear function that describes the throughputs of all nodes in the network. We present several numerical procedures for calculating this inverse, based on fixed-point iteration and Newton's method. Finally, we provide closed-form results for several special conflict graphs using the theory of Markov random fields. We characterize the fairness of decentralized medium access control protocols based on CSMA CA, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of these protocols in small network topologies does not always persist in large topologies. In regular networks, this unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large 1D lattice networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In 2D lattice networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. In irregular networks, the topology is inherently unfair. This unfairness increases with the access intensity of the protocol, but in a much smoother way than in regular two-dimensional networks. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness. Random-access networks may exhibit severe unfairness in throughput, in the sense that some nodes receive consistently higher throughput than others. Recent studies show that this unfairness is due to local differences in the neighborhood structure: nodes with fewer neighbors receive better access. We study the unfairness in saturated linear networks, and adapt the random-access CSMA protocol to remove the unfairness completely, by choosing the activation rates of nodes as a specific function of the number of neighbors. We then investigate the consequences of this choice of activation rates on the network-average saturated throughput, and we show that these rates perform well in non-saturated settings.