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

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

?

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

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

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

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

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

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

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è)備,從而導(dǎo)致節(jié)點成本也較高;無需測距技術(shù)主要有:APIT(Approximate Point-In-Triangulation Test)、質(zhì)心算法、DV-Hop(Distance Vector-Hop)、Amorphous等算法,特點是節(jié)點硬件配置簡單、成本低、網(wǎng)絡(luò)資源開銷少等,但定位誤差稍高。鑒于無線傳感器網(wǎng)絡(luò)的應(yīng)用特點,無需測距定位技術(shù)采用較多,且DV-Hop算法是目前應(yīng)用較多的節(jié)點定位算法之一。

1.1 DV-Hop算法描述

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

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

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

平均每跳跳距:

(1)

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

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

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

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

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

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代表信標(biāo)節(jié)點,標(biāo)號為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的實際距離則相差甚遠(yuǎn),然而DV-Hop算法規(guī)則是:一跳區(qū)域的所有節(jié)點的間距統(tǒng)統(tǒng)按一跳估值。這勢必造成較大誤差。

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

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

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

2 DV-Hop算法的改進(jìn)

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

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

2.2 本文對DV-Hop的改進(jìn)算法

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

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

隨著微電子技術(shù)、通信技術(shù)的高速發(fā)展,RSSI測距技術(shù)也向著低成本、高效能發(fā)展。且根據(jù)WSN具體應(yīng)用的需要,應(yīng)該將基于測距(Range Based)和無需測距(Range Free)技術(shù)融合使用,以收到取長補短的效果。目前,只需給傳感器節(jié)點增加小量的硬件開銷,即可實現(xiàn)精度較高的RSSI短距離(鄰居節(jié)點間)測距。鑒于此,在DV-Hop算法的第二步,節(jié)點接收到其他節(jié)點位置信息后,在進(jìn)行節(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、標(biāo)準(zhǔn)差為σ的高斯分布。在實際計算中,d0通常取1 m,Pr(d0)也是取1 m處的信號強度。在目前常用的RSSI芯片CC2430中,有以下關(guān)系成立[15]。

RSSI=Pr(d)+RSSI_OFFEST

(3)

借助上述公式,可以推導(dǎo)出式(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 改進(jìn)二:引入限跳機制

限制未知節(jié)點與信標(biāo)節(jié)點之間的跳數(shù),既可以提高定位精度,還能減少數(shù)據(jù)報的發(fā)送量[13]。信標(biāo)節(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)信標(biāo)節(jié)點的位置信息,降低了原DV-Hop算法全網(wǎng)洪泛而造成的高通信量和高分組沖突現(xiàn)象;再者,引入限跳機制后,可以保證只有在未知節(jié)點局部區(qū)域內(nèi)的信標(biāo)節(jié)點參與定位,這在一定程度上也會減少檢測環(huán)境不同區(qū)域內(nèi)由于節(jié)點分布不均勻造成的定位誤差,達(dá)到提高定位精度的目的。

限跳值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é)點所需要的最小信標(biāo)節(jié)點個數(shù),ρ表示信標(biāo)節(jié)點所占比例。為提高節(jié)點定位率和定位精度,N的取值通常要比理論計算值稍大一點。

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

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

(6)

(7)

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

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

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

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

3 仿真實驗與分析

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

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

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

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

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

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

4 結(jié)論

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

[1] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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ìn)[J].計算機應(yīng)用,2011,31(5):1189-1192.

[5]毛科技,趙小敏,何文秀,等.WSN中基于區(qū)域劃分的半自動DV-Hop定位算法[J].計算機科學(xué),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ìn)[J].傳感技術(shù)學(xué)報,2011,24(12):1782-1786.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.3969/j.issn.1004-1699.2014.07.019

TP393

:A

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