基于層次聚類(lèi)和貝葉斯的室內(nèi)定位算法

常津銘 王紅蕾

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

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

中圖分類(lèi)號(hào)：TP39? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? 文章編號(hào)：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ù)也變得越來(lái)越完善，但是GPS信號(hào)只有在目標(biāo)與位置間無(wú)遮擋才能準(zhǔn)確定位，然而越來(lái)越多的高樓大廈出現(xiàn)在城市中，這使得GPS在高樓之間的定位結(jié)果不準(zhǔn)確，甚至出現(xiàn)無(wú)法定位的情況，單純的室外定位服務(wù)已無(wú)法滿(mǎn)足需求，因此，室內(nèi)定位技術(shù)的地位日益重要[1]。

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

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

1 基于層次聚類(lèi)和改進(jìn)貝葉斯的定位算法

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

1.1 離線(xiàn)階段層次聚類(lèi)劃分

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

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

⑴

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

⑵

均值距離（ML層次聚類(lèi)）：

⑶

平均距離（AL層次聚類(lèi)）：

⑷

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

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

⑵ 按參考點(diǎn)距離進(jìn)行劃分，首先計(jì)算參考點(diǎn)兩兩之間的歐氏距離Dij。

⑸

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

⑶ 最終劃分完之后，計(jì)算出每個(gè)簇的質(zhì)心所在位置的信號(hào)強(qiáng)度，并存儲(chǔ)。

⑹

其中，k表示該簇中元素的個(gè)數(shù)，RSSIin表示在i位置參考點(diǎn)接收來(lái)自APn的信號(hào)值。

1.2 改進(jìn)的貝葉斯算法

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

⑺

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

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

綜上所述，在線(xiàn)定位階段的步驟為以下。

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

⑻

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

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

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

⑼

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

2 實(shí)驗(yàn)分析及性能評(píng)估

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

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

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

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

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

2.2 實(shí)驗(yàn)結(jié)果及分析

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

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

3 總結(jié)

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

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

參考文獻(xiàn)（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] 汪倫杰，廖興宇，潘偉杰等.基于信號(hào)均值濾波+ k-means+WKNN的Wifi指紋定位算法研究[J].微電子學(xué)與計(jì)算機(jī)，2017.34（3）：30-34

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

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

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

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