一種變權(quán)重k最近鄰的室內(nèi)外無縫定位算法*

李玉峰，張 佩，王宇鵬

（沈陽航空航天大學(xué)電子信息工程學(xué)院，沈陽110136）

1 引言

定位技術(shù)大體上可分為室內(nèi)定位和室外定位兩個(gè)大的方向。室外環(huán)境的定位技術(shù)主要以全球?qū)Ш叫l(wèi)星系統(tǒng)（Global Navigation Satellite System,GNSS）為主，因其易用性和廣泛覆蓋性被廣泛應(yīng)用在戶外定位中[1]，但由于衛(wèi)星導(dǎo)航的固有特性，在室內(nèi)或擁擠的市區(qū)環(huán)境下，無法提供定位服務(wù)。在室內(nèi)定位方面，出現(xiàn)了眾多的定位方案：WiFi、藍(lán)牙、紅外信標(biāo)、超寬帶（Ultra-Wide Bandwidth,UWB）等，在這些技術(shù)中UWB屬于比較新穎的技術(shù)。由于UWB信號(hào)有很高的時(shí)間分辨率，很快在定位領(lǐng)域廣受關(guān)注和研究。在文獻(xiàn)[2]中，由克拉美羅下界可知，UWB的定位精度在厘米級(jí)。但由于其帶寬很寬和功率小的特點(diǎn)，只適用于范圍較小的室內(nèi)環(huán)境，這在很大程度上限制了UWB在室外定位的發(fā)展[3]。

為了提供室內(nèi)外全范圍的定位服務(wù)，依靠單一的定位手段是無法實(shí)現(xiàn)的；而且在大面積和復(fù)雜的室內(nèi)環(huán)境中，定位區(qū)域不止一個(gè)，因此如何在不同定位區(qū)域內(nèi)實(shí)現(xiàn)流暢地軟切換也是一個(gè)有待解決的問題[4]。為解決上面提到的這兩個(gè)定位問題，提出一種基于GPS和UWB的無縫定位方案。該無縫定位方案是基于k最近鄰算法實(shí)現(xiàn)了不同定位數(shù)據(jù)的融合，進(jìn)而實(shí)現(xiàn)不同定位區(qū)域的軟切換，同時(shí)也可實(shí)現(xiàn)定位數(shù)據(jù)的濾波，并在一定程度上抑制了非視距誤差[5]。

k最近鄰算法（kNN）是一種主要用于分類以及回歸的非參數(shù)統(tǒng)計(jì)方法。當(dāng)前在機(jī)器學(xué)習(xí)領(lǐng)域該算法已受到較為廣泛的使用[6]，但在信息的融合以及定位方面，該法并未得到廣泛關(guān)注和使用。

2 無縫定位系統(tǒng)的設(shè)計(jì)

在此定位方法中，把室外GPS定位區(qū)域及室內(nèi)UWB不同的定位區(qū)域都看成是相同類型的定位區(qū)域，進(jìn)行無差別地定位估計(jì)。因此室內(nèi)外無縫定位切換和室內(nèi)不同區(qū)域的軟切換這兩個(gè)問題就抽象為一個(gè)問題：如何處理所有接收的定位數(shù)據(jù)（UWB測距數(shù)據(jù)、GPS數(shù)據(jù)）并進(jìn)行估計(jì)，從而得出一個(gè)最優(yōu)解作為定位的估計(jì)點(diǎn)。這樣在進(jìn)行定位估計(jì)的同時(shí)就完成了不同定位區(qū)域的軟切換。

采用權(quán)重可變的k最近鄰算法[7]來解決上面提到的問題。把所有解算產(chǎn)生的UWB定位估計(jì)點(diǎn)以及GPS定位數(shù)據(jù)點(diǎn)看成是近鄰點(diǎn)，并把前一狀態(tài)的一步預(yù)測值作為參考點(diǎn)來與那些近鄰點(diǎn)進(jìn)行鄰近判斷。根據(jù)二維平面的歐式距離作為權(quán)重計(jì)算依據(jù)來得出k近鄰范圍內(nèi)所有近鄰點(diǎn)的加權(quán)平均值，把該值作為本次定位的估計(jì)值，并用于計(jì)算出下次定位估計(jì)中的一步預(yù)測值。不同定位模塊（UWB或GPS）及相同定位模塊的不同測量形式，如基于TOA（Time of Arrival）、TDOA（Time Difference of Arrival）等，經(jīng)過初步的解算都可以產(chǎn)生二維平面上的坐標(biāo)點(diǎn)，即所提到的近鄰點(diǎn)為：

式中，上標(biāo)代表近鄰的定位數(shù)據(jù)來源，下標(biāo)代表當(dāng)前定位區(qū)域中雙定位基站序號(hào)的組合，n代表最多基站數(shù)。

在決策階段，采用的是權(quán)重決策機(jī)制，即根據(jù)不同近鄰點(diǎn)的權(quán)重進(jìn)行加權(quán)平均進(jìn)而得出最后的定位估計(jì)點(diǎn)。因此問題進(jìn)一步轉(zhuǎn)換為如何動(dòng)態(tài)地調(diào)整所有可能的定位近鄰點(diǎn)的權(quán)重，在動(dòng)態(tài)調(diào)整定位近鄰點(diǎn)權(quán)重的過程中便實(shí)現(xiàn)了錯(cuò)誤數(shù)據(jù)的剔除（包括定位多解的消除）和正確數(shù)據(jù)的融合，從而實(shí)現(xiàn)了不同區(qū)域的軟切換，這樣在室內(nèi)外銜接區(qū)域以及室內(nèi)不同定位區(qū)域便完成了無縫定位與切換。本算法的結(jié)構(gòu)框圖如圖1。

圖1 無縫定位算法整體框圖

3 室外定位坐標(biāo)轉(zhuǎn)換

為實(shí)現(xiàn)室內(nèi)UWB和室外GPS定位的數(shù)據(jù)融合和切換，需把GPS的經(jīng)緯度數(shù)據(jù)轉(zhuǎn)換為室內(nèi)坐標(biāo)系下的定位數(shù)據(jù)。為此，可以先選定室外兩點(diǎn)，精確測試其GPS位置信息，計(jì)算出對(duì)應(yīng)的室內(nèi)UWB基站點(diǎn)的位置坐標(biāo)。

此處室外參考點(diǎn)的坐標(biāo)系是大地坐標(biāo)系。地面參考點(diǎn)P的位置用大地經(jīng)度L、大地緯度B和大地高度H表示。采用高斯投影法[4]實(shí)現(xiàn)了大地坐標(biāo)轉(zhuǎn)換為平面坐標(biāo)(x,y)，變換過程如下：

式中，ΔL為經(jīng)度差，L為所求點(diǎn)的經(jīng)度，L0為3度帶中央子午線的經(jīng)度，為橢圓的第二偏心率，B為所求點(diǎn)的緯度；

式中，X為緯度，B為對(duì)應(yīng)的子午線弧長，N為所求點(diǎn)對(duì)應(yīng)的卯酉圈子午線半徑。經(jīng)過上面的計(jì)算，便可以把GPS的經(jīng)緯度信息轉(zhuǎn)換為平面坐標(biāo)(x,y)的數(shù)據(jù)[8]。

通過上述的坐標(biāo)轉(zhuǎn)換便可以把GPS數(shù)據(jù)轉(zhuǎn)換為當(dāng)前定位坐標(biāo)系下的定位近鄰點(diǎn)zGPS。

4 室內(nèi)定位解算

文獻(xiàn)[9]中提出了TOA、TDOA的融合算法。本研究提出的融合算法可以融合多種不同測距方式所得的數(shù)據(jù)，包括TOA、TDOA等。在此僅對(duì)基于TOA的定位數(shù)據(jù)與GPS定位數(shù)據(jù)進(jìn)行無縫定位研究，未對(duì)TDOA測距數(shù)據(jù)進(jìn)行研究與驗(yàn)證。室內(nèi)定位解算分為兩步：雙定位基站號(hào)序列的確定；雙基站定位解算。

4.1 雙定位基站號(hào)序列的確定

在二維平面中進(jìn)行定位解算，若使用兩個(gè)定位基站進(jìn)行定位，則會(huì)出現(xiàn)多解的問題。但在本算法中，使用k最近鄰的方法可以通過結(jié)合其他雙基站的定位信息而使多解問題得到解決，消除定位多解模糊。

進(jìn)行解算時(shí)，首先需要確定兩個(gè)定位基站。在本算法中，為了更好地利用測距數(shù)據(jù)，采用定位區(qū)域中所有的兩個(gè)基站組合進(jìn)行定位解算。另外考慮到現(xiàn)實(shí)中UWB測距距離的限制，只考慮基站間距離小于UWB測距距離的基站組合可能情況。以所研究的定位情景圖為例，如有效測距最大為D，以區(qū)域A中的一個(gè)定位實(shí)例點(diǎn)M為例，給出在該點(diǎn)M處可進(jìn)行定位解算的雙基站序列如下：

定位實(shí)例點(diǎn)M、定位基站位置以及模擬的定位情景如圖2所示。

圖2 基站位置與定位實(shí)例圖

4.2 雙基站定位解算

在雙定位基站確定后，下一步要進(jìn)行定位的解算。定位解算是基于雙基站TOA測距的定位方案，因此定位模型可抽象為兩個(gè)已知圓求交點(diǎn)的數(shù)學(xué)模型，如圖3所示：

圖3 雙基站定位示意圖

由圖3可知，只要知道兩個(gè)基站的位置坐標(biāo)(Xa,Ya)、(Xb,Yb),以及基站到標(biāo)簽的距離D1、D2便可進(jìn)行計(jì)算，算出兩個(gè)圓的兩個(gè)交點(diǎn)(x1,y1)、(x2,y2)。

每對(duì)雙基站定位數(shù)據(jù)可解算出兩個(gè)定位點(diǎn)，即產(chǎn)生兩個(gè)定位近鄰點(diǎn)，結(jié)合上面已給出的雙基站序列，通過分別計(jì)算不同的雙基站序列的定位數(shù)據(jù)便可計(jì)算出該標(biāo)簽在當(dāng)前環(huán)境下所有可能的定位近鄰點(diǎn)。這些定位近鄰點(diǎn)中包括反映真實(shí)位置的點(diǎn)以及多解點(diǎn)，通過下一節(jié)將會(huì)介紹的k最近鄰算法的計(jì)算便可從這些定位近鄰點(diǎn)中估計(jì)出真實(shí)的定位點(diǎn)。以下是針對(duì)上面給出的定位實(shí)例點(diǎn)而產(chǎn)生的定位近鄰點(diǎn)的集合：

5 k最近鄰計(jì)算

通過上面的GPS定位數(shù)據(jù)的坐標(biāo)轉(zhuǎn)換和UWB雙基站解算，便可得出在該時(shí)刻下該標(biāo)簽位置的所有定位近鄰點(diǎn)的集合Z。下一步可通過基于變權(quán)重的k最近鄰算法進(jìn)行定位點(diǎn)的估計(jì)。最近鄰的參考位置是由上次估算的目標(biāo)移動(dòng)速度和定位估計(jì)點(diǎn)進(jìn)行一步預(yù)測而得出的，其計(jì)算方法如下：

式中，Si為本次一步預(yù)測點(diǎn)，Si-1為上次定位估計(jì)點(diǎn)，Vi-1為上次估計(jì)的移動(dòng)速度，T為計(jì)算周期。

由k最近鄰算法的特點(diǎn)可知，k值的選擇非常重要，選得太大會(huì)使定位誤差增加，而選得太小則可能出現(xiàn)跟蹤失敗而導(dǎo)致計(jì)算發(fā)散。在本算法中采用的是動(dòng)態(tài)k的方法，每次計(jì)算的k值并不固定。以參考點(diǎn)Si為中心，半徑為R的圓內(nèi)的近鄰點(diǎn)的數(shù)目即為本次的k值，即ki。因此R的大小決定了ki值可取的大小。在本次研究中暫不對(duì)R的選擇進(jìn)行深入探討，只是取一個(gè)比較合理的值。在仿真中，近鄰半徑R取150 cm。

在近鄰數(shù)目ki確定后，下一步進(jìn)行各個(gè)近鄰點(diǎn)權(quán)重大小的計(jì)算。在二維平面中，可以由歐氏距離來對(duì)距離遠(yuǎn)近做出評(píng)估，因此首先計(jì)算出ki個(gè)近鄰點(diǎn)各自與參考點(diǎn)的歐氏距離，然后利用該距離值來計(jì)算在i時(shí)刻的第j個(gè)近鄰的權(quán)重wi,j[10]：

式中，f為權(quán)重計(jì)算函數(shù)，(xj,yj)為第j個(gè)近鄰的坐標(biāo)值，(x,y)為i時(shí)刻的計(jì)算參考點(diǎn)。

權(quán)重函數(shù)有多種，理論上只要與誤差成反比即可，如線性函數(shù)y=kx+b(k＜0,b＞0)、高斯函數(shù)等。在本算法中初步選擇均值為0，方差為σ2的高斯函數(shù)作為權(quán)重函數(shù)，且只取自變量在一定范圍內(nèi)的函數(shù)值，具體表達(dá)式如下：

式中，d為近鄰點(diǎn)到參考點(diǎn)的歐氏距離，R為上面提到的近鄰半徑。L為常數(shù)系數(shù)，仿真中取值150。權(quán)重函數(shù)的圖形如圖4所示。由高斯函數(shù)的特點(diǎn)可知，使用高斯函數(shù)可以使近鄰點(diǎn)的權(quán)重分布更集中于參考點(diǎn)附近，而普通的一次函數(shù)就沒有這個(gè)特點(diǎn)。因此選擇高斯函數(shù)作為權(quán)重函數(shù)更有利于減小估計(jì)的誤差，提高估計(jì)精度。

在決策階段，采用的是權(quán)重決策機(jī)制，即根據(jù)不同近鄰點(diǎn)的權(quán)重進(jìn)行加權(quán)平均進(jìn)而得出最后的定位估計(jì)點(diǎn)如下：

圖4 權(quán)重函數(shù)

式中，wi,j為近鄰點(diǎn)的權(quán)重，Zi為近鄰點(diǎn)的坐標(biāo)Zi=(xi,yi)T，為近鄰個(gè)數(shù)。

式中，Δ為本次速度估計(jì)誤差，由本次定位估計(jì)點(diǎn)和本次一步預(yù)測點(diǎn)的差值決定，Vi為本次的速度估計(jì)值。

經(jīng)過上面的動(dòng)態(tài)權(quán)重的k最近鄰算法便可估計(jì)出本次目標(biāo)點(diǎn)的坐標(biāo)P?i以及速度 Vi。坐標(biāo)P?i即為最終的定位估計(jì)點(diǎn)。

6 模擬仿真與分析

本算法通過模擬現(xiàn)實(shí)中的定位場景和定位數(shù)據(jù)來進(jìn)行算法驗(yàn)證，采用MATLAB作為仿真平臺(tái)。定位場景模擬的是室內(nèi)長廊和室外兩個(gè)環(huán)境，室內(nèi)長廊分為兩個(gè)定位區(qū)域，其中分布有6個(gè)定位基站；長廊右邊是室外區(qū)域。

為了更好地逼近真實(shí)的UWB定位數(shù)據(jù)，在距離真值的基礎(chǔ)上疊加了高斯噪聲、隨機(jī)錯(cuò)誤值并通過有效距離函數(shù)進(jìn)行距離的限制。高斯噪聲取均值為0，方差為110[11]；隨機(jī)錯(cuò)誤用隨機(jī)強(qiáng)制置0的方法來模擬UWB出現(xiàn)的定位錯(cuò)誤及信號(hào)丟失的情況；有效距離函數(shù)采用門函數(shù)，即：式中，Dmax表示UWB測距的最大距離，di為未進(jìn)行距離限制的值。

如圖5即是仿真實(shí)驗(yàn)中目標(biāo)點(diǎn)到定位基站5的模擬距離數(shù)據(jù)。

圖5 模擬的定位距離數(shù)據(jù)

通過MATLAB的仿真，得出了定位估計(jì)點(diǎn)的軌跡，如圖6。由圖中可知，定位的估計(jì)點(diǎn)和真實(shí)的點(diǎn)的偏差非常小，而且在室內(nèi)不同區(qū)域的切換中并沒有出現(xiàn)明顯的切換間斷；在室內(nèi)與室外的切換區(qū)域中，也是平滑過渡的。由于GPS數(shù)據(jù)的誤差更大些，因此在仿真時(shí)選取的GPS數(shù)據(jù)的噪聲方差比較大；而UWB測距數(shù)據(jù)的誤差在厘米級(jí)[12]。因此在定位軌跡圖中會(huì)看到在離開室內(nèi)一段距離（即無UWB測距數(shù)據(jù)）后，定位的性能明顯下降。但和原始的GPS定位點(diǎn)形成的軌跡比較可見，該算法進(jìn)行定位估計(jì)比原始的GPS定位有效果上的提升。

圖6 定位估計(jì)軌跡

由于初始參考位置點(diǎn)的未知，會(huì)出現(xiàn)剛開始時(shí)定位估計(jì)誤差大的情況，因此在剛開始進(jìn)行估計(jì)的幾步中（比如圖6中為3步），估計(jì)位置與實(shí)際位置偏差較大，但在收斂到正確值后，估計(jì)誤差可穩(wěn)定到很小的正常水平。

由于在本算法中會(huì)用到速度來對(duì)定位估計(jì)進(jìn)行一步預(yù)測作為k最近鄰的參考點(diǎn)，因此速度的估計(jì)也直接關(guān)系到定位的精度；而且在實(shí)際的定位應(yīng)用中，也希望得到目標(biāo)移動(dòng)速度的估計(jì)。在仿真中給定的是勻速運(yùn)動(dòng)，對(duì)目標(biāo)速度估計(jì)的曲線如圖7。

圖7 目標(biāo)速度估計(jì)

由速度估計(jì)的數(shù)據(jù)可知，在剛開始估計(jì)時(shí)由于定位估計(jì)初始點(diǎn)的未知而未收斂到正確值，因此其估計(jì)誤差比較大；在經(jīng)過幾步計(jì)算后，估計(jì)值已收斂到正確值附近，而且收斂的速度也比較快。在圖7中可觀察到，估計(jì)計(jì)算在4步之后已經(jīng)收斂。

為了定量地分析定位誤差，計(jì)算了在定位過程中各定位估計(jì)點(diǎn)與真值的偏差，如圖8。

圖8 定位偏差圖

通過定位誤差圖可明顯看出本算法定位估計(jì)的性能。在剛開始，會(huì)由于初始參考點(diǎn)的未知而造成定位估計(jì)的誤差較大，但經(jīng)過很短的幾步計(jì)算后便趨于穩(wěn)定，穩(wěn)定在誤差小于10 cm的范圍內(nèi)。在圖8中已標(biāo)出區(qū)域切換的位置（室內(nèi)區(qū)域切換和室內(nèi)到室外的切換），可以看出，在這兩個(gè)位置附近的定位誤差并沒有出現(xiàn)明顯的突變，因此證明了該算法完成了不同區(qū)域軟切換的目標(biāo)；由于在室外環(huán)境中GPS數(shù)據(jù)的誤差要大于UWB的測距誤差，因此在定位的后半段，估計(jì)的誤差會(huì)逐漸變大，直到UWB數(shù)據(jù)完全失效后，定位誤差穩(wěn)定到一個(gè)比較固定的數(shù)值。

為了顯示在不同位置處產(chǎn)生定位近鄰點(diǎn)的情況，選取了四個(gè)比較典型的位置進(jìn)行定位近鄰點(diǎn)的顯示，如圖9。

圖9 定位近鄰的分布圖

從圖中可以看到，在不同的定位位置計(jì)算出的定位近鄰數(shù)是不同的：在圖9(a)中，由于只能接受到4個(gè)基站的定位數(shù)據(jù)，因此計(jì)算出的定位近鄰數(shù)最多為6；在圖9(b)中，接收到兩個(gè)定位區(qū)域的6個(gè)基站的測距數(shù)據(jù)，因此計(jì)算出的定位近鄰數(shù)最多為11；在圖9(c)中，該位置是處在室外區(qū)域，為定位過渡帶，只能接收到2個(gè)定位基站的數(shù)據(jù)和1個(gè)GPS的數(shù)據(jù)，因此最多會(huì)產(chǎn)生2個(gè)定位近鄰；在圖9(d)中，由于UWB定位已失效，只有GPS的數(shù)據(jù)，因此定位近鄰只有一個(gè)GPS的數(shù)據(jù)。

從圖9(c)中還可看出，即使只有兩個(gè)定位基站的測距數(shù)據(jù)也可以進(jìn)行正常的定位，而在其他的算法中，這一點(diǎn)是做不到的。該算法可以在只有兩個(gè)基站數(shù)據(jù)的情況下進(jìn)行正確定位，其原理在于每次進(jìn)行一步預(yù)測的k最近鄰的參考點(diǎn)是由歷史數(shù)據(jù)估計(jì)出來的，該數(shù)據(jù)提供了消除多解的方向信息，因此在只有兩個(gè)基站的兩個(gè)定位解中，會(huì)選擇離該參考點(diǎn)最近的點(diǎn)作為估計(jì)，從而消除定位模糊。本算法的該項(xiàng)特點(diǎn)也使得在定位環(huán)境惡劣的情況下不會(huì)出現(xiàn)定位錯(cuò)誤甚至無法定位的問題，增加了定位系統(tǒng)的魯棒性。

7 結(jié)束語

此種基于變權(quán)重k最近鄰算法的室內(nèi)外無縫定位算法，融合了多種定位信息的方法，不但解決了室內(nèi)外定位無縫切換的需求，而且也克服了室內(nèi)的不同定位區(qū)域切換不流暢的問題；在定位精度方面，由于采用多個(gè)定位基站以不同排列組合進(jìn)行定位，充分利用了不同方位基站的定位信息，使定位精度進(jìn)一步提高，抑制了非視距傳播的影響。而且由于該算法的權(quán)值調(diào)整作用，使定位數(shù)據(jù)實(shí)現(xiàn)了濾波的效果，使定位數(shù)據(jù)更平滑。該算法采用迭代計(jì)算的方式，大大提高了運(yùn)算速度，可以應(yīng)用于實(shí)際中高刷新率的定位服務(wù)中。

由于本研究中并沒有對(duì)基于TDOA的UWB數(shù)據(jù)加入到融合算法進(jìn)行研究，只是提出了這樣一個(gè)融合框架，因此接下來要加入基于TDOA的UWB數(shù)據(jù)進(jìn)行研究。而且在由歷史數(shù)據(jù)進(jìn)行一步預(yù)測的方法也存在可改進(jìn)的空間。后續(xù)工作重點(diǎn)將圍繞這兩個(gè)方面展開，進(jìn)一步提高該無縫定位算法的性能。