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 efficient scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a recently developed scheduling policy, called Delay Weighted Matching (DWM) , has been shown to be \log n) complexity hybrid scheduling policies are recently developed to guarantee } both rate-function delay-optimal (in the many-channel many-user asymptotic regime) and throughput-optimal (in general non-asymptotic setting), it has a high complexity O(n^5), which makes it impractical for modern OFDM systems . To address this issue, we first develop a simple greedy policy called Delay-based Queue-Side-Greedy (D-QSG ) with a lower complexity O(n ^3 ), and rigorously prove that D-QSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically, the rate-function attained by D-QSG for any fixed integer threshold b>0, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n^2), and show that D-SSG achieves the same performance as D-QSG. Thus, we are able to achieve a dramatic reduction in complexity (from O(n ^5) of DWM \log n) of the hybrid policies } to O(n^2)) with a minimal drop in the delay performance.  Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that our proposed greedy policies not only guarantee a near-optimal rate-function, but also empirically are virtually indistinguishable from the delay-optimal policy DWM .
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 ), 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 .
R
efficient
practical
R
recently developed scheduling policy, called Delay Weighted Matching (DWM) , has been shown to be
class of O(n^{2.5
R
delay-optimal
delay optimality
R
throughput-optimal
throughput optimality
R
it has a high complexity O(n^5), which makes it impractical for modern OFDM systems
their practical complexity is typically high
D
first
R
Queue-Side-Greedy (D-QSG
Server-Side-Greedy (D-SSG
R
^3
^2
R
D-QSG
D-SSG
R
D-QSG
D-SSG
D
Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n^2), and show that D-SSG achieves the same performance as D-QSG.
D
dramatic
R
^5) of DWM
^{2.5
A
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.
R
our proposed greedy policies not only guarantee
D-SSG not only guarantees
R
are
is
D
the
R
policy DWM
policies