From LINC
Overview
There is an ever-growing demand for real-time applications such as GPS, streaming video, VoIP etc. that today's mobile communication devices must support. However, the network resources (time/frequency/codes) that these devices use are limited, and must be shared. Therefore, scheduling algorithms that control the access to the resources is an important parameter impacting the performance of a wireless network. A good scheduling algorithm can greatly improve the performance of a network with limited resources.
The downlink of a wireless network refers to the channel from the base-station to the mobile device(s). In emerging standards such as WiMax and LTE, an OFDM-based wireless downlink is used. OFDM stands for Orthogonal Frequency Division Multiplexing, where the downlink bandwidth available at the base-station is divided into several tens to hundreds of orthogonal channels (frequency bands), and a given channel can potentially serve different users over time, but only one user in any given timeslot. Some typical numbers for such a system are as follows:
- 20 MHz downlink bandwidth
- 50 sub-bands (channels)
- Each channel can support ~ 400 kb/s
- Timeslot = 5 ms
Mathematical details
The wireless downlink system can be thought of as a multi-queue multi-server queuing system. There are m queues in the system (corresponding to the m mobile users), n servers (corresponding to the n frequency bands), and each queue is connected to each server by a time-varying channel. There are random external packet arrivals to the queues. A given server can serve at most one queue in a given timeslot, and when it is allocated for service, it provides a time-dependent data-rate to the corresponding user. Our aim is to design a scheduling algorithm for this system that meets certain performance criteria as explained in the following.
Quantifying a good scheduling algorithm
- Our first objective is to design a throughput-optimal algorithm. A throughput-optimal algorithm is one that stabilizes the system (makes the queues positive recurrent) under a given arrival process if there is any other (causal/non-causal) algorithm (possibly designed for the particular arrival process) that can do so. It is well-known in the community that the MaxWeight algorithm by Tassiulas and Ephremides, under very mild assumptions on the allowed arrival and channel processes, is throughput-optimal for this and many other networks.
- We require the algorithm to result in a good delay performance. Real-time traffic (voice/video) is very sensitive to packet delay, and to ensure a good quality of service, we desire that the per-user delay be small. User-perceived delay, in turn, is closely related to the queue-lengths at the base-station. Therefore, we require that the algorithm result in small queues at the base-station, in a large deviations sense. More formally, we consider a system with a large number of users and large bandwidth (which is the typically anticipated scenario for the next generation wireless networks), and fix a finite buffer overflow threshold, b. In a given timeslot, if even one of the user-queues is longer than b, then we call it an overflow event. We want the overflow event to have as large a rate function as possible.
- We desire the algorithm to have a small computational complexity, where the definition of small is subjective! We use the complexity of the classic MaxWeight algorithm as a benchmark.
Our contribution
In [1], we proposed a class of algorithms called iLQF for the above problem, and showed that a particular algorithm in this class, namely iLQF with PullUp, is rate-function optimal for the overflow event. Its computational complexity however is somewhat large: O(m2n2), as compared to O(mn) for the MaxWeight algorithm. We have ongoing work on its throughput-optimality and also on reducing its complexity.
The following LiNC members are involved in this research area: