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

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

0 引言

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

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

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

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

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

1 DV-Hop定位及誤差分析

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

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

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

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

1.2 平均跳距的估算

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

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

2 NHDL定位算法

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

若直接利用分組包傳遞的次數(shù)，估計(jì)錨節(jié)點(diǎn)間的跳數(shù)存在偏差.為此，利用接收的信號(hào)強(qiáng)度指示(RSSI)對(duì)跳數(shù)進(jìn)行修正.

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

圖2 信號(hào)傳輸模型

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

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

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

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

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

2.4 基于最小最大法的節(jié)點(diǎn)位置估計(jì)

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

圖3 基于最小最大法的節(jié)點(diǎn)位置估計(jì)

2.5 定位流程

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

然后，錨節(jié)點(diǎn)依據(jù)2.2節(jié)對(duì)平均跳距進(jìn)行修正，再進(jìn)行廣播分組包，未知節(jié)點(diǎn)接收到分組包后，估算離錨節(jié)點(diǎn)的距離.當(dāng)獲取3 個(gè)以上錨節(jié)點(diǎn)后，再?gòu)闹羞x擇3個(gè)非共線的錨節(jié)點(diǎn)，并依據(jù)最小最大法估計(jì)位置，NHDL 定位算法流程如圖4所示.

圖4 NHDL定位算法流程

3 仿真與分析

3.1 仿真環(huán)境

3.2 錨節(jié)點(diǎn)數(shù)對(duì)定位精度的影響

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

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

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

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

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

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

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

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

3.4 通信半徑對(duì)定位精度的影響

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

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

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

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

4 總結(jié)

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