WSNs中基于測距修正和擬牛頓法的節點定位算法

孫 豫

(駐馬店職業技術學院信息工程學院，河南 駐馬店 463000)

0 引言

隨著通信技術的迅速發展，無線傳感網絡(wireless sensor networks，WSNs)[1]已在環境監測、軍事和醫療等領域廣泛應用。WSNs中節點具有感測、通信能力。這些節點感測環境數據，如溫度、濕度，并將所感測的數據傳輸至控制中心，以便控制中心進行處理。然而，只有明確了節點位置信息，其感測的數據才可能具有意義。因此，定位是WSNs的關鍵技術。

測距定位和非測距定位算法是主要的兩類定位算法。不失一般性，基于測距定位算法精度高于非測距定位算法。常見的測距算法有：基于接收信號強度指標(received signal strength indication, RSSI)[2]、基于信號到達角度(angle of arrival, AoA)[3]、基于信號到達時間(time of arrival, ToA)[4]。與ToA和AoA不同，基于RSSI測距無需額外的測量設備，易實施。因此，基于RSSI測距定位受到廣泛關注。

為了提高基于RSSI測距定位的精度，對RSSI值進行濾波處理。文獻[5]提出雙標簽定位算法。該算法采用兩個水平或者垂直定位標簽，利用這兩個標簽所采集的RSSI值進行測距，進而降低RSSI因環境影響而產生的波動。然而，該算法需要額外部署一個標簽，增加了硬件成本。

近期，由于微處理器數據處理速率和能力的提升，節點能夠在較短時間內處理一定量的數據。因此，一些智能優化算法被用于節點定位。例如，文獻[6]運用人工神經網絡對RSSI進行預處理，降低測量RSSI值誤差，進而提高測距精度，為后續定位提供準確的測距數據。文獻[7]運用獅群優化算法估計節點位置。該算法的定位精度嚴重依賴于測距精度。若測距誤差大，界定了搜索區域存在偏差，這就降低了定位誤差。同時，節點端執行智能優化算法增加了節點能耗。

為此，提出基于測距修正和擬牛頓法節點定位(ranging correction and quasi-Newton method-based localization, RCNL)算法。RCNL算法先通過多次測量收/發兩端間RSSI值，再利用正態濾波對RSSI值進行處理，剔除誤差較大的RSSI值，然后進入定位階段。定位階段細分為兩個子階段：在第一個子階段，未知節點利用RSSI測距，并利用這些測距構建搜索區域，再利用Bounding-box算法估計未知節點的位置，此次所估計的值為初始位置；在第二個子階段，運用擬牛頓法校正初始位置的偏差，提高定位精度。性能分析表明，相比于同類算法，RCNL算法降低了歸一化定位誤差，提高了定位精度。

1 RCNL算法

1.1 RCNL算法概述

RCNL算法先對RSSI值進行濾波，再依據RSSI值估計收/發兩端間距離(測距)。然后，依據這些測距數據作為Bounding-box算法的輸入，輸出為對未知節點的位置估計(初始位置)。考慮牛頓迭代法收斂速度依賴于初始值，將未知節點的初始位置作為擬牛頓法的初始值，再由擬牛頓法估計未知節點的位置。圖1給出RCNL算法的總體框架。

圖1 RCNL算法框圖

1.2 RSSI預處理

接收端記錄接收信號的RSSI值，基于RSSI測距原理，利用RSSI值估算與發送端間距離，依據Shadowing的傳播模型，可得收/發兩端間距離關于RSSI值的關系式[8]：

(1)

式中：Pr表示接收端記錄接收信號的RSSI值；Pt表示發射端傳輸功率；d0表示參考距離，通常取d0=1m；PL(d0)表示在參考距離條件下的路徑損耗功率；χ表示測距噪聲，其服從高斯分布。在理想測距環境，χ=0；d表示收/發兩端間距離，如圖2所示。

圖2 信號傳輸模型

考慮到RSSI值易受外界影響，對RSSI值進行預處理，濾除偏差大的RSSI值，進而提高測距精度。多次測量的RSSI值應呈正態分布。利用正態分布的3σ原則[9]，可知信號分布在(u-σ,u+σ)區域內的概率約為0.652 6。其中u表示均值；σ為方差。

為此，RCNL算法先引用正態濾波策略濾除不在(u-σ,u+σ)區域內的RSSI值, 獲取較準確的RSSI值。盡管引用正態濾波策略濾除了不準確的RSSI值，但其增加了算法的復雜度，將在2.5節中分析算法的復雜度。

然后，計算這組RSSI值的均值：

(2)

(3)

1.3 基于Bounding-box算法估計未知節點初始位置

Bounding-box算法也稱包圍盒算法，其是通過測量與錨節點間距離，并利用距離確定未知節點可能存在的矩形區。未知節點在多個矩形區域的重疊區域的概率最大。將重疊區域中心位置作為未知節點的估計位置。由于Bounding-box算法實施簡單，RCNL算法引用該算法估計未知節點位置。考慮到Bounding-box算法定位精度不高，只將由Bounding-box算法估計的節點位置作為擬牛頓法的初始值[10]。

圖3 基于Bounding-box算法示意圖

1.4 基于擬牛頓法的節點位置修正

1.4.1 BFGS擬牛頓法

作為一種廣泛應用的擬牛頓迭代法，BFGS算法是由Broyden, Fletcher, Goldfard和Shanno四人提出的牛頓法改進算法。BFGS算法通過迭代方式求解問題[11]。

令f表示關于未知變量的函數；X(x,y)表示未知變量。利用BFGS擬牛頓法通過式(4)求解變量X：

(4)

利用由正定矩陣B定義為Hessian矩陣的逆矩陣，即H-1=B。B的第k次迭代的值Bk為：

該橋東西兩側人行道鋪裝均存在縱向裂縫，這主要是由于人行道下板梁間未設鉸縫連接，板梁間拼縫反射到人行道鋪裝表面所致。此外，人行道鋪裝還存在局部網裂和破損。

Bk+1=Bk+ΔBk

(5)

(6)

式中：

sk=Xk+1-Xk

(7)

yk=f′(Xk+1)-f′(Xk)

(8)

1.4.2 基于誤差最小化的目標函數的構建

為了降低定位誤差，將最小化定位誤差作為目標函數：

f(x,y)=minE(x,y)

(9)

對E(x,y)展開，整理可得：

(10)

(11)

將式(11)代入式(1)，可得非約束優化問題。然后，利用BFGS算法迭代求解式(9)。求解步驟為：

步驟一，對參數進行初始化。由Bounding-box算法估計未知節點的位置，并將此位置作為X的初值；設置誤差閾值ξ和最大迭代次數Nmax；將迭代次數k賦予0。

步驟三，設置步長γk，并更新Xk+1：Xk+1=Xk+γkdk。

步驟五，依據式(5)進行迭代運算，再執行k=k+1。

步驟六，判斷k是否達到最大迭代次數Nmax，若達到，就結束迭代，否則跳轉到第二步。圖4給出了BFGS算法求解目標函數的主要流程。

圖4 基于BFGS算法求解目標函數的主流程

2 性能分析

2.1 仿真環境

利用Matlab軟件建立仿真平臺，分析RCNL算法的定位誤差。 在100 m×100 m區域內部署100～225個未知節點，10～30個錨節點。所有節點的通信半徑在25～40 m變化。具體的仿真參數如表1所示。

表1 仿真參數

選擇王宇鵬等[12]提出的基于稀疏傅里葉RSSI測距的低復雜RSSI定位算法(spare fourier-RSSI positioning, SFRP)和文獻[13]提出的基于DV-hop的改進算法(IDV-hop)，并分析它們的歸一化定位誤差性能：

(12)

2.2 定位誤差隨錨節點數的變化情況

圖5給出歸一化定位誤差隨錨節點數的變化曲線，其中節點總數為100，通信半徑為25 m，錨節點數范圍為10～30。

圖5 歸一化定位誤差隨錨節點數的變化情況

由圖可知，定位誤差隨錨節點數的增加而下降。這符合預期：網絡內錨節點數越多，未知節點從錨節點獲取的測距數據越多，這有利于提高測距精度。同時，錨節點數越多，錨節點分布密度也越高，這也提高了測距精度。測距精度越高，定位誤差就越小。

此外，相比于SFRT和IDV-Hop算法， 提出的RCNL算法降低了平均定位誤差，分別下降約2%和6%，原因在于：RCNL算法既從測距階段和定位階段進行了優化。通過加權正態濾波濾除了偏差大的RSSI值，提高了測距精度；結合Bounding-box法和擬牛頓迭代法定位，提高了定位精度。

2.3 定位誤差隨通信半徑的變化情況

圖6繪制了歸一化定位誤差隨通信半徑的變化情況，其中節點數為100，錨節點數為15，節點通信半徑范圍為15～35 m。

圖6 歸一化定位誤差隨通信半徑的變化情況

從圖6的曲線走勢可知，增加節點的通信半徑可有效地降低定位誤差，定位精度得到提升。這符合預期。通信半徑越大，節點間的通信跳數減少，測量RSSI的誤差降低，提高了測距精度。

相比于SFRT和IDV-Hop算法，RCNL算法仍保持低的定位誤差。這是因為RCNL算法先利用Bounding-box算法搜索未知節點的位置，并將此位置作為BFGS擬牛頓法的初始值進行迭代，進而對該位置進行修正，從而提高了未知節點位置的精度。

2.4 定位誤差隨節點數的變化情況

最后討論未知節點數對定位誤差的影響。圖7給出歸一化定位誤差隨節點數的變化情況，其中錨節點數占總節點比例為15%，節點數范圍為100～225，通信半徑為30 m。

圖7 歸一化定位誤差隨節點數的變化情況

從圖7曲線走勢可知，最初，節點數的增加使定位誤差迅速下降。但當節點數增加至約160時，定位誤差不再隨節點數的增加而下降。原因在于：最初，盡管節點數在增加，但節點數仍較少，錨節點數在增加，這有利于增加定位精度。但當節點數增加至一定量后，相對于未知節點數的分布密度，錨節點的分布密度下降。

2.5 算法的復雜度

用算法的運行時間表征算法的復雜度。運行時間越長，算法越復雜。在聯想小新Air14，系統為Windows10，處理器為Intel i5，內存容量為16 GB的PC機上運行定位算法。

實驗參數：通信半徑為30 m；未知節點數為150，錨節點數為30。最大的迭代次數為100。表2給出RCNL算法、SFRT和IDV-Hop算法的運行時間。從表2可知，提出的RCNL算法的運行時間高于SFRT和IDV-Hop算法。原因在于：RCNL算法執行Bounding-box算法和BFGS擬牛頓法，增加了運行時間。RCNL算法的運算時間達到45.2 s。參照文獻[14]，在室外空曠地區GPS的平均定位時間約156 s。相比于GPS系統，RCNL算法的45.2 s定位時間可接受。

表2 算法的運行時間

綜上分析可知，RCNL算法具有較高的定位精度，但其復雜度也較高，定位時間達到45.2 s。即RCNL算法以高的復雜度為代價，得到高的定位精度。高的復雜度使RCNL算法不能及時地估計節點的位置，無法適用于實時性要求高的應用場景。

3 結論

為了降低基于RSSI測距的節點定位誤差，提出基于測距修正和擬牛頓法節點定位 RCNL算法。RCNL算法通過正態濾波剔除誤差較大的RSSI值，提升測距精度。并利用Bounding-box算法和擬牛頓法估計節點位置，提高了定位精度。

然而，提出的RCNL算法的復雜度仍偏高，后期將進一步優化RCNL算法，在保證定位精度的同時，降低算法的復雜度，縮短定位時間，拓展RCNL算法的應用場景。