劉業(yè)輝

摘 要：本文主要探討分析基于位置指紋的WiFi室內(nèi)定位算法，該算法主要是通過層次聚類方式劃分測試環(huán)境區(qū)域，再匹配對應(yīng)的WiFi信號指紋信息，之后利用加權(quán)計(jì)算確定定位位置。按照此次研究結(jié)果顯示，在充足的WiFi熱點(diǎn)數(shù)量之下，對比分析k-means-KNN算法以及原始KNN算法，位置指紋室內(nèi)定位算法在地位給精準(zhǔn)度以及準(zhǔn)確率方面表現(xiàn)良好，此外，還分析加權(quán)最近鄰算法和最近鄰算法等相關(guān)內(nèi)容，希望可以為位置指紋的WiFi室內(nèi)定位算法研究提供參考性價(jià)值。

關(guān)鍵詞：位置指紋 WiFi 室內(nèi)定位算法 加權(quán)最近鄰算法 最近鄰算法

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）01（b）-0044-02

隨著全面普及的無線網(wǎng)絡(luò)以及移動通信技術(shù)，相應(yīng)提升了對定位服務(wù)的需求。需要實(shí)現(xiàn)實(shí)時(shí)位置跟蹤以及路線導(dǎo)航等?；谝陨习l(fā)展現(xiàn)狀，在人們?nèi)粘Ｉ町?dāng)中已經(jīng)逐漸凸顯出定位計(jì)算和服務(wù)的重要性。針對室外定位技術(shù)，現(xiàn)階段比較主流的技術(shù)就是全球定位技術(shù)，在戶外活動方面被廣泛應(yīng)用。然而在室內(nèi)區(qū)域，建筑物會遮擋或者屏蔽信號，在室內(nèi)定位當(dāng)中無法充分發(fā)揮全球定位系統(tǒng)的作用。所以，在室內(nèi)怎樣實(shí)現(xiàn)定位技術(shù)已經(jīng)成為現(xiàn)階段研究的熱點(diǎn)話題之一。當(dāng)前，有較多室內(nèi)定位方式都是借助于基礎(chǔ)設(shè)備具備的某些技術(shù)完成定位，廣泛應(yīng)用無線基礎(chǔ)設(shè)施，無線信號可以全面覆蓋到城市建筑當(dāng)中，所以，通過無線網(wǎng)絡(luò)實(shí)現(xiàn)室內(nèi)定位技術(shù)得以快速發(fā)展。

1 聚類在定位算法當(dāng)中的應(yīng)用

常規(guī)的位置定位算法主要是能夠計(jì)算所有鄰居，全面估算較多鄰居的位置。在實(shí)際計(jì)算期間可以篩選所有的鄰居，這樣能夠獲取更加準(zhǔn)確的結(jié)果，降低估算時(shí)間。在空間當(dāng)中，設(shè)備信號源與設(shè)備接受信號的強(qiáng)度呈正相關(guān)。所以，可以按照鄰居的物理位置將其分為多個(gè)獨(dú)立的簇，主要是通過聚類技術(shù)實(shí)現(xiàn)，自后選擇其中一個(gè)簇作為代表，這樣就可以過濾掉其他簇。

k-means聚類算法主要是劃分空間數(shù)據(jù)實(shí)現(xiàn)的，有關(guān)學(xué)者對于k-means算法的定位方案，算法的思維主要是按照信號的強(qiáng)度進(jìn)行聚類，之后將相似接收相似信號強(qiáng)度定位參考點(diǎn)分組情況，這樣能夠降低定位計(jì)算工作量。然而由于經(jīng)典的k-means聚類算法是在空間數(shù)據(jù)集內(nèi)部各個(gè)子類具有較大差異性時(shí)，為了縮小誤差平方和，需要有效分割最大子類，這樣就使得該種算法限度局部最優(yōu)解，難度全部進(jìn)行最優(yōu)解。為了處理該種現(xiàn)象，需要使用優(yōu)化的聚類準(zhǔn)則函數(shù)來進(jìn)行計(jì)算。

2 最近鄰算法

該種方式是最基本的位置指紋定位算法。在定位時(shí)采用最近臨算法時(shí)，存在m個(gè)WiFi熱點(diǎn)，這樣就使移動終端設(shè)備接收m個(gè)熱點(diǎn)的信號強(qiáng)度值的集合為S=（RSSI1，RSSI1…RSSIm），之后將該離線收集的數(shù)據(jù)匹配具有歷史指紋庫的某一房間的位置數(shù)據(jù)指紋Ai，之后計(jì)算Ai與S之間的距離，在獲取Ai與S的最小距離之后需要將該數(shù)據(jù)對應(yīng)的房間號作為定位結(jié)果。其最小距離的計(jì)算公式如下所示：

…3 （1）

如果式（1）的q值為1時(shí)，Di表示的是曼哈頓距離，當(dāng)q值為2時(shí)，Di表示的是歐幾里得距離，此次研究將q值定為2，因此兩者之間采用的是歐幾里得距離。

首先需要計(jì)算在線實(shí)時(shí)數(shù)據(jù)和離線指紋數(shù)據(jù)庫當(dāng)中的歷史數(shù)據(jù)距離，之后在對其進(jìn)行比較計(jì)算最小距離對應(yīng)的區(qū)域號。由于具有龐大的指紋數(shù)據(jù)庫，因此，需要較長時(shí)間進(jìn)行匹配，在此次期間還會出現(xiàn)較多個(gè)距離相同的值數(shù)，在產(chǎn)生該種情況時(shí)需要再進(jìn)行比較和計(jì)算。首先需要統(tǒng)計(jì)每個(gè)房間數(shù)據(jù)最小值的數(shù)量，之后再將取得較多最小值數(shù)量的房間進(jìn)行定位，之后需要將該房間號作為定位結(jié)構(gòu)。

3 加權(quán)最近鄰算法

3.1 加權(quán)最近鄰算法的原理

由于在此次研究當(dāng)中不適用K近鄰算法，因此，需要提出加權(quán)最近鄰法。加權(quán)最近鄰算法是在最近鄰算法基礎(chǔ)之上進(jìn)行改進(jìn)。加權(quán)最近鄰算法的實(shí)時(shí)采樣信號強(qiáng)度值也是S=（RSSI1，RSSI1…RSSIm），并且該離線收集的數(shù)據(jù)匹配具有歷史指紋庫的某一房間的位置數(shù)據(jù)指紋Ai，其具有較低的定位準(zhǔn)確率，因此，使用加權(quán)最近鄰算法可以有效改善該種情況。

一般情況下，移動設(shè)備會接收的熱點(diǎn)信號之間存在不相同的RSSI值，按照信號傳播的運(yùn)力，能夠得知信號發(fā)射點(diǎn)經(jīng)過的距離較短時(shí)，就會減慢信號衰落，降低衰減速度，這樣就使得移動設(shè)備接收的信號強(qiáng)度比較大。因此，在實(shí)際定位期間，移動信號要距離較大RSSI值熱點(diǎn)近，這樣最近距離熱點(diǎn)就會較大影響定位結(jié)果，具有較強(qiáng)的決定性。在對距離進(jìn)行計(jì)算時(shí)，需要在離線指紋數(shù)據(jù)對應(yīng)的RSSI值與熱點(diǎn)實(shí)時(shí)采集的差值與加權(quán)系數(shù)的乘積，之后再將m個(gè)距離的最小值應(yīng)對區(qū)域與加權(quán)和作為移動設(shè)備的定位結(jié)果。以下公式就是加權(quán)最近鄰算法：

（2）

由式（2）可以看出，加權(quán)最近鄰算法與最近鄰法的最大差別在于加權(quán)系數(shù)，主要是通過每一熱點(diǎn)計(jì)算整個(gè)距離的權(quán)重值，在此時(shí)加權(quán)系數(shù)的取值主要有3種方式：（1）按照移動設(shè)備在固定時(shí)間內(nèi)接受的m個(gè)熱點(diǎn)的RSSI值的平均值；（2）按照移動設(shè)備在固定時(shí)間內(nèi)接受的m個(gè)熱點(diǎn)的RSSI值的方差；（3）按照信號的隨機(jī)性和波動性，得出每一個(gè)熱點(diǎn)與距離計(jì)算行為具有相同的貢獻(xiàn)，因此，導(dǎo)致所有熱點(diǎn)占據(jù)的權(quán)重都是1/m。前兩種方式的具有相同的原理和思想，并且具有較小的準(zhǔn)確率相差情況。因此，本次研究主要是通過平均值作為加權(quán)系數(shù)的計(jì)算標(biāo)準(zhǔn)。

3.2 劃分區(qū)域類

為了確保數(shù)據(jù)的準(zhǔn)確性和可靠性，因此，需要在離線階段多次進(jìn)行采樣，這樣就會形成較大的位置指紋信息庫，盡管可以提升數(shù)據(jù)的準(zhǔn)確性，然而卻進(jìn)行長時(shí)間的匹配。這主要是因?yàn)閷?shí)時(shí)定位期間的匹配都是通過歷史數(shù)據(jù)和實(shí)時(shí)數(shù)據(jù)實(shí)現(xiàn)的，如果存在較大的數(shù)據(jù)庫，相應(yīng)會增加計(jì)算次數(shù)。如果在實(shí)際定位期間可以減少匹配時(shí)間，這樣就可以降低計(jì)算距離，不斷減小匹配范圍。其次，還存在較高便利性的計(jì)算方式，主要是通過數(shù)據(jù)處理之后得出的平均值，并且每一房間內(nèi)的歷史數(shù)據(jù)只存在一行，這樣就會減少匹配時(shí)間。然而該種匹配方式無法確保結(jié)果的準(zhǔn)確性，主要是因?yàn)樵摲N方式存在較強(qiáng)的絕對性，只能明確大致的發(fā)展方向，無法確保細(xì)節(jié)方面，需要不斷促進(jìn)定位目標(biāo)的準(zhǔn)確性。

4 結(jié)語

綜上所述，本文主要是探討分析基于位置指紋的WiFi室內(nèi)定位算法，并且從聚類在定位算法當(dāng)中的應(yīng)用，最近鄰算法，以及加權(quán)最近鄰算法等方面進(jìn)行闡述，其中加權(quán)最近鄰算法主要是分析了加權(quán)最近鄰算法的原理和劃分區(qū)域類等。通過對以上方面的分析研究，可以全面了解和掌握基于位置指紋的WiFi室內(nèi)定位算法。

參考文獻(xiàn)

[1] 高富，賀艷軍.基于WiFi技術(shù)的煤礦井下人員定位系統(tǒng)研究[J].煤炭工程，2017（S2）：160-162.

[2] 王恩良，孟志斌，徐湘寓，等.一種基于WiFi指紋特征匹配的加權(quán)K近鄰室內(nèi)定位算法[J].桂林電子科技大學(xué)學(xué)報(bào)，2017，37（4）：276-281.

[3] 韋信相，張文輝.基于Android的室內(nèi)WiFi指紋定位系統(tǒng)及KNN定位算法的設(shè)計(jì)[J].大眾科技，2017，19（8）：14-16，31.

[4] 何富貴，吳陳沭，周先存，等.一種層次Levenshtein距離的無指紋校準(zhǔn)的室內(nèi)定位方法[J].智能系統(tǒng)學(xué)報(bào)，2017，12（3）：422-429.

[5] 許微，查峰，李豹.基于Android平臺的位置指紋室內(nèi)定位系統(tǒng)研究與設(shè)計(jì)[J].艦船電子工程，2016，36（5）：50-55.