基于跳數(shù)區(qū)域劃分的DV-Hop改進算法*

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

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

?

基于跳數(shù)區(qū)域劃分的DV-Hop改進算法*

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

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

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

無線傳感器網(wǎng)絡(luò);定位;節(jié)點定位;限跳;跳數(shù)區(qū)域

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

1 DV-Hop算法

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

1.1 DV-Hop算法描述

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

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

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

平均每跳跳距:

(1)

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

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

圖1是傳統(tǒng)DV-Hop定位算法流程。

圖1 傳統(tǒng)DV-Hop定位算法流程

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

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

傳統(tǒng)DV-Hop算法的不足之處主要體現(xiàn)在以下幾個方面:

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

圖2 節(jié)點的一跳區(qū)域示意圖

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

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

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

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

2 DV-Hop算法的改進

2.1 DV-Hop算法研究現(xiàn)狀

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

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

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

2.2.1 改進一:引入RSSI測距技術(shù)

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

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

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

(2)

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

RSSI=Pr(d)+RSSI_OFFEST

(3)

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

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

(4)

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

2.2.2 改進二:引入限跳機制

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

限跳值N的大小依據(jù)網(wǎng)絡(luò)的連通度和節(jié)點密度設(shè)定,N的取值由式(5)確定[13]。

(5)

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

2.2.3 改進三:信標節(jié)點優(yōu)化組合進行多次三邊測量,質(zhì)心法估算x的坐標

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

(6)

(7)

圖4 信標節(jié)點優(yōu)化組合進行多次三邊測量估算x的坐標

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

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

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

3 仿真實驗與分析

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

圖6 網(wǎng)絡(luò)連通度與測距誤差率的關(guān)系

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

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

圖7 限跳值N=3時信標節(jié)點占比與定位誤差率的關(guān)系

圖8 限跳值N=4時信標節(jié)點占比與定位誤差率的關(guān)系

4 結(jié)論

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

[1] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[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]趙靈鍇,洪志全.基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進[J].計算機應用,2011,31(5):1189-1192.

[5]毛科技,趙小敏,何文秀,等.WSN中基于區(qū)域劃分的半自動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]李輝,熊盛武,劉毅,等.無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進[J].傳感技術(shù)學報,2011,24(12):1782-1786.

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

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

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

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

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

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

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

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

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

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

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

連麗君(1983-),女,山東威海人,南京郵電大學工學碩士畢業(yè),山東廣播電視大學計算機與通信學院講師,主要研究方向無線傳感器網(wǎng)絡(luò)、信號與信息處理等,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