Improved DV-Hop Location Algorithm Based on Hop Correction*

WEN Jiangtao，F(xiàn)AN Xuemin，WU Xijun

(Key Lab of Measurement Technology and Instrumentation of Hebei Province，Yanshan University，Qinhuangdao，Hebei066004，China)

Improved DV-Hop Location Algorithm Based on Hop Correction*

WEN Jiangtao*，F(xiàn)AN Xuemin，WU Xijun

(Key Lab of Measurement Technology and Instrumentation of Hebei Province，Yanshan University，Qinhuangdao，Hebei066004，China)

To solve the problem that the hop value in traditional DV－Hop algorithm can’t represent the real distance，an improved algorithm based on RSSI is proposed.First of all，the first hop is subdivided into several grades based on RSSI，then the rest hops are modified with the distance ratio of adjacent nodes which is transformed into the corresponding relationship of the RSSI.The simulation results show that the proposed algorithm in the paper possesses of the higher location precision than the traditional algorithm without extra hardware in the same network environment. Key words:wireless sensor network;DV－Hop;received signal strength indicator(RSSI);hop correction;localization accuracy

無線傳感器網(wǎng)絡(luò)的定位算法大致可分為兩類:一類是基于測距(Range－Based)的定位算法，其中最常用的是基于接收信號強度指示(RSSI)［1］的測距方法。另一類是無需測距(Range－Free)的定位算法。非測距定位算法不需要測量相關(guān)物理量信息，而是通過節(jié)點之間的網(wǎng)絡(luò)連通性來進行定位［2］，其憑借在功耗、成本等方面的優(yōu)勢，受到越來越多的關(guān)注。目前主要有質(zhì)心算法(Centroid)［3］、DV－Hop［4－5］算法、APIT算法［6］和Amorphous［7］等算法。其中DV－Hop算法巧妙地將節(jié)點間的距離測量轉(zhuǎn)化為跳數(shù)與平均跳距的乘積，是目前研究最廣泛的算法之一。

針對DV－Hop算法在拓?fù)洳灰?guī)則的網(wǎng)絡(luò)中定位誤差較大的問題的研究已經(jīng)取得了一些成果。文獻［8］采用最小均方誤差準(zhǔn)則對平均每跳距離進行修正，文獻［9］首先采用最小二乘法對信標(biāo)節(jié)點間的平均跳距修正，然后對未知節(jié)點收到的平均跳距進行加權(quán)處理，這兩種改進算法主要修正的是平均跳距，定位精度提高的同時計算量也顯著增大。文獻［10］只對信標(biāo)節(jié)點與未知節(jié)點之間的跳數(shù)作了修正，并未考慮未知節(jié)點之間跳數(shù)的優(yōu)化。文獻［11］利用相鄰節(jié)點接收到的RSSI的比值對跳數(shù)進行加權(quán)，其直接把RSSI的比值作為權(quán)值修正跳數(shù)，精度提高不明顯;針對上述算法的不足本文作了如下改進:引入RSSI測距技術(shù)對第1階段的最小跳數(shù)值從兩個方面進行了修正，首先基于信標(biāo)節(jié)點的直接鄰居節(jié)點接收到的RSSI對第1跳分級，細(xì)化跳數(shù)，然后把跳數(shù)間實際距離的比值作為權(quán)值，并將其轉(zhuǎn)化為RSSI的關(guān)系式對跳數(shù)進行加權(quán)處理使其更接近實際值，進而提高定位精度，通過仿真比較了改進算法與原始算法的性能。

1 DV－Hop算法原理

DV－Hop算法是一種基于距離矢量的分布式定位算法［12］。其定位過程大致分為3個階段。

第1階段:通過典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點得到距離每個信標(biāo)節(jié)點的最小跳數(shù)值。

第2階段:每個信標(biāo)節(jié)點在獲得其他信標(biāo)節(jié)點的位置信息和最小跳數(shù)后，根據(jù)式(1)計算自身的平均每跳距離:

其中，(xi，yi)，(xj，yj)分別為信標(biāo)節(jié)點i，j的坐標(biāo)，hij(i≠j)表示信標(biāo)節(jié)點i，j之間的最小跳數(shù)。該信標(biāo)節(jié)點將計算得到的平均跳距利用可泛洪方式廣播到網(wǎng)絡(luò)中。未知節(jié)點僅記錄收到的第1個跳距值并將該值轉(zhuǎn)發(fā)，然后結(jié)合第1階段得到的最小跳數(shù)值求得與相應(yīng)信標(biāo)節(jié)點的距離。

第3階段:未知節(jié)點得到3個或3個以上與信標(biāo)節(jié)點的距離后，利用三邊定位法或極大似然估計法計算自身的位置坐標(biāo)，從而完成定位。

2 DV-Hop算法改進

傳統(tǒng)DV－Hop算法中，不直接測量鄰居節(jié)點之間的物理量，如距離或角度，而是依據(jù)節(jié)點間的跳數(shù)信息與平均跳距的乘積來估計距離。

在第1階段計算最小跳數(shù)的時候，只要通信半徑R之內(nèi)的距離無論遠近都記為1跳，如圖1所示，節(jié)點1，2的跳數(shù)都記為1，可是他們與信標(biāo)節(jié)點D的實際距離相差很大，依賴這種不能反映實際距離大小的跳數(shù)值來定位，在節(jié)點均勻分布時尚且可以得到合理的平均跳距，但是網(wǎng)絡(luò)拓?fù)湟话闶遣灰?guī)則的，運用相同的平均跳距來估計距離必然會產(chǎn)生較大的定位誤差。

圖1 跳數(shù)示意圖

針對上述問題，本文引入距離這個因素來修正第1階段的跳數(shù)以提高定位精度。以信標(biāo)節(jié)點到直接鄰居節(jié)點的距離作為基準(zhǔn)，設(shè)其距離為L1，跳數(shù)為h1，以其他鄰居節(jié)點間的距離與基準(zhǔn)距離的比值作為權(quán)值修正該跳跳數(shù)。如圖2所示，第2跳的權(quán)值為L2/L1，該跳跳數(shù)為h1·(L2/L1)。則節(jié)點3到信標(biāo)節(jié)點E的跳數(shù)為h1·(1+L2/L1+L3/L1)。因為整個拓?fù)渚W(wǎng)絡(luò)中第1跳的距離也差異很大，所以第1跳的跳數(shù)不能籠統(tǒng)的記為1，本文中對第1跳根據(jù)距離大小進行分級處理。

實際定位過程中距離是未知的，但是大多數(shù)節(jié)點都有檢測信號強度(RSSI)的能力，而RSSI是一種利用信號傳播過程中不斷衰減的信號強度來推測距離的測距技術(shù)。所以在傳統(tǒng)DV－Hop算法中引入RSSI測距技術(shù)進行輔助定位以降低定位誤差。

2.1 RSSI測距原理

無線傳感器網(wǎng)絡(luò)中應(yīng)用最廣泛的信號傳播損耗模型是Shadowing模型［13］，其表達式如下:

上式中:d為接收端與發(fā)射端的距離，d0為選定的一個與發(fā)射端的參考距離，通常選為1 m。Pr(d)表示距離為d時的平均接收功率，單位為W。n為實際測量環(huán)境的路徑損耗因子，范圍在2～6之間。

在上述模型中引入了一個均值為零，標(biāo)準(zhǔn)差為σ服從高斯分布的隨機噪聲，用Xσ表示。若功率以dB作為計量單位，設(shè)距離發(fā)射節(jié)點為d時的接收功率為Pr(d)dB，且令d0=1 m，并設(shè)A為距離發(fā)射端1 m處多次測量所得RSSI值的平均值，則根據(jù)式(2)可以推導(dǎo)出距離發(fā)射端為d處的RSSI值為

Shadowing 模型描述了節(jié)點接收功率與信號傳播距離的關(guān)系，一般情況下距離發(fā)射端越遠的節(jié)點接收到的RSSI值越小。未知節(jié)點可以根據(jù)自己接收到的RSSI值通過Shadowing模型直接計算與信標(biāo)節(jié)點的距離。下面利用RSSI值與距離的關(guān)系對DV－Hop算法中的跳數(shù)值進行修正。

2.2 跳數(shù)修正

2.2.1 基于RSSI對第1跳分級

本文是以第1跳的距離作為基準(zhǔn)作加權(quán)處理的，所以第1跳的跳數(shù)值h1需反映出距離的大小。鑒于通信半徑R對同一批節(jié)點而言是相對固定的，因此把R設(shè)為1跳的理想距離，然后對R做分級處理，每一級對應(yīng)一個跳數(shù)，這樣可以細(xì)化節(jié)點間的跳數(shù)，有助于提高測距精度進而提高定位精度。

設(shè)節(jié)點的通信半徑為R，把第1跳分為m級，信標(biāo)節(jié)點與其直接鄰居節(jié)點間的實際距離為x，第1跳的跳數(shù)記為h1，i為小于m的正整數(shù)，則

實際定位過程中距離是未知的，但是每個節(jié)點都有接收RSSI的能力，所以可以根據(jù)信號傳播衰減模型的式(3)把跳數(shù)與距離的關(guān)系轉(zhuǎn)化為跳數(shù)與接收功率的關(guān)系。當(dāng)時，相應(yīng)的RSSI值的關(guān)系為

由于跳數(shù)對應(yīng)一個功率值的區(qū)間，而高斯噪聲引起功率值的波動遠遠小于這個區(qū)間，所以噪聲對跳數(shù)值影響不大可以忽略，則第1跳的跳數(shù)與對應(yīng)接收功率的關(guān)系如下所示上式根據(jù)信標(biāo)節(jié)點的直接鄰居節(jié)點接收到的RSSI值對跳數(shù)進行分級細(xì)化，該方法使DV－Hop算法中的跳數(shù)值不再是整數(shù)，而是小數(shù)，這有效地提高了跳數(shù)值的準(zhǔn)確性，從而降低了定位誤差。也為后續(xù)跳數(shù)的加權(quán)修正計算提供了保證。

2.2.2 利用RSSI對跳數(shù)加權(quán)修正

引入權(quán)值的定義:在大于一跳的跳數(shù)中，權(quán)值Hj設(shè)為第j跳與第1跳實際距離的比值，其中j為正整數(shù)

同理，需要把權(quán)值與距離的關(guān)系轉(zhuǎn)化為權(quán)值與接收功率的關(guān)系。Shadowing模型的表達式(2)描述了接收功率與信號傳播距離的關(guān)系，該公式里接收功率的單位是W(瓦特)，但是在實際的無線信號傳播過程中，功率常是以dB作為計量單位，以RSSI值的形式從寄存器或是從數(shù)據(jù)包中獲取的。所以對式(2)進一步轉(zhuǎn)化，設(shè)距發(fā)送端為d處的節(jié)點接收到的RSSI用Pr(d)dB表示，則式(2)可寫為

根據(jù)式(7)把權(quán)值轉(zhuǎn)化為節(jié)點接收到的RSSI值的關(guān)系式

得到權(quán)值后與第1跳跳數(shù)h1相乘便為該跳的修正跳數(shù)，這種方法可以修正所有節(jié)點間的跳數(shù)，也包括信標(biāo)節(jié)點間的跳數(shù)，進而可以修正平均每跳距離，使測距誤差進一步降低。

2.3 改進后算法的具體步驟

對跳數(shù)進行分級和加權(quán)處理后改進算法的具體步驟如下:

(1)第1跳:在信標(biāo)節(jié)點廣播的信息數(shù)據(jù)包中加入一個新的數(shù)據(jù)量，RSSI值，即信息數(shù)據(jù)包為{ID，(x，y)，Hopcount，RSSI}，其中ID為信標(biāo)節(jié)點編號，(x，y)為信標(biāo)節(jié)點位置坐標(biāo)，Hopcount為當(dāng)前數(shù)據(jù)包的跳數(shù)，初始值為0。其直接鄰居節(jié)點收到該數(shù)據(jù)包后根據(jù)式(5)計算第1跳的跳數(shù)，更新Hopcount域，并記錄收到該數(shù)據(jù)包時的RSSI值。

(2)其余跳:網(wǎng)絡(luò)中其他節(jié)點收到直接鄰居節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)包后用自身接收該數(shù)據(jù)包時的RSSI值與數(shù)據(jù)包中的RSSI值利用式(8)獲得該跳的權(quán)值Hj，并將數(shù)據(jù)包中的跳數(shù)加上加權(quán)跳數(shù)后保存下來，即Hopcountj=Hopcountj－1+Hjh1，同時將更新后的數(shù)據(jù)包轉(zhuǎn)發(fā)給它的鄰居節(jié)點，但RSSI域并不更新，其一直保存的是第1跳接收到的RSSI值。

(3)第2階段與第3階段仍按照標(biāo)準(zhǔn)的DVHop算法計算平均跳距并利用最小二乘法計算未知節(jié)點的坐標(biāo)，完成定位。

3 仿真結(jié)果驗證

為了比較改進后的DV－Hop算法與傳統(tǒng)DVHop算法的性能，在MATLAB 7.0平臺上進行了仿真實驗，并和文獻［11］中基于相鄰節(jié)點間RSSI直接相除進行加權(quán)的改進算法進行了比較，下面分別研究了在不同錨節(jié)點比例，通信半徑下傳統(tǒng)算法與改進算法的定位精度。

3.1 仿真環(huán)境及參數(shù)設(shè)定

仿真環(huán)境是在100 m×100 m的正方形區(qū)域內(nèi)隨機分布100個節(jié)點，從中隨機選取信標(biāo)節(jié)點，設(shè)所有節(jié)點具有相同的通信半徑R。為了消除由于節(jié)點隨機分布造成的誤差的不穩(wěn)定性，在相同的網(wǎng)絡(luò)環(huán)境下分別進行1 000次仿真實驗取平均值。

歸一化定位誤差是衡量算法定位精度的指標(biāo)［14］。設(shè)節(jié)點i的真實位置為Xi，估計位置為X'i，則定位誤差為|Xi－X'i|，共有N個未知節(jié)點，節(jié)點通信半徑為R，共仿真K次，則所有未知節(jié)點的平均定位誤差error為

則歸一化定位誤差為:

3.2 算法精度分析

圖3是通信半徑R=30 m，第1跳分為不同級數(shù)時，節(jié)點的定位誤差圖。從圖中可以看出隨著信標(biāo)節(jié)點比例的增大，3條曲線的定位誤差都在降低。而且所分級數(shù)越多，定位誤差越小，這是因為m=3比m= 2時所得跳數(shù)值更準(zhǔn)確所以定位精度更高。但是m =2比m=1的精度提高了6%左右，而m=3比m= 2只提高了4%左右，可見隨著級數(shù)的增大，誤差降低的百分比會越來越小。而且分級越多計算量便越大，折中選擇，本文算法中所選的級數(shù)為m=3。

圖3 不同級數(shù)時的歸一化誤差

圖4歸一化定位誤差與錨節(jié)點比例的關(guān)系

圖4 給出了通信半徑為30 m時未知節(jié)點歸一化定位誤差與信標(biāo)節(jié)點比例的關(guān)系曲線，由仿真結(jié)果可以看出，算法誤差隨著信標(biāo)節(jié)點比例的增加而減小并趨于穩(wěn)定。在同一錨節(jié)點比例時，本論文提出改進算法的定位精度比傳統(tǒng)DV－Hop算法提高了15%左右，而文獻［11］提出的改進算法定位精度只能提高5%左右，由此可見，本文提出的算法改進更有效。

圖5給出了信標(biāo)節(jié)點比例為30%時，歸一化定位誤差與通信半徑R的關(guān)系，從圖中可以看出隨著通信半徑的增大，節(jié)點定位誤差都有減小的趨勢，但是本文算法受通信半徑的影響最小，這是因為本文的改進算法有效地修正了節(jié)點間的跳數(shù)，使半徑增大時跳數(shù)誤差沒有明顯增大，而且在同一半徑下本文提出算法的定位精度最高。

圖5 歸一化定位誤差與通信半徑的關(guān)系

3.3 算法復(fù)雜度分析

表1給出了本文算法與其他算法在通信開銷，算法復(fù)雜度，硬件復(fù)雜度上的性能比較。設(shè)網(wǎng)絡(luò)中節(jié)點總數(shù)為N，信標(biāo)節(jié)點數(shù)為A。表中的定位精度選取通信半徑為30 m，錨節(jié)點比例為25%時的數(shù)據(jù)，按照式(11)計算得到。因為本文的改進算法只在數(shù)據(jù)包中添加了一個RSSI量，并未改變數(shù)據(jù)包的傳送路徑所以通信開銷并未增加。從表1中可以看出與傳統(tǒng)DV－Hop算法相比，本文改進算法在以不增加通信開銷的基礎(chǔ)上以較小的計算量代價獲得了更高的定位精度。

表1 各種算法性能比較

在處理器主頻為3.30 GHz內(nèi)存為2.0 Gbyte的計算機上，對傳統(tǒng)DV－Hop算法仿真運行1 000次的時間為3.309 s，本文所提出的改進算法為4.958 s，可見單次時間差為1.6 ms左右，這是由于本文算法在計算跳數(shù)時引入RSSI值對跳數(shù)進行修正使得計算量有所增加，但依然具有較快的速度滿足實時定位的要求。

4 結(jié)論

本文提出的基于RSSI的DV－Hop改進算法引入RSSI測距技術(shù)對原始DV－Hop算法中的跳數(shù)值從兩個方面分別進行了修正，有效地解決了拓?fù)洳灰?guī)則網(wǎng)絡(luò)中，因為跳數(shù)值不能反映實際距離大小而導(dǎo)致定位誤差較大的問題，在無需增加額外硬件的條件下提高了定位精度。仿真結(jié)果表明在100 m×100 m的正方形區(qū)域，節(jié)點隨機分布的網(wǎng)絡(luò)環(huán)境下，改進后算法的定位精度比原始算法提高了15%左右。

［1］Deng－Yin Z，Guo－Dong C.A Union Node Localization Algorithm Based on RSSI and DV－Hop for WSNs［C］//Instrumentation，Measurement，Computer，Communication and Control(IMCCC)，2012 Second International Conference on.IEEE，2012:1094－1098.

［2］Zheng J，Wu C，Chu H，et al.An Improved DV－Hop Localization Algorithm［C］//Progress in Informatics and Computing(PIC)，2010 IEEE International Conference on IEEE，2010，1:469－471.

［3］Hongyang C，Sezaki K，Ping D，etal.An Improved DV－Hop Localization Algorithm with Reduced Node Location Error for Wireless Sensor Networks［J］.IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2008，91(8): 2232－2236.

［4］Chen H，Sezaki K，Deng P，et al.An Improved DV－Hop Localization Algorithm forWireless Sensor Networks［C］//Industrial Electronics and Applications，2008.ICIEA 2008.3rd IEEE Conference on.IEEE，2008:1557－1561.

［5］Zhang J，Wu Y H，Shi F，et al.Localization Algorithm Based on DV－HOP for Wireless Sensor Networks［J］.Journal of Computer Applications，2010，30(2):323－326.

［6］Tian S，Zhang X，Liu P，etal.A RSSI－Based DV－Hop Algorithm for Wireless Sensor Networks［C］//Wireless Communications，Networking and Mobile Computing，2007.WiCom 2007.International Conference on IEEE，2007:2555－2558.

［7］Zhou Z，Xiao M，Liu L，et al.An Improved DV－HOP Localization Algorithm［C］//Information Science and Engineering(ISISE)，2009 Second International Symposium on IEEE，2009:598－602.

［8］嵇瑋瑋，劉中.DV－Hop定位算法在隨機傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報，2008，30(4):970－974.

［9］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點迭代定位算法［J］.通信學(xué)報，2009(10):107－113.

［10］Guo Z，Min L，Li H，et al.Improved DV－Hop Localization Algorithm Based on RSSIValue and Hop Correction［M］.Advances in Wireless Sensor Networks.Springer Berlin Heidelberg，2013:97－102.

［11］周小波，喬鋼柱，曾建潮.無線傳感器網(wǎng)絡(luò)中基于RSSI的加權(quán)DV－HOP定位方法［J］.計算機工程與應(yīng)用，2011，47(14): 109－111.

［12］肖麗萍，劉曉紅.一種基于跳數(shù)修正的DV－Hop定位算法［J］.傳感技術(shù)學(xué)報，2012，25(12):1726－1730.

［13］趙昭，陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進定位算法［J］.傳感技術(shù)學(xué)報，2009，22(3):391－394.

［14］張愛清，葉新榮，胡海峰，等.基于RSSI每跳分級和跳距修正的DV－HOP改進算法［J］.儀器儀表學(xué)報，2012，33(11):2552－2559.

溫江濤(1974－)，男，博士，燕山大學(xué)電氣工程學(xué)院講師，碩士生導(dǎo)師，主要從事基于無線傳感網(wǎng)絡(luò)的定位、識別等研究，wens2002@163.com;

范學(xué)敏(1987－)，女，燕山大學(xué)電氣工程學(xué)院碩士研究生，主要從事無線傳感器網(wǎng)絡(luò)定位的研究，bingchenmin@ 163.com;

吳希軍(1979－)，男，博士，燕山大學(xué)電氣工程學(xué)院副教授，主要從事傳感系統(tǒng)構(gòu)建與光譜測試方面的研，wuxijun@ysu.edu.cn。

基于RSSI跳數(shù)修正的DV－Hop改進算法*

溫江濤*，范學(xué)敏，吳希軍

(河北省測試計量技術(shù)及儀器重點實驗室，燕山大學(xué)，河北秦皇島066004)

針對原始DV－Hop算法中跳數(shù)值不能反應(yīng)出節(jié)點間實際距離大小而導(dǎo)致拓?fù)洳灰?guī)則網(wǎng)絡(luò)中節(jié)點定位誤差較大的問題，提出了一種基于接收信號強度指示RSSI(Rceived Sgnal Srength Idicator)的改進算法。首先根據(jù)直接鄰居節(jié)點接收到的RSSI值對第1跳進行分級，細(xì)化跳數(shù);同時把節(jié)點間的距離比值作為權(quán)值，并將其轉(zhuǎn)化為相應(yīng)RSSI的關(guān)系對跳數(shù)進行加權(quán)修正，使獲得的跳數(shù)值更準(zhǔn)確。仿真結(jié)果表明在相同的網(wǎng)絡(luò)環(huán)境下，與傳統(tǒng)算法相比改進算法在不增加額外硬件的前提下有效地提高了定位精度。

無線傳感器網(wǎng)絡(luò);DV－Hop;接收信號強度指示(RSSI);跳數(shù)修正;定位精度

TP393

A

1004－1699(2014)01－0113－05

2013－07－08修改日期:2013－12－30

C:6150P

10.3969/j.issn.1004－1699.2014.01.021

項目來源:國家自然科學(xué)基金項目(51204145);河北省自然科學(xué)基金項目(2013203300)