High-throughput random access using successive interference cancellation in a tree algorithm

Research output: Contribution to journalArticlepeer-review

88 Scopus citations


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 d-ary SICTA with both gated and window access. It is shown that the throughput for d-ary SICTA with gated access is about (ln d)/(d - 1), and can reach 0.693 for d = 2. This represents a 40% increase over the renowned first-come-first-serve (FCFS) 0.487 tree algorithm. Delay performance is also analyzed for SICTA with gated access, and numerical results are provided.

Original languageEnglish (US)
Pages (from-to)4628-4639
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number12
StatePublished - 2007

Bibliographical note

Funding Information:
Manuscript received February 9, 2005; revised November 4, 2006. This work was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U. S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U. S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. The material in this paper was presented in part at IEEE INFOCOM’05, Miami, FL, March 2005.


  • Collision resolution
  • Markov chain
  • Maximum stable throughput
  • Random access
  • Tree protocol


Dive into the research topics of 'High-throughput random access using successive interference cancellation in a tree algorithm'. Together they form a unique fingerprint.

Cite this