王 林，趙 錦

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

一種基于誤差修正的改進(jìn)DV-Hop算法

王 林，趙 錦

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

1 引言

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

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

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

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

2 DV-Hop定位算法

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

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

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

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

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

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

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

3 DV-Hop定位算法改進(jìn)

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

3.1 差分GPS基本原理

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

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

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

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

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

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

3.2 DV-Hop定位算法改進(jìn)

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

（1）修正誤差計(jì)算

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

（2）距離估計(jì)

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

4 仿真

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

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

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

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

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

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

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

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

圖3 不同實(shí)驗(yàn)定位精度

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

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

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

表1 計(jì)算量對比1）

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

5 結(jié)論

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

[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é)點(diǎn)定位算法研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，34（8）：74-77.

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

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

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

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

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

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

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

[12]劉凱，余君君，譚立雄.跳數(shù)加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，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é)報(bào)，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é)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)中的一項(xiàng)關(guān)鍵技術(shù)，針對DV-Hop算法對不規(guī)則隨機(jī)分布網(wǎng)絡(luò)定位誤差較大的問題，提出了一種基于誤差修正的改進(jìn)算法。該算法借鑒差分GPS思想，在DV-Hop算法距離估計(jì)階段，利用信標(biāo)節(jié)點(diǎn)的誤差差分修正估計(jì)距離；同時(shí)充分考慮網(wǎng)絡(luò)實(shí)際，通過多信標(biāo)誤差加權(quán)的方式獲得估計(jì)距離修正值，以提高算法定位精度。通過仿真研究驗(yàn)證了改進(jìn)算法的有效性。

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

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é)基金項(xiàng)目（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ù)挖掘、機(jī)器學(xué)習(xí)◎