2. 武汉市测绘研究院， 湖北 武汉 430022
2. Wuhan Institute of Surveying and Mapping, Wuhan 430022, China
、
相位整周模糊度的快速准确确定是GNSS研究领域内的难点，也是热点问题之一。针对模糊度问题进行解算的方法可分为3大类：观测值域、模糊度域以及坐标域内的解算。其中以模糊度域内的LAMBDA解算方法最为流行且被广泛采用，其核心思想是通过降低模糊度方差分量之间的相关性来实现对超椭球的压缩以减少搜索候选点数，从而提高解算效率[1, 2]。随后，多位学者基于这个原则先后提出了各自的降相关算法[3, 4, 5, 6, 7, 8, 9]。
由于模糊度解算是一个整数最小二乘问题，实质上等价于格理论中的最近向量问题，因此可按照格基规约的方法进行解算，其中以LLL规约算法[10]为代表的格基规约方法已被多位学者应用于整周模糊度的解算中[11, 12, 13, 14, 15, 16, 17]。文献[18]对规约和降相关之间的等价性进行了理论证明，文献[19]进一步对LLL规约算法和LAMBDA之间的等价性进行了理论证明，表明规约和降相关两者是统一的。因此对降相关性能与搜索效率之间关系的研究也等同于对规约效果与搜索效率二者相互关系的研究。
一般认为实现最大限度地降低模糊度方差阵的相关性和压缩搜索椭球可提高搜索效率，因而常采用条件数和降相关系数等作为衡量降相关性能的指标。但文献[11]指出条件数不能用作评价搜索效率的指标；文献[12]进一步指出正交缺陷度不能用作评价搜索效率的指标。文献[13]从理论上证明了单纯降低方差分量间的相关性和条件数的数值大小并不能减少搜索候选点数。鉴于此，本文对降相关系数、条件数、正交缺陷度、S(A)等常见的降相关(规约)评价指标进行研究分析，并根据所代表的几何意义进行分类归纳。在此基础上采用Seysen规约算法与经典的LAMBDA算法和LLL规约算法的解算结果进行对比，进一步验证搜索效率与不同指标间的关系，从而对不同的降相关效果是否与模糊度的解算效率存在直接关系进行系统探讨，以期为相关研究提供参考。 1 基本原理 1.1 整数最小二乘模型
假定、
分别为实数模糊度和模糊度的方差-协方差阵，对其进行最小二乘模糊度整数估计，估计准则为[1]
对进行Cholesky分解
将式(2)代入式(1)可得
式中，
是一个常数。式(3)在格理论上也被称为最近向量问题。
通常采用整数变换矩阵Z来降低中方差分量之间的相关性来提高式(1)中模糊度的搜索效率。为验证降相关性能是否与搜索效率存在直接关系，本文引入了Seysen规约算法，进行对比分析。
1.2 Seysen规约算法
Seysen规约算法是同时对原始基和对偶基进行规约，但不涉及基向量交换的一种规约方法[20]。其具体原理如下：
假设上三角矩阵B可以看作格L的一组基向量(b1,b2,…,bn)，其对偶基向量为B*=(b*1,b*2,…,b*n)，则存在下列关系
对于一对基向量(bi,bj)，bj对bi的尺度规约有b′j=bj+λbi,λ∈Z，其中λ可以被视为它们之间的相关系数，则对偶基具备下列规约条件
式中，
。
Seysen算法采用式(6)来辅助进行规约
在其规约过程中每一次迭代都要对所有基向量及其相应的对偶基同时进行规约，直到式(6)中的S(A)值不再减小。具体实现过程可参照文献[20—21]。
2 降相关性能的评价指标及其几何意义分析
当对方差-协方差阵整数转换后，可以采用一定的指标对降相关(规约)效果进行评价。目前，模糊度解算常用的定量评价指标主要有条件数κ、降相关系数γ；在格基规约算法中，一般采用正交缺陷度δ、S(A)评价基向量之间的相关性。由于一般认为模糊度的搜索效果取决于降相关程度的好坏，因而以上指标常被用来评价模糊度的搜索效率。下面通过分析它们之间内在的关系及几何含义，为后续验证做好准备工作。
2.1 降相关系数γ和正交缺陷度δ的等价性证明
降相关系数[2]主要用于衡量方差分量之间的相关性，可以表述为
式中，
为整数转换后的方差协方差矩阵；[zii]=diag()。正交缺陷度δ[22]用于衡量基向量之间的正交性，可以表述为
式中，B为进行规约后的上三角矩阵，bi为B的第i个列向量。
由式(2)知，方差分量和规约基之间具有直接的关联性。根据这个关系，笔者对γ和δ之间的等价性进行证明。
证明：
Q =BTB⇒det(B)2=det(Q )
根据Hadamard不等式
，当为对角阵时，取等号。
∵ zii=bTi×bi
[证毕]
可以看出两者在衡量方差分量间的相关性上是等价的，且γ≤1，δ≥1。当它们分别取1时，则方差-协方差阵整数转换后完全对角化。
2.2 基于原始基和对偶基规约的S(A)指标
文献[20]同时采用S(A)作为衡量基向量规约程度的指标
式中，n为维数；α为向量bi和b*i的夹角。由式(4)知，当j≠i时b*i正交于基向量bj，如果夹角α为零时，向量bi和b*i两者相互平行，此时bi同其余基向量相互正交。因此式(9)取等时，基向量之间两两相互正交，且
=BTB的非对角线元素等于零。值得注意的是δ和S(A)虽然都是用来衡量规约后矩阵的对角化程度，但两者却不等价，这是因为S(A)包含对偶基的正交性，从后面的试验可以看到两者的差异。2.3 条件数的分析
对降相关算法的评价中，条件数κ也常被用作评价降相关效果好坏的指标[3]，即
式中，λmax与λmin分别表示
的最大和最小特征值。条件数的几何含义是表示超椭球的扁度[23]，数值越大椭球的扁度也越大。当值为1时模糊度方差阵为一个主对角线元素相等的对角阵，此时二次型的几何形状为一个球体。
综上，γ、δ和S(A)常被用作衡量模糊度方差-协方差阵的降相关性能；κ用来衡量整数变换后椭球的扁度。因此，可把评价指标从效果上分为两大类型：一是反映规约后基向量的正交性，比如δ、S(A)；二是反映椭球的状态，比如κ。
3 试验结果与分析 3.1 方案设计
为验证通过整数变换降低模糊度方差分量的相关性及实现椭球压缩是否对搜索效率有直接的影响，基于文中3种规约方法，采用κ、δ、S(A)衡量规约后方差阵的相关性和模糊度二次型的几何形状；然后采用目前效率最高的SE-VB搜索算法获得搜索耗时；最后采用Bootstraping成功率PBSR作为模糊度整数最小二乘估计成功率的下边界[24]，并用以判别其与搜索效率的关系。其中，PBSR按照式(11)进行计算
式中，di为
经过Cholesky分解后的对角阵D中主对角线元素。首先，借鉴文献[6]设计了如下两种模拟方案：
方案1：L是单位下三角矩阵，且下三角元素li,j(i>j)服从标准正态分布D=diag(15,15,15,0.01,…,0.01)。
方案2：L是一个随机正交矩阵，
、dn=
、di∈(dn,d1)、D=diag(d1,…,di,…,dn)。
上述模拟方案中模糊度方差-协方差阵和浮点解构造如下
根据模糊度和基线分量的关系，如果已知3个模糊度就可唯一确定基线分量，其余模糊度也可相应推出，因此方案1和方案2按照前3个条件方差较大的原则进行设计。
其次，为进一步衡量各种评价指标的实际效果，采用两组实测数据进行验证：
方案3：采用南方S82-C接收机获得的4m短基线实测数据所解算的单历元GPS双差模糊度信息。
方案4：采用Trimble R9接收机获得的8km中长基线实测数据所解算的单历元GPS双差模糊度信息。
为减少计算时间，模拟数据中每个历元的模糊度维数都固定为18维，且上述4种情形均解算100个历元的结果作为验证。本文所有的计算均在笔者的PC计算机上基于MATLAB 2012b软件进行，其软硬件配置为：Intel Core i7-3520 CPU，2.90GHz，4GB内存，win7系统。
3.2 结果分析
表 1统计了4种情形下分别采用LAMBDA、LLL和Seysen算法解算100个历元的平均搜索时间、S(A)、κ和δ，从表中可以看到Seysen算法具有较大的搜索耗时，但S(A)和κ值小于LLL规约算法和LAMBDA算法，δ与搜索时间具有相同的趋势，从表 1初步说明较小的S(A)和κ不能表示可以获得较小的搜索耗时。
| search time/s | S(A) | κ | δ | ||||||||||
| LAMBDA | LLL | Seysen | LAMBDA | LLL | Seysen | LAMBDA | LLL | Seysen | LAMBDA | LLL | Seysen | ||
| 方案1 | 0.007 | 0.008 | 0.016 | 6382.7 | 6382.7 | 2287.5 | 156.6 | 156.6 | 72.1 | 504.72 | 504.72 | 1283.99 | |
| 方案2 | 0.004 | 0.005 | 0.009 | 1437.4 | 1437.4 | 740.3 | 72.5 | 72.5 | 43.1 | 103.54 | 103.54 | 119.45 | |
| 方案3 | 0.001 | 0.001 | 0.017 | 115.3 | 116.8 | 82.7 | 265.8 | 272.0 | 132.8 | 4.72 | 4.72 | 4.75 | |
| 方案4 | 0.002 | 0.002 | 0.033 | 269.6 | 275.0 | 174.0 | 131.0 | 134.7 | 67.6 | 15.48 | 15.48 | 15.96 | |
为进一步说明各种评价指标与搜索耗时的关系，分别在图 1~图 4中给出4种情形下的解算结果。图 1~图 4的(a)图给出的是LAMBDA、LLL和Seysen算法的搜索耗时的累积分布函数图。从4种情形的解算结果看出相对于Seysen 算法，LAMBDA和LLL算法耗时收敛速度较快且二者搜索时间差异较小。图 1~图 4的(b)图中的4个子图依次为S(A)、κ、δ和PBSR在不同历元下LLL算法和Seysen算法分别相对于LAMBDA的比值(红线为LLL相对于LAMBDA的比值；蓝线为Seysen算法相对于LAMBDA的比值)。从(b)图结果可以看出LLL与LAMBDA的解算比值除在方案3处的S(A)和κ值存在上下波动外，其余值在不同情形下基本接近于1，而Seysen算法的S(A)和κ的比值具有相同的变化趋势且值基本小于1。从3种算法的δ结果比值来看，LLL算法和LAMBDA的结果值基本相同，Seysen算法在4种情形下的结果仅能说明在整体上其δ值较大，但在方案2和方案3情形下较多历元处的δ值不大于其余两种算法。从3种算法的PBSR可以得到，LLL与LAMBDA解算的数值差异依然较小，而Seysen算法的PBSR均小于其余两种算法。
 |
| 图 1 方案1解算的搜索时间及评价指标比率 Fig. 1 Search time and assessment criteria for case 1 |
 |
| 图 2 方案2解算的搜索时间及评价指标比率 Fig. 2 Search time and assessment criteria for case 2 |
 |
| 图 3 方案3解算的搜索时间及评价指标比率 Fig. 3 Search time and assessment criteria for case 3 |
 |
| 图 4 方案4解算的搜索时间及评价指标比率 Fig. 4 Search time and assessment criteria for case 4 |
结合表 1和图 1~图 4，可作如下几点分析：
(1) 由于LAMBDA和LLL算法两者对方差-协方差阵按照不同分解方式进行降相关处理，因而在整数转换过程中存在不同的取整误差，导致上述试验结果中两者在搜索耗时和不同降相关性能指标上存在细微区别，但总体上是一致的，验证了两者理论上的等价性，因此下面仅需讨论LLL算法和Seysen算法之间的解算比较结果。
(2) 从S(A)和κ对应的比值来看，降低原始基和对偶基的相关性以及压缩椭球并不是提高效率的关键因素。从δ结果来看，尽管Seysen算法在整体上大于LLL算法，但依然存在一些值较小的情形，因而不能准确解释其在各个历元处的搜索耗时均大于LLL算法的现象。因此，根据S(A)、κ和δ3种指标与搜索效率之间的结果对比可得，以上评价指标不能准确评价模糊度方差阵的规约性能。同时，相对于Seysen算法，LLL算法在进行规约时需要对相邻基向量进行交换，因而可以推知基向量交换(LAMBDA算法采用的是相邻条件方差的排序)是决定模糊度搜索效率的关键因素。
(3) S(A)和κ具有相同的趋势，是因为κ的解算与对偶基也存在直接关系(参见式(10))。S(A)与δ在不同情形下实际解算效果存在显著差异性，是由Seysen算法和LLL算法(仅对原始基规约)自身的规约特性决定的，根据式(8)和式(9)可知S(A)和δ分别较好体现的是Seysen算法和LLL的规约程度。因此，不能简单判断何种规约方法的降相关效果较好，其降相关效果取决于对基向量性质的要求(如需获得一组降相关较好的原始基和对偶基，建议采用如Seysen算法规约性质相类似的算法)。
(4) 从LLL算法和Seysen算法各自解算的PBSR的结果对比来看，当PBSR较大时，此时搜索速度较快，说明PBSR可以作为评价模糊度搜索效率的指标。需要指出的是，PBSR仅作为整数最小二乘成功率的下边界，因而当不同规约方法获得的PBSR存在差异时，并不影响整数最小二乘模糊度解算的成功率。
4 结 论
本文首先对条件数、降相关系数、正交缺陷度、S(A)等4个常见的降相关评价指标所代表的几何意义进行了理论分析，然后针对LAMBDA算法、LLL规约算法和Seysen规约算法，基于上述降相关指标以及Bootstraping成功率进行了模拟和实际数据的验证分析，对模糊度的搜索效果和不同评价指标之间的关系进行了深入探讨，主要获得了如下结论：
通过对条件数、正交缺陷度和S(A)所代表几何意义理论分析可知，条件数可以衡量压缩椭球程度，正交缺陷度和S(A)均从不同角度表示基向量间的相关性。通过LAMBDA、LLL和Seysen规约算法解算结果，不仅验证了降相关不同评价指标与模糊度的搜索效率并不存在直接关系，而且进一步验证得出“最大限度地降低模糊度方差协方差阵的相关性和实现椭球的压缩以提高搜索效率”的观点是片面的。
通过以上3种方法的结果对比分析可知，相对于LAMBDA、LLL算法，Seysen算法可能在降低原始基和对偶基的相关性上和压缩椭球方面具有优势，但并不涉及基向量的排序过程，导致搜索过程中冗余节点数过多，造成耗时较大的现象，说明提高搜索效率的本质在于尽可能地促使基向量按照一定方向排序。这一结论对今后模糊度降相关方法的进一步研究具有启示作用。
此外，从试验角度不仅验证了LAMBDA和LLL算法两者的等价关系，而且进一步验证了Bootstraping成功率与搜索效率基本呈正相关关系，其可以在某种程度上衡量模糊度方差-协方差阵的规约性能。
| [1] | TEUNISSENP J G, JONGEP J D, TIBERIUSC C J M. The Least-squares Ambiguity Decorrelation Adjustment: A Method for Fast GPS Integer Ambiguity Estimation[J]. Journal of Geodesy, 1995, 70(1): 65-82. |
| [2] | TEUNISSENP J G. A New Method for Fast Carrier Phase Ambiguity Estimation[C]//Proceedings of the IEEE PLANS’94. Las Vegas: [s.n.], 1994. |
| [3] | LIU L T, HSU H T, ZHU Y Z, et al. A New Approach to GPS Ambiguity Decorrelation[J]. Journal of Geodesy, 1999, 73(1): 478-490. |
| [4] | XU P L. Random Simulation and GPS Decorrelation[J]. Journal of Geodesy, 2001, 75(1): 408-423. |
| [5] | XU P L. Parallel Cholesky-based Reduction for the Weighted Integer Least Squares Problem[J]. Journal of Geodesy, 2012, 86(1): 35-52. |
| [6] | CHANG X W, YANG X, ZHOU T. MLAMBDA: A Modified LAMBDA Method for Integer Least-squares Estimation[J]. Journal of Geodesy, 2005, 79(9): 552-565. |
| [7] | ZHOU Y M. A New Practical Approach to GNSS High-dimensional Ambiguity Decorrelation[J]. GPS Solutions, 2011, 15(1): 325-331. |
| [8] | LIU Ning, XIONG Yongliang, FENG Wei, et al. An Algorithm for Rapid Integer Ambiguity Resolution in Single Frequency GPS Kinematical Positioning[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 211-217. (刘宁, 熊永良, 冯威, 等. 单频GPS动态定位中整周模糊度的一种快速解算方法[J]. 测绘学报, 2013, 42(2): 211-217.) |
| [9] | ZHOU Yangmei, LIU Jingnan, LIU Jiyu. Return-calculating LAMBDA Approach and Its Search Space[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(4): 300-304. (周扬眉, 刘经南, 刘基余. 回代解算的LAMBDA方法及其搜索空间[J]. 测绘学报, 2005, 34(4): 300-304.) |
| [10] | LENSTR A K, LENSTRA H W, LOVASZ L. Factoring Polynomials with Rational Coefficients[J]. Mathematische Annalen, 1982, 261(4): 515-534. |
| [11] | YU Xingwang. Multi-frequency GNSS Precise Positioning Theory and Method Research[D]. Wuhan: Wuhan University, 2011. (于兴旺. 多频GNSS精密定位理论与方法研究[D]. 武汉: 武汉大学, 2011.) |
| [12] | JAZAERI S, AMIRI-SIMKOOEI A R, SHARIFI M A. On Lattice Reduction Algorithms for Solving Weighted Integer Least Squares Problems: Comparative Study[J]. GPS Solutions, 2014, 18(1): 105-114. |
| [13] | BORNO M A, CHANG X W, XIE X. On “Decorrelation” in Solving Integer Least-squares Problems for Ambiguity Determination[J]. Survey Review, 2014, 46: 37-49. |
| [14] | HASSIBI A, BOYD S. Integer Parameter Estimation in Linear Models with Applications to GPS[J]. IEEE Transactions on Signal Processing, 1998, 46(11): 2938-2952. |
| [15] | GRAFAREND E W. Mixed Integer-real Valued Adjustment(IRA) Problems: GPS Initial Cycle Ambiguity Resolution by Means of the LLL Algorithm[J]. GPS Solutions, 2000, 4(2): 31-43. |
| [16] | FAN Long, ZHAI Guojun, CHAI Hongzhou. Ambiguity Decorrelation Algorithm with Integer Block Orthogonalization[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(8): 818-826. (范龙, 翟国君, 柴洪洲. 模糊度降相关的整数分块正交化算法[J]. 测绘学报, 2014, 43(8): 818-826.) |
| [17] | LIU Zhiping, HE Xiufeng. An Improved LLL Algorithm for GPS Ambiguity Solution[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 286-289. (刘志平, 何秀凤. 改进的GPS模糊度降相关LLL算法[J]. 测绘学报, 2007, 36(3): 286-289.) |
| [18] | LIU Jingnan, YU Xingwang, ZHANG Xiaohong. GNSS Ambiguity Resolution Using Lattice Theory[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 636-645. (刘经南, 于兴旺, 张小红. 基于格论的GNSS模糊度解算[J]. 测绘学报, 2012, 41(5): 636-645.) |
| [19] | LANNES A. On the Theoretical Link between LLL-reduction and LAMBDA Decorrelation[J]. Journal of Geodesy, 2013, 87(4): 323-335. |
| [20] | SEYSEN M. Simultaneous Reduction of a Lattice Basis and Its Reciprocal Basis[J].Combinatorica, 1993, 13(3): 262-376. |
| [21] | LU Liguo. The Research and Analysis Based on Sphere Search for Ambiguity on Reduction[D]. Wuhan: Wuhan University, 2013. (卢立果. 基于球形搜索的模糊度格基规约方法研究与分析[D]. 武汉: 武汉大学: 2013.) |
| [22] | WANG J, FENG Y M. Orthogonality Defect and Reduced Search-space Size for Solving Integer Least-squares Problems[J]. GPS Solutions, 2013, 17(1): 261-274. |
| [23] | GOLUB G H, VAN LOANC F. Matrix Computations[M]. YUAN Yaxiang, trans. Beijing: Science Press, 2001. (戈卢布 G H,范洛恩 C F. 矩阵计算[M]. 袁亚湘, 译. 北京: 科学出版社, 2001.) |
| [24] | TEUNISSEN P J G. Success Probability of Integer GPS Ambiguity Rounding and Bootstrapping[J]. Journal of Geodesy, 1998, 72(10): 606-612. |