無線傳感器網(wǎng)絡(luò)的定位改進算法

雷景生，郝陽陽，郝 偉

(1.上海電力學(xué)院 電子與信息工程學(xué)院，上海 200090;2.63870部隊 測試站電測兼容測試室，陜西 華陰 714200)

無線傳感器網(wǎng)絡(luò)是一種分布式的自組織網(wǎng)絡(luò).在無線傳感器網(wǎng)絡(luò)絕大多數(shù)的應(yīng)用中，節(jié)點的位置信息和感知信息同等重要，沒有位置信息的感知數(shù)據(jù)是沒有實際意義的.傳感器節(jié)點自身的正確定位使待定位事件位置信息得到保障，也就是說，在傳感器節(jié)點自身正確定位的前提下，才可以定位待定位節(jié)點事件的實際位置.因此，節(jié)點的有效定位成為無線傳感器網(wǎng)絡(luò)應(yīng)用需要考慮的重要因素之一.

目前，國內(nèi)外已經(jīng)提出了很多優(yōu)化傳感器網(wǎng)絡(luò)節(jié)點定位算法.DV-Hop算法是通過一個錨節(jié)點到待定位節(jié)點的最小跳數(shù)乘以平均跳距估計待定位節(jié)點和錨節(jié)點之間的距離.然而節(jié)點分布不均，相鄰節(jié)點之間的距離實際差異不能真正反映平均跳距離，甚至有一些實際的距離，相鄰節(jié)點與平均跳距相差很大.[1]所以當(dāng)節(jié)點分布不均勻時，DV-Hop算法的測距誤差較大，從而使定位精度受到影響.而且針對測距誤差已經(jīng)有了很多的改進方法，[2-3]雖然誤差有所降低，[4]但都不是很理想.因此，本文在原有DV-Hop算法的基礎(chǔ)上進行加權(quán)改進，提出了一種新的誤差較小的節(jié)點精確定位算法.

1 經(jīng)典DV-Hop算法分析

DV-Hop定位算法包括3個過程.

第一步 通過典型的距離矢量交換協(xié)議，網(wǎng)絡(luò)中的每個參考節(jié)點向鄰居節(jié)點傳播自身位置信息的分組，使得網(wǎng)絡(luò)中的所有節(jié)點獲得距離參考節(jié)點的最小跳數(shù)信息.然后對跳數(shù)值加1，并轉(zhuǎn)發(fā)到鄰居節(jié)點.通過此方法可以得到網(wǎng)絡(luò)中每個錨節(jié)點的最小跳數(shù).

第二步 利用其他參考節(jié)之間的最小跳數(shù)和位置信息，讓每個參考節(jié)點求出平均跳距，然后將平均跳距當(dāng)作校正值傳播至網(wǎng)絡(luò).當(dāng)未知節(jié)點收到校正值后，以跳數(shù)為根據(jù)可以計算出其與參考節(jié)點之間的距離.

利用其他參考節(jié)點之間的最小跳數(shù)和位置信息，使每一個參考節(jié)點得到平均跳距，然后將平均跳距的平均傳播作為網(wǎng)絡(luò)的校正值，再對跳數(shù)進行校正，每個節(jié)點根據(jù)參考節(jié)點之間的距離進行計算.通過第一步中的校正值，利用式(1)來估算:

式中:(xi，yi)——第i個節(jié)點的坐標;

(xi，yi)——第j個節(jié)點坐標;

hij——第i個節(jié)點至第j個節(jié)點的跳數(shù).

DV-Hop 的模型如圖 1 所示.例如，Q1，Q2，Q3分別是信標節(jié)點，Q1到 Q2的實際距離S12=24，Q1到p的實際距離為13，Q2到p的實際距離為11，Q1與Q2之間跳數(shù)Hops12=5跳;Q2到Q3的距離S23=16，其間的跳數(shù)Hops23=3跳.根據(jù) DVHop算法，得出平均跳距Hopsize=(S12+S23)/(Hops12+Hops23)=5.再根據(jù)Q1和Q2到未知節(jié)點p的跳數(shù)分別為2跳和3跳，得到未知節(jié)點p到信標節(jié)點Q1和Q2的距離分別為d1=10，d2=15.測出的結(jié)果與實際結(jié)果相差較大，造成誤差的原因是節(jié)點分布不均勻.即如圖1，在算法中，Q1僅用了2跳到達未知節(jié)點p.但在實際中，因為節(jié)點分布不均勻而并不是2跳，所以導(dǎo)致測試出來的結(jié)果有差異.

圖1 DV-Hop算法模型

當(dāng)計算完與一個信標點無關(guān)的信標節(jié)點每跳的平均距離后，再將鄰居節(jié)點廣播的消息發(fā)至分組中，其中包含了周圍相鄰節(jié)點先得到的各信標節(jié)點的最新信息.[5]在無線傳感器網(wǎng)絡(luò)中，位置信息以傳播的形式發(fā)散，當(dāng)網(wǎng)絡(luò)節(jié)點收到位置信息時將與原來的位置信息進行比較，若收到的位置信息與原來的位置信息不同，就忽略原來的位置信息，將剛收到的位置信息進行儲存，這樣就可以保證節(jié)點只儲存一條最新的位置信息.待定位節(jié)點收到信標節(jié)點每段的平均距離，再由式(2)計算可得到待定位節(jié)點到信標節(jié)點之間的距離

式中:hops——待定位節(jié)點到錨節(jié)點的最小跳數(shù).

第三步 如果要獲得與3個以上參考節(jié)點的距離時，可以通過最大似然估計法和最小二乘法來計算待定位節(jié)點的位置.

在DV-Hop定位算法中，將跳數(shù)的距離與平均每段的跳距作為距離的估算值，因此DV-Hop的定位精度很大程度上取決于平均跳距.如果要將誤差保持在合理的估算范圍內(nèi)，則需要無線傳感器網(wǎng)絡(luò)中的節(jié)點分布均勻、密集.但在實際的網(wǎng)絡(luò)中，節(jié)點較少且分布離散，這樣很容易造成迭代誤差.而且隨著跳數(shù)的增加，誤差將會越變越大.

2 DV-Hop算法的改進

針對上述DV-Hop算法的誤差分析，下面提出利用mandist和dist分別加權(quán)最小二乘法.

在極大似然估計法的定位過程中，一般步驟為:已知信標節(jié)點 1，2，3，4，…，n 的坐標分別是(x1，y1)，(x2，y2)，(x3，y3)，…，(xn，yn)，待定位節(jié)點C的坐標是(x，y).則由空間坐標計算可知:

式(3)也可以表示為:

式中:

對于方程(4)，由標準的最小均方差的估計法可得到位置節(jié)點坐標為:

在大型網(wǎng)絡(luò)中，位置估計誤差較大.為了解決迭代誤差的問題，可以采用加權(quán)最小二乘估計方法，它根據(jù)每個信標節(jié)點上的最小二乘估計的位置精度定位不同的加權(quán)因子來提高定位精度.[6]在實踐中，加權(quán)系數(shù)的誤差為協(xié)方差.

在實際應(yīng)用中可知，誤差的協(xié)方差與加權(quán)系數(shù)有關(guān).理論上，要使估計誤差的方差最小，則加權(quán)矩陣w取測量值誤差方差矩陣的逆矩陣.然而在實際應(yīng)用中如何定義w還需要進一步研究.[7]一般情況下，隨著節(jié)點間的跳數(shù)變大時產(chǎn)生的誤差也變大，所以加權(quán)取值要小一點;而隨著節(jié)點間的跳數(shù)變小時產(chǎn)生的誤差會變小，所以加權(quán)取值需大一點.

因此，我們需要引入加權(quán)系數(shù)wi，其中wi=1/hi(hi為參加定位節(jié)點與未知節(jié)點C之間的最小跳數(shù)[8])，再利用曼哈頓距離加權(quán)函數(shù)mandist和歐氏距離加權(quán)函數(shù)dist分別加權(quán)wi，可以得出

經(jīng)過加權(quán)，利用最小二乘法可得位置節(jié)點的坐標為X=(CTWC)－1CTWD.

3 仿真與分析

為了對改進算法性能進行檢測，在Matlab平臺上分別將 DV-Hop，mandist，dist加權(quán)定位算法進行仿真，然后對產(chǎn)生的數(shù)據(jù)進行對比分析，主要從平均定位誤差方面對3種定位算法的性能進行評估.

3.1 訓(xùn)練次數(shù)變化分析

仿真網(wǎng)絡(luò)的參數(shù)設(shè)計如表1所示.初始節(jié)點分布如圖2所示.

表1 仿真參數(shù)設(shè)置

圖2 初始節(jié)點分布

由dist和mandist加權(quán)的最小二乘法定位算法與DV-Hop算法每次定位誤差的對比圖結(jié)果分別如圖3和圖4所示.由圖3和圖4可以得出，加權(quán)后的定位算法在每次的訓(xùn)練優(yōu)化后的平均定位誤差都分別低于DV-Hop算法.

圖3 dist加權(quán)和DV-Hop算法每次定位誤差對比

圖4 mandist加權(quán)和DV-Hop算法每次定位誤差對比

3種算法隨訓(xùn)練次數(shù)增加的平均定位誤差對比如圖5所示.

圖5 3種算法隨訓(xùn)練次數(shù)增加的平均定位誤差對比

當(dāng)仿真訓(xùn)練次數(shù)變化到10次時，與DV-Hop算法相比，兩種加權(quán)改進方法的平均定位誤差變化幅度較小，而DV-Hop算法則較大.相比DV-Hop算法，經(jīng)過mandist加權(quán)的最小二乘法的平均定位誤差降低了21.48%;dist加權(quán)的最小二乘法降低了22.49%.從10～100次，DV-Hop算法平均定位誤差變化幅度比較大，且在29～50次中呈現(xiàn)出增加趨勢;mandist加權(quán)的最小二乘法的平均定位誤差從30 次開始保持在33.751 4 ～35.655 0，變化幅度比較小，比較穩(wěn)定;dist加權(quán)的最小二乘法的平均定位誤差從30次開始保持在32.589 2～33.976 9，變化幅度也較小，而且誤差有降低的趨勢，最后基本保持不變，也比較穩(wěn)定.

3.2 錨節(jié)點數(shù)變化分析

隨著錨節(jié)點數(shù)增加而變化的3種定位算法的平均定位誤差對比如圖6所示.

圖6 隨錨節(jié)點增加時3種算法的平均定位誤差對比

由圖6可以看出，隨著信標節(jié)點的增加，DVHop算法平均定位誤差波動較大，并且誤差也較大，平均誤差為52.233 2;經(jīng)過 mandist加權(quán)的最小二乘法算法，誤差波動很小，平均誤差為36.180 9，比 DV-Hop 算法降低了 30.73%，且較為穩(wěn)定;經(jīng)過dist加權(quán)的最小二乘法，誤差波動也較小，平均誤差為34.754 4，比 DV-Hop算法降低了33.46%，很穩(wěn)定，并且誤差最小.由此可以看出，由mandist和 dist加權(quán)改進的 DV-Hop算法，兩者都非常穩(wěn)定，但dist加權(quán)算法更為理想.

4 結(jié)語

本文提出了兩種改進DV-Hop定位算法，即mandist加權(quán)最小二乘法和dist加權(quán)最小二乘法.這兩種算法對經(jīng)典DV-Hop算法存在誤差較大的平均跳距進行了最小跳數(shù)mandist和dist加權(quán)處理，使得改進后的DV-Hop算法能更加有效地對平均每跳距離進行估計.由仿真結(jié)果可以看出，與經(jīng)典的DV-Hop算法相比，本文提出的兩種改進算法的平均定位誤差有所降低，而且定位精度更為穩(wěn)定.

[1]許秀蘭.無線傳感器網(wǎng)絡(luò)距離無關(guān)定位算法研究[J].計算機與現(xiàn)代化，2009，4(10):6-9.

[2]張松濤，蔣洪波，唐振華，等.無線傳感器網(wǎng)絡(luò)中一種精細距離控制定位算法[J].計算機科學(xué)，2010(4):80-83.

[3]謝曉松，程良倫.傳感器網(wǎng)絡(luò)基于移動信標改進的DV-Hop定位算法[J].計算機應(yīng)用與軟件，2011(4):33-36.

[4]李冰，李聰.基于移動代理的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].計算機時代，2010(10):10-13.

[5]方海濤，雷菁，胡昆明，等.基于 RSSI修正的改進 DV-Hop測距算法[J].通信技術(shù)，2012，45(2):16-18.

[6]王建剛，王福豹，段渭軍.加權(quán)最小二乘估計在無線傳感器網(wǎng)絡(luò)定位中的應(yīng)用[J].計算機應(yīng)用研究，2006(9):41-43.

[7]梁銀.傳感器網(wǎng)絡(luò)中的數(shù)據(jù)查詢處理[J].計算機應(yīng)用與軟件，2008，25(5):201-202.

[8]楊軍.無線傳感網(wǎng)絡(luò)節(jié)點定位算法綜述[J].儀器儀表標準化與計量，2012(1):38-41.