一種基于跳數(shù)修正和跳距優(yōu)化的DV-Hop定位算法

張媛，王梅，繆相林，丁凰

( 1.西安交通大學城市學院計算機系，西安 710018；2.西安交通大學計算機學院，西安 710049)

0 引言

隨著智能信息產(chǎn)業(yè)的發(fā)展，基于無線傳感器網(wǎng)絡(WSN)[1]在智慧農(nóng)業(yè)、智能康復醫(yī)療和戰(zhàn)場防線勘察領域得到了廣泛的應用.多數(shù)的WSN 應用需要獲取節(jié)點的位置信息[2]，需通過定位算法估計節(jié)點位置，即對節(jié)點進行定位.

目前節(jié)點定位算法可分為兩類：測距和非測距定位.基于接收的信號強度指示(RSSI)[3]、到達時間差(TDOA)[4]和到達角度(AOA)[5]屬測距定位算法；質(zhì)心定位、DV-Hop定位[6]和凸算法屬非測距定位算法.相比于測距定位算法，非測距定位算法無需額外的硬件設備測量距離，降低了定位成本.

作為經(jīng)典的非測距定位算法，DV-Hop 算法被廣泛應用于估計節(jié)點位置.盡管DV-Hop算法的復雜性低，但其也存在一些不足.如最小跳數(shù)估計精度不高，跳距估計誤差大.為此，研究人員提出了不同的改進策略.

胡玉蘭等[7]提出基于平均跳距優(yōu)化的DV-Hop改進算法(AHDD).通過對跳數(shù)進行優(yōu)化，提高估計平均跳距的精度；鄧浪等[8]對DV-Hop算法的跳數(shù)進行優(yōu)化，并利用最小均方差準則估計平均跳距，提高測距精度；Gao等[9]引入粒子群優(yōu)化算法，利用粒子群算法修正節(jié)點位置，提高定位精度.盡管上述算法減少了定位誤差，但仍存在最小二乘法初值敏感以及生物智能算法的復雜度高等問題.

為此，針對DV-Hop算法的定位精度問題，分析了導致定位精度不高的原因，并提出基于跳數(shù)修正和跳距優(yōu)化的DV-Hop定位算法(NHDL). NHDL 算法利用信號強度值對跳數(shù)進行修正，并利用錨節(jié)點間已知的位置信息對跳距誤差進行優(yōu)化.同時采用易實現(xiàn)的最小最大法估計節(jié)點位置.仿真結果表明：提出的NHDL 算法有效地提高了定位精度.

1 DV-Hop定位及誤差分析

DV-Hop定位算法主要由三個階段構成：1)未知節(jié)點與錨節(jié)點間的最小跳數(shù)的估算；2)未知節(jié)點與錨節(jié)點間的平均跳距的估算；3)未知節(jié)點位置的估算.其中，跳數(shù)和平均跳距的估計存在較大的誤差.

1.1 最小跳數(shù)的估算

傳統(tǒng)的DV-Hop定位算法不論鄰居節(jié)點間的實際距離遠近，只要接收到鄰居節(jié)點發(fā)送的分組包，就將跳數(shù)設置為1.如圖1所示，錨節(jié)點L1與未知節(jié)點A，節(jié)點A與節(jié)點B的距離不同，但是對于節(jié)點A而言，它們離自己的跳數(shù)均為1跳.通過這種方式估算跳數(shù)，再利用跳數(shù)測算距離必然會產(chǎn)生定位誤差.

圖1 DV-Hop算法誤差分析圖

1.2 平均跳距的估算

依據(jù)DV-Hop 算法估算平均跳距策略，錨節(jié)點L1所估算的平均跳距為：( 40+40)/(4+4)=10.未知節(jié)點A接收此平均距離信息后，利用跳數(shù)與平均跳距的乘積作為離L1的距離： 1 ×10= 10.但是實際上，L1與未知節(jié)點A的距離為5.

通過上述分析可知，DV-Hop定位算法在最小跳數(shù)和平均跳距的估算階段存在明顯的誤差.為此，NHDL 算法將對跳數(shù)和跳距進行修正，再通過最小最大法估計未知節(jié)點位置.

2 NHDL定位算法

2.1 基于RSSI 的跳數(shù)修正

若直接利用分組包傳遞的次數(shù)，估計錨節(jié)點間的跳數(shù)存在偏差.為此，利用接收的信號強度指示(RSSI)對跳數(shù)進行修正.

采用對數(shù)衰減模型，通過RSSI 估計距離，如式(1)所示：

圖2 信號傳輸模型

錨節(jié)點將修正后的跳數(shù)載入分組包中，向下一跳鄰居節(jié)點廣播.接收到分組包后，節(jié)點先從分組包中提取跳數(shù)值，并檢查是否已保留了離發(fā)送節(jié)點的跳數(shù)值. 若已保留，就比較這兩個跳數(shù)值，并存儲兩值中的最小值作為這兩個節(jié)點間的跳數(shù).然后，再將此跳數(shù)加1，繼續(xù)廣播分組包.

2.2 基于錨節(jié)點位置的平均跳距優(yōu)化

2.3 定位盲區(qū)感知的錨節(jié)點選擇

文中考慮了節(jié)點位置屬二維空間.估計二維空間中節(jié)點的位置，至少3個錨節(jié)點的測距信息.因此，在估計節(jié)點位置時，需選擇3個錨節(jié)點，并建立相應的距離方程.然而，如果所選擇的3個錨節(jié)點位于同一條直線，即共線，就無法估計節(jié)點位置，出現(xiàn)定位盲區(qū)[10].

為了避免定位盲區(qū)，NHDL 算法先通過行列式法計算3個錨節(jié)點所形成的區(qū)域面積，再判斷區(qū)域面積是否為零.若為零，則表示這3個錨節(jié)點共線；反之，不共線.具體過程如下：

2.4 基于最小最大法的節(jié)點位置估計

首先，未知節(jié)點通過修正后的最小跳數(shù)以及優(yōu)化后的跳距，計算離錨節(jié)點的距離；然后，利用最小最大法計算自己的位置坐標，即定位.最小最大法的思路如下：未知節(jié)點獲取離錨節(jié)點的距離后，以錨節(jié)點位置為圓心以估計的距離為半徑形成圓的外接矩形.二維空間的位置，至少需要形成以3 個非共線的錨節(jié)點的外接矩形；最后，以3個外接矩形所重疊的區(qū)域的中心位置為未知節(jié)點位置的估計值.

圖3 基于最小最大法的節(jié)點位置估計

2.5 定位流程

首先，部署節(jié)點.錨節(jié)點廣播分組包.網(wǎng)絡內(nèi)所有節(jié)點通過接收分組包以及RSSI值對最小跳數(shù)值進行修正，并存儲最小跳數(shù)值.

然后，錨節(jié)點依據(jù)2.2節(jié)對平均跳距進行修正，再進行廣播分組包，未知節(jié)點接收到分組包后，估算離錨節(jié)點的距離.當獲取3 個以上錨節(jié)點后，再從中選擇3個非共線的錨節(jié)點，并依據(jù)最小最大法估計位置，NHDL 定位算法流程如圖4所示.

圖4 NHDL定位算法流程

3 仿真與分析

3.1 仿真環(huán)境

3.2 錨節(jié)點數(shù)對定位精度的影響

本次實驗參數(shù)如下：未知節(jié)點數(shù)n=100；R=20 m；錨節(jié)點數(shù)從10～40變化.圖5給出了DV-Hop算法、AHDD算法和NHDL 算法的平均定位誤差隨錨節(jié)點數(shù)的變化情況.

由圖5可知，平均定位誤差隨錨節(jié)點數(shù)量的增加呈下降趨勢.當錨節(jié)點數(shù)量較少時，增加錨節(jié)點數(shù)可以有效地降低平均定位誤差；但當錨節(jié)點數(shù)達到一定數(shù)量后(大于25)，平均定位誤差隨錨節(jié)點數(shù)量增加而變緩慢.這說明并非增加錨節(jié)點數(shù)就一定能夠降低平均定位誤差.

圖5 錨節(jié)點數(shù)對平均定位誤差的影響

此外，相比于DV-Hop算法和AHDD算法，提出的NHDL 算法具有較低的平均定位誤差.這歸功于NHDL 算法通過RSSI值對跳數(shù)進行了修正，控制了跳數(shù)估計的誤差.同時，利用錨節(jié)點間已知的位置信息，平均跳距進行了優(yōu)化，最終提高了定位精度.

3.3 未知節(jié)點數(shù)對定位精度的影響

本次實驗參數(shù)如下：未知節(jié)點數(shù)從60～200變化，錨節(jié)點個數(shù)等于10%的未知節(jié)點數(shù)，節(jié)點通信半徑為20 m.DV-Hop 算法、AHDD算法和NHDL 算法的平均定位誤差隨未知節(jié)點數(shù)的變化情況，如圖6所示.

圖6 未知節(jié)點數(shù)對平均定位誤差的影響

由圖6可知，節(jié)點數(shù)的增加有利于定位精度的提升.原因在于：網(wǎng)絡內(nèi)節(jié)點數(shù)越多，網(wǎng)絡的連通性越好，節(jié)點能夠獲取的定位信息越充分.此外，相比于DV-Hop 算法和AHDD算法，NHDL算法在平均定位誤差性能方面具有較大的優(yōu)勢.例如，當節(jié)點數(shù)為200時，NHDL 算法的平均定位誤差為0.122 m，而DV-Hop 算法和AHDD算法的平均定位誤差分別為0.274 m 和0.237 m.

3.4 通信半徑對定位精度的影響

最后，分析通信半徑R對定位精度的影響.本次實驗參數(shù)：未知節(jié)點數(shù)n=100；錨節(jié)點數(shù)為10 個；通信半徑從15～40 m 變化.

圖7給出DV-Hop算法、AHDD算法和NHDL算法的平均定位誤差隨通信半徑R的變化情況.由圖7可知，通信半徑的增加有利于降低平均定位誤差.原因在于通信半徑越大，節(jié)點通信的范圍越大，能夠獲取的定位信息越多，這有利于提高定位精度.

圖7 節(jié)點數(shù)對平均定位誤差率的影響

此外，相比于DV-Hop算法和AHDD算法，NHDL算法降低了平均定位誤差.在通信半徑較低時，NHDL算法在平均定位誤差性能方面的優(yōu)勢更明顯.例如，在通信半徑為20 m 時，NHDL 算法的平均定位誤差為0.183 m，而DV-Hop 算法和AHDD算法的平均定位誤差分別為0.520 m 和0.294 m.

4 總結

基于傳統(tǒng)的DV-Hop算法的定位精度不高的問題，提出基于跳數(shù)修正和跳距優(yōu)化的DV-Hop定位算法NHDL. NHDL算法對跳數(shù)和跳距的計算過程進行優(yōu)化，降低定位誤差.利用易實現(xiàn)的最小最大法估計未知節(jié)點位置，降低算法的復雜度.仿真結果表明：提出的NHDL 算法有效地降低了定位誤差.