基于双通信半径的DV-Hop改进算法

赵建平，马淑丽

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



基于双通信半径的DV-Hop改进算法

赵建平，马淑丽

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

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

摘要：节点定位技术是无线传感器网络的关键技术之一。基于双通信半径的DV-Hop定位算法虽然比DV-Hop算法大大提高了定位精度，但是还可以进一步改进。在双通信半径定位算法基础上，用最佳指数值概念改进锚节点计算平均每一跳距离的公式。将平均每跳距离进行加权处理，未知节点选择校正值时，用所有锚节点与未知节点距离的远近影响未知节点的校正值。MATALB仿真实验证明，提出的基于双通信半径的最佳指数加权DV-Hop算法能提高基于双通信半径算法的定位精度。改进的算法不会增加节点的硬件成本。

关键词：无线传感器网络;节点定位;双通信半径DV-Hop;加权DV-Hop

0引言

无线传感器网络(Wireless Sensor Network,WSN)有大量微型、低成本的节点，一般在无人值守的应用环境，节点由飞机等随机抛撒[1]。在无线传感器网络定位技术中节点分两类：锚节点和未知节点。锚节点可以知道自己的位置信息，但是成本比未知节点高，在网络中一般占少数。未知节点靠锚节点计算自身位置信息，成本低，占网络中节点的大多数。网络中每个节点都需要知道自身位置，不然采集到的信息毫无意义。定位技术有多种，其中无需测距的定位算法因为成本低、定位过程简单而被广泛应用[2]。在粗精度定位应用中，DV-Hop算法是应用较为广泛的无需测距的定位算法之一[3-4]。

DV-Hop算法只是用节点间传输信息和跳数值计算坐标[5]，误差很大。影响节点定位精度大的原因很多，如通信半径、锚节点平均每一跳距离、未知节点校正值的选取、锚节点部署方式等。许多文献为了提高定位精度而改进算法。本文结合其他文献(如文献[6])提出的基于多通信半径的DV-Hop算法，在求锚节点平均每一跳距离、未知节点校正值的选取上进一步改进算法，并提出一种基于多通信半径最佳指数值加权的DV-Hop算法。

1多通信半径DV-Hop算法

2003年，美国罗格斯大学(Rutgers University)Dragos Niculescu等人提出6种分布式定位算法，DV-Hop定位算法是其中之一[7-8]。多通信半径DV-Hop算法是DV-Hop算法的一种改进算法。2014年，文献[6]提出基于双通信半径改进的DV-Hop算法。文献[9]在此基础上提出基于三通信半径的改进DV-Hop算法，并实验仿真验证了基于双、三通信半径的改进算法能大大提高DV-Hop算法定位精度。后来，文献[10]提出一种基于多通信半径的DV-Hop算法。

所谓的多通信半径即网络中锚节点可以通过延时发送信息，并在每个固定的时间段使用不同的通信半径。

一般而言，多通信半径的DV-Hop算法的前提环境是锚节点有延时功能，可以有多种通信半径范围。网络中未知节点通信范围相同。所有节点可以接收和发送信息。

n通信半径的DV-Hop算法定位步骤：

第一步：锚节点计时开始，向网络以通信半径R1广播信息。信息内容包括锚节点编号、坐标、跳数值e1。接收节点保留信息并不转发。

第二步：计时一段时间(锚节点传输信息和接收节点保留信息所需要的时间)，假设为t，锚节点计时清零，又开始计时，第二次向网络广播，此次广播信息中的跳数值为e2，通信半径使用R2。接收节点如果在第一步没有接收信息则保留并不转发信息。如果在第一步已经接收了某锚节点的信息则抛弃。

第n+1步：锚节点计算自己平均每一跳距离，如式(1)，并广播。接收节点只接受最近的锚节点平均跳距，并作为校正值。

(1)

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

最后一步，未知节点根据校正值和最小跳数求到每锚节点间的距离，如式(2)。当得到超过三个以上锚节点距离时，可以用三边测量法、极大似然估计法等计算坐标。

dlj=dHopp×hlj

(2)

dHopp为未知节点l的校正值(p即锚节点p)，hlj为未知节点l与锚节点j间的最小跳数值。

一般，多个通信半径DV-Hop算法中锚节点最大通信半径与未知节点的通信半径相同，在第一步到第n步锚节点发送的跳数值和通信半径根据下式得到。

(3)

由式(3)看出，通信半径R越多，跳数值e划分的越细，计算的平均每一跳距离越精确。文献[10]指出锚节点的通信半径个数越多定位精度越高，但是网络节点泛洪次数越多节点能耗越大。

定位精度是评判一个定位算法的重要指标，如式(4)，值越小说明定位误差越小，定位性能越好。

(4)

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

2改进算法

2.1改进基于多通信半径的DV-Hop算法

本文在多通信半径DV-Hop算法基础上实施最佳指数值下的加权DV-Hop算法。本文改进的算法定位步骤与n通信半径的DV-Hop算法前n步相似，在第n+1步和最后一步分别进行算法的改进。在第n+1步改进锚节点计算平均每一跳距离的公式。在最后一步，改进未知节点获取校正值的方法。

2.2改进锚节点求平均每一跳距离公式

用式(1)求平均每一跳距离会导致误差较大。文献[11]根据最小均方差准则提出求锚节点和平均每一跳距离的公式如式(5)，并提出最佳指数值概念。

(5)

本文将计算平均每一跳距离公式改为式(6)，仿真出多通信半径算法下定位精度达到最高时的指数值α，并将其作为最佳值数值代入式(6)，提出最佳指数值下的多通信半径DV-Hop改进算法。经实验发现，本文在n通信半径的DV-Hop算法第n+1步采用式(6)，在最佳指数值α下计算锚节点平均每一跳距离，会降低多通信半径DV-Hop算法误差，提高定位精高度。

(6)

2.3改进未知节点选择校正值的方法

多通信半径DV-Hop算法将未知节点的校正值选择为离自己最近的锚节点的平均每一跳距离。文献[12-13]改进DV-Hop算法时，选择全部锚节点的平均每一跳距离，提出对参与未知节点定位的锚节点进行加权处理。

本文改进多通信半径DV-Hop算法中校正值的选择和计算方法：最后一步求未知节点i校正值时，首先在第n+1步将锚节点p通过式(2)求得的平均每一跳距离乘以一个加权系数XSip。这个系数能体现未知节点i与锚节点p间的跳数值大小。使与未知节点较近的锚节点系数值较大，如式(7)：

(7)

然后，将所有锚节点乘以加权系数的平均每一跳距离累加，累加值作为该未知节点的校正值JZi，如式(8)：

(8)

式(8)中锚节点平均每一跳距离dHopp采用最佳指数值下的式(6)计算，进一步减小距离估算误差。

最后，将未知节点i的校正值乘以与其他锚节点间的跳数值，求得该未知节点与其它锚节点间的估算距离。本文算法在n通信半径的DV-Hop算法最后一步采用式(9)计算未知节点与锚节点的估算距离，如式(9)：

dij=JZi×hij

(9)

3MATLAB实验

考虑多通信半径算法中通信半径数越多节点泛洪次数越多，会影响节点能量消耗和网络生命周期，所以本文只实验基于双通信半径的改进算法。

3.1双通信半径算法与最佳指数加权算法

假设网络区域为100米边长的正方形，随机部署100个节点，锚节点覆盖率9%。节点分布环境如图1所示。

图1　节点分布

在相同锚节点覆盖率和不同的通信半径下，仿真对比文献[6]提出的基于双通信半径的DV-Hop算法、原DV-Hop算法、最佳指数值下的加权DV-Hop算法(单通信半径)。对比两种改进算法能提高的定位精度。由于节点分布随机性，程序仿真100次，如图2所示。

图2　三种算法对比

文献[6]算法比原DV-Hop算法能大大提高定位精度。最佳指数下的加权DV-Hop算法提高的定位精度没有文献[6]算法高。通信半径35米时，文献[6]、最佳指数加权DV-Hop算法分别提高定位精度12.7%、1.85%。

3.2基于双通信半径的最佳指数加权算法

将基于双通信半径加权DV-Hop算法用式(6)求锚节点平均每一跳距离。取不同的α值，找出使双通信半径加权DV-Hop算法的定位精度最高时的α值，并将此值作为最佳值。如图3所示，相同通信半径下，随着指数值增大，定位精度先提高后降低，且不同的通信半径对应不同的最佳指数。

图3　求最佳指数值

将最佳指数值下基于双通信半径的加权DV-Hop算法(即本文改进的算法)与文献[6]算法对比，由于节点分布随机性，程序仿真100次。如图4所示，在不同的通信半径下，本文算法比文献[6]算法定位精度高约2%。

图4两种算法对比

对比图2和图4，可以看出，锚节点覆盖率9%，不同的通信半径下，最佳指数下的加权DV-Hop算法能比DV-Hop算法提高定位精度约1.7%左右，基于双通信半径的最佳指数加权算法能比基于双通信半径的算法提高2%左右的定位精度，所以两种改进的DV-Hop算法的结合能提高的定位精度不是叠加的。本文改进的基于双通信半径的DV-Hop算法能大大提高DV-Hop算法定位精度，通信半径35米时，提高约14.65%。

为了进一步验证改进算法的定位性能，仿真不同锚节点覆盖率和不同通信半径下改进的算法，并与基于双通信半径的DV-Hop算法对比，如图5所示。

图5　两种算法对比

在锚节点覆盖率取10%~28%时，通信半径取25、30、35、40、45、50米时，改进的基于双通信半径DV-Hop算法定位精度明显比基于双通信半径DV-Hop算法高2.5%左右。

4结语

基于多通信半径的DV-Hop算法能大大提高节点定位精度。本文结合文献[6]提出的基于双通信半径的DV-Hop算法进一步改进算法，提出基于双通信半径的最佳指数加权DV-Hop算法。首先，改进锚节点平均每一跳距离公式，求出最佳指数值。然后，将最佳指数之下的锚节点平均每一跳距离乘以加权系数。改进未知节点估算与锚节点间距离的公式，从而减小估算误差。实验结果证明改进的算法能进一步提高定位精度，锚节点覆盖率9%，通信半径35米时，分别比DV-Hop算法、双通信半径的DV-Hop算法提高定位精度14.7%、2%。下一步将研究未知节点获取校正值的方法，进一步提升定位精度。

参考文献：

[1]彭力.无线传感器网络技术[M].北京:冶金工业出版社,2011:2.

PENG Li. Wireless Sensor Network Technology[M].Beijing: Metallurgical Industry Press,2011:2.

[2]曹文明.传感器网络覆盖定位模糊信息处理方法[M]. 北京:电子工业出版社,2010:11.

CAO Wen-ming. Fuzzy Information Processing Method for Sensor Network Coverage[M].Beijing: Electronic Industry Press,2010:11.

[3]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.

[4]WANG W, CHEN. An Improved DV-Distance Localization Algorithm for Wireless Sensor Networks[C]. Advanced Computer Control (ICACC), 2010 2nd International Conference on .IEEE, March 2010 , Volume 5 ,472-476.

[5]WANG Bang, WU Guang, WANG Shu, YANG L T. Localization based on Adaptive Regulated Neighborhood Distance for Wireless Sensor Networks with a General Radio Propagation Model[J].IEEE.Sensors Journal,2014, 14(11):3754-3762.

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

LI Juan, LIU Yu, QIAN Zhi-hong. Improved DV-Hop Localization Algorithm based on Two Communication Ranges for Wireless Sensor Network[J]. Journal of Jilin University (Engineering and Technology Edition), 2014,44(02):502-507.

[7]Njculescu D, Nath B. DV based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication System, 2003,22(1/4):267-280.

[8]Njculescu D, Nath B. Ad Hoc Positioning System(APS) Using AoA[C].IEEE INFOCOM 2003,San Franciso, 2003,3:1734-1743.

[9]黄炎炎,陈向东,倪进权等.改进的DV-Hop无线传感器网络定位算法[J].通信技术,2014, 47(07):765- 769.

HUANG Yan-yan, CHEN Xiang-dong, NI Jin-quan, et al. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Communications Technology, 2014,47(07):765-769.

[10]刘士兴,黄俊杰,刘宏银等.基于多通信半径的加权DV-Hop定位算法[J].传感技术学报,2015,28(06): 883-887.

LIU Shi-xing, HUANG Jun-jie, LIU Hong-yin. An Improving DV-Hop Algorithm based on Multi Communication Radius [J].Chinese Journal of Sensors and Actuators,2015,28(06) :883-887.

[11]马淑丽,赵建平.无线传感器网络中DV-Hop定位算法的改进[J].通信技术,2015,48(07):840-844.

MA Shu-li,ZHAO Jian-ping. The Improvement of DV-Hop Algorithm in Wirless Sensor Networks[J]. Communications Technology, 2015, 48(07):840-844.

[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]蒋馥珍.基DV-HOP的无线传感器网络定位算法研究[D].太原:太原理工大学,2011.

JIANG Fu-zhen. Research on Location Algorithm based on DV-Hop in WSN[D].Taiyuan:Taiyuan University of Technology,2011.

赵建平(1964—)，男，教授，主要研究方向为无线通信技术；

马淑丽(1989—)，女，硕士研究生，主要研究方向为无线传感器网络、无线通信技术。

DV-Hop Modified Algorithm based on Double Communication Radius

ZHAO Jian-ping， MA Shu-li

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

Abstract：Node localization technology is one of the key technologies in wireless sensor networks. DV-Hop localization algorithm based on double communication radius, although has considerable improvement on the positioning accuracy considerably as compared with DV-Hop algorithm, also could be further modified. Based on dual communication radius location algorithm, the formula for calculating the average jump distance of the anchor nodes is improved with the optimal index value concept. When the average hop distance is weighted by the unknown node selection correction, the corrected value of the unknown node could be affected by the distance of between the anchor node and the unknown node. MATALB simulation experiments show that the proposed optimal index weighted DV-Hop algorithm based on double communication radius could improve the positioning precision without any increase in hardware cost of the node.

Key words：wireless sensor network; node localization; double communication radius DV-Hop; weighted DV-Hop

作者简介：

中图分类号：TP393

文献标志码：A

文章编号：1002-0802(2015)12-1406-05

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

收稿日期：2015-07-16；修回日期：2015-10-25Received date:2015-07-16；Revised date：2015-10-25

doi:10.3969/j.issn.1002-0802.2015.12.017