基于動態T檢驗的修正最小二乘BFGS定位算法

孟　娟　洪　利　李亞南　韓智明

(防災科技學院防災儀器系　河北 三河 065201)

?

基于動態T檢驗的修正最小二乘BFGS定位算法

孟娟洪利李亞南韓智明

(防災科技學院防災儀器系河北 三河 065201)

摘要針對傳統基于接收信號強度指示RSSI(Received Signal Strength Indicator)的最小二乘定位算法精度有限的問題，從降低信號噪聲影響出發，提出一種基于動態T檢驗的修正最小二乘-BFGS定位算法。在測距階段，將T檢驗法動態應用于RSSI值篩選，以消除較大測量誤差影響，提高測距精度；定位階段，先基于平均測算距離對傳統的最小二乘法進行修正，提升初步定位精度0.3～2米；在此基礎上，以信號強度誤差最小為目標優化函數，基于BFGS算法對修正最小二乘法計算的初值進行迭代求精，以進一步提高定位精度。仿真實驗表明，該算法有效提升了定位精度，在100 m×100 m范圍內可比傳統最小二乘定位誤差降低4～11米。

關鍵詞定位算法接收信號強度指示T檢驗最小二乘BFGS

0引言

隨著無線傳感器網絡在農業、智能家居、物流、采礦等多行業的應用，傳感器節點的位置信息變得日益重要，在自動組網、網絡監測、網絡負載均衡等應用中，都需要用到節點的位置信息，因此傳感器的節點定位算法備受關注。傳感器的定位算法分為基于測距和距離無關的兩大類，其中前者定位精度較高，是目前研究熱點?；跍y距的定位算法需要先測算節點之間的距離或角度，再利用最小二乘法、最大似然估計法、三邊測量法等計算未知節點坐標。常采用的測距技術有基于TOA(電波傳播時間)、TDOA(電波傳播時間差)、AOA(信道到達角度)、RSSI(接收信號強度)等[1]，其中基于RSSI定位算法具有易實現、無需增加額外硬件、成本低等優點，被廣泛應用于傳感器網絡的節點定位中[2-4]。

為提高定位精度，學術界進行了深入研究，提出了多種基于RSSI的測距/定位算法。在RSSI測距方面，針對由于多徑、反射、繞射、散射等因素帶來RSSI值波動，導致測距不準的問題，提出了利用均值、高斯、卡爾曼、粒子濾波等濾波器來優化RSSI值的方法[5-7]；但當突發干擾導致某些測量值發生強烈跳變時，僅采用濾波器無法完全消除這些粗大誤差帶來的影響。在定位算法方面，為提高定位精度，牛頓法[8]、最速下降法[9]、擬牛頓法[10-12]等最優化算法被用于未知節點位置的求精迭代，其中文獻[9]利用最速下降法對最大似然估計法獲得的初始定位值進行迭代，文獻[11]將最小二乘法計算出來的初值，用擬牛頓法對未知節點坐標進行迭代。但文獻[9]與文獻[11]中均以節點的位置誤差最小為目標優化函數，其參考的距離在估算時引入了噪聲誤差，因此影響了定位精度。

針對以上問題，本文提出一種基于動態T檢驗的修正最小二乘-BFGS定位算法：在測距階段，將傳統的T檢驗方法動態運用于測量數據預處理，消除誤差較大的跳變RSSI值，將剩余較穩定的RSSI值作為有效值，并利用卡爾曼濾波器進行濾波以提高測距精度；在定位階段，對傳統的最小二乘法進行修正，提高初次定位精度；在此基礎上，以信號強度誤差為目標優化函數，利用最優化算法中的BFGS算法進行二次定位，求取未知位置最優解。

1測距/定位原理

基于RSSI的測距/定位算法原理是根據無線信號傳播模型，將未知節點(接收端)接收到的參考節點(發射端)的RSSI值轉化為距離，再根據參考節點位置計算出未知節點坐標。因此，基于RSSI的測距/定位算法分為兩步：RSSI測距和基于多參考節點的定位。

1.1RSSI測距

基于RSSI的測距原理是利用無線信號的傳播模型，根據接收信號強度得到接收機和發射機距離的估計值。常用無線信號傳播模型有自由空間傳播模型、M-K模型、Shadowing模型等，在RSSI測距定位算法中常用的為Shadowing模型[13]：

(1)

式中，RSSI(di)為距離發射端di時接收端接收到的信號強度；d0為參考距離；γ為路徑損耗指數，由傳輸環境決定，通常通過測量獲取；Xδ是均值為0，方差為δ的正態分布隨機噪聲。

在實際測量中，一般取d0=1m，并對RSSI值進行處理(如濾波)，使噪聲Xδ對測量結果的影響降低到最小甚至忽略不計，則式(1)簡化為：

Ri=R0-10γlg(di)

(2)

R0和γ決定了RSSI值與信號傳播距離的關系，根據式(2)可估算未知節點與參考節點間的距離：

(3)

1.2基于最小二乘法的節點定位

若未知節點獲得3個或3個以上參考節點(AP)的信息，則可采用最小二乘法、最大似然估計法、三邊測量法等估算其位置。其中最小二乘法是一種經常采用的方法，其原理如下：假設在待測區域內有m個參考AP，第i個參考AP的位置分別為(xi,yi)，i≤m，未知節點p的位置為(x,y)，據式(3)得到未知節點p到第i個參考AP的距離為di，則可得到下列定位方程組：

(4)

2基于動態T檢驗的修正最小二乘-BFGS定位算法

2.1算法原理

圖1　基于動態T檢驗的修正最小二乘-BFGS定位算法流程圖

由式(2)和式(4)所知，對于確定的無線信號傳播模型，RSSI無線定位算法的精確性依賴于接收信號強度的精確度以及由其計算得到的估算距離。但在實際定位過程中，由于受無線信號傳輸中多徑、散射等因素帶來的噪聲影響，使得式(2)所示的功率關系存在一定誤差，從而降低RSSI定位精度。一方面，噪聲Xδ使式(2)所示的功率關系存在較大誤差，惡化了式(3)所示的距離關系的準確性；另一方面，在最小二乘法定位過程中，通過減去一個參考點方程消去方程組中的二次方變量，若這個被選擇的參考點誤差較大，則會嚴重增加整個線性方程組的誤差，降低定位精度。本文從這兩個方面對傳統的RSSI定位算法進行改進，提出了一種基于動態T檢驗的修正最小二乘-BFGS定位算法，從兩個方面減少噪聲的影響，以有效提高定位精度：一方面，通過對RSSI測量數據進行動態T檢驗和濾波，剔除部分高噪聲數據，提高測距精度；另一方面，在最小二乘法定位過程中，通過減去定位方程的平均值，降低高信噪定位方程對定位精度的影響。

基于以上思考，本文提出的基于動態T檢驗的修正最小二乘-BFGS定位算法流程如圖1所示。算法首先對T檢驗進行動態應用，以對測量數據進行預處理，剔除較大誤差數據，同時進行卡爾曼濾波，使RSSI強度測量值更加穩定可靠；其次，對數據進行基于最小二乘法的初定位，通過減去所有參考方程的平均值減少定位誤差；最后，將目標節點的定位問題轉化為以信號強度誤差最小為優化函數的非線性無約束優化問題進行求解。

2.2RSSI數據預處理-動態T檢驗

由于客觀條件影響或突發干擾，某些RSSI值偏離真實值，需對這樣的數據進行篩選。誤差剔除有多種方法，如Grubbs檢驗、T檢驗、萊依特檢驗等。實際測量時，每個測量點測量次數約50次，根據文獻[14]，此時T檢驗是較優的一種。但傳統的T檢驗法一般用于事后的靜態檢驗處理，而測量數據是動態采集的。為實時對測量數據進行處理，可考慮將傳統的統計檢驗方法進行動態化應用，如文獻[15]將Grubbs檢驗進行了動態應用，采用了一種類似滑動窗口思想，通過動態保持50個測量數據為樣本進行檢驗，從而提高監測數據質量。根據文獻[14]，T檢驗在樣本數小于30時應用效果更優，因此本文借鑒文獻[15]中的算法思想，同時改進該算法中不對最前面數據進行檢驗而導致剔除可疑值不徹底的缺陷：首先，獲取前30個測量數據，對這些數據進行傳統的T檢驗；其次，將T檢驗做動態化應用，獲取當前最新數據，利用T檢驗判斷該值是否為異常值。若判斷為正常則保留該值，否則剔除第一次出現的異常值，而保留連續出現的第二個異常值目的是反映測量過程中因移動或其他原因產生的可能變化。

具體的算法流程如下：

算法1動態T檢驗算法

Step1獲取前30個測量數據。

Step2計算當前n個數據的平均值，查找測量值中與平均值誤差最大的測量值Xd，設其為可疑值。

Step5置異常值連續出現標志flag為false。

Step6判斷數據是否獲取完畢，若完畢則結束算法；否則將窗口移動一位，轉Step7。

Step7讀取最新測量數據Xj(31≤j≤50)。

2.3RSSI數據濾波

由于隨機噪聲影響，RSSI測量值仍將在一定范圍內上下波動，此時需要引入濾波算法使RSSI測量值更穩定。本文采用卡爾曼濾波法對RSSI值進行優化[5,6]，算法流程如下：

算法2基于卡爾曼濾波的RSSI數據優化

Step1設經過動態T檢驗后被保留的測量值為Ζ={Ζ1,Ζ2,…,ΖN}。

Step2初始條件：設過程噪聲協方差Q=1e-6，測量噪聲協方差F=0.01，初值R(1|1)=R(1)，協方差P(1|1)=R(1)。

Step3fromt=2tot=N，計算：

預估信號強度R(t|t-1)=R(t-1|t-1)

預估計協方差矩陣P(t|t-1)=P(t-1|t-1)+Q

卡爾曼增益Kg(t)=P(t|t-1)/(P(t|t-1)+F)

更新信號強度R(t|t)=R(t|t-1)+Kg(t)(Z(t)-R(t|t-1))

更新協防差矩陣P(t|t)=(1-Kg(t))P(t|t-1)。

Step4得到最優估計R(N|N)。

卡爾曼濾波后，根據式(3)估算未知節點與參考AP間的距離，并基于此估算未知節點的位置。

2.4修正的最小二乘法初定位

傳統最小二乘法定位時，若被選擇的參考AP誤差較大，則最終定位結果誤差會變得更大。為提高初始定位精度，對傳統最小二乘法進行修正：將方程組式(4)中所有方程左右兩邊相加并取均值，得到：

(5)

將式(4)中所有方程都減去式(5)則得到新方程組：

(6)

2.5修正最小二乘-BFGS定位算法

最小二乘法在定位過程中可能存在非奇異矩陣，導致估算位置誤差較大。為提高精度，常利用最優化方法進行未知節點位置的迭代求精[8-12]。BFGS是經典擬牛頓算法，收斂快、計算存儲量較小，適合解決中小規模無約束最優化問題。因此,本文選用BFGS算法進行二次定位。

文獻[9,11]中，優化函數中的di在計算時引入了噪聲影響，因此在定位時會疊加距離測算帶來的誤差。在修正的最小二乘法求取未知節點初始坐標后，根據式(2)，本文將目標節點定位問題轉化為以信號強度誤差最小為優化函數的非線性無約束優化問題，即求解式(7)。相比文獻[9,11]，本文目標優化函數直接以信號強度為參考，不會疊加距離測算帶來的誤差，因此可減小定位誤差。

(7)

式中(x,y)為未知點的待估算坐標，Ri為未知節點收到的第i個參考AP的信號強度，R0是距離發射端1m時的接收信號強度，(xi,yi)為第i個參考AP的位置。

算法流程如下：

算法3修正最小二乘-BFGS定位算法

Step1利用修正最小二乘法求取未知坐標的初始估計值，將該值作為BFGS迭代求解的初值x0，設誤差精度ε≤e-6。

Step2設H0=In(n=2)，計算式(7)中f(x,y)在x0處的梯度g0=▽f(x0)。若g0=0，則算法停止，極小值點為x0；否則轉Step3。

Step3令k=0，確定搜索方向為dk=-Hkgk。

Step5計算‖f(xk+1)‖，若‖f(xk+1)‖≤ε，則算法停止，極小值點為xk+1，否則轉Step6。

Step6若k+1=n，則令x0=xn，轉Step3，否則轉Step7。

3仿真分析

為驗證本文算法有效性，利用Matlab進行仿真實驗與分析，并與傳統最小二乘法和文獻[11]的最小二乘-擬牛頓定位算法進行對比。

3.1仿真參數設置與相關定義

將傳統的最小二乘定位算法記為LS，文獻[11]中最小二乘-擬牛頓算法記為LN，本文修正最小二乘算法記為MLS，基于動態T檢驗的修正最小二乘-BFGS算法記為SMB，不加檢驗修正最小二乘-BFGS算法記為MB。

最大仿真網絡環境設置為100m×100m，在仿真區域隨機布置若干個參考AP和k個未知節點，假設無線信號的傳播路徑損耗因子γ=2，R0=-24.5db，隨機噪聲滿足N(0,δ)(2≤δ≤10)的正態分布。為驗證算法穩定性，每種算法均進行100次仿真，以平均定位誤差e來分析算法性能，其定義如下：

(8)

3.2結果分析

圖2仿真了在不同通信范圍內，布置5個參考AP，當噪聲滿足N(0,10)時的不同算法性能對比。隨著通信范圍增大，定位誤差隨之增大。在30m×30m～100m×100m的通信范圍內，相比傳統最小二乘法，本文修正最小二乘法可減小初始誤差約0.3～2m，原因在于修正最小二乘法以平均距離為參考，避免選用誤差較大的距離；二次定位后，誤差可減少4～11m，與文獻[11]的最小二乘-擬牛頓算法相比，平均定位誤差要小約1～4.5m。

圖2　不同通信范圍不同算法的平均定位誤差

圖3仿真了在100m×100m范圍內，布置不同數目的參考AP時的算法性能對比。隨著參考AP數的增加，定位誤差先快速減小，但當參考AP達到一定數量時，定位精度提高較慢。如圖3所示，當參考AP節點數量為8以上時，定位精度提升不明顯。這是因為參考AP節點增加時，信號強度誤差也隨之累加，故最終定位精度不會一直提升。本文算法比傳統最小二乘法的誤差約降低4～11m，比文獻[11]定位誤差平均降低1～4.5m。

圖3　不同AP個數不同算法的平均定位誤差

圖4仿真了在100m×100m范圍內，布置5個參考AP時，在不同的噪聲方差δ條件下的不同算法性能。從圖中看出，隨著δ增加，定位誤差增加。但本文算法比傳統的最小二乘法的定位誤差約小4～11m，比文獻[11]平均定位誤差降低約1～4.5m。

圖4　不同噪聲方差不同算法的平均定位誤差

圖5仿真了在100m×100m范圍內，布置5個參考AP時，在不同的噪聲方差條件下，是否采用動態T檢驗的算法性能。從圖中看出，采用檢驗的定位算法比不采用檢驗的定位算法誤差要小，噪聲方差越大，加檢驗后定位誤差越低，性能提升0.1%～0.45%。

圖5　是否采用動態T檢驗的算法性能對比

4結語

基于RSSI定位算法中信號噪聲的影響，提出一種基于動態T檢驗的修正最小二乘-BFGS定位算法。在定位之前對測量RSSI值進行了預處理，利用動態T檢驗消除了異常值的影響，并利用卡爾曼濾波器得到最優RSSI值，從而提高測距精度。相比于未采用動態T檢驗的定位算法，提高約0.1～0.45m的定位精度。定位時，先利用平均測算距離對傳統的最小二乘法進行了修正，初步提升定位精度0.3～2m；再以信號強度誤差為目標優化函數，結合最優化方法中的BFGS算法，大大提高定位精度。仿真實驗證明，本文算法相比傳統的最小二乘法誤差降低約4～11m，比文獻[11]誤差降低約1～4.5m，表明了算法在提高定位精度的有效性和可行性，同時算法無需增加額外的硬件開銷，具有較強的實際應用價值。需要說明的是，由于采用了檢驗和濾波的方法對RSSI測量數據進行處理，因此本文算法需要較多的RSSI測量數據進行處理，因此本文算法適用于節點相對靜止或低速運動狀態下的定位。課題組下一步將對如何提高節點高速運動下的定位精度進行研究。

參考文獻

[1]VianiF,RoccaP,OliveriG.Localization,tracking,andimagingoftargetsinwirelesssensornetworks:Aninvitedreview[J].RadioScience,2011,46(5).

[2] 劉雪蘭,王宜懷,陸全華,等.無線傳感器網絡RSSI定位算法改進[J].計算機應用與軟件,2013,30(11):87-89,141.

[3]XiuyanZhu,YuanFeng.RSSI-basedAlgorithmforIndoorLocalization[J].CommunicationsandNetwork,2013,5:37-42.

[4] 胡志坤,蔣英明,王文祥,等.基于ZigBee的井下人員精確定位方案及實現[J].計算機應用與軟件,2013,30(5):159-162,170.

[5]AnindyaSPaul,EricAWan.RSSI-BasedIndoorLocalizationandTrackingUsingSigma-PointKalmanSmoothers[J].IEEEjournalofselectedtopicsinsignalprocessing,2009,3(5):860-873.

[6]RungchingChen,YuHsiangLin.ApplyKalmanfiltertoRFIDReceivedSignalStrengthprocessingforindoorlocation[C]//IEEE2012 4thInternationalConferenceonAwarenessScienceandTechnology,21-24Aug,Seoul,Korea,2012:73-77.

[7] 劉興川,張盛,林孝康.基于數據融合的WLAN/MARG組合定位系統[J].系統工程與電子技術,2012,34(11):2361-2365.

[8] 姚金杰,韓焱.基于粒子群和牛頓迭代法的目標定位方法研究[J].計算機應用研究,2010,27(5):1710-1713.

[9] 石琴琴,霍宏,方濤,等.使用最速下降算法提高極大似然估計算法的節點定位精度[J].計算機應用研究,2008,25(7):2038-2040.

[10]FangZhao,HaiyongLuo,HaoGeng,etal.AnRSSIGradient-basedAPLocalizationAlgorithm[J].ChinaCommunications,2014,11(2):100-108.

[11] 程秀芝,朱達榮,張申,等.基于RSSI差分校正的最小二乘-擬牛頓定位算法[J].傳感技術學報,2014,27(1):123-127.

[12]BenjianHao,ZanLi.BFGSquasi-NewtonlocationalgorithmusingTDOAsandGROAs[J].SystemsEngineeringandElectronics,2013,24(3):341-348.

[13]VianiF,LizziL,RoccaP,etal.ObjecttrackingthroughRSSIMeasurementinwirelesssensornetworks[J].ElectronicsLetters,2008,44(10):653-654.

[14] 王文周.未知σ,t檢驗法剔除異常值最好[J].四川工業學院學報,2000,19(3):84-86.

[15] 汪宏峰,肖軍,何俊,等.車載輻射在線監測系統數據動 態檢驗處理方法研究[J].核電子學與探測技術,2013,33(7):881-885.

MODIFIED LEAST SQUARES-BFGS POSITIONING ALGORITHM BASEDONDYNAMICT-TEST

Meng JuanHong LiLi Ya’nanHan Zhiming

(Department of Disaster Prevention Instrument,Institute of Disaster Prevention,Sanhe 065201,Hebei,China)

AbstractConventional least-squares (LS) positioning algorithm based on received signal strength indicator (RSSI) has limitation in positioning precision. In view of this, from the perspective of reducing the impact of signal noise, we presented a dynamic T-test-based modified least squares-BFGS positioning algorithm. In stage of RSSI ranging, in order to eliminate the influence of larger measurement errors and to improve measuring precision, we applied the T-test to RSSI values screening dynamically. In stage of positioning, we first modified the conventional LS algorithm based on average estimation distance to enhance the initial positioning accuracy by 0.3～2 meters. On this basis, we took the minimisation of signal strength error as the function of target optimisation, and made iterative improvement on the initial value calculated by modified LS algorithm based on BFGS algorithm to further improve positioning accuracy. Simulation experimental results showed that the algorithm effectively improved the positioning accuracy, compared with conventional LS positioning algorithm, its error decreased by 4～11meter in a range of 100 m×100 m.

KeywordsPositioning algorithmReceived signal strength indicator (RSSI)T-testLeast-squares (LS)BFGS

收稿日期：2015-05-06。中國地震局星火科技計劃項目(XH140 72)。孟娟，講師，主研領域：無線傳感器網絡，嵌入式。洪利，教授。李亞南，碩士。韓智明，碩士。

中圖分類號TP301.6

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.031