一种基于牛顿插值的蒙特卡罗移动节点定位算法

摘要

本发明公开了一种基于牛顿插值的蒙特卡罗移动节点定位算法，方法如下：预测阶段：采用牛顿插值方法估计当前时刻节点的运动速度和方向；滤波阶段：根据t时刻观测值位置信息，滤除不满足条件的样本，并根据权值更新剩余样本中的位置数据，使用n

说明书

技术领域

本发明涉及无线传感器网络中移动节点定位算法技术领域，具体来说是一种基于牛顿插值的蒙特卡罗移动节点定位算法。

背景技术

近年来，随着微机电技术和无线通信技术的快速发展，促使无线传感器网络作为一种全新的信息获取及数据处理技术应用在智慧城市、智慧旅游、智能家居、智慧养老等众多领域。

无线传感器网络的应用无不依赖于节点的位置信息，而移动节点定位与静止节点定位相对而言，其技术难度更为繁杂，也是基于位置服务的一项重要的技术，因此，如何充分利用节点的运动信息，设计出适用于移动无线传感器网络环境的定位跟踪算法，已成为众多研究学者研究的一个热点问题，此研究具有重要的实际意义和应用价值。

Hu和Evans首次提出了基于贯序蒙特卡罗定位(Sequential Monte CarloLocalization,SMCL)算法，在移动传感器网络节点定位方面取得了良好效果,Frank等人，将蒙特卡罗算法(Monte Carlo Localization，MCL)最早应用于机器人定位，其核心是在Bayes滤波位置估计的基础上，用加权粒子集来估计移动机器人在状态空间的位置分布，但Bayes滤波将先前测量的数据和当前测量的数据相对独立,Aline Baggio等人提出了蒙特卡罗盒定位(Monte Carlo Localization Boxed,MCB)算法，此算法是对MCL算法的改进，通过构建信标盒和采校盒，将信标节点通信范围内的重叠区域作为采样范围，优化了采样区域，提高了定位性能,但当观测数据分布在锚节点盒子的比重很小时，MCB算法的采样效果不佳,然而，采样成功率，是衡量移动节点定位性能的主要指标之一,基于接收的信号强度指示(Received Signal Strength Indication,RSSI)定位算法具有成本低、容易实现等优点，在对精度要求不高的实际定位系统中得到广泛应用,如今，由于大多数射频芯片本身都具有获取接收射频数据的RSSI信息，而无需任何额外的测距硬件，可见，RSSI的测量是价廉且易实现，但由于存在多径、干扰、遮挡等因素，导致单一RSSI的定位算法精度不高，往往达不到精确定位的要求,现在，诸多学者与研究人员，在充分研究RSSI的基础上，发挥其优势，即利用测距信息辅助来优化非测距定位，提出基于测距辅助的蒙特卡罗定位算法，该算法使用RSSI统计模型获取的距离信息作为蒙特卡罗算法滤波阶段的观测值，显著提高了MCL算法的定位精度，但也存在计算量较大，节点能量损耗严重等不足。

发明内容

本发明的目的是为了解决现有技术中的定位精度差、定位效果不好的缺陷，提供一种基于牛顿插值的蒙特卡罗移动节点定位算法来解决上述问题。

为了实现上述目的，本发明的技术方案如下：本发明公开了一种基于牛顿插值的蒙特卡罗移动节点定位算法，方法如下：

(1)、预测阶段：采用牛顿插值方法估计当前时刻节点的运动速度和方向；

(2)、滤波阶段：根据t时刻观测值位置信息，滤除不满足条件的样本，并根据权值更新剩余样本中的位置数据，使用n_t～p(n_t|m_t)描述在给定位置的RSSI>

(3)、重采样阶段

预测后的粒子在经过观察阶段及加权计算之后，很多粒子的权值都非常接近0，需要重新进行位置更新和加权计算，并多次迭代之后才能获得一定数量权值接近1的粒子，为了加速获得权值接近1的粒子，采用基于重要性权值优化的粒子滤波算法，通过引入一个影响因子来优化粒子的重要性权值，进行重采样过程中，更多的粒子将被复制，有效地避免粒子贫化，

基于每次重采样过程中对归一化之后的权值加一个影响因子α(0＜α＜1)，粒子的权值变为再对权值进行归一化后t时刻第i个粒子的权值即：

则每个粒子的权值进行了重新调整，并且权值小的粒子在权值优化后得到提高，相反得到降低。

作为优选，所述的步骤(1)中，具体步骤如下：运动预测基于节点运动轨迹的平滑性，通过前几个时刻的位置估计当前时刻的位置，从而获得当前时刻的运动方向和运动速度，牛顿插值方法具有承袭性的差商,如下式：

牛顿插值方法中的均差具有对称性，调换节点间的位置，均差的值与节点的排列顺序无关，适合于无线传感器网络中节点位置的移动，

假设前3个时刻的位置分别为(x_t-3，y_t-3)，(x_t-2，y_t-2)，(x_t-1，y_t-1)，对x，y方向的数据进行二次牛顿插值得：

x_t＝x_t-3+3×(x_t-2-x_t-3)+3×(x_t-1-2x_t-2+x_t-3)>

y_t＝y_t-3+3×(y_t-2-y_t-3)+3×(y_t-1-2y_t-2+y_t-3)>

根据t时刻的位置可以估算出当前时刻的运动速度和运动方向为：

因此，t时刻的位置预测方程为：

式中，n_t为高斯噪声，

作为优选，所述的步骤(2)中，具体步骤为：设定位置目标节点从采样区域中采集一组样本其中_N是样本数量，每一个样本都存在一个非负权值其定义为：

式中表示样本i在t时刻的权值，根据观测分布，其计算公式为

根据样本和对应权值的集合可以得到节点位置的后验分布为：

式中，δ(·)为脉冲函数，

通过节点位置预测和权值更新的反复计算之后，可得到最终的后验分布 p(m_t|n_1：t)。

作为优选，所述的步骤(3)中，采用下述方法证明步骤(3)的有效性：

假设t时刻未进行归一化的粒子集为利用(18)对权值进行归一化

即：

因为所以可以假设归一化后的权值关系为经过优化后的权值为：

则

由于且(0＜α＜1)

所以

同理：

所以

表明权值小的粒子权值在权值优化后权值增大，在对粒子集进行重新采样过程中，更多的粒子将被复制，有效地避免粒子退化。

本发明解决了RSSI-MCL算法中的：

(1)、在基于RSSI-MCL算法的预测阶段，k时刻的位置概率分布只与k-1时刻的位置以及最大、最小速度有关，没有考虑到k-1时刻之前运动情况的对当前节点的影响；

(2)、RSSI-MCL算法运动模型以节点的当前位置确定节点的运动方向，该算法认为在不同时间段内的运动是相互独立的，有可能导致节点有一些不切实际的运动行为；

(3)在RSSI-MCL定位算法迭代计算位置的后验分布阶段，筛选有效粒子的过程较为缓慢。

本发明相比现有技术具有以下优点：

(1)、本发明采用牛顿插值方法的承袭性，承袭先前移动节点的历史轨迹预测机制来估算出当前时刻移动节点的运动速度；

(2)、本发明在随机中间节点运动模型的基础上,对节点的运动模型进行修正，对当前移动节点的运动方向进行预测；

(3)、本发明采用优化权值策略来加速算法抽样有效粒子的过程。

附图说明

图1显示的是MCL定位算法的拓扑图；

图2显示的是RSSI-MCL定位算法的拓扑图；

图3显示的是RSSI-IMCL定位算法的拓扑图；

图4为锚节点个数对定位误差对比分析的示意图；

图4.1为MCL定位算法、RSSI-MCL定位算法、RSSI-IMCL定位算法的RWP运动模型图；

图5为测距误差对定位误差的对比分析的示意图；

图6为定位误差与运动速度的对比分析的示意图；

图7为优化的粒子的运动模型的示意图。

具体实施方式

为使对本发明的结构特征及所达成的功效有更进一步的了解与认识，用以较佳的实施例及附图配合详细的说明，说明如下：

本发明公开了一种基于牛顿插值的蒙特卡罗移动节点定位算法，方法如下：

(1)、预测阶段：采用牛顿插值方法估计当前时刻节点的运动速度和方向；

(2)、滤波阶段：根据t时刻观测值位置信息，滤除不满足条件的样本，并根据权值更新剩余样本中的位置数据，使用n_t～p(n_t|m_t)描述在给定位置的RSSI>

(3)、重采样阶段

预测后的粒子在经过观察阶段及加权计算之后，很多粒子的权值都非常接近0，需要重新进行位置更新和加权计算，并多次迭代之后才能获得一定数量权值接近1的粒子，为了加速获得权值接近1的粒子，采用基于重要性权值优化的粒子滤波算法，通过引入一个影响因子来优化粒子的重要性权值，进行重采样过程中，更多的粒子将被复制，有效地避免粒子贫化，

基于每次重采样过程中对归一化之后的权值加一个影响因子α(0＜α＜1)，粒子的权值变为再对权值进行归一化后t时刻第i个粒子的权值即：

则每个粒子的权值进行了重新调整，并且权值小的粒子在权值优化后得到提高，相反得到降低。

作为优选，所述的步骤(1)中，具体步骤如下：运动预测基于节点运动轨迹的平滑性，通过前几个时刻的位置估计当前时刻的位置，从而获得当前时刻的运动方向和运动速度，牛顿插值方法具有承袭性的差商,如下式：

牛顿插值方法中的均差具有对称性，调换节点间的位置，均差的值与节点的排列顺序无关，适合于无线传感器网络中节点位置的移动，

假设前3个时刻的位置分别为(x_t-3，y_t-3)，(x_t-2，y_t-2)，(x_t-1，y_t-1)，对x，y方向的数据进行二次牛顿插值得：

x_t＝x_t-3+3×(x_t-2-x_t-3)+3×(x_t-1-2x_t-2+x_t-3)(11)

y_t＝y_t-3+3×(y_t-2-y_t-3)+3×(y_t-1-2y_t-2+y_t-3)>

根据t时刻的位置可以估算出当前时刻的运动速度和运动方向为：

因此，t时刻的位置预测方程为：

式中，n_t为高斯噪声，

作为优选，所述的步骤(2)中，具体步骤为：设定位置目标节点从采样区域中采集一组样本其中N是样本数量，每一个样本都存在一个非负权值其定义为：

式中表示样本i在t时刻的权值，根据观测分布，其计算公式为

根据样本和对应权值的集合可以得到节点位置的后验分布为：

式中，δ(.)为脉冲函数，

通过节点位置预测和权值更新的反复计算之后，可得到最终的后验分布 p(m_t|n_1：t)。

作为优选，所述的步骤(3)中，采用下述方法证明步骤(3)的有效性：

假设t时刻未进行归一化的粒子集为利用(18)对权值进行归一化

即：

因为所以可以假设归一化后的权值关系为经过优化后的权值为：

则

由于且(0＜α＜1)

所以

同理：

所以

表明权值小的粒子权值在权值优化后权值增大，在对粒子集进行重新采样过程中，更多的粒子将被复制，有效地避免粒子退化。

如图1-3所示，本发明使用MATLAB工具，在一个200m×200m的矩形平面区域进行。设定40个信标节点随机分布，位置固定，坐标已知；80个目标节点随机移动，方向速度随机，且移动速度不超过预设的上限，同样因为如此，本文采用RWP运动模型，如图4.1。本文网络中的参数设定如下：节点的最大移动速度取50m/s，信标节点和目标节点的通信半径r都取50m。

参照图1-3，从图1中可见，估计节点的位置在目标节点周围；如图2可以看出，所估计的节点位置，都在目标节点附近，在横坐标为6-10的范围内尤为明显；从图3可以看出，改进的RSSI-MCL定位算法所估计的节点位置几乎和目标节点的位置是重合的，相对于RSSI-MCL定位算法和MCL定位算法，表现出更好的预测效果。

参照图4，锚节点个数对定位误差对比分析

如图2是MCL定位算法、RSSI-MCL定位算法、RSSI-IMCL定位算法定位误差随锚节点个数变化的曲线，随着锚节点个数的增加，三种定位算法的定位误差都在减小。当锚结点在20以内时，3种算法的定位误差波动较大。当锚节点个数接近40时，3种算法的定位误差趋于稳定，且三种算法误差也较接近，但是改进的 RSSI-MCL定位算法略优于另外两种算法。

参照图5，测距误差对定位误差的对比分析

如图5是MCL定位算法、RSSI-MCL定位算法、RSSI-IMCL定位算法定位误差随测距误差变化的曲线，随着测距误差的增大，三种算法的定位误差也都在增加，但是可以看出RSSI-MCL定位算法明显优于另外两种算法。当测距误差在0.1和 0.2之间时，定位误差最小，随后定位误差逐渐增大，所以测距误差在0.1和0.2 之间时定位性能最优。测距误差在0.3之后，定位误差开始上升。

定位误差与运动速度的对比分析

参照图6，定位误差与运动速度的对比分析，图6是MCL定位算法、RSSI-MCL定位算法、RSSI-IMCL定位算法定位误差随粒子运动速度变化的曲线，如图6可以看出：MCL定位算法和RSSI-MCL定位算法在运动速度20时误差最小，随后随着运动速度的增加，误差也在加大。主要是因为节点速度增大，下一个节点位置分布区域增大，较难过滤掉不符合条件的节点，所以误差增大。而改进的RSSI-MCL 定位算法随着速度的增大定位误差相对稳定，主要是由于基于历史轨迹的预测，和对粒子权值优化，更新粒子集的结果。

参照图7，RSSI－MCL定位算法中采用的随机路点移动模型(Random Waypointmobility model,RWP)，它对节点的硬件要求不高，但移动路径的随机性较大。

如图7所示：n_t-2,n_t-1分别表示前两个时刻节点的位置，节点n_t-1首先在场景内随机选取n_t节点作为即将到达的目标位置，并以随机选定的速度V∈[Vmin,>t-1与v_t的夹角。不同时间段内的运动是相互独立的，这就有可能造成节点的运动方向随意性较大，影响定位性能。因此，本文对RWP运动模型的运动方向进行了限制，未知节点的预测采样点被限制在可能的运动方向范围内，将节点的运动方向限定在一个可实现的范围内，即节点所选择的下一时刻的运动方向与原运动方向的夹角应小于可实现的最大夹角，如图1中θ，θ是α的最大值。由此将α限制在θ范围内，避免了节点在运动过程中出现不切实际的过大转角。因此，t时刻的位置预测方程为：

式中Δt为环境影响因子，n_t为高斯噪声，

以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是本发明的原理，在不脱离本发明精神和范围的前提下本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明的范围内。本发明要求的保护范围由所附的权利要求书及其等同物界定。