Method and apparatus for scheduling transmissions in a communication system Number:6,807,426 from the United States Patent and Trademark Office (PTO) owispatent Method and apparatus for a generalized scheduler for scheduling transmissions in a communications system. The scheduler is defined by a priority function of the channel condition and fairness criteria. The generalized scheduler is adapted to apply a variety of combinations of channel condition metrics and user fairness metrics. The scheduler distinguishes among classes of users, allowing individual processing per class. In one embodiment, a system controller receives a Delivery Priority Parameter (DPP) for each of a plurality of users, and maps each DPP to a corresponding common Mapped Priority Parameter (MPP). An operating point is determined and a corresponding MPP value for each of the users is applied to schedule transmissions.<H communication, transmissions, Method, and, appa, 6807426.html, Patent, pto, 6807426

Title: Method and apparatus for scheduling transmissions in a communication system

Abstract: Method and apparatus for a generalized scheduler for scheduling transmissions in a communications system. The scheduler is defined by a priority function of the channel condition and fairness criteria. The generalized scheduler is adapted to apply a variety of combinations of channel condition metrics and user fairness metrics. The scheduler distinguishes among classes of users, allowing individual processing per class. In one embodiment, a system controller receives a Delivery Priority Parameter (DPP) for each of a plurality of users, and maps each DPP to a corresponding common Mapped Priority Parameter (MPP). An operating point is determined and a corresponding MPP value for each of the users is applied to schedule transmissions.

Patent Number: 6,807,426 Issued on 10/19/2004 to Pankaj

Inventors: Pankaj; Rajesh K. (San Diego, CA)
Assignee: QUALCOMM Incorporated (San Diego, CA)

Appl. No.: 09/974,933

Filed: October 10, 2001

Current U.S. Class: 455/453 ; 370/328; 370/329; 370/330; 370/335; 370/338; 370/341; 370/342; 370/356; 370/429; 370/431; 370/441; 370/442; 370/468; 455/436; 455/446; 455/447; 455/450; 455/451; 455/452.1

Field of Search: 370/468,230.1,328,329,330,335,341,342,337,397,398,412,428,429,431,441,442,464,465,338,349,351-356 455/450,451,453,436,446,452

References Cited [Referenced By]

U.S. Patent Documents


4901307	February 1990	Gilhousen et al.
5101501	March 1992	Gilhousen et al.
5103459	April 1992	Gilhousen et al.
5706288	January 1998	Radhakrishnan et al.
5859835	January 1999	Varma et al.
5886993	March 1999	Ruszczyk et al.
5889779	March 1999	Lincoln
5923650	July 1999	Chen et al.
6038217	March 2000	Lyles
6064678	May 2000	Sindhushayana et al.
6072784	June 2000	Agrawal et al.
6101193	August 2000	Ohba
6115360	September 2000	Quay et al.
6157614	December 2000	Pasternak et al.
6377583	April 2002	Lyles et al.
6408005	June 2002	Fan et al.
6459687	October 2002	Bourlas et al.
6515963	February 2003	Bechtolsheim et al.

Foreign Patent Documents


98/35514	Aug., 1998	WO
99/23844	May., 1999	WO
01/54335	Jul., 2001	WO

Other References

TS. Eugene Ng et al. "Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors," INFOCOM 98. 17.sup.th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, IEEE San Francisco, CA, Mar. 29 to Apr. 2, 1998; New York, NY, Mar. 29, 1998, pp. 1103-1111. .
A. Stamoulis et al. "Packet Fair Queueing Scheduling Based on Multirate Multipath-Transparent CDMA for Wireless Networks," INFOCOM 2000. 19.sup.th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceeding IEEE Tel Aviv, Israel, Mar. 26-30, 2000; Piscataway, NJ, USA, Mar. 26, 2000, pp. 1067-1076). .
Matthew Andrews, et al. "Providing Quality of Service over a Shared Wireless Link" IEEE Communications Magazine, Feb. 2001. .
Matthew Andrews, et al. "Providing Quality of Service over a Shared Wireless Link" IEEE Communications Magazine, Feb. 2001..

Primary Examiner: Milord; Marceau
Attorney, Agent or Firm: Wadsworth; Phil R. Godsey; Sandra L.

Parent Case Text

CLAIM OF PRIORITY UNDER 35 U.S.C. .sctn.120

The present Application for Patent claims priority of U.S. Provisional Application No. 60/283,885, filed Apr. 12, 2001, assigned to the assignee hereof and hereby expressly incorporated by reference herein.

REFERENCE TO RELATED CO-PENDING APPLICATIONS

The present Application for Patent is related to U.S. application Ser. No. 09/796,583, filed Feb. 27, 2001, entitled "SYSTEM FOR ALLOCATING RESOURCES N A COMMUNICATION SYSTEM," which is a continuation for U.S. Pat. No. 6,229,795 B1, entitled "SYSTEM FOR ALLOCATING RESOURCES IN A COMMUNICATION SYSTEM," issued Apr. 8, 2001, by Pankaj et al., assigned to the assignee hereof and hereby expressly incorporated by reference herein.

Claims

What is claimed is:

1. In a wireless communication system a scheduling method, comprising: receiving channel condition indicators from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications; determining a function (A) corresponding to each of the channel condition indicators, given as:

2. The method as in claim 1, determining a transmission schedule further comprises: calculating scheduling indicators for the plurality of mobile stations as a function of the channel condition indicator and the fairness indicator; and selecting at least one of the plurality of mobile stations for a next transmission based on the scheduling indicators.

3. The method as in claim 2, wherein calculating scheduling indicators comprises: for each of the plurality of mobile stations, determining a ratio of a corresponding channel condition indicator to a corresponding fairness indicator.

4. The method as in claim 1, wherein the transmission schedule is a function of:

5. The method as in claim 4, wherein the channel condition indicator is a data rate control request, and the average value of channel condition indicators is a filtered data rate control request from the ith mobile station.

6. The method as in claim 5, wherein calculating a function of the channel condition indicator comprises: calculating the filtered data rate control request from the ith mobile station at time t as:

wherein T.sub.c is a fairness time period.

7. The method as in claim 6, wherein calculating a function of the channel condition indicator further comprises: assigning a weight to each of the recently received data rate control requests.

8. The method as in claim 1, wherein for each mobile station the fairness indicator is a fraction of time the mobile station was served during a fairness time period.

9. A program embodied on a computer-readable medium containing computer-executable instructions, comprising: 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 the plurality of mobile users; a third set of instructions for calculating a function (A) corresponding to each of the channel condition indicators, given as:

10. The program as in claim 9, wherein determining a transmission schedule for the plurality of users as a function of the channel condition indicators and the fairness indicators is done by balancing the channel condition indicators with the fairness indicators.

11. In a wireless communication system, an access network, 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 function (A) corresponding to each of the channel condition indicators, given as:

12. A method for scheduling data transmissions in a wireless communication system, comprising: receiving a value for a delivery priority parameter from each of a plurality of mobile users; for each of the plurality of mobile users, applying a mapped priority parameter value corresponding to an operating point; determining a delivery priority parameter value corresponding to the mapped priority parameter value; if any of the delivery priority parameters are different types, mapping each delivery priority parameter to a mapped priority parameter; and determining the operating point based on the mapped priority parameters of the plurality of mobile users.

13. The method as in claim 12 wherein a first delivery priority parameter is a desired time allotment.

14. The method as in claim 12 wherein a second delivery priority parameter is a desired throughput.

15. The method as in claim 12 wherein a third delivery priority parameter is a desired delay.

16. A system controller in a wireless communication system, comprising: means for receiving a delivery priority parameter from each of a plurality of mobile users; means for applying a mapped priority parameter value corresponding to an operating point for each of the plurality of mobile users; means for determining a delivery priority parameter value corresponding to the mapped priority parameter value; means for mapping each delivery priority parameter to a mapped priority parameter if any of the delivery priority parameters are different types; and means for determining the operating point based on the mapped priority parameters of the plurality of mobile users.

17. An apparatus in a wireless communication system, comprising: a processing element; and a memory storage element coupled to the processing element, the memory storage element adapted for storing computer-readable instructions for implementing: receiving a delivery priority parameter from each of a plurality of mobile users; applying a mapped priority parameter value corresponding to an operating point for each of the plurality of mobile users; determining a delivery priority parameter value corresponding to the mapped priority parameter value; mapping each delivery priority parameter to a mapped priority parameter if any of the delivery priority parameters are different types; and determining the operating point based on the mapped priority parameters of each the plurality of mobile users.

18. The apparatus as in claim 17, wherein the computer-readable instructions further implement: applying the operating point to each of the plurality of mobile users, wherein the operating point determines mapped priority parameter values corresponding to each of the plurality of mobile users.

19. The apparatus as in claim 18, wherein the computer-readable instructions further implement: scheduling the plurality of mobile users according to the operating point using the mapped priority parameter values.

Description

BACKGROUND

1. Field

The present invention pertains generally to communications, and more specifically to a method and apparatus for scheduling transmissions in a communication system.

2. Background

Communication systems, and wireless systems in particular, are designed with the objective of efficient allocation of resources among a variety of users. Wireless systems in particular aim to provide sufficient resources to satisfy the requirements of all subscribers while minimizing costs. Various scheduling algorithms have been developed, each based on a predetermined system criteria.

In a wireless communication system employing a Code Division-Multiple Access, CDMA, scheme, one scheduling method assigns each of the subscriber units all code channels at designated time intervals on a time multiplexed basis. A central communication node, such as a Base Station, BS, implements the unique carrier frequency or channel code associated with the subscriber to enable exclusive 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) the "TIA/EIA/IS-95-B Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System" referred to herein as the IS-95 standard; (2) the standard offered by a consortium named "3rd Generation Partnership Project" referred to herein as 3GPP; and embodied in a set of documents including Document Nos. 3G TS 25.211, 3G TS 25.212, 3G TS 25.213, and 3G TS 25.214, 3G TS 25.302, referred to herein as the W-CDMA standard; (3) the standard offered by a consortium named "3rd Generation Partnership Project 2" referred to herein as 3GPP2, and TR-45.5 referred to herein as the cdma2000 standard, formerly called IS-2000 MC, or (4) some other wireless standard.

In a communication system, and a wireless system in particular, users are typically assigned to classes, wherein each class has an associated system performance criteria. For example, each class may be treated differently with respect to a fairness criteria, wherein each user in a class is treated similarly. Classes may be treated according to the priority of each class. In one system, users are classified according to services used in the system, such as according to a service plan. Several classes may be present within one communication system.

Accordingly, there is a need for a method and apparatus for scheduling transmissions in a communication system with application to multiple classes of users. Additionally, there is a need for a scheduling method and apparatus that accommodates a variety of different scheduling priorities.

SUMMARY

Embodiments disclosed herein address the above stated needs by providing a means for scheduling data transmissions in a wireless communication system. A generalized scheduler allows scheduling of multiple mobile stations, wherein each mobile station may have a different delivery priority parameter. The delivery priority parameter defines the parameter used to affect the desired data transmission delivery rate. For example, a delivery priority parameter may be desired throughput, desired time allotment, desired time delay, etc. The delivery priority parameter values are each mapped to a common scale, referred to as a mapped priority parameter. An operating point is then selected and the corresponding mapped priority parameter values for each mobile user extracted. The generalized scheduler then schedules mobile users using a common mapped priority parameter value. In other words, each user is scheduled to achieve a same proportion within the corresponding delivery priority parameter range.

According to one aspect, in a wireless communication system a scheduling method includes 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 the 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 indicators and fairness indicators.

In another aspect, a program embodied on a computer-readable medium containing computer-executable instructions, includes 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 the plurality of mobile users, and a third set of instructions for determining a transmission schedule for the plurality of users as a function of the channel condition indicators and the fairness indicators.

In still another aspect, a method for transmitting data between one remote station of a plurality of remote stations and a base station in a wireless communication system includes receiving at the base station information transmitted by the one remote station, and adjusting at least one grade of service parameter particular to the one remote station based on the information.

In yet another aspect, a method for scheduling data transmissions in a wireless communication system includes receiving a value for a delivery priority parameter from each of a plurality of mobile users, if any of the delivery priority parameters are different types, mapping each delivery priority parameter to a mapped priority parameter, 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 includes a processing element, and a memory storage element coupled to the processing element, the memory storage element adapted for storing computer-readable instructions for implementing: receiving a delivery priority parameter from each of a plurality of mobile user, mapping each delivery priority parameter to a mapped priority parameter, and determining an operating point based on the mapped priority parameters of each the plurality of mobile users.

BRIEF DESCRIPTION OF THE DRAWINGS

The features, objects, and advantages of the presently disclosed method and apparatus 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 transmissions;

FIG. 2 is a flow diagram of a Grade Of Service, GOS, and algorithm for scheduling data transmissions in a wireless communication system.

FIG. 3 is a flow diagram of a scheduling algorithm for data transmissions 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 flow diagram of a combination scheduling algorithm, implementing a proportional-fair algorithm and a GOS algorithm in a wireless communication system;

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

FIG. 7 is a wireless communication system supporting a combination scheduling algorithm such as illustrated in FIGS. 5 and 6; and

FIG. 8 is a flow diagram of a scheduling algorithm for a wireless communication system.

FIG. 9A illustrates a mapping of various delivery priority parameter ranges to a common mapped priority parameter range.

FIGS. 9B, 9C, and 9D illustrate determination of various operating points over multiple mapped priority parameters.

FIG. 10 illustrates a flow diagram of a generalized scheduler.

DETAILED DESCRIPTION OF THE INVENTION

A modern day communication system is required to support a variety of applications. One such communication system is a code division multiple access (CDMA) system which conforms to the "TIA/EIA-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System" and its progeny, hereinafter referred to as IS-95. The CDMA system allows for voice and data communications between users over a terrestrial link. The use of CDMA techniques in a multiple access communication system 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 assigned to the assignee of the present invention and incorporated by reference herein.

In a CDMA system, communications between users are conducted through one or more base stations. In wireless communication systems, forward link refers to the channel through which signals travel from a base station to a subscriber station, and reverse link refers to channel through which signals travel from a subscriber station to a base station. By transmitting data on a reverse link to a base station, a first user on one subscriber station communicates with a second user on a second subscriber station. The base station receives the data from the first subscriber station and routes the data to a base station serving the second subscriber station. Depending on the location of the subscriber stations, both may be served by a single base station or multiple base stations. In any case, the base station serving the second subscriber station sends the data on the forward link. Instead of communicating with a second subscriber station, a subscriber station may also communicate with a terrestrial Internet through a connection with a serving base station. In wireless communications such as those conforming to IS-95, forward link and reverse link signals are transmitted within disjoint frequency bands.

FIG. 1A serves as an example of a communications system 100 that supports a number of users and is capable of implementing at least some aspects and embodiments of the invention. Any of a variety of algorithms and methods may be used to schedule transmissions in system 100. System 100 provides communication for a number of cells 102A through 102G, each of which is serviced by a corresponding base station 104A through 104G, respectively. In the exemplary embodiment, some of base stations 104 have multiple receive antennas and others have only one receive antenna. Similarly, some of base stations 104 have multiple transmit antennas, and others have single transmit antennas. There are no restrictions on the combinations of transmit antennas and receive antennas. Therefore, it is possible for a 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. 1A, various terminals 106 are dispersed throughout the system. Each terminal 106 communicates with at least one and possibly more base stations 104 on the downlink and uplink at any given moment depending on, for example, whether soft handoff is employed or whether the terminal is designed and operated to (concurrently or sequentially) receive multiple transmissions from multiple base stations. Soft handoff in CDMA communications 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 of terminals 106 have multiple receive antennas and others have only one receive antenna. In FIG. 1A, base station 104A transmits data to terminals 106A and 106J on the downlink, base station 104B transmits data to terminals 106B and 106J, base station 104C transmits data to terminal 106C, and so on.

Increasing demand for wireless data transmission and the expansion of services available via wireless communication technology have 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-IS856 cdma2000 High Rate Packet Data Air Interface Specification" referred to as "the HDR specification." HDR service is generally an overlay to a voice communication system that provides an efficient method of transmitting packets of data in a wireless communication system. As the amount of data transmitted and the number of transmissions increases, the limited bandwidth available for radio transmissions becomes a critical resource. There is a need, therefore, for an efficient and fair method of scheduling transmissions in a communication system that optimizes use of available bandwidth. In the exemplary embodiment, system 100 illustrated in FIG. 1A is consistent with a CDMA type system having HDR service.

FIG. 1B illustrates an architecture reference model for a communication system 120 having an Access Network, AN, 122 communicating with an Access Terminal, AT, 126 via an air interface 124. In one embodiment, the system 10 is a Code Division-Multiple Access, CDMA, system having a High Data Rate, HDR, overlay system, such as specified the HDR standard. The AN 122 communicates with AT 126, as well as any other ATs within system 120 (not shown), by way of the air interface 124. The AN 122 includes multiple sectors, wherein each sector provides at least one Channel. A Channel is defined as the set of communication links for transmissions between the AN 122 and the ATs within a given frequency assignment. A Channel consists of a Forward Link (FL) for transmissions from the AN 122 to AT 126 and a Reverse Link (RL) for transmissions from the AT 126 to the AN 122.

For data transmissions, the AN 122 receives a data request from the AT 126. The data request specifies the data rate at which the data is to be sent, the length of the data packet transmitted, and the sector from which the data is to be sent. The AT 126 determines the data rate based on the quality of the Channel between AN 122 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 the quality of the Channel. The AT 126 provides requests for data transmissions by sending a Data Rate Control, DRC, message via a specific channel referred to as the DRC channel. The DRC message includes a data rate portion and a sector portion. The data rate portion indicates the requested data rate for the AN 122 to send the data, and the sector indicates the sector from which the AN 122 is to send the data. Both data rate and sector information are typically required to process a data transmission. The data rate portion is referred to as a DRC value, and the sector portion is referred to as a DRC cover. The DRC value is a message sent to the AN 122 via the air interface 124. In one embodiment, each DRC value corresponds to a data rate in kbits/sec having an associated packet length according to a predetermined DRC value assignment. The assignment includes a DRC value specifying a null data rate. In practice, the null data rate indicates to the AN 122 that the AT 126 is not able to receive data. In one situation, for example, the quality of the Channel is insufficient for the AT 126 to receive data accurately.

In operation, the AT 126 continuously monitors the quality of the Channel to calculate a data rate at which the AT 126 is able to receive a next data packet transmission. The AT 126 then generates a corresponding DRC value; the DRC value is transmitted to the AN 122 to request a data transmission. Note that typically data transmissions are partitioned into packets. The time required to transmit a packet of data is a function of the data rate applied.

This DRC signal also provides the information, which the channel scheduler uses to determine the instantaneous rate for consuming information (or receiving transmitted data) for each of the remote stations associated with each queue. According to an embodiment, a DRC signal transmitted from any remote station indicates that the remote station is capable of receiving data at any one of multiple effective data rates. Such a variable rate transmission system is described in detail in U.S. Pat. No. 6,064,678, entitled "Method for Assigning Optimal Packet Lengths in a Variable Rate Communication System," issued May 16, 2000, assigned to the assignee of the present invention and incorporated by reference herein.

One example of a communication system supporting HDR transmissions and adapted for scheduling transmissions to multiple users is illustrated in FIG. 7. FIG. 7 is detailed hereinbelow, wherein specifically, a base station 820 and base station controller 810 interface with a packet network interface 806. Base station controller 810 includes a channel scheduler 812 for implementing a scheduling algorithm for transmissions in system 800. The channel scheduler 812 determines the length of a service interval during which data is to be transmitted to any particular remote station based upon the remote station's associated instantaneous rate for receiving data (as indicated in the most recently received DRC signal). The service interval may not be contiguous in time but may occur once every n slots. According to one embodiment, the first portion of a packet is transmitted during a first slot at a first time and the second portion is transmitted 4 slots later at a subsequent time. Also, any subsequent portions of the packet are transmitted in multiple slots having a similar 4 slots spread, i.e., 4 slots apart from each other. According to an embodiment, the instantaneous rate of receiving data R.sub.i determines the service interval length L.sub.i associated with a particular data queue.

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

Note that it may be possible for the user to receive a packet correctly even if only a portion of the packet is transmitted. This occurs when the channel condition is better than anticipated by the user. In that case, the user may send an "ACK" signal to the base station indicating that the packet is already correctly received and the remaining portions of the packet need not be transmitted. When this happens, the entire data packet is effectively transmitted to the user over a shorter service interval thereby increasing the effective data rate at which the packet is transmitted. The base station then reassigns the time slots that were originally scheduled to transmit the remaining portions of that packet to transmit another packet either to the same user or to a different user. This process is generally referred to as Automatic Repeat reQuest (ARQ).

In a system supporting ARQ, a data packet is scheduled for a predetermined number of transmissions, wherein each transmission may include different information. The multiple transmissions are interposed with other packets sequentially. When a receiver has received sufficient information to decode and process the packet, the receiver sends an indication to the transmitter that no further information is required for the current packet. The transmitter is then free to schedule the slots originally scheduled for the current packet to another packet. In this way, the system resources are conserved and the 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. Base station controller 810 interfaces with packet network interface 806, Public Switched Telephone Network, PSTN, 808, and all base stations in the communication system (only one base station 820 is shown in FIG. 7 for simplicity). Base station controller 810 coordinates the communication between remote stations in the communication system and other users connected to packet network interface 806 and PSTN 808. PSTN 808 interfaces with users through a standard telephone network (not shown in FIG. 7).

Base station controller 810 contains many selector elements 816, although only one is shown in FIG. 7 for simplicity. Each selector element 816 is assigned to control communication between one or more base stations 820 and one remote station (not shown). If selector element 816 has not been assigned to a given remote station, call control processor 818 is informed of the need to page the remote station. Call control processor 818 then directs base station 820 to page the remote station.

Data source 802 contains a quantity of data, which is to be transmitted to a given remote station. Data source 802 provides the data to packet network interface 806. Packet network interface 806 receives the data and routes the data to the 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, which stores the data to be transmitted to the remote station.

The data is transmitted in data packets from data queue 830 to channel element 826. In the exemplary embodiment, on the forward link, a "data packet" refers to a quantity of data which is a maximum of 1024 bits and a quantity of data to be transmitted to a destination remote station within a predetermined "time slot" (such as .apprxeq.1.667 msec). For each data packet, channel element 826 inserts the necessary control fields. In the exemplary embodiment, channel element 826 performs a Cyclic Redundancy Check, CRC, encoding of the data packet and control fields and inserts a set of code tail bits. The data packet, control fields, CRC parity bits, and code tail bits comprise a formatted packet. In the exemplary embodiment, channel element 826 then encodes the formatted packet and interleaves (or reorders) the symbols within the encoded packet. In the exemplary embodiment, the interleaved packet is covered with a Walsh code, and spread with the short PNI and PNQ codes. The spread data is provided to RF unit 828 which quadrature modulates, filters, and amplifies the signal. The forward link signal is 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, amplifies, quadrature demodulates, and quantizes the signal. The digitized signal is provided to a demodulator (DEMOD) where it is despread with the short PNI and PNQ codes and decovered with the Walsh cover. The demodulated data is provided to a decoder which performs the inverse of the signal processing functions done at base station 820, specifically the de-interleaving, decoding, and CRC check functions. The decoded data is provided to a data sink.

The hardware, as pointed out above, supports variable rate transmissions of data, messaging, voice, video, and other communications over the forward link. The rate of data transmitted from the data queue 830 varies to accommodate changes in signal strength and the noise environment at the remote station. Each of the remote stations preferably transmits a Data Rate Control, DRC, signal to an associated base station 820 at each time slot. The DRC signal provides information to the base station 820, which includes the identity of the remote station and the rate at which the remote station is to receive data from its associated data queue. Accordingly, 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 travels through a 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 channel element 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 a first exemplary embodiment, the channel scheduler 832 is located in the base station 820. In an alternate embodiment, the channel scheduler 812 is located in the base station controller 810, and connects to all selector elements 816 within the base station controller 810.

In the first-mentioned exemplary embodiment, channel scheduler 832 receives information from data queue 830 indicating the amount of data queued up for each remote station, also called queue size. Channel scheduler 832 then performs scheduling based on DRC information and queue size for each remote station serviced by base station 820. If queue size is required for a scheduling algorithm used in the alternate embodiment, channel scheduler 812 may receive queue size information from selector element 816.

During the transmission of a packet to one or more users, the users transmit an "ACK" signal after each time slot containing a portion of the transmitted packet. The ACK signal transmitted by each user travels through a reverse link channel and is received at base station 820 through a receive antenna coupled to RF unit 828. In the exemplary embodiment, the ACK information is demodulated in channel element 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 a first exemplary embodiment, the channel scheduler 832 is located in the base station 820. In an alternate embodiment, the channel scheduler 812 is located in the base station controller 810, and connects to all selector elements 816 within the base station controller 810.

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

Also, a base station 820 of the embodiment discussed above transmits to a selected one, or selected ones, of the remote stations to the exclusion of the remaining remote stations associated with the base station 820 using a Code Division-Multiple Access, CDMA, scheme. At any particular time, the base station 820 transmits to the selected one, or selected ones, of the remote station by using a code, which is assigned, to the receiving base station(s) 820. However, the present invention is also applicable to other systems employing different Time Division-Multiple Access, TDMA, methods for providing data to select base station(s) 820, to the exclusion of the other base stations 820, for allocating transmission resources optimally.

The channel scheduler 812 schedules the variable rate transmissions on the forward link. The channel scheduler 812 receives the queue size, which is indicative of the amount of data to transmit to a remote station, and messages from remote stations. The channel scheduler 812 preferably schedules data transmissions to achieve the system goal of maximum data throughput while conforming to a fairness constraint.

As shown in FIG. 1, remote stations are dispersed throughout the communication system and can be in communication with zero or one base station on the forward link. In the exemplary embodiment, channel scheduler 812 coordinates the forward link data transmissions over the entire communication system. A scheduling method and apparatus for high speed data transmission are described in detail in U.S. patent application Ser. No. 08/798,951, entitled "Method and Apparatus for Forward Link Rate Scheduling," filed Feb. 11, 1997, now U.S. Pat. No. 6,335,922, issued Jan. 1, 2002, to Tiedemann Jr. et al., assigned to the assignee of the present invention and hereby expressly incorporated by reference.

According to an embodiment, the channel scheduler 812 is implemented in a computer system, which includes a processor, Random Access Memory, RAM, and a 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 the exemplary embodiment a generalized scheduler is applied to the system 800 illustrated in FIG. 7 and is detailed hereinbelow. Those modules within the BSC 810 and BS 820 used to implement a priority function for scheduling data transmissions is discussed after establishing the specifics of the generalized scheduler.

Given the growing demand for wireless data applications, the demand for very efficient wireless data communication systems has increased significantly. The IS-95 standard is capable of transmitting traffic data and voice data over the forward and reverse links. In accordance with the IS-95 standard, the traffic data or voice data is partitioned into code channel frames that are 20 milliseconds wide with data rates as high as 14.4 Kbps. In an IS-95 system, each subscriber station is allocated at least one of a limited number of orthogonal forward link channels. While the communication between a base station and a subscriber station is ongoing, the forward link channel remains allocated to the subscriber station. When data services are provided in an IS-95 system, a forward link channel remains allocated to a subscriber station even during times when there is no forward link data to be sent to the subscriber station.

A significant difference between voice services and data services is the fact that the former imposes stringent and fixed delay requirements. Typically, the overall one-way delay of speech frames are specified to be less than 100 milliseconds. In contrast, the data delay can become a variable parameter used to optimize the efficiency of the 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. Typically, for digital systems providing voice services, this translates into a fixed and equal transmission rate for all users and a maximum tolerable value for the error rates of the speech frames. In contrast, for data services, the GOS can be different from user to user and can be a parameter optimized to increase the overall efficiency of the data communication system. The GOS of a data communication system is typically defined as the total delay incurred in the transfer of a predetermined amount of data, hereinafter referred to as a data packet.

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, this additional reliability is not required for data transmission because the data packets received in error can be retransmitted. For data services, the transmit power used to support soft handoff can be more efficiently used for transmitting additional data.

Transmission delay required to transfer a data packet and the average throughput rate are two attributes used to define the quality and effectiveness of a data communication system. Transmission delay does not have the same impact in data communication as it does for voice communication, but it is an important metric for measuring the quality of the 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 simultaneously providing a GOS that is appropriate for the types of service being provided over a wireless channel

The need for a generalized scheduler is based on the requirements and targets of data transmission in a wireless system. For data transmissions, throughput is defined in terms of the delays incurred in the transmission of packets of data rather than in terms of individual bits or bytes. A data packet, such as an Internet Protocol, IP, datagram, is an indivisible unit as, in most cases, receipt of only a portion of a packet does not contain sufficient information for the user to decode and use the entire packet, i.e., the packet is useless to the end user. The end user receives the packet of data, performs a Cyclic Redundancy Check, CRC, on the packet of data, and processes the data. Therefore, the user is most concerned with the arrival time of the last bit of a packet and is not as concerned with the delay of individual bits in the data packet. This allows considerable flexibility in rate allocations to different users over time scales smaller than the transmission time of a data packet. Furthermore, in a Transmission Control Protocol, TCP, type connection, some variation of packets delays is acceptable as long as the variation is not so unpredictable that it causes TCP retransmissions needlessly.

Another feature of the wireless channel is the variability of the channel itself. In an HDR type system, this variability results in variations of the requested rate over a period of time. To maximize use of the channel, the scheduler is designed to serve high rate users, i.e., users requesting the highest data rates. This means that occasionally, the users may not be served for periods of time when their requested rates are lower. The overall throughput will be maximized when the scheduler does not serve low rate users for long periods of time. However, ideally the scheduler balances this against the desire for packet delays and delay variations to be relatively consistent as explained hereinabove.

Another aspect considers the fairness to the multiple users in a system. To accomplish a fair scheduling method, the scheduler ideally distributes the overall throughput among different users. Different bases of fairness (or allowable unfairness) are used by different systems to affect the needs and desires of the individual systems. The concept of fairness is a key concept in many scheduling algorithms. Fairness provides different amounts of flexibility in serving different users and hence has an impact on the overall throughput of a sector.

According to one embodiment, a method and apparatus for scheduling transmissions in a communication system with application to multiple classes of users incorporates a generalized scheduler. The generalized scheduler accommodates a variety of different scheduling priorities. Different classes of users each having specific transmission requirements are serviced by a generalized scheduler, which maintains a high throughput over all users.

In an exemplary embodiment, operation of a generalized scheduler implements a priority function of a channel condition metric and a fairness criteria, wherein the priority function is defined as:

wherein A.sub.i (t) is referred to as the channel condition metric and U.sub.i (t) is referred to as the user fairness metric. The function A.sub.i (t) specifies the desirability of serving user i at time t based on a current channel condition. The function U.sub.i (t) specifies the desirability of serving user i at time t based on the past history of received service. The priority function f( ) combines the two desirability metrics, A.sub.i (t) and U.sub.i (t), to determine a priority level for each user.

Referring to FIG. 9A, in an exemplary embodiment, multiple users each have a desired criteria for receiving transmissions from a same base station. The scale used for measuring the criteria is referred to herein as the Delivery Priority Parameter (DPP), wherein the DPP reflects the desired priority of each user. For example, a first user may desire to receive transmissions for a specified time allotment, while a second user may desire to receive transmissions of a specified throughput. Still a third user may desire to receive transmissions having a specified delay. The DPP of the first user reflects a time scale; the DPP of the second user reflects a bits per second (bps) scale, while the DPP of the third user reflects a time delay scale. The DPP of each user identifies the specific value of the desired criteria for receiving transmissions.

The DPPs of the multiple users are mapped to a common scale. The common scale is a unitless, proportional representation of the range of values within a DPP. As illustrated in FIG. 9A, each of the DPP may have a different range of values, wherein each of the different DPP ranges is mapped to a common scale. The mapping of the actual value of a specific user within a DPP range is referred to herein as the Mapped Priority Parameter (MPP).

FIG. 9B illustrates a first DPP to MPP mapping scenario, wherein three different DPP types are labeled A, B and C. The horizontal axis represents the DPP ranges for each of the three types. The vertical axis represents MPP ranges of values. For clarity of understanding, in FIG. 9B the DPP type A represents a throughput parameter measured in bits per second; the DPP type B represents a time proportion parameter measured as a unitless ratio of time allocated to one user as a proportion of the total time allocated to all users; and the DPP type C represents a time delay proportion measured as a unitless ratio. Alternate embodiments may implement any type of DPP specific to a given system, additionally; alternate embodiments may include actual time units rather than the proportional values described in the examples herein. The ranges of values for a given DPP are provided over a predetermined range. For example, the range of values for DPP type A is from 0 bps to a maximum value supported by the system. Similarly, the range of values for the DPP type B is from 0 wherein the user receives no transmissions to a predetermined maximum wherein the user receives all of the transmission time. The range of values for the DPP type C is from no delay to a maximum delay.

The type A is an increasing function, wherein MPP=1 corresponds to a maximum value and MPP=0 corresponds to a minimum value. The type B is also an increasing function, wherein MPP=1 corresponds to a maximum value and MPP=0 corresponds to a minimum value. Note that the type C is a decreasing function, wherein MPP=1 corresponds to no delay and MPP=0 corresponds to a maximum delay. The MPP range reflects the minimum to maximum values of the DPPs. In other words, the MPP range unitizes the DPP ranges. Alternate mappings may be incorporated to provide a common basis of evaluation for the various DPPs. Continuing with 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 DPP ranges. The operating point defines the exact value of each DPP within the range provided. 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 be the operating points for the individual users having these DPPs. The values d1, d2, d3 are specific values within each of the ranges which are interpreted in light of the units of the corresponding DPP. The value d1 is interpreted in bps; the value d2 is interpreted as a proportion of time; and the value d3 is interpreted as a proportion of delay.

FIG. 9C illustrates the same DPP to MPP mapping wherein a different operating point is selected. The type B and type C DPPs result in a common value d4 and the type A results in a distinct value d5. FIG. 9D illustrates an alternate DPP to MPP mapping. Here the resultant function is a decreasing function; however, the function is not linear. The operating point defines a DPP value d6.

FIG. 10 illustrates a flow diagram of a generalized scheduler method 1200 according to one embodiment. At step 1202 the generalized scheduler receives DPP type information from each of N users. The DPP type information provides the generalized scheduler with information for determining an operating point among the N users. At decision diamond 1204 the generalized scheduler determines if the all of the DPP values are equal for all pairs of users, i.e. the absolute value without considering units. If all the DPP pairs have equal values, processing continues to step 1212 to apply the generalized scheduler defined by Equ. (1) hereinabove. 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 illustrated in FIGS. 9A-9D. At step 1208 the generalized scheduler determines an operating point supported by the available resources for each of the users. At step 1210 the process applies the operating point to each of the users determining the exact DPP value for continued operation. Processing then continues to step 1212 to apply the generalized scheduling algorithm defined by Equ. (1) hereinabove. In this way, the generalized scheduler applies a common MPP operating point to each user without regard to the individual DPPs. Once the MPP operating point is selected, the generalized scheduler extrapolates back to the exact DPP value within each DPP range. The users may therefore each request a different priority parameter, wherein the generalized scheduler applies a common scale to scheduling.

According to the exemplary embodiment, a generalized scheduler serves the user with the highest priority function .function.(A.sub.i (t),U.sub.i (t)) within a given class or type of users. In the exemplary embodiment, the value taken by the priority function .function.(A.sub.i (t),U.sub.i (t)) increases as the channel condition function A.sub.i (t) increases and decreases as the fairness function U.sub.i (t) increases. The functions A.sub.i (t) and U.sub.i (t) are determined accordingly. Further, the priority function f( ) is a function of at least one time period over which the channel condition metric and the user fairness metric are measured. In an alternate embodiment, the priority function f( ) may be a time-dependent per user function. However, for simplicity, it is best to stick with a combiner function that is common to all users and modify the user fairness metric to reflect the user requirements. Also, for clarity of discussion, consider the priority function as a division operation.

The channel condition metric takes advantage of variations in the channel condition. As discussed hereinbelow, this metric may be defined as DRC, DRC/DRCave, DRC-DRCave, or a constant value. To maximize the gains from multi-user diversity, the selected channel quality metric should have higher values when the channel condition is better relative to the average condition for that user. For clarity of discussion, the exemplary embodiment considers DRC/DRCave as the channel condition metric. Of particular importance is the definition of DRCave. The averaging should be done over a channel condition time constant, Tc. In this way, the channel condition metric is expected to change with the DRC over a time scale smaller than Tc. Changes in the DRC value that take place over time scales larger than Tc are considered long term, and affect both the numerator and the denominator of the channel condition metric equally and thus cancel each other out. The value of Tc is selected by looking at the channel dynamics. If the channel dynamics are such that the DRC values change significantly over time scales of length, say, T1, then the time constant Tc should be greater than T1. Note that the channel condition metric should use the largest time constant that is allowed by the user requirements.

According to the exemplary embodiment, the fairness metric is effectively kept constant per class of users. Given the selected channel condition metric, and the tendency for the channel condition metric to oscillate around 1, the scheduler will tend to serve a user that has a low user fairness metric value and will tend not to serve the user that has a high user fairness metric value. In this way, the generalized scheduler is similar to an algorithm that maintains the user fairness metric constant while taking advantage of the multi-user diversity. To determine a user fairness metric such that each user's most desired state leads to the same numerical value of the user-fairness metric, allows the system to serve users with many different types of requirements. Also the slope around the desirable point of operation will determine how excess capacity or capacity deficit is distributed among different users. The key insight into scheduling for different users is maintaining the user fairness metric at a constant value while taking advantage of multi-user diversity.

In a system that classifies users according to service, different classes of users are served according to a priority or other scheme, such as in a round robin fashion. First consider a single class or type of user. The exemplary embodiment uses the highest .function.(A.sub.i (t),U.sub.i (t)); however, alternate embodiments may use a lowest value and/or an alternate type function. Determination of an appropriate definition of f( ), A.sub.i (t) and U.sub.i (t) determines the effectiveness of the scheduling.

The present invention is applicable to a variety of scheduling algorithms and prioritizations, and is not limited to those described herein. For clarity, several scheduling algorithms will be discussed to provide examples of a generalized scheduler 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 whic