基于彈簧系數的無線傳感器網絡定位算法

2019-06-05 06:20:36朱慧勇單志龍

傳感器與微系統 2019年6期

朱慧勇, 單志龍

(1.西安鐵路職業技術學院牽引動力學院,陜西西安 710026；2.華南師范大學計算機學院,廣東廣州 510631)

0 引言

在無線傳感器網絡[1]中,如何用少量錨節點的位置信息來定位大量未知節點的位置是無線傳感器網絡的重點技術之一。距離矢量跳(distance vector hop,DV-Hop)算法[2]對錨節點數量要求少,算法簡單,滿足無線傳感器網絡部署低成本、節能高效的要求,成為了眾多基于非測距定位算法中的研究熱點。在DV-Hop算法中,用錨節點之間的信息來計算平均跳距,但得到的平均跳距有較大誤差；用節點之間的最小跳數來表示兩個節點之間的關系,沒有細化；用平均跳距與最小跳數的乘積來表示距離,沒有更為精確的表示節點之間的估計距離。

針對這些問題,已有的眾多DV-Hop改進算法主要是采用加權或者優選錨節點的方法來提高精度。文獻[3]使用接收信號強度指示(received signal strength indication,RSSI)確定節點之間的分數跳數,得到修正后的平均跳距,采用無約束優化方法進行定位計算。文獻[4]以基于加權誤差修正的信標節點平均跳距之和為平均跳距,并采用改進的最小二乘法對累積定位誤差進行處理。文獻[5]利用RSSI測距技術得到相鄰節點之間的距離,進行輔助定位,并利用未知節點的質心坐標對自己的初始定位結果進行修正,然后利用修正后的坐標重新定位未知節點。上述改進算法主要都是從局部進行改進,雖然得到了一些好的結果,但都沒有從全局進行考慮。文獻[6]通過篩選參與錨節點平均跳距計算的錨節點減小引入誤差,并對其進行加權處理以提高精度。文獻[7]根據不同平均跳距處的RSSI值,選取最大平均跳距、最小平均跳距處、通信半徑處的RSSI值,求出比例因子,再利用該比例因子求出加權系數來修正每一跳數。文獻[8]利用 RSSI 測距來確定與信標節點距離較近的未知節點的位置,將其升級為信標節點,從而增加信標節點的數目；在計算未知節點坐標時,采用自由搜索的算法代替誤差較大的三邊測量法。

本文提出的基于彈簧系數和RSSI的DV-Hop改進算法(spring coefficient and RSSI DV-Hop,SCRDH)算法將節點與錨節點間最短路徑抽象成彈簧模型,然后利用彈簧模型改進了DV-Hop全網平均跳距和節點之間最小跳數的取值方法,并通過增加全網彈簧系數來提高定位精度。

1 SCRDH算法

本文從全局出發,將節點與錨節點間最短路徑抽象成彈簧模型,利用錨節點之間的彈簧模型建立全網的平均彈簧系數,并將彈簧系數應用到全網中進行定位。

1.1 彈簧模型

圖1 錨節點A與錨節點B的最短路徑

(1)

1.2 SCRDH定位算法

針對DV-Hop算法平均跳距、最小跳數和估計距離3個方面的問題,對提出的SCRDH算法進行改進。

1.2.1 計算全網的平均跳距

為了更方便地估計全網的平均跳距,將全網距離劃分為5個等級[9],分別為0.2R,0.4R,0.6R,0.8R,R,其中,R為傳輸半徑。先分別求出節點之間距離為0.2R,0.4R,0.6R,0.8R時,節點收到信號的功率值p1,p2,p3,p4。當節點收到其他節點信號的功率p時,與p1,p2,p3,p4進行比較,得到節點之間的等級距離

(2)

當所有節點都知道其與鄰居節點的距離d時,統計5個等級的個數,做出等級分布如表1。

表1 距離d等級分布

其中,Pt是第t等級的個數與全部等級個數的比值。則全網的平均跳距可表示為

(3)

節點A收到它的鄰居節點B發送的信息后,將功率轉化為等級距離,并且按格式(節點B的標示符,距離等級dBA)將信息存儲下來,節點A的鄰居節點有可能不止節點B一個,同樣,節點A也把其它的鄰居節點的信息存儲下來。當所有節點都把自己的鄰居節點存儲下來后,并且匯總給匯聚節點,匯聚節點計算出全網的平均跳距。匯聚節點再將平均跳距再反饋給每個節點。

1.2.2 計算未知節點到錨節點的最小跳數

錨節點C按格式(錨節點C的標識符,坐標,跳數Hop)發送消息給鄰居節點D,節點D根據之前存儲的信息(錨節點C的標識符,距離等級dCD)與剛收到的信息進行處理,得到(錨節點C的標識符,坐標,Hop=Hop+dCD)信息,存儲并轉發給節點D的鄰居節點。重復以上步驟,直到所有節點都具有錨節點的位置信息和彼此間的最小跳數。廣播時,跳數Hop初始值為0,節點只保留與錨節點最小跳數的信息,其他消息拋棄掉,減少通信開銷。

1.2.3 計算全網的平均彈簧系數

(4)

式中Hopij為錨節點i和錨節點j的最小跳距,其求解方法同1.2.2節計算未知節點到錨節點的最小跳數。

由式(1),錨節點i和錨節點j之間的彈簧系數kij為

(5)

通過求平均值計算出錨節點i的平均彈簧系數

(6)

式中m為錨節點的個數。

根據每個錨節點的平均彈簧系數,匯總給匯聚節點,匯聚節點對其求均值作為全網的平均彈簧系數K反饋給全網的節點

(7)

1.2.4 計算未知節點的位置坐標

經過信息交換后,未知節點i存儲的信息包含有全網的平均跳距、全網的平均彈簧系數K和到錨節點的最小跳數Hopi,根據彈簧模型,未知節點到錨節點的估計距離為

(8)

當未知節點獲取3個或以上錨節點的估計距離后,根據三邊定位法或最小二乘法即可估計出未知節點位置。

2 仿真結果與分析

本文使用MATLAB對SCRDH算法和DV-Hop算法進行了仿真。仿真環境為100 m×100 m的區域,無線傳感器節點隨機分布在區域中。錨節點的個數為5個,通信半徑為20 m,節點總數為100個。為了抑制隨機分布產生的誤差,所得仿真結果均為相同參數下仿真100次的平均值。

2.1 錨節點個數

圖2為不同距離等級與不同錨節點數目對DV-Hop算法、SCRDH算法定位精度的影響。隨著錨節點個數的增加,SCRDH算法和DV-Hop算法的定位精度都隨之提高。當錨節點達到15個時,定位精度的提高基本保持穩定。SCRDH算法的定位精度優于DV-Hop算法,當錨節點個數為25時,SCRDH算法按6個等級的定位精度比DV-Hop算法提高了15 %。按6個等級SCRDH算法使全網的平均跳距更精確一點,最小跳數更細化了,因此,SCRDH算法比DV-Hop算法更精確。

圖2 按不同等級劃分定位精度比較

2.2 通信半徑

圖3(a)為不同通信半徑對SCRDH算法與DV-Hop算法定位誤差的影響,其中錨節點數15個,節點總數為100個。節點通信半徑越大,DV-Hop算法與SCRDH算法的定位精度也就越高。當通信半徑為24 m時,二種算法的定位精度提高的幅度基本保持穩定。通信半徑增加,網絡節點的連通度增加,定位精度也就提高了。從圖中也可看出,SCRDH算法明顯優于DV-Hop算法。

圖3(b)為節點通信半徑對SCRDH算法定位精度的影響。節點通信半徑越大,SCRDH算法的定位精度也就越高。當通信半徑為25 m時,算法的定位精度提高的幅度最大。當錨節點個數為10以后,定位精度的提高幅度趨于漸緩。當錨節點個數為15時,SCRDH算法通信半徑20 m時的定位誤差為29 %,而SCRDH算法通信半徑30 m時的定位誤差為12 %。定位誤差12 %說明SCRDH算法是非常可行的。通信半徑增加,網絡節點的連通度增加,計算全網的平均跳距、最小跳數,更精確,定位精度更提高。