无线传感网络DV-Hop定位改进算法

李丽娜，王 越，张晓东，雷昊东

(辽宁大学 物理学院，辽宁 沈阳)

无线传感网络DV-Hop定位改进算法

李丽娜，王 越，张晓东，雷昊东

(辽宁大学 物理学院，辽宁 沈阳)

针对DV-hop定位算法定位精度不高的问题，提出了一种改进的DV-hop算法，并详细介绍了改进的基本原理.在算法第二阶段融入了RSSI算法修正平均每跳距离，第三阶段采用先减后平方的方法对极大似然估计法计算步骤进行了改进，减小了计算误差.并利用matlab对改进算法进行了仿真分析.仿真结果表明：与传统的dv-hop定位算法相比，改进算法定位误差降低了21.8%，使定位精度有了较大的提高，且不需要增加额外的硬件开销.

DV-Hop定位算法；无线传感网络；极大似然法

0 引言

DV-Hop定位算法是将距离矢量路由与GPS原理相结合的一种非测距分布式定位算法，其优点是功耗小，成本低，计算速度快等，但是由于DV-Hop属于非测距的定位算法，受外界环境影响较大，其定位精度还不够高.近几年关于此算法的研究逐渐深入，本文在原有的基础上，对平均每跳距离进行修正并调整算法第三阶段的计算方式，最终使算法定位更精准，实验验证了本文算法的有效性.

1 基于距离矢量的定位算法

距离矢量的概念是由有线网络的路由协议中引入的，将距离矢量视为设备间传递数据包需要经过的跳数，用距离矢量来衡量数据包从一个节点传送到另一个节点需要花费的成本，由此可确定距离矢量与节点间的物理距离没有直接联系[1].

将距离矢量引入到无线传感网络中，定义传感器节点间传输数据包需要经过的跳数为距离矢量.无线传输模式下，无线节点间数据包传输的跳数与节点距离间存在一定关系，因此可以基于距离矢量对节点进行定位，本文就是基于距离矢量的DV-hop定位算法，并对算法的每个阶段可能产生的误差原因进行仔细分析，对其不足之处进行了研究，进而得出基于距离矢量算法普遍存在的问题以及改进的方向.

2 DV-Hop定位算法研究和分析

2.1 传统的DV-Hop 定位算法原理

DV-Hop定位算法具有方法简单，定位精度较高的特点.DV-Hop 定位算法无需获得节点之间的实际距离，仅仅需要利用网络连通性估计距离.它的定位过程分以下三个阶段：

1)计算未知节点与锚节点的最小跳数值

网络中的各锚节点向邻居节点广播包括自身信息的数据包，跳数初始值置为0.未知节点记录每个锚节点的最小跳数值，并将跳数值加1转发给邻居节点.

2)每个锚节点利用其他参考节点的位置信息及最小跳数来计算平均每跳的距离，并将其作为校正值广播至网络中.当接收到校正值后，节点根据式(1)计算与锚节点之间的距离.

(1)

式中(xi,yi)，(xj,yj)为锚节点i与锚节点j的坐标，Hopsi为锚节点i和j之间的跳数.

3)未知节点收到其到至少三个锚节点的估计距离后，利用极大似然估计或三边测量法计算未知节点的坐标[2].

锚节点和未知节点算法流程图分别如图1及图2所示.

2.2 DV-Hop算法误差分析

DV-Hop算法的第一阶段，由于传感器节点随机分布且广播分组过程中可能存在冲突等因素，节点到锚节点的最小跳数存在有一定偏差.第二阶段，在锚节点估算平均每跳距离时，利用的是除本节点外所有其他锚节点，所以得到的是全网范围内的平均每跳距离，不能反映本锚节点局部范围内的网络密度分布情况，因此采用该方法得出的平均每跳距离在密度均匀的网络中影响不大，但在密度不均匀的网络中，会造成较大误差[3]. 第三阶段，极大似然与三边定位等传统定位算法仍存在较大误差，所以在计算阶段可考虑对传统数学算法的改进.

图1 锚节点算法流程图

图2 未知节点算法流程图

3 DV-HOP算法的改进

第一阶段，为了减小环境变化对算法产生的影响，可由人工布置锚节点，增加系统定位准确度.

第二阶段，未知节点和锚节点如果是以单跳方式通信，它们之间的距离即视为平均每跳距离.在通信范围内无论其相距多远，都将其跳数估计为一跳，而每跳的距离不同，用跳数乘以平均跳距来计算锚节点与未知节点的距离，必然偏离实际距离，造成节点定位出现较大的误差.如图3中的锚节点L1与锚节点L2之间的最短路径，其中每跳的长度都不同，只有最后一跳的长度接近于实际值，即节点的通信半径[4].

图3 节点路径示意图

为了避免实际距离与平均每跳距离之间出现较大的误差，可以根据RSSI损耗模型估算出两个节点之间的实际距离.如果平均每跳距离在损耗模型值范围内，则将平均每跳距离视为两通信节点间的距离，否则取模型值为两通信节点间的距离.

在实际应用中，往往节点间的距离都是曲线路程，所以，算法存在一定的误差.同时，距离锚节点路程越远的未知节点的DV-Hop 定位的精度就越差.本文的思想是采用取多个锚节点的平均每跳距离的均值来代替原算法中的平均每跳距离.改进策略为：对于选定的一个未知节点A，在其通信范围内有n个锚节点，则未知节点从通信范围内的每个锚节点处获得一个平均每跳距离，然后取平均值作为该未知节点的平均每跳距离.然后则可以用三边测量法或极大似然估计法来计算出未知节点的位置.根据未知节点在定位过程中可以找到的锚节点的个数，可以分为以下2种情况：

1)定位时，当未知节点可以找到的锚节点个数在三个或者三个以下时，或找到的锚节点共线时，则不执行极大似然法计算其位置.

2)定位时，未知节点D可以找到锚节点A1,A2,…，An(n>3)，则未知节点D平均每跳距离如公式(2)所示:

(2)

然后未知节点根据DV-Hop算法第一阶段中记录的到锚节点A1,A2,…，An的最小跳数就可以计算出未知节点到这n个锚节点的距离估计值，这样使网络充分利用了锚节点，定位更加精准[5].

传统的极大似然算法是采用多个节点对未知节点进行定位，当节点的数目较多而且连通性比较好的情况下，就可更准确计算未知节点坐标.如图所示，假设己知节点1,2,3…n的坐标为(xi，yi)，他们到未知节点的距离为Si(i=1,2,3…n)，令未知节点P的坐标为(x,y).

则根据两点间距离公式可得公式(3)：

(3)

依次用前n-1个方程去减第n个方程得到公式(4):

(4)

则公式可用线性方程AX=B表示，其中:

(5)

通过计算最小方差得待测节点的坐标X为:X=(ATA)-1ATB.

通过对上式得分析可知：由于式1中Si本身存在误差，在式2中又对其平方，会导致误差更大，所以本文采取先用第n个式子减去前n-1个式子，再对两边进行平方，这样一来，可以在一定程度减小定位误差，达到改善定位精度效果[6].

4 仿真实验与结果分析

为验证算法的可行性，在matlab中进行了DV-hop定位仿真实验.仿真实验选取场景为100 m*100 m大小的空间，信标节点个数为8个，未知节点个数90个，进行仿真测试，结果如图4-图7所示.

图4是定位节点分布图，图5为采用传统DV-hop对未知节点进行定位解算的误差曲线.

图4 节点位置示意图

图5 传统DV-hop定位误差

图6所示是基于平均跳距修正后的误差结果.图7是在基于平均跳距修正基础上对极大似然估计法改进后得到的最终改进结果.

图6 基于平均跳距修正的误差仿真结果

图7 改进的极大似然估计法仿真结果

由上述图片分析计算得，改进的DV-Hop算法精度比传统的DV-Hop算法精度提升21.8%，并且一般来说，网络中节点密度越大，定位精度越高.DV-Hop算法只能在节点分布比较密集的无线传感器网络中才能合理地估算平均每跳距离，然后才能较准确地估算出节点的位置[7].经多次实验证明，本改进算法可将定位误差控制在0.7 m以内，符合大部分高精度室内定位应用的研究.

5 结论与展望

本文在原有的DV-Hop定位基础上，对其进行仔细分析与改进，从该算法的每一阶段探寻改进策略，使算法实用性更加完善，定位结果更加准确，为无线传感网络定位方案做了进一步的铺垫.

另外，该成果是在创客教育教学实践中及大学生创新创业训练计划中通过研究生与本科生结对互助及本科生参与教师科研等方式完成的，论文也主要由学生整理及撰写，是一次有益的创新教学尝试.

[1] Wu G,Wang S,Wang B,et al.A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks[J].Computer Networks,2012,56(7):3581-3593.

[2] 赵昭，陈小慧.无线传感器网络中基于 RSSI 的改进定位算法[J].传感器技术学报，2009，22(3):391-392.

[3] 林金朝，刘海波，李国军，等.无线传感器网络中 DV-HOP 节点定位改进算法的研究[J].计算机应用研究，2009，26(4):1272-1275.

[4] 解慧英.无线传感器网络中一种改进的DV-Hop定位算法[D].武汉：武汉科技大学，2008.

[5] 张品，徐智福，孙岩.基于无线传感器网络的一种改进 DV-Hop 算法[J].电子器件， 2009，32(6)：1091-1093.

[6] Balogh L,Kollar I,Michaeli L,et al.Full information from measured ADC test data using maximum likelihood estimation[J].Measurement,2012,45(2):164-169.

[7] Pan W H,Liu X D.Wireless sensor networks based on the DV-hop localization algorithm[C].Proceedings of 2012 Fourth International Conference on Computational and Information Sciences,2012:1073-1075.

(责任编辑郑绥乾)

ImprovedDV-HopLocalizationAlgorithmforWirelessSensorNetworks

LI Li-na,WANG Yue,ZHANG Xiao-dong,LEI Hao-dong

(Collegeofphysics,LiaoningUniversity,Shenyang,Liaoning,110036,China)

Aiming at the problem of low positioning accuracy of DV-hop positioning algorithm,proposed an improved DV-hop algorithm,and the basic principle of improvement is introduced in detail.In the second phase of the algorithm,the RSSI algorithm is used to correct the average hop distance,and the third stage uses the method of reducing the square after the first,and improves the calculation procedure of the maximum likelihood estimation method,thus reducing the computational error.The improved algorithm is simulated and analyzed by using matlab.The simulation results show that compared with the traditional DV-Hop localization algorithm,the localization of the improved algorithm is decreased by 21.8%,and the positioning accuracy is greatly improved without additional hardware overhead.

DV-Hop location algorithm;Wireless sensor networks;Maximum likelihood method

TN 929.5

A

1000-5846(2017)04-0320-05

2017-08-15

辽宁大学教学改革项目(JG2016YB0043)；辽宁省大学生创新创业项目(201710140000188)

李丽娜(1973-)，女，满族，辽宁本溪人，副教授，硕士研究生导师，主要从事物联网感知层相关技术研究；

王越(1993-)，男，汉族，辽宁本溪人，硕士研究生，主要从事无线传感网络技术及应用研究.