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

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

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

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

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

1 無線信號傳播損耗模型

基于RSSI的測距定位是獲取無線網絡節點位置信息的重要手段，常用的無線信號傳播損耗模型[6]為：

(1)

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

某個節點i傳播距離為d時的路損值記為：

(2)

在實際信號傳播過程中，無線信號強度會隨傳輸距離的增加而衰減，導致測量的RSSI值的相對誤差增大，因此去掉信號較小的RSSI值，可以在一定范圍上提高定位精度。以2.4GHz頻段的無線信號傳播RSSI值的ADAWifi測量數據為例[20]，對所采集數據擬合，得到RSSI值與距離的關系，結果如圖1所示。

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

2 DV-Hop算法基本原理

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

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

3 ADLDV-Hop算法

3.1 跳數閾值

當兩信標節點之間距離一定時，跳數值越高，表明傳播路徑越曲折，對平均跳距的影響越大。因此，去除不合理的跳數，能夠有效的提高定位精度。對于信標節點i來說，最大跳數:

(3)

式中:R為節點通信半徑,m；hi,max為最大跳數,保留2位小數。

3.2 平均跳距

3.2.1 平均跳距加權

在DV-Hop算法中，跳數與信標節點的通信半徑具有強相關性，通信半徑R越大，節點間的最小跳數越小。李鳳超等提出的一種平均跳距加權方法采用式(4)對跳數進行加權[13]：

(4)

式中：wi,j為權重系數,1；m為參與以信標節點i為中心的平均跳距計算的其他信標節點總數,個。

3.2.2 平均跳距節點集構造法

下面以圖2為例說明平均跳距節點集構造法，并由此計算平均跳距。已知信標節點i,j1,j2,j3,j4,j5,j6，未知節點q1,q2,q3，節點通信半徑R，其中j6為距離i最遠的信標節點(距離2R)。得出最大跳數hi,max=2.00。

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

(5)

3.3 節點間距離估計

節點間距離估計分覆蓋與否2種情況。

(6)

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

(7)

則實際跳數為：

(8)

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

(9)

3.4 未知節點坐標估計

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

(10)

令(X0，Y0)，(?x，?y)為待定位坐標的近似值與修正值。現設定X0=x1,Y0=y1，利用泰勒級數將式(8)線性化得到：

(11)

式(11)可以寫作：

(12)

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

3.5 ADLDV-Hop算法流程

算法流程圖如圖3所示。

4 算法仿真及數據分析

使用軟件MATLAB2017b進行結果仿真。仿真模型為100m×100m區域大小。發射功率為40mW，信噪比為10dB，取RSSI噪聲為xσ～N(0,4)[19]，假設信標節點和未知節點通信半徑都為R。試驗次數為50次，試驗結果取其平均值。定義定位精度[14]評價指標為相對定位誤差：

(13)

仿真分為2組進行：第1組與經典的DV-Hop算法和RSSI值測距定位算法進行對比，第2組與文獻[15]中的BRDV-Hop算法和文獻[17]的Hybrid DV-Hop算法進行對比。每組算法分別從節點通信半徑、信標節點比例、節點總數3個方面進行對比分析，每次改變其中的單一變量。

4.1 ADLDV-Hop算法與其他算法的數據對比分析

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

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

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

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

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

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

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

5 結語

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