基于跳距優(yōu)化的DV-Hop定位算法

侯華 曹俊俊 王曹 楊沛釗

摘要：為提高DV-Hop算法的定位精度，該文針對DV-Hop算法存在的跳距誤差累計問題提出了一種改進方案。改進的算法從減少誤差的產(chǎn)生和擴散兩方面對原始算法進行了優(yōu)化，通過讓錨節(jié)點以多個通信半徑廣播信息來降低計算平均跳距時產(chǎn)生的初始誤差，同時又讓未知節(jié)點選擇累積誤差最小的跳距計算距離，以減少錨節(jié)點平均跳距在通信過程中導致的誤差擴散。在MATLAB中對改進的算法與原始DV-Hop算法、雙通信半徑改進算法、跳距加權算法以及跳距修正算法進行了比較，仿真結果表明，改進算法能夠最小化定位誤差，提高定位精度。

關鍵詞：無線傳感器網(wǎng)絡;DV-Hop算法;節(jié)點定位;通信半徑;誤差累計

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）06-0004-04

開放科學（資源服務）標識碼（OSID）：

1 概述

無線傳感器網(wǎng)絡由隨機分布在網(wǎng)絡中的大量傳感器節(jié)點組成[1]。這些節(jié)點用來檢測周圍環(huán)境信息并將感知到的數(shù)據(jù)以及位置轉發(fā)到被稱為匯聚節(jié)點的中心位置[2]。節(jié)點的定位算法根據(jù)其采用的定位方式主要被分為兩大類[3]。一類是在定位過程中需要進行測距的算法，這類算法需要通過硬件設備獲取到網(wǎng)絡中節(jié)點之間的距離才能夠估計出節(jié)點的位置，常見的算法有：RSSI、TOA、TDOA和AOA等。另一類是不需要測距的算法，這類算法主要依靠網(wǎng)絡中節(jié)點的拓撲結構和連通度來實現(xiàn)，不需要配備額外的測距設備，常見的算法有質心算法和DV-Hop算法等[4]。

傳統(tǒng)的DV-Hop算法雖然操作過程簡單，但是在定位精度上略顯粗糙。然而因其可塑性強的特點，國內(nèi)外學者提出了大量的改進方案來提高算法的定位精度。文獻[5]提出為未知節(jié)點所獲取的平均跳距都加上錨節(jié)點平均每跳誤差這一個修正因子，以此來減少錨節(jié)點誤差對未知節(jié)點距離計算的影響，最后使用runner-root算法來求取未知節(jié)點的位置坐標;文獻[6]中對錨節(jié)點使用了兩個通信半徑，使得節(jié)點之間的跳數(shù)更加能夠反映他們之間的真實距離;文獻[7]在算法第二階段中未知節(jié)點將錨節(jié)點誤差作為權重因子對接收到的多個跳距加權，使每個未知節(jié)點獲取的跳距都得到了修正，傳統(tǒng)算法中節(jié)點平均跳距誤差大的問題得到優(yōu)化;文獻[8]提出在未知節(jié)點獲取跳距之后，使用錨節(jié)點的單跳誤差來修正未知節(jié)點跳距中的波動，最后使用LevyPSO算法來求取未知節(jié)點的坐標。

上述改進都在一定程度上對DV-Hop算法的定位性能進行了優(yōu)化，但是該算法仍然存在著不合理跳距導致的誤差累計問題。因此，本文希望通過改進算法從誤差的源頭入手減少誤差在通信過程中的擴散，提高定位精度。

2 DV-Hop算法介紹與分析

2.1 DV-Hop算法介紹

經(jīng)典的DV-Hop算法最大的特點就是不需要測量節(jié)點間的距離便可以計算出未知節(jié)點的位置信息[9]，分為3個階段對未知節(jié)點進行定位。

第一階段：跳數(shù)估計

首先將初始的跳數(shù)值設置為0，然后錨節(jié)點將自身的坐標和跳數(shù)信息打包后向網(wǎng)絡中進行廣播。在此期間，數(shù)據(jù)包每經(jīng)過一個節(jié)點，跳數(shù)值就增加1。當網(wǎng)絡中的所有節(jié)點都接收過錨節(jié)點傳遞的數(shù)據(jù)包后，每個傳感器節(jié)點都獲得了進行通信的最小跳數(shù)[10]。

第二階段：距離計算

使用公式（1）計算錨節(jié)點的平均跳距：

[HopSizei=j≠ixi-yj2+yi-yj2j≠ihj] （1）

式中：[xi，yi]和[xj，yj]為錨節(jié)點[i]和[j]的坐標，[hj]為錨節(jié)點[i]在第一階段中保存的到錨節(jié)點[j]的最小跳數(shù)。

使用公式（2）計算未知節(jié)點與錨節(jié)點的距離：

[dkj=HopSizei×hj] （2）

式中： [HopSizei]表示一個未知節(jié)點周圍相距最近的那個錨節(jié)點的平均跳距，[hj]表示錨節(jié)點[j]在第一階段中保存的到錨節(jié)點[k]的最小跳數(shù)。

第三階段：未知節(jié)點計算自身的坐標

使用[x，y]表示未知節(jié)點的坐標，[xj，yj，j=1，2，……，n]表示錨節(jié)點[j]的坐標，再由公式（2）可得方程組：

[x1-x2+y1-y2=d21x2-x2+y2-y2=d22?xn-x2+yn-y2=d2n] （3）

式中：[dj，j=1，2，……，n]表示當前未知節(jié)點與各個錨節(jié)點之間的估計距離。

對式（3）整理可得：

[A=2x1-xn2y1-yn2x2-xn2y2-yn??2xn-1-xn2yn-1-yn] （4）

[B=x21-x2n+y21-y2n-d21+d2nx22-x2n+y22-y2n-d22+d2n?x2n-1-x2n+y2n-1-y2n-d2n-1+d2n] （5）

[X=xy] （6）

最后通過公式（7）計算出未知節(jié)點的坐標：

[X=ATA-1ATB] （7）

2.2 DV-Hop算法誤差分析

DV-Hop定位算法的優(yōu)點在于對硬件設施條件要求不高且計算簡單，但是存在定位精度較低的缺點，誤差主要表現(xiàn)在以下兩方面。

原始算法中，把任意兩個通信范圍內(nèi)的節(jié)點間的跳數(shù)都記為1。如圖1中的錨節(jié)點B、B1和B2均可在1跳范圍內(nèi)與未知節(jié)點A進行通信，根據(jù)跳數(shù)信息，可以估計出錨節(jié)點B1和B2到未知節(jié)點A的距離相等，但實際上它們之間的距離是不同的。

傳統(tǒng)的DV-Hop算法，未知節(jié)點選擇距離最近的錨節(jié)點平均跳距來計算節(jié)點間距離進而得出自身的位置信息，如果所選擇的平均跳距存在誤差，那么這個誤差就會傳遞給需要計算位置的未知節(jié)點，當未知節(jié)點計算節(jié)點間距離時，這個誤差就會得到擴散，導致定位精度的降低。

3 本文改進算法

3.1 錨節(jié)點通信半徑的選擇

由于在傳統(tǒng)的DV-Hop算法中所有的節(jié)點都有相同的通信半徑，導致在通信范圍內(nèi)不論兩個節(jié)點之間的真實距離如何，估計距離都設為一跳，造成很大的誤差。錨節(jié)點也會將計算自身平均跳距時的誤差傳遞給未知節(jié)點，所以在第一階段如何降低錨節(jié)點在計算自身的平均跳距時所產(chǎn)生的誤差是本文所要思考的。

在本文中對錨節(jié)點使用了多通信半徑的方式來優(yōu)化所提到的問題?？紤]到計算成本，采用了3通信半徑，即[R]、[13R]、[23R]，其中[R]表示網(wǎng)絡中所有節(jié)點正常進行通信時的通信半徑，其余為錨節(jié)點在廣播信息時所特有的通信半徑。錨節(jié)點的3個通信半徑將其正常通信范圍內(nèi)的節(jié)點分為3組，第一組為當錨節(jié)點以[13R]進行通信時，通信半徑內(nèi)的所有節(jié)點;第二組為當錨節(jié)點以[23R]進行通信時，通信半徑內(nèi)的所有節(jié)點;第三組為當錨節(jié)點以[R]進行通信時，通信半徑內(nèi)的所有節(jié)點。第一階段錨節(jié)點向網(wǎng)絡中廣播信息時，第一組接收到信息的節(jié)點到錨節(jié)點的跳數(shù)被記為[13]，第二組接收到信息的節(jié)點到錨節(jié)點的跳數(shù)被記為[23]，第三組接收到信息的節(jié)點到錨節(jié)點的跳數(shù)被記為1。

三組節(jié)點之間的關系如圖2所示，當錨節(jié)點發(fā)出信息后，通信半徑內(nèi)的A、B、C三個區(qū)域內(nèi)的節(jié)點到錨節(jié)點的跳數(shù)分別為[13]、[23]和1。第一階段結束后，網(wǎng)絡中的所有節(jié)點都記錄了相互之間通信的最小跳數(shù)，如果這個通信路徑中包含有A、B兩組節(jié)點，那么最終兩節(jié)點之間的跳數(shù)值就有可能出現(xiàn)小數(shù)，這就使得跳數(shù)的獲取更加的精確，從而定位的精度也得到了提高。

3.2 未知節(jié)點跳距選擇

在傳統(tǒng)的DV-Hop算法中，未知節(jié)點選擇平均跳距時并不會考慮其他錨節(jié)點，只會選擇距離最近的錨節(jié)點跳距。然而在計算錨節(jié)點平均跳距時不可避免地產(chǎn)生了初始誤差，后續(xù)的計算步驟都將使得這個初始誤差得到累計，因此如何減少錨節(jié)點平均跳距誤差的擴散是本文研究的重點。因為誤差在估計各個錨節(jié)點之間的距離時產(chǎn)生，而錨節(jié)點之間的距離大小則會決定誤差累計的大小，網(wǎng)絡中兩個節(jié)點的距離越大，它們之間的跳數(shù)也會越多，導致誤差累計增大。傳統(tǒng)的算法針對這個問題的做法是使未知節(jié)點選擇距離最近的錨節(jié)點平均跳距，這樣的做法已經(jīng)盡量避免了誤差隨著跳數(shù)增多的擴散，但這還不是最優(yōu)的做法。本文中提出來讓未知節(jié)點選擇距離自身累計誤差最小的錨節(jié)點的平均跳距作為自身的平均跳距，以減少錨節(jié)點平均跳距帶來的誤差累計。

圖3中虛線表示兩個節(jié)點之間的真實距離，實線表示兩節(jié)點之間的通信線路。A、B兩個錨節(jié)點之間的實際距離為25，跳數(shù)值為3;A、C兩個錨節(jié)點之間的實際距離為20，跳數(shù)值為4;B、C兩個錨節(jié)點之間的實際距離為42，跳數(shù)為5。通過圖上的數(shù)據(jù)可以計算出三個錨節(jié)點各自的平均每跳距離。

[HopSizeA=20+253+4=6.43] （8）

[HopSizeB=42+253+5=8.38] （9）

[HopSizeC=20+424+5=6.89] （10）

表1中展示了圖3各錨節(jié)點之間的估計距離與真實距離的誤差，根據(jù)表中數(shù)據(jù)可以得出錨節(jié)點A的平均每跳誤差為：[5.71+5.723+4=1.63];錨節(jié)點B的平均每跳誤差為：[0.14+0.13+5=0.03];錨節(jié)點C的平均每跳誤差為：[7.56+7.554+5=1.68]。

圖3中與未知節(jié)點D距離最近的錨節(jié)點是節(jié)點A，按照傳統(tǒng)的做法，未知節(jié)點D將使用錨節(jié)點A的平均跳距來計算距離，通過這種方式計算出節(jié)點B、D之間的距離為[6.43×2=12.86]，誤差為[20-12.86=7.14];同樣根據(jù)錨節(jié)點A的平均跳距計算出節(jié)點C、D之間的估計距離為[6.43×3=19.29]，誤差為[25-19.29=5.71]。

本文改進的做法中，未知節(jié)點D在網(wǎng)絡中尋找距離其累積誤差最小的錨節(jié)點。根據(jù)前面的計算數(shù)據(jù)可得，錨節(jié)點A到未知節(jié)點D的累計誤差為[1.63×1=1.63];錨節(jié)點B到未知節(jié)點D的累積誤差為[0.03×2=0.06];錨節(jié)點C到未知節(jié)點D的累積誤差為[1.68×3=5.04]。顯然，錨節(jié)點B與未知節(jié)點D之間有著最小的累積誤差，因此，未知節(jié)點將獲取B的平均跳距來計算距離，得出 B、D之間的估計距離為[8.38×2=16.76]，誤差為[20-16.76=3.24]; C、D之間的距離為[8.38×3=25.14]，誤差為[25.14-25=0.14]。對比發(fā)現(xiàn)，改進的做法明顯地降低了計算距離時所產(chǎn)生的誤差。

3.3 改進算法的具體步驟

Step 1：計算錨節(jié)點的坐標并以不同的通信半徑向網(wǎng)絡中廣播它們的位置，鄰居節(jié)點接收并轉發(fā)跳數(shù)信息。這一過程結束后，所有傳感器節(jié)點都得到了節(jié)點間可以進行通信的最小跳數(shù)值。

Step 2：改進的距離估計

1） 假設錨節(jié)點[i]和[j]是定位區(qū)域中的任意兩個錨節(jié)點，通過前面的方法可以計算出錨節(jié)點[i]的平均跳距為[HopSizei]，錨節(jié)點[i]與錨節(jié)點[j]之間的跳數(shù)為[hopij]，錨節(jié)點[i]，[j]的坐標為[xi，yi]，[xj，yj]。

2） 錨節(jié)點[i]，[j]之間的估計距離為：

[dij=HopSizei×hopij] （11）

3） 錨節(jié)點[i]，[j]之間的距離誤差為：

[Δdij=dij-xi-xj2+yi-yj2] （12）

4） 錨節(jié)點[i]的平均跳距誤差為：

[averHopErri=j≠iΔdijj≠ihopij] （13）

5） 未知節(jié)點到錨節(jié)點的誤差累計為：

[totalHopErrui=averHopErri×hopui] （14）

其中[hopui]表示未知節(jié)點[u]到錨節(jié)點[i]的跳數(shù)。

6） 計算未知節(jié)點與錨節(jié)點之間的距離：

[dui=HopSizeminErri×hopui] （15）

其中[HopSizeminErri]表示到未知節(jié)點[u]累計誤差最小的錨節(jié)點平均跳距。

Step 3：計算未知節(jié)點位置

根據(jù)Step 2中的錨節(jié)點與未知節(jié)點間的距離，使用最小二乘法得出未知節(jié)點的坐標。

4 仿真結果分析

使用MATLAB對本文算法與原始DV-Hop算法、文獻[5]算法、文獻[6]算法和文獻[7]算法進行比較。仿真環(huán)境為[100m×100m]的方形區(qū)域內(nèi)隨機分布著WSN節(jié)點，在相同網(wǎng)絡條件下分析定位誤差，實驗結果取仿真100次的平均值。

對定位的結果采用相對定位誤差[Er]進行處理：

[Er=i=1Nxi-x′i2+yi-y′i2N×R] （16）

式中：[xi，yi]表示未知節(jié)點的實際位置，[x′i，y′i]表示通過改進算法得出的未知節(jié)點的位置，[N]表示未知節(jié)點個數(shù)。

圖4所示為當錨節(jié)點個數(shù)增加時各算法定位誤差的變化。固定通信半徑[R=30m]，未知節(jié)點的個數(shù)等于200不變，錨節(jié)點個數(shù)從20到80個不斷遞增。從圖中可得，增加錨節(jié)點的個數(shù)，各算法的定位誤差都在降低。本文改進的算法相較于原始DV-Hop算法在定位精度上有較大幅度的提升，與其他改進的算法相比也有更優(yōu)的表現(xiàn)。

圖5展示了未知節(jié)點個數(shù)增加時各算法定位誤差的變化。定位時固定節(jié)點的通信半徑[R=30m]，錨節(jié)點個數(shù)為30，未知節(jié)點個數(shù)從100到300不斷遞增。從圖中可以看出，當未知節(jié)點的個數(shù)小于150時，本文算法與文獻[5]和文獻[6]的效果很接近，但是隨著未知節(jié)點個數(shù)的增加，本文算法相較于其他算法的優(yōu)勢逐漸顯現(xiàn)出來。

圖6為相對定位誤差隨定位區(qū)域面積的變化。固定300個未知節(jié)點，50個錨節(jié)點，通信半徑為30m，定位區(qū)域為[100m2?200m2]。可以看出當定位區(qū)域面積增大時各個算法的定位誤差都在顯著增加，但是本文改進的算法整體保持最優(yōu)的定位效果。

5 結論

本文針對DV-Hop算法的誤差累計的問題提出了一種改進方案。改進的方案從誤差產(chǎn)生的源頭出發(fā)來降低誤差的擴散，在錨節(jié)點向網(wǎng)絡中廣播信息時使用多個通信半徑來減少算法的初始誤差，在未知節(jié)點的跳距選擇階段使得未知節(jié)點選擇累計誤差最小的跳距使用，減少了誤差的累計。將改進的算法在錨節(jié)點數(shù)、未知節(jié)點數(shù)以及定位區(qū)域面積變化的WSN環(huán)境下通過MATLAB做了仿真實驗。對比發(fā)現(xiàn)，本文提出的改進對比傳統(tǒng)DV-Hop算法在定位性能上有了明顯的提升，與相關的改進算法比較也有更優(yōu)的定位效果。如何進一步減小定位過程中的累計誤差，提高節(jié)點的定位準確度，是后續(xù)研究的重點。

參考文獻：

[1] Mehannaoui R，Mouss K N.A study with simulation of range free localization techniques in wireless sensors networks[C]//2019 International Conference on Advanced Electrical Engineering （ICAEE）. Algeria.IEEE，2019：1-4.

[2] WangJ，Hou A Q，Tu Y F，etal.An improved DV-hop localization algorithm Based on selected anchors[J].Computers，Materials & Continua，2020，65（1）：977-991.

[3] 呂敬祥，龍滿生，尹凱.基于加權最小二乘優(yōu)化的DV-HOP定位算法[J].傳感技術學報，2020，33（3）：450-455.

[4] 仇瑩，倪曉軍.基于牛頓迭代法的DV-Hop改進定位算法[J].計算機時代，2020（9）：29-33.

[5] Kanwar V，Kumar A.DV-Hop-based range-free localization algorithm for wireless sensor network using runner-root optimization[J].The Journal of Supercomputing，2021，77（3）：3044-3061.

[6] 周濤，蔣占軍，路宇挺，等.基于粒子群的DV_Hop算法優(yōu)化[J].計算機應用與軟件，2020，37（3）：138-143.

[7] 趙芝璞，吳棟，王艷，等.基于平均跳距和位置優(yōu)化的改進DV-Hop定位算法[J].系統(tǒng)仿真學報，2016，28（6）：1273-1280.

[8] 檀爽，毛永毅.基于最優(yōu)跳距和LevyPSO算法的DV_Hop定位算法[J].傳感技術學報，2018，31（6）：927-931.

[9] Niculescu D，NathB.Ad hoc positioning system（APS）[C]//GlobalTelecommunications Conference，San Antonio，TX：IEEE，2001：2926-2931.

[10] Kumar S，Lobiyal D K.Novel DV-Hop localization algorithm for wireless sensor networks[J].TelecommunicationSystems，2017，64（3）：509-524.

【通聯(lián)編輯：代影】