### Scheduling over a time-varying user-dependent channel with applications to high-speed wireless dataScheduling over a time-varying user-dependent channel with applications to high-speed wireless data

Access Restriction
Subscribed

 Author Andrews, Matthew ♦ Zhang, Lisa Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Scheduling ♦ Stability ♦ Time-varying ♦ User-depedent ♦ Wireless channel Abstract In a wireless network, a basestation transmits data to mobiles at time-varying, mobile-dependent rates due to the ever changing nature of the communication channels. In this article, we consider a wireless system in which the channel conditions and data arrival processes are governed by an $\textit{adversary}.$ We first consider a single server and a set of users. At each time step $\textit{t},$ the server can only transmit data to one user. If user $\textit{i}$ is chosen, the transmission rate is $\textit{ri}(\textit{t}).$ We say that the system is $(\textit{w},$ $ϵ)-\textit{admissible}$ if in any window of $\textit{w}$ time steps the adversary can schedule the users so that the total data arriving to each user is at most 1™ϵ times the total service it receives.Our objective is to design online scheduling algorithms to ensure stability in an admissible system. We first show, somewhat surprisingly, that the admissibility condition alone does not guarantee the existence of a stable online algorithm, even in a subcritical system (i.e., ϵ > 0). For example, if the nonzero rates in an infinite rate set can be arbitrarily small, then a subcritical system can be unstable for any deterministic online algorithm.On a positive note, we present a tracking algorithm that attempts to mimic the behavior of the adversary. This algorithm ensures stability for all $(\textit{w},$ ϵ)-admissible systems that are not excluded by our instability results. As a special case, if the rate set is finite, then the tracking algorithm is stable even for a critical system (i.e., ϵ = 0). Moreover, the queue sizes are independent of ϵ. For subcritical systems, we also show that a simpler max weight algorithm is stable as long as the user rates are bounded away from zero.The offline version of our problem resembles the problem of scheduling unrelated machines and can be modeled by an integer program. We present a rounding algorithm for its linear relaxation and prove that the rounding technique cannot be substantially improved. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 52 Issue Number 5 Page Count 26 Starting Page 809 Ending Page 834

#### Open content in new tab

Source: ACM Digital Library