一種基于圓環(huán)模型的網(wǎng)格搜索定位算法*

王浩祥，鄧 平

(西南交通大學(xué) 信息編碼與傳輸重點(diǎn)實(shí)驗(yàn)室，成都 610031)

0 引 言

隨著信息行業(yè)的不斷發(fā)展，人們對(duì)全區(qū)域精準(zhǔn)定位的需求越來(lái)越大。雖然如今的基站(Base Station,BS)建設(shè)已經(jīng)可以滿(mǎn)足大部分區(qū)域被三個(gè)或三個(gè)以上的BS覆蓋，但是仍有小部分偏僻區(qū)域只能被兩個(gè)BS覆蓋，所以研究雙基站場(chǎng)景的非視距定位算法對(duì)于實(shí)現(xiàn)全區(qū)域的精準(zhǔn)定位具有重大意義。文獻(xiàn)[1]利用BS測(cè)得的電波到達(dá)角(Angle of Arrival,AOA)信息對(duì)散射體進(jìn)行定位，然后將散射體作為虛擬基站進(jìn)行網(wǎng)格搜索，最后將符合條件的網(wǎng)格點(diǎn)約束平均得到移動(dòng)臺(tái)(Mobile Station,MS)位置。文獻(xiàn)[2]根據(jù)先驗(yàn)的建筑信息模型，將建筑模型的幾何約束信息加入到原有的優(yōu)化問(wèn)題中，較好地提升了定位性能。文獻(xiàn)[3]針對(duì)內(nèi)點(diǎn)法局部最優(yōu)性質(zhì)，提出了一種網(wǎng)格搜索方法，設(shè)立兩個(gè)誤差因子，根據(jù)誤差因子的上下限設(shè)置網(wǎng)格區(qū)域，將網(wǎng)格內(nèi)滿(mǎn)足約束的點(diǎn)平均后得到MS位置。文獻(xiàn)[4]根據(jù)先驗(yàn)的基站周?chē)目臻g布局確定出散射區(qū)域并構(gòu)建散射區(qū)模型，然后將聚類(lèi)算法與幾何模型結(jié)合構(gòu)建優(yōu)化問(wèn)題，最后根據(jù)最優(yōu)化理論求解移動(dòng)臺(tái)的位置。

在針對(duì)特定的散射體分布模型的研究中，文獻(xiàn)[5]提出了基于圓環(huán)模型的混合定位算法，通過(guò)不斷迭代的方式確定散射半徑。算法需要6條多徑信號(hào)的到達(dá)時(shí)間(Time of Arrival,TOA)信息和AOA信息，并且要求散射體散射的信號(hào)被兩個(gè)基站同時(shí)接收到，條件比較苛刻。文獻(xiàn)[6]提出了針對(duì)指數(shù)分布和高斯分布的迭代求取移動(dòng)臺(tái)位置的算法。雖然針對(duì)特定散射模型的算法精度不錯(cuò)，但是復(fù)雜度較大。

在近幾年的少基站無(wú)線(xiàn)定位研究中，一般會(huì)加入一些額外的輔助信息或者特定的約束來(lái)進(jìn)行定位。文獻(xiàn)[7]仿真對(duì)比了電波到達(dá)角信息、電波離開(kāi)角信息以及最大散射半徑分別對(duì)定位性能的影響。另外，部分算法根據(jù)不同基站之間距離[8]或者基站與待測(cè)點(diǎn)之間的距離[9]確定不同基站的權(quán)重系數(shù)，利用權(quán)重系數(shù)的差距來(lái)提升定位的準(zhǔn)確性。文獻(xiàn)[10]提出了一種虛擬基站定位算法，在假定最大散射半徑的條件下估計(jì)出散射體位置，然后視散射體為虛擬基站來(lái)約束移動(dòng)臺(tái)位置范圍，最后在網(wǎng)格區(qū)域內(nèi)搜索移動(dòng)臺(tái)位置。

本文針對(duì)目前抗非視距定位算法存在需要的基站數(shù)目過(guò)多、多徑信號(hào)數(shù)目過(guò)多的問(wèn)題，提出了一種基于圓環(huán)模型的網(wǎng)格搜索定位算法。仿真結(jié)果表明，與現(xiàn)有算法相比，本文所提算法具有更好的定位性能。

1 基于圓環(huán)模型的混合定位算法

當(dāng)散射模型處于一種特定的模型時(shí)，比如圓環(huán)分布、圓盤(pán)分布等，用特定的算法可以根據(jù)不同散射模型的幾何約束條件更好進(jìn)行定位，如HRB(Hybrid TOA/AOA Ring Based)算法就是一種基于圓環(huán)模型的混合定位算法[5]。

由圖1可以看出HRB算法適用于雙基站環(huán)境，需要的散射體數(shù)量為3個(gè)或3個(gè)以上，散射體的分布需要符合圓環(huán)分布模型。算法進(jìn)行定位需要6條多徑信號(hào)的TOA和AOA信息。αij代表基站BSj收到的來(lái)自散射體Si的多徑信號(hào)AOA值，Lij代表基站BSj收到的來(lái)自散射體Si的多徑信號(hào)TOA值，R為圓環(huán)散射模型的半徑。

圖1 基于圓環(huán)模型的幾何分布示意圖

根據(jù)圓環(huán)散射模型的幾何特征，基站到散射體的距離可以表示為dij=Lij-R，散射體的坐標(biāo)(xij,yij)可以根據(jù)dij、αij、基站BSj的橫坐標(biāo)xbsj和基站BSj的縱坐標(biāo)ybsj進(jìn)行計(jì)算：

(1)

2Aθ=b。

(2)

(3)

HRB算法的主要步驟如下：

Step1 假定散射體半徑R的初始值。

Step2 根據(jù)每個(gè)基站的測(cè)量TOA值和AOA值通過(guò)式(1)計(jì)算散射體的坐標(biāo)。

Step3 根據(jù)式(3)計(jì)算移動(dòng)臺(tái)MS的坐標(biāo)。

Step4 根據(jù)更新的MS坐標(biāo)計(jì)算散射體半徑R的更新值。

Step5 計(jì)算更新的散射體半徑與原有的散射體半徑差值是否小于設(shè)定的閾值，若大于則用更新之后的R返回Step 2，繼續(xù)迭代；若小于則停止迭代，當(dāng)前步驟求得的MS坐標(biāo)即為最終值。

2 基于圓環(huán)模型的網(wǎng)格定位算法

本文根據(jù)現(xiàn)有的雙基站定位算法，提出了一種改進(jìn)的TOA/AOA混合定位算法。算法應(yīng)用于雙基站定位環(huán)境，需要的散射體數(shù)量為3個(gè)或3個(gè)以上，散射模型為圓環(huán)散射模型，要求多徑信號(hào)數(shù)目在3條或3條以上。算法將虛擬基站思想與網(wǎng)格搜索算法相結(jié)合，主要流程分為三步：首先進(jìn)行散射體位置的確定；其次對(duì)移動(dòng)臺(tái)的位置進(jìn)行網(wǎng)格搜索；最后將所有候選點(diǎn)根據(jù)定義的誤差目標(biāo)函數(shù)的大小進(jìn)行選擇性平均。

2.1 散射體位置的確定

參考HRB算法的迭代改變散射半徑的方式，本文將迭代改變散射半徑的方式改為搜索散射半徑的方式。本文算法將HRB算法所需要的多徑信號(hào)數(shù)量從6條降低到了3條，并且解決了兩個(gè)基站要同時(shí)檢測(cè)到來(lái)自同一散射體散射的信號(hào)這一問(wèn)題。

圖2是散射體數(shù)量為3個(gè)時(shí)，基站、散射體和移動(dòng)臺(tái)的幾何分布示意圖，基站BS1檢測(cè)到了來(lái)自?xún)蓚€(gè)散射體散射的多徑信號(hào)，BS2檢測(cè)到了來(lái)自剩下散射體散射的多徑信號(hào)。根據(jù)圓環(huán)散射模型的幾何特征，基站測(cè)得的距離測(cè)量值減去R可得基站與散射體的距離，然后根據(jù)測(cè)量距離和AOA測(cè)量值求出散射體坐標(biāo)。

圖2 算法幾何分布示意圖

已知散射體坐標(biāo)后，根據(jù)移動(dòng)臺(tái)到各個(gè)散射體的距離均為R可設(shè)立等式方程，對(duì)MS的求解公式為

(4)

搜索散射半徑的主要步驟如下：

Step1 先假設(shè)一個(gè)圓環(huán)散射半徑的初值R，一般從0開(kāi)始。

Step2 將散射體半徑R和基站檢測(cè)到的TOA、AOA信息代入式(1)求解散射體的坐標(biāo)。

Step3 根據(jù)式(4)的最小二乘法，求出移動(dòng)臺(tái)的坐標(biāo)。

Step4 求出移動(dòng)臺(tái)與所有散射體的距離，判斷這些距離與R的差值是否都小于設(shè)定的閾值，若小于則跳出循環(huán)，當(dāng)前散射半徑和散射體坐標(biāo)即為所求；若大于則將R增大一定的步長(zhǎng)，再?gòu)腟tep 2開(kāi)始循環(huán)。

2.2 網(wǎng)格搜索并篩選候選點(diǎn)

當(dāng)完成了散射體位置的確定，接下來(lái)便是網(wǎng)格區(qū)域的確定和候選點(diǎn)的篩選。文獻(xiàn)[10]利用了先驗(yàn)的最大散射半徑這一信息，對(duì)散射體位置進(jìn)行求解，再利用最大散射半徑信息進(jìn)行網(wǎng)格區(qū)域的確定與搜索。本文并沒(méi)有假定最大散射半徑這一限制，在確定散射體坐標(biāo)后，將3個(gè)散射體作為虛擬基站，以搜索好的R作為當(dāng)前虛擬基站得到的TOA值。如圖3所示，移動(dòng)臺(tái)的位置位于以虛擬基站VBSi為圓心、以圓環(huán)散射半徑R為半徑的定位圓交疊域內(nèi)，即圖3中的陰影區(qū)域。

圖3 虛擬基站定位示意圖

由于圖3中的陰影區(qū)域難以確定邊界，所以將圖3中的三個(gè)圓交疊的陰影區(qū)域放大到如圖3所示的三個(gè)矩形區(qū)域的交疊區(qū)域，這樣可將網(wǎng)格搜索的區(qū)域設(shè)定為長(zhǎng)方形，方便進(jìn)行遍歷搜索。即移動(dòng)臺(tái)位于以虛擬基站VBSi位置坐標(biāo)(xVBS,i,yVBS,i)為中心、以2R為邊長(zhǎng)的矩形交疊區(qū)域內(nèi)，從而獲得MS位置范圍為

(5)

(6)

(7)

2.3 選擇性平均

在得到K個(gè)MS的可能位置候選點(diǎn)后，根據(jù)最優(yōu)化定位技術(shù)的思想，構(gòu)建出誤差目標(biāo)函數(shù)：

(8)

(9)

li=dms,si+ds,i=

(10)

將得到的MS的可能位置候選點(diǎn)代入式(8)進(jìn)行求解，然后根據(jù)目標(biāo)函數(shù)F(x,y,Ψs)的大小進(jìn)行排序，排序后舍去較大的K/2個(gè)值(向下取整)，最后將剩下的目標(biāo)函數(shù)的值對(duì)應(yīng)的可能位置候選點(diǎn)坐標(biāo)進(jìn)行算術(shù)平均，得到最終的MS位置坐標(biāo)。

綜上，本文提出的算法流程如圖4所示。

圖4 算法流程圖

3 算法仿真與性能分析

本文仿真過(guò)程是在Matlab軟件下進(jìn)行的，挑選雙基站環(huán)境下的5種算法進(jìn)行比較:HTA(hybrid TOA/AOA algorithm)算法、TACA(TOA/AOA Constraint Algorithm)算法、網(wǎng)格搜索算法(Grid Search Algorithm,GSA)[3]、HRB算法以及本文的改進(jìn)算法。幾何分布圖如圖3所示。散射體模型為圓環(huán)模型，基站數(shù)量為2個(gè)，坐標(biāo)分別為BS1(0,0)、BS2(1 732,0)，單位m。蜂窩網(wǎng)的半徑為1 000 m，移動(dòng)臺(tái)坐標(biāo)為

(11)

通過(guò)使用無(wú)線(xiàn)定位中常用的均方根誤差(Root Mean Square Error,RMSE)、平均定位誤差(Average Location Error,ALE)和累積分布函數(shù)(Cumulative Distribution Function,CDF)三種評(píng)判指標(biāo)來(lái)進(jìn)行不同算法之間的性能比較。

固定角度測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為1°的高斯分布，距離測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為5 m的高斯分布，散射體半徑R作為變量，取值依次分別為100 m、150 m、200 m、250 m、300 m，獨(dú)立仿真1 000次，5種算法的ALE曲線(xiàn)和RMSE曲線(xiàn)分別如圖5和圖6所示。由圖可見(jiàn)，隨著散射半徑的增大，各個(gè)算法的性能都有所下降，主要是因?yàn)閭鞑ゾ嚯x變長(zhǎng)，NLOS誤差變大。本文算法具有較小的平均定位誤差和均方根誤差，并且與其他算法定位誤差差距較為明顯，充分體現(xiàn)了本文算法對(duì)NLOS誤差的適應(yīng)性?xún)?yōu)于對(duì)比的其他算法。

圖5 ALE隨散射半徑的變化

圖6 RMSE隨散射半徑的變化

固定距離測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為5 m的高斯分布，散射半徑設(shè)置為200 m，將角度測(cè)量誤差作為變量，均值為0，標(biāo)準(zhǔn)差依次取值0.5°、1°、1.5°、2°、2.5°，獨(dú)立仿真1 000次的ALE曲線(xiàn)如圖7所示。由圖可以看出，隨著AOA測(cè)量誤差的增大，對(duì)比算法的性能變化不大，但是HRB算法和本文算法的誤差有較小的增大。這主要是因?yàn)檫@兩種算法在定位散射體時(shí)用到了基站的AOA測(cè)量值，該測(cè)量值的準(zhǔn)確性可以影響散射體的坐標(biāo)估計(jì)準(zhǔn)確性。從仿真圖可以看出本文算法的定位性能依然優(yōu)于對(duì)比算法。

圖7 ALE隨角度測(cè)量誤差的變化

固定角度測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為1°的高斯分布，散射半徑設(shè)置為200 m，將距離測(cè)量誤差作為變量，均值為0，標(biāo)準(zhǔn)差依次取值2 m、4 m、6 m、8 m、10 m，獨(dú)立仿真1 000次的ALE曲線(xiàn)如圖8所示。由圖可以看出，算法對(duì)TOA測(cè)量誤差都不敏感，在不同的TOA測(cè)量誤差情況下本文算法性能優(yōu)于對(duì)比算法。

圖8 ALE隨距離測(cè)量誤差的變化

固定角度測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為1°的高斯分布，距離測(cè)量誤差服從均值為0、標(biāo)準(zhǔn)差為5 m的高斯分布，散射半徑設(shè)置為150 m,5種算法的誤差累積分布函數(shù)曲線(xiàn)如圖9所示。由圖可以看出本文算法的平均定位誤差小于200 m時(shí)CDF可達(dá)到100%，表現(xiàn)出了較強(qiáng)的魯棒性，這主要是由于網(wǎng)格搜索法與選擇性平均結(jié)合使用的效果。實(shí)驗(yàn)結(jié)果證實(shí)了本文算法的有效性。

圖9 圓環(huán)模型下累計(jì)分布函數(shù)曲線(xiàn)圖

固定散射模型的兩種算法利用了散射模型的幾何關(guān)系，在先驗(yàn)條件上比HTA、TACA和網(wǎng)格搜索算法多，所以整體上看，固定散射模型的兩種算法性能好于另外的三種算法。

從仿真圖可以看出改進(jìn)的算法性能明顯好于傳統(tǒng)的最優(yōu)化定位算法以及HRB算法。雖然改進(jìn)算法和HRB算法都是基于固定散射模型的算法，但是改進(jìn)算法只使用了3條多徑信號(hào)的信息，而HRB算法使用了6條，并且要求散射體散射的信號(hào)同時(shí)被兩個(gè)基站都檢測(cè)到，條件比較嚴(yán)苛。從算法理論的角度分析，本文算法先是通過(guò)圓環(huán)模型的幾何特征和基站測(cè)量值信息確定出散射體坐標(biāo)，然后根據(jù)虛擬基站技術(shù)可以減少非視距誤差的特性，將散射體視為基站進(jìn)行后續(xù)的定位。算法后續(xù)的網(wǎng)格搜索定位法是一種直接利用約束條件進(jìn)行定位的最優(yōu)化理論算法，相較于對(duì)比的最優(yōu)化內(nèi)點(diǎn)法，既降低了算法復(fù)雜度又解決了內(nèi)點(diǎn)法局部最優(yōu)的情況。

改進(jìn)算法利用圓環(huán)模型的幾何特性，先比較精準(zhǔn)地定位了散射體位置，在基于比較精準(zhǔn)的散射體位置的基礎(chǔ)上將網(wǎng)格搜索法和選擇性平均結(jié)合，很好地提升了定位性能。

4 結(jié) 論

為提升文獻(xiàn)[5]提出的基于固定散射模型的HRB算法的性能，本文先利用圓環(huán)模型的幾何特征，搜索圓環(huán)的半徑，根據(jù)圓環(huán)的半徑、TOA信息和AOA信息確定散射體的位置；然后將散射體作為虛擬基站來(lái)約束MS可能位置范圍，并使用網(wǎng)格搜索來(lái)獲得多個(gè)MS可能的估計(jì)位置；最后根據(jù)目標(biāo)函數(shù)的大小進(jìn)行選擇性平均。不同NLOS場(chǎng)景下的仿真結(jié)果表明，本文算法的定位誤差相較于文獻(xiàn)[5]算法有明顯減少，同時(shí)也要顯著優(yōu)于其他現(xiàn)有算法，驗(yàn)證了算法的有效性。