任克強,鄧 浪

(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

無線傳感器網(wǎng)絡(luò)(Wireless sensor Network,WSN)中,采用多個節(jié)點隨機分布,自組織一個多跳網(wǎng)絡(luò),部署在需要監(jiān)測的某些特定區(qū)域,采集與處理監(jiān)測到的信息,同時將處理后的信息發(fā)送給監(jiān)測人員[1]。WSN作為物理世界與數(shù)字世界的橋梁,在目標(biāo)追蹤、環(huán)境監(jiān)測、軍事偵察甚至在能量管理中已被廣泛的應(yīng)用[2]。在實際的應(yīng)用中,缺少位置信息的感知數(shù)據(jù)是沒有意義的[3]。因此,了解目標(biāo)的位置信息對許多環(huán)境感知的應(yīng)用十分重要,節(jié)點定位技術(shù)也成為WSN研究的關(guān)鍵技術(shù)之一。

在WSN現(xiàn)有的定位機制中,根據(jù)測量距離方式的不同可以劃分成基于測距(Range-based)算法和非測距(Range-free)算法兩個類別[4]。獲取角度或距離信息對于Range-based算法來說十分重要,所以對整個傳感器網(wǎng)絡(luò)的硬件配置要求更為嚴(yán)格,同時也具有更好的定位精確度。Range-based算法主要有:AOA(Angle of Arrival)、TOA(Time of Arrival)、TDOA(Time Difference of Arrival)和RSSI(Received Signal Strength Indicator)等[5]。與Range-based算法相比較,從硬件成本和實現(xiàn)復(fù)雜度等方面考慮,Range-free算法實現(xiàn)簡單,成本較低,但精度稍有不足。目前,Range-free算法主要有:質(zhì)心定位(Centroid)、凸規(guī)劃定位(Convex Programming)、DV-Hop(Distance-Vector-Hop)、MDS-MAP和APIT(Approximate PIT Test)等算法[6]。

作為Range-free算法的代表之一,DV-Hop算法應(yīng)用廣泛、易于擴展并且受限制的條件更少,能做到符合大多數(shù)應(yīng)用場景所要求的定位效果,所以得到了廣泛應(yīng)用與研究[7]。針對DV-Hop自身的一些不足之處,國內(nèi)外相關(guān)學(xué)者從諸多方面提出了相應(yīng)的改進(jìn)方法。文獻(xiàn)[8]對多種Range-free定位技術(shù)進(jìn)行了評估,采用基于粒子群(PSO)的DV-Hop算法,與傳統(tǒng)DV-Hop算法相比具有更好的定位精度和魯棒性,雖然PSO算法收斂速度快,但是容易陷入局部最優(yōu)并且不適合用于處理離散的優(yōu)化問題。文獻(xiàn)[9]針對計算過程中容易產(chǎn)生誤差積累的最小二乘法提出改進(jìn)方案,并對錨節(jié)點跳距進(jìn)行權(quán)值處理,通過改善平均跳距的相對誤差值,提高定位的準(zhǔn)確率,但在增加了定位準(zhǔn)確率的同時,加大了全網(wǎng)的計算量。文獻(xiàn)[10]采用混合加權(quán)定位的方法,通過對質(zhì)心算法進(jìn)行兩次加權(quán)以獲取更好的定位精度,相較于其他混合算法,該算法在耗能控制和計算量方面具有一定優(yōu)勢。文獻(xiàn)[11]在對誤差距離權(quán)值處理的基礎(chǔ)上,對網(wǎng)絡(luò)中節(jié)點位置關(guān)系進(jìn)行判斷,利用距離未知節(jié)點最近的3個錨節(jié)點的跳距信息通過歸一化加權(quán)的方式計算未知節(jié)點的估算跳距,同時針對節(jié)點的坐標(biāo)估算,采用改進(jìn)的遺傳算法進(jìn)行處理,但采用遺傳算法需要考慮到早熟收斂的問題,進(jìn)化至后期時局部搜索的能力較弱。文獻(xiàn)[12]提出基于PSO-BP傳感器位置確定的改進(jìn)策略,通過利用改進(jìn)后的卡爾曼算法對RSSI值進(jìn)行相關(guān)優(yōu)化,目的是減少噪聲與誤差,最后優(yōu)化閾值與權(quán)值,該算法具備獲取全局最優(yōu)值同時避免局部最優(yōu)值出現(xiàn)的能力,有效的改善神經(jīng)網(wǎng)定位算法的效果。文獻(xiàn)[13]首先對DV-Hop的洪泛機制進(jìn)行改進(jìn),獲取最近錨節(jié)點的平均跳距參與估算,然后通過改進(jìn)的差分校正算法減少跳距的累積誤差,最后對整個預(yù)測的區(qū)域使用粒子濾波,提升估計節(jié)點坐標(biāo)的準(zhǔn)確率且通信開銷相對較低。

針對DV-Hop算法跳數(shù)不合理及跳距估算階段誤差累積的問題,本文對DV-Hop算法的跳數(shù)及跳距兩個方面進(jìn)行優(yōu)化與修正,提出了一種基于全局跳數(shù)優(yōu)化與跳距誤差修正的DV-Hop改進(jìn)算法,采用通信半徑等相關(guān)參數(shù)優(yōu)化跳數(shù)的取值,使跳數(shù)趨于合理,通信雙方之間估算跳距的誤差進(jìn)一步減少,以提升定位精度。

1 DV-Hop算法及定位誤差

1.1 DV-Hop算法

DV-Hop算法是基于矢量路由的經(jīng)典Range-free算法之一,定位過程主要包含3個基本步驟[14]:

①節(jié)點間跳數(shù)的估算

所有錨節(jié)點將位置與跳數(shù)數(shù)據(jù)發(fā)送給可通信節(jié)點,接收節(jié)點收集到該數(shù)據(jù)后,保留該數(shù)據(jù)并使跳數(shù)加1,繼續(xù)轉(zhuǎn)發(fā)至未獲得節(jié)點數(shù)據(jù)的目標(biāo),直至整個網(wǎng)絡(luò)中相對距離最近的錨節(jié)點都能獲取到的對方位置和跳數(shù)數(shù)據(jù)。

②節(jié)點間跳距的估算

網(wǎng)絡(luò)中全部的錨節(jié)點獲得了最近錨節(jié)點的最小跳數(shù)值與節(jié)點位置信息,利用獲得的數(shù)據(jù)通過式(1)對節(jié)點平均每跳距離進(jìn)行估算:

(1)

式中:(xi,yi)與(xj,yj)為錨節(jié)點i、j的實際位置坐標(biāo),hij為錨節(jié)點i、j之間的最小跳數(shù),Hopsizei為錨節(jié)點i平均每跳距離。

通過式(2)計算錨節(jié)點i、j之間的估算距離dij:

dij=Hopsizei×hij

(2)

③未知節(jié)點坐標(biāo)的估算

利用節(jié)點距離和跳數(shù)的估算數(shù)據(jù),采取極大似然法估算出未知節(jié)點的坐標(biāo)。

1.2 定位誤差

DV-Hop算法中網(wǎng)絡(luò)連通度和錨節(jié)點間距離信息對未知節(jié)點位置估算十分重要[15],定位過程中產(chǎn)生誤差的原因主要有:

①DV-Hop算法的定位精度很大程度上取決于平均跳距的估算值是否合理,單一的錨節(jié)點估算出的平均跳距不能完全代表整個網(wǎng)絡(luò)的跳距情況,并且多跳情況下,未知節(jié)點與錨節(jié)點的估算距離并不是按照直線計算,節(jié)點密度低的區(qū)域節(jié)點的折線率增大,距離誤差將進(jìn)一步累積,對定位效果產(chǎn)生影響。

②網(wǎng)絡(luò)中隨機播撒的WSN節(jié)點拓?fù)浣Y(jié)構(gòu)往往不規(guī)則,區(qū)域內(nèi)節(jié)點密集程度也就存在差異,不同節(jié)點密度估算出的節(jié)點間跳數(shù)信息以及平均跳距存在一定的誤差。根據(jù)DV-Hop算法的特性,錨節(jié)點通信范圍內(nèi)可通信的節(jié)點均被視為單跳節(jié)點,當(dāng)大量單跳節(jié)點參與距離估算,平均跳距就不能真實的反映網(wǎng)絡(luò)中各節(jié)點間的距離,導(dǎo)致估算距離與真實距離之間存在差異,降低定位精度。

因此,本文從節(jié)點之間的跳數(shù)以及節(jié)點之間估算距離對DV-Hop算法進(jìn)行修正。

2 本文算法

2.1 節(jié)點間跳數(shù)修正

DV-Hop算法估算節(jié)點間跳數(shù)時,通信區(qū)域內(nèi)的所有鄰居節(jié)點都被視作1跳。如圖1所示,B、C、D和E都為節(jié)點A的單跳節(jié)點,但對應(yīng)的真實距離卻各不相同,如果這類節(jié)點都按照DV-Hop算法處理,會產(chǎn)生較大的定位誤差。針對此類情況,本文引入節(jié)點偏差系數(shù)、節(jié)點相對最佳跳數(shù)以及跳數(shù)差值修正系數(shù),并與影響跳數(shù)的相關(guān)參數(shù)相結(jié)合,提出一種全局節(jié)點跳數(shù)優(yōu)化的方法。

圖1 通信范圍內(nèi)單跳誤差

對節(jié)點的通信區(qū)域內(nèi)單跳的數(shù)值進(jìn)行限制,將節(jié)點i、j之間的真實距離dij與通信半徑R之比定義為相對最佳跳數(shù)Hij:

Hij=dij/R

(3)

比較估算跳數(shù)hij和相對最佳跳數(shù)Hij二者的差值,通過式(4)定義偏差系數(shù)σij:

σij=(hij-Hij)/hij

(4)

偏差系數(shù)σij能夠體現(xiàn)互相通信的錨節(jié)點間估算跳數(shù)hij與相對最佳跳數(shù)Hij存在的差異情況。σij越大,標(biāo)志著二者之間存在更大的偏差。在通信半徑不變的情況下,估算跳數(shù)將大于或等于相對最佳跳數(shù),針對此類情況利用式(5)定義差值修正系數(shù)ωij,以優(yōu)化跳數(shù)信息減少誤差的累積。

(5)

此外,跳數(shù)數(shù)據(jù)還受到多個參數(shù)的影響,錨節(jié)點占比、播撒區(qū)域面積和通信半徑都會影響通信過程中的路徑選擇,使跳數(shù)數(shù)據(jù)發(fā)生變化。局部區(qū)域內(nèi)錨節(jié)點數(shù)量增多,將對定位效果產(chǎn)生一定的影響,對于此類區(qū)域,錨節(jié)點占比增加,網(wǎng)絡(luò)連通情況更好,會使一定通信半徑內(nèi)局部單跳節(jié)點增多,將此類節(jié)點估算出來的跳數(shù)應(yīng)用于全網(wǎng),使相對最佳跳數(shù)之間誤差進(jìn)一步加大。于是定義跳數(shù)修正系數(shù)θij:

(6)

式中:L為正方形播撒區(qū)域的邊長,ρ為錨節(jié)點占比。

θij隨著整個網(wǎng)絡(luò)連通度的增加而減少,當(dāng)網(wǎng)絡(luò)連通情況較差且錨節(jié)點比例較低時,利用θij對跳數(shù)進(jìn)行修正,降低單跳節(jié)點對整體跳距計算的影響。當(dāng)網(wǎng)絡(luò)連通度較好且錨節(jié)點比例較高時,θij值將會變小,對跳數(shù)的影響也會降低,避免多跳情況下的誤差累積。

通過差值修正系數(shù)ωij與跳數(shù)修正系數(shù)θij對錨節(jié)點跳數(shù)進(jìn)行修正:

(7)

將差值修正系數(shù)ωij與跳數(shù)修正系數(shù)θij共同應(yīng)用于全網(wǎng)節(jié)點的跳數(shù)估算:

(8)

2.2 平均每跳距離修正

DV-hop算法中平均跳距對于節(jié)點間距離的估算十分重要。如圖2所示,數(shù)據(jù)通過節(jié)點A發(fā)送至節(jié)點B共需3跳,DV-Hop算法中折線距離為估算距離,顯然與虛線所示的真實距離存在較大的誤差。因此,本文利用最佳指數(shù)下的最小均方誤差準(zhǔn)則計算平均跳距并且與依據(jù)實際距離得出的單跳平均誤差共同修正平均跳距,以進(jìn)一步降低平均跳距的誤差,改善定位效果。

圖2 節(jié)點間距離誤差

對于錨節(jié)點,通過式(2)可估算出錨節(jié)點平均每跳距離的估計值,已經(jīng)獲取錨節(jié)點位置信息的前提下,可以利用錨節(jié)點i與s的真實距離與估算距離計算出二者的總體差值:

(9)

通過式(9)求出的總差值除以總跳數(shù)計算出平均每跳距離誤差εi:

(10)

利用估算距離加上平均每跳的距離誤差,得到校正后的平均跳距Dhopε:

Dhopε=hopsizei+εi

(11)

采用自適應(yīng)的最小均方誤差準(zhǔn)則,目的是使總誤差全局最小,相對于偏差和方差來說應(yīng)用于跳距的計算更加合理,但需要使代價函數(shù)f滿足:

(12)

對代價函數(shù)f求hopsizei的偏導(dǎo)并取值為0,得到平均跳距Dhopf:

(13)

通過式(13)計算出的平均跳距,估算距離與實際距離的誤差較小,此外本文將變化的指數(shù)值μ引入式(13),根據(jù)不同μ值對定位誤差的影響,選取最佳值應(yīng)用于平均跳距的修正,式(13)改寫為:

(14)

為了避免單一跳距均值不能很好的反映整個網(wǎng)絡(luò)中跳距的情況,減少數(shù)據(jù)不夠準(zhǔn)確而帶來誤差累積的風(fēng)險,將已校正的平均跳距值與使用最佳μ值下的最小均方誤差計算出的平均跳距進(jìn)行二次平均,得到修正后的平均跳距Dhopave:

(15)

利用式(15)求得修正后的平均跳距,能夠更接近于整個網(wǎng)絡(luò)中實際平均跳距,進(jìn)一步減少跳距誤差累積的影響,從而提升定位精度。

3 仿真結(jié)果與分析

為了測試本文算法的性能表現(xiàn),采用MATLAB R2016b仿真平臺對本文算法、DV-Hop算法和文獻(xiàn)[14]算法從最小均方誤差的不同μ值、差值修正系數(shù)的不同n值、網(wǎng)絡(luò)內(nèi)節(jié)點總數(shù)、節(jié)點通信半徑以及錨節(jié)點占比對定位誤差的影響進(jìn)行仿真實驗。仿真實驗環(huán)境:100 m×100 m的仿真區(qū)域內(nèi),隨機安置150個節(jié)點,其中錨節(jié)點比例為10%,所有節(jié)點的通信半徑均為R=30 m。

采用平均定位誤差Errorave作為評價定位效果的標(biāo)準(zhǔn)。

(16)

圖3 μ值變化下的平均定位誤差

首先驗證最小均方準(zhǔn)則下的指數(shù)值的變化對平均跳距修正的影響,在100 m×100 m的仿真區(qū)域內(nèi),安置150個節(jié)點,錨節(jié)點占比為10%,通信半徑R=30 m,本文對μ取1.95到2.05,步長為0.01。從圖3中能夠了解到,μ值取1.98時平均定位誤差最小。相較于初始原始取值2,平均定位誤差稍稍降低,與μ值取1.95相比較,平均定位誤差減少約1.7%,表明采用最小均方誤差準(zhǔn)則估算平均跳距時,μ的取值將會對平均跳距產(chǎn)生干擾,改變最后的定位效果。本文算法在驗證各參數(shù)對平均誤差影響的實驗中,均以1.98為最小均方誤差最佳指數(shù)值。

圖4表明了在100 m×100 m的仿真實驗環(huán)境下,n值變化下的平均定位誤差的變化情況。本文對n取1.95到2.05,單次增幅為0.01。從圖4中可以看到n取值變化的過程中,平均定位誤差存在些許波動,在1.96取值下定位效果優(yōu)于其他取值,相較于2.05的取值,效果提升了1.85%。表明n的取值會干擾到跳數(shù)值的測定,影響定位誤差。本文算法在驗證各參數(shù)對平均誤差影響的實驗中,差值修正系數(shù)中n均取1.96。

圖4 n值變化下的平均定位誤差

圖5表明仿真實驗環(huán)境下,設(shè)置通信半徑由20 m單次遞加4 m最高至40 m條件下,本文算法、文獻(xiàn)[14]算法以及DV-Hop算法平均定位誤差的變化情況。隨著通信半徑的增長,3種算法定位精度均有所提升,但在增至到某一數(shù)值時,例如36 m,文獻(xiàn)[14]的平均定位誤差出現(xiàn)了些許波動,表明在某些條件下,半徑的增加對文獻(xiàn)[14]的算法而言,定位精度提升不明顯?？傮w來說,本文算法平均定位誤差相比于文獻(xiàn)[14]和DV-Hop算法減少約6.58%～9.56%和13.1%～14.5%,且相較于文獻(xiàn)[14]與DV-Hop兩種算法,大通信半徑導(dǎo)致節(jié)點路徑選擇減少的情況下,整體性能表現(xiàn)較好。

圖5 不同通信半徑的平均定位誤差

圖6表明仿真實驗環(huán)境下,錨節(jié)點比例單次增長2%,由初始的8%增長至20%的條件下,本文算法和對比算法定位效果。隨著仿真環(huán)境中錨節(jié)點占比的增長,3種算法的定位效果都不同程度的增長。DV-Hop算法錨節(jié)點占比由8%增至10%的過程中,定位精度有明顯的提升,而后錨節(jié)點占比的增長對定位效果的影響較小,逐漸趨于平穩(wěn)。本文算法與文獻(xiàn)[14]算法均能針對DV-Hop算法在錨節(jié)點比例較低時節(jié)點隨機分布不均影響定位效果的情況進(jìn)行優(yōu)化,定位精度提升明顯?？刂棋^節(jié)點占比固定值為12%的條件下,DV-Hop算法平均定位誤差為32.8%,文獻(xiàn)[14]算法為27.6%,而本文算法為22.04%,并且整體效果也優(yōu)于其他兩種算法圖7表明仿真實驗環(huán)境下,節(jié)點總數(shù)在100～200范圍內(nèi),每次增加20的條件下,DV-Hop、文獻(xiàn)[14]以及本文算法在節(jié)點數(shù)量變化下平均定位誤差的趨勢。DV-Hop算法整體表現(xiàn)較為平穩(wěn),誤差最大值與最小值僅相差1.7%,而本文算法與文獻(xiàn)[14]算法整體效果依然優(yōu)于DV-Hop算法,由于節(jié)點總數(shù)的增長,單個錨節(jié)點覆蓋的未知節(jié)點數(shù)也一同增長,使整個網(wǎng)絡(luò)的連通度更好,提升了定位精度。相較于文獻(xiàn)[14]與DV-Hop算法,本文算法總體定位精度提升約3.39%與9.69%,表明在WSN總節(jié)點數(shù)增加的情況下,本文改進(jìn)算法效果好于文獻(xiàn)[14]算法與DV-Hop算法。

圖6 不同錨節(jié)點占比的平均定位誤差

圖7 不同節(jié)點總數(shù)的平均定位誤差

4 結(jié)束語

針對WSN中DV-Hop算法信息轉(zhuǎn)發(fā)時跳數(shù)不合理和跳距誤差累積的問題,為了降低累積誤差,以改善定位效果為目的,本文提出了一種跳數(shù)優(yōu)化與跳數(shù)修正的DV-Hop改進(jìn)算法。改進(jìn)算法通過定義跳數(shù)修正系數(shù)對跳數(shù)信息進(jìn)行優(yōu)化,再對指數(shù)最佳值下的平均跳距和校正后的平均跳距進(jìn)行二次優(yōu)化,并在選取最佳μ值與最佳n值的前提下,對WSN環(huán)境中不同通信半徑、不同錨節(jié)點比例和不同節(jié)點總數(shù)的環(huán)境下進(jìn)行定位性能仿真測試。實驗結(jié)果表明,在多種仿真環(huán)境且不增加額外的硬件開銷和通信成本的條件下,本文算法的定位表現(xiàn)優(yōu)于DV-Hop算法與相關(guān)算法,表明本文對DV-Hop算法的改進(jìn)能夠有效提升WSN中節(jié)點的定位精度。如何進(jìn)一步降低跳距誤差累積,以使未知節(jié)點位置信息更加準(zhǔn)確是后續(xù)研究的重點方向。