WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)

任克強(qiáng),李亞杰(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

?

WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)

任克強(qiáng)*,李亞杰
(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

為降低傳統(tǒng)DV-Hop算法對未知節(jié)點(diǎn)估算距離的誤差,提升WSN中的未知節(jié)點(diǎn)定位精度,提出一種基于未知節(jié)點(diǎn)估算距離修正的DV-Hop改進(jìn)算法。該改進(jìn)算法首先對節(jié)點(diǎn)的平均每跳距離進(jìn)行修正,并根據(jù)節(jié)點(diǎn)分布和節(jié)點(diǎn)間鄰居關(guān)系的特點(diǎn)引入節(jié)點(diǎn)遠(yuǎn)離度的概念,以區(qū)分未知節(jié)點(diǎn)和鄰居錨節(jié)點(diǎn)的距離,降低估算距離的誤差;然后對最小二乘法的誤差進(jìn)行修正,并利用鄰居節(jié)點(diǎn)的通信范圍限制關(guān)系對未知節(jié)點(diǎn)估算坐標(biāo)的誤差進(jìn)行修正,以進(jìn)一步減小未知節(jié)點(diǎn)的定位誤差。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)DV-Hop算法及相關(guān)文獻(xiàn)相比,改進(jìn)算法可以有效減小未知節(jié)點(diǎn)估算距離的誤差,提升未知節(jié)點(diǎn)定位的精度。

無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;DV-Hop算法;估算距離;誤差修正

在無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)中,許多應(yīng)用都依賴傳感器的自我定位,如海水監(jiān)測、交通控制、地質(zhì)勘測、抗震救災(zāi)等,這取決于準(zhǔn)確獲取傳感器節(jié)點(diǎn)的位置信息[1]。獲取WSN中節(jié)點(diǎn)位置坐標(biāo)的算法依據(jù)是否需要測量節(jié)點(diǎn)之間的相互距離可分類成基于測距和無需測距的定位算法[2];在低成本和低能耗等要求約束下,后者不依賴特殊硬件,相比于前者更具有優(yōu)勢[3]。

DV-Hop定位算法是一種廣泛應(yīng)用的無需測距定位算法,但當(dāng)WSN中傳感器節(jié)點(diǎn)分布不均勻和不規(guī)則時(shí),DV-Hop算法存在定位誤差較大的缺陷[4]。為了使定位的結(jié)果更加準(zhǔn)確,相關(guān)研究者分別對其進(jìn)行了不同程度的改進(jìn)。文獻(xiàn)[5]通過引入距離矯正因子的概念以修正未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離,使其更接近實(shí)際值,達(dá)到了減小定位誤差的目的。文獻(xiàn)[6]根據(jù)跳數(shù)閾值選擇合理的平均跳距來估計(jì)距離,同時(shí)利用質(zhì)心算法和最小二乘法綜合估計(jì)定位坐標(biāo),有效改善了定位精度。文獻(xiàn)[7]采用多個節(jié)點(diǎn)通信半徑值進(jìn)行多次節(jié)點(diǎn)信息廣播,精確了未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)信息,降低了定位誤差,但增加了節(jié)點(diǎn)間通信的開銷。文獻(xiàn)[8]將網(wǎng)絡(luò)中全部錨節(jié)點(diǎn)平均跳距最大值與最小值的平均值作為全網(wǎng)平均跳距,最后通過細(xì)菌覓食算法(BFO)來定位未知節(jié)點(diǎn),有效地提高了傳感器節(jié)點(diǎn)分布不規(guī)則時(shí)的定位精度。文獻(xiàn)[9]通過距離三角不等式來約束多跳距離誤差,并采用加權(quán)雙曲線法來代替最小二乘法計(jì)算坐標(biāo),在一定程度上提升了定位準(zhǔn)確度,但使用了額外的硬件設(shè)施。文獻(xiàn)[10]使用RSSI測距模型并對傳感器節(jié)點(diǎn)進(jìn)行限跳處理,然后對錨節(jié)點(diǎn)優(yōu)化組合,最后采用質(zhì)心估算法定位未知節(jié)點(diǎn)坐標(biāo),在減小定位誤差的同時(shí)有效地減小了節(jié)點(diǎn)間通信信息量,但限跳會導(dǎo)致一些待定位節(jié)點(diǎn)因不能與錨節(jié)點(diǎn)通信而無法得到其位置坐標(biāo)。文獻(xiàn)[11]通過對誤差距離加權(quán)與修正,選擇合理的跳段距離并使用遺傳算法計(jì)算未知節(jié)點(diǎn)位置,使定位結(jié)果更加準(zhǔn)確。文獻(xiàn)[12]提出一種新的平均跳距求解方法,首先未知節(jié)點(diǎn)獲取所有鄰居錨節(jié)點(diǎn)的平均跳距,通過該跳距求出鄰居錨節(jié)點(diǎn)間相互距離并與實(shí)際值比較,引入百分比誤差作為加權(quán)系數(shù)的參考依據(jù)來計(jì)算未知節(jié)點(diǎn)的平均跳距,提高了定位性能。

針對傳統(tǒng)DV-Hop算法在隨機(jī)網(wǎng)絡(luò)中表現(xiàn)出的局限性,本文對其不合理的方面進(jìn)行了分析研究和改進(jìn),提出一種基于未知節(jié)點(diǎn)估算距離修正的改進(jìn)算法,使得節(jié)點(diǎn)間估算距離更接近實(shí)際值,以提升傳統(tǒng)DV-Hop算法的定位精度。

1 DV-Hop算法

DV-Hop算法主要包括以下3個步驟[13]:

①計(jì)算節(jié)點(diǎn)間最小跳數(shù)

相鄰節(jié)點(diǎn)間互相交換信息,使得網(wǎng)絡(luò)中所有節(jié)點(diǎn)均取得每個錨節(jié)點(diǎn)的坐標(biāo)和與其間的最小跳數(shù)。

②計(jì)算節(jié)點(diǎn)間跳段距離

(1)

(2)

式中:Hopsizei為錨節(jié)點(diǎn)i的平均每跳距離,dij和hij分別為錨節(jié)點(diǎn)i、j之間的距離值和跳數(shù),(xi,yi)和(xj,yj)分別為錨節(jié)點(diǎn)i、j的位置坐標(biāo)。

錨節(jié)點(diǎn)將計(jì)算出的平均每跳距離作為校正值向網(wǎng)絡(luò)廣播,每一個未知節(jié)點(diǎn)只保留最先獲得的校正值,最后將校正值和到其他錨節(jié)點(diǎn)的跳數(shù)相乘得到該未知節(jié)點(diǎn)到其他錨節(jié)點(diǎn)的跳段距離。未知節(jié)點(diǎn)k和錨節(jié)點(diǎn)j之間的跳段距離dkj:

dkj=Hopsizei×hkj

(3)

式中:Hopsizei為k最先保留的校正值,hkj為k、j間的跳數(shù)。

③計(jì)算未知節(jié)點(diǎn)坐標(biāo)

當(dāng)待定位節(jié)點(diǎn)通過式(3)取得不少于3個跳段距離值時(shí),其位置坐標(biāo)可以通過極大似然估計(jì)法來求解。

如果待估算節(jié)點(diǎn)位置坐標(biāo)為(x,y),到錨節(jié)點(diǎn)i的估計(jì)距離為di,(i=1,2,…,n),i的位置坐標(biāo)為(xi,yi),(i=1,2,…,n),可得到方程組:

(4)

將式(4)中前(n-1)個等式分別與第n個等式相減可以得到AX=b形式的線性方程組,其中:

(5)

(6)

(7)

由最小二乘法,解得:

X=(ATA)-1ATb

(8)

2 DV-Hop算法分析與改進(jìn)

DV-Hop算法定位過程中,未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離并不是實(shí)際環(huán)境中兩點(diǎn)之間的距離,而是采用平均每跳距離與跳數(shù)相乘求出的跳段距離來估計(jì)的,平均每跳距離是根據(jù)錨節(jié)點(diǎn)的分布情況計(jì)算出的,因而導(dǎo)致在WSN節(jié)點(diǎn)分布不均勻和不規(guī)則時(shí),必然存在較大的定位誤差。因此,本文從平均每跳距離、未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的估算距離、最小二乘法引起的誤差以及未知節(jié)點(diǎn)定位坐標(biāo)值誤差4個方面對DV-Hop算法進(jìn)行了分析和修正改進(jìn)。

圖1 節(jié)點(diǎn)通信示意圖

2.1 平均每跳距離的修正

根據(jù)DV-Hop算法原理可知,為使得節(jié)點(diǎn)間跳數(shù)最小,節(jié)點(diǎn)在與相距較遠(yuǎn)的節(jié)點(diǎn)通信時(shí),會途經(jīng)靠近通信范圍邊沿的節(jié)點(diǎn)。例如在圖1中,A、B、C和D分別為WSN中的4個傳感器節(jié)點(diǎn),B、C均在A的最大通信半徑范圍內(nèi),為使得A與D之間通信時(shí)的跳數(shù)最小,A與D通信時(shí)則會途經(jīng)更靠近通信范圍邊沿的C,而不經(jīng)過B。

對于傳感器節(jié)點(diǎn)均勻分布的WSN環(huán)境,節(jié)點(diǎn)的一跳距離長度更接近于通信半徑的大小,由式⑴可知,平均跳距是由錨節(jié)點(diǎn)間實(shí)際距離總和除以其間跳數(shù)總和得出的,實(shí)際環(huán)境中節(jié)點(diǎn)隨機(jī)分布,若錨節(jié)點(diǎn)間相距過近,如圖1中節(jié)點(diǎn)A和B,則平均每跳距離值的計(jì)算誤差會偏大,進(jìn)而影響定位效果。為減少因錨節(jié)點(diǎn)相距過近而引起的誤差,對由式⑵計(jì)算的dij進(jìn)行以下修正:

(9)

2.2 未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的修正

在DV-Hop算法定位過程中,待定位節(jié)點(diǎn)與各個錨節(jié)點(diǎn)的估計(jì)距離是采取同一個平均跳距值乘以對應(yīng)的跳數(shù)得出的結(jié)果,這樣會造成一定的誤差[14]。在圖1中,設(shè)節(jié)點(diǎn)B、C、D是錨節(jié)點(diǎn),A是待定位節(jié)點(diǎn),則A到B、C都是一跳,則根據(jù)式(3)計(jì)算出的A分別到B、C的距離是相等的,但實(shí)際上是不相等的,若按照相等的距離進(jìn)行定位計(jì)算,顯然是不合理的,導(dǎo)致定位結(jié)果不準(zhǔn)確。另一方面,假定A的平均跳距值是從B獲得的,大小為HopsizeB,若此值存在較大誤差,則A到其他錨節(jié)點(diǎn)的估算距離值的誤差會隨著跳數(shù)的增加而被累積,且HopsizeB無法代表整個網(wǎng)絡(luò)的分布情況;例如在圖1中,在估算A與D的距離時(shí)采用HopsizeB,顯然忽視了D周圍的分布情況。

①未知節(jié)點(diǎn)與鄰居錨節(jié)點(diǎn)距離的修正

為了區(qū)分不同未知節(jié)點(diǎn)與同一個鄰居錨節(jié)點(diǎn)的估計(jì)距離,本文引入節(jié)點(diǎn)遠(yuǎn)離度的概念,用來表征未知節(jié)點(diǎn)與鄰居錨節(jié)點(diǎn)相離遠(yuǎn)近的程度:

(10)

式中:εik為未知節(jié)點(diǎn)k與其鄰居錨節(jié)點(diǎn)i的遠(yuǎn)離度,其值的大小和k、i間的距離正相關(guān);Seti和Setk分別為i和k的鄰居節(jié)點(diǎn)標(biāo)號集合,crad(Seti∪Setk)為Seti、Setk并集中所有元素個數(shù),crad(Seti∩Setk)為Seti、Setk交集中所有元素個數(shù)。

下面用圖2舉例,說明節(jié)點(diǎn)遠(yuǎn)離度的計(jì)算過程。A為錨節(jié)點(diǎn);B、C分別為節(jié)點(diǎn)A單跳范圍內(nèi)的未知節(jié)點(diǎn);粗實(shí)線大圓、細(xì)實(shí)線大圓和虛線大圓分別為節(jié)點(diǎn)A、B和C的單跳通信范圍;空心小圓圈為其它傳感器節(jié)點(diǎn)。A和B的鄰居節(jié)點(diǎn)標(biāo)號集合分別為SetA和SetB?？梢运愠?crad(SetA∪SetB)為21,crad(SetA∩SetB)為7,B與A的遠(yuǎn)離度εAB=21/7=3,C與A的遠(yuǎn)離度εAC=17/12≈1.42。遠(yuǎn)離度εAB>εAC說明B和A相離更遠(yuǎn),兩者的距離更接近通信半徑,C和A相離更近。

圖2 遠(yuǎn)離度計(jì)算說明圖

(11)

式中:εik為k與i的遠(yuǎn)離度,εimax為i所有鄰居節(jié)點(diǎn)與i的遠(yuǎn)離度最大值。

②未知節(jié)點(diǎn)與非鄰居錨節(jié)點(diǎn)距離的修正

(12)

式中:Hopsizei為k在DV-Hop算法第2)步獲取的校正值,Hopsizej為j的平均跳距,hkj為k到j(luò)的跳數(shù)。

2.3 最小二乘法誤差的修正

在利用最小二乘法求解過程中,將式(4)中前(n-1)個等式分別與第n個等式相減可得出式(6),從而式(6)中每一項(xiàng)均包含dn,若dn的值誤差偏大,則必然給最后的定位結(jié)果帶來一定的誤差[15]?？紤]到此過程中存在的問題,本文將式(4)中的n個等式重新按d1,d2,…,dn的值從大到小降序排列,使得第n個等式中dn的值最小,進(jìn)而降低式(6)中向量b的誤差,然后按式⑻求解得出定位坐標(biāo)。

為了便于分析比較,本文將通過以上改進(jìn)后的DV-Hop算法稱為本文算法1。

2.4 未知節(jié)點(diǎn)坐標(biāo)值誤差的修正

未知節(jié)點(diǎn)由本文算法1計(jì)算得出的坐標(biāo)X′與實(shí)際坐標(biāo)X相比仍然存在一定誤差,此誤差體現(xiàn)在未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離上,例如X′與X分別和每個錨節(jié)點(diǎn)相距遠(yuǎn)近程度是有差異的。為簡化計(jì)算量,只考慮跳數(shù)是否為1的差異,即節(jié)點(diǎn)是否為鄰居關(guān)系的差異,實(shí)際中節(jié)點(diǎn)應(yīng)滿足要求:對于具有鄰居關(guān)系的兩個節(jié)點(diǎn),節(jié)點(diǎn)間距離不超過通信半徑,相反,對于不具有鄰居關(guān)系的兩個節(jié)點(diǎn),節(jié)點(diǎn)間距離大于通信半徑[16],所以對X′為滿足實(shí)際情況進(jìn)行修正。

(13)

(14)

(15)

式中:(xj,yj)(j=1,2,…,n)為錨節(jié)點(diǎn)坐標(biāo),Lx和Ly分別為網(wǎng)絡(luò)區(qū)域橫坐標(biāo)和縱坐標(biāo)的最大值,對式⒂求解得到最后的修正位置坐標(biāo),稱為本文算法2。

未知節(jié)點(diǎn)k誤差修正的流程如圖3所示。

下面以圖4為例,說明未知節(jié)點(diǎn)k誤差的修正過程。圖中節(jié)點(diǎn)1、2、3和4均代表參與k定位計(jì)算的錨節(jié)點(diǎn),空心小圓代表k的真實(shí)位置,空心三角為本文算法1定位得出的估算位置,用k1表示,由式(13)可得,Dk=(-1,-1,1,1),-1表示k1和錨節(jié)點(diǎn)1、2不為鄰居關(guān)系,1表示k1和錨節(jié)點(diǎn)3、4為鄰居關(guān)系。由式(14)可得,Hk=(-1,1,-1,1),表示k實(shí)際位置和錨節(jié)點(diǎn)1、3不為鄰居關(guān)系,和錨節(jié)點(diǎn)2、4為鄰居關(guān)系。Dk≠Hk表明估算位置k1不夠準(zhǔn)確,與實(shí)際位置存在誤差,應(yīng)使其為滿足Hk所表示的關(guān)系進(jìn)行修正,即與錨節(jié)點(diǎn)1保持非鄰居關(guān)系不變,與錨節(jié)點(diǎn)4保持鄰居關(guān)系不變,同時(shí)離開錨節(jié)點(diǎn)3使它們不為鄰居關(guān)系,接近錨節(jié)點(diǎn)2使它們?yōu)猷従雨P(guān)系。滿足條件修正距離最小的點(diǎn)為圖中空心方框位置k2,即通過式(15)的計(jì)算會將k1位置坐標(biāo)修正到k2位置,達(dá)到減小定位誤差的目的。

圖3 未知節(jié)點(diǎn)k坐標(biāo)修正流程圖

圖4 未知節(jié)點(diǎn)k坐標(biāo)修正舉例

3 實(shí)驗(yàn)結(jié)果與分析

使用MATLABR2015b工具對DV-Hop算法、文獻(xiàn)[11]算法、本文算法1和本文算法2進(jìn)行實(shí)驗(yàn)仿真,并對實(shí)驗(yàn)結(jié)果進(jìn)行對比和分析。實(shí)驗(yàn)仿真環(huán)境:在100m×100m的WSN環(huán)境中任意安放100個節(jié)點(diǎn),包括錨節(jié)點(diǎn)和未知節(jié)點(diǎn),且錨節(jié)點(diǎn)數(shù)量+未知節(jié)點(diǎn)數(shù)量=100,節(jié)點(diǎn)通信半徑為R。

評價(jià)定位效果的標(biāo)準(zhǔn)為平均定位誤差error和相對定位誤差aerror:

(16)

aerror=error/R

(17)

圖5是通信半徑R=30m和R=35m時(shí)錨節(jié)點(diǎn)數(shù)目的變化對4種算法平均定位誤差影響的實(shí)驗(yàn)結(jié)果。從結(jié)果可以看到,4種算法在錨節(jié)點(diǎn)數(shù)量依次遞增且通信半徑不變的情況下,平均定位誤差都表現(xiàn)為遞減變化,剛開始下降幅度較大,以后下降逐漸趨于緩慢。本文算法1平均定位誤差在錨節(jié)點(diǎn)數(shù)量為5時(shí)和文獻(xiàn)[11]算法接近,以后隨著錨節(jié)點(diǎn)數(shù)量的增多均優(yōu)于文獻(xiàn)[11]算法;本文算法2是對本文算法1坐標(biāo)誤差修正的結(jié)果,從圖5中可以看到達(dá)到了進(jìn)一步減小誤差的效果。圖5(a)中錨節(jié)點(diǎn)數(shù)量為40時(shí),本文算法2平均定位誤差相比文獻(xiàn)[11]算法和DV-Hop算法分別下降約2.7m和5.4m;通過圖5(a)與圖5(b)對比可以觀察到,錨節(jié)點(diǎn)數(shù)量相同情況下,通信半徑從30m變大為35m會使4種算法的平均定位誤差都略有提升,原因在于通信半徑增大使得錨節(jié)點(diǎn)平均跳距增大,進(jìn)而使未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離和實(shí)際值偏差變大,影響定位效果;但隨著錨節(jié)點(diǎn)數(shù)量的增多,通信半徑增大對本文兩種算法的影響較小。

圖5 不同錨節(jié)點(diǎn)數(shù)量的平均定位誤差比較

圖6是通信半徑R=30m、R=35m和R=40m時(shí)錨節(jié)點(diǎn)數(shù)量的變化對4種算法相對定位誤差影響的實(shí)驗(yàn)結(jié)果。從結(jié)果可以看到,在通信半徑不變的情況下,4種算法的相對定位誤差和圖5變化趨勢一致,都表現(xiàn)為先快速下降而后緩慢下降。在錨節(jié)點(diǎn)數(shù)量為5情況下本文算法1的相對定位誤差與文獻(xiàn)[11]算法差別比較小,以后隨著錨節(jié)點(diǎn)數(shù)量遞增均優(yōu)于文獻(xiàn)[11]算法和DV-Hop算法。圖6(a)中本文算法2的定位性能相比文獻(xiàn)[11]算法和DV-Hop算法分別提升5.0%～9.7%和12.8%～18.6%;由圖6(a)、圖6(b)和圖6(c)對比可以看到,錨節(jié)點(diǎn)數(shù)量相同條件下,通信半徑增大會使4種算法相對定位誤差都表現(xiàn)出小幅度下降,這是因?yàn)橥ㄟ^式(17)計(jì)算平均相對誤差時(shí),通信半徑在分母,使得計(jì)算結(jié)果偏小。

圖6 不同錨節(jié)點(diǎn)數(shù)量的相對定位誤差比較

圖5和圖6表明本文算法的定位性能優(yōu)于文獻(xiàn)[11]算法和DV-Hop算法,這是由于本文通過計(jì)算遠(yuǎn)離度對未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離進(jìn)行修正,并依據(jù)節(jié)點(diǎn)鄰居關(guān)系對估算坐標(biāo)值進(jìn)一步修正,使其更接近實(shí)際值,相比于文獻(xiàn)[11]算法和DV-Hop算法,本文算法的定位性能得到了有效提升。

圖7是通信半徑R=40m、錨節(jié)點(diǎn)數(shù)量n=25時(shí)DV-Hop算法和本文算法2的每個未知節(jié)點(diǎn)的定位誤差。從圖7中可以看到,兩者定位誤差差距較大,DV-Hop算法在11.5m左右波動,而本文算法2在4.5m左右波動,且有30.7%節(jié)點(diǎn)的定位誤差在3m以內(nèi);因此,本文算法2不僅減小了定位誤差,且穩(wěn)定性也得到較好地提升。

圖7 未知節(jié)點(diǎn)的定位誤差比較圖

圖8 未知節(jié)點(diǎn)的實(shí)際位置與定位位置比較

圖8是R=50m、錨節(jié)點(diǎn)數(shù)量n=30時(shí)DV-Hop算法和本文算法2的每個未知節(jié)點(diǎn)的定位位置和實(shí)際位置,圖中黑色小圓點(diǎn)表示實(shí)際坐標(biāo)位置,空心小圓表示定位估計(jì)坐標(biāo)位置,且圖8(a)與圖8(b)中黑色小圓點(diǎn)坐標(biāo)位置相同。從圖8(a)中可以看到,DV-Hop算法存在一部分節(jié)點(diǎn)的估計(jì)坐標(biāo)位置超出了WSN節(jié)點(diǎn)部署區(qū)域范圍的情況,這使得這些節(jié)點(diǎn)的估計(jì)坐標(biāo)位置和實(shí)際位置距離相差過大,造成平均定位誤差偏大的結(jié)果;而從圖8(b)中可以看到,本文算法2不存在節(jié)點(diǎn)的定位位置超出WSN節(jié)點(diǎn)布署區(qū)域范圍的情況,這是由于式(15)的約束作用,保證了所有節(jié)點(diǎn)的定位位置均在WSN節(jié)點(diǎn)部署區(qū)域范圍內(nèi),而且相比DV-Hop算法顯著提升了總體定位效果。

4 結(jié)束語

針對在隨機(jī)分布網(wǎng)絡(luò)環(huán)境中傳統(tǒng)DV-Hop算法的局限性,對引起定位誤差的來源進(jìn)行研究和分析,提出一種改進(jìn)的DV-Hop算法。改進(jìn)算法從錨節(jié)點(diǎn)平均每跳距離的計(jì)算、未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的計(jì)算、最小二乘法求解未知節(jié)點(diǎn)坐標(biāo)以及坐標(biāo)修正4個方面對傳統(tǒng)DV-Hop算法進(jìn)行了改進(jìn),并在不同錨節(jié)點(diǎn)數(shù)量和不同節(jié)點(diǎn)通信半徑的WSN環(huán)境下進(jìn)行了算法定位性能比較實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,本文改進(jìn)算法的平均定位誤差和相對定位誤差均優(yōu)于傳統(tǒng)DV-Hop算法及相關(guān)文獻(xiàn),有效提升了DV-Hop算法的節(jié)點(diǎn)定位性能。如何進(jìn)一步減小未知節(jié)點(diǎn)定位位置與實(shí)際位置的誤差是后續(xù)研究的重點(diǎn)工作。

[1] Xu C X,Chen J Y. Research on the Improved DV-Hop Localization Algorithm in WSN[J]. International Journal of Smart Home,2015,9(4):157-162.

[2] Safa H. A Novel Localization Algorithm for Large Scale Wireless Sensor Networks[J]. Computer Communications,2014,45(3):32-46.

[3] 曹欲曉,嚴(yán)奎,徐金寶. 一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(3):424-429.

[4] Fang X. Improved DV-Hop Positioning Algorithm Based on Compensation Coefficient[J]. Journal of Software Engineering,2015,9(3):650-657.

[5] Wu L,Hou Z,Tan C,et al. Improved DV-Hop Localization Algorithm Based on Distance Correction of Anchor Nodes[J]. International Journal of Future Generation Communication and Networking,2016,9(10):269-278.

[6] 向滿天,王勝,楊友華. 基于閾值機(jī)制與距離校正的WSN改進(jìn)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(6):920-926.

[7] 劉士興,黃俊杰,劉宏銀,等. 基于多通信半徑的加權(quán)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(6):883-887.

[8] Zhao Q S,Hu Y L. An Improved DV-Hop Localisation Algorithm[J]. International Journal of Wireless and Mobile Computing,2016,10(1):20-25.

[9] 周玲,康志偉,何怡剛. 基于三角不等式的加權(quán)雙曲線定位DV-Hop算法[J]. 電子測量與儀器學(xué)報(bào),2013,27(5):389-395.

[10] 夏少波,鄒建梅,朱曉麗,等. 基于跳數(shù)區(qū)域劃分的DV-Hop改進(jìn)算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(7):964-969.

[11] 程超,錢志鴻,付彩欣,等. 一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J]. 電子與信息學(xué)報(bào),2015,37(10):2418-2423.

[12] Wang Y,Fang Z,Chen L. A New Type of Weighted DV-Hop Algorithm Based on Correction Factor in WSNs[J]. Journal of Communications,2014,9(9):699-705.

[13] Zhang W,Yang X,Song Q. DV-Hop Localization Algorithm Based on RSSI Correction[J]. Journal of Software Engineering,2015,9(1):188-194.

[14] Zhang J,Guo N,Li J. An Improved DV-Hop Localization Algorithm Based on the Node Deployment in Wireless Sensor Networks[J]. International Journal of Smart Home,2015,9(10):197-204.

[15] 朱敏,劉昊霖,張志宏,等. 一種基于DV-Hop改進(jìn)的無線傳感器網(wǎng)絡(luò)定位算法[J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2012,44(1):93-98.

[16] Shang F,Lan L,Dong M. Position Location Scheme Using Nonlinear Programming Based on RSSI and DV-Hop[J]. International Journal of Hybrid Information Technology,2015,8(5):1-10.

任克強(qiáng)(1959-),男,教授,碩士研究生導(dǎo)師,主要研究方向?yàn)閳D像與視頻處理、無線傳感器網(wǎng)絡(luò)、信息隱藏,jxrenkeqiang@163.com;

李亞杰(1992-),男,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。

Improvement of DV-Hop Node Localization Algorithm in WSN

REN Keqiang*,LI Yajie
(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

In order to reduce the estimation error of the traditional DV-Hop algorithm,an improved DV-Hop algorithm based on modification of estimation distance was proposed to enhance the localization accuracy of unknown nodes in WSN. Firstly,the improved algorithm modified average distance per hop for nodes,and degree of distance among notes was introduced according to the nodes distribution and the characteristics of neighbor relation between nodes,so as to distinguish the distance between unknown nodes and anchor nodes,and to reduce the error of the estimation distance. Then,the error of the least squares method was modified,and the constraint relationships of communication range between neighbor nodes were utilized to modify the error of the estimation coordinates for unknown nodes,which could further reduce the error of locating unknown nodes. The experimental results show that compared with the traditional DV-Hop algorithm and the related reference,the improved algorithm can effectively reduce the error of the estimation distance for unknown nodes,and improve the localization accuracy of unknown nodes.

wireless sensor network;node localization;DV-Hop algorithm;estimation distance;error modification

2016-07-26 修改日期:2016-12-05

TP393

A

1004-1699(2017)04-0611-07

C:6150P

10.3969/j.issn.1004-1699.2017.04.022