平码五不中公式规律
  • / 18
  • 下载费用:30 金币  

基于CHAN算法与改进牛顿迭代的联合时差定位方法.pdf

关 键 ?#21097;?/dt>
基于 CHAN 算法 改进 牛顿 联合 时差 定位 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利?#29275;?/td>

CN201610911307.6

申请日:

2016.10.19

公开?#29275;?/td>

CN106483496A

公开日:

2017.03.08

当前法律状态:

实审

?#34892;?#24615;:

审中

法?#19978;?#24773;: 实质审查的生效IPC(主分类):G01S 5/00申请日:20161019|||公开
IPC分类?#29275;?/td> G01S5/00 主分类?#29275;?/td> G01S5/00
申请人: 河南城建学院; 无锡纳旭测控科?#21152;?#38480;公司
发明人: 韩耀飞; ?#24459;?#23792;; 何国锋; 刘恋; 杨海江; 樊晓虹; 郭蓓蕾; 李佳佳; 陈国振
地址: 467000 河南省平顶山?#34892;?#22478;区龙翔大道
优?#28909;ǎ?/td>
专利代理机构: ?#26412;?#31185;亿知识产权代理事务所(普通合伙) 11350 代理人: 汤东凤
PDF完整版下载: PDF下载
法律状态
申请(专利)?#29275;?/td>

CN201610911307.6

授权公告?#29275;?/td>

|||

法律状态公告日:

2017.04.05|||2017.03.08

法律状态类型:

实质审查的生效|||公开

摘要

本发明公开了一种基于CHAN算法与改进牛顿迭代的联合时差定位方法,使用CHAN算法,得到未知节点位置估计值;将估计值作为牛顿迭代算法的初始值进行迭代,为了限制搜索方向在迭代过程中对海森矩阵进行特征值校正、为了加快搜索速度用三次插值法引入步长因子、?#31181;?#22312;多重根附近收敛速度特别慢甚至失效的现象引入重根系数改进迭代公式;完成对未知节点位置的求解。本发明的牛顿迭代在寻找近似极值点时更接近极值点,定位结果效果好;测量误差均方根值小;迭代次数明显小于牛顿迭代法和修正牛顿迭代法。本发明的方法计算量要小于牛顿迭代法和修正牛顿迭代法的计算量,定位精度也要比其他两种算法精度要高。

权利要求书

1.一种基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在于,所述基于
CHAN算法与改进牛顿迭代的联合时差定位方法使用CHAN算法,得到未知节点位置估计值;
将估计值作为牛顿迭代算法的初始值进行迭代,迭代过程中为了限制搜索方向在迭代过程
中对海森矩阵进行特征值校正、为了加快搜索速度用三次插值法引入步长因子、?#31181;?#22312;多
重根附近收敛速度特别慢甚至失效的现象引入重根系数改进迭代公式;完成对未知节点位
置的求解。
2.如权利要求1所述的基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在
于,所述迭代的步骤为:
1)将用CHAN算法解得位置初始值u0;
2)求海森矩阵在Hu为非正定矩阵的情况下,将矩阵Hu进行特征值分解得:Hu=UΛ
UT,U为特征向量组合的矩阵,Λ=diag{h1,h2},h1,h2由小到大排列,h1,h2,…有如下三种情
况并进行修正:
均为正,即h2>h1>0,此时Hu为正定矩阵,搜索方向l为下降方向,求得的位置解为极小
值点,
均为?#28023;?#21363;h1<h2<0,此时取
一正一?#28023;?#21363;h1<0<h2,取
修正过的海森矩阵表达式为:
3)求步长因子:在牛顿迭代公式中加入步长因子,得并令
构造三次多项式p(λ)=a+bλ+cλ2+dλ3,当λ=0时,令:




求得a、b、c、d的值,进而求得p(λ)的极小值;将三多项式p(λ)的极小值值点作为极
值点的近似;可知则因此步长因子可选为:

4)求重根系数:记重根系数
5)将初始值u0,代入改进的牛顿迭代关系式得到迭代后的位置
uk+1=(x(k+1),y(k+1))(k=1,2,...,N-1);
6)将uk=(x(k),y(k))代入冗余式
中,求出?#29275;絤in(ε0,εi)i=3,4,...,N,ε0为测距精度要求给定的值;将uk+1=(x(k+1),y(k+1))
代入Δk+1=max(|x(k+1)-xk|,|y(k+1)-yk|);
7)判断是否满足要求εi<ε或者Δk+1<Δ,如果满足其中一个条件,则此次迭代到此结
束,输出值为(x(k+1),y(k+1)),否则将此值作为初始值继续迭代,直到满足要求为止。
3.如权利要求1所述的基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在
于,所述MS位置估计值为最小化二次型目标函数,即:
J(u)=(r-f(u))TQ-1(r-f(u));
Q为噪声的正定协方差矩阵,求解u必须求J(u)的最小值,所得到的估计量称为最小二
乘估计值。
4.如权利要求1所述的基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在
于,所述海森矩阵的特征值校正的海森矩阵表达式为:
的对角线上的元素均为正。
5.如权利要求1所述的基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在
于,所述通过三次插值法改进的步长因子为:
其中
6.如权利要求1所述的基于CHAN算法与改进牛顿迭代的联合时差定位方法,其特征在
于,所述重根值改进包括:
是g(u)的m重根,当充分接近uα时,由Taylor展开?#26657;?br /> <mrow> <msup> <mi>g</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <mrow> <mi>m</mi> <mo>!</mo> </mrow> </mfrac> <munderover> <mo>&Sigma;</mo> <mrow> <mi>p</mi> <mo>=</mo> <mn>0</mn> </mrow> <mi>m</mi> </munderover> <msubsup> <mi>C</mi> <mi>m</mi> <mi>p</mi> </msubsup> <msup> <mi>h</mi> <mi>p</mi> </msup> <msup> <mi>k</mi> <mrow> <mi>m</mi> <mo>-</mo> <mi>p</mi> </mrow> </msup> <mfrac> <mrow> <msup> <mo>&part;</mo> <mi>m</mi> </msup> <mi>f</mi> </mrow> <mrow> <mo>&part;</mo> <msup> <mi>x</mi> <mi>p</mi> </msup> <mo>&part;</mo> <msup> <mi>y</mi> <mrow> <mi>m</mi> <mo>-</mo> <mi>p</mi> </mrow> </msup> </mrow> </mfrac> <msub> <mo>|</mo> <mrow> <mo>(</mo> <msub> <mi>x</mi> <mi>&alpha;</mi> </msub> <mo>,</mo> <msub> <mi>y</mi> <mi>&alpha;</mi> </msub> <mo>)</mo> </mrow> </msub> <mo>+</mo> <mi>o</mi> <mrow> <mo>(</mo> <msup> <mi>&rho;</mi> <mrow> <mi>m</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo>)</mo> </mrow> <mo>;</mo> </mrow>
<mrow> <msup> <mi>g</mi> <mrow> <mo>&prime;</mo> <mo>&prime;</mo> </mrow> </msup> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <mrow> <mo>(</mo> <mi>m</mi> <mo>-</mo> <mn>1</mn> <mo>)</mo> <mo>!</mo> </mrow> </mfrac> <munderover> <mo>&Sigma;</mo> <mrow> <mi>p</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>m</mi> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msubsup> <mi>C</mi> <mrow> <mi>m</mi> <mo>-</mo> <mn>1</mn> </mrow> <mi>p</mi> </msubsup> <msup> <mi>h</mi> <mi>p</mi> </msup> <msup> <mi>k</mi> <mrow> <mi>m</mi> <mo>-</mo> <mn>1</mn> <mo>-</mo> <mi>p</mi> </mrow> </msup> <mfrac> <mrow> <msup> <mo>&part;</mo> <mi>m</mi> </msup> <mi>f</mi> </mrow> <mrow> <mo>&part;</mo> <msup> <mi>x</mi> <mi>p</mi> </msup> <mo>&part;</mo> <msup> <mi>y</mi> <mrow> <mi>m</mi> <mo>-</mo> <mi>p</mi> </mrow> </msup> </mrow> </mfrac> <msub> <mo>|</mo> <mrow> <mo>(</mo> <msub> <mi>x</mi> <mi>&alpha;</mi> </msub> <mo>,</mo> <msub> <mi>y</mi> <mi>&alpha;</mi> </msub> <mo>)</mo> </mrow> </msub> <mo>+</mo> <mi>o</mi> <mrow> <mo>(</mo> <msup> <mi>&rho;</mi> <mi>m</mi> </msup> <mo>)</mo> </mrow> <mo>;</mo> </mrow>
式中,
令在u充分接近uα时即(h,k)→(0,0),则?#26657;?br /> <mrow> <mfrac> <mrow> <mi>l</mi> <mi>n</mi> <mo>|</mo> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>|</mo> </mrow> <mrow> <mi>l</mi> <mi>n</mi> <mo>|</mo> <mi>g</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>|</mo> </mrow> </mfrac> <mo>&RightArrow;</mo> <mi>m</mi> <mo>;</mo> </mrow>
定义函数显然有Ω(u)→m(当(h,k)→(0,0)时),因此使用迭代公式:
<mrow> <mi>u</mi> <mo>=</mo> <msub> <mi>u</mi> <mn>0</mn> </msub> <mo>-</mo> <mi>&lambda;</mi> <mi>&Omega;</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <msubsup> <mover> <mi>H</mi> <mo>~</mo> </mover> <msub> <mi>u</mi> <mn>0</mn> </msub> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msubsup> <msub> <mi>G</mi> <msub> <mi>u</mi> <mn>0</mn> </msub> </msub> <mo>.</mo> </mrow>
7.一种利用权利要求1~6?#25105;?#19968;项所述基于CHAN算法与改进牛顿迭代的联合时差定
位方法的定位系统。

说明书

基于CHAN算法与改进牛顿迭代的联合时差定位方法

技术领域

本发明属于定位技术领域,尤其涉及一种基于CHAN算法与改进牛顿迭代算法联合
的到达时间差定位方法。

背景技术

随着现代科技的进步,定位技术越来越受到重视。在定位技术中,系统的定位精度
的提升也受到重视,除此之外算法的计算时间也越来越受到重视。除了提高硬件的性能,最
重要的是改进算法。常用的迭代求解方法?#26657;篢aylor算法、卡尔曼滤波算法等,主要缺点是
其收敛性非常?#35272;?#20110;初始位置的精度。当初始位置选择不好的时候,迭代时容易陷入局部
极小值点,而?#20063;?#33021;保证收敛性。牛顿迭代法虽然也需要初始估计位置,但它收敛速度比较
快,在满足一定的定位精度要求情况下,可以解决迭代计算时间的问题,可是当初始值远离
最优解时,效率很低,而且好的优化算法并不?#35272;?#31934;确的搜索过程。

综上所述,牛顿迭代算法会出现?#35272;?#21021;始值精确度和迭代次数过多以及在多重根
附近收敛速度特别慢甚至失效的问题。针对这一问题,在牛顿迭代算法的基础上,先对海森
矩阵非正定时迭代方向不正确导致算法不收敛甚至失效对海森矩阵进行特征值改进;然后
在初始值离最优解很远时计算量更大、迭代效率很低时引入步长因子;最后在单重根附近
时收敛速度快,但在多重根附近收敛速度特别慢甚至失效时,在多重根处引入重根系数。

发明内容

本发明的目的在于提供一种基于CHAN算法与改进牛顿迭代的联合时差定位方法,
旨在解决牛顿迭代算法中会出现?#35272;?#21021;始值精确度和迭代次数过多以及在多重根附近收
敛速度特别慢甚至失效的问题。

本发明是这样实现的,一种基于CHAN算法与改进牛顿迭代的联合时差定位方法,
所述基于CHAN算法与改进牛顿迭代的联合时差定位方法使用CHAN算法,得到未知节点位置
估计值;将估计值作为牛顿迭代算法的初始值进行迭代,迭代过程中对海森矩阵进行特征
值校正、通过三次插值法引入步长因子、对有多重根值的迭代公式改进;完成未知节点位置
求解。

所述迭代的步骤为:

1)将用CHAN算法解得位置初始值u0;

2)求海森矩阵在Hu可能为非正定矩阵的情况下,搜索量的搜索方
向不一定是准确的,可能导致算法不收敛甚至失效,将矩阵Hu进行特征值分解得:Hu=UΛ
UT,U为特征向量组合的矩阵,Λ=diag{h1,h2}(h1,h2由小到大排列),h1,h2,…有如下三种
情况并进行修正:

a.均为正,即h2>h1>0,此时Hu为正定矩阵,搜索方向l为下降方向,求得的位置解
为极小值点,

b.均为?#28023;?#21363;h1<h2<0,此时取

c.一正一?#28023;?#21363;h1<0<h2,取

经修正过的海森矩阵的特征值均大于0,从而可以得出无论给定的何种初始值,经
修正后的海森矩阵都是正定矩阵,使得搜索量l的搜索方向为下降方向,进而使得搜索点更
接近极小值点,修正过的海森矩阵表达式为:

3)求步长因子:在牛顿迭代公式中加入步长因子,得并
令构造三次多项式p(λ)=a+bλ+cλ2+dλ3,当λ=0时,令





可以求得a、b、c、d的值,进而求得p(λ)的极小值。将三多项式p(λ)的极小值值点作
为极值点的近似。可知则因此步长因子可选
为:


4)求重根系数:记重根系数

5)将初始值u0,代入改进的牛顿迭代关系式得到迭代后的
位置uk+1=(x(k+1),y(k+1))(k=1,2,...,N-1);

6)将uk=(x(k),y(k))代入冗余式


中,求出ε0为测距精度要求给定的值;将uk+1=(x(k+1),
y(k+1))代入Δk+1=max(|x(k+1)-xk|,|y(k+1)-yk|);

7)判断是否满足要求εi<ε或者Δk+1<Δ,如果满足其中一个条件,则此次迭代到
此结束,输出值为(x(k+1),y(k+1)),否则将此值作为初始值继续迭代,直到满足要求为止。

进一步,所述MS位置估计值为最小化二次型目标函数,即:

J(u)=(r-f(u))TQ-1(r-f(u));

Q为噪声的正定协方差矩阵,求解u必须求J(u)的最小值,所得到的估计量称为最
小二乘估计值。

进一步,所述海森矩阵的特征值校正的海森矩阵表达式为:

的对角线上的元素均为正。

进一步,所述通过三次插值法改进的步长因子为:

其中

进一步,所述重根值改进包括:

是g(u)的m重根,当充分接近uα时,由Taylor展开?#26657;?br />



式中,

令在u充分接近uα时即(h,k)→(0,0),则?#26657;?br />


定义函数显然有Ω(u)→m(当(h,k)→(0,0)时),因此使用迭代
公式:


本发明的另一目的在于提供一种利用所述基于CHAN算法与改进牛顿迭代的联合
时差定位方法的定位系统。

本发明提供的基于CHAN算法与改进牛顿迭代的联合时差定位方法,将高度非线性
问题装化为最小二乘法问题,在利用CHAN算法求解初始解的基础上利用牛顿迭代算法迭代
求解,迭代过程?#34892;?#27491;海森矩阵的特征值,然后加快迭代时间采用三次插值法引入步长因
子,最后对有多重根植点进行改进迭代公式。最后通过仿真验证了该算法具有较好的定位
性能。

在仿真图3中,当噪音标准差为3m时,几种基于牛顿算法的修正与改进的路径仿真
中,可以看出基本牛顿迭代算法定位误差最差,而在修正牛顿迭代的基础上作出改进的算
法定位效果最好。这是因为改进的牛顿迭代在寻找近似极值点时更接近极值点,所以定位
结果效果最好。

在图4中,在不同噪声均方根值的情况下,基本牛顿算法的测量误差均方根值最
大,对修正牛顿迭代的测量误差均方根值最小。对每种算法来说,测量误差均方根值随着噪
声误差均方根的增大而逐渐增大。在噪声误差均方根值为0.5到3之间几种算法的测量误差
均方根值相差不是很大,而在噪声误差均方根值大于3后基本牛顿迭代算法比另两种算法
的测量误差均方根明显有所增加。

图5为各算法随测量误差变化的平均迭代次数的统计结果。随着测量误差的增加,
本发明改进的算法(对修正牛顿迭代的改进算法)的平均迭代次数保持最小,迭代次数明显
小于牛顿迭代法和修正牛顿迭代法,在图3中它的测量误差均方根值也保持最小。这说明本
发明改进的方法计算量要小于牛顿迭代法和修正牛顿迭代法的计算量,而且本发明改进的
方法定位精度也要比其他两种算法精度要高。

附图说明

图1是本发明实施例提供的基于CHAN算法与改进牛顿迭代的联合时差定位方法流
程图。

图2是本发明实施例提供的时差定位的示意图。

图3是本发明实施例提供的几种算法定位结果仿真示意图。

图4是本发明实施例提供的几种算法定位误差仿真示意图。

图5是本发明实施例提供的几种算法定位平均迭代次数。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白,以下结合实施例,对本发明
进行进一步详细说明。应当理解,此处所描述的具体实施例仅仅用以解释本发明,并不用于
限定本发明。

下面结合附图对本发明的应用原理作详细的描述。

如图1所示,本发明实施例提供的基于CHAN算法与改进牛顿迭代的联合时差定位
方法包括以下步骤:

S101:将高度非线性问题装化为最小二乘法问题,在利用CHAN算法求解初始解;

S102:在牛顿迭代过程?#34892;?#27491;海森矩阵的特征值

S103:加快迭代时间采用三次插值法引入步长因子;

S104:最后对有多重根植点引入重根系数进行改进迭代公式。

S105?#21495;?#26029;是否满足条件:否满足要求εi<ε或者Δk+1<Δ。

S106:直到满足要求,输出结果。

所述迭代的步骤为:

1)将用CHAN算法解得位置初始值u0;

2)求海森矩阵在Hu可能为非正定矩阵的情况下,搜索量的搜索方
向不一定是准确的,可能导致算法不收敛甚至失效,将矩阵Hu进行特征值分解得:Hu=UΛ
UT,U为特征向量组合的矩阵,Λ=diag{h1,h2}(h1,h2由小到大排列),h1,h2,…有如下三种
情况并进行修正:

a.均为正,即h2>h1>0,此时Hu为正定矩阵,搜索方向l为下降方向,求得的位置解
为极小值点,

b.均为?#28023;?#21363;h1<h2<0,此时取

c.一正一?#28023;?#21363;h1<0<h2,取

经修正过的海森矩阵的特征值均大于0,从而可以得出无论给定的何种初始值,经
修正后的海森矩阵都是正定矩阵,使得搜索量l的搜索方向为下降方向,进而使得搜索点更
接近极小值点,修正过的海森矩阵表达式为:

3)求步长因子:在牛顿迭代公式中加入步长因子,得并
令构造三次多项式p(λ)=a+bλ+cλ2+dλ3,当λ=0时,令





可以求得a、b、c、d的值,进而求得p(λ)的极小值。将三多项式p(λ)的极小值值点作
为极值点的近似。可知则因此步长因子可选
为:


4)求重根系数:记重根系数

5)将初始值u0,代入改进的牛顿迭代关系式得到迭代后的
位置uk+1=(x(k+1),y(k+1))(k=1,2,...,N-1);

6)将uk=(x(k),y(k))代入冗余式
中,求出?#29275;絤in(ε0,εi)i=3,4,...,
N,ε0为测距精度要求给定的值;将uk+1=(x(k+1),y(k+1))代入Δk+1=max(|x(k+1)-xk|,|y(k+1)-yk
|);

7)判断是否满足要求εi<ε或者Δk+1<Δ,如果满足其中一个条件,则此次迭代到
此结束,输出值为(x(k+1),y(k+1)),否则将此值作为初始值继续迭代,直到满足要求为止。

下面结合附图对本发明的应用原理作进一步的描述。

1时差定位数学模型

假设有M个基站呈随机分布状态,基于时差定位的示意图如图1所示。图中,u=[x,
y]T为未知节点MS待估计位置坐标;si=[xi,yi]T为第i个已知节点BS的实际位置坐标。MS到
BSi的之间的距离为


其中,||||表示模。

ti为电信号从MS到BSi的LOS传播时间,tei为从MS到BSi的的NLOS超量时延,它为一
个正值的随机变量,各tei之间相互独立,当电信号从MS到BSi的是LOS传播时tei=0。不失一
般性,选取s1作为参考接收站,可以得到MS到BSi的时差定位方程为:



其中,为MS到BS1、BSi之间LOS传播的TDOA真值;tei1=tei-te1为NLOS传播给
TDOA测量引入的误差,其均值一般都不为零;ni1为系统测量误差,相对NLOS误差tei1来说很
小可以矫正,并且它与tei1相互独立。用c同时乘以式(2)两端,可得距离差定位方程为:


其中,c为电信号传播速度;为从MS到BS1、BSi的LOS传播距离差;ηi1=
ctei1+cni1为NLOS传播给TDOA测量引入的距离误差与测量误差之和,满足独立分布。令Ri1
(u)=ri0-r10,将式(3)写成矢量形式为:

r=R(u)+η (4)

其中,r=[r21,…,rM1]T;R(u)=[R21(u),…,RM1(u)]T;η=[η21,…,ηM1]T,为方便起
见,认为此噪声η服从均值为零、正定协方差矩阵为Q的高斯分布。

Q=E[(η-E[η])(η-E[η])T] (5)

其中,E[]表示期望值。

根据式(4)可得似然函数为:


其中,Q-1是Q的逆矩阵,因为Q是对称正定矩阵,其逆存在。最大似然估计是最大化
(6)的值,因此可以转化为最小化二次型目标函数,即:

J(u)=(r-R(u))TQ-1(r-R(u)) (7)

根据式(7)可知,求解u必须求J(u)的最小值,所得到的估计量称为最小二乘估计
值,且N-1可以视为一个加权系数矩阵。但用解析方法求解高度非线性函数非常困?#36873;?#22240;此,
本发明采用整体偏移法求解此非线性方程,确定未知节点MS的位置坐标值。

2牛顿迭代算法

牛顿迭代的本质是将非线性方程逐步演变为一种线性方程来求解,方法是使用函
数的泰勒级数的前面几项来寻找方程的根。

根据牛顿迭代法的条件,根据式(3)和(4)方程建立定位方程组:

g(u)=R(u)-r=0 (8)

若假设u为单变量时,求方程的解的方法是在迭代点u0处使用二级泰?#29031;?#24320;,然后
去线性部分,即:

g(u)=g(u0)+(u-u0)g'(u0) (9)

令式(9)等于0,则?#26657;?br />


经过不断迭代,可以求出迭代公式:


在本发明中解决的是极小值问题,所以可以转换成求其导函数零点问题,即求g'
(u)=0的解。

把g(u)用泰勒公式展开到二阶,即:


式(12)中左边与g(u)近似相等,令:


然后对Δu求导,得到:

g'(u)+g”(u)Δu=0 (14)

解得:


然后递推可以得到迭代公式:


以上推断是为单变量进行?#33268;郟?#32780;设定初始值u=(xy)T时则为多变量,在解决牛
顿迭代的优化问题时引入雅可比矩阵和海森矩阵。

从式(8)中选取前2个方程建立如下:


从式(9)中求得的梯度矢量和海森矩阵分别为:


式(8)的梯度矢量和海森矩阵分别为:


把式Gu和Hu代入式(16)中,得到牛顿迭代的方程为:


由此推论,设定初始值u0=(x0,y0)T时牛顿迭代方程为:


式中,和分别为函数在给定初始值u0下的梯度矢量和海森矩阵

3改进的牛顿迭代法算法

牛顿迭代算法有容易发散的问题,对在多重根附近收敛速度特别慢甚至失效的现
象进行改进,提出改进的牛顿迭代算法。

3.1修正海森矩阵

牛顿迭代算法,在估计出初始值后代入牛顿迭代的关系式,直到满足给定的精度
要求。假设函数g(u)在u处二阶连续可导,则它的海森矩阵可能出现三种情况:

1)如果Hu是正定矩阵,则此时u处于局部极小值点;

2)如果Hu是负定矩阵,则此时u处于局部极大值点;

3)如果Hu是不定矩阵,则此时u处不是极值点。

在Hu可能为非正定矩阵的情况下,式(21)中搜索量的搜索方向不一定
是准确的,可能导致算法不收敛甚至失效。针对这个问题,?#25910;?#25552;出基于CHAN算法的修正牛
顿迭代时差定位算法。

将矩阵Hu进行特征值分解得:

Hu=UΛUT (22)

式中,U为特征向量组合的矩阵,Λ=diag{h1,h2}(h1,h2由小到大排列)。

在式(21)中h1,h2,…有如下三种情况并进行修正:

1)均为正,即h2>h1>0,此时Hu为正定矩阵,搜索方向l为下降方向,求得的位置解
为极小值点,

2)均为?#28023;?#21363;h1<h2<0,此时取

3)一正一?#28023;?#21363;h1<0<h2,取

经修正过的海森矩阵的特征值均大于0,从而可以得出无论给定的何种初始值,经
修正后的海森矩阵都是正定矩阵,使得搜索量l的搜索方向为下降方向,进而使得搜索点更
接近极小值点,修正过的海森矩阵表达式为:


从式(23)可以看出,虽然给定?#25105;?#21021;始值都能使经过修正的海森矩阵正定且使搜
索点更接近极小值点,但是想精确搜索且计算量小,也?#35272;?#20110;初始值的精确。当初始值和最
优解相差甚远时,进行迭代求解,计算量大效?#23454;汀?br />

3.2引入步长因子

在正确的搜索方向上,搜索的方向与大小取决于搜索量经过海森矩阵
修正之后搜索方向已经确定,而搜索大小还取决于搜索量l的值。这种搜索方法为了精确搜
索还是需要大量的迭代计算,尤其是在初始值离最优解很远时计算量更大,这种搜索效率
很低。为了使每次迭代过程中搜索方向更接近极小值,引入步长因子λ,使搜索量修改为
而步长因子λ的选取可以利用三次插值法计算。

将迭代方程(21)加入步长因子,得:


将(22)代入函数g(u),并令构造三次多项式:

p(λ)=a+bλ+cλ2+dλ3 (25)

当λ=0时,令:





由(26)~(29)可以求得a、b、c、d的值,进而求得p(λ)的极小值。将三多项式p(λ)的
极小值值点作为极值点的近似。

结合(19)可知:则因此步长因子可选为:


3.3重根值改进

牛顿迭代法事实上是一种特殊的不动点迭代,在单重根附近时收敛速度快,但是
在多重根附近收敛速度特别慢甚至失效。

为了提高牛顿迭代法求非线性方程重根的收敛速度,常见的两种修正的牛顿迭代
格式如下:

1)记对f(u)用牛顿迭代法,即其中Gf(u)、Hf(u)
分别为梯度矢量和海森矩阵;

2)如果事先知道根的重数m(m≥2),则

这两种格式都具有二阶收敛速度,但是在应用中?#21152;?#19968;定的局限性。因为格式1)
要求计算f(u)的梯度矢量和海森矩阵,这要计算g(u)三阶偏导增加了计算工作量;而格式
2)则必须事先知道根的重数,在实?#35270;?#29992;中很难做到。为此做出如下改进:

设是g(u)的m重根,当充分接近uα时,由Taylor展开
?#26657;?br />



式中,

令在u充分接近uα时即(h,k)→(0,0),则?#26657;?br />


定义函数显然有Ω(u)→m(当(h,k)→(0,0)时),因此使用迭代
公式:


用式(33)可以提高收敛速度,在一般的牛顿迭代过程中,用式(21)计算g'(u)、g”
(u)之后,再计算Ω(u)是不会花费很大代价的,因此计算Ω(u)是值得的。

4算法描述

修正牛顿迭代算法过程:

1)将用CHAN算法解得位置并判断是否满足?#24066;?#35823;差,若满足迭代停止;若不满足,
将它设为初始值u0,代入牛顿迭代关系式,构造搜索量,根据式(23)求得海森矩阵根据
式(30)计算步长因子λ,根据求式(33)出迭代后的位置uk+1=(x(k+1),y(k+1))(k=1,2,...,N-
1);

2)将uk=(x(k),y(k))代入冗余式
中,求出?#29275;絤in(ε0,εi)i=3,4,...,
N,ε0为测距精度要求给定的值。将uk+1=(x(k+1),y(k+1))代入Δk+1=max(|x(k+1)-xk|,|y(k+1)-yk
|);

3)判断是否满足要求εi<ε或者Δk+1<Δ,如果满足其中一个条件,则此次迭代到
此结束,输出值为(x(k+1),y(k+1)),否则将此值作为初始值继续上面的迭代步骤,直到满足要
求为止。

下面结合算法仿真与性能分析对本发明的应用效果作详细的描述。

在本发明中,对各个算法的定位性能采用位置估计的均方根误差进行衡量,其定
义式为:


本发明在Matlab R2010a环境下仿真。假设小区为100×100的区域,参与定位的基
站为4个,基站分别为(0,0)、(0,100)、(100,100)、(100,0)。?#24065;?#21160;台以4m/s的速度做匀速
直线运动,采样时间为1s,?#20197;?#22768;标准差为3m时,基于牛顿的几种算法路径定位的结果仿真
图如图3。

在仿真图3中,当噪音标准差为3m时,几种基于牛顿算法的修正与改进的路径仿真
中,可以看出基本牛顿迭代算法定位误差最差,而在修正牛顿迭代的基础上作出改进的算
法定位效果最好。这是因为改进的牛顿迭代在寻找近似极值点时更接近极值点,所以定位
结果效果最好。

为了进一步明显看出几种算法的定位效果,再用几种算法在不同噪声均方根值分
别为0.5、1、1.5、2、2.5、3、3.5、4、4.5、5、5.5、6的情况下进行仿真,每次实验独立进行200
次。测量误差比较的统计结果仿真图如图4。

在图4中,在不同噪声均方根值的情况下,基本牛顿算法的测量误差均方根值最
大,对修正牛顿迭代的测量误差均方根值最小。对每种算法来说,测量误差均方根值随着噪
声误差均方根的增大而逐渐增大。在噪声误差均方根值为0.5到3之间几种算法的测量误差
均方根值相差不是很大,而在噪声误差均方根值大于3后基本牛顿迭代算法比另两种算法
的测量误差均方根明显有所增加。

这三种算法不仅在定位精度上有一定的差别,在迭代次数上也有差别,平均迭代
次数的统计结果如图5。

图5为各算法随测量误差变化的平均迭代次数的统计结果。随着测量误差的增加,
本发明改进的算法(对修正牛顿迭代的改进算法)的平均迭代次数保持最小,迭代次数明显
小于牛顿迭代法和修正牛顿迭代法,在图3中它的测量误差均方根值也保持最小。这说明本
发明改进的方法计算量要小于牛顿迭代法和修正牛顿迭代法的计算量,而且本发明改进的
方法定位精度也要比其他两种算法精度要高。

以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精
神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明的保护范围之内。

关于本文
本文标题:基于CHAN算法与改进牛顿迭代的联合时差定位方法.pdf
链接地址:http://www.pqiex.tw/p-5994827.html
关于我们 - 网站声明 - 网?#38236;?#22270; - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 广西11选5 全球股票指数stock 股票涨跌原理知识分享 湖南幸运赛车如何办理 快乐飞艇是国家发行的吗 北京赛车冠亚最大遗漏 天天棋牌赚钱是真的吗 老彩民微信 分析 云南十一选五今天遗漏