Utility-optimal random access: Reduced complexity, fast convergence, and robust performance

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

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


In this paper, we propose two distributed contention-based medium access control (MAC) algorithms for solving a network utility maximization (NUM) problem in wireless ad hoc networks. Most of the previous NUM-based random access algorithms have one or more of the following performance bottlenecks: (1) extensive signaling among the nodes to achieve semi-distributed implementations, (2) synchronous updates of contention probabilities, (3) small update stepsizes to ensure convergence but with typically slow speed, and (4) supporting a limited range of utility functions under which the NUM is shown to be convex. Our proposed algorithms overcome the bottlenecks in all four aspects. First, only limited amount of message passing among nodes is required. Second, fully asynchronous updates of contention probabilities are allowed. Furthermore, our algorithms are robust to arbitrary large message passing delay and message loss. Third, we do not utilize any stepsize during updates, thus our algorithms can achieve faster convergence. Finally, our proposed algorithms have provable convergence, optimality, and robustness properties under a wider range of utility functions, even if the NUM problem is non-convex. Simulation results show the optimality and fast convergence of our algorithms, performance improvements compared with the subgradient-based MAC, and better efficiency-fairness tradeoff compared with the IEEE 802.11 distributed coordination function.

Original languageEnglish (US)
Article number4786452
Pages (from-to)898-911
Number of pages14
JournalIEEE Transactions on Wireless Communications
Issue number2
StatePublished - Feb 2009

All Science Journal Classification (ASJC) codes

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


  • Complexity reduction
  • Contention-based medium access control
  • Network utility maximization
  • Non-convex optimization
  • Robust design
  • α-fair utility functions


Dive into the research topics of 'Utility-optimal random access: Reduced complexity, fast convergence, and robust performance'. Together they form a unique fingerprint.

Cite this