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

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

?

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

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

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

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

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

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

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

1 DV-Hop定位算法簡介

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個節(jié)點(diǎn)為錨節(jié)點(diǎn),p為待求未知節(jié)點(diǎn)。算法過程如下:

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

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

(1)

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

2 DV-Hop誤差分析

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

①平均每跳距離

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

②跳數(shù)信息

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

③定位計算方法

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

3 CNDV-Hop定位算法

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

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

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

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

3.2 平均跳距的校正

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

(2)

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

(3)

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

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

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

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

(4)

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

X=(ATA)-1ATb

(5)

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

(6)

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

(7)

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

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

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

BorderLength:WSN區(qū)域邊長

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)實際坐標(biāo)矩陣

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

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

第3步 通過最短路徑法計算出節(jié)點(diǎn)間的跳數(shù),錨節(jié)點(diǎn)根據(jù)式(3)計算改進(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ù)和平均跳距參與計算未知節(jié)點(diǎn)與各個錨節(jié)點(diǎn)的估計距離。

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

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

4 仿真與結(jié)果

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

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

(8)

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

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

NAE=AE/R

(9)

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

(10)

式中,e(i)為估計坐標(biāo),r(i)為實際坐標(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è)置通信半徑為30,錨節(jié)點(diǎn)比例為20%,跳數(shù)閾值為4。從兩圖中可以看出,改進(jìn)后的定位精度明顯比DV-Hop算法精度高的多。

圖3 DV-Hop算法實際位置與估計位置誤差

圖4 CNDV-Hop算法實際位置與估計位置誤差

圖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é)論

針對傳統(tǒng)的DV-Hop定位算法定位精度不高的問題,本文提出了一種基于跳距修正的WSN擬牛頓迭代定位算法。改進(jìn)后的算法主要是從設(shè)定跳數(shù)閾值、平均跳距校正、對估計坐標(biāo)進(jìn)行迭代優(yōu)化來進(jìn)行改進(jìn),從仿真結(jié)果可以看出,CNDV-Hop算法使得定位的精度和穩(wěn)定性都有所提高,并且明顯降低了WSN的定位誤差,該算法并沒有改變傳統(tǒng)DV-Hop算法的定位過程,且無需額外的硬件支持,是一種理想的與距離無關(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ǎng)絡(luò)校正加權(quán)質(zhì)心定位算法[J].傳感技術(shù)學(xué)報,2010,23(5):717-721.

[3]江禹生,馮硯毫.一種新的DV-Hop定位算法[J].傳感技術(shù)學(xué)報,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é)報(工學(xué)版),2010,40(5):763-768.

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

[7]李牧東,熊偉,梁青.基于人工蜂群改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報,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ǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報,2011,24(1):83-87.

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

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

喬欣(1988-),女,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)定位與ZigBee通信技術(shù);

丁恩杰(1962-),男,教授,博士,博士生導(dǎo)師,主要研究方向為井下無線傳感器網(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

項目來源:國家科技支撐計劃項目(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