一种快速解算高维模糊度的LLL分块处理算法

刘万科; 卢立果; 单弘煜

doi:10.11947/j.AGCS.2016.20150370

测绘学报 >

2016 , Vol. 45 >Issue 2: 147 - 156

DOI: https://doi.org/10.11947/j.AGCS.2016.20150370

大地测量学与导航

一种快速解算高维模糊度的LLL分块处理算法

刘万科 ,
卢立果 ,
单弘煜

展开

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

刘万科(1978-),男,博士,副教授,研究方向为卫星导航定位和精密定轨数据处理方法。

收稿日期: 2015-07-13

修回日期: 2015-09-17

网络出版日期: 2016-02-29

基金资助

国家自然科学基金(41204030;41374034);国家基础测绘科技项目(201420);中电集团54所高校合作项目(KX132600031);预研基金项目(9140A24020713JB11342;51324040103)

收起

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

LIU Wanke ,
LU Liguo ,
SHAN Hongyu

Expand

1. School of Geodesy and Geomatics, Wuhan University, Wuhan 430079, China;
2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China

Received date: 2015-07-13

Revised date: 2015-09-17

Online published: 2016-02-29

Supported by

The National Natural Science Foundation of China (Nos. 41204030;41374034);The National Basic Surveying and Mapping Science and Technology Project (No. 201420);CLP 54 Universities Cooperation Project (No. KX132600031);Pre-research Fund Project (Nos. 9140A24020713JB11342;51324040103)

Fold

摘要

由于多频多模GNSS观测数据解算的模糊度具有较高的维数和精度,当采用常规的LLL算法进行模糊度整数估计时,规约耗时显著大于搜索耗时,成为限制高维模糊度解算计算效率的主要因素。针对这一问题,通过分析规约耗时与模糊度维数和精度之间的关系,提出了一种LLL分块处理算法。该算法通过对模糊度方差协方差阵进行分块处理,降低单个规约矩阵的维数,以减少规约耗时,从而提高模糊度解算计算效率。通过两组实测高维模糊度数据对本文提出的分块处理算法进行了效果验证。结果显示,当分块选择合理时,本文提出的算法相对于LLL算法的解算效率分别可提高65.2%和60.2%。

关键词： 高维模糊度; 格基规约; 分块LLL; 解算效率

本文引用格式

刘万科 , 卢立果 , 单弘煜 . 一种快速解算高维模糊度的LLL分块处理算法[J]. 测绘学报, 2016 , 45(2) : 147 -156 . DOI: 10.11947/j.AGCS.2016.20150370

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] 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.2014.0094.
[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.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献