一種基于加權(quán)處理和誤差修的DV-Hop定位算法研究*

周杭霞,崔 晨,葉佳駿

(中國計量學(xué)院信息工程學(xué)院,杭州 310018)

?

一種基于加權(quán)處理和誤差修的DV-Hop定位算法研究*

周杭霞*,崔 晨,葉佳駿

(中國計量學(xué)院信息工程學(xué)院,杭州 310018)

針對傳統(tǒng)的DV-Hop算法在定位過程中出現(xiàn)的容易引起誤差的問題,提出了一種綜合考慮所有信標(biāo)節(jié)點的平均跳距并引入權(quán)值修正,將信標(biāo)節(jié)點當(dāng)作未知節(jié)點計算誤差進而優(yōu)化精度的距離估計算法,使網(wǎng)絡(luò)平均跳距和節(jié)點位置估計值更加準(zhǔn)確。通過相關(guān)仿真實驗表明:改進算法優(yōu)化了原算法的定位精度和定位穩(wěn)定性,達到了預(yù)期目標(biāo)。

無線傳感器網(wǎng)絡(luò);DV-Hop定位算法;歸一加權(quán);誤差修正

無線傳感器網(wǎng)絡(luò)是一種特殊的Ad-Hoc網(wǎng)絡(luò)[1],它由大量靜止或移動的傳感器以自組織和多跳的方式構(gòu)成,并通過協(xié)作感知、內(nèi)容采集、匯總處理最終將區(qū)域?qū)ο笾械奶囟ㄐ畔蟾娼o用戶,對于該網(wǎng)絡(luò)而言節(jié)點的位置信息是網(wǎng)絡(luò)實現(xiàn)過程較為重要的上下文信息之一[2]。目前國內(nèi)外關(guān)于無線傳感器網(wǎng)絡(luò)節(jié)點定位的方法有許多種,其中按是否需要測距可將定位算法分為距離相關(guān)定位和距離無關(guān)定位兩類。距離相關(guān)定位算法需要通過測量距離角度等信息實現(xiàn)定位,對硬件和成本要求較高,使得此類方法的應(yīng)用受到了一定限制。而距離無關(guān)算法無需測距技術(shù),僅利用節(jié)點間估計距離來計算位置,更適合于大規(guī)模無線傳感器網(wǎng)絡(luò)的實際要求,是目前備受關(guān)注的定位方法。

DV-Hop算法是目前應(yīng)用較為廣泛的距離無關(guān)定位算法[3],采用的主要思想是將定位節(jié)點到信標(biāo)節(jié)點之間的距離用平均每跳距離和兩者間跳數(shù)的乘積來表示[4]。然而在實驗中我們發(fā)現(xiàn)原始DV-Hop算法在實際應(yīng)用中誤差較大,結(jié)果并不準(zhǔn)確?，F(xiàn)階段雖然有多種改進方法對算法進行了優(yōu)化,比如結(jié)合RSSI量化模型優(yōu)化定位結(jié)果[5],限定主要參數(shù)的最優(yōu)范圍[6],改進定位結(jié)果求解的計算方法[7],但是這些算法并沒有很好的解決DV-Hop算法多跳路徑條件下估計距離不準(zhǔn)確、平均跳距計算誤差較大等問題[8]。本文通過細化原始算法定過過程中的關(guān)鍵步驟,分析誤差產(chǎn)生原因,提出一種綜合全網(wǎng)信息,修正定位誤差并改進節(jié)點定位過程改進方案。仿真結(jié)果表明,該方法可以在不增加節(jié)點硬件開銷的基礎(chǔ)上有效減小定位誤差,提高定位精度。

1 DV-Hop算法介紹與誤差分析

1.1 算法描述

DV-Hop算法由3個階段組成[9]:

①信息廣播與距離計算階段,這一階段主要使用典型的距離矢量交換協(xié)議,錨節(jié)點將位置信息以數(shù)據(jù)分組的形式在網(wǎng)絡(luò)中廣播,其中跳數(shù)信息初始化為0。接受到此分組的每個鄰居節(jié)點保留最小跳數(shù)信息后,跳數(shù)加1后轉(zhuǎn)發(fā)至下一個節(jié)點,這樣可以使網(wǎng)絡(luò)中所有節(jié)點獲得距錨節(jié)點的最小跳數(shù)。

②第2階段,在獲得其他錨節(jié)點位置和相隔跳距之后,錨節(jié)點利用式(1)計算自己的平均每跳距離hopi:

(1)

其中(xi,yi)為信標(biāo)節(jié)點i的位置坐標(biāo);hj為信標(biāo)節(jié)點i和j之間的最小跳數(shù)。之后信標(biāo)節(jié)點然后將其作為一個校正值廣播至網(wǎng)絡(luò)中。校正值采用可控洪泛法在網(wǎng)絡(luò)中傳播,節(jié)點僅接受獲得的第1個校正值,而丟棄所有后來者,在大型網(wǎng)絡(luò)中,可通過為數(shù)據(jù)包設(shè)置一個TTL域來減少通信量[8]。當(dāng)接收到校正值之后,節(jié)點根據(jù)跳數(shù)計算與錨節(jié)點之間的距離。當(dāng)未知節(jié)點獲得與3個或更多錨節(jié)點的距離后,則在第3階段執(zhí)行三邊測量法或極大似然估計法求出節(jié)點坐標(biāo)。

③極大似然估計法

當(dāng)已知節(jié)點的個數(shù)大于或者等于4時,即節(jié)點個數(shù)n>=4,一般都采用極大似然估計值法來進行求解。有:

假設(shè)它的線性方程為Ax=b,其中

則由以上各個方程可得到線性方程Ax=b的解為:

(2)

此解即使為直接點D的坐標(biāo)。

1.2 DV-Hop算法的缺陷

通過對傳統(tǒng)DV-Hop算法的缺陷進行研究和分析我們發(fā)現(xiàn),由于采用跳數(shù)乘以平均跳距來計算未知節(jié)點與錨節(jié)點間的距離,因此當(dāng)跳數(shù)大于2時就會產(chǎn)生如圖1所示的誤差。

圖1 DV-Hop誤差示意圖

圖1中粗虛線代表錨節(jié)點L1和未知節(jié)點A的實際距離,而細虛線代表傳統(tǒng)DV-Hop算法計算時采用的估計距離,由圖示可知,由于無法測量實際距離,雖然DV-Hop算法采用了一種數(shù)值逼近的方法近似地獲取了兩點間的距離,但兩者間還存有較大誤差[10]。另外,原始算法中求出的平均跳距取值的精確性,每跳實際距離與平均跳距之間差值大小都是最終使得真實距離與計算距離之間產(chǎn)生誤差從而影響定位精度[11]的原因之一。

2 改進的DV-Hop算法的實現(xiàn)

雖然傳統(tǒng)DV-Hop算法在定位精度上還存在一些缺陷,但是其實現(xiàn)簡單,通信開銷小,硬件要求低的優(yōu)點還是使其得到了廣泛應(yīng)用,因此改進算法在充分考慮原始算法優(yōu)點的同時,針對其中存在的不足之處做了如下優(yōu)化:

①傳統(tǒng)DV-Hop算法中未知節(jié)點僅接受距離自己最近的一個信標(biāo)節(jié)點估計出的平均每跳距離值作為自身的平均每跳距離,但相對于整個網(wǎng)絡(luò)來說,單個錨節(jié)點的平均每跳距離值不足以反映全網(wǎng)的整體屬性[12],因此我們在計算每個未知節(jié)點的平均每跳距離時需要綜合考慮所有可以與之通信的錨節(jié)點,利用各個錨節(jié)點計算出的平均每跳距離與到未知節(jié)點跳數(shù)的乘積作為距離加權(quán)參數(shù),并對所得權(quán)值進行歸一化處理。其過程具體如下:

首先在信標(biāo)節(jié)點廣播跳數(shù)和平均每跳距離階段,未知節(jié)點記錄所有能獲得的信標(biāo)節(jié)點數(shù)據(jù),并通過計算兩者乘積對數(shù)值較大的賦予較小權(quán)值λi,λi的取值滿足:

(3)

其中n表示未知節(jié)點可得到的所有信標(biāo)個數(shù),j表示其中一個信標(biāo)節(jié)點,dij表示第i個未知節(jié)點到第j信標(biāo)節(jié)點的跳數(shù)與該信標(biāo)節(jié)點平均每跳距離的乘積。通過這個歸一化的加權(quán)可以使未知節(jié)點獲得的n個信標(biāo)節(jié)點的平均每跳距離加權(quán)值之和為1。之后通過結(jié)合對應(yīng)信標(biāo)節(jié)點的平均每跳距離Sj,獲得未知節(jié)點自身的平均每跳距離Si:

(4)

之后再根據(jù)DV-Hop算法的計算過程繼續(xù)下一步的計算。

②雖然通過歸一加權(quán)處理后使得實驗數(shù)據(jù)比原始算法有了較大改進,但單個節(jié)點的計算坐標(biāo)與真實坐標(biāo)相比,每個節(jié)點仍平均有33%左右的定位誤差,為了進一步提高定位精度,我們采用另一種全新的優(yōu)化方法繼續(xù)對定位算法結(jié)果進行改進,具體過程如下:

在獲得原始定位數(shù)據(jù)后,我們從所有n個信標(biāo)節(jié)點中隨機抽取1個信標(biāo)節(jié)點將其轉(zhuǎn)化為未知節(jié)點,之后利用剩余n-1個信標(biāo)節(jié)點對其進行定位,獲得其定位值e′,之后通過與真實坐標(biāo)求差獲得該點處定位誤差值Δe,有Δe=e-e′,此誤差可看作其余n-1個信標(biāo)節(jié)點對該點處及周圍一定范圍內(nèi)所有未知節(jié)點產(chǎn)生的定位誤差,然后我們對該點處一個半徑為R內(nèi)的所有未知節(jié)點通過Δe值進行誤差修正,獲得一個修正值當(dāng)做節(jié)點新的位置坐標(biāo)。最后對剩下n-1個信標(biāo)節(jié)點循環(huán)運用此方法進行二次誤差修正定位,直到對全部n個信標(biāo)節(jié)點及其周圍R范圍內(nèi)的未知節(jié)點完成誤差修正為止。其中隨機分布的信標(biāo)節(jié)點及半徑R的修正覆蓋區(qū)域如圖2所示,其中黑色圓點表示隨機分布的未知節(jié)點,灰色星點表示信標(biāo)節(jié)點。

圖2 節(jié)點閾值半徑R的取值示意圖

3 算法仿真與分析

為了驗證本文改進算法的性能,利用MATLAB2012b對DV-Hop算法和本文改進算法進行了對比仿真研究,算法仿真實現(xiàn)流程如圖3所示。

圖3 改進算法流程圖

仿真場景為100×100的無線傳感器網(wǎng)絡(luò)區(qū)域,未知節(jié)點和錨節(jié)點均為實驗區(qū)域內(nèi)隨機生成,實驗取當(dāng)錨節(jié)點個數(shù)、總節(jié)點個數(shù)、修正范圍半徑值R變化時的節(jié)點定位誤差100次仿真結(jié)果平均值,并對其做了對比分析。歸一化后每個節(jié)點的平均定位誤差由式(4)計算,其中un表示待定位的節(jié)點個數(shù),r為節(jié)點的通信半徑,xi,yi表示由算法得到的定位節(jié)點坐標(biāo),Xi,Yi表示定位節(jié)點的真實坐標(biāo),error越小表示由定位算法得到的坐標(biāo)與節(jié)點的真實坐標(biāo)的差距越小[9],定位精度越高。

(5)

通過對原始算法和實驗結(jié)果的分析我們發(fā)現(xiàn)在無線傳感器網(wǎng)絡(luò)中,信標(biāo)節(jié)點個數(shù)的變化會同時引起定位精度的改變[13],因此仿真實驗中我們設(shè)定網(wǎng)絡(luò)區(qū)域內(nèi)隨機分布200個無線傳感器節(jié)點,通信半徑30,二次誤差修正半徑R為9,信標(biāo)節(jié)點在所有節(jié)點中隨機選取生成,在節(jié)點總數(shù)不變的情況下,信標(biāo)節(jié)點數(shù)量取值分別為20、25、30、35、40和50時,本文算法與DV-Hop算法的性能比較,仿真結(jié)果如圖4所示。

從圖4可以看出,在節(jié)點總數(shù)不變的情況下,兩種算法的error值都會隨著信標(biāo)節(jié)點數(shù)增加而減小。當(dāng)信標(biāo)節(jié)點數(shù)為20時,歸一加權(quán)方法可以使每個節(jié)點的平均定位誤差減小大約11.30%,之后對半徑R內(nèi)節(jié)點采用誤差修正的方法后,每個節(jié)點平均定位誤差再次減少約9.6%,結(jié)合來看本文改進算法可以在相同條件下使得節(jié)點平均定位誤差減少約18.69%,當(dāng)信標(biāo)節(jié)點比例由10%逐漸增大至20%時,由于可參考的節(jié)點信息增加使得平均定位誤差值下降較大,之后隨著信標(biāo)節(jié)點比例增大誤差變化減小并逐漸趨于平穩(wěn),當(dāng)信標(biāo)節(jié)點數(shù)為50時,本文第1步改進算法減少每個節(jié)點平均定位誤差19.63%,第2步改進在此基礎(chǔ)上可再次減少定位誤差17.23%左右,通過分析實驗數(shù)據(jù)改進算法在此條件下可提高原始DV-HOP算法定位精度約33.48%?？傮w來看,經(jīng)過本文第1步歸一加權(quán)優(yōu)化后的DV-HOP算法可以減少每個定位節(jié)點平均誤差14.94%左右,之后采用誤差修正半徑R范圍內(nèi)節(jié)點定位結(jié)果可以再次減少誤差約10.65%,最終本文改進算法在同等條件下可以減少原始DV-HOP定位算法節(jié)點平均定位誤差24.01%左右。

圖4 誤差與錨節(jié)點之間關(guān)系

在固定區(qū)域范圍內(nèi),區(qū)域節(jié)點總個數(shù)也會對定位誤差有影響,節(jié)點數(shù)較少時可供參考的計算信息減少可能造成定位精度不夠,節(jié)點數(shù)過多又會增加計算復(fù)雜度,并造成大量未定位節(jié)點從而影響最終實驗結(jié)果。圖5為信標(biāo)節(jié)點數(shù)固定為20個,節(jié)點總數(shù)分別取100、200、250、300和400時本文改進算法對平均定位誤差的改變結(jié)果。

當(dāng)節(jié)點總數(shù)為100時,本文第1步改進算法減少了原始算法每個節(jié)點平均誤差約9.2%,之后通過誤差修正可以再次提高定位精度約7.8%,此條件下本文改進算法可以減少每個節(jié)點平均定位誤差16.36%左右,之后隨著節(jié)點總數(shù)的增加,平均定位誤差會隨之減少并逐漸趨于平緩,當(dāng)節(jié)點總數(shù)達到400時,本文第1步改進算法可以減少定位誤差約12.64%,第2步改進可再次減少約11.14%,此條件下本文改進算法可以減少每個節(jié)點平均定位誤差23.31%左右?？傮w來看由于節(jié)點位置隨機分布,節(jié)點總數(shù)的增加會造成網(wǎng)絡(luò)結(jié)構(gòu)的節(jié)點連通性的變化,使得定位誤差呈現(xiàn)微小振動變化并且曲線下降趨勢,但是本文改進算法相比較原始算法還是穩(wěn)定的減少了定位誤差,其中經(jīng)過第1步優(yōu)化每個節(jié)點平均定位誤差下降了約11.33%,經(jīng)過第2步優(yōu)化定位誤差再次下降約6.72%,總體來看本文改進算法比傳統(tǒng)DV-Hop算法在同等條件下可以使定位誤差減小16.83%左右。

圖5 誤差與節(jié)點總數(shù)之間關(guān)系

圖6 改進方法中R取值的影響

在第2步改進中,我們添加了誤差修正半徑R,并將已知的信標(biāo)節(jié)點看作未知節(jié)點,依次循環(huán)定位進而對結(jié)果進行最終優(yōu)化。其中半徑R取值范圍的變化也會引起定位結(jié)果最終誤差值的變化,當(dāng)R取值較小時會因為修正區(qū)域內(nèi)覆蓋節(jié)點數(shù)不足造成性能減小,而R過大又會造成范圍疊加引起節(jié)點間的多次修正影響定位精度。因此我們在之前實驗條件的基礎(chǔ)上,對其中選取的R值變化進行了實驗,其中R取值從節(jié)點通信半徑的10%增長至50%,取得每個節(jié)點定位誤差計算5次后的平均值,結(jié)果如圖6所示。

從圖6我們可以發(fā)現(xiàn),當(dāng)修正半徑值從2逐漸增加至8～10之間時,單個節(jié)點平均定位精度逐漸增加,當(dāng)R取值范圍為9時,節(jié)點定位精度的平均提高量達到最高值,每個節(jié)點定位精度平均可提高約1.4%左右,此時優(yōu)化算法誤差最小,修正區(qū)域覆蓋范圍更為合理性能最高,之后隨著半徑R值增大,節(jié)點定位精度提高量開始減少,并且由于覆蓋區(qū)域過大性能逐漸下降,因此最終優(yōu)化算法采用計算誤差并修正半徑R范圍內(nèi)節(jié)點坐標(biāo)這一方法時,選取了節(jié)點通信半徑中最優(yōu)范圍內(nèi)的R取值,以保證定位精度和優(yōu)化性能達到最優(yōu)。

4 結(jié)束語

為了解決傳統(tǒng)的DV-Hop算法在定位過程中求取的平均每跳距離難以正確反映全網(wǎng)信息,以及定位過程中誤差較大,精確度不高的問題[14]提出了一種綜合考慮所有信標(biāo)節(jié)點平均跳距并歸一加權(quán),將信標(biāo)節(jié)點當(dāng)作未知節(jié)點計算誤差并修正的距離估計算法,通過MATLAB軟件的驗證發(fā)現(xiàn)該算法可以使節(jié)點位置估計值更加準(zhǔn)確,提高了定位精度。未來將繼續(xù)針對第2種優(yōu)化方法進行改進,研究在通信能力和信道環(huán)境更為復(fù)雜的情況下的應(yīng)用前景,同時將研究如何在移動節(jié)點的環(huán)境中改善定位結(jié)果,使算法應(yīng)用領(lǐng)域進一步擴大。

[1] 李文辰,張雷. 無限傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法研究[J]. 計算機仿真,2013,30(2):191-194.

[2]Kumar Shrawan,Lobiyal D K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71(2):1365-1385.

[3]劉彩霞,黃延磊. WSN中抵御蟲洞攻擊的改進的DV-Hop算法研究[J]. 傳感技術(shù)學(xué)報,2011,24(10):1473-1478.

[4]趙雁航,錢志鴻,尚小航,等. 基于跳距修正粒子群優(yōu)化的WSN定位算法[J]. 通信學(xué)報,2013,34(9):105-114.

[5]胡斌,李方敏,劉新華. 基于RSSI量化模型的定位算法研究[J]. 武漢理工大學(xué)學(xué)報,2009,31(23):92-95.

[6]張震,閆連山,劉江濤,等. 基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J]. 傳感技術(shù)學(xué)報,2011,24(10):1469-1472.

[7]趙清華,劉少飛,張朝霞,等. 一種無需測距節(jié)點定位算法的分析和改進[J]. 傳感技術(shù)學(xué)報,2010,23(1):122-127.

[8]趙靈鍇,洪志全. 基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進[J]. 計算機應(yīng)用,2011,31(5):1189-1192.

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

[10]李輝,熊盛武,劉毅,等. 無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進[J]. 傳感技術(shù)學(xué)報,2011,24(12):1782-1786.

[11]羅維,姜秀柱,盛蒙蒙. 無線傳感器網(wǎng)絡(luò)選擇性 DV-Hop 定位算法[J]. 傳感器與微系統(tǒng),2012,31(3):71-77.

[12]戴瑩,王建平,張崇巍. 無線傳感器網(wǎng)絡(luò)節(jié)點定位算法的研究與改進[J]. 傳感技術(shù)學(xué)報,2010,23(4):567-570.

[13]Myint T Z,Lynn N,Ohtsuki T. Range-Free Localization Algorithm Using Local Expocted Hop Length in Wireless Sensor Networks[C]//Proceedings of International Symposture on Conmmnicatiuns and Information Technologies. Tokyo:IEEE,2010:356-361.

[14]Zhang Y J,Wang K,Yuan S F,ed al. Research of WSN Node Localization Algorithm Based on Weighted DV-Hop[C]//IEEE. 24th Chinese Control and Decision Conference. Taiyuan:2012,3826-3829.

周杭霞(1963-),女,中國計量學(xué)院信息工程學(xué)院 教授,碩導(dǎo)。主要研究方向算法優(yōu)化,無線傳感網(wǎng)絡(luò)和信息技術(shù)安全,zhx@cjlu.edu.cn;

崔晨(1987-),男,中國計量學(xué)院計算機應(yīng)用技術(shù)專業(yè)碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò),doublecwork@163.com。

AStudyofDV-HopLocalizationAlgorithmBasedonWeightedProcessingandErrorModification*

ZHOUHangxia*,CUIChen,YEJiajun

(College of Information Engineering,China Jiliang University,Hangzhou 310018,China)

Aiming at the traditional DV-Hop algorithm easily caused error,the current thesis proposes a comprehensive consideration of all beacon nodes average one-hop distance and introducing weights corrected results. At the same time use beacon nodes as unknown nodes calculating error and use the error optimizing accuracy. Finally makes the average one-hop distance and node position estimates more accurate. Theoretical analysis and simulation results show that the proposed algorithm has better locating performance in locating precision and precision stability,achieve the expected goal.

wireless sensor networks;DV-Hop localization algorithm;normalized weighted;error correction

項目來源:國家自然科學(xué)基金項目(61027005)

2014-07-12修改日期:2014-10-23

TP393

:A

:1004-1699(2014)12-1699-05

10.3969/j.issn.1004-1699.2014.12.021