WNCG Seminar: On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks

Much of the prior work on scheduling algorithms for wireless networks focuses on maximizing throughput. However, for many real-time applications, delays and deadline guarantees on packet delivery can be more important than long-term throughput. In this talk, we consider the problem of scheduling deadline-constrained packets in wireless networks, under a conflict-graph interference model. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio. This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First). In this talk, we pursue a different approach through a careful randomization over the choice of maximal links that can transmit at each time. We design randomized policies that can achieve delivery ratios much higher than what is achievable by LDF. Further, our results apply to traffic (arrival and deadline) processes that evolve as a (unknown) positive recurrent Markov chain. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work.