INTRODUCTION
As more and more human activities are relying on the use of satellite navigation technology, the integrity of navigation solutions has become a major issue, especially for life-safety-critical applications (e.g., Ochieng et al., Reference Ochieng, Sauer, Walsh, Griffin and Denney2003) and liability-critical applications (Beech et al., Reference Beech, Martinez-Olague and Cosmen-Schortmann2005). Therefore, a reliable integrity monitoring procedure must be used to eliminate hazardous and misleading navigation information caused by failure(s) within the navigation system and provide a timely warning message to the user if the navigation information is not good enough for certain applications at the specific time. To address the satellite navigation integrity risks, two strategies have been proposed (e.g., Kinal et al., Reference Kinal, Nagle and Lipke1992): GNSS Integrity Channel (GIC); Receiver Autonomous Integrity Monitoring (RAIM).
The GIC strategy is based on an independent network of ground monitoring stations and a means of conveying the results of the integrity monitoring to the users, e.g., geostationary satellites for regional and global coverage. However, apart from the high costs and time delay of the GIC operations, the GIC cannot check the full integrity at the user level because its monitoring stations cannot detect the local ranging biases/failures at the user receiver, such as extreme user multipath, and local signal interferences etc.
The RAIM strategy is based on a consistency check of satellite measurements used in a navigation solution. If a faulty measurement/satellite (failure) is detected, a procedure may be activated to identify and exclude the failure from the navigation solution, which will therefore remain fault-free and reliable for use in defined applications. Thus, a RAIM procedure is self-contained and can be used as the ultimate integrity monitor (Stansell, Reference Stansell2000). However, the integrity risk associated with the use of RAIM should satisfy the defined requirements.
When specifying integrity requirements, one should determine which position errors are still acceptable, and which errors are not. Therefore, to ensure that the position error is acceptable, an Alert Limit (AL) is defined to represent the largest position error which results in a safe operation. The position error may not exceed this alert limit without annunciation with a probability higher than that stated by the integrity requirements.
For short term operations, the maximum allowable integrity risk is usually specified on a ‘per operation’ basis. Long lasting operations are customarily thought to be conceptually consisting of multiple segments, and the risk is typically specified per segment rather than for the whole operation. As an example, aviation's Signal-In-Space (SIS) integrity requirements for GNSS-based navigation systems are summarised in Table 1. It can be seen that the integrity requirements are either defined on a ‘per approach’ basis (for the approach phases of flight) or ‘per hour’ (for the en-route, terminal and NPA phases). The integrity risk figures are defined to support an appropriate Target Level of Safety (TLS) during each of the operations, and are related to the Alert Limit, which is determined on the basis of obstacle clearance or aircraft separation requirements for the operation at hand.
Signal-In-Space Integrity Requirements from ICAO (2006).
Although not always explicitly stated, integrity requirements are typically to be understood as a maximum allowed risk for each operation (or segment), rather than being interpreted as an average risk. This paradigm is, however, not always followed rigorously. As this paper shows, the existing RAIM Failure Detection and Exclusion (FDE) algorithms determine their availability on the basis of an average integrity risk, rather than using the risk that is encountered during a particular operation. As a result, these algorithms could underestimate the integrity risk for an operation, and claim availability of the system while in fact they should not. While this might be acceptable for some applications, it might not be for others. Therefore, user communities should be aware of the conceptual difference between the ‘average integrity risk’ and the actual or ‘real-time integrity risk’.
Only when this difference is understood, can these communities ensure that the integrity risks they specify match the integrity risks that users estimate to determine the availability of the system for their particular application. This paper therefore sets out to clarify this difference, which has not been discussed in literature. In particular, great importance is attached to a clearer definition of the integrity risk by showing why and how current ‘average integrity’ based RAIM-FDE algorithms can underestimate the real-time integrity risk after a successful exclusion, both theoretically and in practice through a simple simulation.
2. GNSS PERFORMANCE
The positioning performance of a GNSS-based navigation system depends on the following system characteristics:
• the nominal ranging performance of each satellite;
• the satellite geometry as observed by the user;
• the occurrence rate and nature of (rare) failure conditions.
A unique aspect of GNSS when compared to other navigation systems is the time-varying performance caused by changes in the core satellite geometry, even for a stationary user. GNSS performance also varies across the service volume as a result of the varying satellite-user geometries that are concurrently experienced at different locations.
The nature and occurrence of satellite failures (here roughly defined as ‘significant deflections from the nominal performance’) is an important driver of the integrity that the system can provide. Knowledge of the exact fashion in which failures manifest themselves is usually limited, as failures are rare by nature and can be generated by a variety of different mechanisms. The common effect of interest here is that failures are expected to generate considerably larger-than-usual ranging errors, which has generally been modelled by the addition of a bias to the nominal zero-mean pseudorange noise. The size of the bias usually remains unspecified to reflect the lack of knowledge on the failures, but assumptions on this size may still be necessary to enable evaluation of the system's performance in the presence of failures.
2.1. Real-time/measurement-based and predicted/model-based performance
Due to the variations in GNSS performance over time, use of GNSS for critical operations typically requires users to assess the integrity risk they are exposed to in (more or less) real time while performing a certain operation. When the integrity risk exceeds the requirements for the operation, the system is to be considered ‘unavailable’ for the operation, and the user is to be alerted that he should revert to some other navigation means or abort the operation. For a number of operations, performance prediction is required in addition to the real-time assessment; see for example FAA (2007) and EASA (2003). The prediction calculates the expected availability of the system by predicting the satellite geometry that will be observed, in combination with other intrinsic performance parameters of GNSS, such as the probability of satellite failure and the pseudo-range noise levels.
The results of a real-time performance assessment can differ from the predicted performance due to unforeseen changes in the conditions, such as the availability of fewer satellites due to masking effects. While some of these effects might be predictable in principle, forecasting them is often too hard to be practical. More fundamentally, there are circumstances that are unpredictable by their very nature, such as the occurrence of system failures. Performance prediction is necessarily based on models and ‘a priori’ assumptions about the likelihood that a failure occurs. It therefore provides performance estimates that represent an ‘expected value’ or ‘ensemble average’ view of the integrity risk, based on the expectation that only a small fraction of the operations will encounter a satellite failure: the associate integrity risk is the one that is experienced on average over a large number of operations that are performed under the given conditions.
Real-time assessments have access to extra information in the form of pseudo-range measurements. These measurements contain information on the presence of failures. While there are different ways to exploit this information to improve on the calculations of the integrity risk (e.g., Blanch et al., Reference Blanch, Ene, Walter and Enge2007; Ober, Reference Ober2003), this paper only considers the (potential) use of the internal state of the fault-detection and exclusion circuitry in the receiver as an extra source of information, as this is considered the most instructive way to explain the concepts behind the use of real-time information.
3. RAIM ALGORITHMS AND THEIR PERFORMANCES
The first RAIM Failure Detection (FD) algorithms were developed for use with GPS in the second half of the 1980s. In the 1990s, Failure Detection and Exclusion (FDE) algorithms were introduced. Both variants are concisely discussed here in the light of their respective expected (average) and real-time performances.
3.1. RAIM-FD Performance and Availability
When the RAIM-FD is used, both the detection of a failure, as well as the encountering of a period of RAIM-FD unavailability, would cause the system's use to be discontinued. Receivers that are using the system for navigation therefore operate essentially in one single mode, characterised by the following conditions:
• the assessed integrity risk is sufficiently low and thus the RAIM-FD is available;
• no failure has been detected by the FD algorithm.
With the limited computing power available at the time, simple algorithms were required to evaluate the integrity risk to determine whether the system is available to support the operation. The algorithms developed at the time were based on the assumption that a satellite failure could be modelled conservatively by a bias of a predefined size (such as the Minimal Detectable Bias (MDB)), the smallest bias that can be detected with some predefined probability (or the largest bias that will remain undetected with that probability). The MDB only depends on the number of satellites in view but not on their relative geometry, and can thus easily be pre-computed and stored in a table (see for example Brown Reference Brown1992). The RAIM-FD performance is evaluated by verifying whether a bias of the size of the MDB is likely to cause unacceptably large errors in the position domain. If this is the case, the integrity risk at the Alert Limit is deemed too high and the system is unavailable. The only time varying ‘variable’ in this process is the satellite geometry, as real-time receiver information remains unused. As a result, integrity prediction and real-time evaluation can be based on exactly the same ‘predictive’ algorithm that uses either the predicted or the actual real-time satellite geometry.
Now let us have a look at the way integrity is evaluated in the receiver. Assume that the operation or one of its segments takes a time T S (in hours) to complete. When the probability that a satellite failure occurs over this period is denoted by P F, and the average number of satellites in view equals N, the probability of finding a failing satellite in view is approximately N⋅P F. (For simplicity it is assumed throughout the paper that multiple failures are too rare to be taken into account.) When the probability of not detecting the presence of a failure is P MD (the probability of missed detection), the integrity risk IR FD that is experienced by the receiver is given by:
The receiver can evaluate this risk and compare it against the requirements for a given operation. Let us assume that the acceptable risk for the operation IR REQ equals 10−7 per hour. When typical parameters for GPS are substituted (N=10, P F=10−5/hour), and an operation segment of 1 hour is considered (T S=1 hr), it is readily seen that the integrity risk is acceptable whenever P MD⩽0·001. The receiver then checks whether the largest biases that would not meet this requirement cause no excessive position errors. If they do not, the system is considered available for the operation. We will continue to use these typical figures throughout the paper to allow for easy comparison of all outcomes.
3.2. RAIM-FDE Performance and Availability
The RAIM-FDE combines a failure detection function with a failure exclusion function, which has the capability to exclude failing satellites. The exclusion algorithm determines which of the satellites has been failing and excludes this satellite from the position solution, thereby allowing further navigation using the GNSS. The basic operation of the exclusion algorithm is depicted in Figure 1.
The operation of RAIM FDE. When a failure is detected, the satellite that is most likely to have failed is removed from the position solution. Navigation can only continue successfully when the remaining system performance is still adequate.
In the 1990s, FDE algorithms were extensively investigated by the RTCA's GPS Integrity Working Group SC-159. A baseline algorithm was developed in 1993 by Van Graas and Farrell (Reference Van Graas and Farrell1993) and Van Graas (Reference Van Graas1996). Van Graas' approach has been adopted in many studies on the availability of RAIM-FDE, see for example Van Dyke and Lee (Reference Van Dyke and Lee2002). This baseline algorithm also seems to form the basis of most of the previously performed studies into the use of RAIM for combined Galileo and GPS systems by for example Lee (Reference Lee1999), Van Dyke (Reference Van Dyke2001) and Hewitson et al. (Reference Hewitson, Lee and Wang2004), Hewitson and Wang (Reference Hewitson and Wang2006; Reference Hewitson and Wang2007) as well as the report from Eurocae (2003) and the studies therein described. In case of a detected failure with N satellites in view, this algorithm searches for a subset of N−1 satellites in which the failure detection algorithm no longer detects a failure. When multiple subsets without detection are present, two ‘exclusion’ options are possible:
• navigation is continued with the first subset that is found (successful exclusion);
• navigation is continued with the best subset that is found, that is, the subset with the smallest failure detection test statistic (successful exclusion).
It is assumed here that the second of these options is chosen, as it will provide the lowest probability of wrong exclusion.
In the baseline algorithm, RAIM failure detection and exclusion (FDE) is declared to be available whenever the failure detection function is still available after exclusion. The reasoning behind this criterion, which remains unexplained in most papers, seems to be as follows: for a one hour operation, there is an a priori probability of T S⋅N⋅P F (10−4) that a failure occurs, with a (low) probability P MD (⩽0·001) of remaining undetected. Consequently, there is an a priori probability of T S⋅(1−P MD)N⋅P F≈T S⋅N⋅P F (10−4) that a user navigates with a subset of N−1 satellites, which has at most a probability of IR FDE=T S⋅(N⋅P F)⋅P MD (10−7) of still containing the bad satellite. As long as this risk is associated with a position error that does not exceed the alert limit, the system is said to be available. This requires that the MDBs be related to a probability of missed detection of P MD=0·001, and that their influence on the position error are computed for the satellite geometries of the subsets, rather than the full set. As the probability of missed detection will differ for each of the subsets, it is conservatively assumed that the satellite with the worst detectability over all subsets is the one that failed. Lee and Van Dyke (2002) show that, although this assumption is obviously conservative, it doesn't degrade RAIM-FDE availability significantly.
The baseline approach described above is based on a predictive performance perspective: no real-time information is used to assess the chances of a failure are during the operation. The integrity risk that is considered is the risk that is therefore associated with the average integrity risk that the user will experience. The line of reasoning can be summarised as follows: only a small fraction of 1 out of 10,000 operations is expected to encounter a failure, which remains undetected in the subset used for further navigation in 1 out of 1000 cases. Therefore, on average, an integrity risk of 10−7 can be associated with that condition. However, during an actual operation the receiver knows when it has encountered and detected a failure. Once a failure has been detected by the receiver, the risk of continuing that particular operation with one of the subsets might become much higher than 10−7. In fact, as is shown below, based on the criterion used, the integrity risk that is experienced when navigating on a subset that still contains the failing satellite is only guaranteed to be 10−3, although it will typically be lower than that due to the fact that navigation typically continues with the subset that is least likely to contain that failing satellite. However, when the baseline RAIM-FDE availability criterion is used to assess availability during an operation, it can still happen that the actually experienced integrity risk is orders of magnitude higher than the integrity requirement, while the receiver still claims the system to be available.
Put another way: it has been shown above that RAIM-FD receivers can successfully base their real-time performance assessment on the model-based integrity risk. This is due to the fact that the small fractions of operations that encounter a failure (and thus an increased integrity risk) actually stop using the system. As a result, all receivers that are using the system for navigation operate in one single mode, as indicated above. On the other hand, RAIM-FDE receivers can use a navigation system under two fundamentally different sets of operational conditions:
• The RAIM-FD(E) function was evaluated to be available for the operation;
• no failure has been detected by the FD algorithm (‘no detection’ case);
or
• The RAIM-FD(E) function was evaluated to be available for the operation
• A failure has been detected by the FD algorithm and a satellite has been successfully excluded (‘satellite excluded’ case)
As demonstrated, operations under these two conditions can yield highly different integrity risks, which the receiver should take into account when it is to evaluate its real-time integrity risk for an operation, rather than the average risk it would encounter when repeating the operation many times.
In mathematical notation, the integrity risk IR FDE|NoDet in the ‘no detection’ case approximately equals the probability that a failure remains undetected, just as in the RAIM-FD only case:
which for typical values of the probabilities equals 10−7. After the detection of a satellite failure, the integrity risk IR FDE|SatEx in the ‘satellite excluded’ case equals:
in which P WEX is the probability that the wrong satellite has been excluded and the failing satellite is still in the subset that is to be used for further navigation. While the probability of wrong exclusion is hard to compute exactly, see for example Ober and Harriman (Reference Ober and Harriman2006), simple conservative approximations exist. Within the baseline algorithm that is discussed, the probability of wrong exclusion is controlled by the probability of missed detection in the subset without the suspected satellite. As one knows that after wrong exclusion the failing satellite is still in the subset that is used for further navigation, while the probability that it remains undetected in that subset is at most P MD, one obtains the following upper bound:
With the traditional GPS parameter values substituted it is thus only guaranteed that IR FDE|SatEx⩽10−3. Therefore, using the missed detection probability of subsets as a basis for RAIM-FDE integrity risk and availability assessment potentially significantly underestimates the actual risk. As this upper bound is typically far from tight, typical performance will be significantly better than that for most satellite geometries, but the exact performance that is achieved is not explicitly controlled to remain within the requirements.
3.3. A Numerical Example
Above, it has been demonstrated that the availability criterion can underestimate the integrity risk that a user experiences once a failure has been detected and successfully excluded. Whether such underestimation actually occurs will depend on the interaction of the various optimistic and conservative assumptions underpinning the availability criterion. To further investigate their effects in a limited but realistic setting, a Monte-Carlo simulation to assess the performance of the baseline RAIM-FDE availability criterion has been performed.
In the simulations, a total of 504 satellite geometries are investigated by computing world-wide visibility of the optimized 24 satellite GPS constellation from RTCA/DO-229D (2006) on a grid of 504 locations at one particular moment in time. The performance of RAIM-FDE for each of these geometries is investigated in the presence of a failure on each of the satellites (one at a time). The bias in the range measurements to the failing satellites is chosen such that a probability of missed detection of at least 10−3 is achieved for all of the subsets that contain the failing satellite, assuring that RAIM-FDE is ‘available’ when using the baseline criterion. The detection threshold used by the failure-detection algorithm assures that the probability of false detection equals 0·333×10−6, in accordance with the value in RTCA/DO-229D.
The main interest of the simulations lies in estimating P WEX (or IR FDE|SatEx) by determining the fraction of the simulated data points in which a wrong satellite is excluded. To this end, the internal state of the RAIM-FDE algorithm for each particular satellite-bias-geometry combination is recorded for a total of 105 samples, for which the nominal ranging errors are drawn from a zero mean normal distribution with a standard deviation as prescribed by the WAAS model from RTCA/DO-229D. Statistics for the failure of a random satellite and for the failure of the worst-case satellite (the satellite that showed the highest probability of remaining in the solution after exclusion) are collected separately. The possible outcomes that are recorded for each sample include:
• missed detection;
• correct detection, followed by the exclusion of the correct satellite;
• correct detection, followed by the exclusion of a wrong satellite;
• correct detection, followed by an inconclusive situation in which no exclusion could be made.
It is assumed that exclusion is only performed correctly when the subset without the failing satellite (a) is not detecting a failure and (b) has the smallest failure-detection test statistic over all subsets. As a result, a wrong exclusion occurs when one of the subsets that still includes the failing satellite has the smallest failure-detection test statistic; furthermore, this subset should not detect a failure. Using the baseline exclusion criteria, the only occasion in which no exclusion can be made is the one in which all of the subsets still detect the presence of a failure.
The results are summarised in Tables 2 and 3 as well as Figures 2 and 3. They show that the integrity risk that is experienced after a successful exclusion IR FDE|SatEx is typically well below the probability of missed detection P MD of 10−3, and the upper bound in Equation (4) is very conservative. However, for all but a few geometries, the integrity risk that is observed in the simulation is well above the target risk of 10−7 that was specified to drive the baseline algorithm to determine RAIM-FDE availability. For the worst location, the risk becomes as high as 250×10−7 for those users that experience a failure on a random satellite, increasing to a risk of 600×10−7 for those who have to cope with a failure of the worst-case satellite.
The estimated integrity risk after the exclusion of a satellite for 504 locations on a grid on the earth (latitudes: −65,−55,−45, …, 55,65, latitudes −180,−170,−160, …, 170) for a single point in time (GPS Week 703, 344 064 seconds).
The number of geometries for which a certain integrity risk was found after the exclusion of a satellite – for failures in a random satellite and failures in the worst-case satellite respectively.
Number of geometries with observed missed detection and no exclusion fractions.
Number of geometries with observed integrity risks after an exclusion.
CONCLUSIONS
The paper demonstrates that there are two fundamentally different ways to assess the integrity risk of an operation, based on a different amount of available information. In particular, the availability of real-time receiver information alters the assessment after the detection and exclusion of a failing satellite with respect to the case in which only a priori models of the system can be used. After an exclusion, the real-time integrity risk and system availability should be evaluated conditionally on the fact that there has been a detection to avoid underestimation of this risk, unless it is acceptable that risks are being averaged over multiple operations.
To avoid any misunderstanding, the requirements for any application should clearly state whether the specified integrity risk is to be understood to be applied to each and every operation separately, or whether it is understood that it only needs to be met on average. The following addition to ICAO Annex 10 that was proposed by DeCleene (Reference DeCleene2005) shows that this importance has already been recognised by the aviation community:
“The approach integrity requirements apply in any one landing and require a fail-safe design. If the specific risk on a given approach is known to exceed this requirement, the operation should not be conducted”.
In the same proposal, DeCleene argues that “The continuity requirement should be applied as applying to the average risk of loss of service”. It is felt that other user communities should consider similar clarifications where applicable.
Once the requirements are clear, it should be guaranteed that system performance parameters are calculated in a manner that is compatible with these requirements. As this paper shows, the baseline RAIM-FDE algorithm that has been used in many studies to assess the availability of GNSS is unfit to guarantee that the integrity risk for each and every operation remains within the requirements: once a user encounters a satellite failure which is successfully excluded by the receiver, this calls for the use of a different availability criterion.
