基于跳距修正的WSN擬牛頓迭代定位算法*

喬 欣,常 飛,丁恩杰*,王桃

(1.中國(guó)礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心,江蘇 徐州 221008;2.礦山互聯(lián)網(wǎng)應(yīng)用技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室,江蘇 徐州 221008;3.中國(guó)礦業(yè)大學(xué)信息與電氣工程學(xué)院,江蘇 徐州 221008)

?

基于跳距修正的WSN擬牛頓迭代定位算法*

喬 欣1,2,3,常 飛1,2,3,丁恩杰1,2,3*,王桃1,2,3

(1.中國(guó)礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心,江蘇 徐州 221008;2.礦山互聯(lián)網(wǎng)應(yīng)用技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室,江蘇 徐州 221008;3.中國(guó)礦業(yè)大學(xué)信息與電氣工程學(xué)院,江蘇 徐州 221008)

針對(duì)DV-Hop算法在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)洵h(huán)境下存在誤差較大的問(wèn)題,提出了一種基于跳距修正的WSN擬牛頓迭代定位算法(CNDV-Hop)。在詳細(xì)分析DV-Hop算法過(guò)程與誤差原因的基礎(chǔ)上,提出相應(yīng)改進(jìn):首先設(shè)定跳數(shù)閾值,對(duì)錨節(jié)點(diǎn)進(jìn)行優(yōu)選;然后采用新的方法校正錨節(jié)點(diǎn)跳距,利用對(duì)應(yīng)錨節(jié)點(diǎn)跳距的校正值計(jì)算節(jié)點(diǎn)間的距離;最后用擬牛頓法對(duì)未知節(jié)點(diǎn)坐標(biāo)的最小二乘解進(jìn)行迭代優(yōu)化。仿真結(jié)果表明,本文改進(jìn)算法能有效地降低估計(jì)誤差對(duì)定位準(zhǔn)確度的影響,與現(xiàn)有改進(jìn)DV-Hop算法相比精度更高。

跳數(shù)閾值;DV-Hop定位算法;平均跳距;擬牛頓法

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)由布撒在區(qū)域內(nèi)的大量傳感節(jié)點(diǎn)組成的網(wǎng)絡(luò),通常被用于環(huán)境監(jiān)測(cè)、智能空間、醫(yī)療服務(wù)、軍事目標(biāo)跟蹤等領(lǐng)域[1]。其中,節(jié)點(diǎn)的位置信息是非常重要的,因此,節(jié)點(diǎn)定位技術(shù)成為WSN中的重要研究課題。

對(duì)于大型、不易布置節(jié)點(diǎn)的監(jiān)測(cè)網(wǎng)絡(luò),能耗是整個(gè)網(wǎng)絡(luò)生存的最關(guān)鍵因素,因此,需要一種能耗低、計(jì)算復(fù)雜度低、定位精度相對(duì)較高的定位技術(shù)。DV-Hop是一種典型的無(wú)需測(cè)距定位算法,具有方法簡(jiǎn)單,定位精度相對(duì)較高、通信開(kāi)銷(xiāo)小等優(yōu)點(diǎn)[2],該算法被經(jīng)常用于大型WSN中。但是,在需要高精度定位的災(zāi)害環(huán)境監(jiān)測(cè)區(qū)域下,DV-Hop算法仍然存在不足,目前國(guó)內(nèi)外的研究學(xué)者對(duì)DV-Hop定位算法提出了許多的改進(jìn)方案[3]。文獻(xiàn)[4]提出了一種改進(jìn)加權(quán)DV-Hop算法,該算法通過(guò)減小距離權(quán)值而得到定位精度;文獻(xiàn)[5]提出了利用RSSI測(cè)距技術(shù)代替DV-Hop算法中到錨節(jié)點(diǎn)一跳距離測(cè)量并采用2-D Hyperbolic算法代替三邊測(cè)量法;文獻(xiàn)[6]提出了一種最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)方法;文獻(xiàn)[7]提出在定位階段采用人工蜂群的智能算法進(jìn)行計(jì)算。以上改進(jìn)均是單方面對(duì)DV-Hop算法進(jìn)行改進(jìn),并沒(méi)有綜合考慮該定位算法的誤差因素。基于此,提出了一種綜合的改進(jìn)方法(CNDV-Hop)。首先簡(jiǎn)要描述了該方法的過(guò)程,然后對(duì)其定位誤差進(jìn)行了分析,最后從3個(gè)方面分別對(duì)DV-Hop算法進(jìn)行改進(jìn),并且與文獻(xiàn)[6]、文獻(xiàn)[7]進(jìn)行了仿真對(duì)比,在不明顯增加節(jié)點(diǎn)的計(jì)算和通信開(kāi)銷(xiāo)的前提下,CNDV-Hop具有更高的定位精度。

1 DV-Hop定位算法簡(jiǎn)介

DV-Hop算法是由Niculescu D等[8]人提出的,其基本思想是將未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)平均每跳距離和兩者之間跳數(shù)的乘積表示[9]。如圖1所示,在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,i,j,k3個(gè)節(jié)點(diǎn)為錨節(jié)點(diǎn),p為待求未知節(jié)點(diǎn)。算法過(guò)程如下:

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

首先,錨節(jié)點(diǎn)廣播自身信息到整個(gè)網(wǎng)絡(luò),其他節(jié)點(diǎn)能夠接收到其ID、跳數(shù)、坐標(biāo)信息。錨節(jié)點(diǎn)根據(jù)其接收到其他錨節(jié)點(diǎn)的信息計(jì)算出自身的平均跳距AHD

(1)

最后,當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或者更多與錨節(jié)點(diǎn)的距離時(shí),執(zhí)行三邊定位法或最大似然估計(jì)法求解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)[10]。

2 DV-Hop誤差分析

DV-Hop算法定位誤差較大有以下幾個(gè)原因:

①平均每跳距離

節(jié)點(diǎn)間的估計(jì)距離采用的是平均每跳距離乘以?xún)烧咧g的跳數(shù)表示,未知節(jié)點(diǎn)將最先接收到的錨節(jié)點(diǎn)平均跳距信息作為其平均跳距,然而,WSN網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布,僅根據(jù)單個(gè)錨節(jié)點(diǎn)的平均跳距并不能代表整個(gè)網(wǎng)絡(luò)的平均跳距,因此,定位精度會(huì)受到平均每跳距離值的影響。

②跳數(shù)信息

DV-Hop算法測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離是通過(guò)跳數(shù)與平均跳距的乘積計(jì)算的,在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)洵h(huán)境下,當(dāng)接收到不合理的跳數(shù)值后,不僅對(duì)平均跳距有直接的影響,而且會(huì)帶來(lái)累積誤差,節(jié)點(diǎn)跳數(shù)越多,累積誤差越大。

③定位計(jì)算方法

當(dāng)平均跳距和跳數(shù)信息存在誤差時(shí),而兩者之間的乘積d也會(huì)帶來(lái)很大的誤差。另外,在仿真過(guò)程中發(fā)現(xiàn),當(dāng)ATA為病態(tài)矩陣時(shí),通過(guò)多邊定位法所估計(jì)出的未知節(jié)點(diǎn)坐標(biāo)不僅誤差很大,而且定位精度的穩(wěn)定性較差,有時(shí)甚至得出錯(cuò)誤的結(jié)果。

3 CNDV-Hop定位算法

本節(jié)中,在不明顯增加網(wǎng)絡(luò)通信量、硬件開(kāi)銷(xiāo),不改變DV-Hop算法過(guò)程的條件下,本文對(duì)平均跳距、跳數(shù)和定位估計(jì)3個(gè)因素帶來(lái)的誤差進(jìn)行了改進(jìn)。

3.1 跳數(shù)優(yōu)化

在隨機(jī)的WSN中,節(jié)點(diǎn)跳數(shù)越多,對(duì)距離進(jìn)行估計(jì)產(chǎn)生的誤差就越大。本文首先設(shè)定跳數(shù)閾值δ,當(dāng)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳數(shù)大于δ時(shí),未知節(jié)點(diǎn)舍棄該錨節(jié)點(diǎn)的信息,δ通過(guò)多次仿真得到經(jīng)驗(yàn)值。然而,在WSN的定位計(jì)算中,錨節(jié)點(diǎn)的信息至關(guān)重要,當(dāng)能夠通信的錨節(jié)點(diǎn)較少或者小于3個(gè)時(shí)會(huì)導(dǎo)致定位精度過(guò)低甚至無(wú)法定位。因此要選擇合適的δ,其相關(guān)因素包括:錨節(jié)點(diǎn)比例、通信半徑、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)范圍等,具體可參考表1。

表1 跳數(shù)和平均跳距改進(jìn)對(duì)精度的影響

3.2 平均跳距的校正

從平均跳距的誤差分析和3.1節(jié)可知,較為合理的錨節(jié)點(diǎn)數(shù)量參與定位能夠提高定位精度,故提出綜合多個(gè)錨節(jié)點(diǎn)的平均跳距進(jìn)行改進(jìn)。假設(shè)通過(guò)跳數(shù)閾值δ限制后,未知節(jié)點(diǎn)能夠與mδ個(gè)錨節(jié)點(diǎn)進(jìn)行通信,結(jié)合式(1),則mδ個(gè)錨節(jié)點(diǎn)的平均跳距值為:

(2)

結(jié)合式(2),改進(jìn)后的錨節(jié)點(diǎn)i的平均跳距計(jì)算公式如下:

(3)

針對(duì)跳數(shù)閾值與平均跳距校正的合理性,進(jìn)行了如下仿真,設(shè)置無(wú)線(xiàn)傳感器網(wǎng)絡(luò)區(qū)域?yàn)?00×100,錨節(jié)點(diǎn)比例為20%。通信半徑R變化時(shí),跳數(shù)閾值的設(shè)定與平均跳距的校正給整個(gè)網(wǎng)絡(luò)定位精度帶來(lái)的影響。hm表示跳數(shù)最大值,APδ表示設(shè)置跳數(shù)閾值后定位精度提高百分比,AP?表示平均跳距校正后定位精度提高百分比。

3.3 基于擬牛頓法優(yōu)化求精

由DV-Hop誤差分析可知,多邊定位的誤差較大[11]。故本文提出采用最小二乘法和無(wú)約束擬牛頓法[12]相結(jié)合的算法求解未知節(jié)點(diǎn)的估計(jì)坐標(biāo),首先通過(guò)最小二乘法獲得未知節(jié)點(diǎn)的估計(jì)坐標(biāo),然后把估計(jì)坐標(biāo)作為擬牛頓算法的初值,進(jìn)一步對(duì)未知節(jié)點(diǎn)坐標(biāo)迭代優(yōu)化。

假設(shè)待求未知節(jié)點(diǎn)p坐標(biāo)為(x,y),第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)記為(xi,yi),節(jié)點(diǎn)p到錨節(jié)點(diǎn)i的距離記為di。若WSN中有m個(gè)錨節(jié)點(diǎn)能夠與未知節(jié)點(diǎn)p通信,則未知節(jié)點(diǎn)p的坐標(biāo)可以根據(jù)式(4)方程組估計(jì)得出。

(4)

上述方程組可轉(zhuǎn)換成AX=b的形式,通過(guò)最小二乘法解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)為:

X=(ATA)-1ATb

(5)

將式(4)轉(zhuǎn)化為求非線(xiàn)性最小二乘優(yōu)化的問(wèn)題,即:

(6)

式中,xi,yi分別為錨節(jié)點(diǎn)i的橫坐標(biāo)和縱坐標(biāo),di為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)i的距離。對(duì)于最優(yōu)化求解問(wèn)題,目的就是求出目標(biāo)函數(shù)f(x,y),x∈R+且y∈R+的最優(yōu)解X*(x*,y*)。我們知道當(dāng)f(x,y)在X*處取得局部極小值時(shí),需滿(mǎn)足:

(7)

3.4CNDV-Hop算法實(shí)現(xiàn)步驟

CNDV-Hop算法通過(guò)對(duì)跳數(shù)閾值設(shè)定、平均跳距校正,同時(shí)將擬牛頓算法引入,克服了DV-Hop算法定位誤差較大的缺點(diǎn)。其具體實(shí)現(xiàn)步驟如下:

第1步 網(wǎng)絡(luò)初始化及仿真變量說(shuō)明。

BorderLength:WSN區(qū)域邊長(zhǎng)

NodeAmount:節(jié)點(diǎn)總數(shù)

SimulationTimes:仿真次數(shù)

AnchorAmount:錨節(jié)點(diǎn)數(shù)

UNAmount:未知節(jié)點(diǎn)數(shù)

Hopsthreshold:跳數(shù)閾值

R:節(jié)點(diǎn)通信半徑

gxmax:迭代次數(shù)

h(i,j):跳數(shù)矩陣

Anchor(2,AnchorAmount):錨節(jié)點(diǎn)坐標(biāo)矩陣

UN(2,UNAmount):未知節(jié)點(diǎn)實(shí)際坐標(biāo)矩陣

Dhop(AnchorAmount,1):錨節(jié)點(diǎn)平均跳距

第2步 錨節(jié)點(diǎn)發(fā)送自身信息至網(wǎng)絡(luò)中。

第3步 通過(guò)最短路徑法計(jì)算出節(jié)點(diǎn)間的跳數(shù),錨節(jié)點(diǎn)根據(jù)式(3)計(jì)算改進(jìn)后的平均跳距,未知節(jié)點(diǎn)保存其與錨節(jié)點(diǎn)間的最小跳數(shù)。

第4步 錨節(jié)點(diǎn)將改進(jìn)平均跳距發(fā)送至網(wǎng)絡(luò)中,設(shè)置跳數(shù)閾值,優(yōu)選后錨節(jié)點(diǎn)的跳數(shù)和平均跳距參與計(jì)算未知節(jié)點(diǎn)與各個(gè)錨節(jié)點(diǎn)的估計(jì)距離。

第5步 通過(guò)最小二乘法計(jì)算出未知節(jié)點(diǎn)的估計(jì)坐標(biāo),并將該坐標(biāo)作為擬牛頓法的初值X(0),對(duì)結(jié)果進(jìn)行求精。

第6步 根據(jù)式(8)、式(9)、式(10)對(duì)該算法的定位精度進(jìn)行評(píng)價(jià)。

4 仿真與結(jié)果

4.1 仿真環(huán)境及評(píng)估方法

為了驗(yàn)證算法的性能,本文利用MATLAB 2010b平臺(tái)對(duì)CNDV-Hop算法分析,并同近兩年DV-Hop改進(jìn)方法進(jìn)行對(duì)比。將文獻(xiàn)[6]所述方法記為ORDV-Hop,文獻(xiàn)[7]所述方法記為ABDV-Hop。仿真環(huán)境設(shè)置:WSN區(qū)域大小為100 m×100 m,節(jié)點(diǎn)數(shù)目為100個(gè),SimulationTimes為100,迭代次數(shù)gxmax為20。仿真相關(guān)公式定義如下:

(8)

式中,N為未知節(jié)點(diǎn)的個(gè)數(shù),K為仿真次數(shù),取100。

②歸一化的平均定位誤差(NAE)為

NAE=AE/R

(9)

③算法的性能評(píng)價(jià),通常使用均方根(root mean square)作為算法性能的評(píng)價(jià)指標(biāo),歸一化均方根誤差(NRMSE)為:

(10)

式中,e(i)為估計(jì)坐標(biāo),r(i)為實(shí)際坐標(biāo),N為未知節(jié)點(diǎn)數(shù)目,R通信半徑。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)分布

4.2 仿真結(jié)果分析

圖2仿真了網(wǎng)絡(luò)的節(jié)點(diǎn)分布,錨節(jié)點(diǎn)比例為20%,其中紅色為錨節(jié)點(diǎn),黑色為信標(biāo)節(jié)點(diǎn)。

圖3、圖4中分別仿真了傳統(tǒng)DV-Hop算法與CNDV-Hop算法未知節(jié)點(diǎn)的實(shí)際位置與估計(jì)位置,設(shè)置通信半徑為30,錨節(jié)點(diǎn)比例為20%,跳數(shù)閾值為4。從兩圖中可以看出,改進(jìn)后的定位精度明顯比DV-Hop算法精度高的多。

圖3 DV-Hop算法實(shí)際位置與估計(jì)位置誤差

圖4 CNDV-Hop算法實(shí)際位置與估計(jì)位置誤差

圖5中仿真了4種定位算法錨節(jié)點(diǎn)比例與歸一化平均定位誤差的關(guān)系,設(shè)置通信半徑為30,跳數(shù)閾值為4。從圖中可以看出CNDV-Hop算法比現(xiàn)有改進(jìn)算法具有更低的定位誤差,比傳統(tǒng)DV-Hop算法提高了約40%的定位精度。

圖5 歸一化平均定位誤差與錨節(jié)點(diǎn)比例之間的關(guān)系

圖6 歸一化均方根誤差與通信半徑之間的關(guān)系

圖6中仿真了4種定位算法通信半徑與歸一化均方根誤差的關(guān)系,設(shè)置錨節(jié)點(diǎn)比例為20%,跳數(shù)閾值隨通信半徑不同,部分設(shè)置可參考第1步。從圖中可以看出CNDV-Hop算法定位精度更高、穩(wěn)定性更強(qiáng)。

5 結(jié)論

針對(duì)傳統(tǒng)的DV-Hop定位算法定位精度不高的問(wèn)題,本文提出了一種基于跳距修正的WSN擬牛頓迭代定位算法。改進(jìn)后的算法主要是從設(shè)定跳數(shù)閾值、平均跳距校正、對(duì)估計(jì)坐標(biāo)進(jìn)行迭代優(yōu)化來(lái)進(jìn)行改進(jìn),從仿真結(jié)果可以看出,CNDV-Hop算法使得定位的精度和穩(wěn)定性都有所提高,并且明顯降低了WSN的定位誤差,該算法并沒(méi)有改變傳統(tǒng)DV-Hop算法的定位過(guò)程,且無(wú)需額外的硬件支持,是一種理想的與距離無(wú)關(guān)的定位算法。

[1] Jennifer Yick,Biswanath Mukherjee,Dipak Ghosal.Wireless Sensor Network Survey[J].Computer Networks,2008,52:2292-2330.

[2]劉運(yùn)杰,金明錄,崔承毅.基于RSSI的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)校正加權(quán)質(zhì)心定位算法[J].傳感技術(shù)學(xué)報(bào),2010,23(5):717-721.

[3]江禹生,馮硯毫.一種新的DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2011,23(12):1815-1818.

[4]Li Jian,Zhang Jianmin.A Weighted DV-Hop Localization Scheme for Wireless Sensor Networks[C]//Proc of the Eighth IEEE Inter-national Conference on Embedded Computing and IEEE Interna-tional Conference on Scalable Computing and Communications,June,2009:269-272.

[5]劉衍珩,劉炳日,孫大洋,等.WSN中一種DV-Hop定位精度改進(jìn)算法[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2010,40(5):763-768.

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

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

[8]Niculescu D,Nath B.Ad Hoc Positioning System(APS)Using AOA[C]//Proceedings of the IEEE Infocom 2003.Francisco(Canada),3:1734-1743.

[9]Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems,2003,22(1-4):267-280.

[10]石為人,賈傳江,梁煥煥.一種改進(jìn)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2011,24(1):83-87.

[11]嵇瑋瑋,劉中.DV-Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報(bào),2008,30(4):970-974.

[12]陳蘭平,焦寶聰.非凸無(wú)約束優(yōu)化問(wèn)題的廣義擬牛頓法的全局收斂性[J].應(yīng)用數(shù)學(xué),2005,18(4):573-579.

喬欣(1988-),女,碩士研究生,主要研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位與ZigBee通信技術(shù);

丁恩杰(1962-),男,教授,博士,博士生導(dǎo)師,主要研究方向?yàn)榫聼o(wú)線(xiàn)傳感器網(wǎng)絡(luò)與礦山物聯(lián)網(wǎng),enjied@cumt.edu.cn。

ModifyingAverageHoppingDistancesBasedIterativeAlgorithmforQuasi-NewtoninWSN*

QIAOXin1,2,3,CHANGFei1,2,3,DingEnjie1,2,3*,WANGTao1,2,3

(1.CUMT-IoT Perception Mine Research Center,Xuzhou Jiangsu 221008,China;2.The National and Local Joint Engineering Laboratory of Internet Application Technology on Mine,Xuzhou Jiangsu 221008,China;3.School of Information and Electrical Engineering CUMT,Xuzhou Jiangsu 221008,China)

This paper provided with one modifying average hopping distances based iterative algorithm for quasi-newton in WSN.It put forward improvement based on analysis DV-Hop algorithm progress and source of error:firstly,setting hop threshold,then optimizing anchor nodes;secondly,revising nodes hopping distance with new method and calculating distance between nodes by utilizing adjusted value of the corresponding anchor nodes hopping distances;finally,iterative optimizing least square solution of unknown node coordinates by quasi-newton method.Simulation result shows that the improved algorithm presented in this paper can effectively reduce the influence which evaluated error on location accuracy,and this algorithm is better than the existing improved DV-hop algorithm in precision.

hop count threshold;DV-Hop location algorithm;average hop distance;quasi-newton method

項(xiàng)目來(lái)源:國(guó)家科技支撐計(jì)劃項(xiàng)目(2012BAH12B01,2012BAH12B02)

2014-04-07修改日期:2014-05-14

10.3969/j.issn.1004-1699.2014.06.017

TP393

:A

:1004-1699(2014)06-0797-05