基于跳數(shù)修正的DV-Hop改進(jìn)算法*

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

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

?

基于跳數(shù)修正的DV-Hop改進(jìn)算法*

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

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

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

無線傳感器網(wǎng)絡(luò);節(jié)點定位;定位誤差;限跳機制;平均跳距

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量智能傳感器節(jié)點構(gòu)成的集信息采集、傳送和處理為一體的綜合智能信息網(wǎng)絡(luò),具有環(huán)境適應(yīng)性強、自組織能力和組網(wǎng)成本低等特點[1]。網(wǎng)絡(luò)節(jié)點協(xié)作感知、采集和處理覆蓋區(qū)域內(nèi)被檢測對象的信息,并將結(jié)果傳送給觀測者。WSN在目標(biāo)跟蹤、環(huán)境監(jiān)測甚至是軍事偵測等眾多的領(lǐng)域都有廣泛的應(yīng)用,引起了學(xué)術(shù)界的廣泛關(guān)注和深入研究[2]。對大多數(shù)WSN應(yīng)用而言,沒有時空標(biāo)識的數(shù)據(jù)和信息是沒有意義的,因此,節(jié)點的準(zhǔn)確定位在傳感器網(wǎng)絡(luò)的應(yīng)用中起關(guān)鍵作用[3-4]。目前研究者已經(jīng)提出了很多節(jié)點定位算法。按定位所采用的節(jié)點間距離獲取方式,一般把定位算法分為基于測距算法(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)、凸規(guī)劃定位、質(zhì)心定位、MDS-MAP定位、Amor-phous定位和APIT(Approximate PIT Test)定位等。上述眾多算法各有其優(yōu)勢和不足,第1類方法采用測距技術(shù),通常精度較高,但需要附加硬件設(shè)備而且測距效果受環(huán)境影響較大[8];第2類方法雖然精度稍低,但因其成本低廉,受環(huán)境影響較小等優(yōu)點,越來越受到關(guān)注。尤其是DV-Hop節(jié)點定位算法,以其經(jīng)濟性和簡單實效性得到了廣泛應(yīng)用,但DV-Hop定位算法的缺點是定位誤差稍高[9]。本文深入分析了DV-Hop定位算法存在的缺陷,在不改變原算法步驟,少量增加硬件設(shè)備的條件下,提出了一種基于跳數(shù)修正的DV-Hop改進(jìn)算法。

1 傳統(tǒng)DV-Hop算法及其存在的不足

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

1.1 傳統(tǒng)DV-Hop算法描述

傳統(tǒng)DV-Hop節(jié)點定位算法分為以下3個步驟[11-12]:

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

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

(1)

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

(2)

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

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

圖1 DV-Hop定位算法流程

相關(guān)研究表明,在網(wǎng)絡(luò)節(jié)點平均連通度為10,信標(biāo)節(jié)點占比為10%,且各向同性的環(huán)境中,DV-Hop的平均定位精度可以達(dá)到33%左右[4],可見對于節(jié)點分布均勻、且密集型的網(wǎng)絡(luò),該算法的定位精度基本能滿足要求。但在實際應(yīng)用中,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)常常是隨機且不規(guī)則的,如果直接使用DV-Hop算法,定位精度就會迅速下降。

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

①實際應(yīng)用中,節(jié)點是隨機播撒在檢測區(qū)域內(nèi),網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是不規(guī)則的,且節(jié)點分布不可能均勻,這必然造成網(wǎng)絡(luò)中不同區(qū)域內(nèi)節(jié)點密度差別較大[13],從而使不同區(qū)域內(nèi)的節(jié)點接收到的與各信標(biāo)節(jié)點間的最小跳數(shù)值存在一定偏差,且隨著跳數(shù)值的增大,該偏差也將累計加大,導(dǎo)致測距誤差變大,影響定位精度。

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

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

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

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

圖3 節(jié)點分布示意圖

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

2 改進(jìn)策略分析

2.1 已有的改進(jìn)策略分析

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

2.2 本文改進(jìn)策略描述

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

2.2.1 策略1:引入限跳機制

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

跳數(shù)閾值N的大小主要依據(jù)網(wǎng)絡(luò)的連通度和節(jié)點密度確定[15],如式(3)所示。

(3)

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

2.2.2 策略2:引入RSSI測距技術(shù)

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

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

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

(4)

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

RSSI=Pr(d)+RSSI_OFFEST

(5)

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

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

(6)

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

2.2.3 策略3:修正參與定位的各信標(biāo)節(jié)點的平均每跳距離

這是針對傳統(tǒng)算法第2步操作進(jìn)行的改進(jìn),原算法是采用節(jié)點間的跳數(shù)值與接收到最近信標(biāo)節(jié)點的平均每跳距離的乘積估算未知節(jié)點到各信標(biāo)節(jié)點間的距離,用折線跳段距離代替直線距離。由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是不規(guī)則的,且節(jié)點分布不可能均勻,局部區(qū)域內(nèi)節(jié)點密度越低折線率越高,誤差就會越大。因此,當(dāng)平均每跳距離的估算值與實際值相差較大時,未知節(jié)點到信標(biāo)節(jié)點的估算距離與兩者間實際距離的誤差就會加大[8]。本文采用與傳統(tǒng)算法相似的步驟估算平均每跳距離,不同之處在于,信標(biāo)節(jié)點還要估算出實際距離與估算距離間的誤差,再用該誤差作為修正值修正信標(biāo)節(jié)點的平均每跳距離,最后將修正后的平均每跳距離作為校正值向外廣播,操作原理如下:

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

(7)

(8)

假設(shè)用Ei,j表示信標(biāo)節(jié)點i與信標(biāo)節(jié)點j之間的距離總估算誤差,則有:

(9)

(10)

則信標(biāo)節(jié)點i與信標(biāo)節(jié)點j之間修正之后的平均每跳距離為:

(11)

每個信標(biāo)節(jié)點將修正后的平均每跳距離作為校正值發(fā)送到網(wǎng)絡(luò)中。通過這一步改進(jìn),能大大降低由于網(wǎng)絡(luò)局部區(qū)域內(nèi)節(jié)點分布不均勻而帶來的距離估算誤差。

綜合上述3方面的改進(jìn)策略,得出本文改進(jìn)算法的節(jié)點操作流程,圖4是信標(biāo)節(jié)點i的流程,圖5是未知節(jié)點節(jié)點x的流程。

圖4 改進(jìn)后信標(biāo)節(jié)點i的操作流程

圖5 改進(jìn)后未知節(jié)點x的操作流程

3 仿真測試與結(jié)果分析

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

圖6所示是節(jié)點密度與定位誤差率的關(guān)系,檢測區(qū)域內(nèi)通過改變節(jié)點的總數(shù)來改變平均網(wǎng)絡(luò)節(jié)點密度,設(shè)置信標(biāo)節(jié)點占比恒定為10%,節(jié)點的通訊半徑r為20m不變,調(diào)整節(jié)點總數(shù)從100逐步遞增到180(每次增加10個)。通過對傳統(tǒng)的DV-Hop算法、文獻(xiàn)[5]、文獻(xiàn)[8]改進(jìn)算法以及本文算法進(jìn)行實驗數(shù)據(jù)對比,圖6可以明顯看出,隨著節(jié)點總數(shù)的增加,平均網(wǎng)絡(luò)節(jié)點密度逐步提高,4種算法的定位誤差率都得到了改善,且在相同節(jié)點數(shù)的情況下,本文算法的定位誤差率明顯優(yōu)于傳統(tǒng)算法及其他兩種改進(jìn)算法?？傮w看,本文算法比傳統(tǒng)DV-Hop算法的定位誤差率減少了約17%,與文獻(xiàn)[5]、文獻(xiàn)[8]相比減少了約5%。

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

圖7 信標(biāo)節(jié)點占比對定位誤差率的影響

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

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

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

4 結(jié)論

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

[1] 孫利民,李建中,陳渝,等. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社,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]金純,葉誠,韓志斌,等. 無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J]. 計算機工程與設(shè)計,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]趙靈鍇,洪志全. 基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進(jìn)[J]. 計算機應(yīng)用,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中基于區(qū)域劃分的半自動DV-Hop定位算法[J]. 計算機科學(xué),2012,39(3):39-42.

[8]石為人,賈傳江,梁煥煥. 一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-HOP定位算法[J]. 傳感技術(shù)學(xué)報,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ìn)的無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報,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]李輝,熊盛武,劉毅,等. 無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進(jìn)[J]. 傳感技術(shù)學(xué)報,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]劉玉錕,廖惜春,沈海燕,等. 無線傳感器網(wǎng)絡(luò)中DV-HOP定位算法的改進(jìn)[J]. 五邑大學(xué)學(xué)報,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-),男,山東煙臺人,山東工業(yè)大學(xué)工學(xué)學(xué)士畢業(yè),山東廣播電視大學(xué)計算機與通信學(xué)院教授,主要研究方向為無線傳感器網(wǎng)絡(luò)、寬帶無線接入技術(shù)等,xia_shaobo64@aliyun.com;

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

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

項目來源:山東省自然科學(xué)基金面上項目(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