楊明極，劉愷懌，邵丹

（哈爾濱理工大學(xué)測控技術(shù)與通信工程學(xué)院，黑龍江 哈爾濱 150080）

用于WLAN室內(nèi)定位的PCA聚類算法

楊明極，劉愷懌，邵丹

（哈爾濱理工大學(xué)測控技術(shù)與通信工程學(xué)院，黑龍江 哈爾濱 150080）

在WLAN室內(nèi)定位系統(tǒng)中，針對接收信號強度（RSS）的時變特征降低室內(nèi)定位精度的問題，提出一種基于主成分分析（PCA）白化RSS的聚類算法，該算法首先對信號強度進行PCA白化處理，去除RSS信息的相關(guān)性，提高聚類中心的可靠性和合理性，然后通過K-means聚類方式對RSS信息進行聚類，能夠有效地提高聚類精度，以此來提高定位精度。實驗結(jié)果表明，該算法相比于沒有經(jīng)過PCA的傳統(tǒng)聚類算法，能夠使定位誤差在2 m內(nèi)的概率提高44.8%，性能更優(yōu)良。

WLAN；室內(nèi)定位；去相關(guān)性；主成分分析；聚類算法

1 引言

在通信技術(shù)迅速發(fā)展的今天，人們對位置的需求越來越大，無線定位服務(wù)在很多方面都有廣泛的應(yīng)用前景[1]。目前應(yīng)用最為廣泛的定位方式是GPS定位和蜂窩網(wǎng)定位，通常能夠?qū)κ彝猸h(huán)境有效地定位，但是對于建筑嚴重遮蔽的室內(nèi)環(huán)境，這兩種定位方式都達不到理想的效果，因此對室內(nèi)定位的研究成為熱門方向[2]。

當(dāng)前主要研究的室內(nèi)定位技術(shù)有射頻識別技術(shù)、超寬帶技術(shù)、ZigBee技術(shù)、紅外線技術(shù)、超聲波技術(shù)和WLAN技術(shù)等。這些技術(shù)中，射頻識別技術(shù)對信噪比要求高，受限較嚴重；超寬帶技術(shù)雖然定位精度高，但伴隨的成本也較高，不宜普及；ZigBee技術(shù)成本較低，但是范圍小，難以推廣；紅外線技術(shù)定位精度高，但傳播距離短，易受熒光和房間燈干擾；超聲波技術(shù)需要專門硬件，成本高且受非視距和多徑傳播影響大[3]。與這些技術(shù)相比，基于WLAN室內(nèi)定位有覆蓋面積大、無需額外定位設(shè)備、部署方便等優(yōu)點，所以近些年對WLAN定位技術(shù)的研究越來越多[4]。

基于WLAN位置指紋的定位方法的核心是信號強度[5]。一般來說，系統(tǒng)的定位精度是隨著可利用的AP數(shù)量的增加而提高的，但并不是隨AP的增加而無限增加[6]。過多的AP數(shù)目，一方面導(dǎo)致RSS數(shù)據(jù)維數(shù)增加，影響解算速度，另一方面導(dǎo)致臨近AP的RSS相關(guān)性較大[7]。從位置指紋定位技術(shù)精度和效率的影響因素入手，提出一種將指紋數(shù)據(jù)庫中RSS先進行PCA去相關(guān)處理，然后采用K-means聚類算法將指紋數(shù)據(jù)庫分類的技術(shù)，從而使得聚類精確度更準確，較大地提高了定位效率和精度[8]。

2 PCA聚類算法

基于WLAN的室內(nèi)位置指紋定位是利用定位空間中多個AP的RSS數(shù)據(jù)來描述位置信息[9]，圖1為基于 PCA聚類算法的WLAN室內(nèi)定位系統(tǒng)架構(gòu)。

該方法包括兩個階段：離線階段和在線階段。在離線過程中，第一步確定各個指紋的物理位置，然后在每個指紋點的位置上采集RSS數(shù)據(jù)，將位置信息和RSS信號值結(jié)合起來，形成對應(yīng)的關(guān)系，該關(guān)系就是位置指紋，把位置指紋保存在數(shù)據(jù)庫中，建立位置指紋數(shù)據(jù)庫 （radio map，RM）[10,11]。將位置指紋數(shù)據(jù)庫中的RSS數(shù)據(jù)進行PCA去相關(guān)處理，然后進行K-means聚類。在線階段，對定位終端接收到的RSS信息進行PCA去相關(guān)處理，通過最近鄰（nearest neighbor，NN）法得到待測點所在的聚類類別，在該類別中用KNN算法匹配出測試點的估計位置。

2.1 PCA變換

由于當(dāng)前大部分室內(nèi)AP部署密集，很有可能導(dǎo)致相同指紋位置鄰近AP的RSS信息相關(guān)性較大，導(dǎo)致聚類過程中出現(xiàn)很多相關(guān)性高的聚類中心。因此，在聚類之前，對RSS做去相關(guān)處理、提高聚類中心的可靠性是很有必要的。

PCA算法的基本原理是：根據(jù)霍特林變換在另一空間中確定一組正交向量，該正交向量可以最大限度地表現(xiàn)原始數(shù)據(jù)，從原來的p維空間將原始信息映射到該組正交向量形成的n（n＜p）維空間上，從而完成對數(shù)據(jù)的去相關(guān)和維數(shù)的壓縮。

圖1 基于PCA聚類算法的WLAN室內(nèi)定位系統(tǒng)架構(gòu)

通過PCA處理后，基本消除了Z中各數(shù)據(jù)間的相關(guān)性，保留Z中包含X的大部分信息的前n個主成分，Z′=[S1′,S2′,…,St′]T，其中，St′=(st1,st2,…,stn)，因為 n＜p，因此同時完成了對數(shù)據(jù)的壓縮。

2.2 聚類算法

RM中的每個位置指紋均值通過PCA白化處理后，新樣 本 集 為

白化的K-means算法的工作流程說明如下。

步驟1 整個RM中選取k個指紋作為初始聚類中心（R1,R2,…,Rk），Rk=[rk1,rk2,…,rkn]。由于初始聚類中心的隨機選擇可能導(dǎo)致聚類過于集中或過于分散，因此在選擇k個聚類中心時要盡量地在定位范圍內(nèi)均勻選擇。

步驟2 對于除k個聚類中心之外的其他所有經(jīng)過PCA白化處理的RSS均值，它們與每個聚類中心的歐式距離di為：

將它們分別分配給與其歐式距離最近的聚類。

步驟3 將所有的指紋都分配完成后，獲得新的聚類，因為K-means聚類算法可能會出現(xiàn)空的聚類，為避免這種情況，在每次迭代過程中，將每次聚類中的全部RSS取平均值，當(dāng)作新的聚類中心，該方法被稱為聚類中心的抑制更新方法。

步驟4 不斷重復(fù)步驟2和步驟3，直到k個聚類中心固定不變，終止迭代。

聚類過程結(jié)束，每個位置指紋都被劃分至與之最近的聚類中心，每個聚類都被當(dāng)做一個子區(qū)域。

2.3 匹配算法

離線定位階段，每個聚類中心和相對應(yīng)的位置指紋數(shù)據(jù)形成一個個獨立的子位置指紋數(shù)據(jù)庫。在線定位階段，將測試點處獲得的RSS{xi1,xi2,…,xin}做PCA去相關(guān)處理，然后與各個聚類中心進行比較分析，利用最近鄰法獲取待測點所在的聚類類別。

將d1,d2,…,dk從小到大進行排序，選出最近的聚類中心所在的類族作為參考點的類族。選取的類族記為{C1,C2,…,Cm}，m表示該類中帶權(quán)值的位置指紋參考點的個數(shù)。

在所確定的類別中，各參考點與測試點進行算法匹配，進而利用KNN算法實現(xiàn)對待測點的位置估計。

步驟1 應(yīng)用歐幾里德距離計算測試點與聚類指紋數(shù)據(jù)集中的每個參考點{C1,C2,…,Cm}之間的距離。其中，

步驟2 對步驟1得到的{d1,d2,…,dm}由小到大進行排序，選取前k個參考點。

步驟3 對步驟2得到的k個指紋參考點的位置坐標求平均值，把得到的值作為待測點的估算位置坐標。

改進后的算法在定位階段只需跟位置指紋庫中的某個子集進行計算比較，使得KNN算法的匹配效率得到極大的提高，更能滿足客戶實時性的要求。

3 實驗測試

3.1 實驗環(huán)境建立

為了驗證PCA聚類算法的有效性，在哈爾濱理工大學(xué)8公寓3樓進行實驗，3樓局部平面示意如圖2所示。實驗采用13個CMCC信號發(fā)射器作為AP，使用聯(lián)想Z460的筆記本電腦采集各AP的RSS信號值，信號采集軟件為inSSIDer。實驗選取了253個指紋點和 50個測試點，相鄰指紋點間距為1 m，50個測試點的位置是隨機選擇的，每個位置能接收到來自5～7個AP的 RSS，采集30次為一組，采集2組，采集的時間間隔為2 s。定義定位誤差為：

其中，(xi,yi)表示第 i個測試點的實際物理坐標，(xi′,yi′)表示第i個測試點的估算物理坐標。

3.2 結(jié)果分析

在室內(nèi)傳播過程中RSS不可避免地受遮擋、多徑效應(yīng)等影響，在同一位置上接收到AP的RSS會隨時間變化存在程度不一的波動，導(dǎo)致距離較近的指紋點之間的RSS信號均值相近[15]。此時通過PCA白化處理數(shù)據(jù)，不僅可以解決以上問題，還將數(shù)據(jù)維度進行了壓縮，增加K-means聚類算法的可靠性，同時為后面的聚類和匹配算法降低了復(fù)雜程度。在實驗過程中，原始RSS數(shù)據(jù)的維數(shù)為6，經(jīng)過PCA白化處理后，RSS值保留90%的主要信息，維數(shù)降為 4（n=4）。

圖2 WLAN室內(nèi)定位環(huán)境

首先，為了證明對RSS進行PCA白化處理有利于聚類的準確性，比較了有無經(jīng)過PCA處理的K-means聚類的分塊精準度，如圖3所示。

圖3 K-means聚類算法經(jīng)PCA前后聚類精度比較

圖3為聚類中心由1到8時，經(jīng)過PCA處理和沒有PCA處理的聚類分塊精度對比。首先，信號經(jīng)過PCA處理后的K-means算法在聚類精度上要高于沒有經(jīng)過PCA處理的信號的聚類精度。特別是當(dāng)k值慢慢增大，提高得就更加明顯，因為在定位范圍一定時，聚類中心k值越大，則定位子區(qū)域越多，因此相鄰的子區(qū)域之間RSS強度相關(guān)性越大，通過PCA變換，消除信號之間的相關(guān)性，可以較大地提升聚類精度。其次，從圖3可以看出，k的取值越小，聚類的準確率越高，但是k取值過小，類內(nèi)的信息相似程度低，不利于提高室內(nèi)定位精度和降低計算復(fù)雜度。當(dāng)k=4時，聚類的準確率達到96.9%。隨著k值增大，所有PCA前后的K-means聚類算法的聚類精度都在快速下降，因為k的取值在大于5以后，k值越大，分塊越多，每個類的定位子區(qū)域越小，各個類之間的相似度越大，不但會降低聚類準確率，還會降低室內(nèi)定位精度。

如圖4所示是當(dāng)聚類中心k的取值由1取到8時對應(yīng)的定位精度概率累積分布。

圖4 k取不同值時系統(tǒng)定位精度概率累積分布

由圖4可以發(fā)現(xiàn)，聚類算法可以提高定位精度，當(dāng)聚類中心 k的取值為 2、3、4、5時都高于 k=1（無聚類）時的定位精度。但是聚類中心取值大于6時，低于無聚類時的定位精度概率，聚類算法的優(yōu)勢漸漸消失。其中，聚類中心k=4時，整體的定位精度高于k取其他值，雖然k=4時，定位精度小于 3 m概率不如k=5時高，但是并不影響k=4時系統(tǒng)定位的整體優(yōu)勢。實際上，k=5時累計概率最高為80.1%，k=4時累計概率為77.2%，雖然此處k=5時的概率略高于k=4時，但是由圖3可知，k=5時的聚類精度概率為93.8%，明顯比k=4時的聚類精度概率97.1%要低，并且k=5時在定位精度小于2 m和小于4 m處的累積概率并不高，整體考慮定位精度和聚類精度兩個因素，當(dāng)聚類中心值k=4時定位系統(tǒng)的可靠性和有效性最高。

以上分析說明，聚類中心k的取值嚴重影響系統(tǒng)的定位性能，因此為了既能提高定位精度，縮小搜索的定位范圍，又能保證聚類精度和聚類有效性，將聚類中心取為4。當(dāng)k=4時，比較了K-means聚類算法在RSS進行PCA處理前后的定位精度，如圖5所示。

圖5 最優(yōu)聚類下信號PCA處理對定位精度的影響

從圖5可以看出，經(jīng)過PCA處理后的系統(tǒng)在2 m內(nèi)的定位精度概率達到60.1%，比沒有經(jīng)過PCA的系統(tǒng)定位精度概率提高了44.8%；經(jīng)過PCA處理處理后的聚類定位精度在3 m內(nèi)的概率為77.3%，比沒有經(jīng)過PCA處理的定位精度概率高11.2%；在定位精度為1 m時定位精度概率也有所提高。所以，信號經(jīng)過PCA白化處理后再進行聚類，能夠明顯提高定位精度。

為了更清晰地說明PCA的作用，圖6對PCA處理前后系統(tǒng)定位誤差的最大值、最小值、平均值和定位誤差的標準方差做了對比。

由圖6可發(fā)現(xiàn)，最大定位誤差由未經(jīng)過PCA的7.92 m下降到6.28 m，降了26.1%；而信號經(jīng)過PCA處理后系統(tǒng)的平均定位誤差為2.22 m，未經(jīng)過PCA處理的平均誤差為2.75 m，定位誤差下降了23.9%，此外，PCA處理前的誤差范圍為0.92～7.92 m，經(jīng)過PCA處理的聚類定位誤差范圍為0.62～6.26 m，由于定位誤差范圍越小，則誤差與均值的偏離度越小，定位誤差的標準方差由未經(jīng)過PCA處理的1.86 m降至1.36 m，表明PCA算法可以降低偏離平均定位誤差的程度。

圖6 最優(yōu)聚類下信號是否PCA的定位誤差比較

4 結(jié)束語

通過對實驗結(jié)果的分析可以看出，PCA能夠有效地對接收信號強度去除相關(guān)性和進行維數(shù)壓縮；經(jīng)過PCA的K-means聚類算法比沒有經(jīng)過PCA的聚類算法聚類精度更高，并且當(dāng)聚類中心k=4時既能保證定位精度，又能保證可靠性最高。在最優(yōu)聚類情況下進行PCA處理能有效地提高定位精度，給用戶帶來更好的定位結(jié)果。

[1]FANG S H,LIN T N.A dynamic system approach for radio location fingerprinting in wireless local area networks[J].IEEE Transactions on Communications,2010,58(4):1020-1025.

[2]BORENOVIC M,NESKOVIC A,BUDIMIR D.Space partitioning strategies for indoor WLAN positioning with cascade-connected ANN structures[J].International Journal of Neural Systems,2011,21(1):1-15.

[3]GU Y,LO A,NIEMEGEERS I.A survey of indoor positioning systems for wireless personal networks[J].IEEE Communications Surveys and Tutorials,2009,11(1):13-32.

[4]SUN Y,LA PORTA T F,KERMANIP.A flexible privacy-enhanced location-based services system framework and practice[J].IEEE Transactions on Mobile Computing,2009,8(3):304-321.

[5]CHON M,CHA H.Life map:a smartphone-based context provider for location-based services [J].IEEE Pervasive Computing,2011,10(2):58-67.

[6]TAGASHIRA S,KANEKIYO Y,ARAKAWA Y,etal.Collaborative filtering for position estimation error correction in WLAN positioning systems [J]. IEICE Transactions on Communications,2011,94(3):649-657.

[7]SERTTHIN C,FUJIIT,OHTSUKIT,etal.Multi-band received signal strength fingerprinting based indoor location system[J].IEICE Transactions on Communications,2010,93(8):1993-2003.

[8]KUSHKI A,PLATANIOTIS K N,VENETSANOPOULOS A N.Intelligent dynamic radio tracking in indoor wireless local area networks[J].IEEE Transactions on Mobile Computing,2010,9(3):405-419.

[9]YOO J W,PARK K H.A cooperative clustering protocol for energy saving of mobile devices with WLAN and bluetooth interfaces[J].IEEE Transactions on Mobile Computing,2011,10(4):491-504.

[10]CHAVALIT K,KOMWUT W,KAMOL K.Indoor localization improvement via adaptive RSS fingerprinting database[C]//International Conference on Information Networking,Jan 28-30,2013,Bangkok,Thailand.New Jersey:IEEE Press,2013:412-416.

[11]WANG T.Novel sensor location scheme using time-of-arrival estimates[J].IET Signal Processing,2012,6(1):8-13.

PCA clustering algorithm for indoor positioning in WLAN

YANG Mingji,LIU Kaiyi,SHAO Dan
School of Measure-Control Technology and Communication Engineering,Harbin University of Science and Technology,Harbin 150080,China

In WLAN indoor location system,aiming at the problem of time-varying characteristic of

signal strength (RSS)which reduces indoor positioning accuracy,a clustering algorithm based on principal component analysis (PCA)albino RSS was put forward.The algorithm firstly treated the RSS with PCA whitening treatment to remove the correlation and improve reliability and rationality of the cluster centers.Then,K-means clustering method was used to cluster the RSS and the clustering accuracy was improved effectively,so as to improve positioning accuracy.Experimental results show that compared with the traditional clustering algorithm without PCA,probability of positioning error within 2 meters has improved 44.8%in positioning accuracy,and the performance of positioning system has been more excellent.

WLAN,indoor positioning,remove the correlation,PCA,clustering algorithm

TN929.5

A

10.11959/j.issn.1000-0801.2016186

2016-05-12；

2016-07-05

楊 明 極(1971-)， 男 ， 博 士 ， 哈 爾 濱 理 工 大 學(xué)教授，主要研究方向為計算機網(wǎng)絡(luò)和嵌入式系統(tǒng)。

劉愷懌（1992-），女，哈爾濱理工大學(xué)碩士生，主要研究方向為無線通信技術(shù)。

邵丹（1988-），女，哈爾濱理工大學(xué)碩士生，主要研究方向為無線通信技術(shù)。