HK1115690A - Systems and methods for optimizing the resource allocation in a wireless communication system - Google Patents

Description

System and method for optimizing resource allocation in a wireless communication system

Background

FIELD

The present invention relates generally to wireless communication systems, and more particularly to a system and method for optimizing resource allocation to serve different types of data streams in a wireless communication system.

Background

In a wireless communication system, data transmitted from a transmitter to a remote station may be associated with different types of applications. Some of these applications may be throughput sensitive but delay tolerant. Other applications may have low throughput but may be highly delay sensitive. It is therefore desirable to satisfy the diverse demands of applications residing on remote stations that receive data over the air from a base station. It is desirable to allocate resources at the base station in an optimal manner that best meets the needs of these applications while consuming as little resources as possible. Thus, a system and method that optimizes the allocation of resources to serve different types of data streams in a wireless communication system would be beneficial.

Summary of the invention

A base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system is disclosed. The base station includes a transmitter for transmitting forward links to a plurality of remote stations. The base station also includes a processor and a memory in electronic communication with the processor. Instructions are stored in the memory. The instructions are executable to implement a method that involves computing data metrics for data in a plurality of queues. Each queue corresponds to a different data flow in the wireless communication system. The method also involves using the data metrics to determine a separate one transmission metric for each of a plurality of possible transmission formats. The transmission metrics for a given transmission format depend on those data metrics corresponding to the data allocated for that given format. The transmission metric for a given transport format may also depend on a penalty associated with the given transport format. The method also involves selecting a transport format having an optimal transport metric. The data allocated for the selected transmission format may be transmitted on the forward link according to the selected transmission format.

In some embodiments, the data allocated for a given transport format is determined such that the transmission metric for that transport format is optimized in view of one or more constraints. The one or more constraints may include a packet capacity constraint that specifies that data allocated for the transport format does not exceed a data capacity of one packet. In some embodiments, the method may further involve selecting the data allocated for the given transport format such that the transmission metric is optimized without violating packet capacity constraints.

The one or more constraints may also include an addressing constraint specifying that data allocated for the transport format does not exceed an addressing capacity of a packet. In some embodiments, the method may further involve determining that addressing constraints are violated, and in response, adjusting the allocated data such that the transmission metric is optimized without violating neither the addressing constraints nor the packet capacity constraints.

A separate one bit metric may be calculated for each bit in each of the plurality of queues. The bit metric for a given bit in a given queue may depend on the arrival time of the given bit, the deadline of the given bit, the average throughput experienced by the given queue, and the average throughput expected for the given sequence.

In some embodiments, the method may be performed at each transmission opportunity. The wireless communication system may operate in accordance with the 1xEV-DO standard.

Another embodiment of a base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system is also disclosed. The base station includes means for calculating data metrics for data in a plurality of queues. Each queue corresponds to a different data flow in the wireless communication system. The base station also comprises means for using the data metrics to determine a separate one transmission metric for each of a plurality of possible transmission formats. The transmission metrics for a given transmission format depend on those data metrics corresponding to the data allocated for the given transmission format. The base station further comprises means for selecting one of the transmission formats having the best transmission metric. The base station also includes means for transmitting data allocated for the selected transmission format on the forward link according to the selected transmission format.

A method in a base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system is also disclosed. The method involves calculating data metrics for data in a plurality of queues. Each queue corresponds to a different data flow in the wireless communication system. The method also involves using the data metrics to determine a separate one transmission metric for each of a plurality of possible transmission formats. The transmission metrics for a given transmission format depend on those data metrics corresponding to the data allocated for the given transmission format. The method also involves selecting a transport format having an optimal transport metric. The method also involves transmitting data allocated for the selected transmission format on the forward link according to the selected transmission format.

Brief description of the drawings

Exemplary embodiments of the present invention will become more fully apparent from the following description and the accompanying drawings, which are to be read in conjunction with the accompanying drawings. Understanding that these drawings depict only exemplary embodiments and are not therefore to be considered to be limiting of its scope, the exemplary embodiments of the invention will be described with additional specificity and detail through use of the accompanying drawings, in which:

FIG. 1 illustrates an example of a communication system that supports multiple users and is capable of implementing at least some aspects of the embodiments discussed herein;

FIG. 2 illustrates an exemplary system in which some embodiments may be practiced;

fig. 3 illustrates information regarding available transmission formats that may be used to transmit data on the forward link;

FIG. 4 illustrates a possible data allocation for different data streams within the system;

FIG. 5 illustrates constraints that may affect the allocation of data to be transmitted on the forward link;

FIG. 6 illustrates metrics that may be computed for data in a queue;

fig. 7 shows transmission metrics that may be calculated for each possible transmission format;

FIG. 8 illustrates an exemplary method that may be performed by a scheduler;

FIG. 9 illustrates another example method that may be performed by a scheduler;

FIG. 10 illustrates yet another example method that may be performed by a scheduler; and

figure 11 is a functional block diagram illustrating one embodiment of a base station.

Detailed description of the invention

Communication systems have evolved to allow information signals to be transmitted from a starting station to a physically different end station. When an information signal is transmitted from an origin station over a communication channel, the information signal is first converted into a form suitable for efficient transmission over the communication channel. The conversion or modulation of the information signal involves varying a parameter of the carrier wave in accordance with the information signal in such a way that the resulting spectrum of the modulated carrier wave is confined within the communication channel bandwidth. At the destination station, the original information signal is copied from a modulated carrier wave received over the communication channel. This replication is typically achieved by using the inverse of the modulation process employed by the origination station.

Modulation also facilitates multiple access, i.e., simultaneous transmission and/or reception, of several signals over a common communication channel. Multiple-access communication systems often include multiple remote subscriber units that require intermittent service of relatively short duration rather than continuous access to the common communication channel. Several multiple access techniques are known in the art, such as Code Division Multiple Access (CDMA), Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), and amplitude modulation multiple Access (AM).

Multiple-access communication systems may be wireless or wired and may carry voice and/or data. In a multiple access communication system, communication between users is conducted through one or more base stations. A first user on one subscriber station communicates to a second user on a second subscriber station by transmitting data on the reverse link to a base station. The base station receives the data and may route the data to another base station. The data is transmitted to the second subscriber station on the forward channel of the same or another base station. The forward channel refers to transmission from the base station to the subscriber station, and the reverse channel refers to transmission from the subscriber station to the base station. Similarly, communication may be between a first user at one mobile subscriber station and a second user at a landline station. The base station receives data from the subscriber on a reverse channel and routes the data to a second subscriber through a Public Switched Telephone Network (PSTN). In many communication systems, such as IS-95, W-CDMA, IS-2000, and the like, the forward channel and reverse channel are assigned different frequencies.

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

Note that the exemplary embodiments are provided as examples throughout this discussion; however, alternate embodiments may be incorporated into the various aspects without departing from the scope of the invention. In particular, the present invention is applicable to data processing systems, wireless communication systems, mobile IP networks, and any other system in which it is desirable to receive and process wireless signals.

The exemplary embodiment employs a spread spectrum wireless communication system. Wireless communication systems are widely deployed to provide various types of communication such as voice, data, and so on. These systems may be based on Code Division Multiple Access (CDMA), Time Division Multiple Access (TDMA), or some other modulation technique. CDMA systems offer certain advantages over other types of systems, including increased system capacity.

The wireless communication system may be designed to support one or more standards such as the "TIA/EIA/IS-95-B mobile station-base station compatibility standard for dual-mode wideband spread spectrum cellular systems," referred to herein as the IS-95 standard, the standard referred to herein as the W-CDMA standard in a group of documents including document numbers 3GPP TS 25.211, 3GPP TS 25.212, 3GPP TS 25.213, and 3GPP TS 25.214, 3GPP TS 25.302, the standard referred to herein as the W-CDMA standard, the standard provided by a consortium referred to herein as the third generation partnership project 2, referred to herein as 3GPP2, and TR-45.5, formerly referred to as the IS-2000MC, referred to herein as the CDMA2000 standard. The standards cited above are expressly incorporated herein by reference.

The systems and methods described herein may be used with a High Data Rate (HDR) communication system. The HDR communication system may be designed to conform to one or more standards, such as the "cdma 2000 high data rate packet data air interface specification", 3gpp2c.s0024-a, first edition, published by the third generation partnership project 2 alliance at 3 months 2004. The contents of the aforementioned standards are incorporated herein by reference. An HDR subscriber station, which may be referred to herein as an Access Terminal (AT), may be mobile or stationary, and may communicate with one or more HDR base stations, which may be referred to herein as Modem Pool Transceivers (MPTs). An access terminal transmits and receives data packets through one or more modem pool transceivers to an HDR base station controller, which may be referred to herein as a Modem Pool Controller (MPC). Modem pool transceivers and modem pool controllers are part of a network called an access network. An access network transports data packets between multiple access terminals. The access network may be further linked to other networks outside the access network, such as a corporate intranet or the internet, and may transport data packets between each access terminal and such outside networks. An access terminal that has established an active traffic channel connection with one or more modem pool transceivers is referred to as an active access terminal and is said to be in a traffic state. An access terminal that is in the process of establishing an active traffic channel connection with one or more modem pool transceivers is said to be in a connection setup state. An access terminal may be any data device that communicates through a wireless channel or through a wired channel, for example using fiber optic or coaxial cables. An access terminal may further be any of a number of types of devices including but not limited to PC card, compact flash, external or internal modem banks, or wireless or landline telephones. The communication channel through which an access terminal sends signals to a modem pool transceiver is called a back channel. The communication channel through which a modem pool transceiver sends signals to an access terminal is called a forward channel.

Fig. 1 illustrates one example of a communication system 100 that supports multiple users and is capable of implementing at least some aspects of the embodiments discussed herein. Any of a variety of algorithms and methods may be used to schedule transmissions in system 100. System 100 provides communication for a plurality of cells 102A-102G, each of which is serviced by a corresponding one of base stations 104A-104G, respectively. In the exemplary embodiment, some of base stations 104 have multiple receive antennas, while others have only one receive antenna. Similarly, some of the base stations 104 have multiple transmit antennas, while others have only a single transmit antenna. These do not constitute a limitation on the combination of the transmit antennas and the receive antennas. Thus, the base station 104 may have multiple transmit antennas and a single receive antenna, or multiple receive antennas and a single transmit antenna, or both single and multiple transmit and receive antennas.

Remote stations 106 in the coverage area may be fixed point (i.e., stationary) or mobile. As shown in fig. 1, various remote stations 106 are dispersed throughout the system 100. At any given moment, each remote station 106 communicates with at least one, and possibly more than one, base station 104 on the forward channel and reverse channel depending on 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 handoffs in CDMA communication systems are well known and are described in U.S. patent No.5,101,501 entitled "Method and System for Providing a Soft Handoff in a CDMA cellular telephone System," assigned to the assignee of the present invention.

The forward channel refers to transmissions from the base station 104 to the remote station 106, and the reverse channel refers to transmissions from the remote station 106 to the base station 104. In the exemplary embodiment, some of the remote stations 106 have multiple receive antennas, while others have only one receive antenna. In fig. 1, base station 104A transmits data to remote stations 106A and 106J on a forward channel, base station 104B transmits data to remote stations 106B and 106J, base station 104C transmits data to remote station 106C, and so on.

Fig. 2 illustrates an exemplary system 200 in which some embodiments may be practiced. System 200 includes a base station 204 and one or more remote stations 206. In fig. 2, 3 remote stations 206 are shown, namely a first remote station 206a, a second remote station 206b, and a third remote station 206 c. Each remote station 206 includes one or more data streams 208. More specifically, the first remote station 206a includes a first set of data streams 208a, the second remote station 206b includes a second set of data streams 208b, and the third remote station 206c includes a third set of data streams 208 c. Data stream 208 is a stream of data that may correspond to a particular application, such as IP telephony, video telephony, file transfer protocols, games, and so forth.

Base station 204 includes data 210 for transmission on the forward link to some or all of data streams 208 in system 200. Base station 204 maintains a queue 212 for each data flow 208 in system 200. Data 210 destined for a particular data flow 208 is contained in the data flow's queue 212.

At any transmission opportunity (e.g., time slot), base station 204 may initiate transmission of new data 210 using one of several transmission formats. The transport format specifies how channel resources, such as code space, bandwidth, power, etc., are allocated among the various different data streams 208 that may be serviced during the transmission opportunity. The transport format also specifies the structure of the packets (e.g., packet length, coding, modulation, etc.) used to carry the data in the transport format.

Base station 204 includes a scheduler 214. At each transmit opportunity, the scheduler 214 selects a transmission format to use to transmit the data 210 on the forward link. The scheduler 214 also determines the data allocation for each of the different data streams 208 within the packet(s) associated with the transport format. The transmission format and allocation of data to the various data streams 208 may be collectively referred to as a "transmission instance". Scheduler 214 selects transport formats and determines data allocations to optimize the resource allocation of system 200 to service different types of data flows 208 within system 200. Various exemplary embodiments of the scheduler 214 will be described below.

The embodiment of scheduler 214 shown in fig. 2 uses data metrics to determine the transport format used and the data allocation of the transmitted packets to the different data streams. Scheduler 214 includes a data metric calculation component 215. At each transmit opportunity, the data metric calculation component 215 calculates a data metric for each unit of data (e.g., bits) and each possible transmission format in each queue 212. The metric calculated for a particular unit of data represents a reward associated with transmitting that unit of data on the forward link.

Scheduler 214 also includes a data allocation component 217 and a transmission metric calculation component 219. For each transport format that may be used in the next transmission opportunity, the data allocation component 217 allocates data 210 from a different queue 212 for transmission, and the transmission metric calculation component 219 calculates a transmission metric. The transmission metric for a particular transmission format depends on the sum of the data metrics of the data 210 allocated for transmission. The data allocation component 217 allocates the data 210 to be transmitted according to a particular transmission format to maximize the transmission metric for that transmission format.

Certain constraints of system 200 may affect the distribution of data 210. For example, the amount of data 210 (e.g., the number of bits) included in a packet transmitted on the forward link may not exceed the capacity of the packet to carry the data 210. As another example, the data 210 included in a packet transmitted on the forward link may not exceed the capacity of the packet to address multiple data streams 208 and/or multiple remote stations 206. As another example, a packet may not include more data 210 than the amount of data 210 available for transmission. These are just a few examples of constraints that may be associated with system 200.

The scheduler 214 also includes a constraint verification component 221. Constraint verification component 221 verifies that the data allocation for the possible transmission formats is consistent with one or more constraints of system 200 as mentioned above. If the constraint verification component 221 determines that the data allocation for a particular transmission format violates one or more of the constraints of the system 200, the data allocation component 217 adjusts the data allocation such that the transmission metric is maximized without violating these constraints.

Scheduler 214 also includes a format selection component 223. Once the transmission metrics for the possible transmission formats are calculated, the format selection component 223 selects the transmission format with the largest transmission metric. The data allocated for the transmission format is then transmitted on the forward link according to the transmission format.

Fig. 3 illustrates information regarding available transmission formats that may be used to transmit data on the forward link. Such information can be used and/or stored at base station 204. In the illustrated embodiment, this information is presented in the form of a table 316. However, in other embodiments, the information may be arranged in a different manner. The information given is also relevant to the 1xEV-DO Rev-A forward link. However, embodiments may be practiced in other types of wireless communication systems.

Each row in table 316 corresponds to a different possible transport format. There are 6 columns in table 316. The first column 318 in the table 316 is an index of the transport format. The second column 320 of table 316 is the payload length of the packet created according to the transport format.

A third column 322 in table 316 indicates a Data Rate Control (DRC) value with which the transport format is compatible. The DRC is a signal transmitted from the remote station 206 to the base station 204. The value of the DRC indicates which transmission formats the remote station 206 is capable of receiving given its channel conditions. For example, if the remote station 206 sends a DRC of "0" to the base station 204, the remote station 206 is able to receive packet types corresponding to transmission formats 1, 4, 8, and 13. As another example, if the remote station 206 transmits DRC "1" to the base station 204, the remote station 206 is able to receive packet types corresponding to transmission formats 2, 5, 9, and 14.

Column 4 324 in table 316 indicates whether the packet corresponding to the transport format is a multi-user packet. A multi-user packet is a packet containing data 210 from a queue 212 that may belong to multiple remote stations 206. In some embodiments, DRCs of 0-2 are incompatible with multi-user packets, while DRCs of 3-13 are compatible with multi-user packets.

The fifth column 326 in the table 316 indicates the equivalent data rate of the packet corresponding to the transport format. A sixth column 328 in table 316 indicates the expected transmission duration of the packet corresponding to the transport format.

Fig. 4 illustrates a possible data allocation to different data streams 208 within the system 200. In the illustrated embodiment, the information is presented in the form of a table 430. However, in other embodiments, the information may be arranged in a different manner.

Table 430 includes a separate row for each queue 212 maintained by base station 204. As noted previously, base station 204 maintains one queue 212 for each data flow 208 in system 200. Table 430 includes a separate column for each possible transport format that may be used.

The letters i and j will be used herein as indices of the queue and the transport format, respectively. Thus, cell b of table 430_ijIncluding the number of bits allocated from queue i in the case where the next packet is transmitted using transport format j.

The scheduler 214 builds and/or updates the table 430 at the beginning of each transmission opportunity. Here affecting the bit allocation b_ijSeveral factors of the value of (c). One factor is the DRC being received from the remote station 206. If transport format j is not compatible with the DRC value being received from the remote station 206, no data 210 in queue i is allocated for transmission. However, if transmission format j is compatible with the DRC value being received from the remote station 206, all of the data 210 in queue i may be allocated for transmission subject to some other factor.

Influencing bit allocation b_ijIncluding certain constraints. FIG. 5 illustrates that bit allocation b may be affected in some embodiments_ijOf (2) is determined.

Constraints 532 may include packet capacity constraints 532 a. The packet capacity constraint 532a specifies that the amount of data 210 (e.g., the number of bits) included in a packet transmitted on the forward link does not exceed the capacity of the packet to carry the data 210. In some embodiments, the packet capacity constraint 532a may be expressed as:

in some embodiments, the term b in formula 1_iIndicating the number of bits allocated to the ith queue for transport format j. In such embodiments, there are N data streams (and thus N queues) in the system 200. Item G_i，jIndicating the maximum amount of data from data stream i that transport format j can carry with all channel resources allocated to data stream i.

Alternatively, in some embodiments, term b in formula 1_iIndicating the bits allocated to all data streams residing at the ith remote station. In such an embodiment, there are N remote stations in the system 200. Item G_i，jIndicating the maximum amount of data to remote station i that transport format j can carry with all channel resources allocated to the respective data streams residing on remote station i.

Constraints 532 may also include addressing constraints 532 b. Addressing constraints 532b specify that data 210 included in a packet transmitted on the forward link does not exceed the capacity of the packet to address multiple data streams 208 and/or multiple remote stations 206. In some embodiments, addressing constraint 532b may be expressed as:

in some embodiments, the term b in equation 2_iIndicating the number of bits allocated to the ith queue for transport format j. In such embodiments, item B_i，jWhich indicates the data length a given data stream must be regarded as a number of virtual data streams up to this point (for addressing purposes, etc.) for a packet transmitted according to transport format j. Item K_jRepresenting the maximum number of virtual data streams that transport format j can serve at one time.

Alternatively, in some embodiments, term b in equation 2_iMay indicate the bits allocated to all data streams residing at the ith remote station. In such embodiments, item B_i，jIndicating the data length that a given remote station must be treated as a plurality of virtual remote stations (for addressing purposes, etc.) to that end for a packet transmitted according to transport format j. Item K_jRepresenting the maximum number of virtual remote stations that transport format j can serve at one time.

Constraints 532 may also include data availability constraints 532 c. The data availability constraint 532c specifies that no more data 210 is included in a packet than the amount of available data 210. In some embodiments, the data availability constraint 532c may be expressed as:

{(b₁，b₂，…，b_N)|0≤b_i≤Q_i} (3)

term Q_iIndicating the total queue length of the ith data stream. Of course, other constraints 532 in addition to those shown may also be associated with some systems in which embodiments are practiced.

At each transmit opportunity, scheduler 214 computes a metric for data 210 in a particular queue 212. The metric calculated for a particular unit of data represents a reward associated with transmitting that unit of data on the forward link. These metrics are used to determine the transport format used and the data allocation to the various data streams within the transmitted packet.

Fig. 6 illustrates metrics that may be calculated for data 210 in a queue 212. In the illustrated embodiment, the information is presented in the form of a table 634. However, in other embodiments, the information may be arranged in a different manner.

In the illustrated embodiment, scheduler 214 computes a separate one metric for each bit in each queue 212 and for each transmission opportunity. The metric computed for a particular bit will be referred to herein as a "bit metric".

Table 634 includes the bit metrics calculated for the ith queue 212. A similar table 634 may be created for each queue 212 maintained by base station 204 (i.e., for each data flow 208 in system 200). Table 634 may be created and/or updated for each queue 212 at the beginning of a transmission opportunity. Table 634 includes a separate row for each bit in the queue and a separate column for each possible transport format.

For each bit, scheduler 214 computes a bit metric α (t) for each of the various possible transmission formats. Term alpha_i，j，k(t) refers to the bit metric for the kth bit in the queue for the ith data stream at time t with respect to transport format j.

In some embodiments, the bit metric α_i，j，k(t) can be expressed as:

term t_{Arrival，i，k}Is the arrival time of data bit k of data stream i. The time of arrival is the time at which a given bit and the data in queue 212 preceding the given bit are available for transmission. Term t_DROP，i，kIs the deadline of the data bit k of the data stream i. The deadline is the time beyond which the given bit is no longer needed at the remote station 206. Term τ_{Expedite，i，k}Is the acceleration instant of the data bit k of the data stream i. The acceleration time is the time after which the transmission of the data bit at the remote station 206 attains a high priority. The acceleration time of a data bit k is designed to be substantially less than the deadline of that bit and the deadline of all data in queue 212 after that bit. Item T_i，k(t) is the average throughput experienced by the queue 212 containing the given bit. Item T_{desired，i，k}Is the average throughput expected for the queue 212 containing the given bit. Term R_i(t) is the average sustainable data rate/CQI for the channel for the ith data stream, which is based on the DRC/CQI feedback received from that data stream. The term G (x, y) is an increasing function of two arguments x and y. The term U (.) is a unit step function.

Data with a bit metric of 0 may be discarded from the queue 212. Thus, the step function multiplier in equation (4) allows the data to be discarded once its deadline has passed.

A reasonable choice of function F (,) is:

one reasonable choice of function G (x, y) is:

G(x，y)＝K·U(x)+L·(y-Δ)U(y-Δ) (6)

the metrics calculated for the data 210 in the queue 212 are used to determine the transmission metrics for each possible transmission format. A separate transmission metric is calculated for each possible transmission format. This is shown in fig. 7.

In the table 736 shown in fig. 7, there is a single row for each transport format. The first column 738 of the table 736 includes the possible transport formats. A second column 740 of table 736 includes the transmission metrics calculated for the corresponding transmission format. Thus, the transmission metric M_j(t) refers to the transmission metric calculated for transmission format j.

In some embodiments, the transmission metric for transmission format j may be expressed as:

term alpha_i，j，k(t) as discussed above refers to the bit metric for the k bit in the queue for the ith data stream at time t for transport format j. Item P_jIs the penalty associated with transport format j.

Penalty P associated with a given transport format j in a 1xEV-DO system_jDepending on whether the packet is to be used in a multi-user transmission format or a single-user transmission format. If the packet is used in the form of a multi-user transmission format, the packet can be rated P_j＝A*W_iA penalty of the form, wherein W_iIndicating the number of remote stations whose DRC is compatible with the multi-user packet represented by the transmission format, but no data is allocated in the multi-user packet. If the packet is used in the form of a single-user transmission format, no penalty is assessed.

The inner sum k in equation 7 is to cover all bits from the ith data stream that are allocated for transmission in this given transmission example. Thus, the transmission metric M_j(t) depends on the sum of all bit metrics of the data allocated for transmission. For a given transport format j, scheduler 214 allocates bits from queues 212 to avoid violating any of the constraints 532 discussed aboveMake the transmission metric M for the transmission format_j(t) is maximized.

Once the transmission metric M for a given transport format has been calculated_j(t), the scheduler 214 selects the transport format with the best transmission metric. The data that has been allocated for the transmission format is then transmitted on the forward link in a packet that conforms to the transmission format.

Fig. 8 is a flow diagram that illustrates how components in base station 204 operate to implement a method 800 of optimizing allocation of resources to serve different types of data flows in a wireless communication system. The steps of method 800 may be implemented in software, firmware, hardware, or any combination thereof.

The data metric calculation component 215 calculates a bit metric for each bit in each queue and each possible transmission format at step 802. This has been discussed above in connection with fig. 6.

Steps 804 to 810 of the method 800 are performed for each transport format j that can be used in the next transmission opportunity. The data allocation component 217 selects a number of bits at step 804 to maximize the transmission metric without violating the packet capacity constraint 532 a. One exemplary method of performing step 804 will be discussed below.

The constraint verification component 221 determines whether the addressing constraint 532b is violated at step 806. If not, the method 800 proceeds to step 810. If addressing constraint 532b is violated, data allocation component 217 adjusts the selection of bits at step 808 to maximize the transmission metric without violating address constraint 532 b. One exemplary way to perform step 808 will be discussed below.

The transmission metric calculation component 219 calculates a transmission metric for the transmission format in step 810. One exemplary formula for calculating the transmission metric has been provided above in equation 7 and discussed in connection therewith.

The format selection component 223 selects the transport format with the largest transmission metric at step 812. The data selected for the transmission format in steps 804 through 808 is then transmitted on the forward link according to the transmission format.

Fig. 9 illustrates an exemplary method 900 that may be performed by scheduler 214 to select a number of bits to maximize a transmission metric without violating packet capacity constraint 532 a. In other words, FIG. 9 illustrates one exemplary manner in which step 804 of method 800 illustrated in FIG. 8 may be performed. As before, the steps of method 900 may be implemented in software, firmware, hardware, or a combination thereof.

The data distribution component 217 determines at step 902 if there are any queues from which more bits can be selected without violating the packet capacity constraint 532 a. Mathematically, this may be expressed as determining the following subset of data streams:

Ψ＝{1≤i≤N|(b₁，b₂，…，b_i+1，…，b_N)∈C_j} (8)

in formula 8, the term C_iRefers to the packet capacity constraint 532 a. If the set Ψ is empty, the method 900 exits without performing other steps.

The data distribution component 217 determines which of the queues includes the bit having the largest bit metric at step 904. In other words, step 904 involves selecting the data stream having the largest bit metric value α among the data streams in the set Ψ_m，j，bm+1Index m of the data stream.

The data distribution component 217 determines at step 906 how many of these bits from the queue 212 identified at step 904 can be selected without violating the packet capacity constraint 532 a. Mathematically, step 906 can be expressed as determining so that for any data stream index l ≠ m (b)₁，b₂，…，b_m+δ，…，b_N)∈C_jAndthe maximum number δ of the.

The data allocation component 217 updates the bit allocation in step 908. Mathematically, step 908 may be expressed as setting a variable b_m＝b_m+ δ, wherein b_mIs the number of bits allocated from the queue corresponding to data stream m. The method 900 then returns to step 902.

Fig. 10 illustrates an exemplary method 1000 that can be performed by a scheduler to adjust the selection of bits to maximize a transmission metric without violating addressing constraints. In other words, FIG. 10 illustrates one exemplary manner in which step 808 of method 800 illustrated in FIG. 8 may be performed. As before, the steps of method 1000 may be implemented in software, firmware, hardware, or any combination thereof.

Data distribution component 217 identifies queues 212 from which bits can be deselected to satisfy addressing constraints 532b at step 1002. Mathematically, step 1002 may be expressed as determiningIs the smallest integer u_iAnd d_i. Then marking theThe smallest value of (d) is the data stream index m. Then the variable b_mIs set equal to b_m＝b_m-d_m。

The data packet component 217 identifies the queue 212 from which more bits can be selected to optimize the transmission metric while still satisfying the addressing constraint 532b at step 1004. Mathematically, step 1004 may be expressed as counting each numberAccording to the stream index i, determine the order (b)₁，b₂，…，b_i+u_i，…，b_N)∈C_jMaximum number u of_i. In this context, item C_iRefers to addressing constraints 532 b. Then get the expressionMaximized data stream index 1. Variable b_iThen is set as b_i＝b_i+u_i. If l ═ m, then method 1000 ends. Otherwise, the method 1000 is repeated.

Figure 11 is a functional block diagram illustrating one embodiment of a base station 1104. Base station 1104 includes a processor 1102 that controls the operation of base station 1104. The processor 1102 may also be referred to as a CPU. Memory 1105, which may include both Read Only Memory (ROM) and Random Access Memory (RAM), provides instructions and data to the processor 1102. A portion of the memory 1105 may also include non-volatile random access memory (NVRAM).

Base station 1104, which may be implemented in a wireless communication device such as a cellular telephone, may also include a housing 1107 containing a transmitter 1108 and a receiver 1110 to allow transmission and reception of data, such as audio communications, between base station 1104 and a remote location, such as remote station 206. The transmitter 1108 and receiver 1110 may be combined into a transceiver 1112. An antenna 1114 is attached to the chassis 1107 and is electrically coupled to the transceiver 1112. More antennas (not shown) may also be used. The operation of transmitter 1108, receiver 1110 and antenna 1114 is well known in the art and need not be described again here.

The base station 1104 also includes a signal detector 1116 for detecting and quantifying the level of signals received by the transceiver 1112. As is well known in the art, the signal detector 1116 detects signals such as total energy, pilot energy per Pseudonoise (PN) chips, power spectral density, and other signals.

The state changer 1126 of the base station 1104 controls the state of the wireless communication device based on the current state and other signals received by the transceiver 1112 and detected by the signal detector 1116. The wireless communication device is capable of operating in any of several states.

The base station 1104 also includes a system for controlling the wireless communication device and determining which service provider system the wireless communication device should transmit to when it determines that the current service provider system is inappropriate.

The various components of the base station 1104 are coupled together by a bus system 1130, which bus system 1130 may include a power bus, a control signal bus, and a status signal bus in addition to a data bus. However, for clarity, these various buses are illustrated in FIG. 11 as bus system 1130. The base station 1104 may also include a Digital Signal Processor (DSP)1109 used in processing signals. Those skilled in the art will recognize that base station 1104 shown in fig. 11 is a functional block diagram rather than a listing of specific components.

Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

Those of skill would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

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

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the memory may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

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

1. A base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system, comprising:

a transmitter for transmitting forward links to the plurality of remote stations;

a processor; and

a memory in electrical communication with the processor; the memory having stored therein instructions executable to implement a method comprising:

calculating data metrics for data in a plurality of queues, each queue corresponding to a different data flow in the wireless communication system;

using the data metrics to determine a separate one transmission metric for each of a plurality of possible transmission formats, the transmission metric for a given transmission format being dependent on the data metric corresponding to the data allocated for the given transmission format; and

one of the transmission formats having the best transmission metric is selected.

2. The base station of claim 1, wherein the method further comprises transmitting data allocated for the selected transmission format according to the selected transmission format on the forward link.

3. The base station of claim 1, wherein the data allocated for a given transmission format is determined in a manner such that a transmission metric for the given transmission format is optimized in view of one or more constraints.

4. The base station of claim 3, wherein the one or more constraints include a packet capacity constraint specifying that data allocated for the given transport format does not exceed a data capacity of a packet.

5. The base station of claim 4, wherein the packet capacity constraint for a j-th transport format is expressed as:

wherein b is_iRepresents the number of bits allocated from the ith queue, and G_i，jRepresents the maximum number of bits from the ith queue included in the packet in the case where all channel resources are allocated to the ith data stream.

6. The base station of claim 4, wherein the packet capacity constraint for a j-th transport format is expressed as:

wherein b is_iRepresenting the number of bits allocated to each data stream residing on the ith remote station, and G_i，jRepresenting the maximum number of bits included in the packet from each data stream residing on the ith remote station if all channel resources are allocated to each data stream residing on the ith remote station.

7. The base station of claim 3, wherein the one or more constraints include an addressing constraint specifying that data allocated for the given transport format does not exceed an addressing capacity of a packet.

8. The base station of claim 7, wherein the addressing constraints for the plurality of queues are expressed as:

wherein b is_iIndicating the number of bits allocated from the queue for the ith data stream, B_i，jRepresents: for addressing purposes, the ith data stream is regarded as that data length of the plurality of virtual data streams, and K_jIndicating the maximum number of virtual data streams that can be served at one time by the jth transport format.

9. The base station of claim 7, wherein the addressing constraint for a jth transport format is expressed as:

wherein b is_iIndicating the number of bits allocated to each data stream residing on the ith remote station, B_i，jRepresents: for addressing purposes, the ith remote station is therefore considered to be that data length of the plurality of virtual remote stations, and K_jIndicating the number of virtual remote stations that can be served at one time by the jth transport format.

10. The base station of claim 1, wherein calculating the data metric comprises calculating a separate one bit metric for each bit in each of the plurality of queues.

11. The base station of claim 10, wherein the bit metric for the kth bit in the queue for the ith data stream at time i for transport format j is expressed as:

wherein t is_{Arrival，i，k}Is the arrival time of bit k of the ith data stream queue;

t_DROP，i，kis the deadline of bit k of the queue for the ith data stream;

τ_{Expedite，i，k}is the acceleration time of bit k of the queue for the ith data stream;

T_i，k(t) is the average throughput experienced by the queue for the ith data stream containing bit k;

T_{desired，i，k}is the average throughput expected for the queue for the ith data stream containing bit k;

R_i(t) is the average sustainable data rate/CQI for the channel of the ith data stream based on the received DRC/CQI feedback;

g (x, y) is an increasing function of two arguments x and y; and

u (.) is a unit step function.

12. The base station of claim 11, wherein F (T-T)_desiredAnd R) is expressed as:

13. the base station of claim 11, wherein G (x, y) is expressed as:

G(x，y)＝K·U(x)+L·(y-Δ)U(y-Δ)。

14. the base station of claim 1, wherein the transmission metric for a given transmission format is further dependent on a penalty associated with the given transmission format.

15. The base station of claim 1, wherein the transmission metric for transmission format j is expressed as:

wherein alpha is_i，j，k(t) is the bit metric for the kth bit in the queue for the ith data stream for transport format j at time t; and

P_iis the penalty associated with transport format j.

16. The base station of claim 1, wherein the method further comprises selecting data allocated for the given transmission format to optimize the transmission metric without violating a packet capacity constraint.

17. The base station of claim 16, wherein the method further comprises:

determining that an addressing constraint is violated; and

in response thereto, the allocated data is adjusted to optimize the transmission metric without violating neither the addressing constraints nor the packet capacity constraints.

18. The base station of claim 1, wherein the method is performed at each transmit opportunity.

19. The base station of claim 1, wherein the wireless communication system operates in accordance with a 1xEV-DO standard.

20. A base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system, comprising:

means for calculating data metrics for data in a plurality of queues, each queue corresponding to a different data flow in the wireless communication system;

means for determining a separate one of a plurality of possible transmission formats using the data metric, the transmission metric for a given transmission format being dependent on the data metric corresponding to the data allocated for the given transmission format;

means for selecting a transmission format having an optimal transmission metric; and

means for transmitting data allocated for the selected transmission format on the forward link according to the selected transmission format.

21. A method in a base station configured to wirelessly communicate with a plurality of remote stations in a wireless communication system, comprising:

calculating data metrics for data in a plurality of queues, each queue corresponding to a different data flow in the wireless communication system;

using the data metrics to determine a separate one transmission metric for each of a plurality of possible transmission formats, the transmission metric for a given transmission format being dependent on the data metric corresponding to the data allocated for the given transmission format;

selecting a transmission format having an optimal transmission metric; and

the data allocated for the selected transmission format is transmitted on the forward link according to the selected transmission format.