Stability analysis of collision resolution protocols with retransmission diversity

A class of collision resolution protocols [(B)NDMA] has recently been introduced for slotted packet multiple access, building on the concept of retransmission diversity. These protocols offer the means to improve upon random splitting-based collision resolution protocols, at a moderate complexity cost. However, stability of these protocols has not been established, and the available steady-state analysis is restricted to symmetric (common-rate) systems. In this paper, we formally analyze stability of (B)NDMA, by providing sufficient conditions that guarantee ergodicity of the associated embedded Markov chain. A key tool is the concept of dominant system, which we borrow from the literature on stability analysis of finite population slotted ALOHA. After establishing stability, we take a fresh look at steady-state analysis, bypassing the earlier generating function approach, using instead only balance equations which hold for a stable system. This approach allows dealing with asymmetry (multirate systems), yielding expressions for throughput and delay per queue. Finally, we generalize BNDMA and the associated stability analysis to multicode systems.