改进的GNSS信号快速捕获检测算法

张超逸，曾丹丹，李金海，孙金海，阎跃鹏

(中国科学院 微电子研究所，北京 100029)

改进的GNSS信号快速捕获检测算法

张超逸，曾丹丹，李金海，孙金海，阎跃鹏

(中国科学院 微电子研究所，北京 100029)

为了满足卫星导航接收机在高动态应用场景中对卫星信号快速捕获的需求，本文针对全球导航卫星系统(global navigation satellite system，GNSS)信号的捕获检测问题提出了一种改进的检测算法。该算法结合了N中取M检测算法和唐检测算法的优点，考虑信号存在和不存在时的两种情况，通过设置多级门限检测机制，加快了信号存在时的检测确认速度和信号不存在时的剔除速度。实际数据测试表明，改进算法在检测概率没有任何损失的情况下，捕获检测速度相对于N中取M算法提高3倍，相对于唐检测算法提高1/3。

卫星导航接收机； 高动态； 快速捕获； 全球导航卫星系统；N中取M检测算法； 唐检测算法； 多门限检测； 捕获检测速度

全球卫星导航系统在各行各业中的应用日益广泛。导航接收机设计中首次定位时长是一个重要指标，捕获检测算法的性能对这一指标至关重要[1]。在高动态应用场景中，GNSS信号强度较高，但载体运动时间非常短，因此对接收机的首次定位时间，特别是有星历注入模式下的热启动时间要求非常高。而接收机准确快速地完成GNSS信号的捕获及后续检测是获得快速启动的关键因素。在实际接收机设计中，完成捕获搜索后，需要对捕获结果进行检测确认。由于单次检测结果的检测概率低且虚警概率高[2]，无法满足系统对卫星信号的捕获要求，因此需要进行多次检测以提高整体的信号检测概率，降低虚警概率。常见的捕获检测算法有N中取M检测算法和唐检测算法[2]。本文首先对这两种检测算法进行了分析说明；接着提出了一种改进的检测算法，结合N中取M检测算法和唐检测算法的优点，采用多门限判决机制，提高了检测速度。该检测算法在强信号条件下捕获检测速度快、性能好，适用于实时性要求较高，信号无遮挡且需要有较快捕获检测速度的高动态场景。

1 捕获检测算法分析

1.1N中取M检测算法

N中取M检测算法将信号与门限比较，大于门限则计数器J加1，小于门限J不变，每次比较计数器K减1。当K等于0时进行判决，若此时J不小于M则检测成功，否则检测失败。这里J初始值取0，K初始值取N。其算法流程如图1所示。

图1 N中取M检测算法流程Fig.1 M-of-N detection algorithm flow

图中Th为单次比较的门限值。可以看出N中取M检测算法是一种固定检测次数的检测器，其检测过程满足Bernoulli随机过程，超过门限的信号数目n具有二项式分布。N次试验的系统虚警概率[3]为

1-B(M-1,N,Pfa)

(1)

式中：Pfa为捕获检测的单次虚警概率，B是Bernoulli积分。N次试验的系统检测概率[3]为

1-B(M-1,N,Pd)

(2)

式中：Pd为单次检测概率。不同信噪比、N中取M检测算法的仿真结果如图2,算法性能如表1所示。

图2 N中取M检测算法仿真结果(N=8)Fig.2 Simulation results of M-of-N detection algorithm(N=8)

检测次数M(N=8)单次虚警概率/%信噪比/dB驻留平均数N30.267.6841.107.2852.867865.847.28

从图2和表1中可以看出M=5是最佳值,此时检测概率最高。该算法在系统检测概率达到90%，系统虚警概率等于10-6条件下，信号检测门限信噪比为7～8 dB。N中取M检测算法的缺点是不论信号强弱，检测驻留次数均为N次，导致检测速度非常慢。

1.2唐检测算法

唐检测算法将信号与门限比较，大于门限检测计数器K加1，小于门限检测计数器K减1；当K大于等于检测次数门限A时，认为信号存在；当K=0时认为信号不存在。这里K的初始值取B。其算法流程如图3所示。

图3 唐检测器检测算法流程Fig.3 Tong detection algorithm flow

图中Th为单次比较的门限值。可以看出唐检测算法是一种可变检测次数的检测器，其检测满足两个吸收壁的随机游动过程，系统虚警概率[4-5]为

(3)

系统检测概率[6-7]为

(4)

驻留次数的平均数目为[8]

(5)

唐检测算法的仿真结果如图4和表2所示。

表2 唐检测器检测性能

图4 唐检测器检测算法仿真结果Fig.4 Simulation results of Tong detection algorithm

从图4和表2中可以看出，A的增大提高了系统检测概率，降低了对信号信噪比的要求，但付出的代价是降低了搜索速度。因而A的选择是在搜索速度和检测概率之间的折中。唐检测算法的缺点是在特定的弱信号条件下，检测器会长时间滞留在某个捕获结果的检测确认过程中。

1.3改进的检测算法

基于上述两种算法，本文提出了一种改进算法，使得强信号尽早确认成功，不存在的卫星信号也能很快得到剔除。

首先根据不同的单次虚警概率，针对信号存在和不存在两种情况，设定相应的多个门限。一种实施方法如表3所示。在信号存在时设置5个门限用于确认，在信号不存在时设置2个门限用于剔除。

表3不同虚警概率对应的预设定门限示例

Table3Pre-setthresholdscorrespondingtothedifferentfalsealarmprobability

门限类型虚警概率/%门限信号存在时的检测门限信号不存在时的剔除门限1TH-E10.1TH-E20.01TH-E30.001TH-E40.0001TH-E51TH-NE110TH-NE2

然后将信号与各个门限依次进行比较，比较结果每大于信号存在时的5个门限中的1个，计数器J加1，当J不小于N时检测成功。比较结果每小于信号不存在时的2个门限中的1个，计数器K减1，当K=0时检测失败。其中J初始值取0，K初始值取L，算法流程如图5所示。

在强信号存在条件下，信号有极大概率可一次性大于所有的5个确认门限，满足J=N，实现单次驻留即检测成功，避免了N中取M算法中强信号依然需要检测N次的缺点。在弱信号存在条件下，信号仅大于少数较小的门限时，需要经过多次驻留检测后满足J不小于N时才检测成功，避免了唐检测算法中弱信号会导致计数器反复加减，长时间滞留的情况。在信号不存在的条件下，信号小于剔除门限时，会很快被剔除。综合上述3种情况，改进算法的检测速度会得到有效提升。

图5 改进检测算法流程图Fig.5 Improved detection algorithm flow

接收机天线接收到的卫星信号经过相关器解调、解扩和积分清零之后的I、Q两路1ms相干积分结果为

I=Asinc(ΔfmT)R(τ)Dcos(ΔΦ)+ni

(6)

Q=Asinc(ΔfmT)R(τ)Dsin(ΔΦ)+nq

(7)

单次非相干积分包络为

(8)

当信号不存在时，I与Q服从均值为0，方差为σ02的高斯分布。此时x为噪声的积分，服从Rayleigh分布[9]；x的均值与方差为

(9)

(10)

当信号存在时，x服从Rice分布[9]，其非中心参量为

(11)

此时x的均值与方差为

(12)

D(x/H1)=N(2σ02+s2)-[E(x/H1)]2

(13)

式中：H0、H1分别表示信号不存在和存在两种情况；I0、I1分别为零阶和一阶贝塞尔函数；γ1=s2/(2Nσ02)。

经过M次非相干积分之后可以得到检测量y：

(14)

由中心极限定理可知，当非相干积分时间很大时，非相干积分累加值服从高斯分布，可以用高斯分布进行近似求解[9]。

y的均值与方差分别为

E(y)=M·E(x)

(15)

D(y)=M·D(x)

(16)

根据高斯分布积分函数可以求出虚警概率为

(17)

式中：erfc(x)表示互补误差函数。根据已知的虚警概率，可以求得相应的门限值：

(18)

式中：erfc-1(x)表示互补误差函数的逆函数。根据高斯分布积分函数可以求出检测概率为

(19)

由于设置了多个判决门限，导致系统虚警概率和检测概率难以获得解析解，因此在下一节将采用蒙特卡洛方法分析算法的性能。

2 检测算法测试结果

2.1测试数据与方法

测试数据由思博伦GSS 9000信号模拟器产生，使用思博伦GSS 6425记录回放系统采集所需不同信号强度的中频数据。

使用测试数据对上文提到的3种检测确认算法进行测试。考虑不同算法参数、码相位初始偏差和多普勒频率初始偏差对检测算法测试结果的影响。本文采用的捕获引擎其捕获结果码相位偏差最大为半个码片，多普勒频率偏差最大为200 Hz。

对同一中频数据进行分析，具体的测试方法为：首先考虑不同码相位偏差对测试结果的影响，通过采样点偏移来模拟码相位偏差，即每次略过不同的起始采样点进行多次测试。本文中频采样率取16.368 MHz，半码片速率2.046 MHz，即8个采样点对应1.5码片偏差。在测试时，采用从起始偏移1个采样点直到偏移8个采样点来进行测试，这样可以完全覆盖一个半码片的偏差。然后考虑多普勒偏差的影响，在获取该中频信号某颗卫星的真实多普勒值后，在该值上增加或减少某个固定频率值来模拟不同多普勒偏差对测试造成的影响。最后，每次仿真的数据量需要满足蒙特卡洛的测试要求，如要达到0.01的准确率，仿真的个数至少需要104量级。

测试捕获检测性能时，为了体现检测算法的性能，这里将捕获检测分为二级检测，第一级采用最大值检测[10]：对码相位和频率进行二维捕获，得到的捕获结果取最大值与门限比较进行一级检测。捕获第二级检测则采用检测算法进行判断，这里主要对本文提到的三种检测算法进行比较分析。从检测算法的参数、初始多普勒偏差的影响、信号存在和信号不存在时的检测概率、虚警概率和捕获速度，不同信号强度和不同积分时间的影响这几方面进行测试和验证。

2.2不同检测算法参数的选择

表4给出了一组不同参数下的测试结果，用于测试不同参数下的检测算法性能。测试条件为：数据信号强度-126 dBm，捕获积分策略为2 ms相干积分，1次非相干积分。

表4 不同算法参数下的检测结果

由表4可以看出：

1)唐检测器B=2时的检测性能要优于B=1时的性能，这是因为B=1时，很容易产生漏警。

2)唐检测器B=2时，A越小，对应的检测速度越快，且与A较大时的检测概率基本一致。从性能上来看B=2，A=5性能最优且检测速度最快。

3)改进算法中L=3要优于L=1，检测概率较高。

4)由测试结果可看出，改进检测算法性能最优，一方面检测概率高，另一方面检测速度快。

此外，采用了不同信号强度的数据进行了对比验证，结果与-126 dB·m信号结果的一致性良好。

充灌程序采用自下至上的充灌方法，模袋在充灌进混凝土后，模袋布会出现膨胀拉紧，此时需调整上口边固定槽钢的拉紧葫芦，做好张力放松工作，以防模袋灌注不饱满。整块袋布灌注结束后，取出固定钢管，清洗泵车及管道。

为了使3种检测算法有可比性，在上述结果中挑选各个算法性能最佳的参数：N中取M检测算法取N=8，M=5；唐检测算法取A=5，B=2；改进检测算法取N=5，L=3。

2.3信号存在时多普勒频偏对检测性能的影响

采用信号强度为-126 dB·m的信号，捕获积分策略采用2 ms相干积分，1次非相干积分进行检测，捕获最大值初级检测的检测概率为81.8%，测试结果如表5所示。

表5信号存在条件下不同多普勒偏差的测试结果

Table5TestresultsindifferentDopplerdeviationwhensignalsexist

检测算法多普勒偏差/Hz0125-70-200检测概率/%平均检测次数检测概率/%平均检测次数检测概率/%平均检测次数检测概率/%平均检测次数8中取599.888.0099.198.0099.828.0095.378.00唐检测算法99.922.8899.573.0099.832.9097.43.36改进算法99.942.0699.622.1399.882.1397.912.82

由表5可以看出：

1)二级检测中的3种检测算法，在不同多普勒偏差下，检测概率均达到95%以上，表明这几种检测算法均能满足捕获检测概率达到90%以上的要求。

2)随着多普勒偏差为0～-200 Hz，3种检测算法对应的检测概率均有下降，平均检测次数均有增加。

2.4信号不存在时的剔除速度

下面分析当信号不存在时，3种检测算法对应的性能。

当信号不存在时，对-128 dB·m数据采用2 ms相干积分，1次非相干积分策略，捕获不存在的卫星，得到的结果如表6所示。

表6 信号不存在条件下测试结果

从表6可以看到3种算法的虚警概率都为0，满足了系统虚警概率10-6的要求。在检测速度方面，改进算法在N=5，L=3条件下的剔除速度略优于唐检测，在L=2时明显更快。因此改进算法不仅可以应用到信号存在时的确认过程，同时也可以应用到信号不存在时的剔除过程，既能保证信号的检测概率和虚警概率，也能保证检测速度。

2.5不同信号强度下的算法性能测试

分两方面对检测算法性能进行测试，信号存在时的检测概率和信号不存在时的剔除概率。

首先分析信号存在时的检测结果，对应不同卫星信号强度，采用不同的积分策略，只捕获存在的卫星，测试结果如表7所示。其中检测条件一为：-131 dB·m,2×3积分策略，最大值检测概率为88.73%；条件二为：-131 dB·m,2×3积分策略，最大值检测概率为68.53%；条件三为：-133 dB·m,2×7积分策略，最大值检测概率为89.31%；条件四为：-134 dB·m,2×7积分策略，最大值检测概率为83.41%。从表7可以看出：

1)当捕获最大值检测一级检测的检测概率达到80%以上时，捕获检测确认二级检测的这几种检测算法对应的检测概率均达到99%；当最大值检测一级检测的检测概率下降到70%时，捕获检测确认二级检测的检测概率仍能达到97%的性能。3种检测算法均满足需求。

2)从检测概率，漏检概率和虚警概率的性能来看，这几个检测算法基本一致，相差不大。但是改进算法平均检测次数最少，速度相对于N中取M能提高3倍，相对于唐检测算法能提高1/3。

接着分析不同信号强度下，信号不存在时的检测性能。测试时选择不存在的2号卫星进行捕获，结果如表8所示。从表8可以看到信号不存在时，针对不同信号强度，这几种检测算法都能准确的剔除。但改进算法的剔除速度最快，性能最优。

表7 不同信号强度下信号存在时的检测结果

表8 不同信号强度下信号不存在时的检测结果

3 结论

1)检测确认算法的二级检测受初始多普勒偏差影响，随着多普勒偏差的加大，对应检测算法的检测概率变小，平均检测次数增加。

2)不同信号强度下，当信号存在时，3种算法的检测概率基本相同且都满足系统要求，但是从平均检测次数来看，改进算法最优，速度相对于N中取M能提高3倍，相对于唐检测算法能提高1/3。当信号不存在时，3种算法的虚警概率都接近0,，满足系统要求，但改进算法的剔除速度略优于其他两种方法。说明改进的多门限检测判决不仅可应用到信号检测确认部分，同时也可应用到信号不存在时的剔除过程。

3)检测算法比较结论：在不同多普勒初始偏差和不同信号强度条件下，3种不同检测算法仿真结果说明，改进算法在检测概率虚警概率没有任何损失的情况下检测速度具有明显优势。

[1] 谢钢. GPS原理与接收机设计[M]. 北京：电子工业出版社, 2009: 358-362.

XIE Gang. Principles of GPS and receiver design[M]. Beijing: Publishing House of Electronics Industry, 2009: 358-362.

[2] KAPLAN E D, HEGARTY C J.GPS原理与应用[M]. 2版. 寇艳红译. 北京: 电子工业出版社, 2007: 223-227.

KAPLAN E D, HEGARTY C J. Understanding GPS principles and applications[M]. 2nd Ed. Beijing: Publishing House of Electronics Industry, 2007: 223-227.

[3] WARD P W. GPS receiver search techniques[C]//Proceedings of the IEEE 1996 Position, Location, and Navigation Symposium. Chicago, USA, 1996: 604-611.

[4] TONG P S. A suboptimum synchronization procedure for pseudo noise communication systems[C]//National Telecommunications Conference. Atlanta, USA, 1973: 26D-1-26D-5.

[5] 马琳, 崔嵬, 吴嗣亮. 极低信噪比环境下含近邻约束的改进唐检测判决算法[J]. 系统工程与电子技术, 2011, 33(8): 1745-1749.

MA Lin, CUI Wei, WU Siliang. Improved Tong multiple trial algorithm with near neighbor constraint in extremely low SNR condition[J]. Systems engineering and electronics, 2011, 33(8): 1745-1749.

[6] 马琳, 崔嵬, 田静,等. 基于马尔可夫链的含有检测次数约束条件的唐检测器[J]. 宇航学报, 2011, 32(8): 1799-1804.

MA Lin, CUI Wei, TIAN Jing, et al. Study on Tong detector with number of detection times constraint based on Markov chain[J]. Journal of astronautics, 2011, 32(8): 1799-1804.

[7] 朱云龙, 丑武胜, 杨东凯. Tong检测算法性能分析及参数设置[J]. 北京航空航天大学学报, 2015, 41(3): 418-423.

ZHU Yunlong, CHOU Wusheng, YANG Dongkai. Performance analysis and parameter setting for Tong detection algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(3): 418-423.

[8] 李思超，叶甜春，徐建华. 唐检测器的驻留时间及检测性能分析[J]. 电子测量技术, 2009, 34(3): 53-55.

LI Sichao, YE Tianchun, XU Jianhua. Analysis on resident time and detection performance of tong detector[J]. Electronic measurement technology, 2009, 34(3): 53-55.

[9] PROAKIS J G.数字通信[M]. 4版. 张力军译. 北京: 电子工业出版社, 2003: 29-31.

PROAKIS J G. Digital communications[M]. 4th Ed. Beijing: Publishing House of Electronics Industry, 2003: 29-31.

[10] 欧松林，李金海.GNSS系统中检测与判决的研究[J]. 计算机工程与设计, 2014, 35(3): 741-745.

OU Songlin, LI Jinhai. Study on detection and decision of GNSS system[J]. Computer engineering and design, 2014, 35(3): 741-745.

本文引用格式：张超逸，曾丹丹，李金海，等. 一种改进的GNSS信号快速捕获检测算法[J]. 哈尔滨工程大学学报， 2017， 38(10): 1609-1615.

ZHANG Chaoyi, ZENG Dandan, LI Jinhai, et al. An improved algorithm for rapid detection in acquisition of GNSS signal[J]. Journal of Harbin Engineering University， 2017， 38(10): 1609-1615.

ImprovedalgorithmforrapiddetectioninGNSSsignalacquisition

ZHANG Chaoyi, ZENG Dandan, LI Jinhai, SUN Jinhai, YAN Yuepeng

(Institute of Microelectronics， Chinese Academy of Sciences, Beijing 100029, China)

To ensure fast acquisition of satellite signals in high dynamic applications, an improved algorithm was proposed for signal detection during acquisition by global navigation satellite system. The algorithm combined the advantages of theM-of-Nand Tong detection algorithms. Through the multi-threshold detection mechanism, the detection and rejection speed accelerated whether the signals exist or not. Numerous real data tests show that the improved algorithm is three times faster than theM-of-Ndetection algorithm and one-third times faster than the Tong detection algorithm without any performance deterioration.

satellite navigation receiver; high dynamic; fast acquisition; GNSS;M-of-Ndetection algorithm; Tong detection algorithm; multi-threshold detection; detection speed in acquisition

10.11990/jheu.201605079

http://www.cnki.net/kcms/detail/23.1390.U.20170816.1445.010.html

TN911.23

A

1006-7043(2017)10-1609-07

2016-05-23. < class="emphasis_bold">网络出版日期

日期：2017-08-16.

国家自然科学基金项目(61271423).

张超逸(1990-), 男,博士研究生;阎跃鹏(1964-), 男,研究员,博士生导师.

张超逸，E-mail: zhangchaoyi@ime.ac.cn.