Optimality and robustness in opportunistic scheduler design for wireless networks

textWe investigate in detail two multiuser opportunistic scheduling problems in centralized wireless systems: the scheduling of "delay-sensitive" flows with packet delay requirements of a few tens to few hundreds of milliseconds over the air interface, and the scheduling of "best-effort" flows with the objective of minimizing mean file transfer delay. Schedulers for delay-sensitive flows are characterized by a fundamental tradeoff between "maximizing total service rate by being opportunistic" and "balancing unequal queues (or delays) across users". In choosing how to realize this tradeoff in schedulers, our key premise is that "robustness" should be a primary design objective alongside performance. Different performance objectives -- mean packet delay, the tail of worst user's queue distribution, or that of the overall queue distribution -- result in remarkably different scheduling policies. Different design objectives and resulting schedulers are also not equally robust, which is important due to the uncertainty and variability in both the wireless environment and the traffic. The proposed class of schedulers offers low packet delays, less sensitivity to the scheduler parameters and channel characteristics, and a more graceful degradation of service in terms of the fraction of users meeting their delay requirements under transient overloads, when compared with other well-known schedulers. Schedulers for best-effort flows are characterized by a fundamental tradeoff between "maximizing the total service rate" and "prioritizing flows with short residual sizes". We characterize two regimes based on the "degree" of opportunistic gain present in the system. In the first regime -- where the opportunistic capacity of the system increases sharply with the number of users -- the use of residual flow-size information in scheduling will 'not' result in a significant reduction in flow-level delays. Whereas, in the second regime -- where the opportunistic capacity increases slowly with the number of users -- using flow-size information alongside channel state information 'may' result in a significant reduction. We then propose a class of schedulers which offers good performance in either regime, in terms of mean file transfer delays as well as probability of blocking for systems that enforce flow admission control. This thesis provides a comprehensive theoretical study of these fundamental tradeoffs for opportunistic schedulers, as well as an exploration of some of the practical ramifications to engineering wireless systems.Electrical and Computer Engineerin