Efficient and Innovative Techniques for Collective Acquisition of Weak GNSS Signals ()
1. Introduction
Due to the modernization of GNSS signals and the growing interest in navigation and positioning in harsh environments, the development of techniques and methods for weak satellite signal processing is on the rise. Significant techniques and technologies making mobile phones capable of determining their position have been developed recently in the positioning field. In urban environments, the use of GNSS receivers has increased considerably with the integration of GNSS chips in cellular phones and mobile devices which are used for potential applications in several areas. This geolocation service requires obtaining of high positioning accuracy and resolution of the various problems encountered in GNSS challenging environments. Navigation and positioning techniques become one of the most popular research and development topics with the coming of new satellite navigation Galileo and Beidou systems and the modernization of GPS and GLONASS systems, with new satellites, new frequencies and modern signals.
However, navigation and positioning in urban environment is still a great challenge, because the satellite signals are highly attenuated in urban area and can be affected by several sources of errors such as multipath problems, masking, jamming and interferences. It is almost impossible to acquire and track GNSS signals autonomously because of the importance of obstacles. Then, the receiver cannot calculate its position itself and it delivers a position often affected by an error of several tens of meters [1] .
GNSS signals are already weak (−130 dBm) when they attend the earth surface. So, the receiver should be more sensitive to be able to acquire the attenuated satellite signals. High Sensitivity (HS) receiver is required for GNSS positioning in hostile environment. Compared to a standard GNSS receiver, a HS receiver has to be able to perform correlation for longer times, and therefore, can acquire very weak satellite signals. Under the same conditions, HS receivers have to deliver a faster Time To First Fix (TTFF) and to do re-acquisition in a shorter time than standard receivers. In order to acquire GNSS signal with very low power, HS receivers use coherent and non-coherent integration, and some of them take advantage of massive parallel processing in order to dwell the receiver for longer periods of correlation [2] [3] [4] .
Although HS receivers are capable to acquire weak satellite signals, there are more problematic in deep urban environments compared to other challenged environments such as high attenuation, multipath, etc. So, only High Sensitivity receivers are not enough for deep urban positioning and navigation. Different techniques have been proposed that use some sort of assistance in addition to GNSS signals like Assisted GNSS (A-GNSS) and integrated INS/GNSS using inertial sensors (accelerometers, magnetometers and gyroscopes). In this paper, we are interested in positioning techniques that are based on GNSS signals using assistance information. The assistance data allow the GNSS receiver to reduce the search space by providing information such as satellite ephemeris, reference time and a priori position. Two major approaches to A-GNSS exist: MS-assisted and MS-based GNSS. MS (Mobile Station) designates the GNSS receiver. The position is computed at a server (reference station, RS) in MS-assisted GNSS whereas it is computed by the receiver itself in MS-based GNSS. In MS-assisted GNSS, the receiver only performs the signal acquisition and sends the measurements to the reference station [5] .
The concept of A-GNSS was inspired to develop the new approach of positioning using GNSS signals called as Collective Detection (CD) which is the aim of this paper. Collective Detection is an A-GNSS approach for direct positioning in which all information from satellites in view are combined in order to enable rapid acquisition.
Conventional GNSS receivers process different satellites individually, sequentially one by one, since each signal is treated independently at the acquisition level. In fact, satellite detection is based only on its own signal power and user’s dynamics. In conventional GNSS receiver, acquisition process is performed in code phase (or code delay) and Doppler frequency domain. However, in CD approach, the code phase search for all satellites in view is projected to a receiver position/clock bias grid and the satellite signals are not acquired individually but collectively, known as vector acquisition [3] [4] [5] [6] .
Collective Detection approach has been proposed recently to address positioning problems in non-ideal environments and there are not yet many researchers dealing with this subject compared to other positioning techniques. The vectorial acquisition concept has been developed in depth in [6] . This concept is mainly based on the use of assistance information from the base station to define the user position and clock bias uncertainty range. Then, many works using the vectorial approach were proposed for snapshot positioning with coarse accuracy. The main idea of this concept is to improve the overall acquisition sensitivity by combining coherently the detection metrics from all visible satellites [7] - [19] . Assistance information can be used to eliminate the requirement for GNSS data recovery and the receiver’s ability to increase integration time. Using CD, position solution can be obtained with signals at 20 dB-Hz of C/N0 [7] .
Various studies should be performed in the CD as reducing the complexity of the collaborative approach, increasing the sensitivity by using deeply the assistance information and minimizing as much as possible the assumed available information from the base station. In existing CD methods, the acquisition is performed by several iterations while refining the search space at each iteration until we can get an accurate estimate of the position [7] [8] . The CD approach is computationally intensive because of the important number of candidate points which makes its practical implementation very difficult.
Some approaches have been proposed to solve this complexity problem. For example in [7] , an averaged correlogram is used at the beginning of the search in order to accelerate the detection process. Some works consider the CD approach as an estimation problem. For example, [9] uses MLE (Maximum Likelihood Estimation) to get the position solution and [7] adopts the SAGE (Space Alternating Generalised Expectation-Maximisation) optimization algorithm to solve the problems. The MLE is approximated sequentially by dividing a multi-dimen- sional search into a sequence of single dimensional searches. In [9] [10] , in order to estimate the user position, a MLE is adopted by solving an optimization problem with sequential Monte Carlo methods. So, signal from different satellites are combined in the estimation process.
Since the first proposal of CD, all used a representation in Cartesian coordinates (North-East referential) for the horizontal position search space, a new representation in polar coordinates (Rho-Theta) was proposed in [11] [12] . It can decrease considerably the total number of points to evaluate.
Reducing the complexity by hybridizing the standard correlation with the CD in a multi-stage method has been proposed in [13] . It has been shown that the proposed technique could reduce the complexity without compromising the sensitivity of the receiver because it decreases after several iterations. Another technique for reducing complexity has been proposed in [14] by estimating roughly the clock bias in order to reduce the clock bias search range from 300 km to 100 m and estimating the coarse-time error as a fifth unknown in the navigation solution. This proposed method is called as Accelerated Collective Detection. In order to mitigate the large computational burden required by the traditional CD scheme, this method is based on the hypothesis that there is at least one strong GNSS signal and it is known. Otherwise, an improvement of the multi-resolution approach initiated in [7] was developed in [15] by using small clock bias spacing with large horizontal position step size to get a high time resolution and reduce the calculation load. To accelerate the collective detection process, the combination of the Bi-dimensional Parallel Search (BPS) acquisition method and the Spectral Peak Location (SPL) method of Doppler frequency estimation with delta correction is proposed in [16] . This proposed idea allows having a better result in terms of sensitivity and complexity for the CD approach. In [17] , the complexity reduction was demonstrated using polar coordinates while offering a new way to optimize the search grid resolutions.
Finally, a new approach has been proposed in [18] to handle the CD problem. They consider the acquisition problem as an optimization problem and solve the problem using an improved Pigeon-Inspired Optimization algorithm. A Swarm Intelligence algorithm is adopted in order to obtain the user’s relative position vector with good resolutions without searching the whole search space, and it considerably reduces the computational burden, but the sensitivity was compromised in that work.
The trade-off between complexity and sensitivity has always been critical in GNSS signal acquisition. Uncertainty in both code phase and Doppler search grid dimensions is the main reason for the difficulty in reaching this compromise. With a view to practical use of the CD approach, the performance of the developed algorithms must be tested with real GNSS signals. Thus, in this case the Doppler frequency shift must be taken into consideration. In this paper, techniques to increase receiver sensitivity while reducing complexity using the CD approach are proposed. The first method consists of hybridizing the CD approach with the conventional correlation approach and coupling it with a better technique for Doppler frequency estimate. SPL with delta-correction algorithm is used in order to improve the detection capabilities of the acquisition methods. For that, a new scheme with less computational load is proposed in order to accelerate the detection and location process. This proposal is compared with the direct positioning problem developed in literature. Then, high sensitivity acquisition techniques using long coherent integration and non-coherent integration are performed. Finally, the proposed algorithm will be applied with a mobile RS and an IGS service to test its feasibility as described in [19] .
The rest of this paper is structured as following. In section II, the Collective Detection principles are introduced. Then, the proposed methods to address the trade-off complexity-sensitivity are developed in the Section III with two case studies of CD applications. Section IV shows the performance analysis of the proposed methods with tests using real GPS signals. Finally, we conclude the paper with a discussion of other interesting work to be done on the CD approach.
2. Collective Detection
It has been shown that the Collective Detection is able to enhance signal detection sensitivity by several dBs. The satellite signals are acquired collectively but not individually on by one, and the code delay search for all visible satellites is mapped into a receiver position/clock bias search grid. The CD approach depends heavily on information data from assistance which is given to the MS with the way of defining a position and clock bias uncertainty range. The projection of the signal code phase to the position/clock bias domain is performed differentially with respect to the pseudo range measurements from the reference station. The CD performs the search in the space of receiver position relative to RS position and clock-bias. In fact, the search of the position solution is carried out around the base station with a known position.
A. Description of Collective detection
In conventional acquisition, the input signal is correlated with a local replica and the correlation power of a GNSS receiver corresponding to satellite k is expressed as:
(1)
with
is the input signal and represents the post-Doppler removal complex baseband signal such as :
(2)
where
is the signal vector of the satellite k,
is the code phase,
represents the AWGN (Additive White Gaussian Noise). In Equation (1),
and
represent respectively the signal local replica and the hypothesised code delay of satellite k.
First, in conventional acquisition the peak position of the correlation is estimated as the code delay of each acquired satellite. Then, the estimation of position and others parameters defined as a vector
is carried out. This vector includes three parameters of the estimation of receiver position
and one parameter of the estimation of common clock bias B.
can include other factors according to the parameters to be studied. The navigation solution can be obtained if the number of parameters to be estimated should be no more than the number parameters of satellites acquired. The fourth parameter of
, the common clock bias B, represents the timing difference between the local clock of the receiver and the synchronized clock of the satellite. An uncertainty space
is used to define the parameter
.
Based on this point of view, in CD approach the estimation of parameters is carried out by non-coherently summing the correlation power of all satellites in view computed for conventional acquisition and it is performed in position and clock-bias domain. Then,
(3)
where
represents the satellite position vector.
The ECEF (Earth-Centered Earth-Fixed) coordinates of the satellite k provided by the reference station are
. Then, the pseudo range corresponding to the satellite k can be obtained by the non-linear relationship between the receiver’s position and the code delay.
(4)
where
represents the noise on the phase rate measurement due to non- modelled termsand c being the speed of light.
The acquisition search grid is set in a space defined by 3D position coordinates
and clock bias
. The 3D position coordinates represent the algebraic distances between the receiver and the RS in North, East and Down directions, and the
represents the relative clock bias of receiver to the RS. In fact, Equation (4) is used to project the code delay in the individual detection metric (correlator output) corresponding to a given point in the position/clock bias domain for each satellite. Figure 1 shows the mapping of the signal code delay to the Position/clock bias domain of the user (MS) is done differentially with the respect to the pseudo range measurements
provided by the reference station (RS) for the satellite k.
For the satellite k, the pseudo range seen by the MS can be expressed as:
(5)
For CD, the uncertainty space
is centered on the initial position and clock bias. The accuracy of the initial knowledge is essential in the definition of the uncertainty space. If the pseudo range seen by the RS, at the center of the search space, is
for the satellite k, then the range-offset at a location separated by
from the RS is expressed in terms of the position and the clock bias:
Figure 1. Projection to position/clock bias domain in collective detection of each satellite.
(6)
where
is the azimuth of the satellite k and
is the elevation of the satellite k as seen by the RS(usually the same as for the MS). The coordinates
,
and
represent the 3D position displacement of the MS with respect to the RS in a North-East-Down (NED) local coordinate frame. The term
represents the pseudo range variation due to the clock bias of the MS, and
being the speed of light.
Then, the pseudo range can be converted to an equivalent code phase, at a hypothetical location
and a clock bias
, as :
(7)
where
is the estimated code phase for the satellite k,
is the signal spreading code period (i.e. 1 ms for GPS L1 C/A code),
is the number of code chips per period, and
represents the modulo
operation such that
chip.
Then, the individual detection metric, i.e. the correlator output value, corresponding to this satellite for these 4D coordinates can thus be effectively projected from code phase domain to the position/clock bias domain and calculated by:
(8)
where
corresponds to the correlation output at the code phase
for the satellite k. For all satellites in view, the individual detection metrics obtained for these 4D hypothetical coordinates
are then summed in order to obtain a single Collective Detection metric as:
(9)
Once the Collective Detection metric is carried out for all candidate points, many approaches can be followed to decide which set of values represents the best estimation of the true MS position coordinates and clock bias. If the Collective Detection metric exceeds a pre-defined threshold, the satellite signal could be detected. Then, the method developed in [12] is used to obtain the code phase and Doppler frequency corresponding to the detected signal.
According to Equation (7), the estimation of the code delay for each satellite requires several information from the reference station, such as the RS position for setting the initial MS spatial uncertainty, the pseudo range measurements for all satellites in view as seen from the RS, ephemeris to extract the necessary parameters in order to compute the expected satellite azimuth and elevation angles. The implementation of the CD requires other information provided by the reference station, such as the reference frequency to calibrate the MS oscillator and compensate the oscillator Doppler offset component.
The benefit of the application of the CD approach is shown in Equations (8) and (9). In fact, weak signals may not be detectable in conventional receivers with only individual correlator output value given by the Equation (8). However good, the accumulation of all individual correlation values for each satellite in view can increase the receiver sensitivity using Equation (9) in which the summation operator represents the term “Collective” in the Collective Detection.
The function block diagram of the Collective Detection approach is shown in Figure 2. It is composed mainly of two components, the satellite detection (acquisition) and the position estimation part.
B. CD as a direct positioning and High Sensitivity problem
The Collective Detection technique has been proposed, because of its performance as both a Direct Positioning (DP) method, providing a coarse position/clock bias solution directly from acquisition, and High-Sensitivity (HS) acquisition method, by application of vector detection of all satellites in view.
Direct Positioning Estimation has been introduced in [20] [21] . There are two steps in conventional position estimation: the receiver first estimates the synchronization parameters of the visible satellites and then performs a position estimation with that information. In contrast to the conventional method, the DP introduced the concept of position-based synchronization in one step in which the synchronization parameters can be covered from a user position estimation. And ML estimator of position in the framework of GNSS is obtained. A sequential Monte Carlo method is used to solve the optimization problem. It is shown that this method can mitigate multipath and jamming interferences. A Cramér- Rao Bound of position for both conventional and DPE approaches is presented in [22] in order to show DPE is better compared to the conventional one. Despite the effectiveness of the DPE technique, its implementation within a GNSS receiver remains a great difficulty since these works are still theoretical and very general. However, we will still use the results obtained in these works to compare the results using our CD algorithms.
Figure 2. Block diagram of collective detection.
The idea of direct estimation of the position computation in a single step without going through the tracking step and the decoding of the navigation data is the basis idea of the CD approach, which is why it is considered as a method of direct positioning. In fact, for weak satellite signals, the navigation messages cannot be decoded, hence we must find other alternatives to the determination of the navigation solution by following all the steps like the conventional receivers. Direct Positioning algorithms are based on a set of individual correlogram formed by code delay/Doppler for the satellites potentially visible. CD is able to provide for the MS a first coarse estimate of position and clock bias in situations where the individual satellite signal cannot be acquired and/or tracked. From what we have seen in the previous section, the accuracy of parameter estimates is highly dependent on the available a priori information and especially the geometry of the satellites in view. It has been shown that the positioning error of the CD approach depends on the number of visible satellites, their geometry and signal power; and the CD metric is driven by the stronger signals. Some CD works have shown that the mean horizontal positioning error is within a few tens of meters at best [13] . The positioning error depends on the code phase resolution. For example, for an error of 0.5 chips in the code phase estimation (equivalent to 150 m in pseudo range for L1 C/A), a position error of 30 m may still be within the correct code phase estimation region [17] .
Contrary to the conventional technique, in CD approach all satellite signals are used even if they are very weak. In fact, the objective of CD as a vector acquisition approach is its ability to use stronger signals to facilitate the acquisition of the weaker ones. The number of satellite signals and the relation between their strengths (C/N0, carrier-to-noise ratio level) are essential to analyze the performance of CD as an HS acquisition technique. The positioning error of the CD depends on the number of satellites in view, their geometric configuration, and the signals power.
C. Correlation process in CD
Within overall CD process, the correlation step is performed after establishment of uncertainty range of position/clock bias and estimation of code delay corresponding to each of 4D candidate point in position-time search grid. This step consists in performing the correlation between the incoming satellite signal received by the MS and the signal locally generated for all satellites in view using the code delay estimated previously which is itself based on the pseudo range seen by the RS and each candidate point. This correlation process using FFT technique is shown in the block diagram of the CD in Figure 2.
First, the acquisition process is required to detect all visible satellites. The acquisition grid represents a discretization of two-dimension search space of the code phase and the Doppler frequency.
Then, the correlation method defines the process in which two-dimensional search grid is scanned for obtaining the target set of
values. The aim is to find the parameters
that are the closest to the incoming signal ones. There are four main correlation methods: the Serial or Sequential Search (SS), the Parallel Frequency Search (PFS), the Parallel Code Search (PCS) and Bi-dimensional Parallel Search (BPS) [2] . The parallelization concept is carried out using FFT method. These methods are used as appropriate as there is always a compromise but the important criterion is the number of operations. For the PFS scheme, the number of operations required is reduced to
. And for the PCS, the number of operations is reduced to
. As we see in Figure 2, the PCS acquisition method is used in the CD algorithm.
D. Collective Detection metrics of performance
As a high-sensitivity acquisition method, CD is characterized by two major performance metrics: sensitivity and complexity. And, as a direct positioning method, it is characterized by three major metrics: position error, time to first fix (TTFF) and complexity. These performance metrics are summarized in Table 1. They are all related to the search grid resolution.
It can be deduced that the largest issue to be resolved is the trade-off between the search grid resolution and the total number of candidate points to be analyzed. On the one hand, the search grid resolution must be fine enough to have a higher sensitivity and a lower position error. On the other hand, the number of
Table 1. Performance metrics of collective detection approach [17] .
candidate points has a direct effect on the TTFF and the complexity of the algorithm. The CD approach requires a very high calculation load because of the important number of candidate points which makes its practical implementation very difficult. For example, in [7] there are nearly 31 million candidate points to estimate the user position with ±150 km clock bias search range and ±3 km, ±3 km, ±600 m for the search range in north, east and down directions.
In addition, despite its effectiveness in treating satellite signals in non-ideal environments, there is a large positioning error in the direct positioning approach compared to the conventional positioning method. Depending on the geometry of the satellites and the signal strength, the error can be up to hundreds of meters, which is not interesting for certain applications that require positioning accuracy.
This paper offers some techniques to address these problems of the CD, while reducing the complexity that is the main obstacle to its practical implementation and increasing sensitivity as efficient and innovative techniques for CD.
3. Efficient and Innovative Techniques for CD
We have already seen in the introduction the different works carried out on CD approach which deal with complexity reduction, sensitivity increasing and position error reduction.
In CD, the correlation’s resolution depends on the position grid resolution search of the last iteration. In the literature on the CD using the multi-iteration method for solving the position, we notice that there are solution that is based on 3 iterations [7] [9] [10] [11] [12] [13] and there are others that use 4 iterations [14] . In this paper, in order to get a better estimate of the position, we use a resolution of 10 m in the third iteration, so the change of the estimated code phase between two closest candidates is located in 1/16 chips, i.e. 18.75 m (9.375 m from each side of search). This is enough as a fine resolution to estimate the user position. However, using such a resolution with the search dimensions used in the literature requires a very high computational load. For example, [7] uses a resolution of 30 m in the last iteration, which requires 3 times less research on this latest iteration compared to ours. Thus, some techniques must be implemented to reduce this large number of operations so that we can apply our proposal in order to have a better solution estimate.
In this paper, the Doppler frequency shift is taken into consideration in correlation process. Thus, another loop of frequency search is added to properly estimate the Doppler frequency.
In order to reduce operation costs in CD approach, a new scheme of hybrid method of Collective Detection with conventional High-Sensitivity correlation is proposed. The concept of High Sensitivity is ensured by the use of a better Doppler estimation technique and the variation of coherent integration periods and non-coherent accumulation. This technique of frequency estimation makes it possible to reduce the information required from the reference station, which minimizes the dependency on assistance.
So, Figure 3 shows the new architecture of the proposed CD algorithm which is a new scheme of hybrid CD with conventional acquisition in 3 iterations, coupled with a technique to better estimate the Doppler frequency. The ability to properly estimate the Doppler offset allows for having a sensitivity gain and reduces the algorithm computational load because of the reduction of the frequency uncertainty area. The proposed hybrid CD algorithm makes it possible to solve the problem of sensitivity, complexity, positioning accuracy and the minimization of assistance dependence. The proposed approach is called “Effi-
Figure 3. New scheme of hybrid CD with conventional acquisition (EITHSCD).
cient and Innovative Techniques for High-Sensitivity Collective Detection” (EITHSCD).
A. Hybrid of Collective Detection with conventional acquisition
The idea of using a hybrid method of CD with conventional acquisition has already been proposed in some works [10] [13] [17] , but each approach treats the subject differently. Note that one or more strong signals can be present in challenged environments. The number of strong signals depends on the user location but the presence of these signals greatly helps the performance of CD process. Then, the idea is to take advantage of the strong signals to improve CD performance.
In [10] , the proposed hybrid method is used to reduce the search space of CD by employing SVD of the geometry matrix in order to subtract the contribution of the strong signals. A better position solution and lower computation load are achieved with this approach. Otherwise, works in [17] consist of taking advantage of the fact that it is desirable to make use strong signals in order to optimize the CD search process. Compared to the full CD method, the author of [17] has shown that the hybrid detection methods can detect much weaker signals and significantly reduce the final positioning error using the same signal integration time, number of signals, and satellite geometry. He has shown the improvement in the search grid resolution in the presence of one, two or three strong signals.
In this work, the main idea of hybrid method developed in [13] is used for its ability to dramatically reduce the number of operations throughout the position estimation process. The concept of multi-resolution is adopted and it requires a down sampling of the received signal before calculation of individual detection metric for each iteration. It is proved in [13] that the developed method has higher efficiency in terms of complexity compared to traditional CD [7] , but the disadvantage of this method is that the sensitivity decreases after several iterations. Thus, to overcome the sensitivity problem, this work proposes the use of an efficient technique to better estimate the Doppler frequency. In fact, the proposed acquisition method allows improving the accuracy of the Doppler estimation through FFT, and therefore enhancing the correlation energy.
Note that CD approach requires a high resolution in the correlation block in the last iteration. Thus, there is no need for a better resolution in the 1st iteration in order to avoid the high computational load, a correlation of 1 sample per chip is enough with a position domain resolution of 1 km. Individual detection metric for all satellites in view and CD metric are computed in order to have a rough estimate of the user position and an estimated code phase of each visible satellite. Then, a new correlation around the estimated code phase is performed using a window
with 4 samples per chip resolution, i.e. w/2 on both sides of the estimated code phase and shifted by a sample period
at each correlation. In the same way, it carries out the calculation of individual detection and CD metrics, then a new code phase is estimated for each satellite. A new correlation around the estimated code phase is performed, with a resolution of 16 samples per chip in the 3rd o obtain a final position accuracy of 10 m.
The key point is then the choice of the value of
to have a good estimate of the code during the correlation process but also to optimize the computational load. This method considerably reduces the number of calculations compared to different approaches developed in literature, for example compared to [7] which initiated the use of the multi-iterations approach.
B. Coherent integration and non-coherent accumulation
In order to acquire satellite signal with very low power, HS receivers use long coherent and non-coherent integration, and some of them take advantage of massive parallel processing in order to dwell the receiver for longer periods of correlation. Equation (9) shows the advantage of using the CD by non-coher- ently combining all visible satellites in order to increase signal power. The signal power becomes increasingly higher by accumulating more satellites, and this facilitates the estimation of the position. In other words, the use of CD is advantageous in the presence of several satellites.
However, long integration process is limited by several challenges, such as the possible transitions in the navigation data bit every 20 ms for GPS L1 C/A. In addition, knowing that the Doppler shift increases with the coherent integration time, its inaccurate estimate may severely decrease the correlation power. And this inaccuracy can cause non-detection of weak GNSS signals. Thus, a technique capable of having a better estimate of Doppler is needed if we want to have a good sensitivity gain in CD.
C. New method for Doppler estimation
In order to improve the performance of the receiver in terms of sensitivity, several approaches have been developed. For conventional sequential acquisition, increasing the coherent integration period and non-coherent accumulation is the basic key. For the multi-satellite approach, different techniques have been proposed. For example, [23] proposed a correlator-based fast multi-satellite maximum likelihood algorithm to achieve fast acquisition and provide higher sensitivity for weak signals.
We have seen in the previous section that the sensitivity decreases after several iterations using the hybrid method developed in [13] . So, in this paper, the approach used to solve the problem of sensitivity into the CD process is the implementation of a better technique of Doppler estimate. At the same time, it also reduces the computational burden by reducing the frequency search space. Its ability to combine High Sensitivity and low complexity has been proven in [16] .
The Doppler frequency shift must be taken into consideration in the case of real GNSS signals. In this work, another loop of frequency search is added to conduct the search on Doppler frequency and then to better estimate it. In this case, the carrier is not eliminated in the processed satellite signal.
The objective of this proposal is to achieve a better estimate (fine estimation) of Doppler frequency and also can reduce the dimension of uncertainty area.
Based on architecture in Figure 3, the ephemerides allow to calculate satellite velocity. The way to measure the Doppler and work in velocity domain was developed in [24] .
The measured Doppler frequency has the following relationship with the satellite and user velocity:
(10)
where k represents the satellite number (
),
represents the wavelength of transmitted satellite signal,
and
are respectively the user and the satellite ECEF velocities,
represents the direction unit vector from the satellite to the receiver, and
represents the receiver clock drift.
Note that the main sources of performance degradation of the GNSS acquisition are the uncertainty on the acquisition search grid (code phase and Doppler frequency), the non-compensation of the code Doppler and the presence of bit sign transition (for the modernized GNSS signals: data bit transition on the data component and secondary code bit transition on the pilot component). In this work, we especially focus on the choice of the Doppler search grid value in order to have a better estimate of the Doppler. In fact, the wrong choice of the cell width in acquisition search grid can cause residual estimation errors there. Knowing that the Doppler shift increases with the coherent integration period, it does not change too much in the case of low dynamics or short integration times. An integration interval of 1 ms (1023 chips) requires a residual frequency of less than 500 Hz, and for 20 ms of coherent integration the residual frequency must be less than 25 Hz. Thus, there is a big challenge with a very long integration period, nevertheless, it is the best way to enhance the acquisition sensitivity. The proposed way to better estimate the Doppler frequency within the CD approach is performed in the architecture in Figure 3.
The main sources of frequency offset for GNSS receivers are the satellite motion (±4880 Hz), the uncompensated user motion (±190 Hz) and the oscillator deviation (±440 Hz for ±0.28 ppm) [25] .
If
and
are respectively the uncertainty width in the frequency search space and the uncertainty width in the code delay search space for the satellite k and assuming that the sign of the navigation data bit does not change throughout the period of coherent integration, then the correlation output can be approximated as [26] :
(11)
where
is the autocorrelation function of the signal spreading code evaluated at the code phase offset
between the true and candidate code phase
,
is the offset between the true and candidate carrier frequencies
,
represents the coherent integration time and
represents the resulting noise component.
The code phase and Doppler offsets on the correlation process are used to establish the search grid resolution. So, the grid resolution for the code is
, where
represents the code phase uncertainty dimension,
represents the number of search bins and usually equals to the number of samples per code
, and
represents the length of the code in chips. As seen in the previous section, the possibility of having a better estimate of the Doppler frequency can address the trade-off between sensitivity and complexity of the receiver; and it concerns the setting of the grid resolution for the frequency dimension. In fact, the maximum tolerable loss for the sensitivity performance and the number of search bins to be tested for the complexity problem. These parameters have to be considered. So, the resolution of the FFT search grid is
, where
represents the signal sampling frequency and
represents the data length. Knowing that the maximum frequency offset is half the spacing between cells, so the maximum frequency estimation error is
.
In this paper, Spectral Peak Location (SPL) algorithms are proposed because of its ability to better estimate the Doppler frequency. The capacity of the SPL algorithm to improve the accuracy of FFT frequency estimation has been demonstrated in [26] [27] . This technique can reduce the FFT-derived losses in the coherent processing output is called as. The basic principle of SPL estimators is to have the estimate of the spectral peak index,
, which is based on three consecutive FFT samples:
,
and
. If
is the FFT output at index i, and
represents the frequency bin which produces the highest magnitude FFT output, for a given signal
, the spectral analysis of the three consecutive FFT samples around
as:
(12)
In order to determine the fine
estimate, a fractional correction term,
, is calculated and added to the
index. This technique is called “delta-correc- tion technique” because of the “delta” term which is applied in FFT acquisition. Then,
can be expressed by
. The delta-correction term chosen for the SPL estimators in this paper is the delta term used in [28] .
In this work, the delta-corrected frequency is expressed as
, where
is the frequency correction term as calculated by
, and
obtained in [28] . Thus, the delta-corrected coherent output is defined as:
(13)
(14)
Finally, the CD metric for all visible satellites is expressed as:
(15)
The implementation of the proposed EITHSCD algorithm presented in Figure 3 involves in three steps, corresponding to three iterations:
(1) In the first iteration, there is no need for a better resolution in order to avoid the high computational burden, a correlation of 1 sample per chip is enough with a position domain resolution of 1 km. Individual detection metric for each visible satellite is the correlation value corresponding to the estimated code phase and Doppler frequency. Then, the CD metric for all satellites in view is computed to have a coarse estimate of the user position and an estimated code phase of each visible satellite. It is calculated by summing non-coherently all individual metrics corresponding to the estimated code phase and Doppler. The distinct peak is identified and is used to center the solution process for medium search in the second iteration.
(2) In the second iteration, a new correlation is performed using sequential search around the estimated code phase using a window
with 4 samples per chip resolution. The correlation process is carried out in an interval between
and
and shifted by a sample period
at each correlation. The individual detection corresponds to the estimated code phase within
on both sides and the fixed Doppler frequency estimated in the first correlation. Then, CD metric is computed by summing all correlation values for all visible satellites. A position domain resolution of 100 m is established in order to have a medium grid resolution search. A new code phase can be estimated for each satellite from the correlogram of CD metric which is required in the third iteration process. The search space is re-center on the location where a distinct peak is identified and it is used to perform fine search in the last iteration.
(3) In the last iteration, a new correlation is performed using sequential search around the estimated code phase in second iteration. In order to have a fine estimate, a resolution of 16 samples per chip is used to obtain a final position accuracy of 10 m. The rest of the process remains the same as in the second iteration, i.e. individual detection and CD metrics are calculated with the estimated code phase resulting by correlations around the last iteration around estimated code phase during the second iteration. Position and clock bias of the MS is estimated with regard to the RS. Code phase of the MS for each visible satellite can be obtained.
4. Performance Analysis
To analyze the performance of the proposed CD algorithm, tests with simulated and real signals have been performed. For a better comparison of the proposed algorithm with algorithms developed in the literature, performance analysis in terms of sensitivity, complexity and accuracy are carried out. In most cases, the CD approach developed in [7] is used as a reference approach since it is one of the earliest works on the Collective Detection concept.
A. Simulated signals experiments
To study the performance of the new scheme of hybrid CD with conventional acquisition presented in the proposed EITHSCD architecture in Figure 3, simulated satellite signals in Matlabare used.
The RS is located at ETS Montreal. To facilitate the simulation conditions, the true position of the MS in 4D coordinates (
) w.r.t. the RS is set to be (0, 0, 0, 0), which is centered at RS.
The other simulation parameters used for this test are:
- RS coordinates: N 45˚49'40.350527", W 73˚56'27.701694", 73.899 m
- Mask angle: 10˚
- GDOP: 1 (in order to have a better constellation geometry)
- Search grid description: defined in Table 2
- Window w value: 1
- AWGN noise injected
Table 2 summarizes the values we used for the range and spacing of each component for rough, medium and fine search level during three iterations.
After launching the algorithm, there are 10 satellites in view. This means that there are 10 code phase to estimate. In the algorithm, a satellite is declared visible if the difference between the estimated code phase and the true code phase is less than half the sampling factor which is 16 in our case.
To better analyze the performance of the proposed technique EITHSCD, the conventional CD approach proposed in [7] is used as a reference. First, in order to get and compare the statistical characteristics of results obtained from both algorithms, each algorithm is executed 100 times. For C/N0 = 35 dB-Hz, both approaches find 10 visible satellites. Table 3 shows the mean error and the standard deviation of the difference between the estimated code phase and the true code phase. This makes it possible to analyze the number of correctly estimated code phases.
Table 2. Description of search space for CD process.
Table 3. Comparison of statistical results between EITHSCD and reference approach.
From Table 3, it can be seen that the value of the mean of the difference between the estimated code phase and the true code phase corresponding to the proposed algorithm is always lower than the value of reference approach. Even if the values obtained for the reference approach are still below the threshold and involves the detection of the satellite, it shows that EITHSCD technique offers a better accuracy.
According to the concept of the Collective Detection as a HS acquisition method, the aim of CD approach is to facilitate the acquisition of weak signals by using strong signals. So, to analyze the receiver performance in terms of sensitivity, the probability of detection in function of C/N0 level has to be explored. Thus, three different scenarios are analyzed for both approaches depending on the number of satellites and their power as seen in Table 4.
Each scenario is tested with 1000 independent blocks of 1 ms and 10 ms GPS L1 C/A. Coherent integration during 10 ms is performed in order to increase the sensitivity. Figures 4(a)-(c) show respectively the CD sensitivity analysis corresponding to the three scenarios for both approaches. These curves represent the probability of detection in function of C/N0 after the third iteration.
From Figure 4, it can be seen that using the EITHSCD algorithm the receiver is able to get out a good correlation peak in order to detect the weak satellite signal. EITHSCD approach is very beneficial for short signals of 1 ms in which the difference is very noticeable.
The last comparison for both approaches is the complexity of the algorithm. Ten satellite signals of 35 dB-Hz are simulated to compare some CD approaches. Table 5 presents the performance comparison in terms of computation burden.
We can see that the number of candidate points of the proposed EITHSCD approach is lower than the reference approach. EITHSCD algorithm has a com-
Table 4. Scenarios used in simulation tests.
Table 5. Computational load between some CD approaches.
(a)(b)(c)
Figure 4. Comparison of EITHSCD and reference approach in sensitivity performance. (a) Scenario 1; (b) Scenario 2; (c) Scenario 3.
putational load 4.84 times lower than the CD algorithm developed in the reference approach [7] , 1.37 times faster than the Accelerated CD approach developed in [14] , and 1.07 times lower than the ECPIOCD approach developed in [18] .
Table 6 shows the comparison of the horizontal positioning error (95%) between the EITHSCD algorithm and the reference approach by using good and bad GDOPgiven that the geometric configuration of satellites is essential in the receiver position estimation. Signal power of 20 dB-Hz and 30 dB-Hz are varied to investigate the effect.
Results show that we obtain a better estimate of the position of the MS compared to that obtained by the reference approach. These results of position accuracy are obtained using 1000 acquisitions for varying signal levels and satellite geometries.
B. Real signal experiments
To analyze the performance of the EITHSCD algorithm, tests with real signals were performed. Figure 5 shows the setup used to test the effectiveness of the algorithm with real signals and measurements using good quality receivers. A Septentrio PolaRx3e TR Pro receiver was used as a RS to collect series of mea-
Figure 5. Setup of CD process and real signal acquisition (NordNav R30 as MS & Septentrio PolaRx3e as RS).
Table 6. Horizontal positioning error, 95% [m].
surements. The antenna of this receiver was fixed on the roof of the French Institute of Aeronautics and Space (ISAE). And a NordNav R30 was used to collect raw data inside the building of the navigation lab, near the window, at ISAE wherein the acquisition of the satellite signals is difficult. The horizontal uncertainty range (North/East) was set to 20 km to reflect a realistic application scenario as shown in Table 2.
Table 7 summarizes the various parameters used to perform the test. Using the configurations and settings in Table 7, Figure 6 shows all satellites in view during the setup (above 10˚ elevation). The sky plot represents the geometry of the nine detected satellites, with a GDOP around 2.5.
Figure 6. Satellite geometry of the indoor scenario test.
Table 7. Parameters used for real signal tests.
Table 8 shows the measurements data obtained by the RS receiver during the setup such as mean C/N0 and mean Doppler offset for all satellites in view shown in Figure 6.
In the EITHSCD algorithm, an SPL delta-corrected FFT for a middle-bin offset is used. Consider a Doppler range of ±10 kHz. 1 ms of signal observation is used, i.e. the number of samples per code period is
. This is equivalent to the number of code bins to be scanned and there are a total of approximately 1.8E5 cells to be scanned in code domain for each satellite in view.
Considering a maximum attenuation of the detection metric of 0.3 dB corresponding to the performance of PCS acquisition method, then
.
To better analyze the performance of algorithm in terms of sensitivity, it is important to see the ratio between the maximum peak and the average of the remaining peaks for each detected satellite. This makes it possible to see the ability of the algorithm to get out the weak signals among the different peaks formed because of the noises. Figure 7 shows the value of the ratio between maximum peak and median CAF.
Figure 7. Ratio of maximum peak over average remaining peaks.
Table 8. Power level and Doppler offset for all visible satellites.
The curves in Figure 7 show that the values of the ratio between the maximum peak and the remaining peaks of the EITHSCD algorithm are higher than the ratio value of the reference approach. These curves show that the receiver is able to get out a good correlation peak in order to detect the weak signal with the EITHSCD algorithm thanks to the SPL technique with delta correction for Doppler estimation.
The EITHSCD algorithm allows to have better correlation peaks compared to the reference approach. The sensitivity gain for this parameter is summarized in Table 9 for each satellite.
It can be seen that the gain is always positive for all satellites. Furthermore, the difference of the ratio value is noticeable for weak signals such as PRN 7 and PRN 19. Note that the highest gain corresponds to the PRN 7 which is the lowest satellite signal with 37.25 dB-Hz mean C/N0 level (yellow part in Table 9). This result shows clearly the effect of the delta-corrected technique on the improvement of the detection of GNSS signal. On the other hand, PRN 21 has also low C/N0 level but the difference is not very great because of the elevation angle which is not favorable for this satellite. The minimum gain value (5.47%) corresponds to PRN 18 because of its position. Thus, some parameters can affect the result. The average value of gain for all satellites is 10.26%. There is a better gain of 23.1% for the PRN 7 since it is in a good condition to profit from the delta-corrected acquisition method because its mean Doppler offset is close to a mid-bin frequency value despite its low C/N0 level.
Table 10 shows the comparison between EITHSCD algorithm and some CD approaches in these CD approaches treat the problem of complexity.
The number of point to be scanned is 175,032. Compared to other methods in literature, this value is lower. Note that the number of candidate points is the same as using simulated signals, the difference is in the execution time of the algorithm. The execution of the algorithm is 4.46 times faster compared to the reference approach with real GPS signals, therefore reduces the complexity. These results show that the application of the SPL delta-corrected FFT method within the hybrid CD approach allows to have a better performance in terms of
Table 9. Sensitivity gain for EITHSCD algorithm w.r.t the reference approach.
Table 10. Computational load between some CD approaches.
complexity and sensitivity acquisition. The CD approaches developed in [14] and [18] appear to have good performance compared to the reference approach in [7] in terms of complexity, but the advantage of EITHSCD lies in the fact that it is also capable of increasing the sensitivity of receiver.
Apart from this, the EITHSCD also makes it possible to have a better accuracy of the position solution. Based on the same parameters in Table 7 and Table 8, Table 11 summarizes the results obtained by both approaches to compare their performance.
It can be seen that the accuracy is improved because of the increased sampling rate, but complexity is increased. This compromise is precisely solved by the multi-iteration hybrid approach of conventional correlation with CD approach. Figure 8 shows the cumulative histograms of HPE (North and East) for all visible satellites obtained with mask angle of 10˚. The maximum pseudo range error is 9.3 m.
The histogram in Figure 8 is limited to 100 m positioning error but it is possible to obtain HPE of several hundreds of meters for very poor constellation configurations, i.e. when the satellites are very close to each other which is the case of positioning in challenged environments. In fact, there is just a small part of the sky is visible to the user. Figure 9 shows the error of the solution accuracy
Figure 8. Histogram of snapshot horizontal positioning errors for all satellites in view.
Table 11. Performance comparison between EITHSCD and reference approach.
Figure 9. Position error obtained from EITHSCD algorithm.
on the ISAE map at the end of the recording scenario. This result shows that the position solution obtained is not poor in view of the technique used for direct positioning knowing that the other CD approaches in literature make it possible to have a greater error using the same simulation and test parameters.
Note that the accuracy of EITHSCD algorithm is limited by the level of visible satellites. In fact, if all received satellites are very low, the positioning error is great, but we can always have a complexity gain compared to other approaches.
Furthermore, the proposed technique is not suggested for applications requiring centimeter or millimeter accuracy due to the positioning error but is reasonable for others. In fact, the CD technique is not accurate compared to other positioning approaches but it is interesting if the satellite signals are very weak and the receiver is not able to detect the navigation messages.
C. Application of EITHSCD with mobile RS and IGS service
Finally, EITHSCD algorithm is tested with a CD scenario using a mobile RS and an IGS reference station. Application of a mobile RS and IGS service in CD approach are developed in [19] .
First, scenario of mobile RS and MS simulated on Spirent simulator is tested in order to analyze the feasibility of the EITHSCD algorithm. The RS dynamics and integration period are varied. The different position changes of the RS (5 m, 10 m, 100 m and 1 km) do not impact the probability of detection of weak signals. The results show that it is possible to apply the EITHSCD algorithm since the mobility of the RS has no effect on CD process.
The other application to test the feasibility of the EITHSCD algorithm is the use of an IGS reference station. The nearest reference station in Ottawa Canada (N 45˚27'14.985792", W 75˚37'25.784497", 83.601 m) is used to test the efficiency of the EITHSCD algorithm. In order to estimate roughly the user position, reference station position and ephemeris (to compute all visible satellites coordinates, azimuth and elevation angles) are obtained with IGS service to update the data sets in the MS. There are 7 visible satellites during observation period: PRN 2 (35 dB-Hz), PRN 5 (46 dB-Hz), PRN 13 (35 dB-Hz), PRN 15 (32 dB-Hz), PRN 20 (41 dB-Hz), PRN 21 (31 dB-Hz), PRN 29 (44 dB-Hz). Applying EITHSCD algorithm, the obtained mean positioning error value is 17.46 m. With 1 ms of signal, a clear peak around the MS true location
can be seen in the CD metric plot which is impossible with the conventional FFT individual acquisition. This shows the advantage of using IGS service with EITHSCD algorithm. In fact, the individual signals are undetected on their own even if there is 7 satellites in view and it is quite probable of not having a stable PVT because of the low level of C/N0.
5. Conclusions
By carrying out this work, the core problems of the CD approach can be solved. It has been demonstrated that the proposed EITHSCD algorithm offers better gain of complexity reduction and increased sensitivity according to the typical CD approach. Similarly, a good improvement of the position solution was obtained thanks to the application of this algorithm. The minimization of reliance on assistance information sent by the RS is also addressed. In the EITHSCD algorithm, a new hybrid scheme of collective detection with the conventional correlation approach coupled with a better technique for Doppler frequency estimate is proposed to address the high computational burden, the low sensitivity, the large positioning error and the deep dependence on assistance data. SPL technique with delta-correction is used for frequency estimate within the hybridization CD scheme in order to have a better performance of the proposed algorithm.
The proposed EITHSCD scheme has been compared to traditional CD approach. Experiments with simulated satellite signals have been conducted on both approaches. Results shown that the proposed method is capable of detecting weaker signals, able to process the whole step of position estimation faster, capable of having a low error in the positioning solution. Real signals with real measurements are also used to compare both CD approaches in an indoor scenario. The results show that the EITHSCD outperforms the reference approach in terms of sensitivity, efficiency and accuracy. The number of candidate points is considerably reduced compared to the reference. Similarly, the accuracy of the final solution is also improved. Based on all performance metrics of CD technique, the proposed EITHSCD method is much more efficient than the traditional CD approach. Apart from the Doppler offset value, the choice of the window w greatly affects the performance of the proposed algorithm.
Variation of coherent integration and non-coherent is also conducted to show the receiver sensitivity. Applications of the EITHSCD with mobile RS and IGS service have been also presented to show its efficiency and feasibility.
With these good results, practical use of the CD approach will become increasingly feasible. In addition, we will be able to make good use of the various GNSS satellites to create a multi-frequency/multi-constellation receiver. Using cognitive radio technology to exploit the best satellites within CD approach will be the focus of our future works and it will lead to new lines of research in the CD field.
This work helps reduce costs associated with the installation of additional positioning equipment in GNSS denied environments.
Acknowledgements
This work is funded by Natural Sciences and Engineering Research Council of Canada (NSERC) as part of the research program “Cognitive multi-antenna GNSS/INS Receiver Architectures and Methods for Indoor-Denied Navigation”. The authors appreciate the contributions of the ISAE team for the GPS signals collected in ISAE SupAero Campus using different equipment.