Low-complexity scheduling algorithms for multichannel downlink wireless networks

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

Research output: Contribution to journalArticle

Abstract

This paper considers the problem of designing scheduling algorithms for multichannel (e.g., OFDM-based) wireless downlink networks, with a large number of users and proportionally large bandwidth. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iterated Heaviest matching with Longest Queues First (iHLQF) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function-optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF, however, has higher complexity than MaxWeight (n 4 versus n 2 , respectively). To overcome this issue, a new algorithm called Server-Side Greedy (SSG) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n 2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice tradeoff between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

Original languageEnglish (US)
Article number6161621
Pages (from-to)1608-1621
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume20
Issue number5
DOIs
StatePublished - Mar 2 2012

    Fingerprint

Keywords

  • Large deviations
  • low complexity
  • scheduling algorithms
  • small buffer

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this