無線傳感器網(wǎng)絡(luò)的DV—Hop定位算法改進(jìn)

董靜薇　楊光　劉洋　張?zhí)扃?/p>

摘要：針對(duì)傳統(tǒng)DVHop算法存在定位精準(zhǔn)度低這一缺陷，分析了影響傳統(tǒng)DVHop算法定位精度的三點(diǎn)主要因素：錨節(jié)點(diǎn)分布密度、平均跳距誤差、極大似然法擴(kuò)大誤差。從算法的平均跳距計(jì)算和節(jié)點(diǎn)坐標(biāo)計(jì)算兩個(gè)階段入手，引入RSSI（Receive Signal Strength Indicator）技術(shù)對(duì)平均跳距計(jì)算過程進(jìn)行優(yōu)化處理，同時(shí)對(duì)未知節(jié)點(diǎn)坐標(biāo)計(jì)算過程采用最小二乘法進(jìn)行修正。仿真結(jié)果表明：改進(jìn)后的算法在測(cè)距精度上比原始算法提高了約30%；在相對(duì)定位精度上提高了約35%。

關(guān)鍵詞：DVHop；RSSI；最小二乘法

DOI：10.15938/j.jhust.2018.01.024

中圖分類號(hào)： TP399

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2018）01-0132-05

Abstract：As the problems of lower localization accuracy appeared in the traditional DVHop algorithm， the author analyzed three main factors that influence the localization accuracy of original DVHop algorithm which started from the calculation of the average jump distance in algorithm and the calculation of node coordinates. The author then proposed the calculation method of average jump distance based on the weighted correction of the RSSI（Receive Signal Strength Indicator） and the calculation method of unknown node coordinates based on the correction of the total least squares （TLS）. The simulation result shows that compared to the traditional DVHop algorithm， the accuracy of the improved algorithm increased by about 30% in distance measurement as well as rose approximately by 35% in relative localization precision.

Keywords：DVHop； RSSI； total least squares （TLS）

0引言

無線傳感網(wǎng)絡(luò)（Wireless Sensor Network）屬于一種經(jīng)傳感器節(jié)點(diǎn)利用多跳模式自組建的網(wǎng)絡(luò)，經(jīng)過多年發(fā)展，不再局限在軍事領(lǐng)域，還在環(huán)境、醫(yī)療等領(lǐng)域廣泛應(yīng)用[1]。無線傳感網(wǎng)絡(luò)中最關(guān)鍵技術(shù)就是節(jié)點(diǎn)的準(zhǔn)確定位，沒有精確的定位信息，無線傳感器節(jié)點(diǎn)在監(jiān)測(cè)到的相關(guān)環(huán)境的數(shù)據(jù)信息就沒有意義[2]。現(xiàn)有的WSN定位技術(shù)根據(jù)是否測(cè)距可分為基于測(cè)距和無需測(cè)距技術(shù)[3]。需要測(cè)距的定位技術(shù)一般利用超聲波等探測(cè)手段測(cè)量節(jié)點(diǎn)信息，定位準(zhǔn)確度較高，同時(shí)對(duì)基礎(chǔ)硬件標(biāo)準(zhǔn)苛刻，所以部署網(wǎng)絡(luò)投入成本很高；無需測(cè)距的定位技術(shù)根據(jù)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的估算距離來計(jì)算位置，對(duì)傳感器節(jié)點(diǎn)的硬件要求相對(duì)較低。考慮到網(wǎng)絡(luò)部署的成本，算法功耗等因素，無需測(cè)距的定位算法更具有實(shí)際使用價(jià)值。

DVHop定位方法在WSN的節(jié)點(diǎn)定位中使用廣泛，它是一種不用測(cè)距的定位方法，對(duì)硬件的要求低，環(huán)境影響小。在實(shí)際應(yīng)用場(chǎng)景中，此運(yùn)算方法的優(yōu)勢(shì)包括：耗能少、運(yùn)算量低、環(huán)保、對(duì)硬件無嚴(yán)格要求等。但是DVHop算法因?yàn)楸旧淼挠?jì)算特點(diǎn)存在一些先天缺陷，而最主要缺陷是定位精度較低。例如當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)分布不均衡時(shí)，由于節(jié)點(diǎn)間距都使用同一平均跳距計(jì)算，此時(shí)的節(jié)點(diǎn)的平均距離與實(shí)際距離有很大的偏差，因此該算法的定位誤差比較大。

Dragos Niculescu等學(xué)者歸納提出DVHop計(jì)算方法之后，后續(xù)國內(nèi)外學(xué)者對(duì)這一方法定位準(zhǔn)確率較低的問題做出了優(yōu)化與改進(jìn)。例如文[4]總結(jié)出一種新的加權(quán)算法，算法融合了環(huán)境因素的同時(shí)使用了許多錨節(jié)點(diǎn)的平均跳距。這一方法最大的問題是：對(duì)硬件要求苛刻、運(yùn)算工作量過大。文[5]提出了通過人工方式部署網(wǎng)絡(luò)的方法，使網(wǎng)絡(luò)中的錨節(jié)點(diǎn)分布均衡來減小平均跳距誤差。這種方法對(duì)人力的成本太高且適用場(chǎng)景窄。可以看出，許多的學(xué)者耗費(fèi)了大量精力去分析、探究DVHop算法，同時(shí)總結(jié)出不少改進(jìn)方法，但是想要達(dá)到理想的定位水平還有不小的差距，需不斷的進(jìn)行完善，進(jìn)一步改進(jìn)。

本文針對(duì)DVHop算法定位精度低這一缺陷，提出了對(duì)平均跳距引入RSSI加權(quán)優(yōu)化和對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行最小二乘法修正，改進(jìn)原始DVHop算法中的兩個(gè)定位過程。

1DVHop算法定位流程

DVHop定位步驟一般分三步：

1）獲取錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的最小跳數(shù)。

首先錨節(jié)點(diǎn)通過洪泛的模式，向全網(wǎng)絡(luò)中傳遞自己的信息，數(shù)據(jù)包含跳數(shù)J、坐標(biāo)P。然后未知節(jié)點(diǎn)利用距離向量交換協(xié)議（distance vector routing），獲取錨節(jié)點(diǎn)到自己的跳數(shù)信息。如果到錨節(jié)點(diǎn)有多個(gè)跳數(shù)時(shí)，未知節(jié)點(diǎn)只計(jì)算整個(gè)過程中最小的跳數(shù)h。未知節(jié)點(diǎn)獲取最小跳數(shù)的過程如圖1所示。

2.1定位誤差分析

DVHop在定位的過程中，最為核心的問題是定位精度不夠。研究DVHop定位流程之后，總結(jié)了導(dǎo)致定位精度存在偏差的主要幾個(gè)來源：

1）算法的定位精度與錨節(jié)點(diǎn)的分布情況和分布密度密切相關(guān)：錨節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域部署越均衡，部署量愈多，其定位地準(zhǔn)確度愈大。錨節(jié)點(diǎn)的部署情況對(duì)定位的影響情況如圖3所示。在實(shí)際的網(wǎng)絡(luò)環(huán)境中，節(jié)點(diǎn)的布置是飛機(jī)散播等方式隨機(jī)分布，節(jié)點(diǎn)分布不會(huì)呈現(xiàn)規(guī)律性的等間距分布。另一方面，錨節(jié)點(diǎn)的相對(duì)硬件成本較高，在網(wǎng)絡(luò)中的存在比例小。這種情況下，網(wǎng)絡(luò)容易出現(xiàn)定位盲點(diǎn)區(qū)域，影響算法的定位精度。

2）在定位過程中，網(wǎng)絡(luò)使用平均跳距估計(jì)值與最小跳數(shù)相乘來計(jì)算節(jié)點(diǎn)間的實(shí)際距離。由于網(wǎng)絡(luò)節(jié)點(diǎn)的隨機(jī)部署性，節(jié)點(diǎn)之間的實(shí)際跳距往往差距很大，如果獲得的平均跳距Hopsize不理想，必然會(huì)導(dǎo)致計(jì)算的估計(jì)跳距與實(shí)際跳距誤差增大。當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中進(jìn)行多跳，又會(huì)因?yàn)槠骄啻嬖诘恼`差導(dǎo)致計(jì)算出的定位距離與實(shí)際距離之間誤差累積增大，從而影響后續(xù)的定位過程，定位存在較大的誤差。

3）一般情況下，獲取多個(gè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的估測(cè)距離值之后，利用極大似然估計(jì)法等手段計(jì)算分析其他未知的節(jié)點(diǎn)坐標(biāo)。但由于三邊測(cè)量法對(duì)初始值相對(duì)敏感，測(cè)距誤差對(duì)其影響很大。在極大似然估計(jì)法中，帶有誤差的坐標(biāo)代入矩陣后，誤差矩陣會(huì)嚴(yán)重影響所求矩陣也就是坐標(biāo)定位的精確度。

2.2DVHop算法的改進(jìn)方法

原始算法的定位過程受地形等外界環(huán)境因素的影響較小，但在某些具體的應(yīng)用場(chǎng)景中，當(dāng)節(jié)點(diǎn)分布不均衡時(shí)，實(shí)際跳距與平均跳距之間存在的誤差很大。所以，為了增加DVHop計(jì)算方法的定位準(zhǔn)確率，本文就DVHop計(jì)算方法存在的問題在兩個(gè)方面展開了針對(duì)性的優(yōu)化。

2.2.1RSSI平均跳距優(yōu)化

本文根據(jù)信號(hào)接收強(qiáng)度RSSI測(cè)距原理[6]，在計(jì)算平均跳距時(shí)加入RSSI技術(shù)進(jìn)行測(cè)距優(yōu)化。當(dāng)原算法中用RSSI測(cè)得的跳距轉(zhuǎn)換為一個(gè)修正系數(shù)來修正計(jì)算出的每跳跳距。修正系數(shù)是RSSI測(cè)距長度與RSSI平均測(cè)距長度做比值計(jì)算得來的。優(yōu)化后的跳距可以減小因網(wǎng)絡(luò)中節(jié)點(diǎn)分布不均衡所帶來的每跳的跳距誤差。加入RSSI優(yōu)化后的平均跳距計(jì)算方法如下：

1）改進(jìn)算法在錨節(jié)點(diǎn)廣播含有自身信息的數(shù)據(jù)包時(shí)向包中添加一個(gè)RSSI方法測(cè)得估計(jì)距離數(shù)據(jù)RSSI（n）。節(jié)點(diǎn)在接收到數(shù)據(jù)包后，將自身的RSSI數(shù)據(jù)與包中的RSSI（n）相加，同時(shí)將跳數(shù)Hops+1，然后重新修正數(shù)據(jù)包中的相關(guān)字段。當(dāng)數(shù)據(jù)包進(jìn)行了n跳到達(dá)一個(gè)節(jié)點(diǎn)后進(jìn)行判斷，如果當(dāng)前跳數(shù)小于最小跳數(shù)字段時(shí)，將其刷新，反之丟棄。

2）當(dāng)數(shù)據(jù)包進(jìn)行了n跳到達(dá)一個(gè)錨節(jié)點(diǎn)時(shí)，先通過數(shù)據(jù)包中的相關(guān)字段計(jì)算出節(jié)點(diǎn)間的RSSI每跳跳距，然后使用式（5）計(jì)算RSSI平均估測(cè)距離。

RSSIavg=RSSI（1）+RSSI（2）+…+RSSI（n）n（5）

3）最后對(duì)平均跳距Hopsize進(jìn)行優(yōu)化，優(yōu)化系數(shù)δi是以節(jié)點(diǎn)間每跳的RSSI估測(cè)距離與平均估測(cè)距離RSSIavg做比值，當(dāng)數(shù)據(jù)包里的跳數(shù)是n的情況下，利用公式（6）計(jì)算出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離d。

2.2.2最小二乘法修正的坐標(biāo)計(jì)算

在計(jì)算平均跳距過程中，盡管RSSI進(jìn)行了優(yōu)化，得到的平均跳距更精確，計(jì)算出的節(jié)點(diǎn)間距離值d更接近實(shí)際物理距離。但是計(jì)算出估測(cè)距離d與實(shí)際距離存在一定誤差，由于極大似然估計(jì)法等計(jì)算方法對(duì)初始值敏感，如果直接使用估計(jì)距離對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行求解，存在誤差的初始值代入方程后會(huì)使定位誤差進(jìn)一步擴(kuò)大，致使上一步的RSSI平均跳距優(yōu)化工作失去意義。本文針對(duì)極大似然估計(jì)法存在的問題使用最小二乘法進(jìn)行修正。

根據(jù)圖6中的數(shù)據(jù)可以分析出3種算法的相對(duì)定位誤差區(qū)別較大，改進(jìn)后的算法在相對(duì)定位精度上優(yōu)于原算法約35%，優(yōu)于HDDVHop算法約23%，并且定位誤差抖動(dòng)小，算法的穩(wěn)定性更好。

4結(jié)論

本文研究了傳統(tǒng)的DVHop計(jì)算方法的定位步驟，對(duì)引起定位偏差的根源進(jìn)行了分析和歸納，在計(jì)算平均跳距的步驟中引入RSSI技術(shù)對(duì)實(shí)際跳距進(jìn)行修正；在計(jì)算未知節(jié)點(diǎn)坐標(biāo)的步驟中針對(duì)極大似然估計(jì)法存在的誤差累積使用最小二乘法進(jìn)行修正。

并對(duì)比分析了原算法、HDDVHop算法與改進(jìn)算法。通過仿真實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，根據(jù)本文對(duì)算法的兩個(gè)步驟進(jìn)行改進(jìn)，改進(jìn)后的DVHop算法在相對(duì)定位精度上優(yōu)于原算法約35%，優(yōu)于文獻(xiàn)中的HDDVHop算法約23%。使算法更具有推廣和使用價(jià)值。本文也存在一些不足：只考慮固定錨節(jié)點(diǎn)模型，沒有引入移動(dòng)節(jié)點(diǎn)定位的可能；定位算法只是在二維空間計(jì)算坐標(biāo)節(jié)點(diǎn)。擴(kuò)展到三維空間定位是DVHop定位算法未來的發(fā)展方向。

參 考 文 獻(xiàn)：

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

[2]李文辰，張雷. 無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法研究[J]. 計(jì)算機(jī)仿真，2013（2）：191-193.

[3]朱若茜，張禮勇. 無線傳感器網(wǎng)絡(luò)監(jiān)測(cè)環(huán)境中的煤礦安全度評(píng)價(jià)[J]. 哈爾濱理工大學(xué)學(xué)報(bào)，2013（3）：32-35.

[4]Yu Hu，Xuemei Li. An Improvement of DVHop Localization Algorithm for Wireless Sensor Networks[J]. Telecommunication Systems，2013，53（1）：13-18.

[5]Shrawan Kumar，D. K. Lobiyal. An Advanced DVHop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications，2013，71（2）：1365-1385.

[6]GOLDONI E，SAVIOLI A，RISI M. Lobiyal，et al. Experimental Analysis of RSSIbased Indoor Localization with IEEE 802.15.4[C]// 2010 European Wireless Conference，2010：71-77.

[7]石欣，印愛民. 基于RSSI的多維標(biāo)度室內(nèi)定位算法[J]. 儀器儀表學(xué)報(bào)，2014（2）：262-265.

[8]狄振強(qiáng)，馬淑麗. DVHop算法中未知節(jié)點(diǎn)獲取校正值的改進(jìn)方法[J]. 通信技術(shù)，2016（3）：329-332.

（編輯：關(guān)毅）