A Framework for Opportunistic Schedulingin Wireless Networks?Xin LiuaEdwin K. P. ChongbNess B. Shroffa,∗aSchool of Electrical and Computer Engineering, Purdue University,West Lafayette, IN 47906bDept. of Electrical and Computer Engineering, Colorado State University,Fort Collins, CO 80523AbstractWe present a method, called opportunistic scheduling, for exploiting the time-varying nature of the radio environment to increase the overall performance ofthe system under certain QoS/fairness requirements of users. We first introducea general framework for opportunistic scheduling, and then identify three generalcategories of scheduling problems under this framework. We provide optimal solu-tions for each of these scheduling problems. All the proposed scheduling policiesare implementable on-line; we provide parameter estimation algorithms and imple-mentation procedures for them. We also show how previous work by us and othersdirectly fits into or is related to this framework. We demonstrate via simulationthat opportunistic scheduling schemes result in significant performance improve-ment compared with non-opportunistic alternatives.Key words: scheduling, resource allocation, wireless, time-varying channel,time-slotted system?This research is supported in part by the National Science Foundation throughgrants NCR-9624525, ANI-9805441, 0099137-ANI, 0098089-ECS, ANI-0207892, andANI-0207728, and DARPA throught grant F30602-00-2-0542.∗Corresponding author. Tel: 765-494-3471, Fax: 765-494-3358.Email addresses: [email protected] (Xin Liu),[email protected] (Edwin K. P. Chong), [email protected](Ness B. Shroff).Preprint submitted to Elsevier Science 14 January 20031 Introduction and MotivationWireless networks have unique characteristics, and thus demand specially tai-lored scheduling schemes. The wireless resource is scarce, and mobile usersperceive time-varying channel conditions. Hence, good scheduling schemes inwireless networks should opportunistically seek to exploit channel conditions toachieve higher network performance. Here, the term opportunistic denotes theability to schedule users based on favorable channel conditions. However, thepotential to transmit at higher data rates opportunistically (i.e., when channelconditions permit) also introduces an important tradeoff between wireless re-source efficiency and level of satisfaction among different users. For example,allowing only users close to the base station to transmit at high transmissionpower may result in very high throughput, but sacrifices the transmissions ofother users. Such a scheme cannot satisfy the increasing demand for quality ofservice (QoS) provisioning in the emerging high-rate data wireless networks.To address this problem, we present here a framework for scheduling usersin an opportunistic way. The objective is to improve wireless resource effi-ciency by exploiting time-varying channel conditions while at the same timecontrolling the level of QoS among users. Under this framework, we studyopportunistic scheduling policies with different QoS constraints. The first twoQoS requirements under investigation are in fact fairness requirements. Thethird QoS metric considered in this paper is the minimum “performance” (e.g.,data rate) a user receives.Wireless scheduling schemes have attracted a lot of recent attention. The au-thors of [13–16] have studied wireless fair scheduling policies. They extendthe scheduling policies of wireline networks to wireless networks. These wire-less scheduling schemes provide various degrees of performance guarantees,including short-term and long-term fairness, as well as short-term and long-term throughput bounds. A survey of these algorithms can be found in [7].However, these efforts model a channel as being either “good” or “bad,” whichmay be too simple to effectively characterize realistic wireless channels, espe-cially for data services.In [4,8], the authors present a scheduling scheme for the Qualcomm/HDR sys-tem. Their scheduling scheme exploits time-varying channel conditions whilemaintaining “proportional fairness,” as defined in [8,9].In [2,3,17,18], the authors study scheduling algorithms for the transmissionof data to multiple users. Both delay and channel conditions are taken intoaccount. Throughput optimality is defined in [3] as follows: a scheduling al-gorithm is throughput optimal if it is able to keep all queues stable if this isat all feasible to do with any scheduling algorithm. Furthermore, the authorsof [6] investigate a scheduling algorithm to maximize the minimum weighted2throughput of users. We discuss these schemes in more detail later.Opportunistic scheduling exploits the channel fluctuations of users. Thus anatural question to ask is what we should do in environments with little scat-tering and/or slow fading. In [20], the authors present a scheme that uses mul-tiple transmission antennas to “induce” channel fluctuations, and thus exploitmulti-user diversity. Further, such a scheme can also be used opportunisticallyto null intercell interference.In [1], scheduling problems for real-time traffic are studied. The authors showthat the greedy algorithm is 1/2 competitive against the offline optimal algo-rithm. Further, they show that no deterministic online algorithm can achievea competitive ratio higher than 1/2.In this paper, we present a framework for opportunistically scheduling usertransmissions to exploit the time-varying channel conditions in wireless com-munication systems. The objective is to maximize the wireless system perfor-mance while satisfying various QoS requirements. Our framework enables usto investigate different categories of scheduling problems involving two fair-ness requirements (temporal fairness and utilitarian fairness) and a minimum-performance requirement. We provide optimal scheduling solutions, and studythe asymptotic behavior of our opportunistic scheduling schemes. We also pro-vide a stochastic-approximation-based algorithm that can be used efficientlyto estimate the key parameters of the scheduling schemes on-line. We alsoshow how previous work by us and others directly fits into or is related to thisframework (e.g., [2,6,8,12]).The paper is organized as follows. In Section 2, we introduce the system model,and present our framework for opportunistic scheduling. We study three typesof scheduling problems using this framework. First, in Section 3, we intro-duce a scheduling problem with