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

周杭霞,崔 晨,葉佳駿

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

?

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

周杭霞*,崔 晨,葉佳駿

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

針對傳統的DV-Hop算法在定位過程中出現的容易引起誤差的問題,提出了一種綜合考慮所有信標節點的平均跳距并引入權值修正,將信標節點當作未知節點計算誤差進而優化精度的距離估計算法,使網絡平均跳距和節點位置估計值更加準確。通過相關仿真實驗表明:改進算法優化了原算法的定位精度和定位穩定性,達到了預期目標。

無線傳感器網絡;DV-Hop定位算法;歸一加權;誤差修正

無線傳感器網絡是一種特殊的Ad-Hoc網絡[1],它由大量靜止或移動的傳感器以自組織和多跳的方式構成,并通過協作感知、內容采集、匯總處理最終將區域對象中的特定信息報告給用戶,對于該網絡而言節點的位置信息是網絡實現過程較為重要的上下文信息之一[2]。目前國內外關于無線傳感器網絡節點定位的方法有許多種,其中按是否需要測距可將定位算法分為距離相關定位和距離無關定位兩類。距離相關定位算法需要通過測量距離角度等信息實現定位,對硬件和成本要求較高,使得此類方法的應用受到了一定限制。而距離無關算法無需測距技術,僅利用節點間估計距離來計算位置,更適合于大規模無線傳感器網絡的實際要求,是目前備受關注的定位方法。

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

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

1.1 算法描述

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

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

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

(1)

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

③極大似然估計法

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

假設它的線性方程為Ax=b,其中

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

(2)

此解即使為直接點D的坐標。

1.2 DV-Hop算法的缺陷

通過對傳統DV-Hop算法的缺陷進行研究和分析我們發現,由于采用跳數乘以平均跳距來計算未知節點與錨節點間的距離,因此當跳數大于2時就會產生如圖1所示的誤差。

圖1 DV-Hop誤差示意圖

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

2 改進的DV-Hop算法的實現

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

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

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

(3)

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

(4)

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

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

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

圖2 節點閾值半徑R的取值示意圖

3 算法仿真與分析

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

圖3 改進算法流程圖

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

(5)

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

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

圖4 誤差與錨節點之間關系

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

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

圖5 誤差與節點總數之間關系

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

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

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

4 結束語

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

[1] 李文辰,張雷. 無限傳感器網絡加權質心定位算法研究[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]. 傳感技術學報,2011,24(10):1473-1478.

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

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

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

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

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

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

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

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

[12]戴瑩,王建平,張崇巍. 無線傳感器網絡節點定位算法的研究與改進[J]. 傳感技術學報,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-),女,中國計量學院信息工程學院 教授,碩導。主要研究方向算法優化,無線傳感網絡和信息技術安全,zhx@cjlu.edu.cn;

崔晨(1987-),男,中國計量學院計算機應用技術專業碩士研究生,主要研究方向為無線傳感器網絡,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

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

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

TP393

:A

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

10.3969/j.issn.1004-1699.2014.12.021