一种基于路径匹配的改进DV‑Hop定位方法

摘要

一种基于路径匹配的改进DV‑Hop定位方法，包括步骤：在设定的监测区域内随机布设若干个网络节点，若干个网络节点包括信标节点和未知节点；通过路径匹配算法确定未知节点到信标节点的距离估计值；使用Lateration算法计算未知节点的初始位置；使用改进的粒子群算法对初始位置进行优化。由于通过路径相似度参数选择最佳信标间路径来逼近未知节点与信标间路径，从而相对精确地确定平均每跳距离参数值，使得距离估计值更逼近实际距离，提高了测距精度；此外在定位阶段增加改进的粒子群算法提高定位精度。

说明书

技术领域

本发明涉及无线传感器网络技术领域，具体涉及一种基于路径匹配的改进DV-Hop定位方法。

背景技术

经典的DV-Hop定位方法应用于无线传感器网络节点定位领域，是由美国路特葛斯大学(Rutgers University)的Dragos Niculescu等人提出的一种无需专门设备测距的定位方法。DV-Hop方法的基本思想是：网络中节点通过多跳通信连接，根据网络中部分自身位置已知的节点(称为信标节点)，将未知节点到信标节点之间的距离用平均每跳距离和两者之间最小跳数的乘积表示，然后通过Lateration算法计算未知节点的坐标。DV-Hop方法的最大优点是无需直接测距，实现思路灵活，易于开展。经典DV-Hop定位算法的定位步骤可以归纳为以下两步：

(1)使用距离矢量交换协议，使网络中所有节点获得距离每个信标节点的最小跳数。每个信标节点在获得其他信标节点位置和相隔最小跳数之后，采用公式计算网络平均每跳距离，然后将其作为一个校正值广播到网络中：

式中(xi，yi)、(yi，yj)是信标节点i和j的坐标，hij是i和j(i≠j)之间的跳数。未知节点从最近的信标节点处接收校正值，依次估计自身到各信标节点之间的距离di，计算公式如下：

d_i＝H×h_i，

式中，H是网络平均跳距值的校正值，hi是未知节点到信标节点i的最小跳数值。

(2)当某一未知节点获得与3个或更多个信标节点之间的距离时，采用Lateration算法实现定位计算，获得定位结果。

DV-Hop方法的主要不足在于：大多数应用中节点都是随机布设时，其分布的不均匀会使得通过全网信标节点间距离和除以跳数和平均计算取得的每跳距离估值不能真实反映未知节点与每一个信标之间的每跳平均距离值；另外，Lateration算法对测距误差极为敏感，当距离误差较大时，其定位精度是不能保证的。针对DV-Hop方法的不足之处，很多学者提出多种基于经典DV-Hop方法的改进策略，以期提高其在多样化应用环境下的定位精度。多数改进策略集中在DV-Hop方法第一步骤中的平均跳距修正上面，如利用RSSI测距值调整节点间的跳数记录，并基于跳数计算每个未知节点的加权平均每跳距离参数，以此修正未知节点与信标节点之间的距离估计值，达到提高定位精度的目的；或者通过设定跳数阈值限定了局部信标参与平均每跳距离值的估计，针对1跳范围内未知节点与信标节点间的距离估值，采用RSSI测距值代替，并计算信标节点间实际距离与估算距离之间的误差，再利用该误差反向修正平均每跳距离参数；还有针对每个未知节点，对设定跳数阈值内的信标的平均每跳距离值根据跳数进行加权平均计算，获得每个未知节点的平均每跳距离值，完成初步定位计算后，利用获得位置信息的未知节点反推原信标节点的位置，并计算所有信标节点位置误差值的加权平均值来反向修正未知节点位置。这些策略在一定的实验环境下对定位误差有所改善，但针对各种可能出现的节点分布情况，未能从根本上解决节点间分布不均带来的估算误差；也有的改进方法针对第二步骤的节点定位算法进行改进，但这些策略执行的计算条件均在默认距离估计值精确的前提下，且计算量较大，在分布式定位计算模型中使用存在很大挑战。

通过以上对DV-Hop算法以及相关改进方法的分析可知，算法产生误差的主因是针对每个未知节点计算到信标节点距离时平均每跳距离参数的不精确统计以及定位算法对距离误差的敏感度。

发明内容

针对DV-Hop算法的上述缺陷，本申请提供一种基于路径匹配的改进DV-Hop定位方法，包括步骤：

在设定的监测区域内随机布设若干个网络节点，若干个网络节点包括信标节点和未知节点；

通过路径匹配算法确定未知节点到信标节点的距离估计值；

使用Lateration算法计算未知节点的初始位置；

使用改进的粒子群算法对初始位置进行优化。

一种实施例中，在设定的监测区域内随机布设若干个网络节点之后，还包括步骤：利用距离矢量交换协议使网络中所有节点获得距离各个信标节点的多跳最短路径与最小跳数。

一种实施例中，通过路径匹配算法确定未知节点到信标节点的距离估计值，包括步骤：

提取未知节点到某一信标节点的未知至信标最短路径；

提取剩余的各个信标节点分别到该信标节点的信标至信标最短路径；

分别计算信标至信标最短路径较之未知至信标最短路径的路径相似度参数；

将路径相似度参数值最高的信标至信标的平均每跳距离值作为未知节点到该信标节点的平均每跳距离值；

根据平均每跳距离值计算未知节点到该信标点的距离估计值。

一种实施例中，计算信标至信标最短路径较之未知至信标最短路径的路径相似度参数，包括步骤：

统计未知至信标最短路径所经过节点的数目，并记为第一数值；

分别统计信标至信标最短路径所经过节点的数目，并记为第二数值；

分别统计信标至信标最短路径较之未知至信标最短路径中相同节点的数目，并记为第三数值；

根据公式计算路径相似度参数其中，a₁和a₂是偏离因子，m为第一数值，n为第二数值，q为第三数值，Xsd为路径相似度参数。

一种实施例中，使用Lateration算法计算未知节点的初始坐标，包括步骤：

选取所述路径相似度参数值最高的4个信标节点；

根据未知节点与4个信标节点之间的欧氏距离建立非线性方程组；

将非线性方程组转化为线性方程组；

利用极大似然估计法求解所述线性方程组，获得未知节点的初始坐标。

一种实施例中，改进的粒子群算法对所述初始位置进行优化，包括步骤：

将未知节点的坐标、未知节点与4个信标节点之间的距离组成粒子的未知数向量；

初始化未知向量，并根据适应度函数初始化各粒子的个体最优值和种群的全局最优值；

根据路径相似度参数构建惯性权重矩阵；

根据个体最优值、全局最优值和惯性权重矩阵更新粒子速度；

根据速度优化粒子位置。

一种实施例中，根据所述路径相似度参数构建惯性权重矩阵，具体为：

构建一个6×6的惯性权重矩阵，

其中，W为惯性权重矩阵，w₁为未知节点的x坐标对应的变化速度权值，w₂为未知节点的y坐标对应的变化速度权值，w₃、w₄、w₅和w₆分别为未知节点与4个信标节点之间的距离对应的变化速度权值；

选择路径相似度参数值最高的4个信标节点；

利用4个信标节点的参数分别对w₁、w₂、w₃、w₄、w₅和w₆进行赋值。

一种实施例中，利用4个信标节点的参数分别对w₁、w₂、w₃、w₄、w₅和w₆进行赋值，具体包括：

将4个信标节点对应的所述最高路径相似度参数值均值的倒数对w₁进行赋值；

将4个信标节点对应的所述最高路径相似度参数值均值的倒数对w₂进行赋值；

分别将4个信标节点对应的所述最高路径相似度参数值的倒数对w₃、w₄、w₅和w₆进行赋值。

依据上述实施例的定位方法，由于通过路径相似度参数选择最佳信标间路径来逼近未知节点与信标间路径，从而相对精确地确定平均每跳距离参数值，使得距离估计值更逼近实际距离，提高了测距精度；此外在定位阶段增加改进的粒子群算法提高定位精度。

附图说明

图1为本发明实施例提供的基于路径匹配的改进DV-Hop定位方法流程图；

图2为本发明实施例提供的最佳路径匹配算法说明图；

图3为本发明实施例提供的信标节点比例对测距精度影响的对比图；

图4为本发明实施例提供的节点总数对测距精度影响的对比图；

图5为本发明实施例提供的通信半径对测距精度影响的对比图；

图6为本发明实施例提供的信标节点比例对定位精度影响的对比图；

图7为本发明实施例提供的节点总数对定位精度影响的对比图；

图8为本发明实施例提供的通信半径对定位精度影响的对比图。

具体实施方式

下面通过具体实施方式结合附图对本发明作进一步详细说明。

本例提供一种基于路径匹配的改进DV-Hop定位方法，其流程图如图1所示，具体包括以下步骤。

S1：网络节点初始化。

在设定的监测区域内随机布设若干个网络节点，若干个网络节点包括信标节点和未知节点，具体的，在指定区域内随机布设传感器节点，其中一定比例的节点通过测设或携带GPS等定位装置可获知自身位置，称为信标节点，其余待定位节点称为未知节点。

如，监测区域为100(m)×100(m)的正方形二维平面。传感器节点随机布设于监测区域内，所有的节点同构，所有的节点具有相同的通信半径。为了取得客观准确的实验结果，本例设置了三种实验场景：场景一是区域内随机分布100个节点，节点通信半径设为15m，改变信标节点的比例(5％～30％)；场景二是将通信半径设为15m，信标节点比例固定为15％，改变区域内节点总数(100～225)；场景三是将节点总数设为100，信标节点比例设为15％，改变节点的通信半径(15m～35m)。

分别在3种仿真实验场景之下首先实现距离矢量交换协议算法，记录各信标节点到全网节点间的最小跳数与多跳最短路径，即利用距离矢量交换协议得到各信标节点距离全网节点间的最小跳数与多跳最短路径。

S2：通过路径匹配算法确定未知节点到某一信标节点的距离估计值。

本步骤的基本思路是：针对每个未知节点，其距离某个信标节点之间的最短路径和其他信标节点距离该信标节点间的最短路径进行匹配，选出路径相似度最高的信标节点间路径作为最佳路径计算未知节点至该信标节点的平均每跳距离，进而与最小跳数值相乘获得距离估计值。

根据上述思路，步骤S2具体包括如下步骤：

(1)提取未知节点到某一信标节点的未知至信标最短路径。

(2)提取剩余的各个信标节点分别到该信标节点的信标至信标最短路径。

(3)分别计算信标至信标最短路径较之未知至信标最短路径的路径相似度参数。

步骤(3)中的具体步骤如下：

1)统计未知至信标最短路径所经过节点的数目，并记为第一数值；

2)分别统计信标至信标最短路径所经过节点的数目，并记为第二数值；

3)分别统计信标至信标最短路径较之未知至信标最短路径中相同节点的数目，并记为第三数值；

4)根据公式计算路径相似度参数

其中，α₁和α₂是偏离因子，α₁取0.8，α₂取0.2，m为第一数值，n为第二数值，q为第三数值，Xsd为路径相似度参数。

(4)将路径相似度参数值最高的信标至信标的平均每跳距离值作为未知节点到该信标节点的平均每跳距离值。

(5)根据平均每跳距离值计算未知节点到该信标点的距离估计值。

针对每个未知节点，通过最佳路径匹配算法确定其到某一信标的最佳距离估计值，以图2为例对步骤S2进行具体说明。例如，图2中B1，B2，B3为信标节点，其余为未知节点。估计未知节点u2到信标节点B3的距离时，首先，提取未知节点u2到信标节点B3的最短路径，其结果为：u2-u3-u4-u5-u6-B3；再提取其余信标节点B1、B2到信标节点B3的最短路径，其结果如下：

第一路径：B1-u1-u2-u3-u4-u5-u6-B3，

第二路径：B2-u3-u4-u5-u6-B3。

根据路径相似度参数的计算公式，可得第一路径的相似度参数为0.7，第二路径的相似度参数为0.8，故采用B2到B3间的平均每跳距离来近似u2到B3间的平均每跳距离，再乘以最小跳数获得距离估计值，以此类推，可获得未知节点到所有信标节点的距离估计值。

S3：使用Lateration算法计算未知节点的初始位置。

Lateration算法对测距误差敏感，而且当参与计算的信标节点数目大于4时，再采用增加参与定位计算的信标数目并不能起到提高节点定位精度的作用，故本例采用4个信标参与节点位置计算。所以，针对某一未知节点，选择在距离估计步骤S2中路径匹配最优的4个信标节点参与定位计算，沿用经典DV-Hop方法在这一步骤中使用的Lateration算法获得未知节点的初始定位值。

具体步骤如下：

(1)选取路径相似度参数最高的4个信标节点；

(2)根据未知节点与所述4个信标节点之间的欧氏距离建立如下的非线性方程组；

其中，(x，y)为未知节点的坐标，(x₁，y′₁)、(x₂，y₂)、(x₃，y₃)和(x₄，y₄)分别为4个信标节点的坐标，d₁、d₂、d₃和d₄分别为欧氏距离；

(3)将非线性方程组转化为线性方程组；

将式上述的非线性方程组线性化，转换为AX＝B的形式，其中：

(4)利用极大似然估计法求解线性方程组，获得未知节点的初始坐标。

通过极大似然估计法求解线性方程组，获得的解即是未知节点的坐标，其坐标的表达式为：

S4：使用改进的粒子群算法对初始位置进行优化。

将定位问题建模为非线性方程组求最优解的问题，将未知节点坐标以及未知节点至4个信标节点间的距离全部作为未知数，使用改进的粒子群算法求其最优解，获得未知节点的最终定位值。在改进的粒子群算法中未知数的初始值分别为步骤S2和步骤S3中获得的距离估计值与未知点初始位置坐标。

使用改进的粒子群算法优化的具体过程如下：

(1)将未知节点的坐标值、未知节点与4个信标节点之间的距离组成粒子的未知数向量。

相对于既有粒子群改进算法默认距离估值为精确值只在平面坐标2维空间搜索最优解的策略，本例考虑距离估值存在误差，将其与坐标同时列为粒子的未知数，在6维的目标搜索空间搜索粒子的最优解。

(2)初始化未知数向量，并根据适应度函数初始化各粒子的个体最优值和种群的全局最优值。

其中，第i个粒子可表示为一个6维向量，记作x_i＝(x_i1，x_i2，…，x_i6)，每个粒子向量的分量初始值都设置为步骤S2和步骤S3中获得的距离估计值与未知点初始位置坐标值。

(3)根据路径相似度参数构建惯性权重矩阵。

相对于经典粒子群算法采用固定惯性权重W，本例采用了依步骤S2中距离相似度参数Xsd确定的6×6大小惯性权重矩阵W，具体如下：

构建一个6×6的惯性权重矩阵，

其中，W为惯性权重矩阵，w₁为未知节点的x坐标对应的变化速度权值，w₂为未知节点的y坐标对应的变化速度权值，w₃、w₄、w₅和w₆分别为未知节点与4个信标节点之间的距离对应的变化速度权值；

选择步骤S2中路径相似度参数值最高的4个信标节点；

利用4个信标节点的参数分别对所述w₁、w₂、w₃、w₄、w₅和w₆进行赋值，本例中，将4个信标节点对应的所述最高路径相似度参数值均值的倒数对w₁的进行赋值；将4个信标节点对应的所述最高路径相似度参数值均值的倒数对w₂的进行赋值；分别将4个信标节点对应的所述最高路径相似度参数值的倒数对w₃、w₄、w₅和w₆进行赋值。

本例的权重W可以使得在步骤S2中取得较高精度测距值的距离未知数分量在迭代过程中变化较小，反之则需变化较大，这样可加快迭代收敛，并在一定程度上避免迭代陷入局部最优的状态。

(4)根据个体最优值、全局最优值和惯性权重矩阵更新粒子速度，并根据速度优化粒子位置。

其中，粒子i的运动速度记为v_i＝(v_i1，v_i2，…，v_i6)，粒子i的个体最优值pbes_i＝(p_i1，p_i2，…，p_i6)，全局最优值gbest＝(p_g1，p_g2，p_g3，p_g4，p_g5，p_g6，)。用x_i(t)表示粒子i的当前值列向量，v_i(t)表示粒子i的当前速度，则通过以下所列迭代公式来更新粒子i的速度和位置。

上式中，i＝1，2，…，N；w为惯性权重；t为当前迭代次数；c₁、c₂为学习因子，取c₁＝c₂＝2；r₁、r₂是[0.1]范围内均匀分布的随机数。

改进粒子群算法粒子的适应度函数为式中，fitness_i为粒子i的适应度值，(x_i，y_i)为粒子i中的平面位置坐标，(x_j，y_j)为信标节点j的位置坐标，d_j为未知节点到信标节点j的估计距离。每次迭代计算完成后，每个粒子计算各自的适应度值，并比较更新个体最优值与全局最优值。迭代计算在设定条件下完成后所得解向量中的x，y元素值即为最终求得的未知节点坐标优化值。

下面分别对步骤S2中的距离估计进行对比性实验和步骤S4中定位进行对比性实验，以证明本申请在该步骤中的改进具有明显的效果。

在测距步骤S2实验中，将本例的算法分别与另外的三种算法进行对比分析，另外的三种算法分别为：1.经典DV-Hop算法，2.乔欣等人提出的基于跳距修正的WSN拟牛顿迭代定位算法(下文简称IDV-Hop1)，3.夏少波等人提出的基于跳数修正的DV-Hop定位改进算法(下文简称IDV-Hop2)。其中，IDV-Hop1算法首先设定跳数阈值对信标节点进行优选用来改进平均跳距和跳数，然后利用校正值计算节点间距离，接着使用Lateration算法算出未知节点的坐标，最后用拟牛顿迭代算法对坐标进行迭代优化；IDV-Hop2算法通过设定跳数阈值限定了局部信标参与平均每跳距离值的估计，针对1跳范围内未知节点与信标节点间的距离估值，采用RSSI测距值代替，并计算信标节点间实际距离与估算距离之间的误差，再利用该误差反向修正平均每跳距离参数，最后采用Lateration算法算出未知节点的坐标。其中，本例的算法与另外的三种算法在信标节点比例对测距精度影响的对比图如图3所示，本例的算法与另外的三种算法在节点总数对测距精度影响的对比图如图4所示，本例的算法与另外的三种算法在通信半径对测距精度影响的对比图如图5所示。

在本发明提出的定位策略中，未知节点与信标节点之间的测距精度越高，最终可获得的定位精度越高，因此测距精度是评价算法性能的重要指标。全网的测距精度用所有未知节点与信标节点之间的估计距离误差的平均值来衡量，并归一化为通信半径的百分比来表示。图3、图4、图5分别对比了在三种实验场景下本发明提出的基于最佳路径匹配算法获得的测距精度、原经典DV-Hop方法获得的测距精度、IDV-Hop1算法的测距精度以及IDV-Hop2算法的测距精度，实验结果表明：随着信标节点的比例变化，本发明算法较之原方法可降低约48％测距误差、较之IDV-Hop1可降低约29％测距误差、较之IDV-Hop2可降低约31％测距误差；随着网络节点部署密度的变化，分别可降低约28％、21％和14％的测距误差；随着通信半径大小的变化，分别可降低约60％、29％和20％的测距误差。整体可获得更稳定的测距精度。

在定位步骤实验中，本发明算法也分别与另外三种算法进行对比分析，另外三种算法是：1.经典DV-Hop算法，2.本发明提出的测距改进算法加经典的粒子群算法(下文简称PDV-Hop)，3.IDV-Hop1算法。其中，本例的算法与另外的三种算法在信标节点比例对定位精度影响的对比图如图6所示，本例的算法与另外的三种算法在节点总数对定位精度影响的对比图如图7所示，本例的算法与另外的三种算法在通信半径对定位精度影响的对比图如图8所示。

本发明提出的定位策略的最终目标是获得高精度的未知节点定位，因此定位精度是评价算法性能的关键指标。对全网未知节点的每一次定位操作，定位精度用所有未知节点经过定位计算获得的位置和真实位置之间的欧氏距离的均值来衡量，并归一化为通信半径的百分比来表示。图6、图7、图8分别对比了在三种实验场景下本发明提出的Lateration加改进的粒子群算法获得的定位精度、原经典DV-Hop方法获得的定位精度、IDV-Hop1算法获得的定位精度和PDV-Hop算法获得的定位精度，实验结果表明：随着信标节点的比例变化，本发明算法较之原方法可降低约43％定位误差、较之IDV-Hop1可降低约10％定位误差、较之PDV-Hop可降低约7％定位误差；随着网络节点部署密度的变化，分别可降低约35％、18％和11％的定位误差；随着通信半径大小的变化，分别可降低约41％、14％和15％的定位误差。此外，根据实验统计，在相同的迭代限定条件下(最大迭代次数50或两次粒子适应度函数值变化低于0.0001)，经典粒子群算法平均迭代次数为6，本发明使用的改进粒子群算法平均可将迭代次数减少2次。本发明定位优化算法整体可获得在各种场景之下更稳定的定位精度。

总体而言，本发明提出的基于最佳路径匹配的改进DV-Hop定位方法相对于原经典DV-Hop方法和既有改进算法在相对提高计算量的前提下较好地改善了测距精度与最终的定位精度，表明该方法的可行性。

以上应用了具体个例对本发明进行阐述，只是用于帮助理解本发明，并不用以限制本发明。对于本发明所属技术领域的技术人员，依据本发明的思想，还可以做出若干简单推演、变形或替换。