留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种有效的LLL规约算法

卢立果 刘万科 李江卫

卢立果, 刘万科, 李江卫. 一种有效的LLL规约算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
引用本文: 卢立果, 刘万科, 李江卫. 一种有效的LLL规约算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
LU Liguo, LIU Wanke, LI Jiangwei. An Efficient LLL Reduction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
Citation: LU Liguo, LIU Wanke, LI Jiangwei. An Efficient LLL Reduction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484

一种有效的LLL规约算法

doi: 10.13203/j.whugis20140484
基金项目: 

国家自然科学基金 41204030

详细信息

An Efficient LLL Reduction Algorithm

Funds: 

The National Natural Science Foundation of China 41204030

More Information
图(5)
计量
  • 文章访问数:  2254
  • HTML全文浏览量:  48
  • PDF下载量:  443
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-09-10
  • 刊出日期:  2016-08-05

一种有效的LLL规约算法

doi: 10.13203/j.whugis20140484
    基金项目:

    国家自然科学基金 41204030

    作者简介:

    卢立果, 博士生, 现主要从事GNSS高维模糊度解算的理论研究。lglu66@163.com

    刘万科, 博士, 副教授。wkliu@sgg.whu.edu.cn

    通讯作者: 刘万科, 博士, 副教授。E-mail:wkliu@sgg.whu.edu.cn
  • 中图分类号: P207

摘要: 针对Lenstra-Lenstra-Lovász(LLL)规约算法在高维情况下规约耗时较大的特点,采用贪心算法和部分列向量规约,减少LLL算法规约过程中的基向量交换和尺度规约次数,以降低LLL算法的计算复杂度。通过模拟和实测的数据验证,该改进方法可以降低LLL算法的规约耗时,因而对高维模糊度的快速解算具有一定的参考应用价值。

English Abstract

卢立果, 刘万科, 李江卫. 一种有效的LLL规约算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
引用本文: 卢立果, 刘万科, 李江卫. 一种有效的LLL规约算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
LU Liguo, LIU Wanke, LI Jiangwei. An Efficient LLL Reduction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
Citation: LU Liguo, LIU Wanke, LI Jiangwei. An Efficient LLL Reduction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1118-1124. doi: 10.13203/j.whugis20140484
  • 相位整周模糊度的快速准确确定是GNSS实时精密定位的关键。国内外学者已提出了多种解算整周模糊度的方法,其中以LAMBDA(least-squares ambinwity decorrelation adjustment)方法最具代表性[1]。该方法首次提出降相关的概念,通过采用幺模矩阵对模糊度的方差阵进行整数变换,提高模糊度的搜索效率,随后各种降相关方法被相继提出[2-6]。由于整数最小二乘模糊度解算等价于格上最近向量问题,因而可以采用格基规约的方法处理此类问题。文献[7]提出的LLL规约算法是目前最为流行的格基规约算法。文献[8]把LLL规约算法引入到GNSS领域,并指出LAMBDA来源于LLL算法。随后,文献[9-11]对其作了一些改进,但采用的LLL规约算法缺少基向量交换过程。近来,文献[12]从理论上证明了规约可以有效地减少搜索候选点数;文献[13]对格基规约和降相关之间的等价性也做了证明。

    由于高维模糊度解算中规约耗时在模糊度整体解算时间中占据很大比例,因此,如何减少规约算法的复杂度是本文研究的重点。文献[5]针对LAMBDA算法采用贪心选择过程以减少相邻条件方差的交换次数;文献[14]指出LLL算法的核心是基向量交换部分,并在此基础上提出了部分尺度规约的ELLL(Effective LLL)算法;文献[15]针对ELLL的截断误差较大的特点,提出有选择性进行列向量尺度规约的PLLL(Partial LLL)算法。本文在此基础上进行改进。

    • 假定、分别为最小二乘解算模糊度的实数解和方差-协方差阵,对其进行最小二乘模糊度整数估计,估计准则为[1]:

      (1)

      进行Cholesky分解:

      (2)

      式中,B为上三角矩阵。

      把式(2)代入式(1)得:

      (3)

      式中,是一个常数向量。

      式(3)在格上被称为最近向量问题,常采用LLL规约算法进行解算。

      B进行分解:

      (4)

      式中,D为对角矩阵且主对角线元素为d1, d2, …, dnU为单位上三角矩阵。

      规约后DU中的元素满足如下条件[7]

      (5)

      其中,式(5)中第一行称为尺度规约;第二行称为基向量交换。

    • 由式(5)可以直观看出,LLL算法规约的主要过程是尺度规约和基向量交换。要求|ui, j|≤0.5的主要目的是尽可能地提高基向量交换的能力,以减少搜索过程中每一层的节点数。在进行LLL算法规约时,影响算法复杂度的主要因素是基向量的交换次数以及矩阵U中元素尺度规约个数。针对此,笔者从减少尺度规约个数和基向量交换次数的角度进行了算法改进。

    • 在进行部分尺度规约之前,需要从理论上说明单纯的尺度规约对模糊度搜索候选点数没有影响,证明过程如下。

      假设式(1)的目标函数满足:

      (6)

      对方差阵进行上三角Cholesky分解:

      (7)

      当仅对进行尺度规约不涉及排序过程时,有:

      (8)

      式中,D=D; L=LZ

      式(6)等价于下面形式的变换过程:

      (9)

      式中,

      假若令:

      (10)

      将式(10)代入式(9),可以得到:

      (11)

      可以看出,单纯尺度规约和未进行尺度规约所获得的模糊度候选向量是一致的。当规约时进行基向量排序,则式(8)中LLZ; DD,式(11)结论不再成立。

      上述证明表明,在进行LLL算法时,一般仅需考虑次对角线元素的规约。但是为了规约算法的有效性和数值的稳定性,需要对部分非对角线元素在满足一定条件下的情况进行尺度规约。

      当基向量不满足交换条件时,有:

      (12)

      式中,[ ]round代表取整操作。

      当|[ui-1, i]round| > 2时,需对列向量中其余元素进行规约[15],即

      (13)

      称式(13)为列向量规约过程。

      需要注意的是,每次对矩阵元素进行规约时,需要更新相应的列向量元素,即当对ui-1, i规约时,列向量元素进行如下更新:

      (14)
    • 贪心算法(又称贪婪算法)是指在对问题求解时,总是做出当前看来是最好的选择。即它不从总体最优上加以考虑,所做出的只是某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但在相当广泛的范围内,它能得到许多问题的整体最优解或者是整体最优解的近似解[16]

      由于LLL算法需要进行基向量的迭代交换,因此可以采用贪心算法交换相邻基向量。下面是贪心算法的具体实现。

      (15)

      当选择一对基向量(i-1, i)进行交换时,参数i定义为:

      (16)

      当参数i不存在时,则结束基向量交换。当一对基向量(i-1, i)进行交换后,相邻对角线元素didi-1的值发生了变化,单位上三角阵U中的元素ui-1, iui, i+1的大小也相应发生了变化,因此当下一次基向量交换过程时,仅需更新(di-2, di-1)、(di-1, di)和(di, di+1)三个基向量对所对应的式(16)中的比值。

    • 结合流程图 1,改进的LLL算法的解算步骤如下。

      (1)首先对原始的方差阵按照式(2)进行Cholesky分解,获得上三角阵B

      (2)在第一次基向量交换前,对B中所有的次对角线元素都进行尺度规约,并根据式(15)求出对应的

      (3)根据式(5)的基向量交换条件判断是否存在需要交换的基向量。如果没有则退出整个规约过程;如果存在交换的基向量则按照式(16)选择当前局部最优的一组交换基(k-1, k),并判断这对基向量对应的次对角线元素uk-1, k的绝对值在未进行尺度规约时是否大于2,如果大于则对k-1列的其他元素进行尺度规约,否则不进行列向量规约。

      (4)当上一次基向量交换后,则重新进行步骤(2)、步骤(3)过程。其中步骤(2)过程不再需要计算所有的值,仅需更新(dk-2, dk-1)、(dk-1, dk)和(dk, dk+1)三个基向量对对应的值。

      图  1  改进的LLL规约算法的处理流程

      Figure 1.  Flowchart of Improved LLL Algorithm

    • 笔者采用LLL算法、PLLL算法[15]以及本文改进的LLL规约算法进行对比。考虑到PLLL在进行规约之前采用SortedQR[2, 17]对其进行预排序以降低基向量迭代次数,为便于验证算法的合理性,本文对LLL算法和本文算法也进行了预排序处理。下文分别把采用预排序的LLL算法和改进的LLL算法简称作SLLL和PGLLL算法。

      本文分别基于模拟和实测数据进行统计分析三种算法的规约耗时、基向量交换次数、搜索候选点数以及整体解算耗时,验证PGLLL算法的规约性能。其中,模糊度整数向量的搜索均采用SE-VB算法[5]完成。本文所有的计算均基于MATLAB 2012b软件完成,PC机软硬件配置为:Intel Core i7-3520 CPU,2.90 GHz,4 GB内存,Win7系统。

    • 借鉴文献[5]的模拟方法进行实验数据模拟。模糊度浮点解构造为:

      (17)

      式中,randn(n, 1)表示随机生成的n个服从标准正态分布的元素。

      模糊度的方差阵按照式(18)进行生成:

      (18)

      式中,L是单位下三角矩阵,且下三角元素lij(i > j)服从标准正态分布;D是主对角线为(10, 10, 10, 0.01, …, 0.01)的对角阵。

      上述模拟过程中,已知三个模糊度就可以唯一确定基线分量,其余模糊度也可相应得出,因此在设计时应遵循前三个条件方差相对较大的原则。考虑到高维模糊度解算的需求,笔者随机生成一个维数为40的模糊度方差阵和浮点解

      图 2(a)为三种算法在不同维数下基向量交换个数的变化趋势。从图 2(a)中看到, 三种算法的基向量交换次数与维数呈正相关关系;PGLLL具有最少的交换个数,PLLL和SLLL的交换个数一致。图 2(b)是不同维数下三种算法的规约耗时。从图 2(b)中可以直观看到, 随着维数的增大,模糊度的规约耗时总体呈上升趋势;PGLLL具有最小的规约时间,PLLL规约时间在前10维可能存在大于SLLL的情形,在维数增大时PLLL的规约时间低于SLLL。

      图  2  不同维数下的规约时间和基向量交换次数

      Figure 2.  Reduction Time and Basis Swap Numbers in Different Dimensions

      图 2中的结果进行分析,由于PLLL仅减少一些非对角线元素的尺度规约过程,不影响基向量的排序,因而PLLL在基向量交换次数上等同于SLLL这一现象同理论相符合;PGLLL采用的贪心算法通过寻找局部最优解降低了基向量交换个数,因此PGLLL相对于其他两种算法降低了规约耗时;在低维条件下,三种方法的规约时间均较少,在高维情形下,由于减少了部分列向量规约过程,因而PLLL规约效率优于SLLL。

      图 3表示的是三种算法在不同维数下的搜索候选点数。从图 3中可以看出,搜索候选点数与维数的变化整体上具有相同的趋势,即随着维数的增长,候选点数增大;SLLL与PLLL具有相同的搜索候选点数,而PGLLL的模糊度候选向量与其余两种方法相比特征不太明显,可能在某些情形下优于SLLL和PLLL,也可能差于这两种算法。

      图  3  不同维数下的模糊度搜索候选点数

      Figure 3.  Ambiguity Searching Candidate Numbers in Different Dimensions

      图 3结果分析,由式(11)可知,单纯的尺度规约不改变模糊度搜索的候选整数向量,因此SLLL的搜索候选点个数与PLLL算法的搜索结果是等同的,这与理论相吻合;由于PGLLL采用的贪心算法在规约时选择的基向量每次都是局部最优解,考虑到基向量交换后需要对次对角线元素进行规约,因此获得的最终基向量长度不同于SLLL和PLLL(基向量是按照一定的顺序交换获得的),从而造成不同维数下PGLLL的搜索候选向量个数与SLLL和PLLL相比出现不同的结果。

    • 图 4是基线长约为12.6 km,接收机型号为南方S82-C,采样间隔为1 s,500个历元的GPS+BeiDou单历元处理结果。图 4(a)是三种规约方法解算的500个历元的基向量交换次数的累积分布函数图,从图 4(a)中可以看出,PGLLL的基向量交换个数小于SLLL和PLLL,且SLLL和PLLL具有相同的交换个数。图 4(b)是三种规约方法的规约时间的累积分布函数图,从图 4(b)中可以得到三种算法的规约效率的高低依次为PGLLL、PLLL和SLLL。图 4(c)统计的是所有历元解算后的模糊度候选向量的累积分布函数,可以看出,SLLL和PLLL具有相同的搜索候选点数,而PGLLL的搜索候选点个数与其余两种算法的关系呈现不规则性。图 4(d)为三种规约算法最终解算出模糊度向量所需时间的累积分布函数图,从中可以得到三种算法的优劣顺序为PGLLL、PLLL和SLLL,但三种算法的效率优劣主要取决于累积概率在0.6以下时三者的差异。

      图  4  静态模式下不同历元的模糊度解算结果

      Figure 4.  Ambiguity Resolution in Different Epochs

      综合图 4的结果,在静态单历元情况下三种算法的解算结果基本与模拟结果一致,因而此处不再对上述结果进行解释。

    • 图 5是采用的车载实验解算的结果。基线长变化范围为0~6 km,接收机型号为南方S82-C,采样间隔为5 s,单历元模糊度解算。图 5图 4中各图对应的顺序一致,从结果可以直观看到,图 5(a)图 5(b)与实验2中现象是一致的,因此此处笔者略去其描述,具体可以参照实验2。从图 5(c)可以看出,PGLLL的搜索候选点个数整体上少于其余两种方法,具有明显的差异性。图 5(d)则说明了PGLLL的最终模糊度解算效率明显优于PLLL算法,同时PLLL的解算结果要优于SLLL。

      图  5  动态模式下不同历元的模糊度解算结果

      Figure 5.  Ambiguity Resolution in Different Epochs

      图 5中三种算法解算效率的差异进行分析,由于此时PGLLL在规约效率和减少搜索候选点数上都具有明显的优势,因而具有较优的解算效果。

    • 本文通过采用基向量的贪心选择和部分列向量元素的规约实现对LLL规约算法的改进。理论和实测数据的验证表明,改进后的方法可以减少基向量的交换次数和尺度规约个数,降低了LLL规约算法的计算复杂度,进而提高了规约效率。采用贪心算法可能使获得的规约基存在一定差异,但该算法对搜索候选点数影响较小,因此改进的算法在整体解算耗时上相较于LLL算法具有一定的优势。此改进算法对模糊度的快速解算具有较好的应用价值。

参考文献 (17)

目录

    /

    返回文章
    返回