Scheduling Weighted Packets with Deadlines over a Fading Channel
Fei Li, Zhi Zhang · 2011
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 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 ratios. Our work is the first one addressing weighted throughput for this important problem in the areas of information theory and real-time communications. 1