Improved DV-Hop Location Algorithm Based on Hop Correction*

WEN Jiangtao，FAN 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*，FAN 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

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

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

1 DV－Hop算法原理

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

第1階段:通過典型的距離矢量交換協議，使網絡中所有節點得到距離每個信標節點的最小跳數值。

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

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

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

2 DV-Hop算法改進

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

在第1階段計算最小跳數的時候，只要通信半徑R之內的距離無論遠近都記為1跳，如圖1所示，節點1，2的跳數都記為1，可是他們與信標節點D的實際距離相差很大，依賴這種不能反映實際距離大小的跳數值來定位，在節點均勻分布時尚且可以得到合理的平均跳距，但是網絡拓撲一般是不規則的，運用相同的平均跳距來估計距離必然會產生較大的定位誤差。

圖1 跳數示意圖

針對上述問題，本文引入距離這個因素來修正第1階段的跳數以提高定位精度。以信標節點到直接鄰居節點的距離作為基準，設其距離為L1，跳數為h1，以其他鄰居節點間的距離與基準距離的比值作為權值修正該跳跳數。如圖2所示，第2跳的權值為L2/L1，該跳跳數為h1·(L2/L1)。則節點3到信標節點E的跳數為h1·(1+L2/L1+L3/L1)。因為整個拓撲網絡中第1跳的距離也差異很大，所以第1跳的跳數不能籠統的記為1，本文中對第1跳根據距離大小進行分級處理。

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

2.1 RSSI測距原理

無線傳感器網絡中應用最廣泛的信號傳播損耗模型是Shadowing模型［13］，其表達式如下:

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

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

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

2.2 跳數修正

2.2.1 基于RSSI對第1跳分級

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

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

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

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

2.2.2 利用RSSI對跳數加權修正

引入權值的定義:在大于一跳的跳數中，權值Hj設為第j跳與第1跳實際距離的比值，其中j為正整數

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

根據式(7)把權值轉化為節點接收到的RSSI值的關系式

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

2.3 改進后算法的具體步驟

對跳數進行分級和加權處理后改進算法的具體步驟如下:

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

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

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

3 仿真結果驗證

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

3.1 仿真環境及參數設定

仿真環境是在100 m×100 m的正方形區域內隨機分布100個節點，從中隨機選取信標節點，設所有節點具有相同的通信半徑R。為了消除由于節點隨機分布造成的誤差的不穩定性，在相同的網絡環境下分別進行1 000次仿真實驗取平均值。

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

則歸一化定位誤差為:

3.2 算法精度分析

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

圖3 不同級數時的歸一化誤差

圖4歸一化定位誤差與錨節點比例的關系

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

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

圖5 歸一化定位誤差與通信半徑的關系

3.3 算法復雜度分析

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

表1 各種算法性能比較

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

4 結論

本文提出的基于RSSI的DV－Hop改進算法引入RSSI測距技術對原始DV－Hop算法中的跳數值從兩個方面分別進行了修正，有效地解決了拓撲不規則網絡中，因為跳數值不能反映實際距離大小而導致定位誤差較大的問題，在無需增加額外硬件的條件下提高了定位精度。仿真結果表明在100 m×100 m的正方形區域，節點隨機分布的網絡環境下，改進后算法的定位精度比原始算法提高了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定位算法在隨機傳感器網絡中的應用研究［J］.電子與信息學報，2008，30(4):970－974.

［9］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法［J］.通信學報，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］周小波，喬鋼柱，曾建潮.無線傳感器網絡中基于RSSI的加權DV－HOP定位方法［J］.計算機工程與應用，2011，47(14): 109－111.

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

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

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

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

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

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

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

溫江濤*，范學敏，吳希軍

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

針對原始DV－Hop算法中跳數值不能反應出節點間實際距離大小而導致拓撲不規則網絡中節點定位誤差較大的問題，提出了一種基于接收信號強度指示RSSI(Rceived Sgnal Srength Idicator)的改進算法。首先根據直接鄰居節點接收到的RSSI值對第1跳進行分級，細化跳數;同時把節點間的距離比值作為權值，并將其轉化為相應RSSI的關系對跳數進行加權修正，使獲得的跳數值更準確。仿真結果表明在相同的網絡環境下，與傳統算法相比改進算法在不增加額外硬件的前提下有效地提高了定位精度。

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

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

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