一種虛擬信標節(jié)點機制的DV-Hop定位改進算法

◆胡平霞 龔靜 丁鋒 張玉平

一種虛擬信標節(jié)點機制的DV-Hop定位改進算法

◆胡平霞 龔靜 丁鋒 張玉平

（湖南環(huán)境生物職業(yè)技術(shù)學(xué)院 湖南 421001）

本文為提高無線傳感器網(wǎng)絡(luò)中非測距定位算法DV-Hop的定位精度，特提出一種通過信標節(jié)點移動形成虛擬信標節(jié)點的VADV-Hop改進算法，優(yōu)化信標節(jié)點部署位置，使用網(wǎng)絡(luò)平均跳距校正信標節(jié)點平均跳距。仿真實驗表明VADV-Hop算法在不增加信標節(jié)點數(shù)量上表現(xiàn)出較穩(wěn)定的定位精度。

無線傳感器網(wǎng)絡(luò)；定位；平均跳距；虛擬信標節(jié)點

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是由靜止或移動的傳感器節(jié)點以自組織和多跳的方法組成的無線網(wǎng)絡(luò)，是一種集感知數(shù)據(jù)、采集數(shù)據(jù)、處理數(shù)據(jù)、傳輸數(shù)據(jù)等技術(shù)實現(xiàn)物理世界與信息世界數(shù)據(jù)交互的一種分布式網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點返回的數(shù)據(jù)包含位置信息，沒有位置的數(shù)據(jù)實用價值很低，因此傳感器節(jié)點定位技術(shù)是WSN的關(guān)鍵技術(shù)之一，其定位精度直接影響WSN的發(fā)展和應(yīng)用。

根據(jù)定位過程中是否要測量未知節(jié)點和信標節(jié)點間的距離，把定位方法劃分為基于測距定位（Range-based）方法和免測距定位（Range-free）方法[1]。其中免測距定位方法由于其低成本、易實現(xiàn)等特點得到很多研究者關(guān)注。常用免測距定位方法有DV-Hop算法[2]、質(zhì)心算法[3]、APIT（Approximate Point-in-Triangulation Test）算法[4]、凸規(guī)劃（Convex）算法[5]等，它們都是通過已知節(jié)點位置信息實現(xiàn)對未知節(jié)點的定位。

1 DV-Hop算法

美國Lutegesi大學(xué)的Dragons Niculescu等人在2003年提出DV-hop（Distance Vector-Hop）算法采用距離矢量路由機制定位，是一種基于多跳測距的免距離測距方法[2]。DV-Hop算法是目前研究較多的免測距算法，該算法通過信標節(jié)點位置估算未知節(jié)點位置，然后信標節(jié)點的數(shù)量在實際應(yīng)用中受到成本限制，因此本文在DV-Hop算法思想上提出一種基于虛擬信標節(jié)點技術(shù)的改進算法。

1.1 定位過程

DV-Hop算法節(jié)點定位過程[6]如下：

（1）確定信標節(jié)位置及最小跳數(shù)

通過信標節(jié)點廣播的數(shù)據(jù)包，信標節(jié)點確定其他信標節(jié)點坐標及最小跳數(shù)，未知節(jié)點確定信標節(jié)點坐標及最小跳數(shù)。

（2）確定平均跳據(jù)，估算距離

使用信標節(jié)點的位置坐標及信標節(jié)點間的最小跳數(shù)，通過公式1來計算信標節(jié)點的平均跳距，使用平均跳距結(jié)合公式2計算未知節(jié)點到信標節(jié)點的距離。

節(jié)點的坐標表示為（x，y），節(jié)點的坐標表示為（x，y），、均為網(wǎng)絡(luò)中的信標節(jié)點。信標h表示二節(jié)點、間的最小跳數(shù)，表示、間的跳距平均值。

HopSize是未知節(jié)點選用最鄰近信標節(jié)點的跳距平均值，hop是未知節(jié)點到信標節(jié)點的最小跳數(shù)值。

（3）確定未知節(jié)點位置

未知節(jié)點在獲得2個以上跟信標節(jié)點的參考距離后，使用相應(yīng)信標節(jié)點坐標（x，y）及d，轉(zhuǎn)換成線性方程，通過數(shù)學(xué)方法（最小二乘法）計算得到未知節(jié)點位置坐標。

圖1 DV-Hop估算示意圖

圖1中U為需要定位的未知節(jié)點，通過已知節(jié)點即信標節(jié)點BBB的位置信息來測算U的位置。首先BBB通過洪泛算法進行廣播，各節(jié)點保存最小跳數(shù)信息。其次BBB節(jié)點計算自身平均跳距，U使用最鄰近的節(jié)點B平均跳距作為自身跳距平均值分別計算到信標節(jié)點的距離。最后建立位置矩陣，通過最小二乘法計算U的坐標。

1.2 算法分析

1.2.1客觀條件分析

現(xiàn)實應(yīng)用場景的無線傳感器網(wǎng)絡(luò)，存在以下客觀條件：

（1）異常節(jié)點問題

異常節(jié)點是部署在邊緣的節(jié)點或是被孤立的節(jié)點，這些節(jié)點的位置信息影響定位精度。

（2）節(jié)點密度問題

由于受節(jié)點分布密度的影響，最小跳數(shù)和平均跳距誤差造成的差異會造成節(jié)點定位累積誤差，從而影響算法定位精度[7]。

1.2.2定位誤差分析

DV Hop算法定位誤差主要有：

（1）節(jié)點跳數(shù)產(chǎn)生的誤差

在DV-Hop定位過程中使用節(jié)點間的最小跳數(shù)來估算距離，誤差主要產(chǎn)生在以下兩個方面，一是跳數(shù)值越小表示距離越近，實則不然；二是可感知的鄰節(jié)點間的跳數(shù)為一跳，默認估算距離相等，實際上由于節(jié)點分布不均，相鄰節(jié)點間的距離并不相等。

（2）平均跳距產(chǎn)生的誤差

在DV-Hop定位過程中信標節(jié)點間的平均跳距通過最小跳數(shù)計算得到，由于最小跳數(shù)存在誤差，平均跳距也將存在誤差；未知節(jié)點使用最鄰近信標節(jié)點跳距均值作為自身跳距均值，本身就存在一定算法允許內(nèi)的誤差。

（3）計算定位誤差

使用數(shù)學(xué)方法（最小二乘法）求未知節(jié)點位置時，由于計算公式中的估算距離存在誤差，因此計算結(jié)果也會存在誤差。

2 提出改進算法

根據(jù)DV-Hop算法定位過程中存在的客觀條件和誤差分析，結(jié)合MADV-Hop[9]算法思想提出一種改進算法VADV-Hop，通過信標節(jié)點一定軌跡運動形成虛擬信標節(jié)點，未知節(jié)點參考多個信標節(jié)點信息估算位置坐標，然后取平均值。通過全網(wǎng)平均跳距校正節(jié)點平均跳距，在減少信標節(jié)點開銷的同時提高定準精度。

2.1 基于虛擬信標節(jié)點的改進

在DV-Hop算法基礎(chǔ)上，部署少量信標節(jié)點，信標節(jié)點按一定軌跡運動，每到一個新的位置形成一個新的信標節(jié)點，稱為虛擬信標節(jié)點，計算該信標節(jié)點位置，通過多個虛擬信標節(jié)點位置信息平均值降低計算誤差。

VADV-Hop算法信標節(jié)點分布見圖2，在R x R的監(jiān)測范圍中部署9個信標節(jié)點，確定位置，其中B-B為可移動信標節(jié)點，B為靜態(tài)信標節(jié)點，位置信息描述如下：

表1 m×m的區(qū)域中信標節(jié)點位置坐標

圖2 VADV-Hop信標節(jié)點分布

2.2 平均跳距校正

得到信標節(jié)點平均跳距以后，計算全網(wǎng)平均跳距誤差，利用該誤差值修正平均跳距。

h是信標節(jié)點和信標節(jié)點之間的跳數(shù)最小值，是每跳距離平均值：

為校正權(quán)值，取值為區(qū)間為（-0.5，0.5），使用校正后的平均跳距計算未知節(jié)點到信標節(jié)點的距離估值，使其更接近真實值。

2.3 VADV-Hop算法定位流程

VADV-Hop算法定位方法描述如圖3所示，未具體描述的環(huán)節(jié)保持跟DV-Hop算法一致，重點對從計算平均跳距后有變動的定位步驟進行描述。

（1）開始定位。

（2）信標節(jié)點使用洪泛算法廣播發(fā)送位置信息數(shù)據(jù)包，廣播次數(shù)為4次。

（3）鄰節(jié)點處理到達的數(shù)據(jù)包。

（4）計算跳距均值并校正，校正方法如公式3、公式4。

（5）計算節(jié)點間距值，使用校正后的平均跳距利用公式5計算未知節(jié)點與信標節(jié)點的距離。

（6）計算未知節(jié)點位置。

（7）信標節(jié)點按△d沿預(yù)設(shè)運動軌道運動形成虛擬信標節(jié)點，判斷位置是否重復(fù)，不重復(fù)則確定當前位置為有效位置，更新位置后返回第（2）步。

（8）在未知節(jié)點取3次以上自身坐標平均值。

圖3 VADV-Hop算法描述

3 VADV-Hop算法性能分析

3.1 仿真場景說明

使用Matlab軟件進行仿真實驗，仿真參數(shù)見表2。針對VADV-Hop算法的仿真實驗均進行了100次，每一次仿真實驗在相同仿真場景前提下對原算法也進行了對比實驗，使用100次定位結(jié)果的位置均值進行對比分析。未知節(jié)點在R x R的監(jiān)測范圍內(nèi)呈隨機分布，如圖4所示。

表2 VADV-Hop 仿真實驗參數(shù)設(shè)置

3.2 仿真實驗結(jié)果分析

（1）定位誤差分析

通過在相同模擬網(wǎng)絡(luò)場景下的對比實驗發(fā)現(xiàn)，基于虛擬信標節(jié)點的改進算法性能相對原算法有所提升。如圖5所示，改進后的算法定位誤差在3%到24%之間，誤差曲線基本保持在10%到20%之間，誤差震蕩較小。

（2）通信半徑對定位結(jié)果影響分析

在相同模擬場景下，調(diào)整通信半徑，保持其他參數(shù)不變，對改進算法定位精度進行仿真實驗。仿真數(shù)據(jù)結(jié)果顯示，VADV-Hop算法和原算法在改變通信半徑后定位精密度都受到了影響，其中原算法和VADV-Hop算法在較小通信半徑下定位精密度較低，VADV-Hop算法在半徑值達到一定值時（本實驗中的數(shù)值為30 m）后，表現(xiàn)出較穩(wěn)定的定位精度。

（3）未知節(jié)點數(shù)量對定位結(jié)果影響分析

在相同模擬場景下，改變投放的未知節(jié)點數(shù)量，其他參數(shù)不做調(diào)整，進行仿真實驗。

布置的信標節(jié)點數(shù)量未做調(diào)整，DV-Hop算法和VADV-Hop算法的定位精密度都隨著未知節(jié)點的數(shù)量發(fā)生變化。VADV-Hop算法由于采用了虛擬信標節(jié)點技術(shù)，增加了位置參考信息，在125個未知節(jié)點前定位性能較好，繼續(xù)增大未知節(jié)點數(shù)量后，定位誤差顯著上升。

圖7 未知節(jié)點數(shù)量對定位精度影響分析

4 結(jié)語

VADV-Hop算法在傳統(tǒng)DV-Hop算法的基礎(chǔ)上，通過信標節(jié)點的運動形成多個虛擬信標節(jié)點，一定程度上增加了未知節(jié)點的參考信息，通過模擬場景下的仿真實驗表示，VADV-Hop算法跟原算法比，在不增加信標節(jié)點的基礎(chǔ)上，算法性能穩(wěn)定，定位精度較有所提升，算法復(fù)雜性增加。

由于實驗都是在仿真環(huán)境下特定的網(wǎng)絡(luò)場景中估算未知節(jié)點的位置，未知節(jié)點數(shù)量保持在100附近。實際應(yīng)用中的WSN都是三維空間，網(wǎng)絡(luò)場景差異性很大，通信條件、戶外干擾等問題都會對算法的性能產(chǎn)生影響，因此后續(xù)將對三維場景的VADV-Hop算法進行研究。

[1]CHENG XIUZHEN，SHU HAWING，LIANG QILIAN，et al. Silent positioning in underwater acoustic sensor networks[C]//IEEE Transactions on Vehicular Technology. IEEE，2008：1756-1766.

[2]Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems，2003，22（1-4）：267-280.

[3]Bulusu N，Heidemann J，Estrin D. GPS-less Low Cost Outdoor Localization for Very Small Devices [J].Institute of Electrical and Electronics Engineers Personal Communications Magazine，2000（5）：28-34.

[4]Wang Z J，Jin H. Improvement on APIT Localization Algorithms for Wireless Sensor Networks：Networks Security， Wireless Communications And Trusted Computing，2009[C].International Conference on IEEE，2009（1）：719-723.

[5]Doherty L，El Ghaoui L. Convex Position Estimation in Wireless Sensor Networks [C].Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，2001：1655-1663.

[6]Lv X，Sun X，Zhou X，et al. DV-hop-MSO Based Localization Algorithm in Wireless SensorNetworks[M]//Advances in Wireless Sensor Networks. Springer Berlin Heidelberg，2014：312-316.

[7]于泉.無線傳感器網(wǎng)絡(luò)中DV-Hop改進算法的研究[D].江南大學(xué)，2016.

[8]馮友兵，馬艷，魏玉婷.基于移動錨節(jié)點的改進DV-Hop算法[[J].計算機科學(xué)，2015，42（s2）：277-279.

衡陽市科技計劃項目（2016KJ20）、湖南省教育廳科學(xué)研究項目（16C0565）、衡陽市社會科學(xué)聯(lián)合會（2017D107）、湖南環(huán)境生物職業(yè)技術(shù)學(xué)院支柱工程項目（湘環(huán)院教字〔2017〕46號）。