基于牛顿迭代法的DV-Hop改进定位算法

2020-10-09仇莹倪晓军

计算机时代 2020年9期

仇莹倪晓军

摘要：无线传感网中的节点定位技术应用广泛。然而由于监测区域易变、节点随机部署，因此在节点定位上就存在误差。为了提升DV-Hop算法的定位精度，提出改进后的NDV-Hop（Newton DV-Hop）算法。该算法首先使用整个WSN的每跳平均距离来改进信标节点初始每跳平均距离，再利用信标节点之间真实与估算距离的距离误差来改进未知节点与信标节点间的估算距离，最后引入牛顿法来优化DV-Hop算法计算出来的未知节点估算坐标。相比DV-Hop算法，该算法提升了节点定位精度。

关键词：无线传感网;节点定位;DV-Hop：定位精度;牛顿法

中图分类号：TP393

文献标识码：A

文章编号：1006-8228（2020）09-29-05

Optimizing DV-Hop localization algorithm with Newton's method

Qiu Ying， Ni Xiaojun

（School ofC Computer Science. Nanjing University of Post and TelecornmiLnications， Nanjing， Jiangsu 210023， China）

Abstract： Node localization technology is widely used in wireless sensor networks. However. due to the variability of monitoringarea and random deployment of nodes. there are errors in node localization. In order to improve the positioning accuracy of DV-Hop algorithm. an improved NDV-Hop （Newton DV-Hop） algorithm is proposed. NDV-Hop algorithm uses the whole WSN' averagedistance of each hop to improve original beacon nodes' average distance of each hop， and then uses distance error between actualdistance and estimated distance of two beacon nodes to improve estimated distance of unknown node. Finally， Newton's method isintroduced to optimize the estimated coordinates of unknown nodes calculated by DV-Hop algorithm. Compared with DV-Hopalgorithm， NDV-Hop algorithm improves the accuracy of node localization.

Key words： wireless sensor networks; node localization; DV-Hop; localization accuracy; Newton method

0引言

无线传感网络利用小型集成传感器对监测对象进行实时监控及数据回收与处理，并将信息传给管理节点[2]。基于对节点位置信息的需求，节点定位算法[3-4]应运而生。该算法分为两类：测距算法与非测距算法瞄州。前者有RSSI[7]、TOA[8]、TDOA、AOA算法，后者有质心[9]、凸算法[10]、DV-Hop[13]、Amorphous[11]、APTI[12]等算法。測距算法具有较高的定位精度，但所需硬件设备及通信量都较高;非测距算法需较少的硬件设备及通信量，但定位精度又不及测距算法。考虑到待监测区域环境易变，因此我们认为，非测距算法更适用。DV-Hop算法[13]是一种较为经典的非测距类算法。本文首先简述DV-Hop算法，指出其不足，进而对DV-Hop算法改进。

1DV-Hop算法简述

DV-Hop算法是基于距离矢量路由和GPS技术[15]而提出，大致分为三步：

（1）信标节点通过泛洪方式将自身数据包广播至WSN中，数据包内含有信标节点位置信息（xi，yi）以及跳数值（hopi），通信半径范围内的节点都会收到此数据包，将数据包中的跳数值加1并进行保存。为确保WSN中所有节点都能获得到每个信标节点的最小跳数值，接收数据包的节点需保留较小跳数值的数据包，放弃较大跳数值的数据包[15]。

（2）每个信标节点都可获取其他信标节点的位置信息以及与这些信标节点之间的最小跳数值，并根据公式（1）计算出两两信标节点之间的真实距离。再利用公式（2）计算每个信标节点的每跳平均距离[16]。

（1）

（2）其中，（xi，yi）、（xi，yi）是信标节点i、j坐标，hij是i和j最小跳数值。

（3）信标节点再次通过泛洪方式将自身的每跳平均距离广播出去[17]，未知节点将第一次接收的每跳平均距离作为自身校正值，并放弃其他校正值。此方法确保未知节点可从距离自身最近的信标节点获取校正值。并利用公式（3）计算出未知节点与信标节点间见得估计距离。当未知节点获取足够的距离时，便可通过三边测距等方法来估算自身坐标。

Distancemn=HopSizen*hmn

（3）其中，m、n是信标节点与未知节点，HopSizen是节点n的每跳平均距离，hmn是m与n的最小跳数值。

2DV-Hop算法分析

（1）节点的随机部署会导致以下几种情况：信标节点与未知节点分别部署在某一集中区域;信标节点与未知节点重合;节点处于网络边缘或外围;这就使得网络的拓扑结构呈现不规则状态，影响DV-Hop算法性能。此外，每个节点都需接收、广播所有信标节点的数据包，然而有些数据包对接收节点是无用的，这样无意义的接收、广播必会增加网络流量，消耗节点能量[16，18]。

（2）跳数值依据通信半径、广播次数来计算，通信半径范围内的跳数值都为1，且该值会随着广播次数的增加而增加。但当节点间为“U”型路径时，如图1所示，此时跳数值计算方法就存在不足，节点A和B间的最小跳数值为2，但依据DV-Hop计算出来的最小跳数值是4，与真实值相差一倍。此外，每个信标节点的每跳平均距离都不同，利用某个信标节点的每跳平均距离去替代未知节点的校正值并不真实。且当未知节点获取足够的距离时，便会估算自身坐标，然而此坐标也是依据估计距离计算而来，误差的不断积累，最终定位精度受到影响[16]。

3DV-Hop算法改进

3.1每跳平均距离的改进

利用公式（4）将所有信标节点的每跳平均距离求取平均值，较大的每跳平均距离会得到缩减，较小的每跳平均距离会得到补偿。

（4）其中，m是信标节点的数目，HopSizei是信标节点i的每跳平均距离。

（5）其中，R、E是两两节点间的真实距离、估算距离，hij是两两节点间的最小跳数值。

最后利用公式（6）计算整个WSN更新后的每跳平均距离;接着利用公式（7）计算每个信标节点更新后的每跳平均距离。

（6）

（7）

3.2估算距离的改进

依据DV-Hop可计算出未知节点与信标节点间的估算距离。首先计算某信标节点与其余信标节点间真实距离与估算距离的距离误差，接着计算此距离误差占两两信标节点估算距离的比例。最后将这些距离比例求取平均值，并将此均值作为距离修正因子，记为R;则改进后的未知节点与信标节点间的估算距离可利用初始估算距离、修正因子R、修正系数a以及公式（8）计算出来。

（8）其中，Distanceij是DV-Hop计算出来的未知节点j和信标节点i间的估算距离。

如图3所示，L1，L2，L3是信标节点，U是未知节点。假设L1与L2，L2与L3间的估算距離是依据L1的每跳平均距离计算而来，值为EstDis（L1L2）=48，EstDis（L1k）=105，L1与U之间的估算距离为50。则L1与L1之间的距离误差比例为ratio（L1L2）=（48-40）/48=0.167，L1与L3之间的距离误差比例就为（105-100）/l05=0.047;那么距离修正因子R的值等于（ratio（L1L2） +ratio（L1L3）/2=（0.167+0.047）/2=0.107。基于上述的计算并假定a取为2，则信标节点L1到未知节点U改进后的估算距离为50*（1-0.1072） =49.42。（曲线代替直线距离会使得估算距离大于等于真实距离）

3.3未知节点坐标的改进

牛顿法[19-20]是解决无约束优化问题的通用方法，具有较快收敛速度。流程如图4所示。牛顿法的使用需选取合适的初始迭代值，如果该值选取不当，后续的迭代将无法进行。因此在这一步中，首先获取每个未知节点基于DV-Hop计算而来的估算坐标，并将这些估算坐标作为牛顿法的初始值。此外，牛顿法的目标函数也是需要思考的问题，考虑到未知节点、信标节点间的估算距离及未知节点初始估算坐标均已知晓，因此目标函数可设为公式（9）。

（9）其中，m是未知节点数目，di是改进后的估算距离，（xi，yi）是初始估算坐标。

4仿真实验

实验基于Matalb R2017a平台进行，并将DV-Hop算法、改进算法、文献[21]算法进行对比分析。假设实验环境是一个100m长，100m宽的区域，区域内的节点是随机部署，如图5所示。

此次实验分别通过改变信标节点数目、通信半径以及节点数目来观察改进算法是否具有可行性，并利用公式（10）中的节点定位误差err来衡量算法[16]。

（10）其中，m是未知节点数目，（xi，yi）是未知节点初始坐标，（x，y）是待求的优化后的坐标，R为通信半径。

对比上述三种定位误差图，可以明显看出，改进算法相比于DV-Hop、文献[21]算法，其定位精度得到了提升。首先当信标节点数目较少时，未知节点可获取的数据信息也相对较少，正确率也相对较低，如图6所示，三种算法的定位误差均偏高，当信标节点数目达到一定数值后，此时可获取的信息逐渐增多，正确率得到了提升，因此三种算法的误差也逐渐趋于平稳;其次当通信半径处于某段范围内时，算法的定位误差也均相对平稳，如图7所示，此时前后误差波动较小，当达到某一数值时，三种算法的定位误差开始逐渐缩小;最后当节点数目不断增加时，此时信标节点数目不变，增加的节点就是未知节点，由于未知节点所需信息都来自信标节点，且未知节点的计算都是估计值，因此定位误差会随着未知节点的增加而增大，如图8所示，三种算法的定位误差在最开始时都是一个相对较小的数值，随着节点增加，误差开始慢慢增大。由上述分析可知，改进算法存在一定的有效性及合理性。

5结束语

改进算法利用信标节点的每跳平均距离、节点间估算距离来修正初始值，并利用牛顿法对估算坐标进行修正。仿真实验表明了改进算法的可行性，定位误差缩小，定位精度得到提升。但由于DV-Hop算法本身是估算算法且当节点分布不规则或过度集中时，DV-Hop算法的性能会受影响，因此DV-Hop算法更适合拓扑结构规则的网络。基于DV-Hop算法改进的算法也更适合拓扑结构规则的网络。算法不断地优化需要具有优越性与普适性，将来的研究不仅需要进一步提升DV-Hop这类算法的定位精度，需要扩大也算此类法的适用范围。

参考文献（References）：

[1] Liu Kezhong， Yan Xinping， Hu Fuping. A Modified DV-Hop Localization Algorithm for Wireless Sensor Net-works.In 2009 IEEE International Conference on Intel-ligent Computing and Intelligent Systems[C]. Shanghai，China：IEEE， 2009：530-533

[2]GuiLinqing ， Thierry Val， Wei Anne， et al. Improvement ofrange-free localization technology by a novel DV-hopprotocol in wireless sensor networks[J]. Ad HocNetworks，2015.24：55-73

[3]Tashnim J S， Colin E， Vijay D， et al. Advances onlocalization techniques for wireless sensor networks： Asurvey[J].Computer Networks，2016.110：284-305

[4]Livinsa Z M， Jayshri， S. An Optimized Analysis ofLocalization Algorithm in Wireless Sensor Networks[J].Wireless Personal Communications， 2017.96（1）： 1419-1435

[5]Rahaman M， Trihanuranto I， Mayasari R. Trilateration anditerative multilateration algorithm for localizationschemes on wireless sensor network.2017 InternationalConference on Control. Electronics， Renewable Energyand Communications[C].Yogyakarta， IEEE，2017.88-92

[6]Goyat R， Rai M K， Kumar G， et al. Energy Efficient Range-Free Localization Algorithm for Wireless SensorNetworks[J].Sensors （Basel， Switzerland），2019.19（16）.

[7]Pita R， Utrilla R， Bodrigurz-urrunero R， et al. ExperimentalEvaluation of an RSSI-Based Localization Algorithmon IOT End-Devices[J]. Sensors，2019.19（18）：24

[8]Shalaby M， Shokair M， Mseeiha N W. PerformanceEnhancement of TOA Localized Wireless SensorNetworks[J].Wireless Personal Communications， 2017.95（4）：4667-4679

[9]CuevasU-Martinez JC， Yuste-Delgado AJ， Leon-SanchezAJ， et al. ANew Centralized ClusteringAlgorithm for Wireless Sensor Networks[J]. Sensors（Basel， Switzerland），2019.19（20）：4391

[10]Liu Wu Sun Donghong， Ping， ren， et al. Co-SRL： AConvex Optimization Algorithm forAnchor Localiza- tion in Wireless Sensor Networks[J].AASRI Procedia，2013.5：62-66

[11]安文秀，赵菊敏，李灯熬.基于Amorphous的无线传感器网絡定位算法研究[J].传感器与微系统，2013.32（2）：33-35

[12]TanHongbin，LiuFeng.Research and implementation ofAPrr positioning algorithm in WSN.2012 9thIntema—tional Conference on Fuzzy Systems and KnowledgeDiscovery[C].IEEE，2012：2212—2215

[13]Mashid M，Hassan T，Pooria T.An improved DV—Hoplocalization algorithm based on evolutionary algorithms[J].Telecommunication Systems，2017.64（4）：639—647

[14]Wu Jiawei，YuJinming，OuAijun，et al.RCDV—HopLocalization Algorithm for WSN.2012 8th Intema—tional Conference on Wireless Communications.Net—working and Mobile Computing[C].Shanghai，China，IEEE.2012.

[15]趙菊敏，李灯熬，武健.基于DV—hop定位的误差加权改进算法[J].自动化仪表，2014.35（7）：1—4

[16]孟雯雯，赵建平，王蒙等，基于DV—Hop的改进定位算法[J].通信技术，2016.49（11）：1447—1452

[17]Hu Yu， LiXuemei. An improvement of DV—Hoplocalization algo rithm for wireless sensor netWorks[J].Telecommunication Systems，2013.53（1）：13—18

[18]朱慧勇.DV—Hop定位算的误差分析[J].无线互联科技，2018.15（7）：61—62

[19]柳辉，解线性方程的牛顿迭代法及其应用[J].重庆工学院学报，2007.8：95—98

[20]曹霞.牛顿法在求解计算中的应用研究[J].价值工程，2013.32（17）：196—197

[21]Tao Qihong，Zhang Linghua.Enhancement of DV—HopWeighted Hop Distance. 2016 IEEE AdvancedInformation Management， Communicates， Electronicand Automation Control Conference[C].Xi'an，China，IEEE，2016：1617—1620

收稿日期：2020-05-12

作者简介：仇莹（1996-），女，江苏盐城人，硕士研究生，主要研究方向：无线传感网络。

通讯作者：倪晓军（1969-），男，江苏南京人，硕士研究生，副教授，主要研究方向：无线传感网、嵌入式系统设。