1

Performance Bounds for Finite Moving Average
Change Detection Applied to GNSS
Daniel Egea-Roca⋆, Gonzalo Seco-Granados⋆, José A. López-Salcedo⋆, H. Vincent Poor†

arXiv:1706.05552v1 [cs.IT] 17 Jun 2017

⋆

Department of Telecommunications and Systems Engineering, Universitat Autònoma de Barcelona (UAB), Bellaterra, Spain
†
Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, USA

Abstract—Due to the widespread deployment of Global Navigation Satellite Systems (GNSSs) for critical road or urban
applications, one of the major challenges to be solved is the
provision of integrity to terrestrial environments, so that GNSS
may be safety used in these applications. To do so, the integrity
of the received GNSS signal must be analyzed in order to detect
some local effect disturbing the received signal. This is desirable
because the presence of some local effect may cause large position
errors, and hence compromise the signal integrity. Moreover,
the detection of such disturbing effects must be done before
some pre-established delay. This kind of detection lies within the
field of transient change detection. In this work, a finite moving
average stopping time is proposed in order to approach the signal
integrity problem with a transient change detection framework.
The statistical performance of this stopping time is investigated
and compared, in the context of multipath detection, to other
different methods available in the literature. Numerical results
are presented in order to assess their performance.
Index Terms—Transient Change Detection, Stopping Time,
Finite Moving Average, GNSS, Signal Integrity.

I. I NTRODUCTION
Recently, there has been an increasing interest in Global
Navigation Satellite System (GNSS)-based safety- and
liability-critical applications [1]. These applications, which
are often associated with terrestrial environments, have very
stringent requirements in terms of accuracy, continuity and
integrity of the provided position solution. Besides providing
an accurate navigation solution, timely warnings must be
provided to the user when the system should not be used;
this capability is referred to as the integrity of the system.
The concept of GNSS integrity was originally developed for
civil aviation [2]. In particular, civil aviation standards specify
a set of minimum performance requirements for each operation
and phase of flight [3]. Nevertheless, a standalone GNSS
receiver cannot meet the stringent civil aviation requirements,
and then various augmentation systems have been developed
to fulfill these requirements. These systems are classified
according to their infrastructure into Ground-, Satellite-, and
Aircraft-Based Augmentation Systems (GBAS, SBAS and
ABAS) [2]. They constitute powerful methods providing the
user with integrity information. However, their infrastructure
is very complex and therefore costly.
It is for this reason that Receiver Autonomous Integrity
Monitoring (RAIM) techniques were designed based on calThis work was partly supported by the Spanish Grant TEC2014-53656-R,
the European Commission iGNSSrx project, and the U.S. National Science
Foundation under Grant ECCS-1549881.

culations performed within the user equipment itself [4]–[6].
These techniques rely on redundant measurements coming
from different satellites, which are feasible to obtain in civil
aviation. However, this is not the case in terrestrial environments, where a plethora of obstacles blocking the signal of
different satellites may be present. Moreover, both SBAS and
RAIM assume that local effects like multipath, interference
and spoofing have a controlled influence on the GNSS signal.
This is really the case for civil aviation but it is not for
terrestrial environments, so that position errors and, thus,
integrity are strongly affected [7].
Hence, in terrestrial-critical applications, it is of paramount
importance to promptly detect any possible anomaly or misleading behavior that could be endangering the received GNSS
signal. Otherwise, the safety and trust of the end-user position
and time could be jeopardized. We refer to this capability
as signal integrity, which is currently a concern within the
GNSS community [7], [8]. Moreover, for integrity purposes,
an acceptable detection delay is limited by a given value m, so
that late detections (i.e. delayed more than m) are considered
as missed. This kind of detection lies on the field of sequential
change detection, including quickest change detection (QCD)
and transient change detection (TCD).
The traditional QCD problem deals with a change (i.e.
anomaly) of infinite duration. The optimal criterion in this case
is to minimize the detection delay subject to a level of false
alarms. Comprehensive overviews of this kind of detection
can be found in [9] and [10]. In the present work, we focus
on non-Bayesian approaches in which the change time v is
modeled as being unknown but non-random. For this kind
of approach, the CUSUM algorithm was first proposed as a
continuous inspection scheme in the 1950s [11], but it was
not until 1971 that its optimality for the QCD problem was
established asymptotically (i.e. when false alarms go to zero)
[12]. More than a decade later, Moustakides [13] proved that
the CUSUM is also non-asymptotically optimal.
In contrast, the TCD problem deals with finite change
duration and then a bounded detection delay is desired. Unfortunately, the traditional QCD criterion (i.e. minimizing the
detection delay) does not completely fit into this problem. In
this case, we wish to minimize the probability of missed detection (i.e. late detections) subject to a level of false alarms. This
criterion was first adopted in [14] for the Bayesian approach,
but without controlling the false alarm rate. Recently, the
authors of [15] considered a semi-Bayesian approach imposing
a suitable constraint on the false alarm rate. Very recently, the

2

first optimal results for the non-Bayesian case were provided
by Moustakides in [16]. Nevertheless, it is worth mentioning
that all of these works have considered the very particular case
of m = 1, which has limited practical application.
A. Related Literature
In order to improve integrity in terrestrial environments we
have to detect local effects as soon as possible in order to
quickly alert the user. These effects are well-known problems
within the GNSS community, leading to a plethora of contributions in the existing literature for interference [17], [18], multipath [19], [20] and spoofing [21], [22] detection. However, all
the existing contributions have adopted a classical detection
framework, which is not well suited to fulfill the integrity
requirements of safety-critical applications. For the prompt
detection of integrity threats, it is essential to formulate the
problem under the framework of sequential change detection.
The QCD framework has been extensively applied to a
wide range of fields such as distributed detection in sensor
networks [23], signal detection in multi-antenna receivers [24]
and spectrum sensing in cognitive radio [25], just to mention a
few. Nevertheless, it has barely been used in the GNSS arena.
Based on this observation, we already addressed the problem
of detecting local degrading effects in a QCD framework.
Specifically, we addressed the problem for the case of multiantenna GNSS receivers (see [26], [27]), and for singleantenna receivers in [28] and [29]. Finally, a comprehensive
overview of interference and multipath quickest detection was
provided in [30] and [31], respectively, including an extensive
analysis with real signals. The results in [31] corroborated
the improvements of incorporating signal integrity into the
positioning accuracy and integrity.
Nonetheless, all of these contributions adopted the framework of QCD. However, for integrity purposes, a bounded
delay is desirable and then we should rely on the framework
of TCD. Moreover, we are interested in non-Bayesian approaches. Several approaches have been proposed in the last
decade. Standard solutions are based on the CUSUM algorithm
[32]–[36]. Unfortunately, almost all available results are applicable to off-line detection on finite observation intervals and
they adopt the traditional criterion of QCD. Exceptions, adopting the probability minimization criterion, are [35], which
applies the CUSUM algorithm for GNSS integrity (at position
level), and [36], which proposes a windowed version of the
CUSUM for monitoring the quality of drinking water.
B. Contributions
The TCD framework has not been applied so far to the
problem of signal integrity. Moreover, for the more general
case of finite m > 1, which is the case of GNSS signal
integrity, and to the best of the authors’ knowledge, no optimal
solution has been found for the TCD problem. On the other
hand, the Finite Moving Average (FMA) stopping time has
been shown to be the optimal windowed CUSUM solution
(i.e. using the last m samples) for the Gaussian mean change
case [36]. Based on these observations, we propose the use of
an FMA stopping time for approaching the general problem

of TCD, in general, and signal integrity monitoring in GNSS,
in particular.
Hence, the contribution of this work is twofold. Firstly,
we theoretically investigate the statistical performance of the
FMA stopping time, based on the new optimal criterion of
probability minimization, for any general case. This leads
to the provision of novel bounds valid for any kind of
change and not restricted to the Gaussian mean change. These
bounds are more tight than those available in the literature for
other approaches, drastically benefiting the availability of the
integrity algorithm. These bounds were briefly introduced in
[37]. In this work, though, we provide a more extensive and
complete proof.
Finally, we show with numerical results that the FMA
stopping time outperforms other methods available in the
literature for the TCD. This is done in the setting of signal level
integrity in GNSS, when dealing with multipath detection.
This was briefly introduced in [37] for the carrier-to-noise
ratio (C/N0 ) metric, which was modeled as a Gaussian mean
change. Here, we provide a more extensive analysis including
the three multipath detection techniques presented in [31],
including all possible changes in a Gaussian distribution
(i.e. mean or/and variance changes). Moreover, we present
numerical results analyzing the availability of the proposed
signal integrity algorithm.
The rest of the paper is organized as follows: Section II
provides background on sequential change detection, including
both QCD and TCD, and introducing the proposed FMA stopping time. Next, Section III presents the statistical properties
of the FMA stopping time. Then, Section IV investigates the
application of these results to the analyzed multipath detection
metrics. Finally, Section V presents our numerical results,
while Section VI concludes the paper.

II. BACKGROUND

ON SEQUENTIAL CHANGE DETECTION

A change detection algorithm, including QCD and TCD, is
completely defined by its stopping time T at which the change
is declared. In general, a change detection algorithm can be
modeled as follows: Let {xn }n≥1 be a random sequence observed sequentially providing information about some integrity
threat, and let v be the instant (in samples) when the integrity
threat appears. We consider a family {Pv |v ∈ [1, 2, . . . , ∞]}
of probability measures, such that, under Pv , x1 , . . . , xv−1 and
xv+m , . . . , x∞ , with m the change duration, are independent
and identically distributed (iid) with a fixed marginal probability density function (pdf) f0 , corresponding to the normal
conditions (i.e. the integrity threat is not present, H0 ). On the
other hand, xv , . . . , xv+m−1 are iid with another marginal pdf
f1 6= f0 , corresponding to the abnormal conditions (i.e. the
integrity threat is present, H1 ).
In this section, we firstly briefly recall the problem of QCD.
Secondly, we introduce the problem of TCD. Finally, the idea
of windowed solutions and the FMA stopping time proposed
in this paper are presented.

3

A. Quickest change detection (QCD): CUSUM stopping time
The statistical model for QCD is described as follows:

H0 : f0 (x) if n < v
xn ∼
,
(1)
H1 : f1 (x) if n ≥ v

where in this case m = ∞.
Denoting Ev as the expectation under the probability measure Pv the effectiveness of QCD has been traditionally
quantified by the minimization of [12]:
i
h
+
(2)
d(T ) = sup essup Ev (T − v + 1) |x1 , . . . , xv−1
v≥1

among all stopping times T satisfying E∞ (T ) ≥ γ, where
(x)+ = max(0, x), essup denotes the essential supremum, and
γ > 0 a finite constant. That is, we seek a stopping time T
that minimizes the delay d(T ) within a lower-bound constraint
on the mean time between false alarms E∞ (T ).
The following CUSUM stopping time was proposed in [11]:


n
.
. X
TC (h) = inf n ≥ 1 : max Skn ≥ h ; Skn =
LLR(i),
1≤k≤n

i=k

(3)
.
where LLR(i) = ln(f1 (xi )/f0 (xi )) is the log-likelihood ratio
(LLR) of the observation xi and h is the detection threshold.
The first optimal results of the CUSUM in the sense of the
criterion in (2) were shown in [12] and [13], in an asymptotic
(i.e. γ → ∞) and non-asymptotic (i.e. for all finite γ) way,
respectively. However, as shown in [38], the requirement of
having large values of E∞ (T ) does not guarantee small values
of the probability of false alarm P∞ (l ≤ T < l + mα ) within
a fixed interval of length mα , for all l ≥ 1. As a result, [38]
proposed to replace the traditional constraint E∞ (T ) ≥ γ
by the following constraint on the worst-case probability of
false alarm within any interval of length mα , which is more
convenient for safety-critical applications:
.
Pfa (T, mα ) = sup P∞ (l ≤ T < l + mα ) ≤ α.
(4)
l≥1

It was shown in [38] that the CUSUM stopping time TC
asymptotically minimizes (as Pfa → 0) the detection delay,
over all stopping times T satisfying (4), if h fulfills the
following equation:
Pfa (TC , mα ) ≤ mα e−h .

(5)

We observe from (2) that no hard limit is imposed on
the detection delay; consequently, this quantity can become
arbitrarily large. In this sense, the optimality criteria for the
TCD problem should be modified in order to seek a small
probability of missed detection given an acceptable false alarm
rate. In other words, we wish to have v ≤ T < v+m. Stopping
within the prescribed interval constitutes a desirable event
while stopping at T ≥ v + m is considered a missed detection.
This is equivalent to the optimality criterion introduced in [16]
and [36], used through this paper, which involves the following
minimization:


.
(7)
inf Pmd (T, md ) = sup Pv (T ≥ v + md |T ≥ v)
T ∈Cα

v≥1

among all stopping times T ∈ Cα satisfying
Cα = {T : Pfa (T, mα ) ≤ α} ,

(8)

where md denotes the maximum permitted detection delay and
Pmd and Pfa stand for the worst-case probabilities of missed
detection and false alarm within any interval of length mα ,
respectively, with Pfa defined as in (4). As we will see, this
criterion is very convenient for GNSS integrity monitoring.
This article belongs to the second class of TCD problem
stated above (i.e. safety-critical applications); in this case a
detection with a delay greater than md is considered as missed,
even if m > md . On the other hand, if the duration of the
change m is smaller than md , then such a change is considered
less dangerous because its impact on the system is limited or
negligible. It is for this reason that the duration m is considered
to be known henceforth and equal to md (i.e. m = md ).
Indeed, for integrity algorithms, we can fix m as m = Fs · ttta
(similarly mα = Fs · tα ), with Fs the sampling rate of xn ,
and ttta the so-called time to alert (TTA), which is given by
norms and standards [3], as well as tα . Very recently, the
optimal solution of this class of TCD problem, for m = 1,
was shown to be the Shewhart test [16]
.
TS (h) = inf {n ≥ 1 : LLR(n) ≥ h} .

(9)

Indeed, this is the only available result on optimality for the
criterion in (7)–(8). Nevertheless, for the case of finite m > 1,
which is the case of integrity monitoring, no optimal solution
has been found yet, so the problem is still open.

B. Transient change detection (TCD): Shewhart stopping time
Unlike QCD, in which the change duration m is assumed to
be infinite, the change duration in TCD problems is assumed
to be finite. This is modeled as

H0 : f0 (x) if n < v or n ≥ v + m
xn ∼
. (6)
H1 : f1 (x) if v ≤ n < v + m
As discussed in [36], there are two types of TCD problems.
The first type involves the detection of suddenly arriving
signals of random unknown duration. In this case m denotes
the unknown duration of the change. The second type involves
safety-critical applications where the maximum permitted detection delay is a priori fixed to a pre-established value, and
then m is considered to be known.

C. Windowed solutions: WLC and FMA stopping times
Since there is no optimal solution available in the literature
of TCD for a finite m > 1, we propose a windowed solution
based on the following idea: We know that the optimal solution
for QCD, that is for m = ∞, is the CUSUM test [13], which
uses information about all the past samples. On the other hand,
the Shewhart test, which uses information of one sample, is
established to be optimal for the non-Bayesian TCD problem
with m = 1 [16]. Hence, it is intuitive to think that the optimal
solution for 1 < m < ∞ would be some test statistic between
these two techniques, and particularly, a test statistic using
information about m samples (i.e. windowed).

4

In this context, a window-limited CUSUM (WLC) test
is proposed in [36] by using at each moment the m last
observations, only. The stopping time is given by


.
TWL (h) = inf n ≥ m :
max
Skn ≥ h .
(10)
n−m+1≤k≤n

It is assumed that the WLC is not operational during the first
m − 1 observations. It is also shown that the optimal WLC
stopping time, with respect to the criterion in (7)-(8), for a
Gaussian mean change leads to
)
(
n
 
X
∗
xi ≥ h̃ ,
(11)
TWL
h̃ = inf n ≥ m :

selected in order to satisfy this constraint, and then Pmd turns
out to be a function of the fixed α (i.e. Pmd (TF (h(α̃)), m)).
In some sense, Pmd (TF (h(α̃)), m) plays the same role in the
TCD theory as the Cramér-Rao lower bound in estimation
theory, or as the receiver operating characteristic (ROC) in
classical detection. Moreover, this kind of ROC allow us to
compare the performance of different algorithms in terms of
the optimality criterion in (7). This relation between Pmd and
Pfa is given in the following corollary.
Corollary 1. Let Fi , with i = {0, 1}, be the cumulative
distribution function (cdf) of Sm under Hi and let h be
selected so that

i=n−m+1

where h̃ denotes the chosen threshold.
Inspired by this result and the idea of windowed solution,
in this paper we propose the use of an FMA stopping time for
any general TCD problem, which becomes
.
n
TF (h) = inf {n ≥ m : Sn ≥ h} ; Sn = Sn−m+1
.
(12)
It is worth noting that this stopping time is equivalent to
an FMA test with the LLR of a Gaussian mean change.
Furthermore, the use of the FMA stopping time is motivated
by the fact, as we will show next, that we can obtain tight
bounds for both the probabilities of missed detection and false
alarm. On the contrary, the bounds available in the literature
for these probabilities for the CUSUM and WLC are not that
tight. This is a key factor for the integrity problem since it
considerably improves the availability of the algorithm.
III. S TATISTICAL P ERFORMANCE
T IME

OF THE

FMA S TOPPING

The goal of this section is to theoretically investigate the
statistical performance of the FMA stopping time TF (h);
that is, to determine the worst-case probability of missed
detection Pmd (TF (h), m) and the worst-case probability of
false alarm for a given duration mα , Pfa (TF (h), mα ). The
exact calculation of these probabilities is very complicated,
and it is here where the existence of tight-enough bounds is of
practical interest. These bounds are stated in the next theorem.
Theorem 1. Let us considerPthe FMA stopping time TF (h) in
m
(12) and let Sm = S1m = i=1 LLR(i); then the worst-case
probability of false alarm for a given duration mα is bounded
as
Pfa (TF (h), mα ) ≤ α (h, mα ) ,
(13)
where
α (h, mα ) = 1 − [P∞ (Sm < h)]

mα

.

(14)

On the other hand, the worst-case probability of missed
detection is bounded as
Pmd (TF (h), m) ≤ β(h, m),

(15)

β(h, m) = P1 (Sm < h) .

(16)

where
Proof: The proof is given in Appendix A.
In practice, values α for Pfa are imposed, so that we have
to guarantee that Pfa ≤ α̃. Thus, the threshold h has to be

Pfa (TF (h), mα ) ≤ α̃,

(17)

with α̃ a desirable constant value for the probability of false
alarm. Hence
i
h
1/mα
,
(18)
h (α̃) = F0−1 (1 − α̃)
where F0−1 is the inverse of F0 , and thus
ii
h
h
β (h (α̃) , m) = F1 F0−1 (1 − α̃)1/mα .

(19)

Moreover,

   
(20)
Pmd TF h̃ , m ≤ β (h (α̃) , m) ,
  

with h̃ the threshold such that Pfa TF h̃ , mα = α̃.

Proof: It is straightforward to see that Pj (Sm < h) =
Fi (h), with j = {∞, 1} and i = {0, 1}, is the cdf of Sm
under Hi , respectively, evaluated at h. Hence, from (13) and
(14) we can fix the threshold h as
i
h
(21)
h = F0−1 (1 − α̃)1/mα ,

guaranteeing that Pfa (TF (h), mα ) ≤ α̃, and (18) thus follows.
The proof of (19) follows immediately by the definition of
the cdf F1 and by substituting (21) into (16). In order to
prove
noting that the threshold h̃, such that

 it is worth
 (20)
Pfa TF h̃ , mα = α̃, is lower than h (i.e. h̃ < h) and that

   

(22)
Pmd TF h̃ , m ≤ β h̃, m ≤ β (h, m) ,
where the last inequality follows because β(h, m) in (16) is a
monotonically increasing function on h, so that (20) follows.

The previous results are valid for the general FMA stopping
time. That is, they are not restricted to the Gaussian mean
change, as derived in [36], but they are valid for any kind
of change. Moreover, as we will see later, these bounds
are tighter than bounds for other available methods in the
literature. This is beneficial for the availability of integrity
algorithms. Unfortunately, we cannot establish the optimality
of the proposed FMA stopping time in the class Cα . To do
so we should analyze the speed of convergence of the term
F0−1 [(1 − α)1/mα ], which is beyond the scope of this paper.
Nonetheless, in [36] the optimality of the FMA stopping time
is shown for the particular case of a Gaussian mean change. In
addition, we will show later how the proposed FMA stopping

5

time outperforms other available methods in the literature.
This makes it evident that the FMA stopping time is a good
candidate for TCD problems, and thus for integrity monitoring.
IV. S IGNAL I NTEGRITY M ETRICS
Integrity algorithms are based on the so-called integrity risk,
which is defined as the probability that an integrity threat
is present without raising an alarm within the TTA. This is
equivalent to the probability of missed detection defined in (7).
On the other hand, constraints on the false alarms are given in
the form of (8). It is for this reason that the TCD framework
perfectly fits with integrity algorithms. Specifically, values β̃
and α̃ for the integrity risk and probability of false alarms are
given by norms and standards. Then, the detection threshold is
fixed so that Pfa ≤ α̃ and if Pmd ≤ β̃ the algorithm is declared
available, otherwise the algorithm is not available because it
cannot guarantee integrity within the desired requirements.
If the algorithm is available, an alarm will be raised based
on some integrity metric able to detect integrity threats. For
details on GNSS integrity algorithms see [2].
We focus on signal integrity, henceforth termed sig-RAIM.
One of the crucial factors in sig-RAIM is the computation
of the signal integrity metric. Indeed, we will have different
metrics providing information about different signal integrity
threats. These threats come from the local effects we may
encounter in terrestrial environments, mainly including multipath, radio-frequency interference and spoofing. Hence, different metrics should be available for detecting these kinds of
local effects. Moreover, for the same threat (e.g. interference)
we should use different metrics in order to be able to detect
a wide range of situations covering different behaviors of the
same threat (e.g. wide-band, narrow-band, . . . ) [30], [31]. The
key point of these metrics is that they are computed from
signal features such as the statistical properties, time-frequency
behavior, correlation function, etc., and so we do not need
additional measurements coming from different satellites (as
is the case of traditional RAIM [6]). This is important because
it allows computing these metrics in terrestrial environments,
where redundant information is scarce.
A complete overview of interference and spoofing detection metrics can be found in [30] and [21], respectively. In
this work, we focus on multipath detection metrics, referred
as to signal integrity metrics henceforth. In particular, the
presented metrics in this work are introduced in [31] in a
QCD framework, including the C/N0 , the code discriminator
output (DLLout) and the slope asymmetry metric (SAM),
which are measurable metrics after the correlation process in
a GNSS receiver. In order to fix the detection threshold h
and to compute the integrity risk Pmd given by this threshold
(rather β(h, m)), which are needed for the operation
Pm of sigRAIM, we have to obtain first the cdf of Sm = i=1 LLR(i),
which depends on the signal integrity metric used to feed the
detection algorithm.
In general, the presented signal integrity metrics can be
modeled as Gaussian random variables [31], and then we
model the problem as a change on a Gaussian distribution:

H0 : N (µ0 , σ02 ) if n < v or n ≥ v + m
xn ∼
, (23)
H1 : N (µ1 , σ12 ) if v ≤ n < v + m

p
.
where N (µi , σi2 ) = (1/ 2πσi2 ) exp(−(x − µi )2 /2σi2 ) is the
normal pdf with mean µi and variance σi2 , given by the mean
and variance of xn under Hi . Hence, in general, we have
 
(xn − µ0 )2
(xn − µ1 )2
σ0
+
−
. (24)
LLR(n) = ln
σ1
2σ02
2σ12
It is worth pointing out that the parameters under H1 are
unknown, and so we will use tuning parameters (λ̃) with the
aim of avoiding nuisance parameters. These parameters should
be fixed as the minimum change we want to detect, which will
be given by
.
λ̃ = q(ǫ),
(25)
with ǫ the maximum allowable positioning error without
issuing an alert and q(·) mapping positioning errors to change
parameters.
The goal of this section is to statistically characterize the
multipath detection metrics to use them for sig-RAIM. This
is done by using the general expression of the LLR in (24)
and particularizing it for the different metrics presented in this
work. So, we obtain the LLR distribution for the different
metrics and then we obtain the cdf of Sm . We start with
the simpler cases of having a change in either the mean or
variance of a Gaussian distribution, which are the cases of the
C/N0 and DLLout metrics, respectively. Finally, we present
the most general case of having both a change in the mean
and variance of a Gaussian distribution, which is the case of
the SAM metric.
A. C/N0 metric (Gaussian mean change)
In this section, we analyze the statistical characterization
of the LLR for the C/N0 metric. First, let us introduce the
statistical model, given in [31]

H0 : N (µc,0 , σc2 )
xn,c ∼
,
(26)
H1 : N (µc,1 , σc2 )
with xn,c the C/N0 samples, µc,0 and σc2 the known mean
and variance of xn,c under H0 , and µc,1 the unknown change
parameter, denoting the mean of xn,c under H1 . For the sake
of notational simplicity, we have omitted the time conditions in
each hypothesis (i.e. if n < v or n > v+m, . . . ) corresponding
to the TCD model. Thereby, we model the appearance of
multipath as a change in the mean of a Gaussian distribution,
and then the following result is obtained.
Corollary 2. Let µ̃c,1 and µc,1 be the tuned change parameter,
as in (25), and the actual change parameter, respectively, and
let µc,0 and σc be known. Therefore the LLR for the C/N0 is
given by


µ̃c,1 + µc,0
µ̃c,1 − µc,0
xn,c −
, (27)
LLRc (n) = yn =
σc2
2
with mean and variance equal to
2

(µ̃c,1 − µc,0 )
, σy2 = −2µy,0,
2σc2


µ̃c,1 + µc,0
µ̃c,1 − µc,0
µ
−
.
=
c,1
σc2
2

µy,0 = −
µy,1

(28)

6

Now, let TF,C (hc ) be the FMA stopping time in (12) for
the C/N0 metric with LLR in (27) and threshold hc so that
Pfa (TF,C (hc ), mα ) ≤ α̃, and let Φ(x) denote the cdf of the
standard normal distribution. Hence
q
i
h
(29)
hc (α̃) = mσy2 Φ−1 (1 − α̃)1/mα + mµy,0 ,


hc − mµy,1 
Pmd (TF,C (hc ) , m) ≤ βC (hc , m) = Φ  q
,
mσy2

(30)

mα
h
−
mµ
c
y,0 
. (31)
Pfa (TF,C (hc ) , mα ) ≤ 1 − Φ  q
2
mσy
 

Proof: The change in the C/N0 metric is modeled as
a Gaussian mean change and thus, substituting µ0 = µc,0 ,
µ1 = µ̃c,1 and σ0 = σ1 = σc into (24), (27) follows after
simple calculus. Thereby, it is trivial to see, from (27) and
(26), that the LLR for the C/N0 is Gaussian distributed in
both hypotheses, with mean and variance as in (28). Hence,
Pm
(c)
Sm = i=1 LLRc (i) is Gaussian as well, but with mean and
variance scaled by a factor m, and (29)–(31) thus follows by
direct application of Theorem 1 and Corollary 1.
B. DLLout metric (Gaussian variance change)

Now, we analyze the characterization of the LLR for the
DLLout metric, which is modeled as [29], [31]

2
H0 : N (0, σd,0
)
xn,d ∼
,
(32)
2
H1 : N (0, σd,1 )
2
with xn,d the DLLout samples, σd,0
the known variance under
2
H0 , and σd,1 the unknown variance under H1 . Thereby, we
model the appearance of multipath as a change in the variance
of the DLLout samples, obtaining the following result.
2
2
and σd,1
be the tuned change parameter,
Corollary 3. Let σ̃d,1
as in (25), and the actual change parameter, respectively, and
let σd,0 be known, then the LLR for the DLL is given by

LLRd (n) = ax2n,d + c,
with
a=

2
2
σ̃d,1
− σd,0
;
2 σ̃ 2
2σd,0
d,1

c = ln



σd,0
σ̃d,1

σ1 = σ̃d,1 and µ0 = µ1 = 0 into (24), (33) follows. Thereby,
(d) . P
under H1 , and denoting Sm = m
i=1 LLRd (i), we have
2

m
X
xn,d
(d)
2
+ mc
Sm |H1 = a
σd,1
σd,1
n=1
(38)
m
X
2
= k1
Xn + mc,
n=1

with Xn ∼ N (0, 1) a standard Gaussian random variable. A
similar result is obtained under H0 , and then we can write
(d)
Sm |Hi = ki X̃ + mc, with i = {0, 1} and X̃ a chi-squared
random variable with m degrees of freedom. Hence,
(d)

Hi :

(39)

where χ2m stands for the chi-squared pdf with m degrees of
freedom, and (35)–(37) thus follow by direct application of
Theorem 1 and Corollary 1.
C. SAM metric (General Gaussian Change)
Previously, we have analyzed the characterization of the
LLR for the particular cases of having a change in either the
mean or variance of a Gaussian distribution. In this section,
we analyze the characterization of the LLR for the most
general case of having a change in both mean and variance
of a Gaussian distribution. This is the case of the SAM-based
detection, which is presented in [28] and [31] as

2
H0 : N (µs,0 , σs,0
)
xn,s ∼
,
(40)
2
H1 : N (µs,1 , σs,1 )
2
with xn,s the SAM samples, {µs,0 , σs,0
} the known mean and
2
variance of xn,s under H0 , respectively, and {µs,1 , σs,1
} the
unknown change parameters, denoting the mean and variance
of xn,s under H1 , respectively. Thereby, we model the appearance of multipath as a change in the mean and variance
of the SAM samples, and then, from (24) and after some
manipulations, we can write the LLR of the SAM metric as

(33)


Sm − mc
∼ χ2m ,
ki

LLRs (n) = as x2n,s + bs xn,s + cs ,

(41)

with
.

(34)

Now, let TF,D (hd ) be the FMA stopping time for the DLLout metric with LLR in (33) and threshold hd so that
Pfa (TF,D (hd ), mα ) ≤ α̃, and let Γm (x) denote the cdf of
the chi-squared distribution with m degrees of freedom, and
2
ki = σd,i
a, with i = {0, 1}. Hence,


1/mα
+ mc,
(35)
(1 − α̃)
hd (α̃) = k0 Γ−1
m


hd − mc
, (36)
Pmd (TF,D (hd ), m) ≤ βD (hd , m) = Γm
k1


mα
hd − mc
.
(37)
Pfa (TF,D (hd ), mα ) ≤ 1 − Γm
k0
Proof: The change in the DLLout metric is modeled as
a Gaussian variance change and thus, substituting σ0 = σd,0 ,

2
2
2
2
σs,0
µ̃s,1 − σ̃s,1
µs,0
σ̃s,1
− σs,0
; bs =
;
2
2
2
2
2σs,0 σ̃s,1
σs,0 σ̃s,1


2
2
σ̃s,1
µ2s,0 − σs,0
µ̃2s,1
σs,0
+
,
cs = ln
2 σ̃ 2
σ̃s,1
2σs,0
s,1

as =

(42)

where µ̃s,1 and σ̃s,1 are the tuned change parameters.
In this case we cannot find the distribution of LLRs (n)
in an straightforward way as for the previous cases. Here, in
(s) . Pm
order to find the pdf of Sm = i=1 LLRs (i), we make use
of the so-called Edgeworth series approximation and Extreme
Value Theory (EVT), which provide a very tight closed-form
expression for the bounds for the FMA stopping time of the
SAM metric, TF,S (hs ) [39]. For the sake of notational clarity,
(s)
(s)
let us write Sm as the random variable Zs (i.e. Zs = Sm ).
Thereby, we can state the following result.

7

0

0

10
Worst−case probability of missed detection

Worst−case probability of missed detection

10

−1

10

−2

10

Shewhart
(5) −−> h(Pfa) −−> (34)
WLC
CUSUM
(33) −−> h(Pfa) −−> (34)
FMA

−3

10

−2

10

Shewhart
(5) −−> h(Pfa) −−> (48)
WLC
CUSUM
(47) −−> h(Pfa) −−> (48)
FMA

−3

10

−4

−4

10

−1

10

10
−4

10

−3

−2

−1

−4

10
10
10
Worst−case probability of false alarm (Pfa)

10

−3

−2

−1

10
10
10
Worst−case probability of false alarm (Pfa)

Fig. 1. Simulated ROC for the C/N0 (left) and SAM (right) FMA stopping times and their competitors (i.e. CUSUM, WLC and Shewhart), with the theoretical
results given in (30)–(31) and (44)–(45), respectively, and those obtained with (5) for the bound of the probability of false alarms.

2
Corollary 4. Let µs,i and σs,i
, with i = {0, 1}, be the actual
mean and variance of the SAM metric under hypothesis Hi ,
and let as , bs and cs be defined as in (42). Now, let TF,S (hs )
be the FMA stopping time for the SAM metric with LLR in
(41) and threshold hs so that Pfa (TF,S (hs ), mα ) ≤ α̃, and let
.
φ(x) = N (0, 1) be the standard normal pdf. Hence, we have

ln (− ln (1 − α̃))
,
γ
Pmd (TF,S (hs ) , m) ≤ βS (hs , m) = Fs,1 (hs ) ,


Pfa (TF,S (hs ) , mα ) ≤ 1 − exp −e−γ(hs−δ) ,
hs (α̃) = δ −

with



1
1−
δ=
,
mα
γ = mα fs,0 (δ) ,
−1
Fs,0

A. Evaluation of the probability minimization criterion
(43)
(44)
(45)

(46)

and
Fs,i (z) = Φ(z̃i ) − σzs ,i φ(z̃i )

X

Ck,Hi Hk−1 (z̃i ),

k∈A

"

fs,0 (z) = φ(z̃0 ) 1 +

X

k∈A

#

It is worth pointing out that in the previous section we have
included the unknown change parameters in the theoretical
analysis. Here, we will see the effect of the knowledge of
these parameters in the integrity risk calculation.

(47)

Ck,H0 Hk (z̃0 ) ,

where A = {3, 4, 6}, Ck,Hi , with i = {0, 1}, are the
coefficients Ck (expressions can be found in Appendix B)
under Hi , Hk (z) is the Hermite polynomial of degree k
evaluated at z and z̃i = (z − µzs ,i )/σzs ,i , with



2
+ µ2s,i + bs µs,i + cs ,
µzs ,i = m as σs,i
 2 


2
σz2s ,i = m σs,i
+ 2as µ2s,i + bs µs,i + b2s .
2as as σs,i
(48)
V. N UMERICAL R ESULTS
The aim of this section is to firstly compare the proposed
FMA stopping time with other approaches in the literature of
TCD. This is done in the setting of sig-RAIM by considering
the case of multipath detection. Secondly, the availability of
the sig-RAIM algorithm is analyzed for the different used integrity signal metrics and compared with the other approaches.

Here, we compare the FMA stopping time with those
stopping times currently available in the literature of TCD.
This comparison is done with both simulated and available theoretical results. The simulated results include the calculation
of the worst-case probability of missed detection (i.e. integrity
risk) Pmd (TF (h), m) as a function of the simulated worst-case
probability of false alarm Pfa (TF (h), mα ) ≤ α̃, henceforth
referred to as the ROC. The theoretical results include those
obtained in Section IV for the FMA stopping time of the
different metrics used in this work, stated in Corollaries 2,
3 and 4. On the other hand, we use the bounds available in
the literature for the CUSUM and WLC. For the probability
of missed detection of these two methods we have an upper
bound in the form of (16) (see [35] and [36] for the WLC and
CUSUM, respectively). For the false alarm probability, we use
the upper bound given by (4)–(5), which holds for both the
CUSUM and WLC.
Fig. 1 shows the simulated ROC for the FMA stopping time
corresponding to the C/N0 (left) and SAM (right) metrics.
The simulations are obtained with 106 Monte-Carlo runs.
The obtained theoretical results in Corollaries 2 and 4 are
also shown, respectively. That is, the bound for Pmd in (30)
and (44), respectively, as a function of the bound for Pfa in
(31) and (45), respectively. For the WLC and CUSUM the
same expression for Pmd is used, but taking into account
the fixed threshold (as function of α̃) from (5). This is done
by considering the following parameters for the C/N0 metric,
suggested in [31]: µc,0 = 104.4 , µ̃c,1 = µc,1 = 103.7 and
σc2 = (∆/3)2 , with ∆ = µc,0 (100.3 − 1). Moreover, we use
m = 6, mα = 60 assuming a sampling rate of one second for
the C/N0 and ttta = 6 s and tα = 1 min.

Worst−case probability of missed detection

8

Shewhart stopping time is not giving the best results nether
for the DLL nor for the C/N0 and SAM, making evident the
loss of its optimality properties for m > 1.

−2

10

B. Numerical example: sig-RAIM availability

−3

10

Shewhart
(5) −−> h(Pfa) −−> (40)
WLC
CUSUM
(39) −−> h(Pfa) −−> (40)
FMA
−3

−2

−1

10
10
10
Worst−case probability of false alarm (Pfa)

0

10

Fig. 2. Simulated ROC for the DLLout FMA stopping time and its competitors (i.e. CUSUM, WLC and Shewhart), with the theoretical results given in
(36)–(37) and those obtained with (5) for the bound of the probability of false
alarms.

On the other hand, for the SAM metric we use the following
parameters, similar to those in [28] and [31]: µs,0 = 0.1,
2
2
2
σs,0
= 1.14 · 10−3 , µ̃s,1 = µs,1 = 0.2 and σ̃s,1
= σs,1
=
−3
2.03 · 10 . In this case, we use m = 6, mα = 300 assuming
a sampling rate of one second for the SAM and ttta = 6
s and tα = 5 min. It can be concluded from Fig. 1 that
the FMA stopping time outperforms (for both the C/N0 and
SAM metrics), in the sense of the optimality criterion in
(7)–(8), all the other stopping times considered. Moreover, it
is worth pointing out that the bounds will also impact the
real performance of the methods because the threshold h is
in practice fixed using the bounds, with the aim of fixing
certain desirable performance. Therefore, the availability of
tight bounds is important not only for a theoretical study
but also for setting the threshold in practice and provide a
level of performance that is close to the desired one. We
see how the improvement of the FMA bounds with respect
to those available in the literature for other stopping times
is quite significant, providing between half- to two-orders-ofmagnitude improvement. This is something that, as we will
see next, greatly contributes on improving the availability of
the sig-RAIM.
Fig. 2 shows similar results but for the case of the DLLout
metric and using the following parameters suggested in [29]
2
2
2
= (∆1 /3)2 , with
= σd,1
and [31]: σd,0
= (∆0 /3)2 , σ̃d,1
∆0 = 0.01 chips and ∆1 = 0.07 chips, and m = 6, mα = 60
assuming a sampling rate of one second for the DLLout and
ttta = 6 s and tα = 1 min. The simulations are obtained with
106 Monte-Carlo runs. The theoretical results in Corollary
3 are also shown; that is the bound for Pmd in (36) as a
function of the bound for Pfa in (37). This is for the FMA
stopping time, for the WLC and CUSUM we use (36) but
with the threshold fixed from (5). In this case we also see an
improvement of the FMA stopping time with respect to the
CUSUM and WLC. Moreover, the improvement in terms of
fixed bounds for the FMA with respect to the CUSUM and
WLC is also confirmed. Finally, it is worth remarking that the

This section is intended to show the behavior of the presented metrics in terms of availability of the sig-RAIM.
CASE 1: C/N0 metric
Let us start with the C/N0 metric assuming that we use m = 6,
mα = 60, µc,0 = 104.4 and σc2 = 2.5 · 104 , as previously.
Also let us suppose we have a tolerable error equivalent to
a mean change in the C/N0 of 7dB; thus we fix the change
parameter as µ̃c,1 = 103.7 , but the actual change parameter
is µc,1 = 103.4 . Therefore, for the case of using the FMA
stopping time, fixing the detection threshold from (29) to
hc = 2.92 so that Pfa (TF,C (hc ), mα ) ≤ α̃ = 10−1 , and substituting the previous values in (28) and (30), the integrity risk
is bounded as Pmd (TF,C (hc ), m) ≤ βC (hc , m) = 6.97 · 10−4 .
For the CUSUM or WLC stopping time we fix the threshold h̃c
from (5), which for α̃ = 10−1 gives h̃c = 6.40, and thus from
(30) we get Pmd (TWL (h̃c ), m) ≤ βC (h̃c , m) = 4.56 · 10−3 .
Now, suppose the maximum allowed integrity risk is β̃ =
10−2 ; then since βC (hc ) < βC (h̃c ) < β̃ the sig-RAIM will
be available in the case of using any of the analyzed stopping
times. On the other hand, we suppose we need α̃ = 10−2
so from (29) and (5) we get hc = 3.59 for the FMA and
h̃c = 8.70 for the CUSUM and WLC. Thus, from (30) we have
that βC (hc ) = 1.02 · 10−3 and βC (h̃c ) = 1.33 · 10−2 . Hence,
in this case, the sig-RAIM will be available only if the FMA
stopping time is used. Otherwise, it will not be available since
βC (h̃c ) > β̃. This shows the improvements of the suggested
FMA stopping time and the proposed theoretical bounds in
terms of the sig-RAIM availability.
CASE 2: DLL metric
2
For the DLL we use m = 6, mα = 60 and σd,0
= 1.11 · 10−5
as in Section V-A. Now, we evaluate the effect of using the
actual change parameter on the availability of the sig-RAIM
2
when a threat is present and we use the tuning parameter σ̃d,1
.
2
To do so, imagine that a change is present with σd,1 = 5.44 ·
10−4 , but the maximum tolerable error in the measured range
within the GNSS receiver for each satellite is equal to 14.65 m.
For a GPS signal, 14.65 m of error is equivalent to a variation
of ±0.05 chips, which converted to DLL variance as in [31]
2
gives a minimum detectable change parameter of σ̃d,1
= 2.78·
−4
10 . Assuming we want Pfa (T (h), mα ) ≤ α̃ = 10−2 , from
(35), we have hd = 3.14 for the FMA and, from (5), h̃d =
8.70 for the CUSUM and WLC. Thereby, if we fix the actual
2
2
parameter as σd,1
= σ̃d,1
, we get from (36) βD (hd , m) =
−2
1.70 · 10 and βD (h̃d , m) = 4.25 · 10−2, and then, since they
are above β̃, the sig-RAIM is not available. On the other hand,
if we know the actual change parameter, from (36) we have
βD (hd , m) = 2.74 · 10−3 and βD (h̃d , m) = 7.41 · 10−3, which
are bellow β̃ and thus the sig-RAIM would be available using
either the FMA, CUSUM or WLC stopping time. With this
result we corroborate the improvements on the availability by
knowing the real change parameter in (36).

9

CASE 3: SAM metric
Finally, for the SAM metric we use m = 6, mα = 300,
2
µs,0 = 0.1 and σs,0
= 1.14 · 10−3 as in Section V-A.
For the fixed change parameters, we suppose that the maximum tolerable error leads, from (25), to µ̃s,1 = 0.2 and
2
σ̃s,1
= 2.03 · 10−3 . Also suppose that µs,1 = µ̃s,1 and
2
2
σs,1 = σ̃s,1
, then if we want Pfa (T (h), mα ) ≤ α̃ = 10−2 ,
from (43), we have hs = 5.53 for the FMA and, from (5),
h̃s = 10.31 for the CUSUM and WLC. Thus, from (44)
we get Pmd (TF,S (hs ), m) ≤ βS (hs , m) = 8.75 · 10−3 and
Pmd (TF,S (h̃s ), m) ≤ βS (h̃s , m) = 3.71 · 10−2 . If we wish
β̃ = 10−2 , then since βS (hd , m) ≤ β̃ but βS (h̃s , m) > β̃ the
sig-RAIM will be available only if the FMA stopping time is
used, showing again the improvements in terms of availability.

with
ci =

A PPENDIX A
P ROOF OF T HEOREM 1
The proof of Theorem 1 is divided in three parts. Firstly,
we prove the bound for the probability of false alarm given in
(13)–(14). Secondly, we show the proof of the bound for the
probability of missed detection given by (15)–(16). Finally, we
conclude the proof of the theorem by proving (18)–(20).
A. Probability of false alarm Pfa (TF (h), mα )
We first introduce an important result, stated in the following lemma, that will be very useful for proving Theorem 1.
. Pm
Lemma 1. Let Sn = i=1 LLR(i), k ≥ m and N > k be
integers, then
!
k+N
\−1
N
P∞
{Si < h} ≥ [P∞ (Sm < h)] .
(49)
i=k

Proof: Let yi = LLR(i), then from (12), for n ≥ m we
can write
n
n
X
X
cn−i yi ,
(50)
yi =
Sn =
i=n−m+1

i=1

1
0

if 0 ≤ i ≤ m − 1
,
if i ≥ m

(51)

so that Sn is written as a monotonically increasing function
of {y1 , . . . , yn } (since ci ≥ 0). Therefore, since y1 , y2 , . . . are
iid under P∞ , from Theorem 5.1 of [40], we have that
! k+N −1
k+N
\−1
Y
P∞
{Si < h} ≥
P∞ (Si < h) ,
(52)
i=k

i=k

and the inequality (49) thus follows from the fact that the
distribution of Si , under P∞ , is the same for any i ≥ m.
Now, we aim to prove first another useful result for obtaining (13)–(14), that is
Pfa (TF (h), mα ) = P∞ (m ≤ TF (h) < m + mα ) .

VI. C ONCLUSIONS
This work has investigated the problem of transient change
detection in the context of GNSS signal integrity. We have
proposed the use of an FMA stopping time, inspired by the fact
that the optimal windowed CUSUM for the case of a Gaussian
mean change is the FMA stopping time. This optimality is
based on the criterion of minimizing the probability of missed
detection with a constraint in the false alarms, which perfectly
fits in the GNSS integrity problem. The statistical performance
of the FMA stopping time has been theoretically investigated
and compared by numerical simulations to different methods
available in the literature. This has been done in the setting of
GNSS signal integrity by considering the case of multipath
detection. These experiments have confirmed the goodness
of the presented theoretical results in order to be used for
signal integrity. Moreover, it has also been shown that the
proposed solution outperforms other solutions available in the
literature of transient change detection, benefiting not only the
performance but the availability of the sig-RAIM algorithm.

(

(53)

To do so, in a similar way as in [36], from (8) we can write
Pfa (TF (h), mα ) = sup

l≥m

l+m
α −1
X

P∞ (TF (h) = k).

(54)

k=l

Now denoting Vl = P∞ (l ≤ TF (h) < l + mα ) for l ≥ m and
Uk = P∞ (TF (h) = k), we have that
Pfa (TF (h), mα ) = sup Vl = sup
l≥m

l≥m

l+m
α −1
X

Uk .

(55)

k=l

It is easy to verify, from the definition of TF (h) in (12), that
Um = P∞ (Sm ≥ h)

(56)

and


\
Um+1 = P∞ {Sm < h} {Sm+1 ≥ h}

≤ P∞ ({Sm+1 ≥ h}) = P∞ ({Sm ≥ h}) = Um ,
(57)
where the second to last equality follows because Sn has the
same distribution, under P∞ , for n ≥ m. Similarly, for k > m,
we have
!
k
\
\
Uk+1 = P∞
{Sn < h} {Sk+1 ≥ h}
≤ P∞

n=m
k
\

{Sn < h}

n=m+1

= P∞

k−1
\

{Sn < h}

n=m

\

\

{Sk+1 ≥ h}
!

{Sk ≥ h}

!

(58)

= Uk .

Thus, {Uk }k≥m is a non-increasing sequence, and then
Vl − Vl+1 =

l+m
α −1
X

Uk −

k=l

l+m
Xα

Uk = Ul − Ul+mα ≥ 0,

k=l+1

(59)
so that {Vl }l≥m is a non-increasing sequence as well. Hence,
from (55) and the definition of Vl ,
Pfa (TF (h), mα ) = sup Vl = P∞ (m ≤ TF (h) < m + mα ) ,
l≥m

(60)
and thus (53) follows.

10

Now, we can proceed with the calculation of
Pfa (TF (h), mα ). However, the exact calculation from
(60) is complicated to obtain, and then the calculation of
an upper bound is proposed instead. From (60) and since
TF (h) ≥ m from the definition in (12), we can write
Pfa (TF (h), mα ) = 1 − P∞ (TF (h) ≥ m + mα ) ,

(61)

with
P∞ (TF (h) ≥ m + mα ) = P∞

m+m
\α −1

!

{Sn < h} .

n=m

(62)
So, the proof of (13) and (14) follows by direct application of
(49) to (62).

with ξzs ,n the moments of Zs , under Hi , given by
ξzs ,2 = µ2zs ,i + σz2s ,i ,


ξzs ,3 = m ξy,3 + (m − 1) 3µzs ,i ξy,2 + (m − 2)µ3zs ,i ,
ξzs ,4 = m [ξy,4 + (m − 1) (Ω + (m − 2) (Γ + Λ))] ,

(67)
2
where µzs ,i and σz2s ,i are given by (48), Ω = 4µzs ,i ξy,3 +3ξy,2
,
2
4
Γ = 6µzs ,i ξy,2 , Λ = (m − 3)µzs ,i , and ξy,k are the moments
of Yn given by
n
X
A(i),
(68)
ξy,n =
i=0

with

A(i) =
B. Probability of missed detection Pmd (TF (h), m)

Pmd (TF (h), m) = sup

(63)

n=m

where the last equality follows from the definition of TF (h)
in (12). Due to the windowed behavior of TF (h) we have
assumed that v > m. As for Pfa (TF (h), mα ), the exact
calculation of Pmd (TF (h), m) from (63) is quite difficult, and
then we propose the derivation of an upper bound.
Now, letting the event An = {Sn < h}, with n ≥ m, it is
clear that Av−1 and Am+v−1 are independent because they
do not share any samples, thus
!
!
v−1
m+v−1
\
\
An , (64)
Pv
An ≤ Pv (Am+v−1 ) Pv
n=m

n=m

since in the left side we evaluate more events than in the right
side. So, applying this result to (63) we have that
Pmd (TF (h), m) ≤ sup Pv (Sm+v−1 < h)
v>m

(65)

= P1 (Sm < h) ,
where the equality follows because Sm+v−1 is identically
distributed under Pv , and (15)–(16) thus follow, completing
the proof of Theorem 1.
A PPENDIX B
C ALCULATION OF COEFFICIENTS Ck
A complete proof of the results in Corollary 4 can be found
in [39]. Here we only give the expression for Ck so that
the bounds in Corollary 4 can be calculated. The coefficients
Ck,Hi are obtained as
C3 =

ξzs ,3 − 3µzs ,i ξzs ,2 + 2µ3zs ,i
,
σz3s ,i

C4 =

ξzs ,4 − 4µzs ,i ξzs ,3 + 6µ2zs ,i ξzs ,2 − 3µ4zs ,i
− 3,
σz4s ,i

C6 = 10C32 ,

(69)


where ni = (n!)/(i!(n − i)!) is the binomial coefficient,
.
ξxs ,k = Ei (xkn,s ) is the moment of k-th order of xn,s under
hypothesis Hi and {as , bs , cs } are defined in (42).

Applying the Bayes rule in (7) we have
Pv (TF (h) ≥ v + m)
Pv (TF (h) ≥ v)
v>m
m+v−1

T
Pv
{Sn < h}
n=m
 ,
= sup
v−1
T
v>m
Pv
{Sn < h}

i   
X
n
i n−i i−j j
a bs cs ξxs ,2n−i−j ,
i
j s
j=0

(66)

R EFERENCES
[1] G. Seco-Granados et al., “Challenges in indoor global navigation
satellite systems: unveiling its core features in signal processing,” IEEE
Signal Processing Magazine, vol. 29, no. 2, pp. 108–131, 2012.
[2] P. W. Bradford, J. Spilker, and P. Enge, Global Positioning System:
Theory and Applications. Aiaa, 1996, vol. 2.
[3] R. SC-159, “Minimum operational performance standards for global
positioning system/wide area augmentation system airborne equipment,”
RTCA Inc. Document No. RTCA/DO-229D, 2006.
[4] B. W. Parkinson and P. Axelrad, “Autonomous GPS integrity monitoring
using the pseudorange residual,” Navigation, vol. 35, no. 2, pp. 255–274,
1988.
[5] R. G. Brown and P. McBurney, “Self-contained GPS integrity check
using maximum solution separation,” Navigation, vol. 35, no. 1, pp.
41–53, 1988.
[6] D. Salos et al., “Receiver autonomous integrity monitoring of GNSS
signals for electronic toll collection,” IEEE Transactions on Intelligent
Transportation Systems, vol. 15, no. 1, pp. 94–103, 2014.
[7] J. Cosmen-Schortmann et al., “Integrity in urban and road environments
and its use in liability critical applications,” in Proc. IEEE/ION Position,
Location and Navigation Symposium, 2008, pp. 972–983.
[8] R. Toledo-Moreo et al., “An analysis of positioning and map-matching
issues for GNSS-based road user charging,” in Proc. IEEE Intelligent
Transportation Systems (ITSC), 2010, pp. 1486–1491.
[9] H. V. Poor and O. Hadjiliadis, Quickest Detection.
Cambridge
University Press, 2009.
[10] M. Basseville and I. V. Nikiforov, Detection of Abrupt Changes: Theory
and Application. Englewood Cliffs: Prentice Hall, 1993.
[11] E. Page, “Continuous inspection schemes,” Biometrika, pp. 100–115,
1954.
[12] G. Lorden, “Procedures for reacting to a change in distribution,” The
Annals of Mathematical Statistics, vol. 42, no. 6, pp. 1897–1908, 1971.
[13] G. V. Moustakides, “Optimal stopping times for detecting changes in
distributions,” The Annals of Statistics, pp. 1379–1387, 1986.
[14] T. Bojdecki, “Probability maximizing approach to optimal stopping and
its application to a disorder problem,” Stochastics, vol. 3, pp. 61–71,
1979.
[15] M. Pollak and A. M. Krieger, “Shewhart revisited,” Sequential Analysis,
vol. 32, pp. 230–242, 2013.
[16] G. V. Moustakides, “Multiple optimality properties of the Shewhart test,”
Sequential Analysis, vol. 33, pp. 318–344, 2014.
[17] W. Sun and M. G. Amin, “A self-coherence anti-jamming GPS receiver,”
IEEE Transactions on Signal Processing, vol. 53, no. 10, pp. 3910–3915,
2005.
[18] Y. D. Zhang and M. G. Amin, “Anti-jamming GPS receiver with reduced
phase distortions,” IEEE Signal Processing Letters, vol. 19, no. 10, pp.
635–638, 2012.
[19] H. K. Lee, J. G. Lee, and G.-I. Jee, “GPS multipath detection based on
sequence of successive-time double-differences,” IEEE Signal Processing Letters, vol. 11, no. 3, pp. 316–319, 2004.

11

[20] A. Giremus, J.-Y. Tourneret, and V. Calmettes, “A particle filtering
approach for joint detection/estimation of multipath effects on GPS
measurements,” IEEE Transactions on Signal Processing, vol. 55, no. 4,
pp. 1275–1285, 2007.
[21] M. L. Psiaki and T. E. Humphreys, “GNSS spoofing and detection,”
Proceedings of the IEEE, vol. 104, no. 6, pp. 1258–1270, 2016.
[22] E. Axell, E. G. Larsson, and D. Persson, “GNSS spoofing detection using
multiple mobile COTS receivers,” in IEEE International Conference on
Acoustics, Speech and Signal Processing (ICASSP), 2015, pp. 3192–
3196.
[23] J.-F. Chamberland and V. V. Veeravalli, “Wireless sensors in distributed
detection applications,” IEEE Signal Processing Magazine, vol. 24,
no. 3, pp. 16–25, 2007.
[24] T. Osklper and H. V. Poor, “Quickest detection of a random signal in
background noise using a sensor array,” EURASIP Journal on Applied
Signal Processing, no. 1, 2005.
[25] E. Axell et al., “Spectrum sensing for cognitive radio: State-of-the-art
and recent advances,” IEEE Signal Processing Magazine, vol. 29, no. 3,
pp. 101–116, 2012.
[26] D. Egea, J. A. López-Salcedo, and G. Seco-Granados, “Interference and
multipath sequential tests for signal integrity in multi-antenna GNSS
receivers,” in Proc. IEEE 8th Sensor Array and Multichanel Signal
Processing Workshop (SAM), 2014, pp. 117–120.
[27] D. Egea, G. Seco-Granados, and J. A. López-Salcedo, “Single- and
multi-correlator sequential tests for signal integrity in multi-antenna
GNSS receivers,” in Proc. International Conference on Localization and
GNSS (ICL-GNSS), 2014, pp. 117–120.
[28] D. Egea-Roca, G. Seco-Granados, and J. A. López-Salcedo, “On the
use of quickest detection theory for signal integrity monitoring in
single-antenna GNSS receivers,” in Proc. International Conference on
Localization and GNSS (ICL-GNSS), 2015, pp. 1–6.
[29] ——, “Quickest detection framework for signal integrity monitoring in
low-cost GNSS receivers,” in Proc. IEEE 82nd Vehicular Technology
Conference (VTC Fall), 2015, pp. 1–5.
[30] ——, “Signal-level integrity and metrics based on the application
of quickest detection theory to interference detection,” in Proc. 28th
International Technical Meeting of The Satellite Division of the Institute
of Navigation (ION GNSS+), 2015, pp. 3136 – 3147.
[31] ——, “Signal-level integrity and metrics based on the application
of quickest detection theory to multipath detection,” in Proc. 28th
International Technical Meeting of The Satellite Division of the Institute
of Navigation (ION GNSS+), 2015, pp. 2926–2938.
[32] C. Han, P. K. Willett, and D. Abraham, “Some methods to evaluate
the performance of Pages’ test as used to detect transient signals,” IEEE
Transactions on Signal Processing, vol. 47, no. 8, pp. 2112–2127, 1999.
[33] Z. Wang and P. K. Willett, “All-purpose and plug-in power-law detectors
for transient signals,” IEEE Transactions on Signal Processing, vol. 49,
no. 11, pp. 2454–2466, 2001.
[34] ——, “A variable threshold Page procedure for detection of transient
signals,” IEEE Transactions on Signal Processing, vol. 53, no. 11, pp.
4397–4402, 2005.
[35] B. Bakhache and I. Nikiforov, “Reliable detection of faults in measurement systems,” International Journal of Adaptive Control and Signal
Processing, vol. 14, no. 7, pp. 683–700, 2000.
[36] B. K. Guépié, L. Fillatre, and I. Nikiforov, “Sequential detection of
transient changes,” Sequential Analysis, vol. 31, no. 4, pp. 528–547,
2012.
[37] D. Egea-Roca et al., “A finite moving average test for transient change
detection in GNSS signal strength monitoring,” in Proc. IEEE Statistical
Signal Processing Workshop (SSP), 2016.
[38] T. L. Lai, “Information bounds and quick detection of parameter changes
in stochastic systems,” IEEE Transactions on Information Theory,
vol. 44, no. 7, pp. 2917–2929, 1998.
[39] D. Egea-Roca, G. Seco-Granados, and J. A. López-Salcedo, “Closedform approximations for the performance upper bound of inhomogeneous quadratic tests,” arXiv preprint arXiv:1608.00615, 2016.
[40] J. D. Esary et al., “Association of random variables, with applications,”
The Annals of Mathematical Statistics, vol. 38, no. 5, pp. 1466–1474,
1967.

