最強基站MAC 地址匹配的RSSI 加權室內定位方法

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

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

0 引言

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

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

由于藍牙、WLAN 等價格低廉、易于布設等優點，使其在室內定位領域應用十分廣泛。其主要采用測距交會和指紋匹配2 種方法[4]：測距交會法[10]對室內難以精確定義的信號傳播模型的依賴性，使其精度受到限制；指紋匹配法[11]依靠的是識別表征目標位置的信號特征，利用各點信號的差異性實現定位，不受信號傳播多路徑、反射的影響，且室內復雜的信號傳播模型對其定位精度的影響較小。因此在室內環境下，指紋匹配定位方法會有較好的定位效果。

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

基于上述問題，本文在離線階段，通過模糊c均值聚類算法（fuzzy c-means algorithm， FCM）先進行定位區域劃分，生成聚類指紋庫。在線階段，首先進行區域定位，然后在動態加權最近鄰算法動態選擇k 值的基礎上，根據待測點和選定區域內，參考點介質訪問控制（media access control， MAC）地址序列進行匹配，只信任最強的基站，進一步剔除較為偏遠的參考點，從而篩選出k 個中最優的參考點。最后，計算最優參考點對應坐標的加權平均值作為待測點的最終估計位置。

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

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

2 在線匹配算法

2.1 動態加權最近鄰算法原理

1）將待定點采集的RSSI 信息與指紋庫中的指紋信息進行相似度匹配，獲取近鄰點，其相似匹配依據是信號的歐氏距離，其計算公式為

式中：RSSIj為第j 個基站的信號強度RSSI 值；Rij為位置指紋庫中第i 個參考點接收到的第j 個基站的信號強度RSSI 值；m 為位置指紋庫中參考點的個數；n 為待測點接收到的基站的個數。每個參考點的坐標 Pi( xi，yi)和對應的RSSI 序列 Rij構成了定位區域的位置指紋庫位置指紋庫（point RSSI， PR）。

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

3）將 Di和 E ( S )進行比較，保留那些距離差 Di不大于平均值 E ( S )的參考點，這些參考點的數目就是動態變化的k 值，這樣就可以避免由于固定k值把距離偏遠的參考點選入而影響定位精度的問題。最后，將保留下來的k 個值對應的坐標( xk，yk)加權平均，得到該待定點的估計位置( x， y )為

2.2 改進算法

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

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

模糊c 均值聚類算法是1 種以隸屬度來確定每個數據點屬于某個聚類程度的軟聚類算法[15]。其目標函數為

其約束條件為

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

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

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

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

第1 步，根據實驗訓練經驗值給定聚類數c 和初始聚類中心 0C ，初始化加權系數 2v= ，設定迭代收斂條件（迭代截止誤差ε 、迭代計數l）

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

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

第5 步，計算每個聚類中心C 區域參考點數目，設定閾值，如果小于閾值，迭代停止，劃分為c 類區域；否則跳轉到第1 步，進行下一層次區域劃分。

2.2.2 基于最強基站MAC 地址篩選參考點

研究移動端接收到不同基站的 RSSI 數據時發現，位置接近的待測點與參考點，他們的MAC地址有緊密相關性，盡管其RSSI 強度略有波動，但其MAC 地址序列基本一致[16]。因此本文在動態k 值篩選參考點基礎上，引入基站MAC 地址匹配度進一步篩選出最優的參考點，進而提高定位的精度。

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

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

2）實驗結果表明，即使距離很近的2 個位置， 其基站MAC 序列也不是完全一致的。為了減少信號波動的影響，基于信任最強基站的想法，式（10）取 1j= ，即只選取信號強度最強的基站RSSI 地址進行篩選匹配，從而剔除參考點，提高定位的精度。

2.2.3 不同基站信號強度加權

動態加權最近鄰算法在尋找用于定位的參考點過程中，通過求解參考點與待測點之間RSSI 相似度來確定若干個用于定位的參考點，對這幾個參考點給予權值區別對待，與定位點接收信號強度相似度高的參考點，在確定定位點坐標時有較大的權值。

然而這一過程并沒有對來自于不同基站的信號強度區別對待，在實際情況下，接收到某個基站的信號強度越高，則來自該基站的信號強度對定位的貢獻程度應該最大，所以在定位中可以對不同基站加以可信度，給每個基站分配不同的權值進行RSSI 相似度的計算[17]。

在動態加權最近鄰算法第1 步，即計算待測點與參考點接收到第j 個基站的信號強度相似度時，對歐氏距離加以權值 Wj，Wj和待測點與參考點之間RSSI 相似度的計算公式分別為：

式中：RSSIj為第j 個基站的信號強度RSSI 值；Rij為位置指紋庫中第i 個參考點接收到的第j 個基站的信號強度RSSI 值；m 為位置指紋庫中參考點的個數；n 為待測點接收到的基站的個數。

2.3 整體改進算法流程

本文在動態加權最近鄰算法的基礎上做了改進，具體流程為：離線階段，通過FCM 算法進行定位區域劃分，生成聚類指紋庫。在線階段，首先計算待測點與各區域聚類中心的相似度，確定待測點所在的目標區域；然后根據RSSI 強度加權后的待測點與目標區域參考點的指紋信息，設定閾值，動態選擇k 值，從而剔除距離偏遠的參考點；再次通過RSSI 地址序列匹配的方法，只信任最強的基站，進一步篩選出k 個中最優的參考點；最后計算最優參考點對應坐標的加權平均值，作為待測點的最終估計位置，其流程如圖1 所示。

圖1 算法流程

3 實驗與結果分析

3.1 實驗描述

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

圖2 實驗環境

3.2 結果分析

3.2.1 FCM 區域劃分實驗

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

圖3 FCM 區域劃分

3.2.2 在線定位實驗

1）318 房間定位實驗。在318 房間4 個已知點上分別采集10 s 的RSSI 數據，運用本文的改進算法和EWKNN 算法進行數據處理，對2 種結果進行比較。

分別計算2 種算法的定位誤差（如圖4（a）所示）和誤差累計概率分布（如圖4（b）所示），并將各類數據進行統計（如表1 所示）。本文將最小定位誤差、最大定位誤差、平均誤差和不同定位 精度下的誤差累計概率作為衡量定位精度的標準。

圖4 2 種算法定位誤差與誤差累計概率

表1 2 種算法精度對比

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

2）走廊區域定位實驗。在走廊區域2 個已知點上分別采集10 s 的RSSI 數據，運用本文的改進算法和EWKNN 算法進行數據處理，對2 種結果進行比較。

分別計算2 種算法的定位誤差（如圖5（a）所示）和誤差累計概率分布（如圖5（b）所示），并將各類數據進行統計（如表2 所示）。

表2 2 種算法精度對比

圖5 2 種算法定位誤差與累計概率

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

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

4 結束語

本文提出的最強基站MAC 地址匹配的RSSI加權的改進室內定位方法，能夠在室內復雜環境下有效剔除距離偏遠的參考點，削弱信號不穩定對定位結果的影響，提高定位精度，并且降低定位計算的復雜度，對室內定位的研究有一定的參考價值。但隨著室內應用場景越來越多、室內面積越來越大，如何做好離線指紋庫的快速采集和有效維護是接下來要進一步研究的工作。