﻿ 一种快速解算高维模糊度的LLL分块处理算法
 文章快速检索 高级检索

1. 武汉大学测绘学院， 湖北 武汉 430079;
2. 地球空间信息技术协同创新中心， 湖北 武汉 430079

A New Block Processing Algorithm of LLL for Fast High-dimension Ambiguity Resolution
LIU Wanke1,2, LU Liguo1,2, SHAN Hongyu1
1. School of Geodesy and Geomatics, Wuhan University, Wuhan 430079, China;
2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China
First author: LIU Wanke (1978—), male, PhD, associate professor, majors in the theory and algorithm of GNSS precise positioning and precise orbit determination. E-mail: wkliu@sgg.whu.edu.cn
Abstract: Due to high dimension and precision for the ambiguity vector under GNSS observations of multi-frequency and multi-system, a major problem to limit computational efficiency of ambiguity resolution is the longer reduction time when using conventional LLL algorithm. To address this problem, it is proposed a new block processing algorithm of LLL by analyzing the relationship between the reduction time and the dimensions and precision of ambiguity. The new algorithm reduces the reduction time to improve computational efficiency of ambiguity resolution, which is based on block processing ambiguity variance-covariance matrix that decreased the dimensions of single reduction matrix. It is validated that the new algorithm with two groups of measured data. The results show that the computing efficiency of the new algorithm increased by 65.2% and 60.2% respectively compared with that of LLL algorithm when choosing a reasonable number of blocks.
Key words: high-dimension ambiguity     lattice basis reduction     block LLL     resolution efficiency

1 数学模型 1.1 整数最小二乘原理

Qââ进行Cholesky分解

1.2 基于QR分解的LLL算法

 图 1 LLL算法分块示意图 Fig. 1 The schematic of Block LLL algorithm

(1) 给定分块数m(考虑(Ri,Ri+1)间的交换，一般m≥3)，获得分块大小k及余数r，并设置i=1。

(2) 对传递块Ri按照LLL算法进行解算，获得整数转换矩阵Zi、正交阵QiB(i)，同时对Ri块对应的R中剩余列向量Ric和行向量Rir按照Ric=RicZiRir=QiRir进行更新。其中

(3) 当i≥2时，判断B(i－1)≤δk2B(i)是否成立。如果不等式成立令i=i+1，直到i=m时退出规约过程；否则令i=i－1。

(4) 返回过程(2)。

3 试验数据分析

3.1 模糊度方差阵与规约和搜索耗时的关系

PS,IB计算公式可知其数值取决于条件方差(规约基)的大小。当采用的算法规约性能较优时，可以获得一组相对较短的规约基，此时解算的PS,IB数值较大从而更接近PS,ILS。因此，为较精确地衡量PS,ILS，通常采用规约性能较强的算法(比如LAMBDA或者LLL算法)计算PS,IB。由于PS,IB可以反映基向量的规约程度，因而PS,IB又被用作评价不同规约算法规约性能的指标[15, 20]

 图 2 不同维数和精度下的Bootstrapping成功率、规约耗时和搜索耗时的变化趋势图 Fig. 2 The trend chart of Bootstrapping success rate, reduction time and search time under different dimensions and ADOP

3.2 试验1

 参数 指标 接收机型号 司南M300-II 系统和频率 GPS(L1，L2) BDS(B1，B2，B3) GLONASS(G1，G2) 起始时间 2014-11-20 03:13:00 历元数 2834 采样间隔/s 5 截止高度角/(°) 10 基线长/m 0.5 处理模式 单历元

 图 3 不同历元下的模糊度维数与ADOP值 Fig. 3 Ambiguity dimensions and the value of ADOP under different epoches

 s 方法 reduction search total mean max mean max mean max LLL 0.080 7 0.150 0 0.010 3 0.060 0 0.091 0 0.186 3 IBGS 0.077 6 0.195 7 0.010 5 0.029 6 0.088 1 0.208 8 m=3 0.069 3 0.131 5 0.010 4 0.045 8 0.079 7 0.147 3 m=4 0.058 7 0.100 8 0.010 6 0.042 0 0.069 3 0.119 5 m=5 0.050 4 0.089 2 0.010 6 0.042 8 0.060 9 0.102 2 m=6 0.044 6 0.103 7 0.010 7 0.049 2 0.055 3 0.117 7 m=7 0.039 8 0.084 1 0.011 7 0.056 0 0.051 6 0.100 2 m=8 0.034 2 0.080 0 0.011 6 0.044 0 0.045 8 0.093 5 m=9 0.029 7 0.081 7 0.011 8 0.036 5 0.041 4 0.095 0 m=10 0.025 7 0.075 1 0.012 0 0.051 3 0.037 7 0.090 6 m=11 0.023 9 0.079 5 0.012 4 0.044 2 0.036 4 0.109 2 m=12 0.020 5 0.069 2 0.011 9 0.050 9 0.032 4 0.087 2 m=13 0.019 7 0.068 0 0.012 0 0.052 3 0.031 7 0.082 2 m=14 0.017 9 0.042 9 0.013 8 3.737 8 0.031 7 3.752 9

 图 4 m=13时不同规约方法的模糊度解算耗时和PS,IB Fig. 4 Ambiguity resolution time and PS,IB in different methods under m=13

 图 5 m=14时不同规约方法的模糊度解算耗时和PS,IB Fig. 5 Ambiguity resolution time and PS,IB in different methods under m=14

3.3 试验2

 参数 指标 接收机型号 Trimble NetR9 系统和频率 GPS(L1，L2) BDS(B1，B2，B3) GLONASS(G1，G2) 起始时间 2015-04-10 00:00:00 历元数 2872 采样间隔/s 30 截止高度角/(°) 10 基线长/m 8.4 处理模式 单历元

 图 6 不同历元下的模糊度维数与ADOP值 Fig. 6 Ambiguity dimensions and the value of ADOP under different epoches

 S 方法 reduction search total mean max mean max mean max LLL 0.074 4 0.148 6 0.008 3 0.061 4 0.082 7 0.163 7 IBGS 0.065 9 0.168 6 0.008 8 0.021 1 0.074 7 0.183 8 m=3 0.060 3 0.136 4 0.008 7 0.041 6 0.069 0 0.156 2 m=4 0.048 2 0.110 3 0.008 4 0.055 8 0.056 6 0.132 2 m=5 0.042 9 0.106 8 0.009 1 0.046 1 0.052 0 0.117 9 m=6 0.035 7 0.094 4 0.008 7 0.047 4 0.044 4 0.105 8 m=7 0.030 1 0.084 2 0.008 8 0.048 3 0.039 0 0.101 4 m=8 0.026 5 0.067 5 0.009 4 0.034 3 0.035 9 0.086 4 m=9 0.023 1 0.070 4 0.009 8 0.134 5 0.032 9 0.146 0 m=10 0.020 7 0.059 9 0.011 2 1.789 3 0.031 9 1.804 4

 图 7 m=10时不同规约方法的模糊度解算耗时和PS,IB Fig. 7 Ambiguity resolution time and PS,IB in different methods under m=10
4 结 论

(2) 分块数与规约耗时呈现负相关关系，即在一定的块数范围内，当分块数越多，规约强度越低(PS,IB越小)，规约耗时越小。因此，当分块选择合理时，此时搜索耗时相对稳定，可以获得较高的模糊度解算计算效率。

(3) 对于本文的两组实测高维数据而言，IBGS相对于LLL算法的解算效率略有提高，而本文提出的BLLL算法在分块数分别为13和9时相对于LLL算法的解算效率可以提高65.2%和60.2%。

 [1] TEUNISSEN P J G. The Least-squares Ambiguity Decorrelation Adjustment: A Method for Fast GPS Integer Ambiguity Estimation[J]. Journal of Geodesy, 1995, 70(1-2): 65-82. [2] LIU L T, HSU H T, ZHU Y Z, et al. A New Approach to GPS Ambiguity Decorrelation[J]. Journal of Geodesy, 1999, 73(9): 478-490. [3] XU Peiliang. Random Simulation and GPS Decorrelation[J]. Journal of Geodesy, 2001, 75(7-8): 408-423. [4] XU Peiliang. Parallel Cholesky-based Reduction for the Weighted Integer Least Squares Problem[J]. Journal of Geodesy, 2012, 86(1): 35-52. [5] ZHOU Yangmei. A New Practical Approach to GNSS High-dimensional Ambiguity Decorrelation[J]. GPS Solutions, 2011, 15(4): 325-331. [6] 周扬眉, 刘经南, 刘基余. 回代解算的LAMBDA方法及其搜索空间[J]. 测绘学报, 2005, 34(4): 300-304. 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. [7] 刘宁, 熊永良, 冯威, 等. 单频GPS动态定位中整周模糊度的一种快速解算方法[J]. 测绘学报, 2013, 42(2): 211-217. 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. [8] 卢立果, 刘万科, 于兴旺. 基于交叉排序算法解算模糊度的新规约方法[C]//第五届中国卫星导航学术年会电子文集. 南京: [s.n.], 2014. LU Liguo, LIU Wanke, YU Xingwang. A New Reduction Method for Ambiguity Resolution Based on Cross Sorting Algorithm[C]//The Fifth China Satellite Navigation Conference (CSNC). Nanjing: [s.n.], 2014. [9] 于兴旺. 多频GNSS精密定位理论与方法研究[D]. 武汉: 武汉大学, 2011. YU Xingwang. Multi-frequency GNSS Precise Positioning Theory and Method Research[D]. Wuhan: Wuhan University, 2011. [10] JAZAERI S, AMIRI-SIMKOOEI A R, SHARIFI M A. Fast Integer Least-squares Estimation for GNSS High Dimensional Ambiguity Resolution Using the Lattice Theory[J]. Journal of Geodesy, 2012, 86(2): 123-136. [11] 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. [12] 刘志平, 何秀凤. 改进的GPS模糊度降相关LLL算法[J]. 测绘学报, 2007, 36(3): 286-289. LIU Zhiping, HE Xiufeng. An Improved LLL Algorithm for GPS Ambiguity Solution[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 286-289. [13] 杨荣华, 花向红, 李昭, 等. GPS模糊度降相关LLL算法的一种改进[J]. 武汉大学学报(信息科学版), 2010, 35(1): 21-24. YANG Ronghua, HUA Xianghong, LI Zhao, et al. An Improved LLL Algorithm for GPS Ambiguity Solution[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 21-24. [14] 谢恺, 柴洪洲, 范龙, 等. 一种改进的LLL模糊度降相关算法[J]. 武汉大学学报(信息科学版), 2014, 39(11): 1363-1368. XIE Kai, CHAI Hongzhou, FAN Long, et al. An Improved LLL Ambiguity Decorrelation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2014, 39(11): 1363-1368. [15] 刘经南, 于兴旺, 张小红. 基于格论的GNSS模糊度解算[J]. 测绘学报, 2012, 41(5): 636-645. LIU Jingnan, YU Xingwang, ZHANG Xiaohong. GNSS Ambiguity Resolution Using Lattice Theory[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 636-645. [16] 卢立果. 基于球形搜索的模糊度格基规约方法研究与分析[D]. 武汉: 武汉大学, 2013. LU Liguo. The Research and Analysis Based on Sphere Search for Ambiguity on Reduction[D]. Wuhan: Wuhan University, 2013. [17] LANNES A. On the Theoretical Link between LLL-reduction and LAMBDA-decorrelation[J]. Journal of Geodesy, 2013, 87(4): 323-335. [18] LEICA A, RAPOPORT L, TATARNIKOV D. GPS Satellite Surveying[M]. 4th ed. New York: Wiley, 2015: 324-356. [19] BORNO M A, CHANG X W, XIE X H. On “Decorrelation” in Solving Integer Least-squares Problems for Ambiguity Determination[J]. Survey Review, 2014, 46(334): 37-49. [20] 卢立果, 刘万科, 李江卫. 降相关对模糊度解算中搜索效率的影响分析[J]. 测绘学报, 2015, 44(5): 481-487. DOI: 10.11947/j.AGCS.2015.20140311. LU Liguo, LIU Wanke, LI Jiangwei. Impact of Decorrelation on Search Efficiency of Ambiguity Resolution[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5): 481-487. DOI: 10.11947/j.AGCS.2015.20140311. [21] 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. [22] TEUNISSEN P J G, ODOLINSKI R, ODIJK D. Instantaneous BeiDou+GPS RTK Positioning with High Cut-off Elevation Angles[J]. Journal of Geodesy, 2014, 88(4): 335-350. [23] KOY H, SCHNORR C P. Segment LLL-reduction of Lattice Bases[M]//SILVERMAN J H. Cryptography and Lattices, Lecture Notes in Computer Sciences. Berlin: Springer, 2001, 2146: 67-80. [24] KOY H, SCHNORR C P. Segment LLL-reduction with Floating Point Orthogonalization[M]//SILVERMAN J H. Cryptography and Lattices, Lecture Notes in Computer Sciences. Berlin: Springer, 2001, 2146: 81-96. [25] 范龙, 翟国君, 柴洪洲. 模糊度降相关的整数分块正交化算法[J]. 测绘学报, 2014, 43(8): 818-826. DOI: 10.13485/j.cnki.11-2089.2014.0094. FAN Long, ZHAI Guojun, CHAI Hongzhou. Ambiguity Decorrelation Algorithm with Integer Block Orthogonalization Algorithm[J]. .Acta Geodaetica et Cartographica Sinica, 2014, 43(8): 818-826. DOI: 10.13485/j.cnki.11-2089.20140094. [26] LENSTRA A K, LENSTRA H W, LOVASZ L. Factoring Polynomials with Rational Coefficients[J]. Mathematische Annalen, 1982, 261(4): 515-534. [27] LUK F T, TRACY D M. An Improved LLL Algorithm[J]. Linear Algebra and Its Applications, 2007, 428(2-3): 441-452. [28] NGUYEN P Q, VALLEE B. The LLL Algorithm: Survey and Applications (Information Security and Cryptography) [M]. Paris: Springer, 2010: 145-178. [29] ODIJK D, TEUNISSEN P J G. ADOP in Closed form for a Hierarchy of Multi-frequency Single-Baseline GNSS Models[J]. Journal of Geodesy, 2008, 82(8): 473-492. [30] TEUNISSEN P J G, ODIJK D. Ambiguity Dilution of Precision: Definition, Properties and Application[C]//Proceedings of ION GPS-97. Kansas City: [s.n.], 1997: 891-899. [31] VERHAGEN S. On the Approximation of the Integer Least-squares Success Rate: Which Lower or Upper Bound to Use?[J]. Journal of Global Positioning Systems, 2003, 2(2): 117-124. [32] FENG Yanming, WANG Jun. Computed Success Rates of Various Carrier Phase Integer Estimation Solutions and Their Comparison with Statistical Success Rates[J]. Journal of Geodesy, 2011, 85(2): 93-103. [33] VERHAGEN S, LI Bofeng, TEUNISSEN P J G. Ps-LAMBDA: Ambiguity Success Rate Evaluation Software for Interferometric Applications[J]. Computers & Geosciences, 2013, 54: 361-376. [34] TEUNISSEN P J G. Success Probability of Integer GPS Ambiguity Rounding and Bootstrapping[J]. Journal of Geodesy, 1998, 72(10): 606-612.
http://dx.doi.org/10.11947/j.AGCS.2016.20150370

0

文章信息

LIU Wanke, LU Liguo, SHAN Hongyu

A New Block Processing Algorithm of LLL for Fast High-dimension Ambiguity Resolution

Acta Geodaeticaet Cartographica Sinica, 2016, 45(2): 147-156.
http://dx.doi.org/10.11947/j.AGCS.2016.20150370