无线传感网中DV-Hop定位算法的改进研究

邴晓瑛，徐保国

（1.江南大学轻工过程先进控制教育部重点实验室，江苏 无锡　214122；2.江南大学物联网工程学院，江苏 无锡　214122）

无线传感网中DV-Hop定位算法的改进研究

邴晓瑛1，徐保国2

（1.江南大学轻工过程先进控制教育部重点实验室，江苏 无锡214122；2.江南大学物联网工程学院，江苏 无锡214122）

针对网络拓扑结构不规则的无线传感器网络中经典DV-Hop定位算法计算未知节点位置存在较大误差的问题，提出了一种基于多通信半径修正跳数的改进算法。通过对通信半径进行分级细化，利用多级通信半径修正信标节点到信邻节点的跳数信息，使未知节点的平均跳距更符合实际网络情况。仿真结果表明，在相同的网络拓扑结构下，改进的定位算法有效的提高了传感器节点的定位精度。

无线传感器网络；DV-Hop定位；多通信半径；定位精度

无线传感器网络（Wireless Sensor Network，WSN）现已广泛应用于很多领域，而传感器节点的位置特别重要，是WSN应用的基础。现阶段定位算法主要分为两类，基于测距（Range-based）的定位算法和基于非测距（Range-free）[1]的定位算法。其中DV-Hop[2]算法是典型的基于非测距的定位算法，该算法硬件成本较低、能耗较小，传输的信号受外界影响较小，并且能满足大部分实际应用对定位精度要求。

美国Rutgers University的Dragos Niculescu等利用GPS和距离矢量路由思想提出了DV-Hop算法[3]，定位精度较低。随着社会的发展需要，对许多应用的定位精度要求愈来愈高。许多学者对经典的DV-Hop算法进行了深入研究并改进，文献[4]采用双通信半径细化节点间的跳数信息，提高定位精度；文献[5]利用RSSI修正节点间的跳数信息，使跳数值更精确；文献[6]利用设定跳数阈值选择适当的信标节点估计平均每跳距离，未知节点一句跳数对信标节点分类，并加权修正距离，提高定位精度。

文中深入地分析了传统DV-Hop定位算法定位误差大的原因，在不改变传统算法框架的基础上，利用多通信半径来修正传统算法第一阶段得到的未知节点与信标节点间的最小跳数，使未知节点与信标节点间的距离更接近真实值。实验结果表明，改进的算法能有效的减小定位误差，提高定位精度。

1　问题分析

1.1DV-Hop定位算法

根据DV-Hop定位算法第一、二阶段得到的未知节点D （x，y）与信标节点（x1，y1），（x2，y2），…，（xn，yn）最小跳数与平均每跳距离[7]，求得相应节点间距离为d1，d2，…dn，则

可表示为线性方程组AL+ε=b，ε为n-1维随机误差向量，其中L=（x，y）T，则最小二乘法求得方程的解为L=（ATA）-1ATb。

1.2误差分析

在经典DV-Hop定位算法中，利用到未知节点最近的信标节点的估算平均跳距与最小跳数乘积等效替代其直线距离，精确度受网络连通度影响较大。经过深入分析，最小跳数信息是造成误差原因之一。

DV-Hop定位算法中，选择具有最少折点的几个跳段等效为未知节点与信标节点之间的直线段，那么该折线段中各点越接近共线，误差越小。由于网络中节点随机分布，共线概率较低，误差必然存在。未知节点与信标节点间的跳数越多，与其相关的测量dn距离误差越大，式（3）中向量b的每个元素均包含测量距离dn，导致误差累加。

针对上述DV-Hop定位误差的产生的原因，本文对如何精确未知节点与信标节点间的最小跳数作出相应的改进研究。

2　多通信半径改进跳数信息

2.1基本思想

在DV-Hop定位算法中，两点之间的直线距离小于通信半径，即将其记为1跳。若网络中节点分布如图1所示，设通信半径R=30 m，从图中可以看出，信标节点O可以与节点A、B、C进行通信，那么HopOA=1，HoOB=1，HopOC=1，但是OA与OC的距离相差较大，OD间跳数记为2跳时，对计算信标节点O平均跳距影响比较大。在计算未知节点与信标节点最小距离时，这种计算节点间最小跳数的机制也会导致误差的产生，并在定位过程中继续累加误差。若能将信标节点到信邻节点间的跳数分级细化，必然能减小误差，提高定位精度。文中提出了一种利用多通信半径来精确信标节点与信邻节点间的跳数，减小定位误差。

图1　多通信半径跳数计算Fig.1　More communication radius calculation

2.2具体步骤

设网络通信半径为R，将信标节点与信邻节点间分为m级，网络中各信标节点与其邻居节点的实际距离为d，跳数记为H1，i∈[1，m]且为正整数，则

根据式（4），若取R=30m，m=3，则图1中的OA、OB、OC、 OD跳数值为信标节点与信邻节点的跳数值不再是整数，是更加精确的小数，与距离更接近正比关系，有效的提高了数据的精确性，减小定位误差。

具体步骤如下：

1）设定m，R值，首先取i=1；

2）若i

4）间隔时间t，令i=i+1，转向步骤2）；

5）信标节点以通信半径R在网络中广播自身信息分组，接收节点每接收到一个分组信息，判断是否为记录的最小跳数值。若是，保存该信标节点的最小跳数并将hop=hop+1转发给邻居节点；若不是，将原来已保存的最小跳数值加1转发给邻居节点。若该分组来自同一信标节点，则忽略。

2.3改进DV-Hop具体实现步骤

基于多通信半径改进DV-Hop定位算法流程图如图2。

图2　改进DV-Hop算法流程图Fig.2　Improved DV-Hop algorithm flow chart

3　仿真实验及结果分析

3.1仿真环境及参数设定

本文采用MATLAB仿真软件实现传感器节点定位算法。假设所有传感器节点均匀随机分布在100 m×100 m的正方形区域内。

为了能更直观的评价基于多通信半径改进DV-Hop算法的性能，将其通信半径等级分为m=1，2，3，4，5级进行对比仿真实验，并比较分析实验数据。为确保结果的准确性，在每种测试条件下，算法分别进行50次随机分布测试，取算术平均值。定位算法性能评价标准为归一化定位误差，其计算公式为：

其中，（xir，yir），（xie，yie）代表第 i个未知节点的实际坐标和通过定位算法得出的估计坐标，R为网络通信半径，N为未知节点总数。

3.2仿真结果分析

3.2.1信标节点比例对定位精度的影响

图3表示了节点总数N=100，通信半径R=30 m，信标节点比例在5%～35%变化时，通信半径分级m不同时节点定位误差图。由图可知，m=1，2，3，4，5时定位误差与信标节点比例整体上成反比。在信标节点比例为5%～15%时，定位误差受信标节点比例影响较大，当信标节点比例超过15%后，定位误差变化均趋于稳定。由图可知，m=1，2，3时定位误差减小效果较明显，m=4，5时定位误差减小的较少，m=2较m=1 即DV-Hop定位算法定位误差平均减小了约17%；m=3较m=2定位算法定位误差平均减小了约12%；m=4较m=3定位算法定位误差平均减小了约8%；m=5较m=4定位算法定位误差平均减小了约5%。

图3　信标节点比例不同时的定位误差Fig.3　Localization error with different Beacon node ratio

3.2.2通信半径对定位精度的影响

图4表示了节点总数N=100，信标节点数为30，通信半径在22～50 m变化时，通信半径分级m不同时节点定位误差图。由图可知，m=1，2，3，4，5时定位误差与通信半径变化整体上成反比。这是由于通信半径越大，每个节点的邻居节点越多，网络连通度越高，节点的平均跳距和跳数信息越准确。由图可知，m=1，2，3时定位误差减小效果较明显，m=4，5时定位误差减小的较少。m=2较m=1即DV-Hop定位算法定位误差平均减小了约15%；m=3较m=2定位算法定位误差平均减小了约10%；m=4较m=3定位算法定位误差平均减小了约6%；m=5较m=4定位算法定位误差平均减小了约4%。

图4　通信半径不同时的定位误差Fig.4　Localization error with different communication radius

根据图3、图4，通信半径分为级时节点定位误差较经典DV-Hop减小的较明显，由于信标节点每广播一次自身信息分组，都要有一定的能量消耗，综合考虑，选择通信半径分为3级，细化精确节点间的跳数信息较合理。

4　结　论

文中提出了一种基于多通信半径分级细化节点间跳数的改进DV-Hop定位算法。通过多通信半径精确节点间跳数信息，使求得的未知节点坐标更接近实际坐标，提高定位精度。仿真实验结果表明，文中改进[9-10]算法在相同的网络拓扑[8]结构下，有效的提高了传感器节点的定位精度。如何更有效的节约网络能量开销，也是未来的一个研究方向。

[1]Maung，N.A.M.，Kawai，M.Experimental Evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks[J].2014，50（17）:1246-1248.

[2]Gayan，S.，Dias，D.Improved DV-Hop algorithm through anchor poition re-estimation[C].Wireless and Mobile，2014 IEEE Asia Pacific Conference on.2014:126-131.

[3]NICULESCU D，NATH B.DV Based Positioning in Ad Hoc Networks[C].Telecommunication Systems，2003:22（1/2/3/ 4）:267-280.

[4]李娟，刘禹，钱志鸿.基于双通信半径的传感器网络DVHop定位算法[J].吉林大学学报，2014，44（2）:502-507.

[5]温江涛，范学敏，吴希军.基于RSSI跳数修正的DV-Hop改进算法[J].传感技术学报.2014，27（1）:113-117.

[6]祝宇鸿，历彦恺，胡俊.基于跳数阈值和节点分类的DV-Hop算法[J].吉林大学学报：信息科学版，2014，32（4）:407-412.

[7]Munsuck Jang，Inseong Song.A study on Localization Algorithm using Hop Count and RSSI[J].International Journal of Control and Automation，2013，6（3）:267-280.

[8]贾晓强.一种基于C/S模式的中间件SDO的P2P平台的网络拓扑设计[J].电子设计工程，2014（13）:31-33.

[9]张仁烨，白恩健.降低MIMO-OFDM系统峰均比的改进PTS算法[J].电子科技，2014（12）:1-4.

[10]陈茜.流程改进提升检测实验室管理水平[J].质量与标准化，2013（4）:37-40.

Localization method based on modified particle swarm optimization for wireless sensor networks

BING Xiao-ying1，XU Bao-guo2
（1.Key Laboratory of Industrial Advanced Process Control for Light Industry，Ministry of Education，Jiangnan University，Wuxi 214122，China；2.School of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

An improved algorithm based on more communication radius and weighting corrected the unknown nodes'hop-size in order to solve the problem that when using the traditional DV-Hop algorithm localization error is too large in irregular topology network.The communication radius is graded，and hops between beacon nodes and neighbor nodes are corrected by more level communication radius，in order to make the hop size of unknown nodes more conform to the actual network.The simulation experimental results showed that，the proposed algorithm possesses of higher location precision in the same network topology，broaden the application scope of localization algorithm.

WSN；DV-Hop localization；more communication radius；location precision

TN92

A

1674－6236（2016）01-0086-03

2015-03-08稿件编号：201503105

国家自然科学基金面上项目（21276111）；国家自然科学基金青年基金（21206053）；浙江省自然科学基金重大专项（2011C12033）

邴晓瑛（1989—），女，山东青岛人，硕士。研究方向：无线传感器定位算法。