HK1083048B

HK1083048B - Method and apparatus of scheduling data transmission in a wireless communication system

Info

Publication number: HK1083048B
Application number: HK06103044.4A
Authority: HK
Inventors: 陈道
Original assignee: 高通股份有限公司
Priority date: 2002-07-01
Filing date: 2003-06-28
Publication date: 2010-05-20

Description

Method and apparatus for scheduling data transmission in wireless communication system

Background

Technical Field

The present invention relates generally to data communications, and more specifically to techniques for scheduling data transmissions to a terminal with variable scheduling delays.

Background

Wireless communication systems are widely deployed to provide various types of communication such as voice, data, and so on. These systems may be multiple-access systems capable of supporting communication with multiple users, and may be based on Code Division Multiple Access (CDMA), Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), and some other multiple access techniques. CDMA systems may provide certain advantages over other types of systems, including increased system capacity.

Many CDMA systems are capable of supporting multiple types of services (e.g., voice, packet data, etc.) on the forward and reverse links. Each type of service is generally characterized by a particular set of requirements. For example, voice services generally require a fixed and generic grade of service (GOS) and a relatively strict and fixed delay for all users. In particular, the total one-way delay of a speech frame may be specified to be less than 100 milliseconds. These requirements can be met by providing a fixed and guaranteed data rate for each user (e.g., via dedicated traffic and code channels assigned to the user during a communication session) and guaranteeing a certain maximum error rate for voice frames independent of link resources. To maintain the required error rate at a given data rate, a higher resource allocation is required for users with degraded links.

In contrast, packet data services may be able to tolerate different GOS for different users and may further be able to tolerate variable amounts of delay. The GOS of the packet data service may be defined as the total delay incurred in the data message delivery. This delay may be a parameter used to optimize the efficiency of the data communication system.

In a wireless communication system, the total transmit power available at any given base station is typically fixed. For a multiple access communication system, the total transmit power may be allocated and used to concurrently transmit data to multiple terminals. Multiple terminals with different requirements may require data transmission at any given time. To support both types of services (i.e., voice and packet data), a CDMA system may be designed and operated to first allocate transmit power to voice users requiring a particular GOS and shorter delay. Any remaining transmit power may then be allocated to packet data users that may generally tolerate longer delays.

A major goal of wireless communication systems is then to schedule data transmissions for packet data users to achieve high system performance. A number of challenges are encountered in scheduling data transmissions to terminals for these packet data users. First, the amount of transmit power required by voice users may vary from frame to frame, which may then correspondingly affect the amount of transmit power available to packet data users. Second, the transmit power required by each scheduled terminal for a given data rate depends on the channel conditions and may also vary over time. Third, terminals to be scheduled may have different scheduling delays (which may be defined, for example, as the difference between the time the terminal is scheduled and the time of the actual data transmission). For example, some terminals may be in soft handoff and supported by multiple base stations, and the scheduling delay for these terminals may be longer than those terminals that are not in soft handoff.

There is therefore a need in the art for techniques to schedule data transmissions to terminals with different scheduling delays.

Disclosure of Invention

Scheduling terminals with different scheduling delays is provided herein, which may occur due to different factors, such as soft handoff, communication with different network elements, different backhaul delays, and so forth. Total transmit power P available at a given base station_totAnd will be allocated to non-scheduled terminals (e.g., voice and fixed data rate terminals) first. Then, the remaining transmission power P is adjusted_schedFor scheduled terminals. Terminals associated with different scheduling delays may be scheduled based on various scheduling schemes.

In a first scheme, the scheduling delay for each terminal to be scheduled for data transmission is first determined. The terminals are then scheduled for data transmission based on the longest scheduling delay among all terminal delays and in accordance with a particular scheduling scheme. To perform this scheduling, the total available transmit power for data transmission to the terminals (at the time of actual data transmission) may be estimated or predicted, and the link efficiency for each terminal may also be estimated. The terminals are then scheduled based on their estimated link efficiencies and estimated total available transmit power. Since the longest scheduling delay is used, a higher margin is used in scheduling the terminals. A particular scheduling scheme may consider various factors in scheduling a terminal, such as, for example, link efficiency of the terminal, quality of service (QOS) to be provided, type of service, amount and type of data to be transmitted, revenue and revenue considerations, and so forth.

In a second scheme, the scheduling delay for each terminal to be scheduled for data transmission is first determined. Each terminal is then assigned a particular priority based on its scheduling delay. Generally, terminals with longer scheduling delays will be assigned higher priority than terminals with shorter scheduling delays. The terminals are then scheduled for data transmission based on their assigned priorities and in accordance with a particular scheduling scheme.

In a third scheduling scheme, the scheduling delay for each terminal to be scheduled for data transmission is first determined. The terminals are then classified into a number of categories based on their scheduling delays. Each class may be assigned a particular percentage of the total system capacity (e.g., a certain percentage of the total available transmit power). The terminals in each class are then scheduled for data transmission based on the system capacity assigned to the class and in accordance with a particular scheduling scheme. The percentage assigned to each category may be determined by various factors and may also be dynamically adjusted based on operating conditions and system requirements.

In a fourth aspect, a scheduling delay for each terminal to be scheduled for data transmission is first determined. The terminals are then scheduled for data transmission according to a particular scheduling scheme to provide an individual scheme for each terminal. The scheduling of each terminal is then applied to future transmission intervals based on its scheduling delay.

Various aspects and embodiments of the invention are described in further detail below. The invention further provides methods, program codes, digital signal processors, schedulers, terminals, base stations, systems, and other apparatuses and elements implementing various aspects, embodiments, and features of the invention, as described in further detail below.

Drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like elements have like numerals wherein:

fig. 1 is a diagram of a wireless multiple-access communication system supporting multiple users;

FIG. 2 is a diagram illustrating a timeline for scheduling and transmitting data to a particular terminal;

fig. 3 is a diagram illustrating a first scheduling scheme in which terminals are scheduled for data transmission based on the longest scheduling delay;

fig. 4 is a diagram illustrating a second scheduling scheme in which terminals are scheduled for data transmission based on their scheduling delays;

fig. 5 is a diagram illustrating a third scheduling scheme in which total available transmit power is allocated to various classes of terminals, and terminals in each class are scheduled based on the transmit power allocated to that class;

figure 6 is a flow diagram of an embodiment of a process for scheduling data transmissions for a terminal according to a fourth scheduling scheme;

FIG. 7 is a block diagram of a particular embodiment of the network element shown in FIG. 1; and

fig. 8 is a block diagram of an embodiment of a scheduler.

Detailed Description

Fig. 1 is a diagram of a wireless multiple-access communication system 100 supporting multiple users. System 100 may be designed to implement one or more CDMA standards such as IS-95, CDMA2000, IS-856, W-CDMA, and others, which are well known in the art and incorporated herein by reference. System 100 includes a plurality of base stations 104 that provide coverage for their respective geographic regions. A base station may also be referred to as a Base Transceiver System (BTS), an access point, a UTRAN, or some other terminology. A base station and/or the area it covers is also commonly referred to as a cell. Base stations 104 are coupled to a system controller 102, which system controller 102 provides coordination and control for the base stations coupled thereto. The system controller 102 may be a Base Station Controller (BSC), a Mobile Switching Center (MSC), or some other network entity.

As shown in fig. 1, various terminals 106 are dispersed throughout the system. In an embodiment, each terminal 106 may communicate with one or more base stations 104 on the forward link and/or reverse link at any given moment based on whether the terminal is active and whether it is in an area with sufficient link signal quality from multiple base stations. The forward link (or downlink) refers to transmission from the base station to the terminal, and the reverse link (or uplink) refers to transmission from the terminal to the base station.

In fig. 1, base station 104a transmits user-specific data to terminals 106a, 106b, and 106c on the forward link, base station 104b transmits user-specific data to terminals 106a, 106b, 106d, and 106e, and base station 104c transmits user-specific data to terminals 106b and 106 f. Each of these user-specific transmissions may be for voice, packet data, or both. Other terminals in the system may receive pilot and command/dedicated signaling from the base station, but no user-specific data transmission. For simplicity, these terminals are not shown in fig. 1. Terminals 106a and 106b are within the overlapping coverage areas of multiple base stations and each of these terminals may simultaneously receive user-specific data transmissions from multiple base stations during soft handoff. For simplicity, reverse link communications are not shown in fig. 1.

As described above, the system 100 may be designed to provide various types of services, such as voice, packet data, and so on. Only certain types of services are generally scheduled without scheduling other types of services. For example, voice users are not generally scheduled due to their latency constraints and limited data rates. In contrast, packet data users generally do not have short latency constraints and can tolerate more variation in receiving their data, and therefore are suitable candidates for scheduling.

In an embodiment, voice users and fixed rate (e.g., circuit switched) data users are not scheduled. The use of transmit power may be determined for these users based on automatic feedback from the terminal. Packet data users may have their data rates and durations scheduled by a scheduler using various schemes described below.

Total available transmit power P for a given base station_totMay be used to send data to both unscheduled and scheduled users. The total amount of transmit power P required to support unscheduled users per scheduling interval may be determined_unschedAnd assigns them to these users. The remaining transmit power P is then determined based on the following technique_sched(P_sched＝P_tot-P_unsched) To the scheduled users.

Fig. 2 is a diagram illustrating a timeline for scheduling and transmitting data to a particular terminal. At time T₁An indication is received (e.g., by a scheduler) that there is data to send to the terminal. At time T₂And estimating a link for the terminal.

An estimate of this link is made in response to receiving an indication of upcoming data for the terminal. Alternatively, link estimates may be made for the terminals at regular intervals. Other information needed to schedule the terminal for data transmission is also determined. For example, the expected data transmission (at time T) may be estimated and predicted₅) The amount of transmit power available.

At time T3, data transmissions for this terminal are scheduled along with data transmissions for other terminals. If the terminal is scheduled to receive a data transmission, then at time T₄An announcement is sent to the terminal to allow the terminal to prepare for the data transmission. The announcement may be sent in accordance with the particular standard implemented. The announcement may be provided, for example, via a message sent from the base station to the terminal (e.g., a Supplemental Channel Assignment Message (SCAM) in cdma200₅Data transmission to the terminal is started.

Scheduling may be performed at each "scheduling" interval, and the terminal is typically scheduled for data transmission in one or more subsequent "transmission" intervals. In one embodiment, both the scheduling interval and the transmission interval are given in "frame" units, which may be 20 milliseconds for some CDMA systems. However, other scheduling and transmission intervals may be used and are within the scope of the present invention. For simplicity, the following description assumes that scheduling and data transmission are performed at each frame. In any given frame, (1) scheduling is performed and the terminals are scheduled for data transmission in one or more subsequent frames, and (2) data is transmitted in the current frame to the terminals scheduled for data transmission based on the schedule determined in the previous frame.

As shown in fig. 2, each terminalThe end will be associated with the following times: (1) the data indicates a specific time T between the time and the scheduled time₁₃(2) a specific time T between the link estimation time and the data transmission time₂₅(3) scheduling a specific time T between the time and the notification time₃₄And (4) scheduling a specific time T between the time and the data transmission time₃₅. Time between notification time and start of transmission T₄₅May be from time T₃₅And T₃₄And (4) pushing out.

Terminals to be scheduled for data transmission may be associated with different "scheduling" delays. In one embodiment, the scheduling delay is defined as the difference between the time the terminal is scheduled for data transmission and the actual data transmission time to the terminal (i.e., time T in FIG. 2)₃₅). In another embodiment, the scheduling delay is defined as the difference between the time data is available to the terminal and the actual data transmission time to the terminal (i.e., time T in FIG. 2)₁₅). It is within the scope of the present invention that the scheduling delay may be defined in other ways.

Different scheduling delays between terminals may occur due to various factors. First, some terminals may be in soft handoff with multiple base stations, while other terminals may be in communication with a single base station. For a terminal in soft handover, additional time may be required to collect and report the relevant information needed to schedule the terminal and to schedule data transmissions from multiple base stations to the terminal. This extra time then results in a longer scheduling delay for the terminals in soft handover. Second, terminals moving to adjacent coverage areas or networks not controlled by the original BSC and/or MSC may also be associated with longer scheduling delays. Additional delays are encountered for these terminals in routing the relevant information through the new BSC and/or MSC. Third, terminals supported by base stations with different backhaul delays may also be associated with different scheduling delays. Other factors may also cause different scheduling delays between terminals. These various operating conditions are described in further detail below.

Terminals in soft handoff may be associated with longer "reporting" delays and longer scheduling delays than those terminals not in soft handoff. The need to forward relevant information from all terminal-capable base stations to the entity or entities that need the information for scheduling can result in long reporting delays. Furthermore, if the terminal's communication with a base station in soft handover is interrupted, a long reporting delay may result if the information from that base station needs to be routed through the system controller.

Longer scheduling delays for terminals in soft handover may result from the need to coordinate data transmissions from multiple base stations to the terminal. Different base stations may have different "loads," which refers to various factors related to data transmission to the terminals under the coverage area of the base station. One such factor may relate to the amount of transmit power (i.e., their bits in the transmit buffer of the base station) required to meet the forward link requirements of the terminal. Another factor may relate to the amount of channelization (e.g., Walsh) code space needed to meet the requirements of the terminal.

The load of each base station typically varies over time. For scheduling a terminal that is not in soft handover, only the load of one base station needs to be considered, which then simplifies the scheduling for that terminal. Conversely, to schedule a terminal in soft handover, the load of all affected base stations needs to be considered, which complicates the scheduling for that terminal. For soft handover, coordination is required between the multiple base stations supporting the terminal in soft handover so that data transmission from these multiple base stations to the terminal occurs at approximately the same time. This would then allow the soft-handoff terminal to "soft combine" the symbols received from multiple base stations prior to decoding, which improves performance.

Longer scheduling delays for soft handover may also result from longer notification delays. The scheduling for a terminal in soft handover must be sent to all affected base stations and a notification needs to be sent from each of these base stations to the terminal.

Referring to fig. 1, the additional complexity and delay associated with scheduling a terminal in soft handoff can be illustrated. As an example, base station 104a may be designed to schedule data transmission for terminals 106a and 106b, where terminal 106b is in soft handoff with base stations 104a and 104b and terminal 106b is in soft handoff with 104a, 104b, and 104 c. To schedule the terminal 106a, the base station 104a needs from the base station 104b (1) information about the link efficiency of the terminal 106a with respect to the base station 104b, (2) the load at the base station 104b, and so on. Similarly, to schedule terminal 106b, base station 104a may need from each of base stations 104b and 104c (1) information about the link efficiency of terminal 106b with respect to each of these base stations, (2) the load at base stations 104b and 104c, and so on. Conversely, base station 104a can be freed from additional information from these other base stations when terminal 106c is scheduled for data transmission.

For wireless communication systems, terminals may also experience different scheduling delays based on their location in the system. A terminal located within the coverage area of one base station will be scheduled for data transmission by that base station, which will be associated with the shortest possible scheduling delay. A terminal located between two or more base station coverage areas (i.e., in soft handoff) may be scheduled by (or have its associated information indicated by) a BSC providing coordination and control for that set of base stations. Thus, a longer scheduling delay may result from having to route the relevant information and schedule through the BSC. A terminal located between two or more BSC coverage areas may be scheduled by (or have its associated information indicated by) an MSC that provides coordination and control for that set of BSCs. Additional scheduling delays would then result from having to route the relevant information and schedule through the BSC and MSC. And a terminal located between two or more MSC coverage areas may be scheduled by (or have its associated information indicated by) a network entity that provides coordination and control for that set of MSCs, which may additionally increase latency. Thus, the scheduling latency for a given terminal may increase as the number of network elements scheduled for the terminal and/or routing information increases.

Various types of schemes may be used to perform terminal scheduling for data transmission. Such as a distributed scheduling scheme, a centralized scheduling scheme, and a hybrid scheduling scheme. Other types of scheduling schemes may also be used and are within the scope of the present invention.

For a distributed scheduling scheme, each base station contains a separate scheduler that schedules terminals for data transmission within its coverage area. For this scheme, coordination is required between the multiple base stations supporting each terminal in soft handoff so that data transmission from these multiple base stations to the terminal occurs at about the same time so that the symbols received from these base stations can be soft combined prior to decoding.

For a centralized scheduling scheme, a master scheduler schedules terminals within the coverage area of multiple base stations for data transmission. This master scheduler may be located in the system controller 102 (e.g., a BSC or MSC), one of the base stations 104, or some other network element. For this scheme, all relevant information needed to schedule the terminals is provided to the master scheduler, which then schedules the terminals and provides scheduling for each base station.

For a hybrid scheduling scheme, the primary scheduler schedules terminals for a group of base stations, and a separate scheduler may be used for each base station. For example, the master scheduler may be designed to schedule all terminals in soft handoff, and a separate scheduler at each base station may be designed to schedule terminals not in soft handoff.

For all scheduling schemes, the scheduler may need various types of information in order to perform scheduling efficiently. The information required by each base station may comprise, for example, the load at each base station, the total transmit power available for data transmission to the scheduled terminals, P_schedThe link efficiency of each terminal to be scheduled, the amount of data to be transmitted to each terminal, etc. Some information may be provided by the base station or some other network entity and some information may be provided by the terminal to be scheduled. This information typically varies over time, and scheduling may be performed in a manner that takes into account the variation.

Each terminal to be scheduled provides feedback to all base stations with which it is communicatingAnd (4) information. The feedback information may then be used to schedule data transmission to the terminals. The feedback information may indicate, for example, a signal quality of a signal received at the terminal, a highest data rate supportable by the terminal, a positive Acknowledgement (ACK) and/or a Negative Acknowledgement (NACK) for a previously transmitted packet, other information, or any combination thereof. The quality of the received signal may be determined, for example, by the ratio of the energy per bit of the traffic channel dedicated to the terminal to the total noise and interference (E)_b/I_o) Or the ratio of the energy per pilot chip to the total received power density of the pilot channel (E)_cp/I_o) Or both, for quantitative representation. The highest supportable data rate may be determined by estimating the E of the pilot transmitted by the base station_b/I_oOr some other technique.

For a distributed scheduling scheme, each base station receives feedback information from the terminal for the terminal (including those in soft handoff) as well as other relevant information from other base stations. Each base station then schedules data transmissions for the terminals in its coverage area based on the received information. For a centralized scheduling scheme, each base station may forward feedback information and other related information to the master scheduler, which may then use the information to schedule data transmissions to the terminals.

Scheduling of data transmission for a terminal may be made based on various factors. Some of these factors are described below. Other factors may also be considered, which are within the scope of the present invention.

Link efficiencyLink efficiency indicates the amount of transmit power required to transmit data to a given terminal and may be given in units of Watts per bit per second (Watts/bps). Each terminal needs a specific E for the signal it receives_b/I_oTo achieve a particular performance target level. The object E_b/I_oCommonly referred to as a setpoint, and the target level of performance may be quantified in terms of a particular Frame Error Rate (FER) or Packet Error Rate (PER). Each terminal may also be associated with a particular propagation path loss and may require a particular number of bits per secondAmount of transmit power (denoted as P)_b) To achieve the object E_b/I_o。

The link efficiency for a given terminal may be determined as the desired total transmit power per bit per second, P_bThis is required for reliable data transmission. For terminals communicating with a single base station, P_bIs the amount of transmit power required from this single base station for reliable data transmission. For a terminal in soft handoff with multiple base stations, P_bIs the sum of the transmit power per bit per second required by the respective base stations supporting the terminal in soft handover and can be expressed as:

formula (1)

Wherein P is_b ⁱIs the required per bit per second transmit power of base station i, and N_BIs the number of base stations with which the terminal is in soft handover.

The link efficiency for a given terminal may be determined in various ways. In one embodiment, the link efficiency is determined based on power control bits sent to the terminal on the forward link. In many CDMA systems, the transmit power of each terminal is controlled by a reverse power control mechanism such that the set point is reached at the base station while minimizing the amount of interference to other terminals. The forward link power control bits are used to implement a reverse power control mechanism and are transmitted at a power level estimated to provide reliable detection at the terminal. Determination of link efficiency based on Power control bits is described in further detail in U.S. patent application serial No. 09/239,451, entitled "Method and Apparatus for controlling transmission Power in a CDMA Communication System," filed on 28.1.1999, which is assigned to the assignee of the present invention and is incorporated herein by reference. Link efficiency may also be determined based on traffic data sent to the terminal.

Quality of service (QOS)The quality of service is related to the level of service enjoyed by a given terminal. The QOS may be determined by various parameters such as (1) the total delay experienced by the terminal for data transmission, (2) the average or raw throughput achieved by the terminal, (3) the actual frame error rate of the data transmission, and so on.

Other factors may also be considered in scheduling terminals for data transmission. One such factor may be as to the type of service provided to the terminal. Different types of services may be associated with different revenues or revenues, and terminals associated with higher revenues/revenues may be considered first before associating terminals with lower revenues/revenues. Another factor may relate to the type of data to be sent to the terminal. In scheduling, delay-sensitive data may be given a higher priority, while delay-insensitive data may be given a lower priority. Retransmitted data due to decoding errors of previous transmissions may also be given a higher priority because other processes may be waiting for retransmitted data at the terminal. Other factors may also be considered and are within the scope of the present invention.

Any combination of the above factors may be considered in scheduling a terminal for data transmission. For example, each factor may be weighted by a corresponding weight, and the weighted values of all factors may be combined to provide a score for each terminal. The score may be used to prioritize the terminals and scheduling may be performed based on the priorities of the terminals.

In one particular implementation, the score Φ for terminal i at frame n_i(N) indicates at N_PThe linear average throughput achieved over the previous frame and can be expressed as:

formula (2)

Wherein r is_i(n) is the "achieved" data rate (in bits/frame) at frame n for terminal i. In general, r_i(n) by a specific maximum achievable data rate r_maxAnd a particular minimum data rate (e.g., zero).

In another particular implementation, the score Φ of terminal i at frame n_i(n) indicates the exponential average throughput achieved over a particular time interval and can be expressed as:

Φ_i(n)＝(1-α)·Φ_i(n-1)+α·r_i(n)/r_maxequation (3)

Where α is an exponential averaging time constant, corresponding to a shorter averaging time interval having a larger value of α.

In another particular implementation, the score Φ of terminal i at frame n_i(n) indicates the normalized data rate and can be expressed as:

formula (4)

Wherein Tp_i(n) is the average or recent throughput of terminal i at frame n, and K is a weighting factor.

For scores calculated using equations (2) and (3), a higher priority may be given to terminals with lower scores, which corresponds to a lower average throughput. For scores calculated using equation (4), a higher priority may be given to terminals with higher scores, which corresponds to a lower average or recent throughput.

If the scheduling delay is the same for all terminals to be scheduled for data transmission, the terminals are scheduled based on any combination of the various factors described above. At each frame, relevant information required for scheduling the terminal is received by the scheduler. The scores and/or priorities of the terminals may then be determined and the terminals may be scheduled based on their scores and/or priorities. A notification is then sent to each scheduled terminal as shown in fig. 2. Thereafter, data transmission to these scheduled terminals occurs at the specified times.

The scheduling of terminals for data transmission is described in further detail below: U.S. patent application Ser. No. 09/528,235, entitled "Forward-link Scheduling in a Wireless communication System", filed on 3.17.2000; U.S. patent serial No. 6,335,922, entitled "method and Apparatus for Forward Link scheduling", published on 1 st 1/2002, is assigned to the assignee of the present invention and is incorporated herein by reference.

If the scheduling delays are different for all terminals to be scheduled for data transmission, the terminals are scheduled based on various scheduling schemes, some of which are described below.

In a first scheduling scheme for terminals with unequal scheduling delays, the terminals are scheduled based on the longest scheduling delay among the delays of all terminals to be scheduled. At each frame, the scheduler receives complete information for the terminal to be scheduled for data transmission. As described above, different terminals may be associated with different reporting delays. In that case, each terminal may be considered for scheduling whenever the scheduler receives relevant information for the terminal.

Fig. 3 is a diagram illustrating scheduling of terminals for data transmission based on the longest scheduling delay. In this example, four terminals A, B, C and D would be scheduled for data transmission. These terminals may correspond to terminals 106a, 106b, 106d, and 106e in fig. 1. Terminals a and B are in soft handoff and associated with a longer scheduling delay, and terminals C and D are not in soft handoff and associated with a shorter scheduling delay. In this example, the relevant information is received for terminals A, B, C and D in frame n. In the same frame n it is possible to schedule terminals C and D for data transmission in frame n +1 due to their shorter scheduling delay, while terminals a and B need to be scheduled for data transmission in frame n +2 due to their longer scheduling delay. However, for the first scheduling scheme, all four terminals A, B, C and D are scheduled in frame n for data transmission in frame n +2, corresponding to the longest scheduling delay for all four terminals.

In general, the scheduler is able to determine the maximum scheduling delay D for all terminals to be scheduled_max. At frame n, the scheduler can then use any of the scheduling schemes as at frame n + D_maxThe data transmission at (b) schedules the terminals, and the scheduling scheme may be used to schedule the terminals using equal scheduling delays.

Scheduling of data transmission for a group of terminals is dependent on various factors, such as (1) the total transmit power available for data transmission, P_schedAnd (2) link efficiency per terminal P_b. When data transmission is to begin, at frame n, the scheduler may be provided with a frame n + D_maxExpected total available transmit powerIs estimated. The total available transmit power expected to be available at a later frame may be estimated based on information available at the scheduled time instant. Also provides the scheduler with link efficiencyIs estimated for each terminal to be scheduled in frame n-D_iAnd (4) making. The link efficiency of each terminal is thus D before the current frame n_iMaking an estimate at each frame, where the delay is reported, D_iMay be zero or some other positive value. For total available transmit power with increasing delay between when the estimates are made and when they are usedAnd link efficiencyIs likely to be inaccurate.

The total transmit power available to the scheduled terminals and the link efficiency for each terminal may be estimated (or predicted) at a particular time instant (e.g., when scheduling data transmissions) for a particular future time instant (e.g., a frame at which data transmissions are to begin). However, the link conditions may change between when the estimate is made and when it is actually used. When the link changes, these estimates may be inaccurate when they are actually used. If the total available transmit power for the scheduled terminals is much lower than the estimated and/or the estimated link efficiency is too optimistic, excessive frame errors may result, which may then reduce performance. Alternatively, if the total available transmit power is far above the estimated and/or estimated link efficiency is too pessimistic, then this may result in underutilization of valuable system resources.

For the first scheduling scheme, since the scheduling is based on the longest scheduling delay, a higher margin (e.g., a larger backoff) may be used when scheduling the terminal for data transmission to account for a higher likelihood of inaccurate estimation.

In a second scheduling scheme for terminals with unequal scheduling delays, the terminals are assigned priorities based on their scheduling delays and/or some other factor (e.g., soft handoff). In each frame the scheduler is ready to receive the complete information in a certain later frame for the terminal to be scheduled for data transmission. These terminals may be associated with different scheduling delays. For the second scheme, terminals with longer scheduling delays are assigned a higher priority and terminals with shorter scheduling delays are assigned a lower priority. The terminals are then scheduled for data transmission by taking into account their priorities. The terminals may be scheduled with the same scheduling delay based on the above-described considerations for scheduling of terminals having the same scheduling delay.

For the second scheduling scheme and using the example shown in fig. 3, all four terminals A, B, C and D are scheduled at frame n for data transmission in a subsequent frame n + 2. For scheduling, terminals a and B are assigned a higher priority because they are in soft handoff and associated with a longer scheduling delay, and terminals C and D are assigned a lower priority because they are not in soft handoff. Thus, terminals a and B may be allocated a larger portion of the resources (e.g., transmit power and channelization code space) available in frame n + 2. These terminals are then informed on frame n +2 about any data transmissions scheduled for them. Since the priority of terminals C and D is lower, part of all resources may already be allocated to terminals a and B when the scheduler considers these terminals for data transmission in frame n + 2. However, terminals C and D will still be allocated to any remaining available resources.

Fig. 4 is a diagram illustrating scheduling of terminals for data transmission based on their scheduling delays. As in the example shown in fig. 4, the scheduler receives the relevant information for terminals A, B, C and D in frame n. Similar to the example of fig. 3, terminals a and B are associated with longer scheduling delays, while terminals C and D are associated with shorter scheduling delays. Terminals a and B are scheduled for data transmission at frame n +2, while terminals C and D are scheduled for data transmission at frame n + 1. Due to the longer scheduling delay, terminals a and B are given higher priority when scheduling data transmission for frame n + 2. While terminals C and D are given lower priority when scheduling data transmission for frame n +1 due to their shorter scheduling delays. In practice, it is desirable to have the total transmit power available at frame n +1May have been allocated to terminals with longer scheduling delays when the scheduler performed scheduling at the previous frame n-1.

In general, the second scheduling scheme schedules terminals with longer scheduling delays before scheduling terminals with shorter scheduling delays. However, due to some other considerations (e.g., higher revenue), terminals with shorter scheduling delays may be assigned a higher priority than terminals with longer scheduling delays. The second scheduling scheme attempts to schedule as many terminals as possible for data transmission at the earliest possible time, which, with some exceptions, improves system performance.

In a third scheduling scheme for terminals with unequal scheduling delays, a certain percentage of the available system capacity is allocated to each class of terminals with the same scheduling delay. May be based on the total transmit power P available to the scheduled terminals_schedTo quantitatively describe the system capacity. The particular percentage of system capacity to be allocated to each class of terminals may be determined based on various factors.

In one embodiment, the percentage of available system capacity to allocate to each category is determined based on (e.g., proportional to) the link efficiency of the terminals in the category. Link efficiency may be further weighted based on various factors such as, for example, the transmission capacity (watts) of the base station, the total amount of data to send to the terminals in each class, the throughput of the terminals, the revenue associated with each data bit to send to the scheduled terminals, and so on. In another embodiment, the available system capacity is assigned to the categories based on any combination of factors such as those listed above. In a distributed scheduling scheme, system capacity allocation may be performed by (and for) each base station independently, or for a centralized scheduling scheme, system capacity allocation may be performed by a master scheduler.

Fig. 5 is a diagram illustrating that the total available transmission power is allocated to two different classes of terminals. In this example, category X includes terminals with longer scheduling delays (e.g., terminals a and B in the above example), and category Y includes terminals with shorter scheduling delays (e.g., terminals C and D in the above example). On each frame, the scheduler receives information about the terminals to be scheduled in that frame. The scheduler then classifies the terminals into the appropriate categories based on their scheduling delays. The scheduler may further determine other parameters needed to schedule the terminals, such as the percentage of total available transmit power allocated to the class. Next, the scheduler bases on the transmission power P allocated to the class X_XTo schedule terminals in class X and similarly based on the transmit power P assigned to class Y_YTo schedule terminals in category Y. Scheduling for each class of terminals may be used similar to that described aboveIn a manner that is performed for terminals with equal scheduling delays.

As described above, longer reporting and/or scheduling delays generally result in reduced accuracy in terms of estimated total available transmit power and link efficiency. In one embodiment, different amounts of margin (i.e., different back-off amounts) are used for different classes of terminals. In particular, a larger margin may be used for category X associated with longer scheduling delays, while a smaller margin may be used for category Y associated with shorter scheduling delays. In another embodiment, terminals with longer scheduling delays may be scheduled more conservatively than terminals with shorter scheduling delays. For example, a terminal with a longer scheduling delay may start with a lower data rate.

The transmit power allocated to each class may also be dynamically adjusted to account for changes in operating conditions. For example, the allocation percentage may be adjusted based on the usage of each category, changes in link efficiency, and so on.

In some cases, the transmit power allocated to a given class may also be reallocated and used by another class. In an embodiment, unused transmit power for a class associated with a longer scheduling delay may be used for another class associated with a shorter scheduling delay. For example, at frame n, terminals in category X may be scheduled for data transmission in frame n + 2. At frame n, if it is determined that the transmit power allocated to class X in frame n +1 (allocated by the scheduler at frame n-1) is not completely used up by data transmissions in that class to the terminals to be scheduled, then any remaining unused transmit power of class X for frame n +1 will be used for data transmissions to terminals in class Y. This is possible because terminals in category Y have shorter scheduling delays and can be notified in time for data transmission in frame n + 1.

In a fourth scheduling scheme for terminals with unequal scheduling delays, the terminals are first scheduled for data transmission as if they had equal scheduling delays. The scheduling for each terminal is then applied after its scheduling delay.

Fig. 6 is a flow diagram of an embodiment of a process 600 for scheduling data transmissions for a terminal in accordance with a fourth scheduling scheme. At each frame, the scheduler receives complete information for the terminal to be scheduled for data transmission (step 612). These terminals may be associated with different scheduling delays. For the fourth scenario, each terminal to be scheduled may first be assigned a particular priority based on various factors, such as link efficiency, throughput, yield considerations, and the like, or any combination thereof (step 614). For example, a higher priority may be assigned to terminals with higher link efficiency, lower recent throughput, higher revenue, etc.

The terminals are then scheduled for data transmission by considering their priorities (step 616). For this scheme, the terminals are scheduled with or without consideration of their scheduling delays and may be scheduled for data transmission assumed at the next frame, or at the shortest scheduling delay among the delays of all the terminals being scheduled, or at some other specified time. The total transmit power P expected to be available at this assumed transmission time_schedFor use in scheduling these terminals.

The result of the scheduling is a scheduling of data transmission for each terminal (e.g., data rate and transmit power to be used for the scheduled terminal). Thereafter, the individual scheduling for each terminal is applied after its scheduling delay (step 618). Thus, scheduling for terminals with shorter scheduling delays is applied before scheduling for terminals with longer scheduling delays.

Since scheduling for individual terminals will be applied at different times due to different scheduling delays, for any given frame, the total available transmit power P for that frame_sched(n) may not be sufficient to support all data transmissions that have been scheduled for that frame. If this occurs, then the schedule for the frame is modified accordingly (step 620). For example, the total available transmit power for a given frame may be first allocated to have a longer scheduling delay (or higher priority)) The remaining transmit power may then be allocated to terminals with shorter scheduling delays (or lower priority). Terminals that are "bumped" from their intended frame will be considered for data transmission in the next frame (e.g., by raising their priority). The flexibility of rescheduling terminals with shorter scheduling delays in subsequent (or upcoming) frames is possible because of their shorter notification times. For each frame, data is sent to each terminal scheduled to receive a data transmission in that frame (step 622).

To reduce the likelihood of terminals being knocked out of their scheduled frames, a higher margin may be used when scheduling terminals with longer scheduling delays. For example, a desired link efficiency for a terminal with a longer scheduling delay may be increased by a larger margin than for a terminal with a shorter scheduling delay.

The techniques described herein may be used to schedule terminals with different scheduling delays due to various factors. Further, the scheduling delay may be defined in various ways, as described above.

Fig. 7 is a block diagram of a particular embodiment of various network elements in communication system 100. The system 100 includes a system controller 102 for communicating with a plurality of base stations 104 (only one base station is shown in fig. 7 for simplicity). The system controller 102 is further coupled to a Public Switched Telephone Network (PSTN)112 (e.g., for voice services) and a Packet Data Serving Node (PDSN)114 (e.g., for packet data services). The system controller 102 coordinates communication between the terminals in the wireless communication system and the base station 104, PSTN 112, and PDSN 114.

In the embodiment shown in fig. 7, the system controller 102 includes a call control processor 712, a plurality of selector elements 714 (only one selector element is shown in fig. 7 for simplicity), and a scheduler 716. The call control processor 712 controls the processing of calls for each terminal. One selector element 714 is assigned for controlling the communication between each terminal and one or more base stations. A scheduler 716 is coupled to all selector elements 714 in the system controller 102 and schedules data transmissions for packet data users.

In the example design shown in fig. 7, base station 104 includes a plurality of channel elements 722a through 722 n. One channel element 722 is assigned for handling communications for each terminal and is coupled to an associated selector element 714, which selector element 714 is also assigned to the terminal. Each selector element 714 receives the schedule for the assigned terminal (e.g., data rate, transmit power, and transmit time) from the scheduler 716 and forwards the schedule to the associated channel element 722. Channel element 722 receives, codes, and modulates data for the assigned terminal based on the received schedule. The modulated signal is up-converted and conditioned by a transmitter (TMTR)724, routed through a duplexer 726, and transmitted over a forward link via an antenna 728.

At the receiving end 106, the forward link signal is received by an antenna 750 and routed to a front end unit 752. Front-end unit 752 filters, amplifies, frequency downconverts, and digitizes the received signal to provide data samples. The data samples are then demodulated by a demodulator (Demod)754, decoded by a decoder 756, and provided to a data sink device 758. The demodulation and decoding are performed in a manner complementary to the modulation and coding performed at the base station.

Data transmission on the reverse link occurs in a similar manner. Data is provided in terminal 106 by a data source 760, encoded by an encoder 762, and modulated by a modulator (Mod)764 to provide a modulated signal. The modulated signal is then upconverted and conditioned by a front-end unit 752 and transmitted via an antenna 750.

At base station 104, the reverse link signal is received by an antenna 728, routed through a transceive converter 726, and provided to a receiver (RCVR) 730. A receiver (RCVR)730 filters, amplifies, frequency downconverts, and digitizes the reverse link signal and provides data samples to channel elements 722 assigned to the terminal. The assigned channel element 722 demodulates and decodes the data samples in a manner complementary to the modulation and coding performed at the terminal. The decoded data may be provided to a selector element 714 assigned to the terminal, which may further forward the data to another base station 104, PSTN 112, or PDSN 114. As described above, this design supports the transmission of data and voice services over the system. Other designs are also contemplated as being within the scope of the present invention.

The processing (e.g., coding and modulation) for the forward and reverse links IS defined by a particular CDMA standard or system implemented (e.g., IS-95, CDMA2000, IS-856, or W-CDMA). These standards are well known in the art and are not described herein.

Fig. 8 is a block diagram of an embodiment of a scheduler 716. In this embodiment, scheduler 716 includes a controller 812 coupled to a memory unit 814 and a timing unit 816. The control 812 is further coupled to a selector element 714 in the system controller 102 and receives relevant information (e.g., link efficiency P of the terminal) from the base station_bThe data rate of the unscheduled terminals, the amount of data to be sent to each scheduled terminal, etc.). Controller 812 may use the received information to estimate the total available transmit power P for scheduled terminals_sched. The controller 812 then estimates the total available transmit power P based on the estimated total available transmit power_schedAnd schedules data transmission for the terminal using any one or a combination of the scheduling schemes described above. The result of the scheduling is an individual scheduling for each terminal scheduled for data transmission. The scheduling for each terminal includes, for example, a scheduled data rate, an assigned transmit power, a transmission start time and duration, and the like.

Memory unit 814 may be used to store various types of information needed and/or provided by controller 812, such as relevant information received from base stations, scheduling, and so forth. The timing unit 816 provides a timing signal for performing scheduling to the controller 812. The timing signals also allow the controller 812 to send the schedule to the selector element 714 at the appropriate time. The memory unit 814 may be implemented using RAM, DRAM, flash memory, or other types of memory, or a combination thereof. Timer unit 816 may be comprised of a timer running a system clock, an on-board oscillator locked to an external signal, a storage element for receiving system time from an external source, or some other design.

The scheduling described above can be done with various designs. The location of the scheduler depends on whether a centralized, distributed or mixed scheduling scheme is desired. For example, a scheduler may be located within each base station and used to schedule terminals within the coverage area of the base station. This distributed scheduling may reduce the processing delay for some terminals. Alternatively, the master scheduler may be designed to schedule data transmissions for a group of base stations. Such centralized scheduling may result in more efficient use of system resources.

In any case, the scheduler is tasked with assigning data rates to each modulated terminal to optimize a set of objectives. These goals may include (1) improved utilization of system capacity by sending scheduled and unscheduled tasks that are supportable within as many system capacity limits as possible, (2) improved communication quality and minimized transmission latency, and (3) fair allocation of system capacity to scheduled terminals based on a set of priorities. These goals are optimized by balancing a list of factors.

Scheduling of data transmission on the forward link is also described in further detail in the above-mentioned U.S. patent application serial No. 09/528,235 and U.S. patent serial No. 6,335,922.

The scheduling techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the scheduler or other elements implementing any one or combination of the scheduling techniques described herein may be implemented within one or more Application Specific Integrated Circuits (ASICs), Digital Signal Processors (DSPs), Digital Signal Processing Devices (DSPDs), programmable logic circuits (PLDs), Field Programmable Gate Arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, other electronic units designed to perform the functions described herein, or a combination thereof.

For a software implementation, the scheduling techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in a memory unit (e.g., memory unit 814 of fig. 8) and executed by a processor (e.g., controller 812). The memory unit may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art.

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

Claims

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

Determining a scheduling delay for each of a plurality of terminals to be scheduled for data transmission;

classifying the plurality of terminals into a plurality of categories based on scheduling delays of the terminals;

assigning a specific percentage of the total system capacity to each category; and

one or more terminals in each class are scheduled for data transmission based on the system capacity assigned to the class and in accordance with a particular scheduling scheme.

2. The method of claim 1, wherein the total system capacity is quantitatively described by a total transmit power available for data transmission.

3. The method of claim 1, wherein each of the classes comprises one or more terminals with substantially equal scheduling delays.

4. The method of claim 1, wherein the percentage of the total system capacity allocated to each class is determined based on a link efficiency of a terminal.

5. The method of claim 1, wherein the percentage of the total system capacity allocated to each category is determined based on an amount of data to be transmitted to the plurality of terminals.

6. The method of claim 1, wherein data is sent to one or more terminals in each class at transmission intervals determined based on scheduling delays associated with the classes.

7. The method of claim 1, wherein a higher margin is used in scheduling terminals with longer scheduling delays.

8. The method of claim 1, further comprising:

determining a remaining transmit power from a first class, the first class associated with a longer scheduling delay; and

one or more terminals in the second category associated with the shorter scheduling delay are scheduled with transmit power remaining from the first category.

9. The method of claim 1, wherein the particular scheduling scheme schedules one or more terminals in each class for data transmission based on link efficiency of the terminals.

10. The method of claim 1, wherein the particular scheduling scheme schedules one or more terminals in each class for data transmission based on a priority of the terminal.

11. The method of claim 1, wherein the particular scheduling scheme schedules the one or more terminals in each class for data transmission based on a set of parameters.

12. The method of claim 1, wherein said plurality of terminals includes terminals in soft handoff and terminals not in soft handoff.

13. A scheduler in a wireless communication system, comprising:

a memory unit for storing data for scheduled data transmission; and

a controller coupled to the processor unit and configured to:

14. The scheduler of claim 13, wherein each class comprises one or more terminals with substantially equal scheduling delays.

15. A base station comprising the scheduler of claim 13.

16. An apparatus for scheduling data transmissions in a wireless communication system, comprising:

means for determining a scheduling delay for each of a plurality of terminals to be scheduled for data transmission;

means for classifying a plurality of terminals into a plurality of classes based on scheduling delays of the terminals;

means for assigning a particular percentage of the total system capacity to each category; and

means for scheduling one or more terminals in each class for data transmission based on the system capacity assigned to the class and in accordance with a particular scheduling scheme.

17. A method of scheduling data transmissions in a wireless communication system, comprising:

scheduling a plurality of terminals for data transmission in accordance with a particular scheduling scheme to provide scheduling for each terminal; and

applying scheduling to said each terminal at a transmission interval, said transmission interval being determined based on a scheduling delay of the terminal.

18. The method of claim 17, wherein a higher margin is used when scheduling terminals with longer scheduling delays.

19. The method of claim 17, wherein terminals with longer scheduling delays are assigned higher priorities, and wherein the scheduling is performed based in part on the priorities of the terminals.

20. The method of claim 17, further comprising:

estimating a link efficiency for each terminal, and wherein the plurality of terminals are further scheduled based on the estimated link efficiencies for the terminals.

21. The method of claim 17, further comprising:

determining a total transmit power available for data transmission in a current transmission interval;

evaluating one or more schedules of one or more terminals scheduled for data transmission in a current transmission interval; and

modifying at least one schedule based on the total available transmit power.

22. The method of claim 21, wherein a terminal with a shorter scheduling delay is removed from data transmission in a current transmission interval if the total available transmit power is insufficient to support all terminals scheduled for data transmission.

23. A scheduler in a wireless communication system, comprising:

a memory unit for storing data for scheduled data transmission; and

a controller coupled to the processor unit and configured to:

the scheduling for each terminal is applied at a transmission interval that is determined based on the scheduling delay for that terminal.

24. The scheduler of claim 23, wherein a higher margin is used when scheduling terminals with longer scheduling delays.

25. A method of scheduling data transmissions in a wireless communication system, comprising:

assigning each terminal a particular priority, the particular priority being determined based on its scheduling delay; and

a plurality of terminals are scheduled for data transmission based on the assigned priorities and in accordance with a particular scheduling scheme.

26. The method of claim 25, wherein terminals with longer scheduling delays are assigned a higher priority than terminals with shorter scheduling delays.

27. The method of claim 25, wherein a higher margin is used when scheduling terminals with longer scheduling delays.

28. A scheduler in a wireless communication system, comprising:

a memory unit for storing data for scheduled data transmission; and

a controller coupled to the processor unit and configured to:

29. The scheduler of claim 28, wherein terminals with longer scheduling delays are assigned higher priority than terminals with shorter scheduling delays.

30. A method of scheduling data transmissions in a wireless communication system, comprising:

determining a scheduling delay for each of a plurality of terminals to be scheduled for data transmission; and

the plurality of terminals are scheduled for data transmission according to a particular scheduling scheme based on a longest scheduling delay among the scheduling delays of the plurality of terminals.

31. The method of claim 30, further comprising:

estimating a total transmit power available for data transmission to a plurality of terminals; and

estimating the link efficiency of each terminal, an

Wherein the plurality of terminals are further scheduled based on the estimated total available transmit power and the estimated link efficiency for the terminal.

32. The method of claim 30, wherein a higher margin is used when scheduling multiple terminals for data transmission due to the use of the longest scheduling delay.

33. A scheduler in a wireless communication system, comprising:

a memory unit for storing data for scheduled data transmission; and

a controller coupled to the processor unit and configured to:

34. The scheduler of claim 33, wherein a higher margin is used when scheduling a plurality of terminals for data transmission due to the use of the longest scheduling delay.