New Method for GPS Direct Position Estimation Based on Collective Detection Approach

New Method for GPS Direct Position Estimation Based on Collective Detection Approach

Wantong Chen

Tianjin Key Lab for Advanced Signal Processing Civil Aviation University of China

Tianjin, China

Abstract Collective detection is a direct position estimation method, which is shown to perform effectively in weak signal navigation applications. Different from the traditional GPS signal individual acquisition and tracking, this technique combines the received power from all GPS satellites in view and directly leads to a position solution, thus resulting in a very high sensitivity. However, the huge computation and computational complexity may limit its practical application. We then present a new method for position estimation based on collective detection scheme. We take full account of the structure of the problem to make our algorithm efficient and easy to realize. Real data test results suggest that our algorithm is effective and also good in terms of accuracy.

Keywords GPS; collective detection; weak signal navigation; vector-based tracking; acquisition

1. INTRODUCTION

   In recent two decades, GPS-based position and location requirements have become more and more ubiquitous for many different vehicles in terrestrial, sea, air and space. However, growing interest in indoor positioning is motivating research on techniques for weak GPS signal acquisition and tracking. Also, poor signal reception in other than open-sky environments is still a problem. Hence, a lot of effort is being directed to enhance signal sensitivity such as extending signal integration times [1] and using assisted- GPS techniques [2]. For these traditional methods, the signal of each satellite is acquired and processed individually, thus neglecting the association of different satellite signals on the same location.

   More recently, it has been proposed that combining information from multiple satellites is also a feasible solution, represented by the collective detection technique. By combining the received power from all GPS satellites in view and directly leads to a position solution, this technique is suitable for any application that requires a navigation solution in a signal environment that challenges traditional acquisition techniques [3]. In essence, it is a vector-based acquisition approach. Even if all signals are too weak to be acquired and tracked by the traditional framework, a quick and coarse position solution can be directly estimated by combining the received signal power from each satellite. In addition, this approach could be used to aid deeply-coupled GPS/INS navigation and assist with terrain/feature-landmark recognition in an urban environment.

   Although there is no required hardware change, it is shown that the computational complexity is huge for the

   This project is supported by National Natural Science Foundation of China (Grant No. 61401468).

   traditional collective detection. The present new method aims to reduce the complexity of the algorithm and attempts to mitigate the shortcomings in practical application. Different from the simulated results in current literature, the experiments with actual data have also been performed.

   The rest of this contribution is organized as follows. Section II provides a brief review on the traditional approach to signal acquisition and tracking. Section III describes the collective detection algorithm and its assumptions. Section IV proposes a new method for GPS direct position estimation based on collective detection approach. Section V elaborates on the actual experiments based on GPS observations, which have been performed to verify the correctness of new method and the accuracy of coarse position solution. Section VI concludes the overall contributions of this work and possible improvements are also discussed.

2. THE TRADITIONAL ACQUISITION THEORY

   A. Motivation and Principle

   The purpose of acquisition is to determine visible satellites and coarse values of carrier frequency and code phase of the satellite signals. GPS satellites are differentiated by the different PRN sequences. Only when a local PRN code that is perfectly aligned with the incoming code, a high correlation peak occurs and then the incoming code can be removed from the signal. It is also important to know the received frequency of the signal to be able to generate a local carrier signal, which is used to remove the incoming carrier from the signal. Based on both motivations, the acquisition algorithm assesses the signals correlation power in discrete bins on a grid of code delay and Doppler frequency.

   In detail, the correlation power calculations are based on multiplication of locally generated PRN code sequences and locally generated carrier signals with the sampled signal from the receivers RF front end. Multiplication with the locally generated carrier signal generates the in-phase signal I, and multiplication with a 90 phase-shifted version of the locally generated carrier signal generates the quadrature signal Q. The correlation power is the sum of the I and Q components, I2 + Q2. By mixing the sampled signal with a family of receiver-generated replica signals that span the grid, we can plot the power as a function of code delay and frequency shift, thus producing a correlogram. If the highest correlation peak exceeds a predefined threshold, we assume that the frequency shit and code phase parameters are correct and both parameters can be passed on to the tracking algorithms, which produce more precise measurements of delay dubbed pseudoranges from which the receivers navigation solution is calculated.

   B.Strong Signal Case

   The acquisition algorithm expects that a distinct peak appears in the correlogram bin that corresponds to the true GPS signals code delay and Doppler frequency, as is shown in Figure 1. Normally, if a received signal is sufficiently powerful, a distinct peak appears in the correlogram bin.

   Fig.1 The correlograms for a strong GPS signal acqusitiuon (IF Frequency:4.309MHz;Sampling Frequency:12MHz)

   C.Weak Signal Case

   However, based on the given integration times, the fact that peak power exceeds a predefined threshold is not a certain event. In particular, when the weak signal is present, the correlation peak cannot be distinguished, resulting in the failure of the conventional acquisition approach, see Figure

   2. The typical weak signal environments like indoors, foliage, forest, tunnel and deep urban canyons. The signal strength in these scenarios is normally 10-25 dB weaker than the lower bound of that in open-sky conditions [4].The theoretical probability of detection for traditional acquisition algorithm is discussed in [5].

   Fig.2 The correlograms for a weak GPS signal acqusitiuon (IF Frequency:4.309MHz;Sampling Frequency:12MHz)

   D.Solution for Enhancing Signal Sensitivity

   Increasing the coherent integration time is an effective solution for giving GPS some degree of capability to operate indoors and in other restricted environments [6]. It uses the fact that the zero-mean Gaussian noise accumulates

   slower than the signal of interest by a longer integrated period. However, the data-bit transitions in the signals navigation message should be carefully wiped-off [1]. Any other adverse factors such as receiver clock instability and dynamics should also be sufficiently considered.

3. COLLECTIVE DETECTION THEORY

   In the traditional acquisition, the signals correlation power is evaluated in discrete bins on a grid of code delay and Doppler frequency. Different from that, in the collective detection algoritm, the combined correlation power is evaluated on the position and clock offset grid. Thus, it leads directly to the navigation solution. In other words, collective detection is a direct position estimation method. All the individual GPS signal correlations map into the navigation domain, in which the combined correlation power is evaluated. However, the mapping requires the receiver to have a priori knowledge.

   A.Priori Informaiton

   As a priori knowledge, the approximate position of the receiver, the GPS ephemerides and the current GPS time are often required for the collective detection technique. The approximate position can be provided by the extrapolation of the past positions or other positioning method like GSM and Wi-Fi. The GPS ephemerides can be obtained from the Internet, the wireless communication or the previous satellite data. The current GPS time is an important assumption, which can be attained after the first successful estimation of navigation solution. Then, the receiver clock can be corrected to GPS time and the clock-bias is assumed insignificant in a short period of time.

   B.The Search Space

   With the priori knowledge above, the collect detection algorithm defines the position and clock offset search grid centered on the assumed receiver state. The mapping then relates each one of the position and clock offset grid points to a specific code delay and Doppler frequency for each GPS satellite. Different from the grid of code delay and Doppler frequency which is used in traditional acquisition scheme, the search space of collective detection scheme is set up with all the possible position and clock bias of the receiver. In other words, the search space has four dimensions: three search dimensions for positions and a fourth dimension for the clock-bias. Next, for each candidate North-East-Down-Clock value in the search space, projections are performed from the code-phase/Doppler domain to position/clock-bias domain.

   C.The Basic Principle

   Collective detection is a direct position estimation method, which combines the received power from all GPS satellites in view and directly leads to a navigation solution. Based on the search space described above, the correlation power is summed over all the GPS satellites at each position

   /clock-offset grid point to create a navigation domain correlogram. The grid point that has the highest combined correlation power denotes the optimal position and clock- offset estimation. Since the correlogram is built based on the scheme of non-coherent combination of multiple satellites, the correlation power detection is assumed as collective. It

   indicates that the signals which are too weak to be acquired and tracked can also be incorporated into the estimation of navigation solution.

   D.The Computation Process

   For each grid point of the search space, we should compute the correlation power for each satellite. The correlator values are taken as the multiplication of the sampled IF signal and the locally generated signal. We can use the computed pseudorange to compute the received code-phase by the following equation:

   Since the search space has four dimensions dubbed North-East-Down-Clock, the number of points to be evaluated is huge and requires large computational time. The computational complexity can be reduced to a certain extent by decreasing the step size of the grid, but the accuracy of navigation solution will be reduced significantly. In fact, the largest step size is limited by the length of one ranging code. Hence, the existing collective detection scheme has limited practical applications.

4. NEW METHOD AND ITS IMPLEMENTATION

   = mod c,Tc

   (1)

   This section presents a new method for position estimation based on collective detection scheme. The

   c

   where is the computed code-phase and T is the period of the ranging code and is the computed pseudorange of

   each point in the search grid. We can compute each satellites position using the ephemeris data and then compute the pseudorange with it. Assuming that is the

   pseudorange at the center of the search space, is given by

   =-N cos cos -E sin cos Dsin b (2)

   where is the azimuth of the satellite and is the elevation of the satellite and N, E, D, b is the

   difference between the candidate grid and the center grid. The details of the collective detection approach are presented in [7, 8]. Figure 3 demonstrates the basic principle and computation process of collective detection approach.

   E.The Computational Complexity

   Although the sensitivity can be improved significantly with collective detection, the main issue of the algorithm is the computational complexity.

   proposed algorithm is efficient and easy to realize. Real data test is also performed to verify the correctness of the new method.

   A.The Reduction of Search Space

   In order to accelerate the traditional collective detection, a practical strategy is to cut down the dimension of the search space. Since the clock-bias dimension is much larger than the other three dimensions, it is assumed to be the major factor that increases the complexity of the collective detection algorithm. Thus, a very fine-time assistance will alleviate the computational load. More specifically, the reduction in clock-bias search domain can be achieved in the following two scenarios.

   The first scenario is that a successful positioning has been done. Then, the receiver clock can be corrected to GPS time and the clock-bias is assumed insignificant in a short period of time. The second scenario is that the estimation of receiver clock bias is too coarse but as least one satellite is strong enough to be acquired individually by the acquisition block. In this case, the reference [9] proposed one method to estimate the clock-bias. The basic principle is that the clock bias can be computed by the difference between the measured code-phase and the geometric code-phase. The former can be extracted by the strong satellites correlogram and the latter is calculated by the computed geometric range.

   Navigation

   Domain

   Code Delay and Doppler Search Domain

   Signal Power

   SVN

   Grid Point

   Parameter Estimation of SV1

   Non-coherent

   SV2

   Correlation Power of SV1

   Com bined Correlation

   Power

   combination

   SV2

   on

   North[m]

   Priori Informait

   SVN

   Doppler

   Doppler

   Doppler

   East[m]

   Traversing all the grids

   Code Delay

   Code Delay

   Code Delay

   The Combined Correlation Power Over All the Grids

   The Highest Combined Correlation Power

   Fig.3 The basic principle and computation process of collective detection approach

   B.The Calculation of Code Phase and Doppler

   mt , nt , kt arg max E

   We assume that the receiver clock is synchronous with GPS time and the tiny clock-bias could be ignored. For each grid, the corresponding code phase and the Doppler

   K i m,n,t i1

   m, n, t

   (8)

   frequency of each satellite are thus calculated as follows. Here the position coordinate of the candidate grid is denoted as u , thus we have the following equation:

   rx u

   rx u u

   u s i (tGPS i ) T i u I i u c i (3) where t GPS is the GPS time for the received signal; i is

   1. he Fast Estimation of Signal Transmission Time

      Note that there is no analytic solution for (3) due to its nonlinearity. However, the signal transmission time can be resolved by the dichotomy algorithm. The specific steps are as follows:

      1. Supposing that the transmission time at epoch k for

         satellite i is i and the maximum of fluctuation range of the

         the signal transmission time from the satellite i to the

         candidate grid u ; s i (tGPS i ) is the satellite position when

         k

         trnsmission time at the next epoch is , the interval of

         rx u

         the electric signal is sent from the satellite, which can be

         i

         k 1

         can be given by

         computed with the known GPS ephemerides;

         I i u is

         i

         i , i ,if

         fi tGPS 0

         k 1 k k

         k rx

         (9)

         k 1

         k k

         k

         rx

         ionosphere error and

         T i u

         is the troposphere error; c

         i

         i – , i ,if

         fi tGPS 0

         denotes the velocity of light.

         Equation (3) can be solved by the dichotomy algorithm, which is described in the following section. Assuming that

         the transmission delay i is resolved, the signal sending

         where fi tGPS is the Doppler frequency of satellite i at epoch k.

         k rx

      2. Compute the middle time in the interval given by (a):

         u

         time of satellite clock is given by

         m L H /2

         (10)

         tx rx u rx u

         ti tGPS i dti (tGPS i )

         i GPS i

         (4)

         where L is the lower boundary of the interval and H is the upper boundary of the interval.

      3. Let i be , if we have

         where dt (trx u ) is the satellite clock bias at the GPS

         GPS i

         k +1 m

         u s i (tGPS i ) T i u I i u c i

         (11)

         time (trx u ) . Thus, the received code-phase at GPS time

         rx k 1

         k 1

         rx

         rx k 1

         k 1

         t GPS can be computed by the following equation:

         then the interval will be updated with L,m .Otherwise, if

         Di

         tGPS

         = mod

         u s i (tGPS i

         ) T i u I i u c i

         (12)

         where

         D i tGPS

         rx tx c

         is the computed code-phase and Tc

         ti ,T (5)

         is the

         then the interval will be updated with m , H .

      4. Repeat step (b) and step (c), until the following

   rx

   k 1

   period of the ranging code (1ms for GPS L1 C/A). The condition is required:

   rx k 1

   k 1

   Doppler frequency of satellite i is

   u s i (tGPS i

   ) T i u I i u c i

   104

   (13)

   rx

   fi tGPS =-

   d u s i (tGPS i )

   rx u

   dt

   (6)

   Here i

   can be treated as the solution of (3) at epoch k+1.

   rx

5. RESULTS AND DISCUSSION

   With the estimated code-phase

   D i tGPS

   and the Doppler

   In order to verify the correctness of proposed collective detection method, actual static pointing experiment has been

   rx

   frequency fi tGPS , a local signal is generated. Next, the

   correlation power is calculated by the multiplication of the locally generated signal and the sampled signal from the receivers RF front end. By combining information from multiple satellites, the total correlation power is given by

   K

   carried out. The coordinates of the location of the data acquisition are (39.97995 º N,116.33410 º E,28.9m). For comparison purposes, a power divider is used to split the GPS signal from the antenna into two branches equally. For one branch, the GPS L1 data were logging by JAVAD Alpha-2 receiver with advanced multipath reduction. This

   E m, n, k Ei m, n, k

   i1

   (7)

   branch is denotes as the normal branch. For the other branch, the GPS signal was first attenuated about 8dB by an

   where K is the number of visible satellites and Ei m, n, k

   is the correlation power corresponding to satellite i for the grid m, n, k . By traversing all grids, the grid point that has

   the highest combined correlation power is assumed as the best position. Without loss of generality, we assume that a distinct peak appears in the correlogram bin mt , nt , kt ,

   thus giving by

   attenuator and then data were collected by a RF front end and processed by Software-Defined Receiver. The important parameters for the signal processing are

   • Sampling frequency: 12MHz

   • Intermediate frequency: 4.309 MHz, and

   • One-bit sample.

   Figure 4 shows the constellation of GPS satellites, with seven satellites visible. The carrier-to-noise ratio of each satellite is given in Table 1 for both branches.

   TABLE I. SIGNAL POWER FOR BOTH BRANCHES TABLE II. COMPUTING TIME FOR DIFFERENT STEP SIZE

   GPS Satellites PRN	18	21	24	15	9	22	14
   Normal Branch C/N0(dB-Hz)	49	46	46	43	42	41	40
   Attenuated Branch C/N0(dB-Hz)	41	38	38	35	34	33	32

   Step Size	Position Estimation
   	Averaging computing time(second)	Standard deviation(meter)
   25m	2.668	12.3
   50m	0.958	30.2
   100m	0.389	59.8
   200m	0.245	119.5

   30

   330

   0

   300

   30

   60

   45 9

   22

   60

   18 15

   270

   75

   90

   90

   24

   120

   240

   14 21

   150

   180

   210

   Fig.4 The constellation of GPS satellites

   Note that the traditional positioning will not be achieved for the attenuated branch, because the satellites with strength 35 dB-Hz or lower are not acquired and are almost as noisy as the satellites not visible to the receiver. As is shown in Table 1, PRN 18, 21 and 24 have strong signals and they can be acquired using the standard method. However, the number of satellites with strong signal is less than four satellites, thus making the standard positioning impossible.

   Different from the standard positioning method, the proposed collective detection approach combines the received power from all GPS satellites in view and directly leads to a position solution, as is shown in Figure 5. The priori knowledge about the approximate position of the receiver is provided by a cell-phone tower, and the receiver clock bias is estimated using the averaging clock-bias estimations across all strong satellites, based on the approach proposed in [9]. Both the position accuracy and computational load are determined by the step sizes or the density of grid partition.

   Fig.5 Direct position estimation using the proposed collective detection approach (The step sizes of both the north component and east component are 50m, using the priori height)

   The elapsed times for the proposed method are measured at every epoch using Visual Studio 2008 development platform at a PC with Intel® Pentium(R) 4 CPU 2.40GHz and 2048MB RAM.

   Since the accuracy of position decreases as the computing time decreases, a balance should be achieved for the step size between the computing time and accuracy.

6. CONCLUSIONS

This contribution provides a detailed implementation method of collective detection, and the example results from actual GPS signals show how the non-coherent combination of multiple satellite signals improves the GPS position error in cases where some of the signals are too weak to be acquired and tracked by traditional methods. This capability is particularly useful to a user who benefits from a rapid, but coarse, position solution in a weak signal environment such as indoors and urban Canyon. Although the accuracy of collective detection is in general lower than hat of the traditional GPS positioning algorithm, the proposed method has obvious advantage for the quick position solution under the weak signal scenario. Thus, this technique could provide a new way to aid deeply-coupled GPS/inertial navigation.

ACKNOWLEDGMENTS

This work is supported by the National Natural Science Foundation of China (Grant No. 61401468)

REFERENCES

1. Borio, D., O'Driscoll, C., and Lachapelle, G., "Coherent, Non- coherent, and Differentially Coherent Combining Techniques for Acquisition of New Composite GNSS Signals," IEEE Transactions on Aerospace and Electronic Systems, Vol. 45, No. 3, July 2009, pp. 1227-1240.

2. van Diggelen, F., A-GPS: Assisted GPS, GNSS, and SBAS, Norwood, MA, Artech House, 2009.

3. Langley, R. B., "Innovation: Collective Detection", GPS World, January 2010.

4. Dedes, G., Dempster, A.G., "Indoor GPS positioning-challenges and opportunities", VTC-2005-Fall, Sept., 2005, pp. 412-415

5. Axelrad P., Bradley B. K., Donna J., Mitchell M., Mohiuddin S. "Collective Detection and Direct Positioning Using Multiple GNSS Satellites", Navigation: Journal of The Institute of Navigation, Vol. 58, No. 4, Winter 2011, pp. 305-321.

6. Zhe He, V. Renaudin, M. G. Petovello and G. Lachapelle, "Use of High Sensitivity GNSS Receiver Doppler Measurements for Indoor Pedestrian Dead Reckoning", Sensors 2013, 13, pp. 4303-4326.

7. Bradley, B. K., Axelrad, P., Donna, J., and Mohiuddin, S., "Performance Analysis of Collective Detection of Weak GPS Signals," Proceedings of the 23rd International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2010), Portland, OR, September 21-24, 2010, pp. 3041-3053.

8. Maherizo Andrianarison, Mohamed Sahmoudi, René Landry, "Innovative techniques for Collective Detection of multiple GNSS signals in challenging environments", Indoor Positioning and Indoor Navigation (IPIN) 2016 International Conference on, pp. 1-8, 2016, ISSN 2471-917X.

9. Lakshay Narula, Keshava P.Singh,Mark G.Petovello. "Accelerated collective detection technique for weak GNSS signal environment", 2014 Ubiquitous Positioning Indoor Navigation and Location Based Service (UPINLBS), 20-21 Nov. 2014, pp.81-89.