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

（①國防科學技術大學 電子科學與工程學院，湖南 長沙 410073；②空軍裝備研究院 通信導航與指揮自動化研究所，北京 100843）

0 引言

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

1 DV-Hop算法及誤差分析

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

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

圖1 DV-Hop誤差示意

2 基于RSSI修正的DV-Hop算法改進

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

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

ID 坐標 Hops1RSSID(1)

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

當?shù)趎跳到達某節(jié)點時，該節(jié)數(shù)據包中數(shù)據為：

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

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

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

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

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

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

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

3 仿真實驗

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

3.1 測距誤差

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

圖2 3種不同通信半徑時的測距誤差曲線

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

3.2 定位誤差

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

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

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

4 結語

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

文中的仿真實驗是在原DV-Hop算法基礎上，通過加入RSSI修正值以提高測距和定位精度，下一步的工作是將文中的修正算法與其他的改進型DV-Hop算法相結合進行仿真驗證，另外如何降低算法的能量開銷也將是下一步的研究內容。

[1] 蘇凱峰，雷菁，吳曉光.基于DV-Hop算法的地質災害預警應用研究[J].通信技術，2011,44（04）：152-154.

[2] 蔡玲，周力.定位算法在傳感器網絡中的改進策略[J].通信技術，2011，44（04）：93-96.

[3] 林金朝，劉海波，李國軍.無線傳感器網絡中DV-Hop節(jié)點定位改進算法研究[J].計算機應用研究，2009,26（04）：1272-1275.

[4] 張佳,吳延海,石峰.基于DV-Hop的無線傳感器網絡定位算法[J].計算機應用，2010，30（02）：323-326.

[5] 呂睿,陽憲惠．減少無線傳感器網絡節(jié)點定位誤差的方法[J].清華大學學報：自然科學版，2008，48（S2）：30-36.

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

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

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