王 勇 趙屹立

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

1 引言

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

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

2 DV-Hop算法的缺點

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

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

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

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

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

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

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

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

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

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

l）MIN-MAX算法

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

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

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

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

圖4 MIN-MAX算法示意圖

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

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

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

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

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

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

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

最終整理為

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

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

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

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

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

3）定位過程

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

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

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

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

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

選擇方案如表1所示。

表1 定位方案

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

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

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

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

5 結(jié)語

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