(12) United States Patent
`Li et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,947,748 B2
`Sep. 20, 2005
`
`US006947748B2
`
`(54) OFDMA WITH ADAPTIVE SUBCARRIER-
`CLUSTER CONFIGURATION AND
`SELECTIVE LOADING
`
`(75)
`
`Inventors: Xiaodong Li, Bellevue, WA (US); Hui
`Lill, Sammamish,
`KEHIIH LI,
`Bellevue, WA (US); Wenzhong Zhang,
`Bellevue, WA (US)
`
`(73) Assignee: Adaptix, Inc., Bothell, WA (US)
`.
`.
`.
`.
`.
`( * ) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 765 days.
`
`DE
`DE
`
`E1)
`Ep
`FR
`GB
`JP
`W0
`W0
`W0
`
`FOREIGN PATENT DOCUMENTS
`
`198 00 953 C1
`19800953 C1 *
`
`7/1999
`7/1999
`
`......... .. H04B/7/005
`
`g
`3
`0 929 202 A1
`0999553
`2 777 407 A1
`2 209 858 A
`06029922
`WO 98/16077 A2
`W0 93/30047 A1
`W0 02 49305 A2
`
`7/1999
`5/2000
`10/1999
`8/1997
`2/1994
`4/1998
`7/1993
`6/2002
`
`OTHER PUBLICATIONS
`
`(21) Appl. No.: 09/738,086
`(22)
`Filed:
`Dec 15, 2000
`(65)
`Prior Publication Data
`
`Us 2002/0119731 A1 Aug. 29, 2002
`7
`
`Int. Cl.
`(51)
`(52) U.S. Cl.
`
`.......................... .. H04Q 7/20; H04] 11/00
`..................... .. 455/450; 455/447; 455/453;
`455/455; 455/464; 370/208
`(58) Field of Search ............................... .. 455/447-453,
`455/456.5, 456.6, 509, 512, 513, 524-526,
`62, 63.1, 455, 463, 464, 168.1, 176.1, 179.1,
`1881’ 5501’ 553; 370/311’ 347’ 480’ 203_206>
`208, 210, 329, 375/132
`
`(56)
`
`_
`References Cited
`Us. PATENT DOCUMENTS
`
`5,280,630 A
`5,479,447 A
`55049775 A *
`2
`’
`’
`5,555,268 A
`5,588,020 A
`5,708,973 A
`5,726,978 A *
`5,734,967 A
`5,774,808 A *
`5,822,372 A
`
`1/1994 Wang
`12/1995 Ch0W et a1-
`4/1996 Ch01}1Y ‘*1 a1~
`451/ Eoduhit a1‘1“““““““ " 455/341
`/
`Oy’
`et a ’
`9/1996 Fattouche et al.
`12/1996 Schilling
`1/1998 Rifle,
`3/1998 Fmdigh et a1.
`3/1998 Kotzin et a1,
`6/1998 Sarkioja et al.
`10/1998 Emami
`
`........... N 370/252
`
`........... .. 455/436
`
`Vittoria Mignone et al. “CD3—OFDM: A Novel Demodula-
`tion Scheme for Fixed and Mobile Receives,” IEEE Trans-
`actions on Communications, Sep. 1996, Vol. 44, No. 9.
`
`Bender et al., CDMA/HDR: A BandWidth—EffiCient High-
`Speed Wireless Data Service for Nomadic Users, IEEE
`Communications Magazine, Jul. 2000, pp. 70_87.
`
`(Continued)
`
`Primary Emmme,_Wflham Tm,
`ASS,~S,m Emmme,_Me1eSS Zewdu
`(74) Attorney Agent or Firm—Fulbright & Jaworski LLP
`’
`’
`
`(57)
`
`ABSTRACT
`
`Amethod and apparatus for subcarrier selection for systems
`is described.
`In one embodiment,
`the system employs
`orthogonal frequency division multiple access (OFDMA). In
`one embodiment, a method for subcarrier selection com-
`prises each of multiple subscribers measuring channel and
`interference information for subcarriers based on pilot sym-
`bols received from a base station, at least one of subscribers
`.
`.
`.
`.
`.
`selecting. a set of candidate subcarriers, providing feedback
`information on the set of candidate subcarriers to the base
`station,.and the one subscriber receiving an indication of
`subcarriers of the set of subcarriers selected by the base
`station for use by the one subscriber.
`
`(Continued)
`
`23 Claims, 7 Drawing Sheets
`
`Periodically Broadcast Pilot
`OFDM Symbols to Subscribevs
`
`Subscribar(s)Cnm1numis\y Monilurs
`Pllol S/mhu|sIMeasures SINR andlor
`Other Parameters
`
`101
`
`IM
`
`
`
`
`Each Suhwiber Salsas Om or More
`clusters to: Each Ease smion
`
`1”
`
`Base Station Selects One or More
`cluster:for Each Subscnher
`
`Base Station Names the Subsuibar
`Regarding clusternllmmon
`
`1“
`
`W5
`
`SPRINT 1017
`
`

`
`US 6,947,748 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`2/1999 Baum et al.
`5,867,478 A
`3/1999 Yun et al.
`5,886,988 A
`3/1999 Lindroth et al.
`5,887,245 A
`6/1999 Engstrom et al.
`5,909,436 A
`6/1999 Cimini et al.
`5,914,933 A
`8/1999 Alamouti et al.
`5,933,421 A
`9/1999 Larsson et al.
`5,956,642 A
`10/1999 Li et al.
`5,973,642 A
`11/1999 Abu—Dayya
`5,991,273 A
`12/1999 Cimini, Jr. et al.
`6,005,876 A
`12/1999 Martinez et al.
`6,009,553 A
`2/2000 Williams
`6,026,123 A
`3/2000 Farsakh
`6,041,237 A
`4/2000 Chuang et al.
`6,052,594 A
`5/2000 Dent
`6,061,568 A
`5/2000 Chow
`6,064,692 A
`5/2000 Clark et al.
`6,064,694 A
`5/2000 Paulraj et al.
`6,067,290 A
`8/2000 Balachandran et al.
`6,108,374 A
`8/2000 Yonge, III
`6,111,919 A
`10/2000 Greenstein et al.
`6,131,016 A
`6,141,565 A * 10/2000 Feuerstein et al.
`6,144,696 A
`11/2000 Shively et al.
`6,226,320 B1
`5/2001 Hakkinen et al.
`6,298,092 B1 * 10/2001 Heath, Jr. et al. ......... .. 375/267
`6,307,851 B1
`10/2001 Jung et al.
`......... .. 455/450
`6,327,472 B1 * 12/2001 Westroos et al.
`6,330,460 B1 * 12/2001 Wong et al.
`.............. .. 455/562
`6,366,195 B1
`4/2002 Harel et al.
`6,377,632 B1
`4/2002 Paulraj et al.
`6,377,636 B1 *
`4/2002 Paulraj et al.
`6,449,246 B1
`9/2002 Barton et al.
`6,473,467 B1
`10/2002 Wallace et al.
`6,477,158 B1
`11/2002 Take
`6,545,997 B1
`4/2003 Bohnke et al.
`6,657,949 B1
`12/2003 Jones, IV et al.
`2003/0067890 A1
`4/2003 Goel et al.
`2003/0169681 A1
`9/2003 Li et al.
`2003/0169824 A1
`9/2003 Chayat
`OTHER PUBLICATIONS
`
`............ .. 375/346
`
`........ .. 455/560
`
`Frullone et al., PRMA Performance in Cellular Environ-
`ments with Self-Adaptive Channel Allocation Strategies,
`IEEE Transactions on Vehicular Technology, Nov. 1996, pp.
`657-665 vol. 45, No. 4.
`Xu, Guanghan and Li, San-Qi, Throughput Multiplication
`of Wireless Lans for Multimedia Services: SDMA Protocol
`
`Design, 1994 IEEE, pp. 1326-1332.
`Ward, James and Compton, R. Ted, Jr., High Throughput
`Slotted ALOHA Packet Radio Networks with Adaptive
`Arrays, IEEE Transactions on Communications, Mar. 1993,
`pp. 460-470, vol. 41, No. 3.
`Tsoulos, G.V., Smart antennas for mobile communication
`systems: benefits and challenges, Electronics & Communi-
`cation Engineering Journal, Apr. 1999, pp. 84-94.
`Shad et al., Indoor SDMA Capacity Using a Smart Antenna
`Basestation, 1997 IEEE, pp. 868-872.
`
`Farsakh, Christof and Nossek, Josef A., On the Mobile
`Radio Capacity Increase Through SDMA, no date (after
`1997).
`Bender, et al. “CDMA/HDR: A Bandwidth Efficient High-
`Speed Wireless Data Service for Nomadic Users,” IEEE
`Communications Magazine, Jul. 2000, pp. 70-87.
`Frullone, et al., “PRMA Performance in Cellular Environ-
`ments with Self-Adaptive Channel Allocation Strategies,”
`IEEE Transactions on Vehicular Technology, vol. 45, No. 4,
`Nov. 1996, pp. 657-665.
`Farsakh, C. et al., “Maximizing the SDMA Mobile Radio
`Capacity Increase by DOA Sensitive Channel Allocation”,
`Wireless Personal Communications, Kluwer Academic Pub-
`lishers, NL, vol.
`11, No.
`1, Oct. 1999, pp. 63-76,
`XP000835062, ISSN: 0929-6212.
`Wong, C.Y., et al., Multiuser OFDM With Adaptive Subcar-
`rierg Bit, and Power Allocation, IEEE Journal on Selected
`Areas in Communications, Oct. 1999, IEEE Inc., New York,
`USA, vol. 17, Nr. 10, pp. 1747-1758, XP000854075, ISSN:
`0733-8716 Sections I and II abstract.
`
`Gruenheid, R. et al: “Adaptive Modulation and Multiple
`Access for the OFDM Transmission Technique”, Wireless
`Personal Communications, Kluwer Academic Publishers,
`NL, vol. 13, NR. 1/2, Year 2000, pp. 5-13 XP000894156,
`ISSN: 0929-6212.
`
`Motegi, M. et al.: “Optimum Band Allocation According to
`Subband Condition for BST-OFDM” 11'” IEEE Interna-
`tional Symposium on Personal Indoor and Mobile Radio
`Communications, vol. 2, Sep. 18-21, 2000, pp. 1236-1240,
`XP002213669,
`Piscataway,
`NJ,
`USA,
`ISBN:
`0-7803-6463-5.
`
`Kapoor, S. et al.: “Adaptive Interference Suppression in
`Multiuser Wireless OFDM Systems Using Antenna Arrays”
`IEEE Transactions on Signal Processing, vol. 47, No. 12,
`Dec. 1999, pp. 3381-3391, XP000935422,
`IEEE, New
`York, USA, ISSN: 1053-587X.
`Ye Li, et al.: “Clustered OFDM with channel estimation for
`high rate wireless data”, Mobile Multimedia Communica-
`tions, 1999. (MOMUC ’99). 1999 IEEE International Work-
`shop on San Diego, CA, USA, IEEE, US, Nov. 15, 1999, pp.
`43-50, XP010370695, ISBN: 0-7803-5904-6.
`Nogueroles, R. et al.: “Improved Performance of a Random
`OFDMA Mobile Communication System” Vehicular Tech-
`nology Conference, 1998. VTC 98. 48'” IEEE Ottawa,
`Ontario, Canada, May 18-21, 1998, pp. 2502-2506,
`XP010288120, ISBN: 0-7803-4320-4.
`Kinugawa, Y. et al.: “Frequency and Time Division Multiple
`Access with Demand-Assignment Using Multicarrier
`Modulation for Indoor Wireless Communications Systems”,
`IEICE Transactions on Communications, Institute of Elec-
`tronics Information and Comm. Eng. Tokyo, Japan, vol.
`E77-B, NR. 3, Mar. 1994, pp. 396-402, XP000451014,
`ISSN: 0916-8516.
`
`* cited by examiner
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 1 of 7
`
`US 6,947,748 B2
`
`Subcarfier
`
`101
`
`Cluster
`
`102
`
`F
`
`FBJA
`
`r
`
`Cluster A
`
`
`Cluster B
`
`
`
`
`
`
`
`
`Symbols
`201
`
`!§§!!§!§!!
`Pilot OFDM
`!§§!!§!§!!
`
`!§§!!§!§!!
`
`-§§--§-§II
`
`
`Occupied Clusters
`
`t
`
`a. Cell A
`
`W
`
`201
`
`
`
`!§!§!!§!!!
`!§!§!!§!!!
`
`
`!§!§!!§!!!
`I§I§II§III
`
`
`
`m
`
`-------------------- ~
`
`
`
`
`§!!!!!§!!§
`§IIIII§II§
`
`
`HG2
`
`W
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 2 of 7
`
`US 6,947,748 B2
`
`Periodically Broadcast Pilot
`OFDM Symbols to Subscribers
`
`Subscriber(s) Continuously Monitors
`Pilot SymbolslMeasures SINR and/or
`Other Parameters
`
`101
`
`102
`
`Each Subscriber Selects One or More
`Clusters for Each Base Station
`
`103
`
`Retraining
`Needed
`?
`
`104
`
`105
`
`
`
`Base Station Selects One or More
`Clusters for Each Subscriber
`
`Base Station Notifies the Subscriber
`
`Regarding Cluster Allocation
`
`FIG. 1B
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 3 of 7
`
`US 6,947,748 B2
`
`
`
`Channel/Interference
`Estimation in Pilot
`Periods
`
`
`
`
`
`
`Cluster Ordering
`Request Selected
`and Rate
`Clusters and Coding!
`Prediction
`Modulation Rates
`
`
`
`Trafficllnterference
`Analysis in Date
`
`Periods
`
`3” FIG. 3
`
`
`
`
`
`
`
`
`
`405
`
` Cluster Ordering!
`404 Selection Based on
`SINR and Power
`
`Differenoe
`
`
`
`
`
`
`
`Request Selected
`Clusters and Coding!
`Modulation Rates
`
`406
`
`Per-cluster SINR
`Estimation in
`
`Pilot Periods
`
`
`
`Per—cluster
`Power Calculation
`in Pilot Periods
`
`
`
`Per—cluster
`
`
`
`Power Calculation
`in Data Periods
`
`
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 4 of 7
`
`US 6,947,748 B2
`
`
`
`o
`
`
`
`
`
`
`
`
`\
`
`
`
`
`
`\
`
`
`
`\
`
`
`
`FIG. 8
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 5 of 7
`
`US 6,947,748 B2
`
`1-8: Diverse Clusters
`
`f
`
`
`
`15.
`
`
`
`
`
`
`
`f
`
`
`
`
`
`
`
`
`
`
`
`b. Cell B
`
`
`
`c. Cell C
`
`
`
`
`
`
`
`
`
`
`a. Cell A
`
`:' 13 14
`
`F
`
` I nlll
`l"1’1'I'Il' I!
`h I II
`I
`
`9-16: Plain Clusters
`
`
`
`
`
`
`
`
`
`
`1
`
`
`
`
`
`
`
`
`
`
`
`1
`
`
`
`
`
`'
`I
`
`
`
`
`
`
`IO
`
`
`
`I !
`
`
`
`Subcarrier 1
`
`Subcarrier 2
`
`
`
`:1
`
`."‘:
`i‘;
`
`
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 6 of 7
`
`US 6,947,748 B2
`
`
`
`Variation Detection
`
`
`
`Channel/Interference
`
`1101
`
`
`
`
`
`
`Yes
`
`Any
`Significant Variation
`Detected
`
`
`
`Clusters
`
`?
`
`1104
`
`Select Diversity
`
`1103
`
`Select Coherence
`
`Clusters
`
`FIG. 11
`
`!I
`
`
`
`
`
`'llllllllil'l'lllll*“ll'llllI ’ll"’ll
`I
`1: null
`null:
`Illllu
`
`—.L
`
`a. Cell A
`
`FIG. 12
`
`

`
`U.S. Patent
`
`Sep. 20, 2005
`
`Sheet 7 of 7
`
`US 6,947,748 B2
`
`User Data Buffer lnfonnation
`1311
`
`User1~N
`
`
`
`Multi-user Data
`Buffer
`
`1302
`
`
`
`1303
`
`Multiplexer
`
`
`
`Admission Control
`1301
`1 310
`
`
`Cluster Allocation and
`
`
`
`Load Scheduling
`Controller
`
`Cluster 1 ~ M
`
`1304
`
`1305
`
`T
`
`d
`
`OFDM Transceiver
`
`
`
`
`
`OFDM Signal
`
`
`
`
`Multi-cluster
`'
`'
`
`smate
`R'Z2Z?3E.‘.§,"’a'L§2,
`
`
`
`lndices
`
`1313
`
`
`
`
`
`COMFOI 319113”
`Cluster Allocation
`1312
`
`FIG. 13
`
`

`
`US 6,947,748 B2
`
`1
`OFDMA WITH ADAPTIVE SUBCARRIER-
`CLUSTER CONFIGURATION AND
`SELECTIVE LOADING
`
`FIELD OF THE INVENTION
`
`The invention relates to the field of wireless communi-
`
`cations; more particularly, the invention relates to multi-cell,
`multi-subscriber wireless systems using orthogonal
`fre-
`quency division multiplexing (OFDM).
`BACKGROUND OF THE INVENTION
`
`Orthogonal frequency division multiplexing (OFDM) is
`an efficient modulation scheme for signal transmission over
`frequency-selective channels. In OFDM, a wide bandwidth
`is divided into multiple narrow-band subcarriers, which are
`arranged to be orthogonal with each other. The signals
`modulated on the subcarriers are transmitted in parallel. For
`more information, see Cimini, Jr., “Analysis and Simulation
`of a Digital Mobile Channel Using Orthogonal Frequency
`Division Multiplexing,” IEEE Trans. Commun., vol. COM-
`33, no. 7, July 1985, pp. 665-75; Chuang and Sollenberger,
`“Beyond 3G: Wideband Wireless Data Access Based on
`OFDM and Dynamic Packet Assignment,” IEEE Commu-
`nications Magazine, Vol. 38, No. 7, pp. 78-87, July 2000.
`One way to use OFDM to support multiple access for
`multiple subscribers is through time division multiple access
`(TDMA), in which each subscriber uses all the subcarriers
`within its assigned time slots. Orthogonal frequency division
`multiple access (OFDMA) is another method for multiple
`access, using the basic format of OFDM.
`In OFDMA,
`multiple subscribers simultaneously use different
`subcarriers, in a fashion similar to frequency division mul-
`tiple access (FDMA). For more information, see Sari and
`Karam, “Orthogonal Frequency-Division Multiple Access
`and its Application to CATV Networks,” European Trans-
`actions on Telecommunications, Vol. 9 (6), pp. 507-516,
`November/December 1998 and Nogueroles, Bossert,
`Donder, and Zyablov, “Improved Performance of a Random
`OFDMA Mobile Communication System,”, Proceedings of
`IEEE VTC’98, pp. 2502-2506.
`Multipath causes frequency-selective fading. The channel
`gains are different for different subcarriers. Furthermore, the
`channels are typically uncorrelated for different subscribers.
`The subcarriers that are in deep fade for one subscriber may
`provide high channel gains for another subscriber.
`Therefore,
`it
`is advantageous in an OFDMA system to
`adaptively allocate the subcarriers to subscribers so that each
`subscriber enjoys a high channel gain. For more
`information, see Wong et al., “Multiuser OFDM with Adap-
`tive Subcarrier, Bit and Power Allocation,” IEEE J. Select.
`Areas Commun., Vol. 17(10), pp. 1747-1758, October 1999.
`Within one cell,
`the subscribers can be coordinated to
`have different subcarriers in OFDMA. The signals for dif-
`ferent subscribers can be made orthogonal and there is little
`intracell interference. However, with aggressive frequency
`reuse plan, e.g.,
`the same spectrum is used for multiple
`neighboring cells,
`the problem of intercell
`interference
`arises. It is clear that the intercell interference in an OFDMA
`
`system is also frequency selective and it is advantageous to
`adaptively allocate the subcarriers so as to mitigate the effect
`of intercell interference.
`
`One approach to subcarrier allocation for OFDMA is a
`joint optimization operation, not only requiring the activity
`and channel knowledge of all the subscribers in all the cells,
`but also requiring frequent rescheduling every time an
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`existing subscribers is dropped off the network or a new
`subscribers is added onto the network. This is often imprac-
`tical in real wireless system, mainly due to the bandwidth
`cost for updating the subscriber information and the com-
`putation cost for the joint optimization.
`
`SUMMARY OF THE INVENTION
`
`A method and apparatus for subcarrier selection for
`systems is described.
`In one embodiment,
`the system
`employs orthogonal frequency division multiple access
`(OFDMA). In one embodiment, a method for subcarrier
`selection comprises a subscriber measuring channel and
`interference information for subcarriers based on pilot sym-
`bols received from a base station, the subscriber selecting a
`set of candidate subcarriers, providing feedback information
`on the set of candidate subcarriers to the base station, and
`receiving an indication of subcarriers of the set of subcar-
`riers selected by the base station for use by the subscriber.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention will be understood more fully from
`the detailed description given below and from the accom-
`panying drawings of various embodiments of the invention,
`which, however, should not be taken to limit the invention
`to the specific embodiments, but are for explanation and
`understanding only.
`FIG. 1A illustrates subcarriers and clusters.
`
`FIG. 1B is a flow diagram of one embodiment of a process
`for allocating subcarriers.
`FIG. 2 illustrates time and frequency grid of OFDM
`symbols, pilots and clusters.
`FIG. 3 illustrates subscriber processing.
`FIG. 4 illustrates one example of FIG. 3.
`FIG. 5 illustrates one embodiment of a format for arbi-
`
`trary cluster feedback.
`FIG. 6 illustrates one embodiment of a partition the
`clusters into groups.
`FIG. 7 illustrates one embodiment of a feedback format
`
`for group-based cluster allocation.
`FIG. 8 illustrates frequency reuse and interference in a
`multi-cell, multi-sector network.
`FIG. 9 illustrates different cluster formats for coherence
`
`clusters and diversity clusters.
`FIG. 10 illustrates diversity clusters with subcarrier hop-
`ping.
`FIG. 11 illustrates intelligent switching between diversity
`clusters and coherence clusters depending on subscribers
`mobility.
`FIG. 12 illustrates one embodiment of a reconfiguration
`of cluster classification.
`FIG. 13 illustrates one embodiment of a base station.
`
`DETAILED DESCRIPTION OF THE PRESENT
`INVENTION
`
`A distributed, reduced-complexity approach for subcar-
`rier allocation is described. The techniques disclosed herein
`are described using OFDMA (clusters) as an example.
`However, they are not limited to OFDMA-based systems.
`The techniques apply to multi-carrier systems in general,
`where, for example, a carrier can be a cluster in OFDMA, a
`spreading code in CDMA, an antenna beam in SDMA
`(space-division multiple access), etc. In one embodiment,
`subcarrier allocation is performed in each cell separately.
`
`

`
`US 6,947,748 B2
`
`3
`Within each cell, the allocation for individual subscribers
`(e.g., mobiles) is also made progressively as each new
`subscriber is added to the system as opposed to joint
`allocation for subscribers within each cell in which alloca-
`
`tion decisions are made taking into account all subscribers in
`a cell for each allocation.
`
`For downlink channels, each subscriber first measures the
`channel and interference information for all the subcarriers
`
`and then selects multiple subcarriers with good performance
`(e.g., a high signal-to-interference plus noise ratio (SINR))
`and feeds back the information on these candidate subcar-
`
`10
`
`riers to the base station. The feedback may comprise channel
`and interference information (e.g., signal-to-interference-
`plus-noise-ratio information) on all subcarriers or just a
`portion of subcarriers. In case of providing information on
`only a portion of the subcarriers, a subscriber may provide
`a list of subcarriers ordered starting with those subcarriers
`which the subscriber desires to use, usually because their
`performance is good or better than that of other subcarriers.
`Upon receiving the information from the subscriber, the
`base station further selects the subcarriers among the
`candidates, utilizing additional information available at the
`base station, e.g.,
`the traffic load information on each
`subcarrier, amount of traffic requests queued at the base
`station for each frequency band, whether frequency bands
`are overused, and/or how long a subscriber has been waiting
`to send information. In one embodiment,
`the subcarrier
`loading information of neighboring cells can also be
`exchanged between base stations. The base stations can use
`this information in subcarrier allocation to reduce inter-cell
`interference.
`
`In one embodiment, the selection by the base station of
`the channels to allocate, based on the feedback, results in the
`selection of coding/modulation rates. Such coding/
`modulation rates may be specified by the subscriber when
`specifying subcarriers that it finds favorable to use. For
`example, if the SINR is less than a certain threshold (e.g., 12
`dB), quadrature phase shift keying (QPSK) modulation is
`used; otherwise, 16 quadrature amplitude modulation
`(QAM) is used. Then the base station informs the subscrib-
`ers about
`the subcarrier allocation and the coding/
`modulation rates to use.
`
`In one embodiment, the feedback information for down-
`link subcarrier allocation is transmitted to the base station
`
`through the uplink access channel, which occurs in a short
`period every transmission time slot, e.g., 400 microseconds
`in every 10-millisecond time slot. In one embodiment, the
`access channel occupies the entire frequency bandwidth.
`Then the base station can collect the uplink SINR of each
`subcarrier directly from the access channel. The SINR as
`well as the traffic load information on the uplink subcarriers
`are used for uplink subcarrier allocation.
`For either direction,
`the base station makes the final
`decision of subcarrier allocation for each subscriber.
`
`In the following description, a procedure of selective
`subcarrier allocation is also disclosed, including methods of
`channel and interference sensing, methods of information
`feedback from the subscribers to the base station, and
`algorithms used by the base station for subcarrier selections.
`In the following description, numerous details are set
`forth to provide a thorough understanding of the present
`invention. It will be apparent, however, to one skilled in the
`art, that the present invention may be practiced without these
`specific details. In other instances, well-known structures
`and devices are shown in block diagram form, rather than in
`detail, in order to avoid obscuring the present invention.
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Some portions of the detailed descriptions which follow
`are presented in terms of algorithms and symbolic repre-
`sentations of operations on data bits within a computer
`memory. These algorithmic descriptions and representations
`are the means used by those skilled in the data processing
`arts to most effectively convey the substance of their work
`to others skilled in the art. An algorithm is here, and
`generally, conceived to be a self-consistent sequence of steps
`leading to a desired result. The steps are those requiring
`physical manipulations of physical quantities. Usually,
`though not necessarily, these quantities take the form of
`electrical or magnetic signals capable of being stored,
`transferred, combined, compared, and otherwise manipu-
`lated. It has proven convenient at times, principally for
`reasons of common usage, to refer to these signals as bits,
`values, elements, symbols, characters, terms, numbers, or
`the like.
`
`It should be borne in mind, however, that all of these and
`similar terms are to be associated with the appropriate
`physical quantities and are merely convenient labels applied
`to these quantities. Unless specifically stated otherwise as
`apparent from the following discussion, it is appreciated that
`throughout the description, discussions utilizing terms such
`as “processing” or “computing” or “calculating” or “deter-
`mining” or “displaying” or the like, refer to the action and
`processes of a computer system, or similar electronic com-
`puting device, that manipulates and transforms data repre-
`sented as physical (electronic) quantities within the com-
`puter system’s registers and memories into other data
`similarly represented as physical quantities within the com-
`puter system memories or registers or other such informa-
`tion storage, transmission or display devices.
`The present invention also relates to apparatus for per-
`forming the operations herein. This apparatus may be spe-
`cially constructed for the required purposes, or it may
`comprise a general purpose computer selectively activated
`or reconfigured by a computer program stored in the com-
`puter. Such a computer program may be stored in a computer
`readable storage medium, such as, but is not limited to, any
`type of disk including floppy disks, optical disks,
`CD-ROMs, and magnetic-optical disks, read-only memories
`(ROMs),
`random access memories (RAMs), EPROMs,
`EEPROMs, magnetic or optical cards, or any type of media
`suitable for storing electronic instructions, and each coupled
`to a computer system bus.
`The algorithms and displays presented herein are not
`inherently related to any particular computer or other appa-
`ratus. Various general purpose systems may be used with
`programs in accordance with the teachings herein, or it may
`prove convenient to construct more specialized apparatus to
`perform the required method steps. The required structure
`for a variety of these systems will appear from the descrip-
`tion below.
`In addition,
`the present
`invention is not
`described with reference to any particular programming
`language. It will be appreciated that a variety of program-
`ming languages may be used to implement the teachings of
`the invention as described herein.
`
`Amachine-readable medium includes any mechanism for
`storing or transmitting information in a form readable by a
`machine (e.g., a computer). For example, a machine-
`readable medium includes read only memory (“ROM”);
`random access memory (“RAM”); magnetic disk storage
`media; optical storage media;
`flash memory devices;
`electrical, optical, acoustical or other form of propagated
`signals (e.g., carrier waves, infrared signals, digital signals,
`etc.); etc.
`
`

`
`US 6,947,748 B2
`
`5
`
`Subcarrier Clustering
`The techniques described herein are directed to subcarrier
`allocation for data traffic channels. In a cellular system, there
`are typically other channels, pre-allocated for the exchange
`of control information and other purposes. These channels
`often include down link and up link control channels, uplink
`access channels, and time and frequency synchronization
`channels.
`
`FIG. 1A illustrates multiple subcarriers, such as subcarrier
`101, and cluster 102. Acluster, such as cluster 102, is defined
`as a logical unit that contains at least one physical subcarrier,
`as shown in FIG. 1A. A cluster can contain consecutive or
`
`10
`
`disjoint subcarriers. The mapping between a cluster and its
`subcarriers can be fixed or reconfigurable. In the latter case,
`the base station informs the subscribers when the clusters are
`
`15
`
`the frequency spectrum
`In one embodiment,
`redefined.
`includes 512 subcarriers and each cluster includes four
`
`consecutive subcarriers, thereby resulting in 128 clusters.
`An Exemplary Subcarrier/Cluster Allocation Procedure
`FIG. 1B is a flow diagram of one embodiment of a process
`for allocation clusters to subscribers. The process is per-
`formed by processing logic that may comprise hardware
`(e.g., dedicated logic, circuitry, etc.), software (such as that
`which runs on, for example, a general purpose computer
`system or dedicated machine), or a combination of both.
`Referring to FIG. 1B, each base station periodically
`broadcasts pilot OFDM symbols to every subscriber within
`its cell (or sector) (processing block 101). The pilot symbols,
`often referred to as a sounding sequence or signal, are
`known to both the base station and the subscribers. In one
`
`embodiment, each pilot symbol covers the entire OFDM
`frequency bandwidth. The pilot symbols may be different for
`different cells (or sectors). The pilot symbols can serve
`multiple purposes:
`time and frequency synchronization,
`channel estimation and signal-to-interference/noise (SINR)
`ratio measurement for cluster allocation.
`
`Next, each subscriber continuously monitors the reception
`of the pilot symbols and measures the SINR and/or other
`parameters, including inter-cell interference and intra-cell
`traffic, of each cluster (processing block 102). Based on this
`information, each subscriber selects one or more clusters
`with good performance (e.g., high SINR and low traffic
`loading) relative to each other and feeds back the informa-
`tion on these candidate clusters to the base station through
`predefined uplink access channels (processing block 103).
`For example, SINR values higher than 10 dB may indicate
`good performance. Likewise, a cluster utilization factor less
`than 50% may be indicative of good performance. Each
`subscriber selects the clusters with relatively better perfor-
`mance than others. The selection results in each subscriber
`
`selecting clusters they would prefer to use based on the
`measured parameters.
`In one embodiment, each subscriber measures the SINR
`of each subcarrier cluster and reports these SINR measure-
`ments to their base station through an access channel. The
`SINR value may comprise the average of the SINR values
`of each of the subcarriers in the cluster. Alternatively, the
`SINR value for the cluster may be the worst SINR among
`the SINR values of the subcarriers in the cluster. In still
`
`another embodiment, a weighted averaging of SINR values
`of the subcarriers in the cluster is used to generate an SINR
`value for the cluster. This may be particularly useful in
`diversity clusters where the weighting applied to the sub-
`carriers may be different.
`The feedback of information from each subscriber to the
`base station contains a SINR value for each cluster and also
`
`indicates the coding/modulation rate that
`
`the subscriber
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`desires to use. No cluster index is needed to indicate which
`
`SINR value in the feedback corresponds to which cluster as
`long as the order of information in the feedback is known to
`the base station. In an alternative embodiment, the informa-
`tion in the feedback is ordered according to which clusters
`have the best performance relative to each other for the
`subscriber. In such a case, an index is needed to indicate to
`which cluster the accompanying SINR value corresponds.
`Upon receiving the feedback from a subscriber, the base
`station further selects one or more clusters for the subscriber
`
`among the candidates (processing block 104). The base
`station may utilize additional information available at the
`base station, e.g.,
`the traffic load information on each
`subcarrier, amount of traffic requests queued at the base
`station for each frequency band, whether frequency bands
`are overused, and how long a subscriber has been waiting to
`send information. The subcarrier loading information of
`neighboring cells can also be exchanged between base
`stations. The base stations can use this information in
`subcarrier allocation to reduce inter-cell interference.
`
`After cluster selection, the base station notifies the sub-
`scriber about
`the cluster allocation through a downlink
`common control channel or through a dedicated downlink
`traffic channel if the connection to the subscriber has already
`been established (processing block 105).
`In one
`embodiment, the base station also informs the subscriber
`about the appropriate modulation/coding rates.
`Once the basic communication link is established, each
`subscriber can continue to send the feedback to the base
`
`station using a dedicated traffic channel (e.g., one or more
`predefined uplink access channels).
`In one embodiment,
`the base station allocates all the
`clusters to be used by a subscriber at once. In an alternative
`embodiment, the base station first allocates multiple clusters,
`referred to herein as the basic clusters, to establish a data link
`between the base station and the subscriber. The base station
`
`then subsequently allocates more clusters, referred to herein
`as the auxiliary clusters, to the subscriber to increase the
`communication bandwidth. Higher priorities can be given to
`the assignment of basic clusters and lower priorities may be
`given to that of auxiliary clusters. For example, the base
`station first ensures the assignment of the basic clusters to
`the subscribers and then tries to satisfy further requests on
`the auxiliary clusters from the subscribers. Alternatively, the
`base station may assign auxiliary clusters to one or more
`subscribers before allocating basic clusters to other subscrib-
`ers. For example, a base station may allocate basic and
`auxiliary clusters to one subscriber before allocating any
`clusters to other subscribers. In one embodiment, the base
`station allocates basic clusters to a new subscriber and then
`
`determines if there are any other subscribers requesting
`clusters. If not, then the base station allocates the auxiliary
`clusters to that new subscriber.
`
`From time to time, processing logic performs retraining
`by repeating the process described above (processing block
`106). The retraining may be performed periodically. This
`retraining compensates for subscriber movement and any
`changes in interference. In one embodiment, each subscriber
`reports to the base station its updated selection of clusters
`and their associated SINRs. Then the base station further
`
`performs the reselection and informs the subscriber about
`the new cluster allocation. Retraining can be initiated by the
`base station, and in which case, the base station requests a
`specific subscriber to report its updated cluster selection.
`Retraining can also be initiated by the subscriber when it
`observes channel deterioration.
`
`

`
`US 6,947,748 B2
`
`8
`cells are broadcast at the same time, they will interfere with
`each other (because they occupy the entire frequency band).
`This collision of pilot symbols may be used to determine the
`amount of interference as a worst case scen