基于跳距優化的DV-Hop定位算法

侯華 曹俊俊 王曹 楊沛釗

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

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

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

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

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

1 概述

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

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

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

2 DV-Hop算法介紹與分析

2.1 DV-Hop算法介紹

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

第一階段：跳數估計

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

第二階段：距離計算

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

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

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

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

[dkj=HopSizei×hj] （2）

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

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

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

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

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

對式（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）計算出未知節點的坐標：

[X=ATA-1ATB] （7）

2.2 DV-Hop算法誤差分析

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

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

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

3 本文改進算法

3.1 錨節點通信半徑的選擇

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

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

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

3.2 未知節點跳距選擇

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

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

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

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

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

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

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

本文改進的做法中，未知節點D在網絡中尋找距離其累積誤差最小的錨節點。根據前面的計算數據可得，錨節點A到未知節點D的累計誤差為[1.63×1=1.63];錨節點B到未知節點D的累積誤差為[0.03×2=0.06];錨節點C到未知節點D的累積誤差為[1.68×3=5.04]。顯然，錨節點B與未知節點D之間有著最小的累積誤差，因此，未知節點將獲取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]。對比發現，改進的做法明顯地降低了計算距離時所產生的誤差。

3.3 改進算法的具體步驟

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

Step 2：改進的距離估計

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

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

[dij=HopSizei×hopij] （11）

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

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

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

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

5） 未知節點到錨節點的誤差累計為：

[totalHopErrui=averHopErri×hopui] （14）

其中[hopui]表示未知節點[u]到錨節點[i]的跳數。

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

[dui=HopSizeminErri×hopui] （15）

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

Step 3：計算未知節點位置

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

4 仿真結果分析

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

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

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

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

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

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

圖6為相對定位誤差隨定位區域面積的變化。固定300個未知節點，50個錨節點，通信半徑為30m，定位區域為[100m2?200m2]?？梢钥闯霎敹ㄎ粎^域面積增大時各個算法的定位誤差都在顯著增加，但是本文改進的算法整體保持最優的定位效果。

5 結論

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

參考文獻：

[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] 呂敬祥，龍滿生，尹凱.基于加權最小二乘優化的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算法優化[J].計算機應用與軟件，2020，37（3）：138-143.

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

[8] 檀爽，毛永毅.基于最優跳距和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.

【通聯編輯：代影】