# A Modified Range Consensus Algorithm Based on GA for Receiver Autonomous Integrity Monitoring

Authors: Jing Zhao; Chengdong Xu; Yimei Jian; Pengfei Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

With the considerable increase of visible satellites for positioning, the fault detection and identification performance of Range Consensus (RANCO) algorithm for Receiver Autonomous Integrity Monitoring (RAIM) will significantly be improved. However, the calculation amount of RANCO algorithm will exponentially increase for the sharp addition of visible satellite subsets. This paper proposes a modified RANCO algorithm based on genetic algorithm (GA-RANCO) for RAIM to inhibit the exponentially expanded calculation amount. To reduce the calculation amount in searching the optimal minimal necessary subset (MNS), the preselection step is developed to speed up the convergence process of GA-RANCO. It is executed to exclude the chromosome-represented MNS for which the count of faulty satellites will exceed the upper limit of independent simultaneous satellite faults to be monitored. Mathematical simulations are introduced to determine the GA parameters, and simulation experiments under different schemes are designed to evaluate the performance of GA-RANCO algorithm. Results illustrate that the time consumption under a large number of visible satellites of GA-RANCO is much lower than that of RANCO and the faulty detection and identification performance of GA-RANCO is the same as that of RANCO.


---

## Body

## 1. Introduction

The integrity of GNSS is an important factor to ensure the safety of civil aviation, which can be assured at system or user level [1–3]. The former is provided through an independent network of monitoring stations and a dedicated integrity channel, such as satellite-based augmentation system (SBAS) and ground-based augmentation system (GBAS), and the latter is provided by Receiver Autonomous Integrity Monitoring (RAIM) [4, 5]. With more and more visible satellites from multiconstellations being possible to be received at the same time, the multiple hypothesis solution separation (MHSS) algorithm and the range consensus (RANCO) algorithm were representatively proposed to deal with the multiple satellites fault for RAIM [6–14].The MHSS algorithm is recommended in advanced RAIM (ARAIM), which is developed to meet the integrity requirement of LPV-200 using GPS and Galileo [15]. MHSS is implemented in the position domain and its principle is to minimize the protection level (PL) [16, 17]. However, a faulty satellite with a large pseudorange bias which does not translate in a large position domain error may not be excluded because it reduces the PL just to a small extent [17]. With enough visible satellites being possible to be received, this kind of faulty satellite needs to be excluded even if its pseudorange bias affects the position error slightly, whereas it cannot be achieved using MHSS algorithm [18, 19].The RANCO algorithm is implemented in the measurement domain and it can meet the above requirement [20, 21]. According to the simulation result from Schroth and Song [10, 22], the RANCO algorithm performs higher fault detection probability than the MHSS algorithm and snapshot RAIM algorithm. RANCO is developed based on the elementary idea of the random sample consensus (RANSAC) algorithm, which is well known in the field of graphics and image processing [23], and identifies multiple faulty satellites by searching the outliers for the minimal necessary subset (MNS), containing the least visible satellites able to estimate the user position. All MNSs should be traversed to find the optimal MNS, which presents the optimal consistency with other visible satellites. Then, its inliers will be identified to be the nominal satellite and its outliers will eventually be identified as the faulty satellites. Since all MNSs need to be traversed, the calculation amount of RANCO will exponentially increase with visible satellite addition [10, 21].With regard to reducing the huge calculation amount of RANCO, two preexclusion approaches were proposed via excluding the poor geometry MNS before outlier searching. The first was via calculating the GDOP value of MNS. The MNS with GDOP exceeding a setting threshold will be excluded [24]. The second was via analyzing the correlation of every two line-of-sight (LOS) vectors [11, 25]. The MNS with the correlation coefficient of any two LOS vectors exceeding a setting threshold will be excluded [21]. Test results show that the calculation amount of GDOP approach is much larger than that of LOS approach because of the matrix inversion calculation [22]. However, even if the preexclusion approach is applied, the calculation amount of RANCO algorithm is still huge for multiple GNSS constellations, exponentially increasing with visible satellites addition.In this paper, considering that the essence of RANCO algorithm is to search the optimal MNS, we propose a modified RANCO algorithm based on genetic algorithm (GA) for RAIM, which is a bionic optimization algorithm achieved by simulating the biological evolution process, including inheritance, preselection, selection, crossover, and mutation [26–29]. This modified algorithm, abbreviated as GA-RANCO, can inhibit the exponentially increasing calculation amount of RANCO.The remainder of this paper is organized as follows. Section2 reviews RANCO algorithm with MNS preexclusion using LOS approach, abbreviated as LOS-RANCO. In Section 3, the GA-RANCO algorithm is developed. The convergence process of GA-RANCO is accelerated by the chromosome conditional selection for the initial generation and the chromosome preselection for each generation. Section 4 introduces the determination of GA parameters based on mathematical simulations. Section 5 designs simulation experiments to evaluate the performance of GA-RANCO compared with LOS-RANCO. Section 6 concludes the work with a brief summary.


## 2. Fault Detection and Identification Using LOS-RANCO Algorithm

Assuming that the pseudorange noise of each visible satellite obeys zero mean normal distribution in nominal mode and the pseudorange observations are independent of each other, the RANCO algorithm is designed to identify multiple faulty satellites by searching outliers for the MNS, which contains the least visible satellites being able to estimate the user position.Here, we assume there areN constellations and m visible satellites; then the number of visible satellites for each MNS will be 3 + N and the number of MNSs will be Cm3+N. For the jth MNS, denoted as MNSj, the user position estimate X^j can be expressed as follows:(1)X^j=HjTWjHj−1HjTWjZj,where Hj is the geometry matrix, Zj is the pseudorange vector, and Wj=diag1/σkj2 is the weight matrix, with σkj representing the standard deviation of pseudorange noise for k−th satellite in MNSj.The number of satellites under test (SUT) forMNSj, i.e., the visible satellites not belonging to MNSj, will be i=m−3+N. For the ith visible satellite under test of MNSj, denoted as SUTij, its pseudorange residual can be expressed as follows:(2)ωij=zi−hiX^j,where zi is the pseudorange of SUTij and hi is the corresponding line of SUTij in the geometry matrix.Setting the pseudorange error ofSUTij to be ξi and the pseudorange error vector of MNSj to be ξj=ξ1j,…,ξkj,…,ξ3+NjT, equation (2) can be expressed as(3)ωij=hiX+ξi−hiHjTWjHj−1HjTWjHjX+ξj=ξi−hiHjTWjHj−1HjTWjξj.When each visible satellite inMNSj and SUTij is in the nominal mode, ωij would obey normal distribution with the following statistical characteristics:(4)Eωij=Eξi−hiHjTWjHj−1HjTWjEξj=0,Dωij=Dξi−hiHjTWjHj−1HjTWjDξjhiHjTWjHj−1HjTWjT,where E· and D·, respectively, represent the expectation and the variance of a random variable.SubstitutingEξi=0, Eξj=0, Dξi=σi2, and Dξj=Wj−1 into (4),(5)Eωij=0,Dωij=σi2−hiHjTWj−1Hj−1hiT.When each visible satellite inMNSj is in the nominal mode while in SUTij is a faulty satellite, ωij would obey the following distribution:(6)Eωij=bi,Dωij=σi2−hiHjTWj−1Hj−1hiT,where bi represents the pseudorange bias caused by satellite fault.According to equations (5) and (6), the consistency between SUTij and MNSj, i.e., SUTij is an inlier or an outlier of MNSj, can be checked using the test threshold Tij=3σi2−hiHjTWj−1Hj−1hiT. When ωij≤Tij, SUTij will be considered as an inlier for MNSj, i.e., SUTij has good consistency with MNSj. Otherwise, SUTij will be considered as an outlier for MNSj, i.e. SUTij has poor consistency with MNSj. A low outlier count indicates that the estimate of MNSj can fit the user real position well and MNSj has a high consensus with the other visible satellites.After testing of allSUTij, an augmented subset MNSj+ consisting of all inliers for MNSj and satellites belonging to MNSj can be established. The number of satellites in MNSj+ will be Ij+3+N, where Ij represents the number of inliers and 3+N represents the number of satellites belonging to MNSj. The overall consistency of MNSj+ can be checked using the pseudorange residual sum of squares for MNSj+, denoted as SSEj+. A low SSEj+ indicates a good consistency with MNSj+.SSEj+ belonging to MNSj+ can be calculated as follows:(7)SSEj+=ωj+TWj+ωj+,where Wj+=diag1/σkj+2, with σkj+ representing the standard deviation of pseudorange noise for k−th satellite of MNSj+ and ωj+ is the pseudorange residual vector for MNSj+:(8)ωj+=Zj+−Z^j+=Zj+−Hj+X^j+,where Zj+ is the pseudorange vector for MNSj+, Hj+ is the geometry matrix for MNSj+, and X^j+ is the user position estimate calculated by weighted least squares algorithm according to MNSj+:(9)X^j+=Hj+TWj+Hj+−1Hj+TWj+Zj+.Utilizing the property ofSSEj+, an indicator can be constructed to evaluate the performance for every MNS as follows:(10)Tj=SSEj+Ij+3+N.MNSj with the minimum Tj value will be considered as the optimal one, denoted as MNSopt. It has three characteristics: no faulty satellite, minimum SSEj+ value, and maximum Ij+3+N value. The outliers for MNSopt will be identified to be the faulty satellites.The LOS-RANCO approach to preexclude the poor geometry MNS before outlier identifying is implemented by calculating the correlation coefficient (CCF) of the LOS vectors for each two visible satellites. Assuming that the LOS vectors ofVSi and VSj are, respectively, Xixi,yi,zi and Xjxj,yj,zj, the CCF between the two satellites will be(11)CCFij=xixj+yiyj+zizjxi2+yi2+zi2xj2+yj2+zj2.As seen in equation (11), CCF is the cosine of the angle between two LOS vectors. The value range of CCF is −1,1. Large CCF value indicates strong correlation. CCFij=1 represents the LOS vectors of VSi and VSj are the same, CCFij=0 represents the LOS vectors of VSi and VSj are orthogonal, and CCFij=−1 represents the LOS vectors of VSi and VSj are in the opposite direction. Given a threshold for CCF, the MNS should be excluded when the CCF value of any two satellites in it exceeds that threshold. The threshold for CCF is set as TCCF=0.8 [11].


## 3. A Modified RANCO Algorithm Based on GA

With the rapid development of GNSS, the visible satellites under multiconstellations will increase more and more. The abundantly redundant pseudorange measurements can significantly improve the performance of RANCO algorithm [30, 31]. However, the calculation amount will exponentially increase with visible satellite addition. In this section, a modified RANCO algorithm based on GA is proposed to inhibit the exponentially expanded calculation amount.The flowchart of GA-RANCO algorithm is shown in Figure1, roughly divided into 5 steps:Step 1. Code each visible satellite as a gene.Step 2. Generate the initial population G0.Step 3. Prevent the bad chromosome from getting into the regular operation of GA via preselection.Step 4. Iteratively genetically operate for each generation of population until the genetic generation count reaches T, including selection, crossover, mutation, fitness calculation, and preselection. The population of the t−th generation is signed as Gt. Gt after selection, crossover and mutation are respectively recorded as Gts, Gtc, and Gtm.Step 5. Exclude the faulty satellites according to the optimal MNS, i.e., the MNS represented by the chromosome which owning the maximum fitness among the population of the T−th generation.Figure 1
Flowchart of GA-RANCO.The details of GA-RANCO algorithm is introduced as follows:(1)
Gene coding:Each visible satellite is edited as a gene code, an integer between 1 andm. m represents the total number of visible satellites. A gene code has one-to-one correspondence with a visible satellite, but unrelated to its constellation and its specific satellite number. All of gene codes constitute a gene pool.(2)
Initial population generation:M (an even) chromosomes should be generated for the initial population. Each chromosome consists of 3 + N gene codes, which are arbitrarily selected from the gene pool. Because each chromosome represents a MNS, the gene cannot be repeated and the order of gene codes is arbitrary. To ensure the genetic diversity, each chromosome in the initial population should be different.In order to speed up the convergence process, the outlier number of the chromosome-representedMNS should not exceed the maximum number Nsat,max of independent simultaneous satellite faults to be monitored in the initial population generation. The outlier identification is completed during the fitness calculation for each newly generated chromosome. The specific Nsat,max calculation can be seen in the preselection step and the specific fitness calculation process can be seen in fitness calculation step.(3)
Preselection:The preselection step is specially designed for GA-RANCO and is not a general procedure in GA. It is executed before the regular selection operation of GA. Preselection is used to exclude the chromosome which represents a MNS having more thanNsat,max outliers. Nsat,max is the maximum number of independent simultaneous satellite faults to be monitored. If the chromosome-represented MNS owns outliers more than Nsat,max, it might contain a gene code representing a faulty satellite. Therefore, this chromosome-represented MNS cannot be the optimal one.Nsat,max is the minimum x-value satisfying the following equation [15, 32]:(12)PSAT,not monitored=∑j=x+1mPSAT_j≤PSAT_THRES,wherePSAT_j is the prior probability of j satellites independent simultaneous fault, m is the total number of the visible satellites, and PSAT_THRES is the threshold for the integrity risk coming from unmonitored satellite faults, much smaller than the total integrity budget.With the assumption that the prior probabilityPsat for each satellite fault is the same,(13)PSAT_j=CmjPsatj1−Psat1−j,wherePsat is the prior fault probability of satellite.For example, assume there are 16 visible satellitesm=16, all with Psat=1×10−4, and PSAT_THRES=4×10−8,(14)PSAT,not monitored=1.20×10−6>PSAT_THRESx=1,PSAT,not monitored=5.59×10−10≤PSAT_THRESx=2.Thus,Nsat,max=2, which means more than 2 independent simultaneous satellites fault can be neglected for its integrity risk being much less than the total integrity budget. Then, the MNS can be considered to contain faulty satellite when it has more than 2 outliers in this example.The preselection can prevent the chromosome which may contain the gene code of a faulty satellite getting into the regular operation of GA [31, 33] and speed up the convergence process of GA-RANCO. To ensure a constant chromosome number of the population, the first few large-fitness chromosomes should be repeated to replace the excluded ones after preselection.(4)
Roulette selection:Roulette is used for chromosome selection. Assuming the fitness of theith chromosome cit is fit, the cumulative fitness Fit from ci1 to cit is calculated as follows:(15)Fit=∑j=1ifit.Simulating a roulette, a random variable satisfying the uniform distribution of [0, 1] is generated for each selection time. If the value of the random variable fell betweenFit and Fi−1t, cit would be selected. The large-fitness chromosome has high probability of being selected. To ensure a constant number of chromosomes in the population, M times of roulette selection are executed.(5)
Single-point crossover:As seen in Figure2, the cross point is randomly selected. When a chromosome after crossover shows repeated gene codes, the crossover operation would be revoked.(6)
Single-point mutation:As seen in Figure3, the mutation point is randomly selected as well. To avoid gene repetition in the mutated chromosome, the mutant gene should be different from any one in the original chromosome.(7)
Fitness calculation:The performance evaluation indicator for a chromosome is the fitness. The fitness forcit is as follows:(16)fit=Ii+3+NSSEi+,where SSEi+ is the SSE of the augmented subset consisting of the satellites corresponding to all gene codes in cit and the inliers of cit-represented MNS, where Ii is the inlier count for cit-represented MNS, and N is the constellation count.Figure 2
Single-point crossover.Figure 3
Single-point mutation.As seen in equation (16), the fitness for cit in GA-RANCO is the reciprocal of the performance evaluation indicator for cit-represented MNS in LOS-RANCO. Because a small SSE value and a large inlier count represent good performance of a chromosome, to maintain good performance chromosome in selection, the fitness should be designed to take a large value. During fitness calculation, the outliers for a chromosome-represented MNS can be obtained simultaneously. The specific outlier identification process for MNS can be seen in LOS-RANCO review section.


## 4. GA Parameters Determination

In this section, mathematical simulations are designed to determine the GA parameters, including genetic generationT, population chromosome number M, cross probability Pc, and mutation probability Pm.The work is completed using Microsoft Visual Studio 2010 on a personal computer, which has 3.40 GHz CPU and 8.00 GB RAM.Figure4 shows the simulation architecture. The input of the simulation is ephemeris, simulation epoch, user real position, pseudorange bias, and PRN of faulty satellite. The simulation process can be divided into two parts: the observation data simulation and the fault detection/identification.Figure 4
Simulation architecture.In observation data simulation, satellite position is calculated according to the ephemeris downloaded from IGS website and the specific simulation epoch. Then the visibility of satellite is judged according to elevation angle. If the elevation angle is larger than the masking angle, the satellite is judged to be visible. For a visible satellite, the range between it and the user real position is calculated. If the visible satellite is assumed to be fault, the pseudorange bias would be added on its real range. The pseudorange bias is a constant for the step fault mode, while it is a value linearly increased with time for the ramp step fault mode.The dual-frequency ionosphere-free combination is assumed to be used for the pseudorange observation. The pseudorange observation is generated according to the ephemeris downloaded from IGS website. The satellite clock error, the ephemeris error, and the tropospheric delay are not considered in the simulation. Assuming simulation experiments are conducted in an open area near the ground, only the receiver noise is simulated as the pseudorange noise, using Gaussian models with zero mean. The standard deviations of the receiver noiseσinoise for the ith visible satellite are as follows, coming from the ARAIM interim report [15]:(17)σinoise=0.15+0.43exp−θi6.9,where θi represents the elevation angle in degrees. Actually, (17) is set for GPS. However, it is used for both GPS and BDS pseudorange noise simulating in this simulation because there is no widely used pseudorange noise distribution model used for RAIM of BDS now [34].Using dual-frequency ionosphere-free combination, the pseudorange noise for theith visible satellite is generated as Gaussian noise with the standard deviation as follows:(18)σi=f14+f24f12−f222σinoise,where f1=1575.42MHz for GPS L1 and BDS B1C and f2=1176.45MHz for GPS L5 and BDS B2a.These simulations are implemented in the Asia-Pacific Area (55°S∼55°N, 70°E∼150°E), which is divided into girds. At each gird point, both LOS-RANCO and GA-RANCO are implemented to detect/identify the satellite fault. BDS is simulated as a 14-satellite constellation (5GEO + 5IGSO + 4MEO) and C02 is set as the faulty satellite with the pseudorange bias of 8σ, where σ represents the standard deviation of pseudorange noise for its corresponding satellite.


### 4.1.T and M Determination

To ensure the same fault identification for GA-RANCO and LOS-RANCO, the executed termination condition of GA-RANCO inM and T determining simulation is as follows:(19)maxfGAt−1fLOS<10−4,where maxfGAt is the maximum fitness in the tth generation of GA-RANCO and fLOS is the performance evaluation indicator for the final optimal MNS of LOS-RANCO. The parameter t satisfying the termination condition is recorded as Ts.Both the fault identification probability and the calculation amount should be considered. The GA-RANCO fault identification probability can be measured by the probability ofmaxfGAT−1/fLOS≥10−4, which means the probability of that the faulty satellites identified by GA-RANCO at genetic generation T are different from those identified by LOS-RANCO. To guarantee that GA-RANCO has equivalent fault detection and identification performance of LOS-RANCO, this probability should be as small as possible. The GA-RANCO calculation amount can be measured by the product of T and M, which presents the times of fitness calculation. This product should be as small as possible.SettingPc=0.1 and Pm=0.1, two simulation experiments are designed to determine T and M.The first simulation is used to preliminary screen the suitableM. It is set at a given time epoch (2019-3-13 00:40:00 of UTC time). The Asia-Pacific area is divided into grids with a resolution of 1°. There are in total 111×81=8991 grid points. M is set from 6 to 26. For each M value, the Ts values of 8991 grid points are recorded in Figure 5.Figure 5
Ts for different M values.As seen in Figure5, the times of Ts value larger than 10 decrease with the increase of M, even being less than 6 for M being larger than 14, which is less than 0.1% of the total grid points. When M takes a value smaller than 14, T should be assigned a large value to guarantee the fault detection/identification probability, which will bring a large calculation amount. For example, T should be 60 for M=10 to ensure the probability of maxfGAT−1/fLOS≥10−4 being less than 0.1%. Moreover, with M being larger than 20, the times of that Ts taking a large value (larger than 10) basically keep constant, which means the probability of maxfGAT−1/fLOS≥10−4 keeps almost constant with T=10 and M≥20. Considering both fault detection/identification probability and calculation amount, M should be assigned a value between 14 and 20.The second simulation is to determine the optimal value ofT and M. It is set in a whole day (2019-3-13 00:00:00 to 2019-3-14 00:00:00 of UTC time) with the time step of 600 s. The Asia-Pacific area is divided into grids with a resolution of 2°. There are in total 56×41=2296 grid points. Both GA-RANCO and LOS-RANCO are implemented at each gird point and simulation epoch with M from 14 to 20. For each M value, there are 33062424×6×2296Ts values. The probability of Ts>T, denoted as PTs>T, is calculated, where T=2,3,⋯,40:(20)PTs>T=NTs>TN.In equation (20), NTs>T presents the times of Ts>T for each M value and N presents the total simulation times, N=330624. Actually, PTs>T=maxfGAT−1/fLOS≥10−4.As seen in Figure6, the PTs>T−T curves for M=14,16,18,20 are roughly arranged from high to low, which means PTs>T decreases with M addition at a given T value. The value of PTs>T sharply decreases at the beginning, and its decrease speed slows down gradually to about 0 with T addition. The curves for M=16,18,20 are very close, clearly separated from curve for M=14. Therefore, to obtain the same PTs>T value, the T value for M=14 is much larger than that for M=16,18,20, which means the calculation amount of M=14 will be significantly larger than that of M=16,18,20. For example, to guarantee PTs>T<0.5%, T should take 30 for M=14 and less than 10 for M=16,18,20. The total calculation amount for M=14 will be more than 2 times that for M=16,18,20. Therefore, M=14 should be excluded. Moreover, comparing M=20 with M=18 and M=16, the calculation amount increases are 11.1% and 25.0%, respectively, at a given T value, while the PTs>T decreases are 30%∼60% and 30%∼80%, respectively. The PTs>T decrease is larger than the calculation amount increase. Then, M is set as 20.Figure 6
PTs>T for M = 14, 16, 18, 20.Figure7 presents δPTs>T=PTs>T−PTs>T−1 for two adjacent T values. It can be seen that PTs>T obviously decreases with T addition when T≤8 because every additional generation significantly increases calculation amount and the PTs−T value slightly decreases with T>8. Then, T is set as 8.Figure 7
δPTs−T.


### 4.2.Pc and Pm Determination

The simulation conditions for searching the optimalPc and Pm are the same as those of the second simulation experiment in 4.1. Pc and Pm are searched in the interval from 0.1 to 0.9 with the step of 0.1. In Pc searching simulation, we set Pm=0.1, T=8, and M=20. For each Pc value, 24×6×2296=330624 times of GA-RANCO and LOS-RANCO are implemented. The PFI difference between GA-RANCO and LOS-RANCO (δPFI) for each Pc value is recorded in Figure 8:(21)PFI=NFINF,where NF is the times of algorithm executions when there exists faulty satellite, and NFI is the times of a faulty satellite being identified when it is really fault.Figure 8
δPFI with different Pc values.As seen in Figure8, δPFI reaches maximum at Pc=0.5. Then, Pc is set as 0.5.InPm searching simulation, we set Pc=0.5, T=8, and M=20. δPFI for each Pm value is recorded in Figure 9. As seen in Figure 9, the value of δPFI is positive during searching simulations and reaches maximum value at Pm=0.3, illustrating that the fault identification performance of GA-RANCO is better than that of LOS-RANCO. The reason is the MNS which has obvious inconsistency with a faulty satellite might be preexcluded for its poor geometry in LOS-RANCO. In other words, the LOS preexclusion decreases the fault identification performance of RANCO. It is observed that the faulty satellite may be successfully identified using GA-RANCO but misidentified using LOS-RANCO. Then, Pm is set as 0.3.Figure 9
δPFI with different Pm values.Finally, GA parameters are determined to beT=8, M=20, Pc=0.5, and Pm=0.3. Because these parameters are determined under single constellation and specific pseudorange bias value, whether they are available for double constellations and all pseudorange bias values should be further verified.


## 4.1.T and M Determination

To ensure the same fault identification for GA-RANCO and LOS-RANCO, the executed termination condition of GA-RANCO inM and T determining simulation is as follows:(19)maxfGAt−1fLOS<10−4,where maxfGAt is the maximum fitness in the tth generation of GA-RANCO and fLOS is the performance evaluation indicator for the final optimal MNS of LOS-RANCO. The parameter t satisfying the termination condition is recorded as Ts.Both the fault identification probability and the calculation amount should be considered. The GA-RANCO fault identification probability can be measured by the probability ofmaxfGAT−1/fLOS≥10−4, which means the probability of that the faulty satellites identified by GA-RANCO at genetic generation T are different from those identified by LOS-RANCO. To guarantee that GA-RANCO has equivalent fault detection and identification performance of LOS-RANCO, this probability should be as small as possible. The GA-RANCO calculation amount can be measured by the product of T and M, which presents the times of fitness calculation. This product should be as small as possible.SettingPc=0.1 and Pm=0.1, two simulation experiments are designed to determine T and M.The first simulation is used to preliminary screen the suitableM. It is set at a given time epoch (2019-3-13 00:40:00 of UTC time). The Asia-Pacific area is divided into grids with a resolution of 1°. There are in total 111×81=8991 grid points. M is set from 6 to 26. For each M value, the Ts values of 8991 grid points are recorded in Figure 5.Figure 5
Ts for different M values.As seen in Figure5, the times of Ts value larger than 10 decrease with the increase of M, even being less than 6 for M being larger than 14, which is less than 0.1% of the total grid points. When M takes a value smaller than 14, T should be assigned a large value to guarantee the fault detection/identification probability, which will bring a large calculation amount. For example, T should be 60 for M=10 to ensure the probability of maxfGAT−1/fLOS≥10−4 being less than 0.1%. Moreover, with M being larger than 20, the times of that Ts taking a large value (larger than 10) basically keep constant, which means the probability of maxfGAT−1/fLOS≥10−4 keeps almost constant with T=10 and M≥20. Considering both fault detection/identification probability and calculation amount, M should be assigned a value between 14 and 20.The second simulation is to determine the optimal value ofT and M. It is set in a whole day (2019-3-13 00:00:00 to 2019-3-14 00:00:00 of UTC time) with the time step of 600 s. The Asia-Pacific area is divided into grids with a resolution of 2°. There are in total 56×41=2296 grid points. Both GA-RANCO and LOS-RANCO are implemented at each gird point and simulation epoch with M from 14 to 20. For each M value, there are 33062424×6×2296Ts values. The probability of Ts>T, denoted as PTs>T, is calculated, where T=2,3,⋯,40:(20)PTs>T=NTs>TN.In equation (20), NTs>T presents the times of Ts>T for each M value and N presents the total simulation times, N=330624. Actually, PTs>T=maxfGAT−1/fLOS≥10−4.As seen in Figure6, the PTs>T−T curves for M=14,16,18,20 are roughly arranged from high to low, which means PTs>T decreases with M addition at a given T value. The value of PTs>T sharply decreases at the beginning, and its decrease speed slows down gradually to about 0 with T addition. The curves for M=16,18,20 are very close, clearly separated from curve for M=14. Therefore, to obtain the same PTs>T value, the T value for M=14 is much larger than that for M=16,18,20, which means the calculation amount of M=14 will be significantly larger than that of M=16,18,20. For example, to guarantee PTs>T<0.5%, T should take 30 for M=14 and less than 10 for M=16,18,20. The total calculation amount for M=14 will be more than 2 times that for M=16,18,20. Therefore, M=14 should be excluded. Moreover, comparing M=20 with M=18 and M=16, the calculation amount increases are 11.1% and 25.0%, respectively, at a given T value, while the PTs>T decreases are 30%∼60% and 30%∼80%, respectively. The PTs>T decrease is larger than the calculation amount increase. Then, M is set as 20.Figure 6
PTs>T for M = 14, 16, 18, 20.Figure7 presents δPTs>T=PTs>T−PTs>T−1 for two adjacent T values. It can be seen that PTs>T obviously decreases with T addition when T≤8 because every additional generation significantly increases calculation amount and the PTs−T value slightly decreases with T>8. Then, T is set as 8.Figure 7
δPTs−T.


## 4.2.Pc and Pm Determination

The simulation conditions for searching the optimalPc and Pm are the same as those of the second simulation experiment in 4.1. Pc and Pm are searched in the interval from 0.1 to 0.9 with the step of 0.1. In Pc searching simulation, we set Pm=0.1, T=8, and M=20. For each Pc value, 24×6×2296=330624 times of GA-RANCO and LOS-RANCO are implemented. The PFI difference between GA-RANCO and LOS-RANCO (δPFI) for each Pc value is recorded in Figure 8:(21)PFI=NFINF,where NF is the times of algorithm executions when there exists faulty satellite, and NFI is the times of a faulty satellite being identified when it is really fault.Figure 8
δPFI with different Pc values.As seen in Figure8, δPFI reaches maximum at Pc=0.5. Then, Pc is set as 0.5.InPm searching simulation, we set Pc=0.5, T=8, and M=20. δPFI for each Pm value is recorded in Figure 9. As seen in Figure 9, the value of δPFI is positive during searching simulations and reaches maximum value at Pm=0.3, illustrating that the fault identification performance of GA-RANCO is better than that of LOS-RANCO. The reason is the MNS which has obvious inconsistency with a faulty satellite might be preexcluded for its poor geometry in LOS-RANCO. In other words, the LOS preexclusion decreases the fault identification performance of RANCO. It is observed that the faulty satellite may be successfully identified using GA-RANCO but misidentified using LOS-RANCO. Then, Pm is set as 0.3.Figure 9
δPFI with different Pm values.Finally, GA parameters are determined to beT=8, M=20, Pc=0.5, and Pm=0.3. Because these parameters are determined under single constellation and specific pseudorange bias value, whether they are available for double constellations and all pseudorange bias values should be further verified.


## 5. Simulation Experiments and Analysis

In this section, simulation experiments are designed to verify the superior performance of GA-RANCO. The simulation experiments are conducted under the simulation architecture in Figure4. The performance indicators are the probability of fault detection PFD, the probability of fault identification (PFI), and the time consumption of algorithm execution. The specific PFI calculation method can be seen in equation (21):(22)PFD=NFDNF,where NF represents the times of algorithm executions when there exists faulty satellite; NFD represents the times of fault being detected when there exists faulty satellite. PFD represents the entire navigation system and PFI represents the specific faulty satellite.These simulations are implemented in the Asia-Pacific area (55°S∼55°N, 70°E∼150°E). GPS and BDS are chosen to be the simulation constellations. The former is simulated as a 32-satellite constellation and the latter is simulated as a 14-satellite constellation (5GEO + 5IGSO + 4MEO). The prior probability of fault for each satellite is set asPsat=10−4 [15]. In simulations, the cause of satellite fault is not considered, and the fault satellite is presented by the pseudorange bias, which is directly added to pseudorange of the faulty satellite.


### 5.1. Simulation at a Given Location

This simulation is set at a given location (north latitude 39°, east longitude 116°, and height 0 m) and a given time epoch (2019-3-13 00:40:00 of UTC time) to verify the performance of GA-RANCO algorithm under different constellation numbers and with different pseudorange bias values.Table1 records 4 different kinds of scenarios in this simulation: single faulty satellite under single constellation, double faulty satellite under single constellation, single faulty satellite under double constellations, and double faulty satellites under double constellations. The visible satellite numbers of GPS and BDS are, respectively, 9 and 11. In each simulation scenario, the satellite fault is set as the step fault, bringing pseudorange bias from 1σ to 15σ. For each pseudorange bias, 105 times of simulation are executed. In each time of simulation, the pseudorange noise is randomly generated as shown in (18) and the pseudorange bias is directly added to the pseudorange of the assumed faulty satellite with a constant.Table 1
Simulation scenarios.
ScenarioConstellationFaulty satellite1BDSC022BDSC02 and C133BDS + GPSC024BDS + GPSC02 and G25Figures10–13, respectively, show PFD and PFI and the time consumption for GA-RANCO and LOS-RANCO under different scenarios. As shown in Figures 10–13, both PFD and PFI for GA-RANCO are almost the same as those for LOS-RANCO at each pseudorange bias value.Figure 10
Single faulty satellite under single constellation. (a)PFD, (b) PFI for C02, and (c) time consumption.
(a)(b)(c)Figure 11
Double faulty satellite under single constellation. (a)PFD, (b) time consumption, (c) PFI for C02, and (d) PFI for C13.
(a)(b)(c)(d)Figure 12
Single faulty satellite under double constellations. (a)PFD, (b) PFI for C02, and (c) time consumption.
(a)(b)(c)Figure 13
Double faulty satellites under double constellations. (a)PFD, (b) time consumption, (c) PFI for G25, and (d) PFI for C02.
(a)(b)(c)(d)As shown in Figures10(c) and 11(b), the time consumption of GA-RANCO and LOS-RANCO are almost the same under single faulty satellite fault and double faulty satellites; that is, the number of faulty satellites does not affect the RANCO calculation amount. Moreover, the time consumption of GA-RANCO is about 150 ms, much higher than that of LOS-RANCO about 35 ms. It indicates that the calculation amount of GA-RANCO is much higher than that of LOS-RANCO under one constellation with about 11 visible satellites in this specific simulation experiment. The reason is that at least 20×8+1=180 times of fitness calculation is implemented in GA-RANCO, while only 39 times of performance evaluation indicator calculation for MNS is implemented in LOS-RANCO for only 39 MNSs remained after poor geometry MNS preexclusion.As shown in Figures12(c) and 13(b), time consumption for GA-RANCO and LOS-RANCO is, respectively, about 750 ms and 1200–1450 ms. The time consumption for GA-RANCO is only about 50%–60% of that for LOS-RANCO under two constellations of about 20 visible satellites in this specific simulation experiment. The reason is that at least 20×8+1=180 times of fitness calculation is implemented in GA-RANCO, while 349 times of performance evaluation indicator calculation for MNS is implemented in LOS-RANCO for 349 MNSs remained after poor geometry MNS preexclusion.Comparing Figure12(c) with Figure 13(b), time consumption of GA-RANCO for double faulty satellites is the same as that for single faulty satellite under double constellations. However, the time consumption of LOS-RANCO for double faulty satellites is obviously less than that for single faulty satellite with pseudorange bias larger than 5σ. The reason is that the calculation amount for SSE with double outliers excluded is obviously less than that with single outlier excluded.As shown in Figures12(c), 13(b), 10(c), and 11(b), time consumption of GA-RANCO for double constellations is much larger than that for single constellation with the same genetic generation and population chromosome number. The time consumption increases from single to double constellation are caused by the gene code addition from 4 to 5 of GA-RANCO, which significantly increases the amount of matrix operations during fitness calculation.This simulation experiment illustrates that bothPFD and PFI of GA-RANCO are the same as those of the LOS-RANCO for different pseudorange bias values under single or double constellations. The parameters of GA-RANCO, T=8, M=20, Pc=0.5, and Pm=0.3, are available for double constellations and all pseudorange bias values. The calculation amount of GA-RANCO is much larger than that of LOS-RANCO for single constellation with 11 visible satellites while it is much smaller than that of LOS-RANCO for double constellations with 20 visible satellites.


### 5.2. Simulation in Asia-Pacific Area

Another simulation is designed to further verify the performance of GA-RANCO. This simulation is set in Asia-Pacific area (55°S∼55°N, 70°E∼150°E), divided into grids with a resolution of 2°. The simulation starts at 2019-3-13 00:00:00 of UTC time and lasts 4 hours with the step of 300 s. At each grid point and simulation epoch, both GA-RANCO and LOS-RANCO are implemented. During simulation, the number of visible satellites is 7∼15 for single constellation while being 16∼28 for double constellations with the masking angle of 5°. According to (12) and (13), Nsat,max is set to be 2 for the number of visible satellites from 7 to 28.Table2 records two different kinds of simulation scenarios. The bias added to pseudorange for each faulty satellite is 8σ, where σ represents the standard deviation of pseudorange noise for its corresponding satellite. At each gird point, the pseudorange noise is randomly generated for each visible satellite. And the pseudorange bias is directly added to the pseudorange of the assumed faulty satellite with a constant (8σ).Table 2
Simulation scenarios in Asia-Pacific area.
ScenarioConstellationFaulty satellite1GPSG252BDS + GPSC02 and G25Figures14 and 15, respectively, present PFD and PFI under two scenarios. As shown in Figures 14 and 15, both PFD and PFI of GA-RANCO are similar to those of LOS-RANCO.Figure 14
PFD and PFI of single faulty satellite under single constellation. (a) PFD and (b) PFI.
(a)(b)Figure 15
PFI of two faulty satellites under double constellations. (a) PFD, (b) PFI for G25, and (c) PFI for C02.
(a)(b)(c)Figures16(a) and 16(b), respectively, present the average time consumptions of GA-RANCO and LOS-RANCO for different visible satellite numbers under single constellation and double constellations. With the visible satellite number addition, the GA-RANCO time consumption is linearly increased while the LOS-RANCO time consumption is exponentially increased.Figure 16
Time consumption under single constellation and double constellations. (a) Under single constellation and (b) under double constellations.
(a)(b)As shown in Figure16(a), the time consumption of GA-RANCO is much larger than that of LOS-RANCO at the beginning. Then, the time consumption difference between GA-RANCO and LOS-RANCO gradually shrinks with visible satellite number addition. The time consumption of LOS-RANCO exceeds that of GA-RANCO when the visible satellite number arrives 12. And then the time consumption difference between LOS-RANCO and GA-RANCO gradually expanded with visible satellite number addition. Particularly, when the visible satellite number increases to 15, the time consumption of LOS-RANCO is expanded more than 3 times that of GA-RANCO. Figure 16(a) illustrates that the computation efficiency of GA-RANCO would perform more excellent than that of LOS-RANCO when more than 11 visible satellites exist under single constellations.As seen in Figure16(b), the time consumption of GA-RANCO is larger than that of LOS-RANCO with no more than 16 visible satellites under two constellations. And the time consumption difference between GA-RANCO and LOS-RANCO increases with visible satellite addition. Figure 16(b) illustrates that the computation efficiency of GA-RANCO would far exceed that of LOS-RANCO when more than 16 visible satellites exist under double constellations.Comparing Figure16(a) with Figure 16(b), the time consumption of GA-RANCO is less than that of LOS-RANCO in single constellation with 13–15 visible satellites while being more than that of LOS-RANCO in double constellations with 16 visible satellites. There are two reasons. The first is the sudden increase of GA-RANCO calculation amount caused by the gene code addition from single constellation to double constellations. The second is the decrease of LOS-RANCO calculation amount caused by the MNS preexclusion because the LOS vectors of two satellites from two different constellations are more likely to be highly correlated compared with those from the same constellation.This simulation experiment confirms that with large number of visible satellites, more than 11 for single constellation and more than 16 for double constellations, GA-RANCO will be more suitable than LOS-RANCO for RAIM for its quite lower calculation amount and similar fault detection/identification probability with LOS-RANCO. Analyzing the simulation result, it can be deduced that the fault detection/identification probability of GA-RANCO will be equivalent to that of LOS-RANCO and the time consumption difference between GA-RANCO and LOS-RANCO will expand further for 3 or 4 GNSS constellations. However, because the calculated amount of GA-RANCO is linearly increased, its time consumption will also be very large. Therefore, both LOS-RANCO and GA-RANCO are not suitable for RAIM of 3 or 4 GNSS constellations. Further modification is needed for GA-RANCO to improve its computational efficiency again, making it available for 3 or 4 GNSS constellations.


## 5.1. Simulation at a Given Location

This simulation is set at a given location (north latitude 39°, east longitude 116°, and height 0 m) and a given time epoch (2019-3-13 00:40:00 of UTC time) to verify the performance of GA-RANCO algorithm under different constellation numbers and with different pseudorange bias values.Table1 records 4 different kinds of scenarios in this simulation: single faulty satellite under single constellation, double faulty satellite under single constellation, single faulty satellite under double constellations, and double faulty satellites under double constellations. The visible satellite numbers of GPS and BDS are, respectively, 9 and 11. In each simulation scenario, the satellite fault is set as the step fault, bringing pseudorange bias from 1σ to 15σ. For each pseudorange bias, 105 times of simulation are executed. In each time of simulation, the pseudorange noise is randomly generated as shown in (18) and the pseudorange bias is directly added to the pseudorange of the assumed faulty satellite with a constant.Table 1
Simulation scenarios.
ScenarioConstellationFaulty satellite1BDSC022BDSC02 and C133BDS + GPSC024BDS + GPSC02 and G25Figures10–13, respectively, show PFD and PFI and the time consumption for GA-RANCO and LOS-RANCO under different scenarios. As shown in Figures 10–13, both PFD and PFI for GA-RANCO are almost the same as those for LOS-RANCO at each pseudorange bias value.Figure 10
Single faulty satellite under single constellation. (a)PFD, (b) PFI for C02, and (c) time consumption.
(a)(b)(c)Figure 11
Double faulty satellite under single constellation. (a)PFD, (b) time consumption, (c) PFI for C02, and (d) PFI for C13.
(a)(b)(c)(d)Figure 12
Single faulty satellite under double constellations. (a)PFD, (b) PFI for C02, and (c) time consumption.
(a)(b)(c)Figure 13
Double faulty satellites under double constellations. (a)PFD, (b) time consumption, (c) PFI for G25, and (d) PFI for C02.
(a)(b)(c)(d)As shown in Figures10(c) and 11(b), the time consumption of GA-RANCO and LOS-RANCO are almost the same under single faulty satellite fault and double faulty satellites; that is, the number of faulty satellites does not affect the RANCO calculation amount. Moreover, the time consumption of GA-RANCO is about 150 ms, much higher than that of LOS-RANCO about 35 ms. It indicates that the calculation amount of GA-RANCO is much higher than that of LOS-RANCO under one constellation with about 11 visible satellites in this specific simulation experiment. The reason is that at least 20×8+1=180 times of fitness calculation is implemented in GA-RANCO, while only 39 times of performance evaluation indicator calculation for MNS is implemented in LOS-RANCO for only 39 MNSs remained after poor geometry MNS preexclusion.As shown in Figures12(c) and 13(b), time consumption for GA-RANCO and LOS-RANCO is, respectively, about 750 ms and 1200–1450 ms. The time consumption for GA-RANCO is only about 50%–60% of that for LOS-RANCO under two constellations of about 20 visible satellites in this specific simulation experiment. The reason is that at least 20×8+1=180 times of fitness calculation is implemented in GA-RANCO, while 349 times of performance evaluation indicator calculation for MNS is implemented in LOS-RANCO for 349 MNSs remained after poor geometry MNS preexclusion.Comparing Figure12(c) with Figure 13(b), time consumption of GA-RANCO for double faulty satellites is the same as that for single faulty satellite under double constellations. However, the time consumption of LOS-RANCO for double faulty satellites is obviously less than that for single faulty satellite with pseudorange bias larger than 5σ. The reason is that the calculation amount for SSE with double outliers excluded is obviously less than that with single outlier excluded.As shown in Figures12(c), 13(b), 10(c), and 11(b), time consumption of GA-RANCO for double constellations is much larger than that for single constellation with the same genetic generation and population chromosome number. The time consumption increases from single to double constellation are caused by the gene code addition from 4 to 5 of GA-RANCO, which significantly increases the amount of matrix operations during fitness calculation.This simulation experiment illustrates that bothPFD and PFI of GA-RANCO are the same as those of the LOS-RANCO for different pseudorange bias values under single or double constellations. The parameters of GA-RANCO, T=8, M=20, Pc=0.5, and Pm=0.3, are available for double constellations and all pseudorange bias values. The calculation amount of GA-RANCO is much larger than that of LOS-RANCO for single constellation with 11 visible satellites while it is much smaller than that of LOS-RANCO for double constellations with 20 visible satellites.


## 5.2. Simulation in Asia-Pacific Area

Another simulation is designed to further verify the performance of GA-RANCO. This simulation is set in Asia-Pacific area (55°S∼55°N, 70°E∼150°E), divided into grids with a resolution of 2°. The simulation starts at 2019-3-13 00:00:00 of UTC time and lasts 4 hours with the step of 300 s. At each grid point and simulation epoch, both GA-RANCO and LOS-RANCO are implemented. During simulation, the number of visible satellites is 7∼15 for single constellation while being 16∼28 for double constellations with the masking angle of 5°. According to (12) and (13), Nsat,max is set to be 2 for the number of visible satellites from 7 to 28.Table2 records two different kinds of simulation scenarios. The bias added to pseudorange for each faulty satellite is 8σ, where σ represents the standard deviation of pseudorange noise for its corresponding satellite. At each gird point, the pseudorange noise is randomly generated for each visible satellite. And the pseudorange bias is directly added to the pseudorange of the assumed faulty satellite with a constant (8σ).Table 2
Simulation scenarios in Asia-Pacific area.
ScenarioConstellationFaulty satellite1GPSG252BDS + GPSC02 and G25Figures14 and 15, respectively, present PFD and PFI under two scenarios. As shown in Figures 14 and 15, both PFD and PFI of GA-RANCO are similar to those of LOS-RANCO.Figure 14
PFD and PFI of single faulty satellite under single constellation. (a) PFD and (b) PFI.
(a)(b)Figure 15
PFI of two faulty satellites under double constellations. (a) PFD, (b) PFI for G25, and (c) PFI for C02.
(a)(b)(c)Figures16(a) and 16(b), respectively, present the average time consumptions of GA-RANCO and LOS-RANCO for different visible satellite numbers under single constellation and double constellations. With the visible satellite number addition, the GA-RANCO time consumption is linearly increased while the LOS-RANCO time consumption is exponentially increased.Figure 16
Time consumption under single constellation and double constellations. (a) Under single constellation and (b) under double constellations.
(a)(b)As shown in Figure16(a), the time consumption of GA-RANCO is much larger than that of LOS-RANCO at the beginning. Then, the time consumption difference between GA-RANCO and LOS-RANCO gradually shrinks with visible satellite number addition. The time consumption of LOS-RANCO exceeds that of GA-RANCO when the visible satellite number arrives 12. And then the time consumption difference between LOS-RANCO and GA-RANCO gradually expanded with visible satellite number addition. Particularly, when the visible satellite number increases to 15, the time consumption of LOS-RANCO is expanded more than 3 times that of GA-RANCO. Figure 16(a) illustrates that the computation efficiency of GA-RANCO would perform more excellent than that of LOS-RANCO when more than 11 visible satellites exist under single constellations.As seen in Figure16(b), the time consumption of GA-RANCO is larger than that of LOS-RANCO with no more than 16 visible satellites under two constellations. And the time consumption difference between GA-RANCO and LOS-RANCO increases with visible satellite addition. Figure 16(b) illustrates that the computation efficiency of GA-RANCO would far exceed that of LOS-RANCO when more than 16 visible satellites exist under double constellations.Comparing Figure16(a) with Figure 16(b), the time consumption of GA-RANCO is less than that of LOS-RANCO in single constellation with 13–15 visible satellites while being more than that of LOS-RANCO in double constellations with 16 visible satellites. There are two reasons. The first is the sudden increase of GA-RANCO calculation amount caused by the gene code addition from single constellation to double constellations. The second is the decrease of LOS-RANCO calculation amount caused by the MNS preexclusion because the LOS vectors of two satellites from two different constellations are more likely to be highly correlated compared with those from the same constellation.This simulation experiment confirms that with large number of visible satellites, more than 11 for single constellation and more than 16 for double constellations, GA-RANCO will be more suitable than LOS-RANCO for RAIM for its quite lower calculation amount and similar fault detection/identification probability with LOS-RANCO. Analyzing the simulation result, it can be deduced that the fault detection/identification probability of GA-RANCO will be equivalent to that of LOS-RANCO and the time consumption difference between GA-RANCO and LOS-RANCO will expand further for 3 or 4 GNSS constellations. However, because the calculated amount of GA-RANCO is linearly increased, its time consumption will also be very large. Therefore, both LOS-RANCO and GA-RANCO are not suitable for RAIM of 3 or 4 GNSS constellations. Further modification is needed for GA-RANCO to improve its computational efficiency again, making it available for 3 or 4 GNSS constellations.


## 6. Conclusions

In this paper, a modified RANCO algorithm based on GA (GA-RANCO) for RAIM was proposed to inhibit the exponential increasing calculation amount of RANCO algorithm under multiple GNSS constellations. The preselection step was developed to speed up the convergence process in GA-RANCO. The chromosome containing the gene code of a faulty satellite was excluded via preselection before the regular operation of GA in each generation. Simulation experiments illustrated that with considerable number of visible satellites, more than 11 for single constellation or more than 16 for double constellations, the GA-RANCO algorithm will be more suitable than LOS-RANCO RAIM algorithm for its lower calculation amount and similar faulty detection/identification probability.



---

*Source: 8969032-2020-06-22.xml*