Note: Descriptions are shown in the official language in which they were submitted.
CA 02675225 2009-08-27
JOINT COMMUNICATION AND ELECTROMAGNETIC
OPTIMIZATION OF A MULTIPLE-INPUT MULTIPLE-
OUTPUT ULTRA WIDEBAND BASE STATION ANTENNA
FIELD OF niE IN'VENTION
[0001] This invention relates to multi-user antenna in general and methods of
configuring antennas in an array in particular.
BACKGROLTND OF THE INVENTION
[00021 Pecent work in the area of wireless cornmunications has shown that
when antenna placements in a two-by-two MIMQ system are on the order of a
symbol wavelengtb rather than the carrier wavelength, significaizt
improvements
can be made with respect to performance_ This has given rise to the term of
Signaling Wavelength Antenna Placement (SWAP) Gain to describe the advantages.
The prexnise of this finding is that when the antennas are spaced a symbol
wavelength apart, the likelihood that the channels are correlated is minimaI.
[a003] However, determiniuzg the optimum placement of the antennas is seei-i
as a highly non-linear problem that depends on the number of antennas in the
systerxi, and distribution of the users in the three-dimensior-al wireless
comznunicatiton space_
MIMO Systems
[00041 A MIMO system makes use of multiple antennas to exploit spatial
diversity. By placing the antennas some distance apart, the received signals
from the
same user will appear at each antenna in the system. Si;nce the radio channel
in
many systems is often impaired by effects such as random noise, multipath
interference, co-channel interference (CCI), and adjacent channel
interference, the
resultiazg signals at each antenna will be different in terms of the channel
irnpulse
I
CA 02675225 2009-08-27
response [1], [21. The noise and interference can be considered to be
uncorrelated,
while the message sigzial. appearing at each antenna will retain some
correlation.
However, in cases where the antenna placements are similar, there exists the
pxobabiiity that the noise and interference will be correlated [3], [4], [5]_
[0005] In general, any M-by-N MIMO system configu.ration caiz be modeled
as a matrix of channel impulse finctions from the Mth user to the Nth antenna.
Typically, a wireless communicatiom.s system will rely on a large base station
that
handles the requests from the mobile users in the cell. An example of a mobile
user
placement and antenna placement configuration of a four-by-four system is
shown
in FIG_ 1.
[0006] In the research area of wireless commtznications, current generation
systems are constantly being irnproved upon, with the advances becoming part
of
the next generation of standards. MTMO systems make use of znultiple antennas
to
achieve spatial diversity and h:igh perfoxmance [6], M. Recent work in the
area of
wireless cornmunicatxons has shown that when antenna placements in a two-by-
two
MIMO system are on the order of a symbol wavelength ([speed of light]/[symbol
rate]), rather than the carrier wavelength, significant improvements can be
made
with respect to multiuser performance [8], [9], [10]_ This has given rise to
the term
Signaling Wavelength Antenna Placement (SWAP) Gain to describe the advantages.
The premise of this finding is that when the antennas are spaced a symbol
wavelength, or more, the likelihood that the bits are correlated is mini???=i1
and the
array receives more information. When used in conjunction with an ultra
wideband
(LYWS) spectrum, the communication system holds the potential of deIivering
high-
speed data services to many users [9], [11].
[0007] Much of the M1MO work to date relies heavily on assurning a
randomized multipath rich environmezit to realize the maximum gains frorn
spatial
diversity 16], [12]. The fading characteristics are often modelled as Rayleigh
2
CA 02675225 2009-08-27
distributions. However, in close range indoor situations, the Line of SignaI
(LOS) can
often dominat.e the multipath components (modelled as Ricean distributions),
minimizing the prospective gains from MZMO techniques. It is therefore
necessary
to examine MIMO perfornmance in LOS situations.
[0008] Currently, the problem associated with effective M[MO UWB base
station antennas is that they are large. The optimization of the MIMO UWB base
station antenna is seen as a higWy non-linear problem. Therefore, analytically
a
global optimization is difficult to achieve through traditional z=nethods. An
exhaustive trial-and-error method would be able to determine the optimal
arrangement, but as the complexity of the system increases, the computational
requirements for this method increase exponentially. Also, as wireless systems
Taecome ubiquitous, there exists the need to accommodate increasing data
rates, but
also increasing device numbers [13], [14].
[0009] By strategically arranging the antennas in the system to take advantage
of the SWAP Gaun, an optimal placement exists that will maximize the
performance
of the MIMO system in an LOS situation [15]. Also, by intentionally placing
xet7.ectors in the form of plates and/or solid slzsped surfaces, in front of,
behind, and
around the receiving elements to purposely introduce multipath components into
an
LOS situation, the spatial diversity perforznance gains from MIlvMO techniques
are
improved and overcome the once-dominant LOS component The extra mu.ltipath
components introduced by the reflectors effectively scramble the communication
channel between a transmitter and receiver in a fashion that increases the
MIMO
processing gains.
[0010] However, determining the optimum pXaceznent of antennas and
arrangement of reflectors is seen as a hi,ghly non-linear computafiionally
difficult
problem that depends on the number of antennas in the system, placement and
orientation of reflectors, the radio channel bandwidth, the symbol rate,
fading, and
3
CA 02675225 2009-08-27
the distribution of the users in the wireless communication cc1l [16], [1].
Througli the
use af a GA optirrmization, for a given placement of users in the cell, an
optirnum
antenna and reflector placement i.s achieved. GA optimization has seen success
in
many non-linear apptications, but often the results from these optiunizations
need
int-expretatior< [171, [18], [19]. The algorithm can canverge to a local
maxim.a/rniniina
point rather than reach a global solution. The presence of these vestigial
structures
can prove to be a problem when attempting to gain information from the
results. In
such cases, it is important to evaluate the results in comparison to a known
upper
bound to give an indication on how well the GA optimization is performing.
Spread Spectrum Techniques
[00111 In code division rnultiple access (CDMA) systems, such as the
Evolution-Data Optimized (EVDO) standard and direct sequence ultra wideband
(DS-UWb), multiple users are multiplexed and transmitted over the same channel
by using K-length pseudo random noise maximum length binary sequences, where
K is the spreading factor [201, [21]. The resulting signal from a single user
is thus
increased in band-width by a factor of K. The summation of the signals from
the
total users produces an orthogonal signal set such that the originaI users
signal can
be de-multiplexed from the resultant signal by using the same generating code
on
the receive end of the cha.nnel [22], [231.
[0012] Some of the disadvantages of CDMA schernes are that they are
affected more by multiple access interferenCe (MAI) and intersymbol
interference
(ZSI) [131- To allow for this, a spreading factor greater than the expected
capacity is
used, resulting in a greater grade of service (GOS) at the expense of more
bandwidth.
Symbol Wavelength
[0013] The symbol wavelength, Ar, is defined as
4
CA 02675225 2009-08-27
~~= f
T
(Eq- x)
where c is the speed oiE light and f7 is the symbol rate. It has been shown by
Yanikomeroglu et al. [$], [10] that by placing antennas on the order of a
chiplength
that a greater diversity gain is achieved as opposed to traditional carrier
wavelength
spacing. For purposes of comparison, the antenna separations in the GA
optimization simulation have been normalized with respect to the symbol
wavelength.
Radio Channel
[0014] The mobile radio channel is inherently noisy and cluttered with
interference from other mobiles and rnultipat.h reflections. The overall
performance
of a wireless communication system is concerned with the multiple ways to
improve
the signal-to-interference-plus-noise Ratio (SINR). In 1948, Shannon
demonstrated
that through proper encoding in certain conditions, errors can be reduced to
any
desired level without sacrificing the rate of information transfer [24]. This
led to
what is known as Shannon's channel capacity formula given by
G' = B lcr92(1+ s
JNT
(Eq. 2)
where C is the channel capacity (bits per second), B is the transmission
bandwidth
(Hz), S is the signal power (W), and Nis the noise power (W).
LMS Adaptive Filter
[00151 The least mean square (LMS) adaptive filter is another proven cozxcept
that has shown great performaxtce and widespread use due to its robustness and
CA 02675225 2009-08-27
ease of implernenta.tion [16], [25), [26]. The basic setup of an LMS adaptive
filter is
shown in FIG. 2.
[00161 In this arrangement, the data stream to be txansmitted is given by d,,,
a
denotes the spreading code applied to the data, b represents the wireless
channel
response, ~n is the Additive White Gaussian Noise (AWGN), r,, is the signal
received
at the antenna, M is the adaptive filfer coefficient, d'n is the filtered
received signal,
e,, is the error associated with the filtered received signal, and n is the
discrete-time
index.
[00171 During training, the receiver knows d, as the training sequence would
be programmed into fl1e adaptive filter logic. It will then update the filter
coefficient
Wõ according to
4ot+1 = W. -~- lAer-.,
(Eq- 3)
where Wõ+i is the updated filter coefficient, Wn is the current filter
coefficient, and yc
is the LMS adaptation constant, which is chosen to be small enough such that
the
filter will converge. If p is chosen to be too large, the adaptation will
diverge and the
rnin;iXnum mean square error (MMSE) will not be reached.
[0015] After the filter has finished processing the training sequence, the
filter
then switches from operating on the training sequence and continues to adapt
frorn
the incoming signal. Ideally at this point the adaptive filter has converged
and has
successfully performed the channel inversion to create a matched filter and
remains
at the global min;munt rather than diverging off to some other local minimum.
Generalizing this scalar example to vectors leads to the usual form
W..Fa = W. (Eq. 4)
6
CA 02675225 2009-08-27
[0019] where Wõ+, is vector of the updated filter coefficients, W., is a
vector of
the current filter coefficients, ye is the LNiS adaptation constant, en is a
vector of the
error associated with the filtered receive signal, and rõ is a vector of the
signals
received at the antenna.
Genetic Algorithms
[0020] G.A. optirnization borrows on the ideas of evolution found in the
everyday biology of living organisms- First discussed in Charles Darwiui s
Origin of
Species, the concept is that every living organism that exists today is a
result of a
process of evolution over the many generations that the population has existed
for
over great lengths of time. Within every cell of an organism, a genetic
blueprint is
contained within a chemical substance called deoxyriboiiuclCic acid (DNA).
This
chernical substance is in a double-helical structure and contains cozttinuaus
base
pairs of the nticleotides adenine (A), thymine (T), guanine (G) and cytosine
(C). The
sequencing of tlzese nucleotides provides the basic genetic code that is
capable of
completely reproducing the organism in which the DNA is contained [17], [18].
Thus, the term DNA becomes synonymous with the minimum number of describing
features that is required to fully recreate an individual or organism.
[00211 Traztslating this to science and engineering problems, a set of
possible
solutions becomes the population of ]iving organisms. This population is then
evaluated to determine their fitness to performing the desired goal defined in
the
problem. Such as in nature, the individuals are then subjected to a survival
of the
fittest evaluation, where only a portion of the top performing individuals are
retained for the next generation. These top performing individuals are also
chosen to
be the parents for the succeeding population. These parents then generate
offspring
to fiIl the population. The offspring are generated in primarily two
rnechanisms,
through crossover and mutation.
7
CA 02675225 2009-08-27
[00221 One of the advantages of GAs is that they are capable of operating on a
problem that has a very large set of possible solutions [17], [19]. A problem
with a
large set of solutions may not be computationally practical to investigate
through
"brute force" methods. This leads to the advantage that genetic algorithms
will often
lead to solutions that would otherwise not have been reached through cornmon
numerical techniques.
SUMMARY OF THE INVENTION
[0023] This invention teaches a high-performxng antenna that is compact and
easier to implement in a practical envirozzment. A joint cornmunication and
electxor,nagnetic optimizatian of a 1VII1V10 iJWS base station antenna is
achieved by
implementing a two-dimensional (2-D) design in an LOS situation to optimiz.e
antexizia placements, and designing in three-dimensions (3-D) that will make
use of
reflectors to izurease the apparent electromagnetic and communication size of
the
antenna, and exploiting the advantages gained by using symbol-wavelength
spacing.
[0024] According to one embodiment, the present invention relates to a
method for generating a configuration of elements for a multi-input and multi-
output multi-user antenna array system comprising the steps of selecting
elements
from the group consisting of at least two antennas and, at least one antenna
arxd at
least one electromagnetic signal modifying element; and applying a genetic
algorithm to the antezutas to generate an antenna axray configuration in which
the
antennas form an asymmetric.array and where the array system is optimized for
multi-user performance.
100251 According to another embodiment, the present invention relates to a
multi-input and multi-output multi-user antenna array system cornprising an
asymrnetric array of antennas optimized for multi-user performance.
8
CA 02675225 2009-08-27
[0026] According to another embodiment, the present invention relates to a
method configuration or placement of antennas in an array for a given
placement of
users in a space. Antennas which can be placed include oxnni-directional,
monopole, dipole, and microstrip antennas.
[00271 According to another embodiment, the present invention relates to a
method for deternv.ning the optimum MIMO performance using omni-directional
antennas in an array over LOS radio channels through genetic algorithm
optimization.
[0028] In one embodirnent, the MIMO system has been restricted to 2-D space
and only opkzrrdzes the placement of the antennas through a genetic algorithm
by
evaluating the LC75 signal.
[00291 In another embodiment, the design space for the antenna placement
and user placement is extended to 3-D space.
[00301 In yet another embodiment, reflector elements are incorporated as part
of the design to purposely introduce random reflections to create additional
multi-
path components that will be received by the antennas. By adding these
reflectors to
the system, the MIIviO system behaves as a multi-path rich environment in what
was previously dominated by the LOS component. The number, placement, size,
shape and orientation of these reflectors are determined using a genetic
algorithrn.
[0031] In yet another embodiment, users are placed randornly in the cell to
deterxnine the optimum MIMO performance for all placemerits of users.
[0032] In yet another embodisnent, radiation patterns are added to the
antenna model instead of using the simple omni-directional case.
[0033] Other aspects and features of the present invention will become
apparent to those ordinarily skilled in the art upon review of the following
9
CA 02675225 2009-08-27
description of specific embodiments in conjunction with the accompanying
drawing
figures.
BRIEF DESCRIP'I'YON OF THE DRAWINGS
[0034] Embodiments of the present invention will now be described, by way
of example oxn1y, with reference to the accompanying drawings figures, whereix-
l-
100351 FIG. 1 is a depiction of a four-by-four arrangement for a MIM(] systern
with mobile users placed around the antenna arrangement at the center of the
cell;
[00361 FIG_ 2 is a block diagram of the described simple LMS adaptive filter;
[0037] FIG. 3 is a graph showing the LMS adaptive filter coefficients, Wn, in
terms of tap energy, versus the coefficient index, in a four-by-four MIMO
system, for
each user to antenna cha.nnel;
[00381 FIG. 4 is a graph showing the Ieariurig curves for each user in a fov.r-
by-four MIMG system, displayed as log squared error versus time index;
[0039] FIG. 5 is a depiction of the crossover process in which a new offspring
is created by inheriting attributes from two selected elite parents;
[0040] FIG. 6 is a depieion of the mutation process in which a new offspring
is created by adding perturbations to the attributes of a Tandornly selected
elite
individual;
[00411 FIG. 7 is a generalized flow chart for the CA optimization process;
[0042] FIG. 8 is a configuration used for the placement of the mobile users in
the cell;
CA 02675225 2009-08-27
10043] FIG. 9 is a graph showing the total va7iance of the antenna placements
versus the generation index, y, in a four-by-three MIMO system using the
rnobile
user placement in FIG. 8 and a crossover ratio of 0;
C00441 FIG. 10 is a graph showing the total variance of the antenna
placements rrersus the generation index, y, in a four-by-three MIMO system
using
the mobile user placement in FIG. 8 and a crossover ratio of 0.5;
j0045] FIG. 11 is a graph showing the tot~~l varian.ce of the antenna
placements versus the generation index, y, in a four-by-four MIMO system using
the
mobile user placement hz FIG. 8 and a crossover ratio of 0;
[0046] FTG. 12 is a graph showing the total variance of the antenna
placements versus the generation index, y, in a four-by-four MIMO system using
the
mobile user placement in FIG. 8 and a crossover ratio of 0.5;
[00471 FIG- 13 is a graph showing the total variance of the antenna
placements versus the generation index, y, in a fovr-by-five MIMO system using
the
mobile user placement in FIG. 8 and a crossover ratio of 0;
[0048] FIG. 14 is a graph showing the total variance of the antenna
placements versus the generation index, y, in a four-by-five MIMO system using
the
mobile user placement in FIG. 8 and a crossover ratio of 0.5;
[0049] FIG. 15 is a graph showing the anterma placements in a four-by-three
system for the top 10% using the mobile user placement in FIG. 8 and a
crossover
ratio of 0.5 after 100 generations;
r0050] FIG. 16 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after I
generation;
11
CA 02675225 2009-08-27
100511 FIG. 17 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after 5
generations;
[0052] FIG. 18 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement, in FIG. 8 and a crossover ratio of 0.5
after
generations;
100531 FIG. 19 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after 20
generations;
[0054] FIG. 20 is a graph showing all antenna placements in a four-by-four
system using the mobile user placemenf in FIG. 8 and a crossover ratio of 0.5
after 30
generatioxtis;
[00551 FIG. 21 is a graph showing all antenna placements in a four-by-four
system using the rnobile user placement in FIG. 8 and a crossover ratio of 0.5
after 40
generations;
[0056] FIG. 22 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after 50
generations;
100571 FIG. 23 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. S and a crossover ratio of 0.5
after 60
generations;
[0058] FIG. 24 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0_5
after 70
generations;
12
CA 02675225 2009-08-27
100591 FIG. 25 is a graph showing aII antenna placements in a four-by-four
system using the mobile user placement; in FIG. 8 and a crossover ratio of 0.5
after
80 generations;
[0060] FIG. 26 is a graph showing all antenna placements in a four.-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after 90
generations;
[0061] FIG. 27 is a graph showing all antenna placements in a four-by-four
system using the mobile user placement in FIG. 8 and a crossover ratio of 0.5
after
100 genexations;
[0062] FIG. 28 is a graph showing anterna placements in a four-by-four
system for the top 10% using the mobile user placement in FIG. 8 and a
crossover
ratio of 0.5 after 100 generations;
[0063] FIG. 29 is a graph showing anteruia placement.s in a four-by-five
system for the top 10% using the mobile user placement in FIG. 8 and a
crossover
ratio of 0.5 after 100 generations;
[0064] FIG. 30 is a graph showing antenna placements in a four-by-three
system for the top 10% using the mobile user placement in FIG. 8 using a
crossover
ratio of 0 after 100 generations;
[0065] FIG_ 31 is a graph showing antenna placements in a four-by-four
system for the top 10% using the mobile user placement in FIG. 8 using a
crossover
ratio of 0 after 100 generations;
[0066] FIG. 32 is a graph showing antenna placements in a four-by-five
system for the top 10% using the mobile user placement in FIG. 8 using a
crossover
ratio of 0 after 100 generations;
13
CA 02675225 2009-08-27
[00671 FIG. 33 is a schematic of ray-traci.ng to determine the intersection
point, Prp of a reflector plate and a ray sintplified to 2-D; and
[0068] FIG. 34 is a schematic of ray-tracing to determine the intersection
points, Ptintl and Ptint2, of a target spherical antenna and a ray simplified
to 2D_
[0069] FIG. 35 is a top view of an optixn.ized 3-antenna configuration.
[0070] F'IG. 36 is a front view of an optimized 3-antenna configuration.
[0077] FIG. 37 is a side view of an optimized 3-antenna configuration.
[0072] FIG. 38 is a top view of an optimizCd 3-antenna and 5-reflector (small)
configuration.
[0073] FIG. 39 is a front view of an optimized 3-antenna and 5-reflector
(small) configuration.
[0074] FIG. 40 is a side view of an optxxni7ed 3-antenna and 5-reflector
(small)
configuration.
[0075] FIG. 41 is a top view of an optimized 3-antenna and 5-reflector (large)
coxtifigu.ration.
[0076] F1G. 42 is a front view of an optimized 3-antenna and 5-reflector
(large)
configuration.
[0077] FIG. 43 is side view of an optimized 3-antenna and 5-reflector (large)
configuration.
[0078] FIG. 44 is a top view of an optimized 3-antenna and 5-reflector (sma11)
configuration with users.
14
CA 02675225 2009-08-27
[0079] FIG_ 45 is a front view of an optimized 3-antenna and 5-reflector
(small) configuration with users.
[0080] FIG. 46 is a side view of an optimized 3-antenna and 5-reflector
(small)
configuration with users.
[0081] FIG. 47 is a top view of an optinv.zed 3-antenna and 5-reflector
(Iarge)
configuration with users.
[0082] FIG. 48 is a front view of an optimized 3-antenna and 5-reflector
(large)
con#iguration with users.
[0083] FIG. 49 is a side view of an optimized 3-antenna and 5-reflector
(large)
configuration with users.
[0084] FIG. 50 is a top view of an optimized 3-antenna and 5-reflector (small)
configuration with users in a black box repz'esentation_
[0085] FIG. 51 is a front view of an optimized 3-antYernna and 5-reflector
(small) configuration with users in a black box representation.
[0086] FIG. 52 is a side view of an optimized 3-antenna and 5-reflector
(small)
configuration with users in a black box representation,
[00871 FIG. 53 is a, top view of an optimized 3-ao.tenna and 5-reflector
(Iarge)
configuration with users in a black box representation.
[0088] FIG. 54 is a front view of an optitnized 3-antenna and 5-reflector
(large)
configuration with users in a black box representation.
[0089j FIG. 55 is a side view of an optimized 3-antenna and 5-reflector
(Iarge)
configuration with users in a black box representation.
DETAILED DESCRIPTION OF THE INVENTION
CA 02675225 2009-08-27
[0090] In this application, the following definitions are used:
[00911 "Optimized" or "optimization" - When antenna arrays and antenxia
array systems and elements thereof according to the present invention are
referred
to herein as having been optimized or having had an optixnization applied to
it, it
will be understood by those ski]led in the art that optimized or optirnization
is not
lixnited to a maximum optimi.zation and can include improvements of varying
degrees over prior art apparatus, systems and methods.
SYSTEM LEVEL COMPONENTS
[0092] "Network transceiver unit" - A functional unit of the MIMO multi-
user network system, receiving radio signals transmitted from the users
(mobiles) in
the service area, and transrnitting radio signals to these users (mobiles). It
may
include an antenna array and a cluster of objects that can randomize the radio
channels from the users to the antenna array. These objects can be refractors,
reflectors, scatterers, and diffractors.
[0093] "Data Processing unit(s)" -- Electronic device(s) extract data sent by
the
users (mobiles) from the radio signals received by the network transceiver,
and
encode data from the netwoxiC side, so that the transceiver unit can send them
over
the radio channel to the users (mobiles).
[0094] "Users (mobiles)" - Terminal devices belong to the subscribers of the
network that transrnit and receive radio sigi-wls to and from the network
transceivez
unit.
COMPONENTS OF THE NETWORK TRANSCEIVER UNIT
[0095] "Antenna" - A transducer receives and transmits electromagnetic
waves.
16
CA 02675225 2009-08-27
[0096'] "Antenna array" - A group of antennas positioned to form a spatial
patkern.
[0097] "Reflector" - A geometric object of a chosen rnaterial that reflects
the
incident signal. The reflector can be of disks, sphere, cylinder, parabolic,
and any
other geometric shapes.
[0098] "Refractor" - A geometric object of a chosen material that allows a
portion of the incident signal to be transmitted through the object at a new
direction
that is dependent on the geometry of the object, and the electromagnetic
properties
(permittivity and permeability) of the medium of the incident signal (usually
free
space) and the object.
[0099] "Scatterer" - A geoinetric object of a chosen size and surface
roughness
that redirects (diffuses) the incident signal in all directions_
[00x00] "Diffractor"- A geometric object of a chosen size and shape that
allows
a redirection of the incident signal at the edges to propagate towards a
region that is
norrnally blocked (shadowing region).
Coxnmuzucati.on System Design
MIMO Setup
[00T01j The performance of a certain antenna placement can be evaluated and
the genetic algorithm then has a fitness function to base its evolutionary
process on.
It is possible that the algorithm can converge to a local maxima/minima point
rather
than reach a global solution. The presence of these vestigial stsuctures can
prove to
be problematic when attempting to gain zzi#ormation from the results.
(00102] por the genetic algorithm optimization simulation, three MIMO
systems were chosen as models. This included four-by-three, four-by-four, and
four-
by-five arrangements. This model configuration was chosen since it would be
17
CA 02675225 2009-08-27
complex enough to exhibit characteristics of the non-linearities of the
problem
without being overly computationally complex. In terms of the channel impulse
functions, the channel impulse response (CIR); between the users and the base
stat.ions, the charulel impulse function matrix for the four-by-four system is
given by
hi-i (t) Ara(t) h,.13.(t) hl,,(t)
h(t) h2'1(t) hz3(,t) 17,23(t) h24(t)
_ , .
h31(t) h3?(t) h33(-t) h3d(t)
hd](f) ~ddtilt~ ta43(t) h4dltJ
(Eq- 5)
which has the corresponding Fourier transfotm
Hli(f) H-L'f~) H~(f) 11ia(.~)
Hm (f) Hz2 (t) H23(fJ H
NY)
KY) _
Ral(f) H3Z(J) -gn(f) H3a(f)
~ (Eq.6)
[00103] Variations of these can be used to model the four-by-three azid four-
by-
five systems-
Signal Generation
[00104] For the purpose of the genetic algorithm optimization, a bandwidth
spreading factor of K=$ was chosen, where the highest low-pass frequency is
K12T,
where T is the symbol period. This was chosen as a compromise between giving
the
coded signals enough of a spread to be recovered after noise was added to the
channel, and the computational complexity associated with increasing the
18
CA 02675225 2009-08-27
bandwidth of the transmitted signals. The spread spectrum spreading codes were
generated randornly with complex values and urni,t energy.
Radio Channel Modelling
j00x051 In the described GA optimization, the radio channel was modelled as
being a pure LOS radio channel. In a pure LOS radio channel, the aspects of
multipath xziterference and ground effects are ignored. The attenuation of the
signal
is inversely proportional to the square of the distance. This gives rise to a
path loss
exponent, n, of 2, and determines the received power by
~-
P,(d)=PP(cto) d
( )
(Eq 7)
where P, is the received power (W), do is a reference distance close to the
base
station (rn), and d is the distance from the base station (m). Also, for the
purpose of
this simulation, the antennas were modelled as omni-directionai, meaning the
isotropic gain was unity.
[00I06I The next point to consider is the propagation of the signals is
considered to be in free space and is therefore taken as c, the speed of
light. This
gives rise to a time delay for the propagation from the mobile to the
antennas. Using
the two points of path loss and time delay, the entries of Eq. 6 can now be
expressed
as a furietion of the distance from mobile to the antennas to give
H'd (f ~ - i9~a+~'TfTl3
(Eq. 8)
where Mii is the resulting attenuation of the signal from the ih mobile to the
antenna, t=l is the time delay associated with the signal fron, the ith mobile
to the jul
antenna, and fr is the symbol rate,
19
CA 02675225 2009-08-27
.fa' = ~~7-
(Eq- 9)
[00107] The sources of interference that arise in this simulation are MAI and
AWGN. Complex random zLoise was generated and added to the received signals at
each antenna. The noise variance, d was chosen to give a signal-to-noise
ratio (SNR)
of 40 dB at each antenna.
Signal Extraction
[00108] The LMS adaptive filter was applied to each received signal at each
antenna to extract the original data streazn. The LMS adaptation constant, p,
was set
to 2-5. For the purpose of this simulation, the entire l,ength of the data
stream was
considered known, and the adaptive filter was allowed to train on the whole
data
sequence. The LMS adaptive filter is thus able to determine the filter
coefficients,
W,,, neCessary for the multiuser detection (see FIG. 3) for each user to
antenna
cornmLUiication channel.
[00109] The length of t]ae data sequence was set to be a total of 1024 bits.
The
adaptive filter was assumed to have converged to the global minimum and the
mean squared error (MSE) was then calculated over the second half of the data
stream (512 bits). The value for the MSE over the second half of the data
stream was
taken as the minimuzn mean squared error (MMSE) value for that user. The
ability
to detect all users in the system is imperative, thus it is necessary for all
users to
have converged to a near optima11V1MSE value (see FIG. 4). The total
performance of
al.l the users is evaluated by averaging the MIVISE results. FIG. 4 shows that
the filter
ha5 nearly converged before 400 bits have been processed. From this
observation,
the choice of 512 bits is a sound choice and gives reasonable results for the
MMSE
calculation.
CA 02675225 2009-08-27
GA Optimization Design
Antenna DNA
[001101 In one embodiment of this invention, the simulation comprises
choosing the placement of the four antennas as the individual's DNA structure.
The
antenna placernent is evaluated only in two dimensions, so antenna placement
contains an x and y co-oxdxrtate describing its placement within the cell.
Since each
individual is made up of four antenna placements, the individuals of the
population
can be described by
X1
'02 34a
Dl~I ~iq =
~a Ya
X3 Yd
(Eq. 70)
[00111] This could be modified to account for N antennas by simply extending
Eq. 10 by adding x and y co-ordinates for each additional antenna up to N.
Each
element is referred to as an allele of the individual, which in traditional
genetics is a
sequence of DNA code that is responsible for a particular characteristic in an
individual. A constraint was placed on the DNA of the antenrl~'~s to limit
tile total
distance the antennas were placed from the origin. Specifically, in this
simulation, an
initial constraint was placed to limit the x and y placement within the range
of (-Ar,
Xr). This was imposed to simulate some cost function associated with a given
antenna placement structure. The total distance also gives a method to
quantify an
unstable mutation.
Fitness
[00112] For each generation of individuals that was created, it was necessary
to
evaluate the performance of the individuals according to a fitness function,
how
21
CA 02675225 2009-08-27
well the individuals were capable of achieving the specified goal, In a
wireless
commurtications system, the goal is ultimately to deliver the information
reliably
and efficiently. The two most common metrics that measure a systems
performance
in a wireless cornmunications channel are bit error rate (BER) and the MMSE
described in the Sigrnal Extraction section [27]. For each individual of the
antenna
placement population, four NIlVISE values were determined, one for each user
in the
population. To obtain a single score for each individual in the population,
the fitness
fu.nction, o, was given by
t
~-
w ~ h^I-hriS~~
(Eq.11)
where N is the number of users.
[007.13] Upon calculating o, the population can then be ranked according to
the
resulting scores_ Since a small MMSE is desired, the best scoring individuals
will
have a Iarge value for o.
Generating Populations
[00114] In order to evolve, the next generation of individuals needs to
inherit
the properties of the top perforTmino individuals from the pxevious generation
and
attempt to improve upon them. The portion of top performers retained for the
succeeding generation was set at 10%. These top performers were chosen as the
parents to generate the next population through the techniques of crossover
and
mutation.
Crossover
[00115] To generate a new individual based on the genetic technique of
crossover, two parents are xandomly chosen from the top performing population.
A
22
CA 02675225 2009-08-27
binary crossover vector is randonily generated having equal length of the DNA
code. The new individual is created by using a combination of the alleles
found on
in the DNA codes of the two parents. In this case, on the loci (location of
allele, or
DNA code index) wbere the crossover vector is a 0, the offspring will inherit
the
attribute found at the same site as parent 1 (see FIG. 5).
Mutation
[00116] The second method by which new individuals are created is through
the process of mutation. This method involves adding random perturbations to
the
genetic code to create new individuals that result from a rnorphing of the
parent. In
nature, this process is invoked to increase the available genetic content in a
population. The mathematical equivalent to this is to give the population the
ability
to evolve towards a global optiniization rather than remain at some local
mininna.
Often, it is quite possible as well for individuals to be created with similar
performance, but vastly different characteristics_
[00117] To generate a new individual via mutation, first, an individual is
randomly selected from the top performer population to be mu-tated. A mutation
vector of the same length as the DNA code is then generated by randomly
selecting
a perturbation from a zexo-mean normal distribution. This perturbation vector
is
then added to the selected parent to create a new individual that is a
resultant of the
morphed values (see FIG. 6),
[Q0x18] The standard deviation of the mutation vector, cr,,,, was given a
starting
value, aw, and chosen as 0.7.X=r, where Ar is the symbol wavelength. Another
characteristic of population genetics is that often when a population is
young, it is
necessary for the mutations to be large and abundant. As the populatzon
evolves, it
becomes more specialized and large mutations often appear to provide no
further
advantages. Also, the value of a,,, will deternvne th.e variance associated
with a
population. In order to meet some predefined convergence criteria, it is then
23
CA 02675225 2009-08-27
necessary for the am to decrease as the population becomes more specialized.
This
gives rise to a degradation factor, cc, to determine the value of airt for the
next
population. The calculation of the Q,R is therefore given by
a'm"H - er"aa o'ry', (Eq. 12)
where y, is the generation index- A value for a was chosen as 0.97.
Methods
[00Xx9] Tkte joint optintization of the base station antenna is carried out
through a coxnputer simulation in MATLABT) run on an eight-core Mac Pro
computing platform that makes use of the MATLABT distributed computing engine
(MDCE) toolbox to rnaxirnize computational tluoughput for the eight processing
cores. Since much of the simulation involves coarse-grained parallel
computations,
the processor core utilization is very efficient.
Results
[00120] The simulation was coded as a MATLASCR7 script file. Several different
user orientations were considered and the output of the optimizations was
retained
for each generation. For each user orientation, the population size was set to
100
individuals. The number of generations that were simulated was also 100. The
selection criterion was retained as the top 10% performing individuals. A
crossover
ratio of 0.5 was chosen. This meant that 50% of the new individuals that were
created were done so by using the crossover techniSue, while the reinaining
50%
were generated through mutation. The saTne parameters were used to evaluate
the
four-by-three, four-by-four, and foux-by five MIMO configurations. FIG. 7
shows a
generalized flow chart for the GA optimization process.
10012:[] A second run of the sunulation was repeated for the same user
configurations, but this time choosing a crossover ratio of 0. This meant that
the
24
CA 02675225 2009-08-27
generation of new individuals was done through pure mutation. Similarly, this
was
also done for the four-by-three, four-by-four, and four-by-five
configurations.
[00122] FIG. 8 shows an example of one of the mobile user placements for
which the simulation was run. This particular configuration shows the mobile
users
equally separated around the origin of the cell, each at a radial distance of
fifty Xr.
1001231 To quantify the effectiveness of the GA optirnization, the total
variance
of the antenna placernents was evaluated using
n
7, lrar[Ak(ry)),
h-S
(Eq.13)
where VarY is the total variance of the generation, y is the generataoxl
imdex, n is the
number of unique components in the DNA, and ak(Y) is a vector containing all
the of
the k-01 components the DNA in the generation y(see FIG. 9 through FIG. 14)
Once
this value reached steady-state, it is assumed that the optimization has
converged.
The number of generations was fixed at 100 for this simulation. This allowed
for fine
tuning of tEle final solution in many of the cases, since several of the cases
showed a
vast improvement in as little as 10 generations.
[00124] Using a crossover ratio of 0.5, the results from the four-by-three
system
using the user arrangeinent in FIG. 8, the antenna plaCement moved towards an
isosceles right-angled triangle (FIG. 15). The l.enp=ths of the equaI sides of
the triangle
are on the order of the symbol wavelen,gd-k.
[001251 FIG. 16 through FIG. 27 show how the GA progresses during the
optimization through successive generations. For the purpose of illustration,
these
figures show the placement of all the antennas rather d-wn the top 10%
performing
individuals. Many regions for antenna placermeztt are eliminated within the
first five
to ten generations. This shows the rapid beginning of the optimization within
the
CA 02675225 2009-08-27
first few generations, but also illustrates the need for further successive
generations
for fine tuning.
[00126] For the initial simulation run of the four-by-four system, using a
crossover ratio of 0.5, the GA tended towards an arrangement in which at least
two
antennas are separated by AT as seen by the mobile users and asymmetry (FTG_
28).
100I271 The results from the simulation for the four-by-five system using a
crossover ratio of 0.5 tended towards two distiuut configurations (FIG. 29)
rather
than the single configurations seen in the four-by-three and four-by-four
simulations. Whil.e distinct, the two configurations are closely related. The
four-by-
five configurations show sirtular characteristics to those found in the four-
by-four
configurations. In this case, the minim-um antenna separation is close to a
symbol
wavelength, while the maximum antenna separation is close to two symbol
wavelengths.
[00128] The simulations were then repeated for each of the three systems using
pure mutation as the rnethod of generating new individuals in the populatioxi.
FIG.
30 shows that the GA optimization has converged to essentially a single unique
antenna arrangement. The triangular configuration has spread further than the
minimum of a symbol wavelength, but the maximum antenna separation is still
smaller than two symbol wavelengths.
1041291 For the next siznulation run of the four-by-four system, using a
crossover ratio of 0, e.g. pure mutation, the genetic algoritlzm tended
towards a
different arrangeurLent (FIG. 31). This arrangement also shows asymmetric
qualities
as well as having at least two antennas separated by Ar as seen by the mobile
users.
In fact, this arrangement is a 180-degree rotation of the same anterma
placemeitt
achieved tluough crossover, which can be considered the same result given the
symmetry in the original mobile user placement. This shows that either through
26
CA 02675225 2009-08-27
pure mutation, or including some degree of crossover, the same results can be
achieved.
[001301 Finally, the results of the simulation for the four-by-five system
using
pure mutation also converge to a single unique solution (FIG. 32). This
configuration
is dose to the two solutions that were found using crossover, however, it is
mostly
similar to the fouz'-by-four configurations, but with a greater separation of
the
antennas.
[00131] In this arrangement, there exists antenna separations that are closer
to
two symbol wavelengths in magnitude. The minimum antenna sepaxation seen here
is one instance of two antennas being closer than a symbol wavelength.
3-D Expansion
Motivation
[00132] The natural progression of the 2-D simulation work is to expand the
model to 3-D space. jNhile LOS signals alone can be simplified in the 2-D
plane,
optinmal gains will be made with the addition of reflector elements to
increase the
multipath present in what was previously a close range LOS situation.
Setup
[00133] An M.-by-N MIMO system is considered in 3-D space, wiflt the M users
placed around the receiver structure in a known configuration. 'The placement
and
orientation of reflector and antenna elements is determined by a GA to jointly
optimize the received signals based upon the electrornagnetic properties of
the
induced couznunication channel and the coding scheme used in the transrnitted
signal.
27
CA 02675225 2009-08-27
Reflectors
[00134] The reflector elements are modelled as perfect reflectors havxng a
reflection coefficient of unity. More realistic reflection coefficients could
be
incorporated in the calculations, but to simplify the simulation, a reflection
coefficient of unity is used and assumed to have little effect on the overall
outCome.
This will zttaximize the gains possible from a multipath environrnent as well
as
exploit the SWAP gain.
Initial Placement
[00135] The placement of the reflector elements is randomly determined by the
GA. They are constrained to a maximum distance from the centre point of the
base
station to limit the overaII size of the receiver structure. Each reflector
element will
have a 3-D point in space corresponding to the centre point of the reflector
itself.
Each initial point is determined Erom a uniform distribution from -1 to 1 and
then
normalized to the maximum distance from the centre point of the base station
that is
chosen to constrain the GA.
[00136] The orientation of each reflector element is also z'andomly
determ.ined
by the GA. Again, choosing from a uniform distribution from -1 to 1, three
lengths
are chosen for the directions along the x, y, and z axes to create a
directional vector.
These lengths are then normalized to create a unit directional vector that
describes
the plane on which the reflector will sit, centred around the origin of the
reflector.
Size and Shape
[00137] In order to accurately simulate pure planar reflection from the
reflectors, the size of the reflector elements must meet a minimum. By making
the
reflector elements large in comparison relative to the size of the transmitted
signal's
wavelengths, the effect of diffraction can be minimized. This avoids the more
time
consuming and intensive process of accurately modelling diffra.ction. The
shape of
28
CA 02675225 2009-08-27
the reflector elements are chosen as circular discs with a fixed radius, The
choice of
circular discs makes the most efficient use of reflector material, since this
shape
provides 'the most useable surface area with the least arnount of area lost to
spreading at the edges.
[00738] To simplify the calculations and siunulation, all reflectors are
uniform
in size and shape. From a manufacturing standpoint, identical discs would be
more
easily machined and produced. It wrould be possible to allow the radius of the
reflector surfaces to also be a changeable parameter in the GA. However,
having the
number of reflector elernents as a changeable parameter, the effect of larger
reflector
sizes can be achieved by combining multiple smaller reflectors to c,reate
larger, more
complex surfaces.
Growth
[00139] To facilitate the growth of the reflector elements, some consideration
must be made for the addition (or subtraction) of new reflector elements. An
individual in the population would begin with a certain number of reflector
elements xandorrdy placed. Through the generation of new individuals, a new
paraineter would be chosen for the total number of reflector elements present
in a
single individual.
[00140] In order to limit complexity, a rnaximum would be placed on the total
number of reflector elemerits that a single individual would have.
Additionally,
pruning would occur that would el'xminate reflector elements that did not
contribute
to the performance gain. This pruning would happen during the ray-tracing
stage
such that if it is deterrnined that a reflector el.ement receives no signal
and does not
produce a reflecting signal that is seen by the antennas, it would be
eliminated from
the population
29
CA 02675225 2009-08-27
Ray-Tracing
1001411 For each individual created composed of a random arrangement of
reflectors and antennas, the received signals at the antenna due to the
induced
multipath from the reflectors must be deterxxnuled. A basic ray-tracing
algorithm is
implemented. Computationally, this process could be sirnplified by the use of
a
vector graphics processor. klowever, for simplicity, this calculation is
processed
generically using a general purpose central processing unit.
[00142] The CIR is determined in a sizztilar way as in the 2-D case,
consisting of
the vector sum of received signals at each antenna due to propagation delay
and free
space path loss. However, the addition of reflectors has the added element of
ntaltipath arrivals which must be determined. The entries of the cornplex
passband
channel impulse function matrix in Eq. 5 become
w
aAet2"i,rk a(t - 7-k)1 *tu(t),
(Eq. 14)
where k is the rnultipath component index, ak is the amplitude of the kfi'
rnultipath
component, f~ is the carrier frequency, Tk is the krl, associated propagation
delay, * is
the convolution operator, and w(t) is an ideal low pass filter.
[p0143] The total sum of multipath arrivals that are seen at the antennas is
determined by ray-tracing_ For each user present in an individual arrar-
gement,
directional rays are created from the useXs' position. Using straight lines,
some
granu.Iarity exists, but by setting a small enough step for degree increments,
the total
coverage of the t'ay-tracing is considered sufficient for this siun.ulati.on.
[00144] From each user, based on the degree increment step specified, vectors
are created over the range of a=(-z, 7r), y=(-7r, n), and (-n/ 2, 7c/2). Each
vector is
CA 02675225 2009-08-27
then used to determine the intersection point with the plane of each reflector
or the
region around a tazget antenna.
[001451 To determine whether or not the ray has intersected with a reflector
plate, the intersection point with the plane of the reflector is found. To do
so, the
planar equation in the forxxt of
ax+bx+Gz+d=O (Eq. 15)
is determined, where a, b, c are the x, y, z components of the plane's normal
vector,
nF ~ < a, b, -c ? .
(Eq. 16)
[00146] Eq. 15 can be solved for d using the values of the origin of the
reflector
for x, y, and z. The point of intersection lies along the ray (line) and can
be found by
solving for the scalar factor, s, in
F,g= Prar0 -I-s4,
(Eq.17)
where P,p is the point of intersection of the ray and the reflector plate,
Prorg is the
point of origin of the ray, s is the scaling factor, and dr is the directional
vector of the
ray. The scaling factor, s, can is found by combining the line equation and
the planar
equation yielding
--t3 --- 1 ras g = np
dr np
(Eq.1s)
Substitutin.g s back into Eq. 17, Prp can be solved for.
[00147] Pp is then compared to the origin of the reflector. Based on the shape
and size of the reflector, it is then detennined whether or not the point of
31
CA 02675225 2009-08-27
intersection from the plane and vector is within the region of the reflector.
In the
simple case where the reflector is a circular disc with a fixed radius, an
intersection
of the ray and the reflector is made if the distance from the point of
intersection to
the origin of the reflector is smaller than the radius. That is
r7, < (.P,.p - PP-9) - (P,.g - i y_a),
(Eq.19)
where rp is the radius of the reflector plate, and Ppo,g is the origin of the
reflector
plate, provided that the point of intersection is in the outward positive
direction of
the ray. This is because the general solution will provide a point of
intersection
along the infinite line of the ray, and the ray begins at a finite point
(reflector is
behind the ray). Given the assumption that the reflector surface is large
compared to
the incident wave, the effect of fringing artd spreading is ignored and any
interseCtion will be considered a pure reflection (see FIG. 33).
[00148I To determine whether or not the ray has intersected the region around
the target antennas, the line-sphere intersection method is used. Combining
the
line equation,
Pftri.t = Pra,a
(Eq. 20)
and the sphere equation,
(x - x.o)2' + (y - yo)j 4' (z
(Eq. 21)
yields a quadratic equation of the form
Az? -1- B76 + a = ED,
(Eq. 22)
32
CA 02675225 2009-08-27
where
A dr ' dr,
, .3' ~ 2t~r = (P,.,,.~ -- ~t~n,,g~,
(Eq. 23 & Eq_ 24)
and
c = (P,,-M - A'wg) (P,,o,,. - Pt.,.$) - Fl.
{Eq_ 25)
100149] lpt,,,t is the point of intersection of the ray and the target sphere,
u is a
scalar, xo, yo, and zo are the respective points of origin of the sphere,
Pto,,, and rs is
the radius of the target sphere.
[00150] Solving the quadratic equation yields two solutions, ui and U2 since
the
line will intersect the sphere at two points, unless it is tangent to the
sphere or makes
no intersection at all. Substituting these values into Eq. 20 gives the two
points of
intersection. The distances, d1 and dZ from the origin of the ray to the
points of
intersection are
dl. -VPt:t.cl - -Põo.gI
(Eq. 26)
da = ,,1 p~I2 = P.a
(Eq. 27)
100151] These solutions are considered valid if, like the reflector
intersection,
the signs of the vector from the ray origin to the poiitt of intersection,
that is Prins -
Pn, are the same as the directioi~ial vector, dr (see FIG_ 34).
33
CA 02675225 2009-08-27
[001521 Yf an intersection is made with a target antenna, the ray is
terminated if
it is determined to be the first intersection that the ray has made with
either a target
or other reflector. This means that the ray is terminated in this case if it
has directly
made contact with a target antenna before meeting a reflector.
[00153] If a ray is determined to not make contact with either a reflector or
an
antenna, then it is considered to have not contributed to the received signal
at the
antenna, and its effects are ignored. Standard GA techniques to sample the
surviving individuals were used to maintain genetic diversity by including
survivors with a wide range of fitness fu.nctions.
j001.b4] If a ray is found to have rrade an intersection with multiple
reflectors,
the distance between the reflector and the origin of the incident ray is
determined,
and the reflector that is the nearer is kept. Any intersection made with
reflectors that
are further away are ignored, as this would assume that the ray has been
transmitted through the reflector, when in actual fact it would be in a
shadowing
region in which the ray would not be transmitted.
[0{11551 Once an intersection is made with a reflector, the point of
ixitersection
becomes the new point of origin for the reflected ray. The reflected ray is
then
created based upon the incident ray to the reflector. This reflected ray now
becomes
the new incident ray and is recursively tested for the same intersection.9 of
reflectors
and antennas.
[00156] For all rays that reach the target antenna, the total path travelled
becomes the s mmation of the vectors from the starting position of the user to
each
intersectxon points on the reflectors and end antenna. Using tltis total path,
a
multipath arrival consisting of a propagation delay and signal level based on
free
space path loss can be determined.
34
CA 02675225 2009-08-27
Channel Impulse Response (CIR)
[00157] Once the ray-tracing has been completed, the CIR can be constructedd-
A single CIR for one user to one antenna will consist of the LOS path (if
present) and
the total s mmation of the multipath arrivals that have been induced by the
reflectors. For the purpose of simulation, the CIR is most easily computed
when
described in discrete time. To Iimit the complexity of the calculations, the
maximum
bound is placed the length of the CTR both in terms of number of samples, as
welI as
in terms of time-
[0015$] The numbeer of samples as well as the total delay allowable for the
CIR
must be chosen in tandem to give azt accurate representation of the effects of
the
multipath without sacrificing computational time- The number of samples must
be
large enough such that the identification of discrete paths is on the same
order as
path length differences based on the movement of the reflectors. The length in
time
of the CIR must be long enough to capture the majority of the energy from the
multipath arrivals. This length can be chosen as a multiple of the symbol
period to
best illustrate the desired effects from symbol wavelength spacing.
GA Optimization design
[00159] The GA optirrtization design is built upon the 2-D design outlined in
the GA OQti.mization section. The design is expanded to account for
propagation in
3-D space, as well as the addition of multipath inducing reflectors.
Flow
[00160] Similar to the 2-D design, the basic flow of the GA optimization is as
follows. The population is first seeded with individuals that are
characterized by
their individual DNA. The fitness function is calculated for each of these
individuals
to determine how well the individual is suited to meeting the specified task.
In this
case, the optirnization is towards multiuser performance, using MMSE as the
metric.
CA 02675225 2009-08-27
Once the individuals have been scored, they are ranked and ordered. The top
perforrnimg individuals are chosen to survive to the next generation, as well
as serve
as the parents (donors of characteristic DNA) of the next generation.
[00161] Next, the new population is generated first with the surviving elite
individuals from the previous generatior- The remaining individuals are
generated
using the crossover and mutation methods. As each new individual is created,
those
who have components that are outside the bounds (antenna or reflector too far
from
the origin) have those offending components removed and replaced with a newly
randozrdy generated component. This new population then evaluates the fitness
scores to once again deterrnine the top performers. This process continues
until the
end criteria is met. The end criteria can be set as either a number of
generations to
process, or with a specific performance goal. With the latter case however, it
is
possible that if the specific performance goal can not be met, the simulation
wi111oop
endlessly.
Individual DNA
[OD162] The characteristics of a single individual configuration is described
by
the DNA. A single individual in this popxtlation is described by the DNA for
the
arrtennas and the reflectors. The DNA parameters for the anfiennas is similar
to that
of the 2-D situation shown in Eq. 10, except that in this case a z-component
is added
to the position of the antennas to fully describe it in 3-D space. T'he number
of
antennas is fixed iA this case at N= 4, but similarly could be modified for
any N.
Therefore, the antenna portion of tlle DNA becomes
36
CA 02675225 2009-08-27
Xl. V1 Z1
x~
212 YZ
anten~xas;
-Tg Y3 Z3
xd Yd Zd
(Eq. 28)
[00163] A single individual in the population also described by the reflectors
surrounding the antennas. The DNA parameters that describe the reflectors are
an x-
y-z position in 3-D space, as well as a unit directional vector x'-y'-z'
describing the
orientation of the reflector plate. The shape of the reflector plate is fixed
in this case
to be a circular disc of a fixed radius, which is constant for all of the
reflectors-
HoGVever, the total number of reflectors, N, present in one individual
configuration
is variable, meaning that there is a variation in the size of the reflector
portion of the
DNA from thus, the reflector portion of the DNA can be represented by
xr yi z1 xi &i =i
x, Y2! 22 xy
rc~8ect,~r=s~ =
F F
X?Gr FlY: ~?kt* ~Nr ~fiM ~Nr
[Q0164] In addition to the antenna and reflector DNA portions described in Eq.
28 and Eq. 29, d.ze parameter describing the total number of reflectors, 1Vr,
would also
be contained in the DNA of the individual. Although this can easily be derived
independently rom the information in the reflector DNA, it is included as it
is a
parameter that is modified when creating new individuals using individual i as
a
parent.
37
CA 02675225 2009-08-27
Generating Populations
[00165] For the 3-D simulation, the population is initialized and generated in
a
siznilar fashion to the 2-D case as well. The position co-ordinates of the
antennas are
randomly generated and chosen from a uniform distribution bounded by the
distance limits set from the origin of the individual structure.
j0u166] For the reflectors, the number of reflectors in a given individual are
randomly generated from a uriiform distribution with a limit on the maximum
number of reflectors allowed. The position co-ordinates for each reflector are
then
chQsert fxozn a uniform distribution, as well as the lengths for the
directional vector
of the reflector surface. The direCtional vector is then normalized to unit
length.
(fl01671 T11e process of creating a single individuaI in a population is then
repeated until the population limit is z'eached,
Crossover
[00168] Once the initial population has been created and evaluated, the
individuals in the successive generatior- must be created. Mirroring the 2-D
case, a
new individual is created via crossover by selecting two top performing
individuals
from the previous generation. The new individual is generated by either
inheriting
inforrnation from one parent or the other from each allele, or loci of
information.
Since the number of reflectors is also a variable, in the case of the higlter
number of
reflectors being chosen, the new individual will automatically inherit the
reflectors
from the parent to meet the desired number of reflectors.
Mutation
[00169] The second mechanism by which new individuals are created is
through mutation. This rnirrors the 2-1) case as well, by taking a single
individual
and zxtutating it by perturbing each parameter by a set standard deviation.
Since the
number of reflectors is also being perturbed in this case, the elimination of
38
CA 02675225 2009-08-27
extraneous reflectors is determined randomly using a uniform distribution. ln
the
case in which the number of reflectors needs to be increased, additional
reflectors
are created and added in the same way as when the population is initialized.
Distributed Processing
I00170] Given the high amount of coarse-grained parallelism in the
computational xequzrements of implementing a GA to solve a rnany
configurations
of MIMO communication problems, great advantages can be made by incorporating
distributed processing to handle these tasks. The calculations required for
individuals of a population are not dependent on each other, therefore these
lengthy
linear computations can be conducted in parallel across multiple processors or
nodes.
MDCE
[00171] One method of incorporating distributed processing techniques that
was explored was through the use of the MDCE toolbox available for MATLASS.
This toolbox includes an array of utilities to implement a distributed
processing
solution to a set of computational tasks exhibiting parallelism. The MDCE
implernentati.on consists of the toolbox set to develop and program the work
set, and
the engine to run and man.age the tasks. This toolbox allows not just for
parallel
processing across multiple workstations, but exploiting multiple processing
units ozi
a single workstation, since MATLAS itself is c-urrently single-threaded.
Agents
[00172] An agent in the MDCE is essentially a full instance of the MATLAB(V
program.capable of interpreting the progrants that it is assigned and carrying
out
the calculations. Each agent must be initialized and named such that it can be
properly addressed. A single agent is the processing entity that is capable
handling a
task. To maximize the utilization of multiple core processors, the ideal
nuinber of
39
CA 02675225 2009-08-27
agezits is equal to the number of available processing cores. In a typical
distributed
computing hierarchy consisting of nodes in a cluster, each node (addressable
physical entity) would be assigned a number of agents equal to the number of
processing cores available at that node.
Job Manager
[00173] The job manager is the program responsible for assigning tasks to the
agents and moiiitQring the exchange of information. A single job manager is
required for a single distributed problem, as it oversees the operation of a11
the
agents in a cluster. To rnaximize the processor core utilization, the best
performance
will be achieved when a processing core is resez-ved for the job manager. This
eliminates the downtime and queueing delays that would occur if the job
manager
was forced to share a processing core with an agent.
Jobs
[00174] A job in the MDCE is a task that can be assigned to an agent by the
job
manager. This, in its basic form, is the coarse-grained independent problem
that
needs to be solved. The job is created by calling the desired method with the
appropriate input parameters. It is then assigned an identifier and passed
along to
the job manager.
[00175] At this point, the job manager will take the task and assign it to the
first available agent. If an agent is unavailable, the task will be queued and
held onto
by the job manager. Once the job has been assigned to an agent by the job
manager,
the job manager will wait on the completion of the operation by the agent.
Tlte agent
wilI report back to the job manager with the results, which are then handled
by the
job manager.
[00176] In the i.rnplennentation of the 3-D GA simu7ation, the calculation of
the
fitness function for a single individual exhibits a hi.gh amount of coarse-
grained
CA 02675225 2009-08-27
parallelism. This means that the calculation of an individuals result has no
interdependence on the outcome of another individual wl--en evaluated for the
same
generation. At the sub-individual level, there is also a choice within the
evaluation
of a single individual, ray-tracing, that may benefit from distributed
process, but the
overhead of the distributed setup should be evaluated as it may outweigh the
gains
at this level.
Ray-Tracing
[001771 One of the processes that benefits from distributed processing on the
sub-individual level is the ray-tracing portion. Each ray that is generated is
exhaustively tracked through either multiple reflections until an intersection
with a
target is met, or a miss is recorded. This part of the calculation can be
doxie in
parallel by making each ray a single job.
[001781 Since the calculation of each ray is independent of the other rays
from
the same source, the evaluation can be carried out in parallel. However, in
the
simplest case in which no intersections are made, the overhead for parallel
job
management may be large compared to the evaluation of the ray's intersection
with
reflectors and targets. At low levels of complexity, i.e. a small nuxnber of
reflectors
and antennas, there may be no benefit seen. At higher levels of complexity,
i.e.
where the number of reflectors and antennas in the configuration are large,
the
overhead from the parallel job management becomes proportionately less.
1001791 The two xxZain constraints to consider when deciding on the
computational complexity that is tolerable is by implerneztting a rnaximum
number
of reflections, NR, to calculate as well as a ceiling on the total numbez of
elements
(reflectors and antennas), NE,,,x. Since each ray is compared to each element,
this
represents a total number of NR,,,,x evaluations for every reflection up to
NE,nay.
41
CA 02675225 2009-08-27
MMSE
[00180] In the 3-D simulation expansion, the MIVISE is evaluated in the same
way as in the 2-D case, but with the exception that the input CIR is now more
complex, having the addition of re.Elected multipath components. In relation
to I=he
distributed processing, the calculation of the MMSEs for an individual
configuration
is at the top level of process separation. The next generation is dependent on
the
information ga9ned from the MMSE calculations, and therefore the siniulation
cannot advance at this point.
[00181] Therefore, as the jobs are completed (MMSE or fitness evaluated) for
each individual configuration in the present population, no further
calculation5 are
able to proceed at this point.
[00182] Since the MMSE calculation is identical to the 2-D case once the CIR
has been determined, there should be zio increase in the computational
requirements
for this section, provided the length of the CIR is the same. The approxirnate
computational iirne by a single processor, discounting parallel overhead, for
a
generation of 100 individuals in the 2-D case was on the order of a minute,
puttirig a
complete simulation of 100 generations close to two hours. By implementing
parallel
processing to this portion of the GA, the potential benefit is a reduction by
a factor of
the number of parallel processing units, putting this computation closer to 15
min
for a simulation of 100 individuals. However, the increase in number of
components
in the DNA rnay require an increase by an order of rnagnitude i.zi the
popuXation size
to sufficiezttly provide the information pool with enough unique information
to
reach an optimal solution.
Rendez-Vous
[QMS3] A rendez-vous point occurs at the point in which any part of the
process is unable to continue without the aid of further information. As jobs
are
completed and the queue is emptied, there will exist some time in which there
is
42
CA 02675225 2009-08-27
process under-utilization as the jobs meet up at the rendez-vous point. This
collective point would be seen in this situation at the points where a
distributed task
is being completed. If parallel tasking is used for ray-traeing, the program
must wait
until all rays have been traced before the CIR can be fully constructed. In
the case of
the MMSE fitness evaluation, all individuals in a population must complete
their
evaluation before they can be ranked as a group.
[001$4] In general, at a rendez-vous point, the information from the parallel
tasks can be collected and used to proceed with the next portion of the
evaluation.
Due to the nature of some problems, they are required, but proper problem
separation must be used to limit the performance lost during the under-
utilization
stage.
[00185] The findings conducted by implementation in hardware of the
antenna/reflector configurations that are determined from the GA optirnizaHon
can
then be verified. Measurements would then be carried out to determine if the
simulation was able to accurately predict the multipath arrivals, and
therefore if the
calculated radio cl-La.rnels were reasonable to use in the simulation to
determine the
optimal antenna/reflector arrangement.
[00186] Designs created traditionally based solely on the predicted
contributing elements can also be evaluated in addition to designs created by
the
GA itself.
Example
[00187] One example of the MIMO systein has three antennas, seven users,
and a spread spectrum factor of 3.
[00158] First, the antennas of each individual are constrained within a sphere
of 2 symbol wavelength (WL), centered at the origin of the coordinate system.
Prior
to GA adaptation, 100 individuals are randomly generated, i.e. the locations
of the
43
CA 02675225 2009-08-27
antezulas randomly generated, subjected to the constraint. Fifty random 7-user
locations were also simulated. All the users are located on a circle with 40
WL
radius, and 25 WL below the origin (Z coordinates of the users are all -
25'VI(L).
[001$9] The SINRs obtained by LMS algorithm were used as the fitness
function for the GA, algorithm. Each generation of GA adaptation, 10 survivors
are
selected based on a stochastic universal sampling scheme, so as to ensuring
the
diversity of survived genes and to achieve fast convergence.
[00190] The new population was generated from the 10 survivors with a cross-
over probability of 25% and an exponentially decaying mutation coefficient.
The GA
algorithm ran 20 generations, and the best survivor of each generation were
tested
using a 50 7-user locations, which are different from those used in GA
adaptation
and called the testing sets. The resuftiz-lg SINR are plotted in the left
plot, with
minimum, mean and maximum SINR over the 50 7-user locations. The best survivor
of this GA adaptation after 20 generations is presented in FIGS. 35 to 37.
[00191] Next, the survivors of the first GA adaptation were used as the
starting
point for the subsequ.ent work. A new population was generated based on these
survivors, by adding 5 reflectors to each individual. The location, size and
orientation of each reflector are randomly generated, subject to certain
constraints.
[00192] Two scenarios are simul,ated. 'I'he first one constraints the -range
of the
reflector within a sphere of 4'W"L, and the radius of the xeflectoz' withi,n 2
WL; the
second one constraints the range of the reflector within a sphere of 2 WL, and
the
radius of the reflector within 7 WL. The GA adaptation processes were the same
as
the previous (no reflector) one. The best survivor at each generation was
testing by
the testing set, and the resulting SINR are presented in the middle plot
(first
scenario) and the right plot (second scenario), with the same convention as
the left
plot.
44
CA 02675225 2009-08-27
[00193] The best survivors of the two scenarios after 20 generations are
presented in FIGS. 38 to 40 (first scenario) and FIGS. 41 to 43 (second
scenario). Note
that the LMS learning are all based on 4096 training bits.
CA 02675225 2009-08-27
Table 1 Optimized 3-antenna configuration-coordinates of the anntenas
X Y Z
Antenna 1 1.68 -0.11 0.70
Antenna 2 -0.61 1.55 0.59
Antenna 3 -1.10 -1.15 0.40
Table 2 Optimized 3-antenna and 5-refleetar (smal1) confi,guration-coordinates
of
the antennas
x v z
Antenna 1 2.96 0.14 0.84
Antenna 2 -0.78 2.01 0.77
Antenna 3 -1.19 -0.99 0.47
Table 3 Optimized 3-antenna and 5-reflector (small) configrxration-parameters
of
the reflectors (Cx, Cp, and CZ are the coordinates of the center of the
reflector; N. Ny,
and Na are the normal or direction of the reflector; R is the radius of the
reflector).
Cx Cy Ct Nx Ny Nz R
Reflector 1 0.39 0.38 0.48 -0.42 -0.17 -0.99 0.89
Reflector 2 0.19 0.08 0.04 -0.44 0.68 -0.50 0.61
Reflector 3 0.23 -0.15 0.55 -0.70 -1.09 -0_30 0_21
Reflector 4 0.06 0.18 0.34 -0.35 -0.49 0.88 0.50
Reflector 5 0.16 0.08 0.65 0.19 0.64 -0.13 0.47
Table 4 Optimized 3-antenna and 5-reflector (large) configuration -coordinates
of
the aaretenztas
x y z
Antenna 1 1.80 -0.02 0.29
Antenna 2 -0.97 2.03 0.68
Antenna 3 -0.83 -1.85 0.09
46
CA 02675225 2009-08-27
References
1. B. Widrow, P. Mantey, L. Griffiths, and B. Goode, "Adaptive antenna
systems," Proc. IEEE, vol. 55, pp. 2143-2159, Dec. 1967.
2. J. H. Winters, "Optim.um combining in digital mobile radio with cocharinel
interference," IEE-E J. Sel. Areas Commun., vol. 2, pp. 528-539, July 1984.
3. S. Roy, Space-Time Processing Tethniques zvith Application to Broadband
Wireless
5ystems. PhD thesis, Department of Systems and Computer Engineering,
Carleton University, Aug. 2000.
4. C. S. Bontu, D. D. Falconer, and L. Strawczynski, "Diversity transinission
and
adaptive MI.SE for digital cellular radio," IEEE Trans. on Velzicular
Technology,
vol. 48, p p.1488-1502, Sep. 1999.
5. A. 5ayeeci and V. Raghavan, "Maximizing MIMO capacity in sparse
multipatli wi-th reconEigurable antenna arrays," IEEE J. Sei. Topics SignAt
Process_, vo1.1, pp.156-166, June 2007.
6. J. Yang and S. Roy, "On joint transmitter and receiver optimization for
multiple-input multiple-output (MIN1O) transnu.ssion systems," IEEE Trans.
Commun., vol. 42, pp, 3221-3231, Dec. 1994.
7. D. Gesbert, M. Shafi, S. Da-shan, P. Smith, and A. Naguib, "Prom theory to
practice: an overview of MIMO space-time coded wireless systems," IEEE J.
Set. Areas Commun., vol. 21, pp. 281-302, Apr. 2003.
8. G. Zhu, B. R. Petersen, and B. G. Colpitts, "Signalling wavelength in an
antenna ax-ray for space-time wireless over LOS channels," in Proceedings of
the
3rd A-nnual Cornmunications Networlcs Se.mices and Research Confer'ence (C'NSR
2005), vo1.1, (Halifax, NS, Canada), pp. 69-73, May 2005.
47
CA 02675225 2009-08-27
9. V. V. N. S. Polu, B. G. Cotpitts, and B. R. Petersen, "Symbol-wavelength
IvIMSE gain in a multi-antenna 'C.7WB system," in Proceedings of the 4th
Annuat
Communications Networks and Services R'esearch Conference (CN5R 2006), vol. 1,
(Moncton, NB, Canada), pp. 95-99, May 2006.
10. H. Yanikomeroglu and E. S. Sousa, "Antenna gain against interference in
CDMA macrodiversity systems," IEEE Trans. Commun., vol. 50, pp. 1356-1371,
Aug. 2002.
11. R. Kalbasz, D. D. Falconer, and A. H. Banihashemi, "Optimurn space-time
processors with symbol-rate sampling are bandlirnited," IEEE Trans. Signal
Process., vol. 54, May 2006.
12. M. A. Jensen and J. Wallace, "A review of antennas and propagation for
MIMO wireless communications," IEEE Trans. Antennas Propag., vol. 52, Nov_
2004.
13. P. Jung and P. Alexander, "A unified approach to multiuser detectors for
CDMA and their geometrical interpretations," EEE J. Sel. Areas Commun., vol.
14, pp. 1595-1601, Ckt.1996.
14. A. Goldsmith, S. A. Jafar, N. Jindal, and S. Vishwanath, "Capacity limits
of
MIMO channels," IEEE I. Sel. Areas Comrnun., vol. 21, June 2003.
15. L. Liu, W. Hong, H. Wartg, G. Xang, N. Zhang, H. Zhao, J. Chang, C. Yu, X.
Yu, H. Tang, H. Zhu, and L. Tian, "Characterization of line-of-sight MTIVMO
channel for fixed wireless cozzurrmunications," IEEE Antennas Wireless Propag.
Lett., vol. 6, pp. 36-39, 2007.
16. R. Ziegler and J. Cioffi, "A comparison of least squares and gradient
equalixation for multipath fading in wideband digital mobile radio," in Conf.
Rec. IEEE Globecom 89, vol. 1, pp. 102-105, Nov. 1989.
48
CA 02675225 2009-08-27
17. D. Fogel, "Evolutionary computing," IEEE Spectr., vol. 37, pp. 26-32, Feb.
2000_
18. D. Anastassiou, "Geazomic signal processing," I,EEE Signat Process. Mag.,
vol.
18, pp. 8-20, July 2001.
19. M. Jiang and L. Hanzo, "Multiuser MIMO-OFDM for next-generation wireless
systems;" ProG. IEEE, vol. 95, pp. 1430-1469, July 2007.
20. A. J. Viterbi, CLDMA Principles of Spread Spectrum Communication. Reading,
MA, USA: Addison-Wesley Publishing Co. Inc., 1995.
21. A. Soong and W. Krzymien, "Effect of anteruza diversity on perfornmance of
ieference symbol assisted interference cancellation in CDMA wireless
systems," in Co~tf, Rec. 1997 IEEE 6th International Conference on Universal
persottal Communications (ICUPC), vol.1, pp. 202-207, Oct. 1997.
22. S. Roy and D. D. Falconer, "Multi-user decision-feedback space-time
equalization and diversity reception," in Cor~f. Rec. IEEE Internationa2
Conference on Vehicular Technology (VTC '99), vol. 1, (Houston, TX, USA), pp.
494-498, May 16-19,1999.
23_ S. Roy and D. D. Falconer, "Optimum infinite-Iength MMSE multi-nser
decision-feedback space-time processing in broadband cellular radio,"
Wireless Personal Commxcnõ vol. 27, pp.1-32, Oct_ 2003_
24. T. S. Rappaport, Wireless Communicatwns. Upper Saddle River, New Jersey,
USA: Prentice Hall PTR, 2001.
25. G. Cherubini, E. Eleftheriou, and 5. O1qer, "Filtered multitone modulation
for
very high-speed digital subscriber lines," IEEE J. Sel. Areas Commun., vol.
20,
pp. 1016-1028, June 2002.
49
CA 02675225 2009-08-27
26. A. M. Legnain, D. D. Falconer, and A. U. H. Sheikh, "New adaptive
coxnbiuzed
space-tinze receiver for multiuser interference rejection in synehronous
CDMA systems," in Con.f. Rec, CmadiAn Canfererace on Electrical and Co rputer
Englneering (CCECE), vdl.1, (Waterloo, ON, Canada), pp. 421-424, May 24-28,
1998.
27. J. H. Winters, "Uppez bounds for the bit error rate of optimum combining
in
digital mobile radio," in Conf. Rec. IEEE Globeemn 84, vol. 1, pp. 173-178,
Nov.
1984,
