NDLI: Scheduling Algorithms for Multicarrier Wireless Data Systems

Content Provider	IEEE Xplore Digital Library
Author	Andrews, M. Zhang, L.
Copyright Year	1993
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.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	447
Ending Page	455
Page Count	9
File Size	304327
File Format	PDF
ISSN	10636692
Volume Number	19
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-04-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation algorithms Wireless communication Algorithm design and analysis Approximation methods Optimized production technology Greedy algorithms Schedules wireless systems Communication systems communications technology max weight multicarrier scheduling stability wireless communication wireless networks
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks

Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks

Local Greedy Approximation for Scheduling in Multihop Wireless Networks

Approximation Algorithms for Data Broadcast in Wireless Networks

Stability of the Max-Weight Protocol in Adversarial Wireless Networks

Neither Shortest Path Nor Dominating Set: Aggregation Scheduling by Greedy Growing Tree in Multihop Wireless Sensor Networks

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Minimum Data-Latency-Bound $k$-Sink Placement Problem in Wireless Sensor Networks

Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multihop Wireless Networks

Scheduling Algorithms for Multicarrier Wireless Data Systems

Similar Documents

Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks

Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks

Local Greedy Approximation for Scheduling in Multihop Wireless Networks

Approximation Algorithms for Data Broadcast in Wireless Networks

Stability of the Max-Weight Protocol in Adversarial Wireless Networks

Neither Shortest Path Nor Dominating Set: Aggregation Scheduling by Greedy Growing Tree in Multihop Wireless Sensor Networks

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Minimum Data-Latency-Bound $k$-Sink Placement Problem in Wireless Sensor Networks

Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multihop Wireless Networks

Scheduling Algorithms for Multicarrier Wireless Data Systems