Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multichannel Wireless Networks
- 5 December 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (6) , 1911-1924
Abstract
In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n 2.5 log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n 5 ). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.Keywords
All Related Versions
Funding Information
- ARO MURI (W911NF-08-1-0238)
- NSF (CNS-1065136, CNS-1012700, CNS-0643145)
This publication has 21 references indexed in Scilit:
- Delay-Based Back-Pressure Scheduling in Multihop Wireless NetworksIEEE/ACM Transactions on Networking, 2012
- OFDM downlink scheduling for delay-optimality: Many-channel many-source asymptotics with general arrival processes2011
- Node weighted scheduling2009
- Delay-Optimal Server Allocation in Multiqueue Multiserver Systems With Time-Varying ConnectivitiesIEEE Transactions on Information Theory, 2009
- Optimal Transmission Scheduling in Symmetric Communication Models With Intermittent ConnectivityIEEE Transactions on Information Theory, 2007
- SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATESProbability in the Engineering and Informational Sciences, 2004
- On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit ModelsThe Annals of Applied Probability, 1995
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Node weighted matching1984