基于牛頓迭代法的DV-Hop改進定位算法

仇瑩 倪曉軍

摘要：無線傳感網中的節點定位技術應用廣泛。然而由于監測區域易變、節點隨機部署，因此在節點定位上就存在誤差。為了提升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的每跳平均距離。

計算兩兩信標節點間真實與估計距離的距離誤差及最小跳數值（不重復計算）。如圖2所示，需計算A與B、A與C、B與C間的估算距離、真實距離及最小跳數值，并利用公式（5）計算整個WSN一跳的距離誤差。如圖2所示，整個WSN一跳的距離誤差ErrHop的值就等于（|RAB-EAB|+|RAC-EAC|+|RBC-EBC|/（hAB+hAC+hBC）。

（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算法更適合拓撲結構規則的網絡?；贒V-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-），男，江蘇南京人，碩士研究生，副教授，主要研究方向：無線傳感網、嵌入式系統設。