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 B

11111111111110111111101 R1,1111191111111101 11E1111
(12)

United States Patent

(to) Patent No.:
US 6,870,808 B1
(45) Date of Patent:
Mar. 22, 2005

Liu et al.

(54)

CHANNEL ALLOCATION IN BROADBAND
ORTHOGONAL FREQUENCY-DIVISION
MULTIPLE-ACCESS/SPACE-DIVISION
MULTIPLE-ACCESS NETWORKS

(75) Inventors: Hui Liu, Sammamish, WA (US);
Hujun Yin, Seattle, WA (US);
Xiaodong Li, 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 793 days.

(21) Appl. No.: 09/692,681
(22)

Filed:

(51)
(52)

Int. C1.7
U.S. Cl.

(58)

Oct. 18, 2000

HO4J 11/00; H04B 7/208
370/203; 370/210; 370/329;
370/344
Field of Search
370/203, 206,
370/208, 210, 252, 319, 328, 329, 343,
344, 480, 485, 330; 375/260, 261, 267,
299, 347; 455/450, 507, 509, 517

(56)

References Cited
U.S. PATENT DOCUMENTS
5,280,630 A
5,479,447 A
5,504,775 A

1/1994 Wang
12/1995 Chow et al.
4/1996 Chouly et al.

(List continued on next page.)
FOREIGN PATENT DOCUMENTS
DE

198 00 953 Cl

EP
EP
EP
GB
JP
WO
WO

0 869 647 A2
0 926 912 A2
0 999 658 A2
2 209 858 A
06029922
WO 98/16077 A2
WO 98/30047 Al

OTHER PUBLICATIONS
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 1 and 11 abstract.
(List continued on next page.)
Primary Examiner Alpus H. Hsu
(74) Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor &
Zafman LLP
(57)

ABSTRACT

A network is described. In one embodiment, the network
comprises multiple subscriber units to communicate with the
base station using an orthogonal frequency-division
multiple-access (OFDMA) protocol, and a base station. The
base-station includes a memory unit to store broadband
spatial signature vectors associated with each subscriber and
traffic channel allocation logic. The vectors arc a function of
frequency. The traffic channel allocation logic allocates
OFDMA channels using the broadband spatial signature
vectors of the subscribers.

7/1999

42 Claims, 6 Drawing Sheets

V VV......_ Antenna Array

--- Transmitting
Antenna Array
511

500
Downconverters
501

2-D Spatial
Signature
Estimator
503

Ongoing

10/1998
6/1999
5/2000
8/1997
2/1994
4/1998
7/1998

Upconverters
508

OFDM
Demodulator
502

Parallel
Narrowband
Beamformers
509

OFDMA/SDMA
Traffic Channel
Allocation Logic
505

Ongoing Traffic
SS Register
506

OFDMA
MAC
507

OFDM
Modulator
510

Downlink
Information
Streams
520

US 6,870,808 B1
Page 2

6,449,246 B1 * 9/2002 Barton et al.
6,473,467 B1 * 10/2002 Wallace et al.
6,477,158 B1 11/2002 Take
6,545,997 B1
4/2003 Bohnke et al.
6,657,949 B1 12/2003 Jones, IV et al.
2003/0067890 Al
4/2003 Goel et al.
2003/0169681 Al
9/2003 Li et al.
2003/0169824 Al
9/2003 Chayat

U.S. PATENT DOCUMENTS
5,507,034 A
4/1996 Bodin et al.
5,515,378 A
5/1996 Roy, III et al.
5,555,268 A
9/1996 Fattouche et al.
5,588,020 A
12/1996 Schilling
5,708,973 A
1/1998 Ritter
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.
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,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.
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.

370/210
375/267

OTHER PUBLICATIONS

370/329

370/330

Bender et al., CDMA/IIDR: A Bandwidth—Efficient IIigh
Speed Wireless Data Service for Nomadic Users, IEEE
Communications Magazine, Jul. 2000, pp. 70-87.
Frullone et al., PRMA Performance in Cellular Environments with Self—Adaptive Channel Allocation Strategies,
IEEE Transactions on Vehicular Technology, Nov. 1996, pp.
657-665 vol. 45, No. 4.
Xu, Guanghan and Li, San—Qi, Throughput Multiplication
of Wireless Lans for Multimedia Services: SDMA Protocol
Design, 1994 IEEE, pp. 1326-1332.
Ward, James and Compton, R. Ted, Jr., High Throughput
Slotted ALOHA Packet Radio Networks with Adaptive
Arrays, IEEE Transactions on Communications, Mar. 1993,
pp. 460-470, vol. 41, No. 3.
Tsoulos, G.V., Smart antennas for mobile communication
systems: benefits and challenges, Electronics & 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).
Mignone et al., CD3—OFDM: A Novel Demodulation
Scheme for Fixed and Mobile Receivers, IEEE Transactions
on Communications, vol. 44, No. 9, Sep. 1996.
* cited by examiner

U.S. Patent

US 6,870,808 B1

(i)
E
1=
A

E
A 1::

SDMA: Chdnnel-aware Assignment

Sheet 1 of 6

SDMA: Random Assignment

Mar. 22, 2005

a>

LC)

iv'

N

=

M
;13
o
.m

.4L
(.1)

1-L
43)
CO

4

cv

I4)

tn

4

8
Co

CL
CO

L
co
40

a

a)
c.)
C.

CO

(6
L
Cr)

Li
=
co

ze

U.S. Patent

Mar. 22, 2005

Sheet 2 of 6

US 6,870,808 B1

Q.,
.
0
Ce
2 ›..
._ a)
2
<

g,_
Q Li-,
2

0 e
s.
•*. . iih....

CNI

d

ft

UN

A

OFDMATraffic Channel

Mar. 22, 2005

OccupiedTraffc Channel
i

To Be Allocated

U.S. Patent
Sheet 3 of 6
US 6,870,808 B1

Cr)

Mar. 22, 2005

Sheet 4 of 6

US 6,870,808 B1

Ongoing Traffic Not Affected

Ongoing Traffic Affected

U.S. Patent

LO

•

•

LJ0

'Tr
<0

s
\

U.S. Patent

Mar. 22, 2005

US 6,870,808 B1

Sheet 5 of 6

4

_, 0 ,„
c=
= ,,, e (NJ
E CO

I-i,
tl)
.L
0 0 ••••
0 4E Ci)

t

LL

< $.

Mar. 22, 2005

Sheet 6 of 6

US 6,870,808 B1

Ce, cy,

<X

Cu
'

c2
l
< ca

NN

i 1
< CtS

.r—
...s
"C"— V..'
I I
< 05 < 03
: < as

T"'

N-- .... CNI csi
I 1
I

7I

-110-

I'

CO

v-- 'l
c;

r_K1 r K2

r)
Y
J

r 12

U.S. Patent

(9
LL

US 6,870,808 B1

1

2

CHANNEL ALLOCATION IN BROADBAND
ORTHOGONAL FREQUENCY-DIVISION
MULTIPLE-ACCESS/SPACE-DIVISION
MULTIPLE-ACCESS NETWORKS

A fundamental solution to the above problem is the
"channel-aware" MAC protocol that assigns traffic channels
based on the spatial characteristics of the subscribers. Using
such a protocol, the performance of SDMA system can be
enhanced with spatial signature-based scheduling (e.g.,
assigning the "less-interfering" subscribers to the same time
slot to increase the traffic throughput). The MAC treatment
allows a system to exploit the spatial diversity in an efficient
manner using spatial processing with fixed-complexity. Several scheduling algorithms are proposed and studied for
"narrow band" systems where the spatial characteristics can
be described by a one-dimensional vector; see Shad et al.,
"Indoor SDMA Capacity Using a Smart Antenna Base
Station," IEEE Proc. ICUPC'97, pp. 868-872, 1997; Farsakh et al., "On the Mobile Radio Capacity Increase through
SDMA," Accessing, Transmission, Networking
Proceedings, pp. 293-297, 1998; and U.S. Pat. No. 6,041,
237, "Method of Channel Allocation," issued Mar. 21, 2000.
All of the existing channel allocation schemes, however,
consider "narrowband" TDMAwireless network in conjunction with SDMA. None of them is applicable to broadband
wireless networks. The prime reason is that in broadband
application, subscribers' spatial channels are twodimensional, in both space and frequency, and channel
assignment under spatial multiplexing becomes a more
involved problem.
Recently, there is an increasing interest in frequency
division multiple access (OFDMA) based broadband wireless networks. OFDMA can be viewed from one perspective
as attempting to achieve system capacity over multiplesubscriber broadband wireless channels.

5

FIELD OF THE INVENTION
The present invention relates to the field of communications systems; more particularly, the present invention
relates to orthogonal frequency-division multiple-access
(OFDMA) networks that employ space-division multipleaccess.

10

BACKGROUND OF THE INVENTION
For broadband wireless networks that support mixed
traffic, it is required that a medium access control (MAC) be
able to effectively adapt to changing channel conditions and
traffic requirements. One of the key resources in wireless
communication is the spatial diversity provided by antenna
arrays. Efficient exploitation of spatial diversity is fundamentally important to resource critical wireless applications.
See Tsoulos, "Smart Antennas For Mobile Communication
Systems: Benefits and Challenges," Electronics and Communication Engineering Journal, Vol. 11(2), April 1999.
One of the most aggressive ways of exploiting the spatial
diversity is space-division multiple-access (SDMA), or spatial multiplexing, that attempts to multiply the throughput of
a wireless network by introducing "spatial channels". The
benefits of SDMA in narrowband applications have be
investigated by Shad et al., "Indoor SDMA Capacity Using
a Smart Antenna Base Station," IEEE Proc. ICUPC'97, pp.
868-872, 1997; Farsakh et al., "On the Mobile Radio
Capacity Increase Through SDMA," Accessing,
Transmission, Networking Proceedings, pp. 293-297, 1998;
Xu et al., "Throughput Multiplication of Wireless LANs for
Multimedia Services: SDMA Protocol Design," Proc.
Globecom'94, San Francisco, Calif., November 1994; Ward
et al., "Iligh Throughput Slotted ALOIIA Packet Radio
Networks with Adaptive Arrays," IEEE Trans. COM, Vol.
41(3), pp. 460-470, March 1993. The narrowband SDMA
scheme is particularly suitable for fixed wireless networks
where the spatial characteristics are relatively stable. For a
system with M antenna elements, the underlying idea is to
allow M subscribers to share a time-division multiple-access
(TDMA) slot through M spatial channels/slots, so that the
total number of non-interfering traffic channels can be
increased by M fold.
Though intuitively promising, an obvious flaw of this
scheme is that spatial channels are rarely orthogonal in
practice. In other words, traffic over SDMA channels are
mutually interfering. If multiple subscribers arc assigned to
one time slot without considering these spatial
characteristics, the one with an unfavorable spatial configuration may experience significant throughput disadvantages.
Since the effectiveness of spatial separation depends on the
base-station array responses (often referred to as the spatial
signatures) of all co-slot subscribers and the spatial processing technique employed, the instantaneous signal-to-noiseplus-interference ratio (SINR) of spatially multiplexed outputs can vary dramatically. This problem is investigated by
Ward et al., "High Throughput Slotted ALOHA Packet
Radio Networks with Adaptive Arrays," IEEE Trans. COM,
Vol. 41(3), pp 460-470, March 1993, where collision due to
un-resolvable packets (when the arrival angles of multiple
packets are within a threshold) is accounted for. Although
the analysis is somewhat simplified, the study reveals some
of the key limitations of basic SDMA scheme.

15

20

25

30

SUMMARY OF THE INVENTION
35

40

45

50

55

60

65

A network is described. In one embodiment, the network
comprises multiple subscriber units to communicate with the
base station using an orthogonal frequency-division
multiple-access (OFDMA) protocol, and a base station. The
base-station includes a memory unit to store broadband
spatial signature vectors associated with each subscriber and
traffic channel allocation logic. The vectors are a function of
frequency. The traffic channel allocation logic allocates
OFDMA channels using the broadband spatial signature
vectors of the subscribers.
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. 1A illustrates multiple subscribers.
FIG. 1B illustrates randomly assigning subscribers to
channels and the idea of "spatial signature-aware" channel
assignment, where less interfering subscribers are assigned
to the same traffic slot to increase system capacity.
FIG. 2 shows accommodating a high data rate with
parallel narrowband data streams transmitted over OFDMA
traffic channels.
FIG. 3 illustrates channel assignment in OFDMA/SDMA
in the presence of on-going traffics.
FIG. 4 shows the achievable rates of accessing subscribers in each of the OFDMA traffic channels in the presence
of on-going subscribers.
FIG. 5 is a block diagram of one embodiment of an
OFDMA/SDMA base-station.

US 6,870,808 B1
3
FIG. 6 is a decision making flow of one embodiment of
the OFDMA/SDMA traffic channel allocation logic.
DETAILED DESCRIPTION OF THE PRESENT
INVENTION
A network described herein combines orthogonal
frequency-division multiple-access (OFDMA) with spacedivision multiple-access (SDMA) to provide an OFDMA/
SDMA protocol that offers an increase in capacity, while
assigning OFDMA/SDMA traffic channels to multipleaccess subscribers based on their broadband (twodimensional) channel characteristics. In one embodiment,
such a network is a cellular network implementing OFDMA
in conjunction with spatial multiplexing in a broadband
wireless cellular network. The cellular network includes a
base-station with spatially separated transceivers and multiple subscribers communicating with the base-station using
an OFDMA protocol. The term "subscriber" or "subscribers" is used herein to refer to a subscriber unit or device.
The network includes traffic channel allocation logic that
increases, and potentially maximizes, the network throughput based on the broadband propagation characteristics
between the base-station and the subscribers. In one
embodiment, each traffic channel is a cluster of OFDM
sub-carriers that may be shared by multiple subscribers
through spatial multiplexing. When a new link between the
base-station and a subscriber is to be established, the traffic
channel allocation logic first estimates two-dimensional
(space and frequency/time) broadband propagation channels
between the base-station and the new subscriber. Frequency
and time are the same time represented in two different
domains. The traffic channel allocation logic then accommodates a rate request received from the new subscriber by
assigning traffic channels that utilizes a predetermined (e.g.,
the minimum) amount of transmission power (in comparison
to the amount of transmission power necessary to transmit
over one or more other OFDMA traffic channels that were
not assigned to the new subscriber) and causes a certain
amount of interference (e.g., the least interference in comparison to the interference to other subscribers caused by the
new subscriber using one or more of the OFDMA traffic
channels that were not assigned to the new subscriber) to
co-channel subscribers. The rate request is received from the
subscriber either prior to the process of establishing the new
link or concurrently therewith.
In alternative embodiments, the traffic channel allocator
logic assigns traffic channels that require use of an amount
of transmission power greater than the minimum and/or
cause an amount of interference greater than those channels
that cause the least interference (if used for the new subscriber's traffic). Such assignments may, for example, be
used on other channel allocation or loading requests by
made at the same time or scheduled to occur in the future.
In the following description, numerous details are set
forth in order to provide a thorough understanding of the
present invention. It will be apparent, however, to one
skilled in the art, that the present invention may be practiced
without these specific details. In other instances, well-known
structures and devices are shown in block diagram form,
rather than in detail, in order to avoid obscuring the present
invention.
Some portions of the detailed descriptions which follow
are presented in terms of algorithms and symbolic representations of operations on data bits within a computer
memory. These algorithmic descriptions and representations
are the means used by those skilled in the data processing

4
arts to most effectively convey the substance of their work
to others skilled in the art. An algorithm is here, and
generally, conceived to be a self-consistent sequence of steps
leading to a desired result. The steps are those requiring
5 physical manipulations of physical quantities. Usually,
though not necessarily, these quantities take the form of
electrical or magnetic signals capable of being stored,
transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for
to reasons of common usage, to refer to these signals as bits,
values, elements, symbols, characters, terms, numbers, or
the like.
It should be borne in mind, however, that all of these and
similar terms are to be associated with the appropriate
5 physical quantities and are merely convenient labels applied
to these quantities. Unless specifically stated otherwise as
apparent from the following discussion, it is appreciated that
throughout the description, discussions utilizing terms such
as "processing" or "computing" or "calculating" or "deter20 mining" or "displaying" or the like, refer to the action and
processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data
similarly represented as physical quantities within the com25
puter system memories or registers or other such information storage, transmission or display devices.
The present invention also relates to apparatus for performing the operations herein. This apparatus may be spe30 cially constructed for the required purposes, or it may
comprise a general purpose computer selectively activated
or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer
readable storage medium, such as, but is not limited to, any
35 type of disk including floppy disks, optical disks,
CD-ROMs, and magnetic-optical disks, read only memories
(ROMs), random access memories (RAMs), EPROMs,
EEPROMs, magnetic or optical cards, or any type of media
suitable for storing electronic instructions, and each coupled
40 to a computer system bus.
The algorithms and displays presented herein are not
inherently related to any particular computer or other apparatus. Various general purpose systems may be used with
programs in accordance with the teachings herein, or it may
45 prove convenient to construct more specialized apparatus to
perform the required method steps. The required structure
for a variety of these systems will appear from the description below. In addition, the present invention is not
described with reference to any particular programming
so language. It will be appreciated that a variety of programming languages may be used to implement the teachings of
the invention as described herein.
A machine-readable medium includes any mechanism for
storing or transmitting information in a form readable by a
55 machine (e.g., a computer). For example, a machinereadable medium includes read only memory ("ROM");
random access memory ("RAM"); magnetic disk storage
media; optical storage media; flash memory devices;
electrical, optical, acoustical or other form of propagated
so signals (e.g., carrier waves, infrared signals, digital signals,
etc.); etc.
Overview
Efficient exploitation of spatial diversity in high-speed
wireless network is a challenging task due to the broadband
65 nature of spatial channel characteristics. In OFDMA
networks, the wide spectrum is partitioned into parallel
narrowband traffic channels. The methodology described

US 6,870,808 B1
5

6

herein increases, and potentially maximizes, the capacity of
A goal of broadband traffic channel assignment in
a broadband OFDMA/SDMA network through intelligent
OFDMA described herein is to allocate traffic channels to
traffic channel assignment.
new subscribers (in the presence of on-going traffics) in a
The concept of channel assignment for narrowband
way that increases, and potentially maximizes, the system
SDMA networks is illustrated in FIG. 1. In such application, 5 capacity. The process may be illustrated using FIG. 3.
each spatial channel can be described by a vector, referred
Referring to FIG. 3, on-going traffic identified by solid
to herein as a narrowband "spatial signature." For a system
blocks occupy certain numbers of OFDMA traffic channels
with M antenna elements, the spatial signature can be
(e.g., channels 1, 2, 3, and 6), some of which, e.g., traffic
represented as A i a i, where A i is a fading coefficient of
channel 1, are shared by more than one subscribers using
the channel and ai=[ali, a13 2i, . . . , a Mi] is an Mxl 10 spatial multiplexing. The unshaded blocks represent
vector that characterizes the relative complex gains between
OFDMA channels that are unoccupied (i.e., not being used).
antennas. The level of interference between co-channel
The shaded block represents traffic that is to be allocated or
subscribers (sharing the same spectral resource, e.g., the
assigned to one or more OFDMA channels.
same time slot/the same frequency/the same code (e.g., the
In one embodiment, several factors may be considered in
spreading code) is determined by the degree of orthogonality 15 determining which set of traffic channels are to be assigned
between their corresponding spatial signatures. (See Farsakh
to a new subscriber: (a) the channel fading conditions of the
et al., "On the Mobile Radio Capacity Increase Through
new subscriber at all traffic channels, (b) the spatial signaSDMA", Accessing, Transmission, Networking
ture vectors of the new subscriber across all traffic channels,
Proceedings, pp. 293-297, 1998.) Referring to the example
(c) the spatial signature vectors of on-going traffic, and (d)
in FIG. 1A, the spatial signatures of subscribers 1, 3, and 5 20 the data rate of on-going traffic of subscribers that have
are almost orthogonal, so are those of subscribers 2 and 4.
already been in communication with the base-station.
On the other hand, the spatial signatures of subscribers 1 and
In the communication system described herein, channel
2 are near aligned, indicating strong mutual interference
allocation logic performs "channel-aware" traffic channel
should they be assigned to the same traffic channel.
allocation. In one embodiment, the channel allocation logic
Conventional SDMA simply assigns subscribers to their 25 provides bandwidth on demand and efficient use of spectral
traffic channels (time slots in this case) in a pre-determined
resources (e.g., OFDMA traffic channels) and spatial
order. For example, in top of FIG. 1B, subscriber 1 and 2 are
resources (e.g., the physical location of subscribers as it
allocated to the same time slots, while being separated in
pertains to spatial beamforming) and performs traffic chanspace. Similarly, subscribers 3 and 4 are allocated to the
nel assignment based on broadband spatial channel characsame time slot while being separated in space. The possi- 30 teristics of a requesting subscriber and on-going subscribers.
bility of strong interference between co-channel subscribers
Thus, the channel allocation may reduce resource usage
(in this particular example: slot 1, between subscribers 1 and
(e.g., reduce usage of OFDMA channels).
2; slot 2, between subscribers 3 and 4) is high. To reduce the
In responding to a link request from a new subscriber, or
interference level and improve the system capacity, traffic
when the base-station has data to transmit to a standby
channels are assigned in a way that the most (if not all) 35 subscriber, the logic first estimates the spatial signature of
interfering subscribers are allocated to different time slots
the corresponding subscriber over all, or a predetermined
(as in bottom of FIG. 1B). By lifting the worst case
portion of OFDMA traffic channels. In one embodiment, the
performance, significant capacity gains can be achieved
estimated information, along with the spatial characteristics
using this strategy without undue complexity in spatial
of on-going subscribers are used to determine the achievable
processing.
40 rate of the accessing subscriber over each of the OFDMA
The channel assignment problem becomes much more
channels (with the presence of on-going SDMA
involved in broadband applications (e.g., broadband antenna
subscribers). In an alternative embodiment, the estimated
array systems, etc.) where the spatial signature is no longer
information and the spatial characteristics associated with
a vector. In the case of the OFDMA-based network
on-going traffic channels are used to determine the SINR of
described herein, high data rate traffic is accommodated with 45 the accessing subscriber over each of the OFDMA channels.
multiple low-rate (narrowband) data streams over orthogoThe spatial characteristics may be stored in a register or
nal narrowband traffic channels. These narrowband traffic
other type of storage location (e.g., a spatial signature
channels, centered at different frequencies, provide a parallel
register). In one embodiment, traffic channels that have the
structure for higher flexibility and ease of implementation.
highest achievable rates and will not affect the rates of
FIG. 2 illustrates such a structure in which high data rate so on-going traffic are assigned to the accessing subscriber to
traffic 201 is provided in the form of parallel data streams
satisfy the rate request of the accessing subscriber.
over orthogonal narrowband traffic channels centered at
In an alternative embodiment, traffic channels without the
different frequencies. As a result, the "broadband spatial
highest achievable rates may be allocated to a new
signature" associated with each subscriber becomes a twosubscriber, while leaving the traffic channels with the highdimensional matrix, or a set of narrowband spatial signature 55 est achievable rates to be allocated in the future. Similarly,
vectors that are a function of the frequency. In one
traffic channels that affect the rates of subscribers due to
embodiment, the spatial signature of subscriber i in OFDMA
some level of interference with on-going traffic may be
is given by
allocated in certain instances. For example, in one
[A it a il, A i2, . . . , A iK a iK],
embodiment, such allocations may occur because the
where A ik is the fading coefficient of traffic channel k, so achievable rate is so high that the degradation of on-going
a ik is the Mxl spatial signature vector of traffic channel k,
traffic is tolerable.
and K is the total number of OFDMA traffic channels (in
A base-station architecture that communicates with mulfrequency). When K-1, the above reduces to a narrowband
tiple subscribers in an OFDMA/SDMA fashion is also
setup. In contrast to the narrowband case where the spatial
disclosed. In one embodiment, the base-station includes
signature is "invariant" to the channel assignment, a broad- 65 multiple receiving antennas, each of which is connected to
band subscriber experiences different fading and spatial
a down-converter, an OFDM demodulator, a 2-D spatial
characteristics in different traffic channels.
signature estimator, an on-going traffic register and an

US 6,870,808 B1
7

8

on-going traffic spatial signature register, an OFDMA/
subscribers may affect the traffic rates of on-going subscribSDMA traffic channel allocation logic, an OFDMA medium
ers. Accordingly, in one embodiment, only traffic channels in
access controller, an OFDM modem, an OFDM broadband
which on-going traffic rates will not be affected by the
beamformer, multiple up-converters, and multiple transmisaddition of the new subscribers are reused. Alternatively,
sion antennas, each connected to one of the upconverters. 5 traffic channels in which on-going traffic is affected by a
FIG. 5 is a block diagram of an antenna array base-station
predetermined small amount (e.g., a tolerable amount for the
that communicates with multiple subscribers through
application) may be allocated. Other traffic channels are
OFDMA and spatial multiplexing. Referring to FIG. 5, the
shaded and marked "unusable" (in this case, traffic channels
base-station 500 comprises receiving antenna array 500, a
1, 5, K-1) to the new subscriber.
set of down-converters 501 coupled to receiving antenna to
FIG. 6 illustrates operations performed by one embodiarray 300, an OFDM demodulator 502, a broadband (2-D)
ment of the traffic channel allocation logic. Referring to FIG.
spatial signature estimator 503, an on-going traffic register
6, inputs to the channel allocation logic include the 2-D
504, an OFDMA/SDMA traffic channel allocation logic 505,
spatial signature of the accessing subscriber, A new,1
an on-going traffic spatial signature register 506, an OFDMA
a new,l, . . . , A new,K a new,K; the requested data rate,
medium access controller (MAC) 507, an OFDM modem 15 R new from storage (not shown); the data rates of on-going
510, a set of parallel narrowband beamformers 509, a set of
traffic in each of the traffic channels from on-going traffic
up-converters 508 and a transmission antenna array 511.
storage 601; and the 2-D spatial signatures of on-going
Uplink signals, including the accessing signal from a
subscribers from storage 602.
requesting subscriber, are received by receiving antenna
In one embodiment, the logic starts a loop from traffic
array 500 and down-converted to the base-band by down- 20 channel 1 to traffic channel K and calculates the achievable
converters 501. The base-band signal is demodulated by
rate for the accessing subscriber over each of the traffic
OFDM demodulator 502 and also processed by the 2-D
channels. The results, R new,l,
, R new,K, are saved for
spatial signature estimator 503 for estimation of the accessfurther evaluation. In another embodiment, the logic calcuing subscriber's broadband spatial signature using, e.g., an
lates the SINRs in a manner well-known in the art for the
FFT based spatial signature estimator or other well-known 25 requesting subscriber over each of the traffic channels.
parametric spatial channel estimation algorithms. The estiIn calculating the achievable rate or the SINR value,
mated 2-D spatial signature, along with spatial signature of
different spatial processing algorithms, e.g., single-user
subscribers corresponding to on-going traffic stored in the
detection and multi-user detection, may be used. The achievon-going traffic spatial signature register 506 and on-going
able rate or the SINR value depends on the actual spatial
traffic information stored in the on-going traffic register 504, 30 processing algorithm used in practice.
are fed to OFDMA/SDMA traffic channel allocation logic
Also calculated are the achievable rates of on-going
505 to determine a traffic channel assignment for the accesssubscribers at each of the traffic channels with on-going
ing subscriber, and possibly partial or all of the on-going
traffic for the case that the requesting subscriber is added to
subscribers. The results are sent to OFDMA MAC 507 that
that traffic channel: R i,k, k=1, . . . , K. Similarly, in an
controls the overall traffic.
35 alternative embodiment, the logic can calculate the SINR
Control signals from OFDMA MAC 507 and downlink
values of on-going subscriber at each of the traffic channels,
data streams 520 are mixed and modulated by OFDM
for that case that the requesting subscriber is added to that
modulator 510 for downlink transmission. Spatial beamtraffic channel.
forming can be applied with a set of parallel narrowband
The logic then examines whether these updated achievbeamformers 509 using spatial information stored in the 40 able rates (or SINRs) are lower than the actual rates (or
on-going traffic spatial signature register 506. Specifically,
SINR) requirements of subscribers with on-going traffic
the beamforming coefficients used by beamformers-509 are
(e.g., a minimum data rate requirement that must be
calculated based on each subscriber's spatial signature. The
satisfied). Note the actual rate may be higher when extra
output of beamformers 509 are up-converted by the set of
resources are available of subscribers with on-going traffic.
up-converters 508, and transmitted through transmission 45 Traffic channels in which the requesting subscriber is added
antenna array 511.
and, therefore, in which the new rates or SINRs drop below
In order to find one traffic channel assignment for the
the on-going rates or SINR thresholds are labeled "unusrequesting subscriber, the traffic channel allocation logic
able" for the requesting subscriber. The remaining traffic
first ranks all traffic channels in the order of the so-called
channels are ranked and assigned in a descending order of
achievable rate for the subscriber. In one embodiment, the 50 the achievable rates or SINR values for the requesting
achievable rate of the requesting subscriber over a particular
subscribers. The thresholds may be set to ensure a specific
traffic channel is limited by the noise power, its channel
signal quality at a particular data rate.
fading coefficient, and the spatial signatures of all
The process stops when the total rates for the requesting
co-channels subscribers in this channel. Other factors
subscriber exceed a pre-determined value for the requesting
include the actual signal processing/communication tech- 55 subscriber.
niques employed to separate the co-channel subscribers.
Other criteria, e.g., the mean-squared errors of the spatial
Once the signal processing/communication techniques (e.g.,
multiplexing outputs, the packet error rate in the case of
technology for multi-user beam forming to separate multiple
packet data, etc., can be used for channel allocations in place
users) are selected, the base-station calculates the achievable
of, or in addition to, the achievable rate.
data rate for the accessing subscriber and ongoing subscriber so
Other Quality of Service (QoS) requirements of the new
(s) over each of the traffic channels as shown in FIG. 4.
subscriber or other subscribers with on-going traffic, e.g., the
Referring to FIG. 4, traffic channels in which on-going traffic
packet delay, the throughput, and bit-error-rate, can be used
are affected with the addition of accessing subscriber are
in place of, or together with, the achievable rate or the SINR
shaded. In one embodiment, for the accessing subscriber, its
value in channel allocation.
most favorable traffic channels are those corresponding to 65
Whereas many alterations and modifications of the
the highest rates, e.g., traffic channels 5, 4, 3, . . . However,
present invention will no doubt become apparent to a person
adding a new subscriber to a traffic channel with on-going
of ordinary skill in the art after having read the foregoing

US 6,870,808 B1
9
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, references 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 network comprising:
a base station; and
a plurality of subscriber units to communicate with the
base station using an orthogonal frequency-division
multiple-access (OFDMA) protocol;
the base station including
a memory to store broadband spatial signature vectors
associated with each subscriber, the vectors being a
function of frequency; and
traffic channel allocation logic to allocate OFDMA
channels using the broadband spatial signature vectors of the subscribers.
2. The network defined in claim 1 wherein the broadband
spatial signature vectors are indicative of fading and spatial
characteristics of the subscribers.
3. The network defined in claim 1 wherein at least one of
the spatial signature vectors is indicative of channel fading
conditions of a new subscriber at all OFDMA traffic channels.
4. The network defined in claim 1 further comprising data
rate storage for storing information indicative of the data
rate of on-going traffic.
5. The network defined in claim 1 wherein the traffic
channel allocation logic allocates the OFDMA channels, in
response to 2-D spatial signatures of an accessing subscriber
and one or more subscribers with on-going traffic and data
rates of on-going traffic, by selecting OFDMA channels,
based on calculated achievable rates for the accessing subscriber to achieve a requested data rate and for the one or
more subscribers at each of the OFDMA channels.
6. The network defined in claim 1 wherein the traffic
channel allocation logic allocates the OFDMA channels, in
response to receiving 2-D spatial signatures of an accessing
subscriber and one or more subscribers with on-going traffic
and data rates of on-going traffic, by:
calculating an achievable rate for the accessing subscriber
unit over each of the OFDMA channels,
calculating updated achievable rates of subscribers at each
of the OFDMA channels with on-going traffic as if the
accessing subscriber is added to said each of the
OFDMA channels, and
selecting OFDMA channels, based on achievable rates,
for use by the accessing subscriber to achieve a
requested data rate.
7. The network defined in claim 1 wherein the traffic
channel allocation logic comprises:
a first input for a two-dimensional (2-D) spatial signature
of an accessing subscriber;
a second input for a requested data rate of the accessing
subscriber;
a third input for data rates of on-going traffic in each of the
plurality of OFDMA channels;
a fourth input for 2-D spatial signatures of on-going
subscribers;
achievable rate calculation logic coupled to the first,
second, third, and fourth inputs to calculate an achievable rate for the accessing subscriber over each of the
OFDMA channels and calculates updated achievable

5

10

15

20

25

30

35

4

45

50

55

60

65

10
rates of subscribers at each of the OFDMA channels
with on-going traffic as if the accessing subscriber is
added to said each of the OFDMA channels; and
channel selection logic coupled to the achievable rate
calculation logic to select OFDMA channels, based on
achievable rates, for use by the accessing subscriber to
achieve the requested data rate.
8. The network defined in claim 7 wherein the channel
selection logic does not allocate OFDMA channels in which
calculated updated achievable rates are lower than actual
rates of subscribers with on-going traffic.
9. The network defined in claim 1 wherein the traffic
channel allocation logic allocates the OFDMA channels, in
response to receiving 2-D spatial signatures of an accessing
subscriber and one or more subscribers with on-going traffic
and data rates of on-going traffic, by selecting OFDMA
channels, based on SINRs, for use by the accessing subscriber.
10. The network defined in claim 1 wherein the traffic
channel allocation logic allocates the OFDMA channels, in
response to 2-D spatial signatures of an accessing subscriber
and one or more subscribers with on-going traffic and data
rates of on-going traffic, by:
calculating signal-plus-interference to noise ratios
(SINRs) for the accessing subscriber over each of the
OFDMA channels;
calculating updated SINRs of subscribers at each of the
OFDMA channels with on-going traffic as if the accessing subscriber is added to said each of the OFDMA
channels; and
selecting OFDMA channels, based on SINRs, for use by
the accessing subscriber.
11. The network defined in claim 1 wherein the traffic
channel allocation logic comprises:
a first input for a two-dimensional (2-D) spatial signature
of an accessing subscriber;
a second input for a requested data rate of the accessing
subscriber;
a third input for data rates of on-going traffic in each of the
plurality of OFDMA channels;
a fourth input for 2-D spatial signatures of on-going
subscribers;
calculation logic coupled to the first, second, third, and
fourth inputs to calculate signal-plus-interference to
noise ratio (SINRs) for the accessing subscriber over
each of the OFDMA channels and calculates updated
SINRs of subscribers at each of the OFDMA channels
with on-going traffic as if the accessing subscriber is
added to said each of the OFDMA channels; and
channel selection logic coupled to the calculation logic to
select OFDMA channels, based on SINRs, for use by
the accessing subscriber.
12. The network defined in claim 11 wherein the channel
selection logic does not allocate OFDMA channels in which
calculated updated SINRs are lower than actual SINRs of
subscribers with on-going traffic.
13. The network defined in claim 1 wherein the broadband
spatial signature vectors of the subscribers are 2-D spatial
signature vectors.
14. A method comprising:
determining frequency and spatial characteristics of a
plurality of orthogonal frequency division multiple
access (OFDMA) channels for a new subscriber and
one or more subscribers with on-going traffic;
allocating a subscriber one or more OFDMA channels
based on 2-D spatial signature vectors of the new

US 6,870,808 B1
11

12

subscriber and other subscribers with on-going traffic
allocating candidate traffic channels to the requesting
and data rates of on-going traffic.
subscriber unit to satisfy the requested data rate.
15. The method defined in claim 14 further comprising:
26. The method defined in claim 25 wherein determining
the achievable rate of the requesting subscriber comprises
assigning OFDMA/space-division multiple-access
(SDMA) traffic channels to multiple access subscribers 5 using single-user detection or multi-user detection.
27. The method defined in claim 25 wherein performing
based on broadband channel characteristics, wherein
spatial multiplexing includes performing single-user beamthe broadband channel characteristics comprise space
forming and multi-user beamforming.
and frequency characteristics.
28. The method defined in claim 25 wherein allocating
16. A method comprising:
estimating spatial and frequency characteristics of propa- 10 candidate traffic channels comprises performing channel
allocation based on reducing resource usage while satisfying
gation channels using an FFT-based or parametric
the QoS requirements of the subscriber.
channel estimation algorithm between a base station
29. The method defined in claim 28 wherein performing
and a new subscriber;
channel allocation is based on minimizing the resource
accommodating a rate request of the new subscriber by
15 usage.
assigning OFDMA traffic channels that use a first
30. The method defined in claim 25 wherein determining
amount of transmission power and cause a second
the achievable rate of the requesting subscriber over each of
amount of interference to co-channel subscribers.
the OFDMA traffic channels and calculating the new achiev17. The method defined in claim 16 wherein estimating
able rate of the at least one other subscriber with on-going
characteristics of propagation channels is performed using a
20 traffic occurs based on 2-D spatial signatures of the requestFVF-based or parametric channel estimation algorithm.
ing subscriber and the at least one other subscriber with
18. The method defined in claim 16 wherein the first
on-going traffic and data rates of on-going traffic.
amount comprises a minimum amount of transmission
31. A base station comprising:
power as compared to other OFDMA channels not assigned
a plurality of receiving antennas;
to the new subscriber.
25
a plurality of down converters coupled to the plurality of
19. The method defined in claim 16 wherein the second
receiving antennas;
amount comprises the least amount of interference caused to
co-channel subscribers in comparison to interference caused
a new accessing subscriber spatial signature register;
to one or more subscribers if using one or more of the
an on-going traffic spatial signature register; and
OFDMA traffic channels that are not assigned to the new
an OFDMA traffic channel allocator coupled to the new
30
subscriber.
accessing subscriber spatial signature register and the
20. The method defined in claim 16 wherein estimating
on-going traffic spatial signature register.
spatial and frequency characteristics comprise estimating a
32. The base station defined in claim 31 wherein the
2-D spatial signature of the new subscriber over a predeterchannel allocation logic allocates OFDMA channels to a
mined number of OFDMA channels.
35 new subscriber based on information from the new sub21. The method defined in claim 16 wherein the predescriber spatial signature register and the on-going traffic
termined number of OFDMA channels comprises all of the
spatial signature register.
OFDMA channels.
33. The base station defined in claim 31 further compris22. The method defined in claim 16 further comprising
ing:
determining an achievable rate of the new subscriber over
40
an OFDMA medium access control (MAC) logic coupled
each of the OFDMA channels with a presence of on-going
to the channel allocator;
subscribers.
an OFDM modulator coupled to the OFDMA MAC logic;
23. The method defined in claim 22 wherein determining
a plurality of parallel narrowband beamformers coupled
the achievable rate is performed using spatial characteristics
to the OFDM modulation;
of on-going traffic and a 2-D spatial signature of the new
45
a plurality of upconverters coupled to the plurality of
subscriber over all of the OFDMA traffic channels.
beamformers; and
24. The method defined in claim 16 further comprising
assigning, to the new subscriber, OFDMA traffic channels
a plurality of transmitting antennas coupled to the pluralwith the highest achievable rates and least effect on other
ity of upconverters.
subscribers with on-going traffic over some portion of the
34. The base station defined in claim 1 wherein the new
5
OFDMA channels.
accessing subscriber spatial signature register and the
25. A method of assigning orthogonal frequency-division
on-going traffic spatial signature register store 2-D spatial
multiple-access (OFDMA) traffic channels in conjunction
signatures.
with a space-division multiple access (SDMA) protocol
35. A base station comprising:
comprising:
a plurality of receiving antennas;
55
estimating broadband spatial and frequency channel chara plurality of down converters coupled to the plurality of
acteristics of a requesting subscriber;
receiving antennas;
determining, for each of the OFDMA traffic channel, an
a new accessing subscriber spatial signature register;
achievable rate of the requesting subscriber over each
an on-going traffic spatial signature register; and
of the OFDMA traffic channels;
so
an OFDMA traffic channel allocator coupled to the new
calculating, for each of the OFDMA traffic channel, a new
accessing subscriber spatial signature register and the
achievable rate of at least one other subscriber with
on-going traffic spatial signature register, wherein the
on-going traffic on one or more of the OFDMA traffic
channel allocator comprises
channels if the at least one other subscriber is to share
a first input for a two-dimensional (2-D) spatial signathe one or more OFDMA traffic channels with the 65
ture of an accessing subscriber;
requesting subscriber;
a second input for a requested data rate of the accessing
determining candidate traffic channels; and
subscriber;

US 6,870,808 B1
14

13
a third input for data rates of on-going traffic in each of
the plurality of OFDMA channels;
a fourth input for 2-D spatial signatures of on-going
subscribers;
achievable rate calculation logic coupled to the first,
second, third, and fourth inputs to calculate an
achievable rate for the accessing subscriber over
each of the OFDMA channels and calculates updated
achievable rates of subscribers at each of the
OFDMA channels with on-going traffic as if the
accessing subscriber is added to said each of the
OFDMA channels; and
channel selection logic coupled to the achievable rate
calculation logic to select OFDMA channels, based
on achievable rates, for use by the accessing subscriber to achieve the requested data rate.
36. The base station defined in claim 35 wherein the
channel selection logic does not allocate OFDMA channels
in which calculated updated achievable rates are lower than
actual rates of subscribers with on-going traffic.
37. A base station comprising:
a plurality of receiving antennas;
a plurality of down converters coupled to the plurality of
receiving antennas;
a new accessing subscriber spatial signature register;
an on-going traffic spatial signature register; and
an OFDMA traffic channel allocator coupled to the new
accessing subscriber spatial signature resister and the
on-going traffic spatial signature register, wherein the
channel allocator comprises
a first input for a two-dimensional (2-D) spatial signature of an accessing subscriber;
a second input for a requested data rate of the accessing
subscriber;
a third input for data rates of on-going traffic in each of
the plurality of OFDMA channels;
a fourth input for 2-D spatial signatures of on-going
subscribers;
calculation logic coupled to the first, second, third, and
fourth inputs to calculate signal-plus-interference to
noise ratio (SINRs) for the accessing subscriber over
each of the OFDMA channels and calculates updated
SINRs of subscribers at each of the OFDMA channels with on-going traffic as if the accessing subscriber is added to said each of the OFDMA channels; and
channel selection logic coupled to the calculation logic
to select OFDMA channels, based on SINRs, for use
by the accessing subscriber.
38. The base station defined in claim 35 wherein the
channel selection logic does not allocate OFDMA channels

in which calculated updated SINRs are lower than actual
SINRs of subscribers with on-going traffic.
39. A method comprising:
determining frequency and spatial characteristics of a
5
plurality of orthogonal frequency division multiple
access (OFDMA) channels for a new subscriber and
one or more subscribers with on-going traffic;
ro

15

20

25

30

35

40

45

so

allocating a subscriber one or more OFDMA channels
based on on-going traffic among the OFDMA channels,
including selecting OFDMA channels, in response to
2-D spatial signatures of the new subscriber and one or
more subscribers with on-going traffic and data rates of
on-going traffic, based on calculated achievable rates
for the new subscriber to achieve a requested data rate
and for the one or more subscribers at each of the
OFDMA channels.
40. The method defined in claim 39 further comprising:
calculating an achievable rate for a new subscriber unit
over each of the OFDMA channels,
calculating updated achievable rates of subscribers at each
of the OFDMA channels with on-going traffic as if the
new subscriber is added to said each of the OFDMA
channels, and wherein the OFDMA channels are
selected, based on achievable rates, for use by the new
subscriber to achieve a requested data rate.
41. A method comprising:
determining frequency and spatial characteristics of a
plurality of orthogonal frequency division multiple
access (OFDMA) channels for a new subscriber and
one or more subscribers with on-going traffic;
allocating a subscriber one or more OFDMA channels
based on on-going traffic among the OFDMA channels,
including selecting OFDMA channels, in response to
2-D spatial signatures of the new subscriber and one or
more subscribers with on-going traffic and data rates of
on-going traffic, based on SINRs, for use by the new
subscriber.
42. The method defined in claim 41 further comprising:
calculating signal-plus-interference to noise ratios
(SINRs) for the new subscriber over each of the
OFDMA channels;
calculating updated SINRs of subscribers at each of the
OFDMA channels with on-going traffic as if the new
subscriber is added to said each of the OFDMA channels; and wherein the OFDMA channels are selected,
based on SINRs, for use by the accessing subscriber.