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

Description

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

Background

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. Wireless communications may include low latency data communications, such as voice or video transmissions, or high data rate communications, such as packetized data transmissions. High rate packet data TRANSMISSION is described in U.S. patent application No. 08/963386 filed on 3.11.1997, entitled "METHOD AND APPARATUS FOR HIGH RATE PACKET DATA TRANSMISSION", AND incorporated herein by reference.

Packet data transmissions need not be real-time transmissions, thus allowing base station flexibility in scheduling mobile user transmissions within the system. Once scheduled, the base station may transmit data to only a single mobile user for a given period of time. Generally, scheduling of packet data mobile users in a system has two purposes. The first objective is to optimize the use of each channel. A second objective is to distribute transmissions fairly to mobile users. These two purposes sometimes compete. For example, channel quality conditions and the amount of pending data for a given user may result in excessive time allocation for that user. Therefore, there is a need for a fair method for scheduling efficient packet data transmissions to mobile users.

SUMMARY

In one aspect, in a wireless communication system adapted for packet data transmission, a method comprising: receiving a rate request indicator DRR of a mobile station; determining a fairness parameter alpha of the mobile station; calculating a projected throughput value T 'of the mobile station as a function of the rate request indicator, calculating a priority function for the mobile station, wherein the priority function is DRR/(T')^αA function of (a); and scheduling transmissions to the mobile station as a function of the priority.

According to an aspect, a method for scheduling packet data services in a wireless communication system comprises: determining a user library; calculating a priority function for at least a portion of the user pool; scheduling a first group of users having pending data traffic from the pool of partial users; receiving a rate request indicator from the portion of the subscriber pool; and updating a priority function of the first group of users as a rate request indicator, the rate request indicator divided by a function of the projected throughput and fairness parameters.

In another aspect, a base station apparatus includes a processor, and a storage device coupled to the processor for storing a plurality of computer-readable instructions. The storage device includes: a first set of instructions for receiving a rate request indicator, DRR, of a mobile station; a second set of instructions for determining a fairness parameter α for the mobile station; a third set of instructions for calculating a projected throughput value T' for the mobile station as a function of the rate request indicator; a fourth set of instructions for calculating a priority function for the mobile station, wherein the priority function is DRR/(T')^αA function of (a); and a fifth set of instructions for scheduling transmissions to the mobile stations as a function of the priority.

Brief Description of Drawings

Fig. 1 illustrates, in block diagram form, a wireless communication system.

Fig. 2 illustrates, in flow diagram form, a method for scheduling packet data transmissions.

Fig. 3 illustrates in block diagram form a base station.

Fig. 4 illustrates, in block diagram form, a portion of a base station.

Detailed Description

The word "exemplary" is used exclusively herein to mean "serving as an example, instance, or illustration. Any embodiment described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments.

In an exemplary embodiment of the invention, a base station of a spread spectrum wireless communication system schedules packet data transmissions to mobile users based on instantaneous values of a per-user Priority Function (PF). The user scheduling priority is related to a PF value, wherein a high PF value indicates a high scheduling priority and a low PF value indicates a low priority. In one aspect, a method of determining the PF is based on channel conditions specified by a Rate Request Indicator (RRI). The method also takes into account fairness criteria governed by quality of service requirements (QOS). This approach provides robust protection at the transmitter side against non-zero buffer underruns. In one embodiment, the rate request indicator is carrier-to-interference ratio (C/I) information. Other embodiments may implement other types of rate request indicators or predictors. In an exemplary embodiment, the base station calculates a Priority Function (PF) for a plurality of mobile users. Each PF is a function of the rate request indicator and projected throughput for a given mobile user. The PF value enables the base station to schedule active mobile stations with pending data. Scheduling results in roughly equal sharing of the transmission times allocated to the plurality of mobile stations.

Scheduling assignments improves channel sensitivity by reducing adverse effects associated with assigned data rates. The actual data rate allocation provides a quantized transmission rate. This results in a coarse adjustment to the data rate within the system. The actual data rate may be truncated or otherwise manipulated to identify 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 operating environment of the system.

In the exemplary embodiment illustrated in fig. 1, the wireless communication system 10 includes a base station 12 that communicates with a mobile station 14 and a mobile station 16 over an air interface or radio link. The base station 12 handles individual transmissions for each mobile station 16. As illustrated, the mobile station 14 employs low-latency data communication type services, such as voice communications, while the mobile station 16 employs high-rate packet data communications. Communication between the base station 12 and the mobile station 14 is performed in real time so that all active communications are performed simultaneously and concurrently. In contrast, packet data communications with mobile stations 16 may be scheduled, where communications to multiple mobile stations 16 are transmitted simultaneously at a given time. Other embodiments may allow concurrent transmissions to more than one mobile station 16, thereby optimizing channel utilization.

Fig. 2 illustrates a method 18 of scheduling mobile stations 16 within system 10. The process begins by determining an active mobile user pool within the system 10 in step 20. The total number of mobile stations 16 (i.e., users) in the subscriber pool is designated as "N". If N is equal to 0, the process ends in step 22, otherwise, the process continues to step 24 to calculate the PF for each of a subset of "M" users in the library, where M active users have pending data. The PF calculation is performed according to the following formula:

for j 1.., M (1)

Where j is the user index corresponding to the M active users with pending data. In an exemplary embodiment, the data request indicator is implemented with a DRR (j), which is received from user j, where j 1. The rate request indicator that makes the channel sensitive appears in the numerator in proportion to the scheduling of users within system 10. Then, if the user is scheduled and the user's buffer contains enough data to transmit at the desired rate, the rate request indicator is 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), however, the actual throughput is not directly used in the calculation of equation (1).

In step 26, a further subset of "K" users is determined from the subset of M active users with pending data, which subset is to be scheduled for transmission. In an exemplary embodiment, the subset of K users is determined according to the system architecture and a predetermined scheduling policy. Typically K ═ 1 or K is constrained 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 in step 28. Note that the K scheduled users make up a subset of the N active users, i.e., (K ≦ M ≦ N). The base station 12 then transmits the packet data transmission in step 30 according to the schedule of step 28. Transmission involves the determination of transmit power, power control, data rate, modulation, and other transmission parameters. Note that the base station 12 may concurrently transmit low-latency transmissions to the mobile station 14.

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

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

the digital samples for index n use a low pass filter with filter parameters beta. In one embodiment, the time constant may be related to a target QOS and/or rate for each mobile station 16. In an exemplary embodiment, the rate request indicator is implemented with a DRR (λ), where λ 1. The rate request indicator that makes the channel sensitive appears in the numerator in proportion to the scheduling of users within system 10. 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 in the calculation of equation (1). Instead, the scheduling method makes a prediction or plan for the throughput of a 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 request. The quality of the transmission channel may be a C/I measurement of the transmission received by the user, wherein the corresponding DRR is related to the C/I ratio, such as by a look-up table. In one embodiment, the user sends the C/I ratio to base station 12, and base station 12 determines a data rate based on the C/I. Alternatively, the user may determine the data rate to request based on the measured C/I and based on errors in the transmitted data received by the user. The user may use a number of methods to determine the data rate to be requested by the base station. Similarly, a user may implement a variety of rate request indicators for requesting a data rate from a base station. Also, in one embodiment, different mobile stations 16 implement different rate request indicators.

If K < M in step 34, processing continues to step 36 to update each T' of the non-scheduled users (i.e., users not included in the M scheduled users) in the pool of N active users. The projected throughput calculation for unscheduled users is given by:

t '(i, n +1) ═ 1- β · T' (i, n) (3) where i ═ 1. Here, to calculate the projected throughput for updating each PF associated with non-scheduled users, the rate request indicator is assumed to be zero.

The updated projected throughput value is used to update the PF value. The process then returns to step 26 where any users that still have pending data continue with the updated PF value.

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

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

Fig. 4 further details the scheduler portion of the base station 12. The base station 12 includes a pool calculation unit 40 for determining the number and identity of mobile stations 16 active at a given time. The active mobile station 16 communicates with the base station 12 but may not have any pending data traffic. The library calculation unit 40 receives control information from the mobile stations 16 and BSCs (not shown), and also receives traffic from a network (not shown). Then, the library calculating unit 40 supplies the User identification information "User (User) ID (λ)" (where λ ═ 1.., N) to the PF calculating unit 42. User identification information is provided for all N active users within system 10.

The PF calculation unit 42 receives a data rate request indicator, such as DRR (λ), from the mobile station 16. The PF calculation unit 42 determines the PF of each user using the rate request indicator according to formula (1). Pf (j) (1., K) of all users with pending data is provided to scheduling unit 46. The scheduling unit 46 determines a schedule among the users associated with pf (j). The scheduling unit 46 provides scheduling information to the transmit circuitry 48. DATA IN (DATA IN) is also provided to transmit circuitry 48, which transmits DATA IN accordance with the scheduling information to produce DATA OUT (DATA OUT). The scheduling information is also provided to the calculation unit 50, which updates the projected throughput for the active N users. Scheduled users are updated according to equation (2) and unscheduled users are updated according to equation (3). To update the projected throughput value, the calculation unit 50 receives a rate request indicator for the mobile station 16. The updated projected throughput values for the M subsets of users with pending data are then provided back to the PF calculation unit 42 to update the PF value. The calculation unit 50 comprises a smoothing filter, such as an Infinite Impulse Response (IIR) filter. The tap coefficients of the smoothing filter are configurable.

In one example, the velocity of the mobile station 16 is 3km/hr and experiences a Doppler frequency, fdoppler, of 5.4 Hz. The projected throughput is subject to IIR smoothing filtering according to equations (2) and (3) with a time constant TW of about 2 seconds. The IIR filter tap coefficient β is related to the time constant TW by the following relationship:

resulting in a time constant of 1/100, i.e., 50 frames/sec, for a given frame duration of 20 milliseconds. In general, the calculation of β involves first determining the quality of service of the transmission reflecting the fairness constraint, where each mobile station 16 is assigned a time portion within a predetermined tolerance. This calculation then optimizes a to achieve the best true system throughput.

In one embodiment, the denominator of the priority function is modified to a function f (T '), where the function is a monotonic function of T ', such as (T ')^α. In this embodiment, α is a fairness parameter. Introducing an exponential function of throughput changes the fairness versus overall throughput tradeoff. When applied to a proportional fairness algorithm,orAs with other scheduling algorithms, there is a tradeoff between fairness and throughput. An increase in a correspondingly increases the fairness of the scheduling, however, reduces the overall throughput.

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, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

Those of skill would further appreciate that the various illustrative logical blocks, modules, 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. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

The implementation or execution of the various illustrative logical blocks, modules, and algorithm steps described in connection with the embodiments described herein may be implemented or performed with: a general purpose processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. 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. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a subscriber unit. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

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 (13)

1. In a wireless communication system adapted for packet data transmission, a method comprising:

receiving a rate request indicator DRR of a mobile station;

determining a fairness parameter alpha of the mobile station;

calculating a projected throughput value T' for the mobile station as a function of the rate request indicator;

calculating the priority function of the mobile station as DRR/(T')^α(ii) a And

transmissions to the mobile stations are scheduled as a function of priority.

2. The method of claim 1, wherein said calculating a priority function further comprises using a monotonic function (T')^αA priority function is calculated.

3. The method of claim 1, wherein each of the rate request indicators is a data rate request received from one of a plurality of mobile stations.

4. The method of claim 1, wherein each of the rate request indicators is a request for a carrier-to-interference ratio received from one of a plurality of mobile stations.

5. The method of claim 1, further comprising:

data is transmitted to the plurality of mobile stations in response to the scheduled transmission.

6. The method of claim 1, further comprising:

the priority function of the scheduled mobile stations is updated as a function of the rate request indicator.

7. The method of claim 7, further comprising:

assuming that the rate request indicator is equal to zero, the priority function of the unscheduled mobile stations is updated.

8. A method for scheduling packet data traffic in a wireless communication system, comprising:

determining a user library;

calculating a priority function for at least a portion of the user pool;

scheduling a first group of users having pending data traffic from the pool of partial users;

receiving a rate request indicator from the portion of the subscriber pool; and

the priority function of the first group of users is updated as a function of a rate request indicator divided by the projected throughput and fairness parameters.

9. The method of claim 8, further comprising:

a second group of users in the portion of the user pool is requested to be updated at a rate of zero value, the second group of users being different from the first group of users.

10. The method of claim 8, wherein the partial user pool is users with pending data.

11. The method of claim 10, wherein the first set of users comprises one user.

12. A base station apparatus, comprising:

a processor; and

a storage device coupled to the processor, the storage device for storing a plurality of computer-readable instructions, comprising:

a first set of instructions for receiving a rate request indicator, DRR, for a mobile station;

a second set of instructions for determining a fairness parameter α for the mobile station;

a third set of instructions for calculating a projected throughput value T' for the mobile station as a function of the rate request indicator;

a fourth set of instructions for calculating a priority function for the mobile station, wherein the priority function is DRR/(T')^αA function of (a); and

a fifth set of instructions for scheduling transmissions to the mobile stations as a function of the priority.

13. The method of claim 12, wherein the instructions further comprise:

the sixth set of instructions for calculating the priority function further comprises calculating the priority function asDRR/(T′)^αAs a function of (c).