A DBSCAN-based RAIM algorithm for multiple gross error identification

doi:10.11947/j.AGCS.2026.20250033

Abstract

Abstract:

With the widespread application of GNSS in safety-critical fields such as aviation and maritime navigation, receiver autonomous integrity monitoring (RAIM) technology is crucial for ensuring navigation reliability. To address the limitations of existing RAIM algorithms, namely insufficient detection capability and low computational efficiency when multiple satellites fail simultaneously, this paper proposes a novel RAIM algorithm for multiple gross error identification based on density-based spatial clustering of applications with noise (DBSCAN). The algorithm first constructs observation samples via parity checks, calculates inter-sample distances to highlight anomalies, and then employs DBSCAN clustering to adaptively identify and isolate multiple gross errors based on data density distribution. Simulations and real-world experiments demonstrate that: ① In simulated shipborne scenarios with 50 m and 100 m pseudorange gross errors across three satellites, the proposed algorithm improves positioning accuracy by approximately 82.8%and 92.1%, and computational efficiency by about 96.2%and 96.1%, respectively, compared to the traditional least squares residuals (LSR) method；② In simulated high-dynamic airborne scenarios, the algorithm＇s detection rate for gross errors ranging from 5 m to 100 m increases consistently from 52.9%to 100%, while positioning error remains stable；③ Using real data from an IGS station, the algorithm significantly reduces the horizontal and three-dimensional errors from 8.61 and 9.94 m (with LSR RAIM) to 0.77 and 1.08 m；④ In urban vehicular field tests, the algorithm achieves positioning accuracy comparable to the random sample consensus (RANSAC) RAIM algorithm, but with a computational efficiency improvement exceeding 94.7%. The proposed algorithm significantly enhances multiple gross error identification capability while maintaining high computational efficiency, providing an effective solution for high-reliability navigation and positioning in complex environments.

Key words: GNSS, receiver autonomous integrity monitoring, density-based spatial clustering of applications with noise, multiple gross error identification, computational efficiency, navigation reliability

CLC Number:

P228

Deying YU, Houpu LI, Yi LIU, Shuguang WU, Deyan LI, Mingchao LI, Wenkui LI, Shaofeng BIAN. A DBSCAN-based RAIM algorithm for multiple gross error identification[J]. Acta Geodaetica et Cartographica Sinica, 2026, 55(1): 59-72.

Figures/Tables 15

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Tab. 1

Tab. 2

Fig. 7

Tab. 3

Fig. 8

Tab. 4

Fig. 9

Fig. 10

Fig. 11

References 32

[1]	徐肖豪, 杨传森, 刘瑞华. GNSS用户端自主完好性监测研究综述[J]. 航空学报, 2013, 34(3): 451-463.
	XU Xiaohao, YANG Chuansen, LIU Ruihua. Review and prospect of GNSS receiver autonomous integrity monitoring[J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(3): 451-463.
[2]	YANG Yuanxi, XU Junyi. GNSS receiver autonomous integrity monitoring (RAIM) algorithm based on robust estimation[J]. Geodesy and Geodynamics, 2016, 7(2): 117-123.
[3]	宁津生, 姚宜斌, 张小红. 全球导航卫星系统发展综述[J]. 导航定位学报, 2013, 1(1): 3-8.
	NING Jinsheng, YAO Yibin, ZHANG Xiaohong. Review of the development of global satellite navigation system[J]. Journal of Navigation and Positioning, 2013, 1(1): 3-8.
[4]	MONTENBRUCK O, STEIGENBERGER P, PRANGE L, et al. The multi-GNSS experiment (MGEX) of the international GNSS service (IGS)-achievements, prospects and challenges[J]. Advances in Space Research, 2017, 59(7): 1671-1697.
[5]	赵昂, 杨元喜, 许扬胤, 等. GNSS单系统及多系统组合完好性分析[J]. 武汉大学学报(信息科学版), 2020, 45(1): 72-80.
	ZHAO Ang, YANG Yuanxi, XU Yangyin, et al. Integrity analysis of GNSS single system and multi-system combination[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 72-80.
[6]	PARKINSON B W, AXELRAD P. Autonomous GPS integrity monitoring using the pseudorange residual[J]. Navigation, 1988, 35(2): 255-274.
[7]	STURZA M A. Navigation system integrity monitoring using redundant measurements[J]. Navigation, 1988, 35(4): 483-501.
[8]	BLANCH J, WALTER T, ENGE P. RAIM with optimal integrity and continuity allocations under multiple failures[J]. IEEE Transactions on Aerospace and Electronic Systems, 2010, 46(3): 1235-1247.
[9]	LI Liang, WANG Huan, JIA Chun, et al. Integrity and continuity allocation for the RAIM with multiple constellations[J]. GPS Solutions, 2017, 21(4): 1503-1513.
[10]	ZHAI Yawei, JOERGER M, PERVAN B. Fault exclusion in multi-constellation global navigation satellite systems[J]. Journal of Navigation, 2018, 71(6): 1281-1298.
[11]	EL-MOWAFY A, IMPARATO D, RIZOS C, et al. On hypothesis testing in RAIM algorithms: generalized likelihood ratio test, solution separation test and a possible alternative[J]. Measurement Science and Technology, 2019, 30(7): 075001.
[12]	张倩倩, 归庆明, 宫轶松. 卫星多故障探测和识别的独立分量分析法[J]. 测绘学报, 2017, 46(6): 698-705. DOI: . doi: 10.11947/j.AGCS.2017.20160079
	ZHANG Qianqian, GUI Qingming, GONG Yisong. Multiple satellite faults detection and identification based on the independent component analysis[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6): 698-705. DOI: . doi: 10.11947/j.AGCS.2017.20160079
[13]	刘一, 谷守周, 边少锋, 等. 一种基于观测数据集密度中心的新型RAIM算法[J]. 武汉大学学报(信息科学版), 2021, 46(12): 1900-1906.
	LIU Yi, GU Shouzhou, BIAN Shaofeng, et al. A new RAIM algorithm based on the density center of observed dataset[J]. Geomatics and Information Science of Wuhan University, 2021, 46(12): 1900-1906.
[14]	武明, 许承东, 黄国限, 等. 概率神经网络多历元残差RAIM算法[J]. 系统工程与电子技术, 2023, 45(12): 3967-3974.
	WU Ming, XU Chengdong, HUANG Guoxian, et al. Probabilistic neural network multi-epoch residual RAIM algorithm[J]. Systems Engineering and Electronics, 2023, 45(12): 3967-3974.
[15]	GE Yishan, WANG Zhipeng, ZHU Yanbo. Reduced ARAIM monitoring subset method based on satellites in different orbital planes[J]. GPS Solutions, 2017, 21(4): 1443-1456.
[16]	ZHANG Yabin, WANG Li, FAN Lihong, et al. MHSS ARAIM algorithm combined with gross error detection[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(1): 36-44.
[17]	GAO Yuting, GAO Yang, LIU Baoyu, et al. Enhanced fault detection and exclusion based on Kalman filter with colored measurement noise and application to RTK[J]. GPS Solutions, 2021, 25(3): 82.
[18]	GAO Zhen, ZHAN Xingqun, YANG Rong. An improved detection method of GNSS faults with fractional information divergence[J]. Advances in Space Research, 2023, 72(10): 4229-4243.
[19]	WANG Shizhuang, ZHAI Yawei, CHI Cheng, et al. Implementation and analysis of fault grouping for multi-constellation advanced RAIM[J]. Advances in Space Research, 2023, 71(11): 4765-4786.
[20]	HUANG Guoxian, XU Chengdong, ZHENG Xueen. Sequential advanced receiver autonomous integrity monitoring method considering the optimal sample size[J]. Advances in Space Research, 2023, 71(10): 4173-4184.
[21]	ANGRISANO A, GAGLIONE S, CROCETTO N, et al. PANG-NAV: a tool for processing GNSS measurements in SPP, including RAIM functionality[J]. GPS Solutions, 2019, 24(1): 19.
[22]	TITOUNI S, ROUABAH K, ATIA S, et al. Spectral transformation-based technique for reducing effect of limited pre-correlation bandwidth in the GNSS receiver filter in presence of noise and multipath[J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 252-265.
[23]	DUENAS ARANA G, ABDUL HAFEZ O, JOERGER M, et al. Integrity monitoring for Kalman filter-based localization[J]. The International Journal of Robotics Research, 2020, 39(13): 1503-1524.
[24]	JIANG Chen, ZHANG Shubi, CAO Yizhi, et al. A robust fault detection algorithm for the GNSS/INS integrated navigation systems[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(1): 12-24.
[25]	BHATTACHARYYA S. A computationally efficient Kalman filter-based RAIM algorithm for aircraft navigation with GPS and NavIC[J]. Measurement Science and Technology, 2023, 34(12): 125106.
[26]	WU Qi'an. A two-fault detection and elimination approach to the receiver autonomous integrity monitoring[J]. GPS Solutions, 2024, 28(4): 160.
[27]	WEN Yaxin, DAI Wujiao, YU Wenkun, et al. Mitigation of multiple outliers using consistency checking for GNSS standard point positioning in urban areas[J]. Advances in Space Research, 2024, 73(3): 1721-1733.
[28]	李瑞杰, 李亮, 蒋家昌, 等. 基于多星最差故障搜索的RAIM完好性风险估计方法[J]. 航空学报, 2024, 45(2): 247-261.
	LI Ruijie, LI Liang, JIANG Jiachang, et al. RAIM integrity risk estimation method based on worst multi-satellite faults searching[J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(2): 247-261.
[29]	ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: ACM Press, 1996: 226-231.
[30]	ALSAHFI T. Spatial and temporal analysis of road traffic accidents in major Californian cities using a geographic information system[J]. ISPRS International Journal of Geo-Information, 2024, 13(5): 157.
[31]	RINNE T, SAEED M, SERNA-GUERRERO R. Quantifying the degree of selectivity in a flocculation-flotation process of LiCoO2 and graphite using scanning electron microscopy and image processing analysis[J]. Minerals Engineering, 2024, 209: 108644.
[32]	SONG Chenyu, CUI Jingyuan, CUI Yafei, et al. Integrated STL-DBSCAN algorithm for online hydrological and water quality monitoring data cleaning[J]. Environmental Modelling & Software, 2025, 183: 106262.

系统	伪距粗差	RAIM算法	X		Y		Z
系统	伪距粗差	RAIM算法	RMS	STD	RMS	STD	RMS	STD
GPS/Galileo	50	LSR	15.52	3.37	13.40	7.48	3.20	2.99
		RANSAC	3.53	3.53	2.46	2.46	2.05	2.05
		DBSCAN	3.56	3.55	2.54	2.53	2.03	2.03
	100	LSR	30.68	3.71	28.63	12.31	5.37	4.23
		RANSAC	3.64	3.64	2.45	2.45	1.92	1.92
		DBSCAN	3.64	3.64	2.45	2.45	1.92	1.92
GPS/Galileo/BDS	50	LSR	14.19	3.64	25.93	2.35	14.49	2.34
		RANSAC	3.55	3.55	2.69	2.69	2.19	2.19
		DBSCAN	4.69	4.63	4.75	4.68	2.65	2.65
	100	LSR	27.33	3.55	51.95	2.28	29.06	2.41
		RANSAC	3.59	3.59	2.70	2.70	2.14	2.14
		DBSCAN	3.59	3.59	2.70	2.70	2.14	2.14

系统	伪距粗差/m	运行耗时/s			DBSCAN RAIM效率提升/（%）
系统	伪距粗差/m	LSR RAIM	RANSAC RAIM	DBSCAN RAIM	LSR RAIM	RANSAC RAIM
GPS/Galileo	50	0.626 9	5.707 3	0.371 4	40.75	93.49
GPS/Galileo	100	0.830 4	7.552 7	0.484 6	41.64	93.58
GPS/Galileo/BDS	50	1.044 1	9.496 3	0.606 5	41.91	93.61
GPS/Galileo/BDS	100	1.248 6	11.354 7	0.720 3	42.32	93.66

伪距粗差/m	RAIM算法	识别率/（%）	误检率/（%）	漏检率/（%）	F₁值
5	LSR	0	0	100	0
5	DBSCAN	52.87	18.17	47.13	0.46
10	LSR	28.21	1.18	71.79	0.42
10	DBSCAN	72.90	8.27	27.10	0.70
50	LSR	33.33	0	66.67	0.50
50	DBSCAN	99.92	0.02	0.08	1
100	LSR	33.33	0	66.67	0.50
100	DBSCAN	100	0	0	1

伪距粗差	RAIM算法	X		Y		Z
伪距粗差	RAIM算法	RMS	STD	RMS	STD	RMS	STD
5	LSR	4.49	3.21	3.35	2.06	2.34	1.96
5	DBSCAN	4.42	4.08	3.20	2.64	2.57	2.38
10	LSR	7.06	3.53	5.70	2.12	3.11	1.84
10	DBSCAN	4.92	4.34	4.14	3.16	2.84	2.46
50	LSR	14.48	3.64	25.74	2.26	15.12	2.08
50	DBSCAN	3.89	3.89	2.86	2.86	2.20	2.21
100	LSR	28.28	3.53	51.21	2.17	30.37	2.05
100	DBSCAN	3.71	3.71	2.63	2.63	2.14	2.14