Research Article
Stability and asymptotic optimality of opportunistic schedulers in wireless systems
@INPROCEEDINGS{10.4108/icst.valuetools.2011.245741, author={Urtzi Ayesta and Martin Erausquin and Matthieu Jonckheere and Ina Maria Verloop}, title={Stability and asymptotic optimality of opportunistic schedulers in wireless systems}, proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools}, publisher={ICST}, proceedings_a={VALUETOOLS}, year={2012}, month={6}, keywords={wireless system stability asymptotically optimal opportunistic scheduling \textdollar{}c\textbackslashmu\textdollar{}-rule}, doi={10.4108/icst.valuetools.2011.245741} }- Urtzi Ayesta
Martin Erausquin
Matthieu Jonckheere
Ina Maria Verloop
Year: 2012
Stability and asymptotic optimality of opportunistic schedulers in wireless systems
VALUETOOLS
ICST
DOI: 10.4108/icst.valuetools.2011.245741
Abstract
We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted and users arrive and depart upon service completion. This may model for example the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: (1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based, Proportionally Best or Potential Improvement are stable under the maximum stability conditions, whereas Relative-Best or the cmu-rule are not. (2) We show that choosing the right tie-breaking rule is crucial for the performance as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. In particular, we show that simple priority-index policies with a myopic tie-breaking rule, are stable and asymptotically optimal.