一种基于坐标改正的改进DV-Hop定位算法*

王 兴,聂云峰,徐飞飞

(南昌航空大学信息工程学院,南昌 330063)

项目来源:国家自然科学基金项目(41101426)

2017-04-18修改日期2017-06-09

一种基于坐标改正的改进DV-Hop定位算法*

王 兴,聂云峰*,徐飞飞

(南昌航空大学信息工程学院,南昌 330063)

为有效提高DV-Hop算法在拓扑随机网络中的定位精度,提出一种利用锚节点定位误差修正未知节点坐标的新方法(PEDV-Hop)。首先定义伪距误差因子剔除对平均跳距计算产生较大误差的锚节点,从而有效抑制网络拓扑随机分布影响,提高平均跳距计算精度;其次,视锚节点为未知节点,在计算平均跳距的同时,运用三边或多边测量法评估自身定位坐标,从而可计算得到锚节点坐标改正值,并将平均跳距与坐标改正值向网络广播;最后,未知节点根据接收到各锚节点的坐标改正值来修正自身定位误差,从而有效提高节点定位精度。仿真结果表明,PEDV-Hop算法实现简单,有效提高了节点的定位精度。

DV-Hop算法;节点定位;平均跳距;伪距误差因子

无线传感网络WSN(Wireless Sensor Networks)是由部署在监测区域内的大量微型并装备低能耗收发器和有限数据处理能力的感知节点通过无线通信形成的多跳自组织网络[1]。节点定位是WSN的关键技术之一[2],定位算法按测距与否可分为:基于测距(Range-based)和免测距(Range-free)两种[3]。其中,基于测距的定位方法对硬件有较高要求,一般需借助特定硬件测量出相邻节点间的角度或距离,计算和通信开销大;而免测距定位算法,只需依靠网络连通性或网络拓扑关系就可以实现定位[4-5],具有成本低、定位过程简单且能提供较理想定位精度等优势,因此更适合大规模无线传感网络节点定位的实际应用需求[6]。

DV-Hop定位算法作为一种经典的免测距定位方法,以其过程简洁,效果较好得到广泛的应用,目前国内外研究者针对该算法的优化提出大量具有参考价值的改进算法,大致可分为以下3类:

①锚节点选取优化类算法。文献[7]基于引入RSSI测距技术提出限制机制以减少节点的通信量和能耗,并通过优化参与定位的锚节点组合和质心算法有效降低定位误差;文献[8]通过Min-Max算法对未知节点进行初始位置的估计,然后通过未知节点和锚节点间的位置关系将未知节点升级为锚节点来增加锚节点的密度,从而提高网络中其他节点的定位精度;文献[9]通过设置未知节点接收锚节点信息数量的阈值,选择距离较近的部分锚节点作为参考节点,减少定位误差和计算量,提高效率和定位精度。

②平均跳距修正类算法,如:文献[10]采用Cayley-Menger行列式给出的距离几何约束条件对未知节点和锚节点间的估计距离进行处理,提高定位精度;文献[11]采用最小二乘法和加权处理法修正锚节点间的平均跳距,并通过迭代求解法提高未知节点的定位准确性和精度的稳定性;文献[12]通过最小均方差准则改进平均跳距的公式,并在最佳指数值下,修正锚节点的平均跳距,以此来提高节点定位的精度。

③跳数修正类算法,如:文献[13]通过提出非整数的锚节点间跳数,使用跳数偏离因子对未知节点与锚节点间跳数进行修正,使得节点间距离估计更加准确;文献[14]通过RSSI值对1跳邻居节点进行分级,细化跳数,然后将节点间的距离比值作为跳数修正的权值,从而抑制跳数值计算误差带来的定位偏差较大的问题;文献[15]根据跳数信息对锚节点进行了分类,设定不同跳数阈值,只选择大于或等于跳数阈值的节点参与距离估算,以实现定位精度的提升。

在DV-Hop族系算法中,锚节点平均跳距的估算对定位精度有至关重要影响,对于节点分布均匀、各项同性的密集型网络,通常可得到较合理的平均跳距,从而达到适当的定位精度,但对于网络拓扑不规则、随机分布的传感网络来说,锚节点到未知节点间往往不是直线路径,用跳段距离代替直线距离误差较大,因此定位精度较低[16-17]。为解决上述问题,提出一种利用锚节点定位误差修正未知节点坐标的新方法——PEDV-Hop(Pseudo-Range Error DV-Hop)。该算法首先定义伪距误差因子剔除对平均跳距计算产生较大误差的锚节点,从而有效抑制网络拓扑随机分布影响,提高平均跳距计算精度;其次,视锚节点为未知节点,在计算平均跳距的同时,运用三边或多边测量法评估自身定位坐标,从而可计算得到锚节点坐标改正值,并将平均跳距与坐标改正值向网络广播;最后,未知节点根据接收到各锚节点的坐标改正值来修正自身定位误差,从而有效提高节点定位精度。

1 DV-Hop算法

DV-Hop是Dragos Niculescu等人根据距离矢量路由原理提出的定位算法[18-20],主要包括3个阶段:第1阶段,使用典型的距离矢量交换协议,通过节点间的信息交换,使网络中所有节点获得与锚节点之间的跳数及锚节点位置信息;第2阶段,锚节点计算平均跳距,然后将其作为一个跳距校正值广播至网络中,其中校正值采用可控洪泛法在网络中传播,这意味着一个节点仅接受获得的第1个校正值,而丢弃所有后来者,这个策略确保了绝大多数节点可从最近的锚节点接收校正值。当未知节点接收到该校正值之后,用该校正值乘以到附近各锚节点之间的跳数,从而得出估计的欧氏距离;第3阶段,当未知节点获得与3个或更多锚节点间的欧氏距离时执行三边或多边测量定位法对未知节点进行定位。

传统DV-Hop算法使用平均跳距与跳数相乘来计算实际距离,用节点间的直线距离来估算节点间信息通路的曲线距离。在计算最小跳距时,无论相近节点间物理距离的远近,跳数值均加一,并不能反映出实际距离的差别,并且对于节点随机分布的传感网络而言,锚节点到定位节点往往不是直线路径,故采用经典DV-Hop算法可能会带来较大的距离计算误差。

2 PEDV-Hop算法

针对传统DV-Hop定位算法在节点随机分布、拓扑不规则传感网络中的定位精度较差的问题,提出PEDV-Hop算法通过定义伪距误差因子对第2阶段平均跳距进行修正,并利用锚节点坐标改正值对第3阶段未知节点坐标进行修正,从而有效提高节点定位精度。

2.1 平均跳距修正

设随机分布的网络中锚节点的个数为N。通过典型的距离矢量交换协议,使网络中所有节点获得与锚节点之间的跳数及锚节点位置信息,锚节点Ni利用式(1)估算平均跳距:

(1)

定义Ni与Nj之间的伪距为:

(2)

定义Ni与Nj之间的伪距误差因子为:

(3)

在随机分布的网络中,Ni与Nj之间的伪距与真实距离的误差可能很大,将Ni与Nj之间的伪距误差因子按升序排列。取前K(K≥3)个节点参与Ni平均跳距的计算,目的是剔除对测距误差影响较大的锚节点,从而有效抑制拓扑随机分布的影响,则Ni的平均跳距修正为:

(4)

2.2 锚节点坐标改正值计算

(5)

2.3 未知节点坐标改正

未知节点记录接收到的锚节点的平均跳距及坐标改正值,根据记录的跳数,计算到每个锚节点的跳段距离,采用三边测量或最小二乘法计算自身的估计坐标。

(6)

式中:N为锚节点总数。

2.4PEDV-Hop算法流程

Step 1 网络初始化;

Step 2 使用典型的距离矢量交换协议,锚节点Ni在网络中广播包含自身位置信息的数据包{IDi,(xi,yi),hop},通过节点间的信息交换,使网络中所有节点获得与锚节点之间的跳数;

Step 5 算法结束。

3 仿真分析

仿真场景为100 m×100 m的感知区域,节点总数为150,锚节点总数为N,K取值见3.2节,未知节点和锚节点随机产生。定义平均定位误差ave_error作为算法性能的评价标准,ave_error计算方法如式(7)所示:

(7)

式中:(xi,yi)、(Xi,Yi)分别为节点i的估计坐标和真实坐标,R为通信半径,n为未知节点数。

3.1 结果分析

图1给出了DV-Hop算法、文献[17]算法、DDV-Hop算法、PEDV-Hop_1算法和PEDV-Hop算法在不同锚节点比例及通信半径下定位误差的比较结果。

图1 锚节点比例、节点通信半径变化下各算法定位误差比较

图1表明:①在相同的通信半径下,上述算法的定位误差随着锚节点比例增加而减小,并逐渐趋于平稳。当锚节点比例小于20%时,随着锚节点比例增加,PEDV-Hop算法定位精度提高明显、变化幅度较大,比DV-Hop算法降低19%～25%,比PEDV-Hop_1算法降低8%～14%,比文献[17]定位算法降低4%～10%,比DDV-Hop算法降低2%～12%;当锚节点比例大于20%时,PEDV-Hop算法定位精度提升较慢,趋于平稳,比DV-Hop算法降低17%～26%,比PEDV-Hop_1算法降低7%～13%,比文献[17]定位算法降低5%～15%,比DDV-Hop算法降低1%～6%。

②在相同的锚节点比例下,随着通信半径增大,PEDV-Hop算法、PEDV-Hop_1算法、DV-Hop算法定位精度变化平稳,DDV-Hop算法及文献[17]算法的误差曲线变化波动较大;而且随着通信半径增大,PEDV-Hop算法定位精度总体呈下降趋势,但比DV-Hop算法定位误差减小幅度变大。这是因为随着通信半径的增大,网络连通性变强,网络拓扑结构更加复杂,导致平均跳距的估计误差变大[21],而PEDV-Hop算法通过定义伪距误差因子修正平均跳距,有效的抑制网络拓扑随机分布影响,提高了平均跳距计算精度,从而提高了节点定位精度。

③在相同的通信半径及通信半径下,PEDV-Hop_1算法定位精度比DV-Hop算法平均高11%,说明PEDV-Hop算法第1步修正的有效性;但比PEDV-Hop算法定位精度平均低13%,说明PEDV-Hop算法第2步修正的有效性。

3.2 K取值分析

在PEDV-Hop算法中,K的取值决定参与平均跳距计算锚节点数量,对平均跳距估算有一定的影响。本节通过实验观察K取值对PEDV-Hop定位精度的影响。实验结果如图2所示。

图2 K取值对定位误差的影响

图2表明,K值的变化直接影响算法定位精度。总体上,当3≤K≤⎣N/3」时定位精度呈波动上升趋势;当⎣N/3」≤K≤⎣N/3」时定位精度最优;当⎣N/2」≤K≤N时定位精度呈波动下降趋势。因此,当⎣N/3」≤K≤⎣N/2」时,PEDV-Hop算法定位精度最优。

4 结语

本文介绍了DV-Hop算法的原理及实现过程,分析了DV-Hop在节点随机分布、网络拓扑不规则网络中定位精度较低的问题,提出PEDV-Hop改进算法,通过定义伪距误差因子修正平均跳距,并利用锚节点坐标改正值修正未知节点坐标,从而有效提高节点定位精度。仿真实验对比了在不同通信半径及锚节点比例下PEDV-Hop算法同传统DV-Hop算法以及部分改进算法的定位精度差异,并对K取值进行探究。结果表明:PEDV-Hop算法稳定有效的提高了节点的定位精度;随着通信半径的增大,PEDV-Hop算法对传统DV-Hop算法的改进效果更加明显;总体上,当⎣N/3」≤K≤⎣N/2」时,PEDV-Hop算法精度最高。

[1] 孙立明,李建中,陈瑜,等. 无线传感器网络[M]. 北京:清华大学出版社,2005:149-151.

[2] Han G,Chao J,Zhang C,et al. The Impacts of Mobility Models on DV-Hop Based Localization in Mobile Wireless Sensor Networks[J]. Journal of Network and Computer Applications(S1084-8045),2014,42(4):70-79.

[3] Zhao J,Zhao Q,Li Z,et al. An improved Weighted Centroid Localization Algorithm Based on Difference of Estimated Distances for Wireless Sensor Networks[J]. Telecommunication Systems(S1018-4864),2013,53(1):25-31.

[4] Shang Y,Run I W,Zhang Y. Localization from Mere Connectivity[C]//Proc of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing Anna-Polis,USA:ACM,2003:201-211.

[5] Niculescu D,Nath B. Ad Hoc Positioning System(APS)Using AOA[C]//Proc of the 22nd Annual Joint Conf of the IEEE Computer and Communications Societies(INFOCOM’2003),2003(3):1734-1743.

[6] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2000,7(5):28-34.

[7] 夏少波,邹建梅,朱晓丽,等. 基于跳数区域划分的DV-Hop改进算法[J]. 传感技术学报,2014,27(7):964-969.

[8] 王翥,郝晓强,王玲. 基于锚节点选择的无线传感网络器定位算法[J]. 计算机研究与发展,2010,47(S):31-34.

[9] 申铉京,李成岳,王硕. 基于最优锚节点的无线传感器网络节点定位算法[J]. 吉林大学学报(工学版),2011,41,增刊:208-214.

[10] 郑君刚,吴成东,秦好,等. 基于DV-Hop和距离几何约束的定位算法[J]. 东北大学学报(自然科学版),2011,32(4):457-459.

[11] 林金朝,陈晓冰,刘海波. 基于平均跳距修正的无线传感器节点迭代定位算法[J]. 通信学报,2009(10):107-113.

[12] 马淑丽,赵建平. 多通信半径的无线传感网络DV-Hop定位算法[J]. 传感技术学报,2016,29(4):593-600.

[13] 肖丽萍,刘晓红. 一种基于跳数修正的DV-Hop定位算法[J]. 传感技术学报,2012,25(12):1726-1730.

[14] 温江涛,范学敏,吴希军. 基于RSSI跳数修正的DV-Hop改进算法[J]. 传感技术学报,2014,27(2):502-507.

[15] 祝宇鸿,历彦恺,王鲁娜,等. 基于跳数阈值和节点分类的DV-Hop改进算法[J]. 吉林大学学报(信息科学版),2014,32(4):407-412.

[16] Hou S F,Zhou X J,Liu X X. A Novel DV-Hop Localization Algorithm for Asymmetry Distributed Wireless Sensor Networks[C]//3rd IEEE International Conference on Computer Science and Information Technology(ICCSIT),2010,4:243-248.

[17] Chen H Y,Karo S,Deng P,et al. A Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]//IEEE ICIEA,2008:1557-1561.

[18] Niculescu D. Positioning in Ad Hoe Sensor Networks[C]//IEEE Network,2004,18(4):24-29.

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

[20] Kumar S,Lobiyal K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71:1365-1385.

[21] 嵇玮玮,刘中. DV-Hop定位算法在随机分布传感器网络中的应用研究[J]. 电子与信息学报,2008,30(4):970-974.

AnImprovedDV-HopLocalizationAlgorithmBasedonCoordinateCorrection*

WANGXing,NIEYunfeng*,XUFeifei

(School of Information Engineering,Nanchang Hangkong University,Nanchang 330063,China)

In order to improve the localization accuracy of DV-Hop algorithm in the random topology network scenario,a novel algorithm named PEDV-Hop is put forward. PEDV-Hop uses the localization error of anchor nodes to correct the coordinates of unknown nodes. Firstly,the pseudo-range error factor is defined to remove anchor nodes which may cause a larger calculation error of the average hop distance,through this way to improve the calculation accuracy of average hop distance,and to decrease the influence of topology random distribution. Secondly,the anchor node broadcasts the updated average hop distance together with its coordinate correction values calculated by trilateral or multilateral measurement with the premise of being treated as the unknown node. Lastly,the coordinates of each unknown node are corrected through the weighted average value of the coordinate correction values of the

anchor nodes. The simulation results show that PEDV-Hop algorithm has better localization accuracy and stability than the tradiDV-Hop algorithm and some existing improved algorithms,and it is easy to implement.

DV-Hop algorithm;node localization;average hop distance;pseudo-range error factor

TP393

A

1004-1699(2017)10-1560-05

10.3969/j.issn.1004-1699.2017.10.018

王兴(1992-),男,硕士研究生,主要研究方向为无线传感网络,地理信息系统,Jwangxing0719@163.com;

聂云峰(1980-),男,博士,副教授,主要研究方向为无线传感网络,遥感与地理信息系统,nieyunf@gmail.com;

徐飞飞(1992-),男,硕士研究生,主要研究方向为无线传感器网络,1032074982@qq.com。