基于跳距修正的DV-Hop改进定位算法研究

李琳芳,崔微微,赵欣

（河南科技学院,河南新乡453003）

基于跳距修正的DV-Hop改进定位算法研究

李琳芳,崔微微,赵欣

（河南科技学院,河南新乡453003）

针对DV-Hop（Distance Vector-Hop）定位算法在估算跳距时存在较大误差的情况,分析了跳距影响因子,提出了一种跳距修正算法.该算法通过对每跳的平均距离以及跳数进行加权处理减少跳距误差.仿真结果表明,在相同网络环境下,改进后的DV-Hop算法在不增加硬件开销的基础上提高了定位精度.

无线传感器网络；节点定位；定位算法；DV-Hop

无线传感器网络（WSN）是将大量传感器节点部署在某一区域,借助传感器节点进行信息获取、传输以监测目标区域[1].无线传感器网络中监测及其他许多服务都是基于位置信息的,因此获悉传感器节点位置显得尤为重要[2].传感器节点因应用环境的特殊性,事先将所有节点布置在感知区域不太现实,受成本、能耗等问题的限制,为每个传感器节点安装GPS定位模块或其他外部设施也不实际[3],必须采用其他方法实现传感器节点定位.

无线传感器网络节点定位技术大体分为基于测距的和无需测距的两类.基于测距的定位技术以已知方位的信标节点作为参考坐标点,通过几何测距计算节点的位置[4],目前主要包括TOA,TDOA,AOA、RSSI等算法[5].基于非测距的定位技术一般是根据网络本身的联通性、路由及拓扑结构等信息来估计节点位置,目前主要包括APIT算法、质心法、DV-Hop算法等[6].

基于测距的定位算法优势在于定位精度高、效果好,但需对节点配置硬件装置,定位过程中能耗较大,受环境的影响较大；基于非测距的定位算法则因低成本优势受人推崇,由于对硬件要求低,使得它更适合大规模网络,而且受环境的影响较小,虽然定位精度相对较低,但能满足大多数的传感器应用要求[7]. DV-Hop是一种典型的非测距定位算法,是很多定位算法的思想依据.本文在阐述DV-Hop算法原理及分析DV-Hop算法误差基础上,提出了一种改进算法,从平均跳距与跳数两方面做加权修正处理.

1 DV-Hop定位算法

1.1 DV-Hop定位原理

DV-Hop算法大体分以下三个步骤[8]：

（1）记录信标节点到未知节点的最小跳数

信标节点通过广播方式向邻居节点发送包含跳数的信息元组,邻居节点自动记录下该信标节点的最小跳数信息,然后把跳数加1后发送给邻居节点,这个阶段后,未知节点记录了与每个信标节点的最小跳数.

（2）计算未知节点与信标节点的距离

首先,经过第一步,信标节点可获得与其他信标节点的距离与最小跳数信息,根据公式（1）估算每跳平均距离

式（1）中（xi,yi）,（xj,yj）分别为信标节点i、j的坐标,hj为信标节点i与j之间的最小跳数.

然后,信标节点以广播方式将每跳平均距离告知网络中的未知节点,未知节点以收到的第一个每跳平均距离为参考值,这样确保未知节点从最近的信标节点获取每跳平均距离.

最后,根据之前记录的跳段数信息,用每跳平均距离乘以跳数,估算未知节点到每个信标节点的距离.

（3）计算未知节点坐标

当未知节点估算出与多个信标节点的距离后,利用三边测量法或极大似然估计法计算其坐标.

1.2 DV-Hop算法误差分析

DV-Hop算法的核心思想是用每跳平均距离乘以跳数来估计两个节点间的距离,用估计距离代替两个节点间实际直线距离是DV-Hop算法一个主要的误差来源.

DV-Hop算法误差分析示意图如图1所示.

图1 DV-Hop算法误差分析示意Fig.1 DV-Hop algorithm error analysis schematic

图1中L1、L2、L3为已知的信标节点,M为未知节点,传感器节点受通信半径的限制,不是所有节点都可以直接通信.图1中实线代表节点间可直接通信,虚线代表节点间不能直接通信,需要借助中间节点的跳转实现通信.

根据DV-Hop算法,由公式（1）可求得L1每跳平均距离

节点M与信标节点L1跳数最小,所以M的每跳平均距离为15,M与L1之间跳数为1,估算M与L1跳距为15×1=15,在图1中可知节点M与信标节点L1的实际距离为30.由此可知,估算的跳距与节点间实际距离是存在误差的,所以尽可能的使得估算的跳距与实际距离接近便可提高定位精度.

2 DV-Hop改进算法

基于对DV-Hop算法误差分析,节点定位误差主要由节点间估计距离引起,而估计距离受每跳平均距离和跳数影响,下面针对这两方面对DV-Hop算法进行改进.

2.1 每跳平均距离修正

针对DV-Hop算法中对每跳平均距离的简单取值进行修正,对每跳平均距离作归一化处理,为每跳平均距离求得一个加权系数,用加权后的每跳平均距离代替原始每跳平均距离.

改进算法的每跳平均距离计算步骤如下：

步骤1：根据公式（1）求得每个信标节点的每跳平均距离HopSizei.

步骤2：假设网络中有n个信标节点,且未知节点能收到这n个信标节点的信息.根据公式（2）求得网络中信标节点的每跳平均距离的平均值HopSizeAVG

步骤3：对于n个信标节点,HopSizei与HopSizeAVG相差较小的话赋予一个较大的权值,反之则赋予一个较小的权值.根据公式（3）求得权重因子δi,根据公式（4）对δi作归一化处理得到加权系数Ci

步骤4：根据公式（5）求得修正后的每跳平均距离HopSize

2.2 跳数修正

在DV-Hop算法中,用每跳平均距离与跳数乘积代替节点间的直线距离是存在误差的,跳数越多,累积误差也越大.针对这一问题,可以对不同范围内的跳数赋予不同的权重,以改善跳数过多造成的累积误差过大的现象,使得跳段距离与直线尽可能的拟合.权重赋予原则是跳数越少,权重越大；跳数越多,权重越小[9].通过反复试验构建如公式（6）所示的模型

式（6）中w是权重,hop是跳数,max不表示具体数值,代表极大值,在DV-Hop算法步骤（1）（2）中,涉及到跳数hop的,根据公式（6）进行加权处理,用w×hop代替hop值.

3 仿真及分析

3.1 仿真环境配置

将DV-Hop算法与改进算法在MATLAB平台上进行仿真分析以检验改进算法的性能.

在100 m×100 m在正方形区域内,随机分布200个节点,其中10个信标节点,190个未知节点,节点通信半径R=40 m.节点随机分布图如图2所示,*代表未知节点,o代表信标节点.

图2 节点随机分布图Fig.2 Node random distribution

3.2 实验及结果分析

考虑到节点定位误差受信标节点数量的影响,为更全面地检验改进算法的性能,分别进行了节点数量固定不变与节点数量变动两种情况下的实验研究.

3.2.1 信标节点数量固定不变在信标节点数量保持不变的情况下,节点位置误差如图3所示.图a为DV-Hop算法定位未知节点的位置误差,图3-b为改进算法定位未知节点的位置误差,横轴为未知节点,纵轴为误差距离.

图3 节点位置误差Fig.3 Node position error

根据图3-a与b仿真曲线可知,改进算法单个未知节点定位误差距离整体比传统DV-Hop算法小.定义平均定位误差为

式（7）中eAVG代表平均定位误差,ej表示单个未知节点的误差,n表示未知节点数量.根据公式（7）利用MATLAB仿真求得在上述实验环境配置下,传统DV-Hop算法的平均定位误差为34.150 4 m,改进算法的平均定位误差为24.495 4 m,改进算法平均定位误差距离比传统DV-Hop算法小.

3.2.2 信标节点数量变动网络中信标节点比例与定位误差关系如图4所示.横坐标为信标节点在总节点中所占比例,纵坐标为误差精度.实线表征的是传统DV-Hop算法定位误差与信标节点的比例关系,虚线表征的是改进算法定位误差与信标节点的比例关系.

图4 信标节点比例与定位误差关系Fig.4 Relationship between the ratio of beacon nods and location error

定义误差精度为

式（8）中eAVG为平均定位误差,根据公式（7）可求得,R为通信半径,仿真环境配置R=40 m.

根据图4仿真曲线可知,DV-Hop算法与改进算法的定位误差随网络中信标节点比例的增加都在减小,定位精度都有所提高,而改进算法的定位精度要始终优于DV-Hop算法.

4 小结

针对DV-Hop算法中跳段距离代替节点间实际直线距离误差过大问题,提出了一种改进算法,从平均每跳距离和跳数两方面进行加权修正.通过配置仿真环境,以MATLAB为平台,对DV-Hop算法和改进算法进行实验分析.实验结果表明,与传统DV-Hop算法相比,在不需要增加额外硬件设施的情况下,改进算法极大地减少了定位误差,改善了定位效果,是一种可行算法.当然在网络节点数量多的时候,改进算法计算量较大,仿真时间较长,在这点上,改进算法还有改进的空间.

[1]胡淼,陶正苏.一种基于可移动锚节点的DV-HOP改进定位算法[J].电子设计工程,2011,19（24）：98-100.

[2]张宏君,毛永毅.改进的无线传感器网络节点定位算法[J].计算机应用,2012,32（8）：2103-2105.

[3]李成岳.基于DV-Hop的无线传感器网络节点定位算法研究[D].吉林：吉林大学,2011.

[4]曾星,宋萍.一种基于航迹推算与接收信号强度指示相结合的移动传感器网络节点定位方法[J].科学技术与工程, 2014,14（4）：245-249.

[5]Niculescu D,Nath B.Ad hoc positioning system（APS）using AOA[J].INFOCOM,Twenty-second Annual Joint Conference of the IEEE Computer and Communications,San Francisco,CA,2003：1734-1743.

[6]刘毓,马晓辉,曹津铭.基于WSN特点对DV-HOP算法改进的研究[J].西安邮电学院学报,2012,17（6）：24-26,55.

[7]柳小康.DV-Hop定位算法的定位精度优化算法[D].大连：大连理工大学,2013.

[8]蒋馥珍,王峰,王康,等.基于加权的DV-Hop在WSN中的应用于研究[J].电视技术,2013,37（19）：181-183.

[9]肖丽萍,刘晓红.一种基于跳数修正的DV-Hop定位算法[J].传感技术学报,2012,23（12）：1726-1728.

（责任编辑：卢奇）

Research on DV-Hop improved algorithm based on hop-distance correction

LI Linfang,CUI Weiwei,ZHAO Xin
（Henan Institute of Science and Technology,Xinxiang 453003,China）

Because of a big error in estimating hop-distance for DV-Hop localization algorithm,a new algorithm was proposed after analyzing the influence factors of hop-distance.In the new algorithm,the average distance of each hop and hop count were weighted to reduce the hop-distance error.The simulation results showed that under the same network environment,the improved algorithm could improve the positioning accuracy without increasing the hardware cost.

wireless sensor network;node localization;localization algorithm;DV-Hop

TN929.5；TP212.9

A

1008-7516（2016）01-0051-06

10.3969/j.issn.1008-7516.2016.01.012

2016-01-12

河南省教育厅科学技术研究重点项目(14B120009)

李琳芳(1988―),女,河南新乡人,硕士,助教.主要从事信号与信息处理研究.