2. COLLECTIVE DETECTION

The block diagram of operations in the conventional method and CD are compared in Figure 3. The post-Doppler-frequency removal complex baseband signal can be written as:

(1)$${\bf s} = \sum\limits_{k = 1}^N {a_k {\bf v}_k (\tau _k ) + {\bf n}} $$

where v_k(τ _k) is the signal vector of satellite k (number of satellite visible k∈(1, 2 … N)), τ _k is the code delay, n is the vector of the Additive White Gaussian Noise. In conventional acquisition, the signal s is correlated with a local replica ${\bf \hat v}(\hat \tau _k )$, where $\hat \tau _k $ is the hypothesised code delay of satellite k. Thus the correlation power of a conventional Global Navigation Satellite System (GNSS) receiver is expressed as:

(2)$$S_{conventional} (\tau _k ) = \left| {{\bf s} \cdot {\bf \hat v}(\hat \tau _k )} \right|^2 = \left| {a_k {\bf v}_k (\tau _k ) \cdot {\bf \hat v}(\hat \tau _k ) + {\bf \tilde n} \cdot {\bf v}_k (\tau _k )} \right|^2 $$

Figure 3.

Block diagram of conventional GNSS receiver and CD.

The array containing correlation results for one satellite is defined as the correlogram for that satellite. In conventional detection, the peak position of the correlation is at first estimated as the code delay $\hat \tau _i $(number of satellite acquired i∈(1, 2 … M) and M⩽N) of each acquired satellite and then the estimation of position and other parameters defined as a vector ${\bf \hat \gamma} $ is performed with that information (including tracking). Generally, ${\bf \hat \gamma} $ includes the estimation of receiver position and common clock bias (e _r, n _r, u_r, b). The number of parameters estimated can be more than 4 to include other factors. To obtain the navigation solution, the number of satellites acquired should be no less than the number of parameters to be estimated. The common clock bias b is defined as the timing difference between the receiver's local clock and the synchronized satellite's clock. The parameter space of ${\bf \hat \gamma} $ is defined as the uncertainty space Γ and therefore ${\bf \hat \gamma} \in \Gamma $.

In contrast, CD performs parameter estimation by non-coherently summing the correlation power of all the visible satellite channels calculated for conventional acquisition.

(3)$$S_{CD} (\bf \hat \gamma ) = \sum\limits_{k = 1}^N {\left| {{\bf s} \cdot {\bf \hat v}(\hat \tau _k ({\bf \hat \gamma}, {\bf \psi} ))} \right|} ^2 $$

ψ is the satellite position vector, (e _k, n_k, u_k) are the coordinates of the kth satellite in the Earth-Centred Earth-Fixed (ECEF) coordinates which are known from assisted information. This involves the mapping from position and clock bias space to correlograms of individual satellites.

According to the pseudorange model, the non-linear relationship between the user's position and code delay of the kth satellite is given by the pseudorange,

(4)$$P_k = c\tau _k = c\rho _k + cb + \varepsilon _k = \sqrt {(e_k - e_r )^2 + (n_k - n_r )^2 + (u_k - u_r )^2} + cb + \varepsilon _k $$

with ε _k referring to noise on the phase rate measurement due to non-modelled terms. Then for a given point in the position and CCB space, the corresponding code delay τ _k(e _r, n_r, u_r, b) in the individual correlogram of the satellite can be obtained by mapping with equation (4). The linearised expression with respect to an initial knowledge of position and common clock bias (e _r0, n _r0, u _r0, b ₀) and combination of offset (Δn, Δe, Δu, Δb) is

(5)$${\rm \Delta} P_k = c{\rm \Delta} \tau _k = - \cos (\alpha z_{^k} )\cos (el_{^k} ){\rm \Delta} n - \sin (az_{^k} )\cos (el_{^k} ){\rm \Delta} e + \sin (el_{^k} ){\rm \Delta} u + {\rm \Delta} b$$

where the azimuth and elevation of each satellite are based on the a priori position solution. So for CD, the uncertainty space Γ is centred on the initial position and common clock bias and is bounded by the accuracy of the initial knowledge. Generally, the a priori information is provided via the A-GPS framework or by a coarse estimation.

Obtained by mapping back to the correlogram of each individual satellite, the correlation power for each position and CCB point is summed and the PDPC is created. The location of the PDPC point that has the highest combined correlation power is taken as the best position and clock bias estimate.

The advantage of CD is that correlograms of individually undetectable satellites in a conventional GNSS receiver are combined for position and CCB estimation, which can be very useful for weak signal detection, especially when the number of detectable satellites is smaller than the number of parameters to be estimated.

Although the parameters to be estimated (e _r, n_r, u_r, b) are continuous variables, it is impossible to evaluate an infinite number of points in uncertainty space. As in the case of conventional code phase acquisition in a GNSS receiver, the difficulty is overcome by using sampling. In practice, only a discrete number of PDPC outputs are calculated. The position and CCB points are evenly distributed across the uncertainty space Γ. In the multi-resolution CD algorithm, the uncertainty space Γ is discretised with a grid of different size so as to achieve estimation with a different resolution.

The problem of direct positioning using PDPC is similar to the peak detection of the correlogram in conventional GNSS receiver acquisition. The difference is that in CD, N correlograms are combined to construct one multi-dimensional (at least four) PDPC. Thus, the computation load of CD is much higher.

3. MULTI-RESOLUTION ALGORITHM OF CD

A two level multi-resolution acquisition strategy has been proposed to address the balance between acquisition resolution and computation load in a Galileo receiver (Margaria et al., Reference Margaria, Dovis and Mulassano2008). Axelrad et al. (Reference Axelrad, Bradely, Donna, Mitchell and Mohiuddin2011) and Bradley and Axelrad (Reference Bradley and Axelrad2010) have proposed a three level multi-resolution algorithm to reduce the computation load of CD with large initial uncertainty. The basic features of the Axelrad et al. (Reference Axelrad, Bradely, Donna, Mitchell and Mohiuddin2011) multi-resolution CD algorithm are as follows:

1. (1) As demonstrated in Figure 4 (For simplicity, only one dimension of horizontal position is given. Generally east and north have the same uncertainty and search step size), CD is first executed using a coarse set of step sizes and large uncertainty (or on a coarse grid covering a large uncertainty region) based on the accuracy of initial position from assisted information.

2. (2) The search grid of the subsequent level is centred at the position-CCB estimated from the previous level.

3. (3) Each level has a predetermined uncertainty region and step sizes, where successive levels gradually reduce in step size and uncertainty.

4. (4) The searching strategies of each level are the same. Moreover, equal step sizes of horizontal position and CCB are used, although they have different initial uncertainty and resolution requirements.

5. (5) To allow for a margin of error and increase the overall estimation accuracy, there is a big overlap between the step size of the previous level and the uncertainty range of the current level. For example, if the horizontal position step size of the low-resolution level is set to be 1000 m, the uncertainty range of higher resolution level is set to be ±2000 m.

6. (6) An averaged correlogram, in which each value is the sum over a block of correlation values spanning the desired delay, is used in the rough level to cover a large uncertainty range with a coarse grid. When the step size of both horizontal and CCB are the same and set to be s _p, and s _p is bigger than 300 m, a=f _s·s_p/c (Generally a is a rounded even integer) numbers of correlogram values for individual satellites are averaged to construct the PDPC, where f _s is the sample frequency and cis the speed of light. For a given grid in position and CCB space (e _r (i), n _r(i), u _r(i), b(i)), the corresponding code delay τ _k(i) of satellite k can be calculated by Equation 4, and the averaged correlogram valued can be calculated by:

   (6)$$S_{averaged} (\tau _k (i)) = \displaystyle{1 \over {a + 1}}\sum\limits_{m = - a/2}^{a/2} {\left| {{\bf s} \cdot {\bf \hat v}(\hat \tau _k (i + m))} \right|^2} $$
   and the corresponding PDPC value for this grid is:
   (7)$$S_{CD} (\tau _k (i)) = \sum\limits_{k = 1}^N {S_{averaged} (\tau _k (i))} $$

Figure 4.

Demonstration of uncertainty and search grids of 3-level multi-resolution CD.

To improve the efficiency of multi-resolution CD, we examined the characteristics of the search with different resolutions and designed different searching strategies. As demonstrated in Figure 3, the search engine consists of a coarse search followed by a medium search and a fine search stage. It is proper to be used in an Assisted-GPS (A-GPS) snapshot receiver. The major advantages of the new multi-resolution CD search engine are as follows:

• • Different strategies are applied to coarse search and fine search, considering the different roles they play in the final positioning and the characteristics of PDPC with different resolution. With different searching strategies applied to different levels of search, a better balance between estimation accuracy and computation complexity can be obtained.

• • For the coarse search, the sparse search grid in the position and CCB domain may result in the loss of correlation peak for certain satellites. It is proposed to use CCB step size smaller than 300 m instead of the averaged correlogram to compensate for the correlation loss caused by the large horizontal step size necessary to cover the large space uncertainty. Computation effort will also be saved compared with using an averaged correlogram. A similar search strategy can be used for the medium search.

• • For the fine search, a fine grid is centred on the position-CCB estimate of the coarse or medium search and within small uncertainty. A 3D-Dichotomous search is used to save computation by evaluating only a small number of PDPC points and reducing the uncertainty iteratively.

Figure 5 demonstrates the uncertainty and search grids of the proposed 3-level multi-resolution CD search. With CCB step size smaller than 300 m, the estimation at coarse and medium level will be much more accurate because of high CCB resolution and low correlation loss. As a result, a very big overlap between the uncertainty of the current level and the step size of the previous level is no longer needed, so there is only a small overlap in the proposed scheme. It should be noted that the uncertainty and step size of the fine search is not shown very clearly, and will be given in Section 3.2. The analysis and search strategies of the coarse search and fine search are given in detail in Sections 3.1 and 3.2 respectively.

Figure 5.

Demonstration of uncertainty and search grids of the proposed 3-level multi-resolution CD search engine.

3.1. Coarse Search

In conventional A-GPS detection and positioning, the accuracy of the a priori information provided via GSM cellular networks is typically ±3 km in horizontal position, ±100 m in vertical position and ±2 s in reference time. Since the initial position is within 300 km, the 1 ms ambiguity problem has no impact on CD (Cheong et al., Reference Cheong, Wu and Dempster2012) and only the fractional pseudorange is critical to the process of position determination. So the possible clock biases can be assumed to be ±0·5 ms. The vertical uncertainty range is comparatively small and can be neglected for most applications on the Earth's surface.

The selection of search step size is critical to the computational load. Although using a very coarse search grid will reduce the computation load greatly, too coarse a search grid will lead to severe correlation loss and estimation error, which will mislead the next stage and produce invalid results.

The linear mapping from the position and CCB domains to the pseudorange domain is given by Equation (5). It is obvious that the contributions of position offset and CCB offset to the pseudorange are not equal, due to the difference in their respective coefficients. Notice that the coefficients of position offsets are dependent on the azimuth and elevation of the respective satellites, which differ from each other, while the coefficient of CCB is fixed. Furthermore, the coefficients of position offset are generally smaller than one and that of CCB is exactly one. This indicates the possibility of using different CCB step size and position step size to achieve higher code delay resolution and more accurate estimation.

In existing literature (Axelrad et al., Reference Axelrad, Bradely, Donna, Mitchell and Mohiuddin2011; Bradley and Axelrad, Reference Bradley and Axelrad2010) the CCB step size is set equal to the horizontal position step size in units of metres e.g. both horizontal position step size and CCB step size are set to be as large as 1000 m for the coarse search so as to cover the large uncertainty range of several kilometres. As we know, the auto-correlation peaks of the Pseudo Random Noise (PRN) codes have a 3-dB width of 1 chip, which equates to about 300 m in range. If the step sizes are set to be too big (i.e. the equivalent range exceeds 300 m), this will result in the possibility of missing the correlation peak of certain satellites via mapping. In general, it should be noted that the step sizes of the position and CCB grids must be sufficiently small to avoid excessive correlation losses but not too small, to allow computational tractability.

By further analysing Equation (5), it can be concluded that when mapping back to the correlogram of satellites, the minimum value among the four components of the summation limits the final resolution of code delay. Since the azimuth and elevation of the satellite continuously vary, it is impossible to get a fixed and accurate relationship between the minimum horizontal step size and CCB step size. However, it is clear that when the horizontal position step sizes must be set very large so as to cover a large uncertainty range without incurring huge computational load, the CCB step size can be set to be smaller than 300 m to obtain a higher range and CCB resolution, which will result in a more accurate position estimation as a by-product. For example, when the horizontal position step size is set to as large as 1000 m, the CCB step size can be limited to be 150 m. Figure 2 gives an example of PDPC in the position and CCB domains with 1000 m CCB and 150 m step size respectively. It shows that although the grid size in the position domain is not decreased, the accuracy of both position and CCB estimation can still be improved by decreasing the CCB step size.

Although Axelrad et al. (Reference Axelrad, Bradely, Donna, Mitchell and Mohiuddin2011) and Bradley and Axelrad (Reference Bradley and Axelrad2010) proposed to use an averaged correlogram to resolve the problem caused by excessive step size for coarse search, the signal-to-noise ratio of the averaged correlogram was decreased and it might not function properly in very weak signal conditions as the authors admitted; moreover, the averaging operation also increased the computation load greatly. Table 1 gives the computation load comparison of the three methods. For coarse search with different step size, since s _m<s_p, the number of position and CCB points needed to evaluate is increased by multiple times compared with using the same large step size in both position and CCB domains. But for coarse search with equal step size and averaging, although the number of points needed to evaluate is not increased, the computation for an individual PDPC point is increased by averaging f _s·s_p/c samples of each correlogram. The additional computation is huge compared with just increasing the number of points evaluated.

Table 1.

Coarse search computation.

(Horizontal uncertain range [-R,R], CCB uncertain range [-C,C] Horizontal step size s _p,s_m<s_p)

Figure 6 gives an example of PDPC under weak signal conditions with different CCB step size. It is shown that by just reducing the step size of CCB, not only is a higher resolution CCB estimate obtained, but also the quality of PDPC in the horizontal position domain is improved.

Figure 6.

Comparison of PDPC with different CCB step size.

3.2. Fine Search

PDPC in CD is multi-dimensional and non-linear, which makes it unfeasible to use gradient-based methods to estimate position and CCB. Since the evaluation of a large number of points in PDPC takes time, the search strategy is more important to increase the efficiency. Closas et al. (Reference Closas, Fernandez-Prades and Fernandez-Rubio2007) investigated the Space-Alternating Generalized Expectation Maximization (SAGE) algorithm, which sequentially approximates the MLE by dividing a multi-dimensional search into a sequence of single dimensional searches. Low-complexity as it is, SAGE is highly susceptible to noise as compared with other methods (Cheong, Reference Cheong2010).

There is a family of resolutions to one-dimensional unconstrained problems in engineering (Robert et al., Reference Robert, Virginia and Michael2000), which aims to find the minimum value of a unimodal function in some range, namely the Dichotomous search, Fibonacci search and Golden-section search etc. The Dichotomous search method has been used to locate the true discrete Fourier Transform peak in the one-dimensional frequency space (Zakharov and Tozer Reference Zakharov and Tozer1999; Aboutanios, Reference Aboutanios2004).

Based on the prior position estimated from the coarse search, it can be assumed that the PDPC is unimodal in a very small uncertain range. A 3-D Dichotomous search scheme is designed and shown in Table 2. Figure 7 gives a demonstration of the uncertainty and search grids of three iterations in a simplified 2-D space.

Figure 7.

Demonstration of uncertainty and search grids of simplified 2-D Dichotomous search.

Table 2.

3-D Dichotomous search.

Based on an initial uncertainty range [±E, ±N, ±C], the PDPC values on each sides of the initial maximum and itself, i.e., PDPC(east₀+E, north₀, CCB₀), PDPC(east₀-E, north₀, CCB₀), PDPC(east₀, north₀+N, CCB₀)…PDPC(east₀, north₀, CCB₀) are compared and the position estimation is adjusted midway toward the largest one. The uncertain range is then halved, and the PDPC values on each side of the new initial position are computed and compared to find out the new maximum and so on. The procedure is repeated for ‘numIter’ iterations. Table 3 gives the computation load comparison of the conventional fine search and 3-D Dichotomous search. For every iteration in a 3-D Dichotomous search, fewer than 24 points around the initial position are evaluated, taking into account the situation that some PDPC points around a certain point already have value from the former iterations. The number of iterations needed is decided according to the initial uncertainty and final resolution.

Table 3.

Fine search computation.

A case is used to demonstrate the performance of a 3-D Dichotomous search by comparing it with a conventional fine search (i.e. search with small step size). Both of them begin with the same coarse estimated position. In the example, the accurate position is set to be (0 m, 0 m) but the coarse estimated result is (300 m, −300 m). The fine search step size is set to be 25 m (in this stage, horizontal position step size and CCB step size set to be same), and the initial uncertainty range is set to be (−400 m, 400 m) (horizontal position uncertainty range and CCB uncertainty range are also set to be same). The 3-D Dichotomous search begins with a step size of 400 m in both position and CCB domains, which is half of the uncertainty range. In every iteration, both the uncertainty range and step size are reduced by half and finally the step size is reduced to 25 m, which is same as the resolution of fine search. Figures 8 to 10 demonstrate that the fine search centred on a coarse result ends up finding the fine result. In Figures 9 and 10, it is clearly demonstrated that the estimation converges in five steps from a coarse one to a fine one. Figure 8 shows the unimodality of PDPC under a normal SNR scenario in a small uncertainty range in addition.

Figure 8.

Fine PDPC in position domain.

Figure 9.

Position estimated by 3-D Dichotomous marked on the contour of fine PDPC in position domain.

Figure 10.

CCB estimated by 3-D Dichotomous marked on the fine PDPC in CCB domain.

4. EXPERIMENT

To study the multi-resolution CD algorithm in a real and controlled environment, live satellite signals with injected noise were used in an experiment. The live satellite signals were collected from a rooftop antenna using the Universal Software Radio Peripheral (USRP2), a software-reconfigurable Radio Frequency down converter and digitizer. The configuration of the hardware is shown in Table 4.

Table 4.

RF hardware configuration for USRP2.

The tracked C/N₀ and satellite geometry of the collected data set is given in Table 5 and Figure 11 respectively. The satellite geometry of the tracked satellite is a typical geometry in Sydney, Australia and the tracked C/N₀ of 7 satellites are unequal, which also reflect the true situation of a GPS receiver.

Figure 11.

Geometry of the seven tracked satellites.

Table 5.

Tracked C/N₀ of data set used in experiment.

Gaussian White Noise (AWGN) was injected uniformly to the raw complex baseband samples of the above signal set manually to simulate the low SNR scenarios.

Coarse and fine searches were implemented separately to compare the performance of different methods. For both stages, different methods were compared over 1000 independent 1 ms acquisitions of received data. The correlograms of satellites were simply computed with the frequency slice containing the highest correlation value so as to reduce the search in the Doppler frequency dimension. The vertical position domain search was neglected for simplicity. Although it is proved (Axelrad et al., Reference Axelrad, Bradely, Donna, Mitchell and Mohiuddin2011) that threshold-averaging yields better results than simply taking the location of peak power in the position and CCB domain as the solution, especially in low signal power cases, the single peak power location was used in all the experiments as the estimation because threshold-averaging may bias the estimated position to the centre of uncertainty range.

4.1. Coarse Search

The coarse search searches initially over a coarse grid centred on a random a priori position. The horizontal uncertainty range is set to be ±10 km and CCB uncertainty range is set to be ±150 km. The horizontal position step size is fixed to be 1 km for all the methods. For both coarse search with equal step size and coarse search with equal step size and averaging, 1 km CCB step size is used, namely 1 km and 1 km and 1 km and 1 km and averaging respectively. For coarse search with different step size, 150 m CCB step size is used, namely 1 km and 150 m. The Root Mean Square Error (RMSE) of both position estimation and CCB estimation for the three methods are plotted against the power of injected noise. And the position Root Mean Square Error (PRMSE) is defined as

(8)$$\xi = \left\| {\,p - \hat p} \right\| = \sqrt {(x - \hat x)^2 + (y - \hat y)^2 + (z - \hat z)^2} $$

being $\hat \rho = (\hat x,\hat y,\hat z)$ the estimated position vector of receiver, ρ=(x, y, z) the accurate position vector of the receiver and the operator ||·|| the L ²-norm of a vector.

Figure 12 compares the performance of the three methods. It is noticed that the position estimation error of 1 km and 150 m and 1 km and 1 km and averaging are far lower than that of 1 km and 1 km. For low signal to noise ratio (SNR) scenarios, 1 km and 150 m gives even lower position estimation error than 1 km and 1 km and averaging. Moreover, 1 km and 150 m outperforms the other two in CCB estimation accuracy.

Figure 12.

RMSE of coarse search vs. injected noise power.

Table 6 gives a rough comparison of average run time of three coarse search methods. The computation efficiency of 1 km and 150 m outperforms 1 km and 1 km and averaging although they have comparable estimation accuracy.

Table 6.

Average run time of coarse search(s).

4.2. Fine search

To demonstrate the effectiveness of a 3-D Dichotomous search, a fine search with small step size is also executed for 1000 times as a comparison. The PRMSE of 3-D Dichotomous search with five iterations and ten iterations are given. A random amount between (−300 m, +300 m) in the north and east and a fixed CCB value are used as the initial position (this reflects the true situation that the coarse search offers a coarse position estimation and a fine CCB estimation by using different step sizes in position and CCB domains). All the searches begin with the uncertainty range of ±400 m (with the overlapping of ±100 m). From Figure 13 it can be concluded that the estimation accuracy of a 3-D Dichotomous search is comparable with or even better than fine position estimation at low noise levels. But the PRMSE increases when the injected noise power is bigger because the cost function is no longer unimodal at low SNR. Also the estimation accuracy is improved only slightly by using more iterations because of the accumulated error. Table 7 shows that the computational load can be greatly reduced by using a 3-D Dichotomous search.

Figure 13.

RMSE of fine search vs. injected noise power.

Table 7.

Average run time of fine search(s)