田麗芳,徐慧娟

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

項(xiàng)目來源:河南省科技發(fā)展計(jì)劃項(xiàng)目(132102210020)

2017-03-14修改日期2017-06-26

無線傳感網(wǎng)絡(luò)中基于測距修正的定位算法*

田麗芳*,徐慧娟

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

為了提高DV-Hop算法的定位精度,提出基于測距修正的無跡卡爾曼濾波優(yōu)化定位算法UKF-DV-Hop(Unscented Kalman Filtering Localization algorithm based on modifying average hop distance)。UKF-DV-Hop算法先對(duì)信標(biāo)節(jié)點(diǎn)廣播的信息包進(jìn)行改進(jìn),然后對(duì)跳距誤差進(jìn)行加權(quán)處理,進(jìn)而減少測距誤差,再利用最小二乘法估計(jì)未知節(jié)點(diǎn)位置,最后再利用無跡卡爾曼濾波UKF濾波優(yōu)化節(jié)點(diǎn)位置。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的DV-Hop算法相比,提出的UKF-DV-Hop算法的歸一化平均誤差率下降了約40%。

無線傳感網(wǎng)絡(luò);定位;DV-Hop;跳距;無跡卡爾曼濾波

由于在國防軍事、環(huán)境監(jiān)測、醫(yī)療救護(hù)等領(lǐng)域廣泛應(yīng)用,無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)的相關(guān)研究已受到廣泛關(guān)注[]。通過WSNs中的傳感節(jié)點(diǎn)監(jiān)測環(huán)境,再傳輸感測數(shù)據(jù),進(jìn)而實(shí)現(xiàn)對(duì)環(huán)境監(jiān)測、控制的目的。由于需要對(duì)環(huán)境實(shí)時(shí)、定位監(jiān)控,傳感節(jié)點(diǎn)所感測的數(shù)據(jù)必須提供相應(yīng)的位置。因此,節(jié)點(diǎn)定位已是WSNs應(yīng)用的關(guān)鍵技術(shù)[2-6]。

依據(jù)全球定位系統(tǒng)GPS(Global Positioning System),傳感節(jié)點(diǎn)能夠獲取自己的位置。然而,由于傳感節(jié)點(diǎn)屬于微型器件,體積較小,給每個(gè)傳感節(jié)點(diǎn)安裝GPS系統(tǒng)是不現(xiàn)實(shí)的。因此,需要通過一些定位算法,估算傳感節(jié)點(diǎn)的位置。通常,在WSNs中部署一些已知位置的節(jié)點(diǎn),將這些節(jié)點(diǎn)稱信標(biāo)節(jié)點(diǎn)。而那些未知位置的傳感節(jié)點(diǎn)稱為未知節(jié)點(diǎn)。常用的定位算法就是通過信標(biāo)節(jié)點(diǎn)的信息,例如距離、跳數(shù)等信息,估計(jì)未知節(jié)點(diǎn)的位置。

目前,現(xiàn)有定位技術(shù)可劃分為測距定位和非測距定位[7-8]。非測距定位算法是通過網(wǎng)絡(luò)連通等信息估計(jì)節(jié)點(diǎn)位置,如DV-Hop算法、Amorphous算法;而測距定位是利用離信標(biāo)節(jié)點(diǎn)的距離信息,估計(jì)未知節(jié)點(diǎn)位置,測距技術(shù)主要有AOA(Angle of Arrival)、TOA(Time of Arrival)、RSSI(Received Signal Strong Indicator)等。與測距定位算法相比,非測距定位算法定位精度較低,但是它無需額外的硬件設(shè)備,適用于低成本的傳感網(wǎng)絡(luò)。

作為非測距定位算法的典型代表,DV-Hop算法因?qū)嵤┓奖?、簡?而被廣泛應(yīng)用于WSNs。本文重點(diǎn)討論DV-Hop算法。然而,DV-Hop算法在定位精度存在較大的提升空間。DV-Hop算法先利用跳數(shù)測距,然后常采用三邊測量法估計(jì)節(jié)點(diǎn)位置。因此,可從測距精度和定位算法兩個(gè)階段改進(jìn)傳統(tǒng)的DV-Hop算法。

文獻(xiàn)[9]提出基于跳距修正粒子群優(yōu)化的定位算法,先修正測距,然后利用粒子群優(yōu)化位置估計(jì)值。而文獻(xiàn)[10]利用簇內(nèi)RSSI測距代替通過跳數(shù)測距,提高測距精度,進(jìn)而降低定位誤差。此外,文獻(xiàn)[11]通過引入誤差,修正跳距值,進(jìn)而提高DV-Hop算法的精度。

本文針對(duì)DV-Hop定位算法的不足,提出基于測距修正的無跡卡爾曼濾波優(yōu)化定位算法UKF-DV-Hop。UKF-DV-Hop算法分別從DV-Hop測距階段和定位階段進(jìn)行改進(jìn)。在測距階段,引用測距誤差,并對(duì)測距進(jìn)行校正;而在定位階段,先利用最小二乘法估計(jì)未知節(jié)點(diǎn)位置,然后通過無跡卡爾曼濾波優(yōu)化節(jié)點(diǎn)位置。仿真結(jié)果表明,提出的UKF-DV-Hop算法定位算法能夠提高定位精度,降低了定位誤差。

1 DV-Hop測距原理及問題描述

1.1 DV-Hop測距原理

傳統(tǒng)的DV-Hop測距過程主要有兩個(gè)實(shí)施步驟:

①跳數(shù)估計(jì)

首先,由信標(biāo)節(jié)點(diǎn)廣播信息包,其包含信標(biāo)節(jié)點(diǎn)的ID、位置坐標(biāo)以及跳數(shù)。初始跳數(shù)值為1。信息包格式如表1所示。

表1 信息包格式

②平均跳距估計(jì)

通過第1步,信標(biāo)節(jié)點(diǎn)能夠獲取到其他信標(biāo)節(jié)點(diǎn)的最小跳數(shù)值以及它們位置坐標(biāo)信息。為此,信標(biāo)節(jié)點(diǎn)便可計(jì)算自己的平均跳距值。具體而言,假定信標(biāo)節(jié)點(diǎn)Ai,它獲取了m個(gè)其他信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)以及最小跳數(shù)值。信標(biāo)節(jié)點(diǎn)i計(jì)算的平均跳距Hopsizei:

(1)

式中:(xi,yi)表示信標(biāo)節(jié)點(diǎn)Ai的位置坐標(biāo),而(xk,yk)表示除信標(biāo)節(jié)點(diǎn)Ai外的第k個(gè)信標(biāo)節(jié)點(diǎn)Ak位置坐標(biāo)。而hik表示Ai離Ak最小跳數(shù)值。

然后,未知節(jié)點(diǎn)選擇離自己最近的信標(biāo)節(jié)點(diǎn)的平均跳距作為自己的平均跳距。

圖1描述了DV-Hop測距過程。圖中3個(gè)黑心圓為3個(gè)信標(biāo)節(jié)點(diǎn)。L1離L2、L3的實(shí)際距離分別為40 m、100 m,而L2、L3間的實(shí)際距離為75m。3個(gè)信標(biāo)節(jié)點(diǎn)通過交互信息包,獲取了它們間的最小跳數(shù)值。如圖1所示,L1離L2、L3的最小跳數(shù)分別2跳、6跳。而L2離L3的最小跳數(shù)分別為5跳。因此,通過式(1)可計(jì)算L1、L2、L33個(gè)信標(biāo)節(jié)點(diǎn)的平均跳距:

(2)

由于未知節(jié)點(diǎn)A離信標(biāo)節(jié)點(diǎn)L2最近,A就選擇L2的平均跳距作為自己平均跳距,并由此平均跳距計(jì)算距離。

圖1 DV-Hop測距原理

1.2 問題描述

從1.1節(jié)的分析可知,DV-Hop測距是基于網(wǎng)絡(luò)拓?fù)涞倪B通度信息,在測距時(shí)存在誤差。

首先,跳數(shù)越多,測距誤差越大。而網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)是隨機(jī)分布的,節(jié)點(diǎn)間的跳數(shù)值有大有小,差異性大。其次,在估算距離時(shí),是將跳數(shù)值與平均跳距的乘積代替實(shí)際距離。盡管未知節(jié)點(diǎn)是選擇離自己最近的信標(biāo)節(jié)點(diǎn)的平均跳距作為自己的平均跳距,但這仍然存在誤差。并且通過跳數(shù)計(jì)算的距離是曲線距離,而不是直線距離。

2 UKF-DV-Hop算法

UKF-DV-Hop算法首先對(duì)DV-Hop測距進(jìn)行了改進(jìn)。主要從信息包格式和平均跳距兩方面進(jìn)行優(yōu)化。在定位階段,先用加權(quán)最小二乘法估計(jì)節(jié)點(diǎn)位置,再利用UKF濾波算法對(duì)所估計(jì)的位置進(jìn)行修正。

2.1 測距過程

2.1.1 信息包

依1.2節(jié)分析過程,跳數(shù)越多,測距誤差越大。為了避免跳數(shù)值過大,對(duì)每個(gè)信息包的跳數(shù)進(jìn)行控制。即允許信息包傳輸?shù)淖畲筇鴶?shù)。為此,在信息包中添加一個(gè)字段,即信息包的最大跳數(shù)。修改后的信息包字段格式如表2所示。

表2 修改后信息包格式

當(dāng)信息包傳輸跳數(shù)已到達(dá)最大跳數(shù)值時(shí),就不再轉(zhuǎn)發(fā)該信息包。限制最大傳輸跳數(shù),一方面能夠降低傳輸跳數(shù),另一方面,也減少信息包傳遞的碰撞概率,并降低網(wǎng)絡(luò)開銷。

此外,在信息包中同時(shí)添加自己的平均跳距誤差ε,其計(jì)算過程見2.2.2節(jié)。

2.1.2 基于信標(biāo)節(jié)點(diǎn)的平均跳距誤差

由于系統(tǒng)已知信標(biāo)節(jié)點(diǎn)位置以及每個(gè)信標(biāo)節(jié)點(diǎn)能夠通過式(1)計(jì)算平均跳距,可計(jì)算通過平均跳距所得距離與真實(shí)距離間的誤差值。此誤差反應(yīng)了在測距值的偏差值。

(3)

(4)

通過式(3)和(4)可估計(jì)信標(biāo)節(jié)點(diǎn)Ai的平均每跳距離誤差εi:

(5)

2.1.3 權(quán)值

每個(gè)信標(biāo)節(jié)點(diǎn)通過式(5)計(jì)算誤差ε,并通過信息包獲取其他信標(biāo)節(jié)點(diǎn)的平均跳距誤差,便可計(jì)算自己所估計(jì)的平均跳距的權(quán)值λ。具體而言,信標(biāo)節(jié)點(diǎn)Ai的權(quán)值定義如式(6)所示:

(6)

從式(6)的定義可知,誤差越大,權(quán)值越小。即將小誤差的平均跳距賦予大權(quán)值,反之,賦予小權(quán)值。

2.1.4 未知節(jié)點(diǎn)估算跳距

最后,由未知節(jié)點(diǎn)估計(jì)自己跳距,進(jìn)而測算離信標(biāo)節(jié)點(diǎn)的距離。考慮到離未知節(jié)點(diǎn)距離越遠(yuǎn)的信標(biāo)節(jié)點(diǎn)的誤差越大,并且在估算跳距時(shí),并非信標(biāo)節(jié)點(diǎn)越多,跳距越準(zhǔn)確。因此,未知節(jié)點(diǎn)只選擇離自己最近的3個(gè)信標(biāo)節(jié)點(diǎn)估計(jì)跳距。

具體而言,未知節(jié)點(diǎn)j,它選擇離自己最近的3個(gè)信標(biāo)節(jié)點(diǎn),且分別表示為Aa、Ab以及Ac。這3個(gè)信標(biāo)節(jié)點(diǎn)所估計(jì)的平均跳距以及權(quán)值分別為Hopsizea、Hopsizeb、Hopsizec以及λa、λb、λc。最終,未知節(jié)點(diǎn)j依據(jù)式(7)計(jì)算跳距:

(7)

從式(7)可知,未知節(jié)點(diǎn)所計(jì)算的平均跳距考慮了離它最近的3個(gè)信標(biāo)節(jié)點(diǎn)所計(jì)算的平均跳距和權(quán)值,進(jìn)而降低了測距誤差。

2.2 定位算法

2.2.1 最小二乘法算法

先利用加權(quán)最小二乘算法估計(jì)未知節(jié)點(diǎn)位置,并將此位置作為后續(xù)UKF濾波的初始位置。假定未知節(jié)點(diǎn)i到m個(gè)信標(biāo)節(jié)點(diǎn)的距離分別為d1、d2、d3,…,dm,且m≤n。

(8)

2.2.2UKF濾波算法

最小二乘法所估計(jì)的節(jié)點(diǎn)位置誤差可能較大,為此,進(jìn)一步利用UKF濾波,獲取精確的位置估計(jì)值。

θk=Bθk-1+Vk-1

(9)

然后,建立觀測方程模型。利用已測量的未知節(jié)點(diǎn)離信標(biāo)節(jié)點(diǎn)的距離作為濾波觀測量,所建立的觀測方程如式(10)所示:

(10)

式中:(xk,yk)表示第k個(gè)信標(biāo)節(jié)點(diǎn)位置。ηk是量測噪聲向量。而Hk是雅克比矩陣,如式(11)所示。

(11)

相比于EKF算法[12],UKF算法的濾波精度更高,且不增加計(jì)算量。因此,有多數(shù)情況下,UKF算法代替EKF算法。整個(gè)UKF算法流程如圖2所示。

UKF算法首先進(jìn)行初始化,第2步,計(jì)算采樣點(diǎn);第3步,進(jìn)行時(shí)間更新;第4步,實(shí)現(xiàn)量測更新,最后輸出狀態(tài)量輸出。

先生成2n+1個(gè)sigma點(diǎn)xi。UKF算法的迭代公式如(12)所示:

(12)

式中:Wi表示sigma點(diǎn)xi的權(quán)值。α表示采樣點(diǎn)均值的偏差,通常為一個(gè)小正數(shù)。而λ=α2(n+γ)-n,其中γ為調(diào)整參數(shù)。

然后,便可計(jì)算Z的均值和方差,如式(13)所示:

(13)

最后,建立非線性系統(tǒng),如式(14)所示。

(14)

式中:Xk、Zk分別為狀態(tài)量、觀測量。而νk、ηk分別為過程噪聲、量測噪聲,且它們相互獨(dú)立。

圖2 UKF算法流程

2.2.3 定位過程

首先由錨節(jié)點(diǎn)廣播信息包,其包含ID號(hào)和位置信息。未知節(jié)點(diǎn)接收后,判斷是否是第1次接收該數(shù)據(jù)包,如果是,就保存該數(shù)據(jù),并記錄離該數(shù)據(jù)包的跳數(shù)值。否則,就與緩存區(qū)內(nèi)記錄的跳數(shù)值進(jìn)行比較,并保存最小跳數(shù)值Hop。然后,依據(jù)式(7)進(jìn)行跳距,并計(jì)算距離。再利用最小二乘法估計(jì)未知節(jié)點(diǎn)的位置,并將此位置作為UKF算法的初始值,經(jīng)迭代后,最終得到未知節(jié)點(diǎn)位置,整個(gè)流程如圖3所示。

圖3 UKF-DV-Hop定位算法流程

3 仿真與分析

利用MATLAB建立仿真平臺(tái),分析UKF-DV-Hop算法性能。在100 m×100 m的區(qū)域內(nèi)隨機(jī)分布100個(gè)節(jié)點(diǎn),其中信標(biāo)節(jié)點(diǎn)所占比例為p%。而節(jié)點(diǎn)通信半徑R=30 m。每次實(shí)驗(yàn)獨(dú)立重復(fù)100次,取平均值作為最終數(shù)據(jù)。

此外,選擇同類定位算法:傳統(tǒng)的DV-Hop算法,以及改進(jìn)后的基于最優(yōu)通信半徑的DV-Hop算法(Optimization radius DV-Hop,ORDV-Hop)[13]和基于人工蜂群改進(jìn)的DV-Hop算法(Artificial Bee Colony-DV-Hop,ABDV-Hop)[14]進(jìn)行同步仿真,并與UKF-DV-Hop進(jìn)行比較。ORDV-Hop算法先通過網(wǎng)絡(luò)節(jié)點(diǎn)分布特性,尋找最優(yōu)通信半徑,再利用最小二乘法修正平均跳距。而ABDV-Hop算法先將定位問題轉(zhuǎn)化為全局最優(yōu)問題,然后再利用人工蜂群算法估計(jì)節(jié)點(diǎn)坐標(biāo)。

同時(shí),考慮歸一化平均定位誤差NAE(Normal Average Error)和歸一化均方根誤差NRMSE(Normal Root Average Error)作為性能指標(biāo),定義如式(15)所示[15]。

(15)

3.1 仿真數(shù)據(jù)

在實(shí)驗(yàn)過程中,重點(diǎn)分析信標(biāo)節(jié)點(diǎn)數(shù)對(duì)NAE、NRMSE性能影響。

首先分析信標(biāo)節(jié)點(diǎn)比例對(duì)NAE的性能影響。節(jié)點(diǎn)通信半徑R=30 m,信標(biāo)節(jié)點(diǎn)百分比p%從10%至35%變化,實(shí)驗(yàn)數(shù)據(jù)分別如圖4所示。

圖4 NAE隨信標(biāo)節(jié)點(diǎn)比例的性能影響

從圖4可知,信標(biāo)節(jié)點(diǎn)p%的增加,降低了NAE。原因在于:信標(biāo)節(jié)點(diǎn)百分比的增加,降低了某一個(gè)信標(biāo)節(jié)點(diǎn)對(duì)定位精度的影響,相應(yīng)地,減少了NAE。與DV-Hop算法相比,提出的UKF-DV-Hop算法的NAE下降40%,并且也低于ORDV-Hop和ABDV-Hop算法。

圖5 NRMSE隨通信半徑的性能影響

然后,再分析了節(jié)點(diǎn)通信半徑對(duì)NRMSE的影響。信標(biāo)節(jié)點(diǎn)比例p%=20%,節(jié)點(diǎn)通信半徑R從20～40變化,實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

從圖5可知,提出的UKF-DV-Hop定位算法的NRMSE最低。原因在于UKF-DV-Hop定位算法有效地修正了DV-Hop測距值,同時(shí)通過UKF濾波算法優(yōu)化位置估計(jì)值。此外,從圖5可知,通信半徑的增加有利于提高定位精度,但是,當(dāng)通信半徑增加到一定值后,NRMSE并沒有下降。這說明一味地增加通信半徑,并不能降低NRMSE。

4 總結(jié)

傳統(tǒng)的DV-Hop定位算法在測距階段,只是簡單地采用單一方式計(jì)算平均跳距,增加了測距誤差。為此,基于測距修正的無跡卡爾曼濾波優(yōu)化定位算法UKF-DV-Hop。UKF-DV-Hop算法先優(yōu)化跳距,降低測距誤差,然后通過UKF優(yōu)化節(jié)點(diǎn)位置估計(jì)值。實(shí)驗(yàn)結(jié)果表明,提出的UKF-DV-Hop算法在定位誤差性能方面優(yōu)于傳統(tǒng)的DV-Hop算法。

[1] 梁玉琴,曾慶化,劉建業(yè). 基于UKF濾波的WSN節(jié)點(diǎn)定位研究[J]. 傳感技術(shù)學(xué)報(bào),2010,23(6):878-883.

[2] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2012,7(5):28-34.

[3] Patwari N,Hero A,Perkins M,et al. Relative Location Estimation in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2013,51(8):2137-2148.

[4] 李娟,劉禹,錢志鴻,等. 基于雙通信半徑的傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)),2014,44(2):502-508.

[5] 金純,葉誠,韓志斌.無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2013,34(2):401-405.

[6] 王新生,趙衍靜,李海濤. 基于DV-Hop算法的改進(jìn)研究[J]. 計(jì)算機(jī)科學(xué),2011,38(2):76-78.

[7] Patwari N,Hero A,Perkins M,et al. Relative Location Estimation in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2013,51(8):2137-2148.

[8] Xiao Q,Xiao B,Cao J,et al. Multihop Range-Free Lcalization in Anisotropic Wireless Sensor Networks:A Pattern-Drive Scheme[J]. IEEE Trans. Mobile Comput,2013,9(11):1592-1607.

[9] 趙雁航,錢志鴻,尚小航,等. 基于跳距修正粒子群優(yōu)化的WSN定位算法[J]. 通信學(xué)報(bào),2013,34(9):105-115.

[10] 黃晨鐘,許力,葉阿勇. 基于簇內(nèi)RSSI測距改進(jìn)的DV-Hop算法[J]. 福建師范大學(xué)學(xué)報(bào),2010,26(6):29-34.

[11] 張佳,吳延海,石峰,等. 基于DV-Hop無線傳感網(wǎng)絡(luò)定位算法[J]. 計(jì)算機(jī)應(yīng)用,2010,30(2):323-326.

[12] Julier S U,Durrant W H F. A New Method for the Nonlinear Transformation of Means and Covariance in Filters and Estimators[J]. IEEE Transactions on Automatic Control,2010,45(3):477-482.

[13] 吳玉成,李江雯. 基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法[J]. 華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,40(6):35-42.

[14] 李牧東,熊偉,梁青. 基于人工蜂群改進(jìn)算法的無線傳感網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報(bào),2013,26(2):241-245.

[15] 喬欣,常飛,丁恩杰,等. 基于跳距修正的WSN擬牛頓迭代定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(6):797-801.

LocalizationAlgorithmBasedonModifyingAverageHopDistanceinWirelessSensorNetworks*

TIANLifang*,XUHuijuan

(School of Information Engineering,Huanghuai University,Zhumadian He’nan 463000,China)

In order to improve the localization accuracy of DV-Hop,Unscented Kalman Filtering(UKF)Localization algorithm based on modifying average hop distance(UKF-DV-Hop)is proposed in this paper. Firstly,the he structure of data packets by anchor nodes with broadcasting is changed,then average hop distance error is modified,in order to reduce the ranging error. An inaccurate position coordinate of the unknown node was obtained by least square estimation(LSE),and an accurate node localization method was achieved by using UKF.Numerous simulation results show that normalized average localization error ratio of UKF-DV-Hop algorithm is about 40% less than that of traditional DV-Hop algorithm.

wireless sensor network;localization;DV-Hop algorithm;Hop distance;unscented kalman filtering

TPT393

A

1004-1699(2017)10-1572-06

10.3969/j.issn.1004-1699.2017.10.020

田麗芳(1981-),女,漢族,山西長治人,碩士,講師,研究方向?yàn)閿?shù)據(jù)挖掘、軟件測試、系統(tǒng)建模;

徐慧娟(1977-),女,漢族,駐馬店人,碩士,副教授,研究方向?yàn)閿?shù)據(jù)挖掘、系統(tǒng)分析與建模。