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

作者：Ji Bo^*; Gupta Gagan R; Sharma Manu; Lin Xiaojun; Shroff Ness B

来源：IEEE/ACM Transactions on Networking, 2015, 23(3): 880-893.

DOI：10.1109/TNET.2014.2313120

• Greedy algorithm
• large deviations
• multichannel
• near-optimal asymptotic delay
• OFDM
• optimal throughput
• practical
• rate-function
• scheduling
• wireless networks

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 0(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(2) + 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) log n) of the hybrid policies to 2n2 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.

• 出版日期2015-6
• 单位AT&T Labs