575
1 INTRODUCTION
Satellite navigation has become a cornerstone of the
moderncivilisation,apublicgoods,andanessential
component of a national infrastructure. Growing
number of both navigation and non‐navigation
technologyandsocio‐economicapplications(systems
andservices)rely completelyonprovisionofGlobal
Navigation Satellite Systems (GNSS) Positioning,
Navigation, and Timing (PNT) services, thus raising
importance of robust GNSS, resilient to sources of
GNSS PNT services disruptions and degradations
(HMGovernmentOfficeforScience,2018).Modelsof
GNSS positioning performance degradations and
error sources, based on actual scenarios and
experimentally collected data, allows for
understandingthecausesand
mitigationoftheeffects
on GNSS positioning performance in general and in
relationtospecificapplications.GNSSresiliencemay
then be accomplished through various risk
containment actions, including error correction
modelling, and forecasting GNSS positioning
performance degradation for alerts and corrective
actions.
Model development process suffers from the
complexity of the
positioning environment, as
describedwithourSpaceWeather‐GNSSpositioning
performance coupling model (Filić and Filjar, 2018),
(Filić and Filjar, 2019). GNSS resilience has been
attempted to be achieved through methodologies,
including those that addresses identification of the
closest linear descriptor of GNSS positioning errors
(Filić and Filjar, 2019), examining
GNSS positioning
errors dynamics (Lenac, Filić, and Filjar, 2019), and
advancedstatisticallearningapproaches appliedover
massive data sets of potential positioning
environmentdescriptors (Filić and Filjar, 2018). Still,
on all attempted approaches and scenarios, the
identification of the GNSS positioning performance
degradation onset and duration appeared to be the
criticalissuethatraisedthemodel’suncertainty.
GNSS Positioning Error Change-point Detection in GNSS
Positioning Performance Modelling
M.Filić
UniversityofLjubljana,Ljubljana,Slovenia
R.Filjar
ZagrebUniversityofAppliedSciences,Zagreb,Croatia
UniversityofRijeka,Rijeka,Croatia
ABSTRACT: Provision of uninterrupted and robust Positioning, Navigation, and Timing (PNT) services is
essential task of Global Navigation Satellite Systems (GNSS) as an enabling technology for numerous
technologyandsocio‐economicapplications,acornerstoneofthemoderncivilisation,a
publicgoods,andan
essential component of a national infrastructure. GNSS resilience may be accomplished only with complete
understandingofthe causesofGNSSpositioningperformancedisruptions anddegradations,presentedina
formofapplications‐andscenarios‐relatedmodels.Heretheapplicationofchange‐pointdetectionmethodsis
proposedand
demonstratedinaselectedscenarioofafast‐developing ionosphericstorm’simpacton GNSS
positioning performance, as a novel contribution to forecasting GNSS positioning performance model
developmentandGNSSutilisationriskmitigation.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 13
Number 3
September 2019
DOI:10.12716/1001.13.03.12
576
Here a change‐point detection methodology
(Truong,Oudre, andVaytis,2019),(Aminikhanghahi
andCook,2017),(Schroeder,2016)appliedonGNSS
positioningerrortimeseriesisproposedasavaluable
contribution to GNSS positioning performance
degradation model development. Based on the
experimentaldataandfoundedonstatisticalanalysis
of GNSS positioning
error dynamics, its capacity is
demonstratedfornotonlythechange‐pointdetection,
but also the identification of the intervals with the
increased volatility (variance) of GNSS positioning
errorduetoionosphericconditions.
2 METHODOLOGY
2.1 Case‐studydescription
This researcher examined a known case of a fast
development of
a large ionospheric storm in the
period of quiet solar activity, commenced on 17the
March,2015andknownasthe2015StPatrickʹsDay
Storm. Development of this space weather event,
unusualinaperiodofquietsolaractivity,posedasa
challengefortheresearchcommunityaddressingthe
space
weather and ionospheric impact on GNSS
positioning performance and operation. Space
weather and geomagnetic conditions in March, 2015
were properly described with the planetary
geomagneticKpindex,withitsdynamicsdepictedin
Figure1.
TimeseriesofGNSSnorthing,eastingandheight
positioning errors were derived from the GPS
pseudorange
observationstakenatthePoreč,Croatia
reference station during March, 2015 (31 daily data
sets), processed using the open‐source using a post‐
processing methodology described elsewhere, for
instance (Filić and Filjar, 2018) and (Filić, Filjar, and
Routsalainen, 2016). Time series of GNSS northing,
easting and height positioning errors
were analysed
further using the bespoke R‐based GNSS statistical
analysis framework we developed earlier. Resulting
GPS positioning errors time series followed the
normal distribution well, and are presented
graphicallyinFigure2.
Figure1. Planetary geomagnetic Kp index dynamics in
March,2015.Basedondataprovidedby(NOAA, 2019).
2.2 Changedetectionmethods
(Gustafsson, 2000) defined a change detection as a
decision of inconsistency of the observed data with
the nominal model. (Killick and Eckley, 2014)
narrowed the definition of change detection to
identificationoftheinstanceoftime(thepointintime
series of data, dubbed change‐point),
when (where)
statisticalpropertiesbeforeandafterthattime(point)
differ.
Definition1:Letthetimeseriesofobserveddata
isgiven,asin(1).
12
, ,...,
n
x
txxx
(1)
The change‐point is defined as a time‐series
sample x
τ, taken at the instant of timeτ, exists if
statistical properties of the sub‐set
12
, ,...,
x
txxx
of original data differs from
statistical properties of the remaining sub‐
set
12
, ,...,
n
x
xx
.Achange‐pointmaybedefined
eitherasaglobal(asinglechange‐pointinthewhole
setofobservations),oralocal(anelementofasetof
multiplechange‐pointinthesetofobservations).
Figure2 Time series of GPS northing, easting, and height
positioningerrors,derivedfromexperimentalobservations
takenatthePoreč,Croatiareferencestation(dataprovided
by(Sonel,2019)network)
Acommonexperiencewouldtellthatasufficiently
large set of observations very proba bly comprises a
numberofchange‐points.Theiridentificationmaybe
understood as an optimisation problem that may be
definedasfollows.
Let assume a set of
observations
12
, ,...,
n
x
txx x comprises k change‐
points,withdefinedas
12
, ,...,
k
cp cp cp cp ,with
thecp
1asthefirst(cp1=x1),andthecpkbeingthelast
(cp
k=xn)elementoftheoriginaltimeseries.Asingle
change‐point may be detected/defined using the
likelihoodratiotest(2)
1: 1: 1:
max
nn
LR lx lx lx
(2)
wherelisthelikelihoodfunctionappliedonthedata
setspecified.Achange‐pointisinferredasdetectedif
theconditionLR >λismet,with λbeinga suitably
selected penalty parameter. The time of change
(identification of a change‐point in the time series)
maybe
theninferredasgivenin(3).
1: 1: 1:
arg max
nn
lx lx lx
(3)
The procedure may be generalised for multiple
change‐pointdetectionusingproblemformulationas
given in (4), with additional modelling flexibility
577
provided by introduction of penalty function f(k)
relatedtothenumber of change‐points, and penalty
constantλ(Truong,Oudre,andVaytis,2019).
1
1:
,
1
ii
k
k
i
min l x f k
(4)
Solutionof theoptimisation problem(4) depends
ontheexpectednumberofchange‐points,complexity
of the process that generated time series, and the
required computational performance (Killick, 2016),
(Chandola and Vatsavai, 2011). Change‐point
detection methods utilises various approaches and
constraints (Truong, Oudre, and Vaytis, 2019).
Among them,
one can distinguish: (i) At Most One
Change (AMOC), a method suitable for a single
change‐point detection, (ii) Binary Segmentation,
developedby(ScottandKnott,1974),approximatein
its accuracy, but computationally efficient, (iii)
Segment Neighbourhood, exact in its accuracy, but
computationally demanding, and (iv) Pruned Exact
Linear Time (PELT),
an exact and computationally
efficient method. Optimisation may consider the
mean changes in time series only, the variance
changesintime seriesonly, orto beconcerned with
bothessentialstatisticaldescriptorsofatimeseries.
The methods analysed do not only identify the
change‐point(s), but also determines the
time‐series
sub‐setsofincreasedvariance,usuallycausedbythe
very sources of GNSS positioning performance
degradations.
The above‐described procedures are
comprehensibly available as a separate statistical
libraryintheRenvironmentforstatisticalcomputing.
Named the changepoint, it was used in this research,
andappliedonthe
GPSnorthing,eastingandheight
positioning error time series derived from the
experimental observations during the case‐scenario,
asdescribedinSection2.1.
2.3 Changedetectionimplementation
ThisresearchwasconductedusingtheRenvironment
forstatisticalcomputing,witharangeofchange‐point
methodsdeployedintheRlibrarycalled
changepoint
(Killick,2016). After the initial exploratory statistical
analysisofdata,weconductedathroughexamination
of the changepoint R library methods, and found the
bestfittotheproblemconcernedwiththeutilisation
of the Binary Segmentation change‐point detection
method (Scott and Knott, 1974) on the optimisation
problem
involving both the mean and the variance
change.TheSchwarz(Bayesian)InformationCriterion
(SIC)(Watanabe,2013)PenaltyFunctionwasselected,
and number of expected change‐points set to 10.
Normal distribution of GPS positioning errors time
series was assumed in the change‐point detection
process, based on the exploratory statistical analysis
conducted.
3 CHANGEDETECTIONINGNSSPOSITIONING
ERRORTIMESERIES
Thisresearch addressedthe potential of the change‐
point detection in time series (Truong, Oudre, and
Vaytis, 2019) of GNSS positioning errors for the
purposes of the GNSS positioning error modelling
and mitigation, and potential applications of post‐
processedGNSS
observations.
UsingthemethodologyoutlinedinSection2,and
byvarying parameters ofthe change‐point detection
methodsintheestablishedR‐andchangepointlibrary‐
based framework, optimal change‐point detection in
GPS northing, easting, and height positioning errors
timeserieswasperformed.Themostsuitablechange‐
point detection method was
selected and fine‐tuned
based on the exploratory data analysis (Filić, Filjar,
andRuotsalainen,2016).
The optimised change‐point detection
methodologywasdeployedontheMarch,2015time
series,withtheresultsforGPSnorthing,easting,and
heightpositioningerrorsdepictedinFigures3,4,and
5,respectively.
The
change‐point detection method applied
identifiedcorrectlythe2015StPatrickʹsStormeffects
on the GPS positioning performance, as the most
prominent degradation throughout March, 2015.
Further to this, the method identified periods (time‐
series sub‐sets) of a range of variances, thus
determining time‐series sub‐sets that may
be used
immediately in development of partial descriptive
models.
Figure3. Change‐points detected in GPS northing
positioningerrorstimeseriesduringMarch,2015
Figure4.Change‐pointsdetectedinGPSeastingpositioning
errorstimeseriesduringMarch,2015
578
Figure5.Change‐pointsdetectedinGPSheightpositioning
errorstimeseriesduringMarch,2015
4 DISCUSSIONANDCONCLUSION
Change‐point detection is a simple and elegant
statistics‐basedmethodfortimeseriesanalysis.Here
we argue that it may be utilised for a considerable
improvement of GNSS positioning error time‐series
analysisandanovelcontributioninGNSSpositioning
performance models and forecasts. It allows
for the
clearandaccuratedeterminationoftheonsetofGNSS
positioning performance degradation. The
methodology is based on the strict application of
statistics on experimental data in a form of time
series,andaddressesitsdynamicsonly.Comparison
with time series of supposed causes of GPS
positioning performance degradation
confirmed the
accuracyofchange‐pointdetection.
Traditionally, the onset of a critical GNSS
positioning performance event was determined
through cross‐correlation procedure involving,
combining (supposed) cause and (hopefully direct)
effect.Regretfully,correlationbetweenthesourcesof
space weather, geomagnetic and ionospheric
disturbances,andtheGNSSpositioningperformance
degradation (error dynamics)
is frequently weak, as
the result of a complex and non‐linear relationship
between descriptors of space weather, geomagnetic
andionosphericconditions,andtheGNSSpositioning
performance, respectively. This often results with
descriptionmodelsofmodestquality,andinabilityto
forecast correctly the GNSS positioning performance
response to space weather,
geomagnetic and
ionosphericdisturbances.
The change‐point detection methodology
presented here points clearly and accurately to the
instant of time when the GNSS positioning
performancestartstodeteriorate,usingtheanalysisof
statistical nature of time series dynamics. The
accuracy of the time onset estimation appears to be
related to the
number of expected change‐points (k,
Section 2), when Binary Segmentation method with
SchwarzInformationCriterionPenaltyisconsidered.
This problem is to be addressed by our team in
continuation of this research, with the aim of
development and deployment of a tailored
optimisationalgorithmforthekparameter
selection.
The opportunity for the change‐point detection
procedure application on a smoothed time series of
GPS northing, easting, and height positioning errors
time series was also discussed. While determination
ofchange‐pointswould gomoresmoothlyin sucha
case, information on the process under observation
maybelost,especially
inthecaseofshort‐termlocal
disruptions. We concluded that application of the
Binary Segmentation change‐point detection method
with Schwarz Information Criterion Penalty (Killick,
2016)withreducednumberofexpectedchange‐points
butappliedonoriginal(non‐smoothed)datasetwill
yield more accurate results, without missing or
incorrectly identified change‐points. The
methodology applied split the original data set into
sub‐setswithrelatedvariance,pointingouttoperiods
and data of anomalous behaviour of GNSS
positioning performance. Sub‐set formation in
consideration of local variance may be extended
further to analyses of the cause and result.
Overlapping
intervals of the same‐level variance in
different descriptors time series will allow
determination of the cause‐effect assessment more,
suchasinstudies(FilićandFiljar,2019)and(Filićand
Filjar, 2018) conducted earlier, more accurately and
efficiently.
Finally, the demonstration of the change‐point
detection methodology application on
GNSS
positioning error time series improves numerous
GNSSapplicationscenariosinvolvingpost‐processing
of GNSS observations, including, but not limited to:
science,GNSSerrormodellingandmitigation,GNSS
forensics(eventreconstruction),andactuarialscience.
We identified a potential for a significant
improvement of GNSS positioning performance
understanding, modelling and forecasting using
bespoke tuned change‐point detection methods
applied on time series of GNSS positioning error
components.
In summary, this manuscript presented the
change‐point detection methodology as a valuable
addition to the process of modelling GNSS
positioning performance, thus improving GNSS
positioningperformancemodels,andwideningspace
for the post‐processing
GNSS applications in
disciplinesandscenariosthatrequire knowledgeon,
and understanding of the GNSS positioning
performancedegradations.
ACKNOWLEDGEMENT
Authorsacknowledgepartialsupportoftheresearchfrom
the Research of environmental impact on the operation of
satellitenavigation systems in maritime navigation project
(Project Code: uniri‐tehnic‐18‐66), funded by University of
Rijeka,Rijeka,Croatia.
REFERENCE
Aminikhanghahi,S,Cook,D.(2017).ASurveyof methods
fortime series changepoint detection. Knowledge and
Information Systems, 51(2), 339‐367. Available at:
https://www.eecs.wsu.edu/~cook/pubs/kais16.2.pdf
Chandola, V, Vatsavai, R R. (2011). A Gaussian Process
Based Online Change Detection Algorithm for
MonitoringPeriodicTimeSeries.Procof the2011SIAM
International
Conference on Data Mining, 95‐106. Mesa,
AZ.
579
Filić, M, Filjar, R. (2019). On correlation between SID
monitor and GPS‐derived TEC observations during a
massive ionospheric storm development. Best Student
PaperAwardatURSIAP‐RASC2019.NewDelhi,India.
Availableat:https://bit.ly/2FSJu0Y
Filić, M, Filjar, R. (2018). Forecasting model of space
weather‐drivenGNSS
positioningperformance.Lambert
Academic Publishing. Riga, Latvia. ISBN 978‐613‐9‐
90118‐0.
Filic, M, Filjar, R, and Ruotsalainen, L. (2016). An SDR‐
based Study of Multi‐GNSS Positioning Performance
During Fast‐developing Space Weather Storm.
TransNav,10(3),395‐400.doi:10.12716/1001.10.03.03.
Gustafsson, F. (2000). Adaptive Filtering and Change
Detection.
JohnWiley&Sons.Chichester,UK.
Killick, R. (2016). R Package changepoint. R project for
statistical computing. Available at: https://cran.r‐
project.org/web/packages/changepoint/index.html
Killick,R,Eckley,IA. (2014). Changepoint: AnR Package
for Changepoint Analysis. Journal of Statistical
Software,58(39,1‐19.doi:10.18637/jss.v058.i03
Lenac, K, Filić, M, Filjar, R.
(2019). GPS ionospheric delay
dynamics characterisation using recurrence plot
analysis. Presented for consideration to J of Navigation
(CambridgeUniversityPress).
NOAA.(2019).Kpindexdataarchive.USNationalOceanic
andAtmosphericAdministration(NOAA).Availableat:
ftp://ftp.swpc.noaa.gov/pub/indices/old_indices/
Sonel.(2019).InternetarchiveofGPSobservations.SONEL
network.Availableat:https://www.sonel.org
Schroeder, A L
M M. (2016). Methods for Change‐Point
Detection with Additional Interpretability. London
SchoolofEconomicsandPoliticalSciences.London,UK.
Availableat:http://etheses.lse.ac.uk/3421/
Scott,AJ,Knott,M.(1974).AClusterAnalysisMethodfor
GroupingMeansintheAnalysisofVariance. Biometrics,
30(3),507‐512.
Truong,C,Oudre,L,Vaytis,
N.(2019).Selective reviewof
offline change point detection methods. Preprint at
arXiv: 1801.00718. Available at:
https://arxiv.org/pdf/1801.00718.pdf
Watanabe, S. (2013). A Widely Applicable Bayesian
Information Criterion. J of Machine Learning Res, 14,
867‐897. Available at:
http://www.jmlr.org/papers/volume14/watanabe13a/wat
anabe13a.pdf
HMGovernmentOfficeforScience.(2018).Satellite‐Derived
Time and Position: A Study
of Critical Dependencies.
HMGovernmentoftheUnitedKingdomandNorthern
Ireland.Availableat:https://bit.ly/2E2STnd
