王斌濤，冷騰飛，王益涵，鄭家驊

（上海工程技術(shù)大學(xué)工程訓(xùn)練中心，上海 201620）

0 引 言

隨著智能手機(jī)和無線網(wǎng)絡(luò)的廣泛應(yīng)用，基于位置的服務(wù)（location-based service，LBS）應(yīng)用越來越廣泛［1］。作為LBS的重要組成部分，室內(nèi)定位技術(shù)在工業(yè)和商業(yè)應(yīng)用中展現(xiàn)了巨大潛在價(jià)值，因此引起了許多研究者的關(guān)注［2］。

近年來，研究者相繼提出了多種室內(nèi)定位技術(shù)，如基于超聲波的定位技術(shù)、基于可見光的定位技術(shù)、基于地磁的定位技術(shù)以及基于無線信號(hào)的定位技術(shù)?；跓o線信號(hào)的定位技術(shù)（幾何測距和位置指紋）由于實(shí)現(xiàn)成本較低，被最廣泛采用。常用的幾何測距定位方式有到達(dá)時(shí)間（time of arrival，TOA）、到達(dá)角（angle of arrival，AOA）以及到達(dá)時(shí)間差（time difference of arrival，TDOA）［3］。幾何測距定位方式的性能很大程度上依賴于視線條件。然而，室內(nèi)環(huán)境中信號(hào)傳播存在多徑效應(yīng)，由于多徑效應(yīng)的影響，信號(hào)傳播會(huì)產(chǎn)生噪聲，往往會(huì)使得測距值遠(yuǎn)遠(yuǎn)大于實(shí)際距離，定位精度會(huì)產(chǎn)生巨大誤差。為了避免多徑效應(yīng)和非視距誤差的影響，通常利用位置指紋定位替代幾何測距定位。位置指紋定位是一種模式匹配的方法，其主要原理是收集待定位區(qū)域內(nèi)所有潛在位置的信號(hào)特征，建立位置指紋數(shù)據(jù)庫［4］。

許多研究者針對位置指紋定位提出了各種基于機(jī)器學(xué)習(xí)的算法。其中被廣泛采用的是K 近鄰（K-nearest neighbor，KNN）算法和加權(quán)KNN（weighted KNN，WKNN）算法以及基于變異系數(shù)改進(jìn)的WKNN（VWKNN）算法［5］。這些算法基本原理是通過匹配待定位點(diǎn)的實(shí)時(shí)接收信號(hào)強(qiáng)度指示（received signal strength indication，RSSI）測量值與離線指紋數(shù)據(jù)庫里歐氏距離最小的K個(gè)參考點(diǎn)，然后取這K個(gè)參考點(diǎn)坐標(biāo)的平均值作為待定位點(diǎn)的估計(jì)位置［6］。此類算法定位精度能夠滿足基本需求，但是大型室內(nèi)場景下接入點(diǎn)（access point，AP）個(gè)數(shù)和參考點(diǎn)的個(gè)數(shù)較多，因而離線指紋數(shù)據(jù)庫規(guī)模龐大，在線定位時(shí)通常會(huì)遍歷整個(gè)離線指紋數(shù)據(jù)庫進(jìn)行參考點(diǎn)匹配，導(dǎo)致計(jì)算量激增，使得這類算法在實(shí)際定位時(shí)耗時(shí)過長。綜上，與傳統(tǒng)方法相比，基于機(jī)器學(xué)習(xí)的定位方法提高了定位精度，但這些方法在處理數(shù)據(jù)量較大且含有噪聲的數(shù)據(jù)時(shí)定位效果并不理想。由于信號(hào)噪聲的影響導(dǎo)致位置指紋與坐標(biāo)呈現(xiàn)非線性關(guān)系，此種情況下歐氏距離度量并非最優(yōu)。

為此，本文改進(jìn)了近鄰成分分析（nearest neighbor component analysis，NCA）算法，通過NCA 算法得到最佳度量，再結(jié)合漸進(jìn)梯度回歸樹（gradient boost regression tree，GBRT）算法，提出了NCA-GBRT 定位算法?？s短了訓(xùn)練時(shí)間，加快了訓(xùn)練速度，提高了預(yù)測精度。首先，利用基于距離度量學(xué)習(xí)NCA算法對離線指紋數(shù)據(jù)庫進(jìn)行特征提取并得到轉(zhuǎn)換矩陣，降維重構(gòu)后的數(shù)據(jù)比原始數(shù)據(jù)具有更好的空間特性。然后利用梯度提升回歸樹算法集成多個(gè)弱學(xué)習(xí)器得到參考點(diǎn)指紋與參考點(diǎn)坐標(biāo)的映射關(guān)系，構(gòu)建定位模型。

1 位置指紋定位

1.1 基本原理

位置指紋是指將每個(gè)參考點(diǎn)收到的所有AP信號(hào)強(qiáng)度作為一個(gè)特征，則每個(gè)預(yù)設(shè)參考點(diǎn)能夠得到不同的信號(hào)強(qiáng)度特征，這些得到的特征稱為位置指紋信息［7］?；赗SSI的位置指紋法實(shí)現(xiàn)定位分為2 個(gè)階段：離線階段和在線階段［8，9］。圖1為位置指紋定位流程。

圖1 位置指紋定位流程

1.2 離線階段

在待測區(qū)域中選擇合理的參考點(diǎn)，并測量每個(gè)參考的坐標(biāo)，在每個(gè)參考點(diǎn)處采集所有AP 的RSSI，假設(shè)有n個(gè)AP，m個(gè)參考點(diǎn)，則最終得到的位置指紋數(shù)據(jù)庫的結(jié)構(gòu)如下

式中D為離線指紋庫，包含每個(gè)參考點(diǎn)的坐標(biāo)及其所能接收到的每個(gè)AP 的RSSI，此數(shù)據(jù)庫中共有m×n個(gè)記錄；（rssi1m，rssi2m，…，rssinm）為在參考點(diǎn)（xm，ym）處接收到的n個(gè)AP的RSSI。

1.3 在線階段

在待定位點(diǎn)處測量每個(gè)AP 的RSSI，與離線階段構(gòu)建的位置指紋數(shù)據(jù)進(jìn)行匹配，得到相似度最高的樣本，樣本位置即為待定位點(diǎn)的位置。位置指紋定位問題可以概括為尋找一個(gè)映射，使得待定位點(diǎn)的指紋和位置指紋數(shù)據(jù)庫通過這個(gè)映射得到的估計(jì)值和待定位點(diǎn)的實(shí)際坐標(biāo)期望誤差最小。與數(shù)據(jù)庫進(jìn)行匹配的階段，常用的算法有確定型算法和概率型算法［10］。其中KNN算法是最常用的確定型匹配算法，其原理是比較待定位點(diǎn)的位置指紋和離線數(shù)據(jù)庫中的所有參考點(diǎn)位置指紋，計(jì)算它們之間的歐氏距離或者是曼哈頓距離等，得到前K個(gè)最相似的參考點(diǎn)，計(jì)算其平均位置的坐標(biāo)，即為待定位點(diǎn)的坐標(biāo)。

2 NCA-GBRT定位算法

2.1 離線位置指紋數(shù)據(jù)預(yù)處理

在室內(nèi)環(huán)境中，信號(hào)觀測值包含高斯噪聲和非高斯噪聲，噪聲的存在會(huì)影響定位精度［11］，因此在數(shù)據(jù)預(yù)處理過程中需要對測量得到的信號(hào)進(jìn)行濾波。常用的信號(hào)濾波方法有均值濾波、中值濾波、狄克遜檢驗(yàn)法濾波和高斯濾波等。由于卡爾曼濾波（KF）能在一定程度上削弱由于噪聲疊加造成的RSSI觀測值偏離，經(jīng)過KF算法處理后的RSSI值，具有更好的穩(wěn)定性［12］。因此，本文在構(gòu)建指紋數(shù)據(jù)庫前采用KF算法對數(shù)據(jù)進(jìn)行處理。KF算法利用最小均方誤差作為優(yōu)化估計(jì)準(zhǔn)則，采用信號(hào)和噪聲的狀態(tài)空間模型，然后使用前一時(shí)刻的估計(jì)值和當(dāng)前時(shí)刻的觀測值更新狀態(tài)變量，并計(jì)算當(dāng)前時(shí)刻的估計(jì)值，如圖2所示。

圖2 KF過程

2.2 改進(jìn)NCA算法對原始數(shù)據(jù)特征提取

當(dāng)大量的AP分布于定位區(qū)域時(shí)，待定位點(diǎn)只能接收到部分AP的信號(hào)，其他AP 由于距離待定位點(diǎn)較遠(yuǎn)，或者是信號(hào)受到墻壁等障礙物阻擋，待定位點(diǎn)接收到的部分AP的RSSI較弱，RSSI 向量中存在冗余值，且RSSI 存在時(shí)變特性，使得傳統(tǒng)算法的定位效果不理想。為了提升定位效率和精度，利用NCA算法進(jìn)行特征提取，使得特征提取后的離線指紋數(shù)據(jù)更好地反映位置指紋的空間特性。

本文使用NCA算法將原始的位置指紋數(shù)據(jù)通過最大化目標(biāo)函數(shù)得到位置指紋數(shù)據(jù)的特征。NCA算法的原理是最大化樣本點(diǎn)的分類正確數(shù)目，但本文中樣本的標(biāo)簽為連續(xù)值，因此需要對NCA算法改進(jìn)，使得NCA 算法適用于本文中的回歸問題。重構(gòu)后的指紋數(shù)據(jù)維度會(huì)影響最終定位精度，若保留的特征維度過少會(huì)導(dǎo)致定位精度較低，而特征維度過多則無法有效去除冗余信息。因此NCA 算法需要選擇合適的維度進(jìn)行特征提取。

2.3 GBRT定位模型

GBRT算法預(yù)測精度高，適合低維數(shù)據(jù)，通過選擇合適的損失函數(shù)，可以降低異常值對定位精度的影響。因此，本文利用其構(gòu)建通過學(xué)習(xí)NCA 特征提取后的新指紋數(shù)據(jù)與參考點(diǎn)位置坐標(biāo)的映射關(guān)系得到最終的定位模型，如表1。

表1 構(gòu)建定位模型

2.4 定位流程描述

本文提出的NCA 結(jié)合梯度提升回歸樹算法的定位算法過程如圖3所示。

圖3 本文算法定位過程

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

本文采用MATLAB對提出的定位算法進(jìn)行仿真，實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)［13］，該數(shù)據(jù)采集地點(diǎn)為某大樓地下停車場，測試區(qū)域面積為30 m×30 m，采樣間隔為1 s，該室內(nèi)環(huán)境一共分布有多個(gè)AP，以1 m為采樣間隔，將該室內(nèi)區(qū)域劃分成相同大小的網(wǎng)格，以網(wǎng)格交叉點(diǎn)作為采樣參考點(diǎn)，共726 個(gè)參考點(diǎn)。對每個(gè)采樣點(diǎn)的4 個(gè)方向各測量100 次，然后利用KF算法進(jìn)行處理后作為該參考點(diǎn)的最終RSSI 值，以下以其中某一AP為例，區(qū)域內(nèi)參考點(diǎn)接收到此AP的RSSI值分別如圖4所示。

圖4 測試區(qū)域收到的某個(gè)AP的RSSI

3.1 特征提取維度對定位精度的影響

本文通過對比NCA 算法降維后的維度對定位精度的影響進(jìn)行分析，以平均定位誤差作為性能指標(biāo)，結(jié)果如圖5所示。當(dāng)dim ＝2 時(shí)，只保留了原始指紋數(shù)據(jù)庫的少量特征，因此平均定位誤差達(dá)到了3.162 m。隨著dim 增大，保留原始數(shù)據(jù)的特征增加，平均定位誤差隨之下降；當(dāng)dim ＝5時(shí)，平均定位誤差相比dim ＝2 時(shí)減小了0. 462 m 達(dá)到2.7 m；而當(dāng)dim ＝10 時(shí)，平均定位誤差達(dá)到了最小，為2.66 m，隨著維度的增加，更多的冗余特征影響了定位精度，使得定位誤差逐漸增大。在本文實(shí)驗(yàn)條件下，dim ＝10為最佳的特征維度。

圖5 不同特征提取維度定位精度比較

3.2 不同特征提取算法對定位精度的影響

以累積分布函數(shù)（cumulative distribution function，CDF）為性能指標(biāo)，將本文NCA混合GBRT定位算法和局部線性嵌入結(jié)合GBRT定位算法比較，如表2。圖6展示了特征維度dim ＝10條件下兩種定位算法的CDF。如圖所示，本文算法定位過程中有60%的概率小于2 m，與此同時(shí)，對比算法僅有52%的概率小于2 m。此外，本文算法有90%的概率定位誤差小于4 m，而對比算法僅有80%。結(jié)果表明，本文算法明顯優(yōu)于對比算法。

圖6 不同特征提取算法定位精度的比較

3.3 本文算法與同類算法比較

利用CDF和參考點(diǎn)定位精度作為性能指標(biāo)，將本文算法與WKNN、VWKNN 和監(jiān)督自適應(yīng)局部判別嵌入（supervised adaptive local discriminant embedding，SALDE）+支持向量機(jī)（support vector machine，SVM）算法進(jìn)行對比，對比CDF和各個(gè)測試點(diǎn)的定位誤差，結(jié)果如表3 和圖7、圖8所示。

表3 不同定位算法對定位性能的比較

圖7 不同定位算法定位效果的比較

圖8 不同測試點(diǎn)定位誤差的比較

4 結(jié) 論

本文針對室內(nèi)無線信號(hào)波動(dòng)的影響導(dǎo)致位置指紋存在冗余噪聲因而定位精度不足的問題，提出了一種新的基于NCA和GBRT的定位算法，該算法利用NCA算法重構(gòu)指紋數(shù)據(jù)庫提取特征，增大不同參考點(diǎn)的指紋特征的差異性。再通過迭代構(gòu)造多個(gè)CART TREE，即通過每一個(gè)CART TREE的損失函數(shù)的負(fù)梯度值構(gòu)造下一個(gè)CART，通過集成多個(gè)CART TREE 得到最終的GBRT 定位模型，通過該定位模型實(shí)現(xiàn)對待定位點(diǎn)的位置預(yù)測。本文通過實(shí)驗(yàn)證明了所提出的NCA-GBRT 定位算法性能明顯優(yōu)于其他算法。