Hanaa A El-Natour

Anne-Christine Escher

Christophe Macabiau

Impact of Multipath and Cross-Correlation on GPS acquisition in Indoor Environments

Keywords: receivers, multicarrier communications …), satellite onboard processing (filter banks, DBFN …) and navigation systems

and from the ENSEEIHT in

I. INTRODUCTION

In the past, in order for GPS to work accurately, the presence of an unobstructed Line-Of-Sight (LOS) signal was necessary. Weak signals were not suitable for use because they may have large associated noise and other errors. The expansion of GPS to Location-Based Services and other navigation applications all over the world, such as the E-911 and the E-112 mandates in the United States and Europe respectively, is changing the paradigm. Consequently a dramatic increase in the number of required indoor wireless systems is expected. These rising indoor localization requirements pose a particularly difficult challenge for system designers, since an indoor channel is highly complicated and path loss is very severe most of the time.

An indoor radio communication channel is governed by multiple factors like multipath propagation, shadowing effects, surrounding objects velocity, mobile relative velocity, and signal interference (either with other GPS signals or with other radio signals). The multipath consists of different replicas of the original signal caused by reflections, diffractions or diffusions generated when the signal encounters an obstacle. These replicas are attenuated versions of the original signal; they have different phases, and different arrival times. At the receiver they combine and produce a distorted version of the transmitted signal. The shadowing effect mainly attenuates the direct signal. This attenuation is very severe when the signal must pass through concrete walls, or dense foliage. On the other hand, the mobile relative velocity with respect to the emitting satellite makes the channel variable over time. Furthermore, signal interference with other radio signals and cross-correlation with other GPS signals also causes a signal distortion.

In order to design an indoor radio communication system with optimal performance, there must be a subtle study of the channel characteristics.

In this paper we mainly investigate the impact of multipath and cross-correlation on GPS L1 signal acquisition in a simulated typical indoor environment. For that purpose we have defined a time-varying mobile radio channel model, based on an indoor channel model realized within an ESA (European Space Agency) project entitled "Navigation signal measurement campaign for critical environments" and presented at the ION- GPS-2003[START_REF] Pérez-Fontán | Measurements and Modeling of the Satellite-to-Indoor Channel for Galileo[END_REF]. In this project, the ESA investigated a statistical non-time-varying model which provides the PDF (Probability Density Function) for each of the four parameters used to characterize the channel: the number of paths, each path's amplitude, delay, and phase. These parameters were set to be constant over time. In our model we generate an original signal which stands for a direct LOS signal, and many reflected and diffracted replicas of this signal. The difference between this model and that of the ESA is that each path delay and phase are assumed to be timevarying. For the sake of simplicity, the relative amplitudes and the number of paths are assumed to be constant during the acquisition period. These two parameters are chosen at the beginning of the simulation according to their respective distributions presented in the ESA paper.

This model is used to study the effect of either multipath or GPS signals cross-correlation on the acquisition phase of the signal processing in the receiver.

The paper is organized as follows: first we describe the indoor channel model used, next, we present the acquisition algorithm developed under Matlab ® . The two subsequent parts show simulation results. The first shows the impact of multipath on the acquisition performance, while the second deals with interference induced by another GPS signal. Finally, a conclusion is drawn from these results.

II. THE INDOOR CHANNEL MODEL

The GPS signal studied is considered as the output of an indoor time-varying channel which has the following transfer function:

( ) ∑ = ⋅ - ⋅ = N i t j i i i e t t t h 1 ) ( ) ( ) ( θ τ δ α Eq 1
Where N is the number of rays that reach the receiver. This set of rays may either contain a direct LOS or not. N is constant over the duration of the simulation, and is chosen according to the distribution of the number of rays reaching the receiver given in [F. [START_REF] Pérez-Fontán | Measurements and Modeling of the Satellite-to-Indoor Channel for Galileo[END_REF],

i α is the multipath replicas relative amplitude with respect to the amplitude of the direct ray. This parameter is considered to be constant over the duration of the simulation, and is also chosen according to the distribution of the rays powers given in [F. [START_REF] Pérez-Fontán | Measurements and Modeling of the Satellite-to-Indoor Channel for Galileo[END_REF],

i τ is the delay experienced by the direct LOS ray and the reflected rays respectively. This delay is essentially due to the signal propagation from the satellite to the receiver,

i i i t f t 0 0 ) ( 2 ) ( θ τ π θ - =
is the phase distortion introduced by the channel.

i 0 θ is a random initial phase uniformly distributed over [ ] π 2 ; 0 .
Consequently, the GPS signal that is supposed to reach the receiver has the following expression:

( ) ( ) ( ) ( ) ( ) ( ) ∑ = - ⋅ - ⋅ - ⋅ = N i i i i i t t f t t d t t c t s 1 0 2 cos ) ( θ π τ τ α With 1 L the Coarse/Acquisition (C/A) GPS code carrier frequency, MHz L 42 . 1575 1 =
, c the C/A code, and d the data bits.

When processing the GPS signal we assume that the carrier frequency was already shifted to an Intermediate Frequency (IF) of 1.25 MHz.

The studied signal is then:

( ) ( ) ( ) ( ) ( ) ( ) ∑ = - ⋅ - ⋅ - ⋅ = N i i I i i i t t f t t d t t c t s 1 2 cos ) ( θ π τ τ α Eq 2
Notice that the channel phase distortion only affects the carrier phase.

The delay i τ is assumed to have linear variations with respect to time. Its value depends on two types of multipath replicas: reflected replicas and diffracted ones. These two cases are illustrated in Fig 1. The receiver is supposed to be at 1m above the ground level, i.e. in the hand of a user. We also suppose that it moves horizontally, and its distance with respect to obstacles varies between 0 and 5m approximately.

The delay experienced by the direct LOS ray is: [Kaplan, 1996], where s v is the satellite linear velocity, e r is the earth's radius, s r is the distance between the earth's centre and the satellite, γ is the satellite elevation angle. d v is also considered constant over the duration of the simulation.

The delays experienced by the multipath replicas are defined with respect to that of the direct LOS. In the case of reflected rays, this is done using a classical model of reflection. The path followed by the reflected ray i differs from that of the direct ray ( 0

( ) γ θ - ⋅ + = i r i i t v h h sin 0
, where i h 0 is the initial distance between the receiver and the obstacle; it takes a random value between [ ] m m 5 ; 0 , r v is the receiver velocity.

Hence, the delay experienced by a reflected ray is expressed as:

i i d i c h c t v c d θ τ sin 2 0 + + = Eq 4
Where c is the light velocity.

For a refracted ray, the delay is given by the ratio of the length of the total path followed by the ray divided to the velocity of light. In

( ) ( ) ( ) ( ) c d c d t v d d t v d i i i d i d i + ⋅ ⋅ + ⋅ - + + = ' 0 2 2 0 cos 2 θ τ Eq 5 Where ( ) ( ) ( ) ( ) ( ) ' 0 2 2 0 cos 2 i r i r i i t v d t v d d θ γ - ⋅ ⋅ ⋅ - + = ,
and i d 0 is a random initial distance that lies in [ ] m m 5 ; 0 also.

While there are much more refracted rays than reflected rays, the former are much more attenuated. This is why 80% of the multipath replicas generated will be considered as reflected rays (the less attenuated ones), and the remaining rays are considered to be refracted.

Each generated signal has a duration of 1s.

All of the results presented in this paper deal with a static user since we found that the results obtained with a dynamic user (with a velocity of 2m/s) were similar for the signal duration of 1s. This could indeed be explained by the fact that the receiver velocity is very negligible with respect to that of the satellite. After generating the signal, we add to it white noise with a known power. The resulting value of the signal power to noise density ratio will be referred to by the input 0 / N C . Then we quantify it using a 2-bits quantification process. An attenuation of approximately 1dB is further induced due to this quantification [START_REF] Spilker | Global Positioning System: Theory and Applications Volume I[END_REF]. Finally, we acquire the signal. Throughout the acquisition process we estimate the carrier Doppler frequency, the code delay and the 0 / N C ratio. The result is illustrated by a correlation matrix as it will be explained in the next section.

III. THE ACQUISITION ALGORITHM APPLIED

Acquisition is a coarse synchronization process giving estimates of the PRN code offset and the carrier Doppler. The code offset is due to the signal propagation. The carrier Doppler is the result of the satellites and the receiver dynamics, and of the frequency drift of the receiver local oscillator. The estimated PRN code offset and carrier Doppler can be used to initialize the tracking loops which perform a finer search over the two parameters if the 0 / N C is sufficiently high. We assume the PRN code that must be used for despreading to be already known.

This GPS signal two-dimensional search process is defined in an uncertainty region in which code and carrier phase are aligned with the received signal. The correct alignment is identified by the measurement of the output power of the correlators (Fig 2). The result of this two dimensional search is an estimate of the code Offset to within one half chip, and of the carrier Doppler to within half the Doppler search bin size (several hundred Hz).

The acquisition scheme applied to the quantified GPS signal is based on a Fast Fourier Transform (FFT) algorithm as illustrated in the following block diagram: Averaging the inphase and the quadrature components respectively, in the correlator, before squaring them is called coherent integration. The coherent integration is realized over ms Tp of signal. This reduces the impact of noise on the signal. The whole process can be repeated many times in order to further reduce the impact of noise. This is called non-coherent integration. We define M as the number of non-coherent integrations. The dwell time is then defined as the product of Tp and M. It gives the total duration of the signal being processed in the acquisition phase.

The output signal can be expressed as [START_REF] Spilker | Global Positioning System: Theory and Applications Volume I[END_REF]:

( ) ( ) ( ) ∑ = + = M k k Q k I T 1 2 2 Eq 6 With ( ) ( ) ) ( ) ( cos ) ( ) sin( ) ( 2 ) ( k n k k R T f T f k d A k I I c c p d p d f + ⋅ ⋅ ∆ ∆ ⋅ ⋅ = θ τ ε ε π π ( ) ( ) ) ( ) ( sin ) ( ) sin( ). ( 2 ) ( k n k k R T f T f k d A k Q Q c c p d p d f + ⋅ ⋅ ∆ ∆ ⋅ = θ τ ε ε π π Where , d f ∆ ) (k τ ε and ) (k θ ε
are the Doppler frequency, the code delay and the phase error respectively. The impact of the phase error on the useful signal is eliminated by squaring the two signal components and adding them.

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ] ∑ ∑ = =         + + +       ∆ ∆ =                         + ∆ ∆ +         + ∆ ∆ = M k Q I P P M k Q P P I P P N k n k n T f T f R A T k n T f T f R k d A k n T f T f R k d A T 1 2 2 2 2 2 1 2 2 sin 4 sin sin 2 cos sin 2 π π ε ε π π ε ε π π ε τ θ τ θ τ Eq 7 With ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) k n T f T f R k d A k n T f T f R k d A N Q P P I P P ⋅ ⋅ ∆ ∆ ⋅ ⋅ ⋅ + ⋅ ⋅ ∆ ∆ ⋅ ⋅ ⋅ = θ τ θ τ ε π π ε ε π π ε sin sin cos sin
The previous expression shows that the final signal contains a significant term ( ) ( )

2 2 2 sin 4       ∆ ∆ P P fT fT R A π π ε τ
and two other noise terms that will eventually cause signal attenuation. One of these terms

( ) ( ) 2 2 k n k n Q I + is an
additive noise due to the signal propagation from the satellite to the user receiver, and the other noise term is due to the code delay and the carrier Doppler estimation errors. The next step is to find the right peak of the detection matrix. The one which is likely to correspond to the right Doppler frequency and code delay of the GPS signal studied. This is done by applying a hypothesis test T, called the detection criteria. In the presence of noise, a threshold is set and compared to the value of the signal at the output of the receiver (T). Any cell envelope that is below the threshold is detected as noise, and any cell envelope that is at or above the threshold is detected as the presence of the signal. T is maximum when the replica and the reference signal are aligned.

The frequency bins are a function of the coherent integration time. In our case they are equal to:

p T f 2 1 = ∆ .
The advantage of the FFT algorithm with respect to the conventional sequential time domain technique is that it calculates, for a selected Doppler, the correlation for an entire delay range dimension of duration Tp in a single step. We assume in the following that we need to search all code delays over the whole period of the C/A code, thus using an FFT algorithm reduces the mean acquisition time.

Note that increasing the coherent integration time Tp during the acquisition process, improves the SNR ratio, because the correlator output noise power,

p p n T N f N 4 / 4 / 0 0 2 = =
σ is inversely proportional to this time, and will be lowered. However, this involves more calculations and hence, is time consuming. The time consumption does not increase linearly with Tp . In fact, a higher Tp implies simultaneously an increased number of data points to be treated, and an increased number of frequency cells to be searched since the acceptable frequency uncertainty f ∆ is inversely proportional to Tp resulting in more frequency cells to be searched.

Another limiting factor for Tp is an eventual data bit transition, knowing that a data bit has a duration of 20ms. This problem could be avoided by setting Tp to 1ms, and increasing the number of non-coherent integrations M. But, as a result, the noise is squared. Generally, the noise compensation obtained when increasing Tp is better than that obtained when increasing M. In summary, a compromise must be found.

As a conclusion, the detection of the signal is a statistical process based on a hypothesis test:

Hypothesis 0 H : The signal is not present, and the considered cell contains only noise.

Hypothesis 1 H : The considered cell contains noise with signal present.

In the case of 1 H , when the right Doppler frequency and code delay are found, the resulting attenuation is supposed to be negligible, and the value of the peak detected is supposed to be:

b m A + ≈ 4 max 2
, where b m is the mean noise level. Thus the power of the useful signal is

( ) b m A C - ⋅ = = max 2 2 2 .
In other words, once a peak is found at the end of the acquisition process, the signal power can be estimated.

During our simulations, to insure that the Doppler and the code delay found at the end of the acquisition process are accurate, these two parameters are calculated a priori for each signal.

The Doppler frequency can be deduced from the carrier instantaneous phase which is given by:

i I i f t f t τ π π φ 0 2 2 ) ( - =
Accordingly, the instantaneous frequency is:

di I i I i inst f f dt d f f dt t d f - = ⋅ - = ⋅ = τ φ π 0 ) ( 2 1 With d f the Doppler frequency.
This yields:

      ⋅ - ⋅ + ⋅ = i i r d di c elev v c v f f θ θ sin ) sin( 2 0 For a static receiver, i.e. 0 = r v
m/s, the Doppler frequency of the direct LOS is given by:

c v f f d di ⋅ = 0 Eq 8
Next the simulation results will be presented. Note that the global acquisition time was not studied. By global acquisition time we mean the time needed to load the signal and then processing it.

IV. IMPACT OF MULTIPATH ON ACQUISITION PERFORMANCE

In order to study the impact of multipath on the acquisition performance, we will compare results obtained with a signal without multipath (i.e. just the LOS signal), with a composite signal containing a LOS and different multipath replicas, and with a composite signal without a LOS (Non-LOS). Two GPS signals are tested: that of satellite number 1 with a constant elevation angle of 30°, and that of satellite number 11 with a constant elevation angle of 45°. The multipath replicas have different relative amplitudes, phases and angle of arrivals. These parameters are not the same for the two signals.

The distances between the receiver and the obstacles are not neither the same for the two signals. However, all of these parameters will be the same in the three cases described above, namely the LOS only, the LOS with multipath replicas and the Non-LOS case for a specific GPS signal.

The Doppler frequency and the code delay for the GPS signal of satellite number 1 are calculated by applying Eq 3 and Eq 8 which gives Hz For each of these composite signals we will try to acquire the original signal using the acquisition algorithm described in section III. We first start by setting Tp to 1ms in order to reduce the time consumption. Then we increase the value of M up to 1000 until we got the right values of Doppler frequency and the code delay. If a noncoherent integration over 1000 ms of signal, i.e. 1 second, was not sufficient we increase the value of Tp as long as the computation facilities of the processor allow doing it. We notice that the estimated 0 / N C in these two cases is very close to the real one with an estimation error that is below 0.5dBHz, and the values of the Doppler and the code delay are accurate. Hence multipath replicas did not disturb the acquisition process. ratio that could be detected is rather 40dBHz. In other words, if a direct LOS signal had a 0 / N C ratio lower than 40dBHz and could not reach the receiver (because of shadowing, for instance), the multipath replicas generated would not allow for finding the desired signal. In this case we found that the multipath replicas were severely attenuated with respect to the LOS. We repeated the previous simulations with another signal, and we got similar results as depicted in As a conclusion, the multipath replicas have minor impact on the acquisition performance, when a direct LOS is present. In addition, even if a LOS is not available, the multipath replicas could be explored, but they are much attenuated with respect to the LOS signal. In all cases multipath replicas did not induce errors on the signal acquisition. On the other hand, in Non-LOS cases, the minimum C/N0 of the direct (masked) signal for successful acquisition depended on the indoor environment (25-40 dBHz).

V. IMPACT OF CROSS-ORRELATION ON ACQUISITION PERFORMANCE

After having studied the effect of multipath on signal fading in indoor environments, the next step will be to study the impact of interference between different satellite signals. In fact there are situations where a strong path may interfere with another weak path. In this case, acquiring the weak signal is very difficult, and may lead to a cross-correlation peak. This cross-correlation peak is generally expected approximately -23.9dBHz apart from the autocorrelation peak [Proakis, 1995]. To illustrate this situation, we used the same model that was developed for the multipath simulation As we can see in this figure, the peak corresponds to a null Doppler which is the Doppler of satellite 1, the stronger signal. In addition, this peak is found at approximately dBHz 27 less than the initial 0 / N C applied to the signal of this satellite, namely 50dBHz. By adding the attenuation due to the quantification, the estimated 0 / N C corresponding to this peak will be very close to the theoretical value of approximately dBHz 25 -. This leads us to assume that the peak is very likely to be a cross-correlation one.

In order to be sure that it is a cross-correlation peak, we acquired the signal of satellite 1 alone without noise, but used the C/A code of satellite 11 in this acquisition. The , since we used a sampling frequency of 5MHz. This gives a sampling period of 0.2 s µ , which corresponds to 0.2chip.

Thus the difference we observed between the two figures corresponds to one code delay bin, with a duration of e T . But in general, the code delay uncertainty needed at the end of the acquisition process is of 0.5 chip. Thus the difference observed previously is largely within this limit. However, in general, the cross-correlation matrix is not supposed to have peaks which are stronger than others. But this is not the case in Fig 9 . In other words, we were not supposed to have many strong peaks in the Doppler bin of satellite 1. This may be due to the effect of the code Doppler drift which may cancel some crosscorrelation peaks.

Fig 10 illustrates another case where a cross-correlation peak is detected. We also verified that the detected peak is a cross-correlation one by the same way as before. In conclusion, the main impact of GPS cross-correlation on the acquisition performance is a probable crosscorrelation peak, which leads to inaccurate values of the Doppler frequency and the code delay, and hence to inaccuracies in the user position estimation.

Furthermore, the peak detected by the acquisition algorithm is likely to be a false alarm one. Thus it is generally difficult to verify that a peak is a crosscorrelation one or not, especially when dealing with real GPS data.

VI. CONCLUSION

In this paper we investigated the impact of Multipath replicas and cross-correlation on the GPS signals acquisition. Next, we investigated the impact of multipath by testing the acquisition of these generated signals for a total dwell time of 1s, with Tp=1 or 2ms, and M=1000 or 500. The acquisition is based on a classic FFT algorithm. We focused our work on the capacity of detection of a correlation peak over the detection threshold, and we did not analyze the total time needed for acquisition. The multipath replicas delays in this model are very negligible with respect to those of the direct LOS, thus if we detect a multipath replica it has approximately the same delay and Doppler as that of the LOS. The results show that in the LOS cases, multipath replicas have minor effects and do not disturb the signal acquisition since they much attenuated with respect to the direct LOS. In the Non-LOS cases, even though the multipath replicas are much attenuated, they could be used to find the initial signal.

Studying the cross-correlation, we found that according to this model, a cross-correlation disturbs the acquisition performance. But no subtle conclusions could be drowned yet concerning the impact of cross-correlation.

Our future works include a deeper analysis of the signature of cross-correlation effects. This signature will be used to try and develop different mitigation techniques for indoor acquisition.

Fig 1

 1 Fig 1 reflected and diffracted rays of a GPS signal. Reflected rays are in dotted lines and diffracted rays are in solid lines. The direct LOS is in dashed line.

  Fig 1, Al-Kashi law gives:

  Fig 2: Acquisition process block diagram

  For the GPS signal of satellite number 11, the Doppler frequency and the code delay are expected to be at Hz 4075 and 608.2758 chips respectively.

  by adding to the estimated value the attenuation due to quantification. As it is illustrated in Fig 3 below, for a LOS signal without multipath

Fig 3 :

 3 Fig 3: LOS without multipath replicas; true values: Doppler frequency -4666Hz, code delay 608.2758 chips, initial 0 / N C 21dBHz; estimated values: Doppler frequency -4750Hz, code delay 608.2758 chips, 0 / N C 19.8549dBHz

Fig 4 :

 4 Fig 4: LOS signal with multipath replicas; true values: Doppler frequency -4666Hz, code delay 608.2758 chips, initial 0 / N C 21dBHz; estimated values: Doppler frequency -4750Hz, code delay 608.2758 chips,

Fig 5 :

 5 Fig 5: Non-LOS signal, multipath replicas only; true values: Doppler frequency -4666Hz, code delay 608.2758 chips, initial 0 / N C 40dBHz (

  Fig 6 and Fig 7

Fig 6 :

 6 Fig 6: LOS signal with multipath replicas; true values: Doppler frequency -4075Hz, code delay 608.2758 chips, initial 0 / N C 22dBHz; estimated values: Doppler frequency -4000Hz, code delay 608.2758 chips,

Fig 7 :

 7 Fig 7: Non-LOS signal, multipath replicas only; true values: Doppler frequency -4075Hz, code delay 608.2758 chips, initial 0 / N C 25dBHz (

  , and extended it to support different satellite signals. We tried two satellite signals interfering with each other, with different powers. We started by simulating two GPS signals (for satellites number 1 and 11) and their multipath versions, setting the 0 / N C ratio to 50dBHz for the first one and 25dBHz for the other one. Note that satellite 1 has a null Doppler, while satellite 11 has a Doppler frequency of Hz 4000 -. We tried to acquire the satellite number 11. The result of acquisition is depicted in Fig 8.

Fig 8 :

 8 Fig 8: Cross-correlation between 2 GPS signals: 1-LOS signal of satellite number 11 with multipath replicas, true Doppler -4075Hz, true delay 608.2758 chips, initial 0 / N C 25dBHz 2-LOS signal of satellite number 1 without multipath replicas, true Doppler 0Hz, true delay 604.035 chips, 0 / N C 50dBHz. The signal acquired is the first one (sat1 11). Estimated values: Doppler frequency 0Hz, code delay 980.2386, 0 / N C 22.7722dBHz

  detected peak has the same (Doppler frequency, code delay) couple as that of Fig 8 (in Fig 9).

Fig 9 :

 9 Fig 9: LOS signal of satellite number 1 without multipath replicas or noise, true Doppler 0Hz, true code delay 608.2758chips, signal acquired with C/A code of satellite number 11. Estimated values: Doppler frequency 0Hz, code delay 980.034 chips, 0 / N C 39.3956dBHz

Fig 10 :

 10 Fig 10: Cross-correlation between 2 GPS signals: 1-Non LOS signal of satellite number 26 (just multipath replicas), true Doppler -4000 Hz, true delay 604.0 chips, initial 0 / N C 25dBHz 2-LOS signal of satellite number 1 with multipath replicas, true Doppler 0Hz, true delay 608.2758 chips, initial 0 / N C 50dBHz. Estimated values: Doppler frequency 0Hz, code delay 109.0518 chips,

Fig 8

 8 Fig 8 and 10 show that the cross-correlation disturbs the acquisition of a specific signal. The weakest signals presented if the previous figures, namely the signals of satellites 1 and 11 with 25 dBHz each, could be acquired without difficulties if the interfering signals were not present.

First

  , we implemented an indoor time varying channel model based on a static indoor model developed by the ESA and presented in 2003. This model was used to generate three types of indoor GPS signals: a direct LOS signal, a composite LOS signal with multipath replicas, and a Non-LOS signal which contains only multipath replicas. The cross-correlation effect was studied by adding two of these signals together.

Presented at ION NTM 2005, San Diego

ACKNOWLEDGMENTS

We would like to thank Dr. Bernard SOUNY from the ENAC, Toulouse, France, and Ing. Stephane CORRAZZA from Alcatel Space, Toulouse, France, for their valuable remarks and suggestions.


Hanaa A El-Natour

Enac / Tesa

Michel Monnerat

ENAC Anne-Christine Escher

ENAC Christophe Macabiau

Marie-Laure Boucheret

Enst Biography

A new algorithm to reduce AGPS acquisition TTFF

Keywords: digital receivers, multicarrier communications …), satellite onboard processing (filter banks, DBFN …) and navigation systems

She is investigating different signal processing techniques for GPS positioning.

I. INTRODUCTION

The expansion of GPS to Location-Based Services and other location and navigation applications gives rise to indoor localization requirements which pose particularly difficult problems, like GPS receiver sensitivity, cross-correlation and multipath issues [Parsons, 1992[START_REF] Miller | Satellite Communications: Mobile and Fixed Services[END_REF], or TTFF.

The GPS receiver sensitivity must be as low as possible in order for the receiver to be able to detect very weak signals like those received in indoor environments (inside buildings) or urban canyons where many obstacles can significantly reduce the received power. Moreover, in these harsh environments, it may happen that an interfering GPS signal coming from another satellite arrives at the user antenna while unaffected by any obstacle. It then causes the appearance of high cross-correlation peaks that may have levels comparable to the useful signal autocorrelation main peak. This can result in a false alarm (detection of a wrong signal) and consequently in an inaccurate location estimate. On the other hand, the obstructed signal may still reach the receiver by multiple reflections for example. In this case, the received signal is called multipath. It is an attenuated and delayed version of the original one. Thus even if it could be acquired, it will also lead to inaccurate location estimate. These crosscorrelation and multipath peaks must not disturb the final solution selected by the receiver.

Finally, the TTFF, which is the time needed for a GPS receiver to find its first location, must be as short as possible so that the client does not "lose patience" while the receiver is trying to compute its location.

All of these issues are somehow related to each other. Indeed, one way to enhance sensitivity is to increase coherent and non coherent correlation duration so that weaker signals can be detected [Van Diggelen, 2001]. But this way, the TTFF also increases; and an increased TTFF is not at all desirable for real time applications as already explained.

As for multipath and cross-correlations, they must not affect the detection of the right autocorrelation peak for weaker signals, hence the right Doppler frequency and code delay. The algorithms needed to perform this discrimination might increase the TTFF or the sensitivity of the receiver.

In this paper we investigate a new algorithm for GPS receivers. It essentially decreases, by means of reduced computing load, the traditional TTFF. It may then provide the ability to increase coherent and/or noncoherent correlation duration in order to increase the sensitivity at comparable or even reduced TTFF. In addition, the implementation of the algorithm induces a rejection of some threatening multipath and crosscorrelation peaks, and hence reduces the probability of wrong detection.

The algorithm consists in adding different code replicas to each other before using them to despread the GPS signal. This means that different satellite signals are despread together instead of being despread each one alone. The output which consists in a sum of autocorrelation and cross-correlation functions leads to as many useful correlation peaks as there are replicas added together. This could easily lead to the detection of false peaks when very weak signals are present. But as it will be explained, the algorithm induces a way to reject crosscorrelations. However, even if the harmful crosscorrelation peaks were rejected, a raise in the noise floor is observed. This results in potential false alarms.

Note that this algorithm is based on the Assisted GPS concept to constrain the search space and to improve its false detection ability. That is, Assistance Data (AD) from the GSM network is used to calculate approximate values of the Doppler frequency and code delay for each satellite, and provides a raw user position within a GSM cell [LaMance, 2002]. Thus the GPS receiver is supposed to receive data from a cellular mobile phone. Consequently, the AD disseminated by the telecommunication channel is used by the receiver in order to improve its sensitivity and to decrease the TTFF. Typically in cold start, the AD set required is composed of:

•

The reference time •

The reference location •

The navigation model (Ephemeris) •

The ionosphere correction

The paper is organized as follows: first we describe the classical GPS acquisition algorithm; next, we present the new proposed algorithm. The subsequent section consists in analyzing the algorithm and presenting its strong points and drawbacks. Finally, in the last part we present results for performance evaluation obtained with this algorithm. In what follows, the new algorithm will be referred to as Sum Of Replicas algorithm (SOR).

II. THE CLASSICAL FFT AGPS ALGORITHM

A standard AGPS FFT acquisition scheme is shown in figure 1:

Fig 1 Classical GPS acquisition scheme

In figure 1 The acquisition process first consists in despreading the useful received signal by correlating it with a local replica. This correlation is achieved using the Fast Fourier Transform (FFT) technique. The process aims at finding each satellite signal code delay and Doppler frequency by detecting the location of the signal maximum energy. Figure 2 shows an example of a classical GPS acquisition algorithm output. In a classical case, all the Doppler/code delay bins must be investigated. In our case however, the acquisition process is carried out in an AGPS context, and thus with an aid for a-priori estimates of the Doppler frequency and the code delay for each satellite signal. Nevertheless, one has to keep in mind that these estimates are affected by uncertainties on the reference position and on the receiver clock offset with respect to GPS time.

The received signal Doppler frequency has mainly three sources: (1) the satellite motion, (2) the receiver motion, and (3) the receiver clock drift with respect to GPS time [START_REF] Kaplan | Understanding GPS: Principles and Applications[END_REF]. The AD estimated Doppler frequency is deduced only from the satellite motion. The estimation error on this Doppler frequency is considered negligible and in the order of a few Hz. However, the two other Doppler components cannot be estimated by the AD and must be searched for. We suppose that these two Doppler components vary between ± 2 KHz.

The reference position is that of the transmitting GSM Base Station. Consequently, the uncertainty on the reference position depends on the considered GSM cell radius. A GSM cell radius varies between approximately 1km for urban areas, and 30km for rural areas. The time uncertainty is of the order of ±2s. This value corresponds to the accuracy of the time transfer through the GSM cellular network.

The uncertainties on the Doppler frequency and the code delay lead to the estimate of a code delay range rather than a code delay value, and the correlation can only be computed for the code delay values within this range. But using the FFT technique to compute correlation all the code delay bins are necessarily explored and this information can only be used as an authentication of the acquisition result.

In the case of a standard algorithm, this acquisition process is sequentially repeated for each satellite in view. A joint search of several satellites would allow a reduction of the time allocated to the acquisition of the different satellites. This is the base of the proposed algorithm presented in the next section.

III. THE SOR ALGORITHM

The general principle is to correlate the incoming signal with the sum of C/A code replicas rather than correlating it with only one replica. This yields to a parallel search for all visible satellites rather than searching for them sequentially. The acquisition process is obviously speeded up. Note that visible satellites PRN are known a priori thanks to the AGPS AD.

The acquisition is realized according to the scheme presented in figure 3:

Fig 3 SOR algorithm principle

The resulting correlation function in each explored Doppler cell is equal to the sum of the correlation function which would have been obtained if satellites were individually correlated. Each satellite PRN code has its own delay, and hence corresponds to one of the acquisition peaks detected in this correlation function. At this stage, the issue is to determine the proper correspondence between satellite PRNs and acquisition peaks. This correspondence is done first by trying to locate each acquisition peak within a code delay window. Indeed assuming that the reference location, the reference time and the navigation model are known thanks to AD, the receiver can compute the differential time of arrival between the satellites. This information can be used to identify the correlation peak pattern. The correspondence is then possible since each code delay window is already assigned to a satellite PRN code as it is shown in figure 5 below.

Fig 5 Satellites identification process using the code delay ranges function (red plot) estimated by the AD. The blue plot corresponds to the acquisition code delay positions

However, this identification process is not possible if for example, two or more satellites have the same or close code delays. Thus a discrimination process should first be undertaken. A classification in groups of the visible satellites according to their respective expected code delay is realized to avoid correlation peak collisions. Such potential collisions are eliminated if the code delay windows of satellites in the same group do not intersect with each other. Else, the satellites cannot be part of the same composite replica as shown in Figure 6.

Fig 6 Collisions between satellites having close code delays

Obviously, the accuracy of the provided code delay computed through AD is tremendously important and the wider the code delay windows, the fewer satellites per group.

Once the satellites are grouped according to their code delays, each group goes through an acquisition process by correlating the incoming signal with the sum of the corresponding replicas. The output is a correlation function similar to that shown in figure 4 with as many peaks as there are satellite signals in the considered group.

We still have the satellites identification issue. In fact, the peak position returned by the function is affected by a time offset. This is due to the receiver clock offset

OK

which causes the peak configuration computed by the grouping function to be shifted. This has no impact on the previous processing (correlating the signal with code replicas, grouping the satellites in order to avoid collisions between their code delays), but has an impact on the identification of the peaks. A solution to this problem is to correlate the code delay windows function and the acquisition peaks positions function (resulting from correlation) defined as:

-

η η

The maximum of the resulting correlation function provides the most likely configuration and in the same time provides the relationship between the peaks and the PRN number (figure 7).

Fig 7 Satellites identification by correlating the ranges function (in red) and the acquisition code delay ranges function (in blue)

In practice, even if the satellites were grouped a priori such that collisions are avoided between their code delays, collisions are still possible. The reason is that the code delays detected by the acquisition process do not have necessarily the same pattern as that of the ranges estimated by the AD. This is due to possible crosscorrelation peaks which may mask those of weak signals or even multipath peaks. These peaks have random delays. In this case, some of the output correlation function peaks are wrong. However, the peaks which are not included in any code delay range are not accounted for since code delays are searched for only within the precalculated ranges. Whereas if two peaks are included in the same code delay range, one of them obviously does not correspond to the proper correlation peak, i.e., it does not correspond to a PRN code delay. In such cases, the lower peak is eliminated and only the higher one is taken into consideration. This is also applied if more than two peaks coincide within the same code delay range.

Obviously, the more satellites per group, the greater the complexity reduction with respect to a standard algorithm. But having too many satellites per group may affect the receiver sensitivity as discussed in the next section.

IV. ADVANTAGES AND DRAWBACKS OF THIS ALGORITHM

The SOR algorithm reduces the TTFF by reducing the complexity in comparison to a standard algorithm, since it allows the acquisition of more than one satellite at once, or in other words, it allows for a parallel processing of the satellites. This reduction depends on the number of satellites processed together. Thus the more we have satellites per group, the more the complexity is reduced and the lower is the TTFF.

Conversely, having more satellites per group induces a reduction in sensitivity, since the global noise level is increased. To illustrate this, let us consider a composite GPS signal comprising the signals coming from N satellites. Searching for one of the satellite signals, namely the first, with a standard algorithm yields an autocorrelation function added to N-1 cross-correlation functions. The additive noise is correlated is correlated with only code.

Using the SOR algorithm, suppose that the first group of satellites contains 3. Accordingly, the signal will be correlated with the sum of 3 Doppler compensated replicas. The result is the sum of 3 autocorrelation functions and 6+3*(N-3) cross-correlation functions. In this case, the noise is the correlated with the sum of the codes. Therefore, in this case we have much more crosscorrelation peaks and more autocorrelation peaks, and the noise level is increased.

PRN 1 PRN 3 PRN 2 Time (chips) PRN 1 PRN 3 PRN 2

Time (chips)

In conclusion, compared to the standard algorithm, the SOR algorithm introduces more crosscorrelation peaks which may lead to more false alarms. But the solution to this problem is inherent to the implementation of the SOR algorithm itself. Indeed, the correlation peaks are searched for within predetermined code delay windows. Thus all cross-correlation peaks which occur outside the boundaries of these windows are eliminated. Hence, the smaller the width of the ranges, the lower is the probability of false alarm. Furthermore, we notice an increase of the global noise level due to the correlation of the noise with many C/A codes. This increase must be characterized. Note that the C/A codes are summed together after Doppler compensation, thus they have different delays and Doppler shifts. All of these parameters must be considered in order to have a subtle study of the variation of the noise level when more than one satellite are acquired together.

At this stage, two solutions may be adopted to enhance sensitivity: -The first solution is to set an upper level for the number of satellites per group, such that the loss in C/N 0 is limited to a predetermined value.

-The second solution consists in realizing integrations on signal sections free from bits transitions which may enhance the C/N 0 by 2 or 3dBs approximately depending on the bit transition position within a 20ms section of the signal. The issue is then to pregroup the satellites according to their respective bit transitions, once again thanks to the AD. Next, the correlations are computed with the signal being shifted by the value of each group proper bit transition (in ms).

The next section presents performance evaluation of the algorithm based on the TTFF and the sensitivity parameters.

V. PERFORMANCE EVALUATION OF THE SUM OF REPLICAS ALGORITHM

Prior to presenting performance evaluation results, an example of output of this algorithm is first shown below. It only aims at illustrating the algorithm outputs, performance tests will be shown later. The test signal used is a simulated one using a Spirent STR4500 with 10 visible satellites with characteristics given in Table 1 and2 The 10 satellites in view are divided in 2 groups, with the first group having 7 satellites and the second having 3 satellites. This grouping is realized after computing the estimates of each satellite code delay using the AD. The ranges corresponding to each code delay are then calculated. Next the satellites are grouped such that ranges of satellites of the same group do not collide. All of the signals are at approximately 41.5 dBHz. The reference position uncertainty is set to 10Km. In figure 9, the peaks fall in the middle of the code delay ranges because the AD estimated code delays were set to the accurate ones (The clock drift considered was the exact one). Indeed in this case, the central value of the ranges, which must correspond to the code delays estimated by the AD matches with that calculated after the acquisition process. But for real signals this is not the case. As already mentioned, with the proposed algorithm, the TTFF is reduced since many operations, namely FFTs and Doppler compensation that are done for each satellite in a standard algorithm are rather done for each group of satellites in the SOR algorithm. Consequently, the TTFF is directly related to the number of groups as already explained, and thus to the number of satellites per group. The number of satellites per group is related to the width of the AD ranges. Now, the width of the AD ranges is directly affected by the reference position and the time uncertainties (The satellite elevation and the Doppler also affect the code delay range width but the main contribution to this value is that of the reference position and the time uncertainties). In order to test different GSM environments, three characteristic values of the reference position uncertainty will be considered: 1Km, 10Km and 30Km. These values match with different GSM cell radii. A cell radius of 30Km corresponds to a rural case, whereas the 2 other values correspond to urban cases.

The studied simulations outputs are:

-Mean width of the code delay ranges -Number of subset of satellites used in the algorithm -Mean number of satellites per group Note that for a satellite in the horizontal plane, i.e., with a maximum Doppler frequency of 5KHz [START_REF] Kaplan | Understanding GPS: Principles and Applications[END_REF] and an elevation of 0°(generally the mask angle is of 5°), the range width values due to uncertainties on the reference position and the GPS time add together. For a time uncertainty of 2s, the approximate code delay range width is of 273 chips, 136 chips and 75 chips for GSM cell radii of 30, 10 and 1Km respectively. At the zenith, i.e., with a null Doppler frequency and an elevation of 90° the code delay range width is equal to 0, which means that we have no uncertainty on the code delay in this case. In other words, in this case the code delay for a user located at the Base Station or anywhere else within the considered cell is approximately the same. Figure 12 depicts the code delay range width variation for elevations lying between 0 and 90°, and Doppler frequencies ranging from 5 KHz to 0 correspondingly. The results shown hereafter were obtained by averaging results obtained with different real GPS signals collected using a GPSBuilder receiver. Note that results obtained with simulated signals using a Spirent STR4500 were similar to those obtained with real signals. Thus, the number of satellites per group increases when the reference position uncertainty decreases. For an uncertainty of 10 Km for example, the average number of satellites per group is approximately 3.

The algorithm complexity reduction has been compared to a standard one. The results are given in figure 16 for a TMS320C64x DSP. As we can see in the previous figure, when the satellites are divided into three groups, i.e. the average number of satellites per group is approximately 3, the TTFF is reduced by a factor of approximately 3.

Results concerning sensitivity essentially deal with the reduction of the C/N 0 when more satellites are acquired together, or in other words when more satellites are present in the same group. The tests conducted showed that the more satellites we have per group, the lower is the C/N 0 .

The following example depicts the reduction in the C/N 0 level when more satellites are present in the same group. The signal used to conduct this test was simulated using a Spirent STR4500. For this signal, when only one satellite is present the C/N 0 ratio corresponds approximately to the real one, whereas for three satellites we have an approximate loss of 3dBs and for four satellites, the loss is of approximately 4.5 dBs. The figures below illustrate the correlation function for each group. Considering figures 17, 18, 19, and 20 we can see that the global noise level (mean value of the noise) is lower when only one satellite is present and that the noise variations increase also with the number of satellites processed at once. This explains the loss in the C/N 0 ratio observed for a group of more than one satellite. In addition the noise variations are more important when more signals are present. This can be due to crosscorrelations. Figure 21 below depicts the average loss in the C/N 0 induced by the SOR algorithm, for different groupings of 10 satellites. The signals used here were also simulated using a Spirent STR4500, in order to be able to choose different C/N 0 for each test. The results obtained correspond to the average loss in C/N 0 for these signals at 41.5 and 26.5dBHz respectively. At this stage, one should find the good compromise between the reduction in TTFF and that of sensibility. An upper limit for the number of satellites per group can be set in order for the global loss in the C/N 0 to be limited to a certain value.

The results we have until now show that limiting the number of satellites per group to 3 may be a good compromise.

VI. CONCLUSION

In this paper we presented a new algorithm for GPS acquisition. It essentially enhances the TTFF by correlating the incoming satellite signal with a sum of different C/A codes replicas rather than correlating it with only one code replica. Such processing implies a certain parallelism by searching for more than one satellite at once. It results in a complexity reduction with respect to a standard sequential algorithm. This implies a reduction in the TTFF needed for a GPS receiver to compute a solution.

Evaluating the performances of this algorithm depicted that the global complexity reduction induced by the SOR algorithm in comparison with a standard one depends on the number of satellites processed in parallel. For three satellites the complexity is reduced by a factor of 3 approximately. However, a loss in the C/N 0 ratio was noticed. The more satellites we have per group, the greater is this loss. Thus a compromise must be set in order to have the best correspondence between the reduction in sensitivity and that of the TTFF. An upper limit for the number of satellites per group must be adopted in order to limit the loss in C/N 0 ratio. Bit transitions may be an interesting topic to be considered when correlating in order to compensate for the reduction in sensitivity.

Fig 2 :

 2 Fig 2: An example of a classical GPS acquisition output for a signal at 30dBHz, with a Doppler frequency and code delay of -4500Hz and 600chips respectively

Figure 4 Fig 4

 44 Figure 4 illustrates an example of such a correlation function for a composite signal comprising 10 satellite signals at 30 dBHz. Four of them are acquired in parallel.

Fig 8 :

 8 Fig 8: Correlation function for the first group of satellites with 7 peaks corresponding to each satellite

Fig 10 :

 10 Fig 10: Correlation function for the second group of satellites with 3 apparent peaks

  Fig 12: Variations of the code delay windows with the satellites elevation for three different reference position uncertainties

Fig

  Fig 13: The average width of AD ranges for 3 reference position uncertainties

Fig

  Fig 15: The observed average number of satellites per group for 3 reference position uncertainties

  Fig 16: TTFF improvement brought by the SOR algorithm for different grouping of 10 satellites, in comparison with the standard algorithm

  Fig 17 1 st group (correlation amplitude v/s code delay)

Fig 21 :

 21 Fig 21: Reduction in C/N 0 in terms of the number of satellites per group Reconsidering the case of three satellites per group, the reduction in the C/N 0 is of approximately 3dB.

Table 1 : Satellites grouping to avoid collisions between code delay ranges.

 1 .

	Group number	PRN number
	1	1,3,6,8,10,22,25
	2	17,18,30

Table 3 : Satellites grouping to avoid collisions between code delay ranges Table 4: Satellites respective C/N 0 ratios and code delays (detected after acquisition)

 3

		It comprises 10
	satellites at 41,5 dBHz approximately.
	Group number	PRN Number
	1	1; 3; 8; 10
	2	6; 22; 25
	3	17;18
	4	30

Presented atION NTM 2006, Monterey

ACKNOWLEDGMENTS

This paper has been written in the frame of the research activities of the European project LIAISON. LIAISON is a research project led by Alcatel Alenia Space and involving 34 other European partners, which aims at developing Location Based Services for professional markets. LIAISON has received research funding from the Community's Sixth Framework Program.

We would like to thank Olivier JULIEN for his valuable remarks and suggestions.


Damien Kubrak

Christophe Macabiau

Michel Monnerat

Marie-Laure Boucheret

Vehicular Navigation using a Tight Integration of Aided-GPS and Low-Cost MEMS Sensors

He graduated in 2002 as an electronics engineer from the ENAC, and received the same year his Master of research degree in signal processing. His work focuses on the hybridization of MEMS sensors with a GPS receiver to face personal positioning issues.

Therefore, to augment the availability of the position solution in harsh environments, pseudorange and pseudorange rate measurements are fused in a Kalman Filter (KF) with the Dead Reckoning (DR) solution provided by the sensors assembly following a tight integration scheme.

In the developed vehicular navigation algorithm, the MEMS sensors are used to provide reliable attitude information of the vehicle. It also propagates the position of the vehicle in three dimensions. A conventional GPS receiver gives pseudorange and pseudorange rate measurements for the tight integration. External ephemeredes are used to estimate the satellite Doppler contribution in the user-to-satellite Line Of Sight (LOS).

Results show that as soon as two satellites are tracked, the overall accuracy of the integrated positioning system increases. Moreover, the availability of the position solutions is also augmented. Depending on the type of harsh environments, namely classical or deep urban canyons, heavy map-matching algorithms are not required with such low-cost sensors integration. However, the integration scheme is dependent on the satellite geometry with respect to the user's heading. When a bad satellite configuration is detected, the Integrated Navigation System (INS) relies exclusively on the IMU data. As a consequence, the INS may experience systematic drift for long periods (>1min) without any GPS updates.

INTRODUCTION

Over the past few years, the vehicular navigation has experienced tremendous improvements in both reliability and accuracy. There are indeed many affordable navigation systems available today to assist the user in driving. Current systems are based on powerful High Sensitivity GPS (HSGPS) that are often augmented with odometer and heading information provided by a gyrometer or a magnetometer. Associated with mapmatching algorithms, these navigation systems provide effective means to help the user drive in a city.

As performed in [START_REF] Godha | Performance Analysis of MEMS / IMU / HSGPS / Magnetic Sensor Integrated System in Urban Canyons, ION GNSS[END_REF], [START_REF] Godha | Integration of DGPS with a Low Cost MEMS -Based Inertial Measurement Unit (IMU) for Land Vehicle Navigation Application[END_REF] or [START_REF] Kappi | Unaided MEMS-Based INS Application in a Vehicular Environment[END_REF], this paper investigates the enhancement possibilities of a GPS-based navigation system for land vehicle navigation. More specifically, the study focuses on the feasibility of using very few GPS measurements to estimate IMU errors and thus provide a smoothed and accurate position solution. As discussed and justified in [START_REF] Kappi | Unaided MEMS-Based INS Application in a Vehicular Environment[END_REF], the augmentation of the GPS receiver needs to be small and cheap for LBS perspectives. Therefore in this paper, several low-cost MEMS sensors are used to augment an aided conventional GPS receiver.

In a first section, the MEMS-based sensors assembly is described. A rough analysis is performed to demonstrate the intrinsic low performance capabilities of the different sensors. Then, the GPS core and the aiding method are presented. Section III discusses the integration of both navigation systems in a Kalman Filter. Finally, section IV presents results of the integrated navigation system in real urban conditions. A focus is put on the availability of the integrated system and the hybridization using the measurements of only two GPS satellites to significantly improve the navigation solution.

I -INERTIAL MEASUREMENT UNIT

The Inertial Measurement Unit used in this study is composed of three low-cost MEMS sensors, plus a pressure sensor ($2000 for the integrated unit, but about $15 each sensor). It comprises a triad of accelerometers and gyrometers, and also a triad of magnetometers. The detailed composition is given in Table 1, and characteristics can be found in [6], [START_REF]Analog Devices ADXL[END_REF], [START_REF]Analog Devices ADXRS[END_REF] and [START_REF][END_REF]. Since sensors are low-cost, their intrinsic performance can be expected to be low as well. Thus, in order to use them in a navigation system, all the different errors impacting their respective measurements shall be modelled. These errors are threefold: scale factor, bias and noise. The general sensor output model that will be used in the study is therefore as follows: Among all the errors affecting the measurements, the bias is the worst one. It is composed of a turn-on part, which varies every time the sensor is powered on, and an in-run part, whose variation is closely related to the motion experienced by the sensor. The latter contribution is the more difficult to estimate since the movement of the sensor is unpredictable. It will consequently introduce non-negligible systematic errors in the measurements, especially for accelerometers and gyrometers.

Sensor

[ ] k k true k k output k n b s SF s + + ⋅ + = 1 (1)
The pressure sensor measurements are affected by this kind of error as well, but they are also dependent on atmospheric changes. In the bottom of Figure 1 is plotted data recorded during a whole night in a closed room. As it is shown, the altitude provided by the sensor varies from 145 meters up to 155 meters, whilst the temperature stays constant. The magnetometer's model follows those of equation [START_REF]Global Positioning System Standard Positioning Service Signal Specification[END_REF] and equation ( 2), but must be augmented to take into account random interferences that may occur while driving. The upper part of Figure 1 gives an example of such perturbations caused by windscreen wipers, indicators or rear de-icer and affecting the IMU placed on the dashboard of a car.

The sensors assembly, whose components have been described above, is used as the inertial reference system of the integrated land vehicle navigation system. Gyrometers are used to compute the attitude of the IMU, whereas accelerometers and magnetometers compensate for the drifts, even when the vehicle is moving [START_REF] Kubrak | Performance Analysis of MEMS based Pedestrian Navigation Systems[END_REF].

Figure 2 presents the headings computed with different algorithms during a trial in the city center. The upper part shows the drift of the gyro-based heading with respect to the magnetometer-based one. The GPS derived heading is plotted as well to assess the accuracy of the magnetic heading. The lower part focuses on magnetic interference mitigation. As expected, interferences occurred during the test conducted in the city centre. In the zoom presented Figure 2, the interference lasts about 15 seconds making the magnetic-derived heading unreliable. However, the Kalman filter that fuses the gyro and magnetometer measurements provides good estimate of true heading. The mitigation succeeds so that the attitude computed by the IMU can be used for navigation. The pressure sensor is the last component of the sensors assembly. It is used to check the vertical velocity as well as the vertical position. Figure 3 summarizes the inertial navigation mechanization.

II -GPS MEASUREMENT UNIT

The GPS measurement unit used in this study is composed of two parts. The first one is the receiver itself, whereas the second one is the assistance data.

a) Receiver core

The first part of the GPS measurement unit is a conventional receiver able to acquire and track signals down to 30 dBHz. It is also capable of providing measurements from the different tracking loops as well as pseudoranges with a sampling frequency up to 20 Hz. In our application, only Doppler and pseudorange measurements will be used in the integrated navigation system.

b) Assistance data

The second part of the GPS measurement unit is composed of the assistance data. They are threefold: satellites' ephemeris augmented with ionospheric delay coefficients, rough user's position and rough GPS time.

Ephemeredes and ionospheric delay coefficients are collected using a master GPS receiver operating under clear sky conditions. These data do not help the GPS receiver core to improve the signal acquisition performance. Rough user's position and GPS time are provided only when the GPS unit is started and has not yet given any measurements. This corresponds to the socalled "cold-start" mode. Once the first measurements are available and the initial position has been computed by the receiver, they are no more used as assistance data. The user's position needed to process the ephemeris data is then given whether by the Integrated Navigation System (INS) or the IMU.

The combination of GPS measurements with assistance data allows the computation of four parameters that are useful for the Integrated Navigation System. The first one is the predicted satellite's Doppler contribution, which is computed using ephemeris data, user's position and GPS time. This contribution is estimated with some uncertainty since both position and time are known approximately, at least in the "cold-start" mode.

Given this worst case, an example of the error made on the estimation of the satellites' Doppler contributions is plotted in The satellite clock correction model is as described in [START_REF]Global Positioning System Standard Positioning Service Signal Specification[END_REF]. The receiver core is capable of tracking GPS signals on both L 1 and L 2 , but in our study only the L 1 acquisition and tracking is used. As a consequence, using the notations of [START_REF]Global Positioning System Standard Positioning Service Signal Specification[END_REF], the Space Vehicle clock correction model is as follows: -E is the elevation of the satellite (unit : rad).

( ) ( ) GD k oc f oc f f SV T E a e c t t a t t a a t - ⋅ ⋅ - - + - + = ∆ sin 2 2 2 2 1 0 µ (3)
vap P is the standard ambient vapour pressure.

-T ∆ is the tropospheric delay (unit : m).

In the following, standard conditions will be taken into account, except the ambient pressure that will be provided by the pressure sensor. Consequently, T amb =288,16K, P vap =8,5hPa and P amb =P MS5534 .

The last information provided by the processing of the assistance data is the ionospheric delay impacting the L 1 pseudorange measurements. Despite the dualfrequency capabilities of the receiver core, the Klobuchar algorithm is used for ionospheric delay estimation.

Finally, the GPS Measurement Unit used in this study is composed of a single frequency (L 1 ) receiver core capable of providing Doppler and pseudorange measurements. It is augmented with extra information such as satellite's Doppler contribution and clock bias, ionospheric and tropospheric delays. The principle of the GPS Measurements Unit is summarized in Figure 5.

This unit is then integrated with the IMU described in section I, as discussed in the next section.

III -INTEGRATED NAVIGATION SYSTEM

Several integration schemes can be used to fuse GPS and IMU data. They all can be separated into three categories, namely loose coupling, tight coupling and ultra-tight coupling. Loose coupling is a very famous integration method that gives a great deal of performance for a minimal complexity. It uses GPS position and velocity measurements to correct the data from the IMU. Tight coupling goes deeper in the integration process since it uses raw GPS measurements (Doppler, pseudoranges, delta ranges…) to correct IMU errors. Ultra-tight coupling is the highest integration level, where IMU measurements are used to control GPS tracking In this study, a tight coupling method is investigated to fuse GPS and IMU data and face urban navigation issues when very few GPS measurements are available. Raw pseudorange measurements are collected from the receiver for position correction. The processing of the ephemeredes provides ionospheric, tropospheric and satellite clock corrections so that corrected pseudoranges are fed in the Kalman filter. Because the vehicle is likely to go in urban / deep urban canyons, multi-path may affect these measurements and so the position solution. As a consequence, the receiver Doppler corrected for the satellite contribution is used as the second GPS measurement in the Kalman filter since it is more robust on such perturbations.

The IMU provides position and velocity, whose respective biases are estimated in the filter. Attitude measurements are processed separately to remove drift in pitch, roll and heading angles, as well as to reduce the impact of magnetic interferences on the filtered heading.

The Kalman filter used to fuse both navigation systems is composed of 8 states, as given in equation [START_REF]Analog Devices ADXL[END_REF]. The biases of the gyros are not estimated in the Kalman filter but their estimation is rather done in the attitude filter of the IMU. As discussed above, the measurements used in the filter are of three types and follow the relations given in ( 8), ( 9) and (10). -g is a non-linear function that computes the user's Doppler contribution using -c is the velocity of light

V NED AlongTrack V IMU AlongTrack b V SF V + × = (8) ( ) LOS AT NED AlongTrack LO d receiver GPS corrected d V g f f / , , α + = (9) r receiver GPS corrected clk c D E N ⋅ + ∆ + ∆ + ∆ =
- 1 L is the GPS L 1 frequency.
-N ∆ is the north position difference between the vehicle and the satellite at time of transmission. -E ∆ is the east position difference between the vehicle and the satellite at time of transmission. -D ∆ is the down position difference between the vehicle and the satellite at time of transmission.

The projection coefficient

LOS AT / α that must be applied to the true velocity along the track followed by the vehicle is computed using the satellite position at time of transmission, the position of the vehicle and the result of the processing of the data provided by the IMU. The integrated navigation system principle is summarized in Figure 6. Five measurements at most are fused in the Kalman filter to provide a position solution and also augment the system availability. This navigation system is then tested in actual urban conditions. Results are given in the next section.

IV -TEST RESULTS

This section presents the results of the tests conducted with the system described above. The capability of the INS to provide a position solution in challenging urban canyon conditions is more specifically addressed. The focus is put on the navigation using the IMU and the measurements of only two GPS satellites. IMU data are recorded at 25Hz, whereas GPS data are recorded at 1Hz. The reference trajectory is plotted in Figure 7 as the red path. The traveled distance in the exercised vehicle trial is about 4,5 km for 15 minutes of navigation in urban conditions. The position solution given by the OEM4 GPS receiver is also plotted in blue, and corresponding statistics are given in Table 2 As it can be seen in Figure 7, the position solution availability is medium (66,5 %), that does not allow a full urban navigation. The receiver tracked at least 2 satellites about 93% of the time, which makes the trial suitable for testing the proposed tight integration. During the trial, GPS measurements experienced large errors certainly due to multi-path, as shown by the position solutions inside the green circles. In the following, the two latest satellites that are acquired and tracked will be used in the Integrated Navigation System in order to process data from many satellite configurations and thus simulate real conditions where only 2 GPS measurements were available. In the exercised trial, the satellite configuration, that is the combination of two GPS measurements, changes approximately every 8 seconds.

As a comparison of both navigation systems intrinsic performance, the trajectory computed exclusively with the data provided by the IMU is plotted in Figure 8. In this test, the heading was initialized using the magnetometers and checked by the first GPS measurements. The magnetometers have been calibrated before the trial, so that the magnetic heading is not affected by interference due to the vehicle itself. Two trajectories have been computed, one using the gyro-derived heading (the green plot), the other using the filtered-derived heading (the red plot). As it can be seen in the figure, both trajectories are rapidly drifting. This is mainly due to the accelerometer bias that changes during the trial and impacts the velocity and position computation. The trajectory using the filtered heading provides however the best position solution.

In order to test first the ability of the INS to provide a reliable position solution using very few GPS measurements and second the accuracy of the heading provided by the IMU, a first hybridization is performed using only two Doppler measurements. Results are given in Figure 9. The trajectory using the gyro-derived heading is still unreliable. The gyro drifts affect obviously the heading but also the estimation of the along track velocity through equation ( 9).

Multipath

Opposite, the position solution using the filtered heading is far more accurate. The trajectory shape is clearly recognizable and follows the true path quite well, with a horizontal error bounded by 100m for 15 minutes of navigation. The heading provided by the IMU is thus quite accurate, even if it is not perfect. Because the INS provides a position solution in a Dead Reckoning mode by integrating the debiased velocity, error accumulates so that the position is still drifting and will lead to an unreliable long term position solution. Both trajectories are not affected by multipath, as the GPS-based position is. This is mainly due to the fact that Doppler measurements are less sensitive to multipath than pseudoranges. The above hybridization shows that the use of only Doppler measurements does not allowed the computation of a reliable position with an error bounded in time. As a consequence, pseudorange measurements seem necessary in the integration process.

Another hybridization is therefore performed using only two Doppler and two pseudorange measurements. The filtered attitude provided by the IMU is used in this test. The resulting trajectory provided by the INS is plotted in Figure 10 in red. As a comparison, the GPS trajectory is also plotted in blue.

It can obviously be noticed that the overall accuracy is tremendously improved with the use of pseudorange measurements. The horizontal error stays indeed within 40 meters from the reference trajectory. Even if pseudoranges are used, the hybridized INS trajectory is again resistant to multipath affecting the GPS measurements because of the high confidence in the Doppler measurement model and the position computation strategy implemented in the Kalman filter. In this hybridization test, position estimations with and without height-aiding were performed. However, the horizontal position solution does not vary very much from each integration scheme that is why only the non height-aided solution is plotted in Figure 10.

Figure 11 shows the vertical performance of the hybridized system using only two Doppler and two pseudorange measurements. The upper part of the figure gives the vertical accuracy, with respect to the pressure sensor measurements. As it can be seen in the figure, the vertical error reaches about 30 meters without heightaiding, whereas it stays below 5 meters when the altitude is used in the Kalman filter. However, the path followed during the test was quite flat, as shown in the lower part of the figure. Thus, the capability of the filter to bound the vertical error when Residual « gaps » height-aiding is performed has to be considered with care. The vertical accuracy should be assessed with a hilly path.

The velocity profile of the vehicle computed using two Doppler and two pseudorange measurements is plotted in Figure 12. The velocity of the INS is well debiased compared to the one provided by the IMU itself and that is fed in the Kalman filter. However, the along track velocity profile experiences sudden variations that affect the position solution. Some may be very large, as shown by the black circles in Figure 10. Two velocity profile zooms are plotted in Figure 13 to clearly observe the discontinuities that sometimes appear. In these two examples, discontinuities clearly occur around samples 6750 and 39600. They can be due to two events. The first one occurs when the hybridized solution relies exclusively on IMU data, thus accumulates errors, and then is corrected by GPS data. The second one occurs when low quality GPS data are used to correct the velocity and the position provided by the IMU. Since in our case, discontinuities appear when GPS measurements are combined with IMU data, the hybridization methodology can be considered responsible for those issues.

Figure 14 presents three different plots that explain the reasons of this bad velocity estimation when GPS and IMU data are tightly integrated. The lower right plot gives the PRNs used in the Kalman filter, the upper right plot the velocity computed using these different PRNs and the left plot the satellite geometry and user heading at time of data combination. At the beginning, PRN 14 and 6 are used for hybridization. Based on these two PRNs, the user's velocity along the track followed by the vehicle has been computed and plotted. It corresponds to the green dots in the upper right plot. As it can be stated, this velocity has got a large variance. The position of PRN 14 when it is used in the Kalman filter is plotted on the left as the blue dots, whereas the position of PRN 6 is plotted as the red dots. The heading of the user is also referenced as the black dots. Obviously, given this satellites configuration with respect to the user's heading, the estimation of the user's Doppler contribution is very difficult, even not possible. This explains why the GPS-based user's velocity is very noisy.

The Kalman filter uses then PRNs 14 and 5 to estimate the along track velocity. The configuration of the satellite's position with respect to the user's heading is far better, as it can be seen in the left plot. This also explains why the user's velocity is computed with much accuracy, as shown with the red curve in the upper right plot. It can thus be stated that the satellite geometry is of tremendous importance to estimate the velocity of the vehicle, as the DOP is for GPS positioning accuracy.

Sudden changes

To avoid this discontinuity issue, a criterion based on the geometry of the satellites used for hybridization has been implemented. When bad configurations are detected, GPS measurements are no more taken into account, but the INS relies exclusively on the IMU data.

The results of the along track velocity estimation is plotted in Figure 15, using only two Doppler measurements to avoid the pseudoranges to interfere in the velocity and position computation. The improvement is not obvious. It could either perform better or worse. Sudden variations are still observable, but in that case, they are due to the re-use of new good GPS measurements. The performance of the INS without GPS updates depends directly on the quality of the sensors that are used. The improvement on the position solution is not obvious as well, as it can be noticed in Figure 16. Even if the horizontal accuracy stays within 100 meters from the reference trajectory, the final error is worst than without IMU-based corrections.

CONCLUSION

This paper investigated the land vehicle navigation using low-cost sensors and a conventional GPS receiver using very few GPS measurements for the tight hybridization. It as been shown that two Doppler and two pseudorange measurements were sufficient to allow the estimation of the bias affecting the velocity provided by a low-cost MEMS-based IMU.

The use of only two Doppler measurements shows that the accuracy of the heading provided by the IMU was reliable enough to provide a good short term position solution. Long term positioning is rather difficult since the trajectory is slowly drifting because residual biases affect the attitude of the IMU. However, a horizontal error within 100m is achievable for 15 min of navigation with only two Doppler measurements. Height aiding improves the vertical accuracy that is reduced from 30 meters to 5 meters with the adjunction of pressure sensor measurements in the Kalman filter. The trial exercised here was quite flat, so hilly tests should be performed to assess this improvement.

However, the Integrated Navigation System is dependent on the geometry of the satellites used for hybridization, especially when only two measurements are used. Bad satellites configurations with respect to the user's heading yield to erroneous velocity updates. A detection criterion has thus been implemented to prevent these configurations from biasing both the velocity and the position of the vehicle. During these periods, the performance of the Integrated Navigation System relies then exclusively on the quality of the sensors used in the IMU.

s

  is the actual quantity at epoch k . -output k s is the output of the sensor at epoch k . k b is the bias at epoch k . -on turn k b -is the turn-on bias at epoch k . -run in k b -is the in-run bias at epoch k . k SF is the scale factor at epoch k . k n is the sensor noise at epoch k .

Figure 1 -

 1 Figure 1 -Pressure sensor and magnetic interference issues.

Figure 2 -

 2 Figure 2 -IMU heading measurements.

Figure 3 -

 3 Figure 3 -Inertial Measurement Unit Mechanization.

Figure 4

 4 recorded from visible satellites, but does not take into account time uncertainty, which may introduce extra +/-2 Hz error.

Figure 4 -T

 4 Figure 4 -Satellite Doppler Uncertainty.

Figure 5 -

 5 Figure 5 -GPS Measurement Unit.

  position in the navigation frame. This includes North, East and Down components. -V SF is the along track velocity scale factor. -NED AlongTrack V is the true along track velocity in the navigation frame. -V b is the bias affecting velocity measurements. r clk is the receiver clock bias. r clk ∂ is the receiver clock drift.

  Track to Line Of Sight projection coefficient.

Figure 6 -

 6 Figure 6 -Integrated Navigation System.

Figure 7 -

 7 Figure 7 -Reference trajectory & OEM4 trajectory.

Figure 8 -

 8 Figure 8 -IMU based trajectories.

Figure 9 -

 9 Figure 9 -INS trajectories. 2 Doppler measurements used when available.

Figure 10 -

 10 Figure 10 -INS trajectory. 2 Doppler and 2 pseudorange measurements used when available.

Figure 11 -

 11 Figure 11 -INS vertical error. 2 Doppler and 2 pseudorange measurements used when available.

Figure 12 -

 12 Figure 12 -Along track velocity profile.

3.87 3 .Figure 13 -

 313 Figure 13 -Velocity profile discontinuities.

Figure 14 -

 14 Figure 14 -Satellite geometry issue.

Figure 15 -

 15 Figure 15 -Velocity profile corrected by IMU measurements when bad satellites configurations are detected.

Figure 16 -

 16 Figure 16 -Corrected and non-corrected INS trajectories.

  the position accuracy. A horizontal error within 40 meters of the reference trajectory can indeed be achieved using only two Doppler and two pseudorange measurements. No more drift is noticeable in the Integrated Navigation System position solution.

Table 1 -

 1 IMU components.

		Manufacturer	Product
	Accelerometers	Analog Devices	ADXL202E
	Gyrometers	Analog Devices	ADXRS300
	Magnetometers	Philips	KMZ52
	Pressure sensor	Intersema	MS5534

  .

		OEM4 Tracking status.
	Nb of satellites	0 -1	2	3	≥ 4
	% of time	7,2% 12,3% 14% 66,5%

Table 2 -

 2 OEM4 tracking performance.

Presented atION NTM 2006

ACKNOWLEDMENTS

The authors would like to thank GeoConcept for the GIS software used in the study.

GPS measurements re-used