HK1074719A - Method and apparatus for scheduling packet data transmissions in a wireless communication system - Google Patents

Description

Method and apparatus for scheduling packet data transmissions in a wireless communication system

FIELD

The present invention relates to wireless data communications, and more particularly, to a novel and improved method and apparatus for scheduling packet data transmissions in a wireless communication system.

Background

In a wireless communication system, a base station communicates with a plurality of mobile users. The wireless communication may include low-latency data communication, such as voice or video transmissions, or high-data rate communication, such as packetized data transmissions. U.S. patent application No. 08/963386, entitled "METHOD AND APPARATUS FOR HIGH RATE PACKETDATA TRANSMISSION", filed 1997, on 3/11, describes high rate packet data TRANSMISSION AND is incorporated herein by reference.

Packet data transmissions need not be low latency transmissions, thereby enabling the base station to flexibly schedule mobile user transmissions within the system. Once scheduled, the base station may transmit data to as few as one mobile user for a given period of time. Generally, there are two purposes to schedule packet data for mobile users. The first objective is to optimize the usage of each channel. A second purpose is to distribute transmissions fairly to mobile users. The two purposes sometimes compete. For example, channel quality conditions and the amount of pending data for a user can result in excessive time allocation for that user, especially at the expense of other users.

A fair method is therefore needed to perform channel sensitive packet data transmission scheduling to mobile users.

SUMMARY

The disclosed embodiments provide a novel and improved method for packet data transmission scheduling in a wireless communication system. In one aspect, in a wireless communication system adapted for packet data transmission, a method includes receiving rate request indicators for a plurality of mobile stations, calculating a priority function value for the plurality of mobile stations based on the rate request indicators, and scheduling transmissions to the mobile stations based on the priority function values.

According to another aspect, a wireless device includes a priority factor calculation unit adapted to receive a data rate request from a mobile station and generate a power factor value therefrom, and a scheduling unit coupled to the priority factor calculation unit, the scheduling unit adapted to schedule data transmissions.

According to yet another aspect, a method for scheduling packet data exchanges in a wireless communication network includes determining a pool of users, calculating a priority function for at least a portion of the pool of users, scheduling a first set of users with pending data exchanges from the pool portion of users, receiving a rate request indicator from the pool portion of users, and updating the priority function for the users of the first set in response to the rate request indicator.

Brief description of the drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

fig. 1 illustrates a block diagram from a wireless communication system according to an embodiment;

FIGS. 2A and 2B illustrate a flow diagram of a method of packet data transmission scheduling in the system of FIG. 1, according to one embodiment;

FIG. 3 illustrates a block diagram form of the base station of FIG. 1 in accordance with one embodiment;

FIG. 4 illustrates, in block diagram form, a portion of a base station within FIG. 3, in accordance with one embodiment;

FIG. 5 is a flow chart for scheduling data transmissions;

fig. 6 illustrates data transmission within a wireless communication system;

FIGS. 7A and 7B illustrate an automatic repeat request within a data transmission;

FIG. 8 is an energy diagram of a data transmission; and

fig. 9 is a method for updating a throughput parameter within a data transmission.

Detailed description of the preferred embodiments

In an example embodiment of the present invention, a base station of a spread spectrum wireless communication system schedules packet data transmissions to mobile users based on an instantaneous value of a Priority Function (PF) per user. The user scheduling priority is associated with a PF value, wherein a high PF value indicates a high scheduling priority and a low PF value indicates a low priority. In an aspect, a method for determining a PF value is based on channel conditions specified by a Rate Request Indicator (RRI). The method also considers fairness criteria determined by quality of service (QoS) requirements. This approach provides robust protection against non-zero buffer underrun at the transmitter. In one embodiment, the rate request indicator is a Data Rate Request (DRR). In another embodiment, the rate request indicator is carrier-to-interference (C/I) information. Other embodiments may implement other types of rate request indicators or predictors. In an example embodiment, a base station calculates a Priority Function (PF) for a plurality of mobile users. Each PF is a function of the rate request indicator and the projected throughput of a given mobile user. The PF value enables the base station to schedule active mobile units with pending data. Scheduling generates an allocated transmission time that is approximately equally divided among the plurality of mobile stations.

Scheduling assignments improves channel sensitivity by reducing the negative impact associated with the assigned data rate. The actual data rate allocation provides a quantized transmission rate. This results in coarse data rate adjustment within the system. The actual data rate may be truncated or otherwise manipulated to conform to the assigned and available data rates. By using the rate request indicator to determine the transmission data rate, the data rate is adjusted according to the actual requirements and the operating environment of the system.

Fig. 1 is an example of a communication system 100 that supports multiple users and is capable of implementing at least some aspects and embodiments of the present invention. Any of a variety of algorithms and methods may be used to schedule transmissions within system 100. System 100 provides for communication for a plurality of cells 102A through 102G, each of which is serviced by a respective base station 104A through 104G. In the exemplary embodiment, some of the base stations 104 have multiple receive antennas and others have only one receive antenna. Similarly, some of the base stations 104 have multiple transmit antennas, others have only a single transmit antenna. There is no limitation on the combination of the transmit antenna and the receive antenna. Thus, a base station 104 may have multiple transmit antennas and a single receive antenna, or multiple receive antennas and a single transmit antenna, or both single or multiple transmit and receive antennas.

Terminals 106 within the coverage area may be fixed (i.e., stationary) or mobile. As shown in fig. 1, a plurality of terminals 106 are dispersed throughout the system. Each terminal 106 communicates with at least one, and possibly multiple, base stations 104 on the downlink and uplink at any given moment, depending on, for example, whether soft handoff is used or whether the terminal is designed and used to receive transmissions (concurrently or sequentially) from multiple base stations. Soft HANDOFFs IN CDMA communication SYSTEMs are well known IN the art and are described IN detail IN U.S. Pat. No. 5101501, entitled "METHOD AND SYSTEM FOR PROVIDING A SOFT HANDOFF IN A CDMA CELLULAR TELEPHONESYSTEM", which is assigned to the assignee of the present invention and is incorporated herein by reference.

The downlink refers to transmission from the base station to the terminal, and the uplink refers to transmission from the terminal to the base station. In an exemplary embodiment, some of the terminals 106 have multiple receive antennas and others have only one receive antenna. Similarly, some of the terminals 106 have multiple transmit antennas, and others have only one transmit antenna. In fig. 1, base station 104A transmits data to terminals 106A and 106J on the downlink, base station 104B transmits data to terminals 106B and 106J, base station 104C transmits data to terminal 106C, and so on.

The increasing demand for wireless data transmission and expansion of available services through wireless communication technologies has led to the development of specific data services. One such service is known as High Data Rate (HDR). An exemplary HDR service IS set forth in "EIA/TIA-IS 856 cdma2000 High Rate Packet Data Air InterfaceSpecification," referred to as the HDR specification. HDR services are typically overlaid on voice communication systems, which provide an efficient way to transmit data packets within a wireless communication system. As the amount of data sent and the number of transmissions increases, the limited bandwidth available for radio transmission becomes a critical resource. There is therefore a need for a method of scheduling transmissions in a communication system that is efficient and fair to optimize the use of available bandwidth. In an exemplary embodiment, the system 100 illustrated in fig. 1 is compliant with a CDMA type system with HDR service.

Fig. 2A illustrates a method 200 for scheduling mobile stations within system 100. The process begins by determining a pool of active mobile users within the system 100 at step 202. The total number of mobile stations or users in the pool is designated as "N". If N is equal to 0, then at step 204, the process terminates, otherwise the process continues to step 206 to calculate the PF for each of a subset of "M" users in the pool, where M active users have pending data. The PF calculation is implemented according to the following equation:

for j ═ 1.., M, (1)

Where j is the user index corresponding to the M active users with pending data. In an example embodiment, the rate request indicator is implemented as DRR (j), i.e., a Data Rate Request (DRR) received from user j, j ═ 1. Having a channel sensitive rate request indicator on the numerator provides proportionality with scheduling of users within system 100. The rate request indicator is then divided by the projected throughput T' (j) associated with each user j. The actual throughput for each user j may be denoted as t (j), although the actual throughput is not directly used for the calculation of equation (1).

From the subset of M active users with pending data, a subset of further "K" users scheduled for transmission is determined, step 208. In an example embodiment, the subset of K users is determined according to a system configuration and a predetermined scheduling policy. Often K ═ 1, i.e., K is limited to a single user. However, K may be any number less than or equal to M. Based on the calculated PF value, the base station schedules "K" users at step 210. It is worth noting that the K scheduled users constitute a subset of the N active users, i.e., (K ≦ M ≦ N). The base station then transmits the packet data transmission according to the schedule of step 210 at step 212. Transmission involves determining transmission power, power control, data rate, modulation, and other transmission parameters. It is also worth noting that the base station may send a low latency transmission delay to the mobile station.

In step 214, the base station updates each projected throughput T' for each of the K scheduled users as a function of the corresponding rate request indicator received from each scheduled user. The following formula describes the T' update calculation for scheduled users according to an example embodiment:

T′(j，n+1)＝(1-α)·T′(j，n)+α·DRR(j)， (2)

where α is the time constant of the smoothing filter used for scheduling for the digital samples with index n. In one embodiment, the time constant may be related to the target QOS and/or the speed of each mobile station. In this example embodiment, the rate request indicator is implemented as DRR (l), i.e. a Data Rate Request (DRR) received from user l, where l ═ 1. The rate request indicator with channel sensitivity in the numerator provides proportionality to the scheduling of users within system 100. The rate request indicator is then divided by the projected throughput T' (j) associated with each user j. The actual throughput for each user j may be denoted as t (j), although the actual throughput is not directly used for the calculation of equation (1). Instead, the scheduling method predicts or plans the throughput of each user based on the rate request indicators received from that user. The rate request indicator may be a Data Rate Control (DRC) channel transmitted by a user determining the quality of the transmission channel and determining the corresponding data rate to be requested. The quality of the transmission channel may be a C/I measurement of the transmission received by the user, with the corresponding DRR being associated with the C/I ratio, such as through a look-up table. In one embodiment, the user transmits the C/I ratio to the base station, and the base station determines the requested data rate based on errors in the transmitted data received by the user. The user may determine the data rate requested from the base station using various methods. Similarly, the user may implement various rate request indicators for requesting a data rate from the base station. In addition, in one embodiment, different mobile stations implement different rate request indicators.

If K < M at step 216, processing continues to step 218 to update each T' of unscheduled users in the N active user pools. The projected throughput calculation for unscheduled users is given by:

T′(i，n+1)＝(1-α)·T′(i，n)， (3)

for i ═ 1., (M-K). Here the rate request indicator is assumed to be zero for calculating the projected throughput for updating each PF associated with the unscheduled user. Processing then returns to step 208 where the updated PF value is used to continue scheduling any users that still have pending data.

The exemplary embodiment updates the PF value for each user as if there were always a sufficient amount of pending data for each mobile station and the rate requested by each mobile station is achievable. Thus, the PF generated scheduling sequence as calculated in equations (1) - (3) is not sensitive to the unpredictable state of any transmission buffer as long as the buffer has at least one bit of data to transmit.

FIG. 2B illustrates step 210 of FIG. 2A in greater detail according to one embodiment of determining a schedule. At step 230, a priority function is determined for each user. In the illustrated embodiment, the priority function is the data rate ri (t) of the user. At step 232, the BS selects a winner according to the priority function, and transmits data at step 234. If data is still pending at step 236, processing returns to step 230, otherwise processing ends for the period.

Fig. 3 illustrates the base station 104 in detail, including the signals received, processed, and transmitted. As illustrated, a base station receives rate request indicators, such as DRRs or C/Is, from a plurality of mobile stations. Control information is received at least from the mobile station and possibly from a central controller, such as a Base Station Controller (BSC) (not shown). The base station receives traffic, referred to as "backbone traffic," from a network (not shown), such as the internet. In response to these signals, the base station transmits data to the mobile station.

Fig. 4 illustrates the scheduler portion of the base station in further detail. The base station comprises a pool calculation unit 140 for determining the number and identity of mobile stations active at a given time. The active mobile station communicates with the base station, but may not have any pending data interactions. The pool calculation unit 140 receives control information from mobile stations and BSCs (not shown), and receives traffic from a network (not shown). In response, the pool calculation unit 140 provides the PF calculation unit 142 with user identification information, i.e., user id (l) (for l ═ 1.., N). The user identification information is provided for all N active users within the system 100.

The PF calculation unit 142 receives a data rate request indicator, such as drr (l), from the mobile station. The PF calculation unit 142 uses the rate request indicator to determine the PF of each user according to equation (1). The pf (j) (j ═ 1., K) of all users with pending data are provided to scheduling unit 146. The scheduling unit 146 determines a schedule among a plurality of users associated with pf (j). The scheduling unit 146 provides scheduling information to the transmit circuit 148. The DATA-IN (DATA IN) is also provided to the transmit circuit 148, which transmits DATA according to the scheduling information to generate the DATA-OUT (DATA OUT). The scheduling information is also provided to a calculation unit 150 which updates the projected throughput for the active N users. The scheduled users are updated according to equation (2) and the unscheduled users are updated according to equation (3). To update the projected throughput value, the calculation unit 150 receives a rate request indicator of the mobile station. The updated projected throughput values for the subset of M users with pending data are then provided back to the PF calculation unit 142 to update the PF values. The calculation unit 150 includes a smoothing filter, such as an Infinite Impulse Response (IIR) filter. The tap coefficients of the smoothing filter are configurable.

In one example, the mobile station has a speed of 3 kilometers per hour and experiences a Doppler shift f of 5.4Hz_doppler. The projected throughput is IIR smoothed according to equations (2) and (3) with a time constant T_wApproximately 2 seconds. IIR filter tap coefficient alpha and time constant T_wCorrelation, the relationship is:

the time constant resulting in a given frame duration of 20 milliseconds is 1/100, i.e. 50 frames per second. In the general calculation of α, it first involves determining the quality of service of the transmission, which reflects the fairness constraint, where each mobile station is assigned a fraction of time within a predetermined tolerance. Alpha is calculated and then optimized to achieve the best practical system throughput.

In further embodiments, the proportional fairness algorithm implements a fairness criterion that includes a delay term. In particular, the delay is measured at the base station from the time of arrival of the data packet to the time of transmission of the data from the BS to the user or MS. The delay may be measured after the start of the transmission or after the end of the transmission. The delay is actually measured as the time that the data is maintained at the BS before transmission. The data may be stored in a queue or other memory storage device of BS 12 (not shown).

In general, proportional fairness algorithms maintain a balance between maximizing throughput in a set of users and fairly allocating throughput to individual users. However, this algorithm does not guarantee that certain latency requirements for a single user are met. By modifying the proportional fair priority function PF to include a delay sensitive term, the result provides scheduling that meets the delay requirement. It is noted that the delay requirements are generally dictated by operating standards.

In an exemplary embodiment, the user delay requirements within the system are provided a priori to the BS104 as a function of time (e.g., d given in seconds). The BS then assigns a time delay threshold τ to each user. In particular, the BS104 stores user i ═N value τ_iWhere N is the total number of users at a given time. Calculating the conventional proportional fair priority of the user is given by:

where DRC is the data rate supported by a given MS and T is the throughput of the user. By modifying equation (5) to:

the PF calculation includes a delay function g (d) which is a function of the user delay.

Thus, the scheduling method gives priority to the user when its delay is above a predetermined threshold applying equation (6). When the delay time decreases below the threshold, the user's priority is calculated as in equation (5).

Fig. 5 illustrates a method 300 of scheduling users in a packetized data transmission system. The process calculates the delay for user i, specified as d in step 302_i。d_iThen with a threshold τ_iAnd (4) comparing. Threshold value tau_iIs specific to user i. Other embodiments may implement a single threshold for all users. In addition, the threshold τ_iThe threshold may be dynamic, i.e., updated as the system operates. If the user delay is greater than the threshold at decision block 304, the process computes a delay function g (d) for di at step 306, where the function is defined as:

g(d_i)＝1+k*MAX(0，(d_i-τ_i)) (7)

if the user delay is less than or equal to the threshold, then a delay function g (d) is calculated at step 308 and given as:

g(d_i)＝1 (8)

the process then applies a PF at step 110, using the delay function calculated at step 306 or 308, the PF given as:

PF_i＝(DRC_i/T_i)*g(d_i) (9)

other embodiments may implement any of a variety of delay functions that meet the requirements, performance, and range of a given communication system. In another embodiment, the delay function is defined as:

g(d_i)＝1+k*MAX(0，f(d_i-τ_i))， (10)

where f () may represent an increasing function of the delay, or more specifically, (d)_i-τ_i) Is used as an increasing function of.

Yet other embodiments implement a delay function, as defined by the following equation:

g(d_i)＝1，for d_i＜τ_i； (11)

g(d_i)＝DRC_MAX/DRC_AVE，for d_i≥τ_i， (12)

wherein DRC_MAXIs the maximum DRC for all users, and DRC_AVEIs the average of user i. The delay function of equations (11) and (12) adjusts the PF of a given user as a function of the delay of that user relative to other users. Thus, if user i's average requested data rate, DRC, is much smaller than the maximum DRC across all users in the active set with pending data, and if that user is experiencing a delay exceeding a threshold, user i will receive a goodThe priority is increased.

In another embodiment, the PF of equation (5) is modified to adjust the priority, which is a function of throughput rather than delay, where the PF is calculated as:

including a throughput function g (T)_i). The throughput function reflects the throughput of user i. Especially if the throughput T_iGreater than the throughput threshold, then

g(T_i)＝1； (14)

If the throughput T_iLess than or equal to the throughput threshold, then

g(T_i)＝DRC_MAX/DRC_AVE (15)

In this way, the user priority is modified according to the received throughput. When the throughput is too low, i.e. at or below a threshold, the PF is increased. Otherwise, the priority function is calculated as given in equation (5). Thus, if the average requested data rate, DRC, for user i is much smaller than the maximum DRC across all users in the active set with pending data, and if that user is experiencing throughput violating the throughput threshold, user i will receive an increase in priority.

In addition, other embodiments may implement various delay functions, such as those specified in "Providing Qualityof Service over a Shared Wireless Link," authored by MatthewAnreviews et al, IEEE J. COMMUNICATION, 2001, 2 months, 150-.

Example embodiment providesAnother method is provided for calculating a Priority Function (PF) using a proportional fair scheduling algorithm applied to a data transmission system. The present exemplary embodiment IS discussed herein with respect to an IS-20001 xEVDV system. The present invention is applicable to any wireless communication system using a scheduler. Example embodiments are HDR type systems in which an ARQ scheme is applied to provide retransmission of data packets and/or sub-packets. The data transmission is provided as data packets. Each data packet may be transmitted over a fixed or variable time interval called a slot. In an example embodiment, a time slot is defined as a minimum time interval during which a data packet or a portion of a data packet, referred to as a sub-packet, may be transmitted. For example, in one embodiment, the time slot is 1.25 milliseconds. In an embodiment, multiple slots may be used for transmission of data packets or sub-packets. Fig. 6 illustrates data transfers that may be used in an example embodiment. As illustrated, each data transmission may be of variable length, including one, two, four, or eight time slot lengths. It is noted that in such a system, the data packets may be transmitted in one of the formats illustrated in the figures. For a slot transmission length, the time interval is given as T₁. For a two slot transmission length, the time interval of the transmission is given as T₂Wherein:

T₂＝2*T₁ (16)

similarly, the four slot transmission length is equal to four T₁Time interval, eight time slot transmission length equal to eight T₁And (4) spacing. Other embodiments may apply any number of slots to the transmission interval. Still other embodiments may apply a fixed time interval for data transmission.

Data is typically sent on a sub-packet basis as illustrated in fig. 7A, where forward link data multi-slot packet transmission is illustrated along with reverse link signaling. For a given data packet, the receiver first specifies a requested data rate or DRR, e.g., a Data Request Control (DRC) indicator. The receiver analyzes the channel conditions for the transmission and, in response, specifies a data rate at which the receiver can receive the data transmission. The transmitter receives the DRR, or some other channel condition indicator, and transmits the data packet accordingly.

The exemplary embodiments support an ARQ scheme that supports retransmission of data packets, wherein the receiver provides a feedback signal to the transmitter indicating whether a data packet was received. In particular, the receiver sends an ACK signal to acknowledge that sufficient information has been received to decode the data packet; or conversely, the receiver sends a NAK signal to indicate that a data packet has not been received. In response to the NAK signal, the transmitter retransmits the data packet. The transmitter terminates transmission of the data packet in response to the ACK signal. The data packet may be transmitted in one, two, four or eight time slots as illustrated in fig. 6. It is noted that after retransmission of a data packet and before a NAK signal is received at the transmitter, the transmitter may send other data packets, which may be directed to the same receiver or other receivers.

As illustrated in fig. 7A and 7B, in a system supporting an ARQ scheme, multiple retransmissions may be required for each transmission. Retransmissions are terminated when an Acknowledgement (ACK) signal is received, or when the transmission reaches a maximum number of retransmissions. The maximum number of retransmissions may be a system predetermined value or may be negotiated between the transmitter and the receiver.

Examples of transmissions and retransmissions in the exemplary embodiment are specifically illustrated in fig. 7A and 7B, where the reverse link DRC and ACK/NAK signals from the receiver are illustrated with respect to forward link transmission slots. The DRC is sent by the mobile station at slot i, where the mobile station has pending data and indicates the data rate at which the transmitter mobile station can receive the transmission. In response to receipt of the DRC (indicated by the connection arrow), the transmitter transmits a first portion of the data packet in slot n. It is noted that the slot boundaries on the FL and RL are not necessarily coordinated in time. The transmitter then transmits other information, such as portions of other data packets, on time slots n +1, n +2, and n + 3. The transmitter transmits a second portion of the data packet (associated with the illustrated DRC) during slot n + 4. Other portions of the data packet are then periodically transmitted until the mobile station (receiver) indicates that the data packet was correctly received, i.e., an ACK signal is transmitted. It is noted that the mobile station sends a NAK signal to indicate that a data packet was not received, or that sufficient information was not received to decode the data packet. In response to each NAK signal, the transmitter transmits another portion of the data packet. For example, as illustrated, a NAK is transmitted at slot l +4, and in response a data portion is transmitted at n + 4.

Fig. 7B illustrates the application of an ACK to cause the transmitter to terminate transmission of a data packet. The mobile station sends an ACK indication as illustrated at slot l + 12. The transmitter terminates the data packet transmission and initializes a new data packet at time slot n + 12.

In addition, the exemplary embodiments support Time Division Multiplexed (TDM) transmission, where a transmitter transmits to one receiver during a given time interval. TDM transmission uses all of the transmit energy to transmit data to selected receivers. Example embodiments also support Code Division Multiplexing (CDM) transmission, where a transmitter transmits to multiple receivers during a given time interval. The multiple receivers are separated by spreading codes. The transmitted energy is distributed among a plurality of receivers. The scheduling method is called a scheduler for determining a transmission order. For each time interval, the scheduler selects a winner based on predetermined criteria, such as, but not limited to, channel conditions, amount of pending data, transmission history, user throughput, and the like.

To schedule transmissions, each user or mobile station is assigned a priority index or PF that is directly proportional to the C/I of the mobile station. The priority is defined as equation (1) above, where the priority index or PF is proportional to the average user throughput. The scheduler attempts to equalize the transmission time and transmission energy allocated to the receiver. Generally, a mobile unit at low speed experiences greater gain because the C/I can be estimated with greater accuracy. In other words, the scheduler is better able to track the channel conditions since the channel conditions of slow moving vehicles change slowly. Thus, few, if any, retransmissions may be required to receive the data packet. Conversely, for high speed mobile units, the channel conditions change faster and the scheduler is less able to track the channel conditions. Fast moving receivers tend to require more retransmissions to receive data packets.

The proportional fairness algorithm prioritizes users substantially according to a given metric. The exemplary embodiment uses a scheduler on the forward link (or downlink) to schedule data transmission to multiple data users. A scheduler, such as a proportional fair scheduler, uses C/I (or DRR) feedback information along with user throughput information to select the best user for the next transmission. As described above, a cost function applying the ratio of C/I ratio (or DRR) and user throughput is used to calculate the priority index for each user. The user with the highest priority index will be selected as the next transmission. This cost function takes advantage of channel conditions to maximize system performance and maintain fairness for each end user.

Users within the system will be served a statistically equal amount of time (i.e., will have the same average serving time), with each user being served an equal time interval in each round. Scheduling is accomplished based on receiving channel condition information from the mobile station. The transmission of the C/I or DRC information from the mobile station introduces a delay in the calculation. The delayed C/I information may then introduce significant estimation errors in the return, for example, because the channel is fading quickly, the current information received at the transmitter may have been inconsistent with the changing channel conditions. As discussed above, fast moving receivers may tend to require more retransmissions and, therefore, more time allocations. The difference between slow-moving and fast-moving receivers is different from the balance advocated by the fair proportional algorithm.

A proportional fairness algorithm is applied to a wireless system using an ARQ scheme, where multiple subpackets may be transmitted and throughput is updated at the beginning of the first subpacket transmission. Fairness is maintained when all users have the same average error rate or the same channel conditions. However, when one user has a slow fading channel and another user has a fast fading channel, the users of the fast fading channel may require more retransmissions than the users of the slow fading channel. Thus, if the throughput of a user (and thus the priority index function) is updated only once at the beginning of the first sub-packet transmission, fairness of statistically equal access times may not be maintained. In other words, the scheduler may not be able to use the current information to make scheduling decisions since the channel conditions may change between the transmission of channel condition indicators, such as C/I and DRC from the mobile station, and the completion of the data transmission (i.e., the transmission of the last subpacket).

In an example embodiment, the user throughput is updated and a corresponding PF is generated at each slot of transmission and retransmission. The throughput value is updated as a function of the throughput history and the DRC or payload value. In one embodiment, equations (2) and (3) are combined and the throughput is updated according to:

T(i)＝αT(i-1)+(1-α)[DRC] (17)

other embodiments may include additional throughput history entries, such as T (i-2), or other factors that facilitate a more accurate scheduling scheme. The updating of the throughput occurs at each transmission of a sub-packet and retransmission of the sub-packet. In other words, the throughput is updated at each time slot. As described above, transmission and retransmission of a first data packet (or portions of the same data packet) may be interleaved with other data packets (or portions of other data packets). Other data packets may enter other receivers, where the DRC for the first packet is set to zero when the throughput of the first data is updated on the slots for the other receivers. In this case, the second term in equation (17) is set to zero. Reference is made to equations (2) and (3) as given above.

When a sub-packet is transmitted over multiple slots, the payload of each slot may be generated, i.e., the total payload of the packet divided by the number of slots within the sub-packet. For example, for a multi-slot transmission, the payload may be divided by the total number of slots per transmission, where the quotient defines the size of the sub-packet per slot. This is particularly advantageous within CDM systems. In another embodiment, a multi-slot transmission places the payload of a packet into the first slot of the transmission and fills other slots within the transmission with zeros. Other embodiments may use other methods of distributing the payload over multiple slots for transmission over multiple slots. The payload is added to the throughput on a slot by slot basis at each update.

Alternatively, a scaling factor may be added to the payload calculation to update the update of each retransmission sub-packet. The scaling factor is used to adjust and trade-off the balance between fairness and throughput performance. Other embodiments may apply other schemes to balance the energy distributed to the various users within the system.

When multiple users share the same time interval in CDM fashion, the user with the highest priority index may be given priority to allocate required power. The remaining power will be allocated to the users with lower priority one by one based on the priority indices of the other users until the remaining power is insufficient to support any additional users. At the transmission moment, the proportional fairness algorithm generally updates the throughput for all users that have transmitted data during the time interval. Throughput updates reduce the priority index of users and therefore may reduce the chance that lower priority users transmit with better channel conditions. According to an example embodiment, at each time interval, the system updates the throughput of the highest priority user, which is a function of throughput history and DRC, such as according to equation (17). In this way, recent data transmissions are considered in calculating throughput, thereby increasing throughput values. Increased throughput results in a reduced PF value (because throughput is at the denominator defined by the PF). It is noted that the highest priority user may be defined as having the highest PF value. The throughput values for other CDM users are updated only as a function of throughput history. For example, equation (17) can be simplified as:

T(i)＝αT(i-1) (18)

in this way, recent data transmissions are not considered in calculating the throughput of other receivers, thus reducing throughput. The reduced throughput results in an increased PF. Thus, the remaining CDM receivers give an offset within the next transmission choice. Alternatively, the remaining CDM users may update their throughput and priority indices using scaling factors that are used to adjust and trade-off fairness and throughput performance.

Fig. 8 illustrates an energy map and distribution of transmission of data packets to multiple receivers. Receivers with pending data include receivers identified as A, B and C. Other receivers not illustrated may also be considered. In the first time interval from time t0 to t1, receiver a has the highest PF. In addition to receiver a, the transmitter has sufficient energy to support receiver B. At the end of the time interval, at time t1, receiver a's throughput is updated as a function of throughput history and DRC, such as by applying equation (17), while receiver B is updated as a function of throughput history only, such as applying equation (18). Receiver B has the highest PF as a result of the update value and is scheduled for transmission from time t1 to time t2 for a second time interval. In addition, receiver C is scheduled for transmission in a second time interval, and receiver a is not scheduled. Other embodiments may provide other methods to update the threshold, such as by applying a scaling factor to each receiver selected for transmission in a given time interval.

Fig. 9 illustrates a method 500 for updating throughput and PF information in a spread spectrum communication system. At step 530, the transmitter sends the data packet to a transmission group, such as illustrated in fig. 8. The transmission group has available transmission resources and the PF value of each receiver in the system with pending data. The receiver is selected based on the PF value, starting with the highest PF value, and continues to schedule the receiver until no other receivers can be supported. The transmitter transmits to each CDM receiver in the same time interval. The PF may be calculated as described above, or the PF may be calculated using other methods that take into account the performance criteria of the system and the transmission requirements of the communicating participants. According to an example embodiment, the calculation of the PF takes into account channel conditions and throughput.

In step 532, the scheduler updates the throughput value of the receiver with the highest PF in the last time interval. The update takes into account the throughput history and DRC of the receiver. At step 534, the scheduler updates the throughput of the other receivers as a function of the throughput history, regardless of the DRC. The PF value is then updated based on the updated throughput value. The PF value is then used to select a new transmission group at step 536. If there is pending data at decision block 538, the process sends the data to the transfer group at step 540 and returns to step 532. Otherwise, the process is ended.

According to another embodiment, the PF of other users is updated using the scaling factor. The scaling factor may be a function of the relative weighting of a given PF with respect to the PF value of the highest priority user. Alternatively, the scaling factor may be constant for each other user. Other schemes may implement scaling factors to achieve the desired results within a given system.

Accordingly, a method and apparatus for scheduling packet data transmissions in a wireless communication system is described. Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, circuits, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof. Other embodiments may implement a delay function, such as that specified in "Downlink scheduling in CDMA Data Networks," by Niranjan Joshi et al, ACM Mobile 2000, which is incorporated herein by reference.

Often a system will provide a relatively large margin within the desired system performance requirements that the system can achieve. For example, the system performance requirements may be designed to handle worst case requirements, where the actual operating point is outside of this condition. One embodiment first considers this large margin and takes advantage of the ARQ repetition of data. Since the ARQ scheme repeats transmissions multiple times, the repetition information can be used to gradually and statistically guess the minimum power needed to achieve the required system performance. In this way, the margin may be greatly reduced to more accurately model the operating conditions of the system.

Those of skill would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. The skilled artisan will recognize the interchangeability of hardware and software under these circumstances, and how best to implement the desired functionality for each particular application.

The various logical blocks, modules, and circuits disclosed in the illustrative embodiments herein may be implemented or performed in the manner of: digital Signal Processors (DSPs), Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) or other programmable logic devices, discrete gate or transistor logic, discrete hardware components such as: registers and FIFOs, processors executing firmware instruction sets, any conventional programmable software modules and processors, or any combination thereof to implement the functions described herein. The processor is preferably a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. The processor may reside in an application specific integrated circuit ASIC. The ASIC may reside in a phone (not shown). Alternatively, the processor may reside in the phone. A processor may be implemented as a combination of a DSP and a microprocessor, or as a microprocessor incorporating a DSP core, etc.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (11)

1. In a wireless communication system adapted for packet data transmission, the system having a plurality of mobile stations, a method comprising:

determining a raw priority factor for each of a plurality of mobile stations;

scheduling transmissions to at least one of the plurality of mobile stations based on the original priority function, wherein the first mobile station has a highest priority factor;

transmitting to a first mobile station;

determining an updated priority factor for the first mobile station; and

scheduling of transmissions to at least one of the plurality of mobile stations is based on the updated priority factor for the first mobile station and the original priority functions of the other mobile stations.

2. The method of claim 1, wherein determining the updated priority factor for the first mobile station comprises:

determining an updated throughput value for the first mobile station; and

a priority function is calculated based on the updated throughput values.

3. The method of claim 1, wherein the updated throughput value is calculated as:

T(i)＝αT(i-1)+(1-α)[DRC]

where T is the throughput, a is the scaling factor, and DRC is the payload of the transmitted information.

4. The method of claim 3, further comprising:

determining an updated priority function for at least one other of the plurality of mobile stations, wherein the updated priority function is based on an updated throughput value given by:

T(i)＝αT(i-1)

5. the method of claim 1, wherein the scheduled transmission employs a proportional-fair algorithm.

6. In a wireless communication system adapted for packet data transmission, an infrastructure element comprising:

means for determining a raw priority factor for each of a plurality of mobile stations;

means for scheduling transmissions to one of a plurality of mobile stations based on an original priority function, wherein a first mobile station has a highest priority factor;

means for transmitting to a first mobile station;

means for determining an updated priority factor for the first mobile station; and

means for scheduling transmissions to at least one of the plurality of mobile stations based on the updated priority factor for the first mobile station and the original priority functions of the other mobile stations.

7. In a wireless communication system adapted for packet data transmission and supporting automatic retransmission of data packets, said system having a plurality of mobile stations, a method comprising:

transmitting the first data packet to a first mobile station, the first mobile station having a throughput value;

updating a throughput value of the first mobile station;

receiving a negative acknowledgement signal from a first mobile station; and

the first data packet is retransmitted in response to the negative acknowledgement signal.

8. The method of claim 7, further comprising:

transmission scheduling is performed as a function of throughput values for a plurality of mobile stations.

9. The method of claim 8, wherein the data packets are transmitted over a plurality of transmission slots.

10. In a wireless communication system adapted for packet data transmission and supporting automatic retransmission of data packets, said system having a plurality of mobile stations, an infrastructure element comprising:

means for transmitting a first data packet to a first mobile station, the first mobile station having a throughput value;

means for updating a throughput value of the first mobile station;

means for receiving a negative acknowledgement signal from a first mobile station; and

means for retransmitting the first data packet in response to the negative acknowledgement signal.

11. In a wireless communication system adapted for packet data transmission and supporting automatic retransmission of data packets, the system having a plurality of mobile stations, an infrastructure element storing a plurality of computer readable instructions for implementing:

transmitting the first data packet to a first mobile station, the first mobile station having a throughput value;

updating a throughput value of the first mobile station;

receiving a negative acknowledgement signal from a first mobile station; and

the first data packet is retransmitted in response to the negative acknowledgement signal.