(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2007/0010956A1
`Nerguizian et al.
`(43) Pub. Date:
`Jan. 11, 2007
`
`US 20070010956A1
`
`Publication Classification
`
`(51) Int. Cl.
`(2006.01)
`G06F 9/00
`(52) U.S. Cl. ................................................................ T02/57
`
`(57)
`
`ABSTRACT
`
`A system and method for predicting the location of a
`transmitter in an indoor Zone of interest, including fixed
`receiver for receiving a signal from the transmitter, the
`receiver deriving a fingerprint from the received signal, and
`a trained neural network. The trained neural network pre
`dicts the transmitter location from the fingerprint. The
`method includes receiving a signal transmitted from the
`transmitter at a fixed-location receiver, deriving a fingerprint
`from the received signal, Supplying the fingerprint to a
`trained neural network, and reading the predicted location
`from the neural network. The artificial neural network may
`further be trained and include a plurality of weights and
`biases is also shown. The method may include collecting a
`training data set of fingerprints and corresponding locations,
`inputting the training data set to the neural network, and
`adjusting the weights and biases by minimising a Sum of
`squares error function.
`
`(54) METHOD AND SYSTEM FOR INDOOR
`GEOLOCATION USING AN IMPULSE
`RESPONSE FINGERPRINTING TECHNIQUE
`(76) Inventors: Chahe Nerguizian, Montreal (CA);
`Charles Despins, L'Original (CA);
`Sofiene Affes, Montreal (CA)
`Correspondence Address:
`SCHWEGMAN, LUNDBERG, WOESSNER &
`KLUTH, P.A.
`P.O. BOX 2938
`MINNEAPOLIS, MN 55402 (US)
`(21) Appl. No.:
`11/389,882
`
`(22) Filed:
`
`Mar. 27, 2006
`Related U.S. Application Data
`(63) Continuation of application No. PCT/CA04/01745,
`filed on Sep. 24, 2004.
`Foreign Application Priority Data
`
`(30)
`
`Apr. 7, 2005 (WO)............................. 2005/032189 A1
`
`10
`
`
`
`2
`
`DISPLAY
`
`Page 1 of 19
`
`SAMSUNG EX-1068
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 1 of 9
`
`US 2007/0010956A1
`
`
`
`N
`
`Page 2 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 2 of 9
`
`US 2007/0010956 A1
`
`-N
`-9
`Nur
`Ph
`
`S O
`
`e
`2
`O
`2,
`
`s
`
`Era
`
`H
`
`r
`
`8
`qm
`
`O
`S.
`53
`Co
`
`LD
`
`3 a
`e
`5
`>
`2.
`3
`S Cls
`a s is S S
`a
`2
`C.)
`v.
`Q9
`O X
`S. e.
`
`X
`
`2
`
`
`
`O
`
`O
`
`O
`
`O
`
`O
`D
`
`O
`
`C
`l?)
`9
`
`(990S Sp) 10M0d palaoag peZeULION
`
`c.
`
`5
`
`S.
`
`C a"
`
`Page 3 of 19
`
`

`

`Patent Application Publication Jan. 11,2007 Sheet 3 of 9
`
`US 2007/0010956 Al
`
`30
`
`44
`
`Ch2 AT
`
`
`
`
`
`
`
`
`
`
`
`42
`
`Page 4 of 19
`
`Page 4 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 4 of 9
`
`US 2007/0010956 A1
`
`
`
`Page 5 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 5 of 9
`
`US 2007/0010956 A1
`
`sf3.sSg
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`E g
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`S
`
`S
`
`-
`
`rax. s
`
`3.
`
`
`
`3.
`
`ES
`
`S s
`s
`
`S
`
`
`
`
`
`
`
`ss
`
`s
`
`s
`
`
`
`
`
`rt CN2 O CN2
`
`O
`r.
`
`(II) Xu JOIly used (l)
`
`s' CN2 O CN2
`
`O
`r.
`
`Ea See SS
`ul IOLY tone (II) ( (.) IOLyttone)0
`
`Page 6 of 19
`
`

`

`
`
`
`
`X J0 Stille, I
`
`CIE)
`
`A JO SUL19, ICO
`
`CJO SUL19, UCI)
`
`Page 7 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 7 of 9
`
`US 2007/0010956 A1
`
`=IE-T-T-T-T-rrr!!!!!!
`
`
`
`LÆNo. WWFNINNÍ
`
`·090ý · O20,,
`
`() a yanguage
`
`
`
`
`
`O
`v
`
`ty
`
`O
`
`0
`
`Logo (a yielguage
`
`Page 8 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 8 of 9
`
`US 2007/0010956A1
`
`
`
`
`
`O
`
`ld
`
`s
`
`92|0
`
`X J0 SUL19, U. C.)
`
`A JO SUL19, UCIO
`
`CJO SUL18, u! CO
`
`Page 9 of 19
`
`

`

`Patent Application Publication Jan. 11, 2007 Sheet 9 of 9
`
`US 2007/0010956A1
`
`Page 10 of 19
`
`

`

`US 2007/0010956 A1
`
`Jan. 11, 2007
`
`METHOD AND SYSTEM FOR INDOOR
`GEOLOCATION USING AN IMPULSE RESPONSE
`FINGERPRINTING TECHNIQUE
`
`RELATED APPLICATIONS
`0001. This application is a continuation under 35 U.S.C.
`111(a) of PCT/CA2004/001745, filed Sep. 24, 2004 and
`published as WO 2005/032189 A1, filed Apr. 7, 2005, which
`claimed priority under 35 U.S.C. 119(e) to U.S. Provisional
`Patent Application No. 60/505,753, filed Sep. 26, 2003,
`which applications and publication are incorporated herein
`by reference and made a part hereof.
`
`FIELD OF THE INVENTION
`0002 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 a neural network
`as well as a method for training the neural network.
`
`BACKGROUND OF THE INVENTION
`0003. 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 tele
`communication and geolocation applications have different
`objectives, existing radio channel models developed for
`telecommunications are not appropriate, and different mod
`els and techniques have had to be developed to provide
`adequate and accurate localisation.
`0004 The prior art reveals wireless geolocation applica
`tions where the location system gathers parametric informa
`tion, for example the received signal strengths (RSS), angles
`of arrival (AOA), times of arrival (TOA) or time differences
`of arrival (TDOA) and processes this information to form a
`location estimate. In indoor environments where signal
`propagation is very complex, these existing parametric
`geolocation techniques (and combinations thereof) provide
`only limited location accuracy, as they depend largely on
`Line of Sight (LOS) to ensure accuracy, an element which
`of course is largely not present in indoor environments. The
`major errors in measurement are introduced during the
`extraction of the location dependent metrics, and are due
`primarily to the indoor environment. As a result, the lines of
`position (LOP) do not intersect due to these errors, thereby
`resulting in large estimation errors. Additionally, multiple
`measurements are invariably needed in order to obtain a
`two-dimensional position.
`0005 Geolocation based on a received signals finger
`print have proven more accurate at determining location in
`indoor environments. Due to interference introduced by
`natural or man-made objects, which tend to cause a trans
`mitted signal to break up into a number of different paths,
`each transmitted signal has a unique signature, or finger
`print, by the time it reaches a given receiver dependant on
`the location of the transmitter and the receiver.
`0006 The process of geolocation based on the received
`signals fingerprint 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).
`0007. The first phase consists of recording a set of
`fingerprints as a function of the user's location, covering the
`entire Zone of interest. During the second phase, a finger
`print 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.
`0008 To constitute a “signature' pattern or a fingerprint,
`several types of information can be used such as, received
`signal strength (RSS), received angular power profile (APP)
`and received power delay profile (PDP) or channel impulse
`response (CIR).
`0009. On the other hand, several types of pattern-match
`ing 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:
`0010) nearest neighbour(s) in signal space (location
`estimate defined as the lowest Euclidean, Box-Cox or
`statistical metric in signal space); or
`0011 cross-correlation between signal vectors (loca
`tion estimate defined as the highest correlation coeffi
`cient between signal vectors).
`0012. 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. Reproduc
`ibility means the achievement of almost the same estimated
`set of fingerprint information in one location for different
`observation times. Uniqueness means that the set of finger
`print information in one location is relatively different from
`the one in another location (no aliasing in the signature
`patterns).
`0013 Several geolocation systems, using fingerprinting
`techniques, have been deployed in both indoor and outdoor
`environments. The main differences between these systems
`are the types of fingerprint information and the types of
`pattern matching algorithms.
`0014 RADARTM, is an RF network-based system for
`locating and tracking users inside buildings and uses RSS
`(narrowband measurements) fingerprint information gath
`ered at multiple receiver locations to determine the user's
`co-ordinates. The system, operating with WLAN technol
`ogy, has a minimum of three access points (fixed stations)
`and covers the entire Zone of interest.
`0015 The pattern-matching positioning algorithm con
`sists of the nearest neighbour(s) in signal space. The mini
`mum 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.
`0016 DCMTM, is an RF handset-based system for locat
`ing and tracking users in a metropolitan outdoor environ
`ment. The mobile terminal that needs to be located performs
`measurements of signal strength (narrowband measure
`ments) received from the serving cell and six strongest
`neighbours. The gathered information is then sent to a
`
`Page 11 of 19
`
`

`

`US 2007/0010956 A1
`
`Jan. 11, 2007
`
`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 ID, propagation time delay)
`can also be used within the network. The system, operating
`with the GSM Cellular technology, has several fixed stations
`and covers the entire Zone of interest.
`0017. 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.
`0018) It has to be noted that, since DCMTM is a handset
`based location system, its implementation involves some
`software modifications of the mobile terminal in order to
`enable the retrieval of received signal characteristics.
`0019. In the framework of the WILMA project, RSS
`fingerprinting techniques are used to locate users in a
`building with a WLAN infrastructure. 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.
`0020 RadioCameraTM 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
`coordinates. 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
`neighbour(s) in signal space. The minimum statistical (Kull
`back-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. Pat. No.
`6,112,095 for Signature Matching for Location Determina
`tion in Wireless Communication Systems which is incorpo
`rated herein by reference).
`0021 DCMTM, operating with UMTS technology and
`using CIR as fingerprint information, is the second RF
`handset-based system for locating and tracking users in a
`metropolitan outdoor environment. It has several fixed sta
`tions 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 located
`performs measurements of channel's impulse responses
`(wideband measurements).
`0022. 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.
`
`0023 Measured channel impulse responses are used for
`database collection and for location estimation algorithm.
`The system performs an outdoor geolocation using GSM
`and UMTS technologies.
`0024. The pattern-matching algorithm involved is based
`on the nearest neighbour in signal space. The minimum
`Box-Cox distance between the observed CIR measurements
`and the CIR measurements contained in the database gives
`the estimated user's location.
`0025 The accuracy and coverage of the geolocation
`systems, using the fingerprinting technique, depend on the
`resolution and the size of the database. Calibration measure
`ment and database maintenance are essential in the operation
`of these systems. Moreover, the search methodology,
`involved in the pattern-matching algorithm should be effi
`cient to minimise the time needed for the localisation.
`0026 Systems, using RSS fingerprinting technique
`(RADARTM and WILMA for indoor, DCMTM for outdoor),
`require the involvement of several fixed stations to compute
`the user's location. Moreover, RSS yield a great amount of
`variation for a small location deviation implying a repro
`ducibility concern, which may degrade the location accu
`racy.
`0027. The system, using APP fingerprinting technique,
`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.
`0028 Systems, using CIR or PDP fingerprinting tech
`nique, have the advantage of being reproducible and respect
`ing the uniqueness property, especially when the localisation
`is done on a continuous basis (user's tracking).
`0029. A signature based on the impulse response of the
`channel appears to give the best location accuracy for an
`indoor geolocation. However, its implantation involves the
`use of a wideband receiver.
`0030. On the other hand, the pattern-matching algorithm
`used in RADARTM, DCMTM and RadioCameraTM 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 mini
`mized 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. Hence, the use of an artificial neural
`network (ANN), as the pattern-matching or positioning
`algorithm, is essential to the enhancement of the geolocation
`system.
`0031. As a measure of performance, the median resolu
`tion of the location estimation for indoor and outdoor
`geolocation systems, using fingerprinting techniques, is
`reported to be in the range of 2 to 3 metres and 20 to 150
`metres respectively.
`
`SUMMARY OF THE INVENTION
`0032. The present invention addresses the above and
`other drawbacks of the prior art by providing a system for
`predicting the location of a transmitter located in an indoor
`Zone of interest. The system comprises a fixed receiver for
`receiving a signal from the transmitter, the receiver deriving
`
`Page 12 of 19
`
`

`

`US 2007/0010956 A1
`
`Jan. 11, 2007
`
`a fingerprint from the received signal, and a trained neural
`network. The trained neural network predicts the transmitter
`location from the fingerprint.
`0033. There is also provided a method for training an
`artificial neural network for predicting a location of a
`transmitter in an indoor Zone of interest where the network
`is comprised of a plurality of weights and biases. The
`method comprises the steps of collecting a training data set
`comprising a plurality of fingerprints and corresponding
`locations inputting the training data set to the neural net
`work, and adjusting the weights and the biases by minimis
`ing a sum of squares error function
`
`1 -
`- a. ?
`ED = N 2. (ii - a)
`
`where t, is a corresponding location of an i' entry of the
`training data set offingerprints and a is the neural networks
`predicted transmitter location to the i' entry of the training
`data set fingerprints. The collecting step comprises the steps
`of a) placing a test transmitter at a new location within the
`Zone of interest, b) transmitting a signal from the test
`transmitter to a receiver, c) extracting a fingerprint from the
`received signal, d) associating the fingerprint with the new
`location and e) repeating steps a), b), c) and d) throughout
`the Zone of interest n times.
`0034 Additionally, there is disclosed a method for pre
`dicting the location of a transmitter in an indoor Zone of
`interest. The method comprises the steps of providing a
`receiver having a fixed location, receiving a signal trans
`mitted from the transmitter at the receiver, deriving a fin
`gerprint from the received signal, Supplying the fingerprint
`to an input of a trained neural network and reading the
`predicted location from an output of the neural network.
`BRIEF DESCRIPTION OF THE DRAWINGS
`0035 FIG. 1 is a schematic diagram of a geolocation
`system in accordance with an illustrative embodiment of the
`present invention;
`0.036
`FIG. 2 is a graph illustrating an indoor Power
`Delay Profile (PDP) illustrating the parameters of a channel
`impulse response including mean excess delay t, rms delay
`spreadt, and maximum excess delay spreadt,
`(10 dB);
`0037 FIG. 3 is a schematic diagram of a neural network
`in accordance with an illustrative embodiment of the present
`invention;
`0038 FIG. 4 is a schematic diagram of a system for
`gathering a training data set in accordance with an illustra
`tive embodiment of the present invention;
`0039 FIG. 5 provides location errors in X, Y and Euclid
`ean distance (D) in metres with inputs corresponding to a
`training set of data;
`0040 FIG. 6 provides cumulative distribution functions
`(CDFs) of location errors in X, Y and Euclidean distance (D)
`in metres of the training set of data of FIG. 5:
`0041 FIG. 7 provides location errors in X, Y and Euclid
`ean distance (D) in metres with inputs corresponding to an
`untrained set of data;
`
`FIG. 8 provides CDFs of location errors in X, Y
`0.042
`and Euclidean distance (D) in metres of the untrained set of
`data of FIG. 7; and
`0.043
`FIG. 9 provides a comparison of CDFs of location
`errors in Euclidean distance (D) in metres with inputs
`corresponding to the untrained set of data and three alter
`native positioning algorithms (Euclidean metric, Box-Cox
`metric and artificial neural network).
`
`DETAILED DESCRIPTION OF THE
`ILLUSTRATIVE EMBODIMENTS
`0044) Referring now to FIG. 1, a geolocation system,
`generally referred to using the reference numeral 10, in
`accordance with an illustrative embodiment of the present
`invention will now be described. The geolocation system 10
`consists of at least one mobile transmitter as in 12 located in
`a Zone of interest 14. The Zone of interest 14 is illustratively
`an underground gallery of a mineshaft comprised of a series
`of interconnected tunnels (not shown) and within which the
`mobile transmitters 12 are free to move, although other
`environments, such as hospitals, shopping malls, campuses
`and the like, could also provide suitable Zones of interest.
`0045. The mobile transmitters 12 broadcast channel
`Sounding signals generated by a radio frequency (RF) Syn
`thesizer 16 which are transmitted via an antenna 18 and a
`wireless RF channel 20 to a fixed receiver 22. The fixed
`receiver 22 comprises an antenna 24, a network analyser 26
`for deriving the complex impulse response of the channel 20
`from the received channel Sounding signals and Subse
`quently generating fingerprint information 28, illustratively
`the 7 parameters as discussed herein below, from the com
`plex impulse response, an artificial neural network 30 for
`determining the mobile transmitter's 12 location coordinates
`32 based on the fingerprint information 28, and a display
`device 34 comprising, for example, a digital rendering 36 of
`the Zone of interest on which representative icons 38 of the
`mobile transmitter's 12 location are Superimposed.
`0046 Illustratively, the frequency domain channel
`Sounding has been taken advantage of as a basis for deriving
`the complex impulse response, and thus the fingerprint
`information 28, of the channel 20. In frequency domain
`channel sounding, the RF synthesizer 16 of the mobile
`transmitter 12 is controlled to emit discrete frequencies at a
`known power which make up the band of frequencies of the
`channel 20. The analyser 26 monitors these channel sound
`ing signals and derives the fingerprint information 28 there
`from. Of note, however, is that frequency domain channel
`Sounding requires both the transmitter and receiver to be
`under common control, for example by a vector network
`analyser (not shown). The vector network analyser transmits
`a known signal level via a known frequency via a first port
`and monitors the received signal level at a second port. The
`signal levels allow the analyzer to determine the complex
`frequency response of the channel over the measured fre
`quency range. This is, of course, generally impractical for
`implementation in an actual mobile system, but as will be
`seen below provides a useful basis for collecting training
`data sets and for testing purposes. In an actual implemen
`tation other channel Sounding techniques, for example
`Direct RF Pulse (UWB) channel sounding (where a pulse
`having a width=2/the channel bandwidth is transmitted
`repeatedly at intervals greater than the maximum delay of
`
`Page 13 of 19
`
`

`

`US 2007/0010956 A1
`
`Jan. 11, 2007
`
`the multipath signal, typically about 500 ns for an indoor
`signal), Spread Spectrum Sliding Correlator channel Sound
`ing or a modified WiFi system could be used.
`0047 A quasi-static mobile radio channel may be char
`acterized by its impulse response, i.e. the signal one would
`receive if the transmitted signal was a single impulse (delta
`pulse or Dirac's delta function) with infinitesimal temporal
`extension and unlimited energy. Given multipath propaga
`tion the receiver detects a sequence of these pulses. Their
`amplitude depends on two parameters:
`0048 the length of the propagation path (due to wave
`attenuation in free space the signals will become
`weaker with propagation length and time); and
`0049 the manner in which the multipath components
`interfere at the receiver (depending on the path length
`and the frequency of the signal, the multipath signals
`interfere either constructively or destructively due to
`differing phase values).
`0050 Consequently, the wireless channel may be mod
`elled as a linear time invariant filter with a varying impulse
`response where the variation is due to the transmitters and
`receiver's positions in space. The filtering nature of the
`channel is caused by the combination of amplitudes and
`delays of the multiple arriving signals at the receiver, which
`gives rise fluctuations in signal strength, thereby inducing
`Small scale fading, signal distortion, or both. As a result, the
`impulse response may be used to characterize the channel
`between a given transmitter and receiver pair. As the loca
`tion of the receiver is fixed, and assuming the presence of
`reflecting objects and scatters which are giving rise to the
`multipath nature of the received signal remain constant, the
`impulse response varies only with the position of the trans
`mitter, with the impulse response for transmitters at different
`locations being unique. Therefore, by associating given
`impulse responses with particular position coordinates, a
`given impulse response (or filter characteristic) may be used
`to provide an indication of the location of the transmitter.
`0051. As is known in the art, in order to simplify the
`extraction of the impulse response from a signal received at
`the receiver, it is useful to divide the multipath delay axis t
`of the impulse response into equal time delay segments
`called “excess delay bins', where each bin has a time delay
`width At equal to t-T, where to-0 (known as the Discrete
`Time Impulse Response Model). Any number of multipath
`signals received within the i' bin are represented by a single
`resolvable multipath component having delay t. To each
`multipath component an amplitude and phase value may
`also be assigned. The chosen bin size must be small enough
`to provide adequate resolution, and a value of At Such that
`the bandwidth=%At has proven adequate. Additionally, the
`number of bins must be chosen such that the probability that
`a multipath component does not fall within one of the bins
`is negligible. For example, for a wide band signal of 100
`MHz bandwidth, as in indoor environments the maximum
`delay very rarely exceeds 500 ns and the probability of
`receiving longer delayed components negligible, a bin size
`At of 5 nanoseconds with 100 bins would provide adequate
`resolution and maximum delay.
`0052) The excess delay T, is the relative delay of the i'
`multipath component as compared to the first arriving com
`ponent to. Referring to FIG. 2, in order to quantify different
`
`multipath channels, time dispersion parameters such as the
`mean excess delay T, the rms delay spread t,
`and the
`excess delay spreadt,
`are derived from the Power Delay
`Profile (PDP) P(t) of the transmitted signal. If the transmit
`ted signal is able to resolve the multipaths, then the received
`power is simply the sum of the powers in each multipath
`component T, above a predetermined multipath noise floor.
`The powers of each multipath component can be derived
`from the received amplitude, and as a result, the PDP is
`readily derived from these amplitudes.
`0053. The mean excess delay t, is the first moment of
`P(t), the rms delay spread t,
`is the square root of the
`second central moment of P(t), while the maximum excess
`delay T,
`is determined as the time delay from to during
`which the energy of the received signal falls a predetermined
`amount (in dB) below the maximum. Additionally, the
`number of multipath components N is determined, as well as
`the total received power P, the power of the first path P and
`the delay of the first path t. The parameters T, T,
`and
`T characterize the time spread nature of the channel and the
`parameters P and T provide information vis-á-vis line of
`sight (LOS) and non-line of sight (NLOS) situations. Col
`lectively these parameters are used to quantify the impulse
`response of the channel and, referring back to FIG. 1, make
`up the fingerprint information 28 which is relayed from the
`analyzer 26 to the ANN 30.
`0054 The pattern matching algorithm to be performed by
`the geolocation system and method can be characterised as
`a function approximation problem consisting of a non-linear
`mapping from a set of input variables, illustratively t,
`t,
`T,
`N. P. P. and t, onto output variables representing the
`location of the mobile transmitter 12 in space. Illustratively,
`the location is Cartesian in two dimensions (x, y), although
`providing a location in three dimensions or other types of
`coordinates (polar, latitude and longitude, etc.) would also
`be possible. In order to approximate the non-linear map
`pings to an arbitrary degree of precision, the ANN 30 is
`illustratively a feed forward neural network of the Multi
`Layer Perceptron (MLP) type, although other kinds of
`networks, such as the Radial Basis Function (RBF) type,
`may also be implemented. As will be seen below, a learning
`algorithm is associated with the ANN which trains the
`network by adjusting the internal weights and biases of the
`neural network based on minimisation of an error function.
`0.055
`Referring to FIG. 3, the ANN 30 is comprised of a
`plurality of neurons as in 40 in one or more hidden layers.
`A weight and bias are associated with each neuron 40.
`Neural networks offer a framework for representing non
`linear mappings from several input variables to several
`output variables, where the form of the mapping is governed
`by a number of adjustable parameters. The process for
`determining the values for these parameters on the basis of
`a data set is called learning or training. As a result, this data
`set is typically referred to as the training set.
`0056. The impulse response quantization parameters as
`in T. T. ... t.
`N. P. P., and t are fed into the ANN 30
`via a series of input neurons as in 42 with the coordinates
`(x,y) Subsequently appearing at the output neurons 44, 46.
`0057. As stated above, both Multi Layer Perceptron
`(MLP) and Radial Basis Function (RBF) type neural net
`works were examined. Both of these networks can approxi
`mate any non-linear mapping to an arbitrary degree of
`
`is
`
`lax
`
`Page 14 of 19
`
`

`

`US 2007/0010956 A1
`
`Jan. 11, 2007
`
`precision provided the network is of the correct complexity.
`A specific learning algorithm is associated for each of these
`two networks, and has the role of adjusting the internal
`weights and biases of the network based on the minimization
`of an error function.
`0.058. The MLP network provides global access to 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 providing generalisation in regions where no
`training data was available. RBF networks, on the other
`hand, have access to a 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 typically easier, and the learning is faster, as
`compared with a MLP network.
`0059 Both a generalised regression neural network
`(GRNN), which is a RBF type network with a slightly
`different output layer, and a MLP type network have been
`tested for the illustrative embodiment of the present inven
`tion. The MLP network showed a higher location error,
`compared to the GRNN, during the learning of the training
`set. However, it showed a lower location error during the
`generalisation phase of the network. Since the generalisation
`property of the system was of greater importance in the
`particular illustrative embodiment, the MLP type network
`has been chosen as the pattern-matching algorithm for the
`illustrative embodiment of the present invention.
`0060 Development of the ANN 30 for use in the illus
`trative embodiment of the present invention consisted of two
`phases, a Supervised learning phase and a real time func
`tional phase. During the learning phase, the ANN was
`trained to form a set of fingerprints as a function of user's
`location and acted as a function approximator (non-linear
`regression). A training set of fingerprints, comprising T,
`T.
`T.,
`N. P. P. and t were applied to the input neurons
`42 of the ANN 30 and the output neurons 44, 46 compared
`to the measured location.
`0061 The goal of ANN training is not to learn an exact
`representation of the training data but rather to build a model
`of the process which generated the training data. This is
`important if the ANN is to exhibit good generalisation, i.e.
`the ability to accurately predict outputs for new inputs. In
`th