Scheduling Algorithms for Multicarrier Wireless Data Systems
- 16 September 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 19 (2), 447-455
- https://doi.org/10.1109/tnet.2010.2064175
Abstract
We consider the problem of scheduling multicarrier wireless data in systems such as IEEE 802.16 (WiMAX). Each scheduling decision involves assigning carriers to users for each time slot, subject to the constraint that each carrier is assigned to at most one user, but multiple carriers can potentially be assigned to the same user. One important aspect of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision is made. This “global” information may give a potential for enhancing performance via an optimized allocation of carriers to users. We analyze this problem in a situation where finite queues are fed by a data arrival process. The well-known MaxWeight algorithm for the single-carrier setting maximizes the product of queue size and service rate. We focus on how to adapt MaxWeight to the multicarrier setting. If the same objective is pursued, more service than needed may be assigned to drain a queue, thereby creating wastage. While a simple variant in the objective forbids this wastage, it turns an easy-to-compute old objective into an intractable new objective. We state the hardness of the new optimization problems and propose several extremely simple algorithms with provable performance bounds. We conclude with supporting simulation examples.Keywords
This publication has 23 references indexed in Scilit:
- Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual AlgorithmQueueing Systems, 2005
- Instability of the Proportional Fair Scheduling Algorithm for HDRIEEE Transactions on Wireless Communications, 2004
- A framework for opportunistic scheduling in wireless networksComputer Networks, 2003
- Opportunistic transmission scheduling with resource-sharing constraints in wireless networksIEEE Journal on Selected Areas in Communications, 2001
- Providing quality of service over a shared wireless linkIEEE Communications Magazine, 2001
- CDMA/HDR: a bandwidth efficient high speed wireless data service for nomadic usersIEEE Communications Magazine, 2000
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- An analysis of approximations for maximizing submodular set functions—IIPublished by Springer Science and Business Media LLC ,1978