基于跳數區域劃分的DV-Hop改進算法*

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

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

?

基于跳數區域劃分的DV-Hop改進算法*

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

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

DV-Hop節點定位算法使用跳數乘以平均每跳跳距估算節點間的距離,而平均每跳跳距的估算精確度與網絡的拓撲結構、節點密度、節點通信半徑等參數都有關系。針對DV-Hop算法過程存在的不足,為減少定位誤差,本文提出了一種基于跳數區域劃分的DV-Hop改進算法,引入了RSSI測距技術和限跳機制,優化參與定位的信標節點組合,采用多次三邊測量法,最后用質心法確定未知節點坐標。MATLAB仿真測試表明,在相同的檢測環境下,改進后的算法與其他改進算法相比,能更有效地降低定位誤差,提高定位精度。

無線傳感器網絡;定位;節點定位;限跳;跳數區域

無線傳感器網絡WSN(Wireless Sensor Network)是繼互聯網后又一種新型的信息獲取系統[1],已引起眾多國家、科研機構、專家學者的關注。WSN是由大量多功能、低功耗、成本低廉的傳感器節點組成的網絡[2],節點是被隨機布置或播撒在被檢測目標區域內,區域內節點通過無線通信的方式形成一個多跳自組織網絡[3],它們協作感知、采集和處理目標區域內的信息,節點的定位問題是無線傳感器網絡應用的關鍵技術之一[4-5]。在分布式定位算法中,只有少數節點配備有自定位設備,如全球定位系統GPS(Global Positioning System)等,稱之為信標節點,其他大部分節點是構造簡單、預先并不知道自身位置信息的節點,稱之為未知節點[6]。通常信標節點的成本要比未知節點高100倍左右[7],所以在定位誤差滿足要求的條件下,盡量降低信標節點的比例是節省WSN系統開銷的關鍵[4]。在眾多WSN應用的定位算法中,DV-Hop節點定位算法以其經濟性和簡單實效性得到了廣泛應用,但DV-Hop定位算法的缺點是定位誤差稍高[8-9]。本文深入剖析了DV-Hop定位算法過程中存在的不足,在不改變原算法框架、少量增加用于測距的硬件設備、減少網絡通信量的前提下,提出了一種基于跳數區域劃分的DV-Hop改進算法。

1 DV-Hop算法

節點定位技術按性能劃分,可分為基于測距(Range Based)和無需測距(Range Free)兩大類[10-12]。基于測距技術主要有:RSSI(Received Signal Strength Indicator),TOA(Time Of Arrival),TDOA(Time Difference Of Arrival)和AOA(Angle Of Arrival)等,其特點是定位精度較高,節點需要增加特殊的測距設備,從而導致節點成本也較高;無需測距技術主要有:APIT(Approximate Point-In-Triangulation Test)、質心算法、DV-Hop(Distance Vector-Hop)、Amorphous等算法,特點是節點硬件配置簡單、成本低、網絡資源開銷少等,但定位誤差稍高。鑒于無線傳感器網絡的應用特點,無需測距定位技術采用較多,且DV-Hop算法是目前應用較多的節點定位算法之一。

1.1 DV-Hop算法描述

DV-Hop定位算法是將距離矢量路由與GPS原理相結合的一種非測距分布式定位算法,該算法過程共分為3步[13-14]。

第一步:每個信標節點向全網廣播帶有自身地理位置信息的數據報,鄰居節點接收并存儲與它連通的每個信標節點間的位置信息和最小跳數。通過這個環節,網絡中的所有節點都能記錄下自己到每個信標節點間的最小跳數及它們的地理位置信息。

第二步:每個信標節點根據上述的第一步操作,記錄下了其他信標節點的坐標值以及它們間的跳數,接下來利用式(1),就可以估算出各個信標節點的平均每跳跳距[15]。式(1)中,(xi,yi),(xj,yj)分別表示信標節點i和j的坐標,hj表示信標節點i與j之間的跳數。

平均每跳跳距:

(1)

每個信標節點將計算出的平均每跳跳距作為校正值用帶有生存期字段的分組通過可控洪泛法廣播到網絡中。為保證大多數未知節點都能從最近的信標節點接收平均每跳跳距,網絡中的未知節點只記錄它接收到的第一個平均每跳跳距。未知節點利用接收到的這個平均每跳跳距乘以第一步操作記錄下的各信標節點的相關跳數,就可以計算出自己與連通范圍內的每個信標節點間的估算跳距D(i,x)。

第三步:未知節點利用第二步操作中估算出的到3個(或以上)信標節點間的估算跳距,采用三邊測量法或極大似然估計法估算出自己的坐標值。

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

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

DV-Hop定位算法屬于分布式定位算法APS(Ad Hoc Positioning System)的一種,該算法主要依賴距離矢量路由協議定位。實驗表明,在網絡平均連通度為10,信標節點比例為10%的環境中,DV-Hop的平均定位精度可以達到33%左右[3],這對于大多數WSN應用是足夠的。

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

傳統DV-Hop算法的不足之處主要體現在以下幾個方面:

①在DV-Hop算法過程中,通信范圍內能相互直接通信的節點互稱為鄰居節點,又稱之為一跳(1 h)區域節點[2],圖2所示為節點x的一跳區域示意圖。

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

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

②DV-Hop算法過程中,采用最近信標節點的平均每跳跳距與跳數的乘積求未知節點與周圍所有信標節點間的距離。而平均每跳距離的計算精確度與網絡的連通度、節點密度等有很大關系,且在實際的網絡拓撲結構中,信標節點到未知節點通常大多是折線路徑而不是直線路徑。因此當未知節點和信標節點間的跳數等于或大于2時,誤差將被累計[5],導致DV-Hop算法的估算距離與實際距離間存在較大的誤差,且誤差的大小與節點間跳數值成正比。

③在WSN網絡環境中,檢測區域內靠隨機播撒的節點很難滿足均勻分布的要求,分布于網絡不同區域的節點密度可能有較大差異[11],若節點密度低必然導致節點間跳段的折線率高,就會使節點間跳段長短不一致的現象加劇,造成估算誤差加大。

④在節點的連通范圍內,1跳、2跳、3跳……等是一些區域,這些區域是與節點的通信半徑r相關聯,通過分析不難發現,實際應用中跳段長度不可能是簡單的倍數關系,且必須考慮通信半徑r的影響。圖3所示,當通信半徑是圖中虛線圓時,6號節點為x的2跳節點,而當通信半徑增大到實心圓時,6號節點就變成x的1跳節點了。傳統DV-Hop算法,僅采用了簡單的倍數關系進行估算,忽略了節點通信半徑r的影響。

2 DV-Hop算法的改進

2.1 DV-Hop算法研究現狀

針對DV-Hop算法定位誤差較大的問題,國內外專家學者進行了大量的研究和創新。文獻[11]將定位問題轉化成全局最優化問題,把人工蜂群算法計算最優化問題的優勢,與DV-Hop定位算法的具體步驟相結合,提出了一種自適應人工蜂群算法,以提高定位精度;文獻[13]的改進是通過引入限跳機制,提出根據跳數來調節節點定位過程中的數據包接收量,算法在局部范圍內索取定位信息,并可以部分抵制MAC沖突帶來的錯誤信息,使定位精確度有所提高;文獻[15]借助RSSI測距技術,并對信標節點與待定位節點間估算距離排序選出誤差較小的一組數據,再用此組數據構建最小二乘法方程組中的被減方程,以提高定位精度。上述算法都一定程度上減小了定位誤差,達到了提高定位精度的目的。

2.2 本文對DV-Hop的改進算法

DV-Hop算法對于連通性好、各向同性的網絡,能夠得到較合理的平均每跳跳距,達到適當的定位精度。但對于拓撲結構不規則、節點密度分布不均勻的網絡,DV-Hop算法的定位精度就會急劇下降。針對傳統DV-Hop算法存在的不足,本文提出了一種基于節點跳數區域劃分的DV-Hop改進算法。在原DV-Hop算法基礎上,引入了RSSI測距技術和限跳機制,輔以優化參與定位的信標節點組合,最后采用質心法確定未知節點坐標等三方面的改進,具體描述如下。

2.2.1 改進一:引入RSSI測距技術

隨著微電子技術、通信技術的高速發展,RSSI測距技術也向著低成本、高效能發展。且根據WSN具體應用的需要,應該將基于測距(Range Based)和無需測距(Range Free)技術融合使用,以收到取長補短的效果。目前,只需給傳感器節點增加小量的硬件開銷,即可實現精度較高的RSSI短距離(鄰居節點間)測距。鑒于此,在DV-Hop算法的第二步,節點接收到其他節點位置信息后,在進行節點間跳距估算之前,先對節點間的跳數做一個判斷,若節點間的跳數是1跳,則直接采用RSSI測距技術,若節點間的跳數大于1跳,則按原DV-Hop算法估算跳距。

RSSI是一種根據信號的衰減程度推測距離的測距技術,式(2)是RSSI使用較多的一種理論模型[15]

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

(2)

式(2)中,Pr(d)代表距離發射處dm接受到的信號功率,Pr(d0)代表距離發射處d0m接收到的信號功率,n代表路徑衰減因子,Xσ代表均值為0、標準差為σ的高斯分布。在實際計算中,d0通常取1 m,Pr(d0)也是取1 m處的信號強度。在目前常用的RSSI芯片CC2430中,有以下關系成立[15]。

RSSI=Pr(d)+RSSI_OFFEST

(3)

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

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

(4)

其中A=Pr(1)+RSSI_OFFEST。系數A和n可以通過采集數據擬合得到,理論和實踐證明,在30 m左右的范圍內,RSSI可以獲得較理想的測距精度。

2.2.2 改進二:引入限跳機制

限制未知節點與信標節點之間的跳數,既可以提高定位精度,還能減少數據報的發送量[13]。信標節點向網絡中廣播帶有自身位置信息的分組時,在該分組再加上定義符N,稱之為門限跳數,網絡中鄰居節點接收到該分組時,首先檢測門限跳數N,如果N大于1,則N=N-1后,再轉發分組,否則丟棄該分組不再轉發,這樣可以保證每個節點僅收到N跳范圍內信標節點的位置信息,降低了原DV-Hop算法全網洪泛而造成的高通信量和高分組沖突現象;再者,引入限跳機制后,可以保證只有在未知節點局部區域內的信標節點參與定位,這在一定程度上也會減少檢測環境不同區域內由于節點分布不均勻造成的定位誤差,達到提高定位精度的目的。

限跳值N的大小依據網絡的連通度和節點密度設定,N的取值由式(5)確定[13]。

(5)

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

2.2.3 改進三:信標節點優化組合進行多次三邊測量,質心法估算x的坐標

這是針對傳統算法第三步操作進行的改進。圖4所示,方形點I1,I2,I3,…,I9代表信標節點,無標號的圓形點代表未知節點,用r代表節點的通信半徑,3個同心圓分別表示待定位節點x的1r、2r、3r通信半徑區域,也即3跳區域,假設在3跳這個局部區域內(3跳足夠),與未知節點x連通的共有I1,I2,I3,…,I9等9個信標節點,將這9個信標節點按跳數由小到大I1,I2,I3,…,I9排序,跳數越小估算出的跳距誤差就越小。經改進算法前兩步分別估算出x到I1,I2,I3,…,I9的修正后跳距,按由近及遠排序分別是d1,d2,d3,…,d9。再按照拓撲關系好且距離待定位節點x較近的原則,將參與定位的信標節點I1,I2,I3,…,I9優化組合。以3個信標節點為例,拓撲關系對定位精度的影響主要體現在如下幾種情況:一是當3個信標節點在一條直線(或近似一條直線)上時,二是當2個(或3個)信標節點相距太近且它們距待定位節點又太遠時,等等都會導致定位誤差過大。鑒于此,待定位節點收集限跳范圍內所有信標節點的數據報,根據跳數的大小判斷與各信標節點間的遠近關系,隨機選擇3個信標節點為一個組合,通過共線性可以擇優汰劣[16],對參與定位的信標節點優化組合,如圖4所示各三角形,最后進行3～5次三邊測量法定位。如:I1,I3和I4組合估算出x的坐標為(A1,B1),I2,I3和I4組合估算出x的坐標為(A2,B2),I1,I4和I6組合估算出x的坐標為(A3,B3),以及I1,I3和I9組合估算出x的坐標為(A4,B4)。最后再采用質心法估算出x的位置坐標(An,Bn),如下式(6)和(7)所示:

(6)

(7)

圖4 信標節點優化組合進行多次三邊測量估算x的坐標

圖5 改進后的DV-Hop未知節點算法流程

調整節點的限跳值N和通信半徑r都可以影響參與定位的信標節點數量M,且通信半徑r越大,在局部區域內參與定位的信標節點個數就會越多,組合就會更趨合理,定位誤差就會降低。改進后的DV-Hop定位算法信標節點的流程圖基本不變,未知節點的流程如圖5所示。

本文改進算法與傳統算法相比,在減少了定位誤差的同時,對節點能耗也會有影響。有利的一面是:改進一中,當節點間的跳數是1跳時,直接采用RSSI測距,減少了后續階段的能量開銷;再者,改進二引入限跳機制后,會減少節點間數據報的發送量,同樣有利于降低能耗。而不利的一面是:當通信半徑r、場景大小以及節點總數不變時,隨限跳值N增大,定位所需信標節點數M也增大,而增大M則會導致節點能耗的增加。

3 仿真實驗與分析

為評估所提改進算法的有效性和實用性,利用MATLAB7.0分別對傳統的DV-Hop算法、文獻[13]、文獻[15]改進算法及本文提出的DV-Hop改進算法進行仿真實驗,并對實驗數據分析比較。圖6描述了在網絡節點密度和信標節點占比都不變的條件下,通過改變節點的通信半徑調整網絡連通度,當隨著通信半徑的增大,鄰居節點數增多,網絡連通度逐漸升高時,測試上述4種算法的測距誤差率。仿真實驗的網絡模型主要參數如下:將總數150個節點隨機分布在100 m×100 m的正方形區域內,信標節點比例為10%,盡量保證節點的分布具有一定的均勻性,節點的通訊半徑r從15 m～25 m調整,使節點通信范圍內被檢測區域節點數目逐漸提高。對上述4種算法各進行50次分布測試取算術平均值。

圖6 網絡連通度與測距誤差率的關系

由圖6可以看出,隨著節點通信半徑的增大,通信范圍內節點數隨之提高,網絡連通度增大。在相同的檢測環境下比較4種算法,本文算法測距誤差率與DV-Hop相比降低了約10.5%,與文獻[13]、文獻[15]相比降低了約4.6%。

圖7和圖8描述了在網絡節點密度和節點連通度都不變的條件下,改變信標節點占比,且分別選取不同限跳值N時,測試上述4種算法的定位誤差率。仿真實驗的網絡模型主要參數為:在100 m×100 m的正方形區域內,部署總數為150個節點,通信半徑為20 m,信標節點比例從6%～22%調整,限跳N值分別取3和4。測試結果表明,在信標節點占比相同的情況下,隨著限跳N值的增大,定位精度得到提高。本文算法與傳統的DV-Hop算法、文獻[13]、文獻[15]改進算法相比,其節點的定位精度提高幅度較大,隨著信標節點占比的增加且達到一定數值后,4種算法的定位誤差率均趨于穩定。圖7中當N=3時,本文算法比傳統DV-Hop算法的平均定位誤差率減少了約14.3%,與文獻[13]、文獻[15]相比減少了約6.4%;圖8中當N=4時,本文算法比傳統DV-Hop算法的平均定位誤差率減少了約13.8%,與文獻[13]、文獻[15]相比減少了約5.3%。

圖7 限跳值N=3時信標節點占比與定位誤差率的關系

圖8 限跳值N=4時信標節點占比與定位誤差率的關系

4 結論

傳統的DV-Hop算法采用來之最近信標節點的平均每跳跳距乘以跳數計算節點間距離,由于節點間的傳輸路徑大多是折線,且不同區域的節點密度具有隨機性和不均勻性,從而造成定位誤差較大。本文探討的DV-Hop改進算法優點在于:在不改變傳統DV-Hop算法總體框架的基礎上,引入RSSI測距技術,提出了限跳機制,僅僅增加了少量的硬件設備,既達到降低測距誤差的目的,還大大減少了節點間的通信量,有利于減少節點能耗,提高網絡壽命。最后還采用了優化組合信標節點和質心法估算未知節點坐標,進一步提高了定位精度;不足之處是:對于隨機部署節點的WSN網絡,限制跳數可能影響到邊沿節點的定位不能100%成功。此外,本文算法對節點能耗的影響利弊參半,尚需進行全面的分析計算或仿真研究。這將是本課題小組下一步探討的要點。

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

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

[3]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,IEEE Societies,2003(3):1734-1743.

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

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

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

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

[8]王穎,石昊旸.改進的無線傳感器網絡DV-Hop定位算法[J].計算機工程,2012,38(7):66-69.

[9]楊智鋒,裴騰達,裴炳南,等.基于代數重建法的DV-Hop定位算法[J].計算機工程,2010,36(15):117-119.

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

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

[12]張佳,吳延海,石峰,等.基于DV-HOP的無線傳感器網絡定位算法[J].計算機應用,2010,30(2):323-326.

[13]于寧,萬江文,吳銀鋒.無線傳感器網絡定位算法研究[J].傳感技術學報,2007,20(1):187-192.

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

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

[16]江禹生,馮硯毫.一種新的DV-Hop定位算法[J].傳感技術學報,2010,23(12):1815-1819.

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

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

連麗君(1983-),女,山東威海人,南京郵電大學工學碩士畢業,山東廣播電視大學計算機與通信學院講師,主要研究方向無線傳感器網絡、信號與信息處理等,lianlij2002@163.com。

ImprovedDV-HopAlgorithmBasedonRegionalDivisionofHopCount*

XIAShaobo*,ZOUJianmei,ZHUXiaoli,LIANLijun

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

DV-Hop node localization algorithm uses the hop count multiplied by the average per hop distance to estimate the distance between nodes.The accuracy of estimation is related to the topology of the network,the node density and the node communication radius parameters.Aiming at the defect existing in DV-Hop algorithm process,and in order to reduce the positioning error as well,this paper puts forward the improved DV-hop algorithm based on regional division of hop count.The RSSI location technology and the hop-limitation mechanism was introduced,the combination of the beacon nodes optimized,the three-sided measurement adopted several times,and finally,the centroid method used to determine the coordinates of the unknown nodes.The MATLAB simulation tests show that this improved algorithm,compared with other algorithms,can effectively reduce the positioning error and improve the positioning accuracy in the same environment.

wireless sensor network;location;node localization;limit hop;region of hop count

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

2014-01-18修改日期:2014-06-10

10.3969/j.issn.1004-1699.2014.07.019

TP393

:A

:1004-1699(2014)07-0964-06