基于跳數修正的DV-Hop改進算法*

夏少波,朱曉麗,鄒建梅,連麗君

(山東廣播電視大學計算機與通信學院,濟南 250014)

?

基于跳數修正的DV-Hop改進算法*

夏少波*,朱曉麗,鄒建梅,連麗君

(山東廣播電視大學計算機與通信學院,濟南 250014)

針對無線傳感器網絡DV-Hop定位算法在實際應用中定位誤差較大的問題,提出一種基于跳數修正的改進算法。在引入限跳機制的條件下,按未知節點與信標節點間的跳數值分類估算,對1跳區域內的節點采用RSSI測距技術,對于節點間跳數值大于1跳的節點,則利用信標節點間實際距離與估計距離的誤差值修正平均每跳距離。仿真實驗表明,在相同的網絡條件下,與原DV-Hop定位算法和其他改進算法相比,改進后的算法能更有效地減少跳距估算帶來的定位誤差,提高平均定位精度并保持較好的算法穩定性。

無線傳感器網絡;節點定位;定位誤差;限跳機制;平均跳距

無線傳感器網絡WSN(Wireless Sensor Network)是由大量智能傳感器節點構成的集信息采集、傳送和處理為一體的綜合智能信息網絡,具有環境適應性強、自組織能力和組網成本低等特點[1]。網絡節點協作感知、采集和處理覆蓋區域內被檢測對象的信息,并將結果傳送給觀測者。WSN在目標跟蹤、環境監測甚至是軍事偵測等眾多的領域都有廣泛的應用,引起了學術界的廣泛關注和深入研究[2]。對大多數WSN應用而言,沒有時空標識的數據和信息是沒有意義的,因此,節點的準確定位在傳感器網絡的應用中起關鍵作用[3-4]。目前研究者已經提出了很多節點定位算法。按定位所采用的節點間距離獲取方式,一般把定位算法分為基于測距算法(Range-based)和無需測距算法(Range-free)兩大類[5-7],前者主要有RSSI(Received Signal Strength Indicator)、TDOA(Time Difference on Arrival)、AOA(Angle of Arrival)和TOA(Time of Arrival)等。后者主要有DV-Hop(Distance Vector-Hop)、凸規劃定位、質心定位、MDS-MAP定位、Amor-phous定位和APIT(Approximate PIT Test)定位等。上述眾多算法各有其優勢和不足,第1類方法采用測距技術,通常精度較高,但需要附加硬件設備而且測距效果受環境影響較大[8];第2類方法雖然精度稍低,但因其成本低廉,受環境影響較小等優點,越來越受到關注。尤其是DV-Hop節點定位算法,以其經濟性和簡單實效性得到了廣泛應用,但DV-Hop定位算法的缺點是定位誤差稍高[9]。本文深入分析了DV-Hop定位算法存在的缺陷,在不改變原算法步驟,少量增加硬件設備的條件下,提出了一種基于跳數修正的DV-Hop改進算法。

1 傳統DV-Hop算法及其存在的不足

DV-Hop屬于距離矢量路由DVR(Distance Vector Rou-ting)和全球定位系統GPS(Global Positioning System)技術綜合應用產生的一組分布式定位算法——自組織定位算法APS(Ad-hoc Positioning System),是由美國路特葛斯大學的Dragos Niculescu等人早年提出的[10]。該算法的優點是具有較高的定位覆蓋率、易于擴展、廉價和受限條件少等,因其定位精度能滿足大多數WSN應用的需要,而被廣泛地應用和研究。

1.1 傳統DV-Hop算法描述

傳統DV-Hop節點定位算法分為以下3個步驟[11-12]:

①網絡中的信標節點利用典型的距離矢量路由協議,在網絡中廣播包含自身位置信息的數據分組(含有位置和跳數字段等信息,跳數初始值設為零),網絡中的相鄰節點作為接收方,記錄至各信標節點間的最小跳數,并拋棄來自同一信標節點的較大跳數分組。再將跳數值加1后轉發出去。反復此步驟,各節點均記錄下至各信標節點間的最小跳數值。

②每個信標節點在獲得其他信標節點的位置坐標和最小跳數值后,計算各自的平均每跳距離,然后將其作為校正值以洪泛的方式廣播至網絡中。信標節點i的平均每跳距離(校正值)的估算公式如式(1)。

(1)

式中:(xi,yi),(xj,yj)分別表示信標節點i和j的坐標,hj表示信標節點i與j之間的跳數值。

(2)

③未知節點利用第2階段操作估算出的到3個(或以上)信標節點間的跳距,最后再采用三邊測量法或極大似然法估算自己的坐標值。

圖1是傳統DV-Hop定位算法總流程。

圖1 DV-Hop定位算法流程

相關研究表明,在網絡節點平均連通度為10,信標節點占比為10%,且各向同性的環境中,DV-Hop的平均定位精度可以達到33%左右[4],可見對于節點分布均勻、且密集型的網絡,該算法的定位精度基本能滿足要求。但在實際應用中,網絡的拓撲結構常常是隨機且不規則的,如果直接使用DV-Hop算法,定位精度就會迅速下降。

1.2 DV-Hop算法誤差原因分析

①實際應用中,節點是隨機播撒在檢測區域內,網絡的拓撲結構是不規則的,且節點分布不可能均勻,這必然造成網絡中不同區域內節點密度差別較大[13],從而使不同區域內的節點接收到的與各信標節點間的最小跳數值存在一定偏差,且隨著跳數值的增大,該偏差也將累計加大,導致測距誤差變大,影響定位精度。

②通信范圍內能相互直接通信的節點互稱為鄰居節點,又稱之為1跳(1h)區域節點,圖2所示為節點x的1跳區域示意圖。

圖2 節點的1跳區域示意圖

圖2中,假設方形點I、J代表信標節點,標號為1、2、3、…、x的圓形點代表未知節點,用r代表節點的通信半徑,則圖中所示以r為半徑的圓形區域內,就是節點x的1跳區域。圖2可看出,圓圈內的節點盡管都是x的1跳節點,但有的靠近圓心處(如節點1),而有的則靠近虛線圓圈內側(如節點4),它們距處于圓心的節點x的實際距離相差較大,然而DV-Hop算法的規則是:1跳區域內的所有節點的間距,一律按統一的1跳距離估值。這勢必造成較大誤差。

③DV-Hop算法的核心思想是用接收到的最近信標節點的平均每跳距離與跳數值的乘積估算未知節點與信標節點之間的距離,即使用跳段距離代替直線距離。這對于各向同性的密集網絡,可以得到合理的平均每跳距離,達到適當的測距精度[14],但對于拓撲不規則的網絡,由于節點分布不可能均勻,必將存在以下兩方面的缺陷:一是用單個信標節點估算的平均每跳距離值無法準確地反映全網絡各區域的實際平均每跳距離,采用相同的平均每跳距離估算,就造成了未知節點與其他信標節點間的測距精度降低[8];二是節點間大多是折線連接,節點密度越小折線率越高,因此當網絡中未知節點和信標節點之間的跳數值大于1跳時,以折線結構的跳段距離近似代替直線距離,平均每跳距離的估算值與實際值誤差就會加大,導致DV-Hop算法的估算距離與實際距離間存在較大的誤差,且誤差與節點間的跳數值成正比[7]。以下,用圖3所示的節點分布為例,做進一步的說明。

圖3 節點分布示意圖

在圖3所示節點分布圖中,中間處的方形節點I代表信標節點,其他所有標號為1、2、3、…12等圓形節點代表未知節點,圖中以中間為界左邊1、2、3、…5等節點較密集,而右邊6、7、8、…12等節點分布較稀疏,圖中的若干虛線圓圈代表幾個節點的通信范圍。由圖不難看出,盡管信標節點I到未知節點5與信標節點I到未知節點12之間的距離大致相同(圖中兩條虛直線),但由于左邊節點分布較密集,I到節點5之間有多種跳段路徑可供選擇,且折線近似直線;而右邊節點分布較稀疏,I到節點12之間可供選擇的路徑較少,且折線率高,這就造成I到節點5間的跳數值是3跳,而I到節點12間的跳數值是4跳。這種情況下,節點5和12若再采用相同的平均每跳距離去估算,就會導致測距估算誤差過高。

2 改進策略分析

2.1 已有的改進策略分析

針對傳統DV-Hop算法存在的不足,文獻[5]對算法的改進策略是:利用無線信號在同種介質中傳播速度的不變性,用計數器來測量信標節點間的傳送時間以及信標節點與未知節點間的傳送時間,再利用該時間比例修正未知節點的估算距離,以達到降低距離估算誤差的目的。文獻[7]對算法的改進策略是:從半自動獲取平均每跳距離、劃分定位區域到對邊緣區域采用坐標貼邊等3個方面進行了改進,所謂“半自動”是指在獲取平均每跳距離的過程中,并不是每個步驟都由節點自動完成,而需要人工的參與,事先靠人工在節點中手動寫入必要的參數,這種改進策略雖能提升定位精度,但需要人工參與就會影響WSN的應用范圍。文獻[8]對算法的改進策略是從如下兩個方面進行,一是信標節點首先計算出實際距離與估算距離間的誤差,再用該誤差作為修正值修正信標節點的平均每跳距離。二是摒棄了傳統的三邊定位算法而采用新的二維雙曲線定位算法估算未知節點的坐標。本文在文獻[8]改進算法的基礎上,以節點間的跳數值為突破口,引入限跳機制,按未知節點與信標節點間的跳數值不同進行分類估算,對于1跳區域內的節點,直接采用RSSI測距技術完成測距,而對于跳數值大于1跳的節點,則用節點間實際距離與估算距離的誤差值對平均每跳距離進行重新修正。

2.2 本文改進策略描述

針對傳統DV-Hop定位算法存在的上述諸如跳數值越大則累計誤差就越高,1跳區域內節點距離估算不合理,平均每跳距離誤差過大等缺陷,本文提出了如下3方面的改進策略。

2.2.1 策略1:引入限跳機制

鑒于節點間的跳數值越大,距離估算誤差越高的缺陷,本文在改進算法中引入限跳機制,即設置一個閾值N(跳數值上限)。具體操作是:信標節點向網絡中廣播包含自身位置信息的分組時,在分組中再附加參數N,稱之為跳數閾值,網絡中鄰居節點接收到該分組后,首先比較跳數h與閾值N的大小,如果h小于N,則h=h+1,并轉發該分組,否則丟棄此分組不再轉發,這樣就可以保證每個節點只接收N跳范圍內信標節點的位置信息。

跳數閾值N的大小主要依據網絡的連通度和節點密度確定[15],如式(3)所示。

(3)

式中:r表示節點的通信半徑,A表示網絡內所有節點總數,ρ表示信標節點占比,L表示整個檢測正方形區域的邊長,M表示定位未知節點所需要的最小信標節點的個數。為提高節點定位率和定位精度,通常N的取值要比理論估算值稍大一點(一般取3或4),以滿足網絡整體的定位覆蓋率。

2.2.2 策略2:引入RSSI測距技術

隨著微電子和通信技術的高速發展,RSSI測距技術也實現了低成本和高效能。實際應用中,適當將基于測距(Range Based)和無需測距(Range Free)技術綜合應用,會收到取長補短的效果。通常只需給傳感器節點增加小許硬件開銷,即可實現精度較高的RSSI短距離(鄰居節點間)測距。在DV-Hop算法的第2步,節點接收到其他節點位置信息后,在進行節點間跳距估算之前,先對節點間的跳數值做一個判斷,若節點間的跳數值是1跳,則直接采用RSSI測距技術,若節點間的跳數值大于1跳,則按策略3(后述)估算跳距。

RSSI主要使用RF(射頻)信號測距,由于無線信號在傳播過程中,信號的功率強度會衰減,也就是:已知發射節點的發射信號強度,根據接收節點接收的信號強度,依據信號功率衰減速率與距離的關系進行測距,利用理論的或經驗的信號傳播模型將傳播損耗轉化為距離。常用的路徑損耗模型有:自由空間傳播、對數距離路徑損耗、對數常態分布等,本文選擇RSSI在WIN應用較多的對數常態分布模型[3]。其表達式如下所示。

Pr(d)=Pr(d0)+10nlg(d/d0)+Xσ

(4)

式中:d代表兩節點間的距離,d0代表參考距離,Pr(d)代表距離發射處dm接收到的信號功率強度,Pr(d0)代表距離發射處d0m接收到的信號功率強度,n代表信道衰減指數,Xσ代表均值為0、標準差為σ的高斯分布。實際計算中,通常d0取1 m,Pr(d0)也是取1 m處的信號功率強度。對于芯片CC2430,有以下關系成立。

RSSI=Pr(d)+RSSI_OFFEST

(5)

借助上述公式,可以推導出式(6)

PR(dBm)=A+10nlgr+Xσ

(6)

式中:A=Pr(1)+RSSI_OFFEST。系數A和n可以通過數據采集擬合得到。

2.2.3 策略3:修正參與定位的各信標節點的平均每跳距離

這是針對傳統算法第2步操作進行的改進,原算法是采用節點間的跳數值與接收到最近信標節點的平均每跳距離的乘積估算未知節點到各信標節點間的距離,用折線跳段距離代替直線距離。由于網絡拓撲結構是不規則的,且節點分布不可能均勻,局部區域內節點密度越低折線率越高,誤差就會越大。因此,當平均每跳距離的估算值與實際值相差較大時,未知節點到信標節點的估算距離與兩者間實際距離的誤差就會加大[8]。本文采用與傳統算法相似的步驟估算平均每跳距離,不同之處在于,信標節點還要估算出實際距離與估算距離間的誤差,再用該誤差作為修正值修正信標節點的平均每跳距離,最后將修正后的平均每跳距離作為校正值向外廣播,操作原理如下:

假設(xi,yi),(xj,yj)分別表示信標節點i和j的坐標,hij表示信標節點i與j之間的跳數值。Di,j表示信標節點i和j之間的實際距離,則有:

(7)

(8)

假設用Ei,j表示信標節點i與信標節點j之間的距離總估算誤差,則有:

(9)

(10)

則信標節點i與信標節點j之間修正之后的平均每跳距離為:

(11)

每個信標節點將修正后的平均每跳距離作為校正值發送到網絡中。通過這一步改進,能大大降低由于網絡局部區域內節點分布不均勻而帶來的距離估算誤差。

綜合上述3方面的改進策略,得出本文改進算法的節點操作流程,圖4是信標節點i的流程,圖5是未知節點節點x的流程。

圖4 改進后信標節點i的操作流程

圖5 改進后未知節點x的操作流程

3 仿真測試與結果分析

為評估本文改進算法的有效性,利用MATLAB7.10分別對傳統的DV-Hop算法、文獻[5]、文獻[8]改進算法及本文算法進行仿真實驗,并對實驗數據分析比較。為了取得更客觀、更準確的實驗數據,全部數據采用100次相同實驗的平均值。所有實驗均為二維隨機分布,盡量保證節點的分布具有一定的均勻性,實驗區域大小設定為100m×100m的正方形區域,信標節點與未知節點的通信半徑r相同,本文改進算法限跳閾值N取4,由于本研究尚沒有明確實用環境(不確定),式(6)中的參數A和n無法事先預知,本文算法中各節點均采用經驗數據,預設A=-40dBm,n=3,采用對數常態分布模型對1跳節點進行RSSI測距。

圖6所示是節點密度與定位誤差率的關系,檢測區域內通過改變節點的總數來改變平均網絡節點密度,設置信標節點占比恒定為10%,節點的通訊半徑r為20m不變,調整節點總數從100逐步遞增到180(每次增加10個)。通過對傳統的DV-Hop算法、文獻[5]、文獻[8]改進算法以及本文算法進行實驗數據對比,圖6可以明顯看出,隨著節點總數的增加,平均網絡節點密度逐步提高,4種算法的定位誤差率都得到了改善,且在相同節點數的情況下,本文算法的定位誤差率明顯優于傳統算法及其他兩種改進算法。總體看,本文算法比傳統DV-Hop算法的定位誤差率減少了約17%,與文獻[5]、文獻[8]相比減少了約5%。

圖6 節點密度對平均定位誤差率的影響

圖7 信標節點占比對定位誤差率的影響

圖7為信標點占比與定位誤差率的關系,在檢測區域內節點總數量固定為160個,通信半徑r=20m不變,調整信標節點占比從5%遞增到25%(每次增加5%)。仿真實驗圖7可以看出,上述4種算法都呈現隨著信標節點占比的增加,定位誤差率逐漸降低的趨勢,當信標節點占比為10%左右時,4種算法定位誤差率降低較快,而當信標節點占比達到20%以后,定位誤差率降低幅度趨緩。且本文算法比傳統DV-Hop算法以及文獻[5]和文獻[8]兩種改進算法定位更精確。總體看,本文算法比傳統DV-Hop算法的定位誤差率減少了約15%,比文獻[5]和文獻[8]減少了約4%。

圖8為節點通信半徑r與定位誤差率的關系,在檢測區域內設置節點總數量恒定為160個,信標節點占比為10%不變,調整節點的通信半徑r從15m逐漸遞增到35m(每次增加5m)。圖8可以看出,4種算法定位誤差率都是隨著節點通信半徑r的遞增而下降。數據顯示,本文算法比傳統DV-Hop算法的平均定位誤差率減少了約16%,與文獻[5]、文獻[8]相比減少了約5%。

圖8 節點通信半徑r對定位誤差率的影響

4 結論

傳統的DV-Hop算法用接收的最近信標節點的平均每跳距離乘以跳數值估算節點間的距離。本文在不改變傳統DV-Hop算法步驟的基礎上,提出一種基于跳數值修正的改進算法。仿真測試表明,在相同的網絡環境下,與傳統算法和其他改進算法想比,本文算法能更有效地降低距離估算誤差,提高節點的定位精度。但本文算法也有以下不足:一是為了增加定位的精確性,引入了RSSI測距技術,導致節點硬件開銷比傳統算法略有增大,二是對信標節點的平均每跳距離重新修正,也帶來了計算量稍有增加,但隨著微電子技術的高速發展,這些不足應該不成問題。在具體使用中,可以結合傳統DV-Hop算法、其他改進算法和本文算法綜合加以應用。

[1] 孫利民,李建中,陳渝,等. 無線傳感器網絡[M]. 北京:清華大學出版社,2005:135-155.

[2]Nicolescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems,2003,22(1/4):267-280.

[3]金純,葉誠,韓志斌,等. 無線傳感器網絡中DV-Hop定位算法的改進[J]. 計算機工程與設計,2013,34(2):401-404.

[4]Ren F Y,Huang H N,Lin C. Wireless Sensor Network[J]. Journal of Software,2003,4(7):1282-1291.

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

[6]Nagpal R,Shrobc H,Bachrach J. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network[C]//Proc of IPSN’03. Berlin:Springer-Verlag,2003:333-348.

[7]毛科技,趙小敏,何文秀,等. WSN中基于區域劃分的半自動DV-Hop定位算法[J]. 計算機科學,2012,39(3):39-42.

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

[9]Jonathan B,Christopher T. Handbook of sensor networks[C]//Stojm Enovic Ⅱ,ed. Proc of Localization in Sensor Networks,2005:1-18.

[10]Niculescu D,Nath B. Ad hoc Positioning System(APS)Using AOA[C]//Infocom 2003. 22nd Annual Joint Conference of the IEEE Computer and Communications. San Francisco,USA:2003,IEEE Societies(3):1734-1743.

[11]李牧東,熊偉,梁青. 基于人工蜂群改進的無線傳感器網絡定位算法[J]. 傳感技術學報,2013,26(2):241-245.

[12]Demirkol I,Ersoy C,Alagoz F. MAC Protocols for Wireless Sensor Networks A Survey[J]. IEEE Communications Magazine,2006,44(4):115-121.

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

[14]Basagni S,Carosi A,Melachrinoudis E,et al. Protocols and Model for Sink Mobility in Wireless Sensor Networks[J]. ACM Sigmo-Bile Mobile Computing and Communications Review,2006(10):28-30.

[15]劉玉錕,廖惜春,沈海燕,等. 無線傳感器網絡中DV-HOP定位算法的改進[J]. 五邑大學學報,2013,27(2):59-64.

The Improved DV-Hop Algorithm Based on Hop Count*

XIAShaobo*,ZHUXiaoli,ZOUJianmei,LIANLijun

(College of Computer and Correspondence,Shandong TV University,Jinan 250014,China)

The DV-Hop positioning algorithm for wireless sensor network has lager error in its practical application. The paper put forward an improved algorithm which based on the modified hop count to solve it. Under condition of using the hop-limitation mechanism,according to the hop mechanism of the unknown nodes and beacon nodes to classify and estimate. For the nodes which on the 1 hop region using RSSI ranging technology,and the others use the error of beacon nodes actual distance and its estimated distance to fix the average hop distance. The simulation tests show that under the same network conditions,compared with the original DV-Hop algorithm and other improved algorithm,this improved algorithm can effectively reduce the positioning error of the hop distance estimation,improve the average positioning accuracy and keep its stability.

wireless sensor network;node localization;the positioning error;hop-limitation mechanism;the average hop distance

夏少波(1964-),男,山東煙臺人,山東工業大學工學學士畢業,山東廣播電視大學計算機與通信學院教授,主要研究方向為無線傳感器網絡、寬帶無線接入技術等,xia_shaobo64@aliyun.com;

朱曉麗(1980-),女,山東臨沂人,山東師范大學計算機科學與技術專業碩士畢業,山東廣播電視大學計算機與通信學院副教授,主要研究方向為信息處理,網絡安全等,sdnuzxl@163.com;

鄒建梅(1979-),女,山東臨沂人,曲阜師范大學教育學碩士畢業,山東廣播電視大學計算機與通信學院副教授,主要研究方向為網絡與計算機通信、計算機支持的協同工作、云計算等,zjm1979@163.com。

項目來源:山東省自然科學基金面上項目(ZR2012FM033)

2014-11-16 修改日期:2015-01-27

C:6150P

10.3969/j.issn.1004-1699.2015.05.024

TP393

A

1004-1699(2015)05-0757-06