无线传感器网络中关于DV-Hop定位算法的改进

邹佳顺　张永胜

(山东师范大学信息科学与工程学院　山东 济南 250014) (山东省分布式计算机软件新技术重点实验室　山东 济南 250014)



无线传感器网络中关于DV-Hop定位算法的改进

邹佳顺张永胜

(山东师范大学信息科学与工程学院山东 济南 250014) (山东省分布式计算机软件新技术重点实验室山东 济南 250014)

针对无线传感器网络非基于测距的DV-Hop定位算法中，锚节点与未知节点间平均跳距估计的不足，提出一种改进的DV-Hop算法。通过计时器来计算全网平均每跳处理时间与局部每跳处理时间的比值，并利用该比值通过加权平均的方式修正平均跳距。根据仿真实验结果可知，改进算法减小了定位误差，具有更高的定位精度。

无线传感器网络DV-Hop算法跳距计时器

0　引　言

无线传感器网络WSN(WirelessSensorNetwork)主要是用来监测部署区域的各种环境特性，传感器节点以自组织方式构成的无线网络方式进行通信[1]。但不知道相应位置信息的传感数据往往是没有任何意义的，因此对节点位置信息的定位操作显得格外重要[2]。而传统的定位方式如全球定位系统(GPS)、人工测量和标定等方法由于成本过高等原因而无法应用于WSN中[3]。

目前的WSN定位算法的研究基本是通过测量节点之间的距离信息或信息交换实现定位。根据定位方式的不同可以分为基于测距的定位算法和非基于测距的定位算法两类。与前者相比，后者不需要额外的硬件支持成本较低，因此受到广泛的关注。目前具有代表性的非基于测距定位算法主要有质心算法、凸规划算法、DV-Hop算法及APIT算法等[4,5]。DV-Hop算法是为了克服直接三边定位算法的缺点而提出的，该算法通过未知节点到锚节点的平均跳距与它们之间跳数的乘积表示两者的距离，再用三边定位算法或最大似然估计计算出未知节点的位置信息。该算法的缺点是，对于节点分布不均匀的WSN，节点定位误差会明显增大。针对该问题本文提出一种改进的DV-Hop算法，可大大提高定位精度。

1　相关工作

DV-Hop算法是目前应用最广泛的定位算法之一，关于算法的改进性研究，国内也取得了一些研究成果。如文献[6]提出了一种对DV-Hop算法的改进方案，通过对平均跳距采用加权处理的方式进行修正，提高定位的精度。文献[7]根据多跳的校正值和锚节点的平均每跳距离误差对未知节点与锚节点之间的距离做出修正。文献[8]通过将邻居节点间距离与连通性差异联系起来，定义了一种新的邻居距离估计方法，计算出更精确的邻居距离。文献[9]考虑使用多个锚节点估算的平均跳距离并且采用加权平均跳距代替传统算法中的平均跳距。文献[10]通过添加信息接收及参与定位的节点条件减少算法的定位误差。文献[11]根据无线信号在同种介质中传播速度的不变性对平均跳距进行改进，提高定位精度。

传统DV-Hop算法的不足之处在于，该算法比较适合锚节点分布均匀、密集型的WSN中,因为在这种情况下求得的每跳平均距离值才能更接近实际距离值[12]。而对于分布较随机，密度差距较大的WSN，该算法产生的定位误差则较大。

本文在文献[11]相关研究的基础上提出一种DV-Hop改进算法，综合考虑所有锚节点的平均跳距，通过加权平均的方式计算未知节点附近的跳距，具有较高的定位精度。

2　DV-Hop定位算法

2.1DV-Hop定位算法步骤

WSN中的节点分为两类，一类是通过人工布设或安装GPS等定位设备获得自己物理位置信息，称为锚节点或信标节点。另一类是自身无法定位的节点称为未知节点。DV-Hop定位算法可分为以下几个步骤：

1) 利用矢量路由协议，锚节点广播位置信息数据包，未知节点获得距离所有锚节点最小的跳数信息。

2) 每个锚节点接收到其他锚节点传来的位置和跳数信息后，估计全网的平均跳距如下式:

(1)

其中，(xi,yi)，(xj,yj)是锚节点i和j的坐标。hi是锚节点i和j之间的跳段数。锚节点将计算出的平均跳距广播至全网，每个未知节点以第一个接收到的跳距信息为准，这样基本可以保证每个未知节点以离它最近的锚节点计算出的平均跳距为准。

3) 未知节点(xk,yk)根据自身与锚节点之间跳数以及平均跳距计算自身到各锚节点之间的估计距离值。具体公式如下式:

di=Di×h(i,k)

(2)

4) 使用三边测量法确定未知节点的位置。

2.2三边测量法

图1　三边测量法示意图

三边测量法是一种基本的定位方法，图1为三边测量法的示意图。

如图1所示，未知节点D与三个锚节点A、B、C之间的距离分别为d1、d2、d3,A、B、C三点的坐标分别为(x1,y1)、(x2,y2)、(x3,y3)。假设未知节点D的坐标为(x,y)，则可以通过下列方程组式(3)求得D点的坐标信息。

(3)

根据式(3)可以算出未知节点D的位置(x,y)，当未知节点接收到超过3个锚节点的位置信息时，会计算出多个解，取平均值作为未知节点的位置。

3　DV-Hop算法的改进

3.1DV-Hop定位算法的缺陷

图2是DV-Hop定位算法的示意图。其中A、B、C节点是已知位置信息的锚节点，其余节点为未知节点。且AB之间的距离为30m，BC之间的距离为20m，AC之间的距离为40m。

图2　DV-Hop定位算法示意图

根据DV-Hop定位算法步骤2中的式(1)，锚节点A可计算平均跳距值为(30+40)/(3+4)，锚节点B可计算平均跳距值为(30+20)/(3+2)，锚节点C可计算平均跳距值为(20+40)/(2+4)。不同锚节点计算的校正值各不相同，定位误差就是这样产生的。通过分析可知，对于分布较均匀的节点，DV-Hop算法计算的跳数校正值能够在一定程度上反应整体网络的跳距，但当节点分布较随机时出现的误差往往会增大。

3.2DV-Hop定位算法的改进

本文设定一种计时数据包TimePacket用以测试路径的传送时间。数据包不含实际数据信息。在建立网络拓扑结构时在未知节点与未知节点以及未知节点与锚节点之间传送。

本文的改进DV-Hop算法步骤如下：

1) 锚节点广播位置信息数据包，并且计时器开始计时，所有未知节点获得距离各锚节点的最小跳数信息。

2) 锚节点收到其他锚节点传来的广播数据包后利用式(1)计算平均跳距，并立即返回带自身标记的TimePacket数据包。

3) 锚节点收到其他锚节点传来的TimePacket数据包时，分别记录时间，并停止计时。并利用下式计算全网平均每跳处理时间t，t大于平均每跳的传送时间，因为包括传感器节点对数据的处理时间。各锚节点将平均跳距与t进行广播。如锚节点i需将计算出的平均跳距Di与ti广播至全网。

(4)

4) 未知节点接收到各锚节点传来的平均跳距D及全网平均每跳处理时间t后向邻节点广播含有自身标记的TimePacket数据包，计时器开始计时。

5) 邻节点接收到数据包后在该数据包中加入自身标记并返回数据包。

6) 未知节点收到邻节点返回的数据包时停止计时器的计时，通过下式计算局部每跳处理时间T。不含自身标记的未知节点收到数据包后丢弃。

(5)

其中，该式的分子表示每个邻节点处理并返回数据包所需时间之和；分母表示两倍的邻节点总数,n为其邻节点的个数，可通过接收到的返回数据包进行确定。T与t所表示的都是平均每跳处理时间，但前者表示的是未知节点的局部信息，一个表示的是全网信息。因此可以通过式(6)在一定程度上表示未知节点附近的跳距与全网平均跳距之间的比例。

(6)

因此可以将W的值作为计算局部未知节点跳距的权值。其中Tj表示未知节点j的局部每跳处理时间。当T值明显大于t值时，说明该节点附近平均每跳处理时间较长，在一定程度上表示该节点附近的跳距比全网平均跳距较大，反之则较小。

7) 根据每个锚节点计算的平均跳距和式(6)中提供的权值可通过下式计算未知节点的平均跳距为：

(7)

式中m表示所有锚节点的数目，未知节点通过对所有锚节点计算出的校正值进行加权平均，得出每个未知节点的跳距，并进一步求得未知节点到各锚节点之间的距离。

8) 通过三边测量法确定未知节点的位置。

4　仿真实验与分析

为验证改进算法的性能，本文采用Matlab进行仿真。在100m×100m的网络环境中进行实验，分别控制传感器节点个数从20到100进行变化，锚节点的比例按5%、10%、…、40%进行变化，节点通信半径变化范围为15m到40m，从平均定位误差及节点平均剩余能量两方面与传统DV-Hop算法进行比较。其中节点的分布均符合二维随机分布，每种情况在仿真实验中运行100次，仿真结果取其平均值。

节点的定位误差计算公式如下：

(8)

其中(xm,ym)是节点的实际位置，(xn,yn)为节点的估计位置，R为节点的通信半径。在仿真实验中，是以平均定位误差作为比较的参数。平均定位误差为网络中所有未知节点的定位误差之和与未知节点个数p的比值。可通过下式计算得出。

(9)

由于本文算法与文献[11]使用的原理相同，都是利用无线信号在同种介质中传播速度的不变性，以及发送数据包的形式进行计时，因此具有较强的可比性。本文在仿真实验结果中也加入了与文献[11]中算法性能的对比。

图3为节点数目与平均定位误差之间的关系，在实验区域固定节点通信半径为15m，锚节点比例固定为20%，节点数从20递增变化到100。

图3　节点数与平均定位误差关系

由图3中改进算法与标准算法的对比可以明显地看出，在节点数目相同的情况下，本文的改进算法在平均定位误差方面明显优于标准算法，尤其是在节点稀疏的情况下，优势更加明显。在节点数目为30时，与标准算法相比，改进算法的平均定位误差降低了约16%，就算是在节点比较密集时本文算法也有较高的定位精度。如节点数目为100时，定位误差降低了约13%。与文献[11]算法相比也具有一定的优势。

图4为锚节点比例与平均定位误差之间的关系。在实验区域固定节点通信半径为15m，节点数目为100，逐渐递增锚节点的比例。

图4　锚节点比例与定位误差的关系

由图4中的对比可以看出，随着锚节点的增加,三种算法的平均定位误差都在呈递减趋势。本文中的改进算法比标准DV-Hop算法具有明显的优势。且本文的改进算法明显优于标准算法，如在锚节点比例较少的5%时，改进算法的平均定位误差降低了约14%，在锚节点比例较多的40%时也降低了大约10%。而与文献[11]中的改进算法相比，定位误差也具有大幅度降低。

图5为节点通信半径与平均定位误差之间的关系，在实验区域固定锚节点比例固定为20%，节点数目为100，节点通信半径从15m递增至40m。

图5　节点通讯半径与定位误差的关系

根据图5中三种算法的比较可知，本文改进算法明显优于标准DV-Hop算法。在通信半径为15m时，改进算法的平均定位误差降低了约8%。在通信半径为40m时降低了约7%。定位精度明显高于文献[11]中的定位算法。

此外本文还针对节点的剩余能量方面与标准算法进行了比较，对比结果如图6所示。

图6　节点平均剩余能量与时间的关系

图6是在实验区域中固定节点通信半径为15m，锚节点比例固定为20%，节点数为100的环境下进行的，通过1.4Mbps的802.11MAC进行通信。通过对三种算法进行比较可知，本文的改进算法在节点能耗方面与标准DV-Hop算法相比具有一定的不足。主要是由于在定位操作中本文的改进算法需要消耗较大的能量。而与文献[11]算法相比，能量消耗方面并未有较大的差距，但本文算法的定位精度却远远高于文献[11]中的定位算法。因此在实际使用时，可以根据实际情况对本文算法和标准DV-Hop算法进行选择。对定位精度要求较高时可以采用本文算法，对能耗要求较高时可采用标准算法。

5　结　语

本文对无线传感器网络中的标准DV-Hop定位算法进行了简单的介绍。针对DV-Hop算法定位时的缺陷提出了一种改进算法。在估计平均跳距时并不仅仅以最近的锚节点计算出的校正值为准，而是根据局部与全网每跳处理时间的比值对所有锚节点计算出的平均跳距进行加权平均。仿真实验表明，改进算法具有较高的定位精度。但本文的改进算法也存在不足，由于传输数据量的增加，在能量消耗方面比标准算法略高，因此在定位时可根据实际需要对改进算法与标准算法的选择进行权衡。

[1] 官小云,杨培会,刘珂.移动无线传感器网络定位研究[J].计算机应用与软件,2014,31(4):138-140.

[2] 郑远,蔡宇,赵锐.一种兼顾性能与能耗的DV-Hop改进算法[J].计算机应用与软件,2014,31(4):269-273.

[3] 周小波,乔钢柱,曾建潮.无线传感器网络中基于RSSI的加权DV-HOP定位方法[J].计算机工程与应用,2011,47(14):109-111.

[4] 赵军,裴庆祺,徐展琦.无线传感器网络近似三角形内点测试定位算法[J].计算机工程,2007,33(5):109-112.

[5]NIculescuD,NathB.DVbasedpositioninginadhocnetworks[J].JournalofTelecommunicationSystems,2003,22(1-4):267-280.

[6] 刘文远,王恩爽,陈子军.无线传感器网络中DV-Hop定位算法的改进[J].小型微型计算机系统,2011,32(6):1071-1074.

[7] 张佳,吴延海,石峰,等.基于DV-HOP的无线传感器网络定位算法[J].计算机应用,2010,30(2):323-326.

[8] 江禹生,陈跹,李萍.可信邻居距离估计的DV-Hop校准算法[J].计算机应用,2013,33(11):3016-3018.

[9] 王新生,赵衍静,李海涛.基于DV-Hop定位算法的改进研究[J].计算机科学,2011,38(2):78-90.

[10] 张静,曹敦,傅明,等.DV-Hop算法定位误差和覆盖率的改进[J].计算机应用,2011,31(7):1944-1947.

[11] 赵灵锴,洪志全.基于无线传感器网络的DV-Hop定位算法的改进[J].计算机应用,2011,31(5):1189-1192.

[12] 石为人,贾传江,梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报,2011,24(1):83-87.

IMPROVEMENTOFDV-HOPLOCALISATIONALGORITHMINWIRELESSSENSORNETWORKS

ZouJiashunZhangYongsheng

(School of Information Science and Engineering,Shandong Normal University,Jinan 250014,Shandong,China) (Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology,Jinan 250014,Shandong,China)

Inrange-freebasedDV-Hoplocalisationalgorithminwirelesssensornetworks,theestimationofaveragehopdistancebetweenanchornodesandunknownnodeshasshortcomings.Tosolvetheproblem,thepaperproposesanimprovedDV-Hopalgorithm.Itcalculatestheratiobetweentheaverageprocessingtimeperhopinwholenetworkandtheprocessingtimeperhopinlocalnetworkbythetimer.Basedontheratio,itcorrectstheaveragehopdistancebymeansofweightedaverage.Accordingtotheresultofsimulationexperiment,theimprovedalgorithmreducesthepositioningerrorandhashigherpositioningaccuracy.

WirelesssensornetworksDV-HopalgorithmHopdistanceTimer

2014-09-15。山东省自然科学基金项目(ZR2011FM0 19)。邹佳顺，硕士生，主研领域：网络安全，计算机网络及网络模型。张永胜，教授。

TP393.01

ADOI:10.3969/j.issn.1000-386x.2016.03.033