常津銘 王紅蕾

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

關(guān)鍵詞： 室內(nèi)定位; 層次聚類; 貝葉斯; 實時性

中圖分類號：TP39? ? ? ? ? 文獻標(biāo)志碼：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 引言

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

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

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

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

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

1.1 離線階段層次聚類劃分

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

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

⑴

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

⑵

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

⑶

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

⑷

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

⑴ 將定位區(qū)域均勻劃分后，設(shè)置參考點，并在參考點采集數(shù)據(jù)，進行處理后存儲。

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

⑸

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

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

⑹

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

1.2 改進的貝葉斯算法

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

⑺

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

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

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

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

⑻

找出與M點最近的質(zhì)心所在的簇C。

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

⑶ 將K個參考點的概率作為權(quán)值賦予其對應(yīng)的坐標(biāo)進行加權(quán)平均，計算公式為：

⑼

其中（x，y）為最終坐標(biāo)。

2 實驗分析及性能評估

2.1 實驗環(huán)境和數(shù)據(jù)采集

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

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

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

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

2.2 實驗結(jié)果及分析

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

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

3 總結(jié)

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

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

參考文獻（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].微電子學(xué)與計算機，2017.34（3）：30-34

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

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

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

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