無線傳感器網絡的DV—Hop定位算法改進

董靜薇　楊光　劉洋　張天琦

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

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

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

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

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

1DVHop算法定位流程

DVHop定位步驟一般分三步：

1）獲取錨節點與未知節點間的最小跳數。

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

2.1定位誤差分析

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

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

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

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

2.2DVHop算法的改進方法

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

2.2.1RSSI平均跳距優化

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

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

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

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

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

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

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

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

4結論

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

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

參 考 文 獻：

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

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

[3]朱若茜，張禮勇. 無線傳感器網絡監測環境中的煤礦安全度評價[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算法中未知節點獲取校正值的改進方法[J]. 通信技術，2016（3）：329-332.

（編輯：關毅）