謝東良

一、前 言

（一）背景與研究意義

近年來，隨著移動互聯(lián)網(wǎng)以及位置服務(wù)技術(shù)的發(fā)展，室內(nèi)定位技術(shù)也在更新?lián)Q代。具有位置感知功能的應(yīng)用在各種場合廣受歡迎，手機等智能設(shè)備的涉及范圍也變得越來越廣泛。例如，用戶可以獲取商家的某個商品的位置信息，在琳瑯滿目的商品中準確找到目標，甚至找到搞促銷活動的店家得到優(yōu)惠價格；在機場或火車站找不到洗手間，室內(nèi)定位可以提供幫助；在博物館里想找自己喜歡的版塊，借助室內(nèi)定位確定就能幫忙；在起火大廈里，消防員能室內(nèi)定位求助者的位置；在會議室開會時，手機若能識別出所處的位置并自動開啟靜音，能為粗心的人提供很大幫助；逛商場時想貨比三家，對商品猶豫不決時，手機若能給拍下照片的商品自動打上標簽，能方便我們下次尋找，從而給商家吸引更多的回頭客。這些功能看似不太起眼，卻能極大地方便和改善我們的生活質(zhì)量，讓人們生活得更加便捷。但是，當前使用較多的定位技術(shù)，如GPS衛(wèi)星定位以及GSM（全球移動通信系統(tǒng)）基站定位技術(shù)，還達不到進行室內(nèi)定位所需求的定位精度，而且在信號大幅度衰減的地方，例如被眾多高層建筑遮擋的區(qū)域及地下室，甚至沒辦法進行定位。

現(xiàn)在一些定位技術(shù)，如短距離無線通信定位技術(shù)已經(jīng)開始在室內(nèi)定位中廣泛應(yīng)用。在工業(yè)和醫(yī)療等對定位精度有嚴格要求的領(lǐng)域，基于超寬帶和超聲波的定位技術(shù)也被頻繁使用，但這種定位精度高的方法存在很大的缺憾，信號衰減快，設(shè)備成本高。又如基于藍牙的定位技術(shù)——NOKIA公司的藍牙4.0協(xié)助定位系統(tǒng)，它的定位精度很高（約為1～2m），但其信號衰減距離只有10米左右，為了保證信號強度，藍牙信號發(fā)送器的安裝間隔要很短，因此成本是一個很大的問題。雖然這些定位技術(shù)的定位精度都比較高，但是繁瑣復(fù)雜，同時設(shè)備成本也較高，導(dǎo)致這些技術(shù)并不適合大范圍地實際應(yīng)用。

隨著網(wǎng)絡(luò)通訊技術(shù)的不斷革新，WiFi熱點設(shè)施在各大公共場所中廣泛覆蓋，這使得通過WiFi信號實現(xiàn)室內(nèi)外的無縫定位成為現(xiàn)實[1][2]。對于WiFi定位技術(shù)，通過純軟件可實現(xiàn)常用的基于RSS信號指紋的定位方法，這種方法相對于其他方法，如基于信號到達時間差等，成本較低。方法是在離線階段（也就是準備階段）把待測點接收的來自多個AP的RSS與其對應(yīng)的MAC地址對應(yīng)保存起來，并與該待測點的實際位置坐標進行匹配。定位時，將手機端實時掃描的位置指紋與離線階段建立的指紋庫中的指紋匹配，就可以獲得手機的位置。

WiFi指紋法定位與其他室內(nèi)定位技術(shù)相比較，具有實施方法簡便、成本低、精度較高的優(yōu)點，并且隨著WiFi熱點設(shè)施覆蓋的增多，基于WiFi的室內(nèi)定位研究將有著重大的現(xiàn)實意義。

（二）研究現(xiàn)狀與發(fā)展趨勢

目前，國內(nèi)幾乎所有通訊和移動設(shè)備都支持WiFi連接，含有WiFi熱點的室內(nèi)場合非常多，辦公樓、火車站等很多大型公共場所都有WiFi信號覆蓋，因此把wifi應(yīng)用在室內(nèi)定位技術(shù)中也順勢成為主流。目前主要有以下三種基于WiFi技術(shù)的室內(nèi)定位方案。

1.接收信號強度定位法

接收信號強度定位法，也稱RSS三邊測量定位。這是目前應(yīng)用最廣泛的室內(nèi)定位技術(shù)。該方法利用已知信號的衰弱模型和接收信號強度RSS，以已知參考點與待測點的距離為半徑畫圓，有多個參考點就可以畫出多個圓，這些圓的重疊部分就是待測目標的大致位置。該方法的優(yōu)點是只要采集足夠的WiFi指紋數(shù)據(jù)庫就可以實現(xiàn)，且成本低廉，但相對的定位精度也只有10～20m，局限性較大。

2.基于接收信號強度RSS的指紋定位法

該方法是離線階段采集各個參考點的信號強度RSS并建立指紋數(shù)據(jù)庫，將待測接收信號強度與數(shù)據(jù)庫中各個參考點的信號強度特性進行對比，匹配度最高的參考點位置便是待測目標的位置。這種方法的優(yōu)點是定位精度比較高，能精確到3～5m，但與第一種方法正好相反，如果要大規(guī)模應(yīng)用，那么需要采集的數(shù)據(jù)也會非常龐大，成本十分高。

3.基于信號傳播距離的測量法

這種方法和第一種方法有些類似，無線信號往返于兩個節(jié)點之間，測量其飛行時間并推算節(jié)點間的距離，以參考點和待測點之間的距離值為半徑畫出圓，得到多個圓的重疊位置，即得到待測點的位置。該方法優(yōu)點是定位精度可以低于1m，非常之精準，但同時要求也高，現(xiàn)有的設(shè)備大多無法支持這種精度，因而不太可能進行大范圍應(yīng)用。

上述三種基于WiFi的定位方案各有利弊，優(yōu)缺點明顯，而要想廣泛應(yīng)用于日常生活中，需要做到精度與成本兼顧。下文將會采用基于接收信號強度RSS的指紋定位法的改進方法進行研究，以達到兼顧二者的目的。

總的來說，如今室內(nèi)定位技術(shù)正在高速發(fā)展，目前可預(yù)測的趨勢如下：

第一，藍牙BLE定位技術(shù)將會普及。藍牙室內(nèi)定位技術(shù)雖然不常出現(xiàn)在大眾視野中，卻也在不斷發(fā)展。在零售業(yè)，基于iBeacon技術(shù)的信息推送服務(wù)引起了極大重視，今后BLE技術(shù)會在此基礎(chǔ)上更好地服務(wù)用戶。

第二，混合定位方法將成為主流。很多方案將傳感器技術(shù)與WiFi技術(shù)融合到一起，豐富單一定位技術(shù)無法實現(xiàn)的功能，減小其局限性。Google、Broadcom等都給出了定位技術(shù)混合解決方案[3]，未來也會出現(xiàn)更多混合方案來滿足人們室內(nèi)定位的訴求。

第三，更多地進行低功耗優(yōu)化。通過專有的定位處理引擎減少對應(yīng)用處理器的喚醒，以此降低功耗，同時利用定位技術(shù)混合方案在不損失精度的情況下選擇最低功耗的定位技術(shù)等。

第四，更好地用于位置服務(wù)。其不需要準確位置便能通過附近的感知發(fā)現(xiàn)周圍設(shè)備，同時產(chǎn)生推送，這可以作為定位技術(shù)一個非常好的補充，相關(guān)技術(shù)有BT/BLE、WiFi Direct、NFC等。

第五，室內(nèi)地圖會不斷完善，數(shù)據(jù)庫也會逐步積累，未來室內(nèi)定位技術(shù)的性能將得到很大提高。

（三）WiFi室內(nèi)定位技術(shù)研究現(xiàn)狀

由于基于距離測量的方法精度太低，因此很多研究都在轉(zhuǎn)向基于信號指紋統(tǒng)計模型的定位算法。目前這方面已有不少研究成果，如從最早的最近鄰（NN）算法，到后面陸續(xù)提出的K最近鄰KNN算法、WKNN、貝葉斯概率算法、神經(jīng)網(wǎng)絡(luò)算法、支持向量機算法等；而在定位系統(tǒng)方面也有不少可鑒成果，較典型的有 Radar、eorus、Nibble與 Weyes等室內(nèi)定位系統(tǒng)[3]。

Radar系統(tǒng)是2000年微軟公司研究的一個基于位置指紋定位的實驗項目。該系統(tǒng)的定位過程分為兩個階段：離線和在線。離線階段，Radar系統(tǒng)在待定位的區(qū)域內(nèi)設(shè)置許多分布其中的點，采集各個點接收到的AP的RSS數(shù)據(jù)，這些點就是位置指紋的參考點，包含了位置坐標、RSS等信息。離線階段完成了對指紋參考點的創(chuàng)建。在獲取每個點上的接收信號RSS時，Radar系統(tǒng)采用多次測量取平均值或中值的方法，其中每個指紋節(jié)點的信號強度矢量均來自定位場景中的多個AP。在線定位階段，Radar系統(tǒng)首先由移動終端節(jié)點獲取RSS矢量并將其發(fā)送至定位服務(wù)器，然后服務(wù)器搜索指紋數(shù)據(jù)庫，并根據(jù)離線階段建立的指紋參考點Radio Map來完成對移動終端的定位。其中Radar系統(tǒng)內(nèi)采用的匹配算法有NNSS（即最近鄰法）與NNSS-AVC（即K近鄰法）兩種。而eorus定位系統(tǒng)使用概率模型來創(chuàng)建信號數(shù)據(jù)庫，并以接收信號強度RSS為位置參考點的指紋數(shù)據(jù)。該系統(tǒng)在采集指紋參考點的RSS矢量數(shù)據(jù)時不直接取其均值，而是建立每個AP的RSS在指紋參考點上的概率分布，并以此分布值來建立Radio Map。在線定位時，該系統(tǒng)基于Radio Map位置集的分簇方法來減少計算量并提高系統(tǒng)的定位速度。實際上，因為一個固定AP覆蓋的范圍有限，因此不需要在整個定位區(qū)域內(nèi)進行匹配搜索，而只需在定位時獲取有效AP的列表，并在這個列表中AP的覆蓋范圍內(nèi)進行搜索定位，不僅提高了定位速度，而且兼顧了實時性。數(shù)據(jù)顯示該系統(tǒng)定位精度在2.13m內(nèi)。Nibble定位系統(tǒng)并非采用RSS作為指紋數(shù)據(jù)，而是采用信噪比（SNR）作為信號空間矢量的樣本，以接收信號的信噪比來建立指紋參考點的Radio Map，因為比起信號強度，信號的信噪比的位置特征更明顯，能更好地描述位置。與eorus系統(tǒng)類似，Nibble系統(tǒng)也采用概率模型來建立信號空間，但不同的是該系統(tǒng)采用貝葉斯網(wǎng)絡(luò)來創(chuàng)建信號空間的概率分布圖與指紋參考點的Radio Map。該系統(tǒng)較適合對定位精度要求不高的位置服務(wù)使用，待測位置的點粒度一般被定義為較大的區(qū)域，在測試環(huán)境中的定位精度能達到97%。

綜上所述，以WiFi信號的各種特征值作為指紋的技術(shù)已經(jīng)得到了不少的研究，而WiFi指紋定位技術(shù)本質(zhì)上是一種歸類技術(shù)，即用定量的勘測數(shù)據(jù)對信號特征的分布進行模式擬合，得到一個特定的模型。在實際應(yīng)用時將被定位點信號的指紋特征數(shù)據(jù)代入模型中計算其方位，因此可以用機器學習技術(shù)加以實現(xiàn)。隨著機器學習工具的不斷進步，WiFi指紋的定位模型實現(xiàn)和優(yōu)化變得更為簡單。本文重點探討用機器學習算法和RSS指紋實現(xiàn)WiFi指紋定位的方法，并給出一種旨在降低設(shè)備相關(guān)性的改進方案。

二、關(guān)鍵技術(shù)研究

（一）位置指紋的含義及其組成

1.位置指紋法的基本概念

信號的多徑傳播對周圍會表現(xiàn)出非常強的依賴性。對于任意位置，信道的多徑結(jié)構(gòu)在該位置上是唯一的，終端發(fā)射的無線電波經(jīng)過反射和折射，產(chǎn)生與周圍環(huán)境密切相關(guān)的特定模式的多徑信號，這樣的多徑特征可以認為是該位置相應(yīng)于該特征的“指紋”?？梢哉f，“位置指紋”是一種由無線信號傳播時經(jīng)反射、折射、散射等現(xiàn)象后生成的，和傳播環(huán)境有關(guān)的獨特信號[4]。每個特有的位置特征都可以表示該位置的“指紋”。

2.位置指紋的組成

位置指紋可以分為很多種類型，凡是能有助于區(qū)分不同位置的、獨一無二的位置特征都可以作為一個位置指紋。例如進行通信時信號往返的時間或延遲、從基站或熱點設(shè)施傳播來的信號的RSS、傳播信號的多徑結(jié)構(gòu)等，都是“位置指紋”，這也是最常用的信號特征。

（1）多徑傳播

我們把具有較大載波頻率信號的傳播軌跡近似地看成射線。射線在地板、天花板和走道的墻壁上會進行反射，碰到凹凸不平的障礙物邊緣會發(fā)生衍射，碰到石子、樹葉等較小的障礙物會發(fā)生散射。同樣的位置能接收到從固定發(fā)射源發(fā)出的信號經(jīng)過多條不同傳播路徑傳來的混合信號，因此一個位置上的多條不同射線都有不同的信號強度，信號到達時間也不盡相同。到達時間差由射線的傳播距離決定，信號強度則由傳播路況和傳播距離共同決定。每條到達接收器的射線稱為該信號的一個多徑分量，我們說的多徑結(jié)構(gòu)便是指這一組射線的信號強度和到達時間差，也可稱作功率時延分布。

圖1是一個經(jīng)典的功率時延分布圖，包含了6個多徑分量，功率和時延分別為β1、β2、β3、β4、β5、β6和τ1、τ2、τ3、τ4、τ5、τ6。

圖1 功率時延分布圖

對于帶寬很大的信號，不同多徑分量可以在接收器上進行處理。Ahonen和Eskelinen提出了用這種方法定位3G UMTS網(wǎng)絡(luò)中的手機[5]。研究結(jié)果表明，在接近67%的情況下，這種方法測出的定位精度小于25m，在95%的情況下定位精度可以達到188m，如此高的定位性能滿足了FCC對定位的E-911要求。

（2）接收信號強度RSS

RSS為Received Signal Strength，即接收信號強度。無線通信設(shè)備運行中必然產(chǎn)生信號，因此獲取RSS信號并不難，接收器的位置決定了信號的RSS和接收功率的值。帶寬對RSS造成的影響不大，因此RSS作為信號特征廣受歡迎，被各種定位技術(shù)所使用。

假定一個固定信號發(fā)射源，在離它不同距離的位置上的平均RSS的衰減和距離的對數(shù)成正比，在最簡單的情況下，RSS可以表示為：

式中α稱為路徑損耗指數(shù)，Pt是發(fā)送功率，K是一個常數(shù)，其值由周圍環(huán)境和頻率決定，d表示移動設(shè)備到固定信號發(fā)射源的距離。手機等移動設(shè)備和基站之間的距離可以用RSS大致估算，然而基于RSS測量距離的三邊角方法卻不太可行。這是由于周圍環(huán)境具有不可控性、復(fù)雜性，RSS的浮動范圍會很大，得出的定位結(jié)果誤差較大。

但是，本文研究的WiFi指紋定位卻可以利用RSS進行計算。因為一個移動設(shè)備能同時接收到來自多個發(fā)射源的信號，相對的多個固定的基站也能接收到同一移動設(shè)備的信號，因此我們可以將來自多個固定發(fā)射源或者多個接收器的RSS，組成一個能夠作為“位置指紋”的RSS向量。目前許多WiFi網(wǎng)卡都能夠測出來自多個AP點的RSS，并表示為一個0到100的數(shù)值。現(xiàn)在很多室內(nèi)場景如商場、機場，手機通常會安置多個不同AP，因此使用來自多個AP的RSS作為位置指紋可行性非常高，后文將會以此為基礎(chǔ)進行研究。

（二）位置指紋定位方法

WiFi指紋定位過程一般分兩個階段實現(xiàn)：離線采樣階段和在線定位階段[6]。

離線采樣階段：在待定位區(qū)域進行合理的采樣，采樣點的分布要平均，將每個采樣點的接收信號強度RSS、MAC地址等位置信息記錄并保存下來，作為指紋信息存儲到數(shù)據(jù)庫中，這就建立了位置指紋數(shù)據(jù)庫。數(shù)據(jù)庫中的數(shù)據(jù)要盡可能準確，因為其準確性決定了定位的精確程度。

在線定位階段：利用手機等設(shè)備在待測點測得AP的信號強度和MAC物理地址，然后通過相應(yīng)的匹配算法，搜尋數(shù)據(jù)庫中與測量點相匹配的數(shù)據(jù)，以此獲取用戶的當前位置。

此外，室內(nèi)定位得到的位置坐標通常指當前定位環(huán)境中一個局部坐標系內(nèi)的坐標，而不是經(jīng)緯度。目前，基于位置指紋的定位算法主要分為確定型和概率型，前者的計算效率較高，后者的定位精度較高，但是計算量較大。

（三）位置指紋定位算法

1.最近鄰法

最近鄰法（NN）是最基本的指紋定位算法。NN算法在定位時，移動終端節(jié)點首先獲取AP熱點發(fā)射的信號強度，記為S=(S1，S2…，Sn)，其中n為AP的個數(shù)，然后將此信號強度S與指紋數(shù)據(jù)庫中的指紋數(shù)據(jù)Fi=(Fi1，F(xiàn)i2…，F(xiàn)in)進行匹配，從而獲取移動終端

式中：Di為移動終端接收AP接入點發(fā)射的信號強度S與第i個指紋參考矢量Fi之間的距離；Sj為移動終端接收第j個AP熱點發(fā)送的信號的強度；Fij為第i個指紋矢量Fi中來自第j個AP發(fā)送的信號的強度，l為指紋參考點的個數(shù)；q=l是代表曼哈頓距離，當q=2時代表歐幾里得距離，在實際定位中可根據(jù)自己的需求與定位精度來選取q的取值。實驗表明，NN算法的定位精度并不是隨q值的增大而提升，一般情況下q=2時定位效果較佳，故本文中選取q=2。

2.K近鄰法

K近鄰算法（KNN）是在最近鄰法上進行改進的，它們之間的區(qū)別在于KNN算法在匹配指紋數(shù)據(jù)庫時，并不是選取與移動終端接收信號強度S=(S1，S2…，Sn) 最 近 的 那 個 指 紋 數(shù) 據(jù)Fi=(Fi1，F(xiàn)i2…，F(xiàn)in)，而是獲取與S距離最近的K（K≥2）個指紋數(shù)據(jù)矢量，再通過計算這K個指紋參考點的平均坐標（X，Y），并將其作為移動終端的位置信息，在計算矢量距離時通常采用歐幾里得距離來計算，其定位公式如下所示，其中在式（4）中（Xi，Yi）是第i個指紋參考點的位置坐標。的位置信息。NN算法在匹配時采用下式中的方法，通過計算S與Fi之間的距離，獲取與S距離最小的那個位置指紋Fi，并以Fi的位置坐標（Xi，Yi）作為移動終端的定位結(jié)果。表達式為：

3.K加權(quán)近鄰法

K加權(quán)近鄰法（WKNN）與K近鄰法不同的是，其在選取K（K≥2）個指紋參考點后，并不是直接將這K個指紋參考點對應(yīng)的位置坐標的均值作為移動終端的定位結(jié)果，而是將每個指紋參考點對應(yīng)的位置坐標乘上一個加權(quán)系數(shù)，然后將這K個指紋參考點位置坐標的加權(quán)和作為移動終端的定位結(jié)果。WKNN定位公式如下式所示。

其中di為移動終端的RSS與第i個指紋數(shù)據(jù)之間的距離，其采用式（3）中計算方法，ε為一個很小的正常數(shù)，為防止式中除數(shù)等于0，本文取ε=0.0001是第i個指紋參考點對應(yīng)的位置坐標；為WKNN算法的定位輸出結(jié)果。

本章研究了WiFi指紋定位技術(shù)中的各種關(guān)鍵技術(shù)問題，下面的章節(jié)將采用RSS作為指紋進行仿真研究。

三、方案設(shè)計

（一）RSS數(shù)據(jù)獲取方案

通常情況下都會以實際測量的數(shù)據(jù)進行定位算法或模型的性能分析和驗證，來建立指紋數(shù)據(jù)庫。但這種方法費時費力、數(shù)據(jù)不全面、靈活性不高，采用仿真的方法來獲得RSS數(shù)據(jù)能妥善解決這些問題。本章主要介紹射線跟蹤技術(shù)的基本原理[7]，并以此為基礎(chǔ)計算出用于定位仿真的RSS數(shù)據(jù)。利用這個方法并結(jié)合實地采樣的少量數(shù)據(jù)，得到位置指紋庫與測試數(shù)據(jù)，測試數(shù)據(jù)將用來對后文的定位算法進行驗證與評估。

1.射線跟蹤技術(shù)

信號在沒有障礙物的自由空間中，會從發(fā)射源呈球面狀發(fā)射出去，信號的強度RSS（也可認為是信號的功率P）和傳播距離的平方呈反比

那么RSS衰減應(yīng)與距離的對數(shù)呈正比。假設(shè)已知一個參考距離d0以及這個距離上的RSS為RSS(d0)，那么便得出最常見的對數(shù)距離損耗模型:

在自由空間中n=2。圖2的黑線是一組在走廊中測量的實際數(shù)據(jù)，其波動是由于信號在傳播過程中遇到環(huán)境干擾引起的；紅線則是用對數(shù)距離損耗模型計算的擬合結(jié)果?？梢钥闯鲞@個模型雖然可以反映總體趨勢，但在實際的室內(nèi)傳播環(huán)境下由于存在多徑傳輸，曲線并不會這么理想。

圖2 信號強度與傳播距離模型

2.多徑傳播技術(shù)

為了考慮多徑傳輸問題，這里將WiFi信號的電磁波傳播近似為射線進行分析。對于一個自由空間中的固定發(fā)射源，可以利用對數(shù)距離衰減模型計算各個位置的RSS。在復(fù)雜的環(huán)境下，信號可以遇墻發(fā)生反射，未反射的信號會與反射的信號疊加，為模擬實際中測量到的這種復(fù)雜信號情況，在射線跟蹤技術(shù)中，通過計算出發(fā)射點與接收點之間的多條傳播路徑，對各個路徑的信號進行分析，一般包括信號強度、相位在多次反射或繞射下的計算，然后疊加得到接收點上的信號。

現(xiàn)假設(shè)將一個發(fā)射源AP放置在一個空曠房間左側(cè)的角落，一個接收器放在房間的中央，這樣接收器收到這個AP的信號中包含了來自1條直射路徑的信號與6條經(jīng)墻壁反射的信號。理論上可以計算出任意一點的RSS值，即有6個AP時每個位置點可以分別計算出6個RSS。

（二）系統(tǒng)設(shè)計

1.界面設(shè)計

圖3 定位顯示界面設(shè)計

本系統(tǒng)界面采用簡潔明了的風格（見圖3）。主界面頂部左側(cè)的按鈕表示是否處在定位狀態(tài)，若WiFi未打開則顯示“定位關(guān)閉”。頂部右側(cè)的按鈕對應(yīng)保存定位數(shù)據(jù)，將定位結(jié)果存儲到數(shù)據(jù)庫中。

2.軟件方案設(shè)計

（1）離線階段（勘測階段）

用射線跟蹤技術(shù)仿真模擬出AP信號在房間的運動軌跡，獲取RSS值，通過KNN算法建立數(shù)據(jù)準確的位置指紋數(shù)據(jù)庫。具體流程見圖4。

圖4 離線階段

（2）在線階段

軟件運行時，應(yīng)首先確認WiFi熱點是否為開啟狀態(tài)，若已開啟則開始進行定位。定位階段利用手機在待定位點檢測的AP信息，通過相應(yīng)的模型算法，在指紋數(shù)據(jù)庫中搜索與待測點相匹配的數(shù)據(jù)，并在地圖上實時更新最新的位置。操作流程見圖5。

圖5 在線階段

3.模型設(shè)計

本文采用k最近鄰（KNN）算法[8]。所謂k最近鄰，就是k個最近鄰居的意思，每個樣本都可以用它最接近的k個鄰居來代表。在指紋定位中，對于任意在線RSS向量S，要分別計算它與指紋庫中各個RSS向量{ }

S1，S2，…，SM的距離（歐氏距離），然后選取最近的k個位置指紋，便可獲取所在位置，該方法相較于其他算法更簡單、直觀、有效。

KNN有分類算法和回歸算法，不同的算法實現(xiàn)方式有所不同。對于KNN回歸，標簽是坐標x和坐標y，通過求與待預(yù)測點距離最近的K個點的平均值得到待預(yù)測點的值，這里的“距離最近”采用歐氏距離，也可以是其他距離，具體的效果依數(shù)據(jù)而定。圖6中，x軸是一個特征，y是該特征得到的值，紅色點是已知點，要預(yù)測第一個點的位置，則計算離它最近的三個點，即黃色線框里的三個紅點的平均值，得出第一個綠色點，依次類推，就得到了綠色的線。由此可以看出，這樣預(yù)測的值明顯比直線要準。

圖6 KNN回歸算法

對于KNN分類，將定位區(qū)域劃分為1m×1m的網(wǎng)格，每個網(wǎng)格看作一個類別，用網(wǎng)格標號代替，對k個網(wǎng)格標號計數(shù)投票，選擇票數(shù)最多的網(wǎng)格作為定位結(jié)果。

KNN是較為簡單的空間分類模型，除KNN外還有其他的分類模型，將在第四部分模型對比中分別具體描述。

本部分描述了WiFi指紋定位系統(tǒng)的實現(xiàn)方案，給出了簡單的界面設(shè)計，并對系統(tǒng)的流程和采用的模型進行了闡述，下面將在本部分的基礎(chǔ)上給出具體的實現(xiàn)。

四、系統(tǒng)實現(xiàn)

（一）數(shù)據(jù)產(chǎn)生

1.建立RSS仿真環(huán)境數(shù)據(jù)集

將參數(shù)（AP的位置、房間大小尺寸）設(shè)置好，使各位置點之間的間隔盡量小，每個位置的RSS用射線跟蹤技術(shù)計算，計算一次射線跟蹤后保存數(shù)據(jù)，之后的RSS數(shù)據(jù)都從這個“RSS仿真環(huán)境數(shù)據(jù)集”中獲取。這里使用matlab工具設(shè)置參數(shù)，生成數(shù)據(jù)集。計算并保存位置指紋。

2.建立離線指紋庫，將數(shù)據(jù)采集的過程模擬化

數(shù)據(jù)從上面的“RSS仿真環(huán)境數(shù)據(jù)集”中獲取，比如每隔1m采集一次。

3.獲取定位階段的測試數(shù)據(jù)

模擬目標在已設(shè)置好參數(shù)的房間內(nèi)的運動軌跡，獲取每個軌跡點上的RSS值，用來作為定位算法的測試數(shù)據(jù)。這里簡要描述各部分代碼實現(xiàn)的功能：

main.m：主程序，在仿真環(huán)境中得到離線指紋庫和在線階段的測試數(shù)據(jù)，用于以后的定位測試。

get_rss.m：在空曠房間模擬射線跟蹤。

generate_rss.m：生成RSS仿真環(huán)境數(shù)據(jù)集。

get_random_finger_data.m：模擬隨機數(shù)據(jù)采集，生成位置指紋庫。

get_finger_data.m：模擬均勻數(shù)據(jù)采集，生成位置指紋庫。

get_terminal_data.m：模擬在線階段，生成測試數(shù)據(jù)。

finger_data_location.mat：離線數(shù)據(jù)位置點x、y。

terminal_data_of_trace.mat：生成測試數(shù)據(jù)的運動軌跡，10000*2的數(shù)組，比如trace（10，：）代表的是第10個時刻目標的位置x和y。

terminal_rss_data.mat：生成測試數(shù)據(jù)中與運行軌跡對應(yīng)的RSS，10000*6的數(shù)組，比如（trace10，：）代表的是第10個時刻時目標測得的各個RSS。

（二）指紋定位的實現(xiàn)

這里對前文所屬的KNN模型進行具體的實現(xiàn)：

1.數(shù)據(jù)導(dǎo)入

#導(dǎo)入數(shù)據(jù)

2.knn回歸算法實現(xiàn)

3.knn分類算法實現(xiàn)

4.進行數(shù)據(jù)預(yù)處理、交叉驗證后，分析定位算法，選擇最優(yōu)k實現(xiàn)

圖7 超參數(shù)k與score關(guān)系曲線

由圖7可知，當超參數(shù)k的取值小于10時，score的值極速上升；當k值大于10時，隨著超參數(shù)k的增加，score的值越趨于穩(wěn)定。

圖8 data number與accuracy曲線

由圖8曲線可知，隨著訓(xùn)練數(shù)據(jù)量的增大，定位準確度不斷提高并逐步趨于穩(wěn)定。

（三）各模型對比研究

本節(jié)嘗試使用各種常見的機器學習分類器，比較它們在位置指紋法中的定位準確度，以此評估各種回歸模型的性能。

1.數(shù)據(jù)導(dǎo)入

導(dǎo)入事先已仿真獲取的RSS數(shù)據(jù)：

#導(dǎo)入數(shù)據(jù)

2.邏輯回歸模型

邏輯回歸（也稱LR回歸），雖然這個算法從名字上來看是回歸算法，但本質(zhì)上其實是一個分類算法。在機器學習算法的幾十種分類器中，LR回歸是其中最常用的一個。

LR回歸使用sigmoid函數(shù)，是在線性回歸模型的基礎(chǔ)上，將線性模型wTx的結(jié)果壓縮到［0，1］之間，并給它賦予概率的意義。但它的本質(zhì)仍然是一個線性模型，實現(xiàn)起來相對比較簡單。LR回歸在廣告計算和推薦系統(tǒng)中使用頻率極高，是CTR預(yù)估模型的基本算法，同時也是深度學習的基本組成單元。下面是使用LR回歸獲取定位精度的部分代碼：

使用邏輯回歸算法的定位精度約為3.09m。

3.支持向量機

支持向量機（Support Vector Machine），又稱SVM，是一種監(jiān)督學習數(shù)學模型。假設(shè)n維空間內(nèi)，任意一個點都可以當作由n個變量組成的數(shù)據(jù)項抽象而成，也就是點的各個維度坐標值為各個變量。假定有m類數(shù)據(jù)項，那么可以構(gòu)建m-1個n維超平面將不同種類的數(shù)據(jù)項的點盡量分隔開，則這些超平面為支持向量面，這個分類數(shù)學模型為支持向量機分類模型。

（1）支持向量機-回歸

下面是使用SVM回歸獲取定位精度的部分代碼：

使用SVM回歸算法獲取的定位精度約為2.25m。

（2）支持向量機—分類

下面是使用SVM分類獲取定位精度的部分代碼：

使用SVM分類算法獲取的定位精度約為2.51m。

4.隨機森林

隨機森林（random forest）指的是利用多棵樹對樣本進行訓(xùn)練并預(yù)測的一種分類器。在機器學習中，隨機森林包含了多個決策樹，由個別樹輸出的類別的眾數(shù)決定它的輸出。

（1）隨機森林回歸

下面是使用隨機森林回歸算法獲取定位精度的部分代碼：

使用隨機森林回歸算法獲取的定位精度約為2.21m。

（2）隨機森林分類

下面是使用隨機森林分類算法獲取定位精度的部分代碼：

使用隨機森林分類算法獲取的定位精度約為2.57m。

5.線性回歸

在假設(shè)數(shù)據(jù)滿足線性關(guān)系的條件模型下，可以根據(jù)已有的訓(xùn)練數(shù)據(jù)來訓(xùn)練一個可以用以進行預(yù)測的模型，這就是線性回歸。第三部分中已給出仿真獲取數(shù)據(jù)的方法，因此我們嘗試用線性回歸來獲取定位精度。

下面是使用線性回歸獲取定位精度的部分代碼：

精度：3.83239 m

即使用線性回歸算法獲取的定位精度約為3.83m。

6.嶺回歸

嶺回歸是一種專用于共線性數(shù)據(jù)分析的有偏估計回歸方法，實質(zhì)上是一種改良的最小二乘估計法，通過放棄最小二乘法的無偏性，以損失部分信息、降低精度為代價獲得回歸系數(shù)更為符合實際、更可靠的回歸方法。

下面是使用嶺回歸獲取定位精度的部分代碼：

7.Lasso回歸

lasso回歸與嶺回歸相比較，既可以解決過擬合問題，也可以在參數(shù)縮減過程中完全減掉一些不必要的參數(shù)（即縮減為零），這種算法方便提取有用的特征。在建立廣義線型模型的時候，lasso能處理連續(xù)的和離散的因變量，并且lasso對于數(shù)據(jù)的要求極低，與其他算法相比能夠篩選變量和降低模型的復(fù)雜程度，在目前的機器學習算法中應(yīng)用較廣。

下面是使用Lasso回歸獲取定位精度的部分代碼：

即使用Lasso回歸算法獲取的定位精度約為3.83m。

8.梯度提升決策樹

梯度提升決策樹（Gradient Boosting Decision Tree，GBDT）算法[9]得益于其算法的性能優(yōu)勢，以及該算法在各類數(shù)據(jù)挖掘以及機器學習比賽中的卓越表現(xiàn)，是近年來被提及比較多的一個算法。

下面是使用GBDT算法獲取定位精度的部分代碼：

精度：2.22100m

使用GBDT算法獲取的定位精度約為2.22m。

9.神經(jīng)網(wǎng)絡(luò)多層感知器（Multi-layer Perceptron regressor）

在20世紀80年代，MLP在眾多機器學習算法中非常流行，在如語音圖像識別、機器翻譯等各種領(lǐng)域中都有廣泛的應(yīng)用。但90年代后，由于支持向量機的強大競爭力，MLP算法開始走下坡路。最近幾年由于深層學習的成功，MLP算法重新回到了研究者的視野當中。下面是用MLP算法獲得定位精度的部分代碼：

精度：2.45175m

使用MLP算法獲取的定位精度約為2.45m。

（四）小結(jié)

上述獲得的各回歸模型獲取的定位精度由高到低排行見表1。

從計算得出的大致定位精度來看，KNN、支持向量機、隨機森林、梯度提升這四個模型在定位準確性上要優(yōu)于其他的回歸模型。

五、擴展研究和總結(jié)

（一）設(shè)備無關(guān)的RSS指紋

在WiFi指紋定位實際應(yīng)用時，會有一個無法回避的問題，即各種設(shè)備對于RSS測量存在差異，同一個點測出的RSS指紋可能會因為設(shè)備自身的原因（設(shè)備射頻器件對于無線電信號處理的差異）或不同操作系統(tǒng)的定義不同而存在絕對值大小的差異。為規(guī)避此問題，這里提出一種使用相對信號強度的比值RSS作為指紋的改進方案，即不用RSS絕對值作為指紋特征，而將RSS向量中各分量相對于第一個分量的比值來表征指紋，這樣就很好地解決了設(shè)備差異導(dǎo)致的RSS絕對值誤差帶來的指紋偏離問題。

這里將RSS用作信號的空間數(shù)據(jù)，使用歐幾里得距離來算出RSS的距離。由于指紋參考點的Radio Map（信號覆蓋圖）是基于信號接收強度的差值序列建立的，而沒有直接使用接收到信息的強度，因此，事先利用比值模型來對接收信號強度RSS進行預(yù)處理，生成比值并把該RSS比值序列存儲到Radio Map中，這就建立了我們所需要的Radio Map該信號空間具有與設(shè)備無關(guān)的特點。

表1 各回歸模型獲取的定位精度排行表

（二）研究總結(jié)與未來展望

本文的研究旨在針對目前室外定位技術(shù)的廣泛應(yīng)用。由于室內(nèi)定位技術(shù)仍受限于成本和較低實用性而無法普及，因此，設(shè)計一個低成本與高實用性并存的室內(nèi)定位系統(tǒng)就非常具有意義。當前室內(nèi)WiFi熱點設(shè)施覆蓋面較廣，使得基于WiFi指紋的室內(nèi)定位成了較為經(jīng)濟的可行方案。

為了快速訓(xùn)練模型以及便于各個模型的對比，本系統(tǒng)并非用傳統(tǒng)的實際測量方法獲取數(shù)據(jù)，而是在研究WiFi信號特點的基礎(chǔ)上選用RSS作為指紋數(shù)據(jù)，提出了一種生成仿真RSS指紋庫的方法，解決了傳統(tǒng)方法費時費力的缺點，同時提高了數(shù)據(jù)庫的準確度。在實現(xiàn)部分給出了基于KNN算法進行模型研究的實現(xiàn)代碼，詳細闡述了KNN模型的訓(xùn)練和應(yīng)用。最后通過對不同的模型用同一套數(shù)據(jù)實施訓(xùn)練，并對計算出的定位精度進行對比，評估了機器學習分類器的性能。此外，考慮到實際應(yīng)用中的設(shè)備差異問題，提出了關(guān)于消除測量RSS的設(shè)備差異的改進算法——RSS比值法。

目前，室內(nèi)定位在國內(nèi)正在迅猛發(fā)展，未來各界對于低成本且實用的室內(nèi)定位技術(shù)的研究也將日漸深入。本文采用仿真模擬的方法實現(xiàn)和驗證了WiFi指紋定位理論和方案，以期為今后更加實用化的研究提供參考。