基于回歸近鄰成分分析和GBRT的室內定位方法*

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

（上海工程技術大學工程訓練中心，上海 201620）

0 引 言

隨著智能手機和無線網絡的廣泛應用，基于位置的服務（location-based service，LBS）應用越來越廣泛［1］。作為LBS的重要組成部分，室內定位技術在工業和商業應用中展現了巨大潛在價值，因此引起了許多研究者的關注［2］。

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

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

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

1 位置指紋定位

1.1 基本原理

位置指紋是指將每個參考點收到的所有AP信號強度作為一個特征，則每個預設參考點能夠得到不同的信號強度特征，這些得到的特征稱為位置指紋信息［7］?；赗SSI的位置指紋法實現定位分為2 個階段：離線階段和在線階段［8，9］。圖1為位置指紋定位流程。

圖1 位置指紋定位流程

1.2 離線階段

在待測區域中選擇合理的參考點，并測量每個參考的坐標，在每個參考點處采集所有AP 的RSSI，假設有n個AP，m個參考點，則最終得到的位置指紋數據庫的結構如下

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

1.3 在線階段

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

2 NCA-GBRT定位算法

2.1 離線位置指紋數據預處理

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

圖2 KF過程

2.2 改進NCA算法對原始數據特征提取

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

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

2.3 GBRT定位模型

GBRT算法預測精度高，適合低維數據，通過選擇合適的損失函數，可以降低異常值對定位精度的影響。因此，本文利用其構建通過學習NCA 特征提取后的新指紋數據與參考點位置坐標的映射關系得到最終的定位模型，如表1。

表1 構建定位模型

2.4 定位流程描述

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

圖3 本文算法定位過程

3 實驗與分析

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

圖4 測試區域收到的某個AP的RSSI

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

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

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

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

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

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

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

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

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

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

圖8 不同測試點定位誤差的比較

4 結 論

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