基于層次聚類和貝葉斯的室內定位算法

常津銘 王紅蕾

摘? 要： 針對目前基于WiFi的位置指紋室內定位算法精度不高，計算消耗時間過長，實時性差的問題，提出一種改進的室內定位算法。首先利用層次聚類的算法進行預匹配，縮小定位區域，達到降低匹配數據，提高實時性的目的，然后利用貝葉斯算法進行定位。實驗結果表明，所提出的定位算法在精度和定位實時性方面都有了很大的改善。

關鍵詞： 室內定位; 層次聚類; 貝葉斯; 實時性

中圖分類號：TP39? ? ? ? ? 文獻標志碼：A? ? 文章編號：1006-8228（2019）02-05-04

Indoor location algorithm based on hierarchical clustering and Bayesian

Chang Jinming， Wang Honglei

（School of Electrical Engineering， Guizhou University， Guiyang， Guizhou 550025， China）

Abstract： In order to solve the problems of low precision， long computation time and poor real-time of WiFi-based position fingerprint indoor location algorithm， an improved indoor location algorithm is proposed. Firstly， the hierarchical clustering algorithm is used to pre-match， reduce the location area， reduce the matching data and improve the real-time performance. Then， Bayesian algorithm is used to locate. The experimental results show that the proposed location algorithm has a great improvement in accuracy and real-time positioning.

Key words： indoor location; hierarchical clustering; Bayesian; real-time

0 引言

目前，隨著全球衛星定位系統（GPS）的日益成熟，室外位置服務也變得越來越完善，但是GPS信號只有在目標與位置間無遮擋才能準確定位，然而越來越多的高樓大廈出現在城市中，這使得GPS在高樓之間的定位結果不準確，甚至出現無法定位的情況，單純的室外定位服務已無法滿足需求，因此，室內定位技術的地位日益重要[1]。

國內外學者針對室內定位做了大量的研究，傳統的室內定位技術有基于藍牙、RFID、地磁、紅外線、超寬帶、WiFi等方法，前幾種方法都存在相應的缺陷，要么需要特殊的傳感器，導致成本過高，要么定位區域有限制，使得精度過低等。基于WiFi的室內定位技術由于其成本低廉，不需要額外的傳感器，并且精度可靠等原因，成為了研究的熱點。WiFi定位技術主要分為：①基于傳播模型的定位方法;②基于位置指紋的定位方法[2]。其中，基于位置指紋的方法不需要知道AP（信號發射器）具體位置，且由于算法簡單精度較高，受到了廣泛的關注和研究。高仁強[3]等人結合模糊數學理論的方法對傳統的定位算法進行改進，提高了定位精度;李軍等[4]人利用隨機森林算法對指紋數據進行訓練和分類，縮短了定位時間，提高了系統的可靠性;曹曉祥等[5]人針對位置指紋的幾何結構對傳統的WKNN算法進行改進，提高了定位的精度。

眾多的算法在匹配臨近點的時候，大多會由于WiFi信號的波動，導致定位偏差，并且定位算法在匹配過程中依靠單一變量，這也造成精度不夠。針對此，提出一種融合層次聚類和樸素貝葉斯的新算法，先利用層次聚類算法進行預匹配降低搜索范圍，達到提高定位速度的目的[6]，然后利用改進的貝葉斯算法求解出結果，從而提高精度。

1 基于層次聚類和改進貝葉斯的定位算法

基于WiFi的位置指紋定位算法通常分為兩個階段，離線階段和在線階段。本算法在離線階段，首先對待定位區域進行均勻劃分，最終得到M個參考點，然后記錄每個參考點的坐標，并采集信號，信號為來自各個AP的信號值（RSSI）及MAC地址，最終經過處理，存儲到數據庫中作為匹配數據。每個參考點的信號記錄的格式為：{（xi，yi），（MAC1，RSSIi1），（MAC2，RSSIi2）…}，通過層次聚類質心距離算法對參考點進行劃分，最終得到N個簇。在線階段，則是用戶實時采集數據，預處理數據后，傳輸到服務器端，首先進行預匹配，計算信號與每個簇頭之間的距離，找距離最短簇作為匹配范圍，服務器經過對參考點利用改進貝葉斯算法計算出用戶的實際位置。算法的具體流程如圖1所示。

1.1 離線階段層次聚類劃分

層次聚類可以分為凝聚法和分裂法，其中凝聚法的基本思想是將每個對象均看作單獨的原子簇，然后合并原子簇成為越來越大的簇，當滿足某一條件時停止，分裂法則與之相反，將所有對象均置于一個簇中，然后逐漸分裂為越來越小的簇，當達到某個條件時終止。其中有四個廣泛采用的簇間距離度量方法，其中|Q-Q'|代表兩個對象Q和Q'之間的距離，ni是簇Ai的均值，mi是簇Ai中對象的數目。

最小距離（單連接算法）：

⑴

最大距離（全連接算法）：

⑵

均值距離（ML層次聚類）：

⑶

平均距離（AL層次聚類）：

⑷

本文選取均值距離ML層次聚類算法作為劃分依據，選擇該算法主要是因為單連接算法和全連接算法在距離度量中處于兩個極端，對離群點和噪聲數據過分敏感，而均值距離和平均距離屬于折中辦法，在最大最小距離中可以有效克服離群點的敏感問題，同時均值距離較平均距離更能衡量兩個類之間的簡單距離，更加貼合室內定位場景。初始時將每個元素看作一類，設置距離閾值K，將質心距離最小的兩個類進行合并，當質心距離大于K則停止聚類。離線階段的層次聚類劃分共分為三個步驟。

⑴ 將定位區域均勻劃分后，設置參考點，并在參考點采集數據，進行處理后存儲。

⑵ 按參考點距離進行劃分，首先計算參考點兩兩之間的歐氏距離Dij。

⑸

計算完成后將距離最近的點進行合并，當類的質心距離滿足條件后停止合并。

⑶ 最終劃分完之后，計算出每個簇的質心所在位置的信號強度，并存儲。

⑹

其中，k表示該簇中元素的個數，RSSIin表示在i位置參考點接收來自APn的信號值。

1.2 改進的貝葉斯算法

貝葉斯算法是一種依據貝葉斯和全概率公式進行計算的一種方法，其中先驗概率和后驗概率是核心概念，假設待定位區域有N個參考點，每個參考點的坐標為Ni=（xi，yi），（i=1，2…，N）。指紋數據為（RSSIi1，RSSIi2，…，RSSIin），則待定位點在參考點的坐標概率為P（Ni|m），m代表待定位點的信號強度。則概率求解為：

⑺

其中p（Ni）為參考點出現概率，故為常量。P（m|Ni）則是參考點Ni出現m的概率，選取具有最大概率的參考點作為匹配節點。

由于單個的參考點考慮不合理，所以將所有點概率從大到小排列，然后選取K個最大概率的點，將其概率作為權值賦予對應的點，加權平均最終求取坐標位置。

綜上所述，在線定位階段的步驟為以下。

⑴ 首先根據離線階段的聚類結果，將待定位區域采集的實時信號m=（RSSIi1，RSSIi2，…，RSSIin）與離線階段聚類結果的質心信號進行歐式距離的運算，計算方法為：

⑻

找出與M點最近的質心所在的簇C。

⑵ 根據無線信號強度的區域相似性，可以表明待定位點處于C所在的子區域中，利用改進貝葉斯算法計算待定位點與C中元素概率大小，如式⑺所示，選取K個概率最大的點。

⑶ 將K個參考點的概率作為權值賦予其對應的坐標進行加權平均，計算公式為：

⑼

其中（x，y）為最終坐標。

2 實驗分析及性能評估

2.1 實驗環境和數據采集

為了驗證該算法的定位性能，本文在貴州大學教學樓區域進行了實驗，實驗區域為該學院樓的第五層F5走廊區域。利用該樓現存的WLAN無線網絡進行數據采集，AP具體位置未知。其中實驗區域物理結構，如圖2所示，利用華為手機進行信號采集，每個采樣點采集信號20次，每次間隔2s，求出均值作為該位置參考信號，每個參考點間隔約3m。

考慮到區域實際結構和大小，采樣點分布如圖2所示。為了得到較好的分類效果，在聚類的過程中選取了不同的閾值T進行對比，同時將采集的實時定位數據輸入進行實驗（采集數據步驟將在后面介紹），實驗數據如表1所示。

由針對實驗閾值T的選取實驗結果可知，當T在6、7、8、9時，定位判別準確率隨著T的增大而不斷提高，當T>9時，精度開始降低，從定位平均時間上看，由于采集的樣本數以及定位面積的限制，時間沒有明顯的大變化，但是可以看出花費時間的整體趨勢是不斷減少的，綜合考慮，此次實驗中，選取T為9，即當類聚類距離為9時，停止聚類。

測試定位效果時候，采集定位數據的方法如下：實驗者手持手機勻速走在實驗區域，每隔三秒記錄一次數據，共記錄500次，同時記錄下采集信號的坐標號，并將仿真程序運行到如下配置的PC上：處理器CORE i5，內存：2.0GB，操作系統：Windows 10，MATLAB R2014b。隨機抽取手機記錄的數據作為輸入，進行坐標判別，重復300次，統計精度和誤差。

2.2 實驗結果及分析

將采集好的數據輸入matlab程序中，先利用層次聚類進行劃分，然后將采集好的數據依次輸入到程序中，得到仿真結果，將其與傳統的加權最近鄰算法（WKNN）和貝葉斯算法進行比較，通過統計誤差和定位時間，所得結果如表2所示。

經過仿真分析可知，本文提出的層次聚類貝葉斯判別算法，在實驗區域進行定位實驗，相比于傳統貝葉斯算法和WKNN算法，判別精度有了一定的提升。這是由于改進的算法通過對多個值進行權值賦予，并且通過預匹配縮小范圍，排除了不相關性的干擾。從判別時間上看，由于傳統的貝葉斯算法需要對比每個參考點的信號概率值，所以計算量在三個算法中最大，消耗時間最多，而基于層次聚類的方法，只需要對比每個類的元素概率即可，大大減少了計算量，消耗時間有較大的降低。此外，傳統WKNN算法雖然在時間的消耗上與傳統貝葉斯方法相比減少很多，但是由于精度不夠高，并且需要計算所有參考點與待定位節點信號之間的歐氏距離，定位時間也不如本文算法，故整體效果不如基于層次聚類的改進貝葉斯算法。

3 總結

為了提高定位判別正確率，以及提高定位速度，本文提出了一種基于層次聚類質心距離的聚類方法，通過計算每類質心所包含的無線信號強度與實時信號強度的歐氏距離大小，選取距離最近的類作為預匹配的結果，并在該區域內利用改進貝葉斯進行進一步判定，經過在相關區域進行實驗，驗證了該方法的可行性。與傳統貝葉斯算法和傳統WKNN算法進行了比較，結果顯示，本文方法可以在一定程度上提高定位判別率，并且在定位時間方面有了很大的降低，提高了實時性。

本文研究的方法主要針對二維平面位置，大多數情況下不僅需要知道平面位置，還需要知道樓層號碼，所以接下來，主要針對樓層判別方法進行研究。進一步的研究將對救援、根據位置提供服務、防止人員走丟等方面都有巨大的作用。

參考文獻（References）：

[1] Winternitz L M B，Bamford W A，Heckler G W.A. GPSreceiver for high satellite navigation. IEEE Journal of Selected Topics in Signal Processing，2009.3（4）：541-556

[2] 汪倫杰，廖興宇，潘偉杰等.基于信號均值濾波+ k-means+WKNN的Wifi指紋定位算法研究[J].微電子學與計算機，2017.34（3）：30-34

[3] 高仁強，張曉盼，熊艷，吳水平，晏磊.模糊數學的WiFi室內定位算法[J].測繪科學，2016.41（10）：142-148

[4] 李軍，何星，蔡云澤，徐琴.基于K-means和Random Forest的WiFi室內定位方法[J].控制工程，2017.24（4）：787-792

[5] 曹曉祥，陳國良.一種改進的組合定權的指紋定位算法[J].測繪通報，2018.2：6-10

[6] 王怡婷，郭紅.基于層次聚類的WiFi室內位置指紋定位算法[J].福州大學學報（自然科學版），2017.45（1）：8-15