DV-Hop定位算法的研究與改進(jìn)

劉 超 李海鵬

(西安電子工程研究所 西安 710100)

0 引言

無線傳感器網(wǎng)絡(luò)[1-2](Wireless Sensor Networks, WSN)通信系統(tǒng)由大量傳感器組成，用于對(duì)監(jiān)測(cè)區(qū)域的目標(biāo)進(jìn)行檢測(cè)、定位和跟蹤等，目標(biāo)定位算法尤為重要。DV-Hop算法不需要進(jìn)行角度測(cè)量或信號(hào)強(qiáng)度測(cè)量的設(shè)備，具有低成本[3]的優(yōu)勢(shì)，因而獲得了較多研究。DV-Hop算法僅著眼于欲求坐標(biāo)節(jié)點(diǎn)和已知錨節(jié)點(diǎn)的平均跳數(shù)距離，這種計(jì)算方式令節(jié)點(diǎn)間距與實(shí)際距離存在出入。為了減小誤差值，人們對(duì)DV-Hop 算法做出了許多的改進(jìn)嘗試，如文獻(xiàn)[4]引入的優(yōu)化均跳距優(yōu)化和優(yōu)化位置的改善思路，文獻(xiàn)[5]引入了灰狼算法和極大似然估計(jì)的改善思路。就DV-Hop算法中的不足，分析研究后，本文引入了細(xì)化半徑的通信方式的方法，以期改善定位精度。

1 DV-Hop定位算法

1.1 無線傳感器網(wǎng)絡(luò)技術(shù)

如今，不可計(jì)數(shù)的產(chǎn)品、技術(shù)伴隨著無線傳感器網(wǎng)絡(luò)的進(jìn)步走進(jìn)了人們的視野。其中，在定位技術(shù)方面，研究人員把在節(jié)點(diǎn)定位階段是否需要進(jìn)行距離的測(cè)量作為評(píng)判依據(jù)，歸為距離式和無距離式兩種節(jié)點(diǎn)定位思路[6-7]。其中，距離式定位技術(shù)是通過測(cè)量節(jié)點(diǎn)間的角度信息或者信號(hào)強(qiáng)度信息進(jìn)行未知節(jié)點(diǎn)的坐標(biāo)估算的,主要包括有AOA算法(Angle of Arrival)、TOA[8]算法(Time of Arrival)、TDOA算法(Time Difference on Arrival)和RSSI算法(Received Signal Strength Indicator)等，上述前三種方法對(duì)硬件設(shè)備要求較高,這無疑增加了成本;而RSSI算法在信號(hào)傳播過程中,信號(hào)強(qiáng)度會(huì)被障礙物影響而減弱,抗干擾性能較差。典型的無需測(cè)距的定位算法主要有DV-Hop算法(Distance Vector-Hop)、質(zhì)心算法(CentroidAlgorithm)、APIT(Approximate PIT Test)算法等。此類算法不需要測(cè)量角度或者測(cè)量信號(hào)強(qiáng)度的設(shè)備，大大降低了成本，因而受到研究人員的歡迎。

1.2 傳統(tǒng)DV-Hop定位算法組成

DV-Hop算法源于美國學(xué)者Dragos Niculescu等。其主旨是：首先,獲取未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的最小跳數(shù)、所有錨節(jié)點(diǎn)間的平均跳距；其次,未知節(jié)點(diǎn)選取周圍任意錨節(jié)點(diǎn)的平均跳距作為自身平均跳距值，與自身最小跳數(shù)相乘而得錨節(jié)點(diǎn)和未知節(jié)點(diǎn)間的距離；最后,將距離代入最小二乘法求解欲求節(jié)點(diǎn)坐標(biāo)值。

組成DV-Hop算法的部分有如下文三個(gè)階段[9]。

圖1 DV-Hop算法流程圖

1)最小跳數(shù)獲取

DV-Hop算法采用距離矢量路由協(xié)議的方法，把網(wǎng)絡(luò)中每個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)信息向周邊的節(jié)點(diǎn)進(jìn)行廣播，每個(gè)節(jié)點(diǎn)用{xi,yi,hi}表示,其中(xi,yi)就是錨節(jié)點(diǎn)i的位置坐標(biāo)信息；hi表示這個(gè)節(jié)點(diǎn)到錨節(jié)點(diǎn)i的跳數(shù)值，初始值均設(shè)置成0。

首先，每個(gè)錨節(jié)點(diǎn)將自身坐標(biāo)值和跳數(shù)值向鄰近節(jié)點(diǎn)廣而告之。鄰近節(jié)點(diǎn)處于接收到發(fā)出消息的狀態(tài)后，數(shù)據(jù)中的跳躍值就會(huì)增加1跳，緊接著將更新后的數(shù)據(jù)轉(zhuǎn)發(fā)給別的鄰居節(jié)點(diǎn)，將信息使用泛洪方式傳播。

其次，進(jìn)行跳數(shù)選擇操作：各接收節(jié)點(diǎn)將來自同一錨節(jié)點(diǎn)跳數(shù)值中的最小值保留，其他數(shù)值全部舍去。保持網(wǎng)絡(luò)的暢通，就能讓全部節(jié)點(diǎn)處于獲取每個(gè)錨節(jié)點(diǎn)最小跳數(shù)的狀態(tài)。

2)平均跳距的計(jì)算

全部節(jié)點(diǎn)獲取每個(gè)錨節(jié)點(diǎn)最小跳數(shù)后，可從式(1)獲悉全部錨節(jié)點(diǎn)的平均跳距。

(1)

式(1)中，i、j代表錨節(jié)點(diǎn)；(xi,yi)、(xj,yj)表示錨節(jié)點(diǎn)的坐標(biāo)；hj表示在i與j不等時(shí)錨節(jié)點(diǎn)i、j之間的最小跳數(shù)；HopSizei表示錨節(jié)點(diǎn)i的平均每跳距離。

在網(wǎng)絡(luò)中，將獲得的每個(gè)錨節(jié)點(diǎn)平均跳距進(jìn)行廣播，當(dāng)未知節(jié)點(diǎn)處于獲悉信息狀態(tài)時(shí)，選擇一個(gè)錨節(jié)點(diǎn)平均跳距作為自身的平均每跳距離。此時(shí)，全部未知節(jié)點(diǎn)u使用式(2)計(jì)算距錨節(jié)點(diǎn)i的近似距離dui。式(2)中，hui是錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)u之間的最小跳數(shù)。

dui=hui×HopSizeij(i≠j)

(2)

3)未知節(jié)點(diǎn)坐標(biāo)的解算

當(dāng)獲得的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的間距在3個(gè)或3個(gè)以上時(shí),就能按照最小二乘法進(jìn)行推理解算獲取所求未知節(jié)點(diǎn)的估計(jì)坐標(biāo)值[10]。

利用錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)u的坐標(biāo)(xu,yu) 和(xi,yi)可以得到方程(3)為

(3)

未知節(jié)點(diǎn)的坐標(biāo)用公式(4)求得。

(4)

方程(4)可改寫成Ax=B的形式，可得

(5)

(6)

由此可得未知節(jié)點(diǎn)u的坐標(biāo)為

Xu=(ATA)-1ATB

(7)

1.3 傳統(tǒng)DV-Hop定位算法舉例

圖2展示了4個(gè)節(jié)點(diǎn)的位置關(guān)系：A、B、C三個(gè)節(jié)點(diǎn)是坐標(biāo)已知的錨節(jié)點(diǎn)，N節(jié)點(diǎn)作為未知坐標(biāo)節(jié)點(diǎn)。

圖2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

由勾股定理得節(jié)點(diǎn)A、B的直線距離為20 m，節(jié)點(diǎn)A、C的直線距離為40 m，節(jié)點(diǎn)B、C的直線距離為50 m。

從圖中跳步路徑可得，2為節(jié)點(diǎn)A、B間的最小跳數(shù)值，3為節(jié)點(diǎn)A、C間的最小跳數(shù)值，4為節(jié)點(diǎn)B、C間的最小跳數(shù)值。

式(8)表示A、B、C三個(gè)節(jié)點(diǎn)的平均跳距值，對(duì)應(yīng)為

(8)

N取A的平均跳距值，式(9)獲得N節(jié)點(diǎn)的估計(jì)距離為

(9)

最后，將上述數(shù)值代入最小二乘法中推導(dǎo)解算就可以取得未知節(jié)點(diǎn)N的預(yù)計(jì)坐標(biāo)信息。

2 校正算法

2.1 DV-Hop算法存在的不足

1)跳數(shù)信息

通信半徑R內(nèi)的全部跳數(shù)值統(tǒng)一用1表示，與實(shí)際情況會(huì)產(chǎn)生偏差。比如，把0.3跳的實(shí)際跳數(shù)籠統(tǒng)的記為1，那么估計(jì)距離就會(huì)大于實(shí)際距離，生出誤差。

2)平均跳距

未知節(jié)點(diǎn)的平均跳距值是隨錨節(jié)點(diǎn)選取而發(fā)生著變化的，不是固定值。這種情況下，生出誤差是在所難免的。

3)計(jì)算未知節(jié)點(diǎn)坐標(biāo)的方法

在最小二乘法的推導(dǎo)計(jì)算過程中，不能排除得不到(ATA)-1的情況，一旦發(fā)生這種情況，就無法成對(duì)欲求坐標(biāo)值的解算，更無定位精度可言。

2.2 改進(jìn)算法的主旨思想

在DV-Hop 算法跳數(shù)獲取環(huán)節(jié)，只要鄰近節(jié)點(diǎn)出現(xiàn)在錨節(jié)點(diǎn)半徑為R的通信范圍之內(nèi)(或等于R)，就統(tǒng)一認(rèn)為它們間的跳數(shù)為1跳。

當(dāng)圖3所示的情況出現(xiàn)時(shí)：已知坐標(biāo)的3個(gè)錨節(jié)點(diǎn)，按DV-Hop算法跳數(shù)判定方法，統(tǒng)一認(rèn)為節(jié)點(diǎn)O、A與節(jié)點(diǎn)O、B的最小跳數(shù)值是1跳。實(shí)際情況與之不符，最小跳數(shù)值統(tǒng)一記為1跳，定會(huì)產(chǎn)生有誤差的結(jié)果。

圖3 錨節(jié)點(diǎn)分布示意圖

因此，將節(jié)點(diǎn)間的跳數(shù)細(xì)化非常必要，本文利用細(xì)化通信半徑的方式達(dá)到跳數(shù)細(xì)化的目的。改進(jìn)算法將通信半徑細(xì)分為0.1R、0.2R、0.3R、0.4R、0.5R、0.6R、0.7R、0.8R、0.9R和R共十種，也就是把通信面積分為了十種，R代表通信半徑。

2.3 改進(jìn)算法的具體步驟

第一步：最小跳數(shù)獲取。

1)初始化網(wǎng)絡(luò)，網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)首次廣播的通信半徑是0.1R，在0到0.1R的圓形區(qū)域內(nèi)通過廣播向范圍內(nèi)的節(jié)點(diǎn)發(fā)送自身信息。

當(dāng)信息傳播范圍內(nèi)的節(jié)點(diǎn)處于接收到信息的狀態(tài)后，接收節(jié)點(diǎn)獲悉與錨節(jié)點(diǎn)的最小跳數(shù)值是0.1跳。

2)所有錨節(jié)點(diǎn)以0.2R作為廣播的通信半徑，在0到0.2R的圓形區(qū)域內(nèi)通過廣播向影響范圍內(nèi)的節(jié)點(diǎn)發(fā)送自身信息。

如果是首次獲得錨節(jié)點(diǎn)信息的節(jié)點(diǎn)，該節(jié)點(diǎn)獲悉與錨節(jié)點(diǎn)的最小跳數(shù)值是0.2跳。若該節(jié)點(diǎn)之前就獲取過信息，仍保留0.1跳的數(shù)值。

3)以此類推，在之前通信半徑的基礎(chǔ)上每次增加0.1R進(jìn)行錨節(jié)點(diǎn)的第三、四、五、六、七、八、九和十次廣播，得到最小跳數(shù)值。在通信半徑變化的情況下，通過改變傳感器的發(fā)射功率來實(shí)現(xiàn)傳感器廣播范圍的變化。

第二步：平均跳距的計(jì)算。

使用勾股定理求取錨節(jié)點(diǎn)間的直線距離，再使用式(1)獲取全部錨節(jié)點(diǎn)的平均每跳距離值。

第三步：解算未知節(jié)點(diǎn)坐標(biāo)。

任意選取一個(gè)錨節(jié)點(diǎn)的平均每跳距離作為未知節(jié)點(diǎn)平均跳距進(jìn)行節(jié)點(diǎn)間距離計(jì)算。

最后，按照最小二乘法解算獲取未知節(jié)點(diǎn)的坐標(biāo)值。

3 仿真實(shí)驗(yàn)的結(jié)果與分析

3.1 仿真環(huán)境

使用計(jì)算機(jī)中Matlab R2016a軟件形成邊長100 m的正方形，并在其中任意分布100個(gè)節(jié)點(diǎn)。在錨節(jié)點(diǎn)數(shù)目一致的情況下，設(shè)計(jì)進(jìn)行多組實(shí)驗(yàn),利用蒙特卡洛方法得到定位誤差平均值。本文選取相對(duì)定位誤差作為評(píng)價(jià)標(biāo)準(zhǔn)，如式(5)為

(5)

其中，N為節(jié)點(diǎn)總數(shù)；u為錨節(jié)點(diǎn)數(shù)目；R為節(jié)點(diǎn)的通信半徑；(xi,yi)，(Xi,Yi)分別表示未知節(jié)點(diǎn)i的估算坐標(biāo)與實(shí)際坐標(biāo)。

仿真參數(shù)如表1所示。

表1 實(shí)驗(yàn)仿真參數(shù)

節(jié)點(diǎn)隨機(jī)分布圖如圖4所示。

圖4 節(jié)點(diǎn)隨機(jī)分布圖

3.2 仿真結(jié)果分析

仿真結(jié)果如圖5所示。

圖5 4種半徑對(duì)應(yīng)的原算法相對(duì)定位誤差與錨節(jié)點(diǎn)百分比的關(guān)聯(lián)示意圖

由圖4與圖5分析可得：

1)通信半徑統(tǒng)一的前提下，隨錨節(jié)點(diǎn)百分比的變大，原算法的相對(duì)定位誤差呈減小的趨勢(shì)。

2)錨節(jié)點(diǎn)百分比統(tǒng)一的基礎(chǔ)上，當(dāng)通信半徑逐步變大時(shí)，原算法的定位誤差也呈下降態(tài)勢(shì)，但是降幅在逐步趨小。

3)實(shí)際的工程應(yīng)用時(shí)，通信半徑不是越大就越好的，因?yàn)殡S著通信半徑變大，就需要更大的能量，會(huì)增加相應(yīng)的成本。

4)仔細(xì)觀察可得個(gè)別點(diǎn)的相對(duì)定位誤差會(huì)略高于前邊的點(diǎn)，這是網(wǎng)絡(luò)拓?fù)湓斐呻S機(jī)產(chǎn)生的緣故。

圖6至圖9說明：在以上4種半徑下進(jìn)行節(jié)點(diǎn)定位，改進(jìn)算法的相對(duì)定位誤差值有大幅的減少。這說明節(jié)點(diǎn)間的跳數(shù)細(xì)化對(duì)降低相對(duì)定位誤差的效果是積極的。

圖6 R=20m

圖7 R=30m

圖8 R=40m

圖9 R=50m

誤差降低值如表2所示，改進(jìn)算法相較于原算法削減了16%～39%的相對(duì)定位誤差。

表2 改進(jìn)算法在差別半徑下的誤差降低值

4 結(jié)束語

本文首先研究了經(jīng)典DV-Hop算法，經(jīng)分析發(fā)現(xiàn)了存在的缺陷，以跳數(shù)信息的不足為切入點(diǎn)，引入通信半徑細(xì)化的改善算法，獲得了細(xì)化的跳數(shù)和較為準(zhǔn)確的節(jié)點(diǎn)間距值。

經(jīng)由Matlab仿真實(shí)驗(yàn)，結(jié)果說明：在平等仿真前提下，改進(jìn)算法在沒有大幅度增加算法復(fù)雜度的背景下有效降低了定位誤差，實(shí)現(xiàn)了提高定位精度的目的。

然而本文提出的改進(jìn)算法的優(yōu)勢(shì)只是對(duì)定位精度的改善，對(duì)多次通信半徑的廣播和泛洪中能耗所產(chǎn)生的花銷沒有考慮在內(nèi)。未來應(yīng)著重研究在不影響定位精度的前提下，降低改進(jìn)算法的成本。