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

鄭州大學(xué)信息工程學(xué)院 孔 川 邢慶翔

中國人民解放軍72433部隊(duì) 徐宣軍

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

鄭州大學(xué)信息工程學(xué)院 孔 川 邢慶翔

中國人民解放軍72433部隊(duì) 徐宣軍

一、DV-Hop算法

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

二、RSSI測距技術(shù)

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

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

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

三、改進(jìn)算法方案

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

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

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

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

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

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

具體流程如圖2所示：

圖2 改進(jìn)算法流程

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

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

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

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

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

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

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

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

五、結(jié)論

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