Weighted RAIM for APV: The Ideal Protection Level

Carl D. Milner; Washington Y. Ochieng

doi:10.1017/S0373463310000342

Weighted RAIM for APV: The Ideal Protection Level

Published online by Cambridge University Press: 26 November 2010

Carl D. Milner and

Washington Y. Ochieng

Show author details

Carl D. Milner: Affiliation:
(Imperial College London)
Washington Y. Ochieng*: Affiliation:
(Imperial College London)
*: (Email: w.ochieng@imperial.ac.uk)

Article contents

Abstract
INTRODUCTION
RAIM PROTECTION LEVELS
SYSTEM MODEL
WORST CASE SEARCH
IDEAL VPL
VPL RESULTS
CONCLUSIONS AND FUTURE WORK
References

Rights & Permissions

Abstract

International standards require the use of a weighted least-squares approach to onboard Receiver Autonomous Integrity Monitoring (RAIM). However, the protection levels developed to determine if the conditions exist to perform a measurement check (i.e. failure detection) are not specified. Various methods for the computation of protection levels exist. However, they are essentially approximations to the complex problem of computing the worst-case missed detection probability under a weighted system. In this paper, a novel approach to determine this probability at the worst-case measurement bias is presented. The missed detection probabilities are then iteratively solved against the integrity risk requirement in order to derive an optimal protection level for the operation. It is shown that the new method improves availability by more than 30% compared to the baseline weighted RAIM algorithm.

A version of this paper was first presented at the US Institute of Navigation (ION) GNSS 2009 Conference in Savannah, Georgia.

Keywords

Integrity Monitoring Protection Level GNSS

Type: Research Article
Information: The Journal of Navigation , Volume 64 , Issue 1 , January 2011 , pp. 61 - 73

DOI: https://doi.org/10.1017/S0373463310000342 [Opens in a new window]
Copyright: Copyright © The Royal Institute of Navigation 2010

1. INTRODUCTION

Air navigation performance is specified in terms of accuracy, integrity, continuity and availability, the last one being a function of the first three being met (ICAO, 2006). Integrity is the most critical due to its link to safety and therefore, is the most stringent of the requirements. The integrity risk specification for aircraft approaches cannot be met by stand-alone GPS and as such integrity monitoring is required. Integrity monitoring may be provided at the system level such as Satellite or Ground Based Augmentation Systems (SBAS/GBAS) or at the sensor level known as Receiver Autonomous Integrity Monitoring (RAIM) (RTCA, 2006). Specifications for RAIM have been developed with the view that they may be used as a back-up to WAAS/EGNOS or other Satellite-Based Augmentation Systems (SBAS). Ideally RAIM should be used for all applications as it provides the most localised determination of possible failures.

The baseline RAIM algorithm is composed of three phases, protection level computation, fault detection and fault exclusion. The protection level computation ascertains whether the conditions exist to perform fault detection with sufficient power. It is in essence a performance safeguard. Fault detection is a safeguard of the correct function of the system and ensures that measurements do not contain significant failures. It is achieved by comparing a test statistic with a threshold derived from the continuity requirements. The required Probability of Missed Detection (P_MD) for this process, which relates to the integrity risk, is accounted for by the protection level and not within the fault detection procedure itself when utilising a threshold defined in this manner. Finally, exclusion of the failed satellite from the solution may be possible in the event of a significant failure.

GPS with RAIM operations are currently being used for en-route and, in some states, non-precision approach (NPA) operations. However, more stringent operations such as APV-I are unable to be met using the baseline weighted least squares RAIM algorithm (RTCA, 2006) as high protection levels limit availability. Its use as a supplemental system in more demanding phases of flight would bring a significant operational benefit. This could alleviate would-be outages of the regional SBAS available to the user. Potentially, improved RAIM could also be of great benefit to regions without an operational SBAS in order to meet the international specifications for APV-I and APV-II. This could enable precision approach procedures to be flown.

The rest of this paper is structured as follows. Section 2 discusses one deficiency of RAIM algorithms and defines the research problem. The system model is then introduced in section 3 and the weaknesses of existing methods analysed. A worst-case search is developed in section 4, thereby enabling the specification of the iteration procedure for the ideal VPL in section 5. The results are presented in section 6 highlighting the improvement over traditional techniques. Section 7 discusses the impact of the research and future work.

2. RAIM PROTECTION LEVELS

There have been a number of recent publications relating to novel ways of improving RAIM, particularly in providing higher integrity and hence service availability (Hwang and Brown, Reference Hwang and Brown2005; Lee, Reference Lee2007). One aspect which has not captured the attention of researchers in recent years is the computation of an optimal protection level. Protection levels are used to guarantee the capability of the detection (or indeed exclusion) function to provide sufficient integrity. The protection levels employed today appear, on the basis of citation (Angus, Reference Angus2007; Ober, Reference Ober1998), to be primarily those of Brown and Chin (Reference Brown and Chin1998) and Walter and Enge (Reference Walter and Enge1995). The conservative Brown and Chin bound is guaranteed to protect against potential biases with the required integrity risk. The Walter and Enge bound, although at a lower more realistic level, may potentially be susceptible to biases which cause the required integrity risk to be exceeded.

Analyses performed over the service volume (Ochieng et al, Reference Ochieng, Sauer, Walsh, Brodin, Griffin and Denney2003) have shown that when using the conventional Brown and Chin protection level, RAIM is unable to meet the requirements of APV-I due to low availability in most regions. This is in part due to intrinsic limitations of the current GPS but may also be a consequence of the conservatism of the protection level employed. This conservatism is borne of both the failure bias ambiguity and the correlation between the test statistic and position error domains. For each geometrical configuration there is a worst-case value for the failure magnitude or bias on a satellite's measurements. Determining this value is not simple and involves the evaluation of the integrity risk at a number of biases. The alternative approach taken in the derivation of protection levels is to use a Minimum Detection Bias (MDB) which is sure to protect against larger biases, with the required probability. This MDB is then projected to the position domain to find the protection level. In order to protect against biases smaller than the MDB, an additional buffer term is included. Sensitivity analyses have shown that the true Worst-Case Bias (WCB) is usually much lower than the MDB and as such its use is counter to the optimisation of performance (Milner, Reference Milner2009).

In order to determine an optimised value, referred to as the ideal protection level, the integrity risk at the WCB may be determined for different protection levels until the integrity requirement is matched. In the following section the system model is introduced including the mathematical formulation of existing protection levels.

3. SYSTEM MODEL

The foundation of the weighted least-squares RAIM formulation is the assumption of an over-determined system of linear equations relating the position solution to the measurements after linearization.

(1)

${\bf z \equals Hx}{\bf \plus } {\bmepsi}$

where:

z: : n – dimensional vector of measurements
H: : n×4 – dimensional geometry matrix defined in the local horizontal frame, with the condition n>4
x: : 4 – dimensional vector of unknowns (position and clock bias)
ε: : n – dimensional vector of measurement errors

It is assumed that the measurement errors may be modelled as the sum of the measurement noise v and measurement biases b:

(2)

${\bmepsi} \ {\bf \equals \ b\ \plus \ v}$

and that the underlying measurement noise v′ is normally distributed with diagonal (independent errors) covariance matrix Σ as follows:

(3)

${\bf v \prime {\sim} N\lpar 0\comma} {\bmSigma} {\bf \rpar} }$

The linear equation (1) is assumed to have been normalised by down-weighting the measurements subject to their estimated measurement variances in (3). The resulting measurement errors v are then uncorrelated and of equal variance.

The weighted least squares estimate has been derived as follows:

(4)

${\bf \hat{x}}_{{\bf WLS}} {\bf \ \equals \ }\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf Wz}$

where the down-weighting is defined by setting W to the inverse of Σ, W=Σ⁻¹. The position error, the difference between the navigation position solution ${\bf \hat{x}}_{{\bf WLS}}$ and the true position x_true may be defined from applying the WLS operator to the measurement error vector.

(5)

${\bf e\ \equals \ \hat{x}}_{{\bf WLS}} {\bf \minus x}_{{\bf true}} {\bf \ \equals \ }\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf W} {\bmepsi}$

The test statistic is defined as the magnitude of the parity vector|p|, which is equivalent to the weighted least-squares residual defined in (Walter and Enge, Reference Walter and Enge1995).

(6)

${\bf p \equals Pz \equals P} {\bmepsi} }$

where P is the parity matrix (Sturza, Reference Sturza1988).

A bias in the system is expressed simply by substituting a bias vector into equations 4 and 5 for the position (ebias) and parity (pbias) spaces.

(7)

${\bf ebias\ \equals \ }\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf Wb}$

(8)

${\bf pbias \equals Pb}$

The research presented in this paper addresses the single satellite failure; interested readers of the multiple failure solution may refer to (Milner, Reference Milner2009). The bias vector is then formed of a single scalar bias on the transgressing satellite and zeroes for each other index.

An important relation is the ratio of a measurement bias projected to both position and parity domains. This relation holds in the absence of measurement noise and is defined by the slope parameter as shown in Figure 1.

(9)

${\bf slope}_{\bf i} \ \equals \ {{{\bf ebias}} \over {{\bf pbias}}}\ \equals \ {{\left[ {\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf W}} \right]_{{\bf i\comma \setnum{3}}} } \over {\left[ {\bf P} \right]_{{\bf i\comma \setnum{3}}} }}$

However, in the presence of noise, importantly the stochastic components of the position error and parity vector have known variances under the model, defined as follows:

(10)

${\bf Cov}\left( {\bf e} \right) \equals \left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}}$

(11)

${\bf Cov}\left( {\bf p} \right){\bf \equals PP}^{\bf T} {\bf \equals I}_{{\bf n \minus \setnum{4}}}$

Figure 1. ET Diagram.

The operational requirements for aviation (RTCA DO-229D) are specified as functions of the probability of missed detection, alert limit and a false alarm rate. This false alarm rate may be used to derive the threshold (T) for the parity test statistic used. It is well-known that for vertically guided approaches, the vertical requirement is most critical and so is considered in this paper. The horizontal case may be treated similarly (Milner and Ochieng, Reference Milner and Ochieng2009).

In order to derive the most commonly used Vertical Protection Level (VPL) of Brown and Chin, the first step is to compute the Minimal Detectable Bias (MDB_p) in the parity domain. The P_MD, which is set by the RTCA at 10⁻³ by factoring the probability of a failed satellite 10⁻⁴ into the integrity risk requirement of 10⁻⁷, is used as input to an inverse non-central chi-squared distribution function as follows:

(12)

${\bf MDB}_{\bf p} \equals \sqrt {\bmlambda }$

(13)

${{\bmlambda} {\bf \equals Q}^{{\bf \minus \setnum{1}}} \left( {{\bf P}_{{\bf MD}} {\bf \comma n \minus 4\comma T}} \right)$

such that:

${\bf P}_{{\bf MD}} {\bf \equals Q}\left( {{\bf n \minus 4\comma T\comma} }\bmlambda }} \right) \equals \int_{\bf \setnum{0}}^{\bf T} {{\bmchi }_{{\bf pdf}}^{\bf \setnum{2}} \left( {{\bf n} \minus {\bf 4\comma} {\bmlambda} {\bf \comma t}} \right)\,{\bf dt}}.$

This MDB_p shown in Figure 2 represents the smallest bias transformed into the parity domain which may remain undetected with a probability equal to the P_MD. Therefore larger biases are guaranteed not to lead to a PMD greater than the requirement. The calculation of VPL then projects this bias into the position domain by use of the slope parameter, as clearly demonstrated in Figures 1 and 2.

(14)

${\bf MDB}_{\bf e} \ {\bf \equals \ slope}_{\bf i} {\bf \times MDB}_{\bf b}$

Figure 2. Existing protection levels.

However, this position error value is not guaranteed to provide a protective limit on the P_MD because biases less than the MDB_p may result in more of the probability density lying in the critical missed detection region, as may be inferred from Figure 1. Therefore an additional term is required which protects against the variation in position error (Angus, Reference Angus2007). This is simply the one-sided confidence interval of the position error at the significance level of the PMD.

(15)

${\bf k}^{\bf \plus } {\bf \equals k}_{{\bf MD}} {\bf \times Cov\lpar e\rpar }_{{\bf \setnum{3}\comma \setnum{3}}}$

This leads to the definition of the following Brown and Chin (Reference Brown and Chin1998) protection levels:

(16)

${\bf VPL}_{{\bf BC}} {\bf \ \equals \ MDB}_{\bf e} {\bf \ }$

(17)

${\bf VPL}_{{\bf BC \plus }} {\bf \equals MDB}_{\bf e} {\bf \plus k}^{\bf \plus }$

The Walter and Enge (Reference Walter and Enge1995) bound is defined similarly to equation 17. However, the threshold (instead of the MDB) is projected to the position domain.

(18)

${\bf ebias}_{\bf T} \ {\bf \equals \ slope}_{\bf i} {\bf \times T}$

(19)

${\bf VPL}_{{\bf WE}} {\bf \equals ebias}_{\bf T} {\bf \plus k}^{\bf \plus }$

Of the existing VPLs stated above, only the VPL_BC+ bound is guaranteed to protect the user with the required certainty under the model assumptions. As shown in the results section, the use of this protection level results in low availability. However, the VPL_BC and VPL_WE bounds may potentially under-estimate the risk associated by not accounting for the true Worst Case Bias (WCB) which equates to the highest integrity risk. The following section begins the proposed alternative to the approximate VPLs defined above. These protection levels are shown in Figure 2, though it should be noted that although VPL_BC+ must always be the largest, VPL_WE may exceed VPL_BC.

4. WORST CASE SEARCH

It is known that in the optimally weighted system, the parity vector and position error vector are uncorrelated (Ober, Reference Ober2003; Hwang and Brown, Reference Hwang and Brown2005) and as their joint distribution is multi-normal, are independent (Johnson, Reference Johnson and Kotz1995). Therefore, the P_MD may be expressed as the product of the probability of positioning failure P_PF and the probability of no alert.

(20)

$\eqalign{ {\bf P}_{{\bf MD}} \tab\equals {\bf P}_{{\bf PF}} {\bf \times P}_{{\bf NA}} \cr \tab \equals {\bf P\lpar \vert e\vert \gt VAL\rpar \times P\lpar \vert p\vert \lt }\sqrt {\bf T} {\bf \rpar } \cr}$

These two probabilities may be expressed in analytical form for a known bias vector b, consisting of a single bias scalar B on the failed satellite index.

(21)

${\bf P}_{{\bf PF}} {\bf \equals erfc}\left[ {{{{\bf VAL \minus}\left. {\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf Wb}} \right\vert_{\bf \setnum{3}} } \over {\left. {{\bf Cov\lpar e\rpar }} \right\vert_{{\bf \setnum{3}\comma \setnum{3}}} }}} \right]$

(22)

${\bf P}_{{\bf NA}} \equals \chi ^{\setnum{2}} \lpar {\bf T\comma n \minus 4\comma Pb} \rpar$

The P_MD may then be computed directly and efficiently using equations 20–22 for a given bias B. The challenge faced in identifying the Worst Case Bias (WCB) is to compute the P_MD and thus integrity risk at a number of points whilst maintaining a short computation time.

As stated above, biases greater than the MDB are protected against with the required certainty. An additional lower bound may also be defined, known as the Minimal Hazardous Bias (MHB) (Ober, Reference Ober2003). This parameter is the smallest bias which has the potential to cause a positioning failure with a probability of 0·001. ${\bf MHB\ \equals \ }{{{\bf VPL \minus k}_{{\bf PMD}} {\bf Cov\lpar e\rpar }_{{\bf \setnum{3}\comma \setnum{3}}} } \over {\left\Vert {\left( {{\bf H}^{\bf T} {\bf WH}} \right)^{{\bf \minus \setnum{1}}} {\bf H}^{\bf T} {\bf Wb}} \right\Vert}}$ where k_PMD is the k-factor associated with a probability of 0·001.

The MHB is a function of the VPL or may be expressed for the VAL. When performing the search for the ideal VPL in section 5, the role of an arbitrary VPL takes form. At this stage, it is important to note that if the MHB exceeds the MDB, the VPL used is guaranteed to protect users with the required confidence. Otherwise, the range of biases [MHB, MDB] forms an interval over which the integrity risk could exceed the required level as shown in Figure 3. A search for the WCB is performed over this range.

Figure 3. Worst-case search.

Sensitivity analyses have shown that evaluating at 1000 biases within the [MHB, MDB} range is more than sufficient to find the worst case integrity risk with an error of less than 0·1% (Milner, Reference Milner2009). To achieve this resolution a three-stage search is used with 16 evaluation points as shown in Figure 3. This results in a resolution of 1024 but requires only 48 evaluations of the integrity risk. In order to ensure the reliability of the search process, a test for multiple discreet peaks in the integrity risk function is performed prior to the search and a full 1024 point search undertaken if this fails. Further details on the results of this sensitivity analysis are described in (Milner, Reference Milner2009).

5. IDEAL VPL

The previous section dealt with the computation of a worst case integrity risk at the WCB for an arbitrary VPL. Therefore, a one-to-one mapping exists between the VPL and the integrity risk as shown in Figure 4. The curve shown in Figure 4 is unique to each satellite-to-user geometry. Generally the VAL does not match the required integrity risk (e.g. 10⁻⁷). The proposed ideal VPL is defined as the VPL which matches exactly the required integrity risk.

Figure 4. VPL vs. Integrity Risk.

Once again a search procedure is executed to obtain the ideal VPL. The procedure begins with an improbably large VPL of 2000 m and halves the search step by checking if the corresponding integrity risk exceeds the required level. This process is accelerated by a number of additional checks to the WCB search. Firstly, the MHB is compared to the MDB to determine whether any biases have the potential to be non-compliant. This is usually the case for the initial iterations when the VPL and thus MHB are large.

To complement the use of MHB and MDB at high VPLs, two additional parameters (MHB' and MDB') are defined based on a P_MD of 0·001^1/2. In the event that MHB^1/2 does not exceed MDB^1/2, the integrity risk requirement is surpassed by the integrity risk associated with the range [MHB^1/2, MDB^1/2] and as such the current value of the VPL is too small.

If the two conditions described above are inconclusive, the WCB search is performed to identify the worst case integrity risk. This process may also be cut short, if an integrity risk evaluation exceeds the required level.

The ideal VPL iteration procedure continues until the required accuracy in the VPL value reaches the required limit (e.g. 1 cm). The result is an optimised protection level for the geometry provided and the optimally weighted least squares positioning solution. The benefit of the ideal VPL is that it may be used to test the existing protection levels outlined in section 4 but also could potentially be employed in a real receiver architecture. A comparison of the ideal VPL and existing approaches is given in the following results section.

6. VPL RESULTS

To assess the performance provided by the ideal VPL and existing techniques, each is computed over 24 hours at major international airports. The results are generated for the GPS L1 signal and the GPS L1/L5 combination to assess both APV-I and APV-II availability. Figures 5–7 show the results for GPS L1 at Amsterdam Schipol, JFK and Sydney International. It is clear from the figures that the availability of APV-I using the VPL_BC+ method is much lower than the other traditional VPLs and the ideal VPL. Of particular interest is the apparent greater availability provided by the VPL_BC bound in comparison to the ideal VPL. This is due to the VPL_BC underestimating the true integrity risk during some periods. Therefore, there is an associated integrity risk with using this protection level in real operations. This is also true of the VPL_WE bound which was found to cause an integrity risk in a small percentage of cases.

Figure 5. Amsterdam Schipol GPS L1.

Figure 6. JFK GPS L1.

Figure 7. Sydney GPS L1.

The results of dual frequency (L1/L5) tests showed similar results for APV-II availability as displayed in Figures 8–10. One notable difference is the higher availability shown by the Walter and Enge (VPL_WE). This higher availability is accompanied by periods of integrity risk, approximately 1·5% of the total time.

Figure 8. Amsterdam Schipol GPS L1/L5.

Figure 9. JFK GPS L1/L5.

Figure 10. Sydney GPS L1/L5.

The corresponding results for the dual-frequency Galileo configuration E1/E5 are shown in Figures 11–13. The results show greater periodicity due to the use of a Walker constellation and as expected, RAIM availability for APV-I is found to be 100% at each airport. Similarly, high APV-II availability is achieved using the VPL_BC, VPL_WE and ideal VPL bounds.

Figure 11. Amsterdam Schipol Galileo E1/E5.

Figure 12. JFK Galileo E1/E5.

Figure 13. Sydney Galileo E1/E5.

7. CONCLUSIONS AND FUTURE WORK

The performance of the ideal VPL has been shown to exceed that of the existing protection levels. Existing methods are either excessively conservative (VPL_BC+) or open to potential integrity risks surpassing the requirement (VPL_BC and VPL_WE). Therefore, under a weighted least squares system which is optimally weighted, the ideal VPL is an optimised solution. The potential benefit of the ideal VPL is to open new precision approach capabilities in regions of the globe unaided by an SBAS or as a back-up to SBAS in Europe and CONUS. Enhanced performance is also to be expected for the LPV200 operational category. Extensive results relating to a combined constellation scenario, two-failure scenario and custom failure model are presented in (Milner, Reference Milner2009). Further work is underway to investigate potential applications to NIORAIM (Hwang and Brown, Reference Hwang and Brown2005) to combine the availability maximising properties of each method.

References

REFERENCES

Angus, J. E. (2007) RAIM with Multiple Faults. NAVIGATION, Journal of the Institute of Navigation. 52, 4.Google Scholar

Brown, and Chin, GPS (1998) “Calculation of GPS Threshold and Protection Radius Using Chi Square Methods – A Geometric Approach” ION Red Books.Google Scholar

Hwang, P., Brown, R. G. (2005) RAIM FDE Revisited: A New Breakthrough In Availability Performance With NIORAIM (Novel Integrity Optimized RAIM). ION NTM 2005 San Diego CA.Google Scholar

ICAO SARPs (2006) Annex 10 – Standards and Recommended Practices.Google Scholar

Johnson, and Kotz, (1995) “Continuous Univariate Distributions” 2^nd Edition Wiley InterScience.Google Scholar

Lee, Y. C. (2007) Two New RAIM Methods Based on the Optimally Weighted Average Solution (OWAS) Concept. NAVIGATION. Journal of the Institute of Navigation. 54, 4, 333–345.Google Scholar

Milner, C. and Ochieng, W. Y. (2009) A Fast And Efficient Integrity Computation For Non-Precision Approach Performance Assessment, GPS Solutions (In Press) http://www.springerlink.com/content/f758457j7x524120/.Google Scholar

Milner, C. (2009) Determination of the Effects of GPS Failures on Aviation Applications, PhD thesis, University of London (subject to final submission).Google Scholar

Ober, P. B. (1998) RAIM Performance: How Algorithms Differ. The Proceedings of the 11^th International Technical Meeting of The Satellite Division of The Institute of Navigation, ION GPS-98, September 15–18, 1998, Nashville, Tennessee.Google Scholar

Ober, P. B. (2003) Integrity Monitoring and Prediction. PhD Thesis. TU Delft.Google Scholar

Ochieng, W. Y., Sauer, K., Walsh, D., Brodin, G., Griffin, S. and Denney, M. (2003) GPS Integrity and Potential Impact on Aviation Safety. The Journal of Navigation, 56, 51–65.Google Scholar

RTCA DO-229D (2006) Minimum Operational Performance Standards for GPS/WAAS Airborne Equipment.Google Scholar

Sturza, M (1988) “Navigation System Integrity Monitoring Using Redundant Measurements”.CrossRef Google Scholar

Walter, T and Enge, P., (1995) “Weighted RAIM for Precision Approach” ION NTM 1995.Google Scholar