一种改进的无线传感器网络DV―Ho定位算法

针对无线传感器网络DV-Hop定位算法中，信标节点与未知节点之间的平均跳距估计不足以及定位过程中节点的计算位置与实际位置出现较大误差的情况，提出了一种改进的DV-Hop（Distance Vector-Hop）定位算法。在改进的算法中，对平均跳距进行了一定的补偿，并且对于计算出的未知节点位置给出了一定的约束条件，删除了对定位误差影响较大的信标节点。经仿真表明，与传统的DV-Hop算法相比，改进的算法有效的降低了定位误差。

【关键词】NFC 无线通信 校园应用

近些年来，无线传感器网络（WSN）被广泛应用于医疗、军事侦察、环境监测等领域。然而在大多数情况下，知道采集数据信息的传感器节点所在的位置信息才能这些应用变得更有意义。例如，需要知道森林火灾具置、天然气管道泄漏位置等等。因此，无线传感器网络定位问题一直是研究的热点。

目前，无线传感网络根据测距方式的不同可分为基于测距（range-based）的定位算法和免于测距（range-free）的定位算法。基于测距的算法主要有到达角度测距法AOA（Angle of Arrival）、到达时间差测距法TDOA（Time of difference），和接收信号强度指示RSSI（Received Signal Strength Indicator）。而典型的免测距算法有Centroid算法、dv-hop算法、APIT算法、Amorphous算法、MDS-MAP算法等。

Range-based定位算法确定信标节点与未知节距离关系，然后利用三边测量法或者三角测量法求出位置节点的坐标，其精度较高，但需要额外的硬件支持，因此成本较高。而Range-freed定位算法的基本思想是利用邻近信标节点所获得的连接关系或接近关系等信息计算未知节点的几何坐标，免测距算法对节点的硬件要求低、受环境影响较小、在成本上更加适合用于大规模的传感器网络，因此是一种目前受到普遍关注的定位技术。

DV-Hop（Distance Vector-Hop）定位算法是目前应用最广泛的免于测距的定位算法之一。其基本思想是利用未知节点与信标节点距离用它们之间的跳数与每跳的距离乘积来表示。针对该算法在网络拓扑不规则情况的定位精度迅速下降的缺点，国内不少研究学者提出了相应的改进。如文献[6]提出了利用传统算法定位过程中待定位未知节点中存储的数据，对每跳平均距离进行修正，获得了较高的定位精度，但带来了一定的计算量。文献[7]则利用传感器节点的位置关系对未知节点与信标节点估计位置进行了一定的补偿，比传统DV-Hop算法精度有一定提高，但该算法具有一定随机性。本文主要针对传统DV-Hop算法的不足做出了一定改进，在借助MATLAB7.10仿真工具加以验证，取得了较优的性能。

1 传统DV-Hop定位算法

DV-Hop定位算法最初是由美国鲁特格斯大学（Rutgers University）的Niculescu等人提出来的，其主要是通过距离矢量路由方法，获得距离信标节点的跳数。该算法定位过程分为三个阶段：

（1）计算未知节点与各个信标节点的最小跳数。在这个阶段，主要使用典型的距离矢量交换协议，通过节点之间数据信息交换，记录信标节点与未知节点的跳数。

（2）计算网络平均每跳距离。每个信标节点根据第一阶段所记录的位置信息和相距跳数，利用（1）式估计平均每跳实际距离。

（3）利用三边测量法计算出未知节点坐标位置。在图1中未知节点A获得与之相邻的信标节点i或j，其跳数都为2，估计距离为2AHop，与k的估计距离为6AHop。当未知节点获得至少相邻的3个信标节点的估计距离后，采用三边测量法进行位置估计。已知三个信标节点的位置坐标分别为（x1，y1）、（x2，y2）、（x3，y3）。d1、d2、d3分别为三个信标节点到未知节点的估计距离。

上述算法中由于每跳的距离由估计信标节点物理直线距离除以它们之间的最小跳数得到，一般情况下每跳距离都偏小，特别是节点稀疏分布时，误差更是加大，使得精度急剧降低。

2 改进的DV-Hop定位算法

本文主要针对传统DV-Hop算法的在网络拓扑不规则时，精度迅速下降的缺点，做出相应的改进。传统的DV-Hop定位算法利用信标节点的物理直线距离来估计平均每跳距离，这导致每跳实际距离减小。为了减小这种误差，本文提出了一种补偿真实路径的方法，并对求出的未知节点的坐标给出了验证公式。改进算法如下：

Step1：与传统的DV-Hop算法一致。

Step2：建立网络拓扑模型，如图2所示，信标节点a、b、c的信号在彼此之间任意传播。我们假设如b-3-4-c的传播路径，可以补偿为以dbc为长轴、dmin为短半轴的椭圆以及dbc为长轴、dmax为短半轴的椭圆的结合。

如果跳数Nhi等于1，则未知节点与四个信标节点的距离应该小于通信半径R。如果跳数大于1，则该距离应该在跳数减1乘以节点通信半径与跳数乘以节点通信半径之间。若不满足，则排除该信标节点，选择新的信标节点进行计算，重复此算法，直到找到满足条件的信标节点。

3 算法仿真及分析

为了检验改进算法的性能，本文对传统DV-Hop算法和改进算法在MATLAB7.10平台上进行对比验证，主要对算法的定位误差方面进行了评估。

我们部署了100个传感器节点并且随机分布在100m*100m区域面积中，其中信标节点占取一定的比例。设节点之间通信半径在10m至30m的范围内变化。在仿真过程中，选择不同信标节点的数量以及节点的不同通信半径进行比较，观察两种算法的平均定位误差情况，每种情况进行100次仿真，然后取其平均值进行比较。平均节点定位的误差公式如下：

其中Enor为整个网络的平均节点定位误差，N为未知节点的个数，R为通信半径，（xi，yi）为所求得的未知节点坐标，为实际的未知节点坐标。根据文中算法以及公式可以得出图3的仿真图，横轴为信标节点数，纵轴为平均误差，其中节点通信半径R为20m。

由图3可以看出随着信标节点的增加，两种算法的定位误差都在逐渐减小，在相同数量信标节点情况下，本文中的算法定位误差明显小于传统DV-Hop算法定位误差，例如在信标节点数为20的情况下，传统DV-Hop算法定位误差为36%，而本文的改进算法定位误差则为28%，精度提高了将近30%。

可以看出随着节点通信半径的增加，平均定位误差逐渐减小，并且随着半径的增大，误差率变化趋势更加缓和。

图5是传统DV-Hop算法本文改进算法在不同通信半径时的定位误差率。可以看出，随着节点通信半径的不断增大，本文改进算法一直优于传统DV-Hop算法，并且差距逐渐增大。主要是由于在改进算法的第二和第三阶段都考虑了节点的通信半径，使得半径对定位影响较大。即节点通信半径越大，定位误差越小，并趋于稳定。

4 结论

本文主要针对传统DV-Hop定位算法的定位误差较大问题，提出了一种平均跳距估计补偿和定位坐标后用节点通信半径进行验证的改进的DV-Hop定位算法。在进行理论分析以及仿真验证对传统DV-Hop定位算法以及改进算法进行了对比，结果显示改进算法的定位误差率大大减小。改进算法在不规则网络拓扑结构下和节点稀疏分布情况下也能表现出良好的性能。但同时带来了一定的通信开销，这也是本算法需要继续改进的地方。

参考文献

[1]邱岩，赵冲冲，戴桂兰等.无线传感器网络定位技术研究[J].计算机科学，2008，35（5）：47-50.

[2]TIAN Hui，WANG Shuang and XIE Huaiyao.LocalizationUsing Cooperative AOA Approach[C].Wireless Communications，Netowrking and Mobile Computing 2007.WinCom 2007：2416-2419.

[3]Rong-HouWu，Yang-Han Lee and Hsien-Wei Tseng.Study of characteristic of RSSI signal[C].Industrial Technology，2008 IEEE International Conference.2008：1-3.

[4]JaehunLee，Wooyong Chung and EuntaiKim.Robust DV-Hop a-Lgorithm for localization in Wireless Sensor Network[C].ICCAS.2010：2506-2509.

[5]Y.Jeon，S.Lee，SLee，SChoi，andD.Y.Kim： Consumer Electronics[J].IEEE Transactions，Vol.56（1）.2010：p27.

[6]石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感器学报，2011，24（1）：83-87.

[7]李云飞，江明等.无线传感器网络中DV-Hop定位算法的改进[J].计算机工程与应用，2014，50（3）：79-82.

[8]Wang Sheng Shih，ShihKuei Ping Chang ChihYung.Distributed Direction-Based Localization in Wireless Sensor Networks[J].Computer Communications，2007：1424-1439.

[9]Chia-Yen Shih and MarronP.J.COLA：Complexity-Reduced.Trilateration Approach for 3D Localization in wireless Sensor Networks[C].SENSORCOMM，2010：24-32.

[10]CaixinFu，ZhihongQian，GuangJi，atal.An Improved DV-Hop-Localization Algorithm in Wireless Sensor Network[C].Information Technology and Application（ITA），2013：13-16.

作者单位

重庆大学 计算机学院 重庆市 400044