DV-Hop 定位算法改進方法研究?

王 勇 趙屹立

（江蘇海洋大學海洋技術與測繪學院 連云港 222005）

1 引言

多年來，研究人員已經對節點定位問題提出了各種解決方案。部署過程中的每個傳感器節點的位置通常由大量空間分布的傳感器節點組成［1］。傳感器節點隨著時間的推移，他們的位置可能會改變［2］。因此，自動計算來確定傳感器節點的位置成為優先選擇。全球定位系統可用于準確定位，然而，它對系統硬件的要求較高，并且需要在一個昂貴的成本和功率消耗下解決定位問題［3］。所以，尋找有效的無線網絡傳感器定位算法成為迫切需要［4］。

DV-Hop 算法是為了避免對節點間的距離直接進行測量而提出的一種基于距離矢量路由（根據目的地遠近決定最佳路徑）的非測距定位算法［5］。然而DV-Hop 定位算法也存在缺點，本文就利用MIN-MAX 與最小二乘法相結合的方法對DV-Hop定位算法進行改進［6］。

2 DV-Hop算法的缺點

1）在傳感器網絡體系中，會存在一些bad 節點。

2）如圖1 所示，節點N 可以被稱為節點的位置是不唯一的，所以稱該節點為bad節點。

圖1 第1類bad節點的示意圖

3）如圖2所示，節點N1只存在2個節點。不能確定E和F的位置，所以稱該節點為bad節點。

4）如圖3 所示，bad 節點是一個節點組。并且在節點組中沒有已知的節點，該組可以繞著已知的節點坐標旋轉，所以這個節點組中的所有節點都是bad節點。

圖3 第3類bad節點的示意圖

5）每一個傳感器節點和節點之間的距離的跳躍是已知的，與已知的節點來表示每個跳的平均距離。

6）可對該區域進行監測的范圍比較小，測量節點和已知節點的接觸，必須通過中間節點才能接觸到。

3 DV-Hop算法的改進

傳統的三邊測量法計算節點的坐標會產生一些誤差。MIN-MAX 算法［6］減少了浮點運算量，使計算的成本變得更小。定位精度主要由已知節點數確定，增加已知節點的數目，勢必會導致成本的增加，也會增加功率消耗［7］。因此，采用MIN-MAX和最小二乘法［8］相結合的方法來取代三邊測量法。

l）MIN-MAX算法

MIN-MAX算法出于協調自由分布的優化算法出現的問題，MIN-MAX 算法通過一個新的參數估計分布算法?？紤]到用一種分布式的方法來解決這樣的問題，提出了一種基于梯度的算法。該算法有兩個顯著的特點：

提出了一種分布式函數算法，使用Bregman距離。

2）提供了一種可以替代的分布式原始-對偶算法，也使用Bregman距離。

該算法的缺點是解決一類極小極大的能力分布式問題目前還沒有具體的算法。但能夠基本解決分布式網絡結構所遇到的問題。因此，該算法可以同時解決網絡定位問題。MIN-MAX算法示意圖如圖4所示。

圖4 MIN-MAX算法示意圖

已知節點（xs，ys）的范圍由［（xs-ks），（ys-ks）］*［（xs+ks），（ys+ks）］得到。交集范圍可由式（1）求解出：

2）最小加權二乘法

用待測量節點到已知節點的長度估計值構造的方程ts（x），然后用式（3），求出待測節點的估計坐標［9］：

若所有的距離估計是已知的，通過構造值的加權系數ws，最小加權二乘法的估計值為

若未知節點的坐標設為（x，y），已知節點的坐標設為（xs，ys），度量的長度設為ks，則殘差方程的表達式為

ts（x，y）為非線性函數，求解ts（x，y）的值，用非線性最優化來處理，求解ts（x，y）的表達式如下：

將式（6）減去式（7），得到有以下方程：

最終整理為

設有以下方程組成立：

線性處理完后，最小二乘的結果用矩陣可表示成：

最小加權二乘法的估算坐標為

只有一個對稱正定矩陣可以被確定為最小方差無偏估計。在該情況下，平均誤差的估計值是最小的。

在這個階段，另已知的節點的權重是1，被測量的節點的值是在0.1的基礎上，逐漸增加。

3）定位過程

過程1：這個過程是一個粗略的估計的位置。采用MIN-MAX 算法，未知節點能夠通過其位置和通信模型的優點解決未知節點的距離，根據式（3）和式（4），可以估算出未知節點的坐標近似值［10］。

過程2：隨著周期數的增加，未知節點的權重也在增加，節點的值逐漸接近于節點的權重［10］。一旦未知節點的權重大于1，節點坐標就非常接近。當所有的未知節點被執行時，所有的未知節點就會被定位，算法終止［11］。

4 DV-Hop算法仿真結果與分析

根據無線傳感器網絡的特點對參數進行設置［11］：BorderLength：邊長；BeaconAmount：節點數；Sxy：存儲節點的序號；Beacon：點坐標矩陣；UN：未知節點坐標矩陣；Distance：未知節點到信標節點距離矩陣；H：節點間初始跳數矩陣；X：節點估計坐標初始矩陣，X=［x，y］；R：節點的通信距離［12］。

每個節點的誤差由未知節點的位置和節點位置真值之間的距離表示［13］。算法平均誤差公式為

選擇方案如表1所示。

表1 定位方案

通過修改方案1 的參數，這樣就可以得到一個與方案2和3對比。對比上述結果，得到如下關系：error 和borderlength 為正比例關系；和nodeamount反比關系；與beaconamount 反比關系；與R 成正比關系［14］。

從上面的比較中，我們找出了一個最佳的方案3。此時Error=16.74。仿真結果如圖5、圖6。

圖5 方案3網絡節點分布

圖6 方案3未知節點的誤差

5 結語

本文重點介紹了DV-Hop 定位算法存在節點位置不明確的缺點，提出了以下改進：由于MIN-MAX算法能夠協調自由分布的優化算法出現的問題，所以采用MIN-MAX 算法和最小加權二乘法相結合的方法替代三邊測量法。通過在仿真平臺對算法進行仿真實驗，該算法平均定位誤差Error 為16.74，表明該改進算法可以提高定位精度。