Scheduling Weighted Packets with Deadlines over a Fading Channel

Fei Li, Zhi Zhang

Abstract


We consider scheduling weighted packets with time constraints over a fading channel. Packets arrive at the transmitter in an online manner. Each packet has a value and a deadline by which it should be sent. The fade state of the channel determines the throughput obtained per time unit and the channel’s quality may change over time. In this paper, we design both offline and online algorithms to maximize weighted throughput, defined as the total value of the packets sent by their respective deadlines. We first present polynomial-time exact offline algorithms for this problem. We then present online algorithms and their competitive analysis. We also show the lower bounds of competitive ratio.

Keywords


online algorithm; competitive analysis; scheduling algorithms

Full Text:

PDF


Algorithmic Operations Research. ISSN: 1718-3235