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

王 林，趙 錦

西安理工大學(xué) 自動化學(xué)院，西安 710048

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

王 林，趙 錦

西安理工大學(xué) 自動化學(xué)院，西安 710048

1 引言

隨著傳感器技術(shù)、無線通信技術(shù)、微電子技術(shù)以及嵌入式計算技術(shù)等技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)得到了廣泛應(yīng)用。通過在目標(biāo)區(qū)域部署大量傳感器節(jié)點，可以實現(xiàn)軍事防御、目標(biāo)跟蹤、環(huán)境監(jiān)測、空間探索、醫(yī)療衛(wèi)生監(jiān)測等諸多應(yīng)用。在眾多應(yīng)用中，沒有位置信息的數(shù)據(jù)將毫無意義，位置信息的獲取對于無線傳感器網(wǎng)絡(luò)的應(yīng)用具有重要意義；同時位置信息也可輔助進行無線傳感器網(wǎng)絡(luò)的路由、拓?fù)涔芾淼裙ぷ?。因此，定位技術(shù)成為無線傳感器網(wǎng)絡(luò)的一項關(guān)鍵技術(shù)[1]。

目前，節(jié)點定位算法主要分為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算法主要包括質(zhì)心算法、距離向量-跳段（Distance Vector-Hop，DV-Hop）算法、Amorphous算法、MDS-MAP算法及近似三角形內(nèi)點測試法（Approximate Point-In-Triangulation test，APIT）算法等[2]。Range-based定位技術(shù)對網(wǎng)絡(luò)節(jié)點的硬件要求較高；Range-free定位機制只需得到未知節(jié)點與相鄰節(jié)點間的連通信息，然后利用各種優(yōu)化方法估計未知節(jié)點位置，對硬件要求相對較低[3]。

DV-Hop算法是目前應(yīng)用最廣泛的無需測距定位技術(shù)之一，它具有算法簡單和定位精度高等優(yōu)點，適用于硬件支持有限的應(yīng)用環(huán)境；但由于該算法的定位精度主要依賴于所估計平均每跳距離的精確度，對網(wǎng)絡(luò)拓?fù)洳灰?guī)則的隨機分布無線傳感器網(wǎng)絡(luò)來說，定位誤差往往較大[4]。針對這個問題，許多學(xué)者對其進行了改進，文獻[5-6]分別利用未知節(jié)點到參考節(jié)點的路徑與參考節(jié)點間路徑可能存在部分重合的特性修正平均每跳距離，在一定程度上提高了定位精度，但均未考慮網(wǎng)絡(luò)拓?fù)涞膶嶋H情況，因而不適合節(jié)點隨機分布和網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的應(yīng)用環(huán)境；文獻[7]提出了一種基于接收信號強度指示和平均跳距修正的DV-Hop改進算法，但該算法需要進行高精度的強度測量；文獻[8]在DV-Hop的基礎(chǔ)上通過引入移動信標(biāo)方式對算法進行改進，在一定程度上提高了算法的定位精度，但需要引入高精度的移動信標(biāo)進行輔助定位?；诖耍恍W(xué)者從不增加輔助硬件設(shè)備的角度對DV-Hop定位算法進行改進，文獻[9-10]通過合理選擇錨節(jié)點改善定位精度；文獻[11]采用多個信標(biāo)節(jié)點估計加權(quán)的方法對DV-Hop定位算法進行改進；文獻[12]則通過Friis模型計算誤差并采用誤差加權(quán)的方法進行改進，均在一定程度上對傳統(tǒng)DV-Hop定位算法有所改善。

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

2 DV-Hop定位算法

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

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

第二階段：平均每跳距離計算以及距離估計。網(wǎng)絡(luò)中每個信標(biāo)節(jié)點在獲得到其他信標(biāo)節(jié)點位置和跳數(shù)信息后，計算網(wǎng)絡(luò)平均每跳距離，然后將其作為校正值廣播至網(wǎng)絡(luò)中。信標(biāo)節(jié)點平均每跳距離計算方法如下：

參考節(jié)點將計算得到的平均每跳距離廣播至網(wǎng)絡(luò)中，未知節(jié)點接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，計算到每個信標(biāo)節(jié)點的跳段距離。則未知節(jié)點k到信標(biāo)節(jié)點 j的估計距離為：

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

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

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

3 DV-Hop定位算法改進

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

3.1 差分GPS基本原理

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

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

其中，i代表第i顆衛(wèi)星。

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

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

基于這一原理，本文將其應(yīng)用于無線傳感器網(wǎng)絡(luò)中未知節(jié)點的定位問題，將信標(biāo)節(jié)點作為參考節(jié)點，以此計算網(wǎng)絡(luò)距離誤差，并將其應(yīng)用于未知節(jié)點與信標(biāo)節(jié)點之間的距離估計。

3.2 DV-Hop定位算法改進

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

（1）修正誤差計算

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

（2）距離估計

由此，可以得到信標(biāo)節(jié)點z到未知節(jié)點 y的修正距離為：

4 仿真

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

在實際仿真對比驗證過程中，主要從信標(biāo)節(jié)點數(shù)量對定位精度的影響、網(wǎng)絡(luò)隨機性對定位精度的影響以及計算復(fù)雜度三個方面對三種算法進行對比分析。

（1）信標(biāo)節(jié)點數(shù)量對定位精度的影響

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

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

圖2 定位精度隨信標(biāo)節(jié)點數(shù)量變化曲線

（2）網(wǎng)絡(luò)隨機性對定位精度的影響

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

圖3 不同實驗定位精度

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

（3）算法復(fù)雜度分析

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

表1 計算量對比1）

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

5 結(jié)論

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

[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]趙歡，馮穎，羅娟，等.無線傳感器網(wǎng)絡(luò)的移動節(jié)點定位算法研究[J].湖南大學(xué)學(xué)報：自然科學(xué)版，2007，34（8）：74-77.

[3]彭宇，王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報，2011，25（5）：389-399.

[4]李輝，熊盛武，劉毅.無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進[J].傳感技術(shù)學(xué)報，2011，24（12）：1782-1786.

[5]沈明玉，張寅.基于改進的平均跳距和估計距離的DV-Hop定位算法[J].計算機應(yīng)用研究，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].儀器儀表學(xué)報，2012，33（11）：2552-2559.

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

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

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

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

[12]劉凱，余君君，譚立雄.跳數(shù)加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報，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].傳感技術(shù)學(xué)報，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

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

無線傳感器網(wǎng)絡(luò)；距離向量-跳段算法；估計距離；誤差修正；定位精度

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.

航空科學(xué)基金項目（No.20110196005）。

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

2013-02-22

2013-05-24

1002-8331（2014）24-0109-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-08，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130608.0953.002.html

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學(xué)習(xí)◎