韓雪松，楊鵑

(承德石油高等?？茖W(xué)校計(jì)算機(jī)與信息工程系，河北承德067000)

改進(jìn)的DV-Hop算法在節(jié)點(diǎn)定位中的應(yīng)用

韓雪松，楊鵑

(承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系，河北承德067000)

基于傳統(tǒng)DV-Hop算法的定位技術(shù)，通過(guò)分析該算法誤差產(chǎn)生的主要原因，提出了節(jié)點(diǎn)間跳數(shù)的修正方法。通過(guò)在廣播通信中采用雙通信頻率，將節(jié)點(diǎn)間的跳數(shù)縮減為0．5R，減少了平均跳距的誤差。通過(guò)matlab軟件的實(shí)驗(yàn)驗(yàn)證，本算法可以提高節(jié)點(diǎn)定位精度，且提高網(wǎng)絡(luò)通信頻率，可進(jìn)一步提高定位精度，定位結(jié)果達(dá)到了預(yù)期的目的。

DV-Hop算法;節(jié)點(diǎn)定位;zigbee

節(jié)點(diǎn)定位通過(guò)節(jié)點(diǎn)間的數(shù)據(jù)和定位算法確定未知節(jié)點(diǎn)的具體位置，標(biāo)識(shí)網(wǎng)絡(luò)節(jié)點(diǎn)的空間位置，是無(wú)線傳感網(wǎng)絡(luò)研究的重點(diǎn)內(nèi)容之一。目前應(yīng)用較多的定位算法有RSSI測(cè)距算法、AOA算法、TOA算法、DV-Hop算法、質(zhì)心定位算法、APIT算法等［1］。本文研究使用的DV-Hop算法基于距離矢量，根據(jù)錨節(jié)點(diǎn)的平均跳距和未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)估算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離值，建立坐標(biāo)與距離的方程組，通過(guò)求解方程組獲得未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。

1　傳統(tǒng)DV-HOP定位算法

1．1定位過(guò)程

DV-HOP算法的定位過(guò)程如圖1所示。

錨節(jié)點(diǎn)通過(guò)廣播方式通告自身的位置和跳數(shù)信息，鄰居節(jié)點(diǎn)接收到該數(shù)據(jù)分組后，首先判定是否是首次接收到該錨節(jié)點(diǎn)的數(shù)據(jù)包，如果是首次，則保留記錄，否則，比較跳數(shù)大小，保存跳數(shù)小的記錄。洪泛結(jié)束后，根據(jù)記錄保存的錨節(jié)點(diǎn)信息、跳數(shù)信息和自身坐標(biāo)，求取平均跳距。平均跳距與跳數(shù)的乘積就是未知節(jié)點(diǎn)與該錨節(jié)點(diǎn)間的距離，求解距離方程組即可獲得未知節(jié)點(diǎn)的坐標(biāo)值。

1．2誤差產(chǎn)生的主要原因

1)多跳轉(zhuǎn)發(fā)的定位誤差。在DV-HOP算法計(jì)算過(guò)程中，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離值是由錨節(jié)點(diǎn)的平均跳距和跳數(shù)的乘積確定的，實(shí)際網(wǎng)絡(luò)拓?fù)渲?，未知?jié)點(diǎn)到錨節(jié)點(diǎn)的轉(zhuǎn)發(fā)路徑是一系列折線段，而錨節(jié)點(diǎn)間的實(shí)際距離是直線段，轉(zhuǎn)發(fā)的跳數(shù)越多，累計(jì)的誤差越大，定位誤差也越大［2］。

2)錨節(jié)點(diǎn)密度不均造成的誤差。錨節(jié)點(diǎn)的布局由于實(shí)際空間的限制，不能實(shí)現(xiàn)節(jié)點(diǎn)的均勻布局，會(huì)出現(xiàn)錨節(jié)點(diǎn)密度不均的現(xiàn)象。當(dāng)密度不均勻布局時(shí)，估算的平均跳距誤差較大，因而造成定位誤差較大［3］。

3)錨節(jié)點(diǎn)密度過(guò)低。如果錨節(jié)點(diǎn)密度過(guò)低，則錨節(jié)點(diǎn)周圍的多跳錨節(jié)點(diǎn)的數(shù)目越少，與之建立路徑轉(zhuǎn)發(fā)的錨節(jié)點(diǎn)位置對(duì)平均跳距的求取影響越大，因而造成定位誤差值較大。并且錨節(jié)點(diǎn)密度過(guò)低，網(wǎng)絡(luò)內(nèi)不良節(jié)點(diǎn)數(shù)目的增加［4］，降低了網(wǎng)絡(luò)的定位效果。

1．3研究情況

傳統(tǒng)的DV-Hop算法定位誤差較大，不適合于網(wǎng)絡(luò)稀疏的復(fù)雜工作環(huán)境，很多研究者在本算法的改進(jìn)中取得了較大的成果，提高了算法的適用性。文獻(xiàn)［5］根據(jù)兩節(jié)點(diǎn)間的通信覆蓋率在跳數(shù)計(jì)算過(guò)程中，添加跳數(shù)系數(shù)，降低了每跳距產(chǎn)生的距離誤差。文獻(xiàn)［6］將錨節(jié)點(diǎn)劃分兩類，一跳內(nèi)的節(jié)點(diǎn)采用RSSI定位算法，一跳以上采用DV-Hop算法，該方法簡(jiǎn)單易行，但不適用于復(fù)雜環(huán)境中使用。文獻(xiàn)［7］針對(duì)于礦井復(fù)雜環(huán)境，在DV-Hop定位算法應(yīng)用的基礎(chǔ)上，對(duì)跳數(shù)和跳距進(jìn)行了優(yōu)化處理，提高了定位的精度。文獻(xiàn)［8］添加錨節(jié)點(diǎn)的自定位過(guò)程，將定位結(jié)果與實(shí)際值相比較，得到計(jì)算的修正值，以提高定位的精度。改進(jìn)的定位效果從多個(gè)角度進(jìn)行了算法的優(yōu)化，提高了定位精度，但也附加了一些其他技術(shù)問(wèn)題，需要進(jìn)一步的完善。

2　改進(jìn)的DV-Hop算法

2．1改進(jìn)的基本思想

DV-Hop算法的主要誤差集中在平均跳距和跳數(shù)的問(wèn)題，基于通信半徑、節(jié)點(diǎn)間距離和跳數(shù)三者之間的關(guān)系，本文采用雙通信半徑的思想，減少平均跳距誤差。文獻(xiàn)［9］中采用雙通信半徑用于改善DVHop算法，但通信半徑設(shè)定為R和R/2，在實(shí)際使用中由于網(wǎng)絡(luò)通信環(huán)境不同，很難確定R/2的射頻信號(hào)大小，需進(jìn)行節(jié)點(diǎn)網(wǎng)絡(luò)測(cè)試。

無(wú)線網(wǎng)絡(luò)通信信號(hào)模型公式如下式所示。

其中:λ—路徑損耗系數(shù)，一般取2～5;ξ—隨機(jī)數(shù)，符合高斯分布，平均值為0，其標(biāo)準(zhǔn)差一般取4～10; d0—參考距離，m;d—估計(jì)距離，m;Pr(d0)—參考距離的接收信號(hào)強(qiáng)度，dbm;Pr(d)—估計(jì)距離的接收信號(hào)強(qiáng)度，dbm。

2．2DV-Hop算法的具體改進(jìn)方法

1)網(wǎng)絡(luò)錨節(jié)點(diǎn)首先以RF2廣播數(shù)據(jù)包分組，其中包括節(jié)點(diǎn)ID、節(jié)點(diǎn)坐標(biāo)、初始跳數(shù)、轉(zhuǎn)發(fā)時(shí)間等信息，數(shù)據(jù)包分組的初始跳數(shù)值設(shè)定為0．5。收到數(shù)據(jù)包分組的錨節(jié)點(diǎn)保存記錄，轉(zhuǎn)發(fā)時(shí)間為0后，首次廣播結(jié)束。

2)網(wǎng)絡(luò)錨節(jié)點(diǎn)以RF1廣播數(shù)據(jù)包分組，數(shù)據(jù)包格式與步驟1相同，但初始跳數(shù)為1。如果網(wǎng)絡(luò)節(jié)點(diǎn)首次接收到該數(shù)據(jù)包分組，則保存記錄，否則判定跳數(shù)大小，保存跳數(shù)小的記錄。將跳數(shù)加后，數(shù)據(jù)包分組轉(zhuǎn)發(fā)給其他鄰居節(jié)點(diǎn)。轉(zhuǎn)發(fā)時(shí)間為0后，廣播結(jié)束。

3)與傳統(tǒng)的DV-Hop算法計(jì)算一致，求取平均跳數(shù)，計(jì)算距離值，求解方程組。

3　仿真實(shí)驗(yàn)與分析

為了驗(yàn)證改進(jìn)算法的有效性，本文基于matlab軟件搭建仿真環(huán)境模擬和計(jì)算未知節(jié)點(diǎn)的定位效果，研究在不同錨節(jié)點(diǎn)密度和通信半徑的條件下，平均定位誤差的大小。仿真環(huán)境設(shè)定在100 m×100 m的范圍內(nèi)，初始錨節(jié)點(diǎn)個(gè)數(shù)12個(gè)，通信半徑30 m，網(wǎng)絡(luò)環(huán)境中假定路徑損耗系數(shù)為4，信號(hào)的干擾用均值為5的高斯白噪聲表示，采用最小二乘法求解方程組。實(shí)驗(yàn)中隨機(jī)生成100個(gè)未知節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)定位的平均誤差值。

通信半徑對(duì)定位誤差的影響如圖2所示。網(wǎng)絡(luò)通信半徑增加，則平均定位誤差相對(duì)減小，這也說(shuō)明在網(wǎng)絡(luò)情況允許的情況下，應(yīng)盡量采用大功率的射頻信號(hào)發(fā)射，可降低網(wǎng)絡(luò)的平均定位誤差。錨節(jié)點(diǎn)個(gè)數(shù)初始增加可明顯減小平均定位誤差，但當(dāng)節(jié)點(diǎn)密度達(dá)到一定程度，平均定位誤差基本保持不變。

以通信半徑30 m為例，兩種算法對(duì)比圖如圖3所示。平均定位誤差相差很大，基于傳統(tǒng)DV-Hop算法的平均定位誤差在35．28%～38．8%，改進(jìn)后的算法平均定位誤差在25．1%～28．8%，改進(jìn)后相比于改進(jìn)前大約提高了10%個(gè)精度，達(dá)到了預(yù)期的目的。

4　結(jié)束語(yǔ)

本文在傳統(tǒng)的DV-Hop基礎(chǔ)上采用雙通信半徑方法，將節(jié)點(diǎn)間距離的求取誤差降低了0．5R的誤差，通過(guò)仿真實(shí)驗(yàn)看出，通信半徑對(duì)于定位結(jié)果影響較大，錨節(jié)點(diǎn)密度在達(dá)到一定程度后對(duì)定位結(jié)果影響不大。本文只是針對(duì)于節(jié)點(diǎn)間距離的計(jì)算進(jìn)行了改進(jìn)，后續(xù)研究中應(yīng)考慮求解方程組最優(yōu)解的方法，更進(jìn)一步提高定位精度。

［1］楊鵑，韓雪松．無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)［J］．承德石油高等專科學(xué)校學(xué)報(bào)，2013，15(6):39－43．

［2］夏少波，周建梅，朱曉麗，等．基于跳數(shù)區(qū)域劃分的DV－Hop改進(jìn)算法［J］．傳感技術(shù)學(xué)報(bào)，2014，27(7):964－969．

［3］李雪梅．基于DV-HOP算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)的研究［D］．太原:太原理工大學(xué)，2012．

［4］李冬．基于DV-Hop的無(wú)線傳感器網(wǎng)絡(luò)定位算法研究與改進(jìn)［D］．南京:南京理工大學(xué)，2013．

［5］譚志，張卉．基于節(jié)點(diǎn)間覆蓋關(guān)系的改進(jìn)DV-Hop算法［J］．北京郵電大學(xué)學(xué)報(bào)，2014，37(1):35－38．

［6］Liu Y，Qian ZH，Liu D，et al．A DV-hop positioning algorithm for wireless sensor network based on detection［A］//2009 Fifth International Joint Conference on INC，IMS and IDC［C］．Seoul:International joint conferences，2009．

［7］方旺盛，吳勝寶．基于井下異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)［J］．傳感器與微系統(tǒng)，2014，33(5):125－128．

［8］黃浩，盧文科．無(wú)線傳感器網(wǎng)絡(luò)中基于信標(biāo)節(jié)點(diǎn)反饋的多跳測(cè)距定位算法改進(jìn)［J］．傳感技術(shù)學(xué)報(bào)，2009，22(2): 269－272．

［9］李娟，劉禹，錢志鴻，等．基于雙通信半徑的傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］．吉林大學(xué)學(xué)報(bào)(工學(xué)版)，2014，44 (2):502－507．

Improvement of DV-Hop Algorithm in Application of Node Localization

HAN Xue-song，YANG Juan
(Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China)

Based on the traditional positioning technology of DV-Hop algorithm，through analysis of the main reason for the error occurring in the algorithm，this paper proposes the correction method of Hop count between nodes．Double frequency is used in radio communication．The hop count between nodes can be reduced to 0．5R，which can reduce the average jump distance error．Through matlab software experimental verification，this algorithm can improve the node location accuracy．The higher frequency of network communication can further make the positioning accuracy lower．Positioning results reached the expected purpose．

DV－Hop algorithm;node localization;zigbee

TP393

B

1008-9446(2015)02-0047-03

2014-11-12

韓雪松(1980－)，男，吉林省吉林市人，承德石油高等專科學(xué)校計(jì)算機(jī)與信息工程系講師，主要研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)通信和數(shù)據(jù)融合技術(shù)等。