Wide-Sense CDF Overbounding for GNSS Integrity

2.1 CDF Overbounding

The CDF overbounding concept was proposed and developed by DeCleene (2000). The main aim is to overbound the empirical measurement error distribution, in the field of the CDF, by a simpler distribution that allows better control over the integrity risk, primarily at the tails. The use of a simplified distribution enables both analytical manipulation of the error distributions and the establishment of margins on the true error distributions, which are only partially known.

In the following, the CDF of a random variable X is denoted by $F_X$. According to DeCleene, the random variable $O_X$ is a CDF overbound of the random variable X. We note that $X\preccurlyeq O_X$ if the following holds:

$\begin{array}{c}\forall x\le 0,\hspace{1em}{F}_X\left(x\right)\le F_{O_X}\left(x\right)\\ \forall x\ge 0,\hspace{1em}{F}_X\left(x\right)\ge F_{O_X}\left(x\right)\end{array}$1

The CDF overbound concept is preserved by convolution: if $X\preccurlyeq O_X$ and $Y\preccurlyeq O_Y$, if X and Y are independent, and if all the distributions are unimodal and symmetric, then $\forall \alpha ,\beta \in ℝ$, $\alpha X+\beta Y\preccurlyeq \alpha O_X+\beta O_Y$. This mathematical result demonstrates that the integrity risk associated with the sum $O_x+O_y$ serves as an upper bound for the integrity risk of the sum $X+Y$.

Consequently, each real empirical measurement error distribution is replaced by its overbound distribution, and as the position errors are obtained as a linear combination of the residual measurement errors, the positional errors are also overbounded by a symmetric, unimodal distribution. This property guarantees that integrity in the pseudorange domain implies integrity in the positional domain.

The CDF overbound concept, however, requires that the distributions of error components be centered, meaning that they should be unimodal and symmetric, with no bias. Yet, the verification of hypotheses of zero mean and symmetry for residual measurement errors is never perfectly met. Systematic errors (including tropospheric delays, multipath effects, interchannel biases, etc.) inevitably introduce biases into the residual errors. Furthermore, there is no guarantee that the empirical distributions are indeed unimodal.

These errors are composed of a random part, a noise ϵ_i along the lines of sight, and an additional bias μ_i. If these biases were known, they would be integrated into, for instance, the SBAS corrections and the distributions of the residual errors would be centered, which is not the case. Even if these biases are poorly understood, it is generally assumed that an upper limit of their absolute values is known. It then becomes possible to introduce this upper limit into the variance σ_i of the overbound distributions by applying an inflation factor ξ_n,K, which depends on an integrity factor K and the number n of lines of sight (DeCleene, 2000; Rife et al., 2006):

${\xi }_{n,K}=1+\underset{i=1,\dots ,n}{\max }\frac{\left|{\mu }_i\right|}{{\sigma }_i}\frac{\sqrt{n}}{K}$2

However, this approach is highly conservative and often leads to excessively large protection volumes, which limits service availability.

The concept of the CDF overbound requires that the tails of the overbound cover the tails of the empirical distribution. In the case of a Gaussian overbound (which is generally the case), we know that the tails of Gaussian distributions are very light; thus, we will eventually find a quantile (however large) beyond which the tail of the Gaussian falls below the tail of the empirical distribution. For this reason, in practice, we set a quantile q, beyond the specified integrity risk (IR), q > F^–1(IR/2), within which, over the interval [–q, q], the overbound property exists. This approach can be justified by applying core overbounding (Rife, Walter et al., 2004).

2.2 Paired Overbounding

The paired overbounding concept of Rife et al. (2006) is designed to dispense with the hypotheses of CDF overbounding other than the independence of the random variables, namely, that the distributions of the residual error components must all be centered, unimodal, and symmetrical.

We suppose that the random variables ${ℒ}_X$ and ${ℛ}_X$ provide a paired overbound for the random variable X, and we denote $X\subseteq \left[{ℒ}_X,{ℛ}_X\right]$ if the following hold:

$\begin{array}{c}\forall x\in ℝ,\hspace{1em}{F}_X\left(x\right)\le F_{{ℒ}_X}\left(x\right)\\ \forall x\in ℝ,\hspace{1em}{F}_X\left(x\right)\ge F_{{ℛ}_X}\left(x\right)\end{array}$3

The random variable ${ℒ}_X$ is called the left overbound, and ${ℛ}_X$ is called the right overbound of the variable X.

The paired overbounding property is preserved by convolution if ${ℒ}_X$ and ${ℛ}_X$ are symmetric $\left({ℒ}_X=-{ℛ}_X\right)$: if $X\subseteq \left[-{ℛ}_X,{ℛ}_X\right]$ and $Y\subseteq \left[-{ℛ}_y,{ℛ}_y\right]$, then $\forall \alpha ,\beta \in ℝ$, $\alpha X+\beta Y\subseteq \left[-\left|\alpha \right|{ℛ}_X-\left|\beta \right|{ℛ}_Y,\left|\alpha \right|{ℛ}_X+\left|\beta \right|{ℛ}_Y\right]$. Only independence is needed for the result to hold, and no specific assumptions on the distributions are necessary to demonstrate their stability by convolution. Consequently, if the distribution of each measurement residual error is paired-overbounded, then the positional errors are also paired-overbounded and integrity in the pseudorange domain implies integrity in the positional domain. This approach is very useful when accounting for residual biases and developing an overbound concept that can accommodate any residual distribution shape.

In practice for GNSS integrity, the pair of overbounds are set as two Gaussian distributions with identical standard deviation σ, with mean –μ for the left overbound and +μ for the right overbound. However, although the paired overbounding concept brings generality to range overbounding, the search for left and right limits may lead to conservatism, especially when considering symmetrical overbounding distributions. This issue arises because Equation (3) implies that the tail of ${ℛ}_X$ is heavier on the right than that of X, but also lighter on the left. For Gaussian overbounds with only two degrees of freedom, this situation often leads to an excessive inflation of the μ parameter and over-conservatism.

This specific problem has been addressed by the excess mass CDF overbounding method presented by Rife, Pullen et al. (2004). The main idea is to apply paired overbounding by using distributions in which the total mass is allowed to be greater than unity. This method leverages the fact that only the left tail of the left overbound and the right tail of the right overbound are used to build the protection levels. Furthermore, the properties of paired overbounding do not depend on the fact that the total probability is normalized to unity. Thus, the excess mass method allows one to build an overbounding pair closer to the distribution of interest by relaxing the conditions on the right tail of the left overbound and on the left tail of the right overbound. In practice, the paired overbounding method is very rarely used without excess mass.

An alternative way to deal with the excessive conservatism of paired overbounding with symmetrical overbounds is to consider non-symmetrical (and thus non-Gaussian) overbounding distributions. This approach is taken, for example, by Rife and Pervan (2012); in that work, the authors propose a numerically defined distribution for the right overbound with a light tail on the left side and a heavy tail on the right side. Their left overbound is the mirror reflection of the right overbound. This approach enables one to reduce conservatism at the price of an increased computation load, as no analytical expression is available for the position domain protection level, which must be computed numerically.

To further improve on the excess mass overbounding method, the two-step overbounding method was introduced by Blanch et al. (2018).

2.3 Two-Step Overbounding

Blanch et al. (2018) cleverly blended the last two concepts, the CDF overbound and the paired overbound, taking advantage of the less conservative property of the first concept and the robustness of the second. The purpose is to frame the empirical distribution X of an unmodeled residual error with Gaussian overbounds.

Their approach starts with the construction of left and right overbounds that are symmetrical and unimodal around their medians. Because these distributions do not need to be Gaussian, they are not strongly affected by the issue presented in the section above. Each distribution is then CDF-overbounded by a Gaussian distribution. The result is a pair of biased Gaussian distributions that can be used as a paired overbound for protection-level computation. Because the intermediate paired overbound is symmetrical and unimodal, the integrity demonstration is obtained naturally by applying the CDF and paired overbound stability with convolution. The first step of paired overbounding can also be combined with the excess mass method in order to obtain an overbounding distribution closer to the original distribution.

This construction enables a transfer of integrity from the measurement domain to the positional domain without specific assumptions of symmetry, centering, or unimodality for the empirical error distribution. The approach is less conservative than the paired overbound method. In return, the construction of the paired overbounding (first step) requires a complex optimization algorithm that is not straightforward to implement. In addition, it is not easy to verify whether a distribution is a two-step overbound of another distribution, as this necessitates to exhibit a first step paired overbound that is compatible with the final overbound.

3.1 Overview of the Problem and Proposed Method

In this section, we consider a user of a GNSS with an augmentation system for positioning. The receiver uses measurements with n independent error sources for its positioning. The error sources can be, for example, orbit determination and time synchronization errors or errors in the estimate of the ionosphere delay or some local effect such as multipath. n will a priori be a multiple of the number of lines of sight in view of the receiver. We will suppose that the user has access to a Gaussian CDF overbound of the range errors for the different error sources via the augmentation system. We assume that the errors are unbiased and independent from each other, but without any further hypotheses on the true range error distributions. The case of biased errors will be developed in Section 4.

In our method for constructing a position protection level for an integrity risk I_R, we first compute the usual Gaussian-associated K-factor (K = Φ⁻¹ (1 – I_R/2), where Φ is the CDF of the normal centered distribution) and then multiply it by an inflation factor A_n,K to account for the asymmetry and possible multimodality of the range error distribution. The origin and calculation of the factor A_n,K are presented in Section 3.2. The inflation factor A_n,K depends only on the number of independent errors n and the integrity risk; thus, this factor can be taken from a table or pre-computed once and for all for a particular integrity context (see Section 3.2.6 for how n may be reduced in specific cases). To this end, numerical values of the inflation factor A_n,K are provided in Table 1. Thus, the complexity of our method is equivalent to the complexity of finding the Gaussian CDF overbound of the range errors.

Here, we provide a few definitions and notations that will be used throughout the remainder of this paper. We state that a Gaussian random variable with standard deviation σ provides a wide-sense CDF overbound of the centered random variable X if the following hold:

$\begin{array}{c}\forall x\le 0,\hspace{1em}{F}_X\left(x\right)\le {\Phi }_{\sigma }\left(x\right)\\ \forall x\ge 0,\hspace{1em}{F}_X\left(x\right)\ge {\Phi }_{\sigma }\left(x\right)\end{array}$4

The only difference between this case and conventional CDF overbounding is that we drop the unimodality and symmetry hypotheses on the distribution of X.

We now suppose that for each error source $X_i$, the user has access to a Gaussian wide-sense CDF overbound of $X_i$ with variance ${\sigma }_i^2$. From these overbounds, we obtain the associated reduced error $Y_i=X_i/{\sigma }_i$. To determine its position, the user performs a (possibly weighted) least-square algorithm, so that the position domain error ℰ is a linear combination of the range-level errors (here, ℰ denotes a one-dimensional component of the position error, for example, the vertical error), i.e., $\exists \left(s_i\right)\in {ℝ}^n$ so that $ℰ={\sum }_i{s}_i{X}_i={\sum }_i{s}_i{\sigma }_i{Y}_i$. We note that ${\sigma }_{pos}^2={\sum }_i{s}_i^2{\sigma }_i^2$ (the variance of the position-level CDF overbound that we would obtain if using the CDF overbound concept), and $\epsilon =ℰ/{\sigma }_{pos}$ (the reduced position error). We have the following:

$\epsilon =\sum _i{Y}_i\times \frac{s_i{\sigma }_i}{{\sigma }_{pos}}=\sum _i{\alpha }_i{Y}_i\hspace{1em}\text{where}\hspace{1em}{\alpha }_i=\frac{s_i{\sigma }_i}{{\sigma }_{pos}}$5

(Note that by construction, the vector of α_i is a Euclidean unit vector, i.e., ||(α_i)||₂ = 1).

The main result of this section is that a knowledge of the Gaussian wide-sense CDF overbounds of each error sources is sufficient to construct a protection level associated with an integrity risk I_R. The protection level is given as follows:

$PL=A_{n,K}\times {\sigma }_{pos}\times K$6

where $K={\Phi }^{-1}\left(1-\frac{I_R}{2}\right)$ and A_n,K is a suitable inflation factor whose origin is detailed in Section 3.2 and whose value is presented in Table 1.

Compared with conventional CDF overbounding, our method can deal with error distributions that are not symmetric or unimodal, which is the case for most error sources in practice. The trade-off is reflected in an inflation factor A_n,K that leads to a larger protection volume, to account for the loss of stability by a linear combination of CDF overbounding. The factor A_n,K is specific to the target integrity risk and depends on the number of contributors entering the user’s position determination. However, for a given integrity context, this factor (or a table of factors with different values of n) only has to be computed once and can be broadcast to the user or saved in an integrity algorithm. Consequently, the wide-sense CDF overbound method is very simple to use and is more robust to assumptions on the error distribution.

3.2 Justification of the Method and Integrity Proof

In this section, we justify the origin of the inflation factor A_n,K. The main idea of the wide-sense CDF overbounding method is based on the observation that the condition in Equation (4) is equivalent to having a paired overbound with half-Gaussian distributions. Unlike Equation (4), the paired overbounding is preserved by linear combination, which allows us to obtain an explicit paired overbound of the user position error. The inflation factor A_n,K is then determined by considering the worst sums of half-Gaussian distributions (from the viewpoint of position error) compared with typical sums of Gaussian distributions. In the last part, we prove that our protection level formula is conservative for the considered integrity risk.

3.2.1 From CDF Overbounding to Paired Overbounding

Let us first consider one reduced error source, $Y_i=X_i/{\sigma }_i$, which has an unknown distribution with density f_i and CDF F_i. By assumption, its distribution is CDF-overbounded by a standard normal distribution (whose probability distribution function and CDF are denoted as ϕ and Φ, respectively):

$\begin{array}{c}\forall x\le 0,\hspace{1em}{F}_i\left(x\right)\le \Phi \left(x\right)\\ \forall x\ge 0,\hspace{1em}{F}_i\left(x\right)\ge \Phi \left(x\right)\end{array}$7

However, in general, F_i does not respect the other hypotheses from the CDF overbound, in particular, the symmetry and unimodality hypotheses (but it is centered, because Equation (7) implies that the median of F_i is 0). Notably, this means that Equation (7) will not be preserved per summation (and linear combination) in the general case.

We note (ϕ_l, Φ_l) and (ϕ_r, Φ_r) as the density and CDF of the two half-Gaussian distributions, defined as follows:

${\Phi }_l\left(x\right)=1_{[-\infty ,0[}\left(x\right)\Phi \left(x\right)+1_{[0,\infty [}\left(x\right)\hspace{1em}\text{and}\hspace{1em}{\Phi }_r\left(x\right)=1_{[0,\infty [}\left(x\right)\Phi \left(x\right)$8

As illustrated in Figure 2, Equation (7) is equivalent to F_i being overbounded on the left by Φ_l and overbounded on the right by Φ_r :

${\Phi }_r\left(x\right)\le F\left(x\right)\le {\Phi }_l\left(x\right)\hspace{1em}\forall x\in ℝ$9

• Download figure
• Open in new tab
• Download PowerPoint

FIGURE 2

Graphical illustration of the equivalence between the CDF overbounding condition in Equation (7) by a normal centered Gaussian distribution (panel (a)) and the paired overbounding condition in Equation (9) by left and right half-Gaussian distributions (panel (b)) for the distribution with CDF $F_X$

The two overbounding conditions cause $F_X$ to fall within the shaded green region.

In contrast to Equation (7), the property in Equation (9) is preserved by summation and linear combination with positive coefficients without additional assumptions on F_i. Because the left and right overbounding distributions are reflections of each other about the vertical axis, i.e., ϕ_l(x) = ϕ_r(–x), the property is also preserved under linear combination with real coefficients.

4.1 Proposed Method

Wide-sense CDF overbounding of a potentially biased random variable X is defined as follows. The Gaussian random variables $G_X^{+}$ and $G_X^{-}$ with identical variance σ² and mean ±b provide a paired wide-sense CDF overbound for an error contributor X to positioning error, if the following hold:

$\begin{array}{c}\forall x\le -b,\hspace{1em}{F}_X\left(x\right)\le F_{G_X^{-}}\left(x\right)\\ \forall x\ge +b,\hspace{1em}{F}_X\left(x\right)\ge F_{G_X^{+}}\left(x\right)\end{array}$14

where b is at least larger than the absolute value of the median of X.

The main idea of the wide-sense CDF overbounding concept is based on the observation that the conditions in Equation (14) allow us to build an overbounding pair ${ℒ}_X$ and ${ℛ}_X$ as two half-Gaussian random variables defined as follows. ${ℒ}_X$ has CDF $F_{{ℒ}_X}\left(x\right)=F_{G_{\overline{X}}}\left(x\right)$ for x ≤ –b and $F_{{ℒ}_X}\left(x\right)=1$ for x > –b, and ${ℛ}_X$ is symmetrically defined as $F_{{ℛ}_x}\left(x\right)=F_{G_x^{+}}\left(x\right)$ for x ≥ b and $F_{{ℛ}_X}\left(x\right)=0$ for x < b.

We consider a GNSS user that computes a position with measurements that have n error contributors $X_i$. We assume that each contributor $X_i$ has a wide-sense CDF overbound with standard deviation σ_i and bias b_i (noting that the bias is positive). For an integrity risk I_R, the user computes a protection level as follows:

$PL=A_{n,K}\times K\times {\sigma }_{pos}+\sum _{i=1}^n\left|s_i\right|b_i$15

where A_n,K is the inflation factor defined in the previous section and listed in Table 1, K is the Gaussian K-factor, and σ_pos is given by ${\sigma }_{pos}^2=\sum _i{s}_i^2{\sigma }_i^2$.

If the strategy of DeCleene (2000) is preferred, the biases can be integrated in an additional inflation factor, leading to the following protection level formula:

$PL={\xi }_{n,K}\times A_{n,K}\times K\times {\sigma }_{pos}$16

where ξ_n,K is provided by Equation (2).

In addition to its simplicity, a major advantage of wide-sense CDF overbounding over paired and two-step overbounding is that it does not require majoration of the distribution on the entire x-axis. In regard to CDF overbounding, the main asset of wide-sense CDF overbounding is the guarantee of integrity without the assumption of symmetry, as demonstrated below.

4.2 Integrity Proof

The aim of this section is to show that wide-sense CDF overbounding of a biased distribution and the use of the protection level formulas in Equation (15) or (16) imply position integrity, as follows:

$\mathbb{P}\left(\right|ℰ|>PL)\le I_R$

where ℰ is the position error, PL is the protection level computed according to the definition of wide-sense CDF overbounding, and I_R is the integrity risk. As in Section 3.2.5, this proof is simply an application of the paired overbounding theorem and of our previous definitions and is presented here to summarize the arguments stated above.

For the protection level defined in Equation (15), the proof consists of the following steps:

$\begin{array}{cc}\mathbb{P}\left(\right|ℰ|>PL)& =\mathbb{P}\left(\sum _{i=1}^n{s}_i{X}_i<-A_{n,K}K{\sigma }_{pos}-\sum _{i=1}^n\left|s_i\right|b_i\right)+\mathbb{P}\left(\sum _{i=1}^n{s}_i{X}_i>A_{n,K}K{\sigma }_{pos}+\sum _{i=1}^n\left|s_i\right|b_i\right)\\ & \le \mathbb{P}\left(\sum _{i=1}^n\left|s_i\right|{ℒ}_{X_i}<-A_{n,K}K{\sigma }_{pos}-\sum _{i=1}^n\left|s_i\right|b_i\right)+\mathbb{P}\left(\sum _{i=1}^n\left|s_i\right|{ℛ}_{X_i}>A_{n,K}K{\sigma }_{pos}+\sum _{i=1}^n\left|s_i\right|b_i\right)\\ & =\mathbb{P}\left(\sum _{i=1}^n\frac{\left|s_i\right|{\sigma }_i}{{\sigma }_{pos}}\left(\frac{{ℒ}_{X_i}+b_i}{{\sigma }_i}\right)<-A_{n,K}K\right)+\mathbb{P}\left(\sum _{i=1}^n\frac{\left|s_i\right|{\sigma }_i}{{\sigma }_{pos}}\left(\frac{{ℛ}_{X_i}-b_i}{{\sigma }_i}\right)>A_{n,K}K\right)\\ & \le \mathbb{P}\left({ℒ}_n^{*}<-A_{n,K}K\right)+\mathbb{P}\left({ℛ}_n^{*}>A_{n,K}K\right)\\ & \le \frac{I_R}{2}+\frac{I_R}{2}=I_R\end{array}$17

Step-by-step, we have the following:

• In line 1, we apply the definition of the position error ℰ and protection level from Equation (15).

• For line 2, we use the fact that all $X_i$ are paired-overbounded by ${ℒ}_{X_i}$ and ${ℛ}_{X_i}$ and that paired overbounding is preserved by linear combination.

• Line 3 is a rearrangement of terms to make apparent the normal centered half-Gaussians $\frac{{ℒ}_{X_i}+b_i}{{\sigma }_i}$ and $\frac{{ℛ}_{X_i}-b_i}{{\sigma }_i}$ that were considered in Section 3.

• Line 4 uses the fact that ${\alpha }_i=\frac{\left|s_i\right|{\sigma }_i}{{\sigma }_{pas}}$ forms a Euclidean unit vector, reducing to the case treated in Section 3.

For the protection level defined in Equation (16), an additional step must be added to demonstrate that the overbounding bias can be integrated in the inflation factor of the standard deviation ξ. This demonstration is identical to that provided by DeCleene (2000).