Scheduling weighted packets with deadlines over a fading channel

Author

Fei Li ; Zhi Zhang

Author_Institution

Dept. of Comput. Sci., George Mason Univ., Fairfax, VA

fYear

2009

fDate

18-20 March 2009

Firstpage

707

Lastpage

712

Abstract

We consider scheduling weighted packets with time constraints over a fading channel. Packets arrive in an online manner. Each packet has a value and a hard deadline by which it should be sent. The fade state of the channel determines the throughput obtained per unit of time and the channel´s quality may change over time. In this paper, we design both offline and online algorithms to maximize weighted throughput, which is defined as the total value of the packets sent by their respective deadlines. We first present polynomial-time exact offline algorithms for this problem. Then, we present online algorithms and their competitive analysis, as well as the lower bounds of competitive ratio. Our work is the first one addressing weighted throughput for this important problem in the areas of information theory and communication.

Keywords

fading channels; polynomials; scheduling; fading channel; information theory; packet scheduling; polynomial-time exact offline algorithm; Algorithm design and analysis; Fading; Information theory; Polynomials; Processor scheduling; Resource management; Scheduling algorithm; Throughput; Time factors; Wireless sensor networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Sciences and Systems, 2009. CISS 2009. 43rd Annual Conference on

Conference_Location

Baltimore, MD

Print_ISBN

978-1-4244-2733-8

Electronic_ISBN

978-1-4244-2734-5

Type

conf

DOI

10.1109/CISS.2009.5054810

Filename

5054810