US 6,662,024 B2
`(10) Patent No.:
`a2) United States Patent
`Walton et al.
`(45) Date of Patent:
`Dec. 9, 2003
`
`
`US006662024B2
`
`FOREIGN PATENT DOCUMENTS
`(54) METHOD AND APPARATUS FOR
`ALLOCATING DOWNLINK RESOURCESIN
`EP 884862 Al=12/1998
`
`A MULTIPLE-INPUT MULTIPLE-OUTPUT
`EP
`966125 Al
`12/1999
`(MIMO) COMMUNICATION SYSTEM
`
`OTHER PUBLICATIONS
`
`(75)
`
`Inventors: Jay R. Walton, Westford, MA (US);
`Mark Wallace, Bedford, MA (US);
`Steven J. Howard ‘Ashland MA (US)
`,
`,
`(73) Assignee: Qualcomm Incorporated, San Diego,
`CA (US)
`
`(*) Notice:
`
`Subject to any disclaimer,the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 143 days.
`
`A. Wittneben: “Analysis and Comparison of optimal Pre-
`dictive Transmitter Selection and Combining Diversity for
`DECT” Global Telecommunications Conference, 1995.
`IEEE Singapore 12-17 Nov. 1995; New York, USA, Nov.
`13, 1995, pp. 1527-1531.
`A.Hottinen et al.: “Transmit Diversity by Antenna Selection
`in CDMA Downlink” IEEE International Symposium on
`Spread Spectrum Techniques and Applications, vol. 3, Sep.
`2, 1998, pp. 767-770.
`
`* cited by examiner
`(21) Appl. No.: 09/859,345
`Primary Examiner—Nguyen T. Vo
`(22)
`Filed:
`May16, 2001
`.
`>
`(74) Attorney, Agent, or Firm—Philip Wadsworth; Kent
`Baker, Thomas R. Rouse
`(65)
`Prior Publication Data
`(57)
`ABSTRACT
`US 2003/0087673 Al May 8, 2003
`Techniques to schedule downlink data transmission to a
`(S51)
`Int. C17eee HO04B 1/38; HO4M 1/00
`
`
`
`(52)US.C1.cececneeeneeecscteneseneenees 455/562; 455/452 numberof terminals in a wireless communication system. In
`(58) Field of Search ..........cccccccceeee 455/561, 562,|one method, one or more sets of terminals are formed for
`455/69, 101, 103, 102, 562.1, 450, 451,
`possible data transmission, with each set including a unique
`452.1, 452.2, 509, 513; 375/347, 349
`combination of one 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
`numberof transmit 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-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 coded, modulated, and
`transmitted to each scheduled terminal from one or more
`transmit antennas assigned to the terminal
`8
`,
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,056,109 A
`10/1991 Gilhousenetal.
`5,265,119 A
`11/1993 Gilhousenetal.
`5,628,052 A *
`5/1997 DeSantis et al. .......... 455/562
`5,799,005 A
`8/1998 Soliman
`5,903,554 A .
`5/1999 Saints
`.......... 455/562
`5,933,787 A
`8/1999 Gilhousen et al.
`6,097,972 A
`8/2000 Saints etal.
`6,127,971 A * 10/2000 Calderbanketal. ........ 342/368
`6,131,016 A * 10/2000 Greenstein et al.
`........... 455/69
`6,212,242 B1
`4/2001 Smith et al.
`
`49 Claims, 9 Drawing Sheets
`
`ra
`
`
`
`212
`
`tg
`
`
`
`INITIALIZE, METRICS,
`
`————
`
`
`¥
`RETRIEVE CTLANNEL ESTIMATES FOR EACH
`
` RECEIVE ANTENNAIN THE HYPOTHESIS
`
`——eEe
`SELECT (NEW) ANTENNAASSIGNMENTS:
`
`(SUB-HYPOTHFSTS) FOR THE SELECTED TERMINALS,
`
`
`¥
`EVALUATE THE SUB-HYPOTHESIS AND
`DETERMINEITS PERFORMANCE METRIC
`
`
`+
`UPDATE BEST PERFORMANCE METRIC.
`
`TO REFLECT CURRENT SUB-HYPOTHESIS,
`
`
`
`
`ALL SUB-HYPOTHESIS
`EVALUATED?
`
`ALL SUL-ETYPOTITESTS
`CONSIDERED+
`
`SAVE RESULTS FOR REST SUB-HYPOTHESIS
`AND COMMUNICATE SCIIEDULE AND DATA
`RATES TO TERMINALS IN THE SUB-HYPOTHESIS,
`UPDATE SYSTEM AND TERMINAL METRICS
`EXD
`
`
`
`
`
`
`
`1
`
`AMAZON.COM,INC.,et al.
`
`EXHIBIT 1012
`
`1
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 1 of 9
`
`US 6,662,024 B2
`
`00T
`
`I‘DId
`
`2
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 2 of 9
`
`US 6,662,024 B2
`
`START
`
`INITIALIZE METRICS
`
`200
`
`YY
`
`SELECT A (NEW)SET OF
`TERMINALS TO FORM A HYPOTHESIS
`
`RETRIEVE CHANNEL ESTIMATES FOR EACH
`RECEIVE ANTENNAIN THE HYPOTHESIS
`
`SELECT (NEW) ANTENNA ASSIGNMENTS
`(SUB-HYPOTHESIS) FOR THE SELECTED TERMINALS
`
`EVALUATE THE SUB-HYPOTHESIS AND
`DETERMINE ITS PERFORMANCE METRIC
`
`UPDATE BEST PERFORMANCE METRIC
`TO REFLECT CURRENT SUB-HYPOTHESIS
`
`
`
`ALL SUB-HYPOTHESIS
`EVALUATED ?
`
`YES
`
`NO
`
`226
`
`NO
`
`
`
`ALL SUB-HYPOTHESIS
`CONSIDERED?
`
`YES
`
`
`SAVE RESULTS FOR BEST SUB-HYPOTHESIS
`AND COMMUNICATE SCHEDULE AND DATA
`
`RATES TO TERMINALSIN THE SUB-HYPOTHESIS
`
`212
`
`214
`
`216
`
`218
`
`220
`
`222
`
`228
`
`230
`
`UPDATE SYSTEM AND TERMINAL METRICS
`
`END
`
`FIG. 2
`
`3
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 3 of 9
`
`US 6,662,024 B2
`
`START
`
`300
`
`THE TRANSMIT ANTENNA/TERMINAL
`
`PAIR WITH THE BEST SNR
`
`ASSIGN THE TRANSMIT
`
`ANTENNAIN THE PAIR TO
`
`THE TERMINALIN THE PAIR
`
`wv
`
`
`
`DETERMINE THE BEST SNR IN
`THE MATRIX T AND IDENTIFY
`
`
`
`
`
`REMOVETHE ASSIGNED
`TRANSMIT ANTENNA AND
`
`TERMINAL FROM THE MATRIX [
`ASSIGNED?
`
`
`
`TRANSMIT ANTENNAS
`
`PROVIDE ANTENNA ASSIGNMENTS
`
`320
`
`
`
`FIG, 3
`
`4
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 4 of 9
`
`US 6,662,024 B2
`
`400
`
`wv
`
`412
`
`414
`
`START
`
`SELECT Ny HIGHEST
`PRIORITY TERMINALS
`
`RETRIEVE CHANNEL ESTIMATES
`FOR THE SELECTED TERMINALS
`
`ASSIGN Nt TRANSMIT ANTENNAS
`TO THE SELECTED TERMINALS BASED
`
`416
`
`418
`
`ON THE CHANNEL ESTIMATES
`ANTENNA ASSIGNMENTS
`
`DETERMINE DATA RATES AND CODING
`AND MODULATION SCHEMES FOR THE
`SELECTED TERMINALS BASED ON THE
`
`420
`
`UPDATE SYSTEM AND
`TERMINAL METRICS
`
`FIG. 4
`
`5
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 5 of 9
`
`US 6,662,024 B2
`
`00s
`
`¢‘OIA
`
` N90 vo01
`wOSsdo0UdSwOSSdoOUdiqdOUNOs
`OWAXLVIVOXLVIVd
`
`ISOdaLYOdda/
`
`YATNGAHOS
`
`Mot
`
`cls
`
`OJANI ONTTINGHHOS
`
`6
`
`
`
`

`

`Dec. 9, 2003
`
`Sheet 6 of 9
`
`US 6,662,024 B2
`
`
`
`Iso(ON)Iso
`
`ONIddVW~UAAVATUALNI~TOAWASTANNVHOBETOONS
`
`U.S. Patent 9DI
`
`rotSWVAULSTOMWASatkVLvd\NOLLV1NGOW
`
`
`
`
`VLVGLOMd
`
`NOLLVAQOANI
`
`sLId
`
`7
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 7 of 9
`
`US 6,662,024 B2
`
`
`
`106X
`
`CSI (1)
`
`DECODED DATA
`
`
`
`STREAM(1)
`
`
`
`740
`
`CONTROLLER
`
`
`
`
`
`CSI (2)
`DECODED DATA
`
`STREAM (2) CSI (No)
`
`DECODED DATA
`
`STREAM (Nc)
`
`8
`
`

`

`U.S. Patent
`
`XOZL
`
`w
`
`0z8818918rIgO18
`
`Dec. 9, 2003
`
`
`aqqaoogaWad/IVLLVdS
`WVRILSWOSSaOOUd
`
`VLVdwadoogadMAAVATYSLNINONAWLL-dOVdSyl
`
`
`Sheet 8 of 9
`
`US 6,662,024 B2
`
`XO0CL
`
`Ww
`
`X0T90€8
`
`
`NeWy7SaYOSsdoO0ddYOLVTIAWISyl
`
`
`agaooaaVIVdTANNVHOTHNNVHO
`
`d8“OIAiI+
`
`9
`
`
`
`

`

`U.S. Patent
`
`Dec. 9, 2003
`
`Sheet 9 of 9
`
`US 6,662,024 B2
`
`
`
`ee
`
`\
`
`
`
`XPUI-XBUW‘OWISXlp>—Ge
`
`OWIW$Xp—O—[----~401
`
`(aP)UNS
`
`6‘DIA
`
`(zH/sdq)9LONdHONOYHL
`
`ADVUAAV
`
`10
`
`10
`
`

`

`US 6,662,024 B2
`
`1
`METHOD AND APPARATUS FOR
`ALLOCATING DOWNLINK RESOURCESIN
`A MULTIPLE-INPUT MULTIPLE-OUTPUT
`(MIMO) COMMUNICATION SYSTEM
`
`BACKGROUND
`
`1. Field
`
`invention relates generally to data
`The present
`communication, and more specifically to techniques for
`allocating downlink resources in a multiple-input multiple-
`output (MIMO) communication system.
`2. Background
`Wireless communication systems are widely deployed to
`provide various types of communication such as voice, data,
`and so on, for a numberof users. These systems may be
`based on code division multiple access (CDMA),
`time
`division multiple access (TDMA), frequency division mul-
`tiple access (FDMA), or some other multiple access tech-
`niques.
`A multiple-input multiple-output (MIMO) communica-
`tion system employs multiple (N;) transmit antennas and
`multiple (N,) receive antennas for transmission of multiple
`independent data streams. In one common MIMO system
`implementation, the data streams are transmitted to a single
`terminal at any given time. 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 N, antennas to
`receive one or more of the multiple data streams.
`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 N; transmit and
`Np receive antennas may be decomposed into N¢ indepen-
`dent channels, with N-=min {N,, Nz}. Each of the No
`independent channels is also referred to as a spatial sub-
`channel of the MIMO channel and corresponds to a dimen-
`sion. The MIMO system can provide improved performance
`(e.g.,
`increased transmission capacity)
`if the additional
`dimensionalities of these subchannels created by the mul-
`tiple transmit and receive antennas are utilized.
`Each MIMOchannel 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 N¢ available spatial subchannels are effec-
`tively allocated such that data is transmitted on these sub-
`channels to a “proper” set of terminals in the MIMO system.
`There is therefore a need in the art for techniques to
`allocate downlink resources in a MIMOsystem to provide
`improved system performance.
`SUMMARY
`
`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 mode,all available
`downlink data streamsare allocated to a single terminal that
`employs multiple antennas (i.e., a MIMOterminal). In an
`N-SIMO mode, a single data stream is allocated to each of
`a numberof distinct terminals, with each terminal employ-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`ing multiple antennas (ie., 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. By transmit-
`ting data simultaneously to multiple SIMO terminals, one or
`more MIMO terminals, or a combination thereof, the trans-
`mission capacity of the system is increased.
`In another aspect, scheduling schemes are provided to
`schedule data transmissionsto 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 assign-
`ing the available transmit antennasto 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.
`A specific embodiment of the invention provides a
`method for scheduling downlink data transmission to a
`numberof terminals in 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 spe-
`cific assignments of a numberof transmit antennasto the one
`or more terminals in the hypothesis. The performance of
`each sub-hypothesis is then evaluated, and one of the
`evaluated sub-hypotheses is selected based on their perfor-
`mance. The terminal(s) in the selected sub-hypothesis are
`then scheduled for data transmission, and data is thereafter
`transmitted to each scheduled terminal from one or more
`transmit antennas assigned to the terminal.
`Each transmit antenna may be used to transmit an inde-
`pendentdata 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.
`
`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.
`
`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
`
`The features, nature, and advantages of the present inven-
`tion will become more apparent from the detailed descrip-
`tion set forth below when taken in conjunction with the
`drawings in which like reference characters identify corre-
`spondingly throughout and wherein:
`FIG. 1 is a diagram of a multiple-input multiple-output
`(MIMO) communication system that may be designed and
`operated to implementvarious aspects and embodiments of
`the invention;
`FIG. 2 is a flow diagram ofa process to schedule terminals
`for data transmission, in accordance with an embodiment of
`the invention;
`FIG. 3 is a flow diagram of a process to assign transmit
`antennas to receive antennas using a “max—max”criterion,
`in accordance with an embodimentof the invention;
`
`11
`
`11
`
`

`

`US 6,662,024 B2
`
`3
`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 embodiment of the invention;
`FIG. 5 is a block diagram of a base station and a number
`of terminals in the MIMO communication system;
`FIG. 6 is a block diagram of an embodiment of the
`transmit portion of a base station capable of processing data
`for transmission to the terminals based on the available CSI;
`FIG. 7 is a block diagram of an embodimentof the receive
`portion of a terminal;
`FIGS. 8A and 8B are block diagrams of an embodiment
`of a channel MIMO/data processor and an interference
`canceller, respectively, of a receive (RX) MIMO/data pro-
`cessor at the terminal; and
`FIG. 9 shows the average throughput for a MIMO com-
`munication system with four transmit antennas(i.e., N;=4)
`and four receive antennas at each terminal (i.e., N,=4) for
`two different operating modes.
`
`DETAILED DESCRIPTION
`
`FIG. 1 is a diagram of a multiple-input multiple-output
`(MIMO) communication system 100 that may be designed
`and operated to implementvarious aspects and embodiments
`of the invention. MIMO system 100 employs multiple (N;)
`transmit antennas and multiple (N,) receive antennas for
`data transmission. MIMOsystem 100 is effectively formed
`for a multiple access communication system having a base
`station (BS) 104 that can concurrently communicate with a
`numberof terminals (T) 106. In this case, base station 104
`employs multiple antennas and represents the multiple-input
`(MD)for downlink transmissions from the base station to the
`terminals.
`
`A set of one or more “communicating” terminals 106
`collectively represents the multiple-output (MO) for down-
`link transmissions. As used herein, a communicating termi-
`nal 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.
`MIMOsystem 100 may be designed to implement any
`number of standards and designs for COMA, TDMA,
`FDMA,and other multiple access techniques. The CDMA
`standards include the IS-95, cdma2000, and W-CDMA
`standards, and the TDMAstandards include the Global
`System for Mobile Communications (GSM)standard. These
`standards are known in the art and incorporated herein by
`reference.
`
`MIMOsystem 100 may be operated to transmit data via
`a number of transmission channels. Each terminal 106
`communicates with base station 104 via a MIMO channel.
`
`A MIMO channel may be decomposed into N; independent
`channels, with N.Smin {N,, Nz}. Each of the N, inde-
`pendent channels is also referred to as a spatial subchannel
`of the MIMO channel. For a MIMO system not utilizing
`orthogonal frequency division modulation (OFDM),thereis
`typically only one frequency subchannel and each spatial
`subchannel maybe referred to as a “transmission channel”.
`And for a MIMO system utilizing OFDM, each spatial
`subchannelof each frequency subchannel may bereferred to
`as a transmission channel.
`
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`available at the base station and multiple antennas available
`at each terminal. Terminals 106e through 106/ may receive
`pilot references and other signaling information from base
`station 104 (as indicated by the dashed lines), but are not
`receiving user-specific data from the base station.
`Each terminal 106 in MIMOsystem 100 employs N;,
`antennas for reception of one or more data streams.
`Generally, the number of antennas at each terminal is equal
`to or greater than the numberof data streams transmitted by
`the base station. However, the terminals in the system need
`not all be equipped with equal numberof receive antennas.
`For MIMOsystem 100, the numberof antennasat each of
`the terminals (N,) is typically greater than or equal to the
`numberof antennasat the base station (N;). In this case, for
`the downlink, the numberof spatial subchannels is limited
`by the numberof transmit antennasat the base station. Each
`transmit antenna may be used to send an independent data
`stream that may be coded and modulated based on a scheme
`supported by the spatial subchannel associated with the
`MIMOchannel between the base station and the selected
`terminal.
`
`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 may also be used in combination with
`other multiple access techniques.
`In an aspect, data may be transmitted from a basestation
`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 maybea timeslot, a
`code channel, a frequency subchannel, and so on. Bytrans-
`mitting data simultaneously to multiple SIMO terminals,
`one or more MIMO terminals, or a combination thereof, the
`transmission capacity of the system is increased.
`In another aspect, scheduling schemes are provided to
`schedule data transmissionsto 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 assign-
`ing the available transmit antennasto the selected terminals
`such that high system performance and other requirements
`are achieved. Several scheduling schemes and antenna
`assignment schemes are described in further detail below.
`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 propa-
`gation environmenthassufficient 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. MIMOreceiver
`processing techniques may be used whenthe base station is
`communicating with multiple terminals simultaneously.
`From the terminal’s perspective, the same receiver process-
`ing techniques may be used to process N, different signals
`intended for that terminal (e.g., a single MIMOterminal) or
`just one of the N; signals (i.e., SIMO terminals).
`
`12
`
`12
`
`

`

`US 6,662,024 B2
`
`5
`the terminals may be randomly
`As shown in FIG. 1,
`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
`number of factors such as fading and multipath. At a
`particular instant in time, the channel response between the
`base station’s array of N; transmit antennas and the Nz
`receive antennas for a single terminal may be characterized
`by a matrix H whose elements are composed of independent
`Gaussian random variables, as follows:
`
`H=[4)
`
`fy «+ Ay, j=
`
`Eq (1)
`
`yy
`hyn
`
`fay
`inp
`.
`
`AnyA
`Any2
`:
`
`Ninp
`
`hang
`
`+ nye
`
`where H is the channel response matrix for the terminal, and
`h,; is the coupling between the base station’s i-th transmit
`antenna and the terminal’s j-th receive antenna.
`As shownin equation (1), the channel estimates for each
`terminal may be represented with a matrix having N;xNpz
`elements corresponding to the numberof transmit antennas
`at the base station and the numberof 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 may be used
`(e.g., each element of the matrix H may include a set of
`values for different frequency subchannels or time delays).
`The active terminals in the MIMO system periodically
`estimate the channel response for each transmit-receive
`antenna pair. The channel estimates may befacilitated in a
`number of ways such as, for example, with the use of pilot
`and/or data decision directed techniques knownin theart.
`The channel estimates may comprise the complex-value
`channel response estimate for each transmit-receive antenna
`pair, as described above in equation (1). The channelesti-
`mates give information on the transmission characteristics of
`each of the spatial subchannels, 1e., what data rate is
`supportable on each subchannel with a given set of trans-
`mission 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 other statistic that
`allows the transmitter to select
`the proper transmission
`parameters for that spatial subchannel. Typically, this pro-
`cess 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 channelstate
`information (CSI) that may be reported to the base station.
`Other forms of CSI may also be reported and are described
`below.
`The aggregate CSI received from the collection of termi-
`nals may be used to (1) select a “best” set of one or more
`terminals for data transmission, (2) assign the available
`transmit antennasto 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 per-
`formance by evaluating which specific combination of ter-
`minals and antenna assignments provide the best system
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`performance (e.g., the highest throughput) subject to any
`system constraints and requirements. By exploiting the
`spatial (and possibly frequency) “signatures” of the indi-
`vidual active terminals (i.e., their channel estimates),
`the
`average downlink throughput can be increased.
`The terminals may be scheduled for data transmission
`based on various factors. One set 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. Someorall of these factors may need to be
`satisfied on a per terminal basis (i.e., for each terminal) in a
`multiple access communication system. Another set of fac-
`tors may relate to system performance, which may be
`quantified by an average system throughput rate or some
`other indications of performance. These various factors are
`described in further detail below.
`The scheduling schemescan be designedto select the best
`set of terminals for simultaneous data transmission on the
`
`available transmission channels such that system perfor-
`mance is maximized while conforming to the system con-
`straints and requirements. For simplicity, various aspects of
`the invention are described below for a 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) N; independent data streams
`may be simultaneously transmitted by the base station from
`N, transmit antennas and targeted to one or more terminals,
`each equipped with N,
`receive antennas (i.e., N;xNp
`MIMO), where N,2N;.
`For simplicity, the number of receive antennas is assumed
`to be equal to the numberof transmit antennas(i.e., Nz=N7)
`for much of the description below. This is not a necessary
`condition since all of the analysis applies for the case where
`Nr=Nr.
`Scheduling of data transmission on the downlink com-
`prises two parts:
`(1) selection of one or more sets of
`terminals for evaluation, and (2) assignmentof 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 moresets (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
`numberof antenna assignment schemes. The terminals in the
`best hypothesis may then be scheduled for data transmission
`in an upcominginterval. The flexibility in both selecting the
`best set of terminals for data transmission and the assign-
`ment of the transmitted antennas to the selected terminals
`
`allows the scheduler to optimize performance by exploiting
`multi-user diversity environment.
`In order to determine the “optimum”transmissionto a set
`of terminals, the SNRs or someother 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 expressed as:
`
`Via
`Vi2
`r=;
`
`21
`¥2,2
`.
`
`YNp
`YNyp 2
`.
`
`i
`
`YUN Y2Np
`
`t+ YNNp
`
`Eq (2)
`
`is the post-processed SNR for a data stream
`where y;;
`(hypothetically) transmitted from the i-th transmit antenna to
`the j-th terminal.
`
`13
`
`13
`
`

`

`US 6,662,024 B2
`
`7
`the N; rows in the hypothesis
`In the N-SIMO mode,
`matrix I’ correspond to N, vectors of SNRs from N,
`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 MIMO
`terminal 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 rows as the number of data
`streams to be transmitted for the terminal (i.e., one row per
`data stream). Alternatively, one row in the hypothesis matrix
`T may be used for each SIMO or MIMOterminal, and the
`scheduler may be designed to mark and evaluate these
`different types of terminals accordingly.
`the N,
`At each terminal
`in the set
`to be evaluated,
`(hypothetically) transmitted data streamsare received by the
`terminal’s N, receive antennas, and the N, received signals
`can be processed using spatial or space-time equalization to
`separate out the N; transmitted data streams, as described
`below. The SNRof a post-processed data stream (.e., after
`equalization may be estimated and comprises the post-
`processed SNR for that data stream. For each terminal, a set
`of N; post-processed SNRs may be provided for the N; data
`streams that may be received by that terminal.
`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 SNRachieved at the terminal for each trans-
`mitted data stream depends on the order in which the
`transmitted data streams are detected (i.e., demodulated and
`decoded) to recoverthe transmitted data, as described below.
`In this case, a number of sets of SNRs maybe provided for
`each terminal for a numberof possible detection orderings.
`Multiple hypothesis matrices may then be formed and
`evaluated to determine which specific combination ofter-
`minals and detection ordering provides the best system
`performance.
`In any case, each hypothesis matrix I’ includes the post-
`processed SNRs for a specific set of terminals (ie.,
`hypothesis) to be evaluated. These post-processed SNRs
`represent the SNRsachievable by the terminals and are used
`to evaluate the hypothesis.
`FIG. 2 is a flow diagram of a process 200 to schedule
`terminals for data transmission,
`in accordance with an
`embodimentof the invention. Forclarity, the overall process
`is first described and the details for some of the steps in the
`process are described subsequently.
`the best set of
`Initially, metrics to be used to select
`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 maxi-
`mizes system throughput may be used.
`A (new) set of one or more active terminals is then
`selected from among all 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 numberof active terminals to be considered for
`
`scheduling, which then reduces the numberof hypothesesto
`be evaluated, as described below. For each terminal in the
`hypothesis, the SNR vector(¢.g., Y=[¥1;Y¥2,> -- - Yw,]) is
`retrieved, at step 216. The SNR vectors for all terminals in
`the hypothesis form the hypothesis matrix I shown in
`equation (2).
`For each hypothesis matrix T of N; transmit antennas and
`N, terminals, there are N; factorial possible combinations of
`assignments of transmit antennas to terminals (i.e., Ny!
`sub-hypotheses). Thus, a particular (mew) combination of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`antenna/terminal assignments is selected for evaluation, at
`step 218. This particular combination of antenna/terminal
`assignments forms a sub-hypothesis to be evaluated.
`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 metricis
`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 correspond-
`ing to this sub-hypothesis are saved. The performance and
`terminal metrics are described below.
`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 returns 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.
`If all sub-hypothesesfor a particular hypothesis have been
`evaluated, at step 224, a determination is then made whether
`or not all hypotheses have been considered,at step 226. If all
`hypotheses have not been considered,
`then the process
`returns to step 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.
`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 assign-
`ments may be used to sele