RAIM Algorithm Based on Residual Separation

Abstract

With the rapid development of Global Navigation Satellite Systems (GPS, BDS, GALILEO and GLONASS), the number of available satellites is increasing. The redundancy of GNSS is enhanced. This will offer the possibility of realizing receiver fault detection and exclusion (FDE). Due to factors such as satellite fault and strong electromagnetic interference, measurements from some satellite are vulnerable to become outliers. Unacceptable positioning errors will occur unless such faulty measurements are detected and excluded. Therefore, it is very important to apply RAIM (Receiver Automatic Integrity Monitoring) algorithm for improving the positioning precision. The main function of RAIM algorithm includes two aspects: fault detection and fault exclusion. This paper presents a RAIM algorithm based on residual separation. The algorithm uses the residual sum of squares of observation equations as test statistics. When test statistics exceed alarm threshold, it can be considered that there are faults in measurements. And then the visible satellites are excluded at every turn, while multi-combinations of remaining measurements are obtained. After SSE (Sum of Squared Error) calculated, the combination of remaining measurements with smallest SSE is the optimal result. Field test data and simulation data are processed in this work. The RAIM algorithm based on residual separation can not only avoid excluding too many satellites, but also improve the positioning accuracy in the case of containing faults.

1 Introduction

Single point positioning (SPP) is the simplest and most convenient GNSS positioning technique. However, the positioning accuracy is poor and sometimes even unacceptable, especially when measurements contain faults [1]. Therefore, it is essential to detect and exclude faults with integrity monitoring algorithm. At present, there are mainly two methods to monitor the integrity of navigation system. One method is using the Integrity Augmentation System, such as the WAAS (Wide Area Augmentation System) in the USA, the EGNOS (European Geostationary Navigation Overlay Service) in Europe and the BeiDou Augmentation System in China. The other is the Receiver Automatic Integrity Monitoring (RAIM), which exploits the measurement redundancy from receivers. The Integrity Augmentation System cannot monitor the faults in receivers and the alarm message may not send to users in time. Therefore, it is very important to apply RAIM algorithm in SPP, which is essential to ensure the availability of the positioning results [2].

RAIM was first proposed by Kalafus [3] in 1987. The RAIM algorithm mainly completes two tasks: detecting whether there are faults in the measurements, identifying and excluding the faulty satellites. At present, the fault exclusion methods such as data snooping [3] and parity space vector [3] are extensively used. And they are equivalent [3]. The data snooping presented by Baarda constructs test statistics with elements of residual vector and compares them with threshold one by one. If some of the test statistics exceed the threshold, it can be considered that the corresponding measurements contain faults, which should be excluded. The Baarda method tests the measurements individually, which may exclude the non-faulty satellites, leading to decreased positioning precision [4]. Furthermore, it may even cause the available satellites less than four, resulting in no positioning solutions [5].

This paper proposes a residual-based separation RAIM. First, the fault detection algorithm gives an alarm. Then an available satellite is excluded at every turn, and the SSE of remaining satellites is calculated. If the smallest SSE is less than alarm threshold, the corresponding remaining satellites combination is selected to carry out positioning calculation. Otherwise the next exclusion turn will be executed, until the SSE of remaining satellites is less than alarm threshold. Because only one available satellite is excluded at every turn, it is impossible to exclude too many satellites, which can effectively decrease faulty exclusion frequency and improve the positioning accuracy.

The rest of the paper is organized as follows. Section 2 gives the mathematical model of single point positioning, fault detection method based on least square residuals, fault exclusion method including Baarda method and Residual-based method. Section 3 verifies the performance of Baarda method and RBS method. Section 4 gives the conclusion.

2 Model and Algorithms

2.1 Mathematical Model of SPP

The pseudorange measurement equations containing the receiver clock bias, satellite clock bias and atmospheric propagation delay can be expressed as follows [2]:

$$\rho_{k}^{j} = \left| {\varvec{r}^{j} - \varvec{r}_{k} } \right| + c \cdot \delta t_{k} - c \cdot \delta t^{j} + \delta \rho_{kion}^{j} + \delta \rho_{ktro}^{j} + \varepsilon_{k}^{j}$$

(1)

where, superscript $j$ is the identifier of satellites, $j = 1{\kern 1pt} ,2, \ldots ,n$, $n$ is the number of satellites, and $n \ge 4$; subscript $k$ is the identifier of receivers; $\rho_{k}^{j}$ is the pseudorange measurement from receiver $k$ to satellite $j$; $\varvec{r}^{j}$ is the position vector of the satellite $j$, which can be obtained from satellite ephemeris and launch time of signal; $\varvec{r}_{k}$ is the unknown position vector of receiver $k$; $c$ is the speed of light; $\delta t_{k}$ is the clock bias of receiver $k$, which is a unknown parameter; $\delta t^{j}$ is the clock bias of satellite $j$; $\delta \rho_{kion}^{j}$ is the ionospheric delay; $\delta \rho_{ktro}^{j}$ is the tropospheric delay; $\varepsilon_{k}^{j}$ is random pseudorange measurement noise.

To solve the pseudorange measurement equations, the equation need to be linearized firstly. Assuming that the initial value of the receiver’s position vector is $\varvec{r}_{k0}$, the pseudorange measurement equations can be linearized as [2]:

$$\rho_{k}^{j} = |\varvec{r}^{j} - \varvec{r}_{k0} | - \varvec{r}_{k}^{j0} \cdot \text{d}\varvec{r}_{k} - c \cdot \delta t^{j} {\kern 1pt} + c \cdot \delta t_{k} + \delta \rho_{kion}^{j} + \delta \rho_{ktro}^{j} + \varepsilon_{k}^{j}$$

(2)

where $\text{d}\varvec{r}_{k}$ is the increment of the receiver’s position vector which is unknown;

$\varvec{r}_{k}^{j0}$ is the unit vector from $k$ receiver to $j$ satellite.

2.2 Fault Detection Method Based on Residual Vector

The position of the receiver and receiver clock bias are obtained using above standard SPP algorithm. However,in case of fewer visible satellites, the faulty measurement of the individual satellite will have a large impact on the positioning results. In this paper,the residual vector of least squares estimation is used to detect fault.

The pseudorange residual vector of least square estimation is calculated as:

$$\varvec{\nu}= {\varvec{Y}} - \varvec{A\hat{X}} = (\varvec{I} - \varvec{A}(\varvec{A}^{\varvec{T}} \varvec{PA})^{{ - {\mathbf{1}}}} \varvec{A}^{\varvec{T}} \varvec{P})\varvec{E}$$

(3)

Define the cofactor matrix as:

$$\varvec{Q}_{\varvec{v}} = \varvec{P}^{{ - {\mathbf{1}}}} - \varvec{A}(\varvec{A}^{{\mathbf{T}}} \varvec{PA})^{{ - {\mathbf{1}}}} \varvec{A}^{{\mathbf{T}}}$$

(4)

Thus, the pseudorange residual vector can be rewritten as:

$$\varvec{\nu}= \varvec{Q}_{\varvec{v}} \varvec{PE}$$

(5)

And the corresponding mean square error:

$$\hat{\sigma } = \sqrt {\varvec{v}^{\varvec{T}} \varvec{Pv}/(n - 4)} = \sqrt {SSE/(n - 4)}$$

(6)

where $SSE$ means sum of squared error.

When the system is normal, all the elements of the pseudorange residual vector should follow Gauss distribution with zero mean and $\sigma_{0}^{2}$ variance; when the measurement of a satellite is abnormal, some elements of pseudorange residual vector will no longer follow zero mean, which is the case that need to be detected.

Therefore, according to the statistical theory, $SSE/\sigma_{0}^{2}$ should follow $\chi^{2}$ distribution with $n - 4$ degree of freedom in the absence of fault. Dualistic hypothesis can be proposed [3]:

Hypothesis with fault ${\text{H}}_{0} {:}{\text{ E}}(\varepsilon ) = 0$, thus, $SSE/\sigma_{0}^{2} \sim \chi^{2} (n - 4)$;

Hypothesis without fault ${\text{H}}_{1} {:}{\text{ E}}(\varepsilon ) \ne 0$, thus, $SSE/\sigma_{0}^{2} \sim \chi^{2} (n - 4,\lambda )$;

In the absence of fault, the $SSE$ of the pseudorange residual should maintain at a minor value. If there are accidental factors which cause $SSE$ too large, it should be false alarmed. With given false alarm rate $P_{FA}$, the following formula can be got:

$$P(SSE\text{/}\sigma_{0}^{2} \le T^{2} ) = \int\limits_{0}^{{T^{2} }} {f_{{\chi^{2} (n - 4)}} (x)} dx = 1 - P_{FA}$$

(7)

The alarm threshold can be obtained from the above formula, in which the probability density function of the $\chi^{2}$ distribution with $n - 4$ degree of freedom is expressed as $f_{{\chi^{2} (n - 4)}} (x)$. If mean square error $\hat{\sigma } < \sigma_{0} * T/\sqrt {n - 4}$, it can be considered that the system is working normally [6]. Otherwise, it is considered that there is fault in measurements which should be alarmed [7].

2.3 Fault Exclusion Method

When the GNSS navigation system is used as an auxiliary, the GNSS measurement information should be no longer used after alarming. But if there is no other auxiliary system, the fault in GNSS system needs to be excluded. The faults among measurements needs to be detected with appropriate algorithm, and the corresponding satellite has to be removed from the SPP observation model. At last, navigation results which meet the users’ demand can be obtained.

2.3.1 Baarda Method

Baarda [3] proposed a method of fault exclusion based on elements of least square residual. The test statistics are constructed by elements in residual vector. Then the identifier of satellite with fault is determined by the size of statistics. After that, measurement of the satellite with fault is removed. Finally, the positioning result without fault is obtained after iteratively calculating.

By using pseudorange residual error vector and the coordinated factor matrix, Baarda’s method constructs the statistics as:

$$d_{i} = \frac{{\nu_{i} }}{{\sigma_{0} \cdot \sqrt {Q_{{\nu_{ii} }} } }}$$

(8)

If the measurement of the ith satellite is normal, $\varepsilon_{i}$ should follow Gauss distribution with zero mean and $\sigma_{0}^{2}$ variance. Thus, $\nu_{i}$ and $d_{i}$ should follow the Gauss distribution. If the absolute value of $d_{i}$ is too large, it can be considered that the ith satellite contains fault, and should be excluded from the measurement equations.

Dualistic hypothesis about statistics $d_{i}$ corresponding to the ith satellite can be proposed as:

Hypothesis with fault ${\text{H}}_{0} {:}{\text{ E}}(\varepsilon ) = 0$, $d_{i} \sim N(0,1)$

Hypothesis without fault ${\text{H}}_{1} {:}{\text{ E}}(\varepsilon ) \ne 0$, $d_{i} \sim N(\delta_{i} ,1)$

where, $\delta_{i}$ is the zero offset of statistic $d_{i}$. Assume that false alarm rate of the system is $P_{FA}$, and false alarm rate of each satellite is $P_{FA}^{{\prime }}$. Then the entire system without alarming is equivalent to all of the satellites without alarming, that is $1 - P_{FA} = (1 - P_{FA}^{{\prime }} )^{n}$. Thus, $P_{FA}^{{\prime }} \approx P_{FA} /n$. Assume that the fault threshold $T_{d}$ of $d_{i}$ meets the need of false alarm rate $P_{FA}^{{\prime }}$. Therefore,

$$P(\left| {d_{i} } \right| > T_{d} ) = \frac{1}{{\sqrt {2\pi } }}\int\limits_{{T_{d} }}^{\infty } {e^{{ - \frac{{x^{2} }}{2}}} dx} = \frac{1}{2} \cdot \frac{{P_{FA} }}{n}$$

(9)

In the course of the positioning calculation, if $\left| {d_{i} } \right| > T_{d}$, it is considered that the pseudorange measurement of the ith satellite contains fault, which should to be rejected. If $\left| {d_{i} } \right| \le T_{d}$, it is considered that the satellite is normal and should to be retained. In the end, measurement equations are constructed by all the reserved satellites, which can be used to obtain a satisfactory navigation solution [3].

2.3.2 Residual-Based Separation (RBS) Method

The Baarda method is likely to exclude satellites without faults, which will decrease the positioning precision. Thus, this paper proposes a residual-based separation method, which determines the identifier of faulty satellites with residual sum of squares and excludes only one satellite each time.

After excluding the first satellite, the pseudorange measurement equations are changed to:

$$\mathop {\varvec{Y}}\limits_{(n - 1) \times 1} = \left[ {\begin{array}{c} {\rho_{k}^{2} - |\varvec{r}^{2} - \varvec{r}_{k0} | + c \cdot \delta t^{2} - \delta \rho_{kion}^{2} - \delta \rho_{ktro}^{2} } \\ \vdots \\ {\rho_{k}^{n} - |{\varvec{r}}^{n} - \varvec{r}_{k0} | + c \cdot \delta t^{n} - \delta \rho_{kion}^{n} - \delta \rho_{ktro}^{n} } \\ \end{array}} \right]$$

(10)

$$\mathop {\varvec{A}_{1} }\limits_{(n - 1) \times 4} = \left[ {\begin{array}{*{20}c} {( - \varvec{r}_{k}^{20} )_{1 \times 3}^{T} } & 1 \\ \vdots & \vdots \\ {( - \varvec{r}_{k}^{n0} )_{1 \times 3}^{T} } & 1 \\ \end{array} } \right],\quad \mathop {\varvec{X}_{1} }\limits_{4 \times 1} = \left[ {\begin{array}{*{20}c} {\text{d}\varvec{r}_{k} } \\ {c \cdot \delta t_{k} } \\ \end{array} } \right],\quad \varvec{E}_{1} \varvec{ = }\left[ {\begin{array}{*{20}c} {\varepsilon_{k}^{2} } \\ \vdots \\ {\varepsilon_{k}^{n} } \\ \end{array} } \right]$$

(11)

The estimated value of the unknown parameters is:

$$\hat{\varvec{X}}_{{\mathbf{1}}} = (\varvec{A}_{{\mathbf{1}}}^{{\mathbf{T}}} \varvec{P}_{{\mathbf{1}}} \varvec{A}_{{\mathbf{1}}} )^{{ - {\mathbf{1}}}} \varvec{A}_{{\mathbf{1}}}^{{\mathbf{T}}} \varvec{P}_{{\mathbf{1}}} \varvec{Y}$$

(12)

where,

$$\varvec{P}_{1} = diag(\sigma_{2}^{ - 2} ,\sigma_{3}^{ - 2} , \ldots \sigma_{n}^{ - 2} )$$

(13)

The residual vector becomes:

$$\varvec{v}_{\varvec{1}} \varvec{ = Y}_{\varvec{1}} \varvec{ - A}_{\varvec{1}} \hat{\varvec{X}}_{\varvec{1}} \varvec{ = (I - A}_{\varvec{1}} \varvec{(A}_{\varvec{1}}^{\varvec{T}} \varvec{P}_{\varvec{1}} \varvec{A}_{\varvec{1}} \varvec{)}^{{\varvec{ - 1}}} \varvec{A}_{\varvec{1}}^{\varvec{T}} \varvec{P}^{\varvec{1}} \varvec{)E}_{\varvec{1}}$$

(14)

After rejecting the first satellite, the residual sum of squares is:

$$SSE_{1} =\varvec{\nu}_{1}^{T} \varvec{P}_{1}\varvec{\nu}_{1}$$

(15)

Similarly, after rejecting the second to nth satellite, all of the residual sum of squares can be obtained: $SSE_{2} ,SSE_{3} , \ldots\,SSE_{n}$. Selecting the smallest $SSE$, it can be considered that the corresponding measurement of satellite contains fault. Then, a satisfactory positioning result can be obtained after excluding the satellite.

If the smallest $SSE$ still exceeds the alarm threshold after excluding one faulty satellite, the next exclusion round should be carried out as aforementioned method, until the $SSE$ is smaller than alarm threshold.

3 Algorithms Verifying

3.1 Simulation Data Processing

The Baarda method and RBS method are both fault exclusion algorithm and fault detection method are both based upon residual vector. Therefore, the miss detection frequencies of the two methods are equivalent and the faulty exclusion frequencies are compared in this section.

In order to verify the effect of the two methods systematically, a part of normal data including 11,904 epochs was intercepted. Fault was artificially added in the measurement of a satellite. If measurements without faults are excluded in one epoch, it is considered that fault exclusion appears once. The faulty exclusion frequency of two methods was counted. Increase the faults added at every round, and the results are shown in Table 1.

Table 1 Comparison of faulty exclusion frequency between two methods

From the table we can see that fault detection algorithm doesn’t alarm when the fault added is tiny, so that the faulty exclusion frequency of the two methods are both close to zero; When the fault added is at around 13 m and closes to the normal measurement error, the faulty exclusion frequency of RBS method reaches maximum; When the fault added is larger than 13 m, the faulty exclusion frequency of RBS method is gradually reduced to zero, while the faulty exclusion frequency with Baarda method increases significantly. As a result, it can be considered that RBS method can reduce the faulty exclusion frequency.

3.2 Field Data Processing

From October 20 to 21, 2015 and in Changsha City, Hunan Province, static observation data of 23.7 h was collected. By processing the real measured data, a group of SPP solutions were obtained. Regarding the result of PPP as true value, the output is the error of SPP under three directions in the local geographic coordinate system. The positioning accuracy is evaluated with the RMSE (Root mean square error).

In this paper, the SPP program uses the modified Hopfield model to compensate the tropospheric error, uses the double frequency measurements to compensate the ionospheric error, and rejects the satellite with elevation less than 5°.

From the error curve in Fig. 1, it can be seen that in most of the time single point positioning error results in zero nearby, but in some period of time the error is unacceptable. After analysing the data, it is found that measurement of a low elevation satellite value is abnormal. The positioning results will meet the requirements after rejecting the satellite with fault.

Fig. 1

Position error curve obtained by using standard SPP

The false alarm rate $P_{FA}$ is set as $1 \times 10^{ - 3}$. After fault detection and exclusion with Baarda method and RBS method, the following results are obtained (Fig. 2).

Fig. 2

Position error curve obtained by using Baarda method

According to the above results,it is shown that Baarda method can realize the fault exclusion and improve the accuracy of the SPP. However, it is obvious that the effect of the method is not satisfactory in some periods of time. Sometimes the measurements with faults are not correctly excluded. Therefore, the positioning error is still too large. Sometimes too many satellites are excluded that the number of remaining satellites is less than four. As a result, it’s impossible to carry out single point positioning.

With the same parameters, using the RBS method, the obtained results are shown as follows (Fig. 3):

Fig. 3

Position error curve obtained by using the RBS method

By contrast it’s obvious that the positioning accuracy was improved without large error. And all the time positioning result is able to be obtained with only the GPS satellites. So that it can be considered that positioning result is satisfactory (Table 2).

Table 2 Positioning error comparison among three methods

By comparing the positioning error in three directions, it can be concluded that FDE algorithm is able to improve the positioning precision significantly. As to the fault exclusion algorithm, the performance of RBS is better than Baarda in three directions.

4 Conclusion

The RAIM algorithm is essential for detecting and excluding faults. Otherwise, the positioning precision will be unacceptable. Data snooping method proposed by Baarda is a classic method to exclude faults. However, healthy measurements are possible to be excluded with Baarda method, which will decrease the positioning precision.

This paper proposes a residual-based separation method which is used to exclude faulty measurements. Because only one satellite is excluded at every round, the faulty exclusion frequency will be much smaller than Baarda method.

After comparing and analysing the positioning results, the conclusions are as follows: In case of few available satellites, the accuracy of SPP is greatly affected by the faults among measurements. And fault detection and exclusion algorithm can significantly improve the positioning accuracy. Comparing to the Baarda method proposed in this paper, the RBS method can not only avoid rejecting too many satellites, but also obviously improve the positioning accuracy.