DV-Hop定位算法的研究與改進

劉 超 李海鵬

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

0 引言

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

1 DV-Hop定位算法

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

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

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

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

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

圖1 DV-Hop算法流程圖

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

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

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

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

2)平均跳距的計算

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

(1)

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

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

dui=hui×HopSizeij(i≠j)

(2)

3)未知節(jié)點坐標的解算

當獲得的錨節(jié)點與未知節(jié)點的間距在3個或3個以上時,就能按照最小二乘法進行推理解算獲取所求未知節(jié)點的估計坐標值[10]。

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

(3)

未知節(jié)點的坐標用公式(4)求得。

(4)

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

(5)

(6)

由此可得未知節(jié)點u的坐標為

Xu=(ATA)-1ATB

(7)

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

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

圖2 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

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

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

式(8)表示A、B、C三個節(jié)點的平均跳距值，對應為

(8)

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

(9)

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

2 校正算法

2.1 DV-Hop算法存在的不足

1)跳數(shù)信息

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

2)平均跳距

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

3)計算未知節(jié)點坐標的方法

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

2.2 改進算法的主旨思想

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

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

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

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

2.3 改進算法的具體步驟

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

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

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

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

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

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

第二步：平均跳距的計算。

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

第三步：解算未知節(jié)點坐標。

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

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

3 仿真實驗的結(jié)果與分析

3.1 仿真環(huán)境

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

(5)

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

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

表1 實驗仿真參數(shù)

節(jié)點隨機分布圖如圖4所示。

圖4 節(jié)點隨機分布圖

3.2 仿真結(jié)果分析

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

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

由圖4與圖5分析可得：

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

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

3)實際的工程應用時，通信半徑不是越大就越好的，因為隨著通信半徑變大，就需要更大的能量，會增加相應的成本。

4)仔細觀察可得個別點的相對定位誤差會略高于前邊的點，這是網(wǎng)絡(luò)拓撲造成隨機產(chǎn)生的緣故。

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

圖6 R=20m

圖7 R=30m

圖8 R=40m

圖9 R=50m

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

表2 改進算法在差別半徑下的誤差降低值

4 結(jié)束語

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

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

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