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

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

基于RSSI技術(shù)的DV-Hop算法優(yōu)化

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

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

一、DV-Hop算法

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

二、RSSI測距技術(shù)

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

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

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

三、改進算法方案

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

圖1 節(jié)點路徑示意

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

（1）首先根據(jù)是否為信標節(jié)點，將節(jié)點標識table設(shè)為1或0，然后信標節(jié)點在網(wǎng)絡(luò)中廣播帶有節(jié)點標識符的數(shù)據(jù)包，其他節(jié)點接收相鄰節(jié)點的數(shù)據(jù)包；

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

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

具體流程如圖2所示：

圖2 改進算法流程

四、仿真結(jié)果分析

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

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

圖3 仿真結(jié)果對比

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

在穩(wěn)定性方面可以從定位精度的統(tǒng)計方差方面考慮，改進后的DV-Hop算法在信標節(jié)點比例為0.08時，定位精度的統(tǒng)計方差為0.0544，而傳統(tǒng)的DV-Hop算法方差為0.0972，因此改進后的DVHop算法比原DV-Hop算法的穩(wěn)定性略優(yōu)。

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

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

五、結(jié)論

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