文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.12.016
中文引用格式： 田廣東，楊品章，王珊，等. 基于Kmeans聚類的CSI室內定位[J].電子技術應用，2016，42(12)：62-64，68.
英文引用格式： Tian Guangdong，Yang Pinzhang，Wang Shan，et al. CSI indoor positioning based on Kmeans clustering[J].Application of Electronic Technique，2016，42(12)：62-64，68.
0 引言
隨著無線網絡技術的發展，基于位置的服務得到了相應的發展。基于無線局域網(Wireless Local Area Network，WLAN)的室內定位技術受到了廣泛關注，如今廣泛使用的基于接收信號強度指示(Received Signal Strength Indicator，RSSI)的定位方法精度不理想。在IEEE802.11n標準[1]中，支持信道狀態信息(Channel State Information，CSI)的反饋機制，通過修改無線網卡驅動[2]，可以獲取正交頻分復用(Orthogonal Frequency Division Multiplexing，OFDM)子載波中30個子載波的CSI。CSI描述了信號從發端到收端的衰減因子，包括散射、反射、路徑衰落等。通過對CSI的統計，其結果描述了空間相關性，可以作為基于指紋定位的指紋信息。
目前，基于CSI的室內定位研究已經取得了一定的成果[3]，達到了米級甚至亞米級的定位精度。文獻[4]利用CSI的頻率差異性，建立了CSI衰落與距離的模型，使用三邊測距定位，由于受帶寬的限制，多徑區分能力有限，測距精度不高，從而影響定位精度。文獻[5]利用CSI的頻率差異性，將30個信道CSI合成為5個子信道，并將多個天線的CSI求平均值處理，建立起一個基于概率模型的指紋定位模型。文獻[6]利用CSI信道間的關系提取指紋，建立了一個基于歐式距離作為相似度比較的指紋模型。
以上基于指紋的研究在提取指紋時都是將多個數據包的CSI做均值處理作為指紋。由于室內多徑效應，CSI存在成簇分布的狀況，采用取平均值的方法不能很好地反映位置的多徑傳播，從而影響了定位精度。本文通過采用Kmeans聚類算法，提取多條CSI向量作為指紋來描述位置特性。實驗證明，對比文獻[6]的CSI-MIMO算法，定位精度得到提高。
1 指紋定位系統模型
基于指紋的定位模型分為離線訓練階段和在線定位階段，模型如圖1所示。
離線訓練階段的任務是建立一個位置指紋數據庫。首先要選擇參考點的位置，然后在每個參考點處測量來自信標的信號特征，最后處理信號特征保存在數據庫中。這個數據庫也被稱為位置指紋地圖。
在線定位階段是指通過測量獲得未知位置的信號特征并加以處理，通過相應的匹配算法，比較測量數據與離線訓練建立的數據庫中的數據，找出相似的數據，作為位置的估計值。
2 基于Kmeans的聚類的CSI室內定位算法
2.1 離線訓練階段
在室內定位區域選定L個參考點，參考點位置已知，采用二維坐標(x，y)表示。在每個參考點接收n個CSI數據包。每個數據包有一個p×q×30的復數矩陣HMIMO，其中p為發射天線數，q為接收天線數。m=p×q為天線對個數。
無線信號在室內環境中存在著多徑傳播的情況，CSI幅值也受此影響，存在著成簇分布的情況，如圖2所示，簇內CSI幅值多徑傳播經相似。通過Kmeans算法處理相同天線對中n個數據包的CSI幅值。Kmeans算法能夠使聚類域中的所有CSI幅值向量到聚類中心距離的平方和最小。其原理為：
輸入：聚類個數k，包含n個數據對象的數據集。
輸出：k個聚類。
(1)從n個數據對象中任意選取k個對象作為初始的聚類中心。
(2)分別計算每個對象到各個聚類中心的距離，再把對象分配到距離最近的聚類中。
(3)所有對象分配完成后，重新計算k個聚類的中心。
(4)與前一次得到的k個聚類中心比較，如果聚類中心未發生變化，進行下一步，否則轉到步驟(2)。
(5)輸出聚類結果。
通過此算法，從n個數據包的值中得到k個具有代表性的CSI幅值向量作為位置指紋fin：
根據已有文獻的實驗觀測表明[7]，超過80%的CSI幅值向量只存在4個以內的分簇，但是由于實際的測量過程中存在干擾，分簇數目增加，所以本算法中設置分簇個數k=10。
對于單個天線對得到fin，對于m個天線的每個天線對使用Kmeans算法，得到訓練向量：
2.2 在線定位階段
在線定位階段采用與離線訓練階段相同的方法提取到m個天線對的指紋：
將提取到的指紋與訓練階段建立的數據庫中的指紋作比較，即將獲取到的第i個天線對的指紋矩陣與數據庫中的第i個天線對的指紋矩陣，進行兩個指紋矩陣中任意兩個CSI幅值向量i與j歐式距離的比較：
由于歐式距離反映了兩個向量之間的“不相關性”，即數值越大，相關性越低，數值越小，相關性越高。因此，關注這些距離中數值較小的作為測試點與訓練點之間相似度比較的一個依據。所以不再考慮天線對，將m個天線對的所有歐式距離從小到大排列，共有10×m個距離：
在得到測試點與所有訓練點之間的距離之后，使用K近鄰算法，從中選出距離較小的K個位置坐標平均作為位置估計坐標，本文中K=3。
3 實驗結果與分析
3.1 實驗設置
為評估算法的定位精度，在家庭客廳及其走廊的環境下測試。共選有22個參考節點，相鄰參考節點之間的距離為0.8 m，在參考節點之間有30個測試節點。實驗中使用FAST無線AP作為發射端，使用裝配有Intel WiFi Link 5300網卡的ThinkPad R400作為接收端。接收端使用CSITOOL軟件接收CSI。訓練階段，在訓練節點接收1 000個數據包的CSI。定位階段，在測試節點接收數據包100個。如圖3所示，測試環境建立的二維坐標系，其中“★”代表AP位置，“▲”代表參考點位置，“◆”代表測試點的位置。
將本算法與CSI-MIMO算法作比較，比較的性能由平均定位精度與累積誤差分布函數(Cumulative Distribution Function，CDF)圖來表示定位性能。
3.2 參數設置
采用不同的T值進行試驗評估，T值的選擇對于定位精度有一定的影響。試驗分別從T值為10、20、30、40、50、60進行測試，結果如圖4所示。當T值為10時，定位精度最高，平均定位精度為1.65 m。CSI-MIMO在同樣的測試環境下平均定位精度為2.18 m，提高了24%。
在T為10的情況下，對比本算法與CSI-MIMO的CDF，如圖5所示，50%的定位誤差都在1.34 m以內，優于CSI-MIMO算法。
3.3 定位時間
定位時間分為數據包接收時間和程序處理時間。CSITOOl軟件每秒大約能接收20個數據包，接收100個數據包需要5 s。執行定位程序的時間大約為0.5 s，所以完成一次定位的時間大約為5.5 s。
4 結論
本文提出了一種基于Kmeans聚類算法提取室內環境多徑傳播特征的指紋算法，利用CSI的頻率特性與MIMO的空間特性，所獲取的指紋較以往算法有更好的空間區分性。由于CSI的測量值存在誤差，使用聚類算法生成的多個特征向量能夠在一定程度上減小測量誤差所帶來的影響，從而提高了定位精度。下一步準備從匹配算法入手進行改進，進一步提高定位精度。
參考文獻
[1] IEEE Std 802.11n-2009.IEEE standard for information technology—Local and metropolitan area networks—Specific requirements—Part 11：Wireless LAN medium access control(MAC) and physical layer(PHY) specifications amendment 5：Enhancements for higher throughput[S].
[2] HALPERIN D，HU W，SHETH A，et al.Tool release：gathering 802.11n traces with channel state information[J].ACM Sigcomm Computer Communication Review，2011，41(1)：53-53.
[3] YANG Z，ZHOU Z，LIU Y.From RSSI to CSI: Indoor localization via channel response[J].ACM Computing Surveys，2013，46(2)：25.
[4] WU K，XIAO J，YI Y，et al.FILA：fine-grained indoor localization[J].Proceedings IEEE INFOCOM，2012，131(5)：2210-2218.
[5] XIAO J，WU K，YI Y，et al.FIFS：fine-grained indoor fingerprinting system[C].International Conference on Computer Communications and Networks，2012：1-7.
[6] CHAPRE Y，IGNJATOVIC A，SENEVIRATNE A，et al.CSI-MIMO：an efficient Wi-Fi fingerprinting using channel state information with MIMO[J].Pervasive & Mobile Computing，2015，23：89-103.
[7] SEN S，CHOUDHURY R R，RADUNOVIC B，et al.Precise indoor localization using PHY layer information[C].Proceedings of the 10th ACM Workshop on Hot Topics in Networks，ACM，2011：1-6.