This chapter presents an introduction to cross-layer scheduling and resource allocation for wireless systems and an overview of some of the approaches and proposed algorithms. The use of scheduling is motivated by first considering the fading Gaussian channel. Then, the focus shifts to scheduling and resource allocation for cellular systems. Existing approaches for the uplink and the downlink are discussed, as well as research results relating to the fading Multiple Access and the fading Broadcast Channel. Schemes for OFDMA and CDMA systems as well as systems using multiple antenna transmission are also presented. It is hoped that this survey will affirm the improvement in performance that can be achieved by use of cross-layer approaches in the design of Next-Generation Networks.
Next-Generation Networks will be expected to deliver high data rates to a large number of different users in diverse environments. Moreover, they should be able to accommodate different user needs in terms of Quality of Service (QoS) and, in the same time, guarantee fairness. As the networks expand, energy efficiency will also be required, especially for wireless systems where battery life and radiation levels are major concerns. In order to meet successfully these demands, improved and new system designs are being developed. The designs encompass all system aspects, from smaller, faster and more energy-efficient circuits to sophisticated applications allowing seamless user connectivity and mobility.
Traditionally, system design has been greatly facilitated by following a layered approach where each layer of the network is designed and optimized separately. As an example, the link layer can be optimized by viewing the physical layer as a bit pipe with given capacity and bit-error rate. Historically, systems have greatly benefited from this level of abstraction. However, this view is suboptimal. In order for future networks to achieve the required performance gains and exploit the available resources to the fullest possible extent, more than one layer should be considered jointly when designing the system and when making scheduling and resource allocation decisions. In many cases the attained performance gains (and the associated financial revenue) may justify the increased complexity in the system design and implementation.
This survey focuses on cross-layer resource allocation and scheduling policies for cellular wireless systems. As will be described in the following, these policies consider not only the channel condition (state), but also some utility function that depends, in general, on QoS and fairness criteria. Moreover, because user traffic appears randomly, in order to guarantee stability and increase the achievable rates, the number of bits (or packets) waiting for transmission in the user or node queues often needs to be taken into account. Unlike earlier approaches, the physical layer does not decide on the rate and the modulation scheme independently. Rather, a cross-layer controller schedules users that are allowed to transmit during a given interval and allocates the usage of the resources of the channel at the physical layer based on the traffic needs of higher layers. In general, the controller also implements scheduling, allocation and routing policies at higher layers. However, the focus of this survey is on joint physical and link/network layer adaptation.
Several reviews on cross-layer resource allocation and scheduling have appeared recently, an evidence of the increased research interest in the area. In (Lin, Shroff & Srikant, 2006) a survey of policies for both single-hop and multiple-hop networks is given. For single-hop networks it is assumed that only one user can transmit (or receive) at any given time. While this is generally true in systems using time division and the model can also apply to frequency and code division with appropriate changes, from an information-theoretic point of view it may be optimal to transmit to more than one user simultaneously. In (Berry & Yeh, 2004) the authors focus on techniques for fading multiple access (MAC) and fading broadcast (BC) channels and examine policies that allocate a vector of powers and rates to more than one users, in general. Finally, (Chiang et al., 2007) reviews the current status of the “layering as optimization decomposition” effort to develop a mathematical framework for future networks where an appropriate vertical layer topology is first defined, and each layer is then optimized horizontally.
Key Terms in this Chapter
Network Capacity Region: The closure of the set of all arrival user rates that can be stably supported by a network when all possible scheduling, routing and resource allocation policies are considered. This includes knowledge of future states. The network capacity region cannot exceed the information-theoretic capacity region
Multiple Access Channel (MAC): A channel of N users xi i=1,…,N wishing to send information to a user x0 though a shared medium resulting to superposition of the signals that x0 receives from each user.
Broadcast Channel (BC): A channel comprising a user x0 wishing to send (in general different) information to users xi i=1,…,N through a shared medium resulting to each user receiving the signal emitted by x0 (in general through a different channel).
Throughput Optimality: The property that characterizes a scheduling scheme that guarantees system stability (stability of all individual queues of the network).
Queue State Information (QSI): Information on the queue corresponding to a user. The state may correspond to the queue length, the delay of the packet at the head of the queue, or to more general quantities such as individual packet priorities
Information-Theoretic Capacity Region: The closure of the set of all achievable rates in a channel as found from Information Theory (i.e., the supremium of the mutual information). Assumes regular traffic (or traffic averaged for a sufficiently long time so that burstiness is eliminated)
Channel State Information (CSI): Information on the state of the channel, namely channel gain and/or channel phase. Used by the controller for scheduling and resource allocation