基于改進BKM聚類算法的WiFi室內定位方法

(上海工程技術大學 電子電氣工程學院，上海 201620)

近幾年，移動手機越來越普及，人們生活方式發生顯著變化，基于用戶位置服務(Location Based Services，LBS)也得到快速發展，同時對于定位技術的要求也越來越高。在室外，目前應用最為廣泛的是基于衛星信號的定位技術，像谷歌地圖、百度地圖、高德地圖等一批較成熟的產品，在室外已經可以給用戶提供高精度的定位服務。但是在室內，都是密集的鋼筋建筑，衛星信號會容易被削弱或阻擋，導致用戶無法進行可靠的定位，而室內又是人類活動的主要場所，用戶在室內對于LBS的需求更大，同時針對復雜的室內環境，對于定位技術的要求也更高，所以展開對室內定位技術的相關研究具有重要的意義[1]。

目前常見的室內定位技術有UWB、RFID、ZigBee等技術，雖然以上這些定位技術都能實現對室內用戶終端的定位，但同時也都需要依靠一些特定的硬件設備，部署成本高，很難進行大范圍的推廣。隨著WiFi技術的成熟，在很多場所已經實現WiFi全覆蓋，尤其是在大型的商場、地下停車場等公眾場所。因為WiFi具備自身部署成本低、響應時間快的特點。WiFi已經成為目前室內定位應用上普遍采用的技術之一，同時對WiFi定位技術的研究也越來越廣泛[2-3]。

通過WiFi在空間中的電磁接收信號強度(Received Signal Strength,RSS)，對室內目標進行定位是當前主要方法之一。其中，用的最多的是基于位置指紋的定位方法，通過利用WiFi電磁信號在空間中的分布規律作為定位基礎，實現方法簡單、定位精度高。文獻[4]提出一種K-means聚類算法運用于WiFi室內指紋數據庫的建立階段，改進了指紋數據庫聚類中心選擇的復雜度，但是當指紋數據之間的差異比較大時，該方法可能出現大的子類被過度分割反而降低定位的準確度。文獻[5]提出了內核K-means算法，并結合SVM，減少了非線性SVM的訓練樣本，大大減少了采樣時間復雜度，但是這種方法也容易導致局部定位區域過擬合現象。文獻[6]～文獻[9]都是利用BKM聚類算法來優化定位方法，提高了定位精度，但是BKM聚類算法和經典的K-means聚類算法一樣，在聚類前都需要隨機的確定聚類個數，這樣導致聚類的結果容易受到聚類個數的影響。

針對BKM聚類算法在指紋定位過程中存在的不足，本文結合層次聚類的方法對BKM聚類算法進行改進，通過設置聚類準則函數，不需要在聚類前就初始化聚類個數，可以自動確定聚類個數，并結合Chameleon聚類算法，對一些過度劃分的簇，以及偏移的點進行歸并，優化聚類效果，提高定位精度。

1 基于WiFi電磁指紋定位方法

位置指紋定位方法主要是分為兩個階段完成，分別是離線訓練和在線匹配[10]。離線階段系統采集定位區域內各個參考點接收來自不同無線訪問節點(Access Point,AP)反饋的RSS，與參考點的物理地址進行一一映射，建立位置指紋向量并存儲在數據庫中；在線階段時采集待測點的位置指紋信息，與數據庫中指紋信息進行匹配，最后估算出當前用戶的位置，定位流程如圖1所示。

2 BKM聚類算法

BKM聚類算法基本思想如下：首先初始化簇表S，使S包含所有點組成的簇。然后，隨機從S中選取一個簇ci，通過K-means算法，對選定的簇ci二分，并計算每個簇的最小誤差值，選擇誤差最小的兩個簇，再將得到的兩個簇加入S中，更新簇表S。這樣反復下去，直到最終產生K個簇[11]。

這里通過誤差平方和(SSE)作為目標函數，來衡量聚類質量。SSE的定義如下：

圖1 位置指紋定位方法流程圖

(1)

式中,ci為簇的聚類中心，x為該簇中的一個樣本。

以上過程隱含著一個原則是：聚類性能是通過SSE值來進行衡量的，所以SSE值越小越好，聚類效果也就越好。對上述簇的劃分過程不斷重復，直到最后簇數目達到目標值為止，與K-means算法相比，BKM算法可以加速K-means算法的執行速度，能夠克服K-means收斂于局部最小的缺點，但是BKM聚類算法仍然受初始設定的聚類個數影響。

3 改進的BKM聚類算法

BKM聚類算法與經典K-means聚類算法相比，雖然在計算效率上有所提高，但是在計算過程中需要進行多次K-menas聚類，增加了計算時間上的復雜度。所以，在此基礎上，本文對BKM算法進行改進，聚類前不需要初始設定聚類個數，通過二分聚類一次，就可以得到最小SSE的簇集。算法要求首先引入一個聚類測度函數f:

(2)

式中,xij為樣本(xi1,xi2,…,xin)中的對象，ci為簇中樣本的類中心。選擇一個樣本x={x1,x2,…,xn},樣本包含n個數據對象，分別給定迭代次數和測度函數一個初始值，然后隨機地在樣本中選擇一個ci，并將該ci作為聚類中心，加入到簇表s={s1,s2,…,sk}中。在簇表中選擇一個SSE最大的簇，然后在該簇中找出與該簇中心歐氏距離最大的一個樣本xi，再找出與樣本xi歐氏距離最大的樣本xj，同時將得到的兩個點，作為新的初始的聚類中心，生成兩個新簇，重新計算聚類中心為X1,X2，將其加到簇表中，同時刪除舊的聚類中心，并更新簇表，再計算測度函數ft的值，其中t表示迭代次數。

改進后的BKM算法如下：

輸入 數據集x={x1,x2,…,xn}

輸出 聚類結果X={X1,X2,…,XK}

初始化：f=0.01，t=1,s={}

Begin

Repeat

選擇一個聚類中心，作為初始中心，并將該聚類中心加入到簇表中

選取SSE最大的簇

找出該簇中與簇中心最遠的點以及與該點最遠的點，將這兩個點作為新的聚類中心

將這兩個新的聚類中心加到簇集S中，刪除舊的簇中心

計算當前聚類準則函數的值，與判斷值進行比較

Until

ε>Δ(閾值)

輸出所有聚類結果

初步改進后BKM聚類算法通過設定合理的ε值和測度函數，可以自動確定聚類個數，這樣就不用和BKM聚類算法一樣，需要多次進行K-means計算的過程。但是當ε值選擇不合適的時候容易將數據集劃分過細，所以引進Chameleon算法，根據相近程度合并這些劃分過細的簇。具體方法是通過計算簇表中任意兩個簇的互連性RI和緊密性RC這兩個指標來判定，當RI和RC的值都比較大時才合并這兩個簇[12]。

相對互聯度RI：

(3)

相對近似性RC：

(4)

R=RI(Ci,Cj)×RC(Ci,Cj)α

(5)

其中α為指數，通常大于1。

優化后的算法如下：

輸入 二分聚類后的聚類結果X={X1,X2,…,XK}

輸出 輸出合并后的聚類結果

通過改進BKM聚類算出新的聚類結果，將其中每一個簇看成一個整體

Begin

Repeat

計算每個簇與鄰近每個簇的RC和RI值，得到簇間相似度矩陣

構造K-最近鄰圖，并對其進行劃分

合并對于相似度函數具有最大值的簇

Until

滿足條件

輸出新的聚類結果

4 仿真與驗證

4.1實驗環境

本文通過實驗來驗證定位方法的提高，選擇的實驗環境為本校1號實訓樓的一層實驗室及走廊，實驗用的AP為該樓層現有的部分AP，且選取10個大部分采樣點都能接收到信號的AP。實驗用的信號采集設備為聯想Lenovo天逸310筆記本，通過內置無線網卡和自主開發的采集軟件進行信號采集。

實驗共選取了246個指紋采樣點，每個指紋采樣點處連續采集120組數據，時間間隔為1 s，以1.5 m×1.5 m作為采樣間隔，指紋采樣點分布如圖2所示。為了更好地量化定位效果，所以定義一個用來判斷誤差的函數為：

(6)

圖2 實驗區指紋采樣點參考圖

4.2 數據預處理

因為在實驗過程中會受到人員走動、開關門的影響，室內的RSS具有不穩定性，所以聚類前需要對每個采樣點采集到的多組數據進行預處理，對數據中的離群值進行剔除，保證數據指紋庫的穩定性和可靠性，有利于建立更加精確的指紋數據庫。常用的數據預處理方法有3σ法、Chauvenet法、Grubbs法和狄克遜法。本文主要采用3σ法，對初始數據集進行預處理。如圖3為預處理前后的RSS變化曲線對比。

4.3 實驗結果分析

本文主要通過三種算法進行實驗對比，分別是K-means、BKM和改進BKM，表1為實驗設定的相關參數。

為了直觀展示效果，對實驗結果進行量化，圖4給出了三種算法的定位誤差平均值，可以看出改進的BKM的平均定位誤差為1.2125 m，要比K-meanc和BKM平均誤差降低48.6%和26.5%。

圖3 數據預處理前后的RSS變化曲線對比

實驗區域數據集大小(n)聚類個數K經典K-meansBKM改進BKM區域176333區域298444區域372334

圖4 三種不同算法的平均定位誤差

圖5為不同算法的實際定位誤差累計概率圖，從圖中可以看出，改進的BKM算法在定位結果中，有90%的定位目標誤差范圍在2.5 m內。作為比較，經典的K-means和BKM在2.5 m范圍內的定位誤差概率只有78%和82%。綜合以上所述，可以說明本文提出的改進的BKM算法在定位精度上要比K-means和BKM算法好。

表2所示的是三種算法在3個不同區域上的平均定位時間。從表2中可以看出，BKM聚類在性能上要比經典的K-means聚類算法好，在定位時間上平均快0.44 s，但是相較于BKM算法和經典K-means算法都需要提前確定聚類個數，改進的BKM聚類算法，不用提前指定聚類的個數K值，通過設置聚類準則函數就

圖5 三種算法的定位誤差累計分布概率

表2 不同算法的平均定位時間 單位：s

5 結束語

在室內復雜的環境下，WiFi電磁信號由于受到多徑效應的影響，導致定位精度不高、誤差偏大。本文在分析經典K-means聚類算法和BKM算法的基礎上，提出一種改進的BKM聚類方法，在指紋庫構建階段通過設置聚類測度函數，可以自動獲取聚類的個數，不需要初始化聚類個數，提高了指紋聚類的效果，同時引進Chameleon算法對初步聚類后的結果進行優化，合并一些不合理的簇，提高指紋在線定位階段的可靠性和定位精度。實驗結果表明，通過利用本文的改進方法，能夠將定位平均誤差控制在1.2125 m左右，定位誤差在2.5 m以下的概率也達到了90%。

利用WiFi和位置指紋的定位技術，定位效率高、成本低，市場應用廣泛。而本文提出的定位方法能夠在一定程度上提高定位精度，減少定位時間，增強用戶的定位體驗，具有很好的現實意義。