Scheduling in multi-channel wireless networks: Rate function optimality in the small-buffer regime

Shreeshankar Bodas, Sanjay Shakkottai, Lei Ying, R. Srikant

Research output: Contribution to journalArticle

Abstract

The problem of designing scheduling algorithms for a multichannel (e.g., orthogonal frequency division multiplexing-based) wireless downlink network is considered. The classic MaxWeight algorithm, although throughput-optimal, results in a very poor per-user delay performance in such systems. Hence, an alternate class of algorithms called iterated longest queues first (iLQF) is proposed for overcoming this issue. The iLQF-class algorithms are analyzed in a number of different system configurations. A particular algorithm in this class, called iLQF with pullup, is shown to be rate function optimal for the problem in an appropriate large deviations setting, and is shown to result in a strictly positive value of the rate function for a number of modifications to the basic system model. Thus, the proposed algorithm yields provable performance guarantees. The analytic results are confirmed through simulations.

Original languageEnglish (US)
Article number6676840
Pages (from-to)1101-1125
Number of pages25
JournalIEEE Transactions on Information Theory
Volume60
Issue number2
DOIs
StatePublished - Feb 2014

    Fingerprint

Keywords

  • Delay optimality
  • large deviations
  • perfect matchings
  • random bipartite graphs
  • scheduling algorithms
  • small buffer

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this