基于DV-Hop算法改进的研究

李亚杰 杜春晖 吉高卿

(河北建筑工程学院，河北 张家口 075000)

基于DV-Hop算法改进的研究

李亚杰 杜春晖 吉高卿

(河北建筑工程学院，河北 张家口 075000)

对无线传感器网络中的DV-Hop的定位算法进行了研究和分析，它是一种基于无需测距的无线传感器网络的定位算法.针对DV-Hop根据全部网络的数据计算单跳距离，通信负担大，而且对于锚节点分布不均和稀疏节点网络，定位精度差，提出把网络分局部和分区域.针对非测距算法的定位精度粗糙，在DV-Hop后，加入分布式迭代算法，进一步提高定位的精度.通过对算法的仿真，得出该算法定位精度提高，和改进算法的一些特定应用环境.

DV-Hop；节点定位；距离约束；定位算法

0 引 言

DV-Hop算法是由Niculescud等人提出的，一种非测距的无线传感器网络的定位算法.该算法依赖于软件和编程，不需要任何的其他硬件.算法的核心思想是利用未知节点到锚节点的跳数乘以每跳的估算距离，得到三个或者以上的位置信息，则可以利用三边算法或者最大似然估计来计算节点的位置.由于每跳距离是估算的，定位精度粗糙，本文对定位精度和网络的类型来展开研究，在此算法的基础之上进行相应的改进，通过matlab仿真显示能明显提高定位的精度.

1 DV-Hop基本过程

算法的基本过程由三步构成:(1)网络中广播消息，通过信息交互，节点获得到锚节点的跳数.(2)根据步骤(1)获得的消息，计算网络中跳数的平均距离，让跳数乘以平均距离获得未知节点到锚节点之间的距离信息.(3)当未知节点获得三个或者以上的位置信息后，通过三边测量法或极大似然估计法计算自身位置[1].

DV-Hop算法的定位过程分为三个阶段[2]：

(1)锚节点向周围网络广播自己的位置信息和分组信息，其中包括跳数字段，初始化为0.接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳数的分组.然后将跳数加1，并转发给邻居节点.通过这个方法，网络中的所有节点能够记录下到每个信标节点的最小跳数.

(2)计算未知节点和信标节点的实际跳段距离.每个信标节点根据第一阶段中记录的其他信标节点的位置信息和相距跳数，利用公式(1.1)估算平均每跳的实际距离.

(1.1)

其中，(xi,yi)，(xj,yj)是信标节点i，j的坐标，hj是信标节点i与j(j≠i)之间的跳段数.然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第一个每跳平均距离，并转发给邻居节点.这个策略确保了大多数节点从最近的信标节点接收到每跳平均距离值.未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个信标节点的跳段距离.

(3)利用三边测量法或极大似然估计法计算自身位置.

(1.2)

其中公式(1.2)是三边算法.

2 DV-Hop算法的改进

2.1 算法局部化的改进

根据本文前面的分析和论述，就DV-Hop算法进行相应的修改，对于算法的流程大家已经很清楚，下面就改动的部分做详细的阐述.

在算法的第一步中，锚节点不再向网络中的全部节点广播位置信息，在广播过程中，加入广播信息跳数的限制选项n，就不再向n跳意外的节点发送消息.这样可以大大减轻网络的通信负担，每个区域也都会形成局部的网络[4].

在估算平均每跳距离的算法的第二步中，锚节点选择自本节点范围内的m个锚节点，这样处理既可以保证如实反映网络节点的分布情况，有减少不必要的通信，同时未知节点的定位的准确度，在各向异性的网络中，该算法同样适用.

2.2 协作优化阶段

根据第一步的DV-hop得到的每个位置的精度不是很高的位置信息，可利用质量-弹簧模型对定位的精度迭代优化.从计算量和定位精度的综合考虑，只考虑基于2跳范围连通性约束.具体的步骤如下：

(1)每个未知节点ni向网络中广播自己的当前的计算坐标Pi，并从它的周围2跳范围内获取它的估计的坐标[3].

nj和ni是一跳邻居，那么计算公式如下：

(2.1)

nj和ni是二跳邻居，那么计算公式如下：

(2.2)

(2.3)

(2.4)

根据节点受的作用力和势能公式可以计算出节点新的位置：

(2.5)

由于锚节点本身知道自己的位置，故不参加迭代过程，未知节点迭代后均收敛，定位精度明显提高.

3 算法的仿真与结果分析

对于改进的算法进行相关的仿真工作，利用matlab仿真软件，分别实现了DV-Hop算法和改进算法.利用matlab的rand函数在的范围内随机产生了200个无线传感器网络的节点，其中锚节点比例也是随机产生.并作如下假设：网络中的节点是相同的，并且拥有相同的通信半径.在仿真中距离的误差是指通过算法计算的坐标与真实坐标之间的差值，定义距离误差与节通信半径的比值为估算误差.下面就参变量的不同分布详细的比较两种算法的定位精度.仿真的结果如下所示：

图3.1可以看出，两种算法均随着通信半径的加大，误差在逐步减小.原因是随通信半径的加大，节点可以利用的相关约束信息增加，节点的邻居节点数也在增加，所以误差在逐步减小，但是当通信半径增加到一定程度，这种变化就不是很明显.另外还可以看出，改进的算法比原算法在相同的条件下定位精度要高.

图3.1 估算误差与通信半径关系 图3.2 估算误差与连通度关系

图3.2是估算误差和连通度的变化关系，可以看出，连通度增加，定位误差就减小，因为随着连通度的增加，在迭代阶段，就有更多的相对位置信息可以利用.可以看出，改进算法在随连通度变化前期非常明显，随着在增加，基本变化不大.改进算法比原算法的定位精度提高近15%.

4 结束语

本文对DV-Hop算法作了改进，由于该定位算法针对网络锚节点不均匀，改进的局部的定位算法，减少通信量和网络的工作负担，针对稀疏节点的网络定位精度比原算法高.在此算法基础之上，加入迭代的过程，解决了无测距DV-Hop算法定位的定位精度问题.以上都是在算法上的改进，无需其他的硬件支持.

[1]NiculescuD,NathB.AdHoepositioningsystem(APS)[J].IEEEGlobeCom，2001(5)：2926～2931

[2]田金鹏.无线传感器网络定位技术研究[D].上海大学.2008.

[3]李新.无线传感器网络中节点定位算法的研究[D].中国科学技术大学，2008.

[4]冯缜.基于区域的无线传感器网络定位算法研究[D].华中科技大学，2007.

ResearchontheimprovementofDV-Hopalgorithm

LI Ya-jie1,DU Chun-hui1,JI Gao-qing1

(1.HebeiInstituteofArchitectureandcivilengineeringHebeiZhangjiakou075000)

This paper studies and analyzes the DV-Hop localization algorithm in wireless sensor network,which is based on the wireless sensor network positioning algorithm without ranging.In the DV-Hop,single hop distance is calculated according to the data of whole network,and the communication burden is large.For the uneven distribution of the anchor nodes and the sparse nodes network,the positioning accuracy is poor.So propose the division and the sub region of the network.Because positioning accuracy of the non ranging algorithm is rough,after the DV-hop,the distributed iterative algorithm is added,further improving the accuracy of positioning.Through the simulation of the algorithm,the algorithm can improve the positioning accuracy,and also improve some specific application environment of algorithm.

DV-Hop；Node localization；Distance constraint;localization algorithm

2015-03-21

河北建筑工程学院青年基金项目(QN201418)

李亚杰(1983-)，男，汉，河北邯郸，硕士，讲师，从事计算机控制技术研究.

TP 301.6

A