基于牛頓迭代法的DV-Hop改進(jìn)定位算法

仇瑩 倪曉軍

摘要：無(wú)線傳感網(wǎng)中的節(jié)點(diǎn)定位技術(shù)應(yīng)用廣泛。然而由于監(jiān)測(cè)區(qū)域易變、節(jié)點(diǎn)隨機(jī)部署，因此在節(jié)點(diǎn)定位上就存在誤差。為了提升DV-Hop算法的定位精度，提出改進(jìn)后的NDV-Hop（Newton DV-Hop）算法。該算法首先使用整個(gè)WSN的每跳平均距離來(lái)改進(jìn)信標(biāo)節(jié)點(diǎn)初始每跳平均距離，再利用信標(biāo)節(jié)點(diǎn)之間真實(shí)與估算距離的距離誤差來(lái)改進(jìn)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的估算距離，最后引入牛頓法來(lái)優(yōu)化DV-Hop算法計(jì)算出來(lái)的未知節(jié)點(diǎn)估算坐標(biāo)。相比DV-Hop算法，該算法提升了節(jié)點(diǎn)定位精度。

關(guān)鍵詞：無(wú)線傳感網(wǎng);節(jié)點(diǎn)定位;DV-Hop：定位精度;牛頓法

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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引言

無(wú)線傳感網(wǎng)絡(luò)利用小型集成傳感器對(duì)監(jiān)測(cè)對(duì)象進(jìn)行實(shí)時(shí)監(jiān)控及數(shù)據(jù)回收與處理，并將信息傳給管理節(jié)點(diǎn)[2]。基于對(duì)節(jié)點(diǎn)位置信息的需求，節(jié)點(diǎn)定位算法[3-4]應(yīng)運(yùn)而生。該算法分為兩類：測(cè)距算法與非測(cè)距算法瞄州。前者有RSSI[7]、TOA[8]、TDOA、AOA算法，后者有質(zhì)心[9]、凸算法[10]、DV-Hop[13]、Amorphous[11]、APTI[12]等算法。測(cè)距算法具有較高的定位精度，但所需硬件設(shè)備及通信量都較高;非測(cè)距算法需較少的硬件設(shè)備及通信量，但定位精度又不及測(cè)距算法?？紤]到待監(jiān)測(cè)區(qū)域環(huán)境易變，因此我們認(rèn)為，非測(cè)距算法更適用。DV-Hop算法[13]是一種較為經(jīng)典的非測(cè)距類算法。本文首先簡(jiǎn)述DV-Hop算法，指出其不足，進(jìn)而對(duì)DV-Hop算法改進(jìn)。

1DV-Hop算法簡(jiǎn)述

DV-Hop算法是基于距離矢量路由和GPS技術(shù)[15]而提出，大致分為三步：

（1）信標(biāo)節(jié)點(diǎn)通過(guò)泛洪方式將自身數(shù)據(jù)包廣播至WSN中，數(shù)據(jù)包內(nèi)含有信標(biāo)節(jié)點(diǎn)位置信息（xi，yi）以及跳數(shù)值（hopi），通信半徑范圍內(nèi)的節(jié)點(diǎn)都會(huì)收到此數(shù)據(jù)包，將數(shù)據(jù)包中的跳數(shù)值加1并進(jìn)行保存。為確保WSN中所有節(jié)點(diǎn)都能獲得到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)值，接收數(shù)據(jù)包的節(jié)點(diǎn)需保留較小跳數(shù)值的數(shù)據(jù)包，放棄較大跳數(shù)值的數(shù)據(jù)包[15]。

（2）每個(gè)信標(biāo)節(jié)點(diǎn)都可獲取其他信標(biāo)節(jié)點(diǎn)的位置信息以及與這些信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)值，并根據(jù)公式（1）計(jì)算出兩兩信標(biāo)節(jié)點(diǎn)之間的真實(shí)距離。再利用公式（2）計(jì)算每個(gè)信標(biāo)節(jié)點(diǎn)的每跳平均距離[16]。

（1）

（2）其中，（xi，yi）、（xi，yi）是信標(biāo)節(jié)點(diǎn)i、j坐標(biāo)，hij是i和j最小跳數(shù)值。

（3）信標(biāo)節(jié)點(diǎn)再次通過(guò)泛洪方式將自身的每跳平均距離廣播出去[17]，未知節(jié)點(diǎn)將第一次接收的每跳平均距離作為自身校正值，并放棄其他校正值。此方法確保未知節(jié)點(diǎn)可從距離自身最近的信標(biāo)節(jié)點(diǎn)獲取校正值。并利用公式（3）計(jì)算出未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間見(jiàn)得估計(jì)距離。當(dāng)未知節(jié)點(diǎn)獲取足夠的距離時(shí)，便可通過(guò)三邊測(cè)距等方法來(lái)估算自身坐標(biāo)。

Distancemn=HopSizen*hmn

（3）其中，m、n是信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)，HopSizen是節(jié)點(diǎn)n的每跳平均距離，hmn是m與n的最小跳數(shù)值。

2DV-Hop算法分析

（1）節(jié)點(diǎn)的隨機(jī)部署會(huì)導(dǎo)致以下幾種情況：信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)分別部署在某一集中區(qū)域;信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)重合;節(jié)點(diǎn)處于網(wǎng)絡(luò)邊緣或外圍;這就使得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)呈現(xiàn)不規(guī)則狀態(tài)，影響DV-Hop算法性能。此外，每個(gè)節(jié)點(diǎn)都需接收、廣播所有信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包，然而有些數(shù)據(jù)包對(duì)接收節(jié)點(diǎn)是無(wú)用的，這樣無(wú)意義的接收、廣播必會(huì)增加網(wǎng)絡(luò)流量，消耗節(jié)點(diǎn)能量[16，18]。

（2）跳數(shù)值依據(jù)通信半徑、廣播次數(shù)來(lái)計(jì)算，通信半徑范圍內(nèi)的跳數(shù)值都為1，且該值會(huì)隨著廣播次數(shù)的增加而增加。但當(dāng)節(jié)點(diǎn)間為“U”型路徑時(shí)，如圖1所示，此時(shí)跳數(shù)值計(jì)算方法就存在不足，節(jié)點(diǎn)A和B間的最小跳數(shù)值為2，但依據(jù)DV-Hop計(jì)算出來(lái)的最小跳數(shù)值是4，與真實(shí)值相差一倍。此外，每個(gè)信標(biāo)節(jié)點(diǎn)的每跳平均距離都不同，利用某個(gè)信標(biāo)節(jié)點(diǎn)的每跳平均距離去替代未知節(jié)點(diǎn)的校正值并不真實(shí)。且當(dāng)未知節(jié)點(diǎn)獲取足夠的距離時(shí)，便會(huì)估算自身坐標(biāo)，然而此坐標(biāo)也是依據(jù)估計(jì)距離計(jì)算而來(lái)，誤差的不斷積累，最終定位精度受到影響[16]。

3DV-Hop算法改進(jìn)

3.1每跳平均距離的改進(jìn)

利用公式（4）將所有信標(biāo)節(jié)點(diǎn)的每跳平均距離求取平均值，較大的每跳平均距離會(huì)得到縮減，較小的每跳平均距離會(huì)得到補(bǔ)償。

（4）其中，m是信標(biāo)節(jié)點(diǎn)的數(shù)目，HopSizei是信標(biāo)節(jié)點(diǎn)i的每跳平均距離。

計(jì)算兩兩信標(biāo)節(jié)點(diǎn)間真實(shí)與估計(jì)距離的距離誤差及最小跳數(shù)值（不重復(fù)計(jì)算）。如圖2所示，需計(jì)算A與B、A與C、B與C間的估算距離、真實(shí)距離及最小跳數(shù)值，并利用公式（5）計(jì)算整個(gè)WSN一跳的距離誤差。如圖2所示，整個(gè)WSN一跳的距離誤差ErrHop的值就等于（|RAB-EAB|+|RAC-EAC|+|RBC-EBC|/（hAB+hAC+hBC）。

（5）其中，R、E是兩兩節(jié)點(diǎn)間的真實(shí)距離、估算距離，hij是兩兩節(jié)點(diǎn)間的最小跳數(shù)值。

最后利用公式（6）計(jì)算整個(gè)WSN更新后的每跳平均距離;接著利用公式（7）計(jì)算每個(gè)信標(biāo)節(jié)點(diǎn)更新后的每跳平均距離。

（6）

（7）

3.2估算距離的改進(jìn)

依據(jù)DV-Hop可計(jì)算出未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的估算距離。首先計(jì)算某信標(biāo)節(jié)點(diǎn)與其余信標(biāo)節(jié)點(diǎn)間真實(shí)距離與估算距離的距離誤差，接著計(jì)算此距離誤差占兩兩信標(biāo)節(jié)點(diǎn)估算距離的比例。最后將這些距離比例求取平均值，并將此均值作為距離修正因子，記為R;則改進(jìn)后的未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的估算距離可利用初始估算距離、修正因子R、修正系數(shù)a以及公式（8）計(jì)算出來(lái)。

（8）其中，Distanceij是DV-Hop計(jì)算出來(lái)的未知節(jié)點(diǎn)j和信標(biāo)節(jié)點(diǎn)i間的估算距離。

如圖3所示，L1，L2，L3是信標(biāo)節(jié)點(diǎn)，U是未知節(jié)點(diǎn)。假設(shè)L1與L2，L2與L3間的估算距離是依據(jù)L1的每跳平均距離計(jì)算而來(lái)，值為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?；谏鲜龅挠?jì)算并假定a取為2，則信標(biāo)節(jié)點(diǎn)L1到未知節(jié)點(diǎn)U改進(jìn)后的估算距離為50*（1-0.1072） =49.42。（曲線代替直線距離會(huì)使得估算距離大于等于真實(shí)距離）

3.3未知節(jié)點(diǎn)坐標(biāo)的改進(jìn)

牛頓法[19-20]是解決無(wú)約束優(yōu)化問(wèn)題的通用方法，具有較快收斂速度。流程如圖4所示。牛頓法的使用需選取合適的初始迭代值，如果該值選取不當(dāng)，后續(xù)的迭代將無(wú)法進(jìn)行。因此在這一步中，首先獲取每個(gè)未知節(jié)點(diǎn)基于DV-Hop計(jì)算而來(lái)的估算坐標(biāo)，并將這些估算坐標(biāo)作為牛頓法的初始值。此外，牛頓法的目標(biāo)函數(shù)也是需要思考的問(wèn)題，考慮到未知節(jié)點(diǎn)、信標(biāo)節(jié)點(diǎn)間的估算距離及未知節(jié)點(diǎn)初始估算坐標(biāo)均已知曉，因此目標(biāo)函數(shù)可設(shè)為公式（9）。

（9）其中，m是未知節(jié)點(diǎn)數(shù)目，di是改進(jìn)后的估算距離，（xi，yi）是初始估算坐標(biāo)。

4仿真實(shí)驗(yàn)

實(shí)驗(yàn)基于Matalb R2017a平臺(tái)進(jìn)行，并將DV-Hop算法、改進(jìn)算法、文獻(xiàn)[21]算法進(jìn)行對(duì)比分析。假設(shè)實(shí)驗(yàn)環(huán)境是一個(gè)100m長(zhǎng)，100m寬的區(qū)域，區(qū)域內(nèi)的節(jié)點(diǎn)是隨機(jī)部署，如圖5所示。

此次實(shí)驗(yàn)分別通過(guò)改變信標(biāo)節(jié)點(diǎn)數(shù)目、通信半徑以及節(jié)點(diǎn)數(shù)目來(lái)觀察改進(jìn)算法是否具有可行性，并利用公式（10）中的節(jié)點(diǎn)定位誤差err來(lái)衡量算法[16]。

（10）其中，m是未知節(jié)點(diǎn)數(shù)目，（xi，yi）是未知節(jié)點(diǎn)初始坐標(biāo)，（x，y）是待求的優(yōu)化后的坐標(biāo)，R為通信半徑。

對(duì)比上述三種定位誤差圖，可以明顯看出，改進(jìn)算法相比于DV-Hop、文獻(xiàn)[21]算法，其定位精度得到了提升。首先當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)目較少時(shí)，未知節(jié)點(diǎn)可獲取的數(shù)據(jù)信息也相對(duì)較少，正確率也相對(duì)較低，如圖6所示，三種算法的定位誤差均偏高，當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)目達(dá)到一定數(shù)值后，此時(shí)可獲取的信息逐漸增多，正確率得到了提升，因此三種算法的誤差也逐漸趨于平穩(wěn);其次當(dāng)通信半徑處于某段范圍內(nèi)時(shí)，算法的定位誤差也均相對(duì)平穩(wěn)，如圖7所示，此時(shí)前后誤差波動(dòng)較小，當(dāng)達(dá)到某一數(shù)值時(shí)，三種算法的定位誤差開(kāi)始逐漸縮小;最后當(dāng)節(jié)點(diǎn)數(shù)目不斷增加時(shí)，此時(shí)信標(biāo)節(jié)點(diǎn)數(shù)目不變，增加的節(jié)點(diǎn)就是未知節(jié)點(diǎn)，由于未知節(jié)點(diǎn)所需信息都來(lái)自信標(biāo)節(jié)點(diǎn)，且未知節(jié)點(diǎn)的計(jì)算都是估計(jì)值，因此定位誤差會(huì)隨著未知節(jié)點(diǎn)的增加而增大，如圖8所示，三種算法的定位誤差在最開(kāi)始時(shí)都是一個(gè)相對(duì)較小的數(shù)值，隨著節(jié)點(diǎn)增加，誤差開(kāi)始慢慢增大。 由上述分析可知，改進(jìn)算法存在一定的有效性及合理性。

5結(jié)束語(yǔ)

改進(jìn)算法利用信標(biāo)節(jié)點(diǎn)的每跳平均距離、節(jié)點(diǎn)間估算距離來(lái)修正初始值，并利用牛頓法對(duì)估算坐標(biāo)進(jìn)行修正。仿真實(shí)驗(yàn)表明了改進(jìn)算法的可行性，定位誤差縮小，定位精度得到提升。但由于DV-Hop算法本身是估算算法且當(dāng)節(jié)點(diǎn)分布不規(guī)則或過(guò)度集中時(shí)，DV-Hop算法的性能會(huì)受影響，因此DV-Hop算法更適合拓?fù)浣Y(jié)構(gòu)規(guī)則的網(wǎng)絡(luò)?；贒V-Hop算法改進(jìn)的算法也更適合拓?fù)浣Y(jié)構(gòu)規(guī)則的網(wǎng)絡(luò)。算法不斷地優(yōu)化需要具有優(yōu)越性與普適性，將來(lái)的研究不僅需要進(jìn)一步提升DV-Hop這類算法的定位精度，需要擴(kuò)大也算此類法的適用范圍。

參考文獻(xiàn)（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的無(wú)線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感器與微系統(tǒng)，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定位的誤差加權(quán)改進(jìn)算法[J].自動(dòng)化儀表，2014.35（7）：1—4

[16]孟雯雯，趙建平，王蒙等，基于DV—Hop的改進(jìn)定位算法[J].通信技術(shù)，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].無(wú)線互聯(lián)科技，2018.15（7）：61—62

[19]柳輝，解線性方程的牛頓迭代法及其應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)，2007.8：95—98

[20]曹霞.牛頓法在求解計(jì)算中的應(yīng)用研究[J].價(jià)值工程，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

作者簡(jiǎn)介：仇瑩（1996-），女，江蘇鹽城人，碩士研究生，主要研究方向：無(wú)線傳感網(wǎng)絡(luò)。

通訊作者：倪曉軍（1969-），男，江蘇南京人，碩士研究生，副教授，主要研究方向：無(wú)線傳感網(wǎng)、嵌入式系統(tǒng)設(shè)。