Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multichannel Wireless Networks With Low Complexity: A Practical Greedy Scheduling Policy
Lists
Only you see this
Abstract
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.5</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> +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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.5</sup> logn) of the hybrid policies to 2n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> + 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.
BibTeX
@article{ji2015achieving,
author = {Bo Ji and Gagan Gupta and Manu Sharma and Xiaojun Lin and Ness B. Shroff},
title = {{Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multichannel Wireless Networks With Low Complexity: A Practical Greedy Scheduling Policy}},
journal = {IEEE/ACM Trans. Networking},
year = {2015},
url = {https://openreview.net/forum?id=Yeyb9drIcU},
}Loading related content...