基于RSSI修正的改進(jìn)DV-Hop測(cè)距算法

方海濤， 雷 菁， 胡昆明， 龔政輝

（①國(guó)防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410073；②空軍裝備研究院 通信導(dǎo)航與指揮自動(dòng)化研究所，北京 100843）

0 引言

在多數(shù)無(wú)線傳感器網(wǎng)絡(luò)（WSN，Wireless Sensor Networks）的應(yīng)用中，傳感器節(jié)點(diǎn)是隨機(jī)分布的,除了少數(shù)錨節(jié)點(diǎn)外,絕大多數(shù)節(jié)點(diǎn)的位置是未知的。如何獲取所有節(jié)點(diǎn)的位置信息是應(yīng)用無(wú)線傳感器網(wǎng)絡(luò)前首先需要解決的問(wèn)題[1]。DV-Hop算法是WSN節(jié)點(diǎn)定位中的一種經(jīng)典算法，其基本思想是將未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離用平均每跳距離和兩者之間跳數(shù)的乘積表示[2]。針對(duì)DV-Hop算法改進(jìn)的研究有很多，如文獻(xiàn)[3]是通過(guò)提高平均跳距的精度來(lái)提升定位精度；文獻(xiàn)[4]通過(guò)提高平均跳距計(jì)算精度和優(yōu)化節(jié)點(diǎn)位置計(jì)算方程來(lái)提高定位精度；文獻(xiàn)[5-6]也在定位方程和計(jì)算方法方面進(jìn)行了改進(jìn)；文獻(xiàn)[7]引入優(yōu)先級(jí)方法，提高測(cè)距誤差小的錨節(jié)點(diǎn)的影響度，并使優(yōu)先定位的未知節(jié)點(diǎn)參與其他未知節(jié)點(diǎn)的定位計(jì)算，由此降低定位誤差；文獻(xiàn)[8]采用了RSSI與DV-Hop結(jié)合的方法提高定位精度，但只是簡(jiǎn)單地使用RSSI測(cè)距值代替錨節(jié)點(diǎn)一跳范圍內(nèi)的節(jié)點(diǎn)距離，對(duì)于距錨節(jié)點(diǎn)一跳范圍外的節(jié)點(diǎn)測(cè)距沒(méi)有做修正。這些方法雖然在一定程度上提高了定位精度，然而都沒(méi)有修正因網(wǎng)絡(luò)節(jié)點(diǎn)分布不均所導(dǎo)致的誤差。

1 DV-Hop算法及誤差分析

DV-Hop算法通過(guò)獲取未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)，用平均跳距與最小跳數(shù)的乘積來(lái)估算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。平均跳距的獲得是通過(guò)兩已知錨節(jié)點(diǎn)的距離除以其間最小跳數(shù)而得到。這種計(jì)算平均跳距的方法雖然不受地形、地貌和天氣等環(huán)境因素的影響，但它不能反映出由節(jié)點(diǎn)分布不均引起的實(shí)際跳距（指相鄰節(jié)點(diǎn)間的實(shí)際距離）之間的差異，某些實(shí)際跳距與平均跳距往往相差甚遠(yuǎn)。因此，當(dāng)節(jié)點(diǎn)分布不均時(shí)DV-Hop算法會(huì)引起較大的測(cè)距誤差，進(jìn)而影響定位精度。

如圖1示，假設(shè)L1、L2和L3分別為錨節(jié)點(diǎn)，L1到L2的距離為D12=30，L1到a的實(shí)際距離為17，L2到a的實(shí)際距離為13，L1與L2之間跳數(shù)為Hops12=5跳；L2到L3的距離為D23=18，其間跳數(shù)為Hops23= 3跳。根據(jù)DV-Hop算法，得到平均跳距為Hopsize=(D12+D23)/(Hops12+Hops23)=6。再由L1、L2到未知節(jié)點(diǎn)a的跳數(shù)分別為2跳和3跳，得到未知節(jié)點(diǎn)a到錨節(jié)點(diǎn)L1、L2的距離分別為d1=12、d2=18。此距離與真實(shí)距離相差較大，這種誤差是由于網(wǎng)絡(luò)節(jié)點(diǎn)分布不均勻?qū)е碌?，L1到未知節(jié)點(diǎn)a只有2跳，但節(jié)點(diǎn)分布稀疏，實(shí)際距離較大；而L2到未知節(jié)點(diǎn)a的跳數(shù)雖然有3跳，但由于節(jié)點(diǎn)分布密集，因而實(shí)際距離較小。

圖1 DV-Hop誤差示意

2 基于RSSI修正的DV-Hop算法改進(jìn)

已知發(fā)射節(jié)點(diǎn)的發(fā)射信號(hào)強(qiáng)度，接收節(jié)點(diǎn)根據(jù)收到的信號(hào)強(qiáng)度，計(jì)算出信號(hào)的傳播損耗，再利用損耗模型將傳輸損耗轉(zhuǎn)化為距離，這種方式就是RSSI測(cè)距[9]。雖然RSSI所采用的測(cè)距方法能夠反映出由節(jié)點(diǎn)分布不均而引起的實(shí)際跳距之間的差異，但這種用傳播功率損耗來(lái)推算距離的做法往往受地形、地貌和天氣等環(huán)境因素影響很大。為避免這個(gè)問(wèn)題，文中不直接用RSSI算法得到的路徑長(zhǎng)度作為兩節(jié)點(diǎn)間距離，而是用每一跳的兩節(jié)點(diǎn)間RSSI路徑長(zhǎng)度與平均每跳的RSSI路徑長(zhǎng)度的比值作為修正系數(shù)——該系數(shù)由于是“比值”因而不再受環(huán)境因素的影響——然后再用修正系數(shù)與DV-Hop算得的平均跳距相乘來(lái)修正每跳的跳距。該所得跳距既能反映由節(jié)點(diǎn)分布不均引起的實(shí)際跳距之間的差異，還能不受環(huán)境因素的影響。

算法具體過(guò)程描述如下：第一步與DV-Hop一樣，錨節(jié)點(diǎn)以固定功率泛洪廣播自身位置信息，自身ID、跳數(shù)字段Hops，初始為0，接收到該數(shù)據(jù)的節(jié)點(diǎn)將Hops+1并記錄到數(shù)據(jù)包中，與DV-Hop不同的是該數(shù)據(jù)包中加入了由RSSI理論模型測(cè)得的路徑長(zhǎng)度值，記為RSSID(n)，這樣該節(jié)點(diǎn)數(shù)據(jù)包中記錄的信息如下:

ID 坐標(biāo) Hops1RSSID(1)

節(jié)點(diǎn)再以固定功率繼續(xù)向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)該數(shù)據(jù)包，鄰居節(jié)點(diǎn)收到該節(jié)點(diǎn)轉(zhuǎn)發(fā)的信息后，將跳數(shù)字段Hpos+1，并將自身收到的RSSI所測(cè)得的路徑長(zhǎng)度值與數(shù)據(jù)包中上一跳的路徑長(zhǎng)度值相加，并加入數(shù)據(jù)包，如下：

當(dāng)?shù)趎跳到達(dá)某節(jié)點(diǎn)時(shí)，該節(jié)數(shù)據(jù)包中數(shù)據(jù)為：

與DV-Hop相同，當(dāng)收到同一個(gè)ID的信息包中跳數(shù)小于已有跳數(shù)時(shí)，則替換，否則丟棄。當(dāng)一個(gè)錨節(jié)點(diǎn)的數(shù)據(jù)包經(jīng)n跳被另一個(gè)錨節(jié)點(diǎn)接收后，即可按照DV-Hop的方法計(jì)算平均跳距，同時(shí)計(jì)算平均每跳的RSSI路徑平均長(zhǎng)度值，如式（1）：

然后按DV-Hop方式廣播平均跳距Hopsize和平均RSSI路徑長(zhǎng)度RSSIDavg。

第二步，建立跳距修正系，用每一跳的RSSI路徑長(zhǎng)度RSSID( i)與平均路徑長(zhǎng)度RSSIDavg相除，作為該跳跳距的修正系數(shù)iε：

以跳距修正系數(shù)乘以平均跳距，即得修正后的每跳跳距。例如未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的跳數(shù)為n，求兩節(jié)點(diǎn)之間的距離如下：

由式（2）和式（3）得：

由此，各未知節(jié)點(diǎn)可用自身信息表中存儲(chǔ)的RSSIDN的值和平均跳距、平均路徑長(zhǎng)度，方便地算出到錨節(jié)點(diǎn)的距離。

第三步，與DV-Hop算法一樣，可利用三邊測(cè)量法或極大似然估計(jì)法等計(jì)算出未知節(jié)點(diǎn)的位置坐標(biāo)。

3 仿真實(shí)驗(yàn)

在Matlab環(huán)境下對(duì)文中提出的改進(jìn)型DV-Hop算法進(jìn)行仿真，同時(shí)與傳統(tǒng)DV-Hop算法或其他DV-Hop改進(jìn)算法進(jìn)行比較，蒙特卡洛計(jì)算次數(shù)為500次。

3.1 測(cè)距誤差

設(shè)定總數(shù)為100的節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的正方形內(nèi)，未知節(jié)點(diǎn)和錨節(jié)點(diǎn)具有相同的通信半徑。圖2給出了節(jié)點(diǎn)通信半徑分別為15 m、20 m和25 m時(shí)文中改進(jìn)的算法與原DV-Hop算法測(cè)距誤差比較。

圖2 3種不同通信半徑時(shí)的測(cè)距誤差曲線

從圖2可以看出，在3種不同的通信半徑下，錨節(jié)點(diǎn)數(shù)從10到50，文中改進(jìn)算法的測(cè)距誤差曲線始終低于DV-Hop算法的誤差曲線。其中通信半徑為15 m、20 m和25 m時(shí)，平均誤差分別降低0.57 m、1.78 m和2.33 m。通信半徑越大，文中算法的測(cè)距誤差降低越明顯，這是因?yàn)殡S著通信半徑的增大，平均跳距也會(huì)增大，因而文中算法通過(guò)修正系數(shù)與平均跳距相乘所獲得的修正效果也就越明顯。

3.2 定位誤差

設(shè)定總數(shù)200個(gè)節(jié)點(diǎn)隨機(jī)分布在150 m×150 m正方形的區(qū)域內(nèi)，錨節(jié)點(diǎn)和未知節(jié)點(diǎn)通信半徑均設(shè)為50 m。用估計(jì)坐標(biāo)與真實(shí)坐標(biāo)的距離差值相對(duì)于節(jié)點(diǎn)通信半徑之比表示定位誤差。對(duì)文中改進(jìn)型DV-Hop算法進(jìn)行仿真，并與原始DV-Hop算法、文獻(xiàn)[3，4，8]中算法的定位誤差進(jìn)行對(duì)比，如圖3所示。

圖3 4種算法定位誤差曲線

從圖3可以看出，錨節(jié)點(diǎn)數(shù)從10到60，文中算法定位誤差始終低于另外3種算法。與誤差最小的文獻(xiàn)[8]算法相比，在相同錨節(jié)點(diǎn)數(shù)量的情況下，文中改進(jìn)算法的定位誤差平均降低3.42%，定位性能有效改善。

4 結(jié)語(yǔ)

文中對(duì)DV-Hop算法產(chǎn)生誤差的原因進(jìn)行了分析，針對(duì)DV-Hop算法測(cè)距誤差受節(jié)點(diǎn)分布均勻程度影響較大的問(wèn)題，提出了一種基于RSSI修正的改進(jìn)型DV-Hop測(cè)距算法。該算法以RSSI值為基礎(chǔ)建立修正系數(shù)，用來(lái)修正DV-Hop算法中的每跳跳距。由于RSSI修正系數(shù)是一個(gè)比值，因此不會(huì)受到應(yīng)用環(huán)境變動(dòng)的影響，該算法在提高測(cè)距精度同時(shí)保持了DV-Hop算法環(huán)境適應(yīng)性強(qiáng)的優(yōu)點(diǎn)。仿真實(shí)驗(yàn)證明該算法有效地降低了由于節(jié)點(diǎn)分布不均而引起的測(cè)距誤差，提高了定位精度。

文中的仿真實(shí)驗(yàn)是在原DV-Hop算法基礎(chǔ)上，通過(guò)加入RSSI修正值以提高測(cè)距和定位精度，下一步的工作是將文中的修正算法與其他的改進(jìn)型DV-Hop算法相結(jié)合進(jìn)行仿真驗(yàn)證，另外如何降低算法的能量開(kāi)銷(xiāo)也將是下一步的研究?jī)?nèi)容。

[1] 蘇凱峰，雷菁，吳曉光.基于DV-Hop算法的地質(zhì)災(zāi)害預(yù)警應(yīng)用研究[J].通信技術(shù)，2011,44（04）：152-154.

[2] 蔡玲，周力.定位算法在傳感器網(wǎng)絡(luò)中的改進(jìn)策略[J].通信技術(shù)，2011，44（04）：93-96.

[3] 林金朝，劉海波，李國(guó)軍.無(wú)線傳感器網(wǎng)絡(luò)中DV-Hop節(jié)點(diǎn)定位改進(jìn)算法研究[J].計(jì)算機(jī)應(yīng)用研究，2009,26（04）：1272-1275.

[4] 張佳,吳延海,石峰.基于DV-Hop的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用，2010，30（02）：323-326.

[5] 呂睿,陽(yáng)憲惠．減少無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位誤差的方法[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，48（S2）：30-36.

[6] 林瑋,陳傳峰.基于Rssi的無(wú)線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J].傳感器技術(shù)，2009,289(02):180-182.

[7] 白鳳娥,姜曉榮,牟匯慧.無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的研究[J].計(jì)算機(jī)與數(shù)字工程，2010,38(03):34-36.

[8] 張品，孫巖.一種新的無(wú)線傳感器網(wǎng)絡(luò)DV-Hop算法[J].電子器件，2010,33(01):117-120.