Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multichannel Wireless Networks With Low Complexity: A Practical Greedy Scheduling Policy

In this paper, we focus on the scheduling problem in multichannel wireless networks, e.g., the downlink of a single cell in fourth-generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of O(n^2.5 log n)-complexity hybrid scheduling policies is recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a lower complexity 2n²+2n, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, the rate-function of the delay-violation probability attained by D-SSG for any fixed integer delay threshold b > 0 is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Thus, we are able to achieve a reduction in complexity (from O(n^2.5 logn) of the hybrid policies to 2n² + 2n) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the O(·) notation. Finally, we conduct simulations to validate our theoretical results in various scenarios. The simulation results show that in all scenarios we consider, D-SSG not only guarantees a near-optimal rate-function, but also empirically has a similar delay performance to the rate-function delay-optimal policies.