室內(nèi)定位系統(tǒng)中指紋庫的優(yōu)化方法

馬鑫迪,馬建峰,高 勝

(西安電子科技大學(xué)計算機(jī)學(xué)院,陜西西安 710071)

室內(nèi)定位系統(tǒng)中指紋庫的優(yōu)化方法

馬鑫迪,馬建峰,高 勝

(西安電子科技大學(xué)計算機(jī)學(xué)院,陜西西安 710071)

指紋庫的好壞直接影響到室內(nèi)定位的定位精度,而現(xiàn)有的室內(nèi)定位算法大都是建立在原始指紋庫的基礎(chǔ)之上的,缺乏對指紋庫的優(yōu)化處理.筆者利用k-means算法優(yōu)化指紋庫的構(gòu)建過程,通過聚類的思想剔除已采集指紋庫中的“噪點”,從而為室內(nèi)定位算法提供較好的數(shù)據(jù)樣本源.實驗結(jié)果表明,與現(xiàn)有的室內(nèi)定位系統(tǒng)相比,利用優(yōu)化后的指紋庫進(jìn)行定位能夠明顯提高室內(nèi)定位的精度.

智能終端;k-means方法;指紋庫優(yōu)化;去噪

近年來,基于位置的服務(wù)（Location-Based Services,LBSs)得到廣泛的應(yīng)用.作為LBSs的核心支撐技術(shù),移動定位技術(shù)受到廣泛的關(guān)注.現(xiàn)有的移動定位技術(shù)可分為:室外定位和室內(nèi)定位,其中室外定位已有成熟的系統(tǒng),如全球定位系統(tǒng)（Global Position System,GPS)、北斗等,并且已經(jīng)達(dá)到較高的定位精度,能夠有效地滿足用戶在室外環(huán)境中對精確性的需求.在室內(nèi)環(huán)境下,用戶通常也需要定位自己所在的位置,例如,在大型商場中,用戶利用定位系統(tǒng)定位當(dāng)前的位置,然后按照地圖尋找自己需要的商品.然而,在室內(nèi)環(huán)境中,衛(wèi)星信號穿透建筑物墻壁后,信號衰減非常嚴(yán)重,并且室內(nèi)障礙物較多,環(huán)境比較復(fù)雜,進(jìn)一步引起信號的衰落.因此,室外定位技術(shù)無法應(yīng)用于室內(nèi)環(huán)境中,所以,如何實現(xiàn)高效精確的室內(nèi)定位已成為研究熱點和難點之一.

目前,研究人員致力于部署更加靈敏且精確的室內(nèi)定位系統(tǒng)[1-3].與此同時,用于定位過程中的定位感知技術(shù)也在不斷豐富,如藍(lán)牙技術(shù)、超聲波定位感知技術(shù)、射頻識別技術(shù)及基于無線局域網(wǎng)（Wireless Local Area Network,WLAN)的室內(nèi)定位技術(shù)等.Laoudias等[4]利用指紋庫匹配的方法開發(fā)了Airplace系統(tǒng),其定位精度可達(dá)到2～4 m;Yang等[5]總結(jié)了現(xiàn)有的室內(nèi)定位算法,并利用終端上的傳感器開發(fā)了基于Wi-Fi（Wireless-Fidelity)信號且可在三維空間上實時定位的LIFS定位系統(tǒng);Ozdenizci等[6]則提出采用NFC標(biāo)簽輔助定位的方法,利用終端具有的NFC掃描功能來掃描附近的NFC標(biāo)簽進(jìn)行輔助定位;Yang等[7]提出通過監(jiān)聽物理層信道的狀態(tài)來提高精度;Liu等[8]采用多用戶協(xié)同定位的方法,使用戶定位更準(zhǔn)確;Fang等[9]則通過從已測得的RSS信號值中提取特征性較強(qiáng)的信號,從而降低室內(nèi)環(huán)境中無線網(wǎng)絡(luò)的多徑效應(yīng),使得定位精度提高約40%.

另外,在某些研究工作中,部分學(xué)者利用k-means聚類算法[10]和主成分分析（Principal Component Analysis,PCA)[11]的思想對指紋庫進(jìn)行處理,從而降低計算的復(fù)雜度并提高定位的精度;而Fang等[12]通過研究,提出動態(tài)混合投影（Dynamic Hybrid Projection,DHP)方法對主成分分析和多重判別分析（Multiple Discriminant Analysis,MDA)進(jìn)行優(yōu)勢互補(bǔ),使定位精度得到進(jìn)一步提升.

利用指紋庫中存儲的信號值與當(dāng)前掃描到的信號值進(jìn)行匹配定位是目前室內(nèi)定位算法的主要思路之一.但是,在采集指紋數(shù)據(jù)的過程中,由于信號源功率不穩(wěn)定或者室內(nèi)環(huán)境的變化,會使終端采集到的信號數(shù)據(jù)波動比較大,筆者將這些波動比較大的數(shù)據(jù)稱為信號“噪點”.現(xiàn)有的室內(nèi)定位算法在進(jìn)行定位時大都沒有考慮到對指紋庫的優(yōu)化,而指紋庫的好壞又直接影響到定位的精度,所以,采用未優(yōu)化的指紋庫會在一定程度上影響到定位精度.因此,如何優(yōu)化指紋庫,剔除指紋庫中的信號“噪點”,提高定位精度是要解決的主要問題.

文中采用k-means聚類算法[13]對指紋庫進(jìn)行優(yōu)化處理,把在每一個位置采集到的每個AP的一組信號值作為一個類進(jìn)行計算,將這組信號值中不屬于該類的數(shù)據(jù)剔除掉,即將采集的信號“噪點”剔除.通過部署實驗環(huán)境,采集實驗數(shù)據(jù),并將優(yōu)化后的指紋庫和未優(yōu)化的指紋庫用于同一定位算法進(jìn)行定位結(jié)果對比,結(jié)果表明對指紋庫進(jìn)行優(yōu)化后,定位誤差小于1 m的概率相比于優(yōu)化前有明顯提高.

1 k-means聚類算法

聚類思想[13]是指將一組特征數(shù)據(jù)分為一個一個的類,在一個類之內(nèi)的數(shù)據(jù)相似度比較高,而類之間的數(shù)據(jù)相似度比較低.

筆者采用k-means聚類算法[13]實現(xiàn)對指紋庫的優(yōu)化過程.在聚類問題中,給定訓(xùn)練樣本{x（1),x（2),…,x（n)}.然后,利用k-means算法將樣本聚類成k個簇.例如,將太空中的星星進(jìn)行聚類計算,最終將所有的星星聚集成k個星團(tuán).首先,需要隨機(jī)地選取太空中的k個點（或者k個星星)作為k個星團(tuán)的質(zhì)心,并對每顆星星計算其到每一個星團(tuán)質(zhì)心的距離,選擇距離最近的那個星團(tuán)作為這顆星星所屬的類.經(jīng)計算后,每一顆星星都有了自己的星團(tuán).最后,對于每個星團(tuán),重新計算其質(zhì)心.重復(fù)以上步驟,直到質(zhì)心不變或者變化很小.

在利用k-means算法進(jìn)行指紋庫優(yōu)化時,可以把指紋庫里的信號值看作太空中的星星進(jìn)行聚類計算,首先,計算每個類的質(zhì)心,然后,判斷該類中的每一個元素是否滿足聚類條件屬于這個類,如果不屬于,則刪除元素并重新計算其質(zhì)心;重復(fù)以上步驟直到所有的元素均滿足條件為止.

2 指紋庫優(yōu)化算法及定位算法

首先設(shè)計了指紋庫的優(yōu)化算法;然后,對定位系統(tǒng)中的定位算法進(jìn)行了描述,并解釋了指紋庫優(yōu)化算法在定位算法中的執(zhí)行過程.

2.1 指紋庫優(yōu)化算法

采用k-means聚類算法對指紋庫進(jìn)行優(yōu)化處理.在優(yōu)化處理過程中,可以把每個位置采集到的每個無線接入點（Access Point,AP)的一組信號值作為一個聚類,共有mn個聚類.其中,m為采集的位置個數(shù),n為采集數(shù)據(jù)過程中采集到的所有AP數(shù).

利用k-means聚類算法剔除信號“噪點”的具體實現(xiàn)算法描述如下:

X集合為mn組信號值,xij為第i個聚類中第j個信號值,x[i][].length為第i個聚類中元素的個數(shù),i∈1,2,…,mn,質(zhì)心μi表示第i個聚類的中心,Φ為閾值,當(dāng)信號值滿足時,認(rèn)為信號值xij為“噪點”,將其刪除.

假設(shè)x[i][]集合為終端在位置（a,b)處采集到的某個AP的信號集合,則首先計算集合x[i][]的平均信號值,作為第1輪的中心μi,然后再判斷集合x[i][]中的每個元素是否滿足條件屬于這個聚類,如果不屬于,則直接作為壞點刪除,否則會對構(gòu)建的指紋庫影響比較大,最終會影響到定位的精度.重復(fù)以上步驟,直到集合x[i][]中所有的元素均滿足條件屬于這個聚類為止.利用優(yōu)化算法對數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行優(yōu)化處理,最終計算出mn個聚類的中心作為構(gòu)建指紋庫的元素.

2.2 定位算法

將優(yōu)化后的指紋庫應(yīng)用于加權(quán)k最鄰域（Weighted K-Nearest Neighbor,WKNN)算法[4]進(jìn)行定位測試.WKNN算法的執(zhí)行流程如圖1所示.

圖1 WKNN算法執(zhí)行流程

WKNN算法執(zhí)行過程中,首先需要根據(jù)式（1)計算出Si,（Xi,Yi),Ri1,Ri2,Ri3,…,Rin為存儲在指紋庫中第i個樣本點對應(yīng)的坐標(biāo)及n個AP的信號強(qiáng)度,R′1,R′2,R′3,…,R′n為用戶在當(dāng)前位置采集到的對應(yīng)AP的信號強(qiáng)度,這樣就會求出集合S={S1,S2,S3,…,Sm}.集合S與指紋庫中的m個樣本點坐標(biāo)相對應(yīng),然后,系統(tǒng)將集合S按從大到小的順序排序為集合S′,根據(jù)參數(shù)k從集合S′中選擇出前k個S′i對應(yīng)的坐標(biāo)進(jìn)行定位計算.由于Si表示當(dāng)前位置掃描到的信號值與指紋庫中處理后的信號值的歐氏距離的倒數(shù),所以,可以將集合S的元素作為每個坐標(biāo)的權(quán)重,并利用選擇出的k個點進(jìn)行用戶位置的計算.

文中所采用的k-means算法將用于計算指紋庫中的坐標(biāo)（Xi,Yi)處的元素Ri1,Ri2,Ri3,…,Rin,其計算流程如圖2所示.

圖2 k-means算法流程圖

假設(shè)系統(tǒng)在一個坐標(biāo)處采集了z組數(shù)據(jù),并且每組數(shù)據(jù)有n個AP信號值.首先,系統(tǒng)從數(shù)據(jù)庫中導(dǎo)出采集的原始數(shù)據(jù)（Xi,Yi),Rj1,Rj2,Rj3,…,Rjn,然后利用k-means算法進(jìn)行優(yōu)化計算,將篩選出的“噪點”刪除,如圖2中黑色方格所示,最后將刪選后的數(shù)據(jù)進(jìn)行求中心得到Ri1,Ri2,Ri3,…,Rin作為終端在坐標(biāo)（Xi,Yi)處的特征值.而沒有通過k-means算法優(yōu)化的數(shù)據(jù),如圖2中（Xi,Yi),R′i1,R′i2,…,R′in數(shù)據(jù)所示,由于存在信號“噪點”,所以,得出的R′i1,R′i2,…,R′in特征值與正常值存在明顯偏差,最終導(dǎo)致定位不準(zhǔn)確.

3 實驗及評估

首先描述系統(tǒng)的開發(fā)環(huán)境;然后利用系統(tǒng)采集數(shù)據(jù),并對數(shù)據(jù)集進(jìn)行分析,觀察指紋庫是否需要進(jìn)行優(yōu)化;最后對系統(tǒng)進(jìn)行測試,并對測試結(jié)果進(jìn)行定位精度分析.

3.1 實驗環(huán)境及數(shù)據(jù)分析

由于Android終端設(shè)備處理能力有限,并且存在功耗問題,所以Laoudias等開發(fā)的AirPlace系統(tǒng)存在系統(tǒng)缺陷.筆者在Air Place系統(tǒng)的基礎(chǔ)上進(jìn)行改進(jìn),將主要計算中心從Android終端遷移到服務(wù)器端,使得Android終端計算量減小,從而降低功耗.系統(tǒng)開發(fā)環(huán)境如表1所示.

表1 系統(tǒng)開發(fā)環(huán)境

圖3 數(shù)據(jù)采集

基于實驗室環(huán)境采集數(shù)據(jù)并進(jìn)行系統(tǒng)測試.首先,將系統(tǒng)設(shè)定為每個位置采集30組數(shù)據(jù),每隔0.5 s采集一次,然后,選擇當(dāng)前所處的位置,并采集數(shù)據(jù).采集結(jié)果如圖3所示.

在處理樣本集構(gòu)建指紋庫之前,先對樣本集數(shù)據(jù)進(jìn)行觀察,隨機(jī)抽取終端在某個位置掃描到的某個AP的一組信號值,觀察其波動是否明顯.表2描述了隨機(jī)抽取數(shù)據(jù)的波動大小.

由表2可得,在14 s和25 s處,數(shù)據(jù)存在明顯波動,而且如此大的波動幅度會影響系統(tǒng)定位的精度.所以,可以認(rèn)為14 s和25 s處的數(shù)據(jù)為信號“噪點”,若不刪除,必定會影響定位的精度.因此可以得出,進(jìn)行信號數(shù)據(jù)“去噪”是非常有必要的.

3.2 實驗結(jié)果評估

為了驗證經(jīng)k-means算法優(yōu)化后的指紋庫可以提高定位的準(zhǔn)確率,筆者在實驗室環(huán)境中多次使用設(shè)計的定位系統(tǒng),分別采用優(yōu)化后的指紋庫和未優(yōu)化的指紋庫利用相同的定位算法進(jìn)行定位并記錄定位結(jié)果,然后對結(jié)果數(shù)據(jù)進(jìn)行定位誤差分析.其中一組定位結(jié)果如圖4所示（黑色圓點表示當(dāng)前位置,內(nèi)圓表示離當(dāng)前位置1 m的距離,外圓表示離當(dāng)前位置2 m的距離).

表2 隨機(jī)抽取數(shù)據(jù)波動大小

圖4 定位結(jié)果

從多次試驗中隨機(jī)選取3組定位結(jié)果進(jìn)行分析,并從每組結(jié)果中分別抽取30個,50個,100個誤差點進(jìn)行統(tǒng)計分析,3組統(tǒng)計結(jié)果分別如圖5～7所示.

圖5～7中橫坐標(biāo)表示誤差分別為1 m,2 m,…,5 m,縱坐標(biāo)表示誤差在1 m,2 m,…,5 m內(nèi)的概率.因為3組數(shù)據(jù)分別采集于不同的時間點,信號干擾程度也不同,所以完全可以表現(xiàn)出優(yōu)化后指紋庫的性能.

圖5 1號數(shù)據(jù)結(jié)果分析

圖6 2號數(shù)據(jù)結(jié)果分析

對圖5進(jìn)行分析,可以得出,當(dāng)抽取30個點進(jìn)行對比時,采用未優(yōu)化的指紋庫進(jìn)行定位,誤差在1 m之內(nèi)的概率只有10%,而采用優(yōu)化后的指紋庫進(jìn)行定位,誤差在1 m之內(nèi)的概率達(dá)到了50%;當(dāng)抽取50個點進(jìn)行對比時,采用未優(yōu)化的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率只有8%,而采用優(yōu)化后的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率為38%;當(dāng)抽取100個點進(jìn)行對比時,采用未優(yōu)化的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率為11%,而采用優(yōu)化后的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率為34%.因此,可以得出采用優(yōu)化后的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率更大.

對圖6進(jìn)行分析,可以得出,在采集2號數(shù)據(jù)時,信號干擾比較大,導(dǎo)致定位誤差比較大,但是也可以從統(tǒng)計的結(jié)果分析出優(yōu)化后的指紋庫能使定位更精確.分析結(jié)果顯示采用未優(yōu)化的指紋庫進(jìn)行定位的誤差在1 m之內(nèi)的概率均為0,在2 m之內(nèi)的概率分別為0.07,0.02,0.03,而采用優(yōu)化后的指紋庫的定位誤差在1 m之內(nèi)的概率分別為0,0.14,0.06,在2 m之內(nèi)的概率分別為0.33,0.32,0.21.因此,可同樣說明采用優(yōu)化后的指紋庫進(jìn)行定位能夠提高定位的準(zhǔn)確率.

圖7 3號數(shù)據(jù)結(jié)果分析

對圖7的分析同圖5分析,也能得出同樣的結(jié)論.

因此得出結(jié)論,采用k-means算法進(jìn)行優(yōu)化后的指紋庫能使定位誤差以更大的概率保持在較小的范圍內(nèi),也就是說,優(yōu)化后的指紋庫與未優(yōu)化的指紋庫相比,可以大大提高定位的精度.

4 結(jié)束語

文中引入k-means算法能較好的對指紋庫進(jìn)行優(yōu)化.實驗數(shù)據(jù)分析表明,優(yōu)化指紋庫是有必要的.優(yōu)化后的指紋庫在干擾較小時,能明顯提高定位誤差在1 m之內(nèi)的概率;在干擾較大時,可以同樣使定位誤差在2 m之內(nèi)的概率得到明顯提高.因此可得出結(jié)論,與未優(yōu)化的指紋庫相比,優(yōu)化后的指紋庫可以顯著提高定位精度.

[1]Want R,Hopper A,Falcao V,et al.The Active Badge Location System[J].ACM Transactions on Information Systems,1992,10(1):91-102.

[2]Ward A,Jones A,Hopper A.A New Location Technique for the Active Office[J].IEEE Personal Communications,1997,4(5):42-47.

[3]Priyantha N B.The Cricket Indoor Location System[D].Cambridge:Massachusetts Institute of Technology,2005.

[4]Laoudias C,Constantinou G,Constantinides M,et al.The Airplace Indoor Positioning Platform for Android Smartphones[C]//Proceedings of the IEEE 13th International Conference on Mobile Data Management.Piscataway: IEEE,2012:312-315.

[5]Yang Z,Wu C,Liu Y.Locating in Fingerprint Space:Wireless Indoor Localization with Little Human Intervention [C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.New York: ACM,2012:269-280.

[6]Ozdenizci B,Ok K,Coskun V,et al.Development of an Indoor Navigation System Using NFC Technology[C]// Proceedings of the 4th International Conference on Information and Computing.Piscataway:IEEE,2011:11-14.

[7]Yang Z,Zhou Z,Liu Y.From RSSI to CSI:Indoor Localization via Channel Response[J].ACM Computing Surveys,2013,46(2):25.

[8]Liu H,Gan Y,Yang J,et al.Push the Limit of WiFi Based Localization for Smartphones[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.New York:ACM,2012:305-316.

[9]Fang S H,Lin T N,Lee K C.A Novel Algorithm for Multipath Fingerprinting in Indoor WLAN Environments[J].IEEE Transactions on Wireless Communications,2008,7(9):3579-3588.

[10]Bai S,Wu T.Analysis of k-Means Algorithm on Fingerprint Based Indoor Localization System[C]//Proceedings of the IEEE 5th International Symposium on Microwave,Antenna,Propagation and EMC Technologies for Wireless Communications.Piscataway:IEEE,2013:44-48.

[11]Fang S H,Lin T N.Principal Component Localization in Indoor WLAN Environments[J].IEEE Transactions on Mobile Computing,2012,11(1):100-110.

[12]Fang S H,Wang C H.A Dynamic Hybrid Projection Approach for Improved Wi-Fi Location Fingerprinting[J].IEEE Transactions on Vehicular Technology,2011,60(3):1037-1044.

[13]Wagstaff K,Cardie C,Rogers S,et al.Constrained K-Means Clustering with Background Knowledge[C]//Proceedings of the Eighteenth International Conference on Machine Learning.Williamstown:IMLS,2001:577-584.

（編輯:王 瑞)

Fingerprint optimization method for the indoor localization system

MA Xindi,MA Jianfeng,GAO Sheng
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

The accuracy of the indoor localization is influenced directly by the quality of the fingerprint. But the indoor localization algorithms in existence are almost conducted based on the original fingerprint which is not optimized.The k-means is introduced to optimize the fingerprint in this paper.And deleting the collected bad-points through the theory of cluster could make the fingerprint more accurate for the indoor localization algorithm.Compared with the indoor localization systems in existence,the result of experiments shows that the optimized fingerprint can increase the accurate of indoor localization with a higher probability.

smartphone;k-means method;optimize fingerprint;delete bad-point

TP302.7

A

1001-2400（2015)06-0081-07

10.3969/j.issn.1001-2400.2015.06.015

2014-07-10

時間:2015-03-13

國家自然基金委員會-廣東聯(lián)合基金重點基金資助項目（U1135002);國家自然科學(xué)基金資助項目（61303221,61272398);中央高校基本科研業(yè)務(wù)費專項資金資助項目（JY10000903001)

馬鑫迪（1989-),男,西安電子科技大學(xué)博士研究生,E-mail:xdma1989@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20150313.1719.015.html