Note: Descriptions are shown in the official language in which they were submitted.
CA 02442950 2003-09-26
1
TITLE OF THE INVENTION
METHOD AND SYSTEM FOR INDOOR GEOLOCATION USING AN IMPULSE
RESPONSE FINGERPRINTING TECHNIQUE
FIELD OF THE INVENTION
The present invention relates to a method and system 'For indoor geolocation
using
an impulse response fingerprinting technique. In particular, the present
invention
relates to a method and system for locating a mobile station using a
fingerprinting
technique based on wideband channel measurements' results in conjunction with
an
artificial neural network.
BACKGROUND OF THE INVENTION
One problem of growing importance in indoor environments is the location of
people,
mobile terminals and equipment. Indoor radio channels suffer from extremely
serious
multipath and non-line of sight (NLOS) conditions that: have to be modelled
and
analysed to enable the design of radio equipment for geolocation applications.
Since
telecommunication and geolocation applications have different objectives (see
for
example K. Pahlavan, P. Krishnamurthy and J.E3eneat, "Wideband Radio
Propagation Modeling for Indoor Geolocation ~4pplications", IEEE
Communications
magazine, April 1998, which is incorporated herein by reference) existing
radio
channel models are not appropriate, and different models and techniques have
to be
applied to provide adequate location accuracy.
In traditional wireless geolocation applications, the basic function of the
location
system is to gather parametric information (received signal strengths RSS,
angles of
arrival AOA, times of arrival TOA or time differences of arrival TDOA) about
the
position of a mobile station (MS) and process that information to form a
location
estimate (see, for example, K.Pahlavan, X.Li, et al., "An Overviev~ of
Wireless indoor
Geolocafion Techniques and Systems", Proceeding of M~fIICN 2000, Paris,
France,
May 2000 which is incorporated herein by reference).
CA 02442950 2003-09-26
' 2
In indoor environments where conditions of signal propagation are severe
(multipath,
NLOS), the traditional parametric geolocation techniques (RSS, AOA, TOA, TDOA)
or their combinations (TDOA with AOA or RSS) fail to provide adequate location
accuracy. For these techniques, all the paths used for triangulation have a
LOS to
ensure an acceptable accuracy, a condition that is not met in an indoor
environment.
Geolocation based on the received signals' fingerprint (fingerprinting
technique)
performs better in such an environment (see, for example, C.Nerguizian,
C.Despins
and S.Affes, "A Framework for lndonr Geolocation using an Intelligent System",
3'd
IEEE Workshop on WLANs, Boston, September 2001 [hereinafter Nerguizian et al.]
which is incorporated herein by reference).
Most existing indoor geofocation applications use a network-based system
architecture in which base stations (BS) or access points (AP) extract
location
dependent parameters or metrics (RSS, AOA, TOA or TDOA) from the received
radio signals transmitted by the mobile station (MS) and relay the information
to a
control station (CS). Then the position of the user (MS) is estimated and
displayed at
the CS.
In the parametric geolocation technique, the concept of the line of position
(LOP),
with at least two observations, is used in order to obtain a two-dimensional
position
fix.
Most of the geolocation system architectures and techniques developed for
cellular
systems are applicable for indoor geolocation systems with special
considerations
(see, for example, K.Pahlavan, X. Li and J.P.Makela, "Indoor Geolocation
Science
and Technolog,~', IEEE Communications magazine, F=ebruary 2002 [hereinafter
Pahlavan et al.] which is incorporated herein by reference).
For the parametric geolocation technique using the received signal strength
(RSS), a
mathematical model describing the path loss {PL) attenuation with distance (d)
is
required. If the power transmitted by a mobile station is H;nown, measurement
of the
received signal strength provides a distance estimate between the mobile
terminal
(MS) and the fixed station (BS or AP). The estimated distance will determine a
circle,
CA 02442950 2003-09-26
3
centred at the receiver, on which the mobile transmitter lies. Three RSS
measurements will provide the two-dimensional location ~of the mobile.
For the parametric geolocation technique using the angle of arrival (AOA),
antenna
arrays at fixed stations are required for the direction finding of the signal
of interest
(see, for example, J.C.Liberty and T.S.Rappaport, Smarl Antennas f~r
~1/ireless
Communications:IS-95 and Third Generati~n ODMA Applfcatior7s, Prentice Hali
PTR,
1999 which is incorporated herein by reference). Two fixed stations measure
the
arrival angles of the signal that is transmitted from a mok~ile user. Sased on
the AOA
estimates and the known positions of the fixed ;~fations, simple geometric
relationships are used to form the two-dimensional location estimate.
In the parametric geolocation technique using the tinne of arrival (TOA), if
the
estimate of the propagation time (TOA) of the signal transmitted by a mobile
station
and received by a fixed station is known, the estimated distance between the
mobile
user and the fixed station can be determined providing geometrically a circle,
centred
at the receiver, on which the mobile transmitter lies. Three TOA measurements
will
provide the two-dimensional location of the mobile.
In the parametric geolocation technique using the time difference of arrival
(TDOA),
the locus of the estimated constant TDOA of a pair of fixed stations
(receivers)
defines a hyperbola, with foci at the receivers, on which the mobile
transmitter lies.
Three TDOA measurements will provide the two-dimensional location of the
mobile.
The accuracy of these traditional parametric geolocation techniques (RSS, AOA,
TOA and TDOA) or their combinations (TDOA with AOA or RSS) depends on
several factors, including the:
~ indoor environment (multipath, non-line of sight and local shadowing);
~ path loss model used in the RSS technique to estirnate the ranges;
~ plane wave/near field propagation model, the angular resolution of the
antenna array and the direction of arrival's estimation algorithm used in the
AOA technique;
CA 02442950 2003-09-26
4
~ time or time difference of arrival's estimation algorithm used in TOArfDOA
techniques;
~ number of fixed stations involved in the intersection of the lines of
position
LOP),
~ geographical location of the mobile station relative to the fixed stations;
and
~ positioning algorithm used to estimate the user's location.
Tree main measurement errors, introduced during the extraction of the location
dependent metrics, are due to the indoor environment. 'The lines of position
(LOP),
due to these errors, do not intersect at a point resulting in large estimation
errors.
Moreover, each of these techniques has its limitations.
Although the RSS indoor geolocation is easy to realise, variations in the F2SS
can be
as great as 30 dB over distances on the order of a half wa~,elength due to
small
scale fading and shadowing effects.
Due to the limited angular resolution of the antenna array, large location
errors occur
in the AOA indoor geolocation because the scatterers are located around both
the
transmitter and the receiver. Moreover, a mobile unit situated between two
FSs,
placed face to face, cannot be localised.
For the time-based (TOA and TDOA) indoor geolocation techniques, LOS
propagation conditions are necessary to achieve high Ic~cation accuracy.
Moreover,
the TOA technique requires strict time synchronisation k>etween the
transmitter and
the receivers, whereas only time synchronisation among ail the receivers is
needed
for the TDOA technique.
In general, the time-based TDC)A technique is the most popular one, and may be
combined with other techniques to improve the location accuracy
(http:l/www.comm-
nav.com/e911.htm).
The location accuracy reported by companies, which use the time-based indoor
geolocation technique with proprietary infrastructures (i.e. 3D-iD), is in the
range of 3
CA 02442950 2003-09-26
meters. For the parametric indoor geolocation, Kalman filtering and fusion of
multiple
metrics may be used to improve positioning performance (see, for example,
E. D. Kaplan, Understanding GPS: Principles and Applicati~ns, Artech House,
1996
which is incorporated herein by reference). However, in a non-line of sight
indoor
environment, alternatives to the parametric geolocation techniques have to be
considered.
To improve the accuracy of the user's location in a harsh environment
(multipath and
non-line of sight), the effect of multipath has to be miticlated or multipath
has to be
used as constructive information.
A radio frequency signal transmitted from a given geographical IViS location
has a
distinct pattern by the time it reaches a receiver. Interference caused by
natural or
man-made objects causes the signal to break up into a number of different
paths
(multipath). Hence, each location produces a uniquE; 'signature' pattern
called
fingerprint (see, for example, httpa/www.uswcorp.com).
The process of geolocation based on the received signals' fingerprint
(location
fingerprinting or premeasurement-based location pattern recognition technique)
is
composed of two phases, a phase of data collection (off-line phase) and a
phase of
locating a user in real-time (real-time phase, see, for example, s~lergcaizian
et al.). The
first phase consists of recording a set of fingerprints (in a database) as a
function of
the user's location, covering the entire zone of interest. During' the second
phase, a
fingerprint is measured by a receiver and compared with the recorded
fingerprints of
the database. A pattern matching algorithm (positioning algorithm) is then
used to
identify the closest recorded fingerprint to the measured one and hence to
infer the
corresponding user's location (Figure 1).
To constitute a "signature" pattern or a fingerprint, several types of
information
(referring to Figure 2) can be used such as, received signal strength (RSS),
received
angular power profile (APP) and received power delay profile (PDP) or channel
impulse response (CIP)
CA 02442950 2003-09-26
6
On the other hand, several types of pattern-matching algorithms may be used in
the
fingerprinting technique, which have the objective to give the position of the
mobile
station with the lowest location error. The most popular algorithms are based
on the:
~ nearest neighbours) in signal space (location estimate defined as the lowest
Euclidean, Box-Cox or statistical metric in signal space);
cross-correlation between signal vectors (location estimate defined as the
highest correlation coefficient between signal vectors); and
~ use of an artificial neural network (location estimate defined as the
closest
ANN's output to the training set's outputs).
It has to be noted that the accuracy of the method is primarily a function of
the
reproducibility and uniqueness of the estimated set of fingerprint
information.
Reproducibility means, the achieving of almost the samE; estimated set of
fingerprint
information in one location, for different observation times. lJniqueness
means that
the set of fingerprint information in one location is relatively different
from the one in
another location (no aliasing in the signature patterns).
Several geolocation systems, using fingerprinting technique, have been
deployed in
outdoor and indoor environments. The main differences between these systems
are
the types of fingerprint information and the types of pattern matching
algorithms. An
overview of these systems is given next.
RADAR (designed by IVticrosoft Corporation see http://www.microsoft.com) is an
RF
network-based system for locating and tracking users inside buildings (see,
for
example, P.Eahl and V.N.Padmanabhan, "RA~AR : An ln-Building R'F-based User
L~cation and Tracking Systerrr"', Proceedings of IEEE INF~C~Nl 2000, Tel Aviv,
Israel, IVlarch 2000 which is incorporated herein by reference). It uses RSS
(narrowband measurements) fingerprint information gathered at multiple
receiver
locations to determine the user's co-ordinates. The system, operating with
V1ILAN
technology, has a minimum of three access points (fixE:d stations) and covers
the
entire zone of interest.
CA 02442950 2003-09-26
The pattern-matching positioning algorithm consists of the nearest neighbours)
in
signal space. The minimum Euclidean distance (in signal space), between the
observed RSS measurements and the recorded set of RSS measurements,
computed at a fixed set of locations, gives the estimated user's location.
~CM (concept designed by \1T'T Information Technology/, see http:llwww.vtt.fi)
is an
RF handset-based system for locating and tracking users in a, metropolitan
outdoor
environment (see, for example, H.Laitinen, T.Nordstrc~m and J.Lahteenmaki,
"Dafabase Correlation Method for GSM Location", IIEEE ~fehicular Technology
Conference, Rhodes, Greece, May 2001 which is incorporated herein by
reference).
The mobile terminal that needs to be located performs measurements of signal
strength (narrowband measurements) received from the serving cell and six
strongest neighbours. The gathered information is then sent to a location
server,
where the location of the user is estimated and this estimate is sent back to
the
application server. Other types of signal information (cell i~, propagation
time delay)
can also be used within the network (see, for example, I-I.Laitinen,
T.Nordstr~m and
J.Lahteenmaki, "Location of GSM Terminals using a G~atabase of Signal Strength
Measurements", URSI XXV National Convention on Radio Science, Helsinki,
Finland, September 2000 which is incorporated herein by reference). The
system,
operating with the GSM Cellular technology, has several fixed stations and
covers
the entire zone of interest.
A simple correlation algorithm is used to estimate the user's location. A best
match
search, between the observed RSS measurements by the mobile station and the
recorded set of RSS measurements in the location server, is computed at a
fixed set
of locations and the MS's location is estimated.
It has to be noted that, since 17CM is a handset-I~ased location system, its
implementation involves some software modifications of the mobile terminal in
order
to enable the retrieval of received signal characteristics.
In the framework of the VVILMA project (see http:ll .wilmaproject.org) RSS
fingerprinting technique is used to locate users in a building with a iNLAN
infrastructure (see, for example, R.Sattiti, T.L.Nhat and A.!/iliani,
"Location-Aware
CA 02442950 2003-09-26
Computing: A Neural Network Model for Determining Location in VIlireless
LANs",
Technical Report # DIT-02-0083, University of Trento, 'rrento, Italy, February
2002
which is incorporated herein by reference). The pattern-matching algorithm
involved
is an artificial neural network, which consists of a multi-layer perceptron
(MLP)
architecture with 3, 8 and 2 neurones in the input, hidden and output layers
respectively to achieve the generalisation needed when confronted with new
data,
not present in the training set.
RadioCamera (designed by US Wireless Corporation, see http:llwww.uswcorp.com)
is an RF network-based system for locating and tracking users in a
metropolitan
outdoor environment. It uses multipath angular power profile (APP) information
gathered at one receiver to locate the user's co-ordinates. The system,
operating
with cellular technology, has one-antenna array per cell ('fixed station) and
covers the
entire zone of interest. The pattern-matching algorithm, used to estimate the
user's
location, consists of the nearest neighbours) in signal space. The minimum
statistical (Kullback-Liebler) distance (in signal space), between the
observed APP
measurements and the recorded set of APP measurements, computed at a fixed set
of locations, gives the estimated user's location (see, for example, U.S.
Patent
6,112,095 for Signature Matching for Location Determination in Wireless
Communication Systems which is incorporated herein by reference).
DCM, operating with UMTS technology and using CIR as fingerprint information,
is
the second RF handset-based system conceived by VTT Information Technology for
locating and tracking users in a metropolitan outdoor environment (see, for
example,
S.Ahonen, J.Lahteenmaki, H.Laitinen and S.Horsmar~heimo, '6Usage of Mobile
Location Techniques for UMTS Network Planning in Urban Env~ironmenY', IST
Mobile
and Wireless Telecommunications Summit 2002, Thesaaloniki, Greece, June 2002
which is incorporated herein by reference). It has several fixed stations and
covers
the entire zone of interest. To form the database, a set of fingerprints is
modeled by
computing the radio channel impulse responses (CIR) with a ray-tracing tool.
The
magnitudes of these impulse responses or the power delay profiles (PDP) are
calculated (after setting a threshold value in order to reduce contributions
of noise
power and interference from other codes) from each fixed station to each
receiving
point corresponding to the user's location. The mobile terminal that needs to
be
CA 02442950 2003-09-26
located performs measurements of channel's impulse responses (wideband
measurements).
The magnitude of the impulse response from the strongest fixed station is
correlated
with the content of its database (pattern-matching algorithm) at the location
server.
The receiving point with the highest correlation coefficient is taken to
represent the
co-ordinates of the mobile station.
Referring to T.Nypan, K.Gade and T.Maseng, "Location using Estimated Impulse
Responses in a IVlobile Communication System", 4t" Nordic Signal Processing
Symposium (NORSIG 2001), Trondheim, Norway, October 2001 Chereinafter iilypan
et al.) which is incorporated herein by reference, a measured channel's
impulse
responses are used for database collection and for location estimation
algorithm.
The system performs an outdoor geolocation using GSM and UMTS technologies.
The pattern-matching algorithm involved is based on the nearest neighbour in
signal
space. The minimum Box-Cox distance (see, for example, l-.Nypan, K.Gade and
O.Hallingstad, "Vehicle Positioning by Database Comparison using the fox-Cox
iVletric and Kalman Filtering", IEEE i/ehicular Technology Conference, Vol.
55, No. 4,
Birmingham, USA, February 2002 which is incorporated herein by reference)
between the observed CIR measurement and the CIR .measurements contained in
the database gives the estimated user's location.
The accuracy and coverage of the geolocation systerns, using the
fingerprinting
technique, depend on the resolution and the size of the database. Calibration
measurement and database maintenance are essential in the operation of these
systems. Moreover, the search methodology, involved in the pattern-matching
algorithm should be efficient to minimise the time needed for the
localisation.
Systems, using RSS fingerprinting technique (RADAR and WILMA for indoor, DCM
for outdoor), require the involvement of several fixed stcitions to compute
the user's
location. Moreover, RSS yield a great amount of variation (due 'to fading
effects) for a
specific location implying a reproducibility concern, which may degrade the
location
accuracy.
CA 02442950 2003-09-26
The system, using APP fingerprinting technique (RadioCamera for outdoor),
requires
the use of an antenna array with high angular resolution for indoor
geolocation since
the scatterers are around both the transmitter and the receiver.
5
Systems, using CIR or PDP fingerprinting technique (DCiVI and Nypan et al. for
outdoor), have the advantage to be reproducible and it respects the uniqueness
property, especially when the localisation is done ~on a continuous basis
(user's
tracking).
As a conclusion, it seems that the signature based on t:he impulse response of
the
channel gives the best location accuracy for an indoor ge:olocation, see, for
example,
Nerguizian et al.. However, its implantation involves the use of a wideband
receiver.
On the other hand, the pattern-matching algorithm used ire RADAR, DCM and
RadioCamera systems may show a lack of generalization (an algorithm that gives
an
incorrect output for an unseen input), a lack of robustness against noise and
interference, a lack of pattern match in some situations (i.e. the Euclidean
distance
can be minimized without having the match of the two patterns) and a long
search
time needed for the localization (done during the real-time phase) especially
when
the size of the environment or the database is large. H~:nce, the use of an
artificial
neural network (ANN), as the pattern-matching or positioning algorithm, is
essential
to the enhancement of the geolocation system.
As a measure of performance, the median resolution of the location estimation
for
indoor and outdoor geolocation systems, using fingerprinting techniques, is
reported
to be in the range of 2 to 3 meters and 20 to 150 meters respectively.
Referring to Table 1, the different geolocation techniques are presented in
order to
compare their features, strengths and weaknesses.
CA 02442950 2003-09-26
11
SUMML~RY OF THE INVENTION
In order to address the above and other drawbacks the present invention
implements
a fingerprinting technique using the channel's impulse response information as
a
novel approach for geolocation in mines, which has a bE:fiter reproducibility
property,
compared to the other two fingerprint information (RSS and angular power
profile).
The use of an artificial neural network as a pattern-matching algorithm for
the
proposed system is a new approach that has the advantage to give a robust
response with a generalisation property (the location fingerprint does not
have to be
in the fingerprint database). Moreover, since the training of the ANN is off-
line, there
is no convergence and stability problems that some control (real-time)
applications
encounter. Finally, the transposition of the system from two to three
dimensions is
easy (addition of a third neuron in the ANN's output layer corresponding to
the z
position of the user).
~n the other hand, the fingerprinting technique needs the digital map of the
environment and is not well suited for dynamic areas. Preliminary measurements
in
mine showed that the influence of low human activity is negligible on the
wideband
measurement results at the specific frequency of operation. hlowever, a heavy
machinery or vehicle may considerably change the properties of the channel,
obliging an update of the database's information (a new training of the neural
network). This channel variation issue can be addressed, for example, by using
a
master neural network. After detecting the changes in the channel's
properties, the
system identifies the specific situation (channel state) via a scanning
process and
activates the trained neural network corresponding to this specific situation.
Finally, the method may also be applicable to many other indoor applications
(shopping centres, campuses, office buildings). In addition, some advanced
simulation programs may be used to generate impulse responses as a function of
user location (for the training set of data of the neural network) instead of
deriving
these impulse responses from wideband measurements. This approach will reduce
the database generation time for the proposed geolocation system and will act
in
favour of the proposed system's implementation.
CA 02442950 2003-09-26
12
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 illustrates the process of geolocation using received signals'
fingerprint, a)
off-line phase, b) real-time phase;
Figure 2 provides an overview of the types of fingerprint information;
Figure 3 is a map of the underground gallery with wideband measurement
positions;
Figure 4 is a digital photograph showing a part of the underground gallery,
showing
that the walls have some roughness, the floor is not flat and that it contains
some
plaques of water;
Figure 5 illustrates the operation of the proposed systern, a) learning phase
(off-line
phase), b) recalling phase (real-time phase);
Figure 6 illustrates the proposed pattern-matching ANN;
Figure 7 provides estimated and true position locations in x and y, with
inputs
corresponding to the training set of data defined by the number of positions
of the
mobile station;
Figure 8 provides location errors in x, y and Euclidean distance (c~, with
inputs
corresponding to the training set of data defined by the number of positions
of the
mobile station;
Figure 9 provides cumulative distribution functions (CDI=s) of location errors
in x, y
and Euclidean distance (~, with inputs corresponding to the training set of
data
defined by the number of positions of the mobile station;
Figure 10 provides estimated and true position locations in x and y, with
inputs
corresponding to the untrained set of data defined by the number of positions
of the
mobile station;
CA 02442950 2003-09-26
13
Figure 11 provides location errors in x, y and Euclidean distance (ark, with
inputs
corresponding to the untrained set of data defined by the number of positions
of the
mobile station;
Figure 12 provides cumulative distribution functions (CC~Fs) of location
errors in x, y
and Euclidean distance (c~, with inputs corresponding to the untrained set of
data
defined by the number of positions of the mobile station; and
Figure 13 provides cumulative distribution functions (C~Fs) of location errors
in
Euclidean distance (cn, with inputs corresponding to the untrained set of data
and
with three positioning algorithms (Euclidean metric, Box-Cox metric and
artificial
neural network).
DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMIIIIENT
The proposed geolocation system is an RF network-based system for locating and
tracking users in an indoor mime. It uses a channel's multipath power delay
profile or
impulse response (obtained from wideband measurements) information (see, for
example, Nerguizian et al.), gathered at one receiver, to locate the user's co-
ordinates (uplink network based approach). The system, can be operated with
different radio access technologies, has one fixed station (a second one can
be used
as redundancy) and covers the entire zone of interest.
Measurements were conducted in an underground gallery of an abandoned gold
mine. Located at a 40 m underground level, the gallery stretches over a length
of 75
meters with a width and height both of approximately 5 meters. Figure 3
illustrates
the plan of the gallery with all its under adjacent galleries.
A central frequency of 2.4 GFIz has been used throughout the measurements in
order to have a compatibility with WLAN systems, which may be used far data,
voice
and video communications as well as for radio location purposes. ~ue to the
curvature of the gallery, the existence of a non- line of sight NLc~S case is
visible.
CA 02442950 2003-09-26
14
The digital photograph, given in figure 4, shows a part of the underground
gallery. It
can be seen from the photo that the walls have some roughness, the floor is
not flat
and it contains some plaques of water.
The complex impulse response of the channel (wideband measurements) has been
obtained using the frequency channel sounding technique. During the
measurements, the vector network analyser has performed the transmission and
the
reception of the RF signal. The inverse Fourier transform (IFT) has been
applied to
the measured complex transfer function of the channel iin order to obtain its
impulse
response.
The chosen frequency band was centred at 2.4 GHz with a span of 200 MHz
corresponding to a theoretical time resolution of 5 nanoseconds (in practice,
due to
the use of windowing, the time resolution is estimated to be around 8
nanoseconds).
The sweep time of the network analyser has been decreased to validate the
quasi-
static assumption of the channel. Each sweep consisted of 201 complex samples
spaced of 1 MHz from each other giving an unambiguous delay time of 1
microsecond, which was far beyond the sum of the maximum excess delay for the
studied mining environment and the propagation delay of the cable.
The wideband experimental procedures (see, for exampie, C.Nerguiziian,
C.Despins,
S.Aifes and M.Djadel, "Narrornrband and I~llideband Radio Channel
Measc~rements in
an Underground Mine with Narrov~ lAeins at z.4 sJHz", paper submitted to the
IEEE
Transactions on Wireless Communications, September 2003 which is incorporated
herein by reference) were defined to characterise the relevant parameters of
the
channel and to utilise these parameters in order to perform a radio location
of
workers in the underground gallery. Hence, for thne radio-location purposes
(fingerprinting technique), the experimental procedures given in this article
are
different from those encountered in previous works.
The network analyser and the PC were stationed with the receiving antenna and
the
other receiver components at the predefined referential. The equipment was
tested
for flat response in the measurement band and calibrated in the presence of
the RF
cable. The transmitting antenna and the other transmitter components were
moved
CA 02442950 2003-09-26
to different locations within the underground gallery by varying their
position of 0.5
metres in width (6 positions having a distance of 0.5 meter for the gallery
width of 5
metres) and 1.0 metres in length (70 positions having a distance of 1 metre
for the
gallery length of 70 metres). Some other extra intermediate positions have
also been
5 used for the LOS and NLOS cases giving a total of 490 location measurements
(Fig.
3). During the measurements, the transmitting and receiving antennas were both
mounted on carts at a height of 1.9 meters (simulating, for example, an
antenna
placed on the helmet of a miner).
10 The complex transfer function was obtained at all 490 measurement
locations. For
each location, a temporal average has been performed on a set of ten (10)
measurements of different observation times (a local spatial average may also
be
performed). The time domain magnitude of the complex impulse response has been
obtained, from the measured samples of the frequency domain response, using
the
15 inverse fast Fourier transform (IFFT).
From the magnitude of the complex impulse response, the mean excess delay
(am),
the RMS delay spread (zns), the maximum excess delay (zmax), the total
received
power (P), the number of multipath components (ll~, the power of the first
path (P~)
and the arrival time (delay) of the first path (z?) of the channel have been
computed
at alf 490 measurement locations by using a predefined threshold of 20 dB for
the
multipath noise floor. The first five (5) parameters characterized the time-
spread
nature of the indoor channel and the last two (2) parameters gave an emphasis
about the difference between LOS and NLOS situations. Then, these seven
relevant
parameters (instead of the magnitude of the impulse response), defining the
location-dependent features, have been used as the input for the artificial
neural
network (positioning algorithm).
The choice of these parameters was based on the necessity to have a good
reflection of the user's location 'signature' (good location-dependent
features of the
channel impulse measurements) without having excessive ANN input vector size
to
avoid the over-fitting of the ANN during its training phase.
CA 02442950 2003-09-26
16
A trained artificial neural network can perform complex tasks, such as
classification,
optimisation, control and function approximation. The pattern-matching
algorithm of
the proposed geolocation system can be viewed as a function approximation
problem (non-linear regression) consisting of a non-linear mapping from a set
of
input variables containing information about the relevant parameters of the
channel's
impulse response (zm, z~ms, Z'max~ P, N, l'T, z~) onto a two output variables
representing the two dimensional location of the mobile station (x, y).
The feed-f~rward artificial neural networks that c:an be used as function
approximation are of two types, Multi-Layer herceptron (MLP) networks and
Radial
Basis Function (RBF) networks. Either type of the two networks can approximate
any
nonlinear mapping to an arbitrary degree of precision provided the right
network
complexity is selected (see, for example, S.Haykin, Neural Network, a
C~mprehensive Foundation, MacMillan, 1094 which is incorporated herein by
reference). Specific learning algorithm is associated for each type of the two
networks, which has the role of adjusting the internal weights and biases of
the
network based on the minimization of an error function, and defines the
training of
the network.
The MLP networks enable to reach globally any non-linear continuous function
due
to the sigmoid basis functions present in the network, which are nonzero over
an
infinitely large region of the input space. Accordingly, they are capable of
doing a
generalisation in regions where n~ training data are available (generalisation
property). On the other hand, the RBF networks can reach the given non-linear
continuous function only locally because the basis functions involved cover
only
small, localised regions. However, the design of an RBf= network is easier,
and the
learning is faster compared to the MLP network.
A generalised regression neural network (GRNN), which is an RBF type network
with
a slightly different output layer, and an MLP type network have been tested
for the
proposed geolocation system. The MLP network showed a higher location error,
compared to the GRNN, during the memorisation of the data set. However, it
showed a lower location error during the generalisation phase of the network.
Since
CA 02442950 2003-09-26
17
the generalisation property of the system was of greater importance, the MLP
type
network has been chosen for the pattern-matching algorithm used in the
proposed
geolocation system.
The ANN, used in the proposed system, consisted of two phases, a supervised
learning phase (training of the network) and a recalling (testing or
functional) phase.
During the off-line phase, the MLP network was trained to form a set of
fingerprints
as a function of user's location and acted as a function approximator (non-
linear
regression). Each fingerprint was applied to the input of the network and
corresponded to the channel's relevant parameters (mean excess delay, RMS
delay
spread, maximum excess delay, tote! received power, number of multipath
components, power and arrival time of the first path) extracted from the
impulse
response data received by the fixed station. This phase, where the weights and
biases are adjusted in iterations to minimise the network performance
function, is
equivalent to the formation of the database (recording of the set of
fingerprints as a
function of user's location) seen with other fingerprinting systems.
During the real-time phase, the mentioned relevant parameters from a specific
mobile station (obtained from the measured channel's impulse response) were
applied to the input of the artificial neural network (acting as a pattern-
matching
algorithm). The output of the ANN gave the estimated value of the user's
location
(see Figure 5).
It has to be noted that when the size of an ANN is increased, the number of
the
internal parameters (weights and biases) increase inducing more local and
global
minima in the error surface, and making the finding of a global or a nearly
global
minimum, by the local minimisation algorithm, easier (see, for example,
Y.Shang and
B.IN.iNah, "Global Optimization for Neural Netnrork Training", COMPUTER, pp 45-
56, March 1996 which is incorporated herein by reference).
However, when the size of the ANN is large or equivalently, wl-ien the number
of the
weights and biases is large for the selected training set, an over-fitting
problem
occurs. This means that although the error on the training set is driven to a
very
small value, when new data is presented to the network the error is typically
large.
CA 02442950 2003-09-26
18
This is a case where the network has memorised (for example, using a look up
table)
the training set, but it has not learned to generalise to new situations (see
Fi.Demuth
and M. Beale, Neural Network Toolbox for use with Matiab (User's Guide), The
MathWorks Inc., 1998 [hereinafter Matlab User's GuideJ).
Hence, to have a network with a good generalisation property, the size of the
network should be chosen just large enough to provide an adequate fit. A way
of
improving the generalisation property is the use of a regularisation method
(modification of the performance function by adding to the mean sum of squares
of
the network errors a term that consists of the mean of the sum of squares of
the
network weights and biases). Moreover, to have an automated regularisation
(determination of the optimal regularisation parameters in an automated
fashion),
i3ayesian regularisation in combination with Levenberg-Marquardt algorithm may
be
used (see, for example, F.~.Foresee and M.T.~lagan, "Gaussian-Newton
Approximation to Bayesian Regularization", Proceedings of the 1997
International
Joint Conference on Neural Networks, pp 1930-1935, 1997 which is incorporated
herein by reference).
Hence, property trained MLP networks tend to give reasonable answers when
presented with inputs that they have never seen (generalisation property, see
Matlab
User's Guide). Typically, a new input will lead to an output similar to the
correct
output (target) for input vectors used in training that are similar to the new
input
being presented (no need to train the network on all possible inputloutput
pairs).
In order to have a good generalisation property, the MLP architecture used
consisted
of seven (7) inputs corresponding to the channel's relevant parameters, one
hidden
layer and an output layer with two (2) neurons corresponding to (x, y)
location of the
user (see Figure 6). A differentiable tan-sigmoid type of transfer function
has been
associated for neurons in the hidden Payers and a linear one for the output
layer.
A simulation was carried out using the Neural Network Toolbox of Matlab (see
Matlab User's Guide) with the results showing that ten neurons corresponding
to the
hidden layer are adequate to do the required regression. Special attention has
been
given to the over-fitting problem to respect the generalisation property (the
trainbr.m
CA 02442950 2003-09-26
19
function of Matlab has been used, which applies the Ba~yesian regularisation
with the
Levenberg-Marquardt algorithm). Hence, the designed network was robust to
perturbations at its input (i.e. errors in the measurement data) and was able
to do a
generalisation rather than a memorisation (giving the right location for an
unseen
and non trained input). Moreover, since MLP has an inherent low pass filter
property,
it may remove the high frequency components present ire the location error
signal.
4Nith seven (7) inputs, two (2) output neurons and ten (10) hidden neurons,
the total
adjustable number of weights and biases was equal to 102 ([7*10]+[10*2] for
the
weights, +[10]+[2] for the biases). This is almost four times smaller than the
total
number of the training set, which is equal to 367 and corresponds to the 75%
of the
measured wideband data. As a rule of thumb, to have a good generalisation
property
and to avoid the memorisation of the network, the number of the patterns in
the
training set has to be around four times the number of the internal adjustable
ANN
parameters. Hence the use of ten (10) hidden neurons was justified.
It has to be noted that, before training, the inputs and the targets have been
scaled
or normalised using the premnmx.m function of Matlab so that they fall in the
range [_
1, +1]. The outputs of a trained network, having scaled inputs and targets,
will fall in
the range of [-1, +1]. To convert these outputs back into the same units,
which were
used for the original targets, the postmnmx.m function of MatBab has been
used. The
normalisation of the inputs and targets is essential for the performance
improvement
of the ANN optimisation process.
Moreover, typical data sets often contain redundant information, or measured
values
(computed relevant channel's impulse response parameters), which are highly
correlated. It is useful in this situation to reduce the dimension of the
input vectors by
transforming the full set of training examples into a compressed set that
contains
only essential information. The prepca.m function.of Matlab has been used to
do this
operation based on the principal component analysis which performs three
effects: it
renders orthogonal the components of the input vectors (the vectors become
uncorrelated with each other), it orders the resulting orthogonal components
(principal components) so that those with the largest variation come first,
and it
CA 02442950 2003-09-26
eliminates those components which contribute the least to the variation in the
data
set (see Maflab User's Guide).
Using the Neural Network Toolbox of Matlab, the proposed neural network
5 architecture has been designed. For the learning phase, the seven relevant
parameters of the channel's impulse response and the measured true mobile
station
positions have been used as the input and as the target of the ANN
respectiveiy.
From the 490 measured data, 367 patterns have been employed to train the
network.
For the recalling phase, as a first step, the same 367 patterns have been
applied to
the pattern-matching neural network to obtain the location of the mobile
station
(validation of the memorisation property). The estimated and true position
locations,
the location errors as well as their cumulative density functions (CDF) have
been
computed for analysis purposes. The plots of the corresponding position
locations,
location errors and CDFs of location errors are given in figures 7, 8 and 9.
It has to be noted that the localisation error has been calculated as the
difference
between the exact position of the user and the winning position estimate given
by the
localisation algorithm, and hence represents the f~MS position location error.
Moreover, CDF of the location error has been used as the performance measure
of
the system.
For the training set of data, it can be seen (see Figure 8) that the location
error in x
varies between -3.2 meters and 3.7 meters, the location error in y varies
between -
1.9 meters and 1.8 meters and the maximum error in Euclidean distance, between
the estimated and the true positions, is equal to 3.9 meters.
Moreover, it can be seen, from Figure 8, that a distance location accuracy of
2
meters is found for 90~/a of the trained patterns. An improvement of the
location
accuracy is feasible at the cost of the generalisation property.
As a second step, the remaining 123 non-trained patterns have been applied to
the
network to verify the generalisation property of the proposed geolocation
system.
CA 02442950 2003-09-26
21
The estimated and true position locations, the location errors as well as
their
cumulative density functions (CDFs) have been computed and plotted (Figures
10,
11 and 12).
For the untrained set of data, it can be seen (see Figure 11 ) that the
location error in
x varies between -3.7 meters and 5.8 meters, the location error in y varies
between
-2 meters and 2,9 meters and the maximum error in Euclidean distance, between
the estimated and the true positions, is equal to 5.8 meters.
llAoreover, the accuracy of the position estimate depends on the resolution of
the
map, which in turn depends on the distance threshold used in the map building
process. After localisation has been achieved, the theoretical error between
the
actual and estimated position (localisation error) should therefore vary
between zero
and the distance threshold. Since the size of the grid used in the indoor
wideband
measurements was 0.5 meter wide and 1 meter long, the geolocation accuracy
that
one may expect with the proposed fingerprinting technique, should be between 0
and 1.12 meters (distance threshold) in terms of the Euclidean distance.
It can be seen, from Figure 12, that the location accuracy corresponding to
the
distance threshold is achieved for 40% of all the untrained patterns. ~ience,
the
proposed fingerprinting technique used for the geolocation of the studied
mine, gave
an accurate mobile station location. The results showed that a distance
location
accuracy of 2 meters has been found for 90% and 80% of the trained and
untrained
patterns respectively. This location accuracy, which may be improved at the
cost of
the generalisation property, is much smaller than the one found in the
literature for
indoor geolocation using fingerprinting techniques.
In order to see the advantage of using an ANN in an indoor geofocation system
using the fingerprinting technique, three different pattern-matching
algorithms
(Nearest neighbour minimising the Euclidean distance, nearest neighbour
minimising
the Box-Cox metric, see for example R.V.D. Heiden and F.C.A. Groen, "The Box-
Cox Metric for Nearest Neighbour Classificafion Improv~emeni", Pattern
Recognition
Society, Vol. 30, No. 2, 1997 which is incorporated herein by reference, and
artificial
neural network) has been used with the same empirical data set (untrained
patterns).
CA 02442950 2003-09-26
22
The three curves of Figure 13 give the CDFs of location errors in Euclidean
distance
(d} for the involved three pattern-matching algorithms.
Only the CDF of location errors using the AIVN with the trained patterns is
added on
the figure since the associated curves for the two other algorithms are not
necessary
(their location errors tend to zero due to the memorisation of the two
algorithms).
It can be seen that, for the generalisation property (the most important
property for
the fingerprinting technique), the artificial neural netvrork works the best
giving an
error less than 2 meters for 80%, for all the untrained patterns, compared to
68%
and 72% for the Euclidean and Cox-Box metrics respectively.
In indoor environments, the largest excess delay corresponding to the
detectable
multipath component may be on the order of 500 nanoseconds (see, for example,
H.Hashemi, "Impulse Response Modelling of Indoor Radio propagation Channels",
IEEE Journal on Selected Areas in Communications, Vol. 11, No. 7, September
1993 which is incorporated herein by reference). ~n the other hand, to
characterise
the discrete-time impulse response model or equivalently the multipath power
delay
profile, a reasonable bin (small time interval) resolution is needed. The
value chosen
for a bin depends on the indoor environment of interest.
The resolution of the measured channel impulse response depends on the system
bandwidth. The effect of a limited bandwidth is that multiple reflections may
end up in
the same time bin on the delay axis, implying the vector combination of the
reflections and yielding a resultant signal large or small depending on the
distribution
of phases among the component waves. This will give rise to a reproducibility
problem of the measured channel impulse responses.
For efficient operation of the proposed system, it would be advantageous to be
able
to resolve all multipath components to obtain the power' delay profile or the
impulse
response as a function of the user's location. Hence the radio access
technology
used for an effective implementation of the system should satisfy this
requirement
(resolution of the multipath differential delays in the nanoseconds range).
Several
existing technologies, with some modifications, are good candidates for such
an
CA 02442950 2003-09-26
23
application. The most promising technologies found iri practice are, the
mobile radio
system, the impulse radio system and the WLAN system. In this section, an
overview
about these three technologies will be given with their advantages and
disadvantages. The choice of the wideband receiver technology and its
implementation depend on the specific application and is still an open area of
research.
The popular standards defined in digital mobile radio systems are the
CDMA2000,
the GSM and the IJMTS. The CDMA uses a code division multiple access (CDMA)
with a direct sequence (DSSS) spread spectrum (spreading codes to separate
signals). The chip duration of a CDMA-DSSS is about 815 nanoseconds (a pseudo
noise sequence chip rate of 1.2288 Mbps). A CDMA RAKE receiver is able to
resolve the closely spaced multipath components with delays greater than chip
duration apart. Hence the choice of this technology without any modification
appears
inadequate for the proposed system. A super-resolution method for multipath
delay
estimation (see, for example, G.Morrison and M.Fattouche, "Super-Resolution
Modeling of the Indoor Radio Propagation ChanneP', IEEE Transactions on
Vehicular
Technology, Vol. 47, No. 2, May 1998 and F.Bouchereau, D.Brady and C.Lanzl,
"Multipath Delay Estimation using a Super-resolution PIlI-Correlation Method",
IEEE
Transactions on Signal Processing, Vol. 49, No. 5, May 2001 which are
incorporated
herein by reference) or an over sampling method (limited by the hardware's
clock
rate) can be used to improve the time resolution during the process of power
delay
profile collection.
The GSM uses a time division multiple access (TDMA) with a modulation data
rate of
about 270.833 Kbps (time resolution of 3700 nanoseconds). Hence the choice of
this
technology without any modification would also appear inadequate for the
proposed
system.
The WCDMA (Wide CDMA) accepted for the UMTS standard utilizes a chip rate of
3.86 Mcps and higher (time resolution of about 260 nanoseconds and lower).
When
the standard for receivers in WCDMA will be specified, a WCDMA RAKE receiver
(measuring the delay and the signet strength of all fingers, see Pahlavan et
al.) with
CA 02442950 2003-09-26
24
a high-resolution algorithm as discussed above, may be an acceptable choice
for the
proposed geolocation system.
The Ultra Wide Band (UWB) signalling used in an impulse radio system is a
viable
candidate for indoor geolocation applications since it has fine time
resolution
properties (see, for example, M.Z.Win and R.A.Scholtz, "On f?obustness of
Ultra
Wide Band Signals in ~lultipath Environments", IEEE Communication Letters,
February 1998 which is incorporated herein by reference). It is characterised
by very
low power transmission and by wide bandwidths (greater than a gigahertz). UWB
signalling uses pulses of very short duration (on the order of a nanosecond)
with a
certain repetition period (on the order of 100 nanoseconds). The data
modulation of
UWB is accomplished by a pulse position modulation at the rate of many pulses
per
data bit. Pseudo-random time hopping (time hopping codes) is used to eliminate
catastrophic collisions in multiple accessing. Properly designed UWB receivers
are
capable of resolving multipath components with differential delays of a
fraction of a
nanosecond (see, for example, K.Siwiak, P.Withington and S.Phelan, "Ulfra Wide
Band Radio: The emergence of an important New Technology", IEEE Vehicular
Technology Conference, Rhodes, Greece, May 2001 which is incorporated herein
by
reference). However, the received UWB signal acquisition is more rigorous than
a
CDMA signal. In the near future, when the Federal Communications Commission
(FCC) in the United States accepts the use of the UWB technology without any
restriction, it can be a good choice for the proposed geolocation system. In a
Wireless Local Area Network (WLAfV), access points (AP) represent the fixed
stations and PC cards installed in terminals represent the mobile stations.
The
standard IEEE 802.11 defines the Medium Access Control (MAC) sublayer, MAG
management protocols and services, and the Physical (PHY) layers (see B.O'Nara
and A Petrick, The IEEE 802. ? ? Handbook, IEEE Press, 1999).
The Medium Access Control of IEEE 802.11 supplies the functionality required
to
provide a reliable delivery mechanism for user data over noisy and unreliable
wireless media.
The Physical layer of IEEE 802.11 is the interface between the MAC and
wireless
media, which transmits and receives data frames over a shared wireless media.
CA 02442950 2003-09-26
The standard has four types of physical layers, IEEE 802.11-DSSS (Direct
Sequence Spread Spectrum), IEEE 802.'11b-HR/DSSS (High Rate DSSS), IEEE
802.11-FHSS (Frequency Hopping Spread Spectrum) and IEEE 802.11x-OFDM
5 (Orthogonal Frequency Division Multiplexing).
The IEEE 802.11-DSSS works at 2.4 GHz with a rate of 1 to 2 Mbps (approximate
resolution time of 500 nanoseconds).
10 The IEEE 802.11-FHSS works at 2.4 GHz with a rate of 2 Mbps (approximate
resolution time of 500 nanoseconds).
The IEEE 802.11b-HRIDSSS works at 2.4 GHz with a rate of 11 Mbps (approximate
resolution time of 90 nanoseconds).
The IEEE 802.11a-OFDM works at 5.8 GHz with a rate of 54 Mbps (a potential of
acceptable resolution time may be possible) and its zone of coverage is
smaller than
the HRIDSSS.
Another physical layer IEEE 802.11g-OFDM will be available soon. It will work
at 2.4
GHz with a rate of 54 Mbps. The IEEE 802.11x, fEEE 802.11b and IEEE 802.11g
WLAN systems may be acceptable choices for the proposed geolocation system.
Moreover, since the frequency of operation of the IEEE 802.11b and 802.11g
systems is lower than the one found in the former system, the reproducibility
and
uniqueness of the estimated set of fingerprint information is more easily
obtained in
the studied mining environment where rough wall surfaces induce a scattering
of the
incident signals.
It has to be noted that if the geolocation coverage area exceeds the range of
the
access point (AP), several APs may be used, each performing a geolocation and
covering a part of the zone of interest.
In summary, the choice of the radio access implementation technology depends
on
several parameters such as, time resolution, power consumption, distance
coverage,
CA 02442950 2003-09-26
26
data rate, users capacity, signal to noise ratio, tolerance to interference,
availability
of the product and modification of the available products (hardware and/or
software).
For the proposed geolocation system, the time resolution is a key factor.
Moreover, an important issue in the proposed geolocation system is the
multiple-
access factor (localisation of several mobile stations at the same moment).
Each of
the implementation technologies described above has a certain type of multiple
access technique (Time Division Multiple Access - TDMA, Code Division Multiple
Access -CDMA and Carrier Sense Multiple Access - CSMA). CDMA and TDMA
systems are typically easier to implement than CSM.A (found in WLAN systems).
However, the cost of a WLAN system is lower than sy stems operated with CDMA
or
TDMA.
A possible alternative may be the use of Air5 WL.AN systern, which operates at
a
frequency around 5 GHz and implements collision avoidance through its TDMA-
based synchronous MAC subiayer (see, for example, P. Fowler, "5 GHz Goes the
Qistance for Home Networdsing", IEEE Microwave Magazine, Vol. 3, No. 3,
September 2002 which is incorporated herein by reference). Another alternative
will
be to design a set of signals from different mobile stations in such a manner
that the
access point can distinguish the signals from different mobile units.
Hence, the multiple-access issue is another important factor to consider for
the
proposed geolocation system.
It has to be noted that in practice, it is convenient to have a system able to
support
both telecommunication and geofocation applications. Hence, impacts on
economic
and technical issues should be considered during the chosen technology's
implementation.
In general, it is the belief of the authors that, the WCDMA system may be
focused for
outdoar applications while the WLAN system may be used for indoor
applications.
Although the present invention has been described hereinabove by way of an
illustrative embodiment thereof, this embodiment can be~ modified at will,
within the
CA 02442950 2003-09-26
27
scope of the present invention, without departing from the spirit and nature
of the
subject of the present invention.
