Low-Complexity Scheduling Algorithms for Multichannel Downlink Wireless Networks
This paper considers the problem of designing scheduling algorithms for multichannel (e.g., OFDM-based) wireless downlink networks, with a large number of users and proportionally large bandwidth. For this system, while the classical Max Weight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in the authors' setting). To address this, a class of algorithms called iterated Heaviest matching with Longest Queues First (iHLQF) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function-optimal (i.e., exponentially small buffer overflow probability) for certain arrival/ channel processes.