基于幾何約束及迭代的NLOS環(huán)境定位算法

鄧 平 ，謝 雪

（西南交通大學信息科學與技術(shù)學院，四川 成都 610097）

隨著5G時代的到來，無線定位技術(shù)將成為物聯(lián)網(wǎng)應(yīng)用和推廣的重要支撐技術(shù).現(xiàn)有無線定位技術(shù)中主要包括基于到達時間（time of arrival，TOA）、到達時間差（time difference of arrival，TDOA）、接收信號強度（received signal strength indication，RSSI）、電波到達角度（angle of arrival，AOA）以及 TOA、AOA等多種特征參數(shù)的混合定位技術(shù)[1]等.在室內(nèi)、室外等多種5G網(wǎng)絡(luò)場景的無線定位中，由于移動臺（mobile station，MS）能接收到有效信號的基站（base station，BS）數(shù)目通常有限，因此在算法設(shè)計時通常需要限制可用于定位的BS數(shù)量，并考慮用較少數(shù)量的BS來實現(xiàn)移動臺的位置估計.此外，無論在室內(nèi)還是室外場景，電波的非視距（non-line-ofsight，NLOS）傳播普遍存在，造成 TOA、AOA等電波特征測量值會產(chǎn)生較大偏差，從而大大降低算法的定位精度.

目前，抗NLOS誤差定位算法可分為兩類：第一類是統(tǒng)計處理法，該方法基于NLOS誤差或者信道環(huán)境的統(tǒng)計特性進行處理[2-4].例如文獻[2-3]使用NLOS 誤差和視距（line-of-sight，LOS）誤差先驗信息，實現(xiàn)LOS重建；文獻[4]利用信道環(huán)境的先驗信息估算NLOS誤差大小，實現(xiàn)TDOA測量矩陣和協(xié)方差矩陣的重構(gòu).但是，由于NLOS誤差總是隨著環(huán)境的改變而動態(tài)變化，而實際移動通信環(huán)境復(fù)雜多變，是很難準確捕捉到所在環(huán)境NLOS誤差的統(tǒng)計規(guī)律，致使這一類算法很難得到有效的工程應(yīng)用.

第二類算法簡稱幾何法[5-13]，以BS和MS之間的位置幾何關(guān)系為基礎(chǔ)建立約束條件，把求解MS估計位置轉(zhuǎn)換為求解一個最優(yōu)化問題.這類算法的優(yōu)點在于可以適應(yīng)復(fù)雜的實際變化環(huán)境，有效地利用各種測量信息，但是傳統(tǒng)的最優(yōu)化定位算法往往需要一個比較準確的初始位置估計值才能得到較好的定位精度[6-9].文獻[10-12]雖然無需初始位置估計，但該類算法并沒有有效利用NLOS傳播路徑下與被測目標位置密切相關(guān)的散射信息.

為此，本文提出一種基于幾何約束及迭代的NLOS環(huán)境定位算法，考慮在雙BS定位的場景下，利用NLOS環(huán)境中散射體與BS及MS之間的幾何位置關(guān)系，并基于圓盤散射模型將最大散射半徑作為約束條件構(gòu)建約束范圍.有別于文獻[12]的二維網(wǎng)格搜索算法（grid search algorithm，GSA），本文基于一維線性迭代搜索并使用最小二乘估計得到較準確的MS初始估計位置；為了進一步提高定位精度，本文利用閾值處理以及加權(quán)平均獲得MS的最終估計位置.

1 基于最優(yōu)化理論的MS定位

在不失一般性的前提下，假設(shè)兩基站（BS1、BS2）信號在傳播過程中都經(jīng)歷了單次散射到達移動臺，MS位于△OAB范圍內(nèi)，如圖1所示.圖中：Rc為小區(qū)半徑；BS1和BS2分別為主基站和輔助基站；φ 和θ分別為BS1測量的和真實的AOA值；ri為MS到 BSi的真實 TOA 距離，i=1，2；Si為BSi到 MS 的信號散射體.

圖1 基站與移動臺位置關(guān)系Fig.1 Location relationship between BS and MS

設(shè)MS位置坐標為(x,y)，B Si坐標為(xi,yi),則有

在單次散射模型下，散射點Si坐標為(xSi,ySi)，MS 到B Si的測量距離為Ri，ηi為其測量誤差，μ 為BS1測量的AOA誤差，由此建立測量等式如式（3）和式（4）所示.

由于在NLOS環(huán)境中信號無論被折射或者反射都會使得測量值大于真實值，因此存在NLOS因子αj(j=1,2,3)滿足：

類似于文獻[1]的混合線性定位（hybrid line of position，HLOP）算法，聯(lián)合式（1）、（2）、（5）、（6）可得有關(guān)αj的方程組：

式中：

那么 MS 位置估計值可通過 LS（least squares）求解，即

由式（9）可見，MS定位精度關(guān)鍵取決于是否能獲得準確的αj取值，而傳統(tǒng)最優(yōu)化處理方法通常根據(jù)MS和BS之間幾何位置關(guān)系將該問題轉(zhuǎn)化為非線性約束最優(yōu)化問題進行求解[6].

如上所述，進一步建立非線性約束最優(yōu)化模型.首先由圖1中BS和MS的三角關(guān)系建立不等式約束，并聯(lián)立式（5）表示為矩陣形式，如式（10）.

接著，基于文獻[6]參量取值約束思想，以及蜂窩半徑Rc約束，可以獲得關(guān)于α1、α2的上、下界關(guān)系，如式（11）.

考慮MS真實位置始終位于△OAB可行域內(nèi)，可得B S1的兩條AOA位置線范圍，如式（12）.

式（11）和式（12）中：αj,upp、αj,low分別為αj的上、下界.

為了減小測量誤差的影響，這里以測量值與目標值的殘差平方和為非線性目標代價函數(shù)，如式（13）.

此外，MS位置坐標存在對應(yīng)的幾何位置關(guān)系，如式（14）.

因此，將式（1）、（2）、（14）代入式（13）可得新的代價函數(shù)，如式（15）.

綜上，αj求解問題演化為式（16）非線性優(yōu)化問題：

求解式（16）常用的方法是內(nèi)點法，其思想是利用約束條件和目標函數(shù)來構(gòu)造罰函數(shù)，將不等式優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，然后給定初始值線性逼近目標最優(yōu)解[14].不失一般性，仿真中變量αj初始取值為αj=(αj,low+αj,upp)/2，隨后使用MATLAB優(yōu)化工具箱對優(yōu)化問題進行求解.在獲得αj的最優(yōu)解后，將其代入式（9）即可得到MS的估計位置.

2 基于散射信息約束及迭代的定位算法

上述定位過程的關(guān)鍵是如何求解準確有效的αj值.由于傳統(tǒng)最優(yōu)化求解方法很難確定一個有效的初始變量值使得算法盡可能收斂，且很有可能出現(xiàn)局部最優(yōu)的情況，本文提出充分利用NLOS環(huán)境中的散射信息縮小MS可行域，并以線性迭代方式在αj可行域內(nèi)搜索滿足約束條件的αj值.

2.1 散射半徑幾何約束條件

為了減小目標搜索范圍，本文考慮在單次圓盤散射模型[15]下引入最大散射半徑作為約束條件，其中BS和MS與散射體（圖中用△表示）的幾何位置關(guān)系如圖2所示.

圖2 基站、移動臺和散射體的幾何關(guān)系Fig.2 Geometric relationship of BS，MS and scatterer

假設(shè)最大散射半徑為Rs，由圖2三角形三邊關(guān)系可得BS到MS真實距離r大于最大散射半徑，即

那么，將式（5）中測量值與真實值對應(yīng)關(guān)系代入式（17），可得有關(guān)α1、α2的約束不等式如式（18）.

如果忽略AOA測量誤差，從圖2幾何模型可知α3的最大值為

類似地，把式（5）、（6）代入式（19）可以獲取有關(guān)α1、α3的約束不等式為

最終，在散射半徑約束下，有關(guān)NLOS因子αj新的約束條件為

2.2 基于迭代的MS位置估計

對于以上非線性約束模型，可以基于內(nèi)點法求解，此外還可以使用文獻[13]的網(wǎng)格搜索算法，通過二維網(wǎng)格搜索αj并結(jié)合最小二乘的方式計算得到MS可能位置點，再對其算術(shù)平均可得到MS估計值.但是網(wǎng)格劃分密度極大地影響網(wǎng)格搜索計算量以及定位性能.為此，本文通過一種線性迭代法以αj為權(quán)值進行一維全局搜索，隨后LS估計出MS初始估計值；為了進一步抑制較大的NLOS誤差，本文提出利用MS初始估計值與主基站B S1的距離平均值作為閾值，從而篩選出MS所有可能位置點，最后進行歸一化加權(quán)得到MS最終估計位置.

因此，將所提出算法在有散射半徑約束（約束條件為式（21））下的主要步驟描述如下：

步驟 1首先確定搜索步長l1和l2.將α1、α2區(qū)間長度劃分成k等份，作為迭代增量，如式（22）.

步驟 2設(shè)置下一時刻迭代因子 α1、α2.這里選取 α1、α2的迭代初始起點為α1,0=α1,low,α2,0=α2,low，將滿足約束式（21）的 α1、α2代入式（23）計算相應(yīng) α3，并判斷 α3是否滿足約束條件式（21），若滿足則繼續(xù)執(zhí)行步驟3，否則進行下一次迭代, 設(shè)置下次迭代參量為α1=a1,0+l1, α2=a2,0+l2.

步驟3獲取MS的一個估計位置.將步驟2中搜索的有效αj代入式（9），從而計算出MS的一個初始估計位置(xcp,ycp).

步驟4MS估計位置點篩選.在NLOS環(huán)境下，所有MS可能位置點均應(yīng)在觀測基站的定位圓內(nèi)，這里考慮將MS可能位置限制在以B S1為圓心，Dthr為半徑的圓內(nèi)，其中Dthr表示MS所有初始估計值與BS1的距離平均值.假定通過迭代計算有N個MS 初始估計位置點(xcpn,ycpn),n=1,2,···,N, 則Dthr可表示為

步驟5計算MS加權(quán)估計位置.假定閾值篩選出M個MS候選位置點，其位置坐標為m=1,2,···,M，平均位置坐標為，則各候選點與之距離為利用 的dm歸一化倒數(shù)作為加權(quán)系數(shù)，即可得到MS的最終位置(xMS,yMS).

算法在無散射半徑約束下的處理過程類似，只需將步驟2中的約束條件替換為式（10）～（12）即可.

3 算法仿真與分析

圖1蜂 窩 網(wǎng)絡(luò) 環(huán)境 中 ，假 定Rc為1000 m，MS 坐標為(7 00,100)m，BS1、BS2坐標分別為(0 ,0)、散射體由給定散射半徑的單次圓盤（disk of scatter，DOS）模型產(chǎn)生，TOA 距離測量誤差服從均值uTOA為0、標準差σTOA為5 m的高斯分布，AOA測量誤差服從均值uAOA為0、標準差σAOA為1°的高斯分布，k取值為300.

基于上述仿真參數(shù)，將本文所提出基于迭代MS定位算法與HLOP算法、內(nèi)點法（interior point algorithm，IPA）以及GSA進行性能比較，每個仿真獨立運行 1000 次.記：無散射半徑約束（即式（10）～式（12））為約束條件 1，有散射半徑約束（即式（21））為約束條件2.算法描述如表1所示.

表1 算法描述Tab.1 Algorithm description

為了驗證本文所提出算法的定位性能，首先仿真研究了上述4種算法在約束條件1下的平均定位誤差（mean location error，MLE）隨散射半徑的變化情況，如圖3所示.從圖中可見：這4種算法的定位精度都隨著散射半徑的增大而降低，其中HLOP算法受散射半徑影響最明顯，此外，本文算法定位精度明顯高于其他幾種算法，這是由于所提出基于迭代的MS定位算法通過閾值篩選以及加權(quán)平均的方式剔除了較大的NLOS誤差.

圖3 MLE 隨散射半徑的變化曲線Fig.3 MLE variation with scattering radius

圖4是在圓盤散射半徑為200 m，各算法MLE對應(yīng)的累積分布函數(shù)（cumulative distribution function，CDF）曲線.由圖中可見：本文基于迭代的MS定位算法誤差小于200 m就能達到100%，說明基于迭代定位算法可以明顯減小NLOS誤差對定位性能的影響，并取得較好性能.

圖4 圓盤散射半徑為200 m 累積分布函數(shù)曲線Fig.4 CDF curves with scattering radius of 200 m

驗證增加散射半徑幾何約束條件是否能提高算法的定位性能，將所提出的基于迭代的MS定位算法與IPA、GSA分別在約束條件1、2下的定位性能進行了對比分析，結(jié)果如圖5所示.從圖5中可見：兩種約束條件下，這3種算法定位精度隨著散射半徑的增加而降低，其中在約束條件2下的算法定位精度下降趨勢更加緩慢，說明增加的散射半徑幾何約束條件能有效抑制非視距誤差的影響.縱向來看，本文算法定位性能顯著優(yōu)于其他兩種算法.

圖5 MLE 與有無散射半徑約束的變化曲線Fig.5 MLE variation with or without scattering radius constraint

圖6所示為最大散射半徑200 m時，本文算法、IPA和GSA的MLE對應(yīng)的累積分布函數(shù)曲線.從圖中可以看出：使用散射半徑約束條件下，這3種算法的性能都能得到提升，且本文算法定位精度明顯高于GSA算法，這是由于本文算法采用一維迭代搜索有效值更加逼近中心路徑，并且還對得到的MS估計值進行了閾值篩選和加權(quán)處理.

圖6 累積分布函數(shù)曲線Fig.6 CDF curves with or without scattering radius constraint

為分析TOA距離測量誤差與AOA測量誤差對定位誤差的影響，假定散射半徑為200 m，分別在約束條件1、2下對本文算法、IPA和GSA這3種算法性能進行仿真對比.圖7和圖8分別是改變TOA和AOA測量值標準差時本文算法、IPA和GSA這3種算法對應(yīng)的MLE變化曲線.從仿真結(jié)果可見：隨著TOA或AOA測量誤差的增加，3種算法的MLE在一定程度上有小幅度上升，說明TOA噪聲標準差以及AOA誤差對算法影響極小；縱向?qū)Ρ绕渌麅煞N算法，本文算法具有更好的定位性能.

圖7 MLE 隨距離測量誤差的變化曲線Fig.7 MLE variation with distance measurement error

圖8 MLE 隨角度測量誤差的變化曲線Fig.8 MLE variation with angle measurement error

為分析區(qū)間長度的劃分因子k對MS定位精度的影響，圖9給出了在散射半徑為200 m時，對應(yīng)約束條件1和約束條件2下本文算法的平均定位誤差和均方根誤差隨k值變化曲線.由圖9可見：在k取0時，由于算法做異常情況處理，因此在有無散射約束時算法誤差一致；而隨著k取值增加，算法誤差有小幅度的下降趨勢，這主要是因為k值增加，迭代步長縮小，候選的初始點增加，滿足閾值條件估計結(jié)果得到提高.且k取700即可得到較好的定位性能.

圖9 誤差隨 k 的變化曲線Fig.9 Location error variation with k

本文還仿真研究了不同算法的計算復(fù)雜性.表2給出了3種算法程序在相同環(huán)境下運行1000次的平均消耗時間.從表2可見：本文算法耗時最少，且耗時量僅是網(wǎng)格搜索法的0.4%，而在約束條件2下算法耗時進一步減少，這是由于散射半徑約束縮小了目標的可行域范圍.

表2 算法時間開銷Tab.2 Algorithm time cost s

4 結(jié) 論

本文提出了一種應(yīng)用在雙基站場景下基于幾何約束及迭代的NLOS環(huán)境定位算法.通過引入散射信息縮小目標可行域，以一維線性迭代方式進行尋優(yōu)，有效地規(guī)避了傳統(tǒng)最優(yōu)化定位算法需要給定初始估計位置以確保算法收斂這一問題，最后使用閾值篩選以及歸一化加權(quán)，有效地抑制了較大的NLOS誤差對定位精度的不利影響.仿真結(jié)果表明，本文算法相比傳統(tǒng)的內(nèi)點法以及網(wǎng)格搜索法表現(xiàn)出更高的定位精度和更低的計算開銷.此外，由于僅需兩個基站參與定位，在參與定位基站數(shù)目受限的室內(nèi)外環(huán)境中具有較大的實用價值.