Provable fairness for TDMA scheduling

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.