Utility-optimal random access without message passing

A. Hamed Mohsenian Rad, Jianwei Huang, Mung Chiang, Vincent W.S. Wong

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.

Original languageEnglish (US)
Article number4801448
Pages (from-to)1073-1079
Number of pages7
JournalIEEE Transactions on Wireless Communications
Issue number3
StatePublished - Mar 2009

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Applied Mathematics


  • Message passing
  • Network utility maximization
  • Non-convex optimization
  • Random access
  • Wireless scheduling


Dive into the research topics of 'Utility-optimal random access without message passing'. Together they form a unique fingerprint.

Cite this