Adaptix, Inc. v. Apple Inc et al
Filing
1
COMPLAINT of Patent Infringement against Apple Inc, Cellco Partnership ( Filing fee $ 400, receipt number 0971-8036744.). Filed byAdaptix, Inc.. (Attachments: # 1 Exhibit A to Complaint, # 2 Exhibit B to Complaint, # 3 Civil Cover Sheet)(Shafer, Daniel) (Filed on 9/26/2013)
EXHIBIT A
US007454212B2
(12) United States Patent
(10) Patent N0.:
Li et a].
(54)
(45) Date of Patent:
OFDMA WITH ADAPTIVE
(56)
Nov. 18, 2008
References Cited
SUBCARRIER-CLUSTER CONFIGURATION
AND SELECTIVE LOADING
(75)
US 7,454,212 B2
US. PATENT DOCUMENTS
Inventors: Xiaodong Li, Bellevue, WA (US); Hui
4,670,889 A
6/1987 Hewitt et al'
Liu, Sammamish, WA (US); Kemin Li,
Bellevue, WA (US); Wenzhong Zhang,
Bellevue, WA (US)
(73) Assignee: AdaptiX, Inc., Bellevue, WA (US)
(*)
Notice:
(Continued)
FOREIGN PATENT DOCUMENTS
Subject to any disclaimer, the term of this
patent is extended or adjusted under 35
DE
198 00 953
7/1999
U.S.C. 154(b) by 0 days.
(21) Appl.No.: 11/199,586
(22) Filed:
Aug. 8, 2005
(65)
(Continued)
Prior Publication Data
US 2006/0083210A1
OTHER PUBLICATIONS
Apr. 20, 2006
.
.
Wong et al. “Multiuser OFDM with Adaptive Subcarrier, Bit, and
Related U's' Apphcatlon Data
Power Allocation”, IEEE Journal on Selected Areas in Communica
(63)
Continuation of application No. 09/738,086, ?led on
ti0I1S~IEEE~NeWY0f1<,U$, 1999, V01~ 17,NR~ 10,1311 1747-1758
Dec, 15, 2000, now Pat, No, 6,947,748,
Mexican Of?ce Action issued for PNa/2003/005311 dated Mar. 31,
(51)
Int. C1.
2006
H04B 17/00
(2006.01)
(Continued)
H04B 7/00
H04Q 7/20
H04Q 7/00
(2006.01)
(2006.01)
(2006.01)
Primary ExamineriMeless N ZeWdu
(74) Attorney, Agent, or FirmiFulbright & JaWorski L.L.P.
H04Q 7/28
(52)
(2006.01)
H04M 1/00
H04M 1/38
(2006.01)
(2006.01)
(57)
US. Cl. .................... .. 455/450; 455/67.11; 455/69;
455M522. 455/464. 455/509. 455/5501.
455/5562;455/561;370/329;370/341
(58)
ABSTRACT
Field of Classi?cation Search ............ .. 455/1791
A method and apparatus for subcarrier selection for systems
is described. In one embodiment, the system employs
onhogonal frequency division multiple access (OFDMA)~ In
455/188 1 422 1 516*517 67 11 561 562 1’
4 5 5 /13 2435 4 565*4 566 4 5 5 423*425
one embodiment, a method for subcarrier selection comprises
each of multiple subscribers measuring channel and interfer
455/63_1i63_2’ 6245 41_2l41_3’ 443*453’
455/463i464 509:510 55,3 512*513’ 524*526’
ence information for subcarriers based on pilot symbols
received from a base station, at least one ofsubscribers select
455/55’01 1681’ 1761 69 70’ 266 403’
ing a set of candidate subcarriers, providing feedback infor
4 55 /500 556,2. 370}203i2’10 511’ 3 4 6L3 47’
370/46’5i480’ 312*314 319L322’ 328*330’
mation on the set of candidate subcarriers to the base station,
and the one subscriber receiving an indication of subcarriers
370/338’ 541*344’ $39521, 39,5 '41’ 430:
370/437, 447, 449, 458, 461*462, 913; 375/311,
375/240, 240.07, 24011
ofthe set ofsubcarriers selected by the base station for use by
‘he Onesubsc?ber
See application ?le for complete search hi story.
3 3 Claims, 7 Drawing Sheets
Be in
Peliudimlly Broadcast Pllnl
_, 101
OFDM Symbols l0 Suhsclihers
Suhecribeds) Cunlinuuusly Monitors
Pllul Symbols/Measures SINR end/0| ~10?
Omar Parameters
, ,
Reviving
Each Subscriber Selects One nrMnre ‘103
"0
Clusters for Each Base Slalicrl
Needed
7
1
Ease Slat‘
Clusle
Selecls One or More
I Each Subscriber
Ease Slallon Noti?es me Suhsuriber
Regarding Cluster Allocation
_, 104
‘ 1 "5
US 7,454,212 B2
Page 2
2005/0025099 A1
U.S. PATENT DOCUMENTS
5,280,630
5,437,054
5,479,447
5,504,775
5,507,034
5,515,378
5,555,268
5,588,020
5,708,973
5,726,978
5,734,967
5,774,808
5,822,372
5,839,074
5,867,478
5,886,988
5,887,245
5,909,436
5,914,933
5,933,421
5,956,642
5,973,642
5,991,273
6,005,876
6,009,553
6,023,622
6,026,123
6,041,237
6,052,594
6,061,568
6,064,692
6,064,694
6,067,290
6,091,955
6,108,374
6,111,919
6,131,016
6,141,565
6,144,696
6,226,320
6,282,185
6,298,092
6,307,851
6,327,472
6,330,460
6,366,195
6,377,632
6,377,636
6,411,186
6,415,153
6,449,246
6,473,467
6,477,158
6,526,281
6,545,997
6,553,011
6,567,383
6,657,949
6,726,297
6,904,283
6,920,122
6,985,432
7,047,011
7,373,151
2002/0114269
2003/0067890
2003/0169681
2003/0169824
A1
A1
A1
A1
1/1994
7/1995
12/1995
4/1996
4/1996
5/1996
9/1996
12/1996
1/1998
3/1998
3/1998
6/1998
10/1998
11/1998
2/1999
3/1999
3/1999
6/1999
6/1999
8/1999
9/1999
10/1999
11/1999
12/1999
12/1999
2/2000
2/2000
3/2000
4/2000
5/2000
5/2000
5/2000
5/2000
7/2000
8/2000
8/2000
10/2000
10/2000
11/2000
5/2001
8/2001
10/2001
10/2001
12/2001
12/2001
4/2002
4/2002
4/2002
6/2002
7/2002
9/2002
10/2002
11/2002
2/2003
4/2003
4/2003
5/2003
12/2003
4/2004
6/2005
7/2005
1/2006
5/2006
5/2008
8/2002
4/2003
9/2003
9/2003
Wang
FOREIGN PATENT DOCUMENTS
Rappaport et al.
DE
Chouly et al.
Bodin et al.
............. .. 455/34.1
Roy, III et al.
Fattouche et al.
Schilling
Ritter
Frodigh et al. ............ .. 370/252
Kotzin et al.
Sarkioja et al.
Emami
Plehn et al.
Baum et al.
Yun et al.
Lindroth et al.
198 00 953 C1
7/1999
DE
DE
Chow et al.
19800953
*
019800953 C1 *
7/1999
7/1999
EP
EP
EP
EP
EP
EP
FR
JP
KR
W0
W0
W0
0 869 647
0882377
0 926 912
0 929 202
0 999 658
0999658
2 777 407
06029922
1999-28244
WO 98/16077
WO 98/30047
W0 02 49305
A2
B1
A2
A1
A1
A2
A1
A2
10/1998
4/1999
6/1999
7/1999
5/2000
5/2000
10/1999
2/1994
4/1999
4/1998
7/1998
6/2002
OTHER PUBLICATIONS
Engstrom et al.
Cimini et al.
Alamouti et al.
Larsson et al. ............ .. 455/449
Li et al.
Abu-Dayya
Cimini, Jr. et al.
Martinez et al.
Plaschke et al.
Williams
Farsakh
Chuang et al. ............ .. 455/450
Dent
Chow
Clark et al.
Ye Li et al.; “Clustered OFDM with Channel Estimation for High
Rate Wireless Data”; Mobile Multimedia Communications, 1999.
(MoMuC’99) 1999 IEEE International Workshop on Nov. 15-17,
1999; pp. 43-50.
Korean Of?ce Action issued for 2003-7007962 dated Apr. 28, 2006.
Korean Of?ce Action issued for 2003-7007963 dated Apr. 29, 2006.
Bender et al., CDMNHDR: A Bandwidth-Ef?cient High-Speed
Wireless Data Service for Nomadic Users, IEEE Communications
Magazine, Jul. 2000, pp. 70-87. **
Frullone et al., PRMA Performance in Cellular Environments 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 Wire
less Lans for Multimedia Services: SDMA Protocol Design, 1994
IEEE, pp. 1326-1332. **
Paulraj et al.
Aalto et al.
2/2005 Heath et al.
Ward, James and Compton, R. Ted, Jr., High Throughput Slotted
............... .. 455/447
Balachandran et al.
Yonge, III
Greenstein et al.
Feuerstein et al.
........ .. 455/560
Shively et al.
Aloha Packet Radio Networks with Adaptive Arrays, IEEE Transac
tions on Communications, Mar. 1993, pp. 460-470, vol. 41, No. 3.**
Tsoulos, G.V., Smart Antennas for Mobile Communication Systems:
Bene?ts and Challenges, Electronics & Communication Engineering
Journal, Apr. 1999, pp. 84-94.**
Hakkinen et al.
Hakkinen et al.
Shad et al., Indoor SDMA Capacity Using a Smart Antenna Basesta
tion, 1997 IEEE, pp. 868-872.**
Farsakh, Christof and Nossek, Josef A., On the Mobile Radio Capac
Heath, Jr.
ity Increase Through SDMA, no date (after 1997).**
Jung et al.
Farsakh, C. et al., “Maximizing the SDMA Mobile Radio Capacity
Increase by DOA Sensitive Channel Allocation,” Wireless Personal
Communications, Kluwer Academic Publishers, NL, vol. 11, No. 1.
Oct. 1999, pp. 63-76, XP000835062, ISSN: 0929-6212.**
Wong, C. Y, et al., Multiuser OFDM With Adaptive Subcarrier, Bit,
Westroos et al. .......... .. 455/450
Wong et al. ............... .. 455/562
Harel et al.
Paulraj et al.
Paulraj et al.
Lilleberg et al.
and Power Allocation, IEEE Journal on Selected Areas in Commu
nications, Oct. 1999, IEEE Inc., NewYork, USA, vol. 17, Nr. 10, pp.
1747-1758, XP000855475, ISSN: 0733-8716 Sections I and II
abstract.**
Liew
Barton et al.
Wallace et al. ............ .. 375/267
Take
Gorsuch et al.
Gruenheid, R. et al: “Adaptive Modulcation and Multiple Access for
the OFDM Transmission Technique,” Wireless Personal Communi
cations, Kluwer Academic Publishers, NL, vol. 13, NR. 1/2, Year
........ .. 455/452.1
Bohnke et al.
2000, pp. 5-13 XP000894156, ISSN: 0929-6212.**
Motegi, M. et al.: Optimum Band Allocation According to Subband
Yan et al. .................. .. 370/328
Condition for BST-OFDM 11th IEEE International Symposium on
Bohnke
Jones, IV et al.
Personal Indoor and Modile Radio Communications, vol. 2, Sep.
Uesugi
ISBN: 0-7803-6463-5.**
Li et al. .................... .. 455/450
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, NY, USA, ISSN: 1053-587X.**
Hanaoka et al.
Hadad ...................... .. 370/203
Wikman et al.
Ahmed
Onggosanusi et al.
Goel et al.
Li et al.
Chayat
18-21, 2000, pp. 1236-1240, XP002213669, Piscataway, NJ, USA,
Ye Li, et al.: “Clustered OFDM with channel estimation for high rate
wireless data,” Mobile Multimedia Communications, 1999.
(MOMUC ’99). 1999 IEEE International Workshop on San Diego,
CA, USA, USA, IEEE, US, Nov. 15, 1999, p. 43-50, XP010370695,
ISBN: 0-7803-5904-6.**
US 7,454,212 B2
Page 3
Nogueroles, R. et al.: Improved Performance of a Random OFDMA
Wong et al. “Multiuser OFDM With Adaptive Subcarrier, Bit, and
Mobile Communications System: Vehicular Technology Confer
ence, 1998. VTC 98. 48th IEEE Ottawa, Ontario, Canada, May
18-21, 1998, pp. 2502-2506, XP010288120, ISBN: 0-7803-4320-4.
tions. IEEE. NeWYork, US, 1999, vol. 17. NR. 10, pp. 1747-1758.
Mexican Of?ce Action issued for PNa/2003/005311 dated Mar. 31,
**
KinugaWa, Y.et al.: “Frequency and Time Division Multiple Access
With Demand-Assignment Using Multicarrier Modulation for Indoor
Wireless Communications Systems,” IEICE Transactions on Com
munications, Institute of Electronics Information and Comm. Eng.
Tokyo, Japan, vol. E77-B, NR. 3, Mar. 1994, pp. 396-402,
XP000451014, ISSN: 0916-8516.**
Vittoria Mignone et al. “CD3-OFDM: A Novel Demodulation
Scheme for Fixed and Mobile Receivers,” IEEE Transactions on
Communications, Sep. 1996, vol. 44, No. 9.
Power Allocation”, IEEE Journal on Selected Areas in Communica
2006.
Ye Li et al.; “Clustered OFDM With Channel Estimation for High
Rate Wireless Data”; Mobile Multimedia Communications, 1999.
(MoMuC’99) 1999 IEEE International Workshop on Nov. 15-17,
1999; pp. 43-50.
Korean of?ce Action issued for 2003 -7007962 dated Apr. 28, 2006.
Korean Of?ce Action issued for 2003-7007963 dated Apr. 29, 2006.
Of?ce Action issued for Korean Patent Application No. 2003
7007961, dated Sep. 27, 2006.
* cited by examiner
US. Patent
Nov. 18, 2008
Sheet 1 of7
Subcarrier
US 7,454,212 B2
Cluster
FIG. 1A
Cluster A
Cluster B
f
Pilot OFDM
Symbols
201
t
Occupied Clusters
a. Cell A
(A)
f
201
t
b. Cell B
(B)
f
201
t
FIG. 2
0. Cell (3
(C)
US. Patent
Nov. 18, 2008
Sheet 2 of7
US 7,454,212 B2
Periodically Broadcast Pilot
/ 101
OFDM Symbols to Subscribers
l
Subscriber(s) Continuously Monitors
Pilot Symbols/Measures SlNR and/0r V102
Other Parameters
l
Retraining
Each Subscriber Selects One or More
Clusters for Each Base Station
Needed
?
‘
l
Base Station Selects One or More
_/104
Clusters for Each Subscriber
l
Base Station Noti?es the Subscriber
Regarding Cluster Allocation
FIG. 1B
~105
US. Patent
Nov. 18, 2008
Sheet 3 of7
US 7,454,212 B2
Channel/Interference s-/ 301
—-> Estimation in Pilot
Penods
+
Traf?c/mterference
—-> Analysis in Date
( 303
K 304
_, Cluster Ordering
Request Selected
_>
and Rate
——> Clusters and Coding! —->
Prediction
Modulation Rates
Periods
302
3
Per-cluster SlNR $01
—~>
Estimation in
—-—>
Pilot Periods
402
Per-cluster
f 405
Cluster Ordering!
‘- 406
404 sgllilcgoanngissse?n
—> Power Calculation
in Pilot Periods
I
Difference
-
Request Selected
—> Clusters and Coding! —>
Modulation Rates
Per-cluster
——> Power Calculation
in Data Periods
501 \
Cluster
|D1
502 \
A
4
503 \
Cluster
IDZ
SlNRl
504 \
504 q
504 -\
Cluster
IDs
SlNR2
Group 3
SlNR3
Group 4
/’i x
K
Group 2
FIG. 6
\
US. Patent
Nov. 18, 2008
Sheet 5 of7
US 7,454,212 B2
1-8: Divelerse Clusters
9-16: Piaijn Clusters
f
>
123455 8 9
10 12314b|bl8 11
H
12 123-4515 B 13
14 123415167'815
16
a. CellA
f
>
123455 8 9
10 8123-4511)] 11
H
12 78123415613
14 5181234515
16
b. CellB
f
>
bib/81234 9
10 4516/6123 11
V1
12 341 b 12 13
14 234155! 11 15
16
c.Ce1lC
Subcarner1
Subcarrier2
f
Time1
Time2
Time3
Time4
I
a. Cell A
t
b. Cell B
FIG. 10
US. Patent
Nov. 18, 2008
Sheet 6 of7
US 7,454,212 B2
Channel/Interference \/1101
Variation Detection
1102
Any
»
Signi?cant Variation
Detected
?
1104)
(1103
Select Diversity
Select Coherence
Clusters
Clusters
f
>
1234mm?l
Vt
10 1234156! 9}? 12 12345.0 9}? 14 1234M)! 9H1 16
a. CellA
FIG. 12
US. Patent
Nov. 18, 2008
Sheet 7 of7
US 7,454,212 B2
User Data Buffer Information
USel’ 1 "" N
Multi-user Data
—_7__>
,\ 1302
Buffer
Admission Control
Cluster Allocation and
Load Scheduling —-—-——>
Controller
‘
Mu|tip|exer
f 1303
I I I I I Cluster1~M
Multi-cluster
Transmission and
slNR/Rate
Receiving Buffer
~/\ lndrces
6
f 1304
>
OFDM Transceiver
Control Signal/
Cluster‘Allocation
\/ 1305
OFDM Signa|
1312
FIG. 13
US 7,454,212 B2
1
2
OFDMA WITH ADAPTIVE
SUBCARRIER-CLUSTER CONFIGURATION
AND SELECTIVE LOADING
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 interfer
CROSS REFERENCE TO RELATED
APPLICATION
ence.
One approach to subcarrier allocation for OFDMA is a
joint optimiZation operation, not only requiring the activity
This is a continuing application of application Ser. No.
09/738,086, entitled “OFDMA WITH ADAPTIVE SUB
and channel knowledge of all the subscribers in all the cells,
but also requiring frequent rescheduling every time an exist
CARRIER-CLUSTER CONFIGURATION AND SELEC
ing subscribers is dropped off the network or a new subscrib
ers is added onto the network. This is often impractical in real
TIVE LOADING,” ?led Dec. 15, 2000, the disclosure of
which is hereby incorporated herein by reference thereto.
wireless system, mainly due to the bandwidth cost for updat
ing the subscriber information and the computation cost for
FIELD OF THE INVENTION
the joint optimization.
The invention relates to the ?eld of wireless communica
tions; more particularly, the invention relates to multi-cell,
SUMMARY OF THE INVENTION
multi-subscriber wireless systems using orthogonal fre
quency division multiplexing (OFDM).
20
BACKGROUND OF THE INVENTION
orthogonal frequency division multiple access (OFDMA). In
Orthogonal frequency division multiplexing (OFDM) is an
e?icient modulation scheme for signal transmission over fre
quency-selective channels. In OFDM, a wide bandwidth is
divided into multiple narrow-band subcarriers, which are
25
arranged to be orthogonal with each other. The signals modu
lated on the subcarriers are transmitted in parallel. For more
information, see Cimini, Jr., “Analysis and Simulation of a
Digital Mobile Channel Using Orthogonal Frequency Divi
A method and apparatus for subcarrier selection for sys
tems is described. In one embodiment, the system employs
30
one embodiment, a method for subcarrier selection comprises
a subscriber measuring channel and interference information
for subcarriers based on pilot symbols received from a base
station, the subscriber selecting a set of candidate subcarriers,
providing feedback information on the set of candidate sub
carriers to the base station, and receiving an indication of
subcarriers of the set of subcarriers selected by the base
station for use by the subscriber.
sion Multiplexing,” IEEE Trans. Commun., vol. COM-33,
no. 7, Jul. 1985, pp. 665-75; Chuang and Sollenberger,
BRIEF DESCRIPTION OF THE DRAWINGS
“Beyond 3G: Wideband Wireless Data Access Based on
OFDM and Dynamic Packet Assignment,” IEEE Communi
cations Magazine, Vol. 38, No. 7, pp. 78-87, July 2000.
35
One way to use OFDM to support multiple access for
multiple subscribers is through time division multiple access
which, however, should not be taken to limit the invention to
(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
the speci?c embodiments, but are for explanation and under
standing only.
40
access, using the basic format of OFDM. In OFDMA, mul
tiple subscribers simultaneously use different subcarriers, in a
fashion similar to frequency division multiple access
(FDMA). For more information, see Sari and Karam,
“Orthogonal Frequency-Division Multiple Access and its
FIG. 1B is a ?ow diagram of one embodiment of a process
FIG. 2 illustrates time and frequency grid of OFDM sym
45
“Improved Performance of a Random OFDMA Mobile Com
50
2502-2506.
Multipath causes frequency-selective fading. The channel
group-based cluster allocation.
55
provide high channel gains for another subscriber. Therefore,
FIG. 9 illustrates different cluster formats for coherence
cate the subcarriers to subscribers so that each subscriber
clusters and diversity clusters.
FIG. 10 illustrates diversity clusters with subcarrier hop
60
ping.
FIG. 11 illustrates intelligent switching between diversity
clusters and coherence clusters depending on subscribers
Within one cell, the subscribers can be coordinated to have
interference. However, with aggressive frequency reuse plan,
e.g., the same spectrum is used for multiple neighboring cells,
FIG. 8 illustrates frequency reuse and interference in a
multi-cell, multi-sector network.
it is advantageous in an OFDMA system to adaptively allo
different subcarriers in OFDMA. The signals for different
subscribers canbe made orthogonal and there is little intracell
FIG. 4 illustrates one example of FIG. 3.
FIG. 5 illustrates one embodiment of a format for arbitrary
cluster feedback.
FIG. 6 illustrates one embodiment of a partition the clusters
into groups.
FIG. 7 illustrates one embodiment of a feedback format for
gains are different for different subcarriers. Furthermore, the
channels are typically uncorrelated for: different subscribers.
enjoys a high channel gain. For more information, see Wong
et al., “Multiuser OFDM with Adaptive Subcarrier, Bit and
Power Allocation,” IEEE J. Select. Areas Commun., Vol.
17(10), pp. 1747-1758, October 1999.
bols, pilots and clusters.
FIG. 3 illustrates subscriber processing.
Telecommunications, Vol. 9(6), pp. 507-516, November/De
cember 1998 and Nogueroles, Bossert, Donder, and Zyablov,
The subcarriers that are in deep fade for one subscriber may
FIG. 1A illustrates subcarriers and clusters.
for allocating subcarriers.
Application to CATV Networks,” European Transactions on
munication System,”, Proceedings of IEEE VTC’98, pp.
The present invention will be understood more fully from
the detailed description given below and from the accompa
nying drawings of various embodiments of the invention,
mobility.
65
FIG. 12 illustrates one embodiment of a recon?guration of
cluster classi?cation.
FIG. 13 illustrates one embodiment of a base station.
US 7,454,212 B2
3
4
DETAILED DESCRIPTION OF THE PRESENT
INVENTION
feedback from the subscribers to the base station, and algo
rithms 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.
A distributed, reduced-complexity approach for subcarrier
allocation is described. The techniques disclosed herein are
It Will be apparent, hoWever, to one skilled in the art, that the
described using OFDMA (clusters) as an example. However,
present invention may be practiced Without these speci?c
they are not limited to OFDMA-based systems. The tech
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.
niques apply to multi-carrier systems in general, Where, for
example, a carrier can be a cluster in OFDMA, a spreading
Some portions of the detailed descriptions Which folloW
are presented in terms of algorithms and symbolic represen
code in CDMA, an antenna beam in SDMA (space-division
multiple access), etc. In one embodiment, subcarrier alloca
tion is performed in each cell separately. Within each cell, the
allocation for individual subscribers (e.g., mobiles) is also
tations 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, con
ceived to be a self-consistent sequence of steps leading to a
made progressively as each neW subscriber is added to the
system as opposed to joint allocation for subscribers Within
each cell in Which allocation decisions are made taking into
account all subscribers in a cell for each allocation.
For doWnlink channels, each subscriber ?rst measures the
desired result. The steps are those requiring physical manipu
lations of physical quantities. Usually, though not necessarily,
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))
20
these quantities take the form of electrical or magnetic signals
capable of being stored, transferred, combined, compared,
and feeds back the information on these candidate subcarriers
and otherWise manipulated. It has proven convenient at times,
to the base station. The feedback may comprise channel and
principally for reasons of common usage, to refer to these
signals as bits, values, elements, symbols, characters, terms,
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 por
tion 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.
25
It should be borne in mind, hoWever, that all of these and
similar terms are to be associated With the appropriate physi
cal quantities and are merely convenient labels applied to
these quantities. Unless speci?cally stated otherWise as
30
Upon receiving the information from the subscriber, the
processes of a computer system, or similar electronic com
35
or hoW long a subscriber has been Waiting to send informa
tion. 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 subcar
rier 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
40
tem memories or registers or other such information storage,
transmission or display devices.
The present invention also relates to apparatus for perform
constructed for the required purposes, or it may comprise a
general purpose computer selectively activated or recon?g
ured by a computer program stored in the computer. Such a
computer program may be stored in a computer readable
storage medium such as, but is not limited to, any type of disk
subcarriers that it ?nds favorable to use. For example, if the
SINR is less than a certain threshold (e.g., 12 dB), quadrature
including ?oppy disks, optical disks, CD-ROMs, and mag
netic-optical disks, read-only memories (ROMs), random
phase shift keying (QPSK) modulation is used; otherwise, 16
quadrature amplitude modulation (QAM) is used. Then the
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 sys
tem bus.
55
The algorithms and displays presented herein are not inher
ently related to any particular computer or other apparatus.
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 per
form the required method steps. The required structure for a
60
as the traf?c load information on the uplink subcarriers are
variety of these systems Will appear from the description
beloW. In addition, the present invention is not described With
used for uplink subcarrier allocation.
For either direction, the base station makes the ?nal deci
reference to any particular programming language. It Will be
appreciated that a variety of programming languages may be
sion of subcarrier allocation for each subscriber.
In the folloWing description, a procedure of selective sub
carrier allocation is also disclosed, including methods of
channel and interference sensing, methods of information
puting device, that manipulates and transforms data repre
sented as physical (electronic) quantities Within the computer
system’s registers and memories into other data similarly
represented as physical quantities Within the computer sys
ing the operations herein. This apparatus may be specially
selection of coding/modulation rates. Such coding/modula
tion rates may be speci?ed by the subscriber When specifying
base station informs the subscribers about the subcarrier allo
cation 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 l0-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
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
base station further selects the subcarriers among the candi
dates, utiliZing additional information available at the base
station, e.g., the tra?ic load information on each subcarrier,
amount of tra?ic requests queued at the base station for each
frequency band, Whether frequency bands are overused, and/
numbers, or the like.
65
used to implement the teachings of the invention as described
herein.
A machine-readable medium includes any mechanism for
storing or transmitting information in a form readable by a
US 7,454,212 B2
5
6
machine (e. g., a computer). For example, a machine readable
may be particularly useful in diversity clusters Where the
Weighting applied to the subcarriers may be different.
medium includes read only memory (“ROM”); random
access memory (“RAM”); magnetic disk storage media; opti
The feedback of information from each subscriber to the
base station contains a SINR value for each cluster and also
cal storage media; ?ash memory devices; electrical, optical,
acoustical or other form of propagated signals (e.g., carrier
indicates the coding/modulation rate that the subscriber
Waves, infrared signals, digital signals, etc.); etc.
Subcarrier Clustering
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 sub
The techniques described herein are directed to subcarrier
allocation for data tra?ic 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
scriber. 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
channels, and time and frequency synchronization channels.
FIG. 1A illustrates multiple subcarriers, such as subcarrier
101, and cluster 102. A cluster, such as cluster 102, is de?ned
as a logical unit that contains at least one physical subcarrier,
station further selects one or more clusters for the subscriber
among the candidates (processing block 104). The base sta
tion may utiliZe additional information available at the base
station, e.g., the traf?c load information on each subcarrier,
amount of tra?ic requests queued at the base station for each
as shoWn in FIG. 1A. A cluster can contain consecutive or
disjoint subcarriers. The mapping betWeen a cluster and its
subcarriers can be ?xed or recon?gurable. In the latter case,
the base station informs the subscribers When the clusters are
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
rede?ned. In one embodiment, the frequency spectrum
includes 512 subcarriers and each cluster includes four con
secutive subcarriers, thereby resulting in 128 clusters.
An Exemplary Subcarrier/Cluster Allocation Procedure
can use this information in subcarrier allocation to reduce
25
FIG. 1B is a How 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.
inter-cell interference.
After cluster selection, the base station noti?es the sub
scriber about the cluster allocation through a doWnlink com
mon control channel or through a dedicated doWnlink traf?c
30
Referring to FIG. 1B, each base station periodically broad
casts pilot OFDM symbols to every subscriber Within its cell
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
(or sector) (processing block 101). The pilot symbols, often
referred to as a sounding sequence or signal, are knoWn to 35 station using a dedicated traf?c channel (e.g., one or more
prede?ned uplink access channels).
both the base station and the subscribers. In one embodiment,
each pilot symbol covers the entire OFDM frequency band
Width. 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
In one embodiment, the base station allocates all the clus
ters to be used by a subscriber at once. In an alternative
embodiment, the base station ?rst allocates multiple clusters,
40
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
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
tra?ic, of each cluster (processing block 102). Based on this
45
good performance (e.g., high SINR and loW traf?c loading)
auxiliary clusters from the subscribers.Altematively, the base
relative to each other and feeds back the information on these
50
55
ters 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 sub
scriber.
ters they Would prefer to use based on the measured param
eters.
From time to time, processing logic performs retraining by
In one embodiment, each subscriber measures the SIR of
each subcarrier cluster and reports these SINR measurements
station may assign auxiliary clusters to one or more subscrib
ers before allocating basic clusters to other subscribers. For
example, a base station may allocate basic and auxiliary clus
mance. LikeWise, a cluster utiliZation factor less than 50%
may be indicative of good performance. Each subscriber
selects the clusters With relatively better performance than
others. The selection results in each subscriber selecting clus
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 ?rst ensures the assignment of the basic clusters to the
subscribers and then tries to satisfy further requests on the
information, each subscriber selects one or more clusters With
candidate clusters to the base station through prede?ned
uplink access channels (processing block 103). For example,
SINR values higher than 10 dB may indicate good perfor
referred to herein as the basic clusters, to establish a data link
60
repeating the process described above (processing block
to their base station through an access channel. The SINR
106). The retraining may be performed periodically. This
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
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 per
forms the reselection and informs the subscriber about the
neW cluster allocation. Retraining can be initiated by the base
65
US 7,454,212 B2
7
8
station, and in Which case, the base station requests a speci?c
subscriber to report its updated cluster selection.
Retraining can also be initiated by the subscriber When it
observes channel deterioration.
and modulation rate that a subscriber desires to use. Note that
even for the same subscribers, different clusters can have
different modulation/coding rates.
Pilot symbols serve an additional purpose in determining
interference among the cells. Since the pilots of multiple cells
Adaptive Modulation and Coding
are broadcast at the same time, they Will interfere With each
In one embodiment, different modulation and coding rates
other (because they occupy the entire frequency band. This
are used to support reliable transmission over channels With
collision of pilot symbols may be used to determine the
different SINR. Signal spreading over multiple subcarriers
amount of interference as a Worst case scenario. Therefore, in
may also be used to improve the reliability at very loW SINR.
one embodiment, the above SINR estimation using this
method is conservative in that the measured interference level
is the Worst-case scenario, assuming that all the interference
sources are on. Thus, the structure of pilot symbols is such
that it occupies the entire frequency band and causes colli
An example coding/modulation table is given beloW in
Table 1.
TABLE 1
Scheme
Modulation
sions among different cells for use in detecting the Worst case
Code Rate
0
1
2
3
QPSK, ‘A; Spreading
QPSK, 1A1 Spreading
QPSK, 1/2 Spreading
QPSK
4
8PSK
2/3
5
6
16QAM
64QAM
SINR in packet transmission systems.
During data tra?ic periods, the subscribers can determine
1/2
1/2
1/2
1/2
%
5/6
In the example above, 1/8 spreading indicates that one
QPSK modulation symbol is repeated over eight subcarriers.
the level of interference again. The data tra?ic periods are
used to estimate the intra-cell tra?ic as Well as the inter-cell
20
25
The repetition/spreading may also be extended to the time
domain. For example, one QPSK symbol can be repeated
over four subcarriers of tWo OFDM symbols, resulting also
1/8 spreading.
The coding/modulation rate can be adaptively changed
30
according to the channel conditions observed at the receiver
after the initial cluster allocation and rate selection.
interference level. Speci?cally, the poWer difference during
the pilot and tra?ic periods may be used to sense the (intra
cell) tra?ic loading and inter-cell interference to select the
desirable clusters.
The interference level on certain clusters may be loWer,
because these clusters may be unused in the neighboring
cells. For example, in cell A, With respect to clusterA there is
less interference because clusterA is unused in cell B (While
it is used in cell C). Similarly, in cell A, cluster B Will expe
rience loWer interference from cell B because cluster B is
used in cell B but not in cell C.
The modulation/coding rate based on this estimation is
robust to frequent interference changes resulted from bursty
packet transmission. This is because the rate prediction is
Pilot Symbols and SINR Measurement
In one embodiment, each base station transmits pilot sym
35
bols simultaneously, and each pilot symbol occupies the
entire OFDM frequency bandWidth, as shoWn in FIGS. 2A-C.
Referring to FIG. 2A-C, pilot symbols 201 are shoWn travers
ing the entire OFDM frequency bandWidth for cells A, B and
C, respectively. In one embodiment, each of the pilot symbols
based on the Worst case situation in Which all interference
sources are transmitting.
In one embodiment, a subscriber utiliZes the information
available from both the pilot symbol periods and the data
traf?c periods to analyZe the presence of both the intra-cell
traf?c load and inter-cell interference. The goal of the sub
40
scriber is to provide an indication to the base station as to
have a length or duration of 128 microseconds With a guard
those clusters that the subscriber desires to use. Ideally, the
time, the combination of Which is approximately 152 micro
seconds. After each pilot period, these are a predetermined
number of data periods folloWed by another set of pilot sym
result of the selection by the subscriber is clusters With high
channel gain, loW interference from other cells, and high
availability. The subscriber provides feedback information
that includes the results, listing desired clusters in order or not
bols. In one embodiment, there are four data periods used to
45
transmit data after each pilot, and each of the data periods is
as described herein.
152 microseconds.
A subscriber estimates the SINR for each cluster from the
pilot symbols. In one embodiment, the subscriber ?rst esti
mates the channel response, including the amplitude and
FIG. 3 illustrates one embodiment of subscriber process
ing. The processing is performed by processing logic that
may comprise hardWare (e.g., dedicated logic, circuitry, etc.),
50
softWare (such as that Which runs on, for example, a general
phase, as if there is no interference or noise. Once the channel
purpose computer system or dedicated machine), or a com
is estimated, the subscriber calculates the interference/noise
from the received signal.
The estimated SINR values may be ordered from largest to
smallest SINRs and the clusters With large SINR values are
bination of both.
Referring to FIG. 3, channel/interference estimation pro
selected. In one embodiment, than selected clusters have
SINR values that are larger than the minimum SINR Which
cessing block 301 performs channel and interference estima
tion in pilot periods in response to pilot symbols. Traf?c/
interference analysis processing block 302 performs traf?c
and interference analysis in data periods in response to signal
still alloWs a reliable (albeit loW-rate) transmission supported
by the system. The number of clusters selected may depend
information and information from channel/interference esti
mation block 301.
on the feedback bandWidth and the request transmission rate.
In one embodiment, the subscriber alWays tries to send the
information about as many clusters as possible from Which
the base station chooses.
55
60
Cluster ordering and rate prediction processing block 303
is coupled to outputs of channel/interference estimation pro
cussed above. By using an appropriate SINR indexing
cessing block 301 and traf?c/ interference analysis processing
block 302 to perform cluster ordering and selection along
With rate prediction.
The output of cluster ordering processing block 303 is
input to cluster request processing block 304, Which requests
scheme, an SINR index may also indicate a particular coding
clusters and modulation/coding rates. Indications of these
The estimated SINR values are also used to choose the
appropriate coding/modulation rate for each cluster as dis
65
US 7,454,212 B2
10
selected, the subscriber requests the selected clusters and the
coding/modulation rates With processing block 406.
More speci?cally, in one embodiment, the signal poWer of
selections are sent to the base station. In one embodiment, the
SINR on each cluster is reported to the base station through an
access channel. The information is used for cluster selection
to avoid clusters With heavy intra-cell tra?ic loading and/or
strong interference from other cells. That is, a neW subscriber
may not be allocated use of a particular cluster if heavy
01
each cluster during the pilot periods is compared With that
during the tra?ic periods, according to the folloWing:
intra-cell traf?c loading already exists With respect to that
cluster. Also, clusters may not be allocated if the interference
is so strong that the SINR only alloWs for loW-rate transmis
PN, With no signal and interference
sion or no reliable transmission at all.
Pg + PN, With signal only
The channel/interference estimation by processing block
P0 =
.
.
P, + PN , With interference only
301 is Well-knoWn in the art by monitoring the interference
P; + P, + PN, With both signal and interference
that is generated due to full-bandWidth pilot symbols being
simultaneously broadcast in multiple cells. The interface
Pg + P1, With no signal and interference
information is forWarded to processing block 302 Which uses
P], with signal only
the information to solve the folloWing equation:
P5, With interference only
0, With both signal and interference
Where Sl- represents the signal for subcarrier (freq. band) i, II.
is the interference for subcarrier i, nl- is the noise associated
With subcarrier i, and yl- is the observation for subcarrier i. In
the case of 512 subcarriers, i may range from 0 to 511. The I1
and nl- are not separated and may be considered one quantity.
The interference/noise and channel gain H. are not knoW.
20
Where PP is the measured poWer corresponding to each cluster
during pilot periods, PD is the measured poWer during the
traf?c periods, PS is the signal power, P, is the interference
25
poWer, and PN is the noise poWer.
In one embodiment, the subscriber selects clusters With
During pilot periods, the signal Sl- representing the pilot sym
relatively large PP/ (PP-PD) (e.g., larger than a threshold such
bols, and the observation yl. are knoWns, thereby alloWing
as 10 dB) and avoids clusters With loW PP/ (PP-PD) (e. g.,
determination of the channel gain HZ- for the case Where there
is no interference or noise. Once this is knoWn, it may be
plugged back into the equation to determine the interference/
noise during data periods since Hi, S1- and yl- are all knoWn.
The interference information from processing blocks 301
30
loWer than a threshold such as 10 dB) When possible.
Alternatively, the difference may be based on the energy
difference betWeen observed samples during the pilot period
and during the data tra?ic period for each of the subcarriers in
a cluster such as the folloWing:
and 302 are used by the subscriber to select desirable clusters.
In one embodiment, using processing block 303, the sub
scriber orders clusters and also predicts the data rate that
35
Thus, the subscriber sums the differences for all subcarriers.
Depending on the actual implementation, a subscriber may
use the folloWing metric, a combined function of both SINR
and PP-PD, to select the clusters:
Would be available using such clusters. The predicted data
rate information may be obtained from a look up table With
precalculated data rate values. Such a look up table may store
the pairs of each SINR and its associated desirable transmis
sion rate. Based on this information, the subscriber selects
clusters that it desires to use based on predetermined perfor
40
Where I is a function of the tWo inputs. One example of I is
mance criteria. Using the ordered list of clusters, the sub
Weighted averaging (e.g., equal Weights). Alternatively, a
scriber requests the desired clusters along With coding and
modulation rates knoWn to the subscriber to achieve desired
data rates.
FIG. 4 is one embodiment of an apparatus for the selection
of clusters based on poWer difference. The approach uses
subscriber selects a cluster based on its SINR and only uses
45
lar SINR. The difference may be smaller than a threshold
(e.g., 1 dB).
Both the measurement of SINR and PP—PD canbe averaged
information available during both pilot symbol periods and
data tra?ic periods to perform energy detection. The process
ing of FIG. 4 may be implemented in hardWare, (e.g., dedi
cated logic, circuitry, etc.), softWare (such as is run on, for
example, a general purpose computer system or dedicated
over time to reduce variance and improve accuracy. In one
50
55
cluster in pilot periods, poWer calculation processing block
402 to perform poWer calculations for each cluster in pilot
periods, and poWer calculation processing block 403 to per
form poWer calculations in data periods for each cluster.
Subtractor 404 subtracts the poWer calculations for data peri
ods from processing block 403 from those in pilot periods
from processing block 402. The output of subtractor 404 is
input to poWer difference ordering (and group selection) pro
cessing block 405 that performs cluster ordering and selec
embodiment, a moving-average time WindoW is used that is
long enough to average out the statistical abnormity yet short
enough to capture the time-varying nature of channel and
interference, e.g., 1 millisecond.
machine), or a combination of both.
Referring to FIG. 4, a subscriber includes SINR estimation
processing block 401 to perform SINR estimation for each
the poWer difference PP—PD to distinguish clusters With simi
Feedback Format for DoWnlink Cluster Allocation
In one embodiment, for the doWnlink, the feedback con
tains both the indices of selected clusters and their SINR. An
exemplary format for arbitrary cluster feedback is shoWn in
60
FIG. 5. Referring to FIG. 5, the subscriber provides a cluster
index (ID) to indicate the cluster and its associated SINR
value. For example, in the feedback, the subscriber provides
cluster. ID1 (501) and the SINR for the cluster, SINRl (502),
cluster ID2 (503) and the SINR for the cluster, SINR2 (504),
and cluster ID3 (505), and the SINR for the cluster, SINR3
tion based on SINR and the poWer difference betWeen pilot
(506), etc. The SINR for the cluster may be created using an
average of the SINRs of the subcarriers. Thus, multiple arbi
periods and data periods. Once the clusters have been
trary clusters can be selected as the candidates. As discussed
65
US 7,454,212 B2
11
12
above, the selected clusters can also be ordered in the feed
back to indicate priority. In one embodiment, the subscriber
may form a priority list of clusters and sends back the SINR
information in a descending order of priority.
Typically, an index to the SINR level, instead of the SINR
cluster allocation. Group-based cluster allocation may also be
used to reduce inter-cell interference.
After receiving the pilot signal from the base station, a
subscriber sends back the channel information on one or more
SINR indexing to indicate 8 different rates of adaptive cod
cluster groups, simultaneously or sequentially. In one
embodiment, only the information on some of the groups is
sent back to the base station. Many criteria can be used to
choose and order the groups, based on the channel informa
ing/modulation.
tion, the inter-cell interference levels, and the intra-cell tra?ic
itself is suf?cient to indicate the appropriate coding/modula
tion for the cluster. For example, a 3-bit ?eld can be used for
load on each cluster.
In one embodiment, a subscriber ?rst selects the group With
An Exemplary Base Station
The base station assigns desirable clusters to the subscriber
making the request. In one embodiment, the availability of the
the best overall performance and then feedbacks the SINR
information for the clusters in that group. The subscriber may
cluster for allocation to a subscriber depends on the total
tra?ic load on the cluster. Therefore, the base station selects
order the groups based on their number of clusters for Which
the SINR is higher than a prede?ned threshold. By transmit
ting the SINR of all the clusters in the group sequentially, only
the group index instead of all the cluster indices, needs to be
transmitted. Thus, the feedback for each group generally
the clusters not only With high SINR, but also With loW tra?ic
load.
FIG. 13 is a block diagram of one embodiment of a base
station. Referring to FIG. 13, cluster allocation and load
scheduling controller 1301 (cluster allocator) collects all the
necessary information, including the doWnlink/uplink SINR
of clusters speci?ed for each subscriber (e.g., via SINR/rate
indices signals 1313 received from OFDM transceiver 1305)
20
and user data, queue fullness/traf?c load (e.g., via user data
buffer information 1311 from multi-user data buffer 1302).
Using this information, controller 1301 makes the decision on
cluster allocation and load scheduling for each user, and
stores the decision information in a memory (not shoWn).
Controller 1301 informs the subscribers about the decisions
25
contains tWo types of information: the group index and the
SINR value of each cluster Within the group. FIG. 7 illustrates
an exemplary format for indicating a group based cluster
allocation. Referring to FIG. 7, a group ID, ID1, is folloWed
by the SINR values for each of the clusters in the group. This
can signi?cantly reduce the feedback overhead.
Upon receiving the feedback information from the sub
scriber, the cluster allocator at the base station selects mul
tiple clusters from one or more groups, if available, and then
The packet data of User 1~N are stored in the user data
assigns the clusters to the subscriber. This selection may be
performed by an allocation in a media access control portion
of the base station.
Furthermore, in a multi-cell environment, groups can have
different priorities associated With different cells. In one
embodiment, the subscriber’s selection of a group is biased
by the group priority, Which means that certain subscribers
have higher priorities on the usage of some groups than the
other subscribers.
In one embodiment, there is no ?xed association betWeen
buffers 1302. For doWnlink, With the control of controller
1301, multiplexer 1303 loads the user data to cluster data
one subscriber and one cluster group; hoWever, in an altema
tive embodiment there may be such a ?xed association. In an
through control signal channels (e.g., control signal/cluster
30
allocation 1312 via OFDM transceiver 1305). Controller
1301 updates the decisions during retraining.
In one embodiment, controller 1301 also performs admis
sion control to user access since it knoWs the tra?ic load of the
system. This may be performed by controlling user data buff
ers 1302 using admission control signals 1310.
buffers (for Cluster 1~M) Waiting to be transmitted. For the
uplink, multiplexer 1303 sends the data in the cluster buffers
35
40
scriber and one or more cluster groups, the group index in the
feedback information can be omitted, because this informa
tion is knoWn to both subscriber and base station by default.
to the corresponding user buffers. Cluster buffer 1304 stores
the signal to be transmitted through OFDM transceiver 1305
(for doWnlink) and the signal received from transceiver 1305.
In one embodiment, each user might occupy multiple clusters
and each cluster might be shared by multiple users (in a
45
cluster, e.g., the pilot signal shoWs Which clusters have
Group-Based Cluster Allocation
clusters that are in each group as a result of the partitioning. In
one embodiment, the clusters Within each group are spaced
far apart over the entire bandWidth. In one embodiment, the
clusters Within each group are spaced apart farther than the
channel coherence bandWidth, i.e. the bandWidth Within
Which the channel response remains roughly the same. A
typical value of coherence bandWidth is 100 kHZ for many
50
ters are available for neW allocations. For example, the base
station can transmit a pilot sequence 1111 1111 on the sub
carriers of a cluster to indicate that the cluster is available, and
1111-1 -1 -1-1 to indicate the cluster is not available. At the
receiver, the subscriber ?rst distinguishes the tWo sequences
using the signal processing methods Which are Well knoWn in
the art, e.g., the correlation methods, and then estimates the
55
channel and interference level.
With the combination of this information and the channel
characteristics obtained by the subscriber, the subscriber can
prioritize the groups to achieve both high SINR and good load
balancing.
60
cellular systems. This improves frequency diversity Within
each group and increases the probability that at least some of
the clusters Within a group can provide high SINR. The clus
ters may be allocated in groups. Goals of group-based cluster
allocation include reducing the data bits for cluster indexing
thereby reducing the bandWidth requirements of the feedback
channel (information) and control channel (information) for
In another embodiment, the pilot signal sent from the base
station to the subscriber also indicates the availability of each
already been allocated for other subscribers and Which clus
time-division-multiplexing fashion).
In another embodiment, for the doWnlink, the clusters are
partitioned into groups. Each group can include multiple
clusters. FIG. 6 illustrates an exemplary partitioning. Refer
ring to FIG. 6, groups 1-4 are shoWn With arroWs pointing to
implementation having a ?xed association betWeen a sub
In one embodiment, the subscriber protects the feedback
information by using error correcting codes. In one embodi
ment, the SINR information in the feedback is ?rst com
pressed using source coding techniques, e.g., differential
encoding, and then encoded by the channel codes.
65
FIG. 8 shoWs one embodiment of a frequency reuse pattern
for an exemplary cellular set up. Each cell has hexagonal
structure With six sectors using directional antennas at the
US 7,454,212 B2
14
13
base stations. Between the cells, the frequency reuse factor is
one. Within each cell, the frequency reuse factor is 2 Where
the sectors use tWo frequencies alternatively. As shoWn in
FIG. 8, each shaded sector uses half of the available OFDMA
TABLE 3
Cluster usage for the doWnlink of the shaded sectors With
less than 2/3 ofthe full load.
clusters and each unshaded sector uses the other half of the
clusters. Without loss of generality, the clusters used by the
Cluster Usage
Cell A
Cell B
Cell C
shaded sectors are referred to herein as odd clusters and those
used by the unshaded sectors are referred to herein as even
1
2
Group 1
Group 2
Group 3
Group 1
Group 2
Group 3
3
clusters.
Consider the doWnlink signaling With omni-directional
Table 4 shoWs the priority orders for the unshaded sectors,
antennas at the subscribers. From FIG. 8, it is clear that for the
doWnlink in the shaded sectors, Cell A interferes With Cell B,
Which in turn interferes With Cell C, Which in turn interferes
With Cell A, namely, A—>B—>C—>A. For the unshaded sec
tors Cell A interferes With Cell C, Which in turn interferes With
Which are different from those for the shaded sectors, since
the interfering relationship is reversed.
TABLE 4
Cell B, Which in turn interferes With Cell A, namely, A—>C—
Priority ordering for the doWnlink of the unshaded sectors.
>B—>A.
Priority Ordering
Sector A1 receives interference from Sector C1, but its
transmission interferes With Sector B1. Namely, its interfer
Cell A
Cell B
Cell C
1
2
3
Group 1
Group 2
Group 3
Group 2
Group 3
Group 1
Group 3
Group 1
Group 2
20
ence source and the victims With Which it interferes are not the
same. This might cause a stability problem in a distributed
cluster-allocation system using interference avoidance: if a
frequency cluster is assigned in Sector B1 but not in Sector
C1, the cluster may be assigned inA1 because it may be seen
25
Intelligent SWitching betWeen Coherence and Diversity Clus
ters
as clean inA1 . HoWever, the assignment of this clusterA1 can
In one embodiment, there are tWo categories of clusters:
cause interference problem to the existing assignment in B1.
coherence clusters, containing multiple subcarriers close to
each other and diversity clusters, containing multiple subcar
In one embodiment, different cluster groups are assigned
different priorities for use in different cells to alleviate the
aforementioned problem When the tra?ic load is progres
sively added to a sector. The priority orders are jointly
designed such that a cluster can be selectively assigned to
avoid interference from its interference source, While reduc
30
riers With at least some of the subcarriers spread far apart over
the spectrum. The closeness of the multiple subcarriers in
coherence clusters is preferably Within the channel coherence
35
ing, and potentially minimizing, the probability of causing
interference problem to existing assignments in other cells.
Using the aforementioned example, the odd clusters (used
by the shaded sectors) are partitioned into 3 groups: Group 1,
bandWidth, i.e. the bandWidth Within Which the channel
response remains roughly the same, Which is typically Within
100 kHZ for many cellular systems. On the other hand, the
spread of subcarriers in diversity clusters is preferably larger
40
2, 3. The priority orders are listed in Table 2.
than the channel coherence bandWidth, typically Within 100
kHZ for many cellular systems. Of course, the larger the
spread, the better the diversity. Therefore, a general goal in
such cases is to maximiZe the spread.
FIG. 9 illustrates exemplary cluster formats for coherence
clusters and diversity clusters for CellsA-C. Referring to FIG.
TABLE 2
45
9, for cells A-C, the labeling of frequencies (subcarriers)
indicates Whether the frequencies are part of coherence or
Priority ordering for the doWnlink of the shaded sectors.
diversity clusters. For example, those frequencies labeled 1-8
Priority Ordering
Cell A
Cell B
1
Group 1
Group 3
Group 2
2
Group 2
Group 1
Group 3
3
Group 3
Group 2
are diversity clusters and those labeled 9-16 are coherence
clusters. For example, all frequencies labeled 1 in a cell are
Cell C
Group 1
50
55
part of one diversity cluster; all frequencies labeled 2 in a cell
are part of another diversity cluster;, etc., While the group of
frequencies labeled 9 are one coherence cluster, the group of
frequencies labeled 10 are another coherence cluster, etc. The
diversity clusters can be con?gured differently for different
cells to reduce the effect of inter-cell interference through
interference averaging.
Consider Sector A1. First, the clusters in Group 1 are
selectively assigned. If there are still more subscribers
FIG. 9 shoWs example cluster con?gurations for three
neighboring cells. The interference from a particular cluster
demanding clusters, the clusters in Group 2 are selectively
assigned to subscribers, depending on the measured SINR
(avoiding the clusters receiving strong interference from Sec
tor C1). Note that the neWly assigned clusters from Group 2 to
60
Sector A1 shall not cause interference problem in Sector B1,
unless the load in Sector B1 is so heavy that the clusters in
both Group 3 and 1 are used up and the clusters in Group 2 are
also used. Table 3 shoWs the cluster usage When less than 2/3
of all the available clusters are used in SectorA1, B 1, and C1.
65
in one cell are distributed to many clusters in other cells, e. g.,
the interference from Cluster 1 in Cell A are distributed to
Cluster 1, 8, 7, 6 in Cell B. This signi?cantly reduces the
interference poWer to any particular cluster in Cell B. Like
Wise, the interference to any particular cluster in one cell
comes from many different clusters in other cells. Since not
all cluster are strong interferers, diversity clusters, With chan
nel coding across its subcarriers, provide interference diver
sity gain. Therefore, it is advantageous to assign diversity
US 7,454,212 B2
15
16
clusters to subscribers that are close (e.g., Within the coherent
bandwidth) to the cell boundaries and are more subject to
inter-cell interference.
station. The channel/interference variation detector measures
the channel (SINR) variation from time to time for each
cluster. For example, in one embodiment, the channel/inter
ference detector measures the poWer difference betWeen pilot
Since the subcarriers in a coherence cluster are consecutive
or close (e.g., Within the coherent bandWidth) to each other,
they are likely Within the coherent bandWidth of the channel
fading. Therefore, the channel gain of a coherence cluster can
vary signi?cantly and cluster selection can greatly improve
the performance. On the other hand, the average channel gain
of a diversity cluster has less of a degree of variation due to the
symbols for each cluster and averages the difference over a
moving WindoW (e.g., 4 time slots). A large difference indi
cates that channel/ interference changes frequently and sub
carrier allocation may be not reliable. In such a case, diversity
clusters are more desirable for the subscriber.
FIG. 11 is a How diagram of one embodiment of a process
inherent frequency diversity among the multiple subcarriers
for intelligent selection betWeen diversity clusters and coher
spread over the spectrum. With channel coding across the
subcarriers Within the cluster, diversity clusters are more
robust to cluster mis-selection (by the nature of diversi?ca
ence clusters depending on subscribers mobility. The process
tion itself), While yielding possibly less gain from cluster
Which runs on, for example, a general purpose computer
selection. Channel coding across the subcarriers means that
system or dedicated machine), or a combination of both.
each codeWord contains bits transmitted from multiple sub
carriers, and more speci?cally, the difference bits betWeen
codeWords (error vector) are distributed among multiple sub
carriers.
More frequency diversity can be obtained through subcar
Referring to FIG. 11, processing logic in the base station
performs channel/ interference variation detection (process
ing block 1101). Processing logic then tests Whether the
is performed by processing logic that may comprise hardWare
(e.g., circuitry, dedicated logic, etc.), softWare (such as that
20
cate that the user is mobile or in a ?xed position close to the
edge of the cell (processing block 1102). If the user is not
mobile or is not in a ?xed position close to the edge of the cell,
processing transitions to processing block 1103 Where pro
rier hopping over time in Which a subscriber occupies a set of
subcarriers at one time slot and another different set of sub
carriers at a different time slot. One coding unit (frame)
contains multiple such time slots and the transmitted bits are
25
encoded across the entire frame.
FIG. 10 illustrates diversity cluster With subcarrier hop
ping. Referring to FIG. 10, there are four diversity clusters in
each of cells A and B shoWn, With each subcarrier in indi
vidual diversity clusters having the same label (1, 2, 3, or 4).
There are four separate time slots shoWn and during each of
the time slots, the subcarriers for each of the diversity clusters
change. For example, in cell A, subcarrier 1 is part of diversity
cluster 1 during time slot 1, is part of diversity cluster 2 during
time slot 2, is part of diversity cluster 3 during time slot 3, and
is part of diversity cluster 4 during time slot 4. Thus, more
interference diversity can be obtained through subcarrier hop
30
during retraining.
The ratio allocation of the numbers of coherence and diver
sity clusters in a cell depends on the ratio of the population of
mobile and ?xed subscribers. When the population changes
as the system evolves, the allocation of coherence and diver
35
sity clusters can be recon?gured to accommodate the neW
system needs. FIG. 12 illustrates a recon?guration of cluster
classi?cation Which can support more mobile subscribers
than that in FIG. 9.
Whereas many alterations and modi?cations of the present
using different hopping patterns for different cells, as shoWn
40
invention Will no doubt become apparent to a person of ordi
nary skill in the art after having read the foregoing descrip
tion, it is to be understood that any particular embodiment
order to achieve better interference averaging through coding.
For static subscribers, such as in ?xed Wireless access, the
channels change very little over time. Selective cluster allo
cessing logic in the base station selects coherence clusters;
otherwise, processing transitions to processing block 1104 in
Which processing logic in the base station selects diversity
clusters.
The selection can be updated and intelligently sWitched
ping overtime, With further interference diversity achieved by
in FIG. 10.
The manner in Which the subscriber changes the subcarri
ers (hopping sequences) can be different for different cells in
results of the channel/interference variation detection indi
shoWn and described by Way of illustration is in no Way
intended to be considered limiting. Therefore, references to
45
details of various embodiments are not intended to limit the
cation using the coherence clusters achieve good perfor
scope of the claims Which in themselves recite only those
mance. On the other hand, for mobile subscribers, the channel
time variance (the variance due to changes in the channel over
time) can be very large. A high-gain cluster at one time can be
in deep fade at another. Therefore, cluster allocation needs to
be updated at a rapid rate, causing signi?cant control over
head. In this case, diversity clusters can be used to provide
extra robustness and to alleviate the overhead of frequent
cluster reallocation. In one embodiment, cluster allocation is
features regarded as essential to the invention.
We claim:
1. A method for subcarrier selection for a system employ
performed faster than the channel changing rate, Which is
often measured by the channel Doppler rate (in HZ), i.e. hoW
many cycles the channel changes per second Where the chan
50
55
nel is completely different after one cycle. Note that selective
cluster allocation can be performed on both coherence and
diversity clusters.
60
In one embodiment, for cells containing mixed mobile and
?xed subscribers, a channel/interference variation detector
can be implemented at either the subscriber or the base sta
tion, or both. Using the detection results, the subscriber and
the base station intelligently selects diversity clusters to
mobile subscribers or ?xed subscribers at cell boundaries,
and coherence clusters to ?xed subscribers close to the base
ing orthogonal frequency division multiple access (OFDMA)
comprising:
65
a subscriber unit measuring channel and interference infor
mation for a plurality of subcarriers based on pilot sym
bols received from a base station;
the subscriber unit selecting a set of candidate subcarriers;
the subscriber unit providing feedback information on the
set of candidate subcarriers to the base station;
the subscriber unit receiving an indication of subcarriers of
the set of subcarriers selected by the base station for use
by the subscriber unit; and
the subscriber unit submitting updated feedback informa
tion, after being allocated the set of subcarriers to be
allocated an updated set of subcarriers, and thereafter the
subscriber unit receiving another indication of the
updated set of subcarriers.
2. The method de?ned in claim 1 further comprising the
subscriber unit sending the indication to the base station.
US 7,454,212 B2
17
18
3. The method de?ned in claim 2 further comprising send
ing an indication of the set of subcarriers selected by the base
station for use by the subscriber unit.
4. The method de?ned in claim 3 further comprising the
base station selecting subcarriers for the subscriber unit based
selected by the ?rst base station for use by the at least one
subscriber unit, and Wherein the subscriber unit submits
updated feedback information after being allocated the
5. The method de?ned in claim 1 further comprising the
set of subscriber units to receive an updated set of sub
carriers and thereafter receives another indication of the
updated set of subcarriers.
19. The apparatus de?ned in claim 18 Wherein each of the
subscriber unit using information from pilot symbol periods
plurality of subscriber units continuously monitors reception
and data periods to measure channel and interference infor
mation.
of the pilot symbols knoWn to the base station and the plural
ity of subscriber units and measures signal -plus-interference
to-noise ratio (SINR) of each cluster of subcarriers.
on inter-cell interference avoidance.
6. The method de?ned in claim 1 Wherein the pilot symbols
occupy an entire OFDM frequency bandWidth.
7. The method de?ned in claim 6 Wherein at least one other
pilot symbol from a different cell transmitted at the same time
as the pilot symbols received from the base station collide
With each other.
8. The method de?ned in claim 1 further comprising the
base station selecting the subcarriers from the set of candidate
subcarriers based on additional information available to the
base station.
9. The method de?ned in claim 8 Wherein the additional
information comprises tra?ic load information on each clus
ter of subcarriers.
10. The method de?ned in claim 9 Wherein the tra?ic load
information is provided by a data buffer in the base station.
11. The method de?ned in claim 1 Wherein the indication
of subcarriers is received via a doWnlink control channel.
12. The method de?ned in claim 1 Wherein the plurality of
subcarriers comprises all subcarriers allocable by a base sta
tion.
13. The method de?ned in claim 1 Wherein providing feed
20. The apparatus de?ned in claim 19 Wherein each of the
plurality of subscriber units measures inter-cell interference,
Wherein the at least one subscriber unit selects candidate
subcarriers based on the inter-cell interference.
21. The apparatus de?ned in claim 20 Wherein the base
station selects subcarriers for the one subscriber unit based on
20
25
inter-cell interference avoidance.
22. The apparatus de?ned in claim 18 Wherein the at least
one subscriber unit uses information from pilot symbol peri
ods and data periods to measure channel and interference
information.
23. The apparatus de?ned in claim 18 Wherein the base
station selects the subcarriers from the set of candidate sub
carriers based on additional information available to the base
30
station.
24. The apparatus de?ned in claim 23 Wherein the addi
tional information comprises traf?c load information on each
cluster of subcarriers.
25. The apparatus de?ned in claim 24 Wherein the traf?c
back information comprises arbitrarily ordering the set of
load information is provided by a data buffer in the base
candidate subcarriers as clusters of subcarriers.
station.
26. The apparatus de?ned in claim 18 Wherein the indica
tion of subcarriers is received via a doWnlink control channel
betWeen the base station and the at least one subscriber unit.
27. The apparatus de?ned in claim 18 Wherein the plurality
of subcarriers comprises all subcarriers allocable by a base
station.
28. The apparatus de?ned in claim 18 Wherein the plurality
of subscriber units provide feedback information that com
prises an arbitrarily ordered set of candidate subcarriers as
clusters of subcarriers.
29. The apparatus de?ned in claim 18 Wherein providing
14. The method de?ned in claim 13 Wherein arbitrarily
order candidate clusters comprise clusters in an order With
most desirable candidate clusters being listed ?rst.
15. The method de?ned in claim 1 Wherein providing feed
35
back information comprises sequentially ordering candidate
clusters.
16. The method de?ned in claim 1 further comprising:
the base station allocating a ?rst portion of the subcarriers
to establish a data link betWeen the base station and the
40
subscriber unit; and then
the base station allocating a second portion of the subcar
riers to the subscriber unit to increase communication
bandWidth.
17. The method de?ned in claim 16 Wherein the base sta
45
feedback information comprises sequentially ordering candi
tion allocates the second portion after allocating each sub
scriber unit in the cell subcarriers to establish a data link
betWeen the base station and said each subscriber unit.
50
18. An apparatus comprising:
a plurality of subscriber units in a ?rst cell operable to
generate feedback information indicating clusters of
subcarriers desired for use by the plurality of subscriber
units; and
station allocates the second portion after allocating each sub
55
a ?rst base station in the ?rst cell, the ?rst base station
operable to allocate OFDMA subcarriers in clusters to
scriber unit in the cell subcarriers to establish a data link
betWeen the base station and said each subscriber unit.
32. A method comprising:
the plurality of subscriber units;
each of said plurality of subscriber units to measure chan
nel and interference information for the plurality of sub
carriers based on pilot symbols received from the ?rst
base station and at least one of the plurality of subscriber
date clusters.
30. The apparatus de?ned in claim 18 Wherein the base
station allocates a ?rst portion of the subcarriers to establish
a data link betWeen the base station and the subscriber unit;
and then allocates a second portion of the subcarriers to the
subscriber unit to increase communication bandWidth.
31. The apparatus de?ned in claim 30 Wherein the base
60
a base station allocating a ?rst portion of a plurality of
subcarriers to establish a data link betWeen the base
station and a subscriber unit; and
the base station allocating a second portion of saidplurality
units to select a set of candidate subcarriers from the
of subcarriers to the subscriber unit to increase commu
plurality of subcarriers, and said at least one subscriber
nication bandWidth, Wherein the base station allocates
the second portion after allocating each subscriber unit
unit to provide feedback information on the set of can
didate subcarriers to the base station and to receive an
indication of subcarriers from the set of subcarriers
65
in the cell subcarriers to establish a data link betWeen the
base station and said each subscriber unit.
US 7,454,212 B2
19
20
33. A base station comprising:
means for allocating a ?rst portion of a plurality of subcar-
cation bandwidth, wherein the base station allocates the
second portion after allocating each subscriber unit in
riers to establish a data link betWeen the base station and
a subscriber unit; and
means for allocating a second portion of said plurality of 5
subcarriers to the subscriber unit to increase communi-
the cell subcarriers to establish a data link betWeen the
base station and said each subscriber unit.
*
Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.
Why Is My Information Online?