HK1070525B - Method and apparatus for scheduling transmissions in a wireless communication system - Google Patents

Description

Method and apparatus for scheduling transmissions in a wireless communication system

Priority application according to 35U.S.C. § 120

This patent application claims priority from U.S. provisional application No. 60/283,885, filed on 12/4/2001, assigned to the assignee of the present invention and specifically incorporated herein by reference.

Reference to related pending application

This patent application relates to U.S. patent application No. 09/796,583 entitled System FOR communicating IN A COMMUNICATION System, filed on 27.2.2001, assigned to the assignee of the present invention and hereby incorporated by reference.

Technical Field

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

Background

Communication systems, and in particular wireless systems, are designed with the goal of efficiently allocating resources among multiple users. In particular, wireless systems are directed to providing sufficient resources to meet the requirements of all subscribers while minimizing costs. Various scheduling algorithms have been developed, each based on predetermined system standards.

In a wireless communication system using a code division multiple access, CDMA, scheme, a scheduling method allocates all code channels to each of subscriber units at specified time intervals on a time multiplexed basis. A central communication node, such as a base station, BS, implements a unique carrier frequency or channel code associated with a subscriber to enable private communication with the subscriber. TDMA schemes may also be implemented in landline systems using physical contact relay switching or packet switching. A CDMA system may be designed to support one or more standards such as: (1) "TIA/EIA-95-B Mobile Station-Base Station compatibility Standard for Dual-Mode Wireless band Spread Spectrum Cellular System", herein referred to as IS-95 standard; (2) the standards provided by the association entitled "third generation partnership project," herein referred to as 3 GGP; and implemented in a set of files including file numbers 3G TS 25.211, 3G TS 25.212, 3G TS 25.213, 3G TS 25.214, and 3G TS 25.302, referred to herein as the W-CDMA standard; (3) the standard provided by the association entitled "third generation partnership project 2", herein 3GGP2, and TR-45.5, herein referred to as cdma2000 standard, formerly IS-2000 MC; or (4) some other wireless standard.

In communication systems, and in particular wireless systems, users are typically assigned to categories, each of which has an associated system performance criteria. For example, each category is treated differently with respect to fairness criteria, where each user in a category is treated similarly. These categories may be processed according to the priority of each category. In one system, users are classified according to the services used in the system, such as according to a service plan. Several categories may exist in a communication system.

Accordingly, there is a need for a method and apparatus for scheduling transmissions in a communication system for multiple classes of user applications. Therefore, a scheduling method and apparatus that accommodates multiple different scheduling priorities is needed.

Disclosure of Invention

Embodiments disclosed herein address the above stated needs by providing an apparatus for scheduling data transmissions in a wireless communication system. The generic scheduler allows scheduling of multiple mobile stations, where each mobile station may have a different delivery priority parameter. The delivery priority parameter defines a parameter that affects the required data transmission delivery rate. For example, the delivery priority parameter may be a required throughput, a required time allocation, a required time delay, etc. Each of the transfer priority parameter values is mapped to a common scale (common scale) referred to as a mapping priority parameter. Then selecting an operating point and extracting a mapping priority parameter value corresponding to each mobile user. The common scheduler then uses the common mapped priority parameter value to schedule the mobile users. In other words, each user is scheduled to get the same proportion of the portion within the corresponding delivery priority parameter.

According to one aspect, in a wireless communication system, a method comprises: receiving channel condition indicators from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications; determining a fairness indicator as a function of throughput to a plurality of mobile users; and determining a transmission schedule for the plurality of mobile users, wherein the transmission schedule is a function of the channel condition indicator and the fairness indicator.

In another aspect, a program embodied on a computer-readable medium containing computer-executable instructions comprises: a first set of instructions for processing channel condition indicators received from a plurality of mobile users; a second set of instructions for determining a fairness indicator as a function of throughput to a plurality of mobile users; and a third set of instructions for determining a transmission schedule for the plurality of mobile users as a function of the channel condition indicator and the fairness indicator.

In yet another aspect, a method for transmitting data between a remote station of a plurality of remote stations and a base station in a wireless communication system comprises: receiving at a base station information transmitted by a remote station; and adjusting at least one tier of service parameters specific to one remote station based on the information.

In yet another aspect, a method of scheduling data transmissions in a wireless communication system comprises: receiving values of delivery priority parameters from each of a plurality of mobile users, and mapping each delivery priority parameter to a mapping priority parameter if any of the delivery priority parameters are of different types; and determining an operating point based on the mapped priority parameters of the plurality of mobile users.

According to another aspect, an apparatus in a wireless communication system comprises: a processing unit and a memory storage unit coupled to the processing unit, the memory storage unit adapted to store computer-readable instructions for performing: receiving a value of a delivery priority parameter from each of a plurality of mobile users; mapping each delivery priority parameter to a mapping priority parameter; and determining an operating point based on the mapping priority parameter for each of the plurality of mobile users.

Drawings

The features, objects, 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. 1A is a wireless communication system;

FIG. 1B is a wireless communication system supporting high data rate transmission;

fig. 2 is a flow chart of a class of service, GOS, and algorithm for scheduling data transmissions in a wireless communication system;

fig. 3 is a flow chart of a scheduling algorithm for data transmission in a wireless communication system;

FIGS. 4A and 4B are flow diagrams of a proportional-fair algorithm for scheduling data transmissions in a wireless communication system;

fig. 5 is a flowchart of a combined scheduling algorithm for performing a proportional-fair algorithm and a GOS algorithm in a wireless communication system;

FIG. 6 is a flow diagram of a general scheduler for a wireless communication system;

fig. 7 is a wireless communication system supporting a combined scheduling algorithm such as that shown in fig. 5 and 6; and

fig. 8 is a flow chart of a scheduling algorithm for a wireless communication system.

Fig. 9A illustrates the mapping of various delivery priority parameter ranges to a common mapping priority parameter range.

Fig. 9B, 9C and 9D illustrate the determination of various operating points on a plurality of mapping priority parameters.

FIG. 10 shows a flow chart of a general scheduler.

Detailed Description

Modern communication systems are required to support a variety of applications. One such communication system IS a Code Division Multiple Access (CDMA) system that conforms to the TIA/EIA-95 mobile station-base station compatibility standard for dual-mode wideband spread spectrum cellular systems and its progeny, hereinafter referred to as IS-95. CDMA systems allow voice and data communication between users over a terrestrial link. The use of CDMA technology IN MULTIPLE access communication SYSTEMs is disclosed IN U.S. Pat. No. 4,901,307, entitled "SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS," and U.S. Pat. No. 5,103,459, entitled "SYSTEM AND METHOD FOR GENERATING WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM," both of which are assigned to the assignee of the present invention and are incorporated herein by reference.

In a CDMA system, communication between users is conducted through one or more base stations. In a wireless communication system, the forward link refers to the channel through which signals travel from a base station to subscriber stations, and the reverse link refers to the channel through which signals travel from subscriber stations to a base station. A first user in one subscriber station communicates with a second user in a second subscriber station by transmitting data on the reverse link to the base station. The base station receives data from the first subscriber station and routes the data to a base station serving the second subscriber station. Both may act as a single base station or multiple base stations depending on the location of the subscribing subscriber station. In any case, instead of communicating with the second subscriber station, which may also communicate with the terrestrial internet through a connection with the serving base station, the base station serving the second subscriber station transmits data on the forward link. In wireless communications, such as those conforming to IS-95, the forward link and reverse link signals are transmitted in disjoint frequency bands.

Fig. 1A is an example of a communication system 100, the communication system 100 supporting a number of users and capable of performing at least some aspects and embodiments of the present invention. Any of a variety of algorithms and methods may be used to schedule transmissions in system 100. The system 100 provides communication for a number of cells 102A through 102G, each of which is served by a respective base station 104A through 104G. In the exemplary embodiment, some base stations 104 have multiple receive antennas, while other base stations have only one receive antenna. Similarly, some base stations 104 have multiple transmit antennas, while other base stations have only a single transmit antenna. There is no limitation on the combination of the transmit antenna and the receive antenna. Thus, it is possible for the base station 104 to have multiple transmit antennas and a single receive antenna, or to have multiple receive antennas and a single transmit antenna, or to have both single or multiple transmit and receive antennas.

Terminals 106 in the coverage area may be fixed (i.e., stationary) or mobile. As shown in fig. 1, the various terminals 106 are dispersed throughout the system. Each terminal 106 communicates with at least one base station 104 and possibly more base stations 104 on the downlink and uplink at any given moment, e.g., depending on whether soft handoff is used and whether the terminal is designed and operated to receive multiple transmissions (simultaneously or sequentially) from multiple base stations. Soft Handoff in CDMA communication systems is well known in the art and is described in detail in U.S. Pat. No. 5,101,501, entitled "Method and System for providing a Soft Handoff in a CDMA Cellular Telephone System," which is assigned to the assignee of the present invention.

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 the exemplary embodiment, some terminals 106 have multiple receive antennas and others have only one receive antenna. In fig. 1A, base station 104A transmits data on the downlink to terminals 106A and 106J; 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 service expansion available through wireless communication technologies has led to the development of specific data services. One such service is referred to as High Data Rate (HDR). An exemplary HDR service IS proposed in "EIA/TIA-IS 856 cdma2000 High Rate Packet Data air interface Specification," referred to as the "HDR Specification". In general, the HDR service is an overlay (overlay) of a voice communication system, which provides an efficient method of transmitting data packets in a wireless communication system. The limited bandwidth available for radio transmission becomes a very scarce resource when the amount of data transmitted and the number of transmissions increase. Therefore, there is a need for an efficient and fair method of scheduling transmissions in a wireless communication system that optimally uses the available bandwidth. In an exemplary embodiment, the system 100 shown in fig. 1 is compliant with a CDMA type system with HDR service.

Fig. 1B shows AN infrastructure reference model of a communication system 120, the communication system 120 having AN access network AN122 communicating with AN access terminal AT 126 over AN air interface 124. In one embodiment, system 10 is a code division multiple access, CDMA, system having a high data rate, HDR, overlay system, such as that specified in the HDR standard. AN122 communicates over AN air interface 124 with AT 126 and any other ATs in system 120 (not shown). AN122 includes a plurality of sectors, where each sector provides at least one channel. A channel is defined as a set of communication links used in a given frequency assignment for transmissions between AN122 and AN AT. The channels include a Forward Link (FL) for transmissions from AN122 to AT 126, and a Reverse Link (RL) for transmissions from AT 126 to AN 122.

For data transmission, AN122 receives a data request from AT 126. The data request specifies the data rate at which the data is transmitted, the length of the data packet transmitted, and the sector from which the data is transmitted. AT 126 determines the data rate based on the channel quality between AN122 and AT 126. In one embodiment, the quality of the channel is determined by the carrier-to-interference ratio, C/I. Alternate embodiments may use other metrics corresponding to channel quality. The AT 126 provides a request for data transmission by transmitting a data rate control, DRC, message via a specific channel called a DRC channel. The DRC message includes a data rate portion and a sector portion. The data rate portion represents the data rate requested by the AN122 for transmitting data, and the sector represents the sector from which the AN122 transmits data. Generally, both data rate and sector information are required to handle data transmission. The data rate part is called DRC value and the sector part is called DRC cover. The DRC value is a message sent to the AN122 over the air interface 124. In one embodiment, each DRC value corresponds to a data rate in kbit/sec (kilobits/second) having an associated packet length assigned according to a predetermined DRC value. The allocation includes a DRC value specified as a zero data rate. In effect, a zero data rate indicates to the AN122 that the AT 126 is unable to receive data. For example, in one case, the channel quality is not sufficient for the AT 126 to accurately receive the data.

In operation, the AT 126 continuously monitors the channel quality to calculate the data rate AT which the AT 126 can receive the next data packet transmission. The AT 126 then generates a corresponding DRC value; the DRC value is sent to the AN122 to request data transmission. Note that data transmissions are typically broken into packets. The time required to transmit a data packet is a function of the applied data rate.

This DRC signal also provides information that the channel scheduler uses to determine the instantaneous rate of consumption information (or receive transmitted data) for each remote station associated with each queue. According to one embodiment, a DRC signal transmitted from any remote station indicates that the remote station is capable of receiving data at any one of a plurality of effective data rates. Such a Variable Rate transmission System is disclosed in U.S. patent No. 6,064,678, entitled "Method for Assigning an optimal packet Length in a Variable Rate Communication System," which is assigned to the assignee of the present invention and incorporated herein by reference.

Support for HDR transmission and adaptation to tune to multiple users is shown in FIG. 7An example of a communication system for data transmission. Fig. 7 is described in detail below, in particular, wherein a base station 820 and a base station controller 810 interface with a packet network interface 806. Base station controller 810 includes a channel scheduler 812 for performing scheduling algorithms for transmissions in system 800. The channel scheduler 812 determines the length of the service interval during which data is transmitted to any particular remote station based on the remote station's associated instantaneous rate for receiving data (as represented in the most recently received DRC signal). The service time interval may not be contiguous in time, but may occur once every N slots. According to one embodiment, a first portion of a packet is transmitted during a first time slot at a first time and a second portion is transmitted at a subsequent time 4 time slots later. Also, subsequent portions of the packet are transmitted in multiple slots having a similar 4-slot range (i.e., 4 slots apart from each other). According to one embodiment, the instantaneous rate of receiving data Ri determines the length L of the service interval associated with a particular data queue_i。

In addition, the channel scheduler 812 selects a particular data queue for transmission. The associated amount of data to be transmitted is then retrieved from the data queue 830 and provided to the channel element 826 for transmission to the remote station associated with the data queue 830. As described below, the channel scheduler 812 selects the queue that provides the data, which is transmitted in the ensuing service interval using a channel including information associated with the weight of each queue. The weights associated with the transmitted queues are then updated.

Note that even if only a portion of the packet is transmitted, it is possible for the user to correctly receive the packet. This occurs when the channel conditions are better than the channel conditions that the user has previously considered. In this case, the user may send an "ACK" (acknowledgement) signal to the base station indicating that the packet has been correctly received and that the remainder of the packet need not be transmitted. When this occurs, the entire data packet is effectively transmitted to the user over a shorter service interval, thereby increasing the effective data rate at which data is transmitted. The base station then reallocates the time slots originally scheduled to transmit the remaining portion of the packet and transmits another packet to the same user or a different user. This process is commonly referred to as automatic repeat request (ARQ).

In a system that supports ARQ, data packets are scheduled for a predetermined number of transmissions, where each transmission may include different information. Other packets are inserted into the multiple transmissions sequentially. When the receiver has received enough information to decode and process the packet, the receiver sends an indication to the transmitter that no further information for the current packet is needed. The transmitter is then free to schedule another packet with the time slot originally intended for the current packet. In this way, system resources are saved and transmission time to the receiver is reduced.

A block diagram illustrating the basic subsystems of an exemplary variable rate communication system is shown in fig. 7. The base station controller 810 interfaces with the packet network interface 806, the public switched telephone network PTSN 808, and all base stations in the communication system (only one base station is shown in fig. 7 for simplicity). The base station controller 810 coordinates communication between remote stations in the communication system and other users connected to the packet network interface 806 and the PTSN 808. The PTSN 808 interfaces with other users through a standard telephone network (not shown in fig. 7).

The base station controller 810 includes a number of selector elements 816, although only one is shown in fig. 7 for simplicity. Each selector element 816 is assigned to control communications between one or more base stations 820 and a remote station (not shown). If selector element 816 has not been assigned to a given remote station, call control processor 818 is notified that a remote station needs to be paged. Call control processor 818 then directs base station 820 to page the remote station.

The data source 802 includes a large amount of data to be transmitted to a given remote station. Data source 802 provides data to packet network interface 806. Packet network interface 806 receives the data and routes the data to selector element 816. Selector element 816 then transmits the data to each base station 820 in communication with the target remote station. In the exemplary embodiment, each base station 820 maintains a data queue 830 that stores data to be transmitted to remote stations.

Data is sent in data packets from data queue 830 to channel element 826. In an example embodiment, on the forward link, a "data packet" refers to a large amount of data up to 1024 bits and a large amount of data to be transmitted to a destination remote station in a predetermined "time slot" (such as ≈ 1.667 milliseconds). For each data packet, channel element 826 inserts the required control fields. In the exemplary embodiment, channel element 826 performs a cyclic redundancy check, a CRC, an encoding of the data packet and control fields, and an insertion of a set of tail bits. The data packet, control field, CRC parity bits, and code tail bits comprise a formatted packet. In an example embodiment, channel element 826 then encodes the formatted packet and interleaves (or reorders) the symbols in the encoded packet. In an example embodiment, the interleaved packet is covered with a walsh code and spread with short PNI and PNQ codes. The spread data is provided to an RF unit 828, and the RF unit 828 quadrature modulates, filters, and amplifies the signal. The forward link signals are transmitted over the air through an antenna to the forward link.

At the remote station, the forward link signal is received by an antenna and routed to a receiver. The receiver filters, quadrature demodulates and quantizes the signal. The digitized signal is provided to a demodulator (DEMOD) which despreads the signal with short PNI and PNQ codes and decovers with walsh codes. The demodulated data is provided to a decoder, which performs the inverse of the signal processing functions performed at base station 820, in particular, the de-interleaving, decoding, and CRC check functions. The decoded data is provided to a data sink.

As noted above, the hardware supports variable rate transmission of data, messages, voice, video, and other communications on the forward link. The rate of data transmitted from the data queue 830 varies to accommodate the signal strength and noise environment at the remote station. Preferably, each remote station transmits a data rate control, DRC, signal to the associated base station 820 at each slot. The DRC signal provides information to the base station 820 including the identity of the remote station and the rate at which the remote station receives data from its associated data queue. Thus, circuitry at the remote station measures the signal strength and estimates the noise environment at the remote station to determine the rate information to be transmitted in the DRC signal.

The DRC signal transmitted by each remote station propagates through the reverse link channel and is received at base station 820 through a receive antenna coupled to RF unit 828. In the exemplary embodiment, the DRC information is demodulated in a channel unit 826 and provided to a channel scheduler 812 located in the base station controller 810 or to a channel scheduler 832 located in the base station 820. In the first exemplary embodiment, the channel scheduler 832 is located in the base station 820. In a further embodiment, the channel scheduler 812 is located in the base station controller 810 and is connected to all selector units 816 in the base station controller 810.

In the first exemplary embodiment described above, channel scheduler 832 receives information from data queue 830 indicating the amount of data queued for each remote station, also referred to as the queue size. The channel scheduler 832 then performs scheduling based on the DRC information and queue size for each remote station serviced by the base station 820. If the queue size requires a scheduling algorithm to be used in further embodiments, the channel scheduler 812 may receive queue size information from the selector unit 816.

During transmission of a packet to one or more users, the users transmit an "ACK" signal after each slot that includes a portion of the transmitted packet. The ACK signal transmitted by each user travels through the reverse link channel and is received at base station 820 via a receive antenna coupled to RF unit 828. In the exemplary embodiment, the ACK information is demodulated in channel element 826 and provided to channel scheduler 812 located in base station controller 810 or channel scheduler 832 located in base station 820. In the first exemplary embodiment, the channel scheduler 832 is located in the base station 820. In a further embodiment, the channel scheduler 812 is located in the base station controller 810 and is connected to all selector units 816 in the base station controller 810.

Embodiments of the present invention are applicable to other hardware architectures capable of supporting variable rate transmission. The present invention can be readily extended to include variable rate transmission on the reverse link. For example, instead of determining the rate at which data is received at the base station 820 based on the DRC signal from the remote station, the base station 820 measures the strength of the signal received from the remote station and estimates the noise environment to determine the rate at which data is received from the remote station. Base station 820 then transmits to each associated remote station at the rate at which data is transmitted from the remote station on the reverse link. Base station 820 may then schedule transmissions on the reverse link based on the different rates on the reverse link in the same manner as described herein for the forward link.

Also, the base station 820 in the above-described embodiments transmits to one, or some, of the remote stations using a Code Division Multiple Access (CDMA) scheme, while excluding the remaining remote stations associated with the base station 820. At any particular moment, the base station 820 transmits to one of the remote stations, or some of the remote stations, by using a code assigned to the receiving base station 820. However, the present invention is also applicable to other systems using different time division multiple access, TDMA, methods that provide data to select base stations 820 with the exclusion of other base stations 820 to optimally allocate transmission resources.

Channel scheduler 812 schedules variable rate transmissions on the forward link. The channel scheduler 812 receives a queue size indicating the amount of data to send to the remote station and a message from the remote station. Preferably, channel scheduler 812 schedules data transmission to achieve the system goal of maximum data throughput while meeting fairness constraints.

As shown in fig. 1, remote stations are dispersed throughout a communication system and may communicate with zero or one base station on the forward link. In the exemplary embodiment, channel scheduler 812 coordinates forward link data transmissions throughout the communication system. Scheduling methods and Apparatus for high speed data transmission are described in U.S. patent No. 08/798,951 entitled "Method and Apparatus for Forward Link Rate Scheduling", filed 11/2/1997, assigned to the assignee of the present invention and hereby expressly incorporated by reference.

According to one embodiment, channel scheduler 812 is implemented in a computer system that includes a processor, random access memory, RAM, and program memory for storing instructions to be executed by the processor (not shown). The processor, RAM, and program memory may be dedicated to the functions of the channel scheduler 812. In other embodiments, the processor, RAM, and program memory may be part of a shared computing resource for performing additional functions at the base station controller 810. In an example embodiment, a general scheduler is applied to the system 800 shown in FIG. 7, which will be described in detail below. These modules for implementing the priority function of scheduling data transmissions in the BSC (base station controller) 810 and BS (base station) 820 are discussed after establishing the details of the general scheduler.

As the demand for wireless data applications has grown, the demand for extremely efficient wireless data communication systems has increased dramatically. The IS-95 standard IS capable of transmitting traffic data and voice data on the forward and reverse links. According to the IS-95 standard, traffic data and voice data are divided into code channel frames of 20 milliseconds in width and at data rates up to 14.4 Kbps. In an IS-95 system, at least one of a finite number of orthogonal forward link channels IS assigned to each subscriber station. The forward link channel continues to be allocated to the subscribing subscriber station while communication is ongoing between the base station and the subscribing subscriber station. When providing data services in an IS-95 system, forward link channels continue to be allocated to subscriber stations even during times when no forward link data IS being transmitted to the subscriber stations.

A significant difference between voice services and data services lies in the fact that the former imposes accurate and fixed delay requirements. Typically, the total one-way delay of a speech frame is specified to be less than 100 milliseconds. In contrast, data delay can be a variable parameter used to optimize the efficiency of a data communication system.

Another significant difference between voice services and data services is that the former requires a fixed and common grade of service (GOS) for all users. Generally, for digital systems providing voice services, this translates into a fixed and equal transmission rate for all users, and a maximum allowable value for the error rate of the speech frames. In contrast, for data services, there may be different GOS from user to user and may be one parameter that is optimized to increase the overall efficiency of the data communication system. Generally, the GOS of a data communication system is defined as the total delay occurring in the delivery of a predetermined amount of data (hereinafter referred to as data packets).

Yet another significant difference between voice services and data services is that the former requires a reliable communication link, which in the exemplary CDMA communication system is provided by soft handoff. Soft handoff results in redundant transmissions from two or more base stations to improve reliability. However, for data transmission this additional reliability is not needed, since the received erroneous data packets can be retransmitted. For data services, the transmit power used to support soft handoff may be more efficiently used to transmit additional data.

The transmission delay and the average throughput rate required to communicate data packets are two attributes that define the quality and efficiency of a data communication system. The transmission delay affects data communications differently than it affects voice communications, but is an important measure of the quality of a data communication system. The average throughput rate is a measure of the efficiency of the data transmission capability of the communication system. There is a need in the art for communication systems that provide improved data throughput while providing GOS that is appropriate for the type of service being used for the wireless channel.

The need for a generalized scheduler is based on the requirements and objectives of data transmission in a wireless system. For data transmission, the throughput is defined in terms of the delay that occurs in the transmission of data packets rather than in terms of individual bits or bytes. Data packets such as internet protocol, IP, datagrams are an indivisible unit and in most cases receiving only a part of a packet does not include enough information for the user to decode and use the entire packet, i.e. the packet is useless for the user. The end user receives the data packet, performs a cyclic redundancy check, CRC, on the data packet, and processes the data. Thus, the user is most concerned about the arrival time of the last bit of the packet, and not much about the delay of individual bits in the data packet. This allows considerable flexibility in rate allocation for different users on a time scale that is less than the transmission time of a data packet. Furthermore, in a transmission control protocol, TCP, type connection, some variation in packet delay is acceptable, as long as the variation that undesirably causes TCP retransmission is not too unpredictable.

Another characteristic of a wireless channel is the variability of the channel itself. In HDR-type systems, this variability results in the requested rate varying over a period of time. In order to maximize the use of the channel, the scheduler is designed to serve high-rate users, i.e., users requesting the highest data rate. This means that, occasionally, when the rate requested by the user is low, the user may have a period of time during which no service is available. Overall throughput will be maximized when the scheduler does not serve low rate users for a longer period of time. Ideally, however, the scheduler balances this requirement for packet delay and delay variation relatively consistently, as described above.

Another aspect considers fair treatment of multiple users in a system. To achieve a fair scheduling approach, the scheduler ideally allocates the total throughput among the different users. Different systems use different bases of fairness (or allowed unfairness) to affect the needs and desires of the individual systems. In many scheduling algorithms, the concept of fairness is a key concept. In serving different users, a different amount of adaptability is fairly provided, thus having an impact on the total throughput of the sector.

According to one embodiment, a method and apparatus for scheduling transmissions for use in a communication system at multiple user levels incorporates a generalized scheduler. The generalized scheduler is adapted to a plurality of different scheduling priorities. A generalized scheduler that maintains a high throughput for all users serves different levels of users each having specific transmission requirements.

In an example embodiment, the operation of the generalized scheduler performs a priority function of the channel condition metric and the fairness criterion, wherein the priority function is defined as:

f(A_i(t)，U_i(t))(1)

wherein A is_i(t) refers to a channel condition measure, and U_i(t) refers to a user fairness metric. Function A_i(t) specifies the degree of need to provide service to user i at time t based on the current channel conditions. Function U_i(t) specifies the degree of need to provide service to user i at time t based on the past history of the received service. The priority function f () combines two desirability metrics, A_i(t) and U_i(t) to determine a priority level for each user.

Referring to fig. 9A, in an example embodiment, each of a plurality of users has a required criteria for receiving transmissions from the same base station. The scale used by the measurement criteria is referred to herein as the transmit priority parameter (DPP), where the DPP reflects the priority required by each user. For example, a first user may request to receive a transmission at a specified time allocation, while a second user may request to receive a transmission at a specified throughput. Further, a third user may request to receive a transmission with a specified delay. The DPP of the first user reflects the time scale; the DPP of the second user reflects a scale of bits per second (bps); while the DPP of the third user reflects the time delay scale. Each user's DPP identifies a specific value of the required criteria for receiving the transmission.

The DPPs of multiple users are mapped onto a common scale. The common scale is an unitless, proportional representation of a range of values in the DPP. As shown in fig. 9A, each of the DPPs may have a different range of values, with each of the different DPP ranges mapped onto a common scale. The mapping of the actual values of a particular user in the DPP range is referred to herein as the Mapped Priority Parameter (MPP).

Fig. 9B shows a first DPP to MPP mapping case, where three different DPP types are labeled A, B and C. For each of the three types, the horizontal axis represents DPP range. The vertical axis represents the MPP range of values. For clarity of understanding, in FIG. 9B, the DPP type A indicates a throughput parameter measured in bits per second; type B DPP represents a time scale parameter, measured as a unitless ratio of the proportion of time allocated to one user to the total time allocated to all users; and DPP type C indicates the proportion of time delay measured as a unitless ratio. Further, additional embodiments may implement any DPP type specific to a given system; further embodiments may include actual time units rather than the proportional values described in the examples herein. Providing a range of values for a given DPP over a predetermined range. For example, the values of type A DPP range from 0bps to the maximum supported by the system. Similarly, the value of the type B DPP ranges from 0, where the user does not receive a transmission, to a predetermined maximum value for all transmissions in the user's reception transmission time. The values of type C DPP range from no delay to maximum delay.

Type a is an increasing function, where MPP-1 corresponds to a maximum value and MPP-0 corresponds to a minimum value. Type B is also an increasing function, where MPP 1 corresponds to a maximum value and MPP 0 corresponds to a minimum value. Note that type C is a decreasing function, where MPP-1 corresponds to no delay and MPP-0 corresponds to maximum delay. The MPP range reflects the minimum to maximum values of the DPP. In other words, the MPP range utilizes the DPP range. Additional mappings may be incorporated to provide a common basis for estimating the various DPPs. With continued reference to fig. 9B, an operating point is selected within the MPP range of 1 to 0. The operating point reflects the available resources to satisfy each of the users as reflected in the scope of the DPP. The operating point is first the exact value of each DPP within the provided range. For example, the operating point defines a value of d3 for type A, a value of d2 for type B, and a value of d1 for type C. These will become the operating points for individual users with these DPPs. The values d1, d2, d3 are specific values in each of the ranges interpreted according to the corresponding DPP unit. Interpreting the value d1 as bps; interpreting the value d2 as a proportion of time; and the value d3 is interpreted as a proportion of the delay.

Fig. 9C illustrates the same DPP to MPP mapping, where different operating points are selected. Type B and C DPPs give a common value d4, while type A gives a different value d 5. Fig. 9D illustrates additional DPP to MPP mapping. However, the function generated here is a reduction function, so the function is not linear. The working point defines the DPP value d 6.

FIG. 10 illustrates a flow diagram of a generalized scheduler method 1200 in accordance with one embodiment. At step 1202, the generalized scheduler receives DPP-type information from each of the N users. The DPP type information provides the generalized scheduler with information for determining the operating point among the N users. At decision block 1204, the generalized scheduler determines whether all the DPP values are equal for all pairs of users, i.e., regardless of the absolute value of the unit. If all DPP pairs have equal values, the process proceeds to step 1212 to apply the generalized scheduler defined by equation (1) above. If the DPP values are not all equal, processing continues to step 1206 to map each DPP range to a corresponding MPP range, such as shown in FIGS. 9A-9D. At step 1208, the generalized scheduler determines the operating points supported by the resources available to each user. At step 1210, the process determines the exact DPP value to continue operation for each user application operating point. Processing then continues to step 1212 to apply the generalized scheduler algorithm defined by equation (1) above. As such, the generalized scheduler algorithm applies a common MPP operating point to each user regardless of the individual DPP. Once the MPP operating point is selected, the generalized scheduler extrapolates back to the exact DPP values within each DPP range. Each user can request a different priority parameter where the generalized scheduler applies a common scale for scheduling.

According to an example embodiment, the generalized scheduler pair has the highest priority function f (A) among a given class or type of users_i(t)，U_i(t)) provide services. In an example embodiment, by a priority function f (A)_i(t)，U_i(t)) the value obtained as a function of the channel conditions A_i(t) increases with increasing fairness function U_i(t) is increased and decreased. Define function A accordingly_i(t) and U_i(t) of (d). Further, the priority function f () is a function of at least one time period for measuring the channel condition metric and the user fairness metric. In further embodiments, the priority function f () may be a function of each user with respect to time. However, for simplicity, it is preferable not to leave the combining function common to all users and modify the user fairness metric to reflect user requirements. Also, for clarity of discussion, consider the priority function as a division operation (division operation).

The channel condition metric takes advantage of the variation in channel conditions. This metric may be defined as DRC, DRC/DRcave (DRC mean), DRC-DRcave or a constant value, as described below. To maximize the gain of multi-user diversity, the selected channel quality metric should have a larger value when the channel condition is better than the average condition of the users. For clarity of discussion, the illustrative embodiments consider DRC/DRcave as the channel condition metric. Of particular importance is the definition of DRDave. The averaging should be done over the channel condition time constant, Tc. As such, the channel condition metric is expected to vary with DRC on a time scale less than Tc. Changes in DRC value that occur over a time period greater than Tc are considered to be long-term and have equal effect on both the numerator and denominator of the channel condition metric, and thus cancel each other out. The value of Tc is selected by observing the channel dynamics. If the channel dynamics are such that the DRC value varies significantly over the length of the time scale, i.e. T1, the time constant Tc should be greater than T1. Note that the channel condition metric should use the maximum time constant allowed by the user requirements.

According to an example embodiment, the fairness metric per user class is effectively kept constant. If the selected channel condition metric and the trend of the channel condition metric oscillate around 1, the scheduler will tend to serve users with low user fairness metric values. Thus, the generalized scheduler is similar to an algorithm that achieves the benefits of multi-user diversity while keeping the user fairness metric constant. Determining the user fairness metric such that the state most needed by each user results in a user fairness metric of the same numerical value allows the system to serve users having many different types of requirements. Also, the slope around the desired operating point will determine how excess capacity or deficit capacity is allocated among different users. The key to gaining insight into the scheduling of different users is to keep the user fairness metric constant while taking advantage of multi-user diversity.

In a system where users are classified according to service, different classes of users are served according to priority or other schemes, such as in a non-prioritized manner. Consider first a single category or type of user. Example embodiments use the highest f (A)_i(t)，U_i(t)), however, alternative embodiments may use a lowest value and/or another type of function. f (), (A)_i(t)，U_i(t)) determines the validity of the scheduling.

The present invention is applicable to a variety of scheduling algorithms and prioritization and is not limited to those described herein. For clarity, several scheduling algorithms will be discussed to provide examples of generalized schedulers and various implementations.

Embodiments of the present invention are directed to a system and apparatus for allocating resources among a plurality of subscribers to a communication network served by a single communication node. In each discrete transmission time interval, or "service time interval," an individual subscriber utilizes limited resources of the communication node excluding all other subscribers. Individual subscribers are selected to utilize limited resources based on weights or scores associated with the individual subscribers. The change in weight associated with an individual subscriber is preferably based on an instantaneous rate at which the individual subscriber is able to consume a limited resource.

In one embodiment, the AT 126 covers the DRC value with a DRC cover. The DRC cover is a code applied to identify the sector to transmit data. In one embodiment, the DRC cover is a walsh code applied to the DRC values, with a unique code corresponding to each sector in the active set of the AT 126. The current AT 126 transmits and receives information using the active set, AS, that constitutes the sectors. When the DRC value specifies a data rate and the DRC cover identifies a transmitting sector, the DRC value and the DRC cover provide a complete data request. Alternate embodiments may use alternate overlays or methods of identifying the transmitting sector. Yet another embodiment may include sector identification in the DRC value.

One example of a scheduler that can be implemented using a generalized scheduler framework is an equal time scheduler, which improves system throughput by taking advantage of multi-user diversity. The channel condition metric for this scheduler is DRC/DRCave as described above. In particular, at any time t, the scheduler calculates a channel condition metric a for each user i_i(t)。A_i(t) ═ drci (t)/drcavei (t), where drci (t) is the received DRC signal, which represents the channel condition from user i at time t, and drcavei (t) is given by the following equation:

DRCavei(t)＝DRCavei(t-1)(1-1/ta)+DRCi(t-1)(1/ta)(2)

where ta is the time constant for averaging.

Giving a user fairness metric (U)_i(t)) is fraci (t), wherein fraci (t) is defined using the following formula:

fraci(t)＝fraci(t-1)(1-1/tu)+Servedi(t-1)(1/tu)(3)

user i is Served during time slot t-1, then Served i (t-1) is 1, and if user i is not Served during time slot t-1, then Served i (t-1) is 0. Note that fraci (t) is the average score of the time spent servicing user i, where the averaging is done according to equation (2).

The scheduler then calculates a for each user, at each time slot t, and among those users having data to transmit_i(t)/U_i(t) toward the highest A_i(t)/U_i(t) one user of the service providing unit.

Another example of a scheduler that can be implemented using a generalized scheduler framework is an equal time scheduler that improves system throughput by taking advantage of multi-user diversity, but also provides two different quality of service to two different classes of users. One class of users, class a users, is sensitive to packet delay, so the scheduler provides service with less jitter than another class, class B. The channel condition metric for this scheduler is DRC/DRCave as described above. In particular, at any time t, the scheduler calculates a channel condition metric a for each user i_i(t) is:

Ai(t)＝DRCi(t)/DRCavei(t) (4)

where drci (t) is the received DRC signal, which represents the channel condition from user i at time t, and drcavei (t) is given by the following equation:

DRCavei(t)＝DRCavei(t-1)(1-1/ta)+DRC(t-1)(1/ta) (5)

where ta is the time constant for averaging.

User fairness metrics (U) for users in class A_i(t)) is fracia (t), wherein fracia (t) is defined using the following formula:

fraci(t)＝fraci(t-1)(1-1/tu)+Servedia(t-1)(1/tua)(6)

wherein if class A user i is served during time slot t-1, then Seredia (t-1) is 1, and if class A user i is not served during time slot t-1, then Seredia (t-1) is 0. Note that fracia (t) is the average fraction of time spent servicing user i, where the averaging is done according to equation (5).

User fairness metrics (U) for users in class B_i(t)) is fracib (t), where fracib (t) is defined using the following formula:

fracib(t)＝fracib(t-1)(1-1/tub)+Servedib(t-1)(1/tub)(7)

wherein Servedbi (t-1) is 1 if class B user i is served during time slot t-1, and Servedbi (t-1) is 0 if class B user i is not served during time slot t-1. Note that fracib (t) is the average fraction of time spent servicing user i, where the average is made according to equation (5). The scheduler calculates a for each user at each time slot t and among those users having data to transmit_i(t)/U_i(t) for a compound having the highest A_i(t)/U_i(t) the user providing the service.

In the case of tua < tub, U representing a user in class A_i(t) comparing U of users in class B_i(t) decays faster. As a result, users in class a are provided more frequently with services than users in class B; however, each time a user in class a gets service, it takes only a small amount of time. Overall, the scheduler spends an equal amount of time servicing each user.

Another example of a scheduler that may be implemented using a generalized scheduler framework is a proportional-fair scheduler that improves system throughput by taking advantage of multi-user diversity. The channel condition metric for this scheduler is DRC/DRCave as described above. In particular, at any time t, the scheduler calculates a channel condition metric a for each user i_i(t) is:

Ai(t)＝DRCi(t)DRCAVEI(t) (8)

where drci (t) is the received DRC signal, which represents the channel condition from user i at time t, and drcavei (t) is given by the following equation:

DRCavei(t)＝DRCavei(t-1_(1-1/ta)+DRCi(t-1)1/ta) (9)

where ta is the time constant for averaging. Giving a user fairness metric (U)_i(t)) ServerRateaveei (t)/DRCavei (t), wherein ServerRateaveei (t) is defined using the following formula:

ServedRateavei(t)＝

ServedRateavei(t-1)(1-1/ta)+Served_Rate(t-1)(1/ta)(10)

where the Served _ Ratei (t-1) is the rate at which user i is Served during time slot t-1 and 0 if no service is provided to the user during time slot t-1. Note that the Served _ Ratei (t-1) is the average data rate used to serve user i, where the averaging is according to equation (9).

Now the scheduler calculates a for each user in between each time slot t and the user with pending data to send_i(t)/U_i(t) for a compound having the highest A_i(t)/U_i(t) the user providing the service.

Still another example of a scheduler that may be implemented using the generalized scheduler method is the class of service scheduler. The principle of the class of service scheduler is to keep the bit rate ratio between any two users within a predetermined value G. The class of service scheduler maintains the bit rate ratio requirement over a given time interval. This scheduler improves system throughput by taking advantage of multi-user diversity over short time intervals. The channel condition metric for this scheduler is DRC/DRCave as described above. At any time t, the scheduler calculates a channel condition metric a for each user i_i(t)。A_i(t) ═ drci (t)/drcavei (t), where drci (t) is the received DRCA signal representing the channel condition from user i at time t, and drcavei (t) is given by:

DRCavei(t)＝DRCaei(t-1)(1-1/ta)+DRCi(t-1)(1/ta) (11)

where ta is the time constant for averaging.

The user fairness metric (U) is calculated as follows_i(t)). At each time slot, a measure of the total throughput of the system, i.e., the sum of the throughputs of all users served by the base station, is stored and referred to as Rtotal. One possible way to keep track of Rtotal is to perform the following calculation at each time slot t:

Rtotal(t)＝

Rtotal(t-1)(1-1/ttotal)+SystemServedRate(t-1)(1/ttotal)(12)

where SystemServerdRate (t-1) is the rate at which the system provides service to any of its users at time t-1, and 0 if no users are served at time t-1, where ttotal is a suitably chosen time constant.

Also, a weight W is maintained for each user. When a data packet having a length of B bytes is transmitted to a user and the data rate of the user is less than Rtotal at the time of transmitting the packet, the weight W is incremented by B x G. The weight W is incremented by B after the B byte packet is sent to the user, and the data rate of the user is greater than or equal to Rtotal at the time the packet is sent. Since the weight W varies with time, it is represented as W (t). Also, since each user has a different weight, we use subscripts to identify the user to which the weight belongs. Thus, the weight of user i at time t is denoted as wi (t).

There is also a parameter known as collaar. Collar is a number that is specified as a scheduler parameter and does not change over time. Let wmin (t) be the smallest weight among all users at time t. For stations with weights between Wmin (t) and Wmin (t) + CollarHaving users, measuring the user fairness U_i(t) is defined as 1. In one case, for all other users, U is assigned_i(t) is defined as a large constant, say 1000.

The scheduler then calculates a for each user at each time slot t and among those users having undetermined data to transmit_i(t)/U_i(t) for a compound having the highest A_i(t)/U_i(t) the user providing the service.

As described above, transmissions in systems that support data transmission, such as HDR systems, may be scheduled using a variety of scheduling schemes. One method is called grade of service, GOS, scheduling algorithm. Fig. 2 illustrates a GOS scheduling algorithm applicable to the system 100 of fig. 1, wherein each active user, or mobile station, MS, sends a data rate request to the base station, BS. The GOS scheduler provides a way to select users for data transmission that maintains the rate ratio between any pair of two users, thus satisfying the corresponding fairness criteria. In other words, the fairness criteria of the GOS scheduler ensures that the throughput of each user is proportional to each of the other users.

The scheduler method 200 is performed at the base station and considers a group of active users, wherein a user is a member of the active group when there is pending data to communicate between the user and the base station. Given a total number of active users N, the index i identifies the individual members of the active set. For data transmission, each of the N users in the active set instructs the base station to transmit data at the data rate requested by the user. The data rate information is provided as a data rate request message. In one embodiment, the data rate request is a data rate control, DRC, message. The data rate request message indicates the quality of the forward link, FL.

With continued reference to fig. 2, at step 202, each of the N users transmits a DRC value. At step 204, the base station determines the throughput for each of the N users based on the number of bits transmitted. The base station transmits to each of N usersAnd thus the number of bits sent to each user acknowledgment during a given time period. The throughput for user i is given as Ti. The second index j is used to identify the user as a companion to user i. At decision block 206, the base station determines the ratio of the throughput of all users in the active set, user i to user j. This ratio is then compared to a fair standard ratio, G:for all i and j (13)

Note that the throughput increases with increasing G, as given in equation (13). The increased throughput comes at the expense of fairness, with higher G values allowing for greater variation in throughput for different users. Fairness, in this sense, refers to the actual number of bits sent to a given user. If the ratio of equation (13) does not satisfy the equations for any combination of users i and j, then at step 210 the base station determines a scheduler to obtain or approximate the relationship of equation (13). In this case, the base station will generally increase the transmission for users with low throughput values. In this manner, the ratio of users with the lowest throughput to users with the highest throughput is reduced. If equation (13) is satisfied at decision block 206, the base station determines a scheduler to keep the throughput ratio approximately below or equal to G at step 208. The scheduler is applied at step 212 and the process returns to step 202 to receive the next set of data rate request messages, e.g., DRC.

Another scheduling algorithm that may be applied to the system 100 is illustrated in fig. 3. The scheduling method 250 initializes the weight for each user at step 252. The weights are priority indicators, with larger weights indicating the importance of the user transmission. Further embodiments may implement different importance of the weights. The weights may be determined by a variety of factors, including, but not limited to, by the service plan selected by the user. At step 254, the base station selects the user with the smallest weight. The base station calculates the rth rate threshold at step 256 and compares the rth to the user selected rate at decision block 258. The base station calculates the rate threshold as the average of all instantaneous rates associated with the users having data. Preferably, this calculation eliminates the instantaneous rate associated with the user that does not include data. The base station compares the R-th rate threshold value with the rate selected by the user and if the user rate exceeds the R-th threshold value, then at step 260 the base station increments the weight associated with this user by a lower value, preferably a number representing the amount of data in units such as bits, bytes or megabytes to be transmitted during the subsequent service interval. If the user rate does not exceed the R-th threshold value, step 262 increments the user's weight by a higher value, preferably "K" times the amount of data, such as bits, bytes, or megabytes, to be transmitted during the subsequent service interval.

K is preferably selected based on fairness criteria that supports allocation of service intervals to remote stations or users having capacity to receive data at higher rates. The size of K is selected by the system designer based on the extent to which remote stations supporting reception of data at higher rates exceed lower receiving remote stations. With larger values of K, the base station's more efficient forward link. However, this efficiency comes at the cost of subscribers to slower receiving users who deprive the forward link of transmission resources. Therefore, the system designer preferably selects the value of K in a manner that balances two competing goals: 1) increase the overall efficiency of the forward link and 2) prevent severe deprivation of slower receiving users. Selected users having an associated faster instantaneous data rate (i.e., exceeding the R-th threshold) will tend to have associated weights that are incremented by only a small amount, while selected users having a lower data rate (i.e., not exceeding the R-th threshold) will have associated weights that are incremented by a significantly larger amount. The method 250 of fig. 3 tends to support users of the service who receive data at a relatively fast rate over those remote stations that receive data at a lower data rate. This trend enhances throughput efficiency of base stations transmitting data in the forward link; however, as the weights associated with the normally selected queues associated with users having higher received data rates (i.e., exceeding the R-th threshold) continue to be incremented, these weights eventually approach the weights of the queues associated with the normally less selected queues associated with users having lower received data rates (i.e., not exceeding the R-th threshold). The receiving process will then start to support slower receiving users when the weight of the faster receiving users starts to exceed the weight of the slower receiving users. This imposes a fairness constraint on the selection process by preventing faster receiving users from excluding slower receiving users from dominating the forward link transmission resources of the base station.

Yet another scheduling method is referred to as a proportional fair scheduler which has a fairness criterion that attempts to equalize the transmission time of all users in the active set. According to the proportional fair scheduling method, the base station tracks parameters associated with each user i as a function of time, such as data rate, R_i(t) of (d). The base station receives DRC information from each user in the active set and calculates a ratio for each user in the active set:

DRCi/Ri(14)

the ratio effectively compares the current channel conditions to the recent past. For a given user, if the DRC is high while the parameter R is low, the user is considered a good candidate for transmission. A decreasing R value indicates that the user has not received a data transmission from the base station in the recent past. A high DRC indicates that the user has detected good channel conditions. According to one embodiment, the calculation given for the user parameter R is:

where D represents the data rate received during a predetermined time interval T and T_cRepresenting the most recent time interval under consideration. The most recent data rates are weighted more heavily to reflect the actual conditions of each user.

Fig. 4A illustrates a combination of the above methods, wherein the data rate threshold value is applied to the instantaneous value in a predetermined time period and the GOS criterion is applied over a time period defined by the predetermined time period. The method 400 first initializes a timer to track the GOS time period at step 402. At step 404, if the timer time has not expired, i.e., is also within the GOS time period, processing continues to step 420 of fig. 4B to determine a priority function for each user. In an exemplary embodiment, the priority function is the data rate of the user, R_i(t) of (d). At step 422, the base station selects a winner according to the priority function and transmits the data at step 424. If at step 426 the data is not yet pending, processing returns to step 420, otherwise processing for this time period ends.

With continued reference to fig. 4A, if the timer has expired at step 404, i.e., the GOS time period is complete, processing continues to step 406 to receive DRCs from other users. At step 408, the base station determines the throughput for each user based on the number of bits transmitted. The ratio is then compared to the fair standard ratio, G, given in (15) herein. If the ratio of equation (13) does not satisfy the equations for any combination of users i and j, the base station determines the scheduler to obtain or approximately obtain the relationship of equation (13) at step 414. In this case, the base station will generally increase the transmission for users with low throughput values. In this manner, the ratio of users with the lowest throughput to users with the highest throughput is reduced. If equation (13) is satisfied at decision block 410, the base station determines the scheduler to keep the throughput ratio near less than or equal to G at step 414. The scheduler is applied at step 416 and the process returns to step 402 to receive the next set of data rate request messages, e.g., DRC.

A specific example of the method 400 illustrated in fig. 4A and 4B is provided in fig. 5. At step 602, the method 600 first determines a minimum weight among the M users. Method 600 further determines collar K for the selected user at step 604 and calculates (M + K) at step 606. For those users transmitting a valid DRC and having pending data, if the weight of the user is much smaller than the calculated value of (M + K), the process proceeds to step 612 to select one user according to the channel conditions. Otherwise, processing continues to step 610 to select the user with the smallest weight. The weights of the selected users are updated at step 614 and the process returns to step 602.

One scheduling algorithm proposed for the forward link in an HDR system provides service level fairness over only the small time period allowed by the granularity of the HDR encoder packets. Defining class of service fairness means that the throughput seen by two users should not differ from each other by more than a ratio G: 1 over a certain time period, where G ═ 1. Another way of describing the same thing is that over an arbitrary time period of length t,

wherein b is_A(t) and b_B(t) is the number of bits users a and B receive, respectively, over a time period of length t. The GOS scheduling algorithm first initializes all weights associated with the queues to a nominal weight value of zero. The algorithm then selects a queue for transmission and transmits packets from the selected queue. All the weights for all queues are then updated. The algorithm then selects the next queue for transmission.

The selected queue is initialized to no input and given a negative infinite weight. The process then considers the next queue and checks whether the algorithm has enough time for the next queue to complete the data packet transmission before scheduling to begin control channel transmission. If there is not enough time, the process checks for additional queues. This process continues until a queue is found that can complete the transmission in the available time. The algorithm compares the current queue weight to the weight of the selected queue. If the current queue weight is less than the selected queue weight, the algorithm selects the current queue and stores the weight in memory. Otherwise, if the current queue weight is equal to the weight of the selected queue, the algorithm performs the following checks: (a) can the current queue use a current time slot at least as long as the selected queue? (b) Is a remote station in the current queue able to receive at a higher rate than the rate of the selected queue? If both answers are yes, the algorithm selects the current queue and stores the associated weight in memory. The process is repeated for all queues. If no data is pending, there is no selected queue at that point.

The proportional fairness algorithm results in an increase in sector throughput as the number of active users increases. The GOS algorithm does not have this feature. This difference is caused by maintaining a fair time scale. The proportional fairness scheme does not guarantee fairness on a time scale shorter than the average throughput calculator. As a result, there is adaptability to rescheduling transmissions for different users over a short period of time to gain benefits in channel condition variations. As long as these time periods are short enough that packet delays are not significantly allowed.

However, the proportional fairness algorithm also changes the notion of fairness from the class of service schedulers. Thus, in the worst case, the ratio of bit rates for individual users may be as large as the maximum ratio of requested rates (64: 1 for one embodiment of an HDR system). This is undesirable. It is desirable to take the benefits of channel variation over a short period of time to increase throughput but maintain a level of service fairness over a longer period of time.

As described above, the scheduler according to the concept of fair GOS generally guarantees that equation (16) is satisfied over all time intervals. Modifying equation (16) to include a constant value C yields the following expression

Over an extended time interval, i.e. a large value of t, atTime interval b_A(t) and b_BThe number of bits transmitted during (t) will be very large compared to C. At the limit where t goes to infinity, the new rule is reduced to the old rule. This provides a level of service fairness over long periods of time. However, the number of bits sent to users a and B over a short period of time may have any ratio. Thus, by carefully selecting C, the system can be designed to determine which time period is considered short and which time period is considered long. This allows freedom to violate the GOS fairness criteria over a short period of time, so the system is free to use any scheme that maximizes throughput. The modified algorithms discussed herein differ from each other in that: how each algorithm optimizes performance by taking the benefit of this freedom, and, in addition, how each algorithm determines the value of C.

However, the further scheduling algorithms, which are executed in a similar way to the GOS algorithm described above, may differ depending on the implementation of the user selection process introducing a parameter or constant value C into the selection step. As described above, in one embodiment, the GOS algorithm selects one user having the smallest weight identified by the variable M among the users having valid DRC messages. In a further embodiment, the scheduling algorithm selects one user having a weight in a range defined by a constant value C around the least weighted user, i.e. the range is defined as M + C. In other words, the algorithm implements one margin with respect to the minimum weight. A group of users having weights in a predetermined range, i.e., a weight range determined by (M + C), may be determined. The selection process in the range may be based on additional criteria including, but not limited to, a requested data rate, such as a DRC value, or a function thereof. Various embodiments may implement similar scheduling methods, where the method used for selecting users from this group may vary from one scheduling scheme to another. The minimum weight user is a user having the smallest weight in a group of all valid users including a valid user having no pending data and a valid user having an invalid DRC message. It is therefore possible that no user in this group has pending data and a valid DRC, wherein the user with the smallest weight is chosen among the remaining users to transmit, i.e. the user with more than (M + C) weight but pending data and valid DRC in the valid group.

Fig. 8 illustrates a scheduling algorithm 900 according to one embodiment, wherein the method determines a minimum weight M for a user or queue at step 902. A range value C is determined at step 904, where the value is used to define a range of weights in which further selection criteria may be used. At step 906, the method calculates the range as M + C and determines a set of users in the range at step 908. If at least one user in the group has pending data and a valid DRC message, processing continues to criteria 914 to select the next user from the group. If no user in the group has pending data and a valid DRC message, the group is defined not to include users in the group defined by the range of M + C. In other words, the group is redefined in step 912 as a group of users having weights greater than M + C, and processing returns to 908. If at least one user in the group has pending data and a valid DRC message, processing continues to step 914 to select the next user from the group. Note that if no user has pending data and a valid DRC in the active set, no transmission is to be processed. The criteria used to select a user or queue from a group may be referred to as a desirability measure.

In one embodiment, the value C is a constant, regardless of the number of users. Similar to the proportional fair type algorithm, a filtered version of the average throughput for each user is implemented as the desirability measure. For example, according to one embodiment, the desirability measure is defined as the currently requested data rate minus the average throughput value for a given user.

According to another embodiment, C is a constant and the desirability measure is equal to the currently requested data rate. This method is referred to as a modified GOS algorithm applying a high DRC value.

According to yet another embodiment, C is a constant and maintains a filtered version of the average throughput for each user as in a proportional-metric algorithm. In this embodiment, the desirability metric is set equal to the currently requested data rate divided by the average throughput.

In yet another embodiment, the value of C is proportional to (1/number of active users). A filtered version of the average throughput for each user is maintained in the same manner as the proportional fairness scheme and the desirability metric is set equal to the current requested data rate divided by the average throughput.

In one embodiment, the scheduling algorithm controls the channel scheduler 812 of fig. 7 for scheduling transmissions from the base station 820 to the remote station. As described above, a data queue 830 is associated with each remote station. The channel scheduler 812 assigns a "weight" to each data queue 830, which weight is estimated for selecting a particular remote station associated with the base station 820 to receive data in a subsequent service interval. The channel scheduler 812 selects individual remote stations to receive data transmissions in separate service time intervals. The channel scheduler first initializes the weight for each queue associated with the base station 820.

The channel scheduler 812 cycles through a series of transmission time intervals or service time intervals. The channel scheduler 812 determines whether any additional queues are to be added due to the association of additional remote stations 6 with the base station 820 detected in the previous service interval. The channel scheduler 812 also initializes the weights associated with the new queue. As described above, the base station 820 receives DRC signals from each remote station associated therewith at regular time intervals, such as time slots.

Example embodiments of the present invention are applicable to a variety of scheduling algorithms and effectively derive many fairness criteria. Fig. 6 illustrates a scheduling method 700 of an example embodiment, first estimating channel conditions and preparing channel condition indicators at step 702. A fairness indicator is selected at step 704. The fairness indicator is a measure for estimating the fairness of the implemented scheduling method. The requirement is to optimize system resources by maximizing throughput without incurring delays for users with little pending data or poor channel conditions. Further, the method provides a service according to a category of each user. Fairness criteria include, but are not limited to, the following types: 1) proportional fair method as a function of channel conditions and throughput; 2) a packet-by-Packet General Processor Sharing (PGPS) method as a function of throughput and user priority; 3) an equal time method as a function of service time; 4) GOS method as a function of throughput; and 5) a service time method as a function of the wait time and the last boundary completed.

With continued reference to fig. 6, at step 706, the method 700 determines a fairness indicator as a function of throughput. At step 708, each user is estimated as a function of the channel condition indicator and the fairness indicator. The scheduler is determined from the estimate of step 708 and applied in step 710. According to example embodiments, multiple methods are available for channel condition estimation, and thus, multiple combinations of channel condition indicators and fairness indicators are available for use in scheduling.

Fig. 7 illustrates a system 800 that includes a base station controller, BSC, section 810, and BS section 820 in communication with a network. The network includes a data source 802 and a data sink 804, each in communication with a network packet interface 806. In addition, the network may include the public switched telephone network, PSTN, 808. BSC 810 includes a channel scheduler 812, fairness selector 814, selector element 816, and call control processor 818. Packet network interface 806 is coupled to selector element 816 and call control processor 818. Call control processor 818 reacts to changes in the active set of users in system 800. The selector element 816 determines the target participant of the communication and makes the appropriate connection. Selector element 816 is also coupled to BS 820. Fairness selector 814 allows BSC 810 to implement the required fairness criteria and provide the information to channel scheduler 812. Fairness selector 814 can also receive a fairness indicator designation from BS 820.

BS820 includes a channel scheduler 832 that provides information to channel element 826 with the user selected for the next data transmission. BS820 further comprises a data queue 830, an RF unit 828, a fairness selector 824, and a microprocessor 822. Fairness selectors 814, 824 may implement method 700 shown in fig. 6.

As described above, example embodiments allow for the classification of multiple users according to a priority scheme or other scheme. Consider a system that supports two groups of users. The first group has delay requirements, while the second group simply requires best effort services. The delay requirement of the first group indicates that transmission occurs with less than a predetermined delay and is therefore a higher priority group than the second group. In an example embodiment, user i is a member of the first group. User i specifies that the packet delay for transmission on the forward link, or downlink, is less than a predetermined delay d_iWherein user i will use a predefined level f of adaptability_iTo implement the delay. A second group of users is provided access to the time slots in an equal time manner. The required scheduler will provide multi-user diversity while meeting the requirements of each different user in different ways for scheduling the first and second groups of users. For clarity of illustration, the channel condition metric is not changed.

The first step is to determine a suitable user fairness metric, which is described by a function that is different for the two classes of users. A further limitation is that both the first and second sets produce the same digital value at the required operating point. For example, consider a user fairness metric defined as:

wherein W_i(t) is the delay suffered by a data packet that has been waiting the longest time in the queue of user i that has pending data at time t. This function has the property that when the delay of a packet is d_iWhen it takes 1, but when the delay reaches d_i+f_iIt tends towards 0. The goal is to maintain d_iDelay of (d), but allow it to go towards d_i+f_iThen high, i.e. stays within the required delay range.

For the second group of users, the exemplary embodiment provides the best effect with respect to data packet delay by providing an equal time schedule to all users. To get equal time scheduling, the method may use a user fairness metric, such as:

U_i(t)＝n*frac_i(t)(19)

where n is the total number of users in the sector (of both groups) and frac_i(t) is the fraction of time slots used to serve this user. Calculation of frac by passing through an IIR filter with appropriate time constants_iThe value of (t). This metric is rated at1 for each user, but the actual resulting value depends on the recent channel conditions and the presence of other groups of users. Note that this metric decreases more slowly over time when no service is provided to the user than the metric defined for the first set of users.

For a user, a low value of this metric provides the user with a high priority. This implies that if two users (one per group) are at the rating of the user fairness metric (i.e., user fairness equals 1), but they cannot be served because the scheduler is serving another user, the user fairness metric for the first group of users will drop faster and therefore it will be served from the scheduler earlier than the second group of users. This feature is true because the second group of users only requires best effort services, while the first group conforms to strict last-line boundaries.

Considering the example detailed above, it is possible to identify several differences that help determine a suitable user fairness metric. The time constant, T, should be made_cKept short, allowing processing and taking into account time scales greater than T_cTo the user.

Each scheduler may have a nominal operating point where the scheduler will schedule service to users such that each user gets the same numerical value of the user fairness metric. The metric is to be defined so as to take into account differences in different user requirements. Another consideration is to have a slope around the nominal operating point, indicating that the increase in fairness is a function of the received service. Where fairness tends to support those users with higher priority services at the expense of those users with lower priority services. According to one embodiment, the user fairness metric slope as a function of received service is always negative for decreasing service priority. A sensitivity of 1/(user fairness metric) should take into account the allowed adaptability per user requirement.

For implementations of generalized schedulers for wireless communication systems such as that shown in fig. 7, fairness criteria and channel condition criteria are applied to the channel scheduling function. Implementing the channel condition metric may include providing a channel feedback mechanism, for example. The feedback mechanism may be an explicit indicator, such as a user-provided DRC, or an implicit indicator, such as a C/I measurement. The channel condition indicators and methods used for estimation and scheduling may be system specific. The channel condition indicators are not limited to those provided above, but are provided as examples for clarity of understanding, as detailed herein. Reliable measurement of channel quality is desirable.

Similarly, a reliable measure of user fairness is desirable. When a base station initializes and processes transmissions to a user, the base station has sufficient knowledge of the number of bits or packets transmitted to a particular user in a given time period. The base station uses this information to estimate throughput, accuracy and fairness. The fairness metric can be a function of the system to which it is applied and is therefore not limited to the fairness metric provided above.

Although not explicitly stated, there is no effective limitation on the service to prevent multiple users at the same time. The generalized scheduler may be as f (A)_i(t)，U_i(t)) orders the users in descending order, and if serving the first user in the list leaves the remaining capacity for service, the next user can be served at the same time. Parallel processing by more than one user maximizes bandwidth usage and optimizes system throughput as a whole.

Fig. 4A shows a combination of the above methods, wherein the data rate threshold value is applied to instantaneous values in a predetermined time period and the GOS criterion is applied over a time interval defined by the predetermined time period. The method 400 first initializes a timer to track the GOS time period at step 402. If the timer has not expired at step 404, i.e., is still in the GOS time period, then the process proceeds to step 420 of fig. 4B to determine a priority function for each user. In an example embodiment, the priority function is the data rate of the user, ri (t). At step 422, the base station selects a winner according to the priority function and transmits the data at step 424. If at step 426 the data is still pending, processing returns to step 420, otherwise processing for this time period ends.

With continued reference to fig. 4A, if the timer has expired at step 404, i.e., the GOS time period is complete, the process proceeds to step 406 to receive DRCs from other users. At step 408, the base station determines the throughput for each user based on the number of bits transmitted. The value is then compared to the fairness criteria ratio value, G, given in equation (13) above. If the ratio of equation (13) does not satisfy the equations for any combination of users i and j, then the base station determines to derive or approximately derive the scheduling for the relational equation of equation (13) at step 414. In this case, the base station will generally increase the transmission to users with low throughput values. As such, the ratio of users with the lowest throughput to users with the highest throughput is reduced. If equation (13) is satisfied at decision block 410, the base station determines a schedule at step 414 that keeps the throughput ratio approximately less than or equal to G. Scheduling is applied at step 416 and processing returns to step 402 to receive the next set of data rate request messages, e.g., DRC.

A specific example of the method 400 illustrated in fig. 4A and 4B is provided in fig. 5. At step 602, the method 600 first determines a minimum weight among the M users. Method 600 further determines collar K for the selected user at step 604 and calculates (M + K) at step 606. For those users transmitting a valid DRC and having pending data, if the weight of the user is much smaller than the calculated value of (M + K), the process proceeds to step 612 to select one user according to the channel conditions. Otherwise, processing continues to step 610 to select the user with the smallest weight. The weights of the selected users are updated at step 614 and the process returns to step 602.

One scheduling algorithm originally proposed for the forward link in HDR systems provides service level fairness over only the small time period allowed by the granularity of the HDR encoder packets. Defining class of service fairness means that the throughput seen by two users should not differ from each other by more than a ratio G: 1 over a certain time period, where G ═ 1. Another way of describing the same thing is that over an arbitrary time period of length t,

wherein b is_A(t) and b_B(t) is the number of bits users a and B receive, respectively, over a time period of length t. The GOS scheduling algorithm first initializes all weights associated with the queues to a nominal weight value of zero. The algorithm then selects a queue for transmission and transmits packets from the selected queue. All the weights for all queues are then updated. The algorithm then selects the next queue for transmission.

As described above, example embodiments provide a method for scheduling transmissions among a plurality of users by using for a channel condition indicator and a fairness indicator. As an example, consider a proportional fair scheduler in the framework of a generalized scheduler according to an example embodiment. The function f () defining equation (1) is a simple division operator. The channel condition metric ri (t) is given as:

Ri(t)＝DRC₁(t)/average DRC_i(t) (21)

The user fairness metric is given as:

Ui(t)＝average_throughput_i(t)/average_DRC_i(t)(22)

considering equation (1), the resulting method is the one with the highest DRC_i(t)/average_throughput_i(t) provides a service, which is a proportional fair scheduler. In this case, all averaging is done using an infinite impulse response, IIR, filter with a predetermined time constant. Examination of the expressions provided above reveals that the multi-user diversity gain is a function of, i.e., introduced by, the channel condition metric. Using per user averagesThe time period used for DRC calculates the control of the channel condition metric. The user fairness metric gives the actual fairness in the algorithm. The channel condition metric for each user is given a value around 1. Thus, the relative amount of throughput received by different users over a long period of time is mostly affected by the user fairness metric rather than the channel condition metric. In particular, the relative throughput achieved by the users will be such that the fairness metrics for each user achieve the same value.

Further, the user fairness metric for a given user can be restated as: DRcave while served

If the DRC (in dB) of all users varies with the same statistics around the mean, the ratio of DRcave _ while _ served and DRcave for all users is the same, resulting in equal time behavior of the algorithm.

The advantage of rewriting the proportional fair scheduler formula is that an equal time scheduler results. The equal time scheduler has a gain due to multi-user diversity. The channel condition metric remains the same as that according to the proportional fairness algorithm, but now an equal time for each user is guaranteed by applying the user fairness metric defined by fraction _ of _ slots _ served. In one embodiment, this fraction is averaged using an IIR filter with the same time constant as the current proportional fair algorithm.

Further, as described above, example embodiments allow for individual ones or groups of users to be treated differently according to a classification scheme (differentiation of treatment). In this way, different user fairness metric values can be assigned to different users. If the user fairness metric for class j users is defined as:

Ui(t)＝a_j*average_throughput(t)/average_DRC(t)(24)

then compared to other user classes, where class j users will receive a ratio of (1/a)_j) Relative priority of (2). For example, consider applying the GOS algorithm to a generalized scheduler, the channel condition metric for all users at all times is 1 (i.e., the algorithm does not take advantage of multi-user diversity), and the user fairness metric is the weight assigned to the user. Recall that the weights are assigned in such a way as to obtain GOS fairness while maximizing sector throughput. The combination function is the operator given in equation (10). This example illustrates that for different choices of f, A_i(t) and U_i(t) will affect the same algorithm. In other words, when estimating the priority function, for A_i(t) and U_i(t) the resulting algorithm is the same. For example, consider that f () is a different operator, i.e., f (a, b) ═ a-b, with 0 as the channel condition metric and the weight as the user fairness metric. The result is close to GOS algorithm, and the currently served user is the user with the lowest weight.

In the modified class of service algorithm, one parameter called collar is used and all users with weights in the margin or range of the smallest weight value (i.e., min _ weight to (min _ weight + collar)) are served according to the channel conditions. If no user with pending data to send or a valid DRC to send is found within the range, the method selects the user with the smallest weight among the users. The user fairness metric is then defined to be 1 for all users within this range (i.e., between min _ weight and min _ weight + collar, and infinity for the other users). Various channel condition metrics may be used for example embodiments, including, but not limited to: 1) DRC; and

2)DRC/DRCave。

the enhanced equal time scheduler may be developed according to an equal time scheduler. According to one embodiment, in the enhanced equal time scheduler method, the time constant Tc is associated with a user fairness metric. The time constant Tc may be defined to be equal to a predetermined number of slots based on experience with simulation of the transmission control protocol, TCP, where it is unimportant that the change in throughput over the time scale is less than Tc. However, it is possible that different users have different adaptations in the applied timescale depending on the currently running application. In one embodiment, the user fairness metric continues to calculate the average throughput per user or per group of users, where the user fairness metric calculation uses individual, i.e., different, time constants to calculate the average per user. The use of different time constants per user results in different variations in the average fraction of time slots around each user. Small variations are due to the application of small time constants. The slot fraction per user remains approximately equal. Similar enhancements are possible with other user fairness metrics, such as the metric used by the proportional fair scheduler (average _ throughput/average _ DRC). The application of the priority function f () provides different variability in throughput with respect to each individual user.

For HDR operation of system 120, AN122 and AT 126 each include a processor and AT least one memory storage device, in addition to signal processing modules. The processor may be a central processing unit or may be a dedicated controller. The memory storage devices store computer readable instructions and/or routines that control communication in the wireless system 120. In AN122, the memory storage device may store instructions to control data transmission. In the AT 126, the memory storage device may store instructions that control the sending of data, including data requests.

In one embodiment, a wireless communication system supports a transmission protocol that may result in an actual received data rate that is higher than the requested data rate. One such system is an HDR system incorporating an ARQ scheme. In such a system, a user sends a data rate request message, such as a DRC message, to a transmitter, such as a base station or an access terminal. The DRC message indicates the total number of slots required for transmitting the requested data. The transmitter transmits data in fewer slots than the total number of slots indicated in the DRC message. If the receiver is able to decode the information in a number of slots less than the total number of slots, the receiver sends an acknowledgement message to the transmitter and the transmitter terminates the transmission. Otherwise, if the transmitter does not receive an acknowledgement, the transmitter proceeds and, if no acknowledgement is received, may transmit at the identified total number of time slots.

In the case where the received data rate may be different from the requested data rate, the system designer may require the actual received data rate to be used for scheduling purposes. A problem exists in determining the received data rate, which the transmitter does not know in advance, but is determined in the field during the transmission process. In other words, the transmitter knows the requested data rate, such as DRC, and begins transmitting to the receiver with an understanding of all slots that the transmission may need to identify through the DRC. When the receiver sends an acknowledgement message, the transmitter discovers that the receiver is able to receive the transmission in fewer time slots. This typically occurs after the selection of the scheduling algorithm has been determined. In fact, a wireless communication system supporting a physical layer with an ARQ-type scheme separates the rate of DRC requests from the actual reception rate. Scheduling fairness is affected when DRC is used to select a transmission target.

As an example, consider a system with two access terminals, AT1 and AT 2. The AT1 requests data for a total of two slots AT 307.2kbps rate, while the AT2 requests data for a total of one slot AT 614.4kbps rate. AT1 and AT2 are scheduled with equal time using a proportional fair scheduling algorithm, where the throughput of AT1 is half of the throughput of AT2, i.e., the throughput of AT1 is 153.6kpbs, and the throughput of AT2 is 307.2 kpbs. If AT1 sends an acknowledgement message after receiving one slot AT all times, the reception rate of AT1 is 614.4 kpbs. Thus, the throughput of AT1 is 1/3 AT 204.8kpbs or 614.4kpbs, while the throughput of AT2 is 409.6kpbs and 2/3 AT 2. The fairness criteria will be violated. It is desirable for the user to get a throughput proportional to the actual reception rate, rather than a throughput proportional to the requested rate. In the case where an ARQ-type scheme tends to favor the data rate of users with low data rates, a general proportional fair-type algorithm will counter the benefit obtained by reallocating system resources to all users.

One embodiment described above solves this problem by combining a fair proportional type algorithm with GOS type scheduling. For short time intervals, the combining process uses a fair proportional type algorithm and applies the GOS constraints over longer time intervals. In the case where the GOS fairness criteria estimates the total number of bits or bytes sent over a predetermined time period, the actual requested data rate does not go directly into the selection process.

In an unequal GOS algorithm, two levels can be applied: high and low. Each user is assigned a weight as described above. When serving a premium user, i.e., when the premium user is a recipient of data transmission, the weight of the user is increased by a predetermined value, such as by 1. When a low-level user is served, the weight of the user is increased by an adjustment amount, which is a predetermined value adjusted by a gain factor G. A given user varies the level according to the requested data rate and the average throughput. Users above the threshold pass value are assigned high levels and are assigned elevated average pass values. Users below the threshold are assigned to low levels to minimize any impact on throughput. The threshold value per slot can be calculated using DRC to determine the theoretical average throughput that can be achieved using GOS-type schedulers. The calculation may ignore channel variations.

As described above for the proportional fair type of algorithm, the GOS algorithm has a problem in the case where DRC is different from the actual received data rate. One embodiment solves this problem by tracking the actual average throughput per sector using an IIR filter. The filter time constant may be fixed at a value determined by simulation or in operation. According to this embodiment, the throughput for a given sector or cell is defined as:

T[n+1]＝T[n]*(1-α)+α*R[n](25)

where T is the threshold value, R is the service rate at time instance n, and α is a predetermined value. The high and low level users are then allocated using the throughput as a threshold.

To further take advantage of multi-user diversity while applying the GOS-type scheduling algorithm as a modification and as described above, one embodiment applies a predetermined time period. During the time period, the process takes advantage of multi-user diversity and applies a GOS-type scheduling algorithm over the time period. The method tracks the most recent average of the requested data rate for each user by passing the corresponding DRC through an IIR filter. A ratio of the current DRC to the most recent average of the requested data rate is calculated for each user. The user with the highest ratio receives the service. In a further embodiment, the user with the highest ratio receives the service if all weights are within a predetermined range of values. Where the DRC value is part of the numerator and denominator of the ratio, it is desirable that the selection process reflect the actual received data rate rather than the requested rate.

Yet another embodiment attempts to address the divergence between the requested data rate and the received data rate by modifying a proportional fair scheduling algorithm. The proportional fair algorithm is based on the ratio of requested data rate to average throughput per user, with the user having the highest ratio being selected to provide service. The average throughput was calculated as:

T_ave[n+1]＝T_ave[n]*(1-α)+α*R[n] (26)

wherein T is_aveIs the average threshold value, R is the service rate at time instance n, and α is a predetermined value. Modifying the value of the change throughput is defined as:

T_ave[n+1]＝T_ave[n]*(1-α)+α*DRC[n](27)

the application of a DRC in calculating the average threshold results in an average threshold that is potentially lower than the actual reception throughput. By reducing the control of the ratio of requested data rate to average throughput, the ratio is increased, thereby producing the desired effect.

Thus, a novel and improved method and apparatus for scheduling transmissions in a communication system has been described. Those skilled in the art will appreciate that 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, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. 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. In these cases, the skilled artisan will appreciate the interchangeability of hardware and software. By way of example, the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented or performed with 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 such as, for example, registers and FIFO, a processor executing a set of firmware instructions, any conventional programmable software module and a processor, or any combination thereof designed to perform the functions described herein. The processor may advantageously be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, programmable logic device, array of logic elements, 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 exemplary processor is advantageously coupled to the storage medium such that it reads information from, and writes 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 telephone or other user terminal. In the alternative, the processor and the storage medium may reside in a telephone or other user terminal. A processor may be implemented as a combination of a DSP and a microprocessor or as two microprocessors in conjunction with a DSP core or the like.

Thus, the preferred embodiments of the present invention have been shown and described. However, those skilled in the art will recognize that many modifications may be made to the embodiments disclosed herein without departing from the spirit and scope of the present invention. Accordingly, the invention is not to be restricted except in light of the following claims.

Claims (8)

1. A method of scheduling in a wireless communication system, comprising:

receiving channel condition indicators from a plurality of mobile users,

wherein the channel condition indicator corresponds to forward link communications;

determining a channel condition function (A) corresponding to each of the channel condition indicators as:

A_i(t)＝B_i(t)/B_AVE_i(t)i＝1，...N，

wherein A is_i(t) is a function of the channel condition indicator of the ith mobile station, B_i(t) is the channel condition indicator, B _ AVE, from the ith mobile station at time t_i(t) is an average of channel condition indicators most recently received from the ith mobile station, and N is a total number of mobile stations in the plurality of mobile stations;

determining a user fairness metric as a function of throughput for each of a plurality of mobile users;

determining for each of a plurality of mobile users a ratio of a channel condition function (a) for each mobile user to a user fairness metric for each mobile user; and

determining a scheduling scheme based on a ratio of said per-mobile-user channel condition function (a) to a per-mobile-user fairness metric.

2. The method of claim 1, wherein determining a transmission schedule further comprises:

calculating a ratio of a scheduling indicator for a plurality of mobile stations to a channel condition function (a) for each mobile user and a user fairness metric for each mobile user; and

selecting at least one of the plurality of mobile stations for a next transmission based on the scheduling indicator.

3. The method of claim 1, wherein the channel condition indicator is a data rate control request and the average of the channel condition indicators is a filtered data rate control request from an ith mobile station.

4. The method of claim 3, wherein computing the channel condition function for the channel condition indicator comprises:

the filtered data rate control request from the ith mobile station at time t is calculated as:

B_AVE_i(t+1)＝B_AVE_i(t)[1-(1/T_c)]+B_i(t)[1/T_c]

wherein, T_cIs a fair time period.

5. The method of claim 4, wherein computing the channel condition function for the channel condition indicator further comprises:

a weight is assigned to each of the most recently received data rate control requests.

6. The method of claim 1, wherein the user fairness metric is, for each mobile station, a fraction of time the mobile station is served during a fairness time period.

7. An apparatus for controlling a processing machine to perform a function when the apparatus is coupled to the processing machine, the apparatus comprising:

means for processing channel condition indicators received from a plurality of mobile users;

means for determining a channel condition function (A) corresponding to each of the channel condition indicators, the function (A) being:

A_i(t)＝B_i(t)/B_AVE_i(t)i＝1，...N，

wherein A is_i(t) is a function of the channel condition indicator of the ith mobile station, B_i(t) is the channel condition indicator, B _ AVE, from the ith mobile station at time t_i(t) is an average of channel condition indicators most recently received from the ith mobile station, and N is a total number of mobile stations in the plurality of mobile stations;

means for determining a user fairness metric as a function of throughput for each of a plurality of mobile users;

means for determining for each of a plurality of mobile users a ratio of a channel condition function (a) for each mobile user to a user fairness metric for each mobile user; and

means for determining a scheduling scheme based on a ratio of said per-mobile-user channel condition function (A) to a per-mobile-user fairness metric.

8. An access network in a wireless communication system, comprising:

receiving means for receiving channel condition indicators from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications;

means for determining a channel condition function (A) corresponding to each of the channel condition indicators, the function (A) being:

A_i(t)＝B_i(t)/B_AVE_i(t)i＝1，...N，

wherein A is_i(t) is a function of the channel condition indicator of the ith mobile station, B_i(t) is the channel condition indicator, B _ AVE, from the ith mobile station at time t_i(t) is an average of channel condition indicators most recently received from the ith mobile station, and N is a total number of mobile stations in the plurality of mobile stations;

means for determining a user fairness metric as a function of throughput for each of a plurality of mobile users;

means for determining for each of a plurality of mobile users a ratio of a channel condition function (a) for each mobile user to a user fairness metric for each mobile user; and

means for determining a scheduling scheme based on a ratio of said per-mobile-user channel condition function (A) to a per-mobile-user fairness metric.