一種基于誤差修正的改進DV-Hop算法

王 林，趙 錦

西安理工大學 自動化學院，西安 710048

一種基于誤差修正的改進DV-Hop算法

王 林，趙 錦

西安理工大學 自動化學院，西安 710048

1 引言

隨著傳感器技術、無線通信技術、微電子技術以及嵌入式計算技術等技術的發展，無線傳感器網絡得到了廣泛應用。通過在目標區域部署大量傳感器節點，可以實現軍事防御、目標跟蹤、環境監測、空間探索、醫療衛生監測等諸多應用。在眾多應用中，沒有位置信息的數據將毫無意義，位置信息的獲取對于無線傳感器網絡的應用具有重要意義；同時位置信息也可輔助進行無線傳感器網絡的路由、拓撲管理等工作。因此，定位技術成為無線傳感器網絡的一項關鍵技術[1]。

目前，節點定位算法主要分為Range-based算法和Range-free算法兩大類。其中Range-based算法主要包括信號到達時間（Time Of Arrival，TOA）、信號到達時間差（Time Differential Of Arrival，TDOA）、信號到達角度（Angle Of Arrival，AOA）、信號強度（Received Signal Strength Indicator，RSSI）等；Range-free算法主要包括質心算法、距離向量-跳段（Distance Vector-Hop，DV-Hop）算法、Amorphous算法、MDS-MAP算法及近似三角形內點測試法（Approximate Point-In-Triangulation test，APIT）算法等[2]。Range-based定位技術對網絡節點的硬件要求較高；Range-free定位機制只需得到未知節點與相鄰節點間的連通信息，然后利用各種優化方法估計未知節點位置，對硬件要求相對較低[3]。

DV-Hop算法是目前應用最廣泛的無需測距定位技術之一，它具有算法簡單和定位精度高等優點，適用于硬件支持有限的應用環境；但由于該算法的定位精度主要依賴于所估計平均每跳距離的精確度，對網絡拓撲不規則的隨機分布無線傳感器網絡來說，定位誤差往往較大[4]。針對這個問題，許多學者對其進行了改進，文獻[5-6]分別利用未知節點到參考節點的路徑與參考節點間路徑可能存在部分重合的特性修正平均每跳距離，在一定程度上提高了定位精度，但均未考慮網絡拓撲的實際情況，因而不適合節點隨機分布和網絡拓撲動態變化的應用環境；文獻[7]提出了一種基于接收信號強度指示和平均跳距修正的DV-Hop改進算法，但該算法需要進行高精度的強度測量；文獻[8]在DV-Hop的基礎上通過引入移動信標方式對算法進行改進，在一定程度上提高了算法的定位精度，但需要引入高精度的移動信標進行輔助定位。基于此，一些學者從不增加輔助硬件設備的角度對DV-Hop定位算法進行改進，文獻[9-10]通過合理選擇錨節點改善定位精度；文獻[11]采用多個信標節點估計加權的方法對DV-Hop定位算法進行改進；文獻[12]則通過Friis模型計算誤差并采用誤差加權的方法進行改進，均在一定程度上對傳統DV-Hop定位算法有所改善。

然而，這些方法的研究均未考慮跳段的真實估計誤差，本文在不引進輔助硬件設備的條件下，對DV-Hop算法進行分析，借鑒差分GPS（Global Position System）思想，利用信標節點的真實誤差差分對未知節點距離估算進行補償，設計一種基于誤差修正的改進DV-Hop算法，以提高定位精度。

2 DV-Hop定位算法

DV-Hop算法由美國路特葛斯大學的Dragos Niculescu等學者提出[13]，其基本思想是將未知節點與信標節點之間的距離用網絡平均每跳距離與節點之間最小跳數的乘積表示，并采用三邊測量法獲得節點位置信息。DV-Hop算法的實現大致分可為三個階段：

第一階段：計算每個未知節點與信標節點之間的最小跳數。信標節點向網絡廣播一個包含坐標(xi，yi)和跳數的信息包。鄰近節點接收到信息包后，保存當前接收到的信息包并記錄信標節點的位置坐標和跳數；接著將信息包更新，更新信息包只將跳數加1，而信標節點的坐標保持不變，然后繼續向它的鄰居廣播更新后的數據包；如果某節點接收到來自同一個信標節點的多個信息包，則該節點只保留含有最小跳數值的信息包。

第二階段：平均每跳距離計算以及距離估計。網絡中每個信標節點在獲得到其他信標節點位置和跳數信息后，計算網絡平均每跳距離，然后將其作為校正值廣播至網絡中。信標節點平均每跳距離計算方法如下：

參考節點將計算得到的平均每跳距離廣播至網絡中，未知節點接收到平均每跳距離后，根據記錄的跳數，計算到每個信標節點的跳段距離。則未知節點k到信標節點 j的估計距離為：

第三階段：定位階段。當獲得到三個或更多個信標的距離信息時，利用三邊測量法或極大似然法計算未知節點坐標。

算法定位過程如圖1所示，已知信標節點L1與L2，L3之間的距離和跳數。L2計算得到的平均每跳距離為(40+75)/(2+5)=16.42，假設未知節點A從L2獲得校正值，則它與各個信標節點之間的距離分別為L1∶3×16.42 =49.26，L2∶2×16.42=32.84，L3∶3×16.42=49.26，然后利用三邊測量法確定未知節點A的位置。

圖1 DV-Hop定位算法示意圖

3 DV-Hop定位算法改進

從上述DV-Hop定位算法原理可知，該算法需要經過跳數計算、距離估計和節點定位三個階段。未知節點的定位精度與平均每跳距離的估計精度直接相關，一般來說，算法比較適用于各向同性的密集網絡，對于隨機分布的傳感器網絡，其定位誤差比較大；然而在實際應用中，通常遇到的都是隨機分布的傳感器網絡。為了改善DV-Hop算法針對隨機分布傳感器網絡的定位性能，本文借鑒差分GPS思想，設計一種基于誤差修正的DV-Hop改進算法，對DV-Hop算法中的每跳平均距離進行修正。

3.1 差分GPS基本原理

為了降低GPS信號傳輸過程中各種干擾、延遲、多路徑效應等帶來的定位誤差，差分GPS在已知點（GPS基站）放置一臺高性能的GPS接收機作為參考點。根據差分GPS基站發送的信息形式可將差分GPS定位分為偽距差分、相位平滑偽距差分、載波相位差分和位置差分。它們的工作原理均相同，都是由基準站發送改正數，用戶站接收并以此為基礎對其測量結果進行修正，以獲得精確定位結果；不同之處在于發送改正數的內容不一樣，修正方式不一樣，所得差分定位精度也因此不一樣。這里以偽距差分為例介紹差分定位原理[14]。

在偽距差分中，基準站（位置已知的站）的GPS接收并測量出全部衛星的偽距ρ以及星歷文件，利用已采集到的衛星軌道信息計算各顆衛星的地心坐標 X，Y，Z。根據基準站的地心坐標 Xb，Yb，Zb，則可以求出每一時刻基準站到衛星的真實距離R如下：

其中，i代表第i顆衛星。

因此，可以求出基準站GPS接收機測量中包含的各種誤差，即偽距誤差：

同時，也能求出偽距誤差的變化率：

基于這一原理，本文將其應用于無線傳感器網絡中未知節點的定位問題，將信標節點作為參考節點，以此計算網絡距離誤差，并將其應用于未知節點與信標節點之間的距離估計。

3.2 DV-Hop定位算法改進

本文基于差分GPS原理，采用誤差修正的方法對DV-Hop算法中平均每跳距離的估算進行修正，需要指出的是，改進方法并不改變DV-Hop算法的定位過程。主要改進包括修正誤差計算和距離估計兩部分，分別如下：

（1）修正誤差計算

基于差分GPS原理，本文選取信標節點作為參考節點，在DV-Hop定位算法計算平均每跳距離的基礎上，利用信標節點之間的實際距離與基于DV-Hop定位算法所得信標節點之間的估計距離之差作為修正誤差。修正誤差計算方法如下：

（2）距離估計

由此，可以得到信標節點z到未知節點 y的修正距離為：

4 仿真

為了驗證本文提出算法的有效性，利用MATLAB在假定場景中進行仿真。將總數為N的未知節點隨機分布在20 m×20 m的正方形區域內，分別采用DV-Hop算法、文獻[15]中的改進算法和本文設計的改進算法進行仿真對比研究。為便于分析對比，采用平均相對定位誤差[16]衡量算法定位精度：

在實際仿真對比驗證過程中，主要從信標節點數量對定位精度的影響、網絡隨機性對定位精度的影響以及計算復雜度三個方面對三種算法進行對比分析。

（1）信標節點數量對定位精度的影響

為分析信標節點數量對定位精度的影響，在仿真場景內隨機部署50個未知節點，選擇節點通信半徑為6 m。同時，為使仿真結果更接近實際情況，所有仿真結果均通過20次獨立仿真實驗，各次仿真實驗結果取平均獲得。最終仿真結果如圖2所示。

從圖2可以看出：隨著信標節點數量的增加，定位精度隨之提高；信標節點越多，改進后算法比DV-Hop算法的誤差減小更快。同時在相同數量信標節點下，改進算法定位精度均優于DV-Hop算法，平均定位誤差相比原DV-Hop算法下降12%；從圖中的對比也可以看出，改進后的定位算法相比文獻[15]中的定位算法，在不同信標節點數量時定位精度均有一定提高。

圖2 定位精度隨信標節點數量變化曲線

（2）網絡隨機性對定位精度的影響

為了分析未知節點隨機部署對定位精度的影響，在設定場景中，選擇未知節點數量為50個，并設置15個信標節點，選擇節點通信半徑為6 m，分別進行25次獨立仿真實驗，每次仿真均重新隨機部署未知節點一次，信標節點的部署位置不變。所得仿真結果如圖3所示。

圖3 不同實驗定位精度

從圖3的仿真結果可以看出：所進行25次實驗中，每次實驗改進算法定位誤差均小于原DV-Hop算法；改進算法定位精度優于原DV-Hop算法以及文獻[15]中的方法，其原因在于DV-Hop算法中采用跳段距離代替直線距離，存在較大的誤差，而改進算法通過誤差修正使得誤差在一定程度上得到了補償，定位精度也有了一定提高。

（3）算法復雜度分析

算法的計算量是算法應用中的一項重要指標。本文所設計算法由于其定位過程與DV-Hop一致，相比之下在誤差修正中引入了額外的計算量。以N個信標節點為例，為了計算修正誤差需要進行N×N次減法運算，N次除法運算得到加權因子W，對跳段修正需要進行減法運算與除法運算各N次，乘法運算N×N次，加法運算2N×(N-1)次。在文獻[15]中，相比傳統DV-Hop定位算法，計算平均跳距權值需要進行N×(N-1)次乘法以及除法運算，減法運算3N×(N-1)次；計算平均跳距需要進行N×N次乘法運算，2N×(N-1)次加法運算，N次減法以及除法運算；計算未知節點平均跳距同樣需要進行N×N次乘法運算，2N×(N-1)次加法運算以及N次減法以及除法運算。計算量對比分析如表1所示。

表1 計算量對比1）

從上述算法復雜度的分析可以看出，本文所設計改進算法相比傳統DV-Hop定位算法計算量有一定提高，但相比文獻[15]中的改進定位算法計算量明顯降低。

5 結論

本文提出了一種基于誤差修正的改進DV-Hop算法，在DV-Hop算法的距離估計階段，基于差分GPS原理，對平均每跳距離進行誤差修正，并進行了仿真研究。該算法基本保持了DV-Hop的定位過程，但不需要額外硬件支持。仿真結果表明，該改進算法定位精度優于原DV-Hop算法，同時受到網絡隨機性的影響較小。從與文獻[15]的對比可以看出，本文定位算法的定位精度比文獻[15]中方法有一定提高，但計算復雜度明顯降低。盡管有一定改善，但如何進一步降低計算復雜度將仍是算法后續研究需要重點關注的一個方面。

[1]Liu Y，Yang Z，Wang X，et al.Location，localization，and localizability[J].Journal of Computer Science and Technology，2010，25（2）：274-297.

[2]趙歡，馮穎，羅娟，等.無線傳感器網絡的移動節點定位算法研究[J].湖南大學學報：自然科學版，2007，34（8）：74-77.

[3]彭宇，王丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報，2011，25（5）：389-399.

[4]李輝，熊盛武，劉毅.無線傳感器網絡DV-HOP定位算法的改進[J].傳感技術學報，2011，24（12）：1782-1786.

[5]沈明玉，張寅.基于改進的平均跳距和估計距離的DV-Hop定位算法[J].計算機應用研究，2011，28（2）：648-650.

[6]Zhang Dengyi，Liu Feng，Wang Lei，et al.DV-Hop localization algorithms based on centroid in wireless sensor networks[C]//2012 2nd International Conference on Consumer Electronics，Communications and Networks（CECNET），2012：3216-3219.

[7]張愛清，葉新榮，胡海峰，等.基于RSSI每跳分級和跳距修正的DV-HOP改進算法[J].儀器儀表學報，2012，33（11）：2552-2559.

[8]謝曉松，程良倫.傳感器網絡基于移動信標改進的DV-Hop定位算法[J].計算機應用與軟件，2011，28（4）：84-87.

[9]朱敏，劉昊霖，張志宏，等.一種基于DV-HOP改進的無線傳感器網絡定位算法[J].四川大學學報：工程科學版，2012，44（1）：93-98.

[10]肖麗萍，劉曉紅.一種基于跳數修正的DV-Hop定位算法[J].傳感技術學報，2012，25（12）：1726-1730.

[11]吳玉成，李江雯.基于最優節點通信半徑的改進DV-Hop定位算法[J].華南理工大學學報：自然科學版，2012，40（6）：36-42.

[12]劉凱，余君君，譚立雄.跳數加權DV-Hop定位算法[J].傳感技術學報，2012，25（12）：1539-1542.

[13]Niculescu D，Nath B.DV based positioning in ad hoc networks[J].Journal of Telecommunication Systems，2003， 22（14）：267-280.

[14]Yacob N，Abdullah M，Ismail M.Variation of elevation angle and Total Electron Content（TEC）and profile shape using modified jones 3D ray tracing for differential Global Positioning System（dGPS）in equatorial[C]//IEEE International Conference on RF and Microwave，2008：381-385.

[15]江禹生，馮硯毫.一種新的DV-Hop定位算法[J].傳感技術學報，2010，23（12）：1815-1819.

[16]Yin Min，Shu Jian.The influence of Beacon on DV-hop in Wireless Sensor Networks[C]//Proceedings of the Fifth International Conference on Grid and Cooperative Computing Workshops，Hunan，2006：118-122.

WANG Lin,ZHAO Jin

The Automation Institute,Xi’an University of Technology,Xi’an 710048,China

Localization of nodes is one of the key technologies for the wireless sensor networks.An error compensation based improved algorithm is proposed to deal with the problem of DV-Hop algorithm in the localization of random distributed wireless sensor networks.Based on the principle of differential GPS,the proposed algorithm improves the distance estimation based on the error of beacons in the estimation stage of DV-Hop algorithm;and a multiple beacon errors weighted method is employed to revise the distance estimation.Simulation results prove the effectiveness of the proposed algorithm.

Wireless Sensor Networks（WSN）;Distance Vector（DV）-Hop algorithm;estimation of distance;error compensation;positioning accuracy

節點定位技術是無線傳感器網絡中的一項關鍵技術，針對DV-Hop算法對不規則隨機分布網絡定位誤差較大的問題，提出了一種基于誤差修正的改進算法。該算法借鑒差分GPS思想，在DV-Hop算法距離估計階段，利用信標節點的誤差差分修正估計距離；同時充分考慮網絡實際，通過多信標誤差加權的方式獲得估計距離修正值，以提高算法定位精度。通過仿真研究驗證了改進算法的有效性。

無線傳感器網絡；距離向量-跳段算法；估計距離；誤差修正；定位精度

A

TP393.07

10.3778/j.issn.1002-8331.1302-0120

WANG Lin,ZHAO Jin.Improved DV-Hop algorithm based on error compensation.Computer Engineering and Applications,2014,50（24）：109-112.

航空科學基金項目（No.20110196005）。

王林（1963—），男，博士，教授，從事復雜系統與復雜網絡、無線傳感器網絡信號處理技術研究；趙錦（1986—），通訊作者，女，碩士研究生，從事無線傳感器網絡信號處理技術研究。E-mail：593043944@qq.com

2013-02-22

2013-05-24

1002-8331（2014）24-0109-04

CNKI網絡優先出版：2013-06-08，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130608.0953.002.html

◎數據庫、數據挖掘、機器學習◎