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.
*