Scheduling Weighted Packets with Deadlines over a Fading Channel

Authors

  • Fei Li George Mason University
  • Zhi Zhang George Mason University

Keywords:

online algorithm, competitive analysis, scheduling algorithms

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.

Downloads

Published

2012-01-03

How to Cite

Li, F., & Zhang, Z. (2012). Scheduling Weighted Packets with Deadlines over a Fading Channel. Algorithmic Operations Research, 6(2), Pages 68 – 78. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18294

Issue

Vol. 6 No. 2 (2011)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.