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

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

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

DOI：10.15938/j.jhust.2018.01.024

中圖分類號： TP399

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

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

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

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

1DVHop算法定位流程

DVHop定位步驟一般分三步：

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

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

2.1定位誤差分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)論

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

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

參 考 文 獻(xiàn)：

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

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

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

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

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