XIANG Mantian，WANG Sheng，YANG Youhua（.SchoolofSoftware，NanchangUniversity，Nanchang33009，China；.SchoolofInformationEngineering，NanchangUniversity，Nanchang33003，China）



An Improved DV-Hop Localization Algorithm Based on Threshold Mechanism and Correcting Distance for Wireless Sensor Networks*

XIANG Mantian1*，WANG Sheng1，YANG Youhua2
（1.SchoolofSoftware，NanchangUniversity，Nanchang330029，China；2.SchoolofInformationEngineering，NanchangUniversity，Nanchang330031，China）

In the wireless sensor network DV-Hop localization algorithm，the location of unknown nodes only consid⁃ers the average hop distance from its nearest anchor node，which is used to multiply the number of hops to replace the real distance but thus，it will lead to large positioning errors.This paper proposes a high-accuracy localization al⁃gorithm TMCD-DV-Hop，which is a developed DV-Hop algorithm of relative high accuracy，based upon threshold mechanism and distance correction and the developed algorithm firstly calculates hop thresholds，and the effect of the other beacon nodes lying outside the nearest anchor node in the local range and global range is considered，thus，best corrected average hop distance has been chosen to estimate the distance，and an estimated coordinate is gained by centroid algorithm after the combinatorial optimization of anchor nodes within the single-hop communicative radi⁃us，meanwhile，another estimated coordinate is gained by weighted least-squares method.At last arithmetic mean of two estimated coordinates is considered as orientation coordinate for unknown nodes.Simulation experiment mani⁃fests that in the same network environment，developed TMCD-DV-Hop algorithm could better lower down position⁃ing errors than DV-Hop in the end the positioning accuracy is elevated.

wireless sensor network；DV-Hop algorithm；threshold mechanism；corrected average hop distance

无线传感器网络WSN（Wireless Sensor Net⁃work）是由大量的多功能，低功耗，低成本，能够感知外界特性的传感器节点组成［1］，这些节点随机部署或撒在监测区域内，它们之间通过无线通信的方式形成一个多跳自组织网络［2］。节点的定位技术是无线传感器网络应用中的关键技术之一［3］，根据在定位过程中是否需要测量节点间的距离，可将无线传感器网络定位算法分为测距（Range-based）定位算法和非测距（Range-free）定位算法［4］。在WSN中非测距定位算法备受关注，其中DV-Hop［5］定位算法因有简单、经济、高适用性和高效性等特点而得到了广泛应用，但其也有定位误差较大的不足，如在网络平均连通度为10，锚节点密度为10%时，其定位误差约为33%［6］。因此，本文将重点研究如何对DV-Hop算法进行改进，深入剖析DV-Hop算法定位过程中存在的不足，在不改变原始DV-Hop算法的基本框架和不增加额外硬件设备的前提下，提出了一种改进算法TMCD-DV-Hop，与原始的DV-Hop算法相比，TMCD-DV-Hop能有效地降低定位误差。

1　DV-Hop算法原理

DV-Hop定位算法是由Dragos Niculescu［5-6］等人根据全球定位系统GPS（Global Positioning System）定位思想和距离矢量路由机制提出的一种分布式非测距算法。DV-Hop算法受环境因素的影响小，也无需额外的测距设备，这些特点使DV-Hop算法适用于节点配置简单，成本低和规模大的无线传感器网络。DV-Hop算法所需的锚节点数量较少，采用多跳的方式进行定位，下面对DV-Hop算法进行简单描述。

1.1DV-Hop算法描述

DV-Hop定位算法主要分为以下三个阶段：

①计算跳数：锚节点通过洪泛（Flooding）方式广播自身的坐标信息，其中初始跳数为0，未知节点接收并记录到每个锚节点的最小跳数，同时忽略到同一锚节点其他跳数较大的路径，然后将跳数值加1，并转发给邻居节点。……