Adaptix, Inc. v. T-Mobile USA, Inc.

Filing 1

COMPLAINT against T-Mobile USA, Inc. ( Filing fee $ 350 receipt number 0540-3620802.), filed by Adaptix, Inc.. (Attachments: # 1 Civil Cover Sheet, # 2 Exhibit A - U.S. PATENT NO. 7,146,172, # 3 Exhibit B - U.S. PATENT NO. 6,870,808, # 4 Exhibit C - U.S. PATENT NO. 7,573,851, # 5 Exhibit D - U..S. PATENT NO. 6,904,283, # 6 Exhibit E - U.S. PATENT NO. 7,072,315)(Hill, Jack)

EXHIBIT D

1111111111110111111101R1411111111111111111111111111
(12)

United States Patent

(to) Patent No.:
US 6,904,283 B2
(45) Date of Patent:
Jun. 7, 2005

Li et al.
(54) MULTI-CARRIER COMMUNICATIONS
WITH GROUP-BASED SUBCARRIER
ALLOCATION
(75) Inventors: Xiaodong Li, Bellevue, WA (US); Hui
Liu, Sammamish, WA (US); Hujun
Yin, Seattle, WA (US); Guanbin Xing,
Bellevue, WA (US); Fuqi Mu,
Issaquah, WA (US)
(73) Assignee: Adaptix, Inc., Bothell, WA (US)
* ) Notice:

Subject to any disclaimer, the term of this
patent is extended or adjusted under 35
U.S.C. 154(b) by 727 days.

(21) Appl. No.: 09/837,337
(22) Filed:

Apr. 17, 2001

(65)

5,507,034 A
4/1996
5,515,378 A
5/1996
5,555,268 A
9/1996
5,588,020 A * 12/1996
5,708,973 A
1/1998

FOREIGN PATENT DOCUMENTS
DE
EP
EP
EP
EP
FR
GB
JP
WO
WO
WO

198 00 953 Cl
7/1999
0 869 647 A2 * 10/1998
0 926 912 A2
6/1999
0 929 202 Al
7/1999
0 999 658 A2
5/2000
2 777 407 Al
10/1999
2 209 858 A
8/1997
06029922
2/1994
WO 98/16077 A2
4/1998
WO 98/30047 Al
7/1998
WO 02 49305 A2
6/2002

HO4B/7/02

Vittoria Mignone et al., "CD3-OFDM: A Novel Demodulation Scheme for Fixed and Mobile Receivers," IEEE
Transactions on Communications, Sep. 1996, pp.
1144-1151, vol. 44, No. 9, IEEE.

Related U.S. Application Data
Continuation-in-part of application No. 09/738,086, filed on
Dec. 15, 2000.

(51) Int. C1.7

HO4B 7/00; HO4B 1/38;
HO4Q 7/20; HO4M 1/00; HO4J 11/00
(52) U.S. Cl.
455/450; 455/69; 455/447;
455/448; 455/561; 455/550.1; 370/208
(58) Field of Search
375/133, 135,
375/260, 267; 370/203, 208, 210, 482,
484, 431, 319-321, 328, 329, 332, 342,
344, 345; 455/69, 434, 455, 463, 422.1,
447-450, 452.1, 452.2, 453, 42, 500, 512,
513, 102-105
References Cited
U.S. PATENT DOCUMENTS
5,280,630 A
1/1994 Wang
5,479,447 A * 12/1995 Chow et al.
5,504,775 A
4/1996 Chouly et al.

HO4L/27/26

OTHER PUBLICATIONS

US 2003/0169681 Al Sep. 11, 2003

(56)

370/337

(Continued)

Prior Publication Data

(63)

Bodin et al.
Roy, III et al.
Faitouche et al.
Schilling
Ritter

(Continued)
Primary Examiner-William Trost
Assistant Examiner- Meless Zewdu
(74) Attorney, Agent, or Firm-fflakely, Sokoloff, Taylor &
Zafman LLP
(57)

ABSTRACT

A method and apparatus for subcarrier selection for systems
is described. In one embodiment, a method for subcarrier
selection for a system employing orthogonal frequency
division multiple access (OFDMA) comprises partitioning
subcarriers into groups of at least one cluster of subcarriers,
receiving an indication of a selection by the subscriber of
one or more groups in the groups, and allocating at least one
cluster in the one or more groups of clusters selected by the
subcarrier for use in communication with the subscriber.

375/260

119 Claims, 7 Drawing Sheets
Begin

Pededicalty Broadcast Pilot
OFDM Symbols to Subscribers

101

Subscriber(s) Continuously Monitors
Prot Symbols/Measures SINE and/or --102
Other Parameters

Each Subscriber Salads One or More
Clusters for Each Base Station

-103

Base Station Selects One or More
Clusters for Each Subscriber

-- 104

Base Station Notifies the Subsenber
Regarding Cluster Allocation

105

US 6,904,283 B2
Page 2

U.S. PATENT DOCUMENTS
5,726,978 A
3/1998 Frodigh et al.
5,734,967 A
3/1998 Kotzin et al.
5,774,808 A
6/1998 Sarkioja et al.
5,822,372 A * 10/1998 Emami
5,867,478 A
2/1999 Baum et al.
5,886,988 A
3/1999 Yun et al.
5,887,245 A
3/1999 Lindroth et al.
5,909,436 A * 6/1999 Engstrom et al.
5,914,933 A * 6/1999 Cimini et al.
5,933,421 A
8/1999 Alamouti et al.
5,956,642 A * 9/1999 Larsson et al.
5,973,642 A
10/1999 Li et al.
5,991,273 A
11/1999 Ahu-Dayya
6,005,876 A
12/1999 Cimini, Jr. et al.
6,009,553 A * 12/1999 Martinez et al.
6,026,123 A
2/2000 Williams
6,041,237 A
3/2000 Farsakh
6,052,594 A
4/2000 Chuang et al.
6,061,568 A
5/2000 Dent
6,064,692 A
5/2000 Chow
6,064,694 A
5/2000 Clark et al.
6,067,290 A
5/2000 Paulraj et al.
6,108,374 A
8/2000 Balachandran et al.
6,111,919 A * 8/2000 Yonge, III
6,131,016 A
10/2000 Greenstein et al.
6,141,565 A
10/2000 Feuerstein et al.
6,144,696 A
11/2000 Shively et al.
6,226,320 B1
5/2001 Hakkinen et al.
6,282,185 B1 * 8/2001 Hakkinen et al.
6,298,092 B1 10/2001 Heath, Jr. et al.
6,307,851 B1 10/2001 Jung et al
6,327,472 B1 12/2001 Westroos et al.
6,330,460 B1 12/2001 Wong et al.
6,366,195 B1
4/2002 Harel et al.
6,377,632 B1
4/2002 Paulraj et al.
6,377,636 B1
4/2002 Paulraj et al.
6,449,246 B1
9/2002 Barton et al.
6,473,467 B1 10/2002 Wallace et al.
6,477,158 B1 11/2002 Take
6,545,997 B1
4/2003 Bohnke et al.
6,567,383 B1 * 5/2003 Bohnke
6,657,949 B1 12/2003 Jones, IV et al.
6,726,297 B1 * 4/2004 IJesugi
2002/0114269 Al * 8/2002 Onggosanusi et al.
2003/0067890 Al
4/2003 Goel et al.
2003/0169681 Al
9/2003 Li et al.
2003/0169824 Al
9/2003 Chayat

375/260

370/343
370/208
455/449
342/378
370/525
714/784
455/450
455/450
375/219
375/224
370/329
375/260

370/335

370/347
370/280
375/260
370/208

OTHER PUBLICATIONS
Bender et al., CDMA/HDR: A Bandwidth-Efficient HighSpeed Wireless Data Service for Nomadic Users, IEEE
Communications Magazine, Jul. 2000, pp. 70-87.
Tsoulos, G.V., Smart Antennas For Mobile Communication
Systems: Benefits And Challenges, Electronics & Communication Engineering Journal, Apr. 1999, pp. 84-94.
Shad et al., Indoor SDMA Capacity Using a Smart Antenna
Basestation, 1997 IEEE, pp. 868-872.
Farsakh, Christof and Nossek, Josef A., On the Mobile
Radio Capacity Increase Through SDMA, no date (after
1997).

Fnillone 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
Wireless Lans for Multimedia Services: SDMA Protocol
Design, 1994 IEEE, pp. 1326-1332.
Ward, James and Compton, R. Ted, Jr., High Throughput
Slotted ALOHA Packet Radio Networks with Adaptive
Arrays, IEEE Transactions on Communications, Mar. 1993,
pp. 460-470, vol. 41, No. 3.
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, and Power Allocation, IEEE Journal on Selected
Areas in Communications, Oct. 1999, IEEE Inc., New York,
USA, vol. 17, Nr. 10, pp. 1747-1758, XP000854075, ISSN:
0733-8716 Sections I and II abstract.
Gni enheid, R. et al: "Adaptive Modulation and Multiple
Access for the OFDM Transmission Technique", Wireless
Personal Communications, Kluwer Academic Publishers,
NL, vol. 13, NR. 1/2, Year 2000, pp. 5-13 XP000894156,
ISSN: 0929-6212.
Motegi, M. et al.: "Optimum Band Allocation According to
Subband Condition for BST-OFDM" 11th IEEE International Symposium on Personal Indoor and Mobile Radio
Communications, vol. 2, Sep. 18-21,2000, pp. 1236-1240,
XP002213669, Piscataway, NJ, USA, ISBN:
0-7803-6463-5.
Kapoor, S. et al.: "Adaptive Interference Suppression in
Multiuser Wireless OFDM Systems Using Antenna Arrays"
IEEE Transactions on Signal Processing, vol. 47, No. 12,
Dec. 1999, pp. 3381-3391, XP000935422, IEEE, New
York, USA, ISSN: 1053-587X.
Ye Li, et al.: "Clustered OFDM with channel estimation for
high rate wireless data", Mobile Multimedia Communications, 1999. (MOMUC '99). 1999 IEEE International Workshop on San Diego, CA, USA, IEEE, US, Nov. 15,1999, pp.
43-50, XP010370695, ISBN: 0-7803-5904-6.
Nogueroles, R. et al.: "Improved Performance of a Random
OFDMA Mobile Communication System" Vehicular Technology Conference, 1998. VTC 98. 48th IEEE Ottawa,
Ontario, Canada, May 18-21, 1998, pp. 2502-2506,
XP010288120, ISBN: 0-7803-4320-4.
Kinugawa, Y. et al.: "Frequency and Time Division Multiple
Access with Demand-Assignment Using Multicarrier
Modulation for Indoor Wireless Communications Systems",
IEICE Transactions on Communications, Institute of Electronics Information and Comm. Eng. Tokyo, Japan, vol.
E77-B, NR. 3, Mar. 1994, pp. 396-402, XP000451014,
ISSN: 0916-8516.
* cited by examiner

U.S. Patent

Jun. 7, 2005

Sheet 1 of 7

US

Cluster
(-102

Subcarrier
101

111111111111111

FIG. 1A

Cluster A
Cluster B

r

Pilot OFDMI:
Symbols
201
V
t

201

Occupied Clusters
a. Cell A
(A)

1.

1111111, 'NM
111.:
11111C111.111111111. N MI

1111111.11111111111
b. Cell B
(B)

201

.M111111111111111. MIL
M111111•111C1111,

1111111111111111, `MEV
FIG. 2

c. Cell C
(C)

6,904,283 B2

U.S. Patent

Jun. 7, 2005

Sheet 2 of 7

US 6,904,283 B2

Begin )

Periodically Broadcast Pilot
OFDM Symbols to Subscribers

Subscriber(s) Continuously Monitors
Pilot Symbols/Measures SINR and/or
Other Parameters

102

Each Subscriber Selects One or More1
103
Clusters for Each Base Station

Base Station Selects One or More
Clusters for Each Subscriber

Base Station Notifies the Subscriber
Regarding Cluster Allocation

FIG. 1B

k 104

105

U.S. Patent

Jun. 7, 2005

301

H Channel/Interference
Estimation in Pilot
Periods

1 303
Cluster Ordering
and Rate
Prediction

Traffic/Interference
Analysis in Date
Periods

Per-cluster SINR
Estimation in
Pilot Periods

H
)

302

Request Selected
Clusters and Coding/
Modulation Rates

FIG. 3
405

402

Per-cluster
Power Calculation
in Data Periods

502

Cluster
101

r 304
-

r101

Per-cluster
Power Calculation
in Pilot Periods

501

US 6,904,283 B2

Sheet 3 of 7

r 406

Cluster Ordering!
Selection Based on
404
SINR and Power
Difference

Request Selected
Clusters and Coding/
Modulation Rates

403

FIG. 4
503

SINR1

Cluster
ID2

504

504

SINR2

Cluster
ID3

504
SINR3

FIG. 5
Group 3

Y
t

Group 1

Group 4

Group 2

FIG. 6

• • •

U.S. Patent

roup
GIDI

SINR1

Jun. 7, 2005

SINR2

SINR3

US 6,904,283 B2

Sheet 4 of 7

Group

FIG. 7

FIG. 8

SINR1

SINR2

SINR3

• • •

U.S. Patent

Jun. 7, 2005

Sheet 5 of 7

US 6,904,283 B2

1-8: Diverse Clusters
9-18' Plain Clusters

f

)11.
2 345 6 7 8 9

10 1 2 34 5 6 7 8 11 12 123456T8 13

14 1 2 34 5 6 7 8 15

16

a. Cell A

t

f
2 34567 8 9

10 8 1 2 3456 7 11 12 78 1 2 34 5 6 13

14 67 8 1 2 34 5 15

16

b. Cell B

Vt

f
5 6 T81 23 4 9

10 4 567 81

11 12 3 4 5 6 7 8 1 2 13

14 .2 34-5 6 7 8 1 15

16

c. Cell C

FIG. 9
Subcarrier 1
Subcarrier 2

f

Time 1
Time 2
Time 3
Time 4
a.Cell A

t

b.Cell B

FIG. 10

f

U.S. Patent

Jun. 7, 2005

US 6,904,283 B2

Sheet 6 of 7

Channel/Interference [ 1101
..zVariation Detection
1102
Yes
1104 N
) v

Any
Significant Variation
Detected
9

Select Diversity
Clusters

No

Select Coherence
Clusters

FIG. 11

f
1 11

12 3 4 5 6 7 8 9

111
111
10 12 5 6 7 8 9 1 12 12 5 6 7 13 5 14 1

a. Cell A

FIG. 12

i 11

5 678 91

16

U.S. Patent

US 6,904,283 B2

Sheet 7 of 7

Jun. 7, 2005

11

User Data Buffer Information
1311

Multi-user Data
Buffer

e
Admission Control
1310
Cluster Allocation and
Load Scheduling
Controller
A

SINR/Rate
—,-- Indices
1313

A

User 1 — N

1

--- 1302

11
:II
Y

1303

Multiplexer

Multi-cluster
Transmission and
Receiving Buffer

Cluster 1 — M
[.--- 1304

't'
OFDM Transceiver
Control Signal/
Cluster Allocation
1312

---, 1305

OFDM Signal

1
FIG. 13

US 6,904,283 B2

1

2

MULTI-CARRIER COMMUNICATIONS
WITH GROUP-BASED SUBCARRIER
ALLOCATION

One approach to subcarrier allocation for OFDMA is a
joint optimization operation, not only requiring the activity
and channel knowledge of all the subscribers in all the cells,
but also requiring frequent rescheduling every time an
existing subscribers is dropped off the network or a new
subscribers is added onto the network. This is often impractical in real wireless system, mainly due to the bandwidth
cost for updating the subscriber information and the computation cost for the joint optimization.

This patent application is a Continuation-in-part (CIP) of
patent application Ser. No. 09/738,086 filed Dec. 15, 2000,
entitled "OFDMA with Adaptive Subcarrier-Cluster Configuration and Selective Loading."

5

FIELD OF THE INVENTION

10

SUMMARY OF THE INVENTION

The invention relates to the field of wireless communications; more particularly, the invention relates to multi-cell,
multi-subscriber wireless systems using orthogonal frequency division multiplexing (OFDM).
15

BACKGROUND OF THE INVENTION
Orthogonal frequency division multiplexing (OFDM) is
an efficient modulation scheme for signal transmission over
frequency-selective channels. In OFDM, a wide bandwidth
20
is divided into multiple narrow-band subcarriers, which are
arranged to be orthogonal with each other. The signals
modulated on the subcarriers are transmitted in parallel. For
more information, see Cimini, Jr., "Analysis and Simulation
of a Digital Mobile Channel Using Orthogonal Frequency
25
Division Multiplexing," IEEE Trans. Commun., vol. COM33, no. 7, July 1985, pp. 665-75; Chuang and Sollenberger,
"Beyond 3G: Wideband Wireless Data Access Based on
OFDM and Dynamic Packet Assignment," IEEE Communications Magazine, Vol. 38, No. 7, pp. 78-87, July 2000.
30
One way to use OFDM to support multiple access for
multiple subscribers is through time division multiple access
(TDMA), in which each subscriber uses all the subcarriers
within its assigned time slots. Orthogonal frequency division
multiple access (OFDMA) is another method for multiple 35
access, using the basic format of OFDM. In OFDMA,
multiple 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 40
and its Application to CATV Networks," European Transactions on Telecommunications, Vol. 9 (6), pp. 507-516,
November/December 1998 and Nogueroles, Bossert,
Donder, and Zyablov, "Improved Performance of a Random
OFDMA Mobile Communication System,", Proceedings of 45
IEEE VTC'98, pp. 2502-2506.
Multipath causes frequency-selective fading. The channel
gains are different for different subcarriers. Furthermore, the
channels are typically uncorrelated for different subscribers.
The subcarriers that are in deep fade for one subscriber may SO
provide high channel gains for another subscriber.
Therefore, it is advantageous in an OFDMA system to
adaptively allocate the subcarriers to subscribers so that each
subscriber enjoys a high channel gain. For more
information, see Wong et al., "Multiuser OFDM with Adap- 55
tive Subcarrier, Bit and Power Allocation," IEEE J. Select.
Areas Commun., Vol. 17(10), pp. 1747-1758, October 1999.
Within one cell, the subscribers can be coordinated to
have different subcarriers in OFDMA. The signals for different subscribers can be made orthogonal and there is little so
intracell interference. However, with aggressive frequency
reuse plan, e.g., the same spectrum is used for multiple
neighboring cells, the problem of intercell interference
arises. It is clear that the intercell interference in an OFDMA
system is also frequency selective and it is advantageous to 65
adaptively allocate the subcarriers so as to mitigate the effect
of intercell interference.

A method and apparatus for subcarrier selection for
systems is described. In one embodiment, a method for
subcarrier selection for a system employing orthogonal
frequency division multiple access (OFDMA) comprises
partitioning subcarriers into groups of at least one cluster of
subcarriers, receiving an indication of a selection by the
subscriber of one or more groups in the groups, and allocating at least one cluster in the one or more groups of
clusters selected by the subcarrier for use in communication
with the subscriber.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be understood more fully from
the detailed description given below and from the accompanying drawings of various embodiments of the invention,
which, however, should not be taken to limit the invention
to the specific embodiments, but are for explanation and
understanding only.
FIG. IA illustrates subcarriers and clusters.
FIG. 1B is a flow diagram of one embodiment of a process
for allocating subcarriers.
FIG. 2 illustrates time and frequency grid of OFDM
symbols, pilots and clusters.
FIG. 3 illustrates subscriber processing.
FIG. 4 illustrates one example of FIG. 3.
FIG. 5 illustrates one embodiment of a format for 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 group-based cluster allocation.
FIG. 8 illustrates frequency reuse and interference in a
multi-cell, multi-sector network.
FIG. 9 illustrates different cluster formats for coherence
clusters and diversity clusters.
FIG. 10 illustrates diversity clusters with subcarrier hopping.
FIG. 11 illustrates intelligent switching between diversity
clusters and coherence clusters depending on subscribers
mobility.
FIG. 12 illustrates one embodiment of a reconfiguration
of cluster classification.
FIG. 13 illustrates one embodiment of a base station.
DETAILED DESCRIPTION OF THE PRESENT
INVENTION
An approach for subcarrier allocation is described. A
method and apparatus for subcarrier selection for systems is
described. In one embodiment, a method for subcarrier
selection for a system employing orthogonal frequency
division multiple access (OFDMA) comprises partitioning
subcarriers into groups of at least one cluster of subcarriers,

US 6,904,283 B2
3

4

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

US 6,904,283 B2
5

6

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

US 6,904,283 B2
7

8

reports to the base station its updated selection of clusters
cussed above. By using an appropriate SINR indexing
and their associated SINRs. Then the base station further
scheme, an SINR index may also indicate a particular coding
performs the reselection and informs the subscriber about
and modulation rate that a subscriber desires to use. Note
the new cluster allocation. Retraining can be initiated by the
that even for the same subscribers, different clusters can
base station, and in which case, the base station requests a 5 have different modulation/coding rates.
specific subscriber to report its updated cluster selection.
Pilot symbols serve an additional purpose in determining
Retraining can also be initiated by the subscriber when it
interference among the cells. Since the pilots of multiple
observes channel deterioration.
cells are broadcast at the same time, they will interfere with
Adaptive Modulation and Coding
each other (because they occupy the entire frequency band).
In one embodiment, different modulation and coding rates io This collision of pilot symbols may be used to determine the
are used to support reliable transmission over channels with
amount of interference as a worst case scenario. Therefore,
different SINR. Signal spreading over multiple subcarriers
in one embodiment, the above SINR estimation using this
may also be used to improve the reliability at very low
method is conservative in that the measured interference
SINR.
level is the worst-case scenario, assuming that all the interAn example coding/modulation table is given below in
ference sources are on. Thus, the structure of pilot symbols
Table 1.
15 is such that it occupies the entire frequency hand and causes
collisions among different cells for use in detecting the worst
case SINR in packet transmission systems.
TABLE 1
During data traffic periods, the subscribers can determine
Scheme
Modulation
Code Rate
the level of interference again. The data traffic periods are
20 used to estimate the intra-cell traffic as well as the inter-cell
1/2
0
QPSK, 1/2 Spreading
interference level. Specifically, the power difference during
1/2
QPSK, Vt Spreading
1/2
the pilot and traffic periods may be used to sense the
2
QPSK, 1/2. Spreading
1/2
3
QPSK
(intra-cell) traffic loading and inter-cell interference to select
4
8PSK
the desirable clusters.
5
16QAM
3/4
25
The interference level on certain clusters may be lower,
6
64QAM
5/6
because these clusters may be unused in the neighboring
cells. For example, in cell A, with respect to cluster A there
In the example above, 1/8 spreading indicates that one
is less interference because cluster A is unused in cell B
QPSK modulation symbol is repeated over eight subcarriers.
(while it is used in cell C). Similarly, in cell A, cluster 13 will
The repetition/spreading may also be extended to the time
30 experience lower interference from cell B because cluster B
domain. For example, one QPSK symbol can be repeated
is used in cell B but not in cell C.
over four subcarriers of two OFDM symbols, resulting also
The modulation/coding rate based on this estimation is
?/8 spreading.
robust to frequent interference changes resulted from bursty
The coding/modulation rate can be adaptively changed
packet transmission. This is because the rate prediction is
according to the channel conditions observed at the receiver
35 based on the worst case situation in which all interference
after the initial cluster allocation and rate selection.
sources are transmitting.
Pilot Symbols and SINR Measurement
In one embodiment, a subscriber utilizes the information
In one embodiment, cach base station transmits pilot
available from both the pilot symbol periods and the data
symbols simultaneously, and each pilot symbol occupies the
entire OFDM frequency bandwidth, as shown in FIGS.
traffic periods to analyze the presence of both the intra-cell
2A—C. Referring to FIGS. 2A—C, pilot symbols 201 are 40 traffic load and inter-cell interference. The goal of the
shown traversing the entire OFDM frequency bandwidth for
subscriber is to provide an indication to the base station as
cells A, B and C, respectively. In one embodiment, each of
to those clusters that the subscriber desires to use. Ideally,
the pilot symbols have a length or duration of 128 microthe result of the selection by the subscriber is clusters with
seconds with a guard time, the combination of which is
high channel gain, low interference from other cells, and
approximately 152 microseconds. After each pilot period, 45 high availability. The subscriber provides feedback inforthere are a predetermined number of data periods followed
mation that includes the results, listing desired clusters in
by another set of pilot symbols. In one embodiment, there
order or not as described herein.
are four data periods used to transmit data after each pilot,
FIG. 3 illustrates one embodiment of subscriber processand each of the data periods is 152 microseconds.
ing. The processing is performed by processing logic that
A subscriber estimates the SINR for each cluster from the 50 may comprise hardware (e.g., dedicated logic, circuitry,
pilot symbols. In one embodiment, the subscriber first
etc.), software (such as that which runs on, for example, a
estimates the channel response, including the amplitude and
general purpose computer system or dedicated machine), or
phase, as if there is no interference or noise. Once the
a combination of both.
channel is estimated, the subscriber calculates the
Referring to FIG. 3, channel/interference estimation prointerference/noise from the received signal.
55 cessing block 301 performs channel and interference estiThe estimated SINR values may be ordered from largest
mation in pilot periods in response to pilot symbols. Traffic;
to smallest SINRs and the clusters with large SINR values
interference analysis processing block 302 performs traffic
are selected. In one embodiment, the selected clusters have
and interference analysis in data periods in response to
SINR values that are larger than the minimum SINR which
signal information and information from channel,'
still allows a reliable (albeit low-rate) transmission sup- so interference estimation block 301.
ported by the system. The number of clusters selected may
Cluster ordering and rate prediction processing block 303
depend on the feedback bandwidth and the request transis coupled to outputs of channel/interference estimation
mission rate. In one embodiment, the subscriber always tries
processing block 301 and traffic/interference analysis proto send the information about as many clusters as possible
cessing block 302 to perform cluster ordering and selection
from which the base station chooses.
65 along with rate prediction.
The estimated SINR values are also used to choose the
The output of cluster ordering processing block 303 is
appropriate coding/modulation rate for each cluster as disinput to cluster request processing block 304, which requests

US 6,904,283 B2
9

10

clusters and modulation/coding rates. Indications of these
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 traffic 5
loading and/or strong interference from other cells. That is,
a new subscriber may not be allocated use of a particular
cluster if heavy intra-cell traffic 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 lo
low-rate transmission or no reliable transmission at all.
The channel/interference estimation by processing block
301 is well-known in the art by monitoring the interference
that is generated due to full-bandwidth pilot symbols being
simultaneously broadcast in multiple cells. The interface 15
information is forwarded to processing block 302 which
uses the information to solve the following equation:

Pp=Ps+P,+Ps,
PN, with
PD =

no signal and interference

Ps + PN, with signal only
Pi + PN, with interference only
Ps + Pi + PN, with both signal and interference
Ps + Ph with no signal and interference

Pp — Pp =

Ph with signal only
. with interference only
0, with both signal and interference

11A+1,+n,=y,

where S, represents the signal for subcarrier (freq. band) i,
Ii is the interference for subcarrier i, ni is the noise associated
with subcarrier i, and yi is the observation for subcarrier i.
In the case of 512 subcarriers, i may range from 0 to 511.
The Ii and ni are not separated and may be considered one
quantity. The interference/noise and channel gain Hi are not
know. During pilot periods, the signal Si representing the
pilot symbols, and the observation yi are knowns, thereby
allowing determination of the channel gain Hi 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, Si and y, are
all known.
The interference information from processing blocks 301
and 302 are used by the subscriber to select desirable
clusters. In one embodiment, using processing block 303,
the subscriber orders clusters and also predicts the data rate
that 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
transmission rate. Based on this information, the subscriber
selects clusters that it desires to use based on predetermined
performance criteria. Using the ordered list of clusters, the
subscriber 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 information available during both pilot symbol periods
and data traffic periods to perform energy detection. The
processing of FIG. 4 may be implemented in hardware, (e.g.,
dedicated logic, circuitry, etc.), software (such as is run on,
for example, a general purpose computer system or dedicated machine), or a combination of both.
Referring to FIG. 4, a subscriber includes SINR estimation processing block 401 to perform SINR estimation for
each 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
perform power calculations in data periods for each cluster.
Subtractor 404 subtracts the power calculations for data
periods 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) processing block 405 that performs cluster ordering and selection based on SINR and the power difference
between pilot periods and data periods. Once the clusters

have been selected, the subscriber requests the selected
clusters and the coding/modulation rates with processing
block 406.
More specifically, in one embodiment, the signal power of
each cluster during the pilot periods is compared with that
during the traffic periods, according to the following:

20

where P. is the measured power corresponding to each
cluster during pilot periods, PD is the measured power
during the traffic periods, Ps is the signal power, P, is the
interference power, and P„„ is the noise power.
In one embodiment, the subscriber selects clusters with
25
relatively large Pp/(Pp—PD) (e.g., larger than a threshold such
as 10 dB) and avoids clusters with low Pp/(Pp—PD) (e.g.,
lower than a threshold such as 10 dB) when possible.
Alternatively, the difference may be based on the energy
30 difference between observed samples during the pilot period
and during the data traffic period for each of the subcarriers
in a cluster such as the following:
o = IYr 1 — IYPI
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
40 S1NR and Pp—P„, to select the clusters:
11=ASIN1, Ppl(P,,—Po)

45

50

55

60

65

where f is a function of the two inputs. One example of f
is weighted averaging (e.g., equal weights). Alternatively, a
subscriber selects a cluster based on its SINR and only uses
the power difference Pis,—P„,, to distinguish clusters with
similar SINR. The difference may be smaller than a threshold (e.g., 1 dB).
Both the measurement of SINR and Pp—P, can be averaged over time to reduce variance and improve accuracy. In
one 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.
Feedback Format for Downlink Cluster Allocation
In one embodiment, for the downlink, the feedback contains both the indices of selected clusters and their SINR. An
exemplary format for arbitrary cluster feedback is shown in
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, SINR1 (502),
cluster ID2 (503) and the SINR for the cluster, SINR2 (504),
and cluster ID3 (505), and the SINR for the cluster, SINR3
(506), etc. The SINR for the cluster may be created using an
average of the SINRs of the subcarriers. Thus, multiple
arbitrary clusters can be selected as the candidates. As

US 6,904,283 B2
11
12
discussed above, the selected clusters can also be ordered in
After receiving the pilot signal from the base station, a
the feedback to indicate priority. In one embodiment, the
subscriber sends back the channel information on one or
subscriber may form a priority list of clusters and sends hack
more cluster groups, simultaneously or sequentially. In one
the SINR information in a descending order of priority.
embodiment, only the information on some of the groups is
Typically, an index to the SINR level, instead of the SINR 5 sent back to the base station. Many criteria can be used to
itself is sufficient to indicate the appropriate coding/
choose and order the groups, based on the channel
modulation for the cluster. For example, a 3-bit field can be
information, the inter-cell interference levels, and the intraused for SINR indexing to indicate 8 different rates of
cell traffic load on each cluster.
adaptive coding/modulation.
In one embodiment, a subscriber first selects the group
An Exemplary Base Station
10 with the best overall performance and then feedbacks the
The base station assigns desirable clusters to the subSINR information for the clusters in that group. The subscriber making the request. In one embodiment, the availscriber may order the groups based on their number of
ability of the cluster for allocation to a subscriber depends on
clusters for which the SINR is higher than a predefined
the total traffic load on the cluster. Therefore, the base station
threshold. By transmitting the SINR of all the clusters in the
selects the clusters not only with high SINR, but also with
15 group sequentially, only the group index, instead of all the
low traffic load.
cluster indices, needs to be transmitted. Thus, the feedback
FIG. 13 is a block diagram of one embodiment of a base
for each group generally contains two types of information:
station. Referring to FIG. 13, cluster allocation and load
the group index and the SINR value of each cluster within
scheduling controller 1301 (cluster allocator) collects all the
the group. FIG. 7 illustrates an exemplary format for indinecessary information, including the downlink/uplink SINR
of clusters specified for each subscriber (e.g., via SINR/rate 20 eating a group-based cluster allocation. Referring to FIG. 7,
indices signals 1313 received from OFDM transceiver 1305)
a group ID, ID1, is followed by the SINR values for each of
and user data, queue fullness/traffic load (e.g., via user data
the clusters in the group. This can significantly reduce the
buffer information 1311 from multi-user data buffer 1302).
feedback overhead.
Using this information, controller 1301 makes the decision
Upon receiving the feedback information from the
on cluster allocation and load scheduling for each user, and 25 subscriber, the cluster allocator at the base station selects
stores the decision information in a memory (not shown).
multiple clusters from one or more groups, if available, and
Controller 1301 informs the subscribers about the decisions
then assigns the clusters to the subscriber. This selection
through control signal channels (e.g., control signal/cluster
may be performed by an allocation in a media access control
allocation 1312 via OFDM transceiver 1305). Controller
portion of the base station.
1301 updates the decisions during retraining.
30
Furthermore, in a multi-cell environment, groups can
In one embodiment, controller 1301 also performs admishave different priorities associated with different cells. In
sion control to user access since it knows the traffic load of
one embodiment, the subscriber's selection of a group is
the system. This may be performed by controlling user data
biased by the group priority, which means that certain
buffers 1302 using admission control signals 1310.
subscribers have higher priorities on the usage of some
The packet data of User 1—N are stored in the user data 35 groups than the other subscribers.
buffers 1302. For downlink, with the control of controller
In one embodiment, there is no fixed association between
1301, multiplexer 1303 loads the user data to cluster data
one subscriber and one cluster group; however, in an alterbuffers (for Cluster 1—M) waiting to be transmitted. For the
native embodiment there may be such a fixed association. In
uplink, multiplexer 1303 sends the data in the cluster buffers
an implementation having a fixed association between a
to the corresponding user buffers. Cluster buffer 1304 stores 40 subscriber and one or more cluster groups, the group index
the signal to be transmitted through OFDM transceiver 1305
in the feedback information can be omitted, because this
(for downlink) and the signal received from transceiver
information is known to both subscriber and base station by
1305. In one embodiment, each user might occupy multiple
default.
clusters and each cluster might be shared by multiple users
In another embodiment, the pilot signal sent from the base
(in a time-division-multiplexing fashion).
45 station to the subscriber also indicates the availability of
Group-Based Cluster Allocation
each cluster, e.g., the pilot signal shows which clusters have
In another embodiment, for the downlink, the clusters are
already been allocated for other subscribers and which
partitioned into groups. Each group can include multiple
clusters are available for new allocations. For example, the
clusters. FIG. 6 illustrates an exemplary partitioning. Referbase station can transmit a pilot sequence 1111 1111 on the
ring to FIG. 6, groups 1-4 are shown with arrows pointing 50 subcarriers of a cluster to indicate that the cluster is
to clusters that are in each group as a result of the partitionavailable, and 1111-1-1-1-1 to indicate the cluster is not
ing. In one embodiment, the clusters within each group are
available. At the receiver, the subscriber first distinguishes
spaced far apart over the entire bandwidth. In one
the two sequences using the signal processing methods
embodiment, the clusters within each group are spaced apart
which are well known in the art, e.g., the correlation
farther than the channel coherence bandwidth, i.e. the band- 55 methods, and then estimates the channel and interference
width within which the channel response remains roughly
level.
the same. A typical value of coherence bandwidth is 100 kHz
With the combination of this information and the channel
for many cellular systems. This improves frequency divercharacteristics obtained by the subscriber, the subscriber can
sity within each group and increases the probability that at
prioritize the groups to achieve both high SINR and good
least some of the clusters within a group can provide high so load balancing.
SINR. The clusters may be allocated in groups.
In one embodiment, the subscriber protects the feedback
Goals of group-based cluster allocation include reducing
information by using error correcting codes. In one
the data bits for cluster indexing, thereby reducing the
embodiment, the SINR information in the feedback is first
bandwidth requirements of the feedback channel
compressed using source coding techniques, e.g., differen(information) and control channel (information) for cluster 65 tial encoding, and then encoded by the channel codes.
allocation. Group-based cluster allocation may also be used
FIG. 8 shows one embodiment of a frequency reuse
to reduce inter-cell interference.
pattern for an exemplary cellular set up. Each cell has

US 6,904,283 B2
14

13
hexagonal structure with six sectors using directional antennas at the 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 clusters and each unshaded sector
uses the other half of the clusters. Without loss of generality,
the clusters used by the shaded sectors are referred to herein
as odd clusters and those used by the unshaded sectors are
referred to herein as even clusters.
Consider the downlink signaling with omni-directional
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 sectors, Cell A interferes with Cell C, which in
turn interferes with Cell B, which in turn interferes with Cell
A, namely, A->C->B->A.

TABLE 3

5

Cluster usage for the downlink of the shaded sectors with
less than 2/3 of the full load.
Cluster Usage

Cell A

Cell B

Cell C

1
2
3

Group 1
Group 2

Group 3
Group 1

Group 2
Group 3

10

Table 4 shows the priority orders for the unshaded sectors,
which are different from those for the shaded sectors, since
the interfering relationship is reversed.
15

TABLE 4
Priority ordering for the downlink of the unshaded sectors.
Priority Ordering

20

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

Sector Al receives interference from Sector Cl, but its
transmission interferes with Sector Bl. Namely, its interference source and the victims with which it interferes are not
the same. This might cause a stability problem in a distrib- 25 Intelligent Switching Between Coherence and Diversity
Clusters
uted cluster-allocation system using interference avoidance:
In one embodiment, there are two categories of clusters:
if a frequency cluster is assigned in Sector B1 but not in
coherence clusters, containing multiple subcarriers close to
Sector Cl, the cluster may be assigned in Al because it may
each other and diversity clusters, containing multiple subbe seen as clean in Al. However, the assignment of this
carriers with at least some of the subcarriers spread far apart
cluster Al can cause interference problem to the existing 30 over the spectrum. The closeness of the multiple subcarriers
in coherence clusters is preferably within the channel coherassignment in Bl.
ence bandwidth, i.e. the bandwidth within which the channel
In one embodiment, different cluster groups are assigned
response remains roughly the same, which is typically
different priorities for use in different cells to alleviate the
within 100 kHz for many cellular systems. On the other
aforementioned problem when the traffic load is progres- 35 hand, the spread of subcarriers in diversity clusters is
preferably larger than the channel coherence bandwidth,
sively added to a sector. The priority orders are jointly
typically within 100 kHz for many cellular systems. Of
designed such that a cluster can be selectively assigned to
course, the larger the spread, the better the diversity.
avoid interference from its interference source, while
Therefore, a general goal in such cases is to maximize the
reducing, and potentially minimizing, the probability of
spread.
causing interference problem to existing assignments in 40
FIG. 9 illustrates exemplary cluster formats for coherence
other cells.
clusters and diversity clusters for Cells A—C. Referring to
FIG. 9, for cells A—C, the labeling of frequencies
Using the aforementioned example, the odd clusters (used
(subcarriers) indicates whether the frequencies are part of
by the shaded sectors) are partitioned into 3 groups: Group
coherence or diversity clusters. For example, those frequen1, 2, 3. The priority orders are listed in Table 2.
45 cies labeled 1-8 are diversity clusters and those labeled 9-16
are coherence clusters. For example, all frequencies labeled
TABLE 2
1 in a cell are part of one diversity cluster, all frequencies
labeled 2 in a cell are part of another diversity cluster, etc.,
Priority ordering for the downlink of the shaded sectors.
while the group of frequencies labeled 9 are one coherence
Priority Ordering
Cell A
Cell B
Cell C
so cluster, the group of frequencies labeled 10 are another
coherence cluster, etc. The diversity clusters can be config1
Group 1
Group 3
Group 2
2
Group 2
Group 1
Group 3
ured differently for different cells to reduce the effect of
3
Group 3
Group 2
Group 1
inter-cell interference through interference averaging.
FIG. 9 shows example cluster configurations for three
55 neighboring cells. The interference from a particular cluster
Consider Sector Al. First, the clusters in Group 1 are
in one cell are distributed to many clusters in other cells,
selectively assigned. If there are still more subscribers
e.g., the interference from Cluster 1 in Cell A are distributed
demanding clusters, the clusters in Group 2 are selectively
to Cluster 1,8, 7, 6 in Cell B. This significantly reduces the
assigned to subscribers, depending on the measured SINR
interference power to any particular cluster in Cell B.
(avoiding the clusters receiving strong interference from so Likewise, the interference to any particular cluster in one
Sector Cl). Note that the newly assigned clusters from
cell comes from many different clusters in other cells. Since
Group 2 to Sector Al shall not cause interference problem
not all cluster are strong interferers, diversity clusters, with
in Sector Bl, unless the load in Sector Bl is so heavy that
channel coding across its subcarriers, provide interference
the clusters in both Group 3 and 1 are used up and the
diversity gain. Therefore, it is advantageous to assign diverclusters in Group 2 are also used. Table 3 shows the cluster 65 sity clusters to subscribers that are close (e.g., within the
usage when less than 2A of all the available clusters are used
coherent bandwidth) to the cell boundaries and are more
in Sector Al, Bl, and Cl.
subject to inter-cell interference.

US 6,904,283 B2
15
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 significantly 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 inherent frequency diversity
among the multiple subcarriers spread over the spectrum.
With channel coding across the subcarriers within the
cluster, diversity clusters are more robust to cluster misselection (by the nature of diversification itself), while
yielding possibly less gain from cluster selection. Channel
coding across the subcarriers means that each codeword
contains bits transmitted from multiple subcarriers, and
more specifically, the difference bits between codewords
(error vector) are distributed among multiple subcarriers.
More frequency diversity can be obtained through subcarrier hopping over time in which a subscriber occupies a
set of subcarriers at one time slot and another different set of
subcarriers at a different time slot. One coding unit (frame)
contains multiple such time slots and the transmitted bits are
encoded across the entire frame.
FIG. 10 illustrates diversity cluster with subcarricr hopping. Referring to FIG. 10, there are four diversity clusters
in each of cells A and 13 shown, with each subcarrier in
individual 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 hopping over time, with
further interference diversity achieved by using different
hopping patterns for different cells, as shown in FIG. 10.
The manner in which the subscriber changes the subcarriers (hopping sequences) can be different for different cells
in order to achieve better interference averaging through
coding.
For static subscribers, such as in fixed wireless access, the
channels change very little over time. Selective cluster
allocation using the coherence clusters achieves good performance. 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
significant control overhead. 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 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 channel is completely
different after one cycle. Note that selective cluster allocation can be performed on both coherence and diversity
clusters.
In one embodiment, for cells containing mixed mobile
and fixed subscribers, a channel/interference variation detector can be implemented at either the subscriber or the base
station, or both. Using the detection results, the subscriber
and the base station intelligently selects diversity clusters to
mobile subscribers or fixed subscribers at cell boundaries,
and coherence clusters to fixed subscribers close to the base
station. The channel/interference variation detector mea-

16
sures the channel (SINR) variation from time to time for
each cluster. For example, in one embodiment, the channel/
interference detector measures the power difference between
pilot symbols for each cluster and averages the difference
5 over a moving window (e.g., 4 time slots). A large difference
indicates that channel/interference changes frequently and
subcarrier allocation may be not reliable. In such a case,
diversity clusters are more desirable for the subscriber.
FIG. 11 is a flow diagram of one embodiment of a process
for intelligent selection between diversity clusters and
coherence clusters depending on subscribers mobility. The
process is performed by processing logic that may comprise
hardware (e.g., circuitry, dedicated logic, etc.), software
(such as that which runs on, for example, a general purpose
computer system or dedicated machine), or a combination of
15
both.
Referring to FIG. 11, processing logic in the base station
performs channel/interference variation detection
(processing block 1101). Processing logic then tests whether
2 the results of the channel/interference variation detection
indicate that the user is mobile or in a fixed position close to
the edge of the cell (processing block 1102). If the user is not
mobile or is not in a fixed position close to the edge of the
cell, processing transitions to processing block 1103 where
25 processing 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
30 during retraining.
The ratio/allocation of the numbers of coherence and
diversity clusters in a cell depends on the ratio of the
population of mobile and fixed subscribers. When the population changes as the system evolves, the allocation of
35 coherence and diversity clusters can be reconfigured to
accommodate the new system needs. FIG. 12 illustrates a
reconfiguration of cluster classification which can support
more mobile subscribers than that in FIG. 9.
Whereas many alterations and modifications of the
40 present invention will no doubt become apparent to a person
of ordinary skill in the art after having read the foregoing
description, it is to be understood that any particular embodiment shown and described by way of illustration is in no
way intended to be considered limiting. Therefore, refer45 ences to details of various embodiments are not intended to
limit the scope of the claims which in themselves recite only
those features regarded as essential to the invention.
We claim:
1. A method for subcarricr selection for a system employ50 ing orthogonal frequency division multiple access
(OFDMA) comprising:
partitioning subcarriers into a plurality of groups of at
least one cluster of subcarriers; and
receiving an indication of a selection by a subscriber of
one or more groups in the plurality of groups;
55
allocating at least one cluster in the one or more groups of
clusters selected by the subscriber for use in communication with the subscriber, including selecting the at
least one cluster based on a group priority in which the
60
subscriber has a higher priority for use of the group of
cluster containing the at least one cluster than at least
one other subscriber.
2. The method defined in claim 1 further comprising the
subscriber sending the indication to a base station.
65
3. The method defined in claim 1 further comprising
sending an indication of the group of clusters selected by the
base station for use by the subscriber.

US 6,904,283 B2
17
4. The method defined in claim 1 wherein clusters in each
of the plurality of groups of clusters are spaced apart over
bandwidth allocatable by the base station.
5. The method defined in claim 1 wherein clusters in each
of the plurality of groups are spaced apart farther than
coherent bandwidth of each channel between the bas station
and the subscriber.
6. The method defined in claim 1 wherein the one or more
groups is only a subset of all of the groups of clusters
allocatable by a base station.
7. The method defined in claim 1 further comprising:
sending pilot signal to the subscriber.
8. The method defined in claim 7 wherein the pilot signal
indicates availability of each cluster.
9. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information comprises SINR information for at
least one cluster in each of the one or more groups.
10. The method defined in claim 9 wherein the subscriber
has a fixed association with the at least one group of clusters,
such that group identifier information to identify groups
associated with the S1NR information is not necessary.
11. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information is ordered based on SINR values of
clusters in the one or more groups.
12. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information comprises a group identifier and SINR
value of each cluster within each group.
13. The method defined in claim 12 wherein the group
identifier comprises a group index.
14. The method defined in claim 12 wherein the feedback
information is formatted with, for each of the one or more
groups, a group identifier followed by the SINR values of
clusters in said each of the one or more groups.
15. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and herein the
feedback information is protected using error correcting
codes.
16. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information is compressed using source coding
techniques and encoded with error correcting codes.
17. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and herein the
feedback information comprises a list of candidate cluster
groups desired for use by the subscriber and their associated
signal plus interference to noise ratio (SINR), the candidate
clusters desired for use being a set of all possible clusters
with SINRs relatively higher than other clusters in the set of
all possible clusters.
18. The method defined in claim 17 wherein the list of
candidate cluster groups is ordered based on SINR values of
clusters in the list.
19. The method defined in claim 17 wherein the list of
candidate cluster groups is ordered based on an SINR
associated with each cluster in the group of cluster and
availability of cluster groups in the list.
20. The method defined in claim 17 wherein the feedback
information includes a cluster group identifier followed by
an SINR value for each cluster in the candidate cluster
group.

18
21. The method defined in claim 20 wherein the group
identifier comprises a group index.
22. The method defined in claim 1 further comprising
receiving feedback information on the one or more groups of
5 clusters of subcarriers from the subscriber, and wherein the
subscriber is associated with at least one group of clusters
and, further wherein the feedback information includes an
SINR value associated with each group of clusters without
explicitly specifying an index to the group of clusters.
23. The method defined in claim 1 further comprising
io
receiving addition feedback information on the one or more
groups of clusters; and allocating additional clusters to the
subscriber.
24. A method for subcarrier selection for a system
employing orthogonal frequency division multiple access
15 (OFDMA) comprising:
partitioning subcarriers into a plurality of groups of at
least one cluster of subcarriers; and
receiving an indication of a selection by a subscriber of
one or more groups in the plurality of groups;
20
receiving feedback information on the one or more groups
of clusters of subcarriers from the subscriber, and
wherein the feedback information comprises a group
identifier and SINR value of each cluster within each
group; and
25
allocating at least one cluster in the one or more groups of
clusters selected by the subscriber for use in communication with the subscriber.
25. The method defined in claim 24 wherein the group
identifier comprises a group index.
26. The method defined in claim 24 wherein the feedback
30
information is formatted with, for each of the one or more
groups, a group identifier followed by the SINR values of
clusters in said each of the one or more groups.
27. The method defined in claim 24 further comprising the
35 subscriber sending the indication to a base station.
28. The method defined in claim 24 further comprising
sending an indication of the group of clusters selected by the
base station for use by the subscriber.
29. The method defined in claim 24 wherein clusters in
40 each of the plurality of groups of clusters are spaced apart
over bandwidth allocatable by the base station.
30. The method defined in claim 24 wherein clusters in
each of the plurality of groups are spaced apart farther than
coherent bandwidth of each channel between the base sta45 tion and the subscriber.
31. The method defined in claim 24 further comprising
selecting the at least one cluster based on a group priority in
which the subscriber has a higher priority for use of the
group of clusters containing the at least one cluster than at
so least one other subscriber.
32. The method defined in claim 24 wherein the one or
more groups is only a subset of all of the groups of clusters
allocatable by a base station.
33. The method defined in claim 24 further comprising:
55
sending a pilot signal to the subscriber.
34. The method defined in claim 33 wherein the pilot
signal indicates availability of each cluster.
35. The method defined in claim 24 further comprising
receiving feedback information on the one or more groups of
so clusters of subcarriers from the subscriber, and wherein the
feedback information comprises SINR information for at
least one cluster in each of the one or more groups.
36. The method defined in claim 35 wherein the subscriber has a fixed association with the at least one group of
65 clusters, such that group identifier information to identify
groups associated with the SINR information is not necessary.

US 6,904,283 B2
19

20

37. The method defined in claim 24 further comprising
50. The method defined in claim 47 wherein clusters in
receiving feedback information on the one or more groups of
each of the plurality of groups of clusters are spaced apart
clusters of subcarriers from the subscriber, and wherein the
over bandwidth allocatable by the base station.
feedback information is ordered based on SINR values of
51. The method defined in claim 47 wherein clusters in
clusters in the one or more groups.
5 each of the plurality of groups are spaced apart farther than
38. The method defined in claim 24 further comprising
coherent bandwidth of each channel between the base stareceiving feedback information on the one or more groups of
tion and the subscriber.
clusters of subcarriers from the subscriber, and wherein the
52. The method defined in claim 47 further comprising
feedback information is protected using error correcting
selecting the at least one cluster based on a group priority in
codes.
10
which the subscriber has a higher priority for use of the
39. The method defined in claim 24 further comprising
receiving feedback information on the one or more groups of
group of clusters containing the at least one cluster than at
clusters of subcarriers from the subscriber, and wherein the
least one other subscriber.
feedback information is compressed using source coding
53. The method defined in claim 47 wherein the one or
techniques and encoded with error correcting codes.
more groups is only a subset of all of the groups of clusters
40. The method defined in claim 24 further comprising 15
allocatable by a base station.
receiving feedback information on the one or more groups of
54. The method defined in claim 47 further comprising:
clusters of subcarriers from the subscriber, and wherein the
sending a pilot signal to the subscriber.
feedback information comprises a list of candidate cluster
55. The method defined in claim 54 wherein the pilot
groups desired for use by the subscriber and their associated
signal plus interference to noise ratio (SINR), the candidate 20 signal indicates availability of each cluster.
clusters desired for use being a set of all possible clusters
56. The method defined in claim 47 wherein the feedback
with SINRs relatively higher than other clusters in the set of
information comprises SINR information for at least one
all possible clusters.
cluster in each of the one or more groups.
41. The method defined in claim 40 wherein the list of
57. The method defined in claim 56 wherein the subcandidate cluster groups is ordered based on SINR values of 25 scriber has a fixed association with the at least one group of
clusters in the list.
clusters, such that group identifier information to identify
42. The method defined in claim 40 wherein the list of
groups associated with the SINR information is not necescandidate cluster groups is ordered based on an SINR
sary.
associated with each cluster in the group of cluster and
58. The method defined in claim 47 wherein the feedback
availability of cluster groups in the list.
30 information is ordered based on SINR values of clusters in
43. The method defined in claim 40 wherein the feedback
the one or more groups.
information includes a cluster group identifier followed by
59. The method defined in claim 47 wherein the feedback
an SINR value for each cluster in the candidate cluster
information comprises a group identifier and SINR value of
group.
each cluster within each group.
44. The method defined in claim 43 wherein the group
35
60. The method defined in claim 59 wherein the group
identifier comprises a group index.
identifier comprises a group index.
45. The method defined in claim 24 further comprising
61. The method defined in claim 59 wherein the feedback
receiving feedback information on the one or more groups of
information is formatted with, for each of the one or more
clusters of subcarriers from the subscriber, and wherein the
groups, a group identifier followed by the SINR values of
subscriber is associated with at least one group of clusters
40 clusters in said each of the one or more groups.
and, further wherein the feedback information includes an
62. The method defined in claim 47 wherein the feedback
SINR value associated with each group of clusters without
information is protected using error correcting codes.
explicitly specifying an index to the group of clusters.
63. The method defined in claim 47 wherein the feedback
46. The method defined in claim 24 further comprising:
information comprises a list of candidate cluster groups
receiving additional feedback information on the one or
45 desired for use by the subscriber and their associated signal
more groups of clusters; and
plus interference to noise ratio (SINR), the candidate clusallocating additional clusters to the subscriber.
ters desired for use being a set of all possible clusters with
47. A method for subcarrier selection for a system
SINRs relatively higher than other clusters in the set of all
employing orthogonal frequency division multiple access
possible clusters codes.
(OFDMA) comprising:
50
64. The method defined in claim 63 wherein the list of
partitioning subcarriers into a plurality of groups of at
candidate cluster groups is ordered based on SINR values of
least one cluster of subcarriers; and
clusters in the list.
receiving an indication of a selection by a subscriber of
65. The method defined in claim 63 wherein the list of
one or more groups in the plurality of groups;
candidate cluster groups is ordered based on an SINR
receiving feedback information on the one or more groups 55 associated with each cluster in the group of cluster and
of clusters of subcarriers from the subscriber, and
availability of cluster groups in the list.
wherein the feedback information is compressed using
66. The method defined in claim 63 wherein the feedback
source coding techniques and encoded with error corinformation includes a cluster group identifier followed by
recting codes; and
an SINR value for each cluster in the candidate cluster
allocating at least one cluster in the one or more groups of so group.
clusters selected by the subscriber for use in commu67. The method defined in claim 66 wherein the group
nication with the subscriber.
identifier comprises a group index.
48. The method defined in claim 47 further comprising the
68. The method defined in claim 47 wherein the subsubscriber sending the indication to a base station.
scriber is associated with at least one group of clusters and,
49. The method defined in claim 47 further comprising 65 further wherein the feedback information includes an SINR
sending an indication of the group of clusters selected by the
value associated with each group of clusters without explicbase station for use by the subscriber.
itly specifying an index to the group of clusters.

US 6,904,283 B2
21
69. The method defined in claim 47 further comprising
receiving additional feedback information on the one or
more groups of clusters; and
allocating additional clusters to the subscriber.
70. A method for subcarrier selection for a system
employing orthogonal frequency division multiple access
(OFDMA) comprising:
partitioning subcarriers into a plurality of groups of at
least one cluster of subcarriers; and receiving an indication of a selection by a subscriber of one or more
groups in the plurality of groups;
receiving feedback information on the one or more groups
of clusters of subcarriers from the subscriber, and
wherein the feedback information comprises a list of
candidate cluster groups desired for use by the subscriber and their associated signal plus interference to
noise ratio (SINR), the candidate clusters desired for
use being a set of all possible clusters with SINRs
relatively higher than other clusters in the set of all
possible clusters; and
allocating at least one cluster in the one or more groups of
clusters selected by the subscriber for use in communication with the subscriber.
71. The method defined in claim 70 wherein the list of
candidate cluster groups is ordered based on SINR values of
clusters in the list.
72. The method defined in claim 70 wherein the list of
candidate cluster groups is ordered based on an SINR
associated with each cluster in the group of clusters and
availability of cluster groups in the list.
73. The method defined in claim 70 wherein the feedback
information includes a cluster group identifier followed by
an SINR value for each cluster in the candidate cluster
group.
74. The method defined in claim 73 wherein the group
identifier comprises a group index.
75. The method defined in claim 70 further comprising the
subscriber sending the indication to a base station.
76. The method defined in claim 70 further comprising
sending an indication of the group of clusters selected by the
base station for use by the subscriber.
77. The method defined in claim 70 wherein clusters in
each of the plurality groups of clusters are spaced apart over
bandwidth allocatable by the base station.
78. The method defined in claim 70 wherein clusters in
each of the plurality of groups are spaced apart farther than
coherent bandwidth of each channel between the base station and the subscriber.
79. The method defined in claim 70 further comprising
selecting the at least one cluster based on a group priority in
which the subscriber has a higher priority for use of the
group of clusters containing the at least one cluster than at
least one other subscriber.
80. The method defined in claim 70 wherein the one or
more groups is only a subset of all of the groups of clusters
allocatable by a base station.
81. The method defined in claim 70 further comprising:
sending pilot signal to the subscriber.
82. The method defined in claim 81 wherein the pilot
signal indicates availability of each cluster.
83. The method defined in claim 70 wherein the subscriber has a fixed association with the at least one group of
clusters, such that group identifier information to identify
groups associated with the SINR information is not necessary.
84. The method defined in claim 70 wherein the feedback
information is ordered based on SINR values of clusters in
the one or more groups.

22
85. The method defined in claim 70 wherein the feedback
information comprises a group identifier and SINR value of
each cluster within each group.
86. The method defined in claim 85 wherein the group
5 identifier comprises a group index.
87. The method defined in claim 85 wherein the feedback
information is formatted with, for each of the one or more
groups, a group identifier followed by the SINR values of
clusters in said each of the one or more groups.
88. The method defined in claim 70 wherein the feedback
1
information is protected using error correcting codes.
89. The method defined in claim 70 wherein the feedback
information is compressed using source coding techniques
and encoded with error correcting codes.
90. The method defined in claim 70 wherein the sub15 scriber is associated with at least one group of clusters and,
further wherein the feedback information includes an SINR
value associated with each group of clusters without explicitly specifying an index to the group of clusters.
91. The method defined in claim 70 further comprising:
20
receiving additional feedback information on the one or
more groups of clusters; and
allocating additional clusters to the subscriber.
92. A method for subcarrier selection for a system
employing orthogonal frequency division multiple access
25 (OFDMA) comprising:
partitioning subcarriers into a plurality of groups of at
least one cluster of subcarriers; and
receiving an indication of a selection by a subscriber of
one or more groups in the plurality of groups;
30
allocating at least one cluster in the one or more groups of
clusters selected by the subscriber for use in communication with the subscriber;
receiving additional feedback information on the one or
more groups of clusters; and
35
allocating additional clusters to the subscriber.
93. The method defined in claim 92 further comprising the
subscriber sending the indication to a base station.
94. The method defined in claim 92 further comprising
40 sending an indication of the group of clusters selected by the
base station for use by the subscriber.
95. The method defined in claim 92 wherein clusters in
each of the plurality of groups of clusters are spaced apart
over bandwidth allocatable by the base station.
45
96. The method defined in claim 92 wherein clusters in
each of the plurality of groups are spaced apart farther than
coherent bandwidth of each channel between the has station
and the subscriber.
97. The method defined in claim 92 further comprising
50 selecting the at least one cluster based on a group priority in
which the subscriber has a higher priority for use of the
group of clusters containing the at least one cluster than at
least one other subscriber.
98. The method defined in claim 92 wherein the one or
55 more groups is only a subset of all of the groups of clusters
allocatable by a base station.
99. The method defined in claim 92 further comprising:
sending pilot signal to the subscriber.
100. The method defined in claim 99 wherein the pilot
so signal indicates availability of each cluster.
101. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information comprises SINR information for at
65 least one cluster in each of the one or more groups.
102. The method defined in claim 101 wherein the subscriber has a fixed association with the at least one group of

US 6,904,283 B2
23
clusters, such that group identifier information to identify
groups associated with the SINR information is not necessary.
103. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of 5
clusters of subcarriers from the subscriber, and wherein the
feedback information is ordered based on SINR values of
clusters in the one or more groups.
104. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the io
feedback information comprises a group identifier and SINR
value of each cluster within each group.
105. The method defined in claim 104 wherein the group
identifier comprises a group index.
106. The method defined in claim 104 wherein the feed- 15
back information is formatted with, for each of the one or
more groups, a group identifier followed by the SINR values
of clusters in said each of the one or more groups.
107. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the 20
feedback information is protected using error correcting
codes.
108. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
25
feedback information is compressed using source coding
techniques and encoded with error correcting codes.
109. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the
feedback information comprises a list of candidate cluster 30
groups desired for use by the subscriber and their associated
signal plus interference to noise ratio (SINR), the candidate
clusters desired for use being a set of all possible clusters
with SINRs relatively higher than other clusters in the set of
all possible clusters.
35
110. The method defined in claim 109 wherein the list of
candidate cluster groups is ordered based on SINR values of
clusters in the list.
111. The method defined in claim 109 wherein the list of
candidate cluster groups is ordered based on an SINR 40
associated with each cluster in the group of cluster and
availability of cluster groups in the list.
112. The method defined in claim 109 wherein the feedback information includes a cluster group identifier followed
by an SINR value for each cluster in the candidate cluster
45
group.
113. The method defined in claim 112 wherein the group
identifier comprises a group index.
114. The method defined in claim 92 further comprising
receiving feedback information on the one or more groups of
clusters of subcarriers from the subscriber, and wherein the 50
subscriber is associated with at least one group of clusters
and, further wherein he feedback information includes an
SINR value associated with each group of clusters without
explicitly specifying an index to the group of clusters.
115. An apparatus comprising:
55
a cluster location controller to receive an indication of a
selection by a subscriber of one or more groups a
plurality of groups of at least one cluster of subcarriers
and to allocate at least one cluster in the one or more
groups of clusters selected by the subscriber for use in 60
communication with the subscriber by selecting the at
least one cluster based on a group priority in which the
subscriber has a higher priority for use of the group of
clusters containing the at least one cluster than at least
one other subscriber; and
65
an orthogonal frequency division multiplexing (OFDM)
transceiver coupled to the cluster allocation controller

24
to send a notification to the subscriber indicating the at
least one cluster in the one or more groups of clusters
to be used by the subscriber.
116. An apparatus comprising:
a cluster allocation controller
to receive an indication of a selection by a subscriber of
one or more groups in a plurality of groups of at least
one cluster of subcarriers and feedback information
on the one or more groups of clusters of subcarriers
from the subscriber, and wherein the feedback information comprises a group identifier and SINR value
of each cluster within each group, and
to allocate at least one cluster in the one or more groups
of clusters selected by the subscriber for use in
communication with the subscriber; and
an orthogonal frequency division multiplexing (OFDM)
transceiver coupled to the cluster allocation controller
to send a notification to the subscriber indicating the at
least one cluster in the on or more groups of clusters to
be used by the subscriber.
117. An apparatus comprising:
a cluster allocation controller
to receive an indication of a selection by a subscriber of
one or more groups in a plurality of groups of at least
one cluster of subcarriers and feedback information
on the one or more groups of clusters of subcarriers
from the subscriber, and wherein the feedback information is compressed using source coding techniques and encoded with error correcting codes, and
to allocate at least one cluster in the one or more groups
of clusters selected by the subscriber for use in
communication with the subscriber; and
an orthogonal frequency division multiplexing (OFDM)
transceiver coupled to the cluster allocation controller
to send a notification to the subscriber indicating the at
least one cluster in the one or more groups of clusters
to be used by the subscriber.
118. An apparatus comprising:
a cluster location controller
to receive an indication of a selection by a subscriber of
one or more groups in a plurality of groups of at least
one cluster of subcarriers and feedback information
on the one or more groups of clusters of subcarriers
from the subscriber, and wherein the feedback information comprises a list of candidate cluster groups
desired for use by the subscriber and their associated
signal plus interference to noise ratio (SINR), the
candidate clusters desired for use being a set of all
possible clusters with SINRs relatively higher than
other clusters in the set of all possible dust, and
to allocate at least one cluster in the one or more groups
of clusters selected by the subscriber for use in
communication with the subscriber; and
an orthogonal frequency division multiplexing (OFDM)
transceiver coupled to the cluster allocation controller
to send a notification to the subscriber indicating the at
least one cluster in the on or more groups of clusters to
be used by the subscriber.
119. An apparatus comprising:
a cluster allocation controller
to receive an indication of a selection by a subscriber of
one or more groups in a plurality of groups of at least
one cluster of subcarriers, and
to allocate at least one cluster in the one or more groups
of clusters selected by the subscriber for use in
communication with the subscriber; and

US 6,904,283 B2
25
an orthogonal frequency division multiplexing (OFDM)
transceiver coupled to the cluster allocation controller
to send a notification to the subscriber indicating the at
least one cluster in the one or more groups of clusters
to be used by the subscriber, wherein the cluster allo-

26
cation controller is operable to receive additional feedback information on the one or more groups of clusters
and allocate additional clusters to the subscriber.

UNITED STATES PATENT AND TRADEMARK OFFICE

CERTIFICATE OF CORRECTION
Page 1 of 1

PATENT NO.
: 6,904,283 B2
APPLICATION NO. : 09/837337
DATED
: June 7, 2005
: Xiaodong Li et al.
INVENTOR(S)

It is certified that error appears in the above-identified patent and that said Letters Patent is
hereby corrected as shown below:

column 16. line 53, delete "and".
column 16, line 55, delete "groups;" and insert --groups; and--.
column 18, line 17, delete "and".
column 19, line 52, delete "and".
column 21, line 9, delete "and".
column 22, line 28, delete "and".
column 23, line 56, delete "a cluster location controller" and insert --a cluster allocation controller--.
column 24, line 40, delete "a cluster location controller" and insert --a cluster allocation controller--.

Signed and Sealed this
Fourteenth Day of November, 2006

JON W. DUDAS
Director of the United States Patent and Trademark Office

UNITED STATES PATENT AND TRADEMARK OFFICE

CERTIFICATE OF CORRECTION
PATENT NO.
APPLICATION NO.
DATED
INVENTOR(S)

: 6,904,283 B2
: 09/837337
: June 7, 2005
: Xiaodong Li et al.

Page 1 of 1

It is certified that error appears in the above-identified patent and that said Letters Patent is hereby corrected as shown below:

In the Claims:
Column 17, Claim 15, Line 40, delete the portion of text reading "herein" and replace with
--wherein--.
Column 17, Claim 17, Line 50, delete the portion of text reading "herein" and replace with
--wherein--.
Column 22, Claim 96, Line 47, delete the portion of text reading "bas" and replace with
--base--.
Column 23, Claim 115, Line 57, delete the portion of text reading "groups a" and replace
with --groups in a--.
Column 24, Claim 116, Line 19, delete the portion of text reading "on or more" and
replace with --one or more--.
Column 24, Claim 118, Line 51, delete the portion of text reading "dust" and replace with
--clusters--.

Signed and Sealed this
Sixteenth Day of August, 2011

David J. Kappos
Director of the United States Patent and Trademark Office