WKNN在UWB定位中的應(yīng)用研究

宋雨昊 ，劉林，2，王平，2

（1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都 611756；2.軌道交通工程信息化國(guó)家重點(diǎn)實(shí)驗(yàn)室（中鐵一院），西安 710043）

0 引言

隨著時(shí)代的發(fā)展，人們對(duì)基于位置服務(wù)的需求是迫切的，尤其是在隧道、室內(nèi)、地下等特殊場(chǎng)景下。然而全球定位系統(tǒng)在這些特殊場(chǎng)景下并不能使用，因?yàn)樾l(wèi)星無線電信號(hào)無法穿透堅(jiān)固的墻壁和障礙物［1］。現(xiàn)有的室內(nèi)定位技術(shù)有UWB定位技術(shù)、Zigbee定位技術(shù)、藍(lán)牙定位技術(shù)、WIFI定位技術(shù)、可見光定位技術(shù)，等。UWB定位技術(shù)因?yàn)榭垢蓴_性強(qiáng)、時(shí)間分辨率高、測(cè)距精度高［2］等特點(diǎn)在主流的室內(nèi)定位技術(shù)中脫穎而出。

在UWB定位技術(shù)中，常見的定位方法可以分為位置指紋定位法和三角測(cè)量定位法兩種［3］。在實(shí)際定位過程中，多徑效應(yīng)與非視距環(huán)境的存在會(huì)對(duì)三角測(cè)量定位法產(chǎn)生很大影響［4］。而位置指紋定位法可以通過建立指紋庫，在復(fù)雜的環(huán)境中依然可以提供準(zhǔn)確的位置估計(jì)［5］。決定位置指紋定位法定位精度的核心是指紋密度與指紋匹配算法［6］。指紋匹配算法常采用WKNN算法，但其定位性能受多種因素影響，如何發(fā)揮其優(yōu)良的定位性能，是許多科研人員的研究熱點(diǎn)。

WKNN算法通常通過計(jì)算在線定位階段接收的指紋信息與離線數(shù)據(jù)庫儲(chǔ)存的指紋信息之間的“距離”來評(píng)估指紋相似性。文獻(xiàn)［7］中WKNN算法采用傳統(tǒng)的歐氏距離作為距離度量方式；文獻(xiàn)［8］中采用曼哈頓距離；文獻(xiàn)［9］中采用卡方距離。不同的距離度量方式的定位效果不同。因此分析常見的距離度量方式，找到適用于基于TOA的UWB位置指紋定位方法的最佳距離度量方式以提高WKNN算法定位性能是很重要的。除了距離度量方式的選擇，K值的選擇對(duì)WKNN的定位性能有重要影響。文獻(xiàn)［10］在K值為2～6上進(jìn)行分析，視距場(chǎng)景下K值選為5，非視距場(chǎng)景下K值選為6；文獻(xiàn)［11］在非視距場(chǎng)景下指定K值為3進(jìn)行實(shí)驗(yàn)分析；文獻(xiàn)［12］在K為1～10上進(jìn)行分析后，選取K值為3。以上文獻(xiàn)表明，不同條件下，K值的選擇各不相同，K值的大小會(huì)影響WKNN算法的性能，因此，有必要研究適合UWB定位系統(tǒng)的K值。此外，根據(jù)文獻(xiàn)［11］可知，指紋網(wǎng)格劃分對(duì)定位精度有著一定的影響。針對(duì)上述問題，本文將綜合考慮距離度量方式、K值的選取、網(wǎng)格大小三項(xiàng)指標(biāo)，把UWB測(cè)距值作為指紋信息，在非視距場(chǎng)景下對(duì)基于WKNN的UWB位置指紋定位法進(jìn)行仿真分析。

1 基于TOA的UWB位置指紋定位方法

UWB位置指紋定位法的主要思路是在待定位區(qū)域?qū)崟r(shí)采集指紋信息，通過匹配指紋數(shù)據(jù)庫中預(yù)先采集到的指紋信息來達(dá)到定位的目的。該方法一般分為兩個(gè)階段，第一階段是構(gòu)造指紋數(shù)據(jù)庫的離線采集階段；第二階段是目標(biāo)定位的在線定位階段。UWB位置指紋定位法如圖1所示。

圖1 位置指紋定位法結(jié)構(gòu)

為了減少一定的工作量，離線采集階段一般是將待定位區(qū)域按照網(wǎng)格劃分，把網(wǎng)格的中心或者網(wǎng)格的交界點(diǎn)作為采樣點(diǎn)，再進(jìn)行指紋信息的采集工作。在本文的研究中，考慮到基站與標(biāo)簽之間的到達(dá)時(shí)間信息（time of arrival，TOA）數(shù)值過小，因此將基站與標(biāo)簽之間的測(cè)距值作為指紋。離線數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)如表1所示。

表1 離線數(shù)據(jù)庫

在線定位階段利用指紋匹配算法對(duì)實(shí)時(shí)采集的指紋信息進(jìn)行匹配。本文采用WKNN算法進(jìn)行指紋匹配。WKNN算法是一種判決式方法，在匹配時(shí)，通過計(jì)算實(shí)時(shí)采集的指紋信息與離線階段構(gòu)建的指紋數(shù)據(jù)庫中的指紋信息之間的“距離”，找到相似度最高的K個(gè)采樣點(diǎn)，然后利用K個(gè)采樣點(diǎn)位置信息進(jìn)行加權(quán)處理，從而得出目標(biāo)位置，加權(quán)方式如式（1）所示。式中，D為指紋“距離”，常采用歐氏距離、曼哈頓距離、切比雪夫距離、卡方距離等距離度量方式。

假定兩個(gè)指紋向量M=（x1，x2，x3，x4），N=（y1，y2，y3，y4）。對(duì)于歐氏距離、曼哈頓距離、切比雪夫距離，D的計(jì)算如式（2）所示。

p=1時(shí)為曼哈頓距離；p=2時(shí)為歐氏距離；p=∞時(shí)為切比雪夫距離。

對(duì)于卡方距離，D的計(jì)算如式（3）所示。

2 定位算法性能分析

在本節(jié)中，將主要對(duì)非視距環(huán)境下的WKNN指紋匹配算法進(jìn)行綜合分析。實(shí)驗(yàn)仿真環(huán)境設(shè)置為2 m×6 m的二維矩形平面，基站選取為4個(gè)，標(biāo)簽為1個(gè)；基站的位置坐標(biāo)分別為基站A（0 m，0 m），基站B（6 m，0 m），基站C（6 m，2 m），基站D（0 m，2 m）。訓(xùn)練集大小根據(jù)網(wǎng)格大小而定，網(wǎng)格大小分別為0.25 m×0.25 m、0.5 m×0.5 m、0.75 m×0.75 m三種，對(duì)應(yīng)訓(xùn)練集大小分別為221組、61組、25組數(shù)據(jù)；測(cè)試集均為1000組數(shù)據(jù)。

非視距環(huán)境下，基站與標(biāo)簽之間的系統(tǒng)測(cè)距誤差符合均值為0，標(biāo)準(zhǔn)差為0.1 m的高斯分布；非視距誤差符合均值不為0的高斯分布或者指數(shù)分布。其中,非視距誤差符合指數(shù)分布時(shí)由公式（4）確定。

其中，trms為均方根時(shí)延拓展，根據(jù)文獻(xiàn)［13］可知，T約為19 ns；di為基站與標(biāo)簽之間的距離；在本文的仿真中，ε取0.5；ξ符合對(duì)數(shù)正態(tài)分布10lg(ξ)～N(0,σ)，σ取為4 dB。

2.1 距離度量方式對(duì)定位精度的影響

2.1.1 非視距誤差服從高斯分布時(shí)的影響

圖2是網(wǎng)格邊長(zhǎng)為0.25 m，基站與標(biāo)簽之間的系統(tǒng)測(cè)距誤差符合N（0，0.1 m）的高斯分布，非視距誤差符合N（0.5 m，0.2 m）的高斯分布時(shí)，最近鄰居數(shù)K與測(cè)試集均方根誤差（root mean square error，RMSE）的關(guān)系，其中K的范圍在1～20之間。根據(jù)圖2選擇RSME最小時(shí)四種距離度量方式對(duì)應(yīng)K值（K分別取10、10、9、11）進(jìn)行WKNN位置指紋定位性能分析，定位誤差累積分布函數(shù)（cumulative distribution function，CDF）如圖3所示。

圖2 最近鄰居數(shù)K與均方根誤差的關(guān)系（網(wǎng)格0.25 m）

圖3 誤差累積分布函數(shù)圖（網(wǎng)格0.25 m）

當(dāng)網(wǎng)格邊長(zhǎng)為0.25 m，基站與標(biāo)簽之間的系統(tǒng)測(cè)距誤差符合N（0 m，0.1 m）的高斯分布，非視距誤差符合均值分別為0.4 m、0.5 m、0.6 m，標(biāo)準(zhǔn)差分別為0.1 m、0.2 m的高斯分布的各種情況定位結(jié)果如表2所示。

表2 網(wǎng)格邊長(zhǎng)為0.25 m時(shí)均方根誤差分析單位：m

根據(jù)表2、圖2、圖3可以發(fā)現(xiàn)，當(dāng)網(wǎng)格大小為0.25 m×0.25 m，非視距誤差符合以上類型的高斯分布時(shí)，四種距離度量方式效果接近。

圖4是網(wǎng)格邊長(zhǎng)為0.5 m，其他仿真條件同圖2時(shí)最近鄰居數(shù)K與測(cè)試集均方根誤差的關(guān)系圖。根據(jù)圖4選擇RSME最小時(shí)四種距離度量方式對(duì)應(yīng)K值（K分別取4、5、5、6）進(jìn)行WKNN位置指紋定位性能分析，定位誤差累積分布函數(shù)如圖5所示。表3為網(wǎng)格邊長(zhǎng)是0.5 m，仿真條件同表2時(shí)各種情況下的定位結(jié)果。根據(jù)表3、圖4、圖5可以發(fā)現(xiàn)，當(dāng)網(wǎng)格大小為0.5 m×0.5 m，非視距誤差符合以上類型的高斯分布時(shí)，切比雪夫距離效果最差；歐氏距離、曼哈頓距離效果較好；卡方距離效果略好于其他三種。

圖4 最近鄰居數(shù)K與均方根誤差的關(guān)系（網(wǎng)格0.5 m）

圖5 誤差累積分布函數(shù)圖（網(wǎng)格0.5 m）

表3 網(wǎng)格邊長(zhǎng)為0.5 m時(shí)均方根誤差分析單位：m

圖6是網(wǎng)格邊長(zhǎng)為0.75 m，其他仿真條件同圖2時(shí)最近鄰居數(shù)K與測(cè)試集均方根誤差的關(guān)系圖。根據(jù)圖6選擇RSME最小時(shí)四種距離度量方式對(duì)應(yīng)K值（K分別取2、2、3、3）進(jìn)行WKNN位置指紋定位性能分析，定位誤差累積分布函數(shù)如圖7所示。表4是網(wǎng)格邊長(zhǎng)為0.75 m，其他仿真條件同表2時(shí)各種情況定位結(jié)果。

圖6 最近鄰居數(shù)K與均方根誤差的關(guān)系（網(wǎng)格0.75 m）

圖7 誤差累積分布函數(shù)圖（網(wǎng)格0.75 m）

根據(jù)表4、圖6、圖7可以發(fā)現(xiàn)，當(dāng)網(wǎng)格大小為0.75 m×0.75 m，非視距誤差符合以上類型的高斯分布時(shí)，采用卡方距離效果最好。

表4 網(wǎng)格邊長(zhǎng)為0.75 m時(shí)均方根誤差分析單位：m

2.1.2 非視距誤差服從指數(shù)分布時(shí)的影響

圖8是網(wǎng)格大小為0.5 m×0.5 m，系統(tǒng)測(cè)距誤差服從N（0 m，0.1 m）的高斯分布，非視距誤差符合指數(shù)分布時(shí)，最近鄰居數(shù)K與測(cè)試集均方根誤差的關(guān)系圖。根據(jù)圖8選擇RSME最小時(shí)四種距離度量方式對(duì)應(yīng)K值（K分別取6、6、5、8）進(jìn)行WKNN位置指紋定位性能分析，定位誤差累積分布函數(shù)如圖9所示，曼哈頓距離與卡方距離對(duì)應(yīng)的曲線在上方，說明根據(jù)曼哈頓距離與卡方距離進(jìn)行加權(quán)的效果略優(yōu)。

圖8 最近鄰居數(shù)K與均方根誤差的關(guān)系

圖9 誤差累積分布函數(shù)

表5是系統(tǒng)測(cè)距誤差符合均值為0，標(biāo)準(zhǔn)差為0.1 m的高斯分布，非視距誤差符合指數(shù)分布，網(wǎng)格邊長(zhǎng)分別為0.25 m、0.5 m、0.75 m時(shí)不同距離度量方式的性能分析。

表5 非視距誤差服從指數(shù)分布時(shí)均方根誤差分析單位：m

從以上仿真結(jié)果可以看出，非視距誤差符合以上類型的指數(shù)分布時(shí)，切比雪夫距離與歐式距離效果較差，卡方距離與曼哈頓距離效果較好。綜合非視距誤差服從高斯和指數(shù)分布情況的仿真結(jié)果可以得到，卡方距離是最佳的距離度量方式。

2.2 K值對(duì)定位精度的影響

根據(jù)2.1節(jié)的仿真結(jié)果，本節(jié)將分析距離度量方式為卡方距離時(shí)K值對(duì)定位精度的影響。從圖2、圖4、圖6和圖8可以看出，不同情況下均方根誤差最小時(shí)K值的分布如表6所示。可以發(fā)現(xiàn)，網(wǎng)格邊長(zhǎng)為0.25 m時(shí)，指紋量為221組，指紋密度約為18組/m2，K值的最優(yōu)值在10左右；網(wǎng)格邊長(zhǎng)為0.5 m時(shí)，指紋量為61組，指紋密度約為5組/m2，K值的最優(yōu)值在6左右；網(wǎng)格邊長(zhǎng)為0.75 m時(shí)，指紋量為25組，指紋密度約為2組/m2，K值的最優(yōu)值在3左右。從以上分析可以看出，網(wǎng)格密度越大，K值的最優(yōu)值越大；網(wǎng)格密度越小，K值的最優(yōu)值越小。因此，實(shí)際運(yùn)用時(shí)可以根據(jù)該規(guī)律進(jìn)行K值的選擇。

表6 最佳K值單位：m

為了進(jìn)一步驗(yàn)證K值的影響，本文仿真分析了不同K值下的CDF性能。圖10是網(wǎng)格大小為0.5 m×0.5 m，系統(tǒng)測(cè)距誤差符合N（0 m，0.1 m），非視距誤差符合N（0.5 m，0.2 m）時(shí)的定位誤差累積分布函數(shù)。圖11是非視距誤差服從指數(shù)分布，其他條件同圖10時(shí)的定位誤差累積分布函數(shù)。根據(jù)圖10和圖11可以發(fā)現(xiàn)，K為5～8時(shí)，對(duì)應(yīng)的曲線位于上方，說明K取5～8時(shí)可以使WKNN算法發(fā)揮出較好的定位效果。

圖10 誤差累積分布函數(shù)

圖11 誤差累積分布函數(shù)

從圖2、圖4、圖6和圖8可以發(fā)現(xiàn)，測(cè)試集均方根誤差，隨著最近鄰居數(shù)K的增大，先減小而后增大，說明最近鄰居數(shù)K選擇的過大或過小，均會(huì)影響定位精度。而且，最近鄰居數(shù)K過大也會(huì)增加UWB位置指紋定位法在線定位的時(shí)間。因此，K值的選取可以限制在2~10之間。

2.3 網(wǎng)格大小對(duì)定位精度的影響

非視距誤差符合均值不為0的高斯分布時(shí)，通過對(duì)表2、表3、表4的分析可知，當(dāng)系統(tǒng)測(cè)距誤差一定，非視距誤差符合相同分布，網(wǎng)格邊長(zhǎng)為0.25 m時(shí)的定位誤差的均方根誤差小于網(wǎng)格邊長(zhǎng)分別為0.5 m、0.75 m時(shí)的均方根誤差。例如：當(dāng)系統(tǒng)測(cè)距誤差符合N（0 m，0.1 m），非視距誤差符合N（0.4 m，0.1 m）的高斯分布，根據(jù)表2、表3和表4，網(wǎng)格邊長(zhǎng)為0.25 m時(shí)，定位誤差的均方根誤差為0.2031 m；網(wǎng)格邊長(zhǎng)為0.5 m時(shí)，均方根誤差為0.2310 m；網(wǎng)格邊長(zhǎng)為0.75 m時(shí)，均方根誤差為0.3195 m。

此外，由表2、表3、表4可知，當(dāng)網(wǎng)格邊長(zhǎng)一定，非視距誤差符合高斯分布時(shí)，均值不同，但標(biāo)準(zhǔn)差相同時(shí)，定位誤差均方根誤差均較為接近；且標(biāo)準(zhǔn)差較大時(shí)，均方根誤差亦較大。因此，在實(shí)際定位過程中，通過降低測(cè)距值的波動(dòng)范圍，亦可以提高定位精度。

非視距誤差符合指數(shù)分布時(shí)，通過對(duì)表5的分析可知，當(dāng)系統(tǒng)測(cè)距誤差一定，非視距誤差符合相同分布，網(wǎng)格邊長(zhǎng)為0.25 m時(shí)的定位誤差均方根誤差均小于網(wǎng)格邊長(zhǎng)分別為0.5 m、0.75 m時(shí)的均方根誤差。當(dāng)網(wǎng)格邊長(zhǎng)為0.25 m時(shí)，定位誤差均方根誤差為0.4554 m；網(wǎng)格邊長(zhǎng)為0.5 m時(shí)，均方根誤差為0.5062 m；網(wǎng)格邊長(zhǎng)為0.75 m時(shí)，均方根誤差為0.5575 m。

為了進(jìn)一步說明網(wǎng)格大小對(duì)定位精度的影響，在系統(tǒng)測(cè)距誤差符合N（0 m，0.1 m）的高斯分布，非視距誤差符合指數(shù)分布與N（0.5，0.2 m）的高斯分布，距離度量方式選定為卡方距離的情況下，增加邊長(zhǎng)分別為0.1 m，0.6 m的網(wǎng)格進(jìn)行對(duì)比分析，結(jié)果如表7所示。

表7 網(wǎng)格大小對(duì)定位精度的影響

對(duì)于固定的定位區(qū)域，從指紋量的角度出發(fā)，網(wǎng)格大小決定了指紋密度。網(wǎng)格邊長(zhǎng)小，指紋密度大；網(wǎng)格邊長(zhǎng)大，指紋密度小。根據(jù)上述實(shí)驗(yàn)結(jié)果，說明隨著指紋密度增大，提升定位精度的效果并不是很明顯；但隨著指紋密度變小，定位精度呈現(xiàn)下降的趨勢(shì)。

3 結(jié)語

本文在非視距場(chǎng)景下對(duì)基于WKNN的UWB位置指紋定位法進(jìn)行了仿真分析。仿真表明，WKNN算法采用卡方距離作為距離度量方式優(yōu)于歐氏距離、曼哈頓距離和切比雪夫距離。WKNN算法中最近鄰居數(shù)K的大小對(duì)定位精度有著很大的影響，最近鄰居數(shù)K選擇得過大或過小，均會(huì)影響定位精度。最近鄰居數(shù)K的選擇與指紋密度有關(guān)，一般可限制在2～10之間，指紋密度大時(shí)，適宜選擇在K=10附近；指紋密度中等時(shí)，適宜選擇在K=6附近；指紋密度小時(shí)，適宜選擇在K=3附近。