Title :
Base station scheduling of requests with fixed deadlines
Author :
Agarwal, Mohit ; Puri, Anuj
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA
Abstract :
We consider a packet switched wireless network in which a base station serves the mobiles. The packets for the mobiles arrive at the base station and have to be scheduled for transmission to the mobiles. The capacity of the channel from the base station to the mobiles is varying with time due to fading. We assume the mobiles can obtain different types of service based on the prices they are willing to pay. The objective of the base station is to schedule packets for transmission to mobiles to maximize the revenue earned. Our main result is that a simple greedy algorithm does at least 1/2 as good as the optimal offline algorithm that knows the complete future request pattern and channel conditions. We also show that no other online algorithm can do better.
Keywords :
channel capacity; fading channels; mobile radio; optimisation; packet radio networks; packet switching; scheduling; time-varying channels; base station scheduling; channel capacity; fading channel; fixed deadline requests; greedy algorithm; mobile radio; packet switched wireless network; revenue maximization; time varying channel; Base stations; Channel capacity; Computer networks; Fading; Greedy algorithms; Packet switching; Processor scheduling; Scheduling algorithm; Speech; Wireless networks;
Conference_Titel :
INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE
Print_ISBN :
0-7803-7476-2
DOI :
10.1109/INFCOM.2002.1019293
