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

Thursday, February 20, 2020
EER 3.646

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.


Photo of Prof. Javad Ghaderi
Associate Professor
Columbia University

Javad Ghaderi is an Associate Professor of Electrical Engineering at Columbia University. His research interests include algorithms, optimization, and stochastic processes with application to wireless networks and data centers. He received his B.Sc. from the University of Tehran, Iran, in 2006, M.Sc. from the University of Waterloo, Canada, in 2008, and Ph.D. from the University of Illinois at Urbana-Champaign (UIUC) in 2013. He spent a one-year Simons Postdoctoral Fellowship at the University of Texas at Austin before joining Columbia. He is the recepient of several awards including Best Student Paper Finalist at the 2013 American Control Conference (ACC), Best Paper Award at ACM CoNEXT 2016, and NSF CAREER Award in 2017.