基于跳距加權的DV-hop定位算法改進

趙小平，馬嘉楠，饒 瑞，宮 婧

(南京郵電大學 理學院，江蘇 南京 210023)

0 引 言

隨著無線傳感網絡(WSN)的飛速發展，其在工業環境、智能交通、軍事等領域應用廣泛。在無線傳感網絡研究中，節點定位算法是一個至關重要的問題，同時也是一個技術難點。

節點定位算法，是根據已知坐標的錨節點(通過自身攜帶GPS定位)，對未知節點進行定位。節點定位算法可以分為基于測距和基于無測距的定位算法[1]，基于測距的定位算法，是根據硬件測量節點之間的距離，開銷較大，如RSSI、TOA、TDOA等；而基于非測距的定位算法，是通過間接的手段來獲取節點之間的距離，如Amorphous、APIT、DV-hop等。得到節點之間的距離后，利用最小二乘法、遺傳算法、蟻群算法等優化算法來求解，得到未知節點的坐標。研究定位算法，主要考慮定位精度、能耗開銷、硬件成本等。研究定位算法的改進目標就是通過更小的代價實現更高的定位精度。

文中重點研究DV-hop定位算法，通過對未知節點附近錨節點跳距進行加權得到未知節點到錨節點的跳距，權重由未知節點到信標節點的跳數，并結合信標節點跳距的可信度確定。信標節點可信度根據信標節點實際距離和通過算法求得的跳距乘以跳數得到的距離之間的誤差得到。最后對算法精度進行驗證。

1 經典DV-hop算法

DV-hop定位算法是一種分布式非測距算法[2]。算法受環境的影響較小，也不需要額外的硬件設備支持，所以適應于成本低、規模大、節點配置簡單的無線傳感網絡[3]。

1.1 算法描述

經典DV-hop算法非常類似于傳統網絡中的距離向量路由機制，從而可以將其大致分為三步[4]：

(1)信標節點進行信息廣播，計算未知節點與每個信標節點的最小跳數；

(2)計算未知節點與信標節點的實際跳距；

(3)根據求得的未知節點到信標節點的估計距離，計算未知節點自身坐標。

1.2 算法誤差分析

DV-hop是一種完全依靠網絡連通度來對未知節點進行定位的算法[5]，在定位的過程中，外部環境和定位算法本身都會產生一定的誤差。產生誤差的方面具體如下：

(1)鏡像誤差。

在定位過程中，由于用作未知節點定位的信標節點近似共線[6]，未知節點可能出現誤判，如圖1所示。

圖1 鏡像誤差分析圖

圖中，A、B、C為信標節點，i為未知節點，由于信標節點近似共線，導致誤判成為i'。這種現象稱為鏡像誤差現象，經典DV-hop未考慮這種誤差的影響。

(2)定位計算方法。

在求得未知節點與信標節點之間的距離之后，一般采用極大似然估計法或三邊測量法等估算算法來計算未知節點的坐標[7]。主要是因為算法簡單易實現，求得的結果都會有一定的誤差，并且容易造成一定范圍內的誤差積累。

(3)無法定位節點(不良節點)。

無線傳感網絡中的節點是隨機分布的，很容易造成分布不均[5]。如果未知節點周圍的信標節點數量小于3個，無法對其進行定位，從而產生了定位盲點。

(4)跳數誤差。

在節點跳數獲取階段，信標節點以通信半徑R廣播位置信息，收到該信息的節點均計為1跳。如圖2所示，A、B節點均在信標節點S通信范圍內,都能接收到信標節點的位置信息，并且跳數都為1跳，未知節點C在信標節點通信的邊緣，但是收不到信標節點廣播的信息，而是接收到節點B轉發來的信標節點的位置信息，所以未知節點C的跳數為2跳。A靠近信標節點，B、C位置接近，而A到信標節點的距離與B相等，是C到信標節點的一半，顯而易見，這樣誤差較大[8]。

圖2 跳數誤差分析圖

(5)平均跳距誤差。

當錨節點間的跳數嚴重偏離直線路徑時[9]，采用公式計算誤差較大，用來估計未知節點到錨節點之間的距離時誤差也較大。

2 基于跳距加權的改進DV-hop算法

由于經典DV-hop算法的誤差較大，于是考慮從跳距方面進行改進。文中通過對未知節點周圍信標節點的跳距進行加權，從而得到比較準確的跳距。影響一個錨節點對未知節點的重要性因素，主要分為錨節點到未知節點的距離和錨節點跳距的可信度。而錨節點到未知節點的距離可以用兩者之間的跳距來衡量，錨節點跳距的可信度可用錨節點之間真實距離與估算距離兩者的誤差來度量，兩者誤差越大，可信度越低。

2.1 信息廣播和跳數計算

信標節點通過洪范方式廣播自身的坐標信息[10]，設初始跳數為0。未知節點記錄收到每一個信標節點的最小跳數，同時忽略同一信標節點其他跳數較大的路徑，然后將跳數值加1，繼續轉發給鄰居節點，這樣每一未知節點可以得到信標節點的最小跳數。

2.2 信標節點跳距計算

設信標節點Sk的坐標為(xk,yk),它的鄰居節點Si(i=1,2,…,N)的坐標為(xi,yi)。每個信標節點根據獲得的到其他信標節點的坐標和到其的最小跳距[11]求得跳距，公式如下：

(1)

其中，hik為信標節點Si和Sk之間的最小跳數。

2.3 未知節點到錨節點的跳距

信標節點到未知節點的跳距越大，即相距越遠，信標節點對未知節點的貢獻越小。為了提高定位精度，應充分利用網絡中的信息，并賦予近距離錨節點較大的權重，故利用反距離加權處理平均每跳距離[12]，表示為：

(2)

其中，Hopij為錨節點Si和Sj之間的跳距。

2.4 信標節點跳距可信度

利用信標節點誤差來度量其跳距可信度[13]。首先，利用經典DV-hop算法求得的跳距來估算錨節點之間的距離；其次，與實際距離比較，求出誤差值；最后，利用誤差大小來確定跳距的權重。

(1)計算錨節點誤差。

利用經典DV-hop算法中第二步求得的跳距乘以最小跳數，求得估算距離，從而實際距離與估算距離之間的誤差為：

(3)

其中，Dij為錨節點Si和Sj之間的實際距離；Hopsizej為錨節點Sj的跳距；Hopij為錨節點Si和Sj之間的跳距。

(2)權重確定。

用誤差的倒數作為權重，并進行歸一化，如下：

(4)

(5)

其中，KHopi為距未知節點跳距小于k跳的錨節點。

2.5 計算最終平均跳距

結合信標節點可信度和信標節點離未知節點的跳距，確定最終權重，如下：

ωj=αγj+(1-α)βj

(6)

其中，α為系數，用來衡量信標節點可信度和信標節點與未知節點之間的跳距兩者的重要性。

未知節點使用距其k跳(經典DV-hop所求)的錨節點跳距并結合上述權重進行加權，作為最終的跳距，公式如下：

(7)

其中，HopSizej為未知節點Xi的修正跳距。

2.6 未知節點定位

利用得到的跳距乘以跳數得到節點之間的距離，結合最小二乘法[14]進行求解，得到未知節點的坐標。

首先，計算未知節點到錨節點的距離，利用未知節點到錨節點的最小跳數和信標節點的跳距，得到如下公式：

dij=reHopSize×hij

(8)

其中，dij為未知節點Xi到錨節點Sj的距離；hij為未知節點Xi到錨節點Sj的跳數。

然后，設未知節點坐標為(x,y),錨節點Sj的坐標為(xj,yj)，得到未知節點到信標節點之間的距離di。利用歐氏距離公式有：

(9)

把上式轉化為線性方程組，形式如下：

AX=b

(10)

從而解得未知節點X的坐標:

X=A+b=(ATA)-1ATb

(11)

其中：

(12)

(13)

3 仿真結果與分析

為了驗證基于跳距加權的改進DV-hop算法的性能，利用MATLAB對DV-hop算法和改進DV-hop算法進行對比，并用仿真數據進行分析。實驗中的參數設置如表1所示。

表1 仿真參數設置

仿真中，錨節點和未知節點隨機分布在1000m×1000m的區域內，信標節點和未知節點都是隨機生成的，在有些區域信標節點比較密集，有些地方信標節點數量較少，從而會導致一定的定位誤差，尤其在信標節點稀疏區域，誤差較大。

分析經典DV-hop算法和改進DV-hop算法的定位精度，得到的誤差圖如圖3和圖4所示。

圖3 經典DV-hop誤差圖

圖4 改進DV-hop誤差圖

由圖可知，改進DV-hop的每個未知節點的估計位置偏離真實位置要比經典算法小，從而表明改進DV-hop的精度要比經典DV-hop精度高。而且在信標節點較為密集的區域，誤差較??；而在信標節點較為稀疏的區域，定位誤差較大。下面從誤差值來考慮。定義平均誤差[15]，即所有未知節點的估計位置與真實位置的偏離之和除以通信半徑和未知節點數量，公式如下：

(14)

利用平均誤差公式，計算得到原始DV-hop和改進DV-hop定位算法10次實驗的平均誤差，并作圖進行對比，如圖5所示。

圖5 改進DV-hop和經典DV-hop的誤差對比

由圖可知，改進DV-hop的平均定位誤差明顯比經典DV-hop的低，并且改進定位算法的平均誤差相對比較穩定。因為改進的DV-hop算法考慮未知節點附近參考信標節點的可信度和信標節點到未知節點的跳距，這樣使離未知節點越遠的信標節點對其定位起的作用較小。同理信標節點的可信度越低，對未知節點定位時賦予其較小的權重。這樣使得未知節點得到的跳距更接近真實值，從而減小誤差。

4 結束語

對無線傳感網絡的節點定位進行了簡要分析，對DV-hop定位算法的原理和實現過程進行了詳細陳述，并就其定位誤差進行分析。利用加權的思想對DV-hop的跳距進行修正，提高了精度。最后通過仿真實驗對改進DV-hop和經典DV-hop進行對比，得出改進DV-hop的誤差有較大的優化。

[1] 申屠明.無線傳感器網絡定位算法研究[D].杭州:浙江大學,2007.

[2] 馬淑麗,趙建平.多通信半徑的無線傳感器網絡DV-Hop定位算法[J].傳感技術學報,2016,29(4):593-600.

[3] 向滿天，王 勝，楊友華.基于閾值機制與距離校正的WSN改進DV-Hop定位算法[J].傳感技術學報，2016,29(6):920-926.

[4] 劉 嘯,劉玉龍.一種改進的無線傳感器網絡節點定位算法[J].計算機技術與發展，2014，24(4):92-95.

[5] 李 冬.基于DV-Hop的無線傳感器網絡定位算法研究與改進[D].南京:南京理工大學,2013.

[6] LI Changyun,ZHAO Peizhe,ZENG Yu.Improved DV-Hop localization algorithm for wireless nodes in the smart grid[C]//26th Chinese control and decision conference.[s.l.]:IEEE,2014:4535-4540.

[7] 顧亦然，蔣璐璐.一種改進無線傳感器網絡的DV-Hop定位算法[J].計算機技術與發展，2012,22(12):109-112.

[8] 潘琢金,劉文春,羅 振,等.無線傳感器網絡DV-Hop定位算法的改進[J].計算機工程與設計,2016,37(7):1701-1704.

[9] 王小輝，李圣普，呂海蓮.基于布谷鳥算法的WSN節點定位研究[J].計算機技術與發展，2014,24(12):208-211.

[10] ZHOU Gongqian,YANG Lujing,LIU Zhong.Wireless sensor network node localization based on error bound DV-Hop algorithm[C]//28th Chinese control and decision conference.[s.l.]:IEEE,2016：2390-2396.

[11] ZHANG Ying,ZHU Zhuling.A novel DV-Hop method for localization of network nodes[C]//Proceeding of the 35th Chinese control conference.[s.l.]:[s.n.],2016：8346-8351.

[12] 劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權DV-Hop的定位算法[J].傳感技術學報,2015,28(6):883-887.

[13] WANG Ying,FANG Zhiyi,CHEN Lin.A new type of weighted DV-Hop algorithm based on correction factor in WSNs[J].Journal of Communications，2014，9(9):699-705.

[14] ZHENG Jiuhu, QIAN Huanyan, WANG Lie.An improved DV-Hop positioning algorithm for wireless sensor network[C]//IEEE international conference on progress in information and computing.[s.l.]:IEEE,2015：492-497.

[15] 侯志偉,包理群,安麗霞.基于殘差加權的三維DV-Hop改進WSN定位算法[J].計算機應用與軟件,2016,33(1):112-115.