蔣天潤，尹 露，鄧中亮，王子陽

(北京郵電大學電子工程學院，北京 100876)

0 引言

室外條件下，用戶使用的定位設(shè)備主要基于全球定位系統(tǒng)(Global Positioning System，GPS)。由于室內(nèi)的接收機受到建筑物的遮擋，使得接收到的衛(wèi)星定位信號衰減很快，甚至完全無法接收到信號。隨著移動設(shè)備和無線傳感器的大量部署，關(guān)于室內(nèi)有源主動定位的研究取得了長足發(fā)展，但它在室內(nèi)定位時需要人攜帶有關(guān)的傳感器設(shè)備，使得有源定位的廣泛應用受到較大阻礙。

隨著移動互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，人們對于獲得高精度位置信息的需求愈加強烈，未來室內(nèi)定位將成為一項生活所必須的基本服務(wù)需求。目前，室內(nèi)定位技術(shù)種類繁多，主要有基于射頻識別(Radio Frequency Identification，RFID)、超聲波、紅外線和WiFi等的室內(nèi)定位技術(shù)[1]。RFID定位需要提前布置硬件設(shè)備，實現(xiàn)大范圍推廣的成本很高[2]。紅外定位技術(shù)的精度會受到室內(nèi)燈光、熱源的影響，另外室內(nèi)的各種障礙物也會遮擋紅外線，導致紅外線不能傳輸很遠的距離，以及定位誤差增大[3]。由于超聲波在空氣中傳播時衰減速度很快，距離稍遠超聲波定位技術(shù)的定位誤差就會迅速增大。無線局域網(wǎng)已在人口密集區(qū)域廣泛普及，各處的室內(nèi)都大量部署了無線上網(wǎng)設(shè)備，基于WiFi的室內(nèi)定位技術(shù)具有定位耗時短、覆蓋面積大、成本低等優(yōu)點，因此該技術(shù)成為了室內(nèi)定位研究領(lǐng)域的熱點方向。

目前基于WiFi的室內(nèi)定位研究主要基于接收信號強度指示(Received Signal Strength Indicator，RSSI)。RSSI描述了接收信號功率的大小，由于目前多數(shù)終端設(shè)備都支持獲得RSSI信息，故目前的無線通信技術(shù)都使用RSSI作為評價信道質(zhì)量的標準，從而改進通信系統(tǒng)?；赪iFi的RSSI指紋定位法將處理后的RSSI作為每個位置的指紋特征，從而開展基于位置指紋庫的指紋定位。RSSI是多條路徑信號的簡單疊加[4]，因此RSSI并不能充分描述子信道受環(huán)境的干擾程度。此外，盡管單個信道的信號波動較小，但多條信道中信號疊加的RSSI波動范圍甚至達到了5dB[5]。單一使用RSSI作為信號特征進行指紋定位不能滿足高精度、高穩(wěn)定性的室內(nèi)定位需求。

相較于RSSI，信道狀態(tài)信息(Channel State Information，CSI)能夠更好地描述多徑信道，區(qū)分來自多個信道的多徑信號，在靜態(tài)環(huán)境下具有較好的穩(wěn)定性。CSI的一個數(shù)據(jù)分組中同時包含著多個子載波的幅頻響應和相頻響應。在室內(nèi)定位中以子信道的多維矩陣對單一的RSSI進行擴展來構(gòu)建格點特征，由此可以獲得更高的定位精度。近年來，Inter和Atheros網(wǎng)卡供應商對其部分網(wǎng)卡固件程序進行了處理，并有相關(guān)組織開源了對應的軟件開發(fā)包，使得可以對Linux系統(tǒng)以及Windows系統(tǒng)下的網(wǎng)卡開源驅(qū)動程序進行修改，利用調(diào)試模式來獲取某些無線網(wǎng)卡的CSI數(shù)據(jù)。使用大量部署的基于802.11n標準的WiFi路由設(shè)備可以獲得CSI[6]。基于CSI的指紋定位需要的額外硬件設(shè)備較少，實現(xiàn)成本低，具有廣泛的應用前景。

1 CSI與指紋定位算法

1.1 信道狀態(tài)信息

目前，使用裝配Intel 5300網(wǎng)絡(luò)適配器的普通WiFi設(shè)備能夠獲得一個采樣個數(shù)為30的CSI信息，利用兼容IEEE802.11.n的無線網(wǎng)卡從接收的數(shù)據(jù)包中提取一組CSI，每組CSI代表一個正交頻分復用子載波的幅度與相位,如式(1)所示

(1)

1.2 指紋定位法

指紋定位法主要包括2個階段。離線訓練階段即數(shù)據(jù)采集和處理過程，該過程主要工作是采集格點信息，將該信息處理后構(gòu)建為格點特征，常用的格點特征包括相位和幅度等；實現(xiàn)格點位置與格點特征的映射；建立無線地圖和指紋定位數(shù)據(jù)庫。

在在線定位階段，實時采集待定位點的格點特征，輸入至定位服務(wù)器，服務(wù)器將定位端實時上報的數(shù)據(jù)與離線階段建立的位置指紋庫的數(shù)據(jù)進行匹配，計算出實時數(shù)據(jù)最佳匹配的參考點。在線階段的主要思路是依賴一定的準則選擇與實時數(shù)據(jù)最為接近的參考點。

1.3 研究現(xiàn)狀

文獻[7]表明WiFi的CSI具有更高的時間穩(wěn)定性，并具有從多徑效應中獲益的能力，因此適用于準確的存在檢測和定位。文獻[8]表明由于室內(nèi)環(huán)境的復雜性對多徑信號傳播的影響，難以建立精確的信號傳播模型，因此基于CSI的指紋定位法優(yōu)于基于傳統(tǒng)傳播模型的室內(nèi)定位方法。文獻[9]基于CSI的子信道頻率的不同，用合并且求均值后的5個子載波的CSI代替原來的30個子載波的CSI，并對多根天線的CSI求平均值處理，提出了一種基于后驗概率的指紋定位算法。Qian K.等[10]利用CSI導出運動誘發(fā)的多普勒頻移，并提取出該頻移用于確定運動方向。

2 采集CSI信息與制作指紋庫

在北京郵電大學的新科研樓內(nèi)選擇一間10m×10m的實驗室，室內(nèi)放置有大量物品以及人員走動。根據(jù)地磚將室內(nèi)劃分成1m×1m的方格，在每個參考點測量CSI數(shù)據(jù)，每個格點的CSI數(shù)據(jù)存儲在若干個數(shù)據(jù)包中，如圖1所示。

圖1 數(shù)據(jù)采集環(huán)境示意圖Fig.1 Data collection environment

經(jīng)過上述操作獲得的原始CSI數(shù)據(jù)含有高頻噪聲，需要對原始CSI數(shù)據(jù)進行低通濾波處理。使用h表示該巴特沃斯濾波器的傳遞函數(shù)。單個數(shù)據(jù)包中的CSI數(shù)據(jù)為H(1*30)，濾波后的矩陣記為H′(1*30)

H′=h*H

(2)

(3)

3 算法關(guān)鍵參數(shù)的測試與分析

3.1 測試KNN與wKNN算法

K最近鄰(K-Nearest Neighbor，KNN)算法，K表示距離自己最近的k個數(shù)據(jù)樣本[11]。KNN算法使用的相似度量是曼哈頓距離或歐式距離，該算法所選擇的鄰居都是已經(jīng)正確分類的對象。該算法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

在實際的生產(chǎn)實踐中，KNN算法的缺陷是找到的近鄰并不是實際意義上的近鄰。特征向量之間一般有較大可能性是相關(guān)的，最近距離的求解過程中沒有考慮特征之間的關(guān)系，故距離的計算不夠準確，從而影響了定位的準確度。為了解決以上問題，使用加權(quán)K最近鄰(weighted K-Nearest Neighbor，wKNN)算法[12]。

將每一鄰居樣本的坐標與對應權(quán)重相乘，結(jié)果相加[13]，求出總和后，將結(jié)果除以全部權(quán)重之和。估計坐標的計算方法如式(4)所示

(4)

式中，Di表示鄰居樣本的坐標，wi表示近鄰樣本的權(quán)重，f(x)是預測的坐標結(jié)果。

wi=1/(distance+const)

(5)

式中，權(quán)重wi是距離數(shù)值加上一個常數(shù)的倒數(shù)。

在圖2和圖3中，藍色虛線代表了測試所走過的真實路徑，*號代表在藍色真實路徑上均勻取點所對應的定位結(jié)果。在K=5，離線指紋庫容量為100，在線數(shù)據(jù)集容量為35時，KNN定位誤差是2.732m，wKNN定位誤差是2.651m。

圖2 KNN定位結(jié)果圖Fig.2 The locating result of KNN algorithm

圖3 wKNN定位結(jié)果圖Fig.3 The locating result of wKNN algorithm

在離線數(shù)據(jù)集容量為100,在線數(shù)據(jù)集容量為35時，改變K值，觀察其對定位誤差的影響。

從圖4可以看出，兩種算法的定位誤差隨K的變化曲線有一定的相似性。在K<9時，兩種算法的定位誤差隨K的增大而減??；在K>9后，兩種算法的定位誤差隨K的增大反而逐漸增大，但此時的最大定位誤差仍小于K<9時的最大定位誤差。

圖4 兩種算法定位誤差隨K值變化圖Fig.4 The tendency chart of positioning error with K

OFDM系統(tǒng)中的每個子信道是相互獨立的[14]，在CSI中，理論上每個子信道的幅度也是相互獨立的，即在本次測試中理論上各特征向量之間是不相關(guān)的。因此，使用wKNN算法對定位精度的改善有限，這也解釋了以上兩種算法的定位誤差隨K的變化趨勢較為相似的原因。

較小的K值會導致鄰居不夠，定位精度受此影響[15]，因此K<9時定位誤差隨K的變化趨勢如上所示；但是過大的K值會導致不屬于同一類的點也被分入鄰居內(nèi)，使得定位誤差增大，這是K>9后定位誤差隨K增大而增大的原因。

4 三種算法穩(wěn)定性測試與分析

4.1 算法評價指標與樣本集擴充方法

通常評價一種定位算法性能的依據(jù)是該算法的定位精度，但該評價依據(jù)并沒有考慮到在線測量數(shù)據(jù)增加時，該種算法的穩(wěn)定性問題。因此本文提出了一種評價KNN、wKNN和隨機森林算法優(yōu)劣的依據(jù)：三種算法定位時間的穩(wěn)定性和定位精度的穩(wěn)定性。

某種算法的運行時間在一定程度上反映了該算法的計算量和資源占用的多少，由于算法的運行時間具有一定的時變性和不穩(wěn)定性，選取運行時間的標準差占平均運行時間的百分比作為評價標準。定位精度的穩(wěn)定性可以直接使用在線樣本容量為100～20000時定位精度的平均值與標準差進行評價。

如果將10m×10m的辦公區(qū)域劃分為0.5m×0.5m的方格，則指紋庫中最多只有400個點的指紋信息。0.5m的方格長度相較于超過2m的定位誤差很小，可以認為在該10m×10m的區(qū)域中，至多只存在400個定位結(jié)果，那么，在線數(shù)據(jù)集所有可能點的坐標都在這400個點中產(chǎn)生。因此，樣本容量的擴充方法如圖5所示，將新的在線樣本集逐個編號，每次從以上的原始樣本集中隨機取樣，重復400次，將400個取樣結(jié)果全部用來擴充原始樣本集，將擴充的結(jié)果作為新樣本集，直至樣本容量符合實驗要求。

圖5 樣本集擴充方法Fig.5 Sample capacity expansion method

4.2 穩(wěn)定性測試與分析

測試軟件均使用Pycharm。在線數(shù)據(jù)集的樣本數(shù)量為100～20000。KNN與wKNN算法中K=6，隨機森林算法中決策樹數(shù)量為110，max_features=0.45，max_depth=15。

從圖6和表1中可以看出，根據(jù)定位誤差的標準差對比，隨機森林算法的定位誤差的波動性最小，KNN算法最大。在樣本容量逐漸增加的過程中，隨機森林算法定位誤差最為穩(wěn)定。同時，隨機森林的定位誤差最小，性能也最好。

從三種算法運行時間的標準差占平均運行時間的百分比來看，隨機森林是3.67%，wKNN是5.31%，KNN是9.87%。隨機森林的運行時間穩(wěn)定性要高于KNN和wKNN算法。

圖6 三種算法運行時間與定位誤差隨樣本容量變化圖Fig.6 The tendency chart of positioning time and positioning error with sample size of three algorithms

表1 三種算法評價指標對比

5 結(jié)論

1)本文介紹了CSI和指紋定位法的概念，分析了使用CSI進行指紋定位的優(yōu)勢，闡述了指紋庫的構(gòu)建過程和定位方法。

2)分析了KNN和wKNN算法中關(guān)鍵參數(shù)K對定位誤差的影響。結(jié)果表明，在K較小時，增大K可以使用更多相關(guān)鄰居來計算定位結(jié)果，進而提高定位精度；但過大的K值會導致原本不相關(guān)的鄰居加入鄰居隊列，也會使定位誤差增大。

3)在線樣本集容量增加時，測試了KNN、wKNN和隨機森林算法的運行時間和定位精度的穩(wěn)定性，結(jié)果表明，隨機森林算法不僅定位精度最高，而且定位時間與定位精度的穩(wěn)定性最好。