17-10-2016, 04:35 PM
1459501277-tutcrosslayer.pdf (Size: 215.78 KB / Downloads: 4)
Abstract—This tutorial paper overviews recent developments
in optimization based approaches for resource allocation problems
in wireless systems. We begin by overviewing important
results in the area of opportunistic (channel-aware) scheduling
for cellular (single-hop) networks, where easily implementable
myopic policies are shown to optimize system performance. We
then describe key lessons learned and the main obstacles in
extending the work to general resource allocation problems for
multi-hop wireless networks. Towards this end, we show that a
clean-slate optimization based approach to the multi-hop resource
allocation problem naturally results in a “loosely coupled” crosslayer
solution. That is, the algorithms obtained map to different
layers (transport, network, and MAC/PHY) of the protocol
stack are coupled through a limited amount of information
being passed back and forth. It turns out that the optimal
scheduling component at the MAC layer is very complex and
thus needs simpler (potentially imperfect) distributed solutions.
We demonstrate how to use imperfect scheduling in the crosslayer
framework and describe recently developed distributed
algorithms along these lines. We conclude by describing a set
of open research problems.
I. INTRODUCTION
Optimization based approaches have been extensively used
over the past several years to study resource allocation problems
in communication networks. For example, Internet congestion
control can be viewed as distributed primal or dual
solutions to a convex optimization problem that maximizes the
aggregate system performance (or utility). Such approaches
have resulted in a deep understanding of the ubiquitous
Transmission Control Protocol (TCP) and resulted in improved
solutions for congestion control [1]–[6].
The key question is whether such approaches can be applied
to emerging multi-hop wireless networks to enable a cleanslate
design of the protocol stack1
. Indeed there are unique
challenges in the wireless context that do not allow a direct
application of such techniques from the Internet setting. In
particular, the wireless medium is an inherently multi-access
medium where the transmissions of users interfere with each
other and where the channel capacity is time-varying (due
to user mobility, multipath, and shadowing). This causes interdependencies across users and network layers that are
simply not present in their wireline counterparts. In spite of
these difficulties, there have been significant recent advances
that demonstrate that wireless resources across multiple layers
(such as time, frequency, power, link data rates and end-user
data rates), can be incorporated into a unified optimization
framework. Interestingly, as will be described in detail in
Section III, the solution of such an optimization framework
will itself exhibit a layered structure with only a limited degree
of cross-layer coupling.
We will illustrate the use of such an optimization approach
for two classes of cross-layer problems, namely, the opportunistic
scheduling problem in cellular (or access-point based
single-hop networks), and the joint congestion-control and
scheduling problem in multi-hop wireless networks. We will
see that convex programming is an important tool for this
optimization approach; in particular, Lagrange duality is a
key tool in decomposing the otherwise complex optimization
problem into easily-solvable components. However, we will
also see that convex programming is often not enough. In
fact, unlike their wireline counterparts, the essential features
of many wireless cross-layer control problems are not convex.
For example, due to interference, wireless networks typically
require sophisticated “scheduling” mechanisms to carefully
select only a subset of links to be activated at each time.
In wireless networks, the capacity of each link depends on
the signal and interference levels, and thus depends on the
power and transmission schedule at other links. This relationship
between the link capacity, power assignment, and the
transmission schedule is typically non-convex. Therefore, the
scheduling component needs to solve a difficult non-convex
problem, and usually becomes the bottleneck of the entire
solution.
These inherent non-convex features require that advanced
techniques in addition to convex programming be used to
satisfactorily solve the cross-layer control problem in wireless
networks. In this tutorial, we will see a few examples where
tools from convex programming, combinatorial optimization,
stochastic stability, graph theory, large deviations, and heavytraffic
limits are used to obtain realistic and efficient solutions
to the cross-layer control problem.
We acknowledge that cross-layer optimization has become
a very active research area in the last few years. A comprehensive
survey would be difficult due to the space constraints
in this special issue. Hence, this tutorial is by no means an
exhaustive survey of all subjects in cross-layer optimization.
Rather, our focus is to provide the readers with a sketch of
the main issues, challenges, and techniques in this area, and
also identify the main open problems to the community. For
another survey in this area see [7].
The rest of the tutorial is organized as follows. Section II
will begin with an exposition of the important problem of
scheduling in cellular networks. Here, the emphasis is on
incorporating physical layer channel information into the
scheduling decision. In Section III, we investigate the joint
congestion-control and scheduling problem in multihop wireless
networks. The general formulation provided in Section III
elegantly decomposes the cross-layer problem into a congestion
control component and a scheduling component. However,
due to non-convexity, the perfect scheduling component is usually
very complex and difficult to implement in real networks.
One approach to address this complexity is to use simpler
(and potentially distributed) imperfect scheduling components
in the cross-layer solution. However, the impact of these
imperfect scheduling policies on the overall solution must
be carefully studied. This is the subject of Section IV. In
Section V, we will describe recent developments in obtaining
imperfect distributed scheduling policies with provably achievable
throughput bounds. We then conclude with a set of open
problems.
II. OPPORTUNISTIC SCHEDULING FOR CELLULAR
WIRELESS NETWORKS
In this section, we focus on the opportunistic scheduling
problem in cellular networks (the results also apply to accesspoint
based single-hop wireless networks). Over the last few
years, this multi-user scheduling problem has received significant
attention in both academia and industry. These scheduling
schemes have been motivated by the unique features in
wireless networks: scarce resources, mobile users, interference
from other users in the network, and time-varying channel
conditions (due to fading and mobility). Hence, good scheduling
schemes in wireless networks should opportunistically
seek to exploit channel conditions to achieve higher network
performance. For example, consider a cellular network that
consists of a base station and N users. Further, assume a timeslotted
system and downlink communications, i.e., from the
base-station to the users (receivers). Then the base-station can
determine which user(s) to transmit to, based on the channel
conditions. The idea is that transmissions to receivers with
favorable channel conditions (e.g., with higher SINR) allows
the base-station to transmit at a higher rate (using adaptive
modulation and coding schemes) for a given target bit-errorrate.
Thus, the base-station can opportunistically exploit the
channel conditions to achieve higher network performance. It
should be noted here that the idea of exploiting multi-user
diversity is in contrast to traditional methods (e.g., spread
spectrum, repetitive coding, power averaging, etc.), where the
goal is to smooth out channel variability rather than to exploit
it. Opportunistic scheduling achieves multi-user diversity gains
because when users experiencing good channels are selected, it enables the system to potentially operate close to its peak
rather than average performance.
In [8], under an AWGN (additive white gaussian noise)
model, it has been shown that the sum capacity2 of a wireless
system is maximized when only one user is selected to transmit
at any given time. This result can be shown for either uplink
or downlink assuming complete channel information at both
the receiver and the transmitter. The user with the best channel
condition is chosen for transmission. However, in a networking
context, the difficulty with such a solution is that while it
maximizes the overall throughput, it could result in significant
unfairness among the users. For example, under such a scheme
users that are close to the base-station may always be favored
over those that are further away, resulting in potentially poor
performance for certain users in the system. Such an approach
is especially troubling for high-data-rate wireless users that
may have stringent quality of service (QoS) requirements.
In order to address the above concerns, there have been several
approaches to ensure fairness/QoS in a wireless context.
For simplicity of presentation, we will focus on the downlink,
i.e., base-station to user communication. We will overview
opportunistic scheduling solutions that have been derived for
both infinite- and finite-backlogged cases.
A. Infinite-Backlog Case
The infinite-backlog case is often studied in communication
systems to evaluate protocols and study their maximum
achievable performance. It is also simple and results in a
tractable solution that provides important insights. The objective
in our context is to find a feasible scheduling policy
Q that maximizes the overall system performance for given
fairness/QoS requirements. A policy Q maps a vector U~ =
[U1(x1), ...,UN (xN )] to Q(U~ ), which is the index of the user
selected for transmission. Here, xi
is the data rate transmitted
to user i if it is selected for transmission, Ui
is the utility
function of user i, and Ui(xi) measures the value or benefit to
user i of the receiving data rate xi
. Note that xi
is a function of
the channel condition and the coding and modulation scheme
used. There have been many scheduling schemes that address
this problem [9]–[13]. Interestingly, most of these approaches
result in an optimal solution that can be expressed in the form
of simple myopic index policies given by:
Q
∗ = argmax
i=1,...,N
(αiUi(xi) + βi), (1)
where αi and βi are constants and can be viewed as Lagrange
multipliers. For example, consider the following problem
studied in [12], [13]:
max
Q∈Θ
X
N
i=1
E (Ui(xi))
subject to P{Q(U~ ) = i} ≥ ri
, i = 1, 2, · · · , N, (2)
where Θ is the set of all stationary scheduling policies, and
ri
is the minimum fraction of time-slots assigned to user i