The IMA Volumes in Mathematics and its Applications Volume 143
Series Editors
Douglas N. Arnold Arnd Scheel
Institute for Mathematics and its Applications (IMA) The Institute for Mathematics and its Applications was established by a grant from the National Science Foundation to the University of Minnesota in 1982. The primary mission of the IMA is to foster research of a truly interdisciplinary nature, establishing links between mathematics of the highest caliber and important scientific and technological problems from other disciplines and industries. To this end, the IMA organizes a wide variety of programs, ranging from short intense workshops in areas of exceptional interest and opportunity to extensive thematic programs lasting a year. IMA Volumes are used to communicate results of these programs that we believe are of particular value to the broader scientific community. The full list of IMA books can be found at the Web site of the Institute for Mathematics and its Applications: http://www.ima.umn.edu/springer/volumes.html Douglas N. Arnold, Director of the IMA
**** ****** IMA ANNUAL PROGRAMS
1982-1983 1983-1984 1984-1985 1985-1986 1986-1987 1987-1988 1988-1989 1989-1990 1990-1991 1991-1992
1992-1993 1993-1994 1994-1995 1995-1996 1996-1997 1997-1998 1998-1999
Statistical and Continuum Approaches to Phase Transition Mathematical Models for the Economics of Decentralized Resource Allocation Continuum Physics and Partial Differential Equations Stochastic Differential Equations and Their Applications Scientific Computation Applied Combinatorics Nonlinear Waves Dynamical Systems and Their Applications Phase Transitions and Free Boundaries Applied Linear Algebra Control Theory and its Applications Emerging Applications of Probability Waves and Scattering Mathematical Methods in Material Science Mathematics of High Performance Computing Emerging Applications of Dynamical Systems Mathematics in Biology
Continued at the back
Prathima Agrawal Daniel Matthew Andrews Philip 1. Fleming George Yin Lisa Zhang Editors
Wireless Communications
~ Springer
Prathima Agrawal Department of Electrical and Computer Engineering Auburn University Auburn, AL 36849-5201 USA www.eng.auburn.edu/-pagrawal
Daniel Matthew Andrews Bell Laboratories Lucent Technologies Murray Hill, NJ 07974-0636 USA em.bell-labs. com!cm/ms/who/andrews/
Philip 1. Fleming Network Advanced Technology Motorola, Inc. Arlington Heights, IL 60004 USA
George Yin Department of Mathematics Wayne State University Detroit, MI 48202 USA wwwmath.wayne.edu/-gyin/
Lisa Zhang Computing Sciences Research Center Bell Laboratories Lucent Technologies Murray Hill, NJ 07974 USA em.bell-labs.com/who/ylz/
Series Editors Douglas N. Arnold Arnd Scheel Institute for Mathematics and its Applications University of Minnesota Minneapolis, MN 55455 USA
Mathematics Subject Classification (2000): 90B18, 94-06, 94A05, 60G35 Library of Congress Control Number: 2006933293 ISBN-IO: 0-387-37269-5 ISBN-13: 978-0387-37269-3 © 2007 Springer Science+Business Media, LLC All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
Camera-ready copy provided by the IMA. 9 8 7 6 543 2 1 springer.com
FOREWORD
This IMA Volume in Mathematics and its Applications
Wireless Communications contains papers based on invited lectures at the very successful IMA Summer Program on Wireless Communications, held on June 22 - July 1, 2005. We would like to thank Prathima Agrawal (Auburn University), Daniel Matthew Andrews (Lucent Technologies), Philip J. Fleming (Motorola, Inc.), George Yin (Wayne State University), and Lisa Zhang (Lucent Technologies) for their superb role as workshop organizers and editors of the proceedings. We take this opportunity to thank the National Science Foundation for its support of the IMA.
Series Editors Douglas N. Arnold, Director of the IMA Arnd Scheel, Deputy Director of the IMA
v
PREFACE
This volume presents papers, based on invited talks given at the 2005 IMA Summer Workshop on Wireless Communications, held at the Institute for Mathematics and Its Applications, University of Minnesota, June 22 July 1, 2005. The conference provided a well blended program to facilitate the communications between academia and the industry, and to bridge the mathematical sciences, engineering, information theory, and communication communities. The emphases were on design and analysis of computationally efficient algorithms to better understand the behavior and to control the wireless telecommunication networks. As an achieve, this volume presents some of the highlights of the conference, and collects papers covering a broad spectrum of topics. All papers have been reviewed. Without the help, assistance, support, and encouragement of many people, this workshop could not come into being. We thank the invited speakers, the poster presenters, and all attendees for making the conference a successful event. Our thanks go to Douglas N. Arnold and Fadil Santosa for helping us shaping the conference and proving us with valuable comments and suggestions. We are grateful to Debra Lewis and the IMA staff for their tireless help in the preparation stage and during the conference. The assistance from Arnd Scheel in preparing the proceedings is gratefully acknowledged. We also thank Patricia V. Brick and Dzung N. Nguyen for their help and assistance for putting the final product together in a beautiful piece. Prathima Agrawal
Department of Electrical and Computer Engineering Auburn University
Daniel Matthew Andrews Bell Laboratories Lucent Technologies Philip J. Fleming Network Advanced Technology Motorola, Inc. George Yin Department of Mathematics Wayne State University
Lisa Zhang Bell Laboratories Lucent Technologies VB
CONTENTS Foreword
v
Preface
vii
A survey of scheduling theory in wireless data networks Matthew Andrews
1
Wireless channel parameters maximizing TCP throughput. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19 Francois Baccelli, Rene L. Cruz, and Antonio Nucci Heavy traffic methods in wireless systems: towards modeling heavy tails and long range dependence. . . . . . . . . . . . . . . . . . . . .. 53 Robert T. Buche, Arka Ghosh, Vladas Pipiras, and Jim X. Zhang Structural results on optimal transmission scheduling over dynamical fading channels: a constrained Markov decision process approach Dejan V. Djonin and Vikram K rishnamurthy
75
Entropy, inference, and channel coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 99 J. Huang, C. Pandit, S.P. Meyn, M.Medard, and V. Veeravalli Optimization of wireless multiple antenna communication system throughput via quantized rate control M.A. Khojastepour, X. Wang, and M. Madihian
125
Communication strategies and coding for relaying. . . . . . . . . . . . . . . . . .. 163 Gerhard Kramer Scheduling and control of multi-node mobile communications systems with randomly-vary.ing channels by stability methods Harold J. Kushner
ix
',' . . . . . . .. 177
CONTENTS
x
A game theoretic approach to interference management in cognitive networks
199
Nie Nie, Cristina Comaniciu, and Prathima Agrawal Enabling interoperability of heterogeneous ad hoc networks
221
Santosh Pandey and Prathima Agrawal Overlay networks for wireless ad hoc networks
237
Christian Scheideler Dimensionality reduction, compression and quantization for distributed estimation with wireless sensor networks
259
Joannis D. Schizas, Alejandro Ribeiro, and Georgios B. Giannakis Fair allocation of a wireless fading channel: an auction approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 297 Jun Sun and Eytan Modiano Modelling and stability of FAST TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 331
Jiantao Wang, David X. Wei, Joon-Young Choi, and Steven H. Low
List of workshop participants
357
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS MATTHEW ANDREWS*
Abstract. We survey some results for scheduling data in wireless data systems such as lxEV-DO. An important feature of such systems is that the channel rates between the basestation and the mobile users are both user-dependent and time-varying. The wireless data scheduling problem has recently received a great deal of attention in the literature. However, comparisons of results are sometimes difficult due to the fact that many different models have been studied. In this survey we describe some of the models that have been proposed and analyze the performance of different scheduling algorithms within these models.
1. Introduction. The advent of third-generation wireless systems such as CDMA2000 lxEV-DO [15, 18) means that mobile Internet users can now obtain high data rates in cellular systems. However, in order to effectively utilize the wireless capacity, we require efficient methods for deciding how the wireless resources should be assigned. In particular, we require scheduling algorithms that determine which user should be served in each time step. In this paper we survey some of the basic results about scheduling in wireless data systems. The most important feature of such systems is that due to channel fading and user mobility, the rates at which users can receive data are both user-dependent and time-varying. In particular, when a user is close to the transmitter it can typically receive data at a higher rate than when it is farther away from the the transmitter. In recent years, there has been a great deal of work on developing effective scheduling algorithms for wireless data systems. Unfortunately, many of the results in the literature consider different models which makes comparing results difficult. In this survey, we define a number of models that have been studied and describe what scheduling results are known in each of them. We begin by describing in detail the basic scheduling problem together with the different models that have been considered. The model. We consider a set of n mobile data users in a wireless cell served by a single basestation. (See Figure 1). We focus on the downlink (basestation to mobile) direction since for many applications such as web browsing the majority of data flows in that direction. The basestation maintains a separate queue of data at the basestation for each mobile user. Time is slotted and in each time slot the basestation can transmit data to exactly one user. In order to make this decision the basestation knows at all time steps a vector (ro(t), ... ,rn-l(t)), where r.It] is the amount of data that can be transmitted to user i at time step t. In the EV-DO system this value is known as the Data Rate Control (DRC) value. As already * Bell Laboratories, Murray Hill, N J 07974 (andrewsCOresearch. bell-labs. com).
2
MATTHEW ANDREWS
goodchannel
FIG.
1. A wireless system.
mentioned, channel fading and user mobility mean that DRC values are user-dependent and time-varying. The scheduler at the basestation knows the value of r i (t) because at each time step mobile user i measures the strength of a pilot signal transmitted by the basestation. From the strength of that signal user i can calculate the quality of the channel between the basestation and itself and determine the rate at which the basestation should transmit in order to achieve a low error. The user then sends this rate to the basestation in a control message. The time-varying nature of the channel rates makes the scheduling problem much more complex than in the wireline setting since the "correct" decision about which user to serve will change from time slot to time slot. In general we want to "ride the peaks" of the channel processes and try to pick a user whose current channel condition is better than average. On the other hand, we want to schedule fairly and not starve any users whose channel conditions are poor. Formally, the scheduling problem is as follows. In each time step the scheduler receives the channel rate vector (ro(t), ... ,rn-l(t)). It then makes a decision about which user to serve. If user i is chosen then ri(t) bits are served from the queue of user i (or all the data is served if the queue size is less than r i (t)). As already mentioned, one of the aims of this survey is to highlight the differences between some of the models that are considered in the literature. The models differ in the assumptions that are made about the arrival model and in the assumptions that are made about the channel process between the basestation and the mobile users. With regards to the traffic model, the two options usually considered are an infinitely-backlogged model and a model where the queues for each user are fed by an external arrival process. More formally, these models are defined as follows: • In the infinitely backlogged model each user always has data to transmit. Since there is no arrival process as such, metrics such as queue size and delay do not make much sense. We wish to
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 3
optimize some function of the throughputs achieved by the users. For example, if R; is some measure of the long-term throughput achieved by user i, a popular goal is to optimize the Proportional Fair metric L:i log n; • In the model with an external arrival process, at each time step the scheduler receives a vector (ao (t), ... , an-l (t)), where a, (t) represents the amount of data that arrives for user i in time slot t. This vector is in addition to the channel rate vector described above. In this case, metrics such as queue size and delay become relevant in addition to throughput. One fundamental goal of any scheduling algorithm is stability. In particular, an essential attribute that we would like a scheduler to possess is stability. We say that a scheduler is stable if it keeps the queue sizes bounded whenever this is feasible. With regards to the channel process the two models that are studied are a model in which the channel rates are generated according to a stationary stochastic process and a worst-case model in which the channel rates are generated by an adversary: • For the model in which the channel rates are generated according to a stationary stochastic process we assume that there is a finite set of (aggregate) channel states denoted by M == {l, ... , M}. Associated with each state m E M is a fixed vector of data rates (p/l' ... , I-L N). The channel process is defined by an ergodic Markov Chain m(t) with state space M. In particular, whenever m(t) == m the channel rate vector is given by ri(t) == I-Lr;. In this model we typically aim to derive the "optimal" scheduling rule with respect to some metric. It is often convenient to compare a candidate scheduling algorithm against an ideal Static Service Split (SSS) rule in which we have a set of cPmi such that L:i cPmi == 1. Whenever the state of the Markov Chain is m the SSS rule serves user i with probability cPmi. We note however that it is typically not feasible to implement the optimal SSS rule since the scheduler is not aware of the structure of the underlying Markov Chain. • For the adversarial .modcl we do not assume any type of stationarity. Instead at each time step t the channel rate vector (ro(t), ... ,rn-l (t)) can be an arbitrary vector that is defined by an adversary. We can think of the adversary as trying to create as much trouble for the scheduling algorithm as possible. As in the stationary model we typically wish to compare a candidate online scheduling algorithm against an "ideal" algorithm. The SSS rules do not make much sense here because the optimal scheduling decision for a particular rate vector may change over time. Instead, we assume that at each time step, the adversary has its own schedule that will produce good performance in conjunction with
4
MATTHEW ANDREWS
the channel rate vectors that it generates. Our aim is to match the adversary's schedule as closely as possible. By combining the two possible traffic arrival models with the two channel models we obtain four possible models, each of which has been studied in the literature. In the next four sections of the paper we consider each model separately and present some of the results that are known. We then briefly discuss the case of wireless mesh networks in which there are multiple transmitters and data may need to pass through more than one node.
2. Infinitely backlogged queues - Stationary channel process. In the first model that we consider we assume that all users always have data to send and that the channel conditions are generated by a stationary stochastic process. This is the model that generated one of the most widely used wireless scheduling algorithms, namely the Proportional Fair scheduling algorithm of Tse [28]. In each time step Proportional Fair serves user,
.
J == arg
ri(t)
mfx R i ( t) ,
where R, (t) is the value at time t of an exponentially filtered average service rate that is updated according to,
R. (t t
+
1) == { (1 - T)R i ( t)
(1 - T) R, (t)
+ rr i ( t)
if i == j if i i= j
for some time constant T. (In practice T is typically on the order of 1000 slots.) Note that the Proportional Fair algorithm gives priority to users with a high instantaneous channel value (r i (t)) and a low current average service rate tR, (t) ). The Proportional Fair algorithm has an extremely elegant theoretical property. It maximizes, over all feasible scheduling rules, the function Ei log R i , whereE, is the long-term service rate of user i. This objective is sometimes known as the Proportional Fair metric for the following reason. If (Ro,'" R~_l) is the vector of feasible rates that maximizes Ei log then for any other vector of rates (R o, ... , R n - 1 ) , we have that E (R i R;)/R; < O. In other words, if we move from R; to another feasible rate allocation and we scale the improvement for user i in proportion to the current allocation, the aggregate improvement must be negative. Another way to look at the metric is that multiplying one user's rate by a factor c has the same effect on the objective as multiplying another user's rate by the same factor c. Lastly, observe that by using Ei log R, as a metric we do not starve any user completely since log a == -00. At a high-level the reason why Proportional Fair is optimal with respect to the metric Ei log R, is as follows. If we let S (t) == Ei log R i (t) then (\7S)(t) == (Ro\t)"'" Rn~dt))' We then have,
u;
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 5
L log Ri(t + 1) - L log Ri(t) i
i
~
(V' S)(t) . (Ro(t + 1) - Ro(t ), ... , Rn -1 (t + 1) - Rn -1 ( t))
=
(Ro\t)"'"
= (Ro\t)"oo,
Rn~dt)) . (Ro(t+l)-R o(t), ... , Rn~l (t+l) -
Rn-1(t))
Rn~l(t)) . (-rRo(t),oo.,rTj(t)-rRj(t),oo.,-rRn_1(t))
Trj (t)
== Rj(t) -
Tn,
whenever user j is served. Since T and n are fixed this implies that in order to maximize the change in 2:i log R, (t) we should serve the user that maximizes ri(t)/Ri(t). This is exactly what Proportional Fair does. A formal proof of the optimality of Proportional Fair has been obtained in multiple contexts (e.g. [20, 1, 25]. In this survey we state the asymptotic result of Stolyar [25]. Let be the steady-state rate allocation of the optimal SSS rule with respect to the metric 2:i log R i . Consider a sequence of processes indexed by TO, T1, T2, ... , where Tk 1 O. For each Tk we have a fixed initial state R;k (0) for the average service rates and a fixed initial state m Tk (0) for the Markov Chain that governs the channel process. Suppose that the channel rates evolve according to the Markov Chain and the average service rates evolve according to the Proportional Fair algorithm. Let DTk (t) be the amount of service received by user i in the time slot t under the process indexed by Tk. Let R;k (£1,£2) be the average service rate received between time slot £1 and time slots £2, namely,
R:
£2
R?(£1,£2) = £2 - ~ 1+ 1 'L....J " D?(t). t=£l
Then, the main theorem of Stolyar [25] implies, THEOREM 2.1. Let A be a bounded subset of R+.. Then, for any E > 0, there exist parameters T 1 and T 2 (both depending on A and
lim
sup
Tkl o R;k (O)EA,£1>T1/Tk,£2>T2/Tk
E)
such that,
V(E[R?(£1'£2)] - RiY:::;
E,
where E[·] denotes expectation. In other words, as T 1 0 the long-term average service rate approaches the average service rate of the optimal SSS rule. Another interesting property of Proportional Fair is that if the channel processes take the form r i (t) == a, . b, (t), where o.; is a constant and the b, (t) processes are i.i.d. then in the long run the fraction of slots allocated to each user is 1/n. That is, if the channel rate fluctuations around the mean are the same for all users then the scheduler serves each user for an equal amount of time. This property was derived by Holtzman in [17].
6
MATTHEW ANDREWS
Proportional Fair with Minimum/Maximum Rate Constraints. Note that although the Proportional Fair algorithm maximizes the metric 2::i log R i , it does not provide any absolute guarantees on the service rate provided to any individual user. For some applications, e.g. streaming video, we may need to provide a minimum bandwidth to the users in order for the application to be useful. In some cases we may also want to limit the amount of service that a user receives, e.g. if we want to encourage a user to upgrade to a more expensive service. Suppose therefore in that for each user i we have a minimum rate and a maximum rate ax in Rr and we want the average service rate R i to satisfy, It; Rr ax. The optimization problem then becomes,
Rr
Rr
< <
maxLlogRi subject to
(2.1)
An algorithm for this problem called Proportional Fair with Minimum/Maximum Rate Constraints (PFMR) was presented in [9]. The algorithm operates by maintaining a token counter Ti(t) for each user i. The role of this token counter is to enforce the rate constraints. It is updated according to if user i is served otherwise where R~oken == Ri in if Ti(t) ~ 0 and R~oken == Ri ax if Ti(t) < step t the PFMR algorithm serves the user, j = argmax ri(t) i
R, (t)
o.
At time
eaiTi(t)
,
where a, is a parameter that determines the timescale over which the rate constraints are satisfied. The basic idea of the token counter is that if the in average service rate to user i is less than then T, (t) becomes positive and so we are more likely to serve user i. If the average service rate to user i is more than Rr,rax then Ti(t) becomes negative and so we are less likely to serve user i. Recall that T is the time constraint of the exponential filter used to define Ri(t). The paper [9] shows that if T 1 0 and a, ex T for all i then as long as the algorithm converges it converges to the optimal solution of the problem (2.1). We remark that in [21], Liu, Chong and Shroff considered a similar problem to (2.1) and presented a different algorithm that is based on the theory of stochastic approximation.
Rr
3. External arrival process - Stationary channel process. The results described in the previous section show that by using the Proportional Fair algorithm we can achieve fair rate allocations in the case that
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS
7
each user always has data to serve. However, in some situations different users have different amounts of data to serve and our goal is to serve all the data. Suppose that for each user traffic arrives according to some stationary random process. Let a, (t) be the amount of data arriving for user i at time t. We sometimes refer to the process defined by (ri (t), a,(t)) as the input process of the system. Let qi(t) be the amount of user i data waiting for service at time t. The queueing process is updated as follows. If user i is served at time t then:
else
Let Ai be the mean arrival rate for user i. We say that the input process is schedulable if there is an SSS rule under which the average long-term service rate R, is greater than (1 - E)Ai for some E > O. We would like the scheduling algorithm to be stable. That is, we would like the algorithm to ensure that the queue process has a stationary distribution whenever the input process is schedulable. Note that if the queue process has a stationary distribution then the aggregate queue size cannot drift to infinity.
3.1. Proportional fair is unstable. An extremely natural question is: "Is the Proportional Fair scheduling algorithm stable?" This question was studied in [3]. However, before we present the answer we must examine exactly how the Proportional Fair algorithm is defined in the case that some of the queue sizes are extremely small. We may not want to serve a user that only has a small amount of data to serve. In [3]' three options were considered for whether or not a user is eligible for service. • Option AI. All users are eligible for service at every time slot. • Option A2. User i is only eligible for service at time slot t if qi(t) > O. • Option A3. User i is only eligible for service at time slot t if qi(t) ~ ri(t); i.e. there is enough data to fully utilize the time slot. Among all eligible users, the one with the highest value of ri(t)/ Ri(t) is selected for service. However, this still does not entirely define the algorithm since there remains the question of how we update the average service rate Ri(t) when the amount of data in the queue of the served user is less than the instantaneous service rate. In [3] the following options were considered, • Option B 1. When user i is served then R, (t) IS updated by R; (t + 1) == (1 - T) R, (t) + Tr i ( t). • Option B2. When user i is served then Ri(t) is updated by u,(t + 1) == (I - T)u.(t) + T min {r i ( t), qi(t) }.
8
MATTHEW ANDREWS
(We remark that as far as we are aware most practical implementations of Proportional Fair use options A2 and B1.) By considering all possible combinations of the "A" and "B" options we obtain six different algorithms. The main result of [3] is that none of these six algorithms are stable.' The instability example is extremely simple and consists of two users. The arrival process is constant, al (t) == 49 and a2(t) == 94 for all t. The channel process for user 2 is constant, rz (t) == 100 for all t. The channel process for user 1 is periodic with period 10, namely, mod 10 == 0 otherwise.
r (t) == { 1000 if t 1
100
This example is schedulable since we could schedule user 1 whenever t mod 20 == 0 and we could schedule user 2 in all other slots. In other words, half of the slots where "i (t) == 1000 are assigned to user 1, all other slots are assigned to user 2. This would result in an average service rate to user 1 of 50 and an average service rate to user 2 of 95. These service rates are more than the respective arrival rates. However, it is shown in [3] that Proportional Fair is not able to make the correct slot assignments. In particular, for each of the six versions of Proportional Fair, it is shown that user 2 receives only 9 out of 10 slots and hence its average service rate is only 90. Since the arrival rate for user 2 is 94 this means that the queue for user 2 grows without bound. 3.2. Max-weight is stable. Since the Proportional Fair algorithm is
not stable, the next question to ask is whether or not there exists a stable algorithm. The basic problem with Proportional Fair is that it does not take into account the queue lengths and so it does not know how to react when one queue starts to get too large. A simple algorithm that does not suffer from this problem is the Max- Weight algorithm that always serves the user with the maximum value of qi(t)ri(t). Note that this algorithm favors users with large instantaneous channel rates and users with large queues. Various analyses have shown that this algorithm is stable, for example [26, 27, 8, 7, 22, 19]. At a high level, the reason why the Max-Weight algorithm is stable is that Ilq(t)11 has a negative drift, where Ilq(t)11 == VLi(qi(t))2. To see why this is true, let Xi (t) be the amount of service that user i receives at time t under Max-Weight and let Yi(t) be the amount of service that user i receives at time t under the optimal SSS rule. By the definition of the MaxWeight we have that Li qi(t)Xi(t) ~ Li qi(t)Yi(t) and by the definition of 1 We remark that the instability example of [3] does not quite fit into the model that we have defined in this paper since the channel process is periodic rather than ergodic. (However, we conjecture that the result could also be extended to an example with an ergodic channel process.)
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 9
schedulability we have that for large w, E[Lt~t'~t+w(Yi(t/) - ai(t/))] EWAi for all i and for all t. Therefore,
>
Ilq(t + 1)11 2 == L(qi(t) + ai(t) - Xi(t))2 i
== Ilq(t)11 2 + L qi(t)(ai(t) - Xi(t)) + L(ai(t) - Xi(t))2 i
~ IIq(t)11
2
+L
qi(t)(ai(t) - Yi(t))
+ L(ai(t) -
Xi(t))2.
i
Since for all t and for large w, E[Lt
EWAi, we can use the above inequality to show that Ilq(t)1I has a negative drift over long timescales whenever some queue becomes large. We omit the details from this survey.
4. External arrival process - Adversarial channel process. Proportional Fair and Max-Weight are simple, appealing algorithms with welldefined provable properties. However, all of the results mentioned in the previous two sections make the assumption that the channel process can be modeled by a stationary stochastic process. There may be some situations however where this stationarity assumption does not hold. In particular, consider a vehicle driving away from a basestation. In this case the channel has a negative drift. Hence it makes sense to also consider an adversarial process that allows us to do worst case analysis. In this section we consider the scenario in which the data is generated by an external arrival process. In this case we assume that the adversary generates the arrival process as well as the channel process. As is usual in adversarial analyses, we must make some restrictions on the adversary otherwise it could overload the system and prevent any algorithm from having reasonable performance. We therefore define the adversarial model as follows. At each time step t the adversary generates the channel rate for user i, r i (t), and the amount of arriving data for user i, ai(t). In order to define whether this situation is schedulable, we assume that the adversary has its own "hidden" schedule. If user i is served by this hidden schedule at time t then we write Zi(t) == 1, else Zi(t) == O. We say that the input process is schedulable with parameters (W,E) if for any sequence of W time steps, the amount of data that arrives for user i in those time steps is less by a factor (1 - E) than the amount of service that the hidden schedule gives to user i, i.e. for any to, L~~~(~ ai(t) < (1 - c) L~~~(~ ri(t)zi(t). 4.1. Tracking algorithm is stable. Ideally we would like a schedule such that if the input process is schedulable then the queue sizes are bounded, i.e. there a exists a B such that qi(t) ~ B for all i, t. This question was addressed in the paper [11]. The first part of this paper looks at impossibility results. In particular, two results were proved. In order
10
MATTHEW ANDREWS
to understand the meaning of these results we let n be the set of channel rates used by the adversary. We also let Rinf == inf{r E R : r > O} and RSUP == sup{r E R}. Paper [11] shows: • If E > 0 then for any online scheduling algorithm A, the adversary can create a schedulable input process such that some queue is unbounded under algorithm A. In this example the rate set is infinite and satisfies Rinf == 0, i.e. the nonzero rates used by the adversary can be arbitrarily small. • If E == 0 then for any online scheduling algorithm A, the adversary can create another schedulable input process such that some queue is unbounded under algorithm A. In this example the rate set is infinite and satisfies n inf > 0, i.e. the nonzero rates used by the adversary are bounded away from zero. The intuition behind these results is that at each time step the adversary can determine which user will be served by algorithm A at the next time step. It then injects data in such a way that the only way to keep the queues bounded is to serve a user different from the one served by algorithm A. These results left open the question of whether there is a stable algorithm for the situation in which R is finite or the situation in which E > 0 and Rinf > O. The paper [11] shows that in both these situations we can obtain a stable online algorithm. Let us focus on the case that R is finite. The algorithm of [11] is called the Tracking Algorithm since it operates by trying to track what the adversary's schedule is doing. In order to describe the algorithm in more detail suppose that after the online algorithm has made its decision in time slot t, the adversary reveals which user was served by its schedule at time step t. Suppose also that the chan, J-ln-l). The next nel rate vector at time t, (ro(t), ... , rn-l (t)) == (J-lo, time after t that the channel rate vector equals (J-lo, ,J-ln-l) the Tracking algorithm serves the user that the adversary served at time step t. This very simple algorithm ensures that the queue size for each user i is always bounded by (2Fn + 1 )RSUP, where F == IRI, the number of possible channel rates. Unfortunately, this quantity is exponential in the number of users. Note however that in the Tracking algorithm just described, we need to keep track of which user was last served by the adversary for each possible channel rate vector. We show in [11] that for a slightly more complex version of the Tracking algorithm we can reduce the queuesize bound to (2nF 2 + l)RSUP by only maintaining state for each possible rate vector for each pair of users, rather than for each rate vector for all users. Note that the above description of the Tracking algorithm relies on knowing what the adversary did at the previous time step. In reality we cannot calculate this but we can calculate something similar that is sufficient to make the Tracking algorithm implementable. Recall that for the input process to be schedulable we must have that
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS to+w
L
t=to
11
to+w
ai(t) ~ (1 - E)
L
Ti(t)Zi(t),
(4.1)
t=to
for any to. Hence we can approximate the adversary's schedule in the following manner. We divide time into windows of length w. At the end of each window we know exactly what the arrivals were during that window and we know what the channel process was during the window. This means that if can solve the above integer program (4.1) with respect to the variables Zi(t) we can find the adversary's schedule for the previous w time steps. By using ideas similar to the above, this allows the Tracking algorithm to operate. The bound on the queue size becomes (2nP2 + 1)Rs u P w . However, this is still not quite satisfactory since for large values of w, the integer program (4.1) might be intractable. It is shown in [11] however, that the Tracking algorithm is well-defined even if we allow the adversary's schedule to be fractional (i.e. we divide service among multiple different users in each time slot). In this case the integer program becomes a more tractable linear program and we obtain the same bound on queue size. The above discussion focused on the case in which the feasible rate set is finite. If R is infinite but Rinf > 0 and E > 0 we show in [11] that we can still apply these results to obtain a stable schedule by rounding down each channel rate to the closest value "Yk == RSUP(1 - E/2)k for 0 ~ k ~ flog1-£/2 RsuPjRinfl .
4.2. Max-weight produces large queues. We have just described an online scheduling algorithm that is stable whenever R is finite or when E > 0 and Rinf > O. However, the Tracking algorithm is somewhat complex since it requires calculating the adversary's schedule over the past w time steps. It is therefore natural to ask whether there are any simpler algorithms that are also stable whenever these conditions hold. In particular, we would like to know how well the Max-Weight scheduling algorithm of Section 3 performs in this context. Unfortunately, the extremely interesting question of whether Max-Weight is always stable remains unresolved. However, the paper [12] shows that in some cases Max-Weight can perform significantly worse than the Tracking algorithm.
Recall that the more complex version of the Tracking algorithm produces queue sizes that are polynomial in the number of users. In contrast, [12] shows that for the rate set R used in the EV-DO system the adversary that can create an input process with E == 0 such that the queue size of one user can be as large as 8184 . 211" when n < 2048. The paper [12] also presents some simulation results for a natural example in which E > 0 and the channel rates are governed by a sequence of users moving past a linear array of basestations. In this case Max-Weight produced queue buildups that were significantly larger than those produced by the Tracking algorithm.
12
MATTHEW ANDREWS
Another contribution of [12] is that it defined a simpler Tracking algorithm that only used state for single users, rather than pairs of users. In particular, for each user i and for each /1 E R, the simpler 'Tracking algorithm maintains a counter c, (/1) that equals the number of times that the adversary served user i when ri(t) == /1 minus the number of times that it served user i when ri(t) == u. At all times it serves the user with the maximum value of ci(ri(t)). Although we are not able to prove any bounds for this simpler Tracking algorithm it performed better than the Tracking algorithms with provable performance bounds in many simulation examples.
5. Infinitely backlogged queues - Adversarial channel process. In this section we once again assume that the channel process is generated by an adversary. However, we now consider the case in which each user always has data to serve. Our objective is to maximize log R i , where R; is a measure of the service rate to user i. However, in contrast to Section 2, it no longer makes sense to measure a long-term average of service rate using an exponential filter since the feasible service rates could change dramatically over time due to the channel assignment process defined by the adversary. We therefore define R i (t) to be the total service for user i up to time t. That is, we update Ri(t) by if i == j if i i= j. In the spirit of competitive analysis, our goal is to define an online scheduling algorithm that always produces a rate assignment such that Li log R, (t) is as close as possible to the value produced by the optimal offline algorithm. In [4] it was shown that it is impossible to match the optimal value of the objective. In particular, if there are n users in the system, THEOREM 5.1. For any online algorithm A, the adversary can construct a channel rate process such that for some time t, Li log Ri(t) :::; Li log (t) - O(n log n), where (t) is the total service rate for user i of the offline scheduling algorithm that is optimal for time t. The proof is short and so we reproduce it here. Proof Let p be a parameter. We define a series of special time steps We let T == tn. We also define a sequence of sets Si; For by, tk ==. tk-l < t :::; tk the rate vector is defined by,
R;
R;
i:«
ri(t) == 1 ri(t) == 0
if i E Sk otherwise.
It remains to define the sets Si: The initial set So We define,
{O,1, ... ,n-1}.
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 13
(This means that ik is the user in Sk-l that has received the least amount of service by time tk). We define Sk == Sk-l - {i k }. Note that for online algorithms this process is well-defined since ik does not depend on Sk. We now analyze how much service each user receives. By the definition of iu,
Since rik(t) == 0 for t
> tk, pk + pk-l + ... + p n-k+1
Hence,
'L.-t " log R;(T) :S log -;;; P + log -n---1 p2 + P + ... + log(pn + pn-1
+ ... + p)
i
p(p2+p) ... (pn+pn-1+ ... +p) n! p2p3 ... pk+1 ... pn+l < Iog - - - - - - - n!(p - l)n
== Iog
=
(~lOgpi) + nlog p~ 1 -log(n!)
=
(~lOgpi) - n(n logn).
(The last equality holds because pS- is maximized for p == 2.) On the other hand, there is a valid schedule that assigns all the time slots between t., and ti+l to user i. This implies, n
LlogR;(t) 2: Llogpi. i
i=l
The result follows. 0 We now present a positive result. In particular we show that an extremely simple randomized algorithm can match the bound of Theorem 5.1 up to constant factors. LEMMA 5.1. For any sequence of rate vectors, if we serve each user at each time step with probability lin, the expected throughputs satisfy
LlogE[Ri(T)] 2: LlogR;(T) - O(nlogn). i
Proof Et~T ri(t)ln
i
Follows immediately from the fact that E[R i (T)]
2: RT(T)ln.
0
14
MATTHEW ANDREWS
We remark that we can approximate the performance of this randomized algorithm by treating it as a fractional schedule that assigns a 1/n fraction of each slot to each user and then "tracking" this schedule's performance using the Tracking algorithm of Section 4.
6. Wireless mesh networks. Up until now we have assumed a situation in which we only have a single basestation and multiple mobile receivers. In this section we briefly discuss the case of wireless mesh networks in which traffic is routed through a network consisting of multiple nodes. We consider the following model. We assume a set of sessions, each one consisting of a path through the network from a source node to a destination node. For each node-pair (i, j) we have a channel rate ri,j (t) that indicates the rate at which we can transmit from node i to node j at time t. At each time step, node i can transmit to at most one neighbor. If it selects neighbor j then the transmission rate is r i,j (t). If session i passes through node i then we let qf(t) be the amount of session-k data queued at node i at time t. We also let n~ be the next hop after node i on the path of session k. For the case in which the channel conditions are generated by a stationary stochastic process and data is injected into each session according to an external arrival process, a generalization of the Max-Weight algorithm defined in Section 3 is known to be stable. For this network version of Max-Weight, at each time step t and at each node i, the scheduler at node i calculates k" == argmaxk{(qf(t) - qkk(t))rink(t)}. If qf*(t) ~ qkk*(t) n ' n i
t
i
then node i sends session k* data to node n~* at time t. The amount of data that is sent is min{qf* (t), ri,n~* (t)}. For the case in which the channel conditions are generated by a stationary stochastic process and each session always has data to inject, suppose that we wish to maximize Lk log Rk(t) where Rk(t) is an exponentially filtered average of the session-k data that is served. We can solve this problem by using the Max-Weight scheduling algorithm and then injecting data into session k whenever Rk\t) -Tq;egin(t) > 0, where T is a small parameter and
qtegin (t) is amount of session-k data queued at the first node on session k's path. This mechanism can be viewed as a method for combining congestion control and scheduling in wireless networks. Note that if a wireless node on the path of session k becomes congested, the Max-Weight scheduling algorithm will create "backpressure" that will cause queue buildups at all nodes on session k's path that are upstream from the congested node. Eventually, qtegin (t) will become large. When this happens, the rule for data injection means that we are less likely to inject session-k data. Joint optimization of scheduling and congestion control can provide benefits in wireless networks for many reasons. A discussion of this issue may be found in [5].
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 15
The above algorithms for scheduling and congestion control in wireless mesh networks are special cases of the Greedy Primal-Dual algorithm for network control defined by Stolyar in [24]. (Similar algorithms were also proposed in [16, 23].) We remark that this Greedy Primal-Dual framework provides numerous extensions to these algorithms, including an algorithm for determining routes through the network in the case that routing is not fixed. For the case in which the input process is generated by an adversary much less is known. If only the traffic is generated by an adversary but the channel rates are constant then an algorithm similar to Max-Weight can keep all queues stable whenever possible [2]. This result also holds for the variable channel rate case in which all data is destined for a single destination and the packet routes form a rooted tree [13, 14]. However, for the general problem no algorithm is known that keeps the queues stable whenever possible. One partial result that was presented in [10] considers an algorithm that is a hybrid of the Tracking algorithm of Section 4 and the Nearest-to-Source algorithm [6] for wireline networks that always gives priority to data that is closest to its source. The paper [10] shows that this hybrid algorithm is stable as long as the adversary does not correlate the traffic arrivals with the channel rate process. That is, stability holds as long as the adversary does not overload the network if we restrict attention to a set of time slots that all have a common channel rate vector.
7. Discussion. In this survey paper we have presented a number of different models in which scheduling in wireless data networks can be analyzed. In these models we have discussed algorithms that perform well and we have presented some limits on achievable performance. One of the features of these results that we wish to highlight is that different algorithms work well in different models. For example in the stationary channel model Proportional Fair works well when we are trying to provide a fair throughput allocation and each user always has data to serve. In contrast, if the queues are fed by some arrival process then Proportional Fair is not always the ideal algorithm since it can lead to unstable queues. A number of open problems remain. First as mentioned earlier, what is the performance of the Max-Weight algorithm in adversarial channels? More generally, is there an algorithm that is simpler than the Tracking algorithm and guarantees stability whenever possible in the case of adversarial channels? Lastly, what is the best scheduling algorithm to use in wireless mesh networks? In particular, is there an algorithm that maintains network stability whenever possible and is completely distributed in the sense that it does not require any queue state information to be exchanged between neighboring nodes?
16
MATTHEW ANDREWS
REFERENCES [1] R. AGRAWAL AND V. SUBRAMANIAN. Optimality of certain channel aware scheduling policies. In Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, October 2002. [2] W. AIELLO, E. KUSHILEVITZ, R. OSTROVSKY, AND A. ROSEN. Adaptive packet routing for bursty adversarial traffic. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 359-368, Dallas, TX, May 1998. [3] M. ANDREWS. Instability of the proportional fair scheduling algorithm for HDR. IEEE Transactions on Wireless Communications, 3(5), 2094. [4] M. ANDREWS. Maximizing profit in overloaded networks. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005. [5] M. ANDREWS. Joint optimization of scheduling and congestion control in communication networks. In Proceedings of 40th Annual Conference on Information Sciences and Systems, Princeton, NJ, March 2006. [6] M. ANDREWS, B. AWERBUCH, A. FERNANDEZ, .1. KLEINBERG, T. LEIGHTON, AND Z. LIU. Universal stability results and performance bounds for greedy contention-resolution protocols. Journal of the ACM, 48(1): 39-69, January 2001. [7] M. ANDREWS, K. KUMARAN, K. RAMANAN, A. STOLYAR, R. VIJAYAKUMAR, AND P. WHITING. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Technical Memorandum, April 2000. [8] M. ANDREWS, K. KUMARAN, K. RAMANAN, A. STOLYAR, R. VIJAYAKUMAR, AND P. WHITING. Providing quality of service over a shared wireless link. IEEE Communications Magazine, February 200l. [9] M. ANDREWS, L. QIAN, AND A. STOLYAR. Optimal utility based multi-user throughput allocation subject to throughput constraints. In Proceedings of IEEE INFOCOM '05, 2005. [10] M. ANDREWS AND L. ZHANG. Routing and scheduling in multihop wireless networks with time-varying channels. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, January 2004. [11] M. ANDREWS AND L. ZHANG. Scheduling over a time-varying user-dependent channel with applications to high speed wireless data. Journal of ACM, September 2005. [12] M. ANDREWS AND L. ZHANG. Scheduling over non-stationary wireless channels with finite rate sets. IEEE/ACM Transactions on Networking, 2006. [13] E. ANSHELEVICH, D. KEMPE, AND J. KLEINBERG. Stability of load balancing algorithms in dynamic adversarial systems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Canada, May 2002. [14] B. AWERBUCH, P. BERENBRINK, A. BRINKMANN, AND C. SCHEIDELER. Simple routing strategies for adversarial systems. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 158-167, Las Vegas, NV, October 2001. [15] P. BENDER, P. BLACK, M. GROB, R. PADOVANI, AND N. SINDHUSHAYANA A. VITERBI. CDMA/HDR: A bandwidth efficient high speed data service for nomadic users. IEEE Communications Magazine, July 2000. [16] A. ERYILMAZ AND R. SRIKANT. Fair resource allocation in wireless networks using queue-length based scheduling and congestion control. In Proceedings of IEEE INFOCOM 'OS, Miami, FL, March 2005. [17] J. HOLTZMAN. CDMA forward link waterfilling power control. In Proceedings
of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring, pp. 1663-1667, Tokyo, Japan, May 2000. [18] A. JALALI, R. PADOVANI, AND R. PANKAJ. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceed-
ings of the IEEE Semiannual Vehicular Technology Conference, VTC2000Spring, Tokyo, Japan, May 2000.
A SURVEY OF SCHEDULING THEORY IN WIRELESS DATA NETWORKS 17 [19] N. KAHALE AND P.E. WRIGHT. Dynamic global packet routing in wireless networks. In Proceedings of IEEE INFOCOM '97, Kobe, Japan, April 1997. [20] H. KUSHNER AND P. WHITING. Asymptotic properties of proportional-fair sharing algorithms. In 40th Annual Allerton Conference on Communication, Control, and Computing, 2002. [21] X. LIU, E. CHONG, AND N.B. SHROFF. A framework for opportunistic scheduling in wireless networks. Computer Networks, 41(4): 451-474, 2003. [22] M. NEELY, E. MODIANO, AND C. ROHRS. Power and server allocation in a multibeam satellite with time varying channels. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002. [23] M. NEELY, E. MODIANO, AND C. LI. Fairness and optimal stochastic control for heterogeneous networks. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005. [24] A. STOLYAR. Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems, 50(4): 401-457, 2005. [25] A. STOLYAR. On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation. Operations Research, 53: 12-25, 2005. [26] L. TASSIULAS AND A. EPHREMIDES. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12): 1936-1948, December 1992. [27] L. TASSIULAS AND A. EPHREMIDES. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions on Information Theory, 30: 466-478, 1993. [28] D. TSE. Multiuser diversity in wireless networks. http://www.eecs.berkeley.edu/-dtse/stanford416.ps.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT FRANQOIS BACCELLI*, RENE L. CRUZt, AND ANTONIO NUCCI+
Abstract. We consider a single TCP session traversing a wireless channel, with a constant signal to interference and noise ratio (SINR) at the receiver. We consider the problem of determining the optimal transmission energy per bit, to maximize TCP throughput. Specifically, in the case where direct sequence spread spectrum modulation is used over a fixed bandwidth channel, we find the optimal processing gain m that maximizes TCP throughput. In the case where there is a high signal to noise ratio, we consider the scenario where adaptive modulation is used over a fixed bandwidth channel, and find the optimal symbol alphabet size M to maximize TCP throughput, Block codes applied to each packet for forward error correction can also be used, and in that case we consider the joint optimization of the coding rate to maximize TCP throughput. Finally, we discuss the issue of assigning target SINR values. In order to carry out our analysis, we obtain a TCP throughput formula in terms of the packet transmission error probability p and the transmission capacity C, which is of independent interest. In our TCP model, the window size is cut in half for each packet transmission loss, and also cut in half whenever the window size exceeds C. This formula is then used to characterize the optimal processing gain or the optimal symbol alphabet size as the solution of a simple fixed point equation that depends on the wireless channel parameters and the parameters of the TCP connection. Key words. CDMA, adaptive modulation, processing gain, block coding, signal to noise and interference ratio, power control, bandwidth sharing, congestion control, congestion avoidance, additive increase multiplicative decrease algorithm, TCP throughput, optimization, stochastic process, stationary distribution, Mellin transform. AMS(MOS) subject classifications. Primary 94A05, 94C99, 60K30.
1. Introduction. Cellular wireless networks were originally designed to support voice, which has stringent delay requirements. In these networks, a power control algorithm is used to maintain a target SINR for each user. The power control algorithm adapts to fast multi-path fading that arises due to mobility of users or the sources of scattering, so that a constant bit rate and a required maximum bit error rate is maintained for each connection, with low transport latency. Thus, for example, when a user encounters a fading channel condition, the transmission power is boosted so that the voice conversation can continue in real time. These systems have been adapted to carry data as well. A fixed capacity channel may be allocated for a data user. We are generally interested in optimizing the channel parameters in order to provide the best performance for the data user. For simplicity here we assume that a data user corresponds to a single TCP connection. We assume that the channel is *INRIA-ENS (franco is . baccelli
20
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
allocated a SINR which will be maintained to a constant target value. We focus on the case of a long lived TCP connection. The target SINR value may be adapted over time to respond to user mobility, and we consider the regime where the TCP connection reaches a steady state between updates of the target SINR value. We consider first the case of CDMA, and consider the problem of optimizing the processing gain m and coding rate p to maximize TCP throughput. By adjusting the processing gain and coding rate, we tradeoff the bit transmission rate C and packet transmission error rate p. By making the processing gain m large we increase the energy per bit and so the packet transmission loss probability p is small. However, the bit transmission rate C is proportional to 11m. We also consider the context of a high SINR channel over a fixed bandiwidth. In this case, we study adaptive modulation, where the symbol alphabet size M is adapted. In this case the raw transmission rate C is proportional to log2(M), but the probability of a packet error p grows quickly with M. We find the optimal value of the alphabet size M in order to maximize TCP throughput. To understand the nature of the optimization we consider, it is useful to think of two extremes. At one extreme we can make the bit-transmission rate C high, but the packet transmission error rate p will be large, Packet transmission errors will generally cause the TCP protocol to reduce its window size, and in turn decrease throughput. At the other extreme we can make the packet transmission error rate p very small, at the expense of reduced transmission rate C. The bit transmission rate C ultimately limits the TCP window size, since buffer overflows will occur when the window gets sufficiently large, and TCP will cut the window size in half, responding to the congestion that occurs at the buffer. Thus, TCP throughput is small at this extreme as well. In order to find the optimal operating point, we consider a model for analyzing the TCP throughput where packet losses due to transmission errors and packet losses due to congestion events are distinguished. In Section 3, we consider a fluid model where the window size is cut in half for each packet loss due to a transmission error or buffer overflow event. The packet loss probability is p, and we assume that a congestion event happens when the window size reaches a value that matches the bit-transmission rate, C, on the channel. This model is appropriate for small buffers. This makes sense within e.g. the CDMA context where the bit-transmission rate is small, compared to what is available on wireline networks, and where large downlink buffers would imply large RTTs and hence poor TCP performance as TCP throughput is known to be roughly inversely proportional to RTT. For this model, we find a formula for the TCP throughput asa function of p and C, which is of independent interest. This is a generalization of the well known"square root" formula (e.g. see [11]) for TCP throughput
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 21
where packet transmission errors and buffer overflows are not separately modeled. We also obtain formulas for the probability density function of the TCP window size. In Section 4, we show how to use the analytical framework for TCP throughput in the particular case of wireless channels with fixed SINR. We consider several cases ranging from CDMA to adaptive modulation, with or without FEC. We show that the TCP throughput can be fairly sensitive to the .physical layer parameters, i.e. the processing gain m or symbol alphabet size M, and we give simple analytical characterizations of the optimal values for these parameters. We also discuss, in Section 5, the problem of assignment of target SINR values in a network context, and specifically discuss the case of a wireless cellular CDMA downlink. Before describing our model and analysis in more detail, we first discuss some related work.
2. Related work. Many authors have considered the general problem of performance of the TCP protocol over wireless links. A comparison of various approaches to the problem is given in [4]. One branch of related work is concerned with the problem of determining whether packet losses are due to congestion or due to transmission errors, so that TCP can go into congestion avoidance mode only when packet losses are due to congestion. A second branch of work considers the approach of splitting the TCP connection at the wire-line/wireless infrastructure boundary, so that the TCP connection is isolated from the packet transmission errors on the wireless channel. A third approach to optimizing TCP performance over wireless channels is to optimize the link layer for TCP performance. The approach we take in this paper falls into the third category. Zorzi and Rao [14] considered the effect of correlated errors on TCP throughput. Correlated errors typically occur due to multi-path fading. In our model, we assume a fixed SINR (thanks to power control), so errors can be modeled as independent. Chaskar, Lakshman, and Madhow [5] consider the use of link layer ARQ over the wireless channel to hide packet transmission errors. In this case, TCP primarily reacts to buffer overflows only. In [5], it is suggested that the physical layer parameters should be optimized so that the buffer overflow probability q times the bandwidth delay product squared is equal to one. Liu, Goeckel, and Towsley [10] considered the problem of adapting the coding rate p to the channel conditions, with the objective of maximizing TCP throughput. It was already noted in [10] that optimal values of operating parameters for the channel for TCP were different than those for UDP. In [9], Liu, Zhou and Giannakis used simulation to study cross-layer optimization within the adaptive modulation setting.
22
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
The main novelty of the present paper is the fact that it provides an analytic framework for this adaptation. Several recent papers provide analytical formulas for the throughput of a large collection of competing TCP flows with both congestion and transmission error losses (see [2] and the references therein). The main difference with [2] and related papers is that we are here focusing on the rate of a single TCP connection constrained to remain below the rate C and subject to both random transmission error losses and to losses that occur when its rate reaches or exceeds C. To the best of our knowledge, this setting, the associated formulas for TCP throughput and the analytic characterizations of the optimal wireless channel parameters that are derived in the present paper are all new.
3. TCP throughput. 3.1. Model. In this section, we analyze the throughput of a single TCP flow over a wireless channel. Each packet contains L bits, and when it is transmitted over the channel, it is lost with probability p. We assume that packet transmission errors are independent. Later on, in Section 5, we will consider how the packet transmission loss probability p depends on , and other physical layer parameters. We assume it takes L/C seconds to transmit each packet on the channel. The parameter C is called the raw transmission capacity and has units of bits/sec. We now consider a fluid model for the TCP flow. Our model is in terms of the parameters C and p discussed above. Consider a random process X (t) that models the instantaneous throughput for the TCP flow. The instantaneous throughput is assumed to be proportional to the TCP window size. Our model for the dynamics of X (t) is as follows. Let R be the round trip delay (assumed constant here), in units of seconds. When there is no loss, at time t, X(t) increases at rate L/ R2. If X(t) reaches C, a congestion event occurs, causing X(t) to be reduced in half to the value C /2. Packet losses are modeled by a time in-homogeneous Poisson process, where the rate of loss at time t is ;\(t) == pX(t)/L. This reflects the fact that the rate of packet loss is higher when the packet rate is higher. When there is a packet loss at time t, the value of X (t) is reduced in half. Of course a more refined model would take into account the presence of a buffer and the fact that losses only take place when this buffer overflows. In Section 6, we will show by simulation that the conclusions obtained from our simplified bufferless model are still valid for this refined model.
3.2. Distributions. We first define some notation. Let ex == pR2 / L 2. Define Ao == 1 and for l 2 1 define
Aj =
II l
J=1
(
-4
22]
_
1
)
.
(3.1)
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT
For I
~
23
1 and n ~ 2 define al,n
== A l - 1 exp( _(2 2(l-
[1 + (221~
l) -
1)a(C /2 n ) 2 /2)
(3.2)
n 1)eXP(- (3)22(1- 1)a (C/ 2 )2/ 2)] .
The following is proved in Appendix B. THEOREM 3.1. Let f(x) be the stationary probability density function
for the instantaneous throughput X (t) of the TCP connection. The density f satisfies the differential equation ifC/2 < x S; C ifOS;x
df(x) __ { -axf(x) dx -axf(x)+4axf(2x)
(3.3)
where a == pR2 / £2. The density f(x) is discontinuous at x == C/2 and such that
(3.4) The density f (x) is given by n I Aie _2 f( X ) -_ " L....-t' TVn-l
2l
ax
2/2
(3.5)
l=O
if C /2 n +1 < x < C /2 n for n ~ 0, 0 otherwise, where the constants Vo, VI, . .. are the solutions to the equations
(3.6) n
Vn
==
Lal,nVn-l
for n > 1 ,
(3.7)
l=1
and
L 00
m=O
Vm
1
[C/2
Tn
=+1
2
]
exp( -ax /2)dx =
C/2
[
LT 00
k
]
Ak .
-1
(3.8)
k=O
It is interesting to note that in all cases examined so far, the constants
Vn appear to converge to a constant as n 3.3. this case f(x) is a case the and C.
~ 00.
Limiting cases. First consider the case where p == a == O. In it can be verified that L:~o Vn-lA l == 0 for all n > 1 and hence uniform distribution on [C/2, C]. This is expected since in this trajectory of X (t) is a sawtooth pattern varying between C /2
24
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
(\
I
Ij \\
0.8
I \
0.3
/
0.2
/
/
I
04
I \ I
/
)
\
I \\
/
/
0.1
I
0.6
;'
FIG. 1.
I
I \\ I
0.4
/
02
I
I
\
I !
\
"'.,..-
Probability Density of Instantaneous TCP Throughput: Examples.
Next consider the case where C approaches infinity. In this case, it can be verified that Vn tends to Va for all n. Hence in this case we have f(x) == Va(E~a Aze-22lax2 /2) for all x > O. This is precisely the same result obtained in [3]. This is expected since letting C approach infinity is equivalent to having transmission losses only, which coincides with previous models. 3.4. Examples. We now illustrate the above results with some numerical examples. Suppose C == 5, R == 100 and L == 40. In Figure 1, the density f(x) of the instantaneous throughout is plotted versus x for two different values of the packet loss probability p. The left plot shows the case p small. In this case, note that there is a visible discontinuity in the density at x == C /2, reflecting the jumps from C to C /2 when the instantaneous throughput hits the boundary C. The right plot shows the case p large. In this case the packet loss probability is high enough so that it is unlikely that the instantaneous throughput is near the boundary C, and thus there is no visible discontinuity in the density at x == C /2. Note that in all cases, f (x) is nearly zero when x is close to zero, which is because packet loss becomes an unlikely event when the instantaneous throughput is near x == O. 3.5. Mean values. The mean throughput of TCP is given by
TCP(C,p)
=
1°
xf(x)dx.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 25
Specifically, by using (3.5), after some algebraic manipulation, we can show that
In the following theorem we obtain a closed form equation for TCP(C,p), which leads to a simple approximation for TCP(C,p). Let !(u) be the Mellin transform of f (x): (3.10) with u
~ 1.
Let f(u) be the Mellin transform of e- x , i.e.
1 00
r(u) =
e-Xxu-1dx .
Note that f(·) is the well known gamma function and satisfies the identity I'( u + 1) == uf( u). For alIi ~ 0, define l
III (u) ==
II (1 - 2-
u- 2
k) .
(3.11)
k=O
The following is proved in Appendix C. THEOREM 3.2 (Mean TCP Throughput). The Mellin transform of the probability density f (x) of the instantaneous TCP throughput is given by __
f( U) ==
"LJI?O II I (U )Gu
(ac
l
2
-2-
)
aC 2 l
L:l~O Ill(l)C (-2-)
f(u/2)
r(u/2+1+1)
f(1/2)
(3.12)
f(1/2+1+1)
In particular, the mean TCP throughput is
REMARK 3.1. We have two different expressions for the mean stationary throughput, obtain by two different methods: that of Equation (3.9) and that of Theorem 3.2 above. It would be interesting to prove directly that the two expressions are equal, but we have not been able to do this. We have checked the equality numerically to see if the two expressions yield the same numerical result, and in all cases we tested, the results matched closely. From (3.13) we obtain the following approximation, proved in Appendix D.
26
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
3.1 (Approximation to Mean TCP Throughput). mean TCP throughput satisfies COROLLARY
3C
TCP(C,p) ==
4 -
pR 2C 3 11
---v:- 256 -
925667
+ 377487360
p3 R
6C7
£6
p2R 4 C S
497
£4
491520
The
(3.14)
o( 3 R 6C7jL 6)C . + P
Higher order expansions are easily obtained using e.g. Maple. As expected, the values of the throughput are insensitive to the value of C if the packet loss probability p is sufficiently high. In fact we have the following corollary. A sketch of the proof is provided in Appendix E. COROLLARY 3.2. For all p > 0 we have
.
f2
1 II 00 (2)
1.309
J~oo TCP{C,p) = V~ ftIIoo{l) ~ ..jPR/L ·
(3.15 )
The result in Corollary 3.2 coincides with [3], which is expected since letting C approach 00 is equivalent to considering random transmission losses only. 4. Optimization of wireless channel parameters. In this section we consider optimization of the wireless channel parameters to maximize the throughput of the TCP session that passes through it. We can use the formula for the TCP throughput in (3.14) to evaluate TCP(C,p) as a function of C and p. The wireless channel parameters will determine C and p, and we wish to maximize TCP(C,p) with respect to these parameters. We will consider two regimes, the low SINR regime and the high SINR regime. For example, the low SINR regime arises in the context of codedivision multiple access (CDMA) systems. In this regime, a processing gain m is used to adjust the transmission data rate, or equivalently the transmission energy used per bit. A large processing gain is generally needed to compensate for low SINR. We shall consider the problem of optimizing the processing gain to maximize TCP throughput. We shall also consider the use of error correction codes, and jointly optimize the coding rate and the processing gain. When the SINR is high, it is possible to reliably send more than one bit per transmitted symbol. If the number of possible values of each symbol is M, then M is called the alphabet size. The number of bits per symbol is log2 M. A large SINR generally enables use of an alphabet size greater than two with low probability of symbol error. We consider the problem of adjusting the alphabet size in order to maximize TCP throughput. In the next subsection, we present a wireless channel model, which yields formulas for p and C as a function of the wireless channel parameters.
4.1. Wireless channel model. We first consider a model appropriate for a low SINR at the receiver, in the context of a CDMA network.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 27
4.1.1. Code division multiplexing without FEC. We will consider the case of code-division multiplexing with direct sequence spread spectrum modulation, with a chip duration of T; seconds. Binary Phase Shift Keying (BPSK) is assumed as the underlying modulation scheme. Each bit transmitted is encoded into m chips using a spreading sequence, where m is called the processing gain. The bit transmission rate is thus
c=
1
(4.1)
mTc '
Typically, many users may transmit at the same time, causing interference at each receiver. Each user has a receiver which correlates the incoming signal with the spreading sequence used at the transmitter. Let 1 be the signal to noise plus interference ratio (SINR) at the output of the correlator. We shall define 1 mathematically when we discuss assignment of SINR values later. If we model the interference at the correlator output as Gaussian, the probability of a bit error is
BER == Q(JTF0),
(4.2)
where Q(.) is the CDF of the zero mean unit variance Gaussian density, oo x2 i.e. Q(x) == (1/ /21f) Jx e- / 2dx. In the uncoded case that we consider here (no FEC), each packet corresponds to transmission of L bits on the channel. The probability of a packet error is
(4.3) We will use the following approximation for p, which is valid when BER is small: p ~ LQ( JTF0)
.
(4.4)
4.1.2. Code division multiplexing with FEC. We shall also consider the case where a block code for forward error correction (FEC) is used. In this case, the L bits of each packet are encoded into N bits, where N 2: L. The ratio p == L / N is called the coding rate. Since we count throughput in terms of information conveyed, the bit transmission capacity in this case is C==
p
-T . m
(4.5)
c
The collection of N bits is called a codeword, and there is a codeword for each of the 2£ possible bit patterns of a packet. In general, the N codeword bits contain redundancy, so that if bit transmission errors occur, the bit pattern of the originally encoded packet can sometimes be recovered
28
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
at the receiver. We assume that up to t errors can be corrected, and that t + 1 or more bit transmission errors result in a packet loss. The probability of a packet error is thus
~(N) j
P = j~l
.
[Q (0WYW [1- Q (0WY)] N-J'
.
Define () == (t + 1) IN. We use the following large deviations-based estimate for p: (4.6) where q == Q( jiiVY) and h(x) == -x log2(x) - (1- x) log2(1-x) is the binary entropy function. Notice that this approximation uses the dominant term of Stirling's formula, and that better expansions could be used. In order to determine t, or equivalently (), we use the Gilbert-Varshamov bound ([12] p. 463, [15], §IILA), which implies that for a given coding rate p, there exists a block code with "error correction capability" (), where () satisfies p == 1 - h(2()) .
(4.7)
4.1.3. Adaptive modulation. Next, we discuss a scenario appropriate for high SINRs, where more than one bit can be conveyed per transmitted symbol. In the adaptive modulation we consider, the alphabet size M can be varied. Each symbol can thus take on M possible values. The duration of each symbol is T seconds, and the bandwidth of the transmitted signal is proportional to 1IT. The bit transmission rate in this scenario is therefore C
==
log2 M T .
(4.8)
We define the signal to noise ratio 'Y in this case to be ratio of the average
symbol energy at the receiver to the noise power spectral density. It should be noted that "'I is also equal to the ratio of the signal power at the receiver to the noise power at the receiver, after channel bandpass filtering. As stated in [6], for large values of " the probability of a bit error is well approximated by
Since we have L bits per packet, we use the following approximation for the probability of a packet transmission error, which is valid when BER is small:
(4.9)
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 29
,i
First we consider a single TCP session i which is assigned a given SINR == 1. We are interested in optimizing the processing gain m, == m value and the coding rate Pi == P in order to maximize the mean TCP throughput. Recall that we have C == -mL rc ' and that the packet error probability p is a decreasing function of m and an increasing function of p. We wish to maximize M == TCP( C, p) over all possible values of m and p.
4.2. Optimization of TCP throughput. In this subsection we consider optimization of TCP throughput in the three cases outlined in the previous subsection.
4.2.1. Code division multiplexing without FEC. We first present some numerical results. In Figure 2, we consider the case where Ii == 0.03 and the RTT value is R == 0.1 second. On the top right curve we plot the TCP throughput as a function of the processing gain m. We see that there is fair amount of sensitivity to the processing gain, and there is a unique maximum around m == 450. To get a better sense of this, on the top left plot we illustrate the TCP throughput ISO curves, i.e. values of C and p that yield the same TCP throughput. Superimposed with these ISO curves, we plot the locus of (p, C) values corresponding to different values of processing gain. We see that the optimum processing gain corresponds to crossing a "knee" of a TCP ISO curve. For reference, we consider optimization of the "UDP throughput" C(l- p) in the bottom two plots in Figure 2. In this case we use (4.1) for C and (4.4) for p in the expansion for TCP(C,p) in (3.14), for an explicit optimization of the mean throughput. Using the approximation Q(x) ~ e- 2 in (4.4), we have
vbx x2/
(4.10)
If aC 2 /2 is small, then the first order expansion of the "few losses" case (see (D.3)), corresponding to the first two terms in (3.14), gives the following expression for the mean rate TCP(C p) ,
~
1(3 T21
4Tc
- - - - -3(3- e m m !iYi C
!!!J.) 2
Villi
(4.11 )
'
with 13 = 64il~. Differentiating with respect to m, we get that the optimal m solves
1 1(
- -2 4Tc m
- 3 +(3-
2TJ
(f m/Tii
7) _
- - + - 2/Tii --
m
e
Tn, ) 2
==0
'
that is
(4.12)
30
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI 4
X 10 1.6...---,.....--.....----,-----.---.,
Tep Throu h ut Isocurves
r-;
1.4
2.5
I~",
1.2
1.5 1
t
12000' 10000"'"
/ /
0.8 . 0.6
_8000-......_
_
--.,;:;~.....Io--_
0.01
...._ ..._
- 8000- ..
0.06
,)
0.4~.../
_--Lo._---L_--l
0.04
'
o
0.08
200
400
4
x 10
2.5
UDPGoodput Isocurves
25000 (10
aU
0
0
0
0
0
en
2
2
2.5
en a.
2
,gsa.
1.5
X
0
~
0.02
0.04
0.06
0.08
1000
4
j~-, '"
~
,
-,
I
<;
I I
""-,''"'---
/
a.
1.5
800
10
"'0 0 0 (!}
o
600 m.I
P
0.5 0 0
t
)
200
400
600
800
0
m.I
P
FIG. 2. Example of cross-layer optimization result - Uncoded case: Ii == 0.03, R== 0.1 second.
Higher order approximations of Q can of course be used in the same way when needed. Taking L == 320, R == .1, r == 3 . 10- 2 , T; == 10- 7 , we get {3 rv 1.15 . 10- 6 ; so using the first order approximation for the TCP throughput, the optimal processing gain m satisfies e-· 015m == 4.727.10- 9
mVi'i .
.03+ 2m
(4.13)
The solution is m == 459. The associated value for aC 2 / 2 is pC2 R 2/ (2L2) rv 0.815 which, upon examination of (3.14), justifies the use of the few loss approximation (the correction brought by the second order term is appro 4/1000 of the value given by the first order approximation). REMARK 4.1. Our model has an interesting relation to [5}, where all packet transmission errors are hidden with a link layer mechanism (eg link layer ARQ), so that the only packet losses that TCP reacts to are buffer overflows at the link layer buffer. Let Wbd be the bandwidth delay product (where bandwidth is defined in units of TCP packets/sec). The authors of [5] propose sizing the buffer so that the overflow probability q satisfies q(Wbd)2 == 1. With our method, we find the optimal operating point at aC 2/2 == 0.815, which is equivalent to p(Wbd)2/ 2 == 0.815.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT
rcr ThroughputoPt[bps], sinr=0.03,rtt-u.ts
600 500
---15k
31
UDP GoodputOPt[bps], sinr=0.03, rtt=0.15
500
400
400
-23k -24k _~"(>.):,:.,,,.:
200
-_.
100_~'"
-~
100-~
o
'------'----""-------'---~
0.2
0.4
0.6
,:.~6k
200
0.8
0'------'----"----'-------' 0.2 0.6 0.4 0.8
KlLopt
KlLopt
4
opt X 10 4.5 ..------r-~::.w..a.JIU~:JU..L-...,.....t_____,
opt \
TCPT -
4
UDPG
I
3.5
i
3
~ 2
2.5
2
I
1.5 -
TCPT
UDPG
I
1 '------'----""---------'--~ 0.2 0.6 0.8 0.4
o o
L..-.I---_~ _
250
_" -_
500
__'___----'
750
1000
KlL
,i
FIG. 3. =:
0.03, R
Example of joint optimization of processing gain m, and coding rate K/ L. =: 0.1 second.
4.2.2. Code division multiplexing with FEC. In this case, we wish to jointly optimize the processing gain m and coding rate p in order to maximize TCP throughput. In this case we use (4.5) for C and (4.6) for p, where () is determined from p using (4.7). In Figure 3, we again consider the case where 1 == 0.03 and the RTT value is R == 0.1 second, and plot results for when both the processing gain m and the coding rate p == L / N are jointly optimized. The top left plot shows how the optimum processing gain m * changes as a function of the coding rate p. On the graph we have also labeled the approximate value of the TCP throughput corresponding to each point. For example, for a coding rate of about 0.4, the optimum processing gain is about 100, and the corresponding TCP throughput is about 31Kbps. For comparison, in the top right plot we show how the optimum processing gain m * changes as a function of the coding rate p, where we optimize UDP goodput, i.e. (1 - p)C. In the bottom left plot we show the optimal TCP and UDP throughput as a function of the coding rate p. In the bottom right plot we show the optimum TCP and UDP throughput as a function of the processing gain m. Next, we describe a procedure for an explicit joint optimization. Define J == TCP(C,p). We are interested in maximizing J with respect to the
32
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
processing gain m and the coding rate p. For convenience we optimize the TCP throughput J with respect to m and (), and then the optimal coding rate p* is determined by ()* through (4.7). Note that ()* and m* satisfy g~ == 0 and ~~ == O. Define FI (m, ()) == ~~ and F2 (m,()) == g~. In Appendix F, we provide the calculation of F I and F 2 • We can solve the two non-linear equations F I (m, ()) == 0 and F2 (m,()) == 0 in order to determine the optimal processing gain m* and the optimal value of the coding rate p*, where p* is found from ()* by using equation (4.7).
4.2.3. Adaptive modulation. Using the approximation Q(x) _1_e~x
x 2
/
2
~
in (4.9) we obtain '
p
rv
2L
-1M-I -IMlog 2 (M)
J(M-l)e-2(~~J).
(4.14)
) 67f1
Using C == log2(M)/T and (4.14) in the expansion (D.3) gives: - l) TCP(C p) ~ - 1 ( 3Iog 2(M) - -1) (-1M - 1))M - 1 e- 2 ( M3~) (4.15) '4T T2 -IMlog 2(M)
with rt = 64~1.%wr. Differentiating with respect to M, we get that the optimal M solves
1(3
4Tc
M log(2)
- -1)e _ T2
3~
2(M-l)
k(M) ) = 0
with
k M _ 3')' . (-1M -1)JA1=l ( ) - 2(M - 1)2 -1M log2 (M ) log (M)2M-.JM-l 2
+ +
2y'M-l 2 Mlog 2(M)
(VM -l)VM
-1
(log2(M) 2VM
+
I ) VM log(2)
Mlog~(M)
.
Hence, the optimal M solves e
_ _ _3~_ _ 2(M-l)
3T 2 1 2Iog(2)1] Mk(M) .
== - - - - - -
(4.16)
Consider the case where T == 10- 7 , R == .1, and L == 1500. In this case, we get M* == 7 for T == 60 and M* == 14 for T == 200. In Figure 4, we plot the mean TCP throughput as a function of M for T == 60 and 1 == 200. We see that this analysis predicts the optimal value of M closely.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 33
,/~///F " ' , \ /
./
2. e+07
/
e+07
/f
1. e+07
/
/
/
\\,
\
/
j i
i
I
\ \
/ I
!
/
!
9+07
I
I
e+06
I i
i i
o
o1
2
10
M
FIG.
12
14
16
M
4. Mean TCP throughput as a function of the constellation size based on (4.9).
5. Assignment of SINR values. In this section, we first recall classical results on the downlink of a cellular CDMA network in §5.1. Based on this, we propose in §5.2 an assignment of SINR values (Equation (5.4) below) to the different users, that takes into account their interactions in the network. These SINR values are hence those to be used in e.g. Equation (4.12) when considering the optimization of such a CDMA framework. Suppose there are multiple users on the downlink of a CDMA cellular system, where the users may be associated with different base stations. The signal transmitted for the i t h user at the associated base station is denoted by Si(t) is given by
where Pi(t) is called the spreading code, bi(t) is called the data signal, and Pi is a constant. The spreading code Pi(t) takes on values in {-1, 1} and is constant over intervals of duration T e . Specifically, 00
Pi(t) ==
L
ciu(tjTe
-
k),
k=-oo where u(x) == 1 if 0 < x < 1 and u(x) == 0 otherwise, and for each user i, the elements of the sequence {ci}k=-oo are either +1 of -1. The constant T; is called the chip duration and is constant across users. The data signal bi(t) is also taking its values in {-1, 1}. For the i t h user, we assume that each bit to be sent is repeated m, chips, where m, is an integer. Specifically, we have
34
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI 00
n=-oo
The quantity m, is called the processing gain for user i. The data rate for user i is thus l/(miTe). Note that (Si(t))2 == Pi, and so the parameter Pi is called transmission power for the i t h user. Typically either pseudo-random or known deterministic sequences are used to define the spreading codes. For purposes of analysis here we assume that JP>{ == 1} == JP>{ == -1} == 1/2 for all i, k, and that is independent if i =1= i' or k =1= k'. We shall also assume that the data bits are of random and independent, i.e. IP{b~ == 1} == IP{b~ == -1} == 1/2 for all i, n, and that b~ is independent of b~, if i =1= i' or n =1= n'.
ct,
ct
ct
ct
We assume a so-called flat fading (i.e. frequency non-selective) channel model. Let vgki be the signal path gain from the base station associated with user k to the location of user i. For example, the useful signal at user i is given by vgiiSi(t). However, the signal intended for another user k, namely vgkiSk(t) also arrives at the location of user i, with possibly a time shift reflecting the different distances between base stations and users. In addition, an external white Gaussian noise signal ni(t) is also present at the receiver for user i, with two-sided power spectral density N~. The total signal at the receiver of user i is
ri(t) == vgiiSi(t) +
L
ygkiSk(t -
at) + ni(t).
k:k=j;i The numbers
at characterize the propagation delays between transmitters
and receivers.
We shall assume that a~ == 0 for all users k which are associated with the base station that user i is associated with. This is because the associated signals from such users k travel along the same path as the signal from user i. For other values of k, we shall assume that is a random variable uniformly distributed between 0 and miTe. In general the values of could be larger than miTe, but since we assume that all chips and data bits are random, there should be no loss of generality in this assumption.
a1
a1
5.1. Probability of a bit error. Consider the receiver at user i, in particular the operation of decoding the data bit represented by bb. The receiver first correlates the incoming received signal with the spreading code for user i, namely Pi(t), and integrates the output of the correlator over the interval [0, miTe]. The output of the integrator is Z~, where
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 35
l =l
Z6 =
rn i T c
pi(t)ri(t)dt rn i T c
Pi(t) ( V9iiSi(t)
o
L
j9ki Sk(t - at)
+ ni(t))
dt
k:k:/=i
= b~JgiiPi
l
+
l
rn i T c
(Pi(t))2dt +
o
L
JgkiPk
k:k:/=i
rn i T c
Pi(t)Pk(t - ak)bk(t - ak)dt
== bb J giiPimiTc +
L
+ Yd
J gkiPkPk,i + Yd,
k:ki=i
where
and
Pi,k
=
l
rni T c
Pi(t)Pk(t - aDbk(t - ak)dt.
The first term above, bbJg;;P;miTc, can be thought of as the "signal component"; the second term, Lk:k:/=i Jgk;PkPk,i is the "interference," and the last term yoi is the "noise". The receiver decides whether bb == 1 or bb == -1 on the basis of whether Z~ > 0 or Z~ < 0, respectively. The probability of a bit error for user i, BER i , is therefore
BERi
== P{
L J gkiPkPk,i + yd > J giiPimiTc}. k:ki=i
Note that Yd is a Gaussian random variable with zero mean and variance N~miTc. Using the central limit theorem, we approximate the interference term as being Gaussian as well, and independent of the noise term. In Appendix A we show that the interference term, Lk:k:/=i V9kiPkPk,i has variance (2/3) Lk:k~i gkiPkmi (T c )2. The sum of the interference and noise term therefore has zero mean and variance (Lk:k#i (2/3)9kiPkmi(Tc)2)
+
NOmiTc.
Approximating the interference terms as Gaussian, a standard analysis yields that the probability of a bit error, BER, is (5.1)
where
(5.2)
36
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
The quantity miri is known as the "EbjNo", or energy per bit per noise power density.
5.2. SINR allocation. Due to mobility of users, the gain values {9ki} change with time. We assume that a closed loop power control algorithm is used, to vary the power values {Pi} to maintain the SINR values {r i } at prescribed values. Define the SINR vector r(p) == [r 1,r2, ... ,rN]T. We say that an SINR target vector 1 is feasible if there exists a set of non-negative power values {Pi} such that r(p) == 1. If 1 is feasible, then the power control algorithm sets the transmission powers {Pi} accordingly to achieve the target SINR vector 1. Next we examine the feasibility condition for a target SINR vector. If ~ 1, then for all i we have
r
where a i2 == NoOJTi: Equivalently, we have
Pi - (2/3)'yi
L (gki/ gii)P
k
~ ''fiaT / gii ,
k:ki=i
or in matrix notation, P- F P ~ b, where F == {Fi,j} is an N x N matrix with Fii == 0 and Fi,j == (2j3),i(gjij gii) if i =1= j, and
b == ['1 ar /911, '2a~ /922, ... , '"'(Na'ftv / 9N N ]T. There exists a non-negative finite P satisfying the above, if and only if the spectral radius of the matrix F is less than unity. In this case, the minimal P satisfying the above is P* == (I - F) -1 b. The minimal power vector P* can be found by an iterative distributed algorithm. There may be additional constraints on the power vector, e.g. there is generally a peak power constraint for each base station. A simple sufficient condition for the spectral radius of F to be less than 1] is that each row sum of F is less than 1]. In general, we can set 1] strictly less than 1 as a safety margin, as suggested in [1]. Setting 1] == 1, 1 is feasible if for all i we have
(2/3)'"'(i
L (9ki/9ii) S 1 .
(5.3)
k:ki=i
Note that gki/ gii == 1 for all users k that are associated with the same base station that user i is. Furthermore, the value of 9ki/9ii is the same for all users k which are associated with the same base station. Suppose there are B base stations. Let b, be the base station associated with user i. Assuming b =1= bi, define CYb(i) == 9ki/9ii, where k is such that user k is
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 37
associated with base station b. Let N b be the number of users associated with base station b. Defining Nfnt == Ek:k=/=i (gki/ gii), we thus have
L
Nfnt == N bi - 1 +
ab(i)Nb.
b:b=/=bi We call Nfnt the effective number of interfering users for user i. The attenuation factor ab( i) can be measured by user i by comparing the power received in pilot tones from base station b and it's assigned base station. The values of Ni, can be considered to be slowly varying, and reported directly to the base station associated with a given user i. If each user i reports the measured value of ab( i) to its associated base station for all b, then the value of Niint is known to the base station associated with user i, b.. Hence base station b, can calculate an appropriate value for the target SINR '"'Ii. In particular, we can set 1.51] '"'Ii == N~nt'
(5.4)
t
where 1] is a parameter set to a number strictly less than unity, as a safety factor. Note that in general, since the matrix F varies with time, the feasibility of a set of target SINR values also changes with time. Another simple sufficient condition for the spectral radius of F to be less than 1] is that each column sum is less than 1], i.e. for each j E [1, N] we have
(2/3)
L '"'Ik(gjk/gkk) < 1 .
(5.5)
k:k=/=j Unlike (5.3), the condition (5.5) specifies an explicit coupling between the feasible SINR values of the different users. In summary, we a set of target SINR values for the users is specified by the vector 1. A target vector 1 is feasible if and only if the spectral radius of F is less than one. Alternatively, we can use either (5.3) or (5.5) as the basis for allocating target SINR values 1i to the users. 6. Simulation. The aim of this section is to analyze the effect of a buffer by simulation. We simulate the case of one base station with a buffer that is shared between N TCP users on the downlink. The general setting is that of §4.1.1, with no FEC. The assignment of SINR targets is that of §5: all users having the same SINR target since there is only one base station. We used the hybrid simulator Netscale [7]. More precisely, the simulated dynamics is as follows: as in the mathematical model, each TCP flow is persistent (i.e. always has packets to download); it evolves according to either the slow start or the congestion avoidance phase. In the congestion avoidance phase, it increases its window size W(t) of 1 unit every time
38
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI TABLE 1 Comparison of TCP Formulas with Simulation Results.
TCP Formulas TCP Simulation
Optimal processing gain
Throughput
17 18
155 167
W(t) acks and halves it at each packet loss. Losses occur due to either transmission errors (with probability p as defined in (4.3)) or congestion. In the simulation, if the window size is less than 3 or if several losses occur in the same RTT, the flow may not recover from losses: after some inactive waiting period, a time-out is triggered and the flow restarts in slow-start phase (see [13]). The main difference with the dynamics described above is that congestion losses now stem from the interaction of the N flows via the shared buffer. When one or more flows exceed their transmission capacity C, as defined in (4.1), the shared buffer starts filling in and may eventually overflow, creating congestion losses for these flows and possibly for the other flows as well. In the simulations, we used a size of 200kb for the shared buffer. The minimal value of the RTT is R ==0.5 s. (in the simulation, the RTT increases when the buffer fills in); the packet size is L==2kb and the max window size (not used in the mathematical model but taken into account in the simulation) is of 240 packets. In all cases (see e.g. Figure 5), we again observe a sharp maximum when plotting the long term average TCP rate of one flow in function of the common value chosen for the processing gains of all flows. For N == 2 users, Table 1 gives the optimal processing gains and the corresponding throughput per user (in kbps) as obtained by our mathematical model of Section 4 and by this simulation. Figure 5 plots the UDP and TCP goodput in function of the processing gain in the case with N == 10 users. We observe that in both cases, the optimal gain is slightly larger than what is predicted by theory. This could be explained by the fact that in the simulations, the throughput degradation after losses can be higher, because of time-outs. However our simulations suggest that the presence of a shared buffer does not modify our global conclusions that the maximum TCP throughput is achieved by a precise tuning of the processing gain which is quite different from that for a UDP flow.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 39
1 cell 10 terminals 50 45
UDP goo dput Tep model gOOdpu!
+ /
TC P measured goodput
•
40 35 30
"'
a. -"
25
""
20 15
+ +. +
10 5
a
a
50
100
150
200
processing gain
F IG . 5. N = 10: TCP and UDP goodput as a function of the processing gain by Netscale simulation (in blue) and according to our mathematical model (in green) .
APPENDIX A . Variance of interference. To calculate the variance of the interference, it suffices to show that Pi ,k has variance (2/3)mi(Tc )2. Note that Pi ,k is a zero mean random variab le. Since the statistics of
are identical to that of Pk(t -
aU, we have that E[(Pi,k)2j is
40
FRAN<;OIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
Hence
E[
(l
m iT c
Pi(t)Pk(t _ aUbk(t _ aUdt) 2]
= miE[ = miE[
(l (l
Tc
Pk(t _ at)dt) 2] Tc
Pk(t _ a)dt) 2]
=miE[(aC~l +(TC-a)c~)2] =m i(E[a 2] +E[(Tc-a)2]) == 2miE[a2]
= 2mi(1/Tc)
i
TC
x
2dx
== (2j3)miT~. Therefore, the variance of the interference is
L (2/3)gki mi(T )2Pk. c
k:ki=i
B. Proof of Theorem 1. Let ft(x)be the probability density function for X (t). We wish to examine how the density ft evolves over time, and obtain the steady state density if it exists. For x < Cj2 we have that ft(x)dx is JP>{X(t) E [x, x
+ dx]}
[x - (Lj R 2)dt , x - (Lj R 2)dt + dx]}(l - (pj L)xdt) +JID{X(t-dt) E [2x,2x+2dx]}(pjL)2xdt == ft-dt(X - (Lj R 2)dt)(1 - (pj L)xdt)dx + ft-dt(2x)(pj L)2x2dxdt.
== JID{X(t - dt)
E
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 41
Rewriting this, we have
ft(x)
==
ft-dt(X - (Lj R 2)dt)(1 - (pj L)xdt)
+ ft-dt(2x)(pj L)4xdt
or
ft(x) - ft-dt(X - (Lj R 2 )dt ) ==
-
ft-dt(X - (Lj R 2 )dt )(pj L )xdt
+ft-dt(2x)(pj L )4xdt. Thus,
ft(x) - ft-dt(X) == -
+ ft-dt(X)
- ft-dt(X - (Lj R2)dt) dt ft-dt(X - (Lj R 2)dt)(pj L)x + ft-dt(2x)(pj L )4x.
Letting dt and dx approach zero, we obtain the following equation (A. la Fokker-Planck)
a f~~X)
+ (L/ R 2 ) a ~~x)
= _(p/L)xftCr) + 4(p/ L )xft(2x).
(B.1)
Similarly, for x > Cj2 we have that ft(x)dx is
IfD{X(t)
E
[x,x+dx]} ==IfD{X(t-dt) E [x-(LjR 2)dt,x-(LjR2)dt+dx]} (1 - (pj L )xdt) 2)dt)(1 - (pj L )xdt)dx. == ft-dt(X - (L j R
Rewriting this, we have
ft(x)
==
ft-dt(X - (Lj R 2 )dt )(1 - (pj L)xdt)
or
Thus,
ft(x) - ft-dt(X) + ft-dt(X) - ft-dt(X - (L/R2)dt) dt 2)dt)(p/ L)x. == - ft-dt(X - (L/ R Letting dt and dx approach zero, we obtain
aft(x) + (L/R 2 / ft(X)
at
ax
= -(p/L)xft(x).
(B.2)
We assume that ft(x) ~ f(x) as t ~ 00, i.e. that f is the steady state density of X (t). From the above, setting afa~x) == 0, it follows that f satisfies the differential equation
df(x) {-aXf(X) dx -axf(x)
if C/2 < x < C
+ 4axf(2x)
if 0 ::; x < 0/2
'
(B.3)
42
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
where a == pR 2 / £2, which proves (3.3). For C/2 < x < C, note that a solution to the equation d~~) -axf(x) is given by
f(x) == Vaexp(-ax 2/2)
for x E (C/2,C),
where Va is any constant. It is interesting to note that shape. For (C/4) < x < C/2, we therefore have
f has a Gaussian
d~~) = -axf(x) +4Voaxexp(-4ax 2/2). The solution to this is
f(x) == VI exp( -ax 2 /2) + Va(-4/3) exp( -4ax 2 /2), for x E (C/4,C/2), where VI is any constant. For x E (C/8,C/4), f(x) must therefore satisfy
d~~) = -axf(x) + V14axexp( -4ax 2/2) +Va(-4/3)4xa exp( -16ax 2 /2). A solution to this is
f(x) == V2 exp( -ax 2 /2) + VI (-4/3) exp( -4ax 2 /2) +VO( -4/3)( -4/15) exp( -16ax 2 /2), for x E (C/8,C/4), where V2 is any constant. The general solution can be found by induction to be
f(x)
=
Vnexp(-ax
2/2)
+
t
Vn- 1
[J] (22;~ 1)] exp(-2 2Iax
2/2),
for x E (C /2 n +I , C /2 n ) , which proves (3.5). Next we find the value of the constants Va, VI, V2 , .... Note that ft(C/2 + dx)dx is IP'{X(t) E [C/2, C/2
= JID{ X(t -
+ dx]}
}(1- (p/L)C/2dt) [C - ~2 dt, C - ~2dt + dX] }(1 - (p/ L)Cdt)
dt) E [C/2 -
+JID{ X(t -
dt)
E
~2dt,C/2 - ~2dt + dX]
= ft-dt( C/2 - ~2dt)(1- (p/L)C/2dt)dx + ft-dt ( C -
~2 dt) (1 -
(p/ L )Cdt)dx.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT
Letting dx and dt approach zero, and t
---t
00,
43
we obtain (B.4)
which proves (3.4). This can be used to find a relationship between Va and VI: using (B.4), we have
Va exp( -o:C 2 /8) == VI exp( -o:C 2 /8) + Va(-4/3) exp( -o:C 2 /2) +Va exp( -o:C 2 /2) . Thus,
or equivalently VI == Va(l For n
+ (1/3) exp( -30:C2 /8)), which is equation (3.6).
> 1, ft(C/2 n + dx)dx is
Letting dt approach zero, and t
f((C/2 n ) -
---t
00,
we obtain f((C/2 n )+ )
).
Thus we have
Vn exp (-
=
Vn-1 exp
r
a(~ /2) + ~ v., [J1 (22~~1) ]
exp (-
r/
221a(~ 2)
(-a (~) /2) ~ Vn-l~ + [J1 (22~~ 1)]exp (- 221a(~) /2).
44
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
Therefore we have that Vn exp( -a( ~ )2 /2) is equal to
Vn- 1
[exp(- a(~ r /2) +(4/3) exp (- 4a(~ r /2)]
-t, Vn~l [11 (22;~ 1)] exp (- 22la(~ r /2) ~Vn-l-l [11 (22;~1)] exp( -22la(~r/2)
+
=Vn - 1
[exp( -a(~r/2)+(4/3)exp( -4a(~r/2)]
-t, [11 (22;~ 1)] exp (- 22la(~ r/2) +t, [n (22;~ 1)] exp (- 22(l-1)a(~ r /2) Vn-l
Vn-l
which is equal to
Vn- 1
r/
r
[exp(- a(~ 2)+(4/3) exp (- 4a(~ /2)]
+~ v,.,
[n (22;~ 1)] exp (- 22(l-1)a(~ r/2)
[1+ (22l~1)exp( -(3)22(l-1)a(~r/2)]
.
Thus we have
Vn =
~Vn-l
ll] (22;~ 1)] exp (-
(22(l-1) -1)a(C/2 n)2/2)
[1 +(2 2l~ 1) exp (- (3)22(l-1)a(C/2 n)2/2)] , which is equation (3.7).
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 45
To find the constants {Vn } we will also need the following equation:
1 C
1=
f(x)dx
C
00
= { f(x)dx +
l
:L {
TL
f(x)dx
n=l }C/2 n + 1
}C/2
== Va
C/2
c 2
exp( -ax /2)dx
+
:L l 00
C 2n /
n=l C/2 n +1
C/2
which proves (3.8). The proof of (3.9) is along the same lines.
C. Proof of Theorem 3.2 (Mean TCP throughput). We have
df(x) {-axf(x) dx -axf(x)
< x
(C.l)
where ex == pR 2 / L 2 • The function f is differentiable everywhere but at C /2 where it is differentiable on the right and on the left and with a jump such that:
(C.2) Note that f(x) == 0 for x ~ [0, C]. Let f(u) be the Mellin transform of f(x):
1
00
1(u)
=
f(x)xU-1dx
with u 2: 1. Multiplying both sides of equation (C.l) by w.r.t. x, we get
(C.3) XU
and integrating
f(C-)CU - f((C/2)+)(C/2)U - u {C f(x)xu-1dx }C/2
= -0'
{C f(x)x u+1dx }C/2
(C.4)
46
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
and
(C.5)
Adding (C.4) and (C.5) and using (C.2), we obtain
Note the similarity of equation (C.6) to the well known equation I'(u-} 1) == uf(u), satisfied by the Gamma function. Motivated by this observation, we
now express the unknown function f(·) in terms of a new unknown function g(.) by defining
f(u) Multiplying (C.6) by
2)
u/2
= g(u)r(u/2); (
(C.7)
.
(ir/ 2 ~r(u/2+1)' one gets
g(u) = (1 - 21u ) (\lJ(u)
+ g(u + 2)) ,
(C.8)
with
\lJ(u)
= I(C-) c: (::)U/2 2
1
2
.
f(u/2+1)
For all integers 1 let l
IT (1 - 2-
IIl(u) ==
u
-
2k
) .
k=O
Note that the infinite product II oo (u) is well defined and non zero. The general solution of (C.8) is
g(u) ==
L ITl(U)\lJ(U + 2l) + IIoo(u)h(u), l~O
with h(u) some finite periodic function with period 2. Hence
f(u)
= 1(C-)
2
"'II (u)c u +2l (~)l
~
2
l
(
2)
+I1 oo(u)h(u)f(u/2);
u/2
f(u/2) r(u/2+l+1) .
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 47
Since the density f(x) has its support on [0, CJ, the function f(u) grows at most CU when u tends to 00. The growth of the function
f(C-) ""'IT (u)c u +21(~)l f(u/2) 2 L..-t l 2 f(u/2+l+l) l~O
is easily seen to be at most Cu. So if h(.) is non zero, the order of would be that of
f(u/2)
f (u)
2)u/2 (~
which is a contradiction with the fact that the order of this function is at most CU when u tends to 00. Hence h(u) == 0 necessarily, so that 1(u)
=
f(C-) ""'IT (u)c u+ 21(~)l r(u/2) . 2 L..-t l 2 f(u/2+l+l)
(C.g)
l~O
The constant
f (C-) is determined by the relation
1 = 1(1)
=
f(C-) ""' IT (1)CH21 (~)l f(1/2) . 2 L..-t l 2 f(I/2 + l + 1) l'20
We finally get the following expression for the Mellin transform of interest:
'"
II( )CU+2l(Q)l
1(u) = L.1~O I U '2 '" II (1)Cl+2l (Q) l L.Jl~O l "2
r(u/2)
r(u/2+1+l)
(C.IO)
r(1/2) , r(1/2+l+1)
which proves (3.12). The mean TCP throughput is TCP(C,p) == f(2), which proves (3.13). D. Proof of Corollary 3.1 (Approximation to Mean TCP
throughput). We have
TCP(C,p) == 1(2)
==
3C [1 + ~pR2C2 j L2 + o(pR 2C2 j L 4
2
)]
1+~~pR2C2/£2+o(pR2C2/£2)
(D.1)
pR2C ~ o( R 2C2jL 2)C. L2 256 + P 3
= 3C _
4
Using the Maple software tool, we obtain the following second order expansion _ pR2C ~ f--(2) = 3C 4 L2 256 3
_
p
2R4C5 ~ L4 491520
o( 2R4 C 4 j L 4 )C
+
P
(D )
..2
This suggests using the approximation for the "few losses" case:
1(2) ~ 3C _ pR C ~ 4 L2 256 2
3
.
(D.3)
48
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
E. Proof of Corollary 3.2 (sketch). From Stirling's formula, if n is large,
An (Ae)n
-rv
n!
-
~
1
---
V2nn'
Hence
( An)
log - , n.
r-;»
nlog(A)
+n -
1 1 nlog(n) - -log(n) - -log(27T). 2 2
For A large, the last expression is maximized with respect to n when n satisfies
log(A) -log(n) - -
1
2n
~
0,
i.e., for n close to A. If aC 2 == pR 2C2 / £2 is large, the last observation shows that the dominant term in the numerator of (3.13) is approximately
whereas the dominant term in the denominator is
Hence the ratio tends to 1(2) =
(i_I Il:x>(2)
V~ fi Il
oo(l)
== 1.309 .
JPR/ L
F. Calculation of ~~ and :~. We have
BJ 8e
BJ Be
BJ Bp
= 8C 8e + 8p 8e .
(F.l)
From (3.14), we have 8J R 2 C 3 11 8p ~ -£2256 '
(F.2)
and 8J 3 8C ~ <1 -
R 2C2 33 P£2 256 .
(F.3)
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT
49
Now
(F.4) Next, we have
(_p)
Be _ ~ BO - BO
(F.5)
mTc
2 ) = ( mTc
20
log2 ( 1 - 20) .
(F.6)
We thus have an equation expressing ~: in terms of m and 0, say
(F.7) where the function F I (m, 0) is determined by substitution in the equations above. Next, we have
BJ
-
iim
BJ Be BeBm
BJ Bp Bp Bm
== - - - + - - - .
(F.B)
The quantities g~ and ~~ were given above. We have
Be
am
p
- m 2T
c
(F.9)
·
In order to compute ~ note that
Bp Bm
Bp Bq oqBm·
We have
op ~ ~ [2N[h(O)+O log2(q)+(I-O) log2(I-Q)]] Bq Bq == pL(lj(plog2))(Ojq - (1- O)j(l- q))
= pL(l/ (p log 2)) (qrl -=- qq))
,
(F.10)
(F. 11)
and
~ == __1_e- m "! / 2 {1 om
J27f
V~·
(F.12)
50
FRANQOIS BACCELLI, RENE L. CRUZ, AND ANTONIO NUCCI
We thus have an equation expressing g~ in terms of m and (), say
(F.13) where the function F2 (m, 0) is determined by substitution in the equations above.
7. Conclusion. In this paper we have considered the optimization of wireless channel parameters in order to optimize the throughput of a single TCP connection passing through the channel. We considered the optimization of the transmission energy consumed per bit. We assumed that the SINR at the receiver of the channel is held constant. We considered two regimes - the first where the SINR value is low and where energy per bit is increased by increasing the processing gain, and the second where the SINR value is high and the energy per bit can be decreased by increasing the symbol alphabet size. In both case, we found that the TCP throughput can be fairly sensitive to these parameters, and our results suggest that these parameters should be set carefully and as a function of the system scenario. We have also found that the use of forward error correction, when the coding rate is optimized, can significantly increase TCP throughput. We have also proposed a way to assign SINR values in a network context, where the interaction between users should be taken into account.
Acknowledgments. We would like to thank J. Bolot for his inputs to this line of thoughts as well as D. Hong and L. Fournie for their comments
on the paper and their help on the simulations used in §6. We are also grateful to G. Giannakis for having suggested the idea to apply our ideas, which were initially motivated by CDMA, to adaptive modulation.
REFERENCES [1] F. BACCELLI, B. BLASZCZYSZYN, AND M. KARRAY, "Up and Downlink Admission and Congestion Control and Maximal Load in Large Homogeneous CDMA Networks" ACM MONET, 9(6), Dec. 2004. [2] F. BACCELLI, K.B. KIM, AND D. DE VLEESCHAUWER, "Analysis of the Competition between Wired, DSL and Wireless Users in an Access Network", Proceedings of IEEE INFOCOM'05, March 2005. [3] F. BACCELLI, D.R. McDoNALD, AND J. REYNIER, "A Mean-Field Model for Multiple TCP Connections through a Buffer Implementing RED," Performance
Evaluation, 49: 77-97, 2002. [4] H. BALAKRISHNAN, V.N. PADMANABHAN, S. SESHAN, AND R. H. KATZ, "A comparison of mechanisms for improving TCP performance over wireless links,"
IEEE/ACM Trans. on Networking, 5(6): 756-769, 1997. [5] H. CHASKAR, T.V. LAKSHMAN, AND U. MADHOW, "TCP Over Wireless with Link Level Error Control: Analysis and Design Methodology", IEEE/A CM Trans. Networking, 7(5): 605-615, October 1999. [6] A. GOLDSMITH, Wireless Communications, Cambridge University Press, 2005. [7] D. HONG, Netscale, http://www.n2nsoft.com/. 2005.
WIRELESS CHANNEL PARAMETERS MAXIMIZING TCP THROUGHPUT 51 [8] T.V. LAKSHMAN AND U. MADHOW, "The performance of Tep/IP for networks (9J
[10]
[11]
[12] [13] [14] (15]
with high bandwidth-delay products and random loss," IEEE/ACM Trans. Networking, 5(3): 336-350, June 1997. Q. LIU, S. ZHOU, AND G. GIANNAKIS, "Queuing with Adaptive Modulation and Coding over Wireless Links: Cross-Layer Analysis and Design", IEEE Trans. Wireless Communications, 4(3), May 2005. B. LID, D.L. GOECKEL, AND D. TOWSLEY, "TCP-cognizant adaptive forward error correction in wireless networks," GLOBECOM 2002 - IEEE Global Telecommunications Conference, 21(1): 2139-2144, November 2002. M. MATHIS, J. SEMKE, J. MAHDAVI, AND T. ()TT, "The macroscopic behaviour of the TCP congestion avoidance algorithm," ACM Computer Comm. Review, 27(3): 67-82, July 1997. J .G. PROAKIS, Digital Communications, McGraw-Hill, 3-rd Edition, 1995. W. STEVENS, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. IETF RFC 2001. M. ZORZI AND R.R. RAo, "The effect of correlated errors on the performance of TCP," IEEE Comm. Letter, 1(5): 127-129, 1997. Q. ZHAO, P. COSMAN, AND L. MILSTEIN, "Optimal Allocation of Bandwidth for Source Coding, Channel Coding and Spreading in CDMA Systems", IEEE Transactions on Communications, 52(10): 1797-1808, October 2004.
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS: TOWARDS MODELING HEAVY TAILS AND LONG RANGE DEPENDENCE ROBERT T. BUCHE*, ARKA GHOSHt, VLADAS PIPIRAS+, AND JIM X. ZHANG§
Abstract. Heavy traffic models for wireless queueing systems under short range dependence and light tail assumptions on the data traffic have been studied recently. We outline one such model considered by Buche and Kushner [7]. At the same time, similarly to what happened for wireline networks, the emergence of high capacity applications (multimedia, gaming) and inherent mechanisms (multi-access interference) of wireless networks have led to the growing evidence of long range dependence and heavy tail characteristics in data traffic. Extending heavy traffic methods under these assumptions presents significant challenges. We discuss an approach for extending the methods in [7] under a heavy tail assumption only. The corresponding heavy traffic model is based on (non-Gaussian) stable Levy motion, not Brownian motion which is associated with a light tail assumption. When long range dependence is also present, a promising alternative approach and model based on a Poisson measure representation, motivated from Kurtz [17], are described. The corresponding heavy traffic model is now driven by fractional Brownian motion. As stochastic control analysis for stable Levy motion or fractional Brownian motion is currently undeveloped, the queue limit models characterizing the wireless system can be studied only under given controls, such as stabilizing controls or else heuristic policies. Key words. Wireless queueing networks, heavy traffic method, long range dependence, heavy tails, stable Levy motion, fractional Brownian motion, controls. AMS(MOS) subject classifications. 93E99, 60G18, 60G51, 60G57.
1. Introduction. Heavy traffic methods for wireline queueing systems are well developed (see [21] and the references therein). The basic idea of the heavy traffic method is to simplify the equations for the queueing system dynamics, which has complex stochastics, by looking at the asymptotics which retain much of the structure of the original system. A heavy traffic assumption, loosely speaking, means that the queueing system is operating at near capacity. The asymptotic model of the queueing system under heavy traffic is obtained using weak convergence methods and is expressed as a stochastic differential equation with reflection (SDER). *NC State University, Mathematics Department, Campus Box 8205, Raleigh, NC 27695 (rtbucheeuni t y .ncsu. edu), supported by Intelligent Automation Inc., Rockville, MD, through ARO grant W911NF-04-C-0138. tIowa State University, Statistics Department, 303 Snedecor Hall, Ames, IA 500111210 (apghoshaiast at e . edu). +University of North Carolina, Department of Statistics and OR, Smith Bldg, CB3260, Chapel Hill, NC 27599 (pf.pa raseemai L. unc. edu). §NC State University, Mathematics Department, Campus Box 8205, Raleigh, NC 27695 (j Imxzhangencsu . edu) , supported by Intelligent Automation Inc., Rockville, MD, through ARO grant W911NF-04-C-0138. . 53
54
ROBERT T. BUCHE E1' AL.
Heavy traffic methods for wireless queueing systems have recently been addressed by a few authors. The major difference from the wireline case is the random variations of the wireless medium (the channel variations). In Buche and Kushner [7), a forward-link, one-cell model with a fixed number of queues is considered. The channel process affecting the departure rates is a semi-Markov process. The associated stochastic control problem is to allocate the resource (e.g., power) to the queues where only part of the total power can be allocated; the rest is preassigned to meet a heavy traffic condition (a balance between the mean arrival and mean departure rates). In [32] (see also [31]), a general heavy traffic model is considered under a resource pooling condition, where the channel process is Markovian. Under the resource pooling condition, there is an associated state-space collapse to a one-dimensional workload process. Given a channel state, a collection of service rates is available to choose from and the optimal choice is a MaxWeight discipline that minimizes the system workload. In [1], an SDE model for the queue dynamics with lower and upper reflection boundaries (corresponding to buffer underflow and overflow, respectively) is proposed along with an ergodic control problem to minimize the long-run energy consumption cost and with an overflow (packet drop) constraint. This model allows an explicit solution for the optimal control and is applied to a static channel wireless model. In all of these models, bounded second moment conditions or light tails (LT), and weak or short range dependence (SRD), are imposed leading to Brownian-driven models. Growing empirical evidence and other factors have recently led to a major paradigm shift in various queueing systems from the above assumptions to those of heavy tails (HT) and long range dependence (LRD). This shift has initially occurred in wireline systems [24, 28], and then was followed by similar findings in wireless systems [2, 13, 14, 27]. In particular, there is evidence of HT and LRD in wireless internet traffic due to large file sizes from WWW page downloads and multimedia applications including streaming (music, news clips, movies) and interactive video (e-commerce, gaming). Unlike in wireline systems, LRD can also be explained by the multi-access interference (MAl) in wireless systems [38]. In [37], this effect was heuristically accounted for in a rate control setting (no queueing model). The LRD traffic affects network requirements (e.g. capacity and queue-size) and their design, for example, in planning for the next generation, 4G wireless networks [16]. The main goal of the paper is to discuss initial work toward extending heavy traffic methods and obtaining the limit queue models for wireless systems under HT and LRD assumptions. These are challenging problems with the limit dynamics expected to be driven by stable Levy motion (sLm) or fractional Brownian motion (fErn). Stochastic control theory for these processes is as yet undeveloped, but the queueing model can be used to characterize and make recommendations about the system design. Using the queue limit models, a variety of qualitative and quantitative in-
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
55
formation can be obtained: dimensioning the queues, first passage times, stationary distributions, and others in the spirit of [22, 34]. Extending the methods of [7] to incorporate only HT seems plausible and is discussed in Section §3. The perturbed test function method [19, 23] was used in [7] to show the convergence to the driving Brownian motion and to obtain the limit queue dynamics. This method is based on the wellposedness of the martingale problem (MP) associated with the infinitesimal generator of the limit process. Under HT, we expect the limit process to be sLm which has an infinitesimal generator with an associated well-posed MP. However, in the case of LRD, the limit process is expected to converge to fErn which does not have an associated infinitesimal generator, hence MP. To extend the heavy traffic methods to the case of HT and LRD, referred below simply as the LRD case, we introduce a simplified wireless model in Section §4. In this model, the arrival process is described by the discrete source model [25] where sources turn on according to a Poisson process and stay "On" for a random duration. The HT distribution of the "On" times is used to capture LRD of the data traffic. We employ a general approach of Kurtz [17] to represent the data input and output processes through a convenient Poisson random measure (PRM) on which the heavy traffic analysis can then be based. The discrete source model is closely related to the so-called On/Off model [25, 35] used in [18] for a wireline heavy traffic analysis under LT and SRD assumptions. The weak convergence analysis of [18] sheds light on the PRM approach used in our wireless model. The rest of the paper is organized as follows. In Section §2, the heavy traffic method under LT and SRD assumptions is discussed. In particular, [7] is summarized, highlighting the issues relevant for extension to the cases of HT and LRD. In Section §3, extension of the methods used in [7] to the HT case is considered. In Section §4, we address the extension to the LRD case by using the PRM approach. Glossary of abbreviations. The following abbreviations are used throughout the paper: fBm-fractional Brownian motion HT-heavy tails, heavy-tailed
LT-light tails, light-tailed LRD-long range dependence, long range dependent MAI-multi-access interference MP-martingale problem OMM-orthogonal martingale measure PRM-Poisson random measure SA-stochastic approximation SDER-stochastic differential equation with reflection sLm-stable Levy motion SRD-short range dependence, short range dependent
56
ROBERT T. BUCHE ET AL,
2. Heavy traffic model and stochastic control under light tails (LT) and short range dependence (SRD). We give here a short description of the heavy traffic wireless queueing model of [7], focusing on the aspects of the model needed for the extensionsto the cases of HT and LRD. We consider a one-cell forward-link wireless system with K queues at the base station, each dedicated to a mobile, Data destined for a particular mobile arrives randomly via wireline to the associated queue. The departures from the queue to the mobile is via the wireless medium (channel) whose state is modeled by a Markov or semi-Markov process. The vector channel state is indexed by j E :1; each j specifies the channel for all K mobiles. In particular, we suppose that j specifies ~t(j), i ~ K, an achievable transmission rate/unit power. The actual transmission rate depends on the power applied to a queue and the channel state. We do not impose latency requirements on the data. Interference modeling at the mobiles is not considered in the discussion below. (General interference modeling is discussed in [7] though not the relationship between MAl and LRD considered in [38].)
Heavy traffic analysis. In the heavy traffic method, one considers an embedded sequence of (scaled) queueing systems (Eq. (2.8) below) indexed by scaling parameter n representing the speed of the system in our case. The mean arrival rate and departure rate of the data are O( n). The channel state is given by the process L(nl/t), where 0 < 1/ < 1, so that the rate of channel variations is slower than the rate of arrivals. This is reasonable as the channel coherence times (how long the channel is in a given state) are typically much longer than the service times for packets. The state space scaling is according to the channel process and is given by 1/n T, where , == 1 - 1//2. This "heavy traffic scaling" leads to a driving Brownian motion in the weak limit and is studied below in this section. The departures depend on the power and the design problem is to determine how to allocate power to the queues to meet some performance objective (e.g., keep the queue sizes from becoming too large while maintaining good throughput). The available power is split up into a nominal power Pi (j) to apply to queue i in channel state j and a reserve power Ui(j, x) which is queue state (i.e., x) dependent; the total power applied is Pi (j) + u, (j, x) / n" /2. The nominal power is for balancing the mean arrivals and the reserve power, a small amount subject to control, is used for controlling the stochastic variations. In particular, the mean arrival rate to queue i is equal to
Aia ==.
"\a -b Ai Vi
==
'"""" "\ d ( ') - (.) (') ~ Ai J Pi J 7r J ,
i
< K,
(2.1)
jE.:J
where 7r is the stationary distribution of the channel, ~f is the mean packet is the mean packet size. The system is in heavy traffic in arrival rate, and the sense that the reserve power gives little additional capacity beyond that
vf
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
57
needed to handle the mean arrival rate. Despite that there is little reserve power, its affect on the queueing dynamics is significant in heavy traffic. Applying the heavy traffic scaling with parameter n to the queue balance equations, we obtain (2.2)
Ar
is the cumulative arrival process, where Xi is the (scaled) size of queue i, and is the cumulative departure process. Taking into account Eq. (2.1), the equation (2.2) can be expressed in more detail and a "centered form" as described next. The arrival process Af(t) can be given by either a fluid arrival model or a random arrival model. We will see that these models are equivalent as n ---t 00. For the fluid model, we have
Dr
(2.3) For the random arrival model, the l-th interarrival time for queue i for the n-th system is given by b.~,'ln In. Let nS:,n(t) be the number of packets that have arrived to queue i by time t, and l be the l-th packet size. Then, '
vf
-b
A~(t) == Mr:,n(t) 1.
. 1.
+ -3ib.~n'Y "
«s;: (t) ~
~
b.a,n i,l'
(2.4)
l=l
where
is the scaled variations of the arrival about the mean process. Assume that that the centered and scaled sequence of processes
(2.5) for the interarrival times and packet sizes are tight. This is typically the case in the traditional wireline setting under LT and SRD assumptions and is appropriate here since the data is arriving to the queues via wireline. Note that the state space scaling 1 > 112 used here is "stronger" than the standard 11 scaling for the wireline case. This implies that Mt,n(t) => O. The sum term in Eq. (2.4) is the time t plus an error term en(t) that goes to o as n - t 00. Hence, Eq. (2.3) and Eq. (2.4) are equivalent asymptotically.
vn
58
ROBERT T. BUCHE ET AL.
The departure process is given by
(2.6)
where I{-} is the indicator function and I{xi~(s»O} constrains the queues from being negative. The relation Eq. (2.6) can be rewritten as
Df(t)
= Mid,n(t) -
n v / 2 Aft - Zi(t) +
t I: I{Ln(sl=j}J..f(j)ui(j, xn(s)) ds,
io
jE:!
where
(2.7) and Zi(t) is the reflection process which represents the work that could have been done using the nominal power Pi(·), had the queues not been empty. (We assume that the reflection directions are orthogonal to the faces, so that the so-called completely-S conditions on the reflection process needed in the weak convergence analysis are satisfied. In general, these conditions in the wireless setting are complex [7].) Combining the expressions above and neglecting the error en(t), the prelimit equation is then given by
xr(t) == xr(O)
+ Mt,n(t)
- Mid,n(t) + zr(t)
(2.8)
- t L I{Ln(s)=j}J..1(j)ui(j, xn(s)) ds. io
jE:!
The following theorem is the main result in [7]: THEOREM
2.1.
Under suitable assumptions, Mt,n(.)
=}
0, the zero
process, and
which satisfies
where
ui; (.)
is the i-th component of the Brownian motion w(·)
K}, z, (.) is the reflection process and bi (U, x) == -
L ~t(j)Ui (j, X)1f(j). j
== {Wi (.), i
:::;
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
59
Theorem 2.1 establishes the weak convergence to the controlled reflected diffusion (or SDER) in Eq. (2.9) approximating the actual system. Of main interest in the weak convergence analysis is proving convergence to the driving Brownian motion, which is described next. In Section §3, we consider the weak convergence analysis to sLm under HT assumptions.
Convergence to Brownian motion. To prove Mid,n =} uu, a perturbed test function method used in stochastic approximation (SA) analysis [19, 23) is applied. For the prelimit model given above, the "step-size" of the SA corresponds to a scheduling interval ~ s,n == cn -v which is on the order of the channel coherence time and over which the resource allocations are held constant. In this case, one can write
with ~~l~
L
[I{L(cl)=j} -
n(j)] ~t(j)Pi(j).
(2.10)
j
Set also ~l == (~rl,i :s; K), F~ == a(~l,l < m), E~(·) == E(·IF~) and r~ == L:~m E~~f· The main assumptions needed to show the convergence are:
(AI) There is a matrix I: o such that 1 rn+k-l
lim
n,m,k~oo
(A2) There is a matrix
~l
1
lim
n,m,k~oo
-k
-k
L
E~ (~l[~l]') - I: o ==
o.
l=m
such that rn+k-l
L
E~ (~l [r~l]/) - I: 1 == O.
l=m
These assumptions follow from the assumed bounded departure rates and ergodic properties of the channel process (see [7]). Under these assumptions, one can establish the conditions needed to show tightness and, loosely speaking, convergence of the infinitesimal operator associated with the prelimit process to that associated with the limit Brownian motion (see Section 7.4.3 in [23], for example). In the cases of HT and LRD, we expect convergence to sLm or fBm. In the HT case considered in Section §3, we shall illustrate how the above assumptions can be violated and discuss alternate procedures for showing convergence. The LRD case considered in Section §4 is even more delicate. Stochastic control problem and numerical methods. With the limit Brownian-driven SDER model in Eq. (2.9), one can consider an associated
60
ROBERT T. BUCHE El' AL.
stochastic control problem choosing a cost rate k( x) which penalizes the queue size x. In particular, an infinite horizon cost (x(O) == x)
W(x) =
Ex
LX) e-
f3sk(x(s))
ds,
(3
> 0 and small,
is considered in [7]' with the cost rate k(x) of the form E~l cixfi, c., Pi constants, Pi > 1, with the objective of minimizing the cost over the reserve power u. Given the reflection term in Eq. (2.9), this problem cannot be solved analytically and numerical methods must be used. Preliminary results on this problem can be found in [7, 9]. Since these results are not a focus of the paper, we do not discuss them here.
3. Extension to heavy tails (HT): Convergence to stable Levy motion (sLm). We consider here HT transmissions in the arrival and departure processes and the resulting modifications to the model and methods of Section §2 for showing convergence to the driving process in the limit model. In the HT case, we expect convergence to sLm based on the results in [34] and [25]. We propose carrying out the weak convergence analysis directly in the Skorohod topology and identifying the limit via the infinitesimal generator for sLm and the associated MP. The condition (AI) in Section §2, for example, will not hold in the HT case. To illustrate how (AI) can fail, consider a general multimedia transmission (e.g., movie) model with MPEG encoding. The departure model for this example is different from that considered in Section §2. In particular, in the current example, the data to be transmitted is divided into scenes; different scenes will have different bit-rate requirements depending on the scene content [12]. From [12], the scene size can be Pareto distributed, which is HT. Over a scheduling interval 6.f,n in the scaled system several scenes can be transmitted (since the data rates are O(n) and the channel variations are O(n V ) , 0 < v < 1). We thus assume that ~~l6.;,n, the (centered about the mean) amount transmitted over the l-th scheduling interval for queue i, i ~ K, has HT and hence infinite second moments. Assume also that the channel and scene processes are mutually independent and each are independent over the scheduling intervals {~f,n; l}. Finally, assume that the scheduling intervals are constant: 6.;,n == 6.s,n. Then, the variables ~rl are HT and independent across the time index l. The conditional expectation E~ in (AI) becomes an expectation and ~o cannot be found due to the infinite second moments of ~~l'
3.1. Characterizing sLm: martingale problem (MP). As in the case of LT and SRD in Section §2, the martingale problem (MP) will be used to characterize the desired form of the limit process. The martingale problem for sLm can be formulated as follows. Let D[O, (0) be the space of paths that are right continuous with left-hand limits, and C; denoted the bounded, C 2 functions. Then, given a coordinate mapping process Z (.) E
61
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
D[O, 00), under what conditions does one have existence and uniqueness of a probability measure P on (D[O,oo),Ft == a(Xs,s::; t)) such that (a) P(Zo == zo) == l,and (b) for every
E C~,
f
f(Z(t)) - f(Z(O))
-I
t
£f(Z(s)) ds is a P-Iocal martingale?
(3.1)
In (3.1), L is the infinitesimal generator associated with sLm, given by
£f(x) =
J
[J(x + z) - f(x) -
l{1zl~1} (z)1' (x)z] n(dz),
(3.2)
where
n(dz) =
const
Izll+Q dz
(3.3)
is a Levy measure associated with (symmetric) sLm with index Q. See, for example, [3, 15, 26]. Existence and uniqueness of the solution to the MP gives existence and uniqueness of the corresponding process Z(t). Remark. The above discussion concerns convergence to sLm. For more general queueing limit models, for example, where the arrival and service processes are state dependent, one may need to show convergence to a more general driving process X(t) such as that given by a SDE driven by sLm dX (t)
== a (X (s - )) dZ (t),
(3.4)
where a(·) is some Borel measurable function. In this case, the relationship between unique weak solutions to theSDE (3.4) and the MP problem needs to be considered carefully. Conditions for weak uniqueness of SDE (3.4) need to be considered; some results on existence and uniqueness of SDE driven by sLm can be found in [5, 30, 36].
3.2. Weak convergence to sLm. Wediscuss here the problem of weak convergence of the departure process to sLm, with the details to be carried out in a future work (the arrival process follows analogously). For the HT multimedia model given in the beginning of the section, we consider a similar (centered and scaled) departure process as Mid,n(t) in Eq. (2.10), given by Z1,n(t) in Eq. (3.5). However, there are some differences between Mid,n(t) and Z1,n(t) that are important to point out. A difference is that Mid,n(t) is a scaled sum of centered departures over the scheduling intervals tl;,n, where the tl;,n are on the order of the channel coherence time (how long the channel is in a given state). But for high-speed wireless networks used by multimedia applications, the scheduling intervals can be very small-much smaller' than than the channel coherence time. Consequently, we let z1,n(t) be simply the scaled sum of the centered scene
62
ROBERT T. BUCHE ET AL.
sizes. A second difference is that for Mid,n(t) the rate of transmission is given by >"1 (j)Pi(j); in the multimedia example, the scene sizes ( can influence the power Pi, denoted now by Pi((,j), and canonical rate per unit power, denoted now by Pi((,j). The dependence on (in Pi((,j) can model the choice of a collection of antennas in an antenna array to utilize for transmission. (Transmission strategies incorporating the use of multiple antennas to achieve fast transmission in wireless systems is an area of active research.) An analogue of Mid,n(t) in Eq. (2.10) in the HT case is the following: nSr(t)
zt,n(t) = nIl/a
L
[(~l -
cr] ,
(3.5)
l==l
where (rl, is the size of the l-th scene in queue i, assumed (presently) i.i.d. with mean (r and HT distribution satisfying Q
lim x p((rl
x---+oo
'
> x) == K,
K constant,
(3.6)
and
Sr(t)
=
~ max {m: f~:T:S t},
(3.7)
l==l
where ~:~,n is the service time of the l-th scene in queue i; which depends on the channel state j and scene content (size (). (Do not confuse Eq. (3.5) with the reflection process zf.) Note that the state space scaling for Z1,n(t) is as in [34] and according to the tail distribution of the scene size (see Eq. (3.6)). We now lay down some assumptions leading to a representation of Z1,n(t) as an integral against a martingale measure (Eq. (3.9)). This is the same form as a representation of (unsealed) processes studied in Bass [4] which included the particular case of sLm. We will outline an approach for showing that the scaled processes converges to sLm which seems promising given the similar forms representing the scaled and unsealed processes. Let r~l == L:~: ~ ~:,~' n be the start time for serving the l- th scene; the service time for the l-th scene is ~:,~,n == r~l+l - r~l' Since the service times O(n) are faster than the channel state variations O(n V ) , we can assume that the channel state remains the same for each service interval for a scene. Under this assumption an error is incurred, corresponding to the cases where the channel changes state during the service of a scene, which is asymptotically unimportant. Assume that (rl == z, that is, the l-th scene is of size z, and that the channel state is j for' the duration of serving the scene. In addition, assume that the nominal power applied for the service
z1,n
zt,
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
63
is Pi(Z, j) and the transmission rate per unit power is pr(z, j) == npi(z, j). Then, the duration for the service time is ~~c,n == Z ~,l pr(Z,j)Pi(Z,j)
.
Under this model, the condition analogous to (2.1) is
Af ~ ~fvf
==
JL
Pi(Z,j)Pi(Z,j)7f(j)7fsC(dz),
i::; K,
(3.8)
JEY'
where 7fSC is the distribution for the scene size. There can be great freedom in choosing P and P for meeting the above equality and we assume that we can choose the deterministic functions P and P such that Eq. (3.8) holds and ~ ~cl,n can be modeled as having exponential distribution with parameter , This may seem like a strong assumption but it can be viewed as an assumption on how the scenes are sent to the mobile which should not reflect the heavy tails in the scene content (the details of the scene). It also allows us to consider a tractable Poisson model parallel to the development in [4]. Under the above assumptions, the pairs of (fr, Cr), I == 0, ... are LLd. (in the following we drop the i subscript for notational convenience), where fr corresponds to the jump time of a Poisson process with parameter ,.\ n and have distribution ~n (dz). Define the Poisson random measure on IR+ x IR+ by ~
"\r.
cr
00
J-ln(ds, dz)
==L
6(f[L,([L)
l=l
having the mean measure i/" == And(t)~n(dz), where An == n): Then, Zd,n(t) can be represented as an integral over the martingale measure (J-lnlJn) given by ([4]): t
Zd,n(t) =
1\" r r Z(J.Ln - vn)(ds, dz). n io iIR+
(3.9)
More generally, Zd,n(t) can be a solution to the SDE (3.10)
with the scaled jump size
in the case of Eq. (3.9).
64
ROBERT T. BUCHE ET AL.
By Ito's formula for semimartingales and using the fact that (j1 n is a martingale measure, one can obtain [4] that, for f E C 2 ,
-
vn )
is a martingale, where
c: f(x)
=
Fn(z)
=
J
[f(x
+ Fn(z))
- f(x) - f'(x)Fn(z)] >.nC(dz),
n:/o.·
In other words, the prelimit process Zd,n(t) has the "infinitesimal generator" E": Note that for an a-stable Levy motion, its infinitesimal generator c is given by Eqs. (3.2)-(3.3). In analogy to the Brownian case, we plan to study the convergence of Zd,n to sLm Zd through the convergence of \.en fn(Zd,n(t)) - .ef(Zd,n(t))I--4 0 (in a suitable sense) and Ifn - fl--4 0 (fn is a "perturbation" of f), as in the perturbed test function method. Although this approach for showing weak convergence still needs to be developed, it seems to be a direct approach and may be useful when considering more complex models in a control analysis, for example, when the reserve power u affects the driving process through Zd,n(t-) in Eq. (3.10).
4. Incorporating long range dependence (LRD): Poisson random measure (PRM) approach and convergence to fractional Brownian motion (fBm). In this section, we consider extensions of the heavy traffic analysis to the LRD case. We start with some motivation (Subsection §4.1). In Subsection §4.2, we discuss a related model in the LT and SRD case with a focus on the methods for showing the tightness conditions needed in the weak convergence analysis. This is often the most difficult aspect of the weak convergence analysis. The methods for showing tightness in the LRD case are more complex and it is useful to compare them against those used in the LT and SRD case. In Subsection §4.3, we the consider heavy traffic analysis of a simple wireless model with LRD.
4.1. Motivation. To capture LRD, the related On/Off and infinite source Poisson (also called discrete source) models are often used, for example, in [17, 24, 25], and their large scale analysis naturally involves fErn as the driving process. Both [17] and [25] use a Poisson random measure (PRM) approach to obtain fErn though the approach in [17] is more general as the inputs can be stochastic processes. As fErn is not a semimartingale and does not have an infinitesimal generator or the associated martingale problem, the methods used in the SRD case cannot be applied any longer. In the PRM approach, as in our model in Subsection §4.3, the arrival and departure processes are conveniently represented in terms of an integral
65
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
against a PRM. This helps in showing tightness of the processes by using the properties of orthogonal martingale measures (OMM) which are obtained from the centering and scaling of the PRMs in the heavy traffic analysis. These properties come from stochastic calculus for semimartingales even though the limiting fBm is not a semimartingale.
4.2. Related heavy traffic result for an exponential On/Off model - the case of LT and SRD. A heavy traffic model for an exponential On/Off source model input leading to a Brownian limit model can be found in Kushner and Martins [18]. We outline here the tightness analysis of [18] so that it could be compared to that based on the PRM approach. In [18], the arrival process is the superposition of N independent On/Off sources where the "On" times are exponentially distributed with parameter A and the "Off" times are exponentially distributed with parameter u: When the source is on, the input is according to a Poisson process with rate v. The departures are modeled as a sequence of service times {~~, k == 1,2, ... } which are i.i.d. and independent of the arrival process. Because of the independence assumption between arrivals and departures, the weak convergence analysis for the queueing system can focus separately on the arrival and departure processes. We will focus on the arrival process. The arrival process in [18] can be described by {Yi(·), i == 1, , N}, an indicator function for the source i being "On" and {ai(.), i == 1, , N}, giving the arrivals which are Poisson with rate v. The arrival process has a martingale decomposition given by ((3.1) in [18])
+ A(1 - Yi(t))] dt + dfJi(t), da,(t) == VYi (t) dt + dii, (t), dYi(t) == [J-lYi(t)
(4.1)
where Yi(·) and ai(·) are Ff-martingales and Ff == a({Yi(s),ai(s);s S t, i ::; N}). Part of the centered and scaled (by 1/JF/) arrival process needed in the heavy traffic method is described by centering and scaling L~l Yi(t). Denote this centered and scaled process ZN (t). It turns out (Theorem 3, [18]) that the weak limit of Z N, as N -+ 00, is governed by the linear SDE
dZ(t) == - (A
+ J-l)Z(t) dt + dW (t),
(4.2)
which can be seen from the form of the prelimit (obtained from (4.1))
ZN (tN
+ t) == e-(A+J-1)t ZN (tN) +
t:
e-(A+J-l)(tN+t-s)dZ N (s),
(4.3)
tN
where ZN ( t) == 1/JF/ L~ 1 Yi (t) corresponds to the Wiener process in the limit (4.2). In order to show the weak convergence of {Z N (t N + .), N < oo}, the following tightness result of Kurtz ([10], Chap. 3, Theorem 8.6, p. 138 and
66
ROBERT T. BUCHE Err AL.
[18], p. 1102) is used: the sequence of processes {X n ( . ) ; n 2 I} with paths in D[O, (0) is tight if (i) the collection of random variables {Xn(t); n 2 I}, is tight for each t E V, V a dense set of [0, (0), and (ii) for each T 2 0, lim lim sup sup E[min{l, IXn(T +~) - Xn(T)I}] == 0, Ll-+O
n-+oo
T~T
(4.4)
where the sup is over all stopping times T ~ T. Part (ii) follows here from the special forms in Eq. (4.1) and Eq. (4.3) of the above processes by showing ((3.7) in [18]) that
E
[CZN(tN + e+.6.)
- ZN (tN + ()))2] = 0(.6.),
E [(ZN (tN + () +.6.) - ZN (tN + ()))2]
:s 2.6.E IZ N (tN)1
2
+ 0(.6.).
For part (i), tightness of {Z N ( t); N ~ I}, each t E V, follows from stochastic stability techniques in [19] (Theorem 2 in [18] and is applied in a stochastic approximation rate of convergence analysis in [6]). The method relies on showing a supermartingale property for a Liapunov function (V(x) == x 2 in this case). Showing tightness of the arrival process is completed by showing tightness of AN (t) == I/VNE~l iii(t). This is done by applying the techniques used for showing tightness of ZN ( .). Due to the general arrival process, [17] can no longer use the expressions of the form Eq. (4.1) and Eq. (4.3). As the result, the techniques used for showing tightness (parts (i) and (ii)) above) are more complex in [17].
4.3. PRM approach and application: wireless model. We discuss here the PR:NI approach applied to a simple wireless model in heavy traffic. The details of the heavy traffic analysis will be part of a future work. Model and PRM representations. In Fig. 1, we consider a simplified wireless model that allows us to use the mathematical approach motivated from Kurtz [17] in obtaining limit models of the queue dynamics under HT and LRD. We suppose that each mobile user is requesting one type of files, say multiple WWW-pages. Requests are made at times Sk' k 2 1, which are the arrival times of a Poisson process with a constant intensity Aa. The file sizes are W k , k 2 1, which are assumed to come from an HT distribution. Once a request is made, the server starts sending these WWW-files in the form of packets immediately to the tower through wireline at the rate 1. The data input or rate process X in Kurtz's [17] description is then Xk(s) == s. The files are transmitted to the tower in times T k == Wk , k ~ 1. The resulting arrival process is an infinite source Poisson arrival model. Observe that the total amount of data aggregated until time t over all documents being transmitted simultaneously to the tower is
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
67
www
• ••
• •• (t
aggl'=U (t)
~ ;'.
~
r
("
,
\
,
'
8
FIG. 1. Wireless model.
Ua(t) =
it
=
r
XN(s) (TN(S) /\ (t - s)) dN(s) (4.5)
(r /\ (t - s)) ea(ds X dr),
J(O,tjX'R.+
where N is the Poisson process corresponding to the jumps Sk' k 2: 1, and ~a = L:~o 8(Sk,r!:) is a PRM on IR+ x IR+ with the mean measure ).,am X va (here, m is the Lebesgue measure and va is the distribution of sizes W k = Tk)' The PRM representation which was key in the weak convergence arguments used by Kurtz [17]' plays a fundamental role here as well.
Remark. More general models can be handled where the WWW-file input rate is random. This would be appropriate for the case where these files are sent to the tower through a wireless medium. In this case, XN(s) in Eq. (4.5) would be a general random processes. On the departure side of the tower (transmission from tower to mobile), let S~ , k 2: 1, be the starting times of the transmission of the k-th document. Suppose that S~ = SI:, k 2: 1, that is, the transmission from the tower to a mobile starts as soon as the mobile makes a request. This may seem as an oversimplification. However, we assume that the amount of the document that can be sent from the tower to the mobile depends on how much of the document is received by the tower from the server at
68
ROBERT T. BUCHE ET AL.
any given time. This is reflected in the rate function X~ for departures as described below. Let p(t) denote the total power applied to the data at the tower for transmissions to the mobiles, C(t) denote the channel process modeling the wireless medium, and r (C (t)) denote the departure rate per unit power. Observe that
d(s) =
is
p(v)f(C(v))dv,
is the departure process if the tower transmits documents continuously to the mobile (note that, this may not happen because there may not be packets available at the tower to transmit to the mobile at some time points - leading to idleness at the tower). Since sg == Sf;, the queue-length at the tower at time s from the start of transmission is ,(s - d(s)) for all s ~O, where ,(x(t)) == x(t) - infs~t x(s) is the Skorohod map. This leads to the departure rate process
xt(s) == s - ,(s - d(s)). The first term on the right side is for the arrivals at the tower (at the constant deterministic rate of 1). On the departure side, the time to transmit the kth document from and the the tower to a mobile will depend both on the departure rate size of the document Wk as T~ == inft~o{X~(t) ==.Wk } . Consider now the PRM ~d == L~=o 8(S~,xt,rt) on IR+ x D(IR+,IR+) x IR+ with the mean measure Aam X u", where v d is the joint measure, according to the distribution J.-l on E ~ D(IR+, IR+) x IR+, of each element of the i.i.d. sequence (X~, T~). Then, the controlled departure process is
Tt
Ud(t) =
=
it x~(s) (T~(S) r
A (t
x»
- s)) dN(s) (4.6)
u(rA(t-s))e(dsxduxdr).
J(O,t] x D(IR+,IR+)xIR+
This gives the queue equation at the tower as
Note that there are no reflection terms in the queue equation, since it is The key in absorbed in the definition of the departure rate function the above representation is that Q is expressed in terms of a PRM. This structure is exploited for carrying out the weak convergence analysis and identifying the limit process.
x».
Heavy traffic method and weak convergence. Turning to the discussion of the heavy traffic analysis, we first discuss the case when W k are not
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
69
HT and which does not involve LRD in order to illustrate the weak convergence analysis using the PRM approach. We then discuss the extensions to the LRD case along with important extensions of the model. From the representation in Eq. (4.5), we have E[Ua(t)] == at, where
(4.7) Similarly, from (4.6), E[Ud(t)] == f3t, where
f3
a
= A
1
(4.8)
u(r)fL(du x dr).
The heavy traffic method considers a sequence of embedded systems indexed by the scaling parameter n. At the n-th embedded system, we assume that the arrival (hence the departure) process is turned on by a Poisson process with rate ti). a, and for the departure process we assume that the i.i.d. pair (X~,n, T:,n) has the distribution J1n on E. This scaling then yields a corresponding change on an and f3n in Eq. (4.7) and Eq. (4.8), respectively, for the n-th system. A heavy traffic limit for such a model involves the assumption that under the above rescaling of network measurements, the scaled arrival and departure rates are asymptotically the same. In particular, given the above assumptions and scaling, the n-th embedded queue is then
Qn(t) = ua,n(t) - Qnt _ Ud,n(t) - f3n t + Qnt - f3n t
vn
vn
vn
vn'
The heavy traffic assumption is simply
. an - f3n Iim r: ==
n---+oo
yn
C,
(4.9)
where C is some constant. We now consider the (weak) limits of the scaled and centered processes ((ua,n (t) - ant) / JTi, (Ud,n(t) - f3nt) / JTi). We focus on the departure process, since the arrival process can be viewed as a special case in that the "workload" has a constant instead of random rate. Observe that
Vn(t)
=
Ud,n(t) - f3 t JTi n = n
1
u(r /\ (t - s))3 n(ds x du x dr)
(O,t) x£
Ivn,
where 3 n(A) ~ (~~(A) - A~m x lJ~(A)) for A c IR+ x E. Under the assumption that the jump process for the cumulative number of sources turned "On" has constant intensity, 3 n is an orthogonal martingale measure (OMM).
70
ROBERT T. BUCHE ET AL.
The collection of random processes {V n (.); n} (dropping the "d" dependence in the superscripts for notational simplicity) is tight if the collection of random variables {Vn(t); n ~ I}, each t E V, is tight (as in part (i) of (4.4)) and
E[(Vn(t
+ h) -
V n(t))2(Vn(t) - Vn(t - h))2] :::; CTh(},
(4.10)
for some Cr > 0, f) > 1,0 < h < 1 and h :::; t :S T. The condition (4.10) is equivalent to that in (4.4) (see [10]' Chap. 3, Theorems 8.8 and 8.6). With the process now represented as an integral against an orthogonal martingale measure, the evaluation involving the increments of the process in the lefthand side of the inequality in (4.10) depends on the discontinuities in the process given by the OMM. In particular, the calculation uses the quadratic variations 17i(A)t for the process
L[3 n (A, s) - 3 n (A, s-)]l,
l > 2,
s"S.t
for arbitrary set A E B(E), the Borel sigma algebra generated by the sets in E. For (4.10) to hold, one needs (3.8) and (3.9) in Kurtz [17] to hold which are conditions on the powers of the increments of the workload output processes. To show that {Vn(t); n ~ I}, each t E V, is tight, the stochastic stability results are not applied as in [18). Instead, this follows from conditions on the workload output process assuring a central limit theorem for triangular arrays which are given in (3.6) and (3.7) in Kurtz [17]. The weak convergence analysis establishes the weak convergence of V n ( . ) in the Skorohod topology on D(IR+,IR+) to V(·) where, for t2 > t 1 > 0, V(h, t2)~
r.
(u(r!\ (t2 - s)) - u(r!\ (tl - s))) W(ds x du x dr),
J(O,t)X£
W is Gaussian noise on (0,00) x E corresponding to m x ~ and ~ depends on the scalings used in the prelimit and is associated with the variance of V(tl, t2), described next. In particular, for the weak convergence analysis, one assumes that
· 1un
-2 \ n an AnY
C
==~,
(4.11 )
n~oo
where an is the state-space scaling (1/ Vii in the current example) with the convergence in a "somewhat vague" topology on M (E), the set of measures on E [17]. It follows that the variance of V(tl, t2) is E (V(tl' t2)2] =
r
J(O,t)X£
(u(r
!\
(t2 - s)) - u(r !\ (t 1 - s)))2 ds~(du x dr).
The An, i/" in Eq. (4.11) can depend on the n-th embedded system in a "multiplicative" way (sometimes called a single system). In particular, we
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
71
let An == n). and t/" == u. The physical interpretation for the above assumptions is: for the n-th embedded system the rate of sources activations is increasing linearly with n and the pair of workload and duration of service time is distributed according to the same u. Under such scaling assumptions on A and u, it is immediate that Eq. (4.11) holds where the limiting ~ is simply Av. For the arrival process, the analogous procedure gives
Wn(t) =
vnn
ua,n(t) -
Q
t n =
1
(r 1\ (t - s))3 n(ds x dr),
(O,t)xIR+
where now 3 n(A) ~ (~~(A) - A~m x v~(A)) Ivn, for A C lR+ X lR+. The weak convergence analysis is expected to yield that W n (.) weakly converges (in the Skorohod topology on D(IR+, IR+)) to W (.) where
W(tl t2) = 1
r
(r
1\
(t2 - s) - r
1\
(tl - s))W(ds x dr),
J(O,t)XR+
and W is Gaussian noise on lR+ x lR+ corresponding to m x Aa t/' .
Convergence to mm. Continuing our example with constant rate 1 input to the tower, suppose that the durations T k == W k are HT as lim r!3-1 P{Tk > r} == c, r~oo
2 < {3 < 3. The HT inputs lead to LRD in the input process [25]. This leads to new scalings in the weak convergence analysis dependent on (3, in particular, we can have that ~ in Eq. (4.11) is given by
see [17]. One obtains the weak limit va ('), represented as an integral against a Gaussian random measure, similar to the example above. The limit process is identified as fErn through direct calculation of the variance and using the fact that fErn, denoted B H ('), is a unique zero mean process, with stationary Gaussian increments and variance EB1-I(t) == a 2 t 2 H , a > 0,1/2 < H < 1, where H is the Hurst parameter [11]. There is much flexibility in the scaling through component scalings on the source rate for the "On" -times and the data input process which includes a separate scaling on the input duration. The particular choice of scaling is part of our future research.
Extensions of the model. The model in Fig. 1 can naturally be extended to more detailed modeling cases. In particular, the intensity Aa can depend on the time of day, reflecting the diurnal variations in measured data. The intensity can also depend on the number of active downloads at time t which is derived from N(s) and TN(s): the user is less likely to request
72
ROBERT T . BUCHE ET AL .
www
Outu t1
IISf l'
2
FIG. 2. Wire less m odel with power cont rol.
another download at time t if several are occurring at time t. One could also try to incorporate the LRD model for the multi-access interference in [381. Under this interference modeling , the retransmission of packets to th e mobile will have affects on th e departure modeling. It is very natural to consider extending the power p(.) to depend on the queue state Q(.) and the channel st ate C(·). On one hand, one wishes to have "fair" controls, balancing the queue size and, on the other hand, one wishes for good throughput, taking advantage of th e best channel condition without regard to the queue state. Controlling only for maximum throughput can lead to unfair policies. Furthermore, unlimited power is not available , so th ere is a power constraint - the total power applied at a given time has to be ~ P, a maximum amount available for use. A general set-up for th e power control problem is shown in Fig. 2. Since the stochastic optimal control problems are hard for the limit forms of Q(.), which includes fEm and sLm components, one could consider an a priori st ructure on the cont rol policies, such as threshold controls on the queue size for given chann el conditi on, etc . One could also consider a multiclass cases
HEAVY TRAFFIC METHODS IN WIRELESS SYSTEMS
73
of the above with both WWW and multimedia (movie) sources, where the multimedia has latency requirements.
REFERENCES [1] B. ATA, .I.M. HARRISON, AND L.A. SHEPP, Drift Rate Control of a Brownian Processing System, The Annals of Applied Probability, 15(2): 1145-1160, 2005. [2] D.R. BASGEET, J. IRVINE, A. NluNRO, P. DUGENIE, D. KALESHI, AND O. LAZARO, Impact of Mobility on Aggregate Traffic in Mobile Multimedia System, The 5th International Symposium on Wireless Personal Multimedia Communications (IEEE), 2: 333-337, Oct. 2002. [3] R.F. BASS, Uniqueness in Law for Pure Jump Markov Processes, Probability Theoryand Related Fields, 79: 271-287, 1988. [4) R.F. BASS, Stochastic differential equations with jumps, Probability Surveys,1: 1-19, 2004. [5] R.F. BASS, K. BURDZY, AND Z.Q. CHEN, Stochastic differential equations driven by stable processes for which pathwise uniqueness fails, Stochastic Processes and their Applications, 111(1): 1-15, 2004. [6] R. BUCHE AND H ..I. KUSHNER, Rate of convergence for constrained stochastic approximation algorithms, SIAM Journal on Control and Optimization, 40: 1011-1041, 2001. [7] R. BUCHE AND H ..I. KUSHNER, Control of Mobile Communications With TimeVarying Channels in Heavy Traffic, IEEE Transactions on Automatic Control, 47(6): 992-1003, 2002. [8] R. BUCHE AND H ..J. KUSHNER, Control of Mobile Communication Systems With Time- Varying Channels via Stability Methods, IEEE Transactions on Automatic Control, 49(11): 1954-1962, 2004. [9] R.T. BUCHE AND C. LIN, Heavy traffic control policies for wireless systems with time-varying channels, Proceedings, American Control Conference, 6: 39723974, 2005. [10] S.N. ETHIER AND T.G. KURTZ, Markov Processes: Characterization and Convergence, Wiley, New York, 1986. [11] P. EMBRECHTS AND M. MAEJIMA, Selfsimilar Processes, Princeton University Press, 2002. [12] M. IZQUIERDO AND D.S. REEVES, A survey of statistical source models for variablebit-rate compressed video, Multimedia Systems, 7: 199-21~, 1999. [13] M. JIANG, M. NIKOLIC, S. HARDY, AND L. TRAJKOVIC, Impact of self-similarity on wireless data network performance, IEEE International Conference on Communications, 2: 477-481, 2001. [14] R. KALDEN AND S. IBRAHIM, Searching for self-similarity in GPRS, Proceedings of the 5th annual Passive and Active Measurement Workshop (PAM 2004), Antibes Juan-les-Pins, France, April 19-20, 2004. [15] T. KOMATSU, On the martingale problem for generators if stable processes with perturbations, Osaka J. of Mathematics, 21(1): 113-132, 2004. [16] A. KRENDZEL, Y. KOUCHERYAVY, .1. HARJU, AND S. LOPATIN, Network Planning Problems in 3G/4G Wireless Systems, The 1st COST 290 Management Committee Meeting,Malta, Oct. 2004. [17] T. G. KURTZ, Limit Theorems for workload input models, Stochastic Neworks: Theory and Applications, Eds. F.P. Kelly, S. Zhachery & 1. Ziedins, Oxford, 1996, pp. 119-139. [18] H.J. KUSHNER AND L.F. MARTINS, Heavy Traffic Analysis of a Data Transmission System with many Independent Sources, SIAM J. on Appl, Math., 53(4): 1095-1122.
74
ROBERT T. BUCHE ET AL.
[19] H.J. KUSHNER, Approximation and Weak Convergence Methods for Random Processes, MIT Press, 1984. [20] H.J. KUSHNER AND P. DUPUIS, Numerical Methods for Stochastic Control Problems in Continuous Time, Second Edition, Springer, New York, 2001. [21] H.J. KUSHNER, Heavy Traffic Analysis of Controlled Queueing and Communication Networks, Springer, 2002. [22] H.J. KUSHNER, J. YANG, AND D. JARVIS, "Controlled and optimally controlled multiplexing systems: A numerical exploration", Queueing Systems, 20: 255291, 1995. [23] H.J. KUSHNER AND G. YIN, Stochastic approximation and recursive algorithms and applications, second edition, Springer, New York, 2003. [24] W.E. LELAND, M.S. TAQQU, W. WILLINGER, AND D.V. WILSON, On the selfsimilar nature of Ethernet traffic, IEEE/ACM Transactions on Networking, 2(1): 1-15, 1994. [25] T. MIKOSCH, S. RESNICK, H. ROOTZEN, AND A. STEGEMAN, Is Network Traffic Approximated by Stable Levy Motion or Fractional Brownian Motion?, The Annals of Applied Probability, 12 (1): 23-68, 2002. [26] R. MIKULEVICIUS AND H. PRAGARAUSKAS, On the martingale problem associated with nondegenerate Levy operators, Lithuanian Mathematical Journal, 31 (3): 297-311, 1992. [27] R. NARASIMHA AND R. RAO, Modeling Variable Bit Rate Video On Wired and Wireless Networks Using Discrete- Time Self-Similar Systems, Proceedings, IEEE International Conference on Personal Wireless Communications, pp. 290-294, 2002. [28] K. PARK AND W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation, J. Wiley & Sons, Inc., New York, 2000. [29] V. PIPIRAS AND M. TAQQU, Integration questions related to fractional Brownian motion, Probability Theory and Related Fields, 118: 251-291, 2000. [30] H. PRAGARAUSKAS AND P.A. ZANZOTTO, On one-dimensional stochastic differential equations driven by stable processes, Lithuanian Mathematical Journal, 40 (3): 277-295, 2000. [31] S. SHAKKOTTAI, R. SRIKANT, AND A. STOYLAR,Pathwise optimality of the exponential rule for wireless channels, Advances in Applied Probability, 36 (4): 1021-1045, 2004. [32] A.L. STOLYAR, !vfax Weight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic, The Annals of Applied Probability, 14(1): 1-53, February 2004. [33J D. STROOCK, Diffusion processes associated with Levy generators, Z. Warscheinlichkeitstheorie verw. Gebiete, 32: 209-244, 1975. [34] W. WHITT, An overview of Brownian and non-Brownian FCLTs for the singleserver queue, Queueing Systems, 36: 39-70, 2000. [35] W. WILLINGER, M.S. TAQQU, R. SHERMAN, AND D.V. WILSON, Self-similarity through high-variability: Statistical analysis of ethernet LAN traffic at the source level, IEEE/ ACM Trans. Networking, 5(1): 71-86, Feb. 1997. [36] P .A. ZANZOTTO, On stochastic differential equations driven by a Cauchy process and other stable Levy motions, The Annals of Probability, 30(2): 802-825, 2002. [37] .1. ZHANG, M. Hu, AND N.B. SHROFF, Bursty Data Over CDMA: MAl Self Similarity, Rate Control, and Admission Control, Proceedings, IEEE INFOCOM, 1: 391-399, 2002. [38] J. ZHANG AND T. KONSTANTOPOULOS, Multiple-Access Interference Processes Are Self-Similar in Multimedia CDMA Cellular Networks, IEEE Transactions on Information Theory, 51(3): 1024-1038, 2005. [39] J.A. ZHAO, B. LI, C.W. KOK, AND I. AHMAD, MPEG-4 Video Transmission over Wireless Networks: A Link Level Performance Study, Wireless Networks, 10: 133-146, 2004.
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING OVER DYNAMICAL FADING CHANNELS: A CONSTRAINED MARKOV DECISION PROCESS APPROACH DEJAN V. DJONIN* AND VIKRAM KRISHNAMURTHyt Abstract. The problem of transmission scheduling over a correlated time-varying wireless channel is formulated as a Constrained Markov Decision Process. The model includes a transmission buffer and finite state Markov model for time-varying radio channel and incoming traffic. The resulting cross-layer optimization problem is formulated to minimize the transmission cost under the constraint on a buffer cost such as the transmission delay. Under the assumptions on submodularity and convexity of the cost function it is shown that the optimal randomized policy is monotonically increasing with the increase of the buffer state. Furthermore, the influence of the channel and traffic correlation matrices on the optimal transmission cost is investigated. It is shown that comparison between optimal transmission costs of two different channels can be performed by considering the stochastic dominance relation of their conditional probability distributions. As an example of this result, channels with smaller scattering and the same mean can achieve smaller average transmission cost for the same average buffer cost. Key words. Value function, scheduling, optimal policy, Markov Decision process, correlated sources, correlated channels, transmission scheduling, supermodularity, stochastic dominance, latency, adaptive modulation. AMS(MOS) subject classifications. 93E20.
Primary 94A05, 94A14, 90B18, 90B36,
1. Introduction. Consider the uplink transmission problem comprising of a single user with Markovian traffic arrival, finite buffer and Markovian fading channel. In this paper we derive structural results and a computationally efficient algorithm for the uplink transmission scheduling policy that optimizes a transmission cost, such as power cost subject to a delay constraint. Several wireless standards such as EDGE, IS-856, 802.11a,b and g, WCDMA and 1xEVDo provide a framework for transmission scheduling based on the channel state. Several recent papers have studied resource allocation adaptation for transmission over time-varying fading channels under constraints on the transmission delay [2], [9], [14] [10], [12], [3] and [13]. All of these papers formulate the problem of finding the optimal policies as an unconstrained Markov Decision Process (MDP) and use dynamic programming methods *Department of Electrical Engineering, University of British Columbia, Vancouver, BC, Canada. The work of the first author was supported in part by NSERC PostDoctoral Fellowship. t Department of Electrical Engineering, University of British Columbia, Vancouver, BC, Canada. The work of the second author was supported in part by NSERC strategic grant. 75
76
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
to compute optimal transmission policies. The structure of optimal deterministic rate adaptation policies for non-correlated channels have been analyzed in [12]. In comparison to the above papers, here we present the transmission scheduling problem as a constrained MDP (CMDP) where the global constraints in the CMDP take into account the limitations on the transmission latency. The following two modeling assumptions are employed in our analysis. First, the packet arrivals and channel variation are modeled as a discrete time finite state Markov chain. Transmission scheduler decisions are made at discrete time instants. Restricting the analysis to discrete time finite state processes avoids the technicalities and complexities associated with semi-Markov decision processes which seldom lead to practical algorithms. The discrete time Markov chain assumption on the channel variation implies that the channel is block fading, which is the model used by many authors. Second, it is assumed that channel state is exactly known (or fully observed) and also that the incoming traffic state is exactly known.
1.1. Main results. In order to establish our structural results on the optimal transmission policies, we combine three tools: Lagrangian dynamic programming approach to constrained MDPs [1], supermodularity [23) and sensitivity of MDPs to transition probabilities (15). The first step in this paper is the formulation of the generic rate adaptive transmission scheduling problem as an average cost infinite horizon CMDP. Under suitable regularity conditions, a stationary optimal policy exists. For the unconstrained case or with local constraints only, this stationary policy is pure, i.e., the optimal action is a deterministic function of the state, and the problem can easily be solved via stochastic dynamic programming methods. However for a CMDP (with global constraints), the optimal scheduling policy in general is randomized, i.e., the optimal action at a given time instant is a probabilistic function of the current state and stochastic dynamic programming methods cannot be applied directly to solve for the optimal policy. An infinite horizon average cost CMDP can be formulated as a linear programming problem, and the optimal policy (possibly randomized) of the CMDPs can be obtained by solving this LP. However, in this paper we are interested in deriving structural results on the optimal transmission scheduling policies and not simply solving a CMDP for the optimal policy. Structural results such as supermodularity [23] have been developed for MDPs using the stochastic dynamic programming formulation. In order to exploit these structural results for a CMDP, we need to reformulate the CMDP as a MDP with Lagrangian costs. Therefore, we employ the results from [1] to establish the equivalence in optimal average costs between CMDP and unconstrained MDP with Lagrangian instantaneous costs. Further details are given in Section 3.2. Our second result is the use of supermodular properties on a lattice, developed in [23], to establish several structural results on the nature of
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 77
the optimal transmission policy as a function of the buffer state. For an active constraint on the buffer cost (e.g. latency), it is shown that the optimal transmission policy is a pure policy. A novel result of Theorem 3.1 states that if the Lagrangian cost function of this model satisfies certain supermodularity and convexity properties, then the optimal pure scheduling policies are monotonically non-decreasing in the buffer occupancy. This means that irrespective of the current channel and source states as well as the transition probabilities that describe channel and source Markov chains, the optimal transmission scheduler will take more packets from the buffer as the buffer occupancy increases. This has practical implications for deriving computationally efficient policy search algorithms (such as policy iteration [17]) as the search space for the optimal policy can be significantly red uced to a subset of non-decreasing policies in the buffer size. In particular, for only two rate adaptation policies, our structural results imply that for each traffic and channel state, the scheduling policies will be threshold policies in buffer component of the state variable. A threshold policy takes the same action for state variable less than a fixed threshold and takes a different action for state variable greater or equal than that threshold. In Theorem 3.2 of Section 3.3 we also give the piece-wise linear characterization of the dependence of the optimal transmission cost with respect to the buffer cost constraint. For a general constraint we demonstrate that optimal randomized policies are probabilistic mixture of two pure monotone non-decreasing policies and present a computationally efficient algorithm to compute these mixed policies. Our final result explores the influence of the structure of the transition probability matrix of Markovian channel on the optimal transmission policy subject to a delay (latency) constraint. "VVe present a method utilizing stochastic ordering to compare two Markovian channels based on their transition probability matrices. In Section 3.5 and Theorem 3.3 establish two results that can determine the influence of channel correlations on the optimal cost with a single active constraint. As an illustration to these results, we prove that wireless channels with smaller scattering, same mean and the same latency constraint would have less transmission costs (such as power consumption) when optimal scheduling is applied. Another example is the maximum ratio combining and the favorable influence of adding new diversity branches on the optimal transmission cost. Our results exploit the influence of the transition probability matrices on the value function of a Markov Decision process considered in [15]. The outline of the remainder of the paper is as follows. In Section 2 we pose the problem of the choice of the optimal adaptive transmission policies for a generic transmission model as a CMDP and define all the ingredients that constitute it. A practical communication example that can fit into this model is given in Section 2.4. Results on the monotonic increasing structure of the optimal pure and randomized policies are given in Section 3.2. The dependance of the optimal cost on the constraint is
78
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
discussed in Section 3.3. Section 3.5 deals with a mathematical tool that can be used to classify and compare different channel environments. Proofs are postponed for the Section 4.
2. Scheduling problem formulation as constrained Markov decision process. 2.1. Review of constrained Markov decision processes and Lagrangian optimization. The aim of this section is to quickly review the key results on CMDP and Lagrangian formulation of the optimal constrained cost. Notation: Upper case bold letters denote random variables, while lower case letters are reserved for the instances of random variables. Let X(y) denote the random variable X conditioned on the outcome y of the random variable Y. Let ICI denote the cardinality of a certain finite set C, r[·J denotes the probability measure and lE[·J denotes the expectation operator. Let No be the set of integers including 0. Let S denote an arbitrary finite set called the state space': Let n == 0,1,2, ... denote discrete time. Let As, S E S denote an arbitrary collection of finite sets called action sets. The evolution of a MDP can be described as follows. When the system is in state S E S, a finite number of possible actions which are elements of the set As can be taken. Let an denote the action taken by the decision maker at the time n. The system evolution is Markovian with transition probabilities
°
(2.1)
for some si, Sj E S, a E A S j and n == 0,1, .... Let On, n ~ denote the a-algebra generated by the observed system state So, ... ,Sn at time n. Define the set of Markovian admissible policies == {A == {an} Ian is measurable w.r.t. On, \:In == 0,1, ...}. This means that an is a (potentially) random function of current state Sn. Let D denote the set of all pure policies where an is a deterministic function of current state Sn. The finite cost c( Sn, an) ~ 0 is the instantaneous cost of taking action an in the state Sn. For any admissible policy 7r E , let the infinite horizon cost conditioned on initial state So == So be defined as
where the expectation is over randomized actions An and system state Sn evolution for n == 1,2,.... The goal is to compute the optimal policy 7r* that minimizes the cost (2.2)
(2.3) 1 See Section 2.4 for the remark considering continuous Markov Processes, e.g. for modeling Rayleigh fading channels.
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING
79
subject to the global constraint
(2.4) Here d(s,a) 2: 0 is a known instantaneous finite cost function, where constraint cost D 2: 0 is a user specified parameter. Any policy 1T* that minimizes CSo ( 1T) will be called the optimal policy. Transmission cost of the policy 1T* that is optimal subject to constraint (2.4) will be denoted by C* (D). We will call the constraint (2.4) active if the equality holds in (2.4) for the optimal policy 1T*. Denote with V the set of all constraint costs D such that (2.4) for the optimal transmission scheduler is active, i.e.,
V == {DID(1T*) == D; 1T* is optimal policy for constraint cost D}.
(2.5)
The set V will be called the set of feasible constraints. A CMDP is considered unichain if every feasible policy where an is a deterministic function of So, ... ,Sn induces a single recurrent class plus possibly an empty set of transient states. For finite CMDPs with unichain structure and bounded costs it is sufficient to regard the set of admissible policies that are not history-dependent [1] as the optimal policy can be always found within the set of Markovian admissible policies
cost and policy of the constrained Markov Decision Process can be found using an unconstrained MDP and Lagrangian approach. THEOREM 2.1. The optimal cost function of a finite unichain CMDP problem satisfies
C*(D) == min sup J(1T, A) - AD == sup min J(1T, A) - AD 7rE
(2.6)
A2:0 7rE
where
(2.7) and c(s, a; A) is the Lagrangian cost given with
c(s, a; A) == c(s, a) + Ad(s, a) for a certain Lagrangian multiplier A > O.
(2.8)
80
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
Note that the minimization in the rightmost expression in (2.6) can be performed only over the set of pure policies. This important Theorem establishes that the CMDP problem can be solved by solving the appropriate Lagrangian unconstrained MDP problem and the relative value or policy iteration algorithms available for this case.
2.2. Markovian dynamics for the channel and incoming traffic. We now formulate the generic transmission control problem as CMDP. Consider the transmission scheduling problem comprising of a single user with Markovian traffic arrival, finite transmission buffer and Markovian fading channel as shown in Fig. 1. Then each state s E S is composed of three components s == [h, b, f] and S == H x B x F where x denotes the Cartesian product. H denotes the channel state s.pace, B denotes the buffer state space and F denotes the traffic state space. The following assumption for the stated transmission scheduling problem will be used to establish the main results of the paper. ASSUMPTION 1. The CMDP that models the transmission scheduling problem is unichain.
Higher Layer Application
Higher Layer Application
Buffer
hn FIG. 1. Block scheme of the transmission adaptation system.
As a consequence of this assumption, all components of the state variable form ergodic processes for any feasible Markov policy 1r E
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 81
Note that h is an uncontrollable component of the system state since it is not control dependent. Let H(h n ) be the random variable of the channel state h n+1 ph (·1 h n) as conditioned on the previous state h n. The second component of the state space is the current buffer state b E B where set B == {O, 1, ... , L - 1} corresponds to all possible states of the buffer occupancy in bits. The third component of the state space is f E F{O, 1, ... , P-1} which is the current perfectly observable incoming traffic state. The finite traffic state space satisfies F c No and P == IFI. ASSUMPTION 3. Incoming traffic state that forms an ergodic Markov Chain with transition probabilities pi (fn+llfn) is independent of actions, buffer and the channel state. Therefore, incoming traffic state is also an uncontrollable component of the state space. I"-.J
2.3. Scheduling action space and transition probabilities. Let
W(a) be the buffer retrieval function that denotes the number of bits to be taken from the buffer provided that action a E As is applied in state s E S. The buffer evolves according to the Lindley recursion
(2.9) where f n is the number of incoming packets at time nand G is the incoming traffic packet size in bits. Without the loss of generality we can assume that W(a) is a non-decreasing function of a. An action an is available in state Sn == [hn , bn , fn], (or an E A sn ) , if
(2.10) This condition prohibits actions that would lead to negative buffer occupancy. The next component of the CMDP description are the transition probabilities. As a consequence of Assumptions 2 and 3 and (2.9), the transition probability between the states s == [h n+1 , bn+1 , fn+d and s == [h n, bn, in] is given with
min(bn + Gin+l - w(a n), L)) x ph(h n+1Ih n)pi (in+llin)
p(sn+ll sn,a n) == J (bn+1
-
(2.11)
where an E A S n and £5 (x) is a Kronecker delta function i.e. £5 (x) == 1 if x = 0 while J(x) == 0 otherwise.
2.4. Example of optimal transmission scheduling as CMDP. In this subsection, a transmission scheduling example is formulated as CMDPs. This example is used subsequently in Section 3. REMARK 2.1. While the structural results and examples in this paper are derived for denumerable Markov chains, under suitable regularity
82
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
conditions (cf. !16}) the results also hold for continuous state Markov Processes, such as the Gaussian AR channel model (see Example 1). However, for notational consistency, we assume that a continuous-state Markov Process is discretized (approximated) with sufficient precision by a denumerable Markov chain. EXAMPLE 1. Transmission rate adaptation for average power minimization. Transition Probabilities: Consider the complex channel gain h n at a certain transmission block n modeled as p-th order autoregressive contin-
uous state model p
b«
==
L
(1jh n - j
+ Vn
(2.12)
j=l
where V n is white (complex) Gaussian noise with variance (J'2 and mean u. In view of the Remark 2.1, we assume that continuous-state AR model (2.12) is replaced with a discretized model
(2.13)
Function 3 : C ~ H represents a quantization function performed at the channel gain estimator that ensures that complex gains hn belong to the finite set H c C. For example, quantizer =: can perform uniform quantization of both real and imaginary components of the complex channel gain with finite number of uniformly spaced quantization levels. In this model, the state of the channel at n-th block is the vector h n == {h n - 1 , ... , h n - p } . If p == 1 this model represents a first order Markov Chain as was used in e.g. [24]. Assuming coherent detection at the receiver, the amplitude channel gain of the complex gain h is Ihl. Action Space: Transmission scheduler is performing power adaptation of transmitted code words. Let the actions a E A == {a, ... ,A} correspond to rate a/M codes employed at the transmission scheduler, where M is the number of symbols in the code word. Therefore, it follows that W(a) == a where W(a) is defined in (2.9). Each rate action determines specific transmission power for a fixed BER. Cost: Define the transmission cost as the power 2
c([h,
b, f], a) = f(B;R)lh/ 2 (2 W(a )/ M - 1) ,
(2.14)
that is necessary to achieve code rate W(a)/ M for specified bit error rate BER, and noise variance (J'2. The SNR gap f(BER) of a practical modulation corresponding to the Shannon capacity formula can be found in
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 83
e.g. [11]. The previous power cost comes from the expression for the transmission rate R
R = log2
(1 +
r(BER)lhI
2
;) ,
(2.15)
that can be achieved for signal to noise ratio ~ with bit error rate BER. Constraint: The global constraint is the latency constraint
(2.16)
for a given latency constraint iJ and random variable B n describing the buffer occupancy at time n. According to the Little's formula, (2.16) describes the constrained average delay incurred in the buffer. In terms of the notation of (2.4)
b d([h, b, f], a) = CF where
(2.17)
P is the average number of incoming packets.
3. Structural results for transmission scheduling. In this section we present the main results of this paper and discuss their importance through several examples. Proofs of the results are presented in Section 4. Throughout this section we consider that Assumptions 1, 2 and 3 hold 2 . 3.1. Submodular functions and stochastic dominance. We take a brief detour to give important explanations and definitions that will be necessary to state the results and formalize the proofs. DEFINITION 1. f23} A function f : A x X x p ~ ~ is supermodular (has increasing differences) in (a, x) for a fixed parameter pEP, if for all a' ~ a and x' ~ x,
f(a',x';p) - f(a,x';p)
~
f(a',x;p) - f(a,x;p).
(3.1)
A function is f : A x X x P ~ ~ is submodular (has decreasing differences) in (x, a) if the conditions of previous definition are satisfied and the inequality in (3.1) is reversed. A central question of interest for establishing the monotonic structure of the scheduling policies is to identify when n(x)
== arg min f( a, x; p) aEA
(3.2)
2The unichain assumption is not necessary for our proofs if infinite horizon discounted costs [17] are used in lieu of average costs.
84
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
is non-decreasing in x for any parameter pEP. This result is due to Topkis [23] and shows that submodularity of the function f in the pair (x, a) implies that 7r(x) is non-decreasing function. We shall also need the following definition of the stochastically dominating random variables [15], [22), [20). Let TQ be the set of all bounded functions f : Q ~ R such that f(q) < 00, for all q E Q and certain finite set Q. DEFINITION 2. [15J, [22J, [20J Let x, and X 2 be r.v. with the support ~Q X 2, if IE [u(X l)] 2: on Q and let 9 c TQ . Xl dominates X 2, or IE [u(X 2 ) ] for all functions u E g. Each set 9 thus defines a dominance partial ordering. Let X(h) be a random variable with support on finite ordered set Q and conditioned on the scalar parameter h E Q. We will call X( h) stochastically nondecreasing on 9 if X(h l ) ~Q X(h 2 ) for some hI > b». Similarly, X(h) is stochastically non-increasing on 9 if X(h l ) =5g X(h 2 ) for some b, > h2 . It is well known [22) that if 9 is the set of increasing functions on a finite set Q, then the stochastic dominance ordering corresponds to the first-order stochastic dominance ordering. In this case, X, ~l X 2 if and only if Fl(x) F 2(x) for all x, where FI(x) and F2(x) are cumulative distribution functions of r.v. Xl and X 2, respectively. By definition, second-order stochastic dominance proceeds from the Definition 2 by restricting the set of functions 9 to all non-decreasing and concave functions. It is of interest to note that if X, first-order stochastically dominates X 2 , then X, second-order stochastically dominates X 2 . Also, if X. second-order stochastically dominates X 2 , and if Xl and X 2 have the same mean, then X, has smaller variance than X 2 •
x,
<
3.2. Effect of buffer occupancy on the optimal transmission scheduling policies. In this section we establish the first main result of this paper - sufficient conditions for the optimal transmission policy 7r of the described transmission scheduling model to be monotonically nondecreasing in the buffer state b. To state our result, we need the following assumption and definitions: ASSUMPTION 4. Set of feasible actions As in state s == [h, b, f] E S is a non-empty set of actions a E A for which b + f' - w(a) :::; Land b - \lJ(a) 2: 0 and any f' E F. Note that previous assumption prohibits transmitter buffer overflows and underflows. DEFINITION 3. For any 0 :S q :::; 1, mixed policy 7r is a randomized policy formed of two pure policies 7rl and 7r2 such that policy 7rl is applied with probability q and policy 7r2 is applied with probability 1 - q. According to the previous definition, mixed policy 7r is a randomized policy that is convex combination of pure policies 7r1 and 7r2. DEFINITION 4. Pure policy 7r is non-decreasing in the buffer state b if the ordinal number (index) of the action a == 7r([h, b, f)) taken in state
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 85
[h, b, f] is non-decreasing in buffer state b for each channel state hand traffic state f. THEOREM 3.1. Let the Assumptions 1, 2, 3, 4 hold. Let the instantaneous Lagrangian cost c([h, b, f], a; A) (2.8) be submodular, convex function of b and increasing in buffer state b. Let \lJ(a) defined in (2.9) be concave increasing function of a. Then for cost constraint fJ > 0, the optimal randomized policy n* ([ h, b, f]) is a mixed policy of two pure policies n 1 ([h, b, f]) and 7[2([h, b, f]) that are non-decreasing functions of buffer state b (see Definition 4). Furthermore,. there exists only one state s E S such that n1(s) i= n 2(s). As buffer retrieval function \lJ (a) is chosen to be increasing in the ordinal number of action a, Theorem 3.1 states that with increasing buffer occupancy b, the pure policies 1T"1 and 1T"2 that constitute the optimal policy 1T"* take more bits from the buffer, irrespective of the channel state. Therefore the average number of bits taken from the buffer by the optimal mixed policy 1T"* is also an increasing function of the buffer occupancy b. Note that the Theorem 3.1 does not place conditions on instantaneous cost c([h, b, f], a) and constraint related cost d([h, b, f], a) defined in Section 2, i.e. both of these functions can be dependent on all three components of the state space [h, b, f]. Example of Theorem 3.1. Consider the power adaptation Example 1 with transmission cost given in (2.14) and buffer cost given in (2.17). Then since the power does not depend on buffer state b and instantaneous buffer cost d([h, b, f], a) is not dependent on a, the Lagrangian cost c([h, b, f], a; A) is submodular in (b, a). In the power adaptation Example 1 instantaneous transmission cost c([h, b, f], a) (2.14) is a convex function of a and not a function of buffer state b, while instantaneous buffer cost d( [h, b, f], a) (2.17) is a convex function of b and not a function of a. Then the Lagrangian cost c([h, b, f], a; A) is convex in b. Assuming that \lJ(a) is a non-increasing function of action a (which simply amounts to notational convention), Theorem 2 holds. COROLLARY 1. Under the conditions of Theorem 3.1, the optimal policy 7[* (s), s E S of Example 1 is a mixed policy of two deterministic policies that are non-decreasing functions of the buffer state for each channel and traffic states. Note that each of the pure policies that constitute a mixed policy in Theorem 3.1 can be calculated from an unconstrained MDP with a fixed Lagrangian multiplier A > O. The algorithms for computation of the Lagrangian multiplier is presented in the next subsection. 3.3. Effect of the constraint on the optimal transmission scheduling cost. This section explores the properties of the dependence of the optimal transmission cost C* (fJ) on the buffer cost constraint fJ. Function C* (D) is also presenting a lower bound on the achievable region of transmission costs for given buffer cost constraint D.
86
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
Let 7r~ be the optimal pure policy of the Lagrangian formulation (2.6) of the CMDP model for a certain Lagrange multiplier A and let IIp == {7r~IO < A < oo}. Since in the finite CMDP model S < 00 and A < 00, IIp == {7ri, 7r2,... , 1rQ} for some Q < 00 as the number of possible pure policies for transmission schedulers is finite. Therefore, there is a finite number of pairs [C(1rl ), D (7rl)] ,l == 1, ... , Q that satisfy the equations (2.3) and (2.4). Without the loss of generality, assume the ordering D(1rl1) < D (1rl2) for certain II < 12 and II, l2 E {1, ... , Q}. If the conditions of Theorem 3.1 are satisfied then each of schedulers 7r l, 1 == 1, ... ,Q possess the non-decreasing structure in the buffer state. THEOREM 3.2. Let the Assumptions 1, 2, 3 hold.
(1) For any buffer length L E No, the optimal average transmission scheduling cost C* (D) is a piece-wise linear non-increasing function of jj E V that can be expressed as C*(D) == max (D(1r;J - D) A + AEA
C(7r~)
(3.3)
where A defined as
is a finite set. (2) In addition to the above stated assumptions, suppose that Assumption 4 holds and that c( [h, b, f], a; A) is jointly convex in b, a and A and let \lJ(a) be concave increasing in a. Then C*(D) is piece-wise linear convex non-increasing function of fJ. Interpretation of Theorem 3.2. In Example 1 Lagrangian cost function c([h, b, f], a; A) is jointly convex in b,a and A and \l1(a) is concave in a. That implies that optimal power is convex decreasing function of the average delay in the buffer. The vertices of the piece-wise linear convex function (3.3) are the power and delay costs attained by optimal pure transmission schedulers, whereas the points in the linear segments between the vertices can be attained by using mixed policies. The main use of Theorem 3.2 is that it gives us a representation of the transmission cost C* of the optimal randomized policy for the transmission scheduling problem as a piece-wise linear convex function of the constraint D. This leads to an efficient algorithm for the calculation of the optimal randomized policy as discussed in Section 3.4. For a given feasible cost constraint fJ E V, let the optimal policy be mixed policy of pure policies 7r; and 7rt:, where the first policy is taken with probability q and the second with probability 1 - q. Note that, according to [18] policies 7r; and differ only in one state. Under the Assumption 1
r:
D == qD(nj) + (1 -
q)D(n'k).
(3.5)
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 87
Using the above discussion and notation it can be concluded that the set of feasible cost constraints D == [D(1ri), D( 1rQ)]. Under the condition of Theorem 3.2 pairs [C(1ri),D(1ri)]' l == 1, ... , Q constitute the vertices of a piece-wise linear convex function C*(D). Furthermore, Theorem 3.2 implies that given a parameter D E D, the pure policies 1rj and that form the optimal mixed policy are adjacent, i.e. k == j + 1 as all other combinations of pure policies would give larger power cost due to the convexity of C(15). Under the conditions of Theorem 3.1 pure policies 1rj and 1rj+1 that form the optimal mixed policy are differing in only one state. Due to the piece-wise linearity and convexity of the dependence of the function C*(D), several consequences of the Theorem 3.2 can be stated. The lower and upper bounds on achievable performance can be given with the following Corollaries. COROLLARY 2. (Lower bound) Let ~ ~ A, where A is the set of
r:
coefficients of linear segments defined in (3.4). Then a lower bound on the convex function C* (D) is given by the piece-wise linear function max '\E~
(D - D(1r~)) A + C(1r~) < C*(D).
(3.6)
The practical importance of the Corollary 2 is that knowledge of only a subset of segments of the piece-wise linear function C* (D) can produce a lower bound on the achievable transmission cost region. For example, if any two adjacent pure policies 1r_i and 7r_;+1 are known, then a line through points [C(1rj),D(1rj)] and [C(7rj+l),D(7rj+l)] constitutes a lower bound on
C(D). COROLLARY 3. (Upper bound) If only a subset of Z points [C l, .ol], l == 1,2, ... , Z on the convex piece-wise linear function C*(D) is known, then an upper bound on function C* (D) is formed by the piece-wise linear function with vertices [Cl , Dl) ,l == 1, 2, ... , z. REMARK 3.1. The simplest of the upper bounds can be constructed by considering Z == 2 in Corollary 3. Then only extremal policies 1ri and 1rQ
exist and their respective transmission and buffer costs are [C1,Dd == [C(1f;),D(1r;)] and [C2 ,15 2 ] == [C(7r Q),D(7rQ)]. Note that, pure policy 1ri can be computed from the Lagrangian formulation of the CMDP model for A -7 00, while 1rQfollows from the same model for A == o. Under special conditions on the transmission cost c(s, a) and buffer cost d(s, a) of Section 2, the optimal pure policy 1ri can be found without the use of stochastic dynamic programming methods. For example, when c(s, a) is not dependent on the buffer occupancy b and traffic state f and d(s, a) is increasing in b while not dependent on channel state h and traffic state f (as in Example 1), then the optimal policy 1ri is equal to 1r~([h, b,
f]) == m~x{ala
E A[h,b,J]}.
(3.7)
88
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
3.4. Algorithm for computation of the lagrange multiplier and optimal mixed policy. The optimal pure policy for a CMDP can be found using the relative value iteration (RVI) in case that the constraint is (2.4) active. However, we can still pose the question of computation the suitable Lagrangian multiplier .\ that satisfies the constraint with equality. Note that the average constraint for the optimal policy 7r~ for Lagrangian multiplier .\ can be given with (3.8)
For the model of Section 2 and positive transmission and buffer costs, D( 7r~) is piece-wise constant decreasing function of A. A simple algorithm designed to find the smallest .\ (that will be called A*) such that the constraint (2.4) is satisfied can be formulated as following
(3.9) where the step
En
==
~. The convergence to .\ * is ensured as the function
1(D( >J - iJ) o. ,\
1r
is piece-wise linear concave function that attains its global maximum at .\ * and its derivative is D(7r~). Therefore the algorithm (3.9) is just a gradient descent algorithm. We demonstrate how to employ the estimated parameter A* to find the optimal randomized policy for any feasible constraint b E V with RVI. Assume that conditions of Theorem 3.1 hold. First, find the A* for a given feasible constraint D. In view of Theorem 3.2 and [6]' perturb the parameter A* by some 6.\ to get .\- == A* - 6.\ and A+ == .\ * + c5A. Next we find the optimal pure policies 7r~ _ and 7r~ + and their respective average constrained costs D- == D(1f;_) and D+ == D(1f;+). As stated in Theorem 3.1, the optimal randomized policy is a mixed policy of two pure policies and let parameter q determine the probability of taking the policy 7r~_ and 1- q be the probability of taking the policy 7r~+. Now, parameter q can be computed such that qD- + (1 - q)D+ == D. 3.5. Influence of channel dynamics. In this section we present new results on the influence of the fading distributions on the performance of scheduling algorithms. We start with a general result on the influence of channel dynamics on the optimal transmission scheduling cost in Theorem 3.3. This result is later made more specific in Theorem 3.4 for the first order dominance and Corollary 6 for the second order dominance of transition probabilities of the channel. Consider channels P and Q, and let Hp(h n ) and HQ(h n ) be random variables with the support on H that describe the channel state in the next
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 89
decision epoch as conditioned on the previous state h n E H, for channels P and Q respectively. Where needed, we explicitly state the dependence of costs, feasible delays and value functions on transition probabilities by denote using the appropriate subscripts P and Q. For example C p and the optimal costs of (2.3) for channels P and Q respectively. For a unichain unconstrained MDP model with instantaneous costs given in (2.8), the differential value function V(s; A) of the optimal pure policy x" can be calculated from [4]
Co
L p(s/ls, a)V(s'; A)]
C*(A) + V(s; A) == min [C(S, a; A) + aEA s .
(3.10)
s'ES
where V(sr; A) == 0 for a certain reference state Sr E S. C*(A) is the optimal average cost defined in (2.3). The previous equation is also referred to as the Bellman's equation. The differential value function can be calculated using relative value iteration forming the sequence of estimates Vffi(S; A). If convergence is achieved V(s; A) == limffi~oo sup Vffi(S; A). For a feasible action a E As in state s we can define the state-action value function
Q(s, a; A) == c(s,a; A) +
L p(s'ls, a)V(s'; A).
(3.11 )
s'ES
Function Q( s, a; A) can be perceived as the equivalent instantaneous cost for the dynamic stochastic problem that can be used to find the optimal action in a given state. Now, the optimal policy can be found according to 1f~(s) == argminaQ(s,a;A). The optimal cost C*(A) for a given A can be calculated using (3.10). Let us revert to the transmission scheduling problem formulated in Section 2. Recall as in Section 3.1 that TQ denotes the set of bounded functions on a finite set Q. THEOREM 3.3. Consider tllJO fading channels P and Q 'w'ith Hp(h)
and HQ(h) random variables of the next channel state as conditioned on the previous state h E H, for channels P and Q respectively. Let Assumptions 1, 2, 3 hold. Suppose that Vp([h, b, f]; A), VQ([h, b, f]; A) E g for any b E B, f E F and A E ~+ where 9 is a subset o] all bounded junctions on H i.e. 0 C T1{. Then ifHp(h) dominates HQ(h) on 0, it follows that C*p -> C*Q
(3.12)
for any feasible buffer cost constraint fJ E 'Dp n 'DQ , where 'Dp, 'DQ are feasible cost constraint sets (2.5) of channels P and Q respectively. C p and are optimal costs (2.3) of channels P and Q respectively. In the sequel we discuss the conditions on the channel and cost under which functions V([h, b, f]; A) are the elements of a set of functions 9 c T'}-{, for any b E 13, f E F and A E ~+. In the following Theorem we give
Co
90
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
sufficient conditions under which differential value functions V([h, b, f]; A) belong to the set of non-decreasing functions in h. THEOREM 3.4. Let the Assumptions 1, 2, 3 hold. A sufficient condition for V([h, b, f]; A) to be non-increasing function of h for any b E B, f E :F and A E ~+ is that: (1) H (h) be first order stochastically nondecreasing in h, and (2) c([h, b, f], a) be non-increasing function of h.
The results of Theorem 3.4 can be combined with the results of Theorem 3.3 to establish the following Corollary. COROLLARY 4. Let the Assumptions 1, 2, 3 hold. Let Hp(h) and HQ (h) be first order stochastically increasing in h and let H p (h) be first order stochastically dominating HQ(h) for any h. Then, if c([h, b, f], a) is non-increasing function of h
C*P
< C*Q
(3.13)
-
fJ E 1) p n 1)Q . The below example gives a consequence of this result for the case of autoregressive (AR) models for channel fading gains. Consider the special case of first order AR model of (2.13) with p == 1. i.e. for any feasible average buffer cost constraint
(3.14) COROLLARY 5. Let the Assumptions 1, 2, 3 hold. Consider channels P and Q modeled as in Example 1 and their respective fading gains that have Rician distribution. If both channels are first order AR models (3.14) with the same noise variance 0- 2 and af 2: a~, then Hp(h) is first order stochastically dominating HQ(h) for any h. Then the minimum necessary power cost to achieve certain feasible average buffer cost fJ E 1) p n 1)Q would be less for the channel P than for the channel Q.
Next we consider the second-order stochastic dominance ordering of
Hp(h) over HQ(h) as this will give us an even more precise comparison among two channels. The definition and discussion of the second order stochastic dominance is given in Section 3.1. The following Corollary is stated without proof as it follows the same ideas as Theorem 3.4 and Corollary 4. COROLLARY 6. Let the Assumptions 1, 2, 3 hold. Let Hp(h) and
HQ (h) be second-order stochastically increasing in h and let H p (h) be second-order stochastically dominating HQ(h) for any h. If c([h, b, f], a) is non-increasing and convex function of h for any b E B, f E :F and A E ~+ then C*p
< - C*Q
for any feasible average buffer cost constraint
(3.15)
fJ
E
Vp
n V Q.
Fading channels with stronger scattering have larger variance of the fading gain h. Therefore, based on Corollary 6 we can state the following
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 91
rule of thumb: Channels with less scattering and the same mean require less average transmission cost for the same buffer cost constraint. The second order dominance property of Corollary 6 can also be used to investigate the performance of scheduling algorithms used in conjunction with the Maximum Ratio Combining (MRC) for multichannel receivers (cf. [21]). Consider the use of an optimal scheduling algorithm over a Rayleigh flat fading channel with the distribution I 1_l! p(hlh ) == ~e i
(3.16)
!
of the received power gain h with mean 1, variance 12 and independent of the previous channel state h'. Recall that the power gain is proportional to the signal to noise ratio. The instantaneous cost c(s, a) can be then given as in (2.14) and the constrained buffer cost as in (2.17). We explore the influence of the use of multichannel MRC receiver with K diversity branches with Rayleigh fading gains h l , l == 1,2, ... ,K on the performance of the scheduling algorithm for fixed buffer cost constraint fJ. To ensure a fair comparison, it is assumed that each diversity branch has the same noise power as in the single diversity system. Furthermore, the average powers are equally distributed across all diversity branches, i.e. IE[h l ] ==
k'
;;z == ~ == l == 1,2, ... , K. The equivalent power gain after MRC combining is given by [21] (3.17) Under the above assumptions on the distribution of signal and noise powers across the diversity branches, the equivalent power gain after MRC diversity combining has the chi-square distribution (cf. [21], p. 267) K
1
1
P (hlh) = (K -l)!("Y/K)K h
K -1 _ ~h
e
~
(3.18)
-2
with mean l' and variance k' Since the distribution of the single channel receiver gain have the same mean but larger variance than the corresponding multichannel receiver gain, we can employ Corollary 6 and the properties of second order stochastic dominance to show that multichannel MRC receivers will always have smaller average transmission cost than the single channel receivers, for the fixed feasible average buffer cost. Using the same approach it can also be shown that receivers with more branches will also perform better. The following Corollary summarizes this discussion. COROLLARY 7. Consider the Maximum Ratio Combining reception
system (cf. (3.17)) with K diversity branches with independent fading processes. Let each branch follow a Rayleigh fading distribution with average
92
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
signal to noise ratio S~R for some fixed constant SNR. Under the conditions of Corollary 6 the average transmission cost is a decreasing function of the number of diversity branches for any feasible buffer cost constraint ti. 4. Proofs. Proof of Theorem 3.1. Let us first consider the case that the buffer cost constraint fJ in (2.4) is chosen such that a pure stationary policy exists that is optimal for the stated communication model and that constraint (2.4) holds with the equality for the optimal policy, i.e. the constraint (2.4) is active. Later this condition is relaxed and a non-decreasing property is shown for general constraints and randomized policies. This implies that there exist a Lagrange multiplier A and the optimal pure policy 1r~ that attain the sup and min respectively in the righthand side of (2.6), such that the global constraint D (1r~) == b. In order to prove that 1r~ ([h, b, f]) is increasing function of buffer occupancy b, we have to demonstrate that Q([h, b, f], a;'x) is submodular function in the pair (b, a). First notice that according to the statement of the theorem c([h, b, f], a;'x) is submodular function of (b,a). Therefore we only need to show that the second term of (3.11)
Q1([h, b, f], a; ,X)
=
L L ph(h'lh)pf(f'If)V([h',b-1J!(a)+G!,,!,];'x)
(4.1)
h'EH fIEF
is submodular function of (b, a) for any hand f. Here we used the Assumptions 1,2,3,4 of our model to simplify (3.11). We first state the following Lemma whose proof is after the end of the proof. LEMMA 4.1. Under the Assumptions 1,2,3,4, V([h,b,f];'x) is con-
vex increasing function of buffer state b for any h, f and ,X given a convex increasing instantaneous cost function c([h, b, f], a;'x) in b and concave function w(a) . Now, if function V([h,b,f];'x) is convex in buffer state b, it can be shown that V([h',b - \lJ(a) + Gf',f'];A) is also submodular in (b,a) for any h' E H, f' E :F. This follows by noting that for a convex function V([h, b, f];,X) of b it holds that V([h, x, f];,X) + V([h, y, f];,X) ?: V([h, ax + (1 - a)y, f];,X)
(4.2)
+ V([h, (1 -
a)x + ay, j];,X)
for certain 0 ::; a ::; 1. This is a direct consequence of the definition of convex function V([h,b,j];'x). Substituting x == b - w(a') + Gj,y == b' - w(a) + Gf and a == (\l1(a') - \l1(a))/(\l1(a') - \l1(a) + b' - b) in the previous equation and rearranging the terms we can get the following
V([h, b - w(a') + Gj, j];,X) + V([h, b' - w(a) + Gj, j];'x) (4.3) ?: V([h, b' - w(a') + G f, f];,X) + V([h, b - w(a) + G j, j];'x)
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 93
Rearranging the terms of the previous inequality we get
V([h, b' - w(a/) + G[, f]; A) - V([h, b' - w(a) + Gt, f]; A)
< V([h, b -
(4.4)
w(a/) + Gf, f]; A) - V([h, b - w(a) + Gf, f]; A)
that for a/ ~ a and b' ~ b is equivalent to the submodularity of V([h, b- W(a) + G f]; A) in the pair (b, a) for some channel and traffic states hand f. Furthermore, positive weighted sum of submodular functions is also submodular, which establishes the submodularity of Q([h, b, f], a; A) in (b, a) and monotonic structure in buffer occupancy of the optimal pure policy for active constraint. Using the result of [6] the optimal randomized policy for a general constraint jj is a mixed policy of two pure policies that can be computed for two different Lagrange multipliers. As discussed above, for A > 0 all optimal pure policies are non-decreasing in the buffer occupancy and both of the policies that constitute the mixed policy for a general constraint jj possess that non-decreasing structure as well. Further, according to [18], the number of states with randomized actions in a unichain MDP model with only one constraint is no more than 1. Therefore the pure policies that constitute the optimal mixed policy differ in only one state. This concludes the proof. D Proof of Lemma 4.1. The proof follows by mathematical induction and using the relative value iteration. As RVI converges for any initial VO([h, b, f]; A), let us choose that VO([h, b, f]; A) is a convex increasing function of buffer state b. The non-decreasing property of function vm([h, b, f]; A) in b follows from the non-decreasing property of the instantaneous Lagrangian cost c([h, b, f], a; A) in b. Now, we will show that increasing and convex property of Vm([h, b, I]; A) implies the increasing and convex property of V m +1 ([h, b, f]; A) in b. Note that under the Assumption 4 minimization in Lindley formula (2.11) can be omitted for any feasible action a and buffer occupancy b. According to the value iteration algorithm V m+ 1([h, b, I]; A) == minQm([h, b, f], a; A). a
(4.5)
Under the conditions of the lemma, as shown above, if vm([h, b, f]; A) is convex in b, then Qm([h, b, f], a; A) is submodular in (b, a). Therefore,
Qm([h,b',f],a';A) - Qm([h,b,f],a';A)
< Qm([h, b',f], a; A) - Qm([h, b, f], a; A) for some a/ ~ a and b' ~ b. Using the convexity of Qm([h, b, f], a; A) in b, the previous equation implies
94
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
Qm([h,
u, f], a'; A) -
Qm([h, b, f], a'; A) ~ Qm([h, b' +p, f], a; A) - Qm([h, b + p, f], a; A)
for certain p 2: o. Rearranging the terms of the previous equation and substituting b' == band b == b- p we can get
Qm([h, b+ p, f], a; A) - Qm([h, b, f], a'; A) 2: Qm([h, b, f], a; A) - Qm([h, b- p, f], a'; A) a == argminaQm([h,b,f],a;A) and using (4.5)
Now, substituting a' we get
V m+1([h,b+p,f];A) - V m+1([h,b,f];A)
2: V m +1([h, b, f]; A) - V m +1([h, b- p, f]; A) which is equivalent to convexity of vm+l ([h, b, f]; A) in b. This concludes the proof. D Proof of Theorem 3.2. (1) The non-decreasing property of function C* (D) follows from the positivity of costs c(s, a) and d(s, a). As discussed in Section 3.3 finite state CMDP with finite number actions has only a finite number of pure policies. Only a finite number of pure policies exist that attain the minimum in (2.6) and their respective Lagrange multipliers can be given by (3.4) for fJ > O. Therefore (2.6) can be rewritten as
C*(D)
=
L (JC ,>.) - >'D) Ip.=suPA~omin"E.pD 7f
J(1r,>")->"D}
(4.6)
..\EA
where I{x} is the indicator function that returns 1 if x is true, and 0 otherwise. The piecewise linear characterization (3.3) of the achievable region C*(D) follows by differentiating (4.6) with respect to D and using the continuity arguments of Lagrangian costs c(s, a; A) in A. (2) According to Theorem 2.1 for a feasible constraint fJ E V, the optimal average cost can be calculated as
c(15) == SUpC*(A) - AD
(4.7)
..\>0
where C*(A) is defined in (3.10). The non-decreasing property of function C(D) follows from the positivity of costs c(s, a) and d(s, a). To prove that C(D) is convex in D, we have to show that C*(A) - AD is convex in A for each D. This follows from the fact that max; f(x, a) is convex in x if f(x,a) is convex in x for each a [19].
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING 95
This is equivalent to showing that C*(A) is convex in A. Further, C*(A) can be calculated for a known differential value function V[h, b, f]; A) from
C*(A) == min[c([hr , br , fr], a; A) a
+
L
:r
h' EH
f' EF
(4.8)
ph(h'lh r )pf (f'lfr )V([h', br - w(a) + G1', f']; >')]
for a certain reference state S r == [hr , br , j r ]. Previous equation follows under Assumptions 1, 2, 3 and 4 from (3.10). Next, we show that if V ([h, b, j]; A) is jointly convex in buffer state b and A, then V ([h, b- (a) + G f, f] is also jointly convex in a and A. If V([h, b, f]; A) is convex in a and A, it follows that
w
aV([h, b- W(al)+Gj, j]; AI)+(1-a)V([h, b- w(a2)+G j, f]; A2) a
2 V([h, b-(aw(al)-(1-a)w(a2))+Gj, f]; aAI +(1-a)A2) b
2 V([h, bl
-
(4.9)
w(aal +(1-a)a2)+G j, j]; aAI + (1-a)A2)
a
b
where 2 follows from convexity of V([h, b, j]; A) in b and A and 2 follows from the concavity of \lJ(a) and non-decreasing property of V([h, b, f]; A) in b. The proof that V([h, b, j]; A) is convex in b and A is omitted as it stems from the covexity of c([h, b, j], a; A) in b and A by following the similar steps as in proof of Lemma 4.1. Therefore, V ([h, b- (a) + G I, j] is jointly convex in a and A. The convexity of C* (A) now follows by noting that
w
c([hr, br , fr], a; A)+
L L h' EH
ph(h'lh r )pf (f'lfr)V([h', b; - \lJ(a)
+ Gf', f']; A)
f' EF
of (4.8) is jointly convex in a and A. Using the property that g(x) min a f(x, a) is a convex function of x for a jointly convex function f of (x, a), it follows that C* (A) is also convex function of A which concludes the proof. 0 Proof of Theorem 3.3. Based on the Theorem 1 we have that
C p == sup min Jp(7f, A) A>07TE
AD
(4.10)
Similar equation follows for channel Q. Now min.; J p( 7f; A) can be determined through relative value iteration algorithm of Section III and the proof follows by mathematical induction. Start by choosing V~(s; A) 2: V8(s; A)
96
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
Vp(s; A) ~ VQ(s; A) implies V;+l (s; A) >
for any initial state s.
VQ+1(s; A) since
V;+l(s;'x)
= m}n [C(S, a; A) + L
p(s/ls,
a)Vp(~; .:\)]
s/ES
=
mln[c(s,a;'x) + L
pi (J'If) LPi(h'lh)
fIEF X
h'
Vp([h', min(b + Gf' - '1J(a), L), /'];.:\)
2mln[c(s,a;'x) + L
pi(J'If) LP~(h'lh)
fIEF X
Vp([h', min(b + Gt'
b
~ m}n[c(s, a;'x) + L
- '1J(a), L), /']; .:\)]
b
~
pi (J'If) LP~(h'[h)
f'EF X
(4.11)
h'
li'
VQ([h ', min(b + G f'
- '1J(a), L), /']; .:\)]
1
== VQ+ (s) a
where ~ follows from the stochastic dominance of Hp (h) over HQ(h), while b
.
~
follows from the induction assumption Vp(s;.:\) ~ VQ(s; A). Since the value iteration is converging, the previous result further implies (4.12) for any initial state distribution and A E ~+. For D E Dp constraint in (2.4) is active constraint and it follows that
Cp
==
n DQ
supminCp(A,u) - AD ~ supminCQ(A,u) - AD == CQ A>O
A>O
U
the
(4.13)
U
which concludes the proof.
0
Proof of Theorem 3.4. The proof of this Theorem proceeds by employing mathematical induction and the relative value iteration for the calculation of vm([h, b, I]; A). Start by choosing VO([h, b, I]; A) that is nonincreasing in h. Then assuming that vm([h, b, I]; A) is non-increasing in h and the statement of the theorem it follows that V;+l ([h, b, I]; A) given by
V;+l([h, b, f],'x) = ~n[c([h, b, f], a) + L
p(J'If) LPp(h'[h)
f' EF X
Vp([h', min(b + GI'
h'
- w(a), L), I']; A)]
(4.14)
is also non-increasing in h, where we have used the stochastic dominance property of Hp(h '). D
STRUCTURAL RESULTS ON OPTIMAL TRANSMISSION SCHEDULING
97
5. Conclusions. This paper establishes general structural results of optimal pure and randomized policies for the constrained MDP formulation of the transmission scheduling problems. It is shown that the optimal policies are monotonically increasing provided that certain conditions on the convexity of the instantaneous transmission and buffer costs are satisfied. A particularly interesting and useful extension of the work presented in this paper is to devise efficient adaptive control algorithms that can adaptively improve the control policies in unknown environments. Since the state space of the MDP for our transmission scheduling model can be large, it is of interest to employ the structure of the optimal policies in order to speed up the convergence of algorithms such as the Q-Iearning or TD learning [5]. Some similar algorithms that use the structure of the policies and value function in order to simplify the policy improvement of the iterative algorithms have been established in [7], [8]. The presented results can also be used to investigate the influence of correlations of the channel and traffic on the optimal average transmission costs such as power cost. We have established the condition under which it is certain that wireless channels with less scattering would have smaller necessary transmission power for the same transmission latency. This result is also extended to show that maximum ratio combining decreases the necessary average transmission power for a fixed average latency. We also refer the reader to [25], [26] for gradient based simulation optimization algorithms for adaptive control of constrained Markov decision processes. The algorithms in [25], [26] use measure valued differentiation to optimize the constrained MDP via a primal dual type stochastic approximation algorithm. In future work we plan to use the structural results in this paper to analyse constrained MDPs in cross layer admission control of multiclass networks comprising of CDMA users - see [27] for the constrained MDP formulation.
REFERENCES [1] E. ALTMAN, Constrained Markov Decision Processes: Stochastic Modeling, London: Chapman and Hall CRC, 1999. [2] B.E. COLLINS, Transmission policies for time varying channels with average delay constraints, in Proc. of Allerton Conf. on Comm., Control and Compo (1999). [3] R. BERRY AND R. GALLAGER, Communication over fading channels with delay constraints, IEEE Trans. on Inform. Theory (2002), pp. 1135-1149. [4] D.P. BERTSEKAS, Dynamic Programming and Optimal Control, Vol. 2, Belmont, Massachusetts: Athena Scientific, 1996. [5] D.P. BERTSEKAS AND J. TSITSIKLIS, Neuro-Dynamic Programming, Belmont, Massachusetts: Athena Scientific, 1996. [6] F.J. BEUTLER AND K.W. Ross, Optimal policies for controlled Markov chains with a constraint, Journal of Math. Anal. and Applications, 112 (1985), pp. 236-252. [7] C. BOUTILIER, R. DEARDEN, AND M. GOLDSZMIDT, Exploiting structure in policy construction, in Proc. Fourteenth Inter. Conf. on AI (IJCAI-95) (1995), pp. 1104-1111.
98
DEJAN V. DJONIN AND VIKRAM KRISHNAMURTHY
[8] R.P.C. GUESTRIN, D. KOLLER, AND S. VENKATARAMAN, Efficient solution algorithms for factored MDPs, Journal of Artificial Intelligence Research, 19 (2003), pp. 399-468. [9] D. RAJAN, A. SUBHARWAL, AND B.AAZHANG, Delay and rate constrained transmission policies over wireless channels, in Proc. of Globecom Conf. (2001), pp. 806-810. [10] H. WANG AND N.B. MANDAYAM, Delay and energy constrained dynamic power control, in Proc. of Globecom Conf., 2 (2001), pp. 1287-1291. [11] J.M. CIOFFI, A multicarrier premier, available at http:j jwww.stanford.eduj groupjcioffijpdfjmulticarrier.pdf (Nov. 1999). [12] M. GOYAL, A. KUMAR, AND V. SHARMA, Power constrained and delay optimal policies for scheduling transmission over a fading channel, in Proc. of INFOCOM (2003), pp. 311-320. [13] A.K. KARMOKAR, D.V.DJONIN, AND V. K. BHARGAVA, Delay constrained rate and power adaptation over correlated fading channels, in Proc. of Globecom Conf. (2004), pp. 3448-3453. [14] B. PRABHAKAR, E. UYSAL-BIYIKOGLU, AND A.E. GAMAL, Energy-efficient transmission over a wireless link via lazy packet scheduling, in Proc. of INFOCOM (2001), pp. 386-394. [15] A. MULLER, How does the value function of a Markov decision process depend on the transition probabilities'?, Mathematics of Operations Research (1997), pp. 872-895. [16] O. HERNANDEZ-LERMA AND J .-E. LASSERRE, Discrete-time Markov control processes: Basic optimality criteria, Springer, New York, 1996. [17] M.L. PUTTERMAN, Markov Decision Procsses: Discrete Stochastic Dynammic Programming, New York: John Wiley & Sons, 1994. [18] K.W. Ross, Randomized and, past-dependent policies for Markov 'decision processes with multiple constraints, Operations Research, 37 (1987), pp. 474-477. [19] S. BOYD AND L. VANDENBERGHE, Convex Optimization, Cambridge University Press, 2003. [20] M. SHAKED AND J .G. SHANTIKUMAR, Stochastic Orders and Their Applications, Academic Press, San Diego, CA, 1994. [21] M.K. SIMON AND M.-S. ALOUINI, Digital Communication over Fading Channels: A Unified Approach to Performance Analysis, John Wiley & Sons, New York, 2000. [22] J. E. SMITH AND K. F. MCCARDLE, Structural properties of stochastic dynamic programs, Operations Research (2002), pp. 796-809. [23] D. M. TOPKIS, Supermodularity and Complementarity, Princeton University Press, Princeton, NJ, 1998. [24] R.A. ZIEGLER AND J .M. CIOFFI, Estimation of time-varying digital radio channels, IEEE Trans. on Vehicular Tech. (1992), pp. 134-151. [25] F. VAZQUEZ ABAD AND V. KRISHNAMURTHY, Self Learning Control of Markov Chains - A Gradient Approach, Proceedings of 41st IEEE Conf. on Decision and Control, Las Vegas, pp. 1940-1945, 2002. [26] F. VAZQUEZ ABAD AND V. KRISHNAMURTHY, Constrained Stochastic Approxima-
tion Algorithms for Adaptive Control of Constrained Markov Decision Processes, Proceedings of 42nd IEEE Conf. on Decision and Control, pp. 28232828, 2003. [27] S. SUNGH, V. KRISHNAMURTHY, AND H.V. POOR, Integrated Voice/Data Call Admission Control for Wireless DS-CDMA Systems with Fading, IEEE Transactions Signal Processing, Vol. 50, No.6, pp. 1483-1495, June 2002.
ENTROPY, INFERENCE, AND CHANNEL CODING J. HUANG*, C. PANDITt, S.P. MEYN+, M. MEDARD§, AND V. VEERAVALLI'
Abstract. This article surveys application of convex optimization theory to topics in Information Theory. Topics include optimal robust algorithms for hypothesis testing; a fresh look at the relationships between channel coding and robust hypothesis testing; and the structure of optimal input distributions in channel coding. A key finding is that the optimal distribution achieving channel capacity is typically discrete, and that the distribution achieving an optimal error exponent for rates below capacity is always discrete. We find that the resulting codes significantly out-perform traditional signal constellation schemes such as QAM and PSK. AMS(MOS) subject classifications. Primary: 94A24. 94A13, 94A17. Secondary: 94A34, 94A40, 60F10. Key words. Information theory; channel coding; error exponents; fading channels.
1. Introduction. This article surveys application of convex optimization theory to topics in information theory. Our main focus is on channel coding, and the relationships between channel coding and robust hypothesis testing. The optimization problems considered in this paper concern minimization or maximization of a convex function over the space of probability measures. The focus is on the following three central areas of information theory: hypothesis testing, channel capacity, and the exponential bounds on the probability of error in channel coding. One foundation of this work lies in the theory of convex optimization [5, 9]. In particular, the structural properties obtained are based on convex duality theory and the KuhnTucker alignment conditions. A second foundation is entropy. Recall that for two distributions /-l,7r the relative entropy, or Kullback-Leibler diver-
gence is defined as, if J.l -< n, otherwise. Relative entropy plays a fundamental role in hypothesis testing and communications, and it arises as the natural answer to several important ques*Marvell Technology, Santa Clara, CA (j ianyih(Omarvell. com). tMorgan Stanley and Co., 1585 Broadway, New York, NY 10019 (charuhas.pandit(O morganstanley. com). +Department of Electrical and Computer Engineering and the Coordinated Sciences Laboratory, University of Illinois at Urbana-Champaign (meyn
100 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI tions in applications in data compression, model-selection in statistics, and signal processing [29, 15, 12, 4, 16, 13, 14, 20, 36, 8, 17, 31].
1.1. Channel models. We consider a stationary, memoryless channel with input alphabet X, output alphabet Y, and transition density defined by
P(Y E dy I X == x) == p(Ylx) dy,
x E X, Y E Y.
(1.1)
It is assumed that Y is equal to either IR or C, and we assume that X is a closed subset of IR. For a given input distribution f.-l on X, the densitity for the marginal distribution of the output is denoted,
pJ1-(dy) =
J
jl(dx)p(y[x),
Y E Y.
(1.2)
Many complex channel models in which X is equal to C are considered by viewing f.-l as the amplitude of X. Details on this transformation are given prior to Theorem 1.1 below. Throughout the paper we restrict to noncoherent channels in which neither the transmitter nor the receiver knows the channel state. A signal constellation is a finite set of points in X that is used to define possible codewords. Two well known examples when X == Care quadratureamplitude modulation (QAM), and phase-shift keyed (PSK) coding. In these coding schemes the codewords are chosen using a random code constructed with a uniform distribution across the given signal constellation. These methods are largely motivated by properties of the additive Gaussian noise (AWGN) channel, where it is known that a random code book obtained using a Gaussian distribution achieves capacity. The problem of constellation design has recently received renewed attention in information theory and communication theory. While many techniques in information theory such as coding have readily found their way into communication applications, the signal constellations that information theory envisages and those generally considered by practitioners differ significantly. In particular, while the optimum constellation for an AWGN channel is a continuous constellation that allows for a Gaussian distribution on the input, commonly used constellations over AWGN channels, such as quadrature amplitude modulation (QAM), are not only discrete, but also generally regularly spaced. This gap between theory and practice can be explained in part by the difficulty of deploying, in practical systems, continuous constellations. However, there is also a body of work which strongly suggests the continuous paradigm favored by theoreticians is inappropriate for realistic channel models in the majority of today's applications, such as wireless communication systems. Under any of the following conditions the optimal capacity achieving distribution has a finite number of mass points, or in the case of a complex channel, the amplitude has finite support:
101
ENTROPY, INFERENCE, AND CHANNEL CODING
(i) The AWGN channel under a peak power constraint [38, 37, 32, 10].
(ii) Channels with fading, such as Rayleigh [1] and Rician fading [22, (iii)
(iv)
This cally
21]. Substantial generalizations are given in [25]. Lack of channel coherence [27]. For the noncoherent Rayleigh fading channel, a Gaussian input is shown to generate bounded mutual information as SNR goes to infinity [11, 30]. Under general conditions a binary distribution is optimal, or approximately optimal for sufficiently low SNR ([19], and [39, Theorem 3].) article provides theory to explain why optimal distributions are typidiscrete based on the Kuhn-Tucker alignment conditions.
1.2. Capacity and error exponents. Operator-theoretic notation is convenient in the convex-analytic setting of this article. We let M denote the set of probability distributions on the Borel sigma field on some state space X, which is always taken to be a closed subset of Euclidean space. For any distribution jJ EM, and any measurable function f: X - t IR, we denote
\IL, J):=
J
f(x) lL(dx).
Mutual information is defined as,
J-LEM,
(1.3)
and channel capacity is determined by maximizing mutual information subject to two linear constraints: (i) The average power constraint that
(J-L,¢) < a~ where ¢(x) :== x 2 for x E JR. (ii) The peak power constraint that J-L is supported on X n [-M, M] for a given M ~ 00. Hence the input distribution is constrained by J-L E M (a~, M, X), where
M((J~, M, X) := {IL EM: \IL, ¢)
< (J~,
IL{[-M, M]} = 1},
(1.4)
and the capacity C(a~, M, X) is expressed as the value of a convex program,
sup subject to
I(J-L) J-L
E M(a~,
M, X).
(1.5)
The channel reliability junction is denoted,
R>O,
(1.6)
102 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI Er(R) Optimal code 0.25
---_ ...--
QAM
0.20
0.15
,, ,, ,, ,, ,, ,,
0.10
0.05
0
' ... '
....
-
0.1
0
R 0.3
0.2
0.4
0.5
Fig. 1: The error exponent E: (R) for the two codes shown in Figure 11. The 3-point constellation performs better than 16-point QAM for all rates R ~ C.
where Pe(N, R) is the minimal probability of error, where the minimum is over all block codes of length N and rate R. The random coding exponent Er(R) may be expressed for a given R < C via, Er(R) =
sup ( 0:Sp:Sl
[-pR -log(GP(Jl))]) ,
sup
(1.7)
1-LEM(a~,M,X)
where for each p 2 0 we define,
GP(Jl):=
J[J
Jl(dx)p(Ylx)l/(HP)] Hp dy.
(1.8)
The following random-coding bound holds under the assumptions imposed in this paper,
Pe(N,R)::; exp(-NEr(R)),
N2:1,R2:0.
Moreover, the equality E(R) == Er(R) holds for rates greater than the critical rate
Refit
[7, 18].
If one can design a distribution with a large error exponent, then the associated random code can be constructed with a correspondingly small block-length. This has tremendous benefit in implementation. Figure 1 shows an example taken from [26) that illustrates how a better designed code can greatly out-perform QAM for rates R below capacity. Optimization of the random coding exponent is addressed as follows. Rather than parameterize the optimization problem by the given rate R > 0, we consider for each Lagrange multiplier p the convex program, inf
subject to
GP(J-l) J.-l E
M(a~,M,X).
(1.9)
ENTROPY, INFERENCE, AND CHANNEL CODING
103
The value is denoted GP*, and we have from (1.7)
Er(R) == sup [-pR -log(GP*)] . O~p~l
Our objective is to explore the structure of optimal input distributions achieving either channel capacity or the random coding exponent Er(R). Instead of studying individual channel models, which have been the topics of numerous papers, we take a systematic approach to study these problems under very general channel conditions. We believe this viewpoint will clarify the our applications of optimization theory to information theory.
1.3. Assumptions and examples. The basis of our analysis is the structure of two sensitivity functions that may be interpreted as gradients with respect to J-l of the respective objective functions I(J-l) and GP(J-l). The channel sensitivity function is defined by gl'(X):= / log [p(y!x)/pl'(y)]p(y!x) dy,
x E lR,
(1.10)
where PJ-L was defined in (1.2), For each x, gJ-L(x) is the relative entropy between two probability distributions p(ylx) and PJ-L(Y). The error exponent sensitivity function is given by,
g~(X):= /
r
[/ J-t(dz)p(y!z)l j (l+ P) p(ylx)l j ( l+ p) dy,
x E X.
(1.11)
The following limit follows from elementary calculus,
_ I'
-gJ-L (x ) -
Ilfl P-'O
log g~ (x) P
,
x E JR.
The existence of a solution to (1.5) or (1.9) requires some conditions on the channel and its constraints. We list here the remaining assumptions imposed on the real channel in this paper. (Al) The input alphabet X is a closed subset of JR., Y == C or JR., and min(a~, M) < 00. (A2) For each n 2: 1, lim P(IYI Ixl-+oo
< niX == x) == O.
(A3) The function log(p( . I . )) is continuous on X x Y and, for any Y E Y, log(p(yl')) is analytic within the interior of X. Moreover, gJ-L is an analytic function within the interior of X, for any J-l E M(a~,M,X). Conditions (AI )-(A3) are also the standing conditions in [25, 26]. A complex channel model is more realistic in the majority of applications. We describe next a general complex model, defined by a transition
104
J.
HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
density p.(vlu) on C x C. The input is denoted U, the output V, with U E U == a closed subset of C, and V E V == C. The input and output are related by the transition density via,
P{V E dv I U == u} == p.(vlu) dv,
u,v E C.
The optimization problem (1.5) is unchanged: The average power constraint is given by E[IUI 2 ] ~ a~, and the peak-power constraint indicates that lUI ~ M, where Izi denotes the modulus of a complex number z E C. It is always assumed that the complex model is symmetric: symmetric: p. (v Iu)
== P. (ej v Iej u) , Q
u, v E C, a E IR.
Q
(1.12)
Under (1.12) we define, (i) X == lUI, X == U n IR+, and M again denotes probability distributions on B(X); (ii) For any J.l E M, we define J.l. as the symmetric distribution on C whose magnitude has distribution u. That is, we have the polarcoordinates representation,
1
J.l.(dx x da) == -J.l(dx) do , 27fx
x
> 0, 0 < a
< 27f,
(1.13)
and we set J.l( {O}) == J.l. ({O} ). This is denoted J.l~ in the special case J.l == <5 x . For each x E X, the distribution J.l~ coincides with the uniform distribution on the circle {z E
(iv) g/-L: lR+ ~ lR+ is defined as the channel sensitivity function corresponding to the transition density p. This may be expressed,
where J.l. and J.l correspond as in (ii). The symmetry condition (1.12) is a natural assumption in many applications since phase information is lost at high bandwidths. It is shown in [25] that in all of the standard complex channel models, Assumptions (A1)-(A3) hold for the corresponding real channel with input X == lUI. Moreover, both the capacity and random coding exponent Er(R) for the complex and real models coincide. We recall the most common channel models here:
The Rician channel This is the general complex fading channel, in which the input and output are related by, V:=(A+a)U+N
(1.14)
ENTROPY, INFERENCE, AND CHANNEL CODING
105
where U and V are the complex-valued channel input and output, a 2:: 0, and A and N are independent complex Gaussian random variables, A Nc(O, O"~) and N rv Nc(O, O"~). The Rician channel reduces to the complex AWGN channel when O"~ == o. Throughout this paper we assume that N and A are circularly symmetric. Consequently, V has a circularly symmetric distribution whenever the distribution of U is circularly symmetric. 0 f"V
On setting a == 0 in (1.14) we obtain another important special case:
The Rayleigh channel. The model (1.14) with a == 0 is known as the Rayleigh channel. Under our standing assumption that N, A have circularly symmetric distributions, it follows that the output distribution is symmetric for any input distribution (not necessarily symmetric.) Based on this property, the model may be normalized as follows, as in [2]: Setting X == IUIO" A/O"N and Y == IVI 2/O"~, we obtain a real channel model with transition density x, Y E IR+.
(1.15)
o The phase-noise channel. This noncoherent AWGN channel emerges in communication systems where it is not possible to provide a carrier phase reference at the receiver [28]. The channel model is represented by
V == Uej (} + N, where U and V are the complex-valued channel input and output, N is an independent complex Gaussian random variable with variance 20"~, and () is an independent random phase distributed uniformly on [-1r, 1r]. It is easy to see the input phase does not convey any information, and the mutual information is decided by the conditional probability density of the channel output amplitude Y given the channel input magnitude X,
y exp (y2 p(ylx) == -2-
«»
+2x 2 ) f o ( -2xy ) ,
2a N
«»
(1.16)
where f o is the zeroth-order modified Bessel function of the first kind. 0 The sensitivity function gp, is easily computed numerically for the Rayleigh or phase-noise channels based on (1.15) or (1.16). For the general Rician model, computation of gP, appears to be less straightforward since this requires computation of gP,e' which involves integration over the complex plane. The capacity-achieving input distribution is discrete under conditions imposed here when M is finite [25]. We find that the distribution optimizing the error exponent E r for a given positive rate R < C always has finite support, with or without a peak power constraint. Consequently,
106
J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
in the symmetric complex channel, the distribution is symmetric, and its magnitude has finite support. The following result provides a summary of results obtained for the real channel or the symmetric complex channel. The proof of Theorem 1.1 (ii) follows directly from Propositions 3.2 and 3.3. THEOREM 1.1. The following hold for the real channel model under Assumptions (Al)-{A3): (i) If M < 00 then there exists an optimizer f.1* of the convex program (1.5) definining capacity. The distribution J-L* has finite support. (ii) Consider the convex program (1.9) under the relaxed condition that min(a~, M) < 00. For each p there exists an optimizer J-L P , and any optimizer has finite support. Moreoever, for each R E (0, C) there exists p* achieving the maximum in (1. 7) so that,
Er(R) == -p* R -log(GP*) == -p* R -log(GP* (f.1P*)).
o The remainder of the paper is organized as follows: Section 2 reviews well known results on hypothesis testing, along with a promising new approach to robust hypothesis testing. The formulae for capacity and the random coding exponent are explained, based on results from robust and ordinary hypothesis testing. Section 3 contains results from [25, 26] showing why the capacityachieving input distribution and the distribution optimizing the error exponent are discrete. The numerical results contained in Section 4 show that the resulting codes can significantly out-perform traditional signal constellation schemes such as QAM and PSK. Section 5 concludes the paper.
2. Hypothesis testing and reliable communication. The focus of this section is to characterize optimal input distributions in hypothesis testing, channel capacity, and error exponents. A goal is to clarify the relationship between the solutions to these three optimization problems. In Section 2.1 we survey some results from [23, 6, 41] on asymptotic hypothesis testing based on Sanov's Theorem. These results will be used to set the stage for the convex analytic methods and geometric intuition to be applied in the remainder of the paper. We first briefly recall Sanov's Theorem: If X is a real-valued sequence, the empirical distributions are defined as the sequence of discrete probability distributions on B, 1 fN(A)
= N
N-l
L ll{X
k E
A},
AEB.
(2.1)
k=O
Suppose that X is i.i.d. with marginal distribution n, Sanoy's Theorem states that for any closed convex set A ~ M, lim -N-1logP{fN E A} == inf{D(f.1l1n) : f.1 E A}.
N-+-oo
ENTROPY, INFERENCE, AND CHANNEL CODING
107
The relative entropy is jointly convex on M x M, and hence computation of the minimum of D(p,lln) amounts to solving a convex program.
2.1. Neyman-Pearson hypothesis testing. Consider the binary hypothesis testing problem based on a finite number of observations from a sequence X == {Xt : t == 1, ... }, taking values in the set X == IR d . It is assumed that, conditioned on the hypotheses Hi, or HI, these observations are independent and identically distributed (i.i.d.). The marginal probability distribution on X is denoted n j under hypothesis H, for j == 0,1. The goal is to classify a given set of observations into one of the two hypotheses. For a given N ~ 1, suppose that a decision test ¢ N is constructed based on the finite set of measurements {Xl, ... , XN}. This may be expressed C XN . The test declares that as the characteristic function of a subset hypothesis HI is true if ¢N == 1, or equivalently, (X1,X2 , ... ,XN ) E Af'. The performance of a sequence of tests ¢ :== {¢N : N ~ I} is reflected in the error exponents for the type-II error probability and type-I error probability, defined respectively by,
Af
!4>
:== -lim inf N-Hx)
1 N log(P 11"1 (¢N(X I , . . . ,XN) == 0)),
1 J¢ :== -lim inf N log(P 11"0 (¢w(X1 , ... , X N ) N-HX)
= 1)).
The asymptotic N-P criterion of Hoeffding [23] is described as follows: For a given constant 7] ~ 0, an optimal test is the solution to the following optimization problem, sup I,
subject to
(2.2)
¢
where the supremum is over all test sequences ¢. The optimal value of the exponent I¢ in the asymptotic N-P problem is described in terms of relative entropy. It is shown in [41] that one may restrict to tests of the following form without loss of generality: for a closed set A ~ M, ¢N == TI{fN E A},
(2.3)
where [T N } denotes the sequence of empirical distributions (2.1). Sanov's Theorem tells us that for any test of this form,
For an arbitrary measure t: E M and for {3 E IR+, consider the divergence set,
(2.4)
108 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
j.l(log(l)) = j.l" (log (l ))
........................................................
Fig . 2: The Neyman-Pearson hypothesis testing problem. The likelihood ratio test is interpreted as a separating set between the convex sets Qf)(7l"0) and QI3"(7l"1).
The divergence set Qt(n) is a closed convex subset of M since D(· II .) is jointly convex and lower sem i-continuous on M x M. Consequently, from Sanov's Theorem the smallest set A that gives 14> ~ TJ is the divergence set A* = Q~(nO), and hence the solution to (2.2) is the value of the convex program,
Theorem 2.1 may be interpreted geometrically as follows. We have "'(* E Q~ (nO) n (n l), and the convex sets Q~ (nO) and (n l) are separated by the following set, which corresponds to the test sequence in
Qt"
Qt"
(2.7):
n=b
EM : ("'( , log £)
= ("'(* , log £)}.
This geometry is illustrated in Figure 2. THEOREM 2.1. Suppose that {nO,n l} have strictly positive densities on X = IR d , denoted {pO , pI}, and suppose that the optimal value of 14> in (2.2) is finite and non-zero. Then the following statements hold, (i) The optimal value of (2.2) is given by the minimal Kullback-Leibler divergence (3* given in (2.5). (ii) There exists p* > 0 such that the following alignment condition holds for the optimizer "'(* of (2.4):
d"'(* () * 1 d,,/* () (3* + P* T/, 1og dn 1 x + p og dn o x::;
x E X,
with equality almost everywhere. Consequently, the optimizer "'(* E Q~(nO) has density,
x E X, where k o > 0 is a normalizing constant.
(iii) {3* =
rr;~{ -PrJ -
(1 +
p) log(J (pO (x)) If,; (pI (x)) l~P dX) },
where the maximum is attained at the value of p" in (ii).
(2.6)
109
ENTROPY, INFERENCE, AND CHANNEL CODING
(iv) The following log-likelihood ratio test (LRT) is optimal, described as the general test (2.3) using the set, A:=={,EM:("logP) ~ jJ*-1]},
(2.7)
where P denotes the likelihood ratio P == d7fo / dn 1 . Proof Part (i) of Theorem 2.1 is due to Hoeffding [23]. This result follows from Sanov's Theorem as described above. Parts (ii) and (iii) were established in [6]. We sketch a proof here since similar ideas will be used later in the paper. To prove (ii) we construct a dual for the convex program (2.5). Consider the relaxation in which the constraint, E ('rrO) is relaxed through the introduction of a Lagrange multiplier p E IR+. The Lagrangian is denoted,
Qt
(2.8)
w:
and the dual function IR+ ~ IR is defined as the infimum of the Lagrangian over all probability distributions,
(2.9) An optimizer
,P can be characterized by taking directional derivatives. Let
, E Mbe arbitrary, and define
,e
== 0,
+ (1 -
P
d,P
O),p. Then the first order
condition for optimality is,
o~
de. I dO £(, ,p)
e=o
_
- \, - , ,log -d1 7f
+ P(log d,P d °- 1]) ). 7f
On setting, == 6x , the point-mass at x E X, we obtain the bound,
d,P
log dn 1 (x)
d,P + p log dno (x)
s: DhPlldn 1 ) + pDhPlldnO),
,*
,P
and on integrating both sides of this inequality with respect to we con== ,P*, where clude that equality holds a.e. [,P]. This proves (ii), with p* is chosen so that ,P* E Q~ (7f O) . Substituting the optimizer explicit expression for the dual,
,P into the Lagrangian (2.8) leads to an (2.10)
The term within the brackets is constant, which gives,
110 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
To complete the proof of (iii) we argue that {3* is the value of the dual, (3* == max{'!J(p) : p 2: O}.
Given this combined with the expression (2.10) for w(p) we obtain the representation (iii). Part (iv) follows from Sanov's Theorem and the geometry illustrated in Figure 2: The likelihood ratio test is interpreted as a separating set between the convex sets Q1J (7f O) and Qf3* (7f1 ). 0
Robust hypothesis testing. In typical applications it is unrealistic to assume precise values are known for the two marginals 7f o, 7f1. Consider the following relaxation in which hypothesis Hi corresponds to the assumption that the marginal distribution lies is a closed, affine subset Pi c M. A robust N-P hypothesis testing problem is formulated in which the worstcase type-II exponent is maximized over 7f1 E PI, subject to a uniform constraint on the type-I exponent over all 7fo E Po: subject to
inf
7roEPo
> TJ.
J7r O ¢ -
(2.11 )
A test is called optimal if it solves this optimization problem. The optimization problem (2.11) is considered in [34, 35, 33] in the special case in which the uncertainty sets are defined by specifying a finite number of generalized moments: A finite set of real-valued continuous functions {fj : i == 1, ... , n} and real constants {c~ : i == 1, ... , n} are given, and P i :==
{7f
EM: (7f,fj) == c~,
j
== 0, ... ,n},
i == 0,1.
(2.12)
As a notational convenience we take fo == 1 and c6 == 1. It is possible to construct a simple optimal test based on a linear function of the data. Although the test itself is not a log-likelihood test, it has a geometric interpretation that is entirely analogous to that given in Theorem 2.1. The value (3* in an optimal test can be expressed, (2.13)
Moreover, the infimum is achieved by some u" E Q~(Po) n Qt*(P I ) , along with least favorable distributions 7fo E Po, 7fi E PI, satisfying
The distribution J.-l* has the form J.-l*(x) == eo (x)7f o(x), where the function eo is a linear combination of the constraint functions {fi} used to define Po. The function log eo defines a separating hyperplane between the convex sets Q~ (Po) and Qt* (IP\), as illustrated in Figure 3.
111
ENTROPY, INFERENCE, AND CHANNEL CODING
...............................~ .::
:.:.:.: ;; f............ ·
_
..,:.:;.:.,:...::
,:
(J.l,log(io» = (J.l- , log(io)) .
Fig. 3: The two-moment worst-case hypothesis testing problem . The uncertainty classes P i, i = 0, 1 are determined by a finite number of linear constraints, and the thickened regions Q7/(lPo), Qt'- (lPI) are each convex. The linear thres hold test is interpreted as a separating hyperplane between these two convex sets .
Note that log f o is defined everywhere, yet in applications the likelihood rato df.L* jd7r may be defined only on a small subset of X. PROPOSITION 2.1. Suppose that the moment classes JIll o and JIll l each
o
satisfy the non-degeneracy condition that the vector (ch, , c~) lies in the relative interior of the set of all possible moments {f.L(Jo , , fn) : f.L EM}. Then, there exists {Ao, . . . , An} E lR such that the function f o = 2: Adi is non-negative valued, and the following test is optimal
rP'N = 0 {=:} ~
N -I
L 10g(fo(X d ) ::; n.
(2.14)
t=o
Proof The result is given as [34, Proposition 2.4]. We sketch the proof here, based on the convex geometry illustrated in Figure 3. Since (JIllo) and (JPlI) are compact sets it follows from their construction that there exists f.L* E Qt(JIllo)nQt-(JPll) ' Moreover, by convexity there exists some function h: X ~ lR defining a separating hyperplane between the sets Q;(JIllo) and Q;_ (JP>t) , satisfying
Qt
Qt-
The remainder of the proof consists of the identification of h using the Kuhn-Tucker alignment conditions based on consideration of a dual functional as in t he proof of Theorem 2.1. 0
2.2. Mutual information. In this section we derive the expression (1.5) for channel capacity based on Theorem 2.1, following ideas in Anantharam [3] (see also [12, 15].) Consider the decoding problem in which a set of N-dimensional code words are generated by a sequence of random variables with marginal distribution f.L . The receiver is given the output sequence {Yl , . . . YN} and considers an arbitrary sequence from the code book {xt,... X'j"}, where i is the index in a finite set {I , .. . , eNR} , where R is the rate of the code. Since Xi has marginal distribution f.L, Y has marginal distribution P/L defined in (1.2).
112 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI For each i, this decision process can be interpreted as a binary hypothesis testing problem in which Hi, is the hypothesis that {(X;, Yj) : j == 1, ... ,N} has marginal distribution
That is, Xi and Yare independent if codeword i was not sent. Hypothesis HI is the hypothesis that i is the true code word, so that the joint marginal distribution is 7f1
:== J-i, 8 p[dx, dy] :== J-i,(dx)p(ylx)dy.
Suppose that the error exponent TJ > 0 is given, and an optimal N-P LRT test is applied. Then I¢ == TJ means that,
== -
1 lim N log(P{Code word i is accepted
N~oo
Iii- i*}),
where the index i* denotes the code word sent. Consideration of eRN codewords, our interest lies in the probability that at least one of the eRN - 1 incorrect code words is mistaken for the true code word. We obtain through the union bound, P{The true code word i" is rejected}
:S" lim P{Code word i is accepted I i Z::
N-+oo
=1=
i*},
i#i*
from which we obtain, TJ - R ~ -
1 lim N 10g(P{The true code word i* is rejected}).
N-+oo
(2.15)
We must have R < 1] to ensure that right hand side is positive, so that the probability that the true code word i* is rejected vanishes as N ~ 00. One must also ensure that TJ is not too large, since it is necessary that {3* > 0 so that J¢ > 0 under the LRT. Hence an upper bound on R is the supremum over TJ satisfying {3* > 0, which is precisely mutual information:
This conclusion is illustrated in Figure 4. The channel capacity is defined to be the maximum of I over all input distributions J-i, satisfying the given constraints. We thus arrive at the convex program (1.5).
ENTROPY, INFERENCE , AND CHANNEL CODING
113
p.0p
.
I-" ~pl'
Fig. 4: The cha nnel capacity is equal to t he maximal relat ive ent ropy between PI' ® J10 and PI' 0 P, over all input d istribut ions /l satisfying t he given const rai nts .
2.3. Error exponents. A representation of the channel-coding random coding exponent can be obtained based on similar reasoning. Here we illustrate the form of the solut ion, and show that it may be cast as a robust hypothesis testing prob lem of the form considered in Section 2.1. For a given I-" E M , denot e by Po the space of product measures on
XxV, Po = {I-" 0
II : II
is a probability measur e on Y},
and define the corresp onding divergence set for a given R > 0,
v
Equivalently, Q"k(J!»o) = b: min, Db II I-" 0 lI) :s; R}. The robust hypothesis testing problem is binary, with HI as defined in the channel capacity problem , but with H o defined using Po: Ho: {(XJ, lj ) : j = 1, , N} has marginal distribution nO E Po. HI : {(XJ,lj ) : j = 1, , N} has marginal distribution n l := I-" 0 p. Proposition 2.2 shows th at the random coding exponent Er(R) can be repr esented as the solution to the robust N-P hypoth esis testing problem (2.11) with TJ = R and PI = {I-" 0 pl. PROPOSITION 2.2 . Er (R ) =
S~P(i~f { jJ : Qt(1-" 0
p) n Q"k(J!»o) f-
0}) .
(2.17)
Suppose that there exists a triple (1-"* , t/ " ; ')'*) that solve (2.17) in the sens e that
Th en, there exists a channe l transition density P such that ')'*
= 1-"* 0
P,
u" =
PI'·'
114 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI and the rate can be expressed as mutual information,
Proof Blahut in [6] establishes several representations for E r , beginning with the following
Er(R) == sup p,
inf
p,8PEQ~
D({l8p II {l8p)
(2.18)
where the supremum is over all {l, subject to the given constraints, and the infimum is over all transition densities p satisfying {l 8 PE Q~ where
Q"h :== {{l8 p : D({l8 p II {l Q9 pp,) < R}. The optimization problem (2.17) is a relaxation of (2.18) in which the distributions {v} in the definition of r o are constrained to be of the form PP" and the distributions {"'(} are constrained to be of the form {l 8 P for some transition density p. It remains to show that these restrictions hold for any solution to (2.17), so that the relaxed optimization problem (2.17) is equivalent to (2.18). For fixed u; denote the infimum over (3 in (2.17) by, (3* ({l) :== inf {(3 :
Q; ({l8 p) n Q"h (ro) f= 0}.
(2.19)
If (v*, "'(*) solve (2.19) in the sense that
D("'(*
II
{l8 p) == (3* ({l),
D("'(*
1/
{l Q9 v*) == R,
then the distribution "'(* solves the ordinary N-P hypothesis testing problem with nO == {l Q9 v* and n 1 == 11 8 p. It then follows that the first marginal "'(i is equal to {l by the representation given in Theorem 2.1 (ii). Moreover, the second marginal of "'(2 can be taken to be v* since for any t/,
These conclusions imply that "'(* == {l 8 P for some channel density p, and u" == PP" which establishes the desired equivalence between the optimiza0 tion problems (2.17) and (2.18). The solution to the optimization problem (2.19) is illustrated in Figure 5. The channel transition density p shown in the figure solves
(3* (11) == inf {(3 : Qt ({l8 p) n Q~(110 pp,)
f= 0}
== D(118p 11118P)· The error exponent is equal to the maximal relative entropy (3* ({l) over all u, and the rate can be expressed as mutual information R == I({l*;p) :== D(I1* 8 P II {l* 0 pp,) where 11* is the optimizing distribution.
ENTROPY, INFERENCE, AND CHANNEL CODING
115
Fig . 5: The error exponent. is equal to the solution of a robust. N-P hypothesis testing problem .
3. Convex optimization and channel coding. The alignment conditions for the N-P hypothesis testing problem were derived in Theorem 2.1 based on elementary calculus. Similar reasoning leads to alignment conditions characterizing channel capacity and the optimal error exponent. 3.1. Mutual information. Recall that the channel sensitivity function gJ.'(x) is the point-wise relative entropy, glJ.(x) := D(P( · I x)lIp(· I f-L)) . The next result, taken from [25], shows that glJ. is the gradient of I at f-L. 0 PROPOSITION 3.1. For any given f-L ,f-L E M((J"~,M,X), (i) I(f-L) = (f-L , glJ.) = max (f-L , gJ.'f) . IJ.'EM
(ii) Letting f-Lo := (1- ())f-L0 + ()f-L , the first-order sensitivity with respect to () E
[0, 1] is (3.1)
o The dual functional \It : JR+ ---. JR+ is defined by \It(r) = sup [I( f-L ) - r(f-L ,¢)],
r
2: 0 ,
(3.2)
IJ.EM o
where Mo = M(M 2 , M,X) = M(oo, M,X) denotes the constraint set without an average power constraint. The dual functional is a convex, decreasing function of r , as illustrated in Figure 6. Note that we do not exclude M = 00 . In this case, M o = M , which denotes the set of probability distributions on X. The parameter r provides a convenient parameterization of the optimization problem (1.5). The proof of Theorem 3.1. may be found in [25, Theorem 2.8]. THEOREM 3.1. If M < 00, then an optimizing distribution f-L; exists for (3.2) for each r > 0, and the following hold: (i) The alignment condition holds, g,dx) ::; \It(r) with equality a.e. [f-L; ].
+ r x2 ,
Ixl ::; M ,
116
J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
\11(1')
Co - 1'oa 2(1'o)
:
.
r TO
Fig. 6: The dual functional is convex and decreasing. For a given ro > 0, the slope determines an average power constraint a 2(ro), and the corresponding capacity Co :== C((T2(ro), M, X) may be determined as shown in the figure.
(ii) Let a 2(r) :== - ddT \lI(r). The distribution J-l; is optimal under the corresponding average power constraint:
Moreover, we have I(J-l;) == \lI(r) + ra 2(r). (iii) The capacity C( . , M, X) is concave in its first variable, with
d 2 -d 2 C(ap,M,X) == r, ap
o
3.2. Error exponents. Boundedness of the sensitivity function central to the analysis of [25]. LEMMA 3.1. 0 < g~(x) ~ 1 for each x, and g~ -4 0 as x -4 00. Continuity of GP follows easily from Lemma 3.1. The following set results establishes convexity and differentiability of GP with respect to For u, /Lo E M and 0 E [0,1] we denote /L{} :== (1 - O)J-l° + O/L. PROPOSITION 3.2. For any given u, J-l0 E M(a~, M, X) and p > 0, (i) For a given p, the mapping GP: M(a~, AI, X) r--t IR+ is continuous in the weak topology. (ii) The functional GP is convex, and can be expressed as the maximum of linear functionals,
is
0 of J-L.
(iii) Fix p 2: 0, /Lo EM. The first order sensitivity is given by
o For fixed p, the optimization problem (1.9) is a convex program since GP is convex. Continuity then leads to existence of an optimizer. The
ENTROPY, INFERENCE, AND CHANNEL CODING
117
0.77 0.75 0.74 0.73
0.72 0.71 l--_"""---_~_"""""___--'--
_
__'__~
X
Fig. 7: Numerical results for the Rayleigh channel Y = AX constraint for rate R < C, with O"~ = O"J..., = 1 and p = 0.5.
+N
subject to peak-power
following result from [26] summarizes the structure of the optimal input distribution. It is similar to Theorem 3.1 which requires the peak power constraint M < 00. We stress that this condition is not required here. THEOREM 3.2. For each p ~ 0, there exists J-LP E M((J~,M,X) that achieves GP*. Moreover, a distribution J-L0 E M((J~,M,X) is optimal if and only if there exists a real number Ai and a positive real number A2 such that
If thes e conditions hold, then
o Shown in Figure 7 are plots of g~ for two distributions. The input distribution J-Lo violates the alignment condition in Theorem 3.2 (ii), and hence is not optimal. The alignment condition does hold for J-Ll, and we conclude that this distribution does optimize (1.5). PROPOSITION 3.3. For given p, any optimal input distribution J-L* achieving GP* is discrete, with a finite number of mass points in any interval. Proof To see that the optimizer g~* is discrete consider the alignment conditions. There exists a quadratic function q* satisfying q*(x) ::; g~* (x), with equality a.e. [J-L*]. Lemma 3.1 asserts that g~* takes on strictly positive values and vanishes at infinity. It follows that q* is not a constant function, and hence q*(x) --+ -00 as x --+ 00. This shows that the optimizer has bounded support, with
Moreover, since g~* is an analytic function on X it then follows that g~* (x) == q*(x) is only possible for a finite number of points. 0
118 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
Optimal binary distributions. Gallager in [19] bounds the random coding exponent by a linear functional over the space of probability measures. The bound is shown to be tight for low SNR, and thus the error exponent optimization problem is converted to a linear program over the space of probability measures. An optimizer is an extreme point, which is shown to be binary. Similar arguments used in [25] can be generalized to the model considered here. We begin with consideration of zero SNR, which leads us to consider the senstivity function using J..L == 60, the point mass at 0, denoted 9g :== 9~o(X). It is easy to see 9g(0) == 1, and we have seen that 9g(X) ~ 1 everywhere. Given the analyticity assumption, it follows that this function has zero derivative at the origin, and non-positive second derivative. We thus obtain the bound, dlog(l - 9g(X)) I > 2, dlog(x) x=o with equality holding if and only if the second derivative of 9g (x) is non-zero at x == O. We have the following proposition concerning the binary distribution at low SNR. This extends Theorem 3.4 of [25] which covers channel capacity. However, unlike this previous result and the result of [19], we do not require a peak power constraint on the input distribution. PROPOSITION 3.4. Consider a channel with X == IR+. For a fixed p > 0, suppose that the following hold,
(i) dd;29b (0) == O. (ii) There is a unique
Xl
>0
satisfying
dlog(1 - 9g(X)) d log(x) (iii) There is 'positive sensitivity' at
I
== 2.
X=Xl
Xl:
~ (dlog(l - 9g(X))) I dx
dlog(x)
:f O.
X=Xl
Then, for all SNR sufficiently small, the optimal input distribution is binary with one point at the origin. 0 The proof of Proposition 3.4 may be found in [26]. We illustrate the proof and its assumptions using the Rayleigh channel. Given the channel transition probability function (1.15), the sensitivity function is, X ~
O.
ENTROPY, INFERENCE, AND CHANNEL CODING g~(x)
dlog(l- 9b(X)) dlog(:r)
qp. (X) quadratic
", , " ,, ,
119
'iii:
2
----------------
-------------
Xl
,, , 0.5
gb
Fig. 8: Optimal binary distribution for the Rayleigh channel. At left is a plot of together with the quadratic function aligned with The two functions meet at only two points. Shown at right is a plot of the log-derivative: The nonzero point of support for the optimal binary input is found by setting this equal to 2.
gb .
From the plot shown at left in Figure 8 we see that there exists a quadratic function qo satisfying qo (x) ~ gg (x), with equality at the origin and precisely one Xl > o. The plot at right shows that (iii) holds, and hence that all of the assumptions of Proposition 3.4 are satisfied. Consequently, with vanishing SNR, the optimizing distribution is binary, and approximates the binary distribution supported on {O,Xl}.
4. Signal constellation design. We now show how the conclusions of this paper may be applied in design. For a symmetric, complex channel we have seen in Theorem 1.1 that the optimal input distribution is circularly symmetric on C, and discrete in magnitude. We consider in this section discrete approximations of this optimal distribution on C. We propose the following approach to signal constellation design and coding in which the signal alphabet and associated probabilities are chosen to provide a random code that approximates the random code obtained through the nonlinear program (1.5). We conclude this paper with examples to illustrate the performance of this approach, as compared to standard approaches based on QAM or PSK. Complex A WGN channel. This is the complex channel model given by Y == X + N with N complex Gaussian. Examples considered in [7] suggest that QAM typically outperforms PSK when the constellation sizes are fixed, and the signal to noise ratio is large. For small SNR, it is known that QAM and PSK are almost optimal (see [7, Figure 7.11], [40], and related results in [37]). Figure 9 shows results using two signal constellation methods: 4-point QAM and a 5-point distribution which contains the 4-point QAM plus a point at origin. The 5 point distribution is an approximation to the optimal input distribution, which is binary in magnitude, and uniformly distributed in phase. The 5-point constellation performs better than 4-point QAM by about 13%, with lower power consumption, 0
120
J. HUANG, C. PANDIT, S.P, MEYN, M. MEDARD, AND V. VEERAVALLI
• :3
..
•
It
.'
'3
0
'.
.'
Fig. 9: Left: the 4-point QAM signal constellation for complex AWGN channel Y == X + N, with u~ == 9 and uJv == 1, i.e. SNR == 9 (9.54dB). The mutual information achieved by this 4-point QAM is 1.38 nats/syrnbol. Right: A 5-point constellation signal constellation for complex AWGN channel Y == X + N, with uJv == 1, with 4 points (with equal probability) at the same position as QAM plus one point at origin with probability equal to 0,1077. The constellation achieves 1.52 nata/symbol mutual information.
1.71
5.31
: 5
Fig. 10: Left: the 16-point QAM signal constellation for Rayleigh channel Y == AX + N, with u~ == 1, CTJv == 1, and average power constraint u~ == 11.7. The mutual information achieved is 0.1951 nata/symbol. Right: A 2-point constellation with one point at origin (with probability 0.5346) and another point with magnitude 5, for the same channel model and average power constraint. The mutual information achieved is 0,4879 nata/symbol, which is 2.5 times more than that achieved by the 16-point QAM.
Rayleigh channel with low SNR. We consider the normalized model in which A, N are each Gaussian, mutually independent, and circularly symmetric, with O"~ == 1, O"Jv == 1. Consideration of the magnitude of X and Y leads to the real channel model with transition density shown in (1.15). We compare codes obtained from the two constellations illustrated in Figure 10. The first constellation is a 16-point QAM. Since the code used in QAM is a random code with uniform distribution, the average power is given by (J~ == 11.7. The second constellation has only two elements: one point at origin and another point at position 5 E C. The weights are chosen so that the average power is again (J~ == 11.7, which results in fL{O} == 1- fL{5} == 0.5346. This is the optimal input distribution when the peak-power constraint M == 5 is imposed.
121
ENTROPY, INFERENCE, AND CHANNEL CODING
2.57
7.71
:2.7
:8
Fig. 11: The plot at left shows the 16-point QAM signal constellation, and at right is shown a three-point constellation with one point at origin; one point on a circle of radius 2.57; and the third point on a circle of radius 8. The respective probabilities are uniform for the QAM code, and given by (0.5346,0.1379,0.397) for the respective codewords in the three-point constellation.
Computations show that the simpler coding scheme achieves mutual information 0.4879 nata/symbol, which is about 2.5 times more than the mutual information achieved by the 16-point QAM code. 0
Rayleigh channel with high SNR. In this final example the same parameters used in the previous experiment are maintained, except now the average power is increased to a~ == 26.4. The optimal input distribution is given as follows when the channel is subject to the peak power constraint IX/ ~ 8: The phase may be taken uniformly distributed without any loss of generality, and the magnitude has three points of support at {D.O, 2.7, 8.0} with respective probabilities {0.465, 0.138, 0.397}. Consequently, we propose a constellation whose magnitude is restricted to these three radii. This is compared to 16-point QAM. The two constellation designs are illustrated in Figure 11. If the probability weights {0.465, 0.138, 0.397} are used in the proposed constellation design, then the resulting mutual information is 0.5956 nata/symbol, which is about 3 times larger than the mutual information achieved by the 16-point QAM. 0 5. Conclusions. Many problems in information theory may be cast as a convex program over a set of probability distributions. Here we have seen three: hypothesis testing, channel capacity, and computation of the random coding exponent. Another example considered in [24] is computation of the distortion function in source coding. Although the optimization problem in each case is infinite dimensional when the state space is not finite, in each example we have considered it is possible to construct a finite dimensional algorithm, and convergence is typically very fast. We believe this is in part due to the extremal nature of optimizers. Since optimizers
122 J. HUANG, C. PANDIT, S.P. MEYN, M. MEDARD, AND V. VEERAVALLI
have few points of support, this means the optimizer is on the boundary of the constraint set, and hence sensitivity is typically non-zero. There are many unanswered questions: (i) The theory described here sets the stage for further research on channel sensitivity. For example, how sensitive is the error exponent to SNR, coherence, channel memory, or other parameters. (ii) It is possible to extend most of these results to multiple access channels. However, we have not yet extended the cutting plane algorithm to MIMO channels, and we don't know if the resulting algorithms will be computationally feasible. (iii) Can we apply the results and algorithms we have here to adaptively construct efficient constellations for fading channels?
REFERENCES [1] I.C. ABOU-FAYCAL, M.D. TROTT, AND S. SHAMAI. The capcity of discrete-time memoryless Rayleigh-fading channels. TIT, 47(4):1290-1301, May 2001. [2] I.C. ABOU-FAYCAL, M.D. TROTT, AND S. SHAMAI. The capacity of discretetime memoryless Rayleigh-fading channels. IEEE Trans. Inform. Theory, 47( 4):1290-1301, 2001. [3] V. ANANTHARAM. A large deviations approach to error exponents in source coding and hypothesis testing. IEEE Trans. Inform. Theory, 36(4):938-943, 1990. [4] R"R. BAHADUR. Some Limit Theorems in Statistics. SIAM, Philadelphia, PA, 1971. [5] D.P. BERTSEKAS. Nonlinear Programming. Athena Scientific, Belmont, MA, 1999. [6] R.E. BLAHUT. Hypothesis testing and information theory. IEEE Trans. Information Theory, IT-20:405-417, 1974. [7] R.E BLAHUT. Principles and Practice of Information Theory. McGraw-Hill, New York, 1995. [8] .I.M, BORWEIN AND A.S. LEWIS. A survey of convergence results for maximum entropy. In A. Mohammad-Djafari and G. Demoment, editors, Maximum Entropy and Bayesian Methods, pp. 39-48. Kluwer Academic, Dordrecht, 1993. [9] S. BOYD AND L. VANDENBERGHE. Convex Optimization. Cambridge University Press, Cambridge, 2004. [10] T.H. CHAN, S. HRANILOVIC, AND F.R. KSCHISCHANG. Capacity-achieving probability measure for conditionally Gaussian channels with bounded inputs. to appear on IEEE Trans. Inform. Theory, 2004. [IIJ RONG-RONG CHEN, B. HAJEK, R. KOETTER, AND U. MADHOW. On fixed input distributions for noncoherent communication over high SNR Rayleigh fading channels. IEEE Trans. Inform. Theory, 50(12):3390-3396, 2004. [12] T. COVER AND J. THOMAS. Elements of Information Theory. Wiley, New York, 1991. [13] I. CSISZAR. Sanov property, generalized I -projection and a conditional limit theorem. Ann. Probab., 12(3):768-