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

劉晨

(江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點(diǎn)建設(shè)實(shí)驗(yàn)室(無(wú)錫太湖學(xué)院),江蘇 無(wú)錫 214064)

0 引言

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

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

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

1 基于測(cè)量距離的定位方法

1.1 NLOS 誤差概述

理想情況下，每個(gè)基站發(fā)射攜帶時(shí)間戳的信號(hào)[9]，終端在接收到信號(hào)后，通過接收和發(fā)送的時(shí)間差可計(jì)算終端與基站之間距離dt，計(jì)算公式為

式中：c為光速，取值 3 ×108m/s；tr為接收到數(shù)據(jù)的時(shí)間；ts為發(fā)送數(shù)據(jù)的時(shí)間.由于NLOS 環(huán)境下觀測(cè)到的無(wú)線信號(hào)傳播時(shí)間有誤差，會(huì)導(dǎo)致觀測(cè)距離值大于真實(shí)距離值，即存在一個(gè)非負(fù)的測(cè)距誤差.圖1為不同終端個(gè)數(shù)下的觀測(cè)距離值和真實(shí)距離值的誤差圖.

圖1 觀測(cè)距離值和真實(shí)距離值的誤差圖

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

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

圖3 實(shí)際情況下三維定位示意圖

1.2 最小二乘估計(jì)初始位置

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

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

式(3)的矩陣形式為

式中：

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

對(duì)式(5)求導(dǎo)，并令其等于0，可得最小二乘估計(jì)為

2 目標(biāo)位置估計(jì)的迭代求解

2.1 高斯-牛頓法

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

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

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

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

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

5)當(dāng)Δx足夠小時(shí)終止迭代，此時(shí)的xk作為優(yōu)化結(jié)果輸出，否則繼續(xù)進(jìn)入下一次迭代.

2.2 改進(jìn)的高斯-牛頓法

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

選擇概率為

式中，F(xiàn)it(i)為個(gè)體適應(yīng)值，選取適應(yīng)度最高的點(diǎn)為初始值.具體步驟為：

1)隨機(jī)選取M個(gè)圖3 中重疊區(qū)域的終端坐標(biāo)(xi,yi,zi)，i=1,2,3···,N，對(duì)所選初始值進(jìn)行編碼；

2)對(duì)輸入的種群進(jìn)行初始化并計(jì)算個(gè)體適應(yīng)度，根據(jù)計(jì)算結(jié)果執(zhí)行復(fù)制、交換、突變等操作；

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

4)將最優(yōu)初始值作為高斯-牛頓法的迭代初值進(jìn)行迭代搜索，最終得到精確的終端坐標(biāo).

2.3 基于改進(jìn)高斯-牛頓法的定位模型

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

假設(shè)(x0,y0,z0)為遺傳算法選取出的終端最優(yōu)初始值，將式(9)在初始位置(x0,y0,z0)領(lǐng)域內(nèi)用泰勒級(jí)數(shù)展開，忽略二階偏導(dǎo)以上分量，得

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

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

3 實(shí)驗(yàn)與分析

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

圖4 終端二維平面坐標(biāo)圖

圖5 終端三維坐標(biāo)圖

為了進(jìn)一步衡量定位性能，列出600 個(gè)待測(cè)終端在各個(gè)方向上的平均定位誤差、最大定位誤差、最小定位誤差以及定位誤差小于1 m 的概率，相應(yīng)誤差結(jié)果如表1 所示.

由表1 可知，在600 個(gè)測(cè)試點(diǎn)中，本文定位模型在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.從實(shí)驗(yàn)結(jié)果可以看出，室內(nèi)定位時(shí)終端z方向上的定位誤差較大，但其誤差小于1 m 的概率為89.2%.

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

表2 1 000 個(gè)測(cè)試點(diǎn)定位誤差統(tǒng)計(jì)結(jié)果

由表2 可知，在1 000 個(gè)測(cè)試點(diǎn)中本文定位模型在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 個(gè)測(cè)試點(diǎn)在三維空間的平均定位誤差為0.642 m，誤差小于1 m 的概率為88.2%，誤差小于1.2 m 的概率能達(dá)到96.5%，平均誤差相比于文獻(xiàn)[19]約小0.65 m.通過測(cè)試數(shù)據(jù)可知，室內(nèi)三維定位較大誤差出現(xiàn)概率相對(duì)較低，符合本文定位模型預(yù)期.此外，幾種定位模型的誤差累積分布函數(shù)曲線(CDF)如圖6 所示，橫坐標(biāo)為定位精度，縱坐標(biāo)為定位模型達(dá)到某一精度的概率.

圖6 定位誤差累積分布函數(shù)曲線圖

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

4 結(jié)束語(yǔ)

本文分析了NLOS 環(huán)境下基于測(cè)量距離定位方法的誤差，針對(duì)無(wú)線傳感網(wǎng)絡(luò)進(jìn)行室內(nèi)定位過程中由于信號(hào)NLOS 傳播而導(dǎo)致精度低的問題，提出一種基于改進(jìn)高斯-牛頓法的NLOS 誤差消除室內(nèi)三維定位模型.利用最小二乘得到被測(cè)終端的初始位置，并通過遺傳算法對(duì)初始位置進(jìn)行選取，得到最優(yōu)初始值后再用高斯-牛頓法進(jìn)行迭代以細(xì)化具體位置.實(shí)驗(yàn)結(jié)果表明，本文所提模型可有效降低 NLOS 誤差的影響，定位精度顯著提高.