基于改進高斯-牛頓法的NLOS 誤差消除三維定位模型

劉晨

(江蘇省物聯網應用技術重點建設實驗室(無錫太湖學院),江蘇 無錫 214064)

0 引言

隨著無線局域網、智能終端的高速發展以及慣性傳感器的普及，人們對于位置信息的需求正在逐步增加.GPS和北斗衛星導航系統(BDS)通常用于室外定位，定位精度高，但信號在穿透固體時會受到衰減，無法實現室內的快速定位.室內三維定位過程中，無線信號在傳播時易受非視距(NLOS)阻擋、多徑傳播、多址干擾[1]等環境因素影響，導致基站到終端傳播時間的測量值與精確值之間存在誤差，這些誤差極大地降低了定位精度.

如何減小NLOS 環境下的定位誤差是室內定位算法的研究重點.到達時間(TOA)的定位和到達時間差(TDOA)的定位[2]實現簡單，并且計算精度高，是蜂窩網絡定位中最常用的技術[3].距離觀測在各種高精度測距定位中廣泛應用，其方程為非線性函數模型.除確定待定點位置坐標參數外，再附加多余參數以精化平差函數模型，其有關平差模型都是非線性的，當平差模型的非線性強度較高時，選取不同初始值及近似正交過程，可導致線性近似引起的系數矩陣擾動和截斷誤差偏大，常用的測距觀測方程非線性平差方法有高斯-牛頓法、擴展牛頓迭代法[4].文獻[5]提出了一種NLOS 環境下接收信號強度(RSS)和TDOA 聯合的信源被動定位方法，通過建立加權最小二乘模型來抑制NLOS 誤差對定位精度的影響，并利用迭代法估計NLOS 誤差與信源位置以提高定位精度；文獻[6]提出了一種基于測距信息的加權最小二乘法定位算法，根據測量距離構建加權矩陣，但該方法忽略了鏈路中隨機噪聲的影響[7]；文獻[8]基于典型的NLOS 室內環境下的信道測量，對TOA和信號接收強度的估計誤差進行建模，但該方法只適合在相對較短的距離內，超出距離則無法保證室內環境的定位精度.田昕等[9]提出了基于TOA 測距下的改進擴展卡爾曼濾波器(EKF)算法.采用預測和測量比較閾值以及誤差分析結合的方法完成NLOS 狀態的辨識，拋棄包含NLOS 誤差的測量，使用剩下的測量值實現定位[10]，這種方法在實際定位環境中會導致測量值有限，無法保證定位精度.Cheng等[11]為解決室內定位中NLOS 因素降低定位精度的問題，將錨節點分成若干組，并通過最大似然估計(MLE)獲得每組目標節點的位置信息，利用NLOS 識別算法丟棄包含NLOS 誤差的位置估計，通過建立多概率矩陣并結合位置估計來獲得目標位置.Chen等[12]提出一種非凸魯棒加權最小二乘問題來定位多個目標節點，并聯合估計目標節點位置，將魯棒加權最小二乘問題轉化成混合半定和二階錐規劃問題.文獻[13]對測量噪聲建立有色噪聲模型，濾波參數根據NLOS環境的惡劣情況動態調整，再結合卡爾曼濾波算法，進而實時調整濾波過程以獲得最優估計，但增益系數需要提前設置.文獻[14]提出了一種基于卡爾曼濾波TDOA和到達角度的混合定位算法，利用卡爾曼濾波器的估計值計算NLOS 數據的方差，通過調節卡爾曼濾波器的參數從而減小測量值的NLOS 誤差，但NLOS 誤差需服從指數分布，NLOS 誤差分布模型又受實際地理環境的影響.

針對上述問題，本文提出一種基于高斯-牛頓法的NLOS 誤差消除三維定位模型.該模型以最小二乘法為基礎得到終端的估計坐標，引入遺傳算法選取高斯-牛頓迭代的初始參數，并構建循環迭代，使之逐漸逼近真實目標位置，從而達到提高定位精度的目的.

1 基于測量距離的定位方法

1.1 NLOS 誤差概述

理想情況下，每個基站發射攜帶時間戳的信號[9]，終端在接收到信號后，通過接收和發送的時間差可計算終端與基站之間距離dt，計算公式為

式中：c為光速，取值 3 ×108m/s；tr為接收到數據的時間；ts為發送數據的時間.由于NLOS 環境下觀測到的無線信號傳播時間有誤差，會導致觀測距離值大于真實距離值，即存在一個非負的測距誤差.圖1為不同終端個數下的觀測距離值和真實距離值的誤差圖.

圖1 觀測距離值和真實距離值的誤差圖

當用戶終端(MS)即目標位置收到4 個基站(BS)的信息(三維空間下至少需要4 個)，以4 個基站的坐標為圓心，其到終端的距離為半徑可以得出4 個相交的圓，4 個圓的交點坐標即為用戶終端坐標，如圖2 所示.在NLOS 環境下，受NLOS 誤差的影響，4 個圓的相交部分不一定是終端的準確位置，而是處于4 個圓的重疊區域，如圖3 所示.

圖2 理想情況下三維定位示意圖

圖3 實際情況下三維定位示意圖

1.2 最小二乘估計初始位置

由于NLOS 下4 個以距離為半徑的圓交于一片區域，終端的位置求解可轉換成最優估計問題.假設終端的坐標為(x,y,z)，4 個基站的坐標分別(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)、(x4,y4,z4)，dt1、dt2、dt3、dt4分別為終端到4 個基站之間的測量距離，計算方程為

將式(2)中的前三項分別減去第四項，可得

式(3)的矩陣形式為

式中：

由于測量距離dt有誤差，式(2)中所列方程式的個數少于方程中所包含的未知量的個數，一般無相容解，則不存在滿足矩陣(4)的解.引入平方誤差準則函數

對式(5)求導，并令其等于0，可得最小二乘估計為

2 目標位置估計的迭代求解

2.1 高斯-牛頓法

高斯-牛頓法是一種非線性回歸模型中求回歸參數進行最小二乘的迭代方法，利用泰勒展開式近似代替非線性模型，然后進行反復迭代，多次修正回歸系數，使回歸系數逼近非線性模型的最佳系數，最后使原模型的殘差平方和達到最小[15].其一般步驟為：

1)初始值的選取，給定一個初始值x0；

2)將非線性回歸模型在x0附近泰勒級數展開，并忽略二階及二階以上偏導分量；

3)利用最小平方法估計修正因子，得到第一個迭代值；

4)對于第k次迭代，尋找一個增量Δxk，使得殘差平方和達到極小值；

5)當Δx足夠小時終止迭代，此時的xk作為優化結果輸出，否則繼續進入下一次迭代.

2.2 改進的高斯-牛頓法

高斯-牛頓法在求解局部最優解時，若參數初值選擇適當，則收斂速度快且精確度較高.當估計坐標位置遠離真實值或非線性強度大，測距方程出現相關病態問題時，高斯-牛頓法可能會出現迭代不收斂或收斂到錯誤結果[16].因此，本文基于遺傳算法[17]對終端坐標初始值進行選取，得到一個全局最優近似解，并將此近似解作為高斯-牛頓法的迭代初值進行迭代搜索，最終得到精確終端坐標.遺傳算法的具體實施過程是從初始種群出發，計算個體適應度，并通過復制、交換、突變、反復迭代等操作選出新一代種群，直到得到符合設定的最優解[18].合理的參數初值的選擇按照適應度函數進行選取，在本文定位模型中采用的適應度函數為

選擇概率為

式中，Fit(i)為個體適應值，選取適應度最高的點為初始值.具體步驟為：

1)隨機選取M個圖3 中重疊區域的終端坐標(xi,yi,zi)，i=1,2,3···,N，對所選初始值進行編碼；

2)對輸入的種群進行初始化并計算個體適應度，根據計算結果執行復制、交換、突變等操作；

3)若個體適應度值符合誤差要求，則獲取最優初始值，否則重復上述步驟直到樣本誤差滿足定位要求，停止迭代；

4)將最優初始值作為高斯-牛頓法的迭代初值進行迭代搜索，最終得到精確的終端坐標.

2.3 基于改進高斯-牛頓法的定位模型

終端到基站 B Si實際距離為di，i=1,2,3···,n，在復雜的室內環境下，將測量距離減去NLOS 誤差 εi，可以得di=dti-εi，i=1,2,3,···,n.基站與終端之間測量距離與實際距離之間的差值函數為

假設(x0,y0,z0)為遺傳算法選取出的終端最優初始值，將式(9)在初始位置(x0,y0,z0)領域內用泰勒級數展開，忽略二階偏導以上分量，得

式(10)中，將fi(x0,y0,z0) 表示為Fi，當測量距離與實際距離之間的差值fi(x,y,z)足夠小，由式(10)可得

Δx、Δy和Δz分別為x、y和z的偏差；

3 實驗與分析

為驗證改進模型的定位性能，利用具有20 個基站、20×1 000 個TOA 測量數據以及1 000 個終端真實坐標的數據集進行測試.隨機選取600 個待測終端的定位結果，給出如圖4 所示的二維平面和如圖5 所示的三維坐標圖.其中，終端的實際坐標為(,,)，i=1,2,···,N，改進的定位模型的定位坐標為(xi,yi,zi)，i=1,2,···,N.由圖4 可知，本文的定位模型在二維平面上幾乎都可以準確定位.圖5 表明本文模型在z方向上存在誤差，但誤差基本都在0.8 m 以內，NLOS誤差消除效果顯著.

圖4 終端二維平面坐標圖

圖5 終端三維坐標圖

為了進一步衡量定位性能，列出600 個待測終端在各個方向上的平均定位誤差、最大定位誤差、最小定位誤差以及定位誤差小于1 m 的概率，相應誤差結果如表1 所示.

由表1 可知，在600 個測試點中，本文定位模型在x方向平均誤差為0.168 m，在y方向平均誤差為0.171 m，在z方向平均誤差為0.719 m.定位效果在x、y、z方向上最小定位誤差分別為0.006 m、0.002 m、0.014 m，效果最差的情況下定位誤差分別為0.806 m、0.974 m、1.190 m，最大誤差均不超過1.2 m.從實驗結果可以看出，室內定位時終端z方向上的定位誤差較大，但其誤差小于1 m 的概率為89.2%.

表2 展示了1 000 個待測終端在各個方向上的平均定位誤差、最大定位誤差、最小定位誤差以及定位誤差小于 1 m 的概率.

表2 1 000 個測試點定位誤差統計結果

由表2 可知，在1 000 個測試點中本文定位模型在x方向平均誤差為0.175 m，在y方向平均誤差為0.179 m，在z方向平均誤差為0.721 m.定位效果在x、y、z方向上最小定位誤差分別為0.001 m、0.001 m、0.014 m，效果最差情況下的定位誤差分別為1.013 m、1.198 m、1.220 m，最大誤差均約在1.2 m.定義三維空間的平均誤差為

由式(15)可求得，1 000 個測試點在三維空間的平均定位誤差為0.642 m，誤差小于1 m 的概率為88.2%，誤差小于1.2 m 的概率能達到96.5%，平均誤差相比于文獻[19]約小0.65 m.通過測試數據可知，室內三維定位較大誤差出現概率相對較低，符合本文定位模型預期.此外，幾種定位模型的誤差累積分布函數曲線(CDF)如圖6 所示，橫坐標為定位精度，縱坐標為定位模型達到某一精度的概率.

圖6 定位誤差累積分布函數曲線圖

圖6 中基于最小二乘法的基本定位模型的定位誤差小于1 m 的概率約為24%，文獻[19]定位模型的定位誤差小于1 m 的概率約為68%，本文定位模型的定位誤差小于1 m 的概率約為88%.可以看出，本文定位模型比基于最小二乘法的基本定位模型和文獻[19]的模型具有更好的定位精度，可以滿足大部分室內定位的需求.

4 結束語

本文分析了NLOS 環境下基于測量距離定位方法的誤差，針對無線傳感網絡進行室內定位過程中由于信號NLOS 傳播而導致精度低的問題，提出一種基于改進高斯-牛頓法的NLOS 誤差消除室內三維定位模型.利用最小二乘得到被測終端的初始位置，并通過遺傳算法對初始位置進行選取，得到最優初始值后再用高斯-牛頓法進行迭代以細化具體位置.實驗結果表明，本文所提模型可有效降低 NLOS 誤差的影響，定位精度顯著提高.