WSN中基于最佳指数的加权DV-Hop算法*

2015-03-25马淑丽赵建平

通信技术 2015年10期

关键词：指数值定位精度半径

马淑丽，赵建平

(曲阜师范大学物理工程学院,山东曲阜 273165 )

WSN中基于最佳指数的加权DV-Hop算法*

马淑丽，赵建平

(曲阜师范大学物理工程学院,山东曲阜 273165 )

DV-Hop算法是一种低成本、低定位精度的无需测距定位算法，在粗精度定位中应用广泛。为提高DV-Hop算法定位精度，从减小锚节点的平均每一跳距离误差和减小未知节点平均每一跳校正值误差两方面考虑。首先，用最佳指数值下的公式计算锚节点平均每一跳距离。然后，将未知节点的校正值加权处理，使所有的锚节点根据与未知节点距离的远近影响校正值的大小。MATLAB实验证明，改进的基于最佳指数值下的加权DV-Hop算法比DV-Hop算法、加权DV-Hop、最佳指数值下DV-Hop算法定位精度分别提高2%左右、1.65%左右、1.15%左右，同时不会增加网络硬件成本。

无线传感器网络;节点定位;加权DV-Hop算法;最小均方差

0 引言

近几年来，国内无线传感器网络(Wireless Sensor Network，WSN)的应用越来越广泛[1]，其关键技术的研究也越来越受到重视。WSN关键技术包括节点定位技术、路由协议技术、时间同步、信息融合等[2]，而这些关键技术成为限制WSN发展的瓶颈。WSN中有大量微型低成本的传感器节点，在一些环境恶劣或无人值守的应用中，节点一般由飞机散落或导弹散射，节点负责采集并将信息发送出去[3]。然而，如果不知道节点的位置，那么采集的信息毫无意义[4]。

由于成本原因，节点中只有少数装有GPS[5]，其它节点只能靠定位技术计算坐标。无需测距的定位算法由于成本低、简单等原因应用较广[6]，其中DV-Hop算法是众多学者一直在研究并改进突破的热点算法之一。本文结合其他文献改进DV-Hop算法。

1 DV-Hop算法概述

DV-Hop定位算法是由美国罗格斯大学(Rutgers University)Dragos Niculescu等人提出的6种分布式定位算法之一[7]。

DV-Hop定位算法只是利用节点间的传输跳数值信息和锚节点的坐标值进行未知节点的坐标计算。假设网络中：所有节点都可以进行双通信，通信过程无障碍，每个节点都有自己的通信范围即通信半径，自带GPS 导航设备的锚节点有n个。

DV-Hop算法步骤[8-10]：

第一步：锚节点向网络广播信息，包括自身位置信息、初始跳数值、节点编号等。路由方式为泛洪方式。设定一个较大的跳数值阈值，转播过程中如果跳数值超过阈值则转发停止。接收节点接到信息后，比较接收跳数值的大小，如果比自己保留的跳数值大则抛弃信息，如果较小则保留信息，并将跳数值加1转发出去。

第二步：锚节点根据第一步得知的其它锚节点位置信息等，计算自己的平均每一跳距离。

(1)

锚节点i到其他锚节点的平均每一跳距离是dHopi。锚节点i、j间的最小跳数是hij。

第三步：锚节点再次向网络广播信息，包括自己的平均每一跳距离信息、节点编号。未知节点就近原则只接收一个锚节点的信息，并将其作为自己计算平均每一跳距离时的校正值。假设未知节点l的校正值为dHopp(即锚节点p为向该未知节点第一个送达信息)，未知节点l与锚节点j间的跳数为hlj。未知节点估算自己与其它锚节点间的距离如下式。

dlj=dHopp×hlj

(2)

第四步：未知节点得到所有锚节点间的估算距离后，用三边测量法、极大似然法等计算自身坐标。假设未知节点坐标(x,y)，未知节点与锚节点i间的估算距离di。

极大似然估计法：

(3)

AX=b

(4)

(5)

(6)

(7)

算法的性能指标用定位精度判定，定位精度值越小定位精度越高，如式(8):

(8)

网络中节点个数为N，节点通信半径R，节点i真实坐标与估算坐标分别为(x0i,y0i)、(xi,yi)。

2 改进的DV-Hop定位算法

文献[11]提出根据信号的强弱对跳数值加权，修正值为0.5或1的DV-Hop改进算法。文献[12]提出对锚节点的平均每一跳距离进行加权，提出基于加权系数矩阵的DV-Hop改进算法。文献[13-14]等也基于加权的DV-Hop算法研究了一系列的改进算法。加权的DV-Hop算法比DV-Hop算法提高了定位精度。文献[15]提出改进锚节点平均每一跳距离的DV-Hop算法，在最小均方差准则下提出最佳指数值概念，也提高了DV-Hop算法定位精度。

由于节点在网络中随机部署，节点间的距离不一致，有的距离大有的距离小，而在DV-Hop算法中，计算节点间跳数值时，在通信半径R范围内的节点全记为1，这样距离较大和距离较小的节点间的跳数值可能会相同。最后会导致锚节点用式(1)计算自己平均每一跳距离时与实际平均每一跳距离间的误差很大。考虑减小锚节点平均每一跳距离误差，文献[15]利用最小均方差准则，提出的改进公式：

(9)

根据多次仿真实验，将改进的算法定位精度最高时的α值，作为最佳指数值。

在DV-Hop算法第三步中，未知节点只是利用离自己最近的锚节点，将其平均每一跳距离作为校正值，然后用式(2)求该未知节点与所有锚节点间的估算距离。这样会导致锚节点利用率低、估算距离误差大。文献[12,14]等考虑充分利用所有锚节点，根据锚节点与未知节点的远近(依据跳数值大小判定)，对每个锚节点的平均每一跳距离乘以一个加权系数。这个系数根据所有锚节点与未知节点节点间的跳数值确定。然后，将每个锚节点加权处理后的平均每一跳距离求和。最后，将该和代入式(2)求未知节点与每个锚节点间的估算距离。

本文将上述改进的方法结合，提出基于最佳指数值下的加权DV-Hop改进算法。并验证可以进一步提高定位精度。本文改进算法：

假如共有n个锚节点，求未知节点i到所有锚节点的估算距离时，锚节点j的加权系数Mji为：

(10)

锚节点j加权处理后的平均每一跳距离为：

MDji=Mji×dHopj

(11)

此处的dHopj由式(9)计算。未知节点i的校正值为：

(12)

未知节点i与锚节点f(f取1～n)的估算距离为：

dif=MJi×hif

(13)

3 实验仿真

将仿真环境建立在100 m×100 m的正方形区域，将100个节点随机部署在网络，锚节点覆盖率取9%～32%，通信半径取22～45 m。

3.1 不同通信半径下多种算法对比

锚节点覆盖率取9%，仿真不同通信半径下多种改进的DV-Hop定位算法和本文改进的DV-Hop算法。

首先，求加权DV-Hop算法下的最佳指数值。在不同的通信半径下，将α取不同的值，仿真改进的算法。由于节点分布的随机性，将程序循环100次取平均值。

如图1所示，在相同通信半径下，随着指数值增大，定位精度先提高后降低。在通信半径22、23、24、…、32 m，分别对应有最佳的指数，使定位精度最高。由图1可知，最佳指数值分别为1.99、1.99、1.99、1.98、1.97、…、1.97。

图1 不同通信半径下求最佳指数值

然后，将最佳指数值代入式(9)得锚节点平均每一跳距离，然后代入式(11)，开始进行最佳指数值下的加权DV-Hop定位。为了便于与文献[15]对比，也求出文献[15]改进算法下的最佳指数。将本文算法与文献[12]加权DV-Hop算法、文献[15]最佳指数值DV-Hop算法、DV-Hop算法对比仿真，如图2所示。

图2 不同通信半径下4种算法对比

在不同的通信半径下，本文改进的最佳指数加权DV-Hop算法都比其它算法明显的占优势。随着通信半径的增大4种算法定位精度都降低。通信半径34米时，本文改进的算法比DV-Hop算法、文献[12]加权DV-Hop算法、文献[15]最佳指数DV-Hop算法分别提高定位精度2.05%、1.65%、1.12%。

3.2 不同锚节点覆盖率下多种算法对比

通信半径取34 m，仿真不同锚节点覆盖率下多种改进的DV-Hop定位算法和本文改进的DV-Hop算法。

在不同的锚节点覆盖率下，将α取不同的值，求加权DV-Hop算法下的最佳指数值。将程序循环100次取平均值。如图2所示，在不同的锚节点覆盖率下，分别对应有最佳的指数，使定位精度最高。最佳指数值分别为1.95、1.94、1.94、1.93、1.94、1.93、1.93、…、1.92。

图2 不同锚节点覆盖率下求最佳指数值

将本文算法与文献[15]最佳指数值DV-Hop算法、DV-Hop算法对比仿真，如图3所示。

图3 不同锚节点覆盖率下3种算法对比

在不同的锚节点覆盖率下，本文改进的最佳指数加权DV-Hop算法比其它算法占优势。锚节点覆盖率28%时，本文算法定位精度达到最高，为0.241%。锚节点覆盖率14%时，本文改进的算法比DV-Hop算法、文献[15]最佳指数DV-Hop算法分别提高定位精度2.8%、1.2%。

3.3 不同锚节点覆盖率和不同通信半径对比

在不同的锚节点覆盖率和不同的通信半径下，对比本文算法和DV-Hop算法，如图4所示。本文算法定位精度总体比DV-Hop算法高2%左右。

图4

以上实验结果说明，可以将最佳指数值下求平均每一跳距离的式(9)应用到加权求未知节点校正值的式(12)里，这样改进的DV-Hop算法能提高定位精度，同时不会增加节点硬件成本和节点泛洪次数。

4 结语

本文结合文献[12]和文献[15]改进DV-Hop算法。用文献[15]提出的最佳指数值下的公式求锚节点平均每一跳距离，然后根据文献[12]提出的加权DV-Hop算法，将平均每一跳距离乘以加权系数，该系数使离未知节点较近的锚节点能较大的影响未知节点的定位。MATLAB仿真实验，找出不同条件下的最佳指数值，然后带入本文算法，发现本文改进的算法比文献[12]、文献[15]提出的改进算法更占优势。在相同定位条件下，本文算法能提高2%左右定位精度。下一步研究，改进基于多通信半径的DV-Hop算法。

[1] 陈瑜,张铁民,孙道宗等.基于无线传感器网络的设施农业车辆定位系统设计与试验[J].农业工程学报,2015, 31(10):190-197. CHEN Yu, ZHANG Tie-min, SUN Dao-zong, et al. Design and Experiment of Locating System for Facilities Agricultural Vehicle based on Wireless Sensor Network[J].Transactions of the Chinese Society of Agricultural Engineering(Transactions of the CSAE),2015,31(10):190-197.

[2] 许毅.无线传感器网络原理及方法[M].北京:清华大学出版社,2012:53. XU Yi.Principles and Methods of Wireless Sensor Networks[M].Beijing:Tsinghua University press, 2012:53.

[3] 李建奇,孔玲爽,王辅文等.基于无线传感器网络的葡萄栽培环境监测系统[J].排灌机械工程学报,2014,32 (07):637-644. LI Jian-qi, KONG Ling-shuang, WANG Fu-wen, et al. Wireless Sensor Network based Viticulture Environmental Monitoring System[J].Journal of Drainage and Irrigation Machinery Engineering (JDIME).2014,32(07):637-644.

[4] 周明伟.无线传感器网络的安全定位研究[D].无锡：江南大学,2014. ZHOU Ming-wei. Research on Security Location of Wireless Sensor Networks[D].WuXi：Jiangnan University,2014.

[5] 朱敏,刘昊霖,张志宏等.一种基于DV-Hop改进的无线传感器网络定位算法[J].四川大学学报:工程科学版,2012,44(01):93-98. ZHU Min, LIU Hao-Lin, ZHANC Zhi-hong, et al. An Improved Localization Algorithm based on DV-HOP in WSN[J].Journal of Sichuan University(Engineering Science Edition),2012,44(01):93-98.

[6] 高翔.无线传感器网络低功耗路由与节点目标跟踪定位研究[D].西安：西安电子科技大学,2011. GAO Xiang. Research on Energy-Efficient Routing Protocols and Target Tracking in Wireless Sensor Networks[D]. Xi'an：Xi'an Electronic and Science University,2011.

[7] 陈敏，王擘，李军华.无线传感器网络原理与实践[M].北京：化学工业出版社，2011. CHEN Min, WANG Bo, LI Jun-hua. Wireless Sensor Network Theory and Practice [M]. Beijing: Chemical Industry Press, 2011.

[8] Gayan S,Dias D.Improved Dv-Hop Algorithm Through Anchor Position Re-Estimation[C]. Wireless and Mobile, 2014 IEEE Asia Pacific Conference on. (Aug 2014)126-131.

[9] CHANG Xiao-hui, LUO Xiong. An Improved Self-Localization Algorithm for Ad hoc Network based on Extreme Learning Machine[C].Intelligent Control and Automation (WCICA),2014 11th World Congress on.IEEE,2014,564-569.

[10] HU Juan, JIANG Min-lan. An Improved Node Localization Algorithm in Wireless Sensor Network [C].Advanced Research and Technology in Industry Applications (WARTIA),2014 IEEE Workshop on, Sept2014,398-401.

[11] 倪海燕,应祥岳,简家文.无线传感器网络中基于DV-Hop的一种改进算法[J].工业控制计算机,2008,21 (12):43-45. NI Hai-yan, YING Xiang-yue, JIAN Jia-wen.An Improved Algorithm based on DV-Hop in Wireless Sensor Networks[J]. Industrial Control Computer, 2008, 21 (12):43-45.

[12] 冯江,朱强,吴春春.改进的DV-Hop定位算法研究[J].计算机工程,2012,38(19):74-81. FENG Jiang, ZHU Qiang, WU Chun-chun. Research on Improved DV-Hop Localization Algorithm[J]. Computer Engineering,2012,38(19):74-81.

[13] 魏全瑞,刘俊,韩九强.改进的无线传感器网络无偏距离估计与节点定位算法[J].西安交通大学学报,2014, 48(06):1-6. WEI Quan-rui, LIU Jun, HAN Jiu-qiang. An Improved DV-Hop Node Localization Algorithm based on Unbiased Estimation for Wireless Sensor Networks [J].Journal of Xi’an Jiaotong University,2014,48(06):1-6.

[14] 蒋馥珍.基DV-HOP的无线传感器网络定位算法研究[D].太原：太原理工大学,2011. JIANF Fu-zhen. Research on Location Algorithm Based on DV-Hop in WSN[D]. Taiyuan ：Taiyuan University of Technology,2011.

[15] 马淑丽,赵建平.无线传感器网络中DV-Hop定位算法的改进[J].通信技术,2015,48(07):840-844. MA Shu-li,ZHAO Jian-ping. The Improvement of DV-Hop Algorithm in Wireless Sensor Networks[J]. Communications Technology, 2015, 48(07):840-844.

Weighted DV-HopAlgorithm based on Optimal Index in WSN

MA Shu-li，ZHAO Jian-ping

(College of Physics Engineering, Qufu Normal University, Qufu Shandon 273165, China )

DV-Hop algorithm, as a range-free localization algorithm with low cost, low positioning accuracy, is widely used in coarse-precision positioning. In order to improve the location accuracy of DV-Hop algorithm, two aspects should be considered, i.e.,to decrease average hop distance error of anchor node and to reduce average hop correction value error of unknown node. Firstly, the average hop distance of anchor node is calculated by formula with the best index value. Then, the correction value of unknown node is weighted, so that all the anchor nodes could be corrected in accordance with the distance from unknown node. MATLAB results indicate that the location accuracy of the modified weighted DV-Hop algorithm based on optimal index is improved approximately 2%, 1.65% and 1.15% respectively as compared with that of DV-Hop algorithm, weighted DV-Hop and DV-Hop algorithm with optimal index value, and meanwhile with no increase of the network hardware cost.

wireless sensor network; node localization; weighted DV-Hop; least mean square error

10.3969/j.issn.1002-0802.2015.10.010

2015-05-17；

2015-09-03 Received date:2015-05-17；Revised date：2015-09-03

国家自然科学基金(No.11302118)；山东省自然科学基金(No.ZR2014FM011)；山东省高等学校科技计划项目(No.J12LN08)

Foundation Item:National Natural Science Foundation of China(No.11302118); National Natural Science Foundation of Shandong Province(No. ZR2014FM011);Supported by the Science and Technology Project of Higher Education of Shandong Province(No.J12LN08)

TP393

1002-0802(2015)10-1147-05