基于RSSI技術的DV-Hop算法優化

鄭州大學信息工程學院 孔 川 邢慶翔

中國人民解放軍72433部隊 徐宣軍

基于RSSI技術的DV-Hop算法優化

鄭州大學信息工程學院 孔 川 邢慶翔

中國人民解放軍72433部隊 徐宣軍

一、DV-Hop算法

DV-Hop算法是APS分布式定位系統中的一種。該算法的基本思想是將未知節點到信標節點之間的距離用網絡中節點平均每跳距離和到信標節點間的跳數乘積來標識，再使用極大似然估計法來獲得節點的位置信息。DV-Hop算法的定位過程可以分為以下3個階段：計算未知節點與每個信標節點的最小跳數；計算未知節點與信標節點的實際跳段距離，每個信標節點根據第1個階段中記錄的其他信標節點的位置信息和相距跳段數估算平均每跳的實際距離；當未知節點獲得與3個或更多錨節點的距離之后，利用極大似然估計法實現節點定位。

二、RSSI測距技術

RSSI接收信號強度指示器是一種利用信號強度衰減推測距離的測距技術。典型的定位系統有RADARD等。本文引入RSSI測距技術的目的，是為了計算未知節點到信標節點之間的通信距離。自由空間的無線電傳播路徑損耗模型由下式給出：

式中，d為發射端與接收端的距離（km），f為無線電傳播頻率（Mhz），n為路徑衰減因子，一般取值2～5。在實際的應用環境中，由于多徑、繞射、障礙物等因素的影響，無線電傳播路徑損耗與理論值相比有些變化，常采用對數常態分布模型。模型的數學表達式如下：

式中，PL(d)為經過距離d后的路徑損耗（dbm），d0為參考距離，Xσ是平均值為0的高斯分布隨機變數，其標準差一般為4～10，PL0是經過參考距離d0后的路徑損耗。由式（1）和式（2）可以得到接收端的信號強度表達式為：Pr(d)=Pt-PL(d)。其中，Pr(d)為接收信號強度（dbm），Pt的值為32.44（dbm）。

三、改進算法方案

1. DV-Hop算法的不足。在DV-Hop算法中，由于在實際網絡中信標節點到未知節點的距離往往不是直線路徑，使用DV-Hop算法會帶來較大的誤差。如圖1所示，設節點1為信標節點，信標節點的平均每跳距離為20m。對于未知節點4，由DV-Hop算法計算出，信標節點1到未知節點4的距離為60m。然而，這一估算距離遠大于實際兩點之間的距離，因為節點1到節點4并非是直線連接。

圖1 節點路徑示意

2. DV-Hop算法改進。為了減少估算距離與實際距離之間的誤差，改進算法利用RSSI技術估算出未知節點到信標節點一跳的距離。當整個網絡部署完之后，信標節點在網絡中廣播數據包，其他節點解析接收過來的數據包，并計算出兩節點之間的距離。一旦某個未知節點接收到3個或3個以上從不同信標節點發送的數據包時，就可利用極大似然估計法計算出自己的位置信息，然后將自己提升為信標節點，依次類推，直到所有節點計算出位置信息為止。改進后的算法分為多“輪”，每“輪”中根據網絡已有的信標節點計算出未知節點的坐標，如果一“輪”結束，所有未知節點并未估算出結果，則將已計算的未知節點提升為信標節點繼續估算未知節點坐標，直到所有節點估算出為止。算法過程如下所示：

（1）首先根據是否為信標節點，將節點標識table設為1或0，然后信標節點在網絡中廣播帶有節點標識符的數據包，其他節點接收相鄰節點的數據包；

（2）節點解析接收過來的數據包，分析獲得發送和接收信號的強度，由衰減模型計算出兩節點之間的距離；

（3）利用極大似然估計法計算出自己的位置。

具體流程如圖2所示：

圖2 改進算法流程

四、仿真結果分析

采用MATLAB對DV-Hop算法和改進的算法進行試驗仿真，并對結果進行分析。仿真環境假設如下：100個網絡節點隨機均勻分布在100×100的區域內，設置信標節點數為8，其中信標節點和未知節點隨機產生。節點的通信模型都是以自身為中心的圓形，通信半徑R為50，信標節點與未知節點的通信能力相同，且都為R。節點間具有對稱的通信能力，以及相同的發送和接收能力。為便于仿真，假設網絡中并未存在障礙物或干擾。

主要對傳統的DV-Hop和改進的DV-Hop在定位精度、穩定性、定位覆蓋率等方面進行比較。每種算法執行20次，并繪制出曲線圖。DV-Hop和改進的DV-Hop算法仿真結果如圖3所示。

圖3 仿真結果對比

從仿真圖中可以看出，DV-Hop 的定位精度平均值約為32.45%，而改進的DV-Hop算法的定位精度平均值為22.73%，因此改進后的算法定位精度較原算法有明顯的提高，而且發現在仿真過程中隨著信標節點密度的降低原DV-Hop算法定位誤差變大，但改進后的DV-Hop算法定位誤差變化并不大。另外從仿真中還可以看出，DV-Hop得出的未知節點的坐標容易重疊在一起，而改進后的算法定位出的節點則很少會重疊在一起。

在穩定性方面可以從定位精度的統計方差方面考慮，改進后的DV-Hop算法在信標節點比例為0.08時，定位精度的統計方差為0.0544，而傳統的DV-Hop算法方差為0.0972，因此改進后的DVHop算法比原DV-Hop算法的穩定性略優。

在定位覆蓋率上，改進后的算法在信標節點中的比例為0.08時，定位覆蓋率為98%，原DV-Hop的定位覆蓋率為92%，傳統的DVHop算法的覆蓋率達到98%時需信標節點的比例為0.25，因此改進后的DV-Hop算法在定位覆蓋率上有明顯的提高。

從以上仿真結果分析可以看出，改進后的DV-Hop算法在定位精度、穩定性以及定位覆蓋率上的效果都要好于傳統的DV-Hop算法。

五、結論

本文針對DV-Hop算法存在的不足，利用RSSI技術測量一跳節點之間的距離，并將已經定位出的未知節點提升為信標節點，經過仿真驗證，改進后的算法在定位精度上明顯優于DV-Hop，并且具有較好的穩定性。然而改進后的算法仍有一些不足，比如將定位出的未知節點提升為信標節點時容易產生誤差累積，因此該算法還有不少需要改進的地方。