一种矩阵分块的GNSS相位模糊度快速解算方法

李克昭 朱国库

1 河南理工大学测绘与国土信息工程学院，河南省焦作市世纪路2001号，454003 2 北斗导航应用技术协同创新中心，郑州市科学大道62号，450001

在目前诸多GNSS定位模糊度求解方法中，以降相关思想为核心的LAMBDA算法应用最为广泛[1-2]。LAMBDA算法解算模糊度的步骤主要包括：模糊度降相关、模糊度搜索和模糊度检验。其中，模糊度降相关过程涉及大量矩阵运算，耗时较长。为此，学者们进行了大量研究：Chang等[3]和Borno等[4]分别利用贪心算法和部分元素降相关方法对LAMBDA算法进行改进；Liu等[5]通过上下三角过程构造联合去相关算法，降低模糊度之间的相关性；徐琦等[6]通过对比分析认为，联合去相关法的处理成功率高于迭代法；Xu[7]使用Cholesky分解构建整数高斯矩阵，结果表明，在高维情况下分解得到的浮点解协方差矩阵条件数最小；陈树新[8]以降低协方差矩阵的条件数为准则，提出一种性能更加优越的模糊度去相关算法；Liu等[9]通过三次差分测量得到模糊度浮动解，通过降低模糊度协方差矩阵的维数对搜索空间进行去相关处理，克服了Z变换可能带来的矩阵病态分解，减少了20%的解算时间。还有学者研究不同的排序算法对降相关性能的影响[10-14]。 Hassibi等[15]将格理论中的规约算法Lenstra-Lenstra-Lovász(LLL)应用于模糊度降相关的研究中，此后大量学者对LLL算法进行了详细研究与分析，并开展相应的改进和优化[16-22]。

综上可知，减少矩阵的复杂运算是提高降相关效率的重要手段之一。LAMBDA算法的模糊度降相关过程主要包括Cholesky分解和矩阵降相关2个步骤。其中，传统Cholesky分解过程复杂，会造成大量计算冗余；矩阵降相关过程主要为条件方差排序计算，每次排序计算都需要对非主对角元素进行降相关处理，涉及大量复杂运算。基于此，本文提出一种分块最小二乘模糊度降相关(BLAMBDA)算法：采用条件方差分块算法优化降相关过程，对条件方差矩阵进行分块，减少条件方差排序次数，并在此基础上对Cholesky分解公式进行整合，减少Cholesky分解过程中的数乘运算。

1 整数最小二乘去相关算法模型

(1)

式中，a为模糊度整数候选向量。

(2)

(3)

(4)

(5)

(6)

2 BLAMBDA算法求解整周模糊度

为满足式(4)，LAMBDA算法在条件方差交换时需按照从后往前的顺序排列。当遇到判别交换的条件方差dk和dk+1相差过大时，dk+1、dk+2及之前的交换过程可能不再满足条件，需要对其进行再次交换，此过程会发生大量重复交换的情况，并增加元素降相关的运算时间。基于此，本文对条件方差矩阵进行分块处理，使条件方差在块内交换，通过改变交换维数和方式来减少条件方差的交换次数，并对Cholesky分解过程进行优化处理，提出改进的LAMBDA算法。

首先，对式(5)LTDL分解中的D矩阵进行分块处理：

(7)

将n维矩阵D分成m块(R1,R2,…,Rm)，前(m-1)块的大小为k,Rm的大小为r=n-(m-1)k,r为不足分块大小的部分。任意分块Ri(1≤i≤m)和Rm可表示为：

(8)

(9)

BLAMBDA算法若不满足式(6)，则仅在各分块内进行交换。由于各分块的维数较低，因此在分块内更容易满足式(4)，使得各分块条件方差交换次数之和远小于LAMBDA算法降相关过程中条件方差的交换次数，减少了大量矩阵运算和高斯变换过程。以di和di+1进行一次条件方差交换为例，减少的计算过程公式推导如下：

(10)

令

(11)

则有：

(12)

在各分块内完成交换后，需要对相邻块进行条件方差交换，完成条件方差的块传递。相邻块条件方差交换条件为：

δ(d(i-1)k+1×d(i-1)k+2×…×dik)>

dik+1×dik+2×…×d(i+1)k

(13)

式中，δ为条件约束因子，其大小决定了相邻块是否需要使用相邻块传递的对称旋转策略[3]。

当相邻块不满足式(13)时，需要对Ri的第1个元素d(i-1)k+1和Ri+1的最后1个元素d(i+1)k进行交换。当Ri中的条件方差远小于Ri+1时，需使用一次对称旋转策略，此过程会使2分块内的条件方差大致按降序排列；否则仅对Ri和Ri+1的相邻元素dik和dik+1作比较交换处理，实现相邻块的交换传递。交换公式为：

(14)

(15)

虽然在块之间的传递过程中使用对称旋转策略会增加部分计算量，但该计算量远小于条件方差交换过程中减少的计算量。

为进一步减少BLAMBDA算法的矩阵运算耗时，对LAMBDA算法的分解算法进行优化，即(ModifyLTDL,MLTDL)。优化策略如下：

(16)

式中，

qn=dn，qT=lTdn，l=q/dn

(17)

Q=Q-lTdnl=LTDL

(18)

将式(17)代入式(18)中，得：

Q=Q-qTl=LTDL

(19)

从式(16)～(19)可以看出，该迭代过程中没有开平方根运算，且式(19)在式(18)的基础上减少了数乘运算。

3 实验验证与分析

本文利用MATLAB 2014构建算法的仿真实验平台，基于Visual Studio 2019 C语言进行实验的整体解算。计算机系统为Windows 10，处理器为8 GB内存的Intel(R) Core(TM) i7-8550U CPU@1.80 GHz 1.99 GHz。在实际解算过程中，基于RTKLIB进行基线解算，短基线的双差模糊度整体高于中长、长基线的双差模糊度。实测实验以代表性实测数据(长、中长、短基线)为例进行深入分析，具有更强的说服力。

3.1 仿真实验分析

仿真实验的方差协方差矩阵不依赖于特定卫星和接收机的几何构图及定权方式，能更全面地检验BLAMBDA算法。构造方法如下：

(20)

式中，randn(n,1)为随机函数生成的符合正态分布的n个随机数。

首先对2种LTDL分解方法进行仿真实验，仿真维数为6～40维。为避免偶然性，对每组仿真数据的2种分解方式各模拟100次，求取时间的平均值。图1为BLAMBDA算法中改进后的MLTDL分解算法与LAMBDA算法中LTDL分解算法的解算时间对比。

图1 2种分解算法的平均运行时间Fig.1 Average running time of two decomposition algorithms

为更直观地说明BLAMBDA算法能够减少条件方差交换次数，仅对条件方差矩阵进行分块处理，模拟方式与图1相同，实验结果如图2所示。BLAMBDA算法和LAMBDA算法整体降相关耗时对比如图3所示。

图2 2种算法条件方差交换次数对比Fig.2 Comparison of conditional variance switching times between two algorithms

图3 2种算法降相关耗时对比Fig.3 Time consumption of decorrelation of two algorithms

由图1可见，LTDL分解算法具有可行性，说明减少矩阵的数乘可以明显提高矩阵分解效率。由图2可见，相较于LAMBDA算法，BLAMBDA分块算法具有明显的优越性。由图3可见，总体上看，BLAMBDA算法在去相关耗时效率上优于LAMBDA算法。

3.2 实测实验

实测实验分为3组：1)短基线组采用1组和芯星通UB4B0-MINI板卡采集的静态观测数据，基线长89.83 m，采样间隔为1 s，截取3 000个历元进行实验分析； 2)中长基线组采用武汉大学IGS数据中心下载的香港地区HKSL和HKWS测站的IGS数据，2站构成的基线长度为42.51 km，采样间隔为30 s；3)长基线组采用武汉大学IGS数据中心下载的香港地区HKSL测站和上海SHAO测站的IGS数据，2站构成的基线长度为1 216.01 km，采样间隔为30 s。本文所使用的数据包括星历数据和观测数据，且均为标准RINEX格式。为保证实验的合理性，BLAMBDA算法和LAMBDA算法均采用SEVB搜索算法进行降相关处理[3]。本实验基于RTKLIB的源代码进行数据处理,实际解算过程中对2种算法的固定模糊度进行对比发现，二者结果一致性较高。本文提出的算法与RTKLIB源代码中的LAMBDA算法具有一致性，在此基础上采用GPS、BDS、Galileo、GLONASS等多系统数据进行整周模糊度融合解算，3种基线解算时间对比情况如图4所示，耗时概率分布如图5所示。

图4 3种基线解算时间对比Fig.4 Comparison of three baseline calculation time

图5 3种基线解算时间耗时概率对比分布Fig.5 Probability distribution of three baseline calculation time

由图4可见，BLAMBDA算法的解算时间明显短于LAMBDA算法。由于中长、长基线的采样间隔为30 s，而短基线的时间间隔为1 s，中长、长基线的观测时间长于短基线，因此图4(a)的时间波动比图4(b)、(c)的平缓。此外，短基线的双差模糊度维数整体高于中长、长基线，双差模糊度维数越高，BLAMBDA算法对时间效率的提升越明显。

由图5(a)可见，LAMBDA算法在0.021～0.035 s内的解算耗时概率明显高于BLAMBDA算法，BLAMBDA算法的解算耗时大都集中在0.020 s左右；由图5(b)、(c)可见，中长基线和长基线的BLAMBDA算法解算耗时与LAMBDA算法相比方差较小，解算耗时分布更加集中。LAMBDA算法存在高耗时的现象，而BLAMBDA算法在某种程度上弥补了这一缺陷。由此可以看出，BLAMBDA算法不仅在解算效率上优于LAMBDA算法，而且具有更好的稳定性。

4 结 语

为解决LAMBDA算法模糊度去相关过程计算量过大的问题，引入条件方差矩阵分块方法，并对分解算法进行改进，提出BLAMBDA算法。仿真与实测实验结果表明，BLAMBDA算法求解模糊度的整体效率高于LAMBDA算法。各历元解算耗时大小的概率分布表明，BLAMBDA算法的计算稳定性优于LAMBDA算法。

在BLAMBDA算法中，对条件方差矩阵进行分块处理，可以进一步提高模糊度的解算效率，这将是BLAMBDA算法下一步的研究重点。