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

馬鑫迪,馬建峰,高 勝

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

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

馬鑫迪,馬建峰,高 勝

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

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

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

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

目前,研究人員致力于部署更加靈敏且精確的室內(nèi)定位系統(tǒng)[1-3].與此同時(shí),用于定位過程中的定位感知技術(shù)也在不斷豐富,如藍(lán)牙技術(shù)、超聲波定位感知技術(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)信號(hào)且可在三維空間上實(shí)時(shí)定位的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]則通過從已測(cè)得的RSS信號(hào)值中提取特征性較強(qiáng)的信號(hào),從而降低室內(nèi)環(huán)境中無線網(wǎng)絡(luò)的多徑效應(yīng),使得定位精度提高約40%.

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

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

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

1 k-means聚類算法

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

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

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

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

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

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

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

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

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

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

2.2 定位算法

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

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

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

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

圖2 k-means算法流程圖

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

3 實(shí)驗(yàn)及評(píng)估

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果評(píng)估

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

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

圖4 定位結(jié)果

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

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

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

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

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

對(duì)圖6進(jìn)行分析,可以得出,在采集2號(hào)數(shù)據(jù)時(shí),信號(hào)干擾比較大,導(dǎo)致定位誤差比較大,但是也可以從統(tǒng)計(jì)的結(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號(hào)數(shù)據(jù)結(jié)果分析

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

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

4 結(jié)束語

文中引入k-means算法能較好的對(duì)指紋庫進(jìn)行優(yōu)化.實(shí)驗(yàn)數(shù)據(jù)分析表明,優(yōu)化指紋庫是有必要的.優(yōu)化后的指紋庫在干擾較小時(shí),能明顯提高定位誤差在1 m之內(nèi)的概率;在干擾較大時(shí),可以同樣使定位誤差在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

時(shí)間:2015-03-13

國(guó)家自然基金委員會(huì)-廣東聯(lián)合基金重點(diǎn)基金資助項(xiàng)目（U1135002);國(guó)家自然科學(xué)基金資助項(xiàng)目（61303221,61272398);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（JY10000903001)

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

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