Scheduling over a time-varying user-dependent channel with applications to high speed wireless data
Scheduling over a time-varying user-dependent channel with applications to high speed wireless data
复制标题
通过时变的用户相关信道进行调度，并应用于高速无线数据
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Lisa Zhang
中科院分区：
文献类型：
--
作者：
M. Andrews;Lisa Zhang
在无线网络中，由于通信信道的性质不断变化，基站以时变的、依赖于移动设备的速率向移动设备传输数据。本文考虑一个信道条件和数据到达过程由对手控制的无线系统。我们首先考虑一个服务器和一组用户。在每个时间步骤1中，服务器只能向一个用户传输数据。如果选择用户i，则传输速率为r/sub i/(t)。我们说系统是（/spl omega/, /spl epsiv/）可接受的，如果在/spl omega/时间步长的任何窗口中，攻击者可以调度用户，使到达每个用户的总数据最多是它接收的总服务的1 - /spl epsiv/倍。我们的目标是设计在线调度算法以确保可接受系统的稳定性。令人惊讶的是，我们首先证明，即使在次临界系统（即/spl epsiv/ >）中，单独的容许条件也不能保证稳定在线算法的存在。例如，如果无限速率集中的非零速率可以任意小，则对于任何确定性在线算法，次临界系统都可能是不稳定的。积极的一面是，我们提出了一种跟踪算法，试图模仿对手的行为。该算法确保了所有（/spl ω /, /spl epsiv/）允许系统的稳定性，这些系统不被我们的不稳定性结果排除在外。作为一种特殊情况，如果速率集是有限的，那么即使对于临界系统（即/spl epsiv/ = 0），跟踪算法也是稳定的。此外，队列大小与e无关。对于亚临界系统，我们还表明，只要用户速率有界远离零，一个更简单的最大权重算法是稳定的。我们问题的离线版本类似于调度不相关机器的问题，可以用整数程序建模。针对其线性松弛性提出了一种舍入算法，并证明了舍入技术不能得到实质性的改进。最后，我们讨论了将我们的模型扩展到网络环境的问题。
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 paper we consider a wireless system in which the channel conditions and data arrival processes are governed by an adversary. We first consider a single server and a set of users. At each time step t the server can only transmit data to one user. If user i is chosen the transmission rate is r/sub i/(t). We say that the system is (/spl omega/, /spl epsiv/)-admissible if in any window of /spl omega/ time steps the adversary can schedule the users so that the total data arriving to each user is at most 1 - /spl epsiv/ times the total service it receives. Our objective is to design on-line 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. /spl epsiv/ > 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 (/spl omega/, /spl epsiv/)-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. /spl epsiv/ = 0). Moreover, the queue sizes are independent of e. 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. We conclude by discussing the extension of our model to the network setting.