景路路,张玲华(.南京邮电大学物联网学院,南京 20003;2.南京邮电大学江苏省通信与网络技术工程研究中心,南京 20003)



基于跳距优化的改进型DV-Hop定位算法*

景路路1,张玲华2*
(1.南京邮电大学物联网学院,南京 210003;2.南京邮电大学江苏省通信与网络技术工程研究中心,南京 210003)

DV-Hop定位算法是无线传感器网络节点定位的关键技术之一。传统DV-Hop定位算法节点定位,因跳数计算和跳距估计产生偏差,影响定位误差,为了提高定位精度,提出一种改进型定位算法。改进算法引入多通信半径方法细化节点间的跳数,计算未知节点平均跳距时,剔除孤立节点,并对利用锚节点得到的平均跳距进行加权归一化处理,使得未知节点定位精度提高。仿真结果显示,改进算法在不明显提高算法复杂度与通信量的基础上大大提高了定位精度。

无线传感器网络;DV-Hop定位算法;改进算法;通信半径;加权平均

节点定位是无线传感器网络非常关键的一项技术。根据现有定位机制,将定位算法分为基于距离的(Range-based)定位算法和距离无关的(Range-free)定位算法两种。基于距离的(Range-based)定位的算法有RSSI、TOA、TDOA、AOA等,适用于定位精度要求较高的应用场景中,这类算法对传感器节点的硬件要求较高。距离无关的(Range-free)定位算法适用于定位精度要求不高的场景,或者出于硬件成本、实现复杂度等方面的考虑,可以采用距离无关(Range-free)的定位技术,常用有质心定位算法[1]、APIT[2]定位算法、DV-Hop[3-16]等。目前实际应用的定位系统绝大多数采用距离无关的(Range-free)定位算法。

DV-Hop算法采取距离矢量-跳数机制,由于其无需节点间距的测量及不需附加硬件支持,成为一种备受关注的距离无关的(Range-free)算法。目前许多学者提出了不同的方法对DV-Hop算法进行改进以提升定位精度:文献[9-16]对跳数进行修正,再根据估计距离的误差修正平均跳距;文献[10]利用平均跳距误差修正待定位节点的平均跳距;文献[11]提出了一种基于跳距加权平均的的DV-Hop算法,对未知节点与各个锚节点的平均跳距进行归一化加权处理,离未知节点较近的锚节点分配大的权值;文献[12]计算每个锚节点平均跳距误差,进而修正之前得到的平均跳距。文献[11-12]与传统DV-Hop算法相比较,定位精度有一定提高,缺点是计算成本和通信开销比较大。文献[13]在跳距修正、未知节点与锚节点之间距离的计算以及节点定位方法3个方面进行了改进,缺点是计算量较大。本文提出了一种基于跳距优化的改进型DV-Hop算法。在尽可能减小计算量的情况下,采用多通信半径进行通信,并对利用锚节点计算得到的平均跳距进行加权归一化处理,使得未知节点与锚节点之间的平均跳距更接近于真实值。仿真结果表明,相比原始DV-Hop算法,本文算法在定位精度上有显著提高。

1 DV-Hop算法与误差分析

1.1 传统DV-Hop算法

DV-Hop算法是Rutgers大学的Dragons等人基于矢量路由及全球定位系统GPS提出的一种距离无关的(Range-free)定位算法[3]。主要包括3个阶段,大体步骤如下:

①计算未知节点与锚节点的最小跳数。锚节点广播包含自身位置信息和跳数字段的分组,跳数初始化为0.其他节点记录其收到的每个锚节点的最小跳数,忽略来自同一锚节点较大跳数的分组,并将跳数字段加1转发给相邻节点。通过这种方式,网络中所有节点均能获得到每个锚节点的最小跳数。

②估算未知节点和锚节点间的距离。每个锚节点根据第1阶段中获得的其他锚节点的位置信息和最小跳数,利用式(1)估算锚节点平均每跳距离:

(1)

式中:(xi,yi)为锚节点i的位置坐标;hij为锚节点i和j之间的最小跳数。然后锚节点将计算的平均每跳距离广播至网络中,未知节点收到每跳距离并根据其到各个锚节点的最小跳数来估算其到各锚节点的距离。用hi表示某未知节点到第i个锚节点的最小跳数:

di=hi×HopSizeij(i≠j)

(2)

就可以计算出未知节点距第i个锚节点的距离,这里用di表示,见式(2)。

③利用基于距离的(Range-based)定位算法计算节点位置。未知节点利用步骤(2)中计算得到的到各锚节点的距离,采用基于距离的(Range-based)定位算法(极大似然估计)估计节点自身位置。

为了便于理解,我们假设网络拓扑结构如图1所示。

图1 传统DV-Hop算法示例

图1中B1、B2、B3是3个锚节点,P是未知节点。经过步骤(1)B1得到带有B2、B3位置信息和跳数信息的分组,如图所示,B1、B2之间跳数为2,B2、B3之间的跳数为5,我们可以计算出该网络中锚节点平均每跳的跳距:

hopsize=(42+77)/(2+5)=17

(3)

即可获得未知节点P到B1、B2、B33个锚节点的距离:

(4)

1.2DV-Hop算法误差分析

在DV-Hop算法中,用最小跳数来衡量节点间的距离。当跳数越小,即可认为距离就越近。假设两个节点,只要可以进行直接通信,那么跳数值就记为1。能和同一节点直接通信的所有节点,距离不会完全一样,比如图1中B1、B2之间,一个未知节点间隔成两段,跳数都计为1,但距离并不一样。由此可见,经常会有节点间实际距离相差很大但是最小跳数一样的情况。这样的跳数误差也会导致一定的定位误差。所以,在计算跳数时可以采用多个通信半径的方法,细化节点间跳数。

在通信过程中,通信半径规定了某些节点属于上级节点的相邻节点,从而对节点间的跳数起了决定性作用,也同样的决定了每一跳的距离。所以,在计算未知节点平均每跳的距离时,对利用锚节点所得到的平均跳距进行加权归一化处理,能得到更精确的平均跳距值,进一步减小定位误差。

在本文中,我们采用相对定位误差来研究不同DV-Hop算法的定位误差问题:

(5)

式中:N是未知节点的数量,(xm,ym)、(xr,yr)为待定为节点的估计坐标和真实坐标,R是通信半径。

2 改进型的iDV-Hop算法

2.1 基本思路

通过对传统DV-Hop算法分析可知,通信半径的选取至关重要,在考虑到计算成本的同时,本文选取4个通信半径,即R(未知节点和锚节点都使用的通信半径R)、0.75R、0.5R、0.25R,这3个为锚节点专用通信半径。锚节点不同的通信范围,划分了4组节点,如图2,分为A、B、C、D。A组指的是锚节点在通信半径0.25R内广播信息时,能接收到信息的所有相邻节点;B组指的是在通信半径0.5R内广播信息时,能接收到信息的所有相邻节点。C组指的是在通信半径0.75R内广播信息时,能接收到信息的所有相邻节点。D组指的是在通信半径R内广播信息时,能接收到信息的所有相邻节点。如图2所示:4组节点之间具有包含关系。

图2 4通信半径示意图

锚节点广播跳段信息时,A组节点到锚节点的最小跳数计为0.25,B组节点到锚节点的最小跳数计为0.5,C组节点记录的到锚节点的最小跳数计为0.75,D组节点到锚节点的最小跳数计为1。然后,相邻节点以通信半径R广播锚节点发来的分组信息。当消息传输结束后,每个节点都获得了到锚节点的最小跳数。最短通信路径如果经过A组和B组节点,最后记录的最小跳数就有可能不是一个整数。使用这种办法,锚节点利用0.75R、0.5R和0.25R的通信半径通信时,最小跳数更加精确,跳距的计算也更为准确,定位精度提高。

与图1对比,图3采用同样网络拓扑结构,B1与A节点之间的跳数为0.25,B2与P之间为两个0.25,P与B3之间有两个0.75、一个1,则有下式:

(6)

式(6)比式(3)更接近于真实值。P与B1、B2、B3之间的距离也更接近于真实值。

图3 4通信半径算法示例

传统DV-Hop算法中,未知节点估计自身位置,接收的是距离最近的锚节点估计的平均跳距值,用该值作为未知节点自身的平均跳距来估计自身位置。网络中某个锚节点的平均跳距值并不能反映网络中全部节点的属性。改进算法在计算未知节点的平均跳距时进行加权处理,综合考虑可以与未知节点通信的全部锚节点,各个锚节点计算出的平均跳距值与到未知节点跳数值的乘积作为未知节点平均跳距的加权参数值,并对所有权值进行归一化处理。加权参数如下:

(7)

式中:n为未知节点可以通信的锚节点个数,disu表示未知节点到第u个锚节点之间跳数与锚节点平均跳距的乘积,通过式(7)归一化处理,未知节点获得n个锚节点平均跳距加权值,这n个加权值之和为1。在锚节点广播跳数和平均跳距信息时,未知节点记录两者乘积并对数值较大的赋予较小的权值αu,求未知节点的平均跳距,加入该加权参数进行校正。

以上改进算法称为iDV-Hop算法。

2.2 改进算法的基本步骤

①获取网络中未知节点与锚节点的最小跳数

与传统DV-Hop算法相同,通过泛洪的方式在网络中广播自身的位置信息。网络初始化,锚节点先在网络中进行第1次广播分组信息,此时的通信半径设为0.25R。相邻节点接收到锚节点发送的分组信息,到该锚节点的最小跳数记为0.25。此时的相邻节点并不进行信息的转发,这样可以减小通信方面的开销。

经过第1个时间t后,锚节点进行第2次广播分组信息,通信半径为0.5R。如果节点是第1次收到某个锚节点的分组信息,就把距该锚节点的最小跳数记为0.5。若不是第1次,证明该节点记录的最小跳数为0.25。保留较小的跳数值,即0.25。此时的相邻节点不进行信息的转发,同样可以减小通信开销。

经过第2个时间t后,锚节点进行第3次的广播分组信息,通信半径为0.75R。最小跳数获取同上。

经过第3个时间t后,锚节点进行第4次的广播分组信息,通信半径为R。最小跳数获取后,节点把目前记录的跳数值相应地加1后转发出去。这样,每个节点就都能获得距锚节点的最小跳数,这里也用hi表示。

图4 不同通信半径误差分析图

②计算平均每跳距离,估算未知节点与锚节点之间的距离

每个锚节点根据步骤①可获得到其他锚节点的位置信息和最小跳数,利用式(1)估算锚节点的平均每跳距离。锚节点广播带有跳数和平均跳距的分组,未知节点记录跳数和锚节点平均跳距的乘积值di,并对di值较大的赋予较小的权值αu,加权参数为式(7),再利用式(8)计算未知节点的平均跳距值:

(8)

校正之后,式(2)求未知节点到第i个锚节点距离计算方法则变成式(9):

avgdi=hi×UnHopSizei

(9)

利用式(9)可得未知节点与锚节点之间的距离。

③利用基于距离的(Range-based)定位算法计算节点位置。未知节点利用步骤②得到未知节点到锚节点的距离,采用基于距离的定位算法(极大似然估计)估计节点自身位置。

3 仿真结果分析

假设仿真环境为边长100 m的正方形二维区域,100个节点随机分布。通信半径分别取:20 m、28 m、36 m、44 m、分别对传统DV-Hop算法和改进iDV-Hop算法进行了对比。相同比例的锚节点情况下,实验进行100次,取平均值。图4(a)～图4(d)为不同半径时,随锚节点比例变化的误差分析图。

由图4(a)～图4(d)可以看出,不同半径下,相对定位误差随着锚节点个数的增加而呈现减小的趋势,100个节点中,锚节点个数大于20时,相对定位误差会趋于稳定。当锚节点个数小于20时,通信半径在30 m左右或者大于30 m时,相对定位误差基本处于0.20以下,即控制在20%以内。当锚节点个数一定,通信半径变大时,相应网络的连通度会变大,相对定位误差趋于变小。

图4(a)～图4(d)是通信半径为20 m～44 m时的改进算法和传统算法的对比,iDV-Hop算法(改进的4通信半径算法)比改进的2通信半径算法相对定位误差降低了7%～9%,iDV-Hop算法(改进的4通信半径算法)比改进的3通信半径算法相对定位误差降低了2%～3%,iDV-Hop算法(改进的4通信半径算法)比传统DV-Hop算法相对定位误差降低了16%～25%。

4 结束语

本文首先对传统DV-Hop算法进行了分析,明确了误差的部分来源,在此基础上采用了多半径通信和加权参数的方法进行改进,在利用锚节点求平均跳距时剔除了孤立节点,综合考虑所有可进行通信的锚节点的平均跳距值,并进行了加权归一化处理。可以看出,采用了改进算法之后,相对定位误差降低16%～25%。此外,网络拓扑结构的变化也会带来定位误差的变化,本文是在相同的仿真条件下进行了100次实验取得的平均值,尽可能减小这种拓扑结构的影响。锚节点的覆盖率也会影响实验结果,未来会进一步改进。

[1] 陈维克,李文峰,首珩,等. 基于RSSI的无线传感器网络加权质心定位算法[J]. 武汉理工大学学报,2006,30(12):265-268.

[2] 周勇,夏士雄,丁世飞,等. 基于三角形重心扫描的改进APIT无线传感器网络自定位算法[J]. 计算机研究与发展,2009,46(4):566-574.

[3] Hadir A,Zine-Dine K,Bakhouya M,et al. An Optimized DV-Hop Localization Algorithm Using Average Hop Weighted Mean in WSNs[C]//Codes,Cryptography and Communication Systems(WCCCS),2014 5th Workshop on,IEEE,Nov,2014:25-29.

[4] 江禹生,冯砚毫. 一种新的DV-Hop定位算法[J]. 传感器技术学报,2003,23(12):1815-1819.

[5] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems,2003,22(1/4):267-280.

[6] Wang Yun,Wang Xiao,Wang Demin,et al. Range-Free Localization Using Expected Hop Progress in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[7] 孙利民,李建中,陈渝,等. 无线传感器网络[M]. 北京:清华大学出版社,2005:135-155.

[8] Peng Y,Wang D. A Review:Wireless Sensor Networks Location[J]. Journal of Electronic Measurement and Instrument,2011,25(5):389-399.

[9] 夏少波,邹建梅,朱晓丽,等. 无线传感器网络DV-Hop定位算法的改进[J]. 计算机应用,2015,35(2):340-344.

[10] Ju H,Yang X,Qi Y,et al. Dynamic Updating Multigranulation Fuzzy Rough Set:Approximations and Reducts[J]. International Journal of Machine Learning and Cybernetics,2014,5:981-990.

[11] 刘峰,张翰,杨骥. 一种基于加权处理的无线传感器网络平均每跳跳距估计算法[J]. 电子与信息学报,2008,30(5):1222-1225.

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

[13] Ji W,Liu Z. Study on the Application of DV-Hop Location Algorithms to Random Sensor Networks[J]. Journal of Electronics and Information Technology. 2008,30(4):970-974.

[14] 魏全瑞,刘俊,韩九强. 改进的无线传感器网络无偏距离估计与节点定位算法[J]. 西安交通大学学报,2014,48(6):1-6.

[15] 李娟,刘禹,钱志鸿. 于双通信半径的传感器网络DV-Hop定位算法[J]. 吉林大学学报(工学版),2014,44(22):502-507.

[16] 夏少波,朱晓丽,邹建梅,等. 基于跳数修正的DV-Hop改进算法[J]. 传感器技术学报,2015,28(5):757-762.

景路路(1989-),南京邮电大学,硕士研究生,主要研究方向为无线传感器网络定位,279233614@qq.com;

张玲华(1964-),南京邮电大学,教授、博士生导师,主要研究领域为数字信号处理、智能信号处理、语音信号处理及现代通信技术、无线传感器网络等,zhanglh@njupt.edu.cn。

An Improved DV-Hop Algorithm Based on Optimization of One-Hop Distance for Sensor Network Localization*

JING Lulu1,ZHANG Linghua2*
(1.College of Internet of things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.Jiangsu Engineering Research Center of Communication and Network Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

DV-Hop localization algorithm is one of the key technologies of wireless sensor network node localization. The traditional DV-Hop localization algorithm due to the deviation of calculation the number of hops and estimate of one-hop distance,resulting in greater localization errors. In order to reduce the location error,an improved positioning algorithm is proposed. The improved algorithm broadcasts the data using multi communication radius and refines the hops to reduce the location error. When calculating the average hop distance of unknown nodes,,remove the isolated nodes,introduce weighted normalization processing,to obtain a more precise one-hop distance. The simulation result indicates that the improved algorithm can greatly improve the location accuracy without obviously increasing algorithm complexity and communication traffic.

wireless sensor network;DV-Hop location algorithm;improved algorithm;communication radius;weighted average

项目来源:江苏省教育自然科学研究重大项目(13KJA510003);江苏高校优势学科建设工程项目(PAPD)

2016-10-11 修改日期:2016-12-01

TP393

A

1004-1699(2017)04-0582-05

C:7230

10.3969/j.issn.1004-1699.2017.04.017