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.
The well-known product form to analyze the throughput of idealized CSMA CA networks with a general conflict graph was first introduced in @cite_13 , where its insensitivity with respect to the packet length distribution was also shown. Insensitivity with respect to the length of the back-off period was proven much later in @cite_30 @cite_3 .
@cite_30 @cite_13 @cite_3
2125890347 2029650413 2096448929
Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years, fairly tractable models have been shown to yield remarkably accurate throughput estimates for CSMA networks. These models typically assume that both the transmission durations and the back-off periods are exponentially distributed. We show that the stationary distribution of the system is in fact insensitive with respect to the transmission durations and the back-off times. These models primarily pertain to a saturated scenario where nodes always have packets to transmit. In reality however, the buffers may occasionally be empty as packets are randomly generated and transmitted over time. The resulting interplay between the activity states and the buffer contents gives rise to quite complicated queueing dynamics, and even establishing the stability criteria is usually a serious challenge. We explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulties arising in other cases. In this paper, we use a Markov model to develop a product form solution to efficiently analyze the throughput of arbitrary topology multihop packet radio networks that employ a carrier sensing multiple access (CSMA) protocol with perfect capture. We consider both exponential and nonexponential packet length distributions. Our method preserves the dependence between nodes, characteristic of CSMA, and determines the joint probability that nodes are transmitting. The product form analysis provides the basis for an automated algorithm that determines the maximum throughput in networks of size up to 100 radio nodes. Numerical examples for several networks are presented. This model has led to many theoretical and practical extensions. These include determination of conditions for product form analysis to hold, extension to other access protocols, and consideration of acknowledgments. This work started out with our discovery of a pattern of throughput distributions among links in IEEE 802.11 networks from experimental results. This pattern gives rise to an easy computation method, which we term back-of-the-envelop (BoE) computation. For many network configurations, very accurate results can be obtained by BoE within minutes, if not seconds, by simple hand computation. This allows us to make shortcuts in performance evaluation, bypassing complicated stochastic analysis. To explain BoE, we construct a theory based on the model of an “ideal CSMA network” (ICN). The BoE computation method emerges from ICN when we take the limit c → 0, where c is the ratio of the mean backoff countdown time to the mean transmission time in the CSMA protocol. Importantly, we derive a new mathematical result: the link throughputs of ICN are insensitive to the distributions of the backoff countdown time and transmission time (packet duration) given the ratio of their means c. This insensitivity result explains why BoE works so well for practical 802.11 networks, in which the backoff countdown process is one that has memory, and in which the packet size can be arbitrarily distributed. Our results indicate that BoE is a good approximation technique for modest-size networks such as those typically seen in 802.11 deployments. Beyond explaining BoE, the theoretical framework of ICN is also a foundation for fundamental understanding of very-large-scale CSMA networks. In particular, ICN is similar to the Ising model in statistical physics used to explain phenomena arising out of the interactions of a large number of entities. Many new research directions arise out of the ICN model.