High-Throughput Random Access Using Successive Interference Cancellation in a Tree Algorithm

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> Random access is well motivated and has been widely applied when the network traffic is bursty and the expected throughput is not high. The main reason behind relatively low-throughput expectations is that collided packets are typically discarded. In this paper, we develop a novel protocol exploiting successive interference cancellation (SIC) in a tree algorithm (TA), where collided packets are reserved for reuse. Our SICTA protocol can achieve markedly higher maximum stable throughput relative to existing alternatives. Throughput performance is analyzed for general <emphasis><formula formulatype="inline"> <tex>$d$</tex></formula></emphasis>-ary SICTA with both gated and window access. It is shown that the throughput for <emphasis><formula formulatype="inline"> <tex>$d$</tex></formula></emphasis>-ary SICTA with gated access is about <emphasis><formula formulatype="inline"><tex>$(\ln d)/(d-1)$</tex></formula></emphasis>, and can reach <emphasis><formula><tex>$0.693$</tex></formula></emphasis> for <emphasis><formula formulatype="inline"><tex>$d=2$</tex></formula></emphasis>. This represents a 40% increase over the renowned first-come-first-serve (FCFS) <emphasis><formula> <tex>$0.487$</tex></formula></emphasis> tree algorithm. Delay performance is also analyzed for SICTA with gated access, and numerical results are provided. </para>