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

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

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

關鍵詞：DVHop；RSSI；最小二乘法

DOI：10.15938/j.jhust.2018.01.024

中圖分類號： TP399

文獻標志碼： A

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

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

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

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

1DVHop算法定位流程

DVHop定位步驟一般分三步：

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

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

2.1定位誤差分析

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

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

2）在定位過程中，網(wǎng)絡使用平均跳距估計值與最小跳數(shù)相乘來計算節(jié)點間的實際距離。由于網(wǎng)絡節(jié)點的隨機部署性，節(jié)點之間的實際跳距往往差距很大，如果獲得的平均跳距Hopsize不理想，必然會導致計算的估計跳距與實際跳距誤差增大。當節(jié)點在網(wǎng)絡中進行多跳，又會因為平均跳距存在的誤差導致計算出的定位距離與實際距離之間誤差累積增大，從而影響后續(xù)的定位過程，定位存在較大的誤差。

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

2.2DVHop算法的改進方法

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

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

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

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

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

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

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

2.2.2最小二乘法修正的坐標計算

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

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

4結論

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

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

參 考 文 獻：

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

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

[3]朱若茜，張禮勇. 無線傳感器網(wǎng)絡監(jiān)測環(huán)境中的煤礦安全度評價[J]. 哈爾濱理工大學學報，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的多維標度室內定位算法[J]. 儀器儀表學報，2014（2）：262-265.

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

（編輯：關毅）