(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY(PCT)
`
`(19) World Intellectual Property Organization
`International Bureau
`
`(43) International Publication Date
`21 November 2002 (21,11,2002)
`
`
`
`PCT
`
`UY OYTUT
`
`(10) International Publication Number
`WO 02/093819 Al
`
`(51) International Patent Classification’:
`
`HO4AL 1/06
`
`(81) Designated States (national); AV, AG, AL, AM, AT, AU,
`AZ, BA, BB, BG, BR, BY, BZ, CA, CH, CN, CO, CR, CU,
`CZ, DE, DK, DM, DZ. EC, EE, ES, FI, GB, GD, GE, GIT,
`(21) International Application Number:=PCT/US02/15920
`GM, HR, HU, TD, TL, IN, TS, JP, KE, KG, KP, KR, KZ, LC,
`LK, LR, LS, Ll, LU, LV, MA, MD, MG, MK, MN, MW,
`MX, MZ, NO, NZ, OM, PH, PL, PT, RO. RU, SD, SE, SG,
`SL SK, SL, TJ, TM, TN, TR, TT, TZ, UA, OG, UZ, VN,
`YU, ZA, ZM, ZW.
`
`(22) International Filing Date;
`
`15 May 2002 (15.05.2002)
`
`(25) Filing Language:
`
`(26) Publication Langunge:
`
`English
`
`English
`
`(30) Priority Data:
`09/859,345
`
`16 May 2001 (16.05.2001)
`
`US
`
`(71) Applicant: QUALCOMM INCORPORATED [US/US]:
`5775 Morehouse Drive, San Diego, CA 92121-1714 (US).
`
`(72) Inventors: WALTON,Jay, R.; 7 Ledgewood Drive, West-
`ford, MA O1886 (US). WALLACE, Mark; 4 Madel Lane,
`Bedtord, MA 01730 (US). HOWARD,Steven, J.; 75 Her-
`ilage Avenue, Ashland, MA 01721 (US).
`
`(74) Agents: O’CONNELL, Robert, J. et al.; Qualcomm In-
`corporated, 5775 Morehouse Drive, San Diego, CA 92121-
`1714 (US).
`
`(84 — Designated States (regional); ARIPO patent (GH, GM,
`KE, LS, MW, MZ, SD, SL. SZ, TZ, UG, ZM. ZW),
`Eurasian patent (AM, AZ, BY, KG, KZ, MD, RU, TJ.'TM),
`European patent (AT, BE, Cll, CY, DE, DK, ES, FI, FR,
`GB, GR, IE, IT, LU, MC, NL, PT, SE, TR), OAPI patent
`(BE, BJ, CF, CG, Cl, CM. GA, GN, GQ, GW, ML, MR,
`NE, SN, TD, TG),
`
`Published:
`with international search report
`before the expiration of the time limit for amending the
`claims and to be republished in the event ofreceipt of
`amendments
`
`[Continued on next page]
`
`(54) Title: METIIOD AND APPARATUS FOR ALLOCATING RESOURCES IN A MULTIPLE-INPUT MULTIPLE-OUTPUT
`(MIMO) COMMUNICATION SYSTEM
`
`(04y
`
`DATA STREAMS
`
`MODULATION
`SYMBOL STREAMS
`
`520K
`
`BITS
`
`
`PILOT DATA
`
`INFORMATION
`
`(57) Abstract: Techniques to schedule downlink data transmission lo a numberof terminals in a wireless communication system. In
`one method, one or more sets of terminals are formed for possible data transmission, with each set including a unique combination
`of one or more terminals and corresponding to a hypothesis to be evaluated. One or more sub-hypotheses may further be formed for
`each hypothesis, with each sub-hypothesis corresponding to specific assignments of a numberoftransmit antennas to the one or more
`terminals in the hypothesis. The performance of each sub-hypothesis is then evaluated, and one of the evaluated sub-hypothesesis
`selected based on their performance. The terminal(s) in the selected sub-hypothesis are then scheduled for data transmission, and
`data is therealter coded, modulated, and transmitted to each scheduled terminal from one or more transmit antenna assigned to the
`terminal.
`
`1
`
`DELL EX. 1009
`
`ANYTT
`WO02/093819Al
`
`DELL EX. 1009
`
`

`

`WO 02/093819 Ad
`
`/IMITIMVUINUNITININNUNCAMONTCh
`
`Far two-leiier codes and olher abbreviations, refer lo the "(Guid-
`ance Notes on Codes and Abbreviations" appearing at the begin-
`ning ofeach regular issue ofthe PCTGazette:
`
`2
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`METHOD ANS APPARATUS FOR ALLOCATING RESOURCES IN A MULTIPLE-INPUT
`MULTIPLE OUTPUT (MIMO) COMMUNICATION SYSTEM
`
`BACKGROUND
`
`Field
`
`[1001]
`
`The present invention relates generally to data communication, and more
`
`specifically to techniquesfor allocating downlink resources in a multiple-input multiple-
`
`output (MIMO) communication system.
`
`Background
`
`(1002] Wireless communication systems are widely deployed to provide various
`
`types of communication such as yoice, data, and so on, for a number of users. These
`
`systems may be based on code division multiple access (CDMA), time division multiple
`
`access (TDMA), frequency division multiple access (FDMA), or some other multiple
`
`access techniques.
`
`[1003]
`
`<A multiple-input multiple-output (MIMO) communication system employs
`
`multiple (Ny) transmit antennas and multiple (Nr) receive antennas for transmission of
`
`multiple independent data streams.
`
`In one common MIMO system implementation, of
`
`the data streams are transmitted to a single terminal at any given time all. However, a
`
`multiple access communication system having a base station with multiple antennas
`
`may also concurrently communicate with a number of terminals.
`
`In this case, the base
`
`station employs a number of antennas and each terminal employs Nr antennas to
`receive one or more of the multiple data streams.
`
`[1004]
`
`The connection between a multiple-antenna base station and a single
`
`multiple-antenna terminal is called a MIMO channel. A MIMO channel formed by
`
`these Nr transmit and Neg receive antennas may be decomposed into Ne independent
`
`channels, with Ne < min {Ny, Nr}. Each of the Ne independent channels is also
`
`referred to as a spatial subchannel of the MIMO channel and corresponds to a
`
`dimension. The MIMO system can provide improved performance (e.g., mcreased
`
`3
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`transmission capacity) if the additional dimensionalities of these subchannels created by
`
`the multiple transmit and receive antennas are utilized.
`
`2
`
`
`
`[1005]|Each MIMO channel between the base station and a terminal typically
`
`experiences different link characteristics and is associated with different transmission
`
`capability, so the spatial subchannels available to each terminal have different effective
`
`capacities. Efficient use of the available downlink resources (and higher throughput)
`
`may be achieved if the Nc available spatial subchannels are effectively allocated such
`that data is transmitted on these subchannels to a “proper” set of terminals in the MIMO
`
`system,
`
`[1006]
`
`There is therefore a need in the art for techniques to allocate downlink
`
`resources in a MIMO system to provide improved system performance.
`
`SUMMARY
`
`[1007]
`
`Aspects of the invention provide techniques to increase the downlink
`
`performance of a wireless communication system.
`In an aspect, data may, be
`transmitted from a base station to one or more terminals using one of a number of
`different operating modes.
`In a MIMO mous, all available downlink data streams are
`allocated to a single terminal that employs multiple antennas (i.e., a MIMO terminal),
`
`In an N-SIMO mode,a single data streamis allocated to each of a numberofdistinct
`
`terminals, with each terminal employing multiple antennas(i.e., SIMO terminals). And
`
`in a mixed-mode, the downlink resources may be allocated to a combination of SIMO
`and MIMOterminals, with both types of terminals being simultaneously supported. By
`transmitting data simultaneously to multiple SIMO terminals, one or more MIMO
`
`terminals, or a combination thereof,
`
`the transmission capacity of the system is
`
`increased,
`
`[1008]
`
`In another aspect, scheduling schemes are provided to schedule data
`
`transmissions to active terminals. A scheduler selects the best operating mode to use
`
`based on various factors such as, for example, the services being requested by the
`terminals. In addition, the scheduler can perform an additional level of optimization by
`selecting a particular set of terminals for simultaneous data transmission and assigning
`the available transmit antennas to the selected terminals such that high system
`
`performance and other requirements are achieved. Several scheduling schemes and
`antenna assignment schemes are provided and described below.
`
`4
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`3
`
`[1009]
`
`A specific embodiment of the invention provides a method for scheduling
`
`downlink data transmission to a number of terminals im a wireless communication
`
`system.
`
`In accordance with the method, one or more sets of terminals are formed for
`
`possible data transmission, with each set including a unique combination of one or more
`
`terminals and corresponding to a hypothesis to be evaluated. One or more sub-
`
`hypotheses may further be formed for each hypothesis, with each sub-hypothesis
`
`corresponding to specific assignments of a number of transmit antennas to the one or
`
`more terminals in the hypothesis. The performance of each sub-hypothesis is then
`
`eyaluated, and one of
`
`the evaluated sub-hypotheses is selected based on their
`
`performance. The terminal(s) in the selected sub-hypothesis are then scheduled for data
`
`transmission, and data is thereafter transmitted to each scheduled terminal from oneor
`
`more transmit antennas assigned to the terminal.
`
`(1010)
`
`Each transmit antenna may be used to transmit an independent data stream.
`
`To achieve high performance,each data stream may be coded and modulated based on a
`
`scheme selected, for example, based on a signal-to-noise-plus-interference (SNR)
`
`estimate for the antenna used to transmit the data stream.
`
`[1011]
`
`Terminals desiring data transmission (i.e., “active” terminals) may be
`
`prioritized based on various metrics and factors. The priority of the active terminals
`
`may then be used to select which terminal(s) to be considered for scheduling and/or to
`
`assign the available transmit antennas to the selected terminals.
`
`(1012)
`
`The invention further provides methods,
`
`systems, and apparatus that
`
`implement various aspects, embodiments, and features of the invention, as described in
`
`further detail below.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[1013]
`
`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 reference characters
`
`identify correspondingly
`
`throughout and wherein:
`
`(1014)
`
`FIG.
`
`1
`
`is
`
`a diagram of
`
`a multiple-input multiple-output
`
`(MIMO)
`
`communication system that may be designed and operated to implement various aspects
`
`and embodiments of the invention;
`
`5
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`4
`
`FIG, 2 is a flow diagram of a process to schedule terminals for data
`[1015]
`transmission, in accordance with an embodimentofthe invention;
`
`[1016]
`
`FIG. 3 is a flow diagram ofa process to assign transmit antennas to receive
`
`antennas using a “max-max” criterion,
`
`in accordance with an embodiment of the
`
`invention;
`
`[1017]_—_—FIG. 4 is a flow diagram for a priority-based scheduling scheme whereby a
`set of one or more highest priority terminals is considered for scheduling, in accordance
`
`with an embodimentof the invention;
`
`[1018]
`
`FIG, 5 is a block diagram ofa base station and a numberofterminals in the
`
`MIMO communication system;
`
`FIG. 6 isa block diagram of an embodimentof the transmit portion of a base
`[1019]
`Station capable of processing data for transmission to the terminals based on the
`
`available CST,
`
`FIG, 7 is a block diagram of an embodiment of the receive portion of a
`
`[1020]
`terminal;
`
`FIGS. 8A and 8B are block diagrams of an embodiment of a channel
`[1021]
`MIMO/data processor and an interference canceller, respectively, of a receive (RX)
`MIMO/data processorat the terminal; and
`[1022]
`FIG. 9 showsthe average throughput for a MIMO communication system
`with four transmit antennas (i.e., Ny = 4) and four receive antennas at each terminal
`
`(i.e., Np = 4) for two different operating modes.
`
`DETAILED DESCRIPTION
`
`(MIMO)
`a diagram of a multiple-input multiple-output
`is
`1
`FIG.
`[1023]
`communication system 100 that may be designed and operated to implement various
`aspects and embodimentsof the invention. MIMO system 100 employs multiple (Ny)
`transmit antennas and multiple (Ng) receive antennas for data transmission. MIMO
`system 100 is effectively formed for a multiple access communication system having a
`base station (BS) 104 that can concurrently communicate with a number of terminals
`(T) 106.
`In this case, base station 104 employs multiple antennas and represents the
`multiple-input (MI) for downlink transmissionsfrom the base station to the terminals,
`[1024]
`_A set of one or more “communicating” terminals 106 collectively represents
`the multiple-output
`(MO)
`for downlink transmissions.
`As used herein,
`a
`
`6
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`5
`
`communicating terminal is one that receives user-specific data from the base station,
`
`and an “active” terminal is one that desires data transmission in an upcomingor future
`
`transmission interval. Active terminals may include terminals that are currently
`
`communicating.
`
`[1025]
`
`MIMOsystem 100 may be designed to implement any numberofstandards
`
`and designs for CDMA, TDMA, FDMA,and other multiple access techniques. The
`
`CDMAstandards include the IS-95, cdma2000, and W-CDMA standards, and the
`
`TDMA standards include the Global System for Mobile Communications (GSM)
`
`standard. These standards are knownin the art and incorporated herein by reference.
`
`[1026]
`
`MIMO system 100 may be operated to transmit data via a number of
`
`transmission channels. Each terminal 106 communicates with base station 104 via a
`
`MIMOchannel. A MIMO channel may be decomposed into Nc independent channels,
`
`with Nc < min {Nr, Nr}. Each of the Nc independent channels is also referred to as a
`
`spatial subchannel of the MIMO channel. For a MIMOsystem notutilizing orthogonal
`
`frequency division modulation (OFDM),
`
`there is typically only one frequency
`
`subchannel and each spatial subchannel maybereferred to as a “transmission channel”,
`
`And for a MIMOsystem utilizing OFDM,each spatial subchannel of each frequency
`
`subchannel may bereferred to as a transmission channel.
`
`[1027]
`
`For
`
`the example shown in FIG.
`
`1, base station 104 concurrently
`
`communicates with terminals 106a through 106d (as indicated by the solid lines) via
`
`multiple antennas available at the base station and multiple antennas available at each
`
`terminal. Terminals 106e through 106h mayreceive pilot references and othersignaling
`
`information from base station 104 (as indicated by the dashed lines), but are not
`
`receiving user-specific data from the basestation.
`
`[1028]
`
`Each terminal 106 in MIMO system 100 employs Nx antennas for reception
`
`of one or more data streams. Generally, the number of antennas at each terminal is
`
`equal to or greater than the number of data streams transmitted by the base station.
`
`However, the terminals in the system need not all be equipped with equal number of
`
`receive antennas.
`
`[1029]
`
`For MIMOsystem 100, the number of antennas at each of the terminals (Nr)
`
`is typically greater than or equal to the number of antennas at the base station (Nz).
`
`In
`
`this case, for the downlink, the numberof spatial subchannels is limited by the number
`
`of transmit antennasat the base station. Each transmit antenna may be used to send an
`
`7
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`6
`
`independent data stream that may be coded and modulated based on a scheme supported
`
`by the spatial subchannel associated with the MIMO channel between the base station
`
`and the selected terminal.
`
`[1030]
`
`Aspects of the invention provide techniques to increase the performance of a
`
`wireless communication system. These techniques may be advantageously used to
`
`increase the downlink capacity of a multiple access cellular system. These techniques
`mayalso be used in combination with other multiple access techniques.
`[1031]
`In an aspect, data may be transmitted from a base station to one or more
`
`terminals using one of a numberofdifferent operating modes.
`
`In a MIMO mode,the
`
`available downlink resources are allocated to a single terminal (i.e., a MIMO terminal).
`
`In an N-SIMO mode, the downlink resources are allocated to a number of distinct
`
`terminals, with each terminal demodulating a single data stream (i.e., SIMO terminals).
`
`And in a mixed-mode, the downlink resources may be allocated to a combination of
`
`SIMO and MIMO terminals, with both types of terminals being simultaneously
`
`supported on the same channel, which may be a time slot, a code channel, a frequency
`
`subchannel, and so on.
`
`By transmitting data simultaneously to multiple SIMO
`
`terminals, one or more MIMOterminals, or a combination thereof, the transmission
`
`capacity of the system is increased.
`
`[1032]
`
`In another aspect, scheduling schemes are provided to schedule data
`
`transmissions to active terminals. A scheduler selects the best operating mode to use
`
`based on various factors such as, for example, the services being requested by the
`
`terminals. In addition, the scheduler can perform an additional level of optimization by
`
`selecting a particular set of terminals for simultaneous data transmission and assigning
`
`the available ‘transmit antennas to the selected terminals such that high system
`
`performance and other requirements are achieved. Several scheduling schemes and
`
`antenna assignment schemesare described in further detail below.
`
`[1033]|With MIMO,multiple independent data streams may be transmitted from the
`
`base station via multiple transmit antennas to one or more scheduled terminals.
`
`If the
`
`propagation environment has
`
`sufficient
`
`scattering, MIMO receiver processing
`
`techniques may be used at
`
`the
`
`terminals
`
`to efficiently exploit
`
`the
`
`spatial
`
`dimensionalities of the MIMO channel
`
`to increase transmission capacity. MIMO
`
`receiver processing techniques may be used when the base station is communicating
`
`with multiple terminals simultaneously. From the terminal’s perspective, the same
`
`8
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`7
`
`receiver processing techniques may be used to process Ny different signals intended for
`
`that terminal (e.g., a single MIMO terminal) or just one of the Nr signals (.e., SIMO
`
`terminals).
`
`[1034]
`
`As shown in FIG, 1, the terminals may be randomly distributed in the base
`
`station’s coverage area (or “cell”) or may be co-located. For a wireless communication
`
`system, the link characteristics typically vary over time due to a numberof factors such
`
`as fading and multipath. At a particular instant in time, the channel response between
`
`the base station’s array of Nr transmit antennas and the Ne receive antennasfor a single
`
`terminal may be characterized by a matrix H whose elements are composed of
`
`independent Gaussian random variables, as follows:
`
`H =[h, h,... hy J=
`
`| Ih;
`hy
`M
`Thx,
`
`hh, A
`Pry.
`Mh, A
`Tyg
`M
`M
`hon, A Pye.
`
`Eq (1)
`
`where H is the channel response matrix for the terminal, and /;; is the coupling between
`
`the base station’s i-th transmit antenna and the terminal’s j-th receive antenna.
`
`[1035]
`
`As shown in equation (1), the channel estimates for each terminal may be
`
`represented with a matrix having N,N, elements corresponding to the number of
`
`transmit antennas at the base station and the number of receive antennasat the terminal.
`
`Each element of the matrix H describes the response for a respective transmit-receive
`
`antenna pair between the base station and one terminal. For simplicity, equation (1)
`
`describes a channel characterization based on a flat fading channel model (i.e., one
`
`complex value for the entire system bandwidth).
`
`In an actual operating environment,
`
`the channel may be frequency selective (i.e., the channel response varies across the
`
`system bandwidth) and a more detailed channel characterization maybe used(e.g., each
`
`element of the matrix H may include a set of values for different frequency subchannels
`
`or time delays).
`
`[1036]
`
`The active terminals in the MIMO system periodically estimate the channel
`
`response for each transmit-receive antenna pair.
`
`The channel estimates may be
`
`facilitated in a number of ways such as, for example, with the use ofpilot and/or data
`
`decision directed techniques known in the art. The channel estimates may comprise the
`
`complex-value channel response estimate for each transmit-receive antenna pair, as
`
`9
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`8
`
`described above in equation (1).. The channel estimates give information on the
`
`transmission characteristics of each of the spatial subchannels, i.e., what data rate is
`
`supportable on each subchannel with a given set of transmission parameters. The
`
`information given by the channel estimates may be distilled into a post-processed
`
`signal-to-noise-plus-interference ratio (SNR) estimate for each spatial
`
`subchannel
`
`(described below), or some otherstatistic that allows the transmitter to select the proper
`
`transmission parameters for that spatial subchannel.
`
`Typically,
`
`this process of
`
`derivation of the essential statistic reduces the amount of data required to characterize a
`
`channel.
`
`In either case,
`
`this information represents one form of channel state
`
`information (CSI) that may be reported to the base station. Other forms of CSI may
`
`also be reported and are described below.
`
`[1037]
`
`The aggregate CSI received from the collection of terminals may be used to
`
`(1) select a “best” set of one or more terminals for data transmission, (2) assign the
`
`available transmit antennas to the selected terminals in the set, and (3) select the proper
`
`coding and modulation scheme for each transmit antenna. With the available CSI,
`
`various scheduling schemes may be designed to maximize the downlink performance by
`
`evaluating which specific combination of terminals and antenna assignments provide
`
`the best system performance (e.g.,
`
`the highest
`
`throughput) subject to any system
`
`constraints and requirements. By exploiting the spatial
`
`(and possibly frequency)
`
`“signatures” of the individual active terminals (i.e., their channel estimates), the average
`
`downlink throughput can be increased.
`
`[1038]
`
`The terminals may be scheduled for data transmission based on various
`
`factors. Oneset of factors may relate to system constraints and requirements such as the
`
`desired quality of service (QoS), maximum latency, average data rate, and so on. Some
`
`or all of these factors may need to be satisfied on a per terminal basis (i.e., for each
`
`terminal) in a multiple access communication system. Anotherset of factors may relate
`
`to system performance, which may be quantified by an average system throughputrate
`
`or some other indications of performance. These various factors are described in further
`
`detail below.
`
`[1039]
`
`The scheduling schemes can be designed to select the best set of terminals
`
`for simultaneous data transmission on the available transmission channels such that
`
`system performance is maximized while conforming to the system constraints and
`requirements. For simplicity, various aspects of the invention are described below for a
`
`10
`
`10
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`9
`
`MIMO system without OFDM in which one independent data stream may be
`
`transmitted by the base station from each transmit antenna.
`
`In this case, (up to) Nr
`
`independent data streams may be simultaneously transmitted by the base station from
`
`Ny transmit antennas and targeted to one or more terminals, each equipped with Nr
`
`receive antennas(i.e., N. x N, MIMO), where Nr 2 Nr.
`
`
`
`(1040)_—“Por simplicity, the numberof receive antennas is assumed to be equal to the
`
`number of transmit antennas(i.e., Np = Nr) for much of the description below. Thisis
`
`not a necessary condition sinceall of the analysis applies for the case where Np = Nv.
`
`Scheduling of data transmission on the downlink comprises two parts: (1)
`[1041]
`selection of one or more sets of terminals for evaluation, and (2) assignment of the
`
`available transmit antennas to the terminals in each set. All or only a subset of the
`
`active terminals may be considered for scheduling, and these terminals may be
`
`combined to form one or more sets (i.e., hypotheses) to be evaluated. For each
`
`hypothesis, the available transmit antennas can be assigned to the terminals in the
`
`hypothesis based on any one of a number of antenna assignment schemes. The
`
`terminals in the best hypothesis may then be scheduled for data transmission in an
`
`upcoming interval. The flexibility in both selecting the best set of terminals for data
`
`transmission and the assignment of the transmitted antennas to the selected terminals
`
`allows the scheduler to optimize performance by exploiting multi-user diversity
`
`environment.
`
`[1042]
`
`In order to determine the “optimum”transmission to a set of terminals, the
`
`SNRsor some other sufficient statistics are provided for each terminal and each spatial
`
`subchannel. If the statistic is the SNR, then for each set of terminals to be evaluated for
`
`data transmission in an upcoming transmission interval, a hypothesis matrix I of “post-
`
`processed” SNRs(defined below) for this terminal set may be expressedas:
`
`
`
`Na=oY SOA Yel
`
`r=
`
`feo A a
`ye
`Vin, Vane A Yreity
`
`Eq (2)
`
`where ¥,,
`
`is the post-processed SNR for a data stream (hypothetically) transmitted
`
`from the 7-th transmit antennato the j-th terminal,
`
`11
`
`11
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`10
`
`[1043]
`
`In the N-SIMO mode, the Ny rows in the hypothesis matrix I correspond to
`
`Ny vectors of SNRs from Nr different terminals.
`
`In this mode, each row in the
`
`hypothesis matrix I gives the SNR of each transmit data stream for one terminal. And
`
`in the mixed-mode,for a particular MIMOterminal designated to receive two or more
`
`data streams, that terminal’s vector of SNRs may be replicated such that the vector
`
`appears in as many rowsas the numberof data streams to be transmitted for the terminal
`
`(i.e., one row per data stream). Alternatively, one row in the hypothesis matrix I° may
`
`be used for each SIMO or MIMOterminal, and the scheduler may be designed to mark
`
`and evaluate these different types of terminals accordingly.
`
`[1044]
`
`At each terminal
`
`in the set
`
`to be evaluated,
`
`the Ny (hypothetically)
`
`transmitted data streams are received by the terminal’s Np receive antennas, and the Nr
`
`received signals can be processed using spatial or space-time equalization to separate
`
`out the Ny transmitted data streams, as described below. The SNR of a post-processed
`
`data stream (i.e., after equalization) may be estimated and comprises the post-processed
`
`SNR for that data stream. For each terminal, a set of Nr post-processed SNRs maybe
`
`provided for the Nr data streams that may be received bythat terminal.
`
`[1045]
`
`If a successive equalization and interference cancellation (or “successive
`
`cancellation”) receiver processing technique is used at a terminal to process the received
`signals, then the post-processed SNR achieved at the terminal for each transmitted data
`stream depends on the order in which the transmitted data streams are detected (i.e.,
`
`demodulated and decoded) to recover the transmitted data, as described below.
`
`In this
`
`case, a number of sets of SNRs may be provided for each terminal for a number of
`
`possible detection orderings. Multiple hypothesis matrices may then be formed and
`evaluated to determine which specific combination of terminals and detection ordering
`
`provides the best system performance.
`
`[1046]
`
`In any case, each hypothesis matrix I includes the post-processed SNRsfor
`
`a specific set of terminals (i.e., hypothesis) to be evaluated. These post-processed SNRs
`
`represent the SNRsachievable by the terminals and are used to evaluate the hypothesis.
`
`[1047]
`
`FIG. 2 is a flow diagram of a process 200 to schedule terminals for data
`
`transmission, in accordance with an embodiment of the invention. For clarity, the
`
`overall process is first described and the details for some of the steps in the process are
`
`described subsequently.
`
`12
`
`12
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`Il
`
`[1048]
`
`Initially, metrics to be used to select the best set of terminals for data
`
`transmission are initialized, at step 212. Various performance metrics may be used to
`
`evaluate the terminal sets and some of these are described in further detail below. For
`
`example, a performance metric that maximizes system throughput may be used.
`
`[1049]
`
`A (new) set of one or more active terminals is then selected from amongall
`
`active terminals considered for scheduling, at step 214. This set of terminals forms a
`
`hypothesis to be evaluated. Various techniques may be used to limit the number of
`
`active terminals to be considered for scheduling, which then reduces the number of
`
`hypotheses to be evaluated, as described below. For each terminal in the hypothesis, the
`
`SNR vector(e.g., i= [14.59%a,jVm_7] ) is retrieved, at step 216. The SNR vectors for
`
`all terminals in the hypothesis form the hypothesis matrix T shown in equation (2).
`
`[1050]
`
`For each hypothesis matrix [ of Nr transmit antennas and Nr terminals,
`
`there are Ny factorial possible combinations of assignments of transmit antennas. to
`
`(new) combination :of:
`Thus, a particular
`sub-hypotheses).
`terminals (i.e., Ny!
`antenna/terminal assignments is selected for evaluation, at step 218. This particular
`
`combination of antenna/terminal assignments forms a sub-hypothesis to be evaluated.
`
`{1051]|The sub-hypothesis is then evaluated and the performance metric (e.g., the
`
`system throughput) corresponding to this sub-hypothesis is determined (e.g., based on
`
`the SNRsfor the sub-hypothesis), at step 220. This performance metric is then used to
`
`update the performance metric corresponding to the current best sub-hypothesis, at step
`
`222. Specifically, if the performance metric for this sub-hypothesis is better than that of
`
`the current best sub-hypothesis, then this sub-hypothesis becomes the new best sub-
`
`hypothesis, and the performance metric and other terminal metrics corresponding to this
`
`sub-hypothesis are saved. The performance and terminal metrics are described below.
`
`[1052]
`
`A determination is then made whether or not all sub-hypotheses for the
`
`current hypothesis have been evaluated, at step 224. If all sub-hypotheses have not been
`
`evaluated, the process retums to step 218 and a different and not yet evaluated
`
`combination of antenna/terminal assignments is selected for evaluation. Steps 218
`
`through 224 are repeated for each sub-hypothesis to be evaluated.
`
`[1053]
`
`If all sub-hypotheses for a particular hypothesis have been evaluated, at step
`
`224, a determination is then made whether or notall hypotheses have been considered,
`
`at step 226. If all hypotheses have not been considered, then the process returns to step
`
`13
`
`13
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`12
`
`214 and a different and not yet considered set of terminals is selected for evaluation.
`
`Steps 214 through 226 are repeated for each hypothesis to be considered.
`
`[1054]
`
`If all hypotheses have been considered at step 226, then the specific set of
`
`terminals scheduled for data transmission in the upcoming transmission interval and
`
`their assigned transmit antennas are known. The post-processed SNRs corresponding to
`
`this set of terminals and antenna assignments may be used to select the proper coding
`
`and modulation schemes for the data streams to be transmitted to the terminals. The
`
`scheduled transmission interval, antenna assignments, coding and modulation schemes,
`
`other information, or any combination thereof,may be conveyed to the scheduled
`
`terminals (e.g., via a control channel), at step 228. Alternatively, the terminals may
`
`perform “blind” detection and attemptto detectall transmitted data streams to determine
`
`which ones,if any, of the data streams are intended for them.
`
`[1055]
`
`If the scheduling scheme requires other system and terminal metrics to be
`
`maintained (e.g. the average data rate over the past K transmission intervals, latency for
`data jeananniasion., and so on), then these metrics are updated, at step 230. The terminal
`metrics may be used to evaluate the performance of the individual terminals, and are
`described below. The scheduling is typically performed for each transmission interval.
`
`[1056]
`
`For
`
`a given hypothesis matrix IT,
`
`the
`
`scheduler evaluates various
`
`combinations of transmit antenna and terminal pairings (i.e., sub-hypotheses)
`
`to
`
`determine the best assignments for the hypothesis. Various assignment schemes may be
`
`used to assign transmit antennas to the terminals to achieve various system goals such as
`
`fairness, maximize performance, and so on.
`
`[1057]
`
`In one antenna assignment scheme,all possible sub-hypotheses are evaluated
`
`based on a particular performance metric and the sub-hypothesis with the best
`
`performance metric is selected. For each hypothesis matrix T, there are Ny factorial
`
`(i.e., Nr!) possible sub-hypotheses that may be evaluated.
`
`Each sub-hypothesis
`
`corresponds to a specific assignment of each transmit antenna to a respective terminal.
`
`Each sub-hypothesis may thus be represented with a vector of post-processed SNRs,
`
`which may be expressed as:
`
`Ysub—hyp 7 VuarYaroTrier) ,
`
`14
`
`14
`
`

`

`WO 02/093819
`
`PCT/US02/15920
`
`13
`
`where y;, is the post-processed SNR for the i-th transmit antennato the j-th terminal,
`
`and the subscripts {a, b,
`
`... and r} identify the specific terminals in the transmit
`
`ante