Tree-Algorithms with Multi-Packet Reception and Successive Interference Cancellation

In this paper, we study binary tree-algorithms that exploit a combination of multi-packet reception (MPR) and successive interference cancellation (SIC), which so far has not been considered in the literature. Specifically, we assume that the receiver is capable of successfully decoding any collision of up to and including K concurrent packet transmissions and can perform SIC along the tree. We show a number of novel results for this type of tree algorithms. We first derive the basic performance parameters, which are the expected length of the collision resolution interval and the throughput normalized with K , conditioned on the number of contending users. We then analyze their asymptotic behaviour, identifying an oscillatory component that amplifies as K increases. In the next step, we derive the maximum stable throughput (MST) for the gated and windowed access assuming Poisson arrivals. We show that for windowed access, the bound on MST normalized with K increases with K. Finally, we discuss practical issues related to implementation of such scheme, as well as compare it to slotted ALOHA-based schemes that exploit both K -MPR and SIC.