A Unified Analytical Framework of Aloha and CSMA

　

Aloha and Carrier Sense Multiple Access (CSMA) are two representative random-access protocols. Despite their simplicity in concept, the performance analysis of Aloha and CSMA networks has long been known as notoriously difficult. Numerous models and analytical approaches have been proposed in the past four decades. Yet how to integrate them into a coherent theory remains an open challenge.

Toward this end, a unified analytical framework was recently proposed in [Dai'12], based on which a comprehensive study of throughput, delay and stability performance of Aloha networks was presented. In [Dai'13], the framework is further extended to CSMA networks. The analysis shows that both CSMA and Aloha have the same bi-stable property, and the performance of both networks critically depends on the selection of backoff parameters. Different from Aloha, however, substantial gains can be achieved in CSMA networks by reducing the mini-slot length a and the collision-detection time x. The maximum throughput with CSMA is derived as an explicit function of a and x, and shown to be higher than that with Aloha if a < e^{1/e}-1 ≈ 0.445. With a small mini-slot length a, CSMA networks are also found to be more robust than Aloha networks thanks to larger stable regions of backoff parameters. To demonstrate how to properly tune the backoff parameters to stabilize the network, the complete stable region of the initial transmission probability q0 is characterized, and illustrated via the example of p-persistent CSMA with the cutoff phase K = 0. The optimal values of q0 to maximize the network throughput and to minimize the first and second moments of access delay are also obtained, which shed important light on practical network control and optimization.

In [Dai'12] and [Dai'13], the classical collision model was assumed, that is, a packet transmission is successful only if there are no concurrent transmissions. The analytical framework was further extended to incorporate the capture model in [Li-Dai'16], i.e., each node's packet is decoded independently by treating others' as background noise, and a packet can be successfully decoded as long as its received signal-to-interference-plus-noise ratio (SINR) is above a certain threshold, and the successive interference cancellation (SIC) receivers in [Li-Dai'18].

Moreover, in addition to the network throughput, the network sum rate, i.e., the average number of successfully transmitted information bits of the network per unit time, is another important performance indicator, which depends on both the throughput and the transmission rate of each node. In [Li-Dai'16] and [Sun-Dai'17], the sum rate performance was characterized for Aloha and CSMA networks, respectively. Specifically, [Li-Dai'16] considered an Aloha network where all the nodes have an identical channel gain distribution and adopt a uniform transmission rate. It was shown that there exists an inherent tradeoff between the transmission rate and the network throughput: the higher transmission rate of each packet, the fewer packets that can be successfully decoded on average, and thus the lower network throughput. The sum rate was further maximized by optimizing the transmission rate of each node, and obtained as a function of the mean received signal-to-noise ratio (SNR). The analysis reveals that similar to the sum capacity of the multiple access channel, the maximum sum rate of slotted Aloha also logarithmically increases with the mean received SNR, but the high-SNR slope is only 1/e. At the low SNR region, the maximum sum rate becomes a monotonic increasing function of the number of nodes n, and approaches 1/e log2 e ≈ 0.5307 as n goes to infinity. [Sum-Dai'17] further considered a multi-rate CSMA network where nodes may have different transmission rates. The analysis shows that to achieve the maximum sum rate, only the group of nodes with the largest transmission rate should be allowed to access the channel, which leads to severe unfairness. The maximum sum rates with two fairness constraints, throughput fairness and data-rate fairness, were further characterized, and found to be significantly lower than the unconstrained maximum sum rate when the difference in the transmission rates of nodes is large. To achieve the unconstrained maximum sum rate without sacrificing the fairness performance, power control should be adopted instead, to ensure that all the nodes have a uniform transmission rate.

Another key assumption in [Dai'12] and [Dai'13] is that a packet stays in the queue until it is successfully transmitted. In practical random-access networks, however, a packet may be discarded if it reaches the maximum number of transmission attempts. [Sun-Dai'16] further extended the analytical framework to include a retry limit M and studied the effect of M on the optimal network performance including the maximum network throughput and the minimum mean access delay. The analysis provides direct guidance on performance optimization of practical CSMA networks such as IEEE 802.11 networks.