无线传感器网络选择性DV-Hop定位算法*

罗 维，姜秀柱，盛蒙蒙

（1.中国矿业大学 计算机科学与技术学院，江苏徐州 221116;2.北京理工大学信息与电子学院，北京 100081）

0 引言

无线传感器网络（wireless sensor networks，WSNs）就是由部署在监测区域内大量的微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统［1］。确定事件发生的位置或获取消息的节点位置是无线传感器网络最基本的功能之一。在无线传感器网络中，定位算法有很多种分类。根据定位过程中是否测量实际节点间的距离，把定位算法分为基于距离的（range-based）定位算法［2，3］和距离无关的（range-free）定位算法［4，5］。其中距离无关的矢量跳距（DV-Hop）定位算法［5］应用最为广泛，目前已有对DV-Hop算法改进的很多方法［6～8］。本文在对传统 DVHop算法分析后，提出了一种选择性DV-Hop（selective DVHop，SDV-Hop）算法，该算法使得估计的平均每跳距离更接近实际每跳距离，能获得高的定位精度。

1 DV-Hop定位算法

传统DV-Hop定位算法的定位过程由3个阶段组成:

1）使用典型的距离矢量交换协议，通过节点间信息交换，使网络中所有节点获得与信标节点之间的最小跳数。

2）每个信标节点在获得其他信标节点位置信息和跳数信息之后，利用公式（1）计算网络平均每跳距离，并将其作为一个跳距校正值广播至网络中

其中，（xi，yi），（xj，yj）分别为信标节点i，j的位置信息，h（i，j）为信标节点i到信标节点j的最小跳数。

3）未知节点接收第1个校正值后，用该校正值乘以到附近各信标节点之间的最小跳数计算出估计距离。最后通过三边测量法计算出自身的位置。

如图1所示，已知信标节点L1与L2，L3之间的实际距离和跳数，L2计算得到校正值为（40+75）/（2+5）=16.42m。假设A从L2获得校正值，则它与3个信标节点之间的距离分别为L1:3 ×16.42 m，L2:2×16.42 m，L3:3×16.42 m。然后使用三边测量定位法确定节点A的位置。

图1 DV-Hop算法示意图Fig 1 Diagram of DV-Hop algorithm

2 SDV-Hop定位算法

SDV-Hop算法［9］能完成对未知节点更精确的定位，区别于传统DV-Hop算法主要体现在定位过程中对平均每跳距离的修正。传统DV-Hop算法由3个阶段组成，SDV-Hop算法也按照3个阶段进行。

2.1 跳数误差分析与改进

在传统DV-Hop算法中信标节点利用公式（1）的平均每跳距离计算出网络中所有信标节点的平均每跳距离的平均值如公式（2）所示

其中，N是信标节点的总数量。

2个信标节点之间的实际距离如公式（3）所示

其中，（xi，yi），（xk，yk）分别为信标节点i，k的位置信息

由式（2）、式（3）可以得到信标节点i，k的估计跳数如公式（4）所示

已知每一个信标节点的实际跳数h（i，k）和估计跳数h'（i，k），利用公式（4）可以得到跳数差如公式（5）所示

跳数差反映出信标节点i，k的实际跳数和估计跳数之间误差的大小。当DHC（i，k）的值大于 0.5～1 或小于 －0.5～－1时，说明节点计算预期位置时，第k个信标节点不在第i个信标节点的泰森多边形（Voronoi图）区域内。由此可见在传统的DV-Hop算法中节点获得的最小跳数是存在误差的。

SDV-Hop算法在第1阶段获得最小跳数时作了改进。最小跳数的获得是在剔除了长距离信标节点之后，再按照传统的DV-Hop算法使网络中的节点获得距离邻居信标节点的最小跳数。

2.2 平均每跳距离误差分析与改进

利用公式（1）计算的平均每跳距离是一个平均值，所以，当未知节点利用平均每跳距离估计到信标节点的距离时会产生误差。已知未知节点到信标节点的距离增加时，距离信标节点的跳数也增加，误差随着增大。因此，当未知节点要定位自身的位置时，应该排除长距离信标节点的信息。

已知未知节点g距离所有信标节点的最小跳数，则求得平均跳数如公式（6）所示

其中，h（g，k）为未知节点g到信标节点k的最小跳数，M为未知节点g能到达的信标节点总数目

将计算出的平均跳数广播到网络中，所有未知节点获得这一平均跳数信息。当h（g，k）大于Hg时，则剔除长距离信标节点k的信息。最后计算剩余信标节点的平均每跳距离C0如公式（7）所示

其中，（xi，yi），（xw，yw）分别为信标节点i，w的位置信息，h（i，w）是剔除长距离信标节点信息后，信标节点i获得的到邻居信标节点w的最小跳数。

剔除长距离信标节点后，这里要进一步修正平均每跳距离。根据信标节点i，w的位置信息（xi，yi），（xw，yw），求得信标节点i到信标节点w的实际距离如公式（8）所示

已知信标节点i到信标节点w的最小跳数h（i，w）和估计平均每跳距离C0，由此得信标节点i到信标节点w的估计距离如公式（9）所示

由公式（8）、式（9）得信标节点i到信标节点w的距离总误差如公式（10）所示

其中，D（i，w）是信标节点i到信标节点w的实际距离，D（i，w）是信标节点i到信标节点w的估计距离。

根据n个信标节点间的跳数总和为C2n，由信标节点的距离总误差求得每跳平均距离误差如公式（11）所示

根据公式（11）的每跳平均距离误差，第二次更新信标节点i到信标节点w的平均每跳距离如公式（12）所示［10］

最后信标节点i将最接近实际每跳距离的平均每跳距离Clast广播到网络中的所有节点。

2.3 未知节点定位自身位置

未知节点获得剩余可信的信标节点的平均每跳距离信息后，估计到信标节点的距离就可以确定自身位置。假设某一未知节点g坐标为（x，y）测得到n个信标节点的距离，第w个信标节点的坐标为（xw，yw），未知节点g到信标节点w的距离为dw。根据上面的已知数据，可以得到一个非线性方程组，将其线性化并使用最小二乘法［11］来求解，可以得到未知节点的坐标。

3 仿真与分析

利用Matlab仿真实验平台比较SDV-Hop算法与传统DV-Hop算法的性能。节点随机分布在100 m×100 m的方形区域里，未知节点与信标节点的坐标随机产生。下面分别讨论信标节点比例、节点数量以及通信半径对两种定位的平均定位误差的影响。每种性能的仿真都是随机进行500次然后取平均值所得。

定位误差率指的是通过定位算法得到的未知节点的估算位置与实际位置的偏差，这种偏差可以用两者之间的欧氏距离除以节点的通信半径来衡量，计算节点定位误差如公式（13）所示

其中，（xa，ya）为未知节点的估算位置信息，（xb，yb）为未知节点的实际位置信息，R为节点的通信半径。

在仿真环境中n个未知节点的定位误差率求平均得到平均定位误差率如公式（14）所示

从图2可以看出:当信标节点比例增加时，两种定位算法的平均定位误差都减小并趋于稳定，但SDV-Hop算法的平均定位误差比传统DV-Hop算法减少了约6%。

从图3可以看出:随着节点通信半径的增大，SDV-Hop算法的平均定位误差始终低于传统DV-Hop算法。在通信半径为65 m时，SDV-Hop算法的平均定位误差比传统DVHop算法减少了10%。

从图4可以看出:随着节点总数的增加，传统DV-Hop和SDV-Hop的平均定位误差都减小并趋于稳定，当节点总数为90个时，SDV-Hop算法的平均定位误差比传统DVHop算法减少了5%。

图2 平均定位误差与信标节点比例的关系图Fig 2 Relation diagram of average localization error vs ratio of beacon nodes

图3 平均定位误差与通信半径关系图Fig 3 Relation diagram of average localization error vs communication radius

图4 平均定位误差与节点总数关系图Fig 4 Relation diagram of average localization error vs number of nodes

4 结论

SDV-Hop改进算法对平均每跳距离做了二次修正，使得平均每跳距离更接近实际每跳距离。仿真结果表明:SDV-Hop算法使得未知节点定位自身位置时，平均定位误差明显减小。同时，该算法能剔除长距离信标节点的信息，因此，在实际应用中既适合节点分布均匀的无线传感器网络，同样也适合节点分布非均匀的无线传感器网络。该算法也存在着缺点，多次修正平均每跳距离增加了计算量。

［1］孙利民，李建中，陈 渝.无线传感器网络［M］.北京:清华大学出版社，2005:1 －3.

［2］Caffery J.A new approach to the geometry of ToA location［C］//Proc of IEEE Vehicular Technology Conference（VTC），2000:1943－1950.

［3］Nicolescu D，Nath B.Ad Hoc positoning systems（APS）using AoA［C］//Proc of the IEEE INFOCOM，San Francisco:IEEE Computer and Communications Societies，2003:1743 －1743.

［4］Niculescu D.Positioning in Ad Hoc sensor network［J］.IEEE Network，2004，18（4）:24 －29.

［5］Niculescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Telecommunication Systems，2003，22（1 －4）:267 － 280.

［6］张鸿飞，董齐芬，俞 立.基于局部信标选择的无线传感器网络定位算法［J］.传感技术学报，2010，23（4）:571 －576.

［7］姚忠孝，俞 立，董齐芬.基于移动信标的DV-Hop无线传感器网络定位算法［J］.传感技术学报，2009，22（10）:1504－1509.

［8］刘少飞，赵清华，王华奎.基于平均跳距估计和位置修正的DV-Hop定位算法［J］.传感器技术学报，2009，22（8）:1154－1158.

［9］Jin Seung-hwan，Yoo Sang-jo.Improved positioning scheme based on DV-Hop for wireless sensor networks［C］// IEEE ISCIT，2009:69－74.

［10］石为人，贾传江，梁焕焕.一种改进的无线传感器网络DVHop 定位算法［J］.传感技术学报，2011，24（1）:83－87.

［11］Langendoen K，Reijers N.Distributed localization in wireless sensor networks:A quantitative comparison［J］.Computer Networks，2003，43:69 －74.