TY - JOUR

T1 - Nearly-optimal scheduling of users with Markovian time-varying transmission rates

AU - Cecchi, Fabio

AU - Jacko, Peter

N1 - This is the author’s version of a work that was accepted for publication in Performance Evaluation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Performance Evaluation, 99-100, 2016 DOI: 10.1016/j.peva.2016.02.002

PY - 2016/5

Y1 - 2016/5

N2 - We address the problem of developing a well-performing and implementable scheduler of users with wireless connections to the central controller, which arise in areas such as mobile data networks, heterogeneous networks, or vehicular communications systems. The main feature of such systems is that the connection quality of each user is time-varying, resulting in time-varying transmission rate corresponding to available channel states. We assume that this evolution is Markovian, relaxing the common but unrealistic assumption of stationary channels. We first focus on the three-state channel and study the optimal policy, showing that threshold policies (of giving higher priority to users with higher transmission rate) are not necessarily optimal. For the general channel we design a scheduler which generalizes the recently proposed Potential Improvement (PI) scheduler, and propose its two practical approximations, whose performance is analyzed and compared to existing alternative schedulers in a variety of simulation scenarios. We suggest and give evidence that the variant of PI which only relies on the steady-state distribution of the channel, performs extremely well, and therefore should be used for practical implementation.

AB - We address the problem of developing a well-performing and implementable scheduler of users with wireless connections to the central controller, which arise in areas such as mobile data networks, heterogeneous networks, or vehicular communications systems. The main feature of such systems is that the connection quality of each user is time-varying, resulting in time-varying transmission rate corresponding to available channel states. We assume that this evolution is Markovian, relaxing the common but unrealistic assumption of stationary channels. We first focus on the three-state channel and study the optimal policy, showing that threshold policies (of giving higher priority to users with higher transmission rate) are not necessarily optimal. For the general channel we design a scheduler which generalizes the recently proposed Potential Improvement (PI) scheduler, and propose its two practical approximations, whose performance is analyzed and compared to existing alternative schedulers in a variety of simulation scenarios. We suggest and give evidence that the variant of PI which only relies on the steady-state distribution of the channel, performs extremely well, and therefore should be used for practical implementation.

KW - Wireless networks

KW - Opportunistic scheduling

KW - Non-stationary

KW - Performance evaluation

KW - Stability

KW - Markov decision processes

KW - Stochastic scheduling

U2 - 10.1016/j.peva.2016.02.002

DO - 10.1016/j.peva.2016.02.002

M3 - Journal article

VL - 99-100

SP - 16

EP - 36

JO - Performance Evaluation

JF - Performance Evaluation

SN - 0166-5316

ER -