In this paper, we focus on the scheduling problem in multi-channel 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 are recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in  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 O(n^2) \lower  , and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically,  the rate-function attained by D-SSG for any fixed integer 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 O(n^2 ) ) 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(\cdot) notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies.
In this paper, we focus on the scheduling problem in multi-channel 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 are 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, we show that the rate-function attained by D-SSG for any delay-violation threshold b , 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 2n^2 + 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(\cdot) notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies.
R
complexity
-complexity
A
the
D
lower complexity O(n^2)
A
complexity 2n^2+2n
R
rate-function-based
asymptotic
A
we show that
R
fixed integer threshold b>0
delay-violation threshold b
R
O(n^2 )
2n^2 + 2n