基于RSSI平均跳距路損的DV-Hop定位算法

周向，鄒學(xué)玉 (長江大學(xué)電子信息學(xué)院，湖北 荊州 434023)

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，室內(nèi)無線定位技術(shù)在生活中的應(yīng)用越來越廣泛，例如大型商場、地下停車場等室內(nèi)場景，這些地方人口相對(duì)集中，對(duì)人員、物品等位置信息有較高的需求。已知的定位技術(shù)，比如全球定位系統(tǒng)[1]和北斗衛(wèi)星導(dǎo)航系統(tǒng)[2]，在室內(nèi)定位精度上已經(jīng)無法滿足人們的需求，于是很多學(xué)者開展了關(guān)于室內(nèi)無線定位技術(shù)的研究。經(jīng)典的定位算法有基于測距的定位算法和基于非測距的定位算法[3]2大類。基于測距的定位方法有到達(dá)時(shí)間(time of arrival,TOA)[4]、到達(dá)時(shí)間差(time difference of arrival,TDOA)[5]、到達(dá)角度(angle of arrival,AOA)[5]和信號(hào)接收強(qiáng)度(received signal strength Indication,RSSI)[6～8]等。目前使用RSSI測距定位的算法較多，該技術(shù)主要使用radio frequency(RF)信號(hào)，根據(jù)接收信號(hào)強(qiáng)度值計(jì)算信號(hào)的傳播損耗，按照相應(yīng)傳播損耗模型將傳播損耗值轉(zhuǎn)化為距離。這類方法具有較好的定位效果，但硬件成本高，能耗大。基于非測距的定位方法有質(zhì)心法(centroid method)[7]、距離向量法(distance vector hop,DV-Hop)[9]、無定型算法(amorphous)[10]、近似三角形內(nèi)點(diǎn)測試法(approximate point-in-triangulation test,APIT)[11]及凸規(guī)劃法[12]等。這類方法能節(jié)省硬件成本，但定位精度不高。

針對(duì)上述2大類測距方法的優(yōu)缺點(diǎn)，部分學(xué)者提出了多種改進(jìn)方案：李鳳超等[13]研究了一種無線傳感器網(wǎng)絡(luò)中改進(jìn)的DV-Hop定位算法，該方法采用設(shè)置跳數(shù)閾值，并對(duì)跳數(shù)進(jìn)行加權(quán)來求平均跳距，在一定程度上提高了定位精度；方旺盛等[14]結(jié)合DV-Hop與RSSI測距方法，提出設(shè)定一個(gè)基準(zhǔn)值RSSIbasic，結(jié)合DV-Hop中每一跳的RSSI值來求出兩者比值，以此作為跳數(shù)的方法；劉三陽等[15]利用信標(biāo)節(jié)點(diǎn)的平均跳距誤差，對(duì)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離進(jìn)行了修正；Feng Xin等[16]給出了一種以RSSImax為參考對(duì)象的比值改進(jìn)方案并由此提出了HCRDV-Hop算法；Omar等[17]提出了Hybrid DV-Hop算法，該算法主要是利用RSSI值把未知節(jié)點(diǎn)升級(jí)為信標(biāo)節(jié)點(diǎn)，并循環(huán)優(yōu)化位置信息。

上述方案在一定程度上提高了未知節(jié)點(diǎn)的定位精度，但依然存在一些問題，如跳距加權(quán)系數(shù)分母可能為0；以路損比作為跳數(shù)無法表征路損值與距離的非線性特性；DV-Hop全局平均跳距不能準(zhǔn)確反映局部平均跳距。針對(duì)上述問題，筆者提出了基于RSSI平均跳距路損DV-Hop定位算法(average hop distance’s path loss DV-Hop，ADLDV-Hop)：首先改進(jìn)跳距加權(quán)系數(shù)計(jì)算方法避免其分母為0；然后，對(duì)不同信標(biāo)節(jié)點(diǎn)構(gòu)造相應(yīng)的估計(jì)平均跳距節(jié)點(diǎn)集，以提高局部范圍的平均跳距準(zhǔn)確性；最后，以平均跳距路損值為基準(zhǔn)折合實(shí)際單跳路損值為非整跳數(shù)，以期減小節(jié)點(diǎn)間距估計(jì)誤差。

1 無線信號(hào)傳播損耗模型

基于RSSI的測距定位是獲取無線網(wǎng)絡(luò)節(jié)點(diǎn)位置信息的重要手段，常用的無線信號(hào)傳播損耗模型[6]為：

(1)

式中:d為發(fā)射點(diǎn)與接收點(diǎn)之間的距離,m；PL(d)為閱讀器收到距離為d時(shí)標(biāo)簽的RSSI值,dBm；d0為基準(zhǔn)距離，通常為1m；PT為信號(hào)發(fā)射功率,dBm；pL(d0)為基準(zhǔn)距離RSSI值,dBm；η為標(biāo)量,表示路徑損耗指數(shù)，一般取2～4；xσ為均值為0、方差為σ2的高斯噪聲，4≤σ2≤10[19]。

某個(gè)節(jié)點(diǎn)i傳播距離為d時(shí)的路損值記為：

(2)

在實(shí)際信號(hào)傳播過程中，無線信號(hào)強(qiáng)度會(huì)隨傳輸距離的增加而衰減，導(dǎo)致測量的RSSI值的相對(duì)誤差增大，因此去掉信號(hào)較小的RSSI值，可以在一定范圍上提高定位精度。以2.4GHz頻段的無線信號(hào)傳播RSSI值的ADAWifi測量數(shù)據(jù)為例[20]，對(duì)所采集數(shù)據(jù)擬合，得到RSSI值與距離的關(guān)系，結(jié)果如圖1所示。

圖1中包括了線性插值擬合折線和對(duì)數(shù)擬合曲線。由于RSSI值易受環(huán)境因素的影響，且該影響并不隨著距離改變而變化，所以線性插值擬合折線會(huì)出現(xiàn)波動(dòng)起伏；另外該折線反映了距離越遠(yuǎn)，RSSI值越小這一整體趨勢。對(duì)原始數(shù)據(jù)使用最小二乘法進(jìn)行對(duì)數(shù)擬合得到對(duì)數(shù)擬合曲線，該曲線驗(yàn)證了RSSI值與距離之間的對(duì)數(shù)關(guān)系。由于RSSI值是反映實(shí)際距離的信號(hào)強(qiáng)度數(shù)值，所以誤差較小的RSSI值可以使距離的計(jì)算更精確。由于較小的信號(hào)強(qiáng)度不易被檢測，會(huì)導(dǎo)致相對(duì)誤差增大，因此，不使用RSSI較小的值計(jì)算距離可以提高定位精度，在筆者算法ADLDV-Hop中只取單跳的路損值作為測距依據(jù)。

2 DV-Hop算法基本原理

DV-Hop基本原理是通過計(jì)算信標(biāo)節(jié)點(diǎn)兩兩之間的距離，然后信標(biāo)節(jié)點(diǎn)將攜帶的信息傳播給其它相鄰節(jié)點(diǎn)，并在傳播過程中記錄不同信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)[12～14]。該算法主要由距離矢量和節(jié)點(diǎn)之間的最小跳數(shù)來估計(jì)平均每跳距離，進(jìn)而估計(jì)信標(biāo)節(jié)點(diǎn)和待定位節(jié)點(diǎn)之間的距離。當(dāng)某待定位節(jié)點(diǎn)得到至少3組到信標(biāo)節(jié)點(diǎn)的距離信息時(shí)，使用三角形法或最小二乘法求出該節(jié)點(diǎn)的估計(jì)坐標(biāo)。通過這種方法，可以利用少量的信標(biāo)節(jié)點(diǎn)，求得較多的待定位節(jié)點(diǎn)坐標(biāo)，并且定位范圍較廣。

由于節(jié)點(diǎn)在平面上隨機(jī)分布，不同節(jié)點(diǎn)之間跳數(shù)、跳距存在較大的差異性，導(dǎo)致實(shí)際坐標(biāo)與利用DV-Hop算法估計(jì)的坐標(biāo)之間有較大的誤差。為解決算法中跳距方差過大使得定位誤差較大問題，引入非整數(shù)跳數(shù)(即節(jié)點(diǎn)之間的跳數(shù)可以為非整數(shù)，如1.22數(shù)值)來降低定位誤差。

3 ADLDV-Hop算法

3.1 跳數(shù)閾值

當(dāng)兩信標(biāo)節(jié)點(diǎn)之間距離一定時(shí)，跳數(shù)值越高，表明傳播路徑越曲折，對(duì)平均跳距的影響越大。因此，去除不合理的跳數(shù)，能夠有效的提高定位精度。對(duì)于信標(biāo)節(jié)點(diǎn)i來說，最大跳數(shù):

(3)

式中:R為節(jié)點(diǎn)通信半徑,m；hi,max為最大跳數(shù),保留2位小數(shù)。

3.2 平均跳距

3.2.1 平均跳距加權(quán)

在DV-Hop算法中，跳數(shù)與信標(biāo)節(jié)點(diǎn)的通信半徑具有強(qiáng)相關(guān)性，通信半徑R越大，節(jié)點(diǎn)間的最小跳數(shù)越小。李鳳超等提出的一種平均跳距加權(quán)方法采用式(4)對(duì)跳數(shù)進(jìn)行加權(quán)[13]：

(4)

式中：wi,j為權(quán)重系數(shù),1；m為參與以信標(biāo)節(jié)點(diǎn)i為中心的平均跳距計(jì)算的其他信標(biāo)節(jié)點(diǎn)總數(shù),個(gè)。

3.2.2 平均跳距節(jié)點(diǎn)集構(gòu)造法

下面以圖2為例說明平均跳距節(jié)點(diǎn)集構(gòu)造法，并由此計(jì)算平均跳距。已知信標(biāo)節(jié)點(diǎn)i,j1,j2,j3,j4,j5,j6，未知節(jié)點(diǎn)q1,q2,q3，節(jié)點(diǎn)通信半徑R，其中j6為距離i最遠(yuǎn)的信標(biāo)節(jié)點(diǎn)(距離2R)。得出最大跳數(shù)hi,max=2.00。

從圖2中可以得到以下信息：j1,j3在通信半徑內(nèi)，i到j(luò)1,j3的最小跳數(shù)為1跳；i到j(luò)2的最小跳數(shù)為1跳，由于j2不在i及其有關(guān)節(jié)點(diǎn)的可達(dá)半徑R內(nèi)，則j2不參與i的平均跳距計(jì)算；j4在i的通信半徑R外，但在j3的通信半徑內(nèi)(j3可與i節(jié)點(diǎn)通信)，因此j4最小跳數(shù)為2；j5,j6都在i的通信半徑外，j5到i的最小跳數(shù)為2，j6到i的最小跳數(shù)為3，大于所設(shè)定閾值2.00，舍去j6。綜合上述信息求平均跳距得：

(5)

3.3 節(jié)點(diǎn)間距離估計(jì)

節(jié)點(diǎn)間距離估計(jì)分覆蓋與否2種情況。

(6)

假設(shè)信標(biāo)節(jié)點(diǎn)i(這里的i也可為未知節(jié)點(diǎn))與覆蓋的未知節(jié)點(diǎn)q之間的路損值pi,q(di,q)(簡記為pi,q)，已知i，q之間的估計(jì)距離為d=Di,q，考慮隨機(jī)噪聲xσ均值為0，則由式(2)可得Di,q應(yīng)滿足：

(7)

則實(shí)際跳數(shù)為：

(8)

2)信標(biāo)節(jié)點(diǎn)i不覆蓋未知節(jié)點(diǎn)q但連通可達(dá)。若i到未知節(jié)點(diǎn)q之間存在多個(gè)不同傳播路徑，則Di,q取所有路徑中的累加距離的最小值。具體方法如下：取節(jié)點(diǎn)i到未知節(jié)點(diǎn)q的每條可達(dá)路徑上的相鄰節(jié)點(diǎn)間的單跳路損值，若路徑l(l=1,2,…,L)為i-j1-j2-…-jn-q(其中j1,j2,…,jn為未知節(jié)點(diǎn)),則路徑l上每條鏈路的路損值為pi,j1,pj1,j2,…,pjn-1,jn,pjn,q，由式(6)計(jì)算每條鏈路距離，路徑l的估值距離為：

(9)

3.4 未知節(jié)點(diǎn)坐標(biāo)估計(jì)

設(shè)未知節(jié)點(diǎn)q與n(n≥3)個(gè)信標(biāo)節(jié)點(diǎn)連通，，若n個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)分別為(x1,y1),(x2,y2),…,(xn,yn)，由式(8)或式(9)估算未知節(jié)點(diǎn)q到n個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為d1,q,d2,q,…,dn,q，用最小二乘法[18]求出未知節(jié)點(diǎn)q的坐標(biāo)(xq,yq)。設(shè)待定位節(jié)點(diǎn)坐標(biāo)為(xq,yq)，誤差值為Vi，可列出誤差方程如下：

(10)

令(X0，Y0)，(?x，?y)為待定位坐標(biāo)的近似值與修正值?，F(xiàn)設(shè)定X0=x1,Y0=y1，利用泰勒級(jí)數(shù)將式(8)線性化得到：

(11)

式(11)可以寫作：

(12)

根據(jù)最小二乘法，即殘差向量V和權(quán)矩陣A滿足VΤAV為最小的條件下，求取未知數(shù)的最佳估值。 如當(dāng)V=O時(shí)有最小平方差時(shí)，求解方程(18)得X=-(ATA)-1(ATL)，未知節(jié)點(diǎn)的坐標(biāo)(xq,yq)為(x1+?x,y1+?y)。

3.5 ADLDV-Hop算法流程

算法流程圖如圖3所示。

4 算法仿真及數(shù)據(jù)分析

使用軟件MATLAB2017b進(jìn)行結(jié)果仿真。仿真模型為100m×100m區(qū)域大小。發(fā)射功率為40mW，信噪比為10dB，取RSSI噪聲為xσ～N(0,4)[19]，假設(shè)信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)通信半徑都為R。試驗(yàn)次數(shù)為50次，試驗(yàn)結(jié)果取其平均值。定義定位精度[14]評(píng)價(jià)指標(biāo)為相對(duì)定位誤差：

(13)

仿真分為2組進(jìn)行：第1組與經(jīng)典的DV-Hop算法和RSSI值測距定位算法進(jìn)行對(duì)比，第2組與文獻(xiàn)[15]中的BRDV-Hop算法和文獻(xiàn)[17]的Hybrid DV-Hop算法進(jìn)行對(duì)比。每組算法分別從節(jié)點(diǎn)通信半徑、信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)總數(shù)3個(gè)方面進(jìn)行對(duì)比分析，每次改變其中的單一變量。

4.1 ADLDV-Hop算法與其他算法的數(shù)據(jù)對(duì)比分析

選取空曠地區(qū)的路徑損耗指數(shù)η=2,信噪比為10dB。

1)未知節(jié)點(diǎn)總數(shù)加上信標(biāo)節(jié)點(diǎn)總數(shù)為100個(gè)，節(jié)點(diǎn)通信半徑R=30m，信標(biāo)節(jié)點(diǎn)比例在5%～45%范圍內(nèi)改變。圖4反映了隨著信標(biāo)節(jié)點(diǎn)比例不斷升高的過程中5種定位算法的相對(duì)定位誤差逐漸減小這一整體趨勢。當(dāng)信標(biāo)節(jié)點(diǎn)比例在5%～10%之間變化時(shí)5種對(duì)比算法的相對(duì)定位誤差都高于30%，缺乏實(shí)際的定位意義；當(dāng)信標(biāo)節(jié)點(diǎn)比例在10%～40%之間變化時(shí)，5種算法定位精度提高明顯，其中ADLDV-Hop算法相對(duì)于DV-Hop、RSSI測距定位、BRDV-Hop和HCRDV-Hop算法，其相對(duì)定位誤差上分別減小了約10%、8%、7%、5%；在信標(biāo)節(jié)點(diǎn)與節(jié)點(diǎn)總數(shù)比例在5%～45%范圍內(nèi)改變時(shí)ADLDV-Hop算法的定位精度優(yōu)于其他4種算法。另外，從圖4中可以看出，當(dāng)信標(biāo)節(jié)點(diǎn)比例高于40%時(shí)，信標(biāo)節(jié)點(diǎn)比例增加所引起的定位精度提高趨于飽和，此時(shí)依靠增加信標(biāo)節(jié)點(diǎn)比例來降低相對(duì)定位誤差的性價(jià)比較低。

2)未知節(jié)點(diǎn)加上信標(biāo)節(jié)點(diǎn)總數(shù)為100個(gè)，其中信標(biāo)節(jié)點(diǎn)20個(gè)，未知節(jié)點(diǎn)80個(gè)，改變節(jié)點(diǎn)通信半徑R。從圖5中可以看出，當(dāng)信標(biāo)節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)比例一定時(shí)，增加節(jié)點(diǎn)通信半徑，ADLDV-Hop算法相對(duì)于DV-Hop、RSSI測距定位、BRDV-Hop和HCRDV-Hop算法，其相對(duì)定位誤差上分別最大減小提高了17.2%、13.3%、8.2%和7.6%；隨著通信半徑在10～40m的范圍內(nèi)增大，DV-Hop、RSSI測距定位、BRDV-Hop算法的相對(duì)定位誤差下降趨勢緩慢，而HCRDV-Hop和ADLDV-Hop算法的相對(duì)定位誤差下降較為顯著；通信半徑從10m增至40m時(shí)，ADLDV-Hop算法的相對(duì)定位誤差減小了6.6%，優(yōu)于BRDV-Hop和HRCDV-Hop算法的相對(duì)定位誤差減小值3.8%和3.2%。結(jié)果表明，在滿足一定信噪比的情況下，ADLDV-Hop算法在節(jié)點(diǎn)通信半徑增大時(shí)有利于提高定位精度。

3)保持信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)例為2∶8，且節(jié)點(diǎn)的通信半徑為R=20m，節(jié)點(diǎn)總數(shù)在100～400個(gè)范圍內(nèi)變化。在通信半徑R=20m的情況下，增加節(jié)點(diǎn)總數(shù)時(shí)保持信標(biāo)節(jié)點(diǎn)比例不變，從圖6中可以看出，ADLDV-Hop算法相對(duì)于DV-Hop、RSSI值測距定位、BRDV-Hop和HCRDV-Hop算法，其相對(duì)定位誤差分別最大減小了11.2%、10.6%、6.2%和4.1%；隨著節(jié)點(diǎn)總數(shù)的增加，5種算法相對(duì)定位誤差均逐漸減?。划?dāng)節(jié)點(diǎn)總數(shù)數(shù)量增加到3倍時(shí)，ADLDV-Hop算法的相對(duì)定位誤差從28.0%下降到18.6%，BRDV-Hop算法的相對(duì)定位誤差從32.0%下降到24.4%，HRCDV-Hop算法的相對(duì)定位誤差從32.0%下降到22.5%。結(jié)果表明，依賴節(jié)點(diǎn)總數(shù)數(shù)量增加來提高定位精度需要付出較大代價(jià)，性價(jià)比不高。

4.2 不同信噪比和不同路徑損耗指數(shù)對(duì)ADLDV-Hop算法相對(duì)定位誤差的影響

1)保持節(jié)點(diǎn)總數(shù)為100個(gè)，信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)比例為2∶8，路徑損耗指數(shù)η=2。對(duì)不同信噪比情況下的相對(duì)定位誤差進(jìn)行分析仿真試驗(yàn)，結(jié)果如圖7所示。從圖7中可以看出，在信噪比為5dB時(shí)，ADLDV-Hop算法相對(duì)定位誤差為30.4%，隨著信噪比的增大，相對(duì)定位誤差逐漸減??；當(dāng)信噪比為30dB時(shí)相對(duì)定位誤差減小到5.1%；由此表明，信噪比增加，有利于ADLDV-Hop算法定位精度的提升。

2)保持節(jié)點(diǎn)總數(shù)為200，信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)比例為2∶8，信噪比為10dB。選取不同的路徑損耗指數(shù)η，對(duì)3種算法(HCRDV-Hop算法、BRDV-Hop算法和ADLDV-Hop算法)進(jìn)行仿真試驗(yàn)，結(jié)果如圖8所示。從圖8中可以看出，在路徑損耗指數(shù)η取值范圍內(nèi)，隨著路徑損耗指數(shù)在2～4之間逐漸增加，3種算法相對(duì)定位誤差都逐漸增加，但ADLDV-Hop算法相較于BRDV-Hop和HCRDV-Hop算法具有更高的定位精度。結(jié)果表明，路徑損耗指數(shù)越高，ADLDV-Hop算法定位精度下降，但在相同條件下的定位精度優(yōu)于BRDV-Hop和HCRDV-Hop算法。

5 結(jié)語

筆者提出的ADLDV-Hop算法，通過改進(jìn)跳距加權(quán)系數(shù)，解決了可能出現(xiàn)跳距系數(shù)無限大的情況；針對(duì)不同的信標(biāo)節(jié)點(diǎn)計(jì)算其平均跳距，克服節(jié)點(diǎn)分布不均勻帶來對(duì)定位精度的影響；后以平均跳距及其參考路損折合實(shí)際路損來估算節(jié)點(diǎn)間距，增加了估計(jì)距離的準(zhǔn)確性。相對(duì)于HVRDV-Hop和BRDV-Hop算法，在相同條件下，ADLDV-Hop算法進(jìn)一步提高了定位精度；同時(shí)，增加節(jié)點(diǎn)通信半徑和信噪比有利于提高定位精度。