Title: Dynamic rate control methods and apparatus for scheduling data transmissions in a communication network
Abstract: The scheduling of data transmissions for a CDMA system downlink or other type of communication network is implemented on a dynamic basis using a revenue-based policy. For a given transmission slot or other transmission interval, a maximum-rate user is identified from among a set of users requesting data transmissions, and a data transmission of the maximum-rate user is scheduled for the given interval. The maximum-rate user is identified based on application of coefficients of a revenue vector to corresponding feasible rates of the requesting users. The revenue vector is determined in an iterative manner using an adaptive algorithm which updates the revenue vector periodically to compensate for observed deviations between actual and target throughput, such that the deviations are reduced over time and the revenue vector converges to an optimal revenue vector. Advantageously, the invention allows the revenue vector to be determined without direct estimation of the frequency of occurrence of particular user rates.
Patent Number: 7,006,466 Issued on 02/28/2006 to Borst, et al.
| Inventors:
|
Borst; Simon C. (Amsterdam, NL);
Whiting; Philip Alfred (New Providence, NJ)
|
| Assignee:
|
Lucent Technologies Inc. (Murray Hill, NJ)
|
| Appl. No.:
|
803247 |
| Filed:
|
March 9, 2001 |
| Current U.S. Class: |
370/329; 370/352; 370/412 |
| Current Intern'l Class: |
H04Q 7/00 (20060101) |
| Field of Search: |
370/348,229-230,232,335,342,412,443,252,337,347,329
455/450,452.1,452.2
|
References Cited [Referenced By]
U.S. Patent Documents
| 5914950 | Jun., 1999 | Tiedemann et al.
| |
| 6072792 | Jun., 2000 | Mazur et al.
| |
| 6590890 | Jul., 2003 | Stolyar et al.
| |
| 6721278 | Apr., 2004 | Rimhagen et al.
| |
| 2003/0185224 | Oct., 2003 | Ramanan et al.
| |
| Foreign Patent Documents |
| WO 95/3498/1 | Dec., 1995 | EP.
| |
Other References
U.S. Appl. No. 09/517,659, filed Mar. 3, 2000, S. Stolyar et al., "Method of
Packet Scheduling, With Improved Delay Performance, for Wireless Networks.".
U.S. Appl. No. 09/393,949, filed Sep. 10, 1999, K. Ramanan et al., "Method and
Apparatus for Scheduling Traffic to Meet Quality of Service Requirements in a Communication Network.".
A. Bedekar et al., "Downlink Scheduling in CDMA Data Networks," Proc. IEEE Globecom
'99, pp. 1-32, 1999.
P. Bender et al., "CDMA/HDR: A Bandwidth-Efficient High-Speed Wireless Data Service
for Nomadic Users," IEEE Communications Magazine, vol. 38, pp. 70-77, 2000.
U.S. Appl. No. 09/517,659, filed Mar. 3, 2000, S. Stolyar et al., "Method of
Packet Scheduling, With Improved Delay Performance, for Wireless Networks.".
P. Bender et al., "CDMA/HDR: A Bandwidth Efficient High Speed Wireless Data Service
for Nomadic Users," QUALCOMM, pp. 1-34, undated.
A. Bedekar et al., "Downlink Scheduling in CDMA Data Networks," Proc. IEEE Globecom
'99, pp. 1-32, 1999.
P. Bender et al., "CDMA/HDR: A Bandwidth-Efficient High-Speed Wireless Data Service
for Nomadic Users," IEEE Communications Magazine, vol. 38, pp. 70-77, 2000.
|
Primary Examiner: Phunkulh; Bob
Assistant Examiner: Wilson; Robert W.
Claims
What is claimed is:
1. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the adaptive algorithm starts from an arbitrary initial revenue vector
and iteratively adjusts the coefficients of the revenue vector to compensate for
observed deviations between actual and target throughput, such that the deviations
are reduced over time and the revenue vector converges to an optimal revenue vector.
2. The method of claim 1 wherein the communication network comprises a wireless
communication system, and the data transmissions comprise downlink data transmissions
from a given base station of the system to users of the system.
3. The method of claim 1 wherein the revenue vector is determined without direct
estimation of the frequency of occurrence of particular user rates.
4. The method of claim 1 wherein at least a subset of the transmission intervals
comprise fixed-duration transmission slots, with a data transmission for only one
of the users occurring within a given one of the transmission slots.
5. The method of claim 4 wherein the adaptive algorithm updates the revenue vector
based on randomly-selected transmission intervals.
6. The method of claim 1 wherein the identifying and scheduling steps are applied
jointly to multiple users including at least one user at each of a plurality of
base stations of the communication network.
7. The method of claim 1 wherein the identifying and scheduling steps are applied
so as to take into account diversity antennas associated with one or more base
stations of the communication network.
8. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the maximum-rate user for which a data transmission is scheduled in an
n-th transmission interval is a user m*(n) identified as follows:
##EQU37##
where w
1, . . . , w
M denote the coefficients of a revenue
vector w, and R
m(n) denotes the feasible rate for an m-th one of M users.
9. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the feasible rates for Musers comprise a set of feasible rates (R
1,
. . . , R
M) having a discrete distribution on a bounded set J
⊂##CHR4##
M.
10. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the feasible rates for M users comprise a set of feasible rates (R
1,
. . . , R
M) having a continuous distribution on a bounded set U
⊂##CHR5##
M.
11. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the adaptive algorithm adjusts one or more of the coefficients of the
revenue vector in accordance with a specified step size δ
k in
the form of a predetermined convergent sequence.
12. The method of claim 11 wherein the predetermined convergent sequence comprises
a sequence δ
k+1=δ
1ρ
k with ρ<1.
13. The method of claim 11 wherein the predetermined convergent sequence comprises
a sequence δ
k=δ
1k
-β with β>1.
14. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the adaptive algorithm updates the revenue vector based on sample periods
which increase in size as a function of time.
15. The method of claim 14 wherein the updates to the revenue vector occur at
predetermined slots K(n), with the length of an n-th sample period given by L(n):=K(n+1)-K(n).
16. The method of claim 14 wherein the adaptive algorithm updates the revenue
vector w(n) for an n-th sample period in accordance with an update direction v(w(n))
based on throughput obtained during the n-th sample period when the revenue vector
w(n) is used, and further wherein at a subsequent update of the revenue vector
for an (n+1)-th sample period, the revenue vector is recursively determined as
w(
n+1)=
w(
n)-δ(
n)
v(
w(
n)),
where δ(n) denotes a step size of a predetermined convergent sequence.
17. The method of claim 16 wherein the update direction v(w(n)) is determined
by averaging the actual throughput for each user over the sample period, partitioning
the users into a first group with above-average throughput and a second group with
below-average throughput, decreasing the revenue vector coefficient values for
the users in the first group, and increasing the revenue vector coefficient values
for the users in the second group, such that as the size of the sample period increases,
the actual throughputs will approach specified target throughputs.
18. A method of scheduling data transmissions in a communication network, the
method comprising the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the adaptive algorithm comprises at least one of an Update-Extreme algorithm
and a Move-to-Average algorithm.
19. An apparatus for scheduling data transmissions in a communication network,
the apparatus comprising:
a processor operative to identify for a given transmission interval a particular
user from among a plurality of users requesting data transmissions, the particular
user being identified as a maximum-rate user after application of coefficients
of a revenue vector to corresponding feasible rates of the plurality of users,
the revenue vector being determined in an iterative manner using an adaptive algorithm;and
to schedule a data transmission of the particular user for the given transmission
interval; and
a memory coupled to the processor, the memory storing at least a portion of the
revenue vector;
wherein the adaptive algorithm starts from an arbitrary initial revenue vector
and iteratively adjusts the coefficients of the revenue vector to compensate for
observed deviations between actual and target throughput, such that the deviations
are reduced over time and the revenue vector converges to an optimal revenue vector.
20. A machine-readable storage medium having one or more programs stored therein
for use in scheduling data transmissions in a communication network, wherein the
one or more programs when executed implement the steps of:
identifying for a given transmission interval a particular user from among a
plurality of users requesting data transmissions, the particular user being identified
as a maximum-rate user after application of coefficients of a revenue vector to
corresponding feasible rates of the plurality of users, the revenue vector being
determined in an iterative manner using an adaptive algorithm; and
scheduling a data transmission of the particular user for the given transmission interval;
wherein the adaptive algorithm starts from an arbitrary initial revenue vector
and iteratively adjusts the coefficients of the revenue vector to compensate for
observed deviations between actual and target throughput, such that the deviations
are reduced over time and the revenue vector converges to an optimal revenue vector.
Description
RELATED APPLICATIONS
The present invention is related to the inventions described in U.S. patent application
Ser. No. 09/517,659 filed in the name of inventors S. Stolyar et al. and entitled
"Method of Packet Scheduling, With Improved Delay Performance, for Wireless Networks,"
now issued as U.S. Pat. No. 6,590,890, and U.S. patent application Ser. No. 09/393,949
filed Sep. 10, 1999 in the name of inventors K. Ramanan et al. and entitled "Method
and Apparatus for Scheduling Traffic to Meet Quality of Service Requirements in
a Communication Network," both of which are commonly assigned herewith and incorporated
by reference herein.
1. Field of the Invention
The present invention relates generally to wireless communication systems and
more particularly to techniques for scheduling data transmissions in wireless code
division multiple access (CDMA) wireless systems and other types of communication networks.
2. Background of the Invention
Next-generation wireless networks are expected to support a wide
range of services, including high-rate data applications. Examples of such wireless
networks include those CDMA systems known in the art as IS-95B, cdma2000, third
generation (3G), Universal Mobile Telephone System (UMTS) and wideband CDMA (WCDMA)
systems. The high-rate data applications to be supported by these networks are
generally characterized by bursty traffic. Moreover, in contrast to voice users,
data applications can usually accept a certain amount of packet delay, as long
as sufficient data throughput is provided over a particular interval. As a result
of the bursty traffic and relative delay intolerance of data applications, scheduling
techniques can be particularly effective in optimizing system throughput for such applications.
An example of a conventional scheduling technique particularly directed to the
scheduling of high-rate data transmissions on a base-to-mobile link, i.e., downlink,
of a CDMA system is described in A. Bedekar et al., "Downlink scheduling in CDMA
data networks," Proc. IEEE Globecom '99, pp.2653-2657, 1999, which is incorporated
by reference herein. Related techniques maybe applied in low-mobility scenarios,
such as indoor networks. In such environments, Rayleigh fading frequencies can
be quite low, and the fading levels can even be anticipated to some extent. For
example, fading can be measured by having the base station provide a pilot signal
which can be measured by all the users and utilized to generate corresponding signal-to-noise
ratios (SNRs). The measurements can be fed back to the base station, and used to
estimate fading levels and SNRs, and hence user rates, in subsequent slots. It
is therefore possible to exploit the variations in the channel conditions so as
to transmit to the user with the currently "best" channel. This type of an approach
is utilized in the High Data Rate (HDR) technique developed by Qualconum. More
particularly, in such a technique mobile users may be configured to make measurements
on a common pilot signal, and to report the measurements on a dedicated uplink
channel, e.g., a 3.2 kbps dedicated uplink channel. These and other aspects of
the HDR technique are described in greater detail in P. Bender et al., "CDMA/HDR:
a bandwidth-efficient high-speed wireless data service for nomadic users," IEEE
Communications Magazine, Vol. 38, pp. 70-77, 2000, which is incorporated by reference herein.
The above-noted estimates of user rates for subsequent slots can provide a basis
for scheduling user transmissions. However, the estimates fail to provide the probability
that each user will have a given SNR and a potential maximum rate. Although it
is possible to determine such probabilities from a joint distribution of user rate
declarations, this would generally involve keeping records from slot to slot of
the user rate declarations, and building up a relative frequency table, and would
thus require excessive computational and memory resources in a practical system
implementation. A need therefore exists for improved techniques for scheduling
high-rate data transmissions, on a CDMA downlink or other type of communication
network link, without requiring direct estimation of the frequency of occurrence
of particular user rates.
SUMMARY OF THE INVENTION
The invention provides methods and apparatus for scheduling data transmissions
in CDMA systems and other types of communication networks.
In accordance with one aspect of the invention, the scheduling of data transmissions
for a CDMA system downlink or other type of communication network is implemented
using a revenue-based policy. For a given transmission slot or other transmission
interval, a maximum-rate user is identified from among a set of users requesting
data transmissions, and a data transmission of the maximum-rate user is scheduled
for the given interval. The maximum-rate user is identified based on application
of coefficients of a revenue vector to corresponding feasible rates of the requesting
users. The revenue vector is determined in an iterative manner using an adaptive
algorithm which updates the revenue vector periodically to compensate for observed
deviations between actual and target throughput. As a result, the deviations are
reduced over time and the revenue vector converges to an optimal revenue vector.
Advantageously, the revenue vector can be determined without direct estimation
of the frequency of occurrence of particular user rates.
In accordance with another aspect of the invention, the maximum-rate user for
which a data transmission is scheduled in an n-th transmission interval is a user
m*(n) identified as follows:
##EQU1##
where w
1, . . , w
M denote the coefficients of a revenue
vector w, and R
m(n) denotes the feasible rate for an m-th one of M users
for the n-th transmission interval.
In accordance with a further aspect of the invention, convergence of the revenue
vector to its optimal value is ensured by the adaptive algorithm periodically adjusting
the coefficients of the revenue vector in accordance with a specified step size
taken from a predetermined convergent sequence.
In accordance with yet another aspect of the invention, the adaptive algorithm
updates the revenue vector based on sample periods which increase in size as a
function of time. For example, the updates to the revenue vector occur at predetermined
slots K(n), with the length of an n-th sample period given by L(n):=K(n+1)-K(n).
The adaptive algorithm may be configured to update the revenue vector w(n) for
an n-th sample period in accordance with an update direction v(w(n)). The update
direction is determined based on throughput obtained during the n-th sample period
when the revenue vector w(n) is used. At a subsequent update of the revenue vector
for an (n+1)-th sample period, the revenue vector is recursively determined as
w(
n+1)=
w(
n)-δ(
n)
v(
w(
n)),
where δ(n) denotes a step size of the above-noted predetermined convergent
sequence. The update direction v(w(n)) may be determined by averaging the actual
throughput for each user over the sample period, partitioning the users into a
first group with above-average throughput and a second group with below-average
throughput, decreasing the revenue vector coefficient values for the users in the
first group, and increasing the revenue vector coefficient values for the users
in the second group. As the size of the sample period increases, the actual throughputs
will approach specified target throughputs.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows an exemplary code division multiple access (CDMA) wireless communication
system in which a technique for scheduling of data transmissions in accordance
with the invention is implemented.
FIG. 2 is a block diagram showing a base station which is utilized in the FIG.
1 system for scheduling data transmissions in accordance with the invention.
FIG. 3 is a flow diagram of the a data transmission scheduling process that
is implemented in the base station of FIG. 2.
FIG. 4 shows a plot of expected throughput per time slot as a function of revenue
vector coefficient for an example two-user case.
DETAILED DESCRIPTION OF THE INVENTION
The present invention will be illustrated below in conjunction with an exemplary
code division multiple access (CDMA) wireless communication system. It should be
understood, however, that the invention is not limited to use with any particular
type of communication system, but is instead more generally applicable to any wireless
system in which it is desirable to provide improved scheduling of data transmissions.
For example, although the techniques are illustrated with reference to certain
types of CDMA systems, it will be apparent to those skilled in the art that the
techniques are also applicable to other CDMA systems, as well as to other types
of wireless systems and communication networks.
EXAMPLE SYSTEM
FIG. 1 shows an exemplary CDMA wireless cellular system 10 in which a
data transmission scheduling technique of the invention is implemented. The system
10 may be configured in accordance with well-known conventional wireless
communication system standards. The system 10 as illustrated includes a
mobile station (MS) 12 and a number of base stations BS1, BS2,
BS3 and BS4. The base station BS1 of FIG. 1 represents a primary
base station, communicating with mobile station 12 via the path designated
by solid two-way arrow 24, while the surrounding base stations BS2,
BS3 and BS4 may serve as secondary base stations which can detect
signals transmitted via the paths indicated by dashed one-way arrows 26.
The primary base station BS1 communicates with the mobile station 12
using CDMA techniques that are well known in the art. As the mobile station 12
moves within the system 10, handoffs occur, such that base stations other
than BS1 become primary base stations for communicating with the mobile
station 12. Also, handoffs may occur from a given antenna sector of the
primary base station and another sector of that base station.
Transmissions from a given base station of the system 10 to
the mobile station 12 are referred to as base-to-mobile or downlink transmissions.
Transmissions from the mobile station 12 to a given base station of the
system 10 are referred to as mobile-to-base or uplink transmissions.
The system 10 in this illustrative embodiment also includes first and
second mobile switching centers (MSCs) 14-1 and 14-2.
A given MSC typically connects several BSs with a public switched telephone network
(PSTN) 16. For example, MSC 14-1 connects base stations BSI
and BS2 with the PSTN 16 and MSC 14-2 connects base
stations BS3 and BS4 with the PSTN 16. The system 10
also includes a memory 18 having a number of registers including a home
location register (HLR) 20 and a visitor location register (VLR) 22.
The HLR 20 and VLR 22 store user data and billing information for
each mobile station 12 of the system 10.
The system of FIG. 1 is shown in simplified form for purposes of illustration,
and will generally include a substantially larger number of base stations and mobile
stations, as well as other system elements that are not explicitly shown in the
figure. Each of the mobile stations within the system is more generally referred
to herein as a "user." It should be noted that the term "user" is intended to include
not only mobile stations, but also any other type of subscriber unit of a given
system, including, e.g., fixed wireless subscriber units.
FIG. 2 shows a more detailed view of an apparatus which represents a given one
of the base stations BS1, BS2, BS3 or BS4 of the system
10. The apparatus includes an antenna 32 which receives signals from
and transmits signals to other elements of the system 10. A receive signal
is directed by a diplexer filter 33 to an input of a receiver 34
which may implement conventional downconversion, demodulation, digital-to-analog
conversion and other processing of the receive signal. A transmitter 35
performs complementary operations such as analog-to-digital conversion, modulation
and upconversion to generate a transmit signal which is directed via diplexer 33
to the antenna 32 for transmission.
A processor 36 is coupled to both the receiver 34 and the transmitter
35. The processor 36 operates in conjunction with a memory 38
to control the communication functions of the base station BSi. For example, data
or other information in messages which are part of a receive signal may be supplied
to or otherwise processed by a processor 36 such that processor 36
can implement data transmission scheduling techniques to be described in greater
detail below.
General Scheduling Approach
The present invention provides improved techniques for scheduling of high-rate
downlink data transmissions in a CDMA wireless system such as that illustrated
in conjunction with FIGS. 1 and 2. Advantageously, the techniques of the invention
avoid the need for direct estimation of the frequency of occurrence of particular
user rates.
As previously noted, conventional scheduling techniques for high-rate data transmissions
on a CDMA downlink may be configured to estimate the channel conditions, and to
transmit to the user with the currently "best" channel. In accordance with an illustrative
embodiment of the invention, the user having the "best" channel may be identified
as a maximum-rate user when a set of feasible rates are weighed with appropriately-determined
coefficients. Each of these coefficients may be viewed as a particular price or
other reward value in a revenue vector, and the data transmission scheduling may
then be viewed as a revenue-based policy which always assigns an available transmission
slot to the user yielding the maximum revenue. The term "coefficient" as used herein
in conjunction with a revenue vector is intended to include a price, reward value
or any other revenue-related value that may comprise an element of the revenue
vector. As will be described in detail below, the revenue vector coefficients are
used to weight a set of feasible rates for system users eligible for data transmission,
and are adjusted over time such that actual throughput ratios converge to target
throughput ratios.
It should be noted that direct calculation of an optimal revenue vector of the
type described above may be a difficult task, in that such direct calculation will
generally require detailed information on the channel statistics. The present invention
avoids such direct calculation by providing adaptive algorithms for determining
the optimal revenue vector in an iterative manner, without the need for direct
estimation of the frequency of occurrence of particular user rates. Starting from
an arbitrary initial vector, the algorithms iteratively adjust the revenue vector
coefficients to compensate for observed deviations from target throughput ratios.
The adjustments ensure that discrepancies between actual and target throughput
cannot persist, and are gradually reduced in size over time such that the revenue
vector converges to the optimal revenue vector.
The illustrative embodiment will be described in conjunction with a base station
serving M data users. The base station transmits in slots of fixed duration in
this embodiment, although transmission intervals other than fixed-duration slots
may be used in other embodiments. In each slot, the base station transmits to exactly
one of the users. It is assumed that the feasible rates for the various users vary
over time according to a stationary discrete-time stochastic process {(R
1(n),
. . . , R
M(n)}, n=1, 2, . . . , with R
m(n) representing the
feasible rate for user m in the n-th slot. It is assumed that the base station
has perfect knowledge of the maximum feasible rate R
m(n) for user m
at the start of the n-th slot. Let (R
1 . . . , R
M) be a random
vector with a distribution corresponding to the joint stationary distribution of
the feasible rates.
It should be noted that these and other assumptions made herein are for purposes
of simplification and clarification of the description, and should not be construed
as limiting the scope of the invention in any way. Alternative embodiments in which
one or more of the assumptions do not apply will be apparent to those skilled in
the art.
The above description allows for dependence between the feasible rates for the
various users.
Independence may be a reasonable assumption in the case of an isolated
base station serving a group of independent users. In the case of several base
stations, however, the feasible rates may vary not only due to independent fading,
but also because of the common impact of control actions at adjacent base stations.
For example, base stations may transmit at reduced power if there are no backlogged
users, inducing strong correlations in interference levels between users.
The slot duration in the illustrative embodiment may be assumed to be relatively
short compared to the relevant time scales in the traffic patterns and delay requirements
of the data users.
For example, the slot duration may be on the order of the 1.67 ms used in the
above-noted HDR technique.
The M data users in the illustrative embodiment may be viewed as a subset of
active backlogged users among a greater population, which may change over time.
For scheduling purposes, however, the separation of time scales allows the subset
of active users to be viewed as nearly static and continuously backlogged. In practice,
flow control algorithms such as Transmission Control Protocol (TCP) will typically
be used to feed the data into the base station buffer at a relatively slow rate,
comparable to the actual throughput provided to the user over the wireless link.
Thus, the bulk of the backlogs will usually reside at the sender rather than the
base station buffer.
Throughput maximization is a common performance objective for high-rate
data transmissions on a CDMA downlink, and may be the performance objective in
the illustrative embodiment of the invention. It should be noted that this objective
can be achieved simply by assigning each slot to the user with the currently highest
feasible rate. The disadvantage of this approach is that typically only a few strong
users will ever be selected for transmission, causing starvation of all others.
An alternative approach which alleviates this problem is to equalize the expected
throughput of the various users. This can easily be achieved by assigning each
slot to the user with the currently smallest cumulative throughput. The disadvantage
of this alternative approach is that it does not exploit the variations in the
feasible rates. Moreover, by insisting on equal throughput, a few weak users may
cause the throughput of all others to be dramatically reduced. Another approach
is to equalize the proportion of slots allotted to the various users. Such an approach
can be realized simply by using a round-robin scheduling technique. Again, however,
this approach fails to take advantage of the fluctuations in the feasible rates.
In addition, some users may end up with extremely low throughput, despite receiving
their fair share of the number of transmission slots.
The present invention in the illustrative embodiment avoids the problems of the
above-noted approaches by defining throughput target values α
1,
. . . , α
M for the various users. These target values may be set
arbitrarily, taking into account the Quality-of-Service (QoS) requirements of the
users, or possibly their current activity levels or locations. For example, the
target values may be set lower for users with higher path losses, in order to prevent
weak users from dragging down the throughput of all other users. The target values
may also be applied to the proportion of transmission slots allotted to the various users.
Some additional notation will now be introduced. Let Y
m(n):=X
m(n)
R
m(n), with X
m(n) a 0-1 variable indicating whether or not
the n-th slot is assigned to user m. Further define:
##EQU2##
as the expected average throughput received by user m after N slots. The illustrative
embodiment considers the problem of maximizing the minimum long-run expected average
normalized throughput
##EQU3##
with y
m:=lim inf
N→∞y
m(N). The
above problem may equivalently be formulated as maximizing z subject to the constraint
z≦y
m/α
m for all m=1, . . . , M. The constraints
may in fact be tightened to z=y
m/α
m, since one can
always reduce the throughput for the users with a surplus. With the equality constraints
in place, the objective function may then be generalized to
##EQU4##
for any
positive vector w∈
##CHR1##
+M.
The above-stated problem is thus equivalent to maximizing an arbitrary weighted
sum of the throughputs, subject to the normalized throughputs being equal. Thus,
any scheduling strategy which maximizes an arbitrary weighted combination of the
throughputs, while equalizing the normalized throughputs, is optimal.
A class of revenue-based scheduling strategies for implementing the above-described
maximization will now be introduced. Assume there are rewards w
1, .
. . , w
M per bit transmitted to the various users. A revenue-based scheduling
strategy assigns the n-th transmission slot to the user m*(n) with the current
maximum rate-reward product, i.e.,
##EQU5##
Clearly, the above revenue-based scheduling strategy maximizes the revenue
earned in each individual slot, and thus the total cumulative revenue as well as
the average revenue. Different tie-breaking rules may be used. However, regardless
of the particular tie breaking rule used in a given implementation, this revenue-based
scheduling strategy will definitely not assign the n-th slot to any user k with
##EQU6##
It should be noted that revenue is simply a weighted combination of the throughputs,
and thus any revenue-based policy which balances the throughputs, is in fact optimal.
It should also be noted that setting throughput targets is equivalent to normalizing
the feasible rates by the corresponding values. Therefore, it will be assumed in
the following description that the throughput target values are discounted for
in the rates, such that (α
1, . . . , α
M)=(1,
. . . , 1).
In practice, there is always a small probability that a transmission fails because
the signal cannot be successfully decoded. The results described herein remain
valid if R
m(n) is redefined to represent the expected feasible rate,
and the 0-1 variable X
m(n) is modified to indicate both which user is
selected and whether or not the transmission is successful.
FIG. 3 is a flow diagram illustrating the general data transmission scheduling
process described above. This process is implemented in the base station of FIG.
2, e.g., using software stored in memory 38 and executed by processor 36.
In step 100, the base station determines the feasible rates (R
1,
. . . , R
M) for the M users eligible for data transmission in the n-th
transmission slot. The base station then applies in step 102 the coefficients
of the current revenue vector to the corresponding feasible rates, so as to generate
a set of weighted feasible rates for the M users. In step 104, the base
station identifies the maximum-rate user from among the Musers, and in step 106
schedules data transmission to the maximum-rate user in the n-th transmission slot.
The revenue vector is periodically adjusted as indicated in step 108 so
as to compensate for observed deviations between actual and target throughput ratios.
Step 108 may but need not be repeated for each scheduling operation, and
is therefore shown in dashed outline in the figure. After the scheduling operation
in step 106, and the revenue vector adjustment, if any, in step 108,
the process returns to step 100 to schedule data transmission for the next
transmission slot.
In an alternative embodiment, instead of the expected feasible rate, one can
take
R′
m(n):=K
m+R
m(n), using K
m to
obtain a weighted combination of received rates and slot allocations. More particularly,
by choosing suitable values for K
m, one can give weight to balancing
the proportion of slots allotted to the various users, while also achieving relative
throughput targets.
Discrete Rate Distribution
This section will consider a case in which the feasible rates (R
1,
. . . , R
M) have a discrete distribution on a bounded set J
⊂##CHR2##
M.
Since the feasible rates are assumed to be stationary in the illustrative embodiment,
the description will focus on the class of stationary policies. However, the analysis
may be readily extended to deal with non-stationary policies.
Let p
j be the stationary probability that the feasible rate vector
is j∈J. Define R
ij=j
i for j=(j
1, . . .
j
M)∈J. Let x
ijπ be the probability
that policy π selects user i for transmission when the feasible rate vector
is j∈J. Then the minimum average throughput achieved under policy π
is
##EQU7##
with
##EQU8##
Let π
w be the revenue-based scheduling strategy corresponding
to the vector w=(w
1, . . . , w
M). Without loss of generality,
it may be assumed that
##EQU9##
since only the relative values of the revenue coefficients matter.
Policy π is optimal if x
ijπ, z
π
are an optimal solution to the following linear program:
##EQU10##
##EQU11##
##EQU12##
##EQU13##
This implies that for an optimal policy π at most |J|+M-1 of the variables
x
ijπ are non-zero, which forces most of the variables
to be one. Thus, only for a limited number of rate combinations are the slots shared
among several users.
It was noted above that a revenue-based policy which balances the throughputs
is optimal. It can also be shown that the revenue criterion is in fact a necessary
optimality condition, in the sense that there exists a revenue vector w* such that
when user i does not have the maximum rate-reward product, i.e.,
##EQU14##
then x
ijπ=0, i.e., user i should not be selected
for transmission. Thus, any optimal scheduling strategy must be a revenue-based
policy associated with w*. More specifically, if policy π is optimal, then
there exists a vector w*≧0 such that
##EQU15##
for all i=1, . . . , M, j∈J.
Continuous Rate Distribution
This section will consider a case in which the feasible rates (R
1,
. . . , R
M) have a continuous distribution on a bounded set U
⊂##CHR3##
M.
Let p(u) be the stationary density of the feasible rate vector, i.e., the probability
that the feasible rates are in some set V
⊂U is
##EQU16##
Define R
i(u)=u
i for u=(u
1, . . . , u
M)∈U.
Let x
iπ(u) be the probability that policy π selects
user i for transmission when the feasible rate vector is u∈U.
Policy π is optimal if and only if (iff) x
iπ(u),
z
π are an optimal solution to the following mathematical program:
##EQU17##
##EQU18##
##EQU19##
##EQU20##
As noted previously, a revenue-based policy which balances the throughputs is
optimal. It can also be shown that the revenue principle is in fact a necessary
optimality criterion, in the sense that there exists a revenue vector w* such that
if user i does not have the maximum rate-reward product on some set of non-zero
measure, then user i should not be selected for transmission on that set. Thus,
in the above sense, any optimal scheduling strategy must be a revenue-based policy
associated with w*. More specifically, if policy π is optimal, then there
exists a vector w*≧0 such that
##EQU21##
for all i=1, . . . , M.
Adaptive Algorithms for Adjusting Revenue Vector
The previous two sections illustrate that revenue-based policies optimize throughput
relative to pre-specified target values. However, as noted above, calculating the
optimal revenue vector directly is a complicated problem, requiring detailed information
on the channel statistics in the form of the joint stationary distribution of the
feasible rates (R
1, . . . , R
M). The present invention avoids
this problem by providing adaptive algorithms for determining the optimal revenue
vector in an iterative fashion without the need for direct estimation of the frequency
of occurrence of particular user rates. Starting from an arbitrary initial vector,
the algorithms iteratively adjust the revenue vector coefficients to compensate
for observed deviations from the target throughput ratios. The corrections ensure
that discrepancies in throughput cannot persist. To ensure convergence to the optimal
revenue vector, the size of the adjustments is gradually reduced.
The next two sections will assume that the channel state is governed by a discrete
time irreducible Markov chain with a finite discrete state space S. When the channel
state is s∈S, the feasible rates have a continuous M-dimensional distribution
F
s(·) on R
⊂[R
min, R
max]
M,
0<R
min<R
max<∞, with zero probability
measure in any set of Lebesgue measure zero. In practice, the feasible rates will
typically have to be selected from a limited set of discrete values. However, it
is possible to adhere to the above assumptions by simply adding a small random
perturbation. By choosing the random perturbation to be sufficiently small, the
true achieved throughputs should be arbitrarily close to the perturbed ones.
Denote by
##EQU22##
the set of all revenue vectors. For any w∈W, denote by Ξ
m(w)
the expected average throughput per slot received by user m under revenue vector
w in stationarity. Define
##EQU23##
as the average, the minimum, and the maximum expected throughput per slot under
revenue vector w over all users, respectively.
The above assumptions ensure that the expected throughput vector (Ξ
1(w),
. . . , Ξ
M(w)) is completely determined by the revenue vector
w, without the need to specify a tie breaking rule. The assumptions further imply
that the expected throughput vector (Ξ
1(w), . . . , Ξ
M(w))
is a continuous function of the revenue vector w.
Denote by w* the optimal revenue vector, i.e., the revenue vector which balances
the expected throughputs. To simplify the description, it will be assumed that
w* is unique, although the analysis may be modified in a straightforward manner
for the case where there is a range of optimal revenue vectors.
Two-User Adaptive Algorithm
For illustrative purposes, an adaptive algorithm will be described in this section
for the case of two users, denoted user 1 and user 2. The next section will describe
an adaptive algorithm for the more general case of an arbitrary number of users.
Before describing the algorithm for the two-user case in detail, some additional
notation will be introduced. First, let w=w
1, so that w
2=1-w.
Denote ΔY(n):=Y
1(n)-Y
2(n), and define
##EQU24##
as the difference in cumulative throughput between users 1 and 2 after N slots.
The absolute difference |U(N)| is referred to as the throughput gap. The throughput
gap widens in the N-th slot if
##EQU25##
User 1 is said to be leading if U(N)>0, and is referred to as lagging otherwise,
and vice versa for user 2. A cross-over occurs in the N-th slot if the leading
and lagging users exchange positions, which means that the throughput gap changes
sign, i.e., U(N) U(N-1)<0.
The adaptive algorithm for the two-user case may now be described as follows.
In every slot, the user with the maximum revenue-rate product, at the current price,
is selected for transmission. Thus, the n-th slot is assigned to user 1 if w(n)R
1(n)>(1-w(n))R
2(n),
and to user 2 otherwise (ties being broken arbitrarily). To drive the revenue vector
w(n) towards the optimal revenue vector w*, the price is adjusted over time on
the basis of the observed throughput realizations. As long as the throughput gap
does not widen, the price is left unaltered. However, if the throughput gap does
widen, then the price is changed in favor of the deficit user, thus at the expense
of the surplus user. The price of the leading user is decreased by δ
k(n),
while the price of the lagging user is simultaneously increased by the same amount.
To ensure convergence, a reset is triggered at every cross-over. The step size
δ
k(n) is then reduced by incrementing k(n), with {δ
k,
k=1, 2, . . . } being a predetermined convergent sequence (e.g., δ
k+1=δ
1ρ
k
with ρ<1, or δ
k=δ
1k
-β
with β>1).
For the two-user adaptive algorithm described above, the revenue vector w(n)
converges to the optimal price w* wp 1 (where wp 1 denotes "with probability 1,"
meaning "always" or "almost surely") and consequently the sequence z(n) converges
to the optimal value z
πw* wp 1.
Adaptive Algorithm for Arbitrary Number of Users
The adaptive algorithm described in the previous section for the case of two
users may be extended directly to an arbitrary number of users through modification
of the rule for when to trigger a reset. For example, if a reset is triggered at
every cross-over of any pair of users, as in the two-user case described above,
then resets may occur too rapidly in the case of several users. Two leapfrogging
users may cause the step size to be quickly reduced, while still far removed from
the other users. The revenue vector may then get trapped in a bias region, and
never reach the optimal point. A more appropriate rule for the several-user case
is to trigger a reset only when every user has become leading or lagging. It is
nonetheless important to ensure that resets occur frequently enough compared to
wrong moves, because otherwise the revenue vector may continue to become trapped
in a bias region.
This section describes an alternative adaptive algorithm that is particularly
well-suited for the case of an arbitrary number of users. This algorithm makes
revenue vector updates based on sample periods of predetermined ever-increasing
size. Thus, the revenue vector updates occur at predetermined slots K(n), instead
of randomly determined slots as before, with L(n):=K(n+1)-K(n) the length of the
n-th period. In every slot of the n-th sample period, the revenue vector sequence
w(n) is used for selecting a user for transmission, with n used to index sample
periods, rather than transmission slots as in the previous description.
To drive the revenue vector w(n) towards the optimal point w*, the prices are
adjusted over time on the basis of the observed throughput realizations. The direction
in which the revenue vector is modified at the n-th update is determined by a random
vector v(w(n)) based on the throughput obtained during the n-th sample period when
the revenue vector w(n) is used. The size of the n-th update is δ(n)=δ
k(n),
with {δ
k, k=1, 2, . . . } being a predetermined convergent sequence.
Thus, at the (n+1)-th update, the revenue vector is recursively determined as
w(
n+1)=
w(
n)-δ(
n)
v(
w(
n)).
To ensure convergence, the step size δ(n) is reduced by incrementing k(n)
every time a reset is triggered. Intuitively, resets should occur only rarely when
the revenue vector is far from the optimal point w*, but should occur readily once
the revenue vector is close to w*.
The update direction v(w(n)) is determined as follows. For every user, the empirical
average throughput over the sample period is computed. The users are then partitioned
into two groups: (a) those with above-average throughput; (b) those with below-average
throughput. The prices of the above-average users are decreased, while the prices
of the below-average users are increased. This ensures that, as the sample size
grows, the empirical average throughputs will with high probability line up with
the true expected throughputs, and the revenue vector will get closer to the optimal
point w*.
More formally, denote by X
m the throughput received by user m during
a particular sample period in which revenue vector w is used, define
##EQU26##
as the average throughput over all users, and denote by Ω
-:={m:
X
m≦X
ave} and Ω
+:={m: X
m>X
ave}
the groups of below-average and strictly above-average users, respectively; the
revenue vector update direction v(w) is then determined as
##EQU27##
Note that Ω
-0 is always non-empty, since it is impossible
for all users to have strictly above-average throughput. However, Ω
+
may be empty in a case in which all users have exactly equal throughput. In that
case, the revenue vector is simply left unaltered.
Also note that the price ratios within both Ω
- and Ω
+
are maintained. This ensures that the expected throughput of the below-average
users increases, while the expected throughput of the above-average users decreases.
The above revenue vector update cannot be applied in a case in which the prices
of some of the users in Ω
+ are zero. To prevent that situation
from happening, the revenue vector update process may be restricted to the set
W
v:={w∈W: w
m≧v for all m=1, . . . , M}, with
v:=R
min/(R
min+(M-1)R
max). If w
m≦v,
then Ξ
m(w)=0, which implies that w*∈W
v. In order
to restrict the revenue vector update process to the set W
v, the update
is truncated at the boundary if necessary.
To ensure convergence, a reset is triggered under the condition that every user
has been a member of Ω
+ at least once during a consecutive sequence
of updates. Once the reset has occurred, the next one is not triggered until every
user has been a member of Ω
+ at least once again.
The above-described revenue vector update increases the throughputs of the users
in Ω
- and decreases throughputs of the users in Ω
+.
This can be seen as follows. Let w, w′∈W be two revenue vectors and
Θ
-, Θ
+⊂{1, . . .
, M} be two groups of users such that for all
##EQU28##
for all k≠i, and for all
##EQU29##
for all k≠j. Then
Ξ
i(
w′)≧Ξ
i(
w)
i∈Θ-,
Ξ
j(
w′)≦Ξ
j(
w)
j∈Θ+,
As indicated above, when a correct revenue vector update direction is selected,
the revenue vector should get closer to the optimal point w* by some definite amount.
To measure distance from w*, a function T(·) is introduced which attains a
unique minimum at w*. Define Γ
∈:={w∈W: Ξ
max(w)-Ξ
min(w)≦∈}
as an "∈-neighborhood" of w*. The following assumption implies that if a
correct direction is chosen, then outside Γ
∈ the reduction
in the value of T(·) for small enough step size δ is at least δ
times a constant of proportionality η.
There exist positive constants δ*>0, η>0, ξ>0
such that for all revenue vectors w∉Γ
∈, for any
ξ-right direction v(w), and for any δ∈(0, δ*),
T(
w+δv(
w))≦
T(
w)-δη.
One example of a function T(·) satisfying this assumption is
T(
w):=Ξ
max(
w)-Ξ
min(
w),
i.e., the maximum difference in expected throughout between any pair of users.
By definition T(w*)=0, and T(w)≧0 for all w≠w*, with strict inequality
in case the optimal revenue vector w* is unique. Another example of a function
T(·) satisfying the above assumption is
##EQU30##
i.e., the total expected revenue earned. As noted previously, the optimal revenue
vector w* minimizes that quantity over all vectors in the set W, i.e., T(w*)≦T(w)
for all w∈W, w≠w*, with strict inequality in case w* is unique.
The second example T(·) function, unlike the first, also satisfies the above
assumption for various alternative options for selection of a revenue vector update
direction, e.g.,
##EQU31##
and v
k=β
n/(M-2) for all k≠i*,j*, for lim
nβ
n=0,
a given positive sequence. This alternative option is referred to herein as the
"Update-Extreme" algorithm, while the basic implementation previously described
will be referred to as the "Move-to-Average" algorithm.
The revenue vector sequence w(n) for both of these algorithms converges to the
optimal revenue vector w* wp 1, and consequently the sequence z(n) converges to
the optimal value z
πw* wp 1.
The n-th sample is referred to as "ξ-right" if for every user the empirical
average throughput is within ξ from the true expected throughput, i.e., |X
m(n)-Ξ
m(w(n))|≦ξ
for all m=1, . . . , M. Otherwise the sample is referred to as "ξ-wrong."
The following points can then be made regarding the above-described example adaptive algorithms:
- 1. For any fixed ξ>0, the total number of ξ-wrong samples
is finite wp 1.
- 2. The total number of resets is infinite wp 1.
- 3. The revenue vector sequence w(n) cannot converge to a point outside Γ∈.
- 4. The revenue vector sequence w(n) visits Γ∈
infinitely often.
- 5. The revenue vector sequence w(n) cannot move from Γ∈
to outside Γ2∈, infinitely often.
The illustrative embodiment as described above establishes convergence to the
optimal revenue vector w* through selection of the step sizes {δ
k,
k=1, 2, . . . } as a convergent sequence. As one possible alternative, the step
sizes may be kept fixed at a given value δ. In this case, it is expected
that the revenue vector sequence will continue to oscillate around w*, but with
smaller amplitudes for smaller values of δ. There is an inherent trade-off
between the accuracy achieved on the one hand and the speed of the convergence,
and thus the responsiveness to changing conditions, on the other hand. The value
of δ then may be used to find the right balance between these two conflicting objectives.
Numerical Results
This section describes numerical results of experiments conducted to investigate
the convergence properties of the adaptive algorithms described above. The results
verify long-term convergence of the adaptive algorithms, and also illustrate transient
performance, in particular the rate at which the revenue vector converges to the
optimal vector.
Results are presented below for a total of seven experiments. The first three
experiments to be described consider continuous rate distributions. The fourth
experiment assumes a discrete distribution where the feasible rates are determined
by a fading
