使用分簇方式实现对无线传感器网络DV—Hop定位算法的改进

童轩等

摘要：许多无线传感器网络定位算法已经被提出来提供每个节点的位置信息，可将这些定位算法分为两类：基于距离的和距离无关的。基于距离的定位算法使用点到点的绝对距离估计值或角度估计值来计算位置，而距离无关的定位算法只利用网络连通度等来得到近似的位置信息。文章研究了距离无关的无线传感器网络定位算法。

关键词：无线传感器；网络定位算法；分簇方式；DV-Hop算法；质心算法；APIT算法 文献标识码：A

中图分类号：TP393 文章编号：1009-2374（2015）28-0039-02 DOI：10.13535/j.cnki.11-4406/n.2015.28.019

目前从传感器网络节点定位算法所采用的技术手段来看，其可以分为两大类：基于距离（range-based）的定位算法和距离无关（range-free）的定位算法，距离无关的定位算法主要有DV-Hop（Distance Vector-Hop）算法、质心算法、APIT（Approximate Point-In-Triangulation Test）算法、Amorphous算法等。

1 DV-Hop算法缺陷分析

美国罗格斯大学的Dragos Niculescu等人提出了基于距离向量路由和GPS定位的APS（Ad hoc Positioning System）定位系统，DV-Hop（Distance Vector-Hop）定位算法就是其中之一。它的中心思想是：用未知节点距锚节点的最小跳数与未知节点的平均每跳距离的乘积来表示未知节点到锚节点的距离，然后通过极大似然估计法得出未知节点的坐标。

DV-Hop定位算法在节点密度较高，节点分布较均匀的网络中可以得到较高的定位精度。但该算法的缺点是当节点密度降低或节点分布不均匀时，定位精度将会有较大恶化。

DV-Hop虽然实现简单、易于扩展，但其不足之处在于：（1）在信标节点获得平均每跳距离的计算过程中，由于是以跳段距离近似直线距离，当节点个数非常少时，定位误差将会非常大，若一些节点获得的信标节点位置不足3个而无法定位，导致定位覆盖率较低；（2）全网使用统一的平均每跳距离，并不考虑节点分布密度在各个部分的不同导致的平均每跳距离的不同，从而在较大范围随机分布感知节点的时候会出现较大误差。

2 改进DV-Hop算法

第一，通过采取分簇计算平均每跳距离的方式来使它的值更加贴近于实际。实际应用中，在较大范围内随机分布信标节点的时候，节点密度由于地形、随机分布性等原因在每块区域是不一致的，因而平均每跳距离也是不一样的，那么平均每跳距离在这样的情况下就不该取全网范围内所有信标节点的平均每跳距离的平均值，而是应该采取将无线传感器网络分簇，逐个算出适用于本簇的平均每跳距离，未知节点使用簇内平均每跳距离，

从而提高未知节点计算到信标节点的距离的准确度。

上述算法的具体实现说明：每个节点都把自己看作簇的中心节点，跳数限制若为3跳，对于信标节点而言，它只利用3跳范围之内的其他信标节点进行平均每跳距离的计算，对于未知节点而言，它只利用3跳范围之内的信标节点的平均每跳距离，在收到簇内信标节点发来的平均每跳距离后，未知节点取它们的平均值作为它自己的平均每跳距离，未知节点使用最小二乘法计算自身位置的时候，它也是只使用簇内信标节点作为参考参数进行计算。这样的分簇方式只是在计算自身位置时使用，是逻辑上的分簇，并不会实际增加无线传感器的能量开销。

第二，吸收使用适用于分簇算法的加权最小二乘法，由近及远的权值是由大到小的。由于每个未知节点周围的信标节点数是不一样的，权值是随之变化的。在编写程序时，不能一直像原算法一样使用固定权值。算法的matlab仿真实现为：

3 算法仿真实验及分析

为了检验可行性和有效性，本文算法在matlab平台上进行了仿真实验，并对实验结果进行了比较分析。在实验中，节点分布在1000m×1000m的正方形区域内，有用户输入节点总数N、信标节点个数n和节点通信半径，程序在该区域内随机分布这些节点。设所有节点都处在相同的网络环境下，实验最终结果取多次运算的平均值。算法的性能主要从平均定位误差方面进行了评估，本文使用的是相对误差。本文不考虑网络不连通的情况。

如图1，在1000m×1000m的正方形区域内，300个传感器节点，其中60个为信标节点，通信半径为200m的实验设置下，进行的三轮实验中，使用分簇方式改进算法的平均定位误差相比原算法降低了大约5倍。

采用分簇方法的DV-Hop算法在应用到C型节点分布和S型节点分布的无线传感器网络中，效果也是十分明显的。C型节点分布和S型节点分布分别如图2和图3所示。

由图4、图5给出在通信半径不同、节点密度不同、信标节点密度不同的情况下，C型节点分布和S型节点分布下，定位误差的比较结果，可以看到改进后的算法相对原算法平均定位误差降低了将近9倍。随着通信半径的增加，平均定位误差逐渐减小，随着节点密度的增加，平均定位误差逐渐减小，随着信标节点比例的增加，平均定位误差也逐渐减少。

4 结语

定位精度是评价定位算法的首要指标，本文针对DV-Hop定位算法精度不高、不适用于节点分布不均匀、位置计算方法笼统等缺陷，提出了采用分簇方式的DV-Hop算法，同时融入了适用于分簇方法的加权最小二乘法来改进经典DV-Hop算法。该算法无需额外硬件支持，不会有额外的能量开销，小幅度增加了通信量，适用于实际生产环境。从仿真结果来看，本文算法在较大范围内随机分布节点的定位精度要优于经典DV-Hop算法的定位精度，是可取的改善措施。

参考文献

[1] Akyildiz L F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks[J].IEEE Communication Magazine，2002，40（8）.

[2] 史龙，王福豹，段渭军，任丰厚.无线传感器网络Range Free自身定位机制与算法[J].计算机工程与应用，2004，（23）.

[3] 张媛.基于无线传感器网络定位技术的研究[D].东北大学，2008.

[4] Harter A，Hopper A.A distributed location system for the active office[J].IEEE Network，1994，8（1）.

作者简介：童轩（1994-），男，福建建阳人，南京邮电大学物联网学院学生，研究方向：网络工程。

（责任编辑：陈 倩）