Quality-of-service analysis of scheduling algorithms in wireless networks

Recent advance in wireless communications has led to increasing demands on wireless systems. There are inherent limitations on the performance of such systems due to physical constraints such as finite bandwidth, power, interference and fading. The adverse effects of interference and fading can be mitigated by intelligent scheduling algorithms. Significant effort has been put forth by the research community in understanding the impact of scheduling algorithms on network performance. A well-celebrated milestone is the development of throughput-optimal scheduling algorithms. These are algorithms that will stabilize the system whenever it is possible to stabilize the system using any other algorithm. While stability is a useful first-order measure of success, many delay-sensitive wireless applications require stronger guarantees on the Quality-of-Service (QoS). Unfortunately, there have been few results in the literature on the QoS guarantees of scheduling algorithms. In this thesis, we are interested in QoS metrics in the form of the probability that a certain function f(Q) of the backlog vector Q exceeds a threshold B, where the function f(˙) is designed to reflect the delay requirement of the system. The question of how to design scheduling algorithms that minimize the aforementioned overflow probability turns out to be very challenging. One of the reasons is that for general queuing systems, there is no closed form solution for the distribution of queue lengths in the system. The approach that we take is to use the theory of large deviations to study the asymptotic decay-rate of the overflow probability when the threshold B becomes large. A scheduling algorithm is said to be QoS-optimal in the large-deviations sense when it maximizes this large deviations decay-rate. The main contributions of this dissertation are the following. For a general network topology with multi-hop transmission of multiple flows subject to general interference constraints, we provide a sufficient condition to determine when a scheduling algorithm is QoS-optimal. We study several commonly used multi-hop wireless systems such as convergecast to the root in a tree topology and end-to-end data transfer in a system with acyclic multihop flows, and use the aforementioned condition to provide insights into the behavior of the optimal scheduling algorithm. We then successfully turned the insights into novel practical scheduling algorithms and proved their optimality both in theory and via simulations