TCS Journal 2014 Journal Article
Comparative study of approximation algorithms and heuristics for SINR scheduling with power control
- Lukas Belke
- Thomas Kesselheim
- Arie M.C.A. Koster
- Berthold Vöcking
Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on designing and analyzing approximation algorithms with provable approximation guarantees. While these studies revealed interesting effects from a theoretical perspective, so far there has not been a systematic evaluation of the theoretical results in simulations. In this paper, we examine the performance of various approximation algorithms and heuristics for the common scheduling problems on instances generated by different random network models, e. g. , taking clustering effects into account. Using (mixed) integer linear programming, we are able to compute the theoretical optima for some of these instances such that the performance of the different algorithms can be compared with these optima. The simulations support the practical relevance of the theoretical findings. For example, setting transmission powers by a square-root power assignment, the network's capacity increases significantly in comparison to uniform power assignments. Furthermore, the developed approximation algorithms are able to exploit this gap providing in general a better performance than any algorithm using uniform transmission powers, even with unlimited computational power. The obtained results are robust against changes in parameters and network generation models.