Provable fairness for TDMA scheduling

Marcin Bienkowski, Jaroslaw Byrka, Krzysztof Chrobak, Tomasz Jurdzinski, Dariusz Kowalski

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the task of assigning time slots on a user-dependent and time-varying wireless channel. This scheduling problem occurs in cellular networks due to the presence of channel fading and user mobility. We introduce a simple notion of global fairness, where each of n users is guaranteed a 1/(n + ε) fraction of its total possible throughput, for some approximation parameter ε ≥ 0, and study its limitations from theoretical and experimental perspectives. We formally prove that a slight modification of the standard proportional fair algorithm satisfies the global fairness constraint. To the best of our knowledge, this is the first formal analysis providing global fairness property to the channel in any execution and any channel conditions. As confirmed by our simulations, our global fairness constraint is in fact satisfied by a wide class of algorithms. Our framework allows optimization of an arbitrary metric subject to the global fairness constraint. In particular, we have analyzed a variant of the provably fair algorithm that optimizes the total throughput. It turned out that the channel utilization of this algorithm is significantly better than that of the classical Proportional Fair algorithm.

Original languageEnglish (US)
Title of host publication2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781479983810
StatePublished - Aug 21 2015
Externally publishedYes
Event34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015 - Hong Kong, Hong Kong
Duration: Apr 26 2015May 1 2015

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015
Country/TerritoryHong Kong
CityHong Kong


  • fairness
  • Proportional Fair algorithms
  • throughput
  • Wireless channel

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Provable fairness for TDMA scheduling'. Together they form a unique fingerprint.

Cite this