TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 3911 ~ 39
1
9
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.4879
3911
Re
cei
v
ed O
c
t
ober 2
0
, 201
3; Revi
se
d Decem
b
e
r
7, 2013; Accepte
d
Jan
uary 2, 2014
Fault Detection and Iso
l
ation for GPS RAIM Based on
Genetic Resampling Particle F
ilter Approach
Ershen Wan
g
*, Tao Pang
, Ming Cai, Zhixian Zhan
g
Schoo
l of Elect
r
onics a
nd Info
rmation En
gin
e
e
rin
g
, Shen
ya
n
g
Aerosp
ace U
n
iversit
y
,
Sh
e
n
y
ang
, C
h
in
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
w
e
s
2
0
16@s
au.ed
u.cn
A
b
st
r
a
ct
An
i
n
tegrity
mo
nitori
ng
sy
stem is an
in
s
epar
abl
e
part
of g
l
o
bal
p
o
s
itioni
ng
syste
m
(GPS).
Accordi
ng to t
he
me
asur
e
m
ent n
o
ise f
eat
ure of
GPS r
e
ceiv
er a
nd th
e de
ge
neracy
phe
no
me
no
n
and
allev
i
ati
ng the
sampl
e
i
m
pov
erish
m
e
n
t pro
b
l
e
m
in p
a
rt
icl
e
filter (PF
)
. An appr
oach to fa
ult detecti
on a
n
d
i
s
o
l
a
t
io
n (FD
I
) fo
r GPS re
cei
v
e
r
au
to
nom
ou
s i
n
teg
r
ity
monitor
i
ng
(RAI
M) base
d
o
n
gen
etic res
a
mplin
g
particl
e filter
is
pro
pose
d
. T
h
e g
e
n
e
tic a
l
g
o
r
i
thm (GA) is
melted
int
o
the
r
e
-sa
m
pl
in
g
pro
c
ess of th
e
ba
sic
particl
e filter
to so
lve th
e
pa
rticles d
e
g
e
n
e
r
a
cy a
nd
im
p
o
v
e
r
i
s
hm
en
t p
r
ob
l
e
m
.
A ma
in
GA-a
i
d
ed
pa
rticl
e
filter (GPF
) is
used
to pr
oce
ss
all
the
me
asure
m
ents to
prod
uce
t
he opti
m
a
l
state estimate,
sev
e
ral
auxil
iary GPF
s
are us
ed to
pr
ocess su
bsets
of measur
e
m
e
n
ts to prod
uce
the state esti
mate
as d
e
tect
ion
referenc
es. By setting up th
e log-l
i
ke
lih
oo
d ratio (LL
R
) te
st to check the c
onsiste
n
cy of test statistics. The
particl
es in GP
F
are assorted
by w
e
ights, in
order to
re
duc
e the co
mp
utat
ion co
mpl
e
xity of the alg
o
rith
m,
only the l
o
w
e
r w
e
ight particl
e
s
particip
a
te in
genetic
o
per
ations. By coll
ecting the GPS d
a
ta from the G
P
S
reciver, the
fe
asibi
lity
and
ef
fectiveness
of
the RAIM
ap
pr
oach
is v
e
rifie
d
, an
d c
o
mpar
ing
w
i
th exte
n
d
e
d
Kal
m
a
n
filter (EKF
) and PF
alg
o
rith
m. T
h
e
results s
how
that the ap
proa
ch in
the cas
e
of non-Gaussi
an
me
asur
e
m
ent
nois
e
ca
n est
i
mate th
e stat
e acc
u
rately
,
also c
a
n
succ
essfully
detect
fault sat
e
ll
ite
,
therefore, i
m
pr
ove the rel
i
a
b
il
i
t
y of GPS positioni
ng.
Ke
y
w
ords
:
global positioning system
(GPS),
receiver autonomous integrit
y monitoring (RAIM), particle
filter, genetic a
l
gorith
m
,
exten
ded Ka
l
m
a
n
filter
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
With the deve
l
opment of th
e global n
a
vigati
on satellite system
(G
NSS) and the
gro
w
s
of
use
r
p
e
rfo
r
m
ance requi
re
ments for
G
N
SS service,
for safety-critical appli
c
a
t
ions of
glo
b
al
navigation
satellite syste
m
(G
NSS),
su
ch a
s
ai
rcraft and
missile n
a
vigatio
n syste
m
s, i
t
is
importa
nt to
be abl
e to d
e
tect an
d ex
clud
e faults
that co
uld
ca
use
ri
sks to t
he a
c
curacy
and
integrity, so
that the
navig
ati
on
system
ca
n o
perate
co
ntinuo
usly
witho
u
t any
deg
rad
a
tion
in
perfo
rman
ce
[1, 2]. Becau
s
e it nee
ds a
long time for satellite fault
monitorin
g
to alarm th
rou
g
h
controlling the satellite navigation syst
em itself, us
ually within 15 minutes to a few hours, that
can't me
et the dema
nd of air navigatio
n
.
As a resu
lt, to monitor th
e satellite fau
l
t rapidly, na
mely
the receiver a
u
tonomo
u
s in
tegrity monito
ri
ng (RAIM) h
a
s be
en re
se
arched a lot [3, 4].
In re
cent ye
a
r
s, va
riou
s fai
l
ure
dete
c
tion
g
metho
d
s ha
ve bee
n di
scussed
to imp
r
ove the
accuracy and reliability of t
he systems.The snaps
hots algorithm has been widely used at
pre
s
ent. Thi
s
kind
of alg
o
rithm mai
n
l
y
has Pa
rity spa
c
e
(Parit
y) method, t
he sum of l
east
Squares
of the Error
(SSE) method, and the larges
t i
n
terval method, etc [5, 6].
Kalman filteri
n
g
algorith
m
is
by usin
g hi
storical me
asure to im
p
r
ove
the pe
rform
a
nce, Kalm
an
filter-ba
s
e
d
fault
detectio
n
ap
proa
ch
ha
s
been
used [
7
]. For mo
st
system
s a
r
e
usu
a
lly nonl
inear
and
sy
stem
noise a
r
e g
e
nerally
non
-Gau
ssi
an, G
N
SS mea
s
u
r
ement e
r
ror
doe
s not foll
ow a
Ga
ussi
an
distrib
u
tion p
e
rfectly. Kalm
an filter is
difficult to
obtain
the optimal
state estimatio
n
. Particle filt
er
algorith
m
is
suitabl
e to a
n
y non-li
nea
r, non-G
a
u
ssi
an sy
stems,
therefo
r
e,
the
particl
e filter for
fault detectio
n
has be
en
widely use
d
[8]. Bu
t basi
c
parti
cle
filter exists the degene
racy
phen
omen
on
and
alleviati
ng the
samp
le impove
r
i
s
hment p
r
o
b
le
m. In orde
r
to solve
the
s
e
probl
em, in t
he pa
prer, g
enetic
algo
rit
h
m is melted
into ordi
na
ry parti
cle filtering alg
o
rithm
by
geneti
c
mani
pulation to improve the q
uality of
particle
s
, combi
n
ed with the log-li
kelih
ood
ratio
(LL
R
) te
st me
thod. By checking the
con
s
i
s
ten
c
y of
the test statistic, f
ault satellite i
s
dete
c
ted.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3911 – 39
19
3912
2
.
Genetic Algorithm
Aid
e
d
Particle Filter
Particle filter i
s
a filter method ba
sed on
M
onte Ca
rlo
simulatio
n
an
d recursive Bayesia
n
estimation. Since Go
rd
on prop
osed the
seque
ntial
importa
nce re
sampli
ng (SI
R
) pa
rticle fil
t
er
algorith
m
based on se
que
ntial Monte Carlo metho
d
,
particl
e filter algorith
m
becomes a h
o
tsp
o
t
of nonline
a
r non-Gau
s
si
an sy
stem
state e
s
ti
mat
i
on problem,
being
widel
y used i
n
fault
diagn
osi
s
, sig
nal pro
c
e
s
sin
g
, navigati
on
and othe
r re
search a
r
ea
s [9-11].
The
core id
e
a
of
the part
i
cle filter i
s
t
o
use finite
rand
om
sam
p
les
(the
se
sampl
e
s
referred
to a
s
"parti
cle
s
") a
nd thei
r
weig
ht to
app
roxi
mate the
po
sterio
r p
r
ob
abili
ty distributio
n
of
state vari
able
s
, thereby obt
ain the e
s
tim
a
te of the
state. Re
sam
p
lin
g pa
rticle filte
r
can in
hibit the
dege
neracy o
f
weight
s, but
also
ma
ke t
he resample
d
parti
cle
s
no l
onge
r ind
epe
ndent. Ge
neti
c
algorith
m
is a search
optimizatio
n
algo
ri
thm
based o
n
n
a
tural
sele
ct
ion an
d ge
netic
mec
h
anis
m
s
.It inc
l
udes
selec
t
ion, c
r
oss
o
ver a
nd mutation operations
. In order to obtain
the
optimal solut
i
on or
sati
sfactory
soluti
on, t
he pro
c
e
ss te
rmin
ates u
n
til it meets
ce
rtain
perfo
rman
ce indicators
[12
-
15].
Th
e
g
e
n
e
tic of parti
cl
es is m
anip
u
lated in the re
al domain, th
e
cod
e
c of ge
netic mani
pu
lation is avo
i
ded. T
he a
d
vantage of
the introdu
ction of gen
etic
algorith
m
s lie
s in:
It ca
n im
prove
the
efficien
cy of
pa
rticle
s,
g
r
eatly r
edu
ce
s
the required num
b
e
r
of particl
es t
o
approximat
e
the maxim
u
m poster
ior probability distributio
n. Secondly, genetic
algorith
m
ca
n effectively increa
se the
diversity
of particl
e, and
effectively solve the part
i
cle
degradatio
n
phen
omen
a, thus imp
r
ovi
ng the a
c
cura
cy of state
estimation.
Con
s
id
erin
g
the
dynamic
state spa
c
e mo
d
e
l belo
w
:
kk
k
-
1
k
-
1
kk
k
k
()
()
X=
f
X
,
v
Z=
h
X
,
n
W
h
er
e
k
x
is a
state vecto
r
,
k
z
is
an output m
easure
m
ent
v
e
ctor,
f
(.
,
.
)
and
h(
.
,
.)
ar
e
state tra
n
sitio
n
functio
n
an
d mea
s
u
r
em
ent functio
n
resp
ectively.
1
k
v
i
s
a
pro
c
e
s
s
noise vecto
r
indep
ende
nt of
cu
rrent sta
t
e,
and
k
n
is a
measurement
noi
se
vecto
r
inde
pen
dent
of
states an
d
the system n
o
ise.
The detaile
d step
s of the GPF applie
d are a
s
follows:
Step 1: Initialization. Samp
le a set of ran
dom parti
cle
s
01
{}
S
N
i
i
x
from the pro
b
ability density
function (pdf)
0
()
p
x
. The weig
ht of each pa
rticl
e
is set by
1
s
N
.
Step 2: Up
da
te the weight
s of p
a
rticl
e
s.
Cal
c
ulatin
g
and u
pdatin
g
the pa
rticle
weig
hts
according to t
he wei
ght cal
c
ulate fo
rmul
a. Calc
ulating
the weig
ht and no
rmali
z
e
d
formula
are
as
follows
:
1
1
0:
1
0
:
()
(
)
,
1
,
2
,
,
(,
)
ii
i
kk
kk
ii
kk
s
ii
kk
k
pz
x
p
x
x
iN
qx
x
z
(1)
1
s
N
ii
i
kk
k
i
(2)
Step 3: Asort
the p
a
rti
c
les by weight
s.T
he th
re
shold
of pa
rticle
we
ight cl
assifica
tion at
time
k
can be
calcul
ated by:
12
,,
,
s
N
kk
k
As
o
r
t
(3)
((
)
)
3
s
th
r
N
k
A
r
ound
(4)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Fault Dete
ction and Isolati
on for GPS RAIM Based o
n
Geneti
c
Re
sam
p
ling…
(Ersh
en Wang
)
3913
If
the weight
of particle
i
k
x
is less than th
e threshold
()
i
kt
h
r
k
,
the particl
e will be
cla
ssif
i
e
d
as l
o
w-
wei
ght
pa
rt
icle
cla
ssif
i
c
a
t
i
on
1
{}
L
N
l
kl
x
.Otherwi
se, the particl
e
will be put into high-
weig
ht
part
i
cl
e cla
ssif
i
cat
i
o
n
1
{}
H
N
h
kh
x
, where
LH
s
NN
N
.
Step 4: Genetic m
anipul
ation. Co
ndu
ct gen
etic m
anipul
ation o
n
pa
rticle
set
of low-
weig
ht cla
ssif
i
cation. Spe
c
i
f
ic step
s are as follo
ws:
a) Cro
s
sove
r.
Select
two
rand
om sam
p
les
,1
(,
)
s
N
mn
kk
m
n
xx
from the
low-wei
ght particle set
1
L
N
l
k
l
x
accordi
ng to the rule
s as f
o
llows:
(1
)
mm
n
kk
k
xx
x
(5)
(1
)
nn
m
kk
k
xx
x
(6)
Whe
r
e
~(
0
,
)
N
and
~(
0
,
1
)
U
. T
he guid
e
line
of cro
s
sover i
s
:
If
()
m
a
x
{
()
,
(
)
}
mm
n
kk
k
k
kk
p
zx
p
z
x
p
zx
, particle
m
k
x
a
c
cepted. Ot
herwise, accept the
particl
e with
a pro
bability
of
()
m
a
x
{
()
,
(
)
}
mm
n
kk
k
k
kk
p
zx
p
z
x
p
z
x
. Accept o
r
aban
don p
a
rticle
n
k
x
in
the same
wa
y.
b) Mutation.
Select o
ne
random
sampl
e
1
()
s
N
j
kj
x
from th
e lo
w-weig
ht pa
rticle
set
1
L
N
l
k
l
x
according to the rule
s a
s
follow
s
:
,
~
(
0
,
)
jj
kk
xx
N
The guid
e
line
of mutation is as follo
w
s
:
If
()
(
)
j
j
kk
k
k
pz
x
p
z
x
, particle
j
k
x
accepte
d
. Otherwi
se, a
c
ce
pt the parti
cle with a
prob
ability of
()
(
)
j
j
kk
kk
pz
x
p
z
x
.
Through the cro
s
sover a
nd m
u
tation ope
ra
tion descri
b
e
d
above, getting a new
se
t of
low-wei
ght pa
rticle
s
1
L
N
l
k
l
x
, then merg
eing it w
i
th high-weig
ht particle
set
1
H
N
h
k
h
x
obtained in
step
3, therefore o
b
taining a n
e
w
parti
cle set
''
'
1
,
s
N
ii
kk
i
x
.
Step
4:
Re
sampli
ng
from
ne
w
particl
e
set
''
'
1
,
s
N
ii
kk
i
x
,
we will obtain
a ne
w re
sa
mpled
particl
e set
''
'
1
,
s
N
ii
kk
i
x
,
'
1
1
s
N
i
k
i
.
Step
5:
Predi
ctio
n.
Cal
c
ulate
the
state
e
s
ti
mation
by
1
ˆ
s
N
ii
kk
k
i
x
x
, and p
r
edi
cte
the
unkno
wn stat
us
1
i
k
x
by using the state eq
ua
tion
f
as
1
(,
)
,
1
,
2
,
,
ii
kk
k
s
xf
x
i
N
.
Step 6: Turn to step 2 when
1
kk
.
3. GPF Algor
ithm for RAIM
RAIM incl
ud
e two fu
nctio
n
s: dete
c
tion
of
satellite
wheth
e
r th
ere is
a fault, Identify a
faulty satellite, and the navigation calcula
t
ing pro
c
e
ss
will be re
mov
ed.
Fault dete
c
tio
n
an
d isolati
on mo
del
ba
sed
on
GPF
algorith
m
for
receiver auto
nomou
s
integrity moni
toring sy
stem
is as follo
ws:
System state
equation:
11
1
kk
k
k
X
FX
w
(7)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, N
o
. 5, May 2014: 3911 – 39
19
3914
Where,
[,
,
,
]
xy
z
Xr
r
r
,
is the
e
rro
r
of re
ceive
r
time
with
re
spe
c
t
to satellite
tim
e
,
F
is the
tra
n
sfe
r
mat
r
ix, whi
c
h i
s
ch
aract
e
risti
c
m
a
trix
in the
statio
nary
state,
w
i
s
th
e
pr
oc
ess
noise.
Measuremen
t equation:
()
(
)
()
()
()
ii
i
i
i
i
kR
k
c
T
k
E
k
k
(8)
Whe
r
e,
i
is th
e pseud
ora
n
ge bet
wee
n
receive
r
(,
,
)
xy
z
rr
r
and
satellite
(,
s
,
s
)
ii
i
xy
z
is
,
c
stand
s for lig
htspe
ed,
is the time com
pen
sation,
i
E
is
the eph
eme
r
i
s
erro
r,
is the co
de
observation
noise. And
，
22
2
()
(
)
(
)
ii
i
i
xx
y
y
z
z
Rr
s
r
s
r
s
stand
s for the true distance
betwe
en the
satellite
i
and the re
ceive
r
[16].
Measurement
sele
cted in
clude
s: coo
r
di
nates of
sat
e
llite
i
(,
s
,
s
)
ii
i
xy
z
s
, pseu
do
rang
e
i
,
the comp
en
sation
at each time.
The flow dia
g
ram of impl
ementing the
satellite fault detection a
nd isolatio
n method
based on L
L
R
test and G
P
F algorithm
sho
w
s in Figu
re 1.
MM
ˆ
x
,p
y
AA
ˆ
x
,p
y
BB
ˆ
x
,p
y
FF
ˆ
x
,p
y
SA
SB
SF
Figure 1. FDI Appro
a
ch Based o
n
LL
R Test and GPF
Algorithm
From each input measur
ed valu
e of
PFs,
it can
be seen that
when a positioning
satellite fails, one of auxiliary PFs will not
contain the measured va
l
u
es from the fault
satellite,
so the consistenc
y test can b
e
detected.
3.1.
Logarith
mic Likelihood Ra
tio Tes
t
Statis
tic
The
L
L
R
te
st can be define
d
as
the ratio of
each a
u
xiliary PFs and
main PF’
s
p
r
obability
den
sity function[17], and can be expressed a
s
:
ln
q
q
A
p
y
sy
p
y
(9)
The accu
mul
a
te LLR of m
easure
m
ent
s from
j
y
to
k
y
can be
expre
s
sed a
s
:
1
1
q
k
ii
k
j
A
ij
ii
py
Y
Sq
l
n
py
Y
(10
)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Fault Dete
ction and Isolati
on for GPS R
A
IM Based o
n
Geneti
c
Re
sam
p
ling…
(Ersh
en W
ang
)
3915
Becau
s
e
the
syste
m
state e
s
timation
likeliho
od fu
n
c
tion
ca
n b
e
app
roximate
d by the
norm
a
lized weig
hts
of particl
es, so
the
form
ul
a
1
q
ii
py
Y
and
1
A
ii
py
Y
above
ca
n b
e
expre
s
sed a
s
:
1
1
1
N
qq
ii
i
m
p
yY
w
m
N
(11
)
1
1
1
N
AA
ii
i
m
p
yY
w
m
N
(12
)
3.2.
RAIM Based on Genetic Particle Filter
The accum
u
l
a
ted LLR fun
c
tion of each
time
by
Equation (10
)
ca
n be obtaine
d, then
based on th
e accumul
a
te
d LLR fun
c
tion’s featu
r
e that under n
o
rmal ci
rcum
stan
ce
s, as time
increa
se
s, the curve i
s
a smooth functio
n
. W
hen the
data ch
ang
es, there will be
a negative d
r
ift
before the
chang
e, and a positive dri
ft after t
he chang
e.Wh
en the chan
ge i
s
refle
c
ted in
the
c
u
r
v
e o
f
fu
ncti
o
n
k
j
S
, it is a fl
uctuatio
n quit
e
differe
nt fro
m
the othe
r ti
me. With thi
s
feature
any
faults of syste
m
can be d
e
tected [18, 19]
.
Decision function for FD is:
11
ma
x
m
a
x
>
k
kj
kU
j
k
d
D
Sd
(13
)
Whe
r
e,
U
is th
e wi
ndo
w fu
nction
that
contain
s
the
e
a
ch
ob
se
rvati
ons befo
r
e
current
time, the window
size is selecte
d
ba
se
d on experi
e
n
c
e.
is the de
ci
sion threshol
d.
Whe
n
>
k
, it means the syste
m
has dete
c
ted a fault, it
sho
u
ld set al
arm and
set the
current time as
a
t
. Then, fault isol
ation
can
be con
ducte
d by u
s
ing the follo
wing fo
rmula
to
determi
ne fau
l
ty satellite ID: obtain the index
g
of the fa
ulty subset.
1
ar
g
m
ax
>
a
k
ta
dD
gS
k
t
(14)
In which the para
m
eter
g
stand
s for the index of faulty sub
s
et of me
asu
r
em
ents.
The detaile
d algorith
m
pro
c
e
s
ses
can b
e
expre
s
sed
by:
Step 1. Gen
e
rate the i
n
itial parti
cle
s
from the p
r
i
o
r pdf
0
()
p
x
arou
nd
the re
ceiver’s
coo
r
din
a
te for main PF and
auxiliary PFs. The particl
e
s
are:
Main PF:
0
{(
)
,
1
,
2
,
,
}
A
s
x
ii
N
Auxiliary PFs:
0
{(
)
,
1
,
2
,
,
}
q
s
x
ii
N
And
0
()
(
)
qA
o
x
ix
i
.
Step 2. State
predi
ction.
Put
0
{(
)
,
1
,
2
,
,
}
A
s
x
ii
N
and
0
{(
)
,
1
,
2
,
,
}
q
s
x
ii
N
into the sy
stem
state Equatio
n (7)
re
spe
c
t
i
vely, t
he predicte
d
valu
es of pa
rticl
e
1
()
A
kk
x
i
and
1
()
q
kk
x
i
can be
obtaine
d.
Step 3.
Cal
c
ulate p
a
rti
c
le
wei
ghts.
Pu
t parti
cle
pre
d
icted
value
s
1
()
A
kk
x
i
,
1
()
q
kk
x
i
, the
positio
n co
ordinate
s
(,
,
)
ii
i
xy
z
ss
s
of satellite
i
and th
e time error
into system
measuremen
t
equatio
n, obt
ain the
p
r
edi
cted
pseud
orange
value
i
of satellite
i
. The normali
ze
d
particle
weig
hts
()
A
k
i
and
()
q
k
i
can b
e
cal
c
ula
t
ed by p
u
tting the
pseudo
rang
e p
r
e
d
ict
i
on value
i
and
pse
udo
ran
ge measurement
value
i
into wei
ght cal
c
ulatio
n formula.
Step 4. Calcu
l
ate the LLR.
Calculating t
he log-li
keli
ho
od ratio by Equation (15
)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, N
o
. 5, May 2014: 3911 – 39
19
3916
11
11
()
l
n
(
(
)
(
)
)
ss
NN
k
kq
A
jr
r
rj
i
i
ss
Sq
i
i
NN
(
15)
Step 5. Calcu
l
ate the deci
s
i
on functio
n
b
y
11
ma
x
m
a
x
(
)
k
kj
kU
j
k
q
Q
Sq
.
Step 6. Fault detectio
n
. De
cisi
on thre
sh
old is
.
If
k
, fault alarm sets at time
a
tt
and skip to st
ep 6;
If
k
, there is n
o
fault, go to step 7.
Step 7. Faul
t isolation.
Compa
r
ing th
e
q
cum
u
lative LLRs
()
k
t
Sq
for
a
kt
, the fault
y
satellite
g
will be the one that
make
s a
ccu
mulated LL
R
maximum.
Step 8. Statu
s
upd
ates. Update pa
rticle
s of parti
cle filter by resamp
ling.
4. Experiment Re
sults a
nd Analy
s
is
Usi
ng
N22
0
GPS re
ceiver, the GPS da
ta wa
s colle
cted.The o
b
se
rvation dat
a i
n
clu
d
e
s
positio
n info
rmation
and
th
e p
s
eu
do
rang
e value
s
of th
e satellite fo
r
PVT sol
u
tion,
and
the
data
is
colle
cted fo
r 418
se
co
nd
s. In the
me
antime, the
r
e
are
six
sat
e
llites fo
r P
V
T sol
u
tion.
The
pse
udo
ran
g
e
mea
s
u
r
ed v
a
lue
can
be
expre
s
sed
a
s
13
4
5
6
(
,
,,
,,
)
y
y
y
yy
yy
. In order t
o
verify
wheth
e
r the
prop
osed F
D
I algorithm i
s
able to dete
c
t
and isolate the fault satell
ite, intentiona
lly,
the pse
udo
ra
nge bia
s
was
adde
d to the pse
udo
ran
ge
measurement
s of satellite 1
9
.
In the experi
m
ent, EKF, PF and GPF a
l
gorithm
a
r
e
employed to
pro
c
e
ss the
collecte
d
experim
ental
data, in o
r
de
r to com
pare t
he pe
rf
orman
c
e of th
ree
al
gorithm
s
whe
n
used in
RAI
M
algorith
m
. Figure 2
sho
w
s the de
cisi
o
n
function fo
r fault detect
i
on und
er no
rmal conditio
n
.
Figure 3 sh
o
w
s the
cumul
a
tive LLR of EKF, PF and GPF algo
rithm unde
r normal con
d
ition
.
Figure 2. De
cision Statistic
for Fault
Dete
ction un
der Norm
al Condition
Figure 3. Cu
mulative LLR
for Fault Isola
t
ion
unde
r No
rmal
Conditio
n
It can be see
n
in Figure 2
that GPF-ba
sed FDI's deci
s
ion fun
c
tion
value at each
time is
less than the
EKF-ba
s
ed
FDI's
and PF
-ba
s
ed
FDI's
deci
s
io
n function value, which
sho
w
s that
for the sel
e
ct
ed ala
r
m thresh
old, usi
n
g
GPF algorit
hm FDI sy
stem is le
ss li
kely to rea
c
h
the
alarm thresh
old whe
n
the failure did
not occu
r, whi
c
h is to say, the system false al
arm
prob
ability of FDI sy
stem u
s
ing
GPF alg
o
rithm i
s
le
ss than the F
D
I
method
usi
n
g EKF algo
rithm
and PF algo
ri
thm. Figure 3
sho
w
s the
cumulative LL
R cu
rve
s
of each a
u
xiliary
EKF-ba
s
ed F
D
I,
auxiliary PF-based FDI a
nd auxilia
ry
GPF-b
a
sed FDI. With re
gard to the
cumul
a
tive LLR
function
curv
e of the
same
satellite, EK
F-ba
se
d F
D
I
and PF
-ba
s
e
d
F
D
I's
cu
mul
a
tive LL
R h
a
ve a
greate
r
fluctu
ation ran
ge than the cu
m
u
lative LLR o
f
FDI based
on GPF, indicating that G
P
F
algorith
m
ca
n
estimate the
system
state more
p
r
e
c
isel
y than EKF algorithm a
nd
PF algorithm.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Fault Dete
ction and Isolati
on for GPS RAIM Based o
n
Geneti
c
Re
sam
p
ling…
(Ersh
en W
ang
)
3917
Figure 4 a
n
d
Figure 5
sh
ows the exp
e
r
iment
re
sults unde
r failu
re
con
d
ition
s
. Figure 4
sho
w
s the
d
e
c
isi
on
statisti
c
cu
rves of F
D
I ba
se
d
on
EKF, PF an
d
GPF fo
r fa
ul
t deci
s
io
n, a
n
d
Figure 5 sh
o
w
s the
cumul
a
tive LLR curves of
each a
u
xiliary filter for fault isolati
on.
Figure 4. De
cision Statistic
for Fault De
ci
sion
unde
r Failu
re
Conditio
n
Figure 5. Cu
mulative LLR
for Fault Isola
t
ion
unde
r Failu
re
Conditio
n
The p
s
eu
do
range m
e
a
s
u
r
ements
of sa
tellite No.19 f
r
om time
20
0
k
to time
41
8
k
has b
een m
o
dified by addi
ng co
nsta
nt erro
rs. As
ca
n be se
en from
Figure 4
and
Figure 5,
wh
en
the fault occu
rs, the d
e
ci
si
on stati
s
tic
k
of three F
D
I sy
stems all jum
p
cro
ss the ala
r
m thre
sh
old
signifi
cantly. This m
ean
s they all set al
arm afte
r th
e
onset of a fault. The FDI
algorithm
using
GPF sets al
a
r
m at the time
20
5
k
, the FDI usi
ng EKF and FDI usin
g PF sets ala
r
m at the time
21
0
k
. In Figure 5, the cumulati
ve LLR value
()
a
k
t
SD
of satellite No.19 ha
s the greate
s
t valu
e
among
othe
r LL
Rs,
acco
rding to
the f
ault dete
c
tion
prin
cipl
e a
b
o
ve, the p
s
e
udorang
e d
a
ta of
satellite
No.1
9 do
es’t exi
s
t in auxilia
ry P
F
D,
so
satelli
te No.1
9
can
be d
e
termi
n
e
d
to b
e
the fa
ult
satellite. Fa
u
l
t isolatio
n
can b
e
corre
c
tly ac
com
p
li
she
d
by discarding
the 19th satellite
’
s
observation
data for po
sition velocity and time
solut
i
on. Figure 4 and Figure 5 sho
w
s that all
three
FDI sy
stem
s can
succe
ssfully d
e
tect
a
nd i
s
olate the
fau
l
ty satellite.
Und
e
r
nomi
n
al
con
d
ition, but RAIM algorit
hm based on
GPF has
a smalle
st pro
b
ability of setti
ng false ala
r
m
than EKF and PF. The detection an
d isolatio
n perf
o
rma
n
ce of GPF-b
a
sed RAIM algorit
hm is
better than P
F
-ba
s
e
d
RAIM algorithm a
nd EKF-ba
s
e
d
RAIM algori
t
hm.
Table 1. Perf
orma
nce Co
mpari
s
o
n
of Different Algo
rithms
Algorithm
Number o
f
Parti
c
les
Average Numbe
r
of Effective Part
icles
RMSE
EKF
15.63751
PF
100 17.8779
7.45375
300 36.6847
6.85361
GP
F
100 28.7612
6.98691
300 59.6315
6.57852
Whe
r
e, The a
v
erage n
u
mb
er of effective
particle
s
an
d
RMSE can b
e
cal
c
ulate
d
by:
()
2
1
1(
)
s
N
k
ef
f
i
k
N
(16)
2
1
1
ˆ
()
s
N
k
ii
k
s
RM
SE
x
x
N
(17)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3911 – 39
19
3918
As sho
w
n in
Table
1, wh
e
n
the n
u
mbe
r
of pa
rticle
s
selecte
d
a
s
100
s
N
, RMSE of GPF
is 6.986
91, RMSE of PF is 7.45375, a
n
d
RMSE of EKF is 15.63
7
51, whi
c
h in
d
i
cate
s that G
P
F
has the
optim
al a
c
curacy
o
f
state
estima
tion. Th
e
ave
r
age
n
u
mbe
r
of effective
p
a
rticle
s of GP
F
is 2
8
.761
2, which
is mo
re
than PF,
indi
cates
GPF
do
better i
n
sup
p
r
essin
g
sam
p
le de
gra
datio
n.
Whe
n
the nu
mber of pa
rticle
s ch
osen as
30
0
s
N
, RMSE of GPF and PF both red
u
ced, the
averag
e num
ber of effe
ctive particl
es
o
f
GP
F and P
F
both in
cre
a
s
ed, me
an
s
unde
r the
sa
me
con
d
ition
s
, the more p
a
rticl
e
s, the more accurate of the estimation.
4. Conclusio
n
The
app
roa
c
h of fault
de
tection
and
i
s
olatio
n (FDI
) for GPS
receive
r
a
u
to
nomou
s
integrity moni
toring
(RAIM) based on
g
enetic al
go
ri
thm-a
s
siste
d
particl
e
filter (GPF) algo
rithm
and the
log
-
l
i
kelih
ood
rati
o (L
LR) te
st method
wa
s p
r
op
osed.
Comp
ared
wi
th PF and
EKF
estimation,
th
e a
c
cura
cy
of improved
pa
rticle
filt
er e
s
t
i
mation i
s
im
proved
by a
p
p
lying
sele
cti
on,
cro
ssove
r
an
d mutation of
genetic
algo
rithm into the
basi
c
pa
rticle
filter. The qu
ality of particl
es
after resampl
i
ng i
s
im
prov
ed. Th
e
RAIM alg
o
rithm
prop
osed
are
co
mpa
r
ed
wi
th PF-b
ased
and
EKF-ba
s
ed
RAIM alg
o
rit
h
m a
nd ve
rified by
mea
s
u
r
ed
data
coll
ected
from
t
he GPS
re
ce
iver
experim
ent platform, the
simulation
results sho
w
that in environme
n
t of non-G
a
u
ssi
an
measurement
noise, the F
D
I app
ro
ach
usin
g GPF i
s
sup
e
ri
or to P
F
-ba
s
e
d
F
D
I and EKF-ba
s
ed
FDI. Applying
GPF algorith
m
in FDI for
RAIM also
re
duce the false alarm
rate
of fault detect
i
on,
sho
r
ten th
e ti
me of
setting
alarm
s
. Th
e
geneti
c
al
gori
t
hm-a
ssi
sted
particl
e filter (GPF)
algo
rith
m
improve
s
th
e
state
estima
tion a
c
cura
cy
, improve
s
th
e reli
ability of
fault dete
c
tion. It is fea
s
i
b
le
and
effective
to
combi
ne
GPF alg
o
rith
m with
log
-
likelihoo
d ratio
test meth
d fo
r GPS
re
ceiv
er
autonom
ou
s i
n
tegrity monit
o
ring
(RAIM)
in non
-G
au
ssian me
asure
m
ent noi
se
e
n
vironm
ent, a
nd
the
detection and
isol
ation perfo
rman
ce of
GP
F-ba
se
d RAIM method is better t
han EKF-b
ased
RAIM ap
proa
ch
and
PF-b
ase
d
RAIM a
ppro
a
ch.
Th
e
GPF-ba
sed
RAIM alg
o
rit
h
m p
r
op
osed
in
this pap
er
ha
s a certai
n si
gnifica
nce value for the
stu
d
y of Beidou
se
con
d
-g
ene
ration navigati
on
receiver a
u
to
nomou
s integ
r
ity monitorin
g
.
Ackn
o
w
l
e
dg
ements
The wo
rk wa
s su
ppo
rted
by the National Natu
ral Scien
c
e Fou
ndation of China (No.
6110
1161
), t
he Ae
ron
auti
c
al S
c
ien
c
e
F
ound
ation
of
Chin
a (No.
2
011Z
C54
010
), the Joint F
u
nds
of the Natural
Science Fou
ndation of Lia
oning Province (No. 20
130
2400
3).
Referen
ces
[
1
]
Mat
h
ie
u J,
F
a
ng-C
hen
g C,
St
even
L,
et
al.
RAI
M
d
e
t
e
ct
or an
d est
i
mat
o
r d
e
sig
n
t
o
mini
mi
z
e
t
h
e
integr
ity risk.
P
r
oceedings of
the 25th
Intern
ational T
e
chni
cal M
eeting
of
the Satellit
e Di
vision of t
h
e
I
n
st
it
ut
e of
Navigat
i
on.
Nas
hvil
le.
201
2;
385
6-
386
7.
[2]
Binj
ammaz T
,
Al-Bay
atti A, Al
-Hargan A.
GPS integr
ity monitoring for
an
i
n
telli
gent trans
port system
.
Procee
din
g
s of
t
he 10t
h Workshop o
n
Posit
i
oni
ng
Nav
ig
at
i
on an
d Comm
unic
a
t
i
on.
Dres
den.
20
13;
1-
6.
[
3
]
Xu
Xia
oha
o,
Yang
Chu
ans
en,
Li
u Ru
ihu
a
.
Revi
e
w
a
n
d
pros
pect
of
GNSS receiv
er aut
o
nomo
u
s
int
egr
it
y
Mo
nit
o
ring.
Act
a
Aero
naut
ic
a et
Ast
r
ona
ut
ica Si
nica
.
2013;
34(
3):
451-4
63.
[
4
]
Sun Qia
n
,
Ju
n Z
han
g,
ed
it
ors.
RAI
M
me
t
hod f
o
r
i
m
pro
v
ement
o
n
G
N
SS rel
i
ab
ilit
y
and
int
e
grit
y.
Procee
din
g
s o
f
28t
h Digit
a
l
Avionics S
y
st
ems Conf
ere
n
c
e:
Moder
nizat
i
on of
Avionics
and AT
M-
Perspect
i
v
e
s f
r
om t
he Air and
Ground.
Orla
nd
o,
F
L
.
2009;
7(
3):
1-11.
[5]
Yang Jing, Zhang Hongy
u
e.
Optimal
Parit
y
V
e
ctor M
e
thod for
Satellit
e Fault Di
agnosis.
Ch
ine
s
e
Journ
a
l of
Aero
naut
ics.
20
02;
23(2):
18
3-6.
[
6
]
Sun Gu
oli
a
n
g
,
Sun M
i
n
gha
n,
Che
n Ji
np
ing.
A st
ud
y
on t
i
me an
d s
e
t
co
mbin
ed m
e
t
h
o
d
f
o
r rec
e
iv
e
r
int
egr
it
y
a
u
t
o
n
o
mous mo
nit
o
r
i
ng.
Act
a
Aero
naut
ic
a et
Ast
r
ona
ut
ica Si
nica
.
2006;
27(
6):
1171-
117
5.
[7
]
Ma
th
ieu
J, Bo
ris P.
I
n
t
egrit
y risk of
kal
m
a
n
f
ilt
er-bas
ed R
A
I
M
.
Proceedi
ng
s of
t
he 24t
h I
n
t
e
rnat
i
o
n
a
l
T
e
chnical Meet
ing of
T
he Sat
e
llit
e Div
i
sio
n
of
t
he I
n
st
it
ut
e of
Navig
at
io
n.
Na
shvill
e.
201
1;
3
856-
386
7.
[
8
]
Yun Yo
ungs
un
,
Do
yoon K
i
m.
I
n
t
egrit
y Moni
t
o
ring Al
gorit
h
m
s Usi
ng F
ilt
e
r
ing Ap
pro
a
ch
es f
o
r Hig
h
e
r
Navig
at
io
n Per
f
orma
nce:
C
o
n
s
ider
at
ion
of
t
he N
on-Gauss
i
an Gnss M
e
a
s
ure
m
e
n
t
s
.
Procee
din
g
s o
f
t
he 20t
h I
n
t
e
rn
at
ion
a
l T
e
chnic
a
l Meet
i
ng of
t
he Sat
e
l
lit
e.
F
o
rt
Wort
h,
T
X
.
2
007;
30
70-
308
1.
[
9
]
Arulam
pal
am
MS,
Maskell
S
,
Gordon
N,
et
al.
A t
u
t
o
r
i
al
on p
a
rt
icl
e
f
ilt
e
r
s f
o
r on
lin
e n
onli
n
e
a
r/
no
n-
Gaussia
n
Ba
ye
sian t
r
acki
ng.
IEEE Transacti
ons on Si
gnal
Processi
ng
.
20
02;
50(2):
1
74-
188.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Fault Dete
ction and Isolati
on for GPS RAIM Based o
n
Geneti
c
Re
sam
p
ling…
(Ersh
en W
ang
)
3919
[
10]
Gust
af
sson F
,
F
r
edrik G.
Part
icle F
ilt
ers f
o
r
Posit
i
o
n
in
g,
Na
vigat
i
on,
an
d T
r
ackin
g
.
IEEE Transactions
on Sig
nal Pr
oc
essin
g
.
200
2;
50(2):
425-
37.
[
11]
Wu Mei,
F
u
jun
Pei.
I
m
proved
Dist
ribut
e
d
Pa
rt
icle F
ilt
er f
o
r Simult
a
neo
us
Loca
lizat
i
on a
n
d
Mapp
in
g.
T
E
LKOMNI
KA I
ndon
esi
an Jou
r
nal of
Elect
r
ic
al Eng
i
ne
eri
n
g
.
2013;
1
1
(12):
152
6-15
30.
[
12]
Yang Y
ang,
Xue
Xia
o
zh
on
g.
Appl
icat
io
n of
GA-aid
e
d
part
i
cle f
ilt
er i
n
t
i
gh
t
coupli
ng GPS
/
I
N
S s
y
st
em.
Journ
a
l of
PLA
Universit
y of
S
c
ienc
e an
d
T
e
chno
logy (N
at
ur
al Scie
nce Edit
ion).
20
11;
12(
4):
322-3
27.
[
13]
F
Jianch
e
n
g
,
Xi
ao
lin
N.
Aut
onom
ous C
e
l
e
st
ial N
a
vig
a
t
i
o
n
f
o
r Lu
nar E
x
p
l
or
er Base
d
on Gen
e
t
i
c
Algorit
hm Parti
c
le Filter.
Jour
nal
of
Beij
ing
Univers
it
y of
Aeron
aut
ics a
n
d
Ast
r
onaut
ics
.
200
6;
32(1
1
)
:
127
3-12
79.
[
14]
Yan
Xues
ong,
Wu Qin
g
h
ua,
Li
u H
a
mmin.
An I
m
prov
ed
Rob
ot
Pat
h
Pl
ann
ing
Al
gorit
hm Bas
e
d
on
Genet
ic Al
gorit
hm.
T
E
LKOMNI
KA I
ndon
esi
an Jo
urna
l of
Elect
r
ical E
n
g
i
neer
ing.
2
0
1
2
;
10(8):
19
48-
195
5.
[
15]
Yang
Nin
g
,
F
eng Qia
n
,
Rui
Z
hu.
I
m
proved
Part
icle F
ilt
e
r
Based
on G
enet
ic A
l
gor
it
h
m
.
Journa
l o
f
Shan
gh
ai Jia
o
t
ong U
n
ivers
i
t
y
.
2011;
4
5
(10):
152
6-15
30.
[
16]
Kapl
an E,
H
e
g
a
rt
y
C.
Un
ders
t
andi
ng GPS:
Princip
l
es an
d Appl
icat
io
ns.
S
econ
d
Ed
it
ion.
USA:
Art
e
c
h
Hous
e,
I
n
c.
2006:
239-
26
4.
[
17]
Rosih
an R,
A I
ndri
y
at
m
o
ko,
S
Chun.
Part
ic
le
F
ilt
ering A
ppr
oach t
o
F
a
u
l
t
Det
ect
i
o
n
an
d
I
s
olat
io
n f
o
r
GPS I
n
t
egrit
y
Monit
o
ri
ng.
Pr
oceedings of the 19th
International T
e
chni
cal
Meeting of
the Satellite
Divisi
on of
T
he I
n
st
it
ut
e of
Navigat
i
on.
F
o
rt
Wort
h,
T
X
.
200
6;
873-8
81.
[
18]
Li Pin
g
,
Visaka
n K.
Part
icle F
ilt
erin
g Base
d L
i
keli
ho
od R
a
t
i
o
Approac
h t
o
F
ault
Di
agn
osis
in No
nli
n
e
a
r
St
ochast
i
c S
y
s
t
ems.
I
EEE Tr
ansacti
ons on System
s, Man,
and Cy
berneti
cs, Part C: Ap
plicati
ons and
Review
.
200
1;
31(3):
33
7-3
4
5
.
[19] VASWANI
N.
Boun
d o
n
error
s
in p
a
rt
icle f
ilt
erin
g w
i
t
h
incor
r
ect
mo
de
l ass
u
mpt
i
o
n
s an
d i
t
s imp
licat
i
o
n
f
o
r cha
n
g
e
det
ect
i
on.
Pr
oceedings of
IEEE I
n
ternati
o
nal
Conf
erenc
e
on Ac
oustics, Speec
h and signal
process
i
ng.
Mo
nt
real.
20
04:
I
I
729-I
I
732.
Evaluation Warning : The document was created with Spire.PDF for Python.