最強(qiáng)基站MAC 地址匹配的RSSI 加權(quán)室內(nèi)定位方法

孫玉曦，甄 杰，郭 英，李晨輝,3

（1. 中國測繪科學(xué)研究院，北京 100036；2. 山東科技大學(xué) 測繪科學(xué)與工程學(xué)院，山東 青島 266590； 3. 遼寧工程技術(shù)大學(xué) 測繪與地理科學(xué)學(xué)院，遼寧 阜新 123000）

0 引言

隨著社會(huì)的發(fā)展，室內(nèi)場所的面積越來越大，出現(xiàn)了許多大型的商場、辦公場所、娛樂場所等，而且人們大部分的活動(dòng)時(shí)間都在室內(nèi)，對(duì)室內(nèi)位置服務(wù)（indoor location based service， ILBS）的需求日益強(qiáng)烈[1]。當(dāng)前，依賴可移動(dòng)智能設(shè)備（智能手表、智能手機(jī)、平板電腦等）的室內(nèi)移動(dòng)位置服務(wù)，在人們生活中扮演著不可或缺的角色，具有巨大的市場潛在價(jià)值。

目前可用于室內(nèi)定位的技術(shù)有很多，如芬蘭Quuppa 公司[2]推出的藍(lán)牙天線陣列系統(tǒng)，蘋果公司推出的基于低功耗藍(lán)牙的iBeacon 系統(tǒng)[3]，谷歌公司則把視覺定位技術(shù)(visual positioning service， VPS)[4]列為其核心技術(shù)，還有較為常見的射頻識(shí)別(radio frequency identification， RFID)[5]、無線局域網(wǎng)(wireless local area networks， WLAN)[6]、藍(lán)牙[7]、超寬帶(ultra-wide band， UWB)[8]、地磁[9]等，許多研究機(jī)構(gòu)與學(xué)者利用這些技術(shù)開發(fā)了不同的室內(nèi)定位系統(tǒng)，滿足了不同用戶的室內(nèi)定位精度需求。

由于藍(lán)牙、WLAN 等價(jià)格低廉、易于布設(shè)等優(yōu)點(diǎn)，使其在室內(nèi)定位領(lǐng)域應(yīng)用十分廣泛。其主要采用測距交會(huì)和指紋匹配2 種方法[4]：測距交會(huì)法[10]對(duì)室內(nèi)難以精確定義的信號(hào)傳播模型的依賴性，使其精度受到限制；指紋匹配法[11]依靠的是識(shí)別表征目標(biāo)位置的信號(hào)特征，利用各點(diǎn)信號(hào)的差異性實(shí)現(xiàn)定位，不受信號(hào)傳播多路徑、反射的影響，且室內(nèi)復(fù)雜的信號(hào)傳播模型對(duì)其定位精度的影響較小。因此在室內(nèi)環(huán)境下，指紋匹配定位方法會(huì)有較好的定位效果。

指紋匹配定位方法分為確定性指紋定位算法和概率性指紋定位算法。確定性算法主要有最鄰近法(nearest neighbor， NN)、k-鄰近法(k-nearest neighbor， KNN)、帶有權(quán)重的 k-鄰近法(k-weight nearest neighbor， KWNN)、神經(jīng)網(wǎng)絡(luò)法(artificial neural networks， ANNS)[12]；概率性算法主要是貝葉斯算法等[13]，定位需要大量的假設(shè)統(tǒng)計(jì)工作，導(dǎo)致在線定位階段算法更加復(fù)雜。確定性算法中的神經(jīng)網(wǎng)絡(luò)法也存在類似的問題，離線階段需要大量的工作。KNN 算法與這2 種相比，實(shí)現(xiàn)更為簡單，并且對(duì)硬件要求不高，但是該算法在判定近鄰點(diǎn)時(shí)，會(huì)引入距離待定點(diǎn)較遠(yuǎn)的參考點(diǎn)，從而影響定位精度。利用動(dòng)態(tài)加權(quán)最近鄰算法[13](enhanced weighted k nearest neighbor， EWKNN)可以設(shè)定1 個(gè)閾值來動(dòng)態(tài)選擇k 值，提高定位精度，但該算法選擇的參考點(diǎn)也有出現(xiàn)距離較遠(yuǎn)的現(xiàn)象。

基于上述問題，本文在離線階段，通過模糊c均值聚類算法（fuzzy c-means algorithm， FCM）先進(jìn)行定位區(qū)域劃分，生成聚類指紋庫。在線階段，首先進(jìn)行區(qū)域定位，然后在動(dòng)態(tài)加權(quán)最近鄰算法動(dòng)態(tài)選擇k 值的基礎(chǔ)上，根據(jù)待測點(diǎn)和選定區(qū)域內(nèi)，參考點(diǎn)介質(zhì)訪問控制（media access control， MAC）地址序列進(jìn)行匹配，只信任最強(qiáng)的基站，進(jìn)一步剔除較為偏遠(yuǎn)的參考點(diǎn)，從而篩選出k 個(gè)中最優(yōu)的參考點(diǎn)。最后，計(jì)算最優(yōu)參考點(diǎn)對(duì)應(yīng)坐標(biāo)的加權(quán)平均值作為待測點(diǎn)的最終估計(jì)位置。

1 基于RSSI 的位置指紋定位算法

基于接收信號(hào)強(qiáng)度指示（received signal strength indicator， RSSI）的位置指紋定位算法，分為離線勘測和在線定位2 個(gè)階段。離線勘測階段主要是信息采集和樣本訓(xùn)練，利用參考點(diǎn)的已知位置數(shù)據(jù)和接收到接入點(diǎn)的RSSI 信號(hào)特征值，包括RSSI、MAC 地址、均值、方差等，建立位置-指紋數(shù)據(jù)庫，從而建立空間位置與RSSI 序列準(zhǔn)確的映射關(guān)系；在線定位階段,利用接收到的待定點(diǎn)的RSSI 序列與建立的位置指紋數(shù)據(jù)庫進(jìn)行匹配，然后運(yùn)用某一定位匹配算法，解算出待定點(diǎn)的位置信息[14]。所采用的匹配算法會(huì)直接關(guān)系到定位結(jié)果的準(zhǔn)確性。

2 在線匹配算法

2.1 動(dòng)態(tài)加權(quán)最近鄰算法原理

1）將待定點(diǎn)采集的RSSI 信息與指紋庫中的指紋信息進(jìn)行相似度匹配，獲取近鄰點(diǎn)，其相似匹配依據(jù)是信號(hào)的歐氏距離，其計(jì)算公式為

式中：RSSIj為第j 個(gè)基站的信號(hào)強(qiáng)度RSSI 值；Rij為位置指紋庫中第i 個(gè)參考點(diǎn)接收到的第j 個(gè)基站的信號(hào)強(qiáng)度RSSI 值；m 為位置指紋庫中參考點(diǎn)的個(gè)數(shù)；n 為待測點(diǎn)接收到的基站的個(gè)數(shù)。每個(gè)參考點(diǎn)的坐標(biāo) Pi( xi，yi)和對(duì)應(yīng)的RSSI 序列 Rij構(gòu)成了定位區(qū)域的位置指紋庫位置指紋庫（point RSSI， PR）。

2）通過設(shè)定1 個(gè)閾值 R0，保留式（1） Di中不大于 R0對(duì)應(yīng)的 Di，并將其記為 Si(i =1， 2，…， L)將剩下的 Si按從小到大的順序排列，并計(jì)算其平均值E ( S )為

3）將 Di和 E ( S )進(jìn)行比較，保留那些距離差 Di不大于平均值 E ( S )的參考點(diǎn)，這些參考點(diǎn)的數(shù)目就是動(dòng)態(tài)變化的k 值，這樣就可以避免由于固定k值把距離偏遠(yuǎn)的參考點(diǎn)選入而影響定位精度的問題。最后，將保留下來的k 個(gè)值對(duì)應(yīng)的坐標(biāo)( xk，yk)加權(quán)平均，得到該待定點(diǎn)的估計(jì)位置( x， y )為

2.2 改進(jìn)算法

在大型場所定位時(shí)，遍歷所有參考點(diǎn)的計(jì)算量較大，并且會(huì)大大降低系統(tǒng)的實(shí)時(shí)性。為了減少待匹配參考點(diǎn)的個(gè)數(shù)，本文首先用模糊c 均值聚類算法，將定位場所劃分成若干個(gè)區(qū)域，在線定位階段，首先進(jìn)行區(qū)域定位，然后再用改進(jìn)的MAC 地址匹配算法在該區(qū)域內(nèi)進(jìn)行位置估計(jì)，既可減少指紋匹配時(shí)間，提高定位的實(shí)時(shí)性，也能提升定位精度。

2.2.1 模糊c 均值聚類算法劃分定位區(qū)域

模糊c 均值聚類算法是1 種以隸屬度來確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類程度的軟聚類算法[15]。其目標(biāo)函數(shù)為

其約束條件為

式中：n 為聚類樣本數(shù)；c 為聚類數(shù)目；X= { x1， x2，… ， xn}為 樣本集合；C = {c1， c2，… ， cn}為 聚類中心；v 為1 個(gè)加權(quán)系數(shù)； uij為樣本集χj歸屬于所有類別的隸屬度矩陣。

由拉格朗日乘數(shù)法求解，目標(biāo)函數(shù)式（4）取極小值滿足的條件為[15]：

采用迭代的方法求解式（6）和式（7），直至滿足收斂條件，得到最優(yōu)解。

FCM 算法對(duì)于滿足正態(tài)分布的數(shù)據(jù)聚類效果會(huì)很好，因此本文用該算法對(duì)離線位置指紋庫PR進(jìn)行聚類分析，劃分定位區(qū)域。采用FCM 算法對(duì)離線指紋庫進(jìn)行聚類，每1 個(gè)子類包含1 個(gè)聚類中心，代表該類的特征，用于在線定位階段進(jìn)行區(qū)域匹配定位。算法具體步驟為：

第1 步，根據(jù)實(shí)驗(yàn)訓(xùn)練經(jīng)驗(yàn)值給定聚類數(shù)c 和初始聚類中心 0C ，初始化加權(quán)系數(shù) 2v= ，設(shè)定迭代收斂條件（迭代截止誤差ε 、迭代計(jì)數(shù)l）

第2 步，更新隸屬度矩陣，其計(jì)算公式為

第3 步，更新聚類中心，其計(jì)算公式為

第5 步，計(jì)算每個(gè)聚類中心C 區(qū)域參考點(diǎn)數(shù)目，設(shè)定閾值，如果小于閾值，迭代停止，劃分為c 類區(qū)域；否則跳轉(zhuǎn)到第1 步，進(jìn)行下一層次區(qū)域劃分。

2.2.2 基于最強(qiáng)基站MAC 地址篩選參考點(diǎn)

研究移動(dòng)端接收到不同基站的 RSSI 數(shù)據(jù)時(shí)發(fā)現(xiàn)，位置接近的待測點(diǎn)與參考點(diǎn)，他們的MAC地址有緊密相關(guān)性，盡管其RSSI 強(qiáng)度略有波動(dòng)，但其MAC 地址序列基本一致[16]。因此本文在動(dòng)態(tài)k 值篩選參考點(diǎn)基礎(chǔ)上，引入基站MAC 地址匹配度進(jìn)一步篩選出最優(yōu)的參考點(diǎn)，進(jìn)而提高定位的精度。

1）在線階段待測點(diǎn)的MAC 地址序列跟離線指紋庫中參考點(diǎn)的MAC 地址序列進(jìn)行匹配，其匹配公式為

式中：iL 為求得的第i 個(gè)參考點(diǎn)的匹配度；ijN 為定位階段與第i 個(gè)參考點(diǎn)匹配時(shí)，前j 個(gè)基站的MAC 地址相同的個(gè)數(shù)。如果基站的MAC 地址序列完全相同，則iL 取最大值。

2）實(shí)驗(yàn)結(jié)果表明，即使距離很近的2 個(gè)位置， 其基站MAC 序列也不是完全一致的。為了減少信號(hào)波動(dòng)的影響，基于信任最強(qiáng)基站的想法，式（10）取 1j= ，即只選取信號(hào)強(qiáng)度最強(qiáng)的基站RSSI 地址進(jìn)行篩選匹配，從而剔除參考點(diǎn)，提高定位的精度。

2.2.3 不同基站信號(hào)強(qiáng)度加權(quán)

動(dòng)態(tài)加權(quán)最近鄰算法在尋找用于定位的參考點(diǎn)過程中，通過求解參考點(diǎn)與待測點(diǎn)之間RSSI 相似度來確定若干個(gè)用于定位的參考點(diǎn)，對(duì)這幾個(gè)參考點(diǎn)給予權(quán)值區(qū)別對(duì)待，與定位點(diǎn)接收信號(hào)強(qiáng)度相似度高的參考點(diǎn)，在確定定位點(diǎn)坐標(biāo)時(shí)有較大的權(quán)值。

然而這一過程并沒有對(duì)來自于不同基站的信號(hào)強(qiáng)度區(qū)別對(duì)待，在實(shí)際情況下，接收到某個(gè)基站的信號(hào)強(qiáng)度越高，則來自該基站的信號(hào)強(qiáng)度對(duì)定位的貢獻(xiàn)程度應(yīng)該最大，所以在定位中可以對(duì)不同基站加以可信度，給每個(gè)基站分配不同的權(quán)值進(jìn)行RSSI 相似度的計(jì)算[17]。

在動(dòng)態(tài)加權(quán)最近鄰算法第1 步，即計(jì)算待測點(diǎn)與參考點(diǎn)接收到第j 個(gè)基站的信號(hào)強(qiáng)度相似度時(shí)，對(duì)歐氏距離加以權(quán)值 Wj，Wj和待測點(diǎn)與參考點(diǎn)之間RSSI 相似度的計(jì)算公式分別為：

式中：RSSIj為第j 個(gè)基站的信號(hào)強(qiáng)度RSSI 值；Rij為位置指紋庫中第i 個(gè)參考點(diǎn)接收到的第j 個(gè)基站的信號(hào)強(qiáng)度RSSI 值；m 為位置指紋庫中參考點(diǎn)的個(gè)數(shù)；n 為待測點(diǎn)接收到的基站的個(gè)數(shù)。

2.3 整體改進(jìn)算法流程

本文在動(dòng)態(tài)加權(quán)最近鄰算法的基礎(chǔ)上做了改進(jìn)，具體流程為：離線階段，通過FCM 算法進(jìn)行定位區(qū)域劃分，生成聚類指紋庫。在線階段，首先計(jì)算待測點(diǎn)與各區(qū)域聚類中心的相似度，確定待測點(diǎn)所在的目標(biāo)區(qū)域；然后根據(jù)RSSI 強(qiáng)度加權(quán)后的待測點(diǎn)與目標(biāo)區(qū)域參考點(diǎn)的指紋信息，設(shè)定閾值，動(dòng)態(tài)選擇k 值，從而剔除距離偏遠(yuǎn)的參考點(diǎn)；再次通過RSSI 地址序列匹配的方法，只信任最強(qiáng)的基站，進(jìn)一步篩選出k 個(gè)中最優(yōu)的參考點(diǎn)；最后計(jì)算最優(yōu)參考點(diǎn)對(duì)應(yīng)坐標(biāo)的加權(quán)平均值，作為待測點(diǎn)的最終估計(jì)位置，其流程如圖1 所示。

圖1 算法流程

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)描述

實(shí)驗(yàn)場地為某5 層樓的3 層，包含走廊及318 房間。走廊長45、寬3.6 m，每隔5～6 m 布設(shè)1 個(gè)iBeacon 基站（共有7 個(gè)基站）；318 房間長11.5、寬5.5 m，布設(shè)5 個(gè)基站，基站附著在天花板上。將智能手機(jī)（小米6）作為采集設(shè)備，信號(hào)的采樣率設(shè)為1 Hz。實(shí)驗(yàn)者手持采集設(shè)備在每個(gè)采樣點(diǎn)上分別在東、西、南、北4 個(gè)方向上采集60 s 的數(shù)據(jù)，用均值濾波處理RSSI 數(shù)據(jù)，然后存入后臺(tái)指紋庫 (密度為1 m)。實(shí)驗(yàn)場地、指紋參考點(diǎn)以及基站布設(shè)情況如圖2 所示，實(shí)驗(yàn)分為318 房間實(shí)驗(yàn)以及走廊部分實(shí)驗(yàn)。

圖2 實(shí)驗(yàn)環(huán)境

3.2 結(jié)果分析

3.2.1 FCM 區(qū)域劃分實(shí)驗(yàn)

使用FCM 算法對(duì)318 房間及走廊區(qū)域進(jìn)行區(qū)域劃分，其參考點(diǎn)的分布情況如圖3 所示，大部分參考點(diǎn)都可以按照區(qū)域進(jìn)行劃分，只有少量參考點(diǎn)未能按區(qū)域劃分。

圖3 FCM 區(qū)域劃分

3.2.2 在線定位實(shí)驗(yàn)

1）318 房間定位實(shí)驗(yàn)。在318 房間4 個(gè)已知點(diǎn)上分別采集10 s 的RSSI 數(shù)據(jù)，運(yùn)用本文的改進(jìn)算法和EWKNN 算法進(jìn)行數(shù)據(jù)處理，對(duì)2 種結(jié)果進(jìn)行比較。

分別計(jì)算2 種算法的定位誤差（如圖4（a）所示）和誤差累計(jì)概率分布（如圖4（b）所示），并將各類數(shù)據(jù)進(jìn)行統(tǒng)計(jì)（如表1 所示）。本文將最小定位誤差、最大定位誤差、平均誤差和不同定位 精度下的誤差累計(jì)概率作為衡量定位精度的標(biāo)準(zhǔn)。

圖4 2 種算法定位誤差與誤差累計(jì)概率

表1 2 種算法精度對(duì)比

由圖4（a）、圖4（b）及表1 測試結(jié)果可知，改進(jìn)的算法優(yōu)于EWKNN 算法：EWKNN 算法的平均定位誤差為1.90 m，誤差在1 和2 m 以內(nèi)的可信度分別為7.5%和67.5%；而改進(jìn)算法的平均定位誤差為1.51 m，誤差在1 和2 m 以內(nèi)的可信度分別為35.0%和85.0%；改進(jìn)算法的最大定位誤差為2.60 m，EWKNN 算法的最大定位誤差為3.29 m；而且改進(jìn)算法的定位誤差均在3 m 以下，而EWKNN 方法定位誤差在3.5 m 以下。

2）走廊區(qū)域定位實(shí)驗(yàn)。在走廊區(qū)域2 個(gè)已知點(diǎn)上分別采集10 s 的RSSI 數(shù)據(jù)，運(yùn)用本文的改進(jìn)算法和EWKNN 算法進(jìn)行數(shù)據(jù)處理，對(duì)2 種結(jié)果進(jìn)行比較。

分別計(jì)算2 種算法的定位誤差（如圖5（a）所示）和誤差累計(jì)概率分布（如圖5（b）所示），并將各類數(shù)據(jù)進(jìn)行統(tǒng)計(jì)（如表2 所示）。

表2 2 種算法精度對(duì)比

圖5 2 種算法定位誤差與累計(jì)概率

由圖5（a）、圖5（b）及表2 測試結(jié)果可知，改進(jìn)算法的定位誤差在 2.5 m 以下的概率大于EWKNN 算法。EWKNN 算法的平均定位誤差為2.74 m，改進(jìn)算法在此基礎(chǔ)上降低了0.33 m，改進(jìn)算法的定位誤差均在4 m 以下，而EWKNN 方法定位誤差在4.5 m 以下。

通過以上實(shí)驗(yàn)分析可知，本文改進(jìn)算法在房間以及走廊區(qū)域的平均定位誤差、最大誤差相比EWKNN 算法均有所改善，誤差累計(jì)概率有較好的提升，這說明該算法通過FCM 區(qū)域劃分、MAC 地址匹配篩選后，能夠有效剔除較為偏遠(yuǎn)的參考點(diǎn)，提高定位精度。

4 結(jié)束語

本文提出的最強(qiáng)基站MAC 地址匹配的RSSI加權(quán)的改進(jìn)室內(nèi)定位方法，能夠在室內(nèi)復(fù)雜環(huán)境下有效剔除距離偏遠(yuǎn)的參考點(diǎn)，削弱信號(hào)不穩(wěn)定對(duì)定位結(jié)果的影響，提高定位精度，并且降低定位計(jì)算的復(fù)雜度，對(duì)室內(nèi)定位的研究有一定的參考價(jià)值。但隨著室內(nèi)應(yīng)用場景越來越多、室內(nèi)面積越來越大，如何做好離線指紋庫的快速采集和有效維護(hù)是接下來要進(jìn)一步研究的工作。