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

田麗芳,徐慧娟

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

項目來源:河南省科技發(fā)展計劃項目(132102210020)

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

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

田麗芳*,徐慧娟

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

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

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

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

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

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

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

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

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

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

1.1 DV-Hop測距原理

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

①跳數(shù)估計

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

表1 信息包格式

②平均跳距估計

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

(1)

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

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

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

(2)

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

圖1 DV-Hop測距原理

1.2 問題描述

從1.1節(jié)的分析可知,DV-Hop測距是基于網(wǎng)絡(luò)拓撲的連通度信息,在測距時存在誤差。

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

2 UKF-DV-Hop算法

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

2.1 測距過程

2.1.1 信息包

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

表2 修改后信息包格式

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

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

2.1.2 基于信標節(jié)點的平均跳距誤差

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

(3)

(4)

通過式(3)和(4)可估計信標節(jié)點Ai的平均每跳距離誤差εi:

(5)

2.1.3 權(quán)值

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

(6)

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

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

最后,由未知節(jié)點估計自己跳距,進而測算離信標節(jié)點的距離?？紤]到離未知節(jié)點距離越遠的信標節(jié)點的誤差越大,并且在估算跳距時,并非信標節(jié)點越多,跳距越準確。因此,未知節(jié)點只選擇離自己最近的3個信標節(jié)點估計跳距。

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

(7)

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

2.2 定位算法

2.2.1 最小二乘法算法

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

(8)

2.2.2UKF濾波算法

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

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

(9)

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

(10)

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

(11)

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

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

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

(12)

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

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

(13)

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

(14)

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

圖2 UKF算法流程

2.2.3 定位過程

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

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

3 仿真與分析

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

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

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

(15)

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

在實驗過程中,重點分析信標節(jié)點數(shù)對NAE、NRMSE性能影響。

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

圖4 NAE隨信標節(jié)點比例的性能影響

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

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

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

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

4 總結(jié)

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

[1] 梁玉琴,曾慶化,劉建業(yè). 基于UKF濾波的WSN節(jié)點定位研究[J]. 傳感技術(shù)學報,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]. 吉林大學學報(工學),2014,44(2):502-508.

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

[6] 王新生,趙衍靜,李海濤. 基于DV-Hop算法的改進研究[J]. 計算機科學,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]. 通信學報,2013,34(9):105-115.

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

[11] 張佳,吳延海,石峰,等. 基于DV-Hop無線傳感網(wǎng)絡(luò)定位算法[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é)點通信半徑的改進DV-Hop定位算法[J]. 華南理工大學學報(自然科學版),2012,40(6):35-42.

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

[15] 喬欣,常飛,丁恩杰,等. 基于跳距修正的WSN擬牛頓迭代定位算法[J]. 傳感技術(shù)學報,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-),女,漢族,山西長治人,碩士,講師,研究方向為數(shù)據(jù)挖掘、軟件測試、系統(tǒng)建模;

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