DV-Hop 定位算法改進(jìn)方法研究?

王 勇 趙屹立

（江蘇海洋大學(xué)海洋技術(shù)與測(cè)繪學(xué)院 連云港 222005）

1 引言

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

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

2 DV-Hop算法的缺點(diǎn)

1）在傳感器網(wǎng)絡(luò)體系中，會(huì)存在一些bad 節(jié)點(diǎn)。

2）如圖1 所示，節(jié)點(diǎn)N 可以被稱為節(jié)點(diǎn)的位置是不唯一的，所以稱該節(jié)點(diǎn)為bad節(jié)點(diǎn)。

圖1 第1類bad節(jié)點(diǎn)的示意圖

3）如圖2所示，節(jié)點(diǎn)N1只存在2個(gè)節(jié)點(diǎn)。不能確定E和F的位置，所以稱該節(jié)點(diǎn)為bad節(jié)點(diǎn)。

4）如圖3 所示，bad 節(jié)點(diǎn)是一個(gè)節(jié)點(diǎn)組。并且在節(jié)點(diǎn)組中沒有已知的節(jié)點(diǎn)，該組可以繞著已知的節(jié)點(diǎn)坐標(biāo)旋轉(zhuǎn)，所以這個(gè)節(jié)點(diǎn)組中的所有節(jié)點(diǎn)都是bad節(jié)點(diǎn)。

圖3 第3類bad節(jié)點(diǎn)的示意圖

5）每一個(gè)傳感器節(jié)點(diǎn)和節(jié)點(diǎn)之間的距離的跳躍是已知的，與已知的節(jié)點(diǎn)來表示每個(gè)跳的平均距離。

6）可對(duì)該區(qū)域進(jìn)行監(jiān)測(cè)的范圍比較小，測(cè)量節(jié)點(diǎn)和已知節(jié)點(diǎn)的接觸，必須通過中間節(jié)點(diǎn)才能接觸到。

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

傳統(tǒng)的三邊測(cè)量法計(jì)算節(jié)點(diǎn)的坐標(biāo)會(huì)產(chǎn)生一些誤差。MIN-MAX 算法［6］減少了浮點(diǎn)運(yùn)算量，使計(jì)算的成本變得更小。定位精度主要由已知節(jié)點(diǎn)數(shù)確定，增加已知節(jié)點(diǎn)的數(shù)目，勢(shì)必會(huì)導(dǎo)致成本的增加，也會(huì)增加功率消耗［7］。因此，采用MIN-MAX和最小二乘法［8］相結(jié)合的方法來取代三邊測(cè)量法。

l）MIN-MAX算法

MIN-MAX算法出于協(xié)調(diào)自由分布的優(yōu)化算法出現(xiàn)的問題，MIN-MAX 算法通過一個(gè)新的參數(shù)估計(jì)分布算法?？紤]到用一種分布式的方法來解決這樣的問題，提出了一種基于梯度的算法。該算法有兩個(gè)顯著的特點(diǎn)：

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

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

該算法的缺點(diǎn)是解決一類極小極大的能力分布式問題目前還沒有具體的算法。但能夠基本解決分布式網(wǎng)絡(luò)結(jié)構(gòu)所遇到的問題。因此，該算法可以同時(shí)解決網(wǎng)絡(luò)定位問題。MIN-MAX算法示意圖如圖4所示。

圖4 MIN-MAX算法示意圖

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

2）最小加權(quán)二乘法

用待測(cè)量節(jié)點(diǎn)到已知節(jié)點(diǎn)的長(zhǎng)度估計(jì)值構(gòu)造的方程ts（x），然后用式（3），求出待測(cè)節(jié)點(diǎn)的估計(jì)坐標(biāo)［9］：

若所有的距離估計(jì)是已知的，通過構(gòu)造值的加權(quán)系數(shù)ws，最小加權(quán)二乘法的估計(jì)值為

若未知節(jié)點(diǎn)的坐標(biāo)設(shè)為（x，y），已知節(jié)點(diǎn)的坐標(biāo)設(shè)為（xs，ys），度量的長(zhǎng)度設(shè)為ks，則殘差方程的表達(dá)式為

ts（x，y）為非線性函數(shù)，求解ts（x，y）的值，用非線性最優(yōu)化來處理，求解ts（x，y）的表達(dá)式如下：

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

最終整理為

設(shè)有以下方程組成立：

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

最小加權(quán)二乘法的估算坐標(biāo)為

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

在這個(gè)階段，另已知的節(jié)點(diǎn)的權(quán)重是1，被測(cè)量的節(jié)點(diǎn)的值是在0.1的基礎(chǔ)上，逐漸增加。

3）定位過程

過程1：這個(gè)過程是一個(gè)粗略的估計(jì)的位置。采用MIN-MAX 算法，未知節(jié)點(diǎn)能夠通過其位置和通信模型的優(yōu)點(diǎn)解決未知節(jié)點(diǎn)的距離，根據(jù)式（3）和式（4），可以估算出未知節(jié)點(diǎn)的坐標(biāo)近似值［10］。

過程2：隨著周期數(shù)的增加，未知節(jié)點(diǎn)的權(quán)重也在增加，節(jié)點(diǎn)的值逐漸接近于節(jié)點(diǎn)的權(quán)重［10］。一旦未知節(jié)點(diǎn)的權(quán)重大于1，節(jié)點(diǎn)坐標(biāo)就非常接近。當(dāng)所有的未知節(jié)點(diǎn)被執(zhí)行時(shí)，所有的未知節(jié)點(diǎn)就會(huì)被定位，算法終止［11］。

4 DV-Hop算法仿真結(jié)果與分析

根據(jù)無線傳感器網(wǎng)絡(luò)的特點(diǎn)對(duì)參數(shù)進(jìn)行設(shè)置［11］：BorderLength：邊長(zhǎng)；BeaconAmount：節(jié)點(diǎn)數(shù)；Sxy：存儲(chǔ)節(jié)點(diǎn)的序號(hào)；Beacon：點(diǎn)坐標(biāo)矩陣；UN：未知節(jié)點(diǎn)坐標(biāo)矩陣；Distance：未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)距離矩陣；H：節(jié)點(diǎn)間初始跳數(shù)矩陣；X：節(jié)點(diǎn)估計(jì)坐標(biāo)初始矩陣，X=［x，y］；R：節(jié)點(diǎn)的通信距離［12］。

每個(gè)節(jié)點(diǎn)的誤差由未知節(jié)點(diǎn)的位置和節(jié)點(diǎn)位置真值之間的距離表示［13］。算法平均誤差公式為

選擇方案如表1所示。

表1 定位方案

通過修改方案1 的參數(shù)，這樣就可以得到一個(gè)與方案2和3對(duì)比。對(duì)比上述結(jié)果，得到如下關(guān)系：error 和borderlength 為正比例關(guān)系；和nodeamount反比關(guān)系；與beaconamount 反比關(guān)系；與R 成正比關(guān)系［14］。

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

圖5 方案3網(wǎng)絡(luò)節(jié)點(diǎn)分布

圖6 方案3未知節(jié)點(diǎn)的誤差

5 結(jié)語

本文重點(diǎn)介紹了DV-Hop 定位算法存在節(jié)點(diǎn)位置不明確的缺點(diǎn)，提出了以下改進(jìn)：由于MIN-MAX算法能夠協(xié)調(diào)自由分布的優(yōu)化算法出現(xiàn)的問題，所以采用MIN-MAX 算法和最小加權(quán)二乘法相結(jié)合的方法替代三邊測(cè)量法。通過在仿真平臺(tái)對(duì)算法進(jìn)行仿真實(shí)驗(yàn)，該算法平均定位誤差Error 為16.74，表明該改進(jìn)算法可以提高定位精度。