Multiple threshold scheduler

The present invention provides different scheduling criteria depending on overall system performance in an effort to maintain fairness among mobile terminals and sustain a required QoS level. The invention is particularly effective for multi-carrier systems, wherein scheduling must also take into consideration the carrier used to transmit the scheduled data. In one embodiment, the present invention determines the spread of throughput rates for all mobile terminals being served by a given base station and bases the scheduling criteria thereon. Preferably, a standard deviation calculation is used to measure the throughput spread. The standard deviation of throughput associated with a collective group of mobile terminals is indicative of the differences between the lowest and highest throughputs with respect to the average throughput for the collective group of mobile terminals.

FIELD OF THE INVENTION

The present invention relates to wireless communications, and in particular to scheduling data for transmission from a base station to one or more mobile terminals.

BACKGROUND OF THE INVENTION

Wireless communication networks that allocate communication resources, such as time or frequency, require a scheduler to select data to be transmitted. When multiple users are vying for these resources, the scheduler must analyze the incoming data and determine the data having the highest priority for transmission. Priority has traditionally been based on maximizing overall system throughput or maintaining a certain Quality of Service (QoS) level to ensure that data is transmitted in a timely fashion. When maximizing throughput, users having better channel conditions are favored over those with worse channel conditions. Thus, the users with the less favorable channel conditions are always given lower priority. As a result, those users with poor channel conditions are prone to lower QOS levels. In contrast, trying to maintain certain QOS levels often leads to unnecessarily low system throughput.

Many schedulers prioritize packets based solely on carrier-to-interference ratios (CIRs) derived from information fed back from the mobile terminals. Such schedulers maximize throughput without regard to fairness or minimum throughput requirements and typically schedule delivery for users that are closest to the base station. Schedulers attempting to provide some degree of fairness use rudimentary scheduling criteria resulting in poor system throughput. There are also many problems with existing schedulers in terms of supporting multi-media wireless-internet services. Further, most schedulers are not designed for multi-carrier operation, which makes them unsuitable for multiple carrier—data and voice (MC-DV) environments.

These existing scheduling techniques fail to provide an adaptive scheduling criterion that is capable of evolving to meet the constantly varying demands of the wireless communication environment to optimize throughput while ensuring a defined degree of fairness among users. Accordingly, there is a need for an adaptive scheduling technique to optimize throughput while ensuring fairness among users. There is a further need for a scheduling technique with these capabilities that can optimize multi-carrier diversity in order to maximize overall system throughput while maintaining a desired degree of fairness.

SUMMARY OF THE INVENTION

The present invention provides different scheduling criteria depending on overall system performance in an effort to maintain fairness among mobile terminals and sustain a required QoS level. The invention is particularly effective for multi-carrier systems, wherein scheduling must also take into consideration the carrier used to transmit the scheduled data. In one embodiment, the present invention determines the spread of throughput rates for all mobile terminals being served by a given base station and bases the scheduling criteria thereon. Preferably, a standard deviation calculation is used to measure the throughput spread. The standard deviation of throughput associated with a collective group of mobile terminals is indicative of the differences between the lowest and highest throughputs with respect to the average throughput for the collective group of mobile terminals.

The throughput associated with a high standard deviation indicates that certain mobile terminals are experiencing very low throughput while others are experiencing relatively high throughput, and the potential for unfair scheduling is increased. As such, the scheduling criterion for higher standard deviation in cumulative throughput attempts is to inject higher priority on lower throughput mobile terminals. In contrast, as the standard deviation decreases, when most of the mobile terminals' throughputs are close to the average cumulative throughput, the scheduling criteria should emphasize overall throughput and thus select scheduling for mobile terminals where throughput can be maximized, instead of ensuring that mobile terminals with lower throughput are treated fairly.

When attempting to maximize throughput, maximum carrier-to-interference ratio (CIR) scheduling may be used wherein data is scheduled for a carrier and mobile terminal combination associated with the most favorable channel conditions based on the CIR or the like. Alternatively, proportional fairness scheduling may be used instead of or in combination with the maximum CIR scheduling. Proportional fairness scheduling attempts to take advantage of temporal variations of the channels by scheduling transmissions to the mobile terminals using the carriers associated with the strongest signal levels. Those skilled in the art will recognize other scheduling criteria compatible with the concepts of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

With reference toFIG. 1, wireless networks use access points, such as base stations10, to facilitate communications with access terminals, such as mobile terminals12, within a select coverage area, or cell. Respective groups of base stations10are supported by a communication network14, which may include mobile switching centers, a public switched telephone network (PSTN), a packet-switched network, or a combination thereof. The communication network14is used to transport packets to and from the base station10. The packets may be communicated in a direct packet-switched manner or on top of a circuit-switched platform. The manner in which the packets are communicated to the base station10is not critical to the invention.

During forward link communications from the base station10to select mobile terminals12, the base station10must determine the manner and order in which to transmit the data received in the packets from the communication network14to the mobile terminals12. In multiple carrier systems, the base station10will also determine the carrier, or channel, on which to deliver the packets. Accordingly, the base station10will include a control system16having a control plane18controlling the flow of data through a data plane20. For communicating with the mobile terminals12, the data plane20will process packets received from the communication network14via a network interface22under the control of the control plane18. The packets are processed into units, which are delivered to radio frequency (RF) transceiver circuitry24for transmission. For the sake of clarity, the term “packet” refers to packetized data, which is received by the base station10from the communication network14. The term “unit” refers to packetized data that is transmitted from the base station10to the mobile terminals12. A unit may include all or any part of one or more packets. Although units may directly correspond to packets, units are preferably a given size wherein packets may vary in size from one packet to another. The units may include voice, video, or traditional data.

The forward link from the base station10to the mobile terminal12will include one or more channels, which are divided into defined time slots. The RF transceiver circuitry24is configured to modulate a given unit as dictated by the control plane18and transmit the modulated unit via one or more antennas26during a single time slot. The RF transceiver circuitry24is preferably configured to implement different modulation and coding techniques based on channel conditions, the capabilities of the mobile terminals12, or required transmission standards. As noted, the RF transceiver circuitry24may transmit units over a number of distinct carriers. Those skilled in the art will recognize the various possible modulation techniques and that multiple units may be transmitted in a given time slot.

The control plane18includes a scheduler28, which is configured to prioritize and control the delivery order of units to the mobile terminals12based on parameters detailed further below. During operation, packets for any number of mobile terminals12are received and stored in a buffer30associated with the data plane20. The buffer30is segregated into multiple queues, each associated with a given mobile terminal12. If the packets do not directly correspond to units, the incoming packets are processed into the desired units. The units are stored in the respective queues in the order in which they are received. Preferably, the queues use a first-in-first-out (FIFO) configuration.

The present invention provides different scheduling criteria depending on overall system performance in an effort to maintain fairness among mobile terminals12and sustain a required QoS level. The invention is particularly effective for multi-carrier systems, wherein scheduling must also take into consideration the carrier used to transmit the scheduled data. In one embodiment, the present invention determines the spread of throughput rates for all mobile terminals12being served by a given base station10and bases the scheduling criteria thereon. Preferably, a standard deviation calculation is used to measure the throughput spread. The standard deviation of throughput associated with the collective group of mobile terminals12is indicative of the differences between the lowest and highest throughputs with respect to the average throughput for the collective group of mobile terminals12. Thus, the throughput associated with a high standard deviation indicates that certain mobile terminals12are experiencing very low throughput and very high throughput, and the potential for unfair scheduling is increased. As such, the scheduling criteria for higher standard deviation in cumulative throughput attempts is to inject higher priority on lower throughput mobile terminals12. In contrast, as the standard deviation decreases, when most of the mobile terminals' throughputs are close to the average cumulative throughput, the scheduling criteria should emphasize overall throughput and thus select scheduling for mobile terminals12where throughput can be maximized, instead of ensuring that mobile terminals12with lower throughput are treated fairly.

Further details will be provided below after an overview of an exemplary process according to one embodiment of the present invention. With reference to the flow diagram ofFIG. 2, operation of the scheduler28is illustrated according to one embodiment. On an ongoing basis, the units to transmit are placed in queues for the corresponding mobile terminals12(step100). Further, the scheduler28will continuously monitor channel conditions for each carrier and each mobile terminal12as reported back from the mobile terminals12(step102). In general, a channel condition represents the quality of the transmission channel from the base station10to the mobile terminals12for each of the multiple carriers. The throughput rates may be a function of actual or estimated data throughput rates, channel conditions, or a combination thereof.

Channel conditions may vary continuously and may be determined using any number of techniques. For example, carrier-to-interference ratios (CIR), which represent a measure of carrier signal power to interference power, may be fed back to the base station10from the mobile terminals12. The scheduler28will preferably continuously track channel conditions for each carrier and mobile terminal12. The scheduler28will also monitor the throughput for each mobile terminal12(step104).

Assume that there are M active mobile terminals12served by the base station10. The cumulated throughput for all mobile terminals12in time slot n can be expressed by a vector,Λ(n), as
Λ(n)=[Λ0(n),Λ1(n), . . . ,ΛM−1(n)].Eq.1
Due to the channel variations such as path loss, shadow fading and Rayleigh fading, significant variations in throughput may occur between different mobile terminals12at any given time. These variations seriously degrade the throughput performance and the QoS associated therewith. To evaluate throughput performance, the standard deviation, σth(n), of cumulated throughput for all mobile terminals12in time slot n, is determined. The standard deviation for cumulative throughput, σth(n), is defined as follows:

σth⁡(n)=1M⁢∑m=0M-1⁢{Λm⁡(n)-μ⁢⁢(n)}2,Eq.⁢2
where μ(n) is the mean of cumulated throughput for time slot n, as given by

To calculate the standard deviation σth(n), each mobile terminal12monitors the channel conditions of N separate carriers using N common pilot signals and determines N separated CIRs. The CIRs are then sent to the base station10. The base station10will create a CIR matrix,Γ(n) (step106), which can be expressed as

By using the resulting transmission rate matrix,R(n), as well as the maximum CIR user scheduling, the scheduler28can estimate the cumulated user throughput in the next time slot n (step110), as given by
{circumflex over (Λ)}(n)=[{circumflex over (Λ)}0(n),{circumflex over (Λ)}1(n), . . . ,{circumflex over (Λ)}M−1(n)]Eq.6
where

Λ^m⁡(n)=Λm⁡(n-1)+∑k=0N-1⁢αk,m⁡(n)·Rk,m⁡(n)Eq.⁢7
and where αk,m(n)=1 for an active kth carrier for the mth user and αk,m(n)=0 for an inactive kth carrier for the mth user. Or αk,m(n)=p for an active kth carrier for the mth user and αk,m(n)=1−p for an inactive kth carrier for the mth user, p is a positive number less than unit. Using the estimated throughputs, {circumflex over (Λ)}m(n), the scheduler28can readily obtain the standard deviation of the estimated throughput, {circumflex over (σ)}th(n) (step112) and will then schedule units for transmission for select mobile terminals12and on select carriers using scheduling criteria selected based on the standard deviation of the estimated throughput, {circumflex over (σ)}th(n) (step114).

For example, a detailed multiple-threshold (N=3) adaptive scheduling criteria is described below in three-carrier environment. With three thresholds, there are four categories of scheduling criteria. In the example, maximum CIR scheduling indicates the scheduler will systematically select the carrier and mobile terminal12having the greatest CIR until each available carrier has a unit scheduled for transmission for the given time slot n. The exemplary scheduling criteria follows in association withFIGS. 3A-3D:If {circumflex over (σ)}th(n)≦σ1(max), use maximum CIR scheduling for each of the three carriers (FIG. 3A);If σ1(max)<{circumflex over (σ)}th(n)≦σ2(max),identify a mobile terminal12with the least received throughput and allocate one slot on the best carrier for the identified mobile terminal12. Apply maximum CIR scheduling for the remaining two carriers (FIG. 3B);If σ2(max)<{circumflex over (σ)}th(n)≦σ3(max), identify two mobile terminals12with the least received throughput and allocate two slot on the first and second best carriers for these mobile terminals12. Apply maximum CIR scheduling to the remaining carrier (FIG. 3C); andIf {circumflex over (σ)}th(n)>σ3(max), identify three mobile terminals12with the least received throughput and allocate three slots on the carriers for these mobile terminals12. No maximum CIR user scheduling is applied (FIG. 3D).
Here, σk(max)is the threshold of standard deviation of throughput, whereby streaming service performance can be easily controlled under a desired level of σN(max), for k=1, 2, . . . , N.

In order to define the threshold of standard deviation of throughput σk(max), two values, σLand σHare set. If {circumflex over (σ)}th(n)≦σL, the maximum CIR scheduling should be utilized, while if {circumflex over (σ)}th(n)>σH, the maximum CIR scheduling has to be terminated. As an example, the threshold of standard deviation of throughput σk(max)is determined based on both σLand σH, and represented by:

As seen from the above, the present invention looks at the spread for throughput across multiple users to determine a scheduling criteria. As the spread decreases, the amount of CIR scheduling increases. As the spread increases, lower throughput mobile terminals are prioritized during scheduling. Although the above example implements standard deviation to provide a statistical analysis for the relative spread for the throughput of each mobile terminal12, those skilled in the art will recognize other techniques and algorithms to use for analyzing the relative spread for throughput and selecting scheduling criteria based thereon.

As an alternative to the maximum CIR scheduling described above, proportional fairness scheduling may be used. Proportional fairness scheduling attempts to take advantage of temporal variations of the channels by scheduling transmissions to the mobile terminals12using the carriers associated with the strongest signal levels. For example, the mobile terminals12may request certain data rates based on signal levels or channel quality, and the base station10will send the data to the mobile terminal12based on the requested data rate. When proportional fairness scheduling is required, data is scheduled for transmission to the mobile terminals12based on a ratio of the requested data rate to an average throughput rate over a given window. The latter favors those mobile terminals with better capability to transmit larger volumes of data.

These aspects of the invention can be implemented using alternative equations and relationships than those described in detail above. Those skilled in the art will recognize improvements and modifications to the preferred embodiments of the present invention. All such improvements and modifications are considered within the scope of the concepts disclosed herein and the claims that follow.