基于GAWK-means的地鐵車站指紋定位方法

金 霄，吳 飛，鄢 松，陸雯霞，張忠藝

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

隨著城市軌道交通的不斷發(fā)展[1]，在推進智慧地鐵建設時，需要將地下空間的精準定位技術作為保障來實現(xiàn)人員和物資設備的精準定位，以便達到降本增效的目的。藍牙技術雖發(fā)布于1998年，但直到2013年，基于低能耗藍牙(Bluetooth Low Energy，BLE)的iBeacon室內(nèi)定位系統(tǒng)才開始被用于定位。隨著對市場和藍牙技術的深入了解，藍牙技術在基于位置服務(Location Based Services，LBS)領域有著越來越多的業(yè)務使用場景[2]。

在地鐵車站環(huán)境下，利用無線定位技術實現(xiàn)定位主要采用多邊定位法和指紋匹配定位法。其中，指紋匹配法相較于多邊定位法具有更好的定位精度[3-4]。在2009年，日本名古屋大學設計了一種基于WiFi技術的地鐵信息指紋定位系統(tǒng)[5]，通過對名古屋市地下83個站點，1 777個接入點(Access Point,AP)，共28 620個采樣點指紋采集，在iPod Touch終端構建了7個地鐵信息應用程序為市民的生活提供服務。此外，上海地鐵也利用藍牙技術對地鐵車站空間內(nèi)的定位導航平臺進行了初步建設[6]。指紋匹配定位法憑借其較高的定位精度，被廣泛應用于室內(nèi)定位領域，但是在較大空間下使用指紋匹配定位容易降低匹配效率。針對此問題，國內(nèi)外學者也展開了相應的研究。文獻[7]提出利用最遠空間數(shù)據(jù)的最小相關性和易于收斂的特點縮短聚類時間，提高聚類效果和定位精度。文獻[8]提出通過層次聚類的思想對二分K-means聚類算法進行改進，并結合變色龍算法將部分劃分過細的簇合并，減小了定位誤差。文獻[9]研究了歐式距離加權系數(shù)對K-means算法的影響，并利用Iris數(shù)據(jù)集對提出的4種權重系數(shù)進行聚類結果的比較，證明了利用加權系數(shù)可提升算法的整體效益。

基于此，本文主要通過研究地鐵環(huán)境的iBeacon指紋定位技術，針對傳統(tǒng)K-means容易陷入局部最優(yōu)的缺陷，提出基于GAWK-means的地鐵車站定位方法。該方法在傳統(tǒng)K-means的誤差準則函數(shù)歐式距離部分，根據(jù)數(shù)據(jù)本身的離散程度進行權重優(yōu)化使其更好地體現(xiàn)類內(nèi)相似度。為解決聚類結果陷入局部最優(yōu)的問題，本文將改進的K-means結合遺傳學思想來優(yōu)化聚類結果。最后，在試點地鐵車站現(xiàn)場采集數(shù)據(jù)并進行實驗，結果表明本文所提出的優(yōu)化算法提高了指紋定位的精度。

1 iBeacon指紋聚類定位技術

指紋定位技術是近年來室內(nèi)定位技術的研究重點。指紋法雖然不需要在信號強度和距離中建立轉(zhuǎn)化模型，但需要將環(huán)境的位置與特定的指紋聯(lián)系起來[10-11]。相較于WiFi技術，iBeacon技術具有低功耗、易布置、定位精度高的特點。此外，在地鐵車站環(huán)境下，WiFi路由器需要獨立供電，故具有一定的建設復雜性。在實際定位中，iBeacon指紋定位過程主要分為兩個階段：離線階段和在線階段[12-13]。離線階段中，首先需設定坐標系，并進行網(wǎng)格劃分設定采樣點。在所有采樣點中，第i個位置，測量j次來自m個接入點的接收信號強度(Received Signal Strength，RSS)，最后匯總所有RSS數(shù)據(jù)，對數(shù)據(jù)清洗并對數(shù)據(jù)預處理。在得到原始指紋庫后，利用聚類算法對指紋庫聚類分類。在線階段中，需要選擇適合的匹配算法將實時采集的指紋數(shù)據(jù)和歐式距離最為接近的子指紋庫匹配來獲取最終位置。圖1為iBeacon指紋聚類匹配整體流程。

目前指紋匹配算法中使用最廣的是K近鄰(K-Nearest Neighbor，KNN)。KNN是模式識別統(tǒng)計學方法，從定位角度理解，KNN是在在線階段采集的RSS中選擇前k個歐式距離最小的位置指紋，然后計算指紋對應位置坐標的平均值，并將其作為定位結果。其中歐式距離代表在線采集RSS和指紋庫中RSS向量的接近程度[14]，即

(1)

(2)

式中，(xi,yi)為第i個采樣點的位置坐標；(x,y)為待定位點坐標；di為待定位點和第i個采樣點的歐式距離；i=1,2,…,m；j=1,2,…,n。

2 傳統(tǒng)K-means聚類算法

K-means聚類算法是一種無監(jiān)督學習的迭代求解聚類分析算法，由于具有簡潔性和高效性在工程應用中被廣泛使用[15]。假設定義一個由n個數(shù)據(jù)構成的原始數(shù)據(jù)集合(p1,p2,…,pn)，每個pi為m維向量。K-means算法的目的是在給定分類組數(shù)為K的條件下，將原始數(shù)據(jù)分成K類。K值一般通過手肘方法[16]確定，并在數(shù)值模型上求平方誤差準則函數(shù)E的最小值

(3)

式中，p為數(shù)據(jù)集中的對象；zi為簇Ci的均值。

其算法步驟主要由以下幾部分組成：

步驟1從原始數(shù)據(jù)集合中隨機取K個元素，作為K個簇各自的中心；

步驟2分別計算剩下的元素到K個簇中心的平方誤差值E1，將這些元素分別劃歸到相異度最低的簇；

步驟3根據(jù)聚類結果，重新計算K個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數(shù)；

步驟4將數(shù)據(jù)集合中全部元素按照新的中心重新聚類，計算平方誤差值E2；

步驟5若|E1-E2|≤e，則迭代結束，否則E2賦值給E1，轉(zhuǎn)入步驟4；

步驟6將結果輸出。

傳統(tǒng)K-means算法在聚類過程中容易由于初始值的隨機性而陷入局部最優(yōu)[17]，這將導致聚類效果不準確，影響定位精度。為解決這一問題，本文接下來將對傳統(tǒng)K-means算法進行改進。

3 遺傳算法和改進的K-means算法結合

3.1 遺傳算法

遺傳算法(Genetic Algorithms，GA)是一種自適應全局優(yōu)化搜索算法[18]。GA算法源于生物學遺傳進化原理，包括生物的繁殖、交配、變異3個現(xiàn)象。其在搜索過程中使用適應度函數(shù)來度量群體中各個個體的優(yōu)化計算中有可能達到最優(yōu)解的優(yōu)良程度，因此有可能會跳出局部最優(yōu)解，從而達到全局最優(yōu)的效果。

首先采用GA算法對數(shù)據(jù)進行編碼操作，將問題解空間的可行解表示成遺傳空間的基因型染色體串結構數(shù)據(jù)。串結構數(shù)據(jù)的不同組合構成了不同的可行解。接下來進行遺傳迭代過程，其中遺傳算法主要構成要素包括個體適應度評價函數(shù)、選擇算子、交叉算子、變異算子，其中3個算子在一定的概率參數(shù)控制下產(chǎn)生后代，用后代群體替換雙親群體，產(chǎn)生新一代個體并保持數(shù)目不變。然后重新進行適應度函數(shù)計算，不斷循環(huán)，直至滿足終止條件。最后，解碼獲得最優(yōu)解，代表問題獲得解決。

3.2 GAWK-means算法

在離線階段，傳統(tǒng)K-means聚類各個采樣點的指紋向量和每次聚類中心的相似程度多采用歐式距離表示。本文從不同AP的RSS數(shù)據(jù)本身角度出發(fā)，通過分析不同AP的離散程度來確定加權系數(shù)的大小，例如AP1的離散程度比AP2大，則認為AP1在聚類中起著重要作用，給予其較高的權重來調(diào)整特征空間。這樣操作可以體現(xiàn)出較好的類內(nèi)相似度，從而提高聚類效果。本文描述離散程度的指標為變異系數(shù)(Coefficient of Variation，CV)。CV為標準差與其平均數(shù)之比，不僅可以比較兩組數(shù)據(jù)的離散程度，還可以消除測量尺度和量綱的影響。本文定義每個AP的加權系數(shù)為(w1,w2,…,wc)，則利用CV獲得的加權系數(shù)為

(4)

式中，sj表示第j個AP對應數(shù)據(jù)對象的標準差；avr表示第j個AP對應數(shù)據(jù)對象的平均值；rssij表示第j個AP對應的第i個采樣點的RSS值。

加權后的歐式距離為

(5)

式中，wj為權重系數(shù)。

由于初始聚類中心的設置是隨機的，所以聚類容易陷入局部最優(yōu)，于是研究人員常將全局優(yōu)化算法機制引入聚類分析。本文將GA算法與改進的 K-means 算法結合，利用GA 算法的全局尋優(yōu)能力來彌補 K-means 算法容易陷入局部最優(yōu)的不足。本文GA優(yōu)化K-means編碼方式采用基于聚類劃分的整數(shù)編碼，適應度函數(shù)f的定義如式(6)所示。類內(nèi)離散度和越小，適應度值越大。

(6)

式中，E為簇內(nèi)誤差平方和。

本文GAWK-means算法步驟如下：

步驟1輸入聚類指紋數(shù)據(jù)集，類別數(shù)量為K，群體規(guī)模為M，交叉概率為Pc，變異概率為Pm，當前迭代次數(shù)為lcur，最大迭代次數(shù)為lmax，隨機產(chǎn)生初始群體包含M個個體；

步驟2開始循環(huán)，lcur>lmax；

步驟3計算改進后的誤差準則函數(shù)E，記錄各代最優(yōu)值，計算串適應度函數(shù)f；

步驟4采用輪盤賭策略進行選擇操作；

步驟5以概率Pc生成一個交叉位，從中間群體隨機選擇兩個個體，單點交叉操作，直至全被選擇；

步驟6對所有個體以概率Pm對染色體中的每一位進行變異運算，生成子代群體；

步驟7再對新生成的子代群體進行評估；

步驟8保留M個個體，形成下一代群體；

步驟9更新lcur=lcur+1，若lcur>lmax則結束循環(huán)，否則返回步驟3；

步驟10將總的最優(yōu)個體的染色體解碼，返回給各個樣本類別號；

步驟11輸出最優(yōu)聚類劃分。

4 實驗驗證與分析

4.1 實驗環(huán)境

本文的實驗場地為上海地鐵諸光路站站廳層。區(qū)域采樣點分布如圖2所示，其中實驗區(qū)域長度為101 m，寬度為19 m。實驗測試環(huán)境的AP為地鐵站廳層已布置的AP，共42個iBeacon。實驗中不會隨意更改AP或者加入其他AP。信號采集工具為自主開發(fā)的軟件，采集RSS信息的設備為華為P20。每4個小網(wǎng)格組成1個大網(wǎng)格，以大網(wǎng)格中心為采樣點，共有289個采樣點，時長為60 s，采集的頻率為5 Hz，每個采樣點采集到120個左右的藍牙節(jié)點，其中包括用于指紋定位的42個iBeacon。本文對除了42個iBeacon外的其他藍牙數(shù)據(jù)進行刪除，對重復數(shù)據(jù)作均值處理，部分缺失數(shù)據(jù)統(tǒng)一用-99表示，以構建一個較為健壯的指紋庫。在定位結果方面，為將定位結果量化，利用真實值與測量值之間的距離定義為誤差，即

圖2 AP站廳層付費區(qū)采樣點分布

(7)

式中，(xi,yi)為測試點的實際物理位置；(x′i,y′i)為測試點的估算位置坐標。

4.2 實驗結果分析

本文對站廳層289個采樣點構成的指紋庫利用GAWK-means算法進行聚類優(yōu)化，目的是獲得K個較優(yōu)的子指紋庫，并將提出的算法與未聚類和傳統(tǒng)K-means算法進行定位誤差比較。將實驗中參數(shù)設置為M=100，lmax=800，Pc=0.8，Pm=0.2。根據(jù)肘方法對K值進行設定，根據(jù)反復實驗，將KNN算法中的K值選擇為4。本文中的289個采樣點部分指紋信息如表1所示。

表1 采樣點部分指紋信息

圖3表示利用手肘法的指紋數(shù)據(jù)集K值曲線。由圖可知，K值取4～6時較優(yōu)。圖4表示本文提出的GAWK-means優(yōu)化算法在K值為5的情況下誤差準則函數(shù)迭代圖。優(yōu)化后的簇內(nèi)誤差準則函數(shù)相比優(yōu)化前更小，且通過實驗可知在K取5時迭代效果較好，故K值取5。

圖3 手肘法K值選擇

圖4 遺傳算法優(yōu)化迭代曲線

圖5是K取5時，傳統(tǒng)K-means和改進聚類算法聚類結果在二維坐標的映射。由圖可以看出，本文所提算法下的聚類分布更加均衡。

(a)

圖6所示為本文提出的聚類算法、傳統(tǒng)K-means聚類算法和未聚類處理的定位誤差累計概率分布圖。表2所示為3種方法的匹配定位時間對比。從圖6可以看出，本文提出的GAWK-means聚類的總體定位效果更好，算法整體穩(wěn)定且明確。由表2可見經(jīng)過聚類后的指紋匹配時間效率更高。結合定位誤差累計分布概率圖可直觀地看出，本文提出的GAWK-means定位系統(tǒng)平均定位誤差達到1.52 m，比傳統(tǒng)K-means聚類和未經(jīng)聚類的定位系統(tǒng)平均定位誤差縮小了0.41 m以上，具有更優(yōu)的定位精度和匹配效率。

圖6 不同方法的定位誤差累積概率分布圖

表2 不同方法定位時間對比

5 結束語

本文在地鐵環(huán)境下利用iBeacon技術進行定位。采用指紋匹配法，在離線指紋庫建立階段，提出了一種基于GAWK-means的指紋聚類方法。該方法在傳統(tǒng)K-means的誤差準則函數(shù)部分，根據(jù)數(shù)據(jù)本身的離散程度進行歐式距離權重優(yōu)化來更好地體現(xiàn)類內(nèi)相似度。為減少聚類結果陷入局部最優(yōu)的情況，本文將改進K-means結合遺傳算法優(yōu)化聚類結果，并對聚類結果利用KNN算法進行定位評估。對比驗證可知本文提出的算法定位系統(tǒng)的性能優(yōu)于傳統(tǒng)K-means聚類和未聚類的定位系統(tǒng)。GAWK-means可以有效提高在地鐵空間下藍牙指紋定位系統(tǒng)的定位精度和定位效率。在今后的研究中，可以通過在聚類初始點的選擇上進行優(yōu)化，使得指紋聚類更加合理，從而獲得更優(yōu)的定位效果。