仇瑩 倪曉軍

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

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

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：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引言

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

1DV-Hop算法簡述

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

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

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

（1）

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

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

Distancemn=HopSizen*hmn

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

2DV-Hop算法分析

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

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

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

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

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

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

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

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

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

（6）

（7）

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

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

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

如圖3所示，L1，L2，L3是信標(biāo)節(jié)點，U是未知節(jié)點。假設(shè)L1與L2，L2與L3間的估算距離是依據(jù)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?；谏鲜龅挠嬎悴⒓俣╝取為2，則信標(biāo)節(jié)點L1到未知節(jié)點U改進(jìn)后的估算距離為50*（1-0.1072） =49.42。（曲線代替直線距離會使得估算距離大于等于真實距離）

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

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

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

4仿真實驗

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

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

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

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

5結(jié)束語

改進(jìn)算法利用信標(biāo)節(jié)點的每跳平均距離、節(jié)點間估算距離來修正初始值，并利用牛頓法對估算坐標(biāo)進(jìn)行修正。仿真實驗表明了改進(jìn)算法的可行性，定位誤差縮小，定位精度得到提升。但由于DV-Hop算法本身是估算算法且當(dāng)節(jié)點分布不規(guī)則或過度集中時，DV-Hop算法的性能會受影響，因此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)越性與普適性，將來的研究不僅需要進(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ǎ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].自動化儀表，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].無線互聯(lián)科技，2018.15（7）：61—62

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

[20]曹霞.牛頓法在求解計算中的應(yīng)用研究[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-），女，江蘇鹽城人，碩士研究生，主要研究方向：無線傳感網(wǎng)絡(luò)。

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