A Novel 3-D Clustering-Based Indoor Localization System

近幾十年來，室內定位技術發展得非常快速，許許多多的系統架構相繼被提出且實現，其中以使用Wi-Fi訊號強度作為辨識特徵最為常見，輕易使用行動裝置蒐集以及不用另外增加硬體是這項技術的最大特點。在眾多系統當中，準確率相當高的無線區域網路訊號紋系統是一個非常常見的架構，訊號紋系統在實行時大致可分為兩個階段：(1)離線階段，訊號紋資料庫蒐集及建立模組。(2)線上階段，接收訊號以及即時定位。 訊號紋資料庫的建立是藉由蒐集室內每個參考點的Wi-Fi訊號強度紀錄而成，若室內空間過大，則使用整個訊號紋資料庫會使即時定位的系統運算量非常大。一個減少運算量的好方法是將整個資料庫相似的參考點歸類為一群，則整個資料庫可分成較少的幾個群。傳統的分群方法包括k 平均值分群、支持向量機分群和近鄰傳播分群演算法。經過分群之後，同一個群中的參考點可能互相不相連且分散，利用權重定位演算法時，就可能將定位位置定在一些完全不可能出現的位置，例如百貨的中空區域或是樓與樓之間，我們將之稱為禁區問題。 在這篇研究的分群方法，除了傳統訊號強度的資訊之外，更加入地理上的資訊來增加分群結果在地理空間的群聚性，此種方法稱為加入地理資訊的間隔傳播分群演算法。使用支持向量機的間隔來作分群的一大優點是可以保留原始的訊號分佈。除此之外，在線上階段分群指配處理時，這篇論文也提出一個可適性的分群指配方式來產生群集合而不是只挑選機率最高的單一群。此種演算法增加了分群指配的準確率及定位精準度。 在這樣的室內定位系統中， 利用國立台灣大學博理館進行的室內定位系統可達到平均誤差1.15公尺的精準度。Indoor localization develops fast in recent years and many systems or architectures are proposed in this topic. Among these methods, receive signal strength of Wi-Fi is a common feature because of its easy collection and no need for additional hardware. Fingerprintbased system of WLAN is a common model for its high accuracy in indoor localization. The fingerprint methods can be classified into two stages in this approach:(1)the offline radio map construction and model training, and (2)the online measuring and location estimating. It collects features and records them from reference points of whole indoor environment to construct radio map. Due to the high computation complexity of location estimating with the whole radio map. The reference points are classified into some smaller clusters, which is called clustering. It is a good solution for reducing computation complexity of system. In traditional clustering methods, such as k-means, support vector clustering, or affinity propagation, reference points in the same cluster may be disjoint or far apart from each other. With weighted-sum-based methods of location estimation, the location may be located outside of the region of cluster, such as a hollow square or the area between different floors in a building. We call it Prohibition Area Problem. To solve the problem, unlike the traditional methods, we combine the information of signal domain and spatial domain to gain the compaction of clusters in spatial domain. A Margin Propagation with Spatial Clustering (MPSC) is proposed with this new perspective. Besides, one of advantages for clustering with margins of support vector machine is reserving the distribution of original signal. Moreover, in the online stage, the measurements are assigned to the corresponding cluster, which is called cluster matching. In traditional methods, a fixed number of clusters is chosen beforehand. However, the suitable number of clusters is not equal at different locations. The proposed method adaptively adds clusters with similar probabilities to form larger cluster set, which is called adaptive multi-cluster matching. It increases the accuracy of cluster matching and improves the localization performance. Finally, a kernel-based weighted sum of reference points in corresponding cluster set is used to give estimated location. This 3-D indoor localization system achieves 1.15m as average error in BL Building of National Taiwan University.List of Figures iii List of Tables v 1 Introduction 1 2 Related Works of Indoor Localization System 5 2.1 Propagation Model . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Fingerprint-based Approach . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 k Nearest Neighbor . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Probabilistic approach . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Compressive Sensing . . . . . . . . . . . . . . . . . . . . . 8 3 Proposed Indoor Localization System 9 3.1 Radio Map Construction . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 AP selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Pre-filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Dimension Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 Margin Propagation with Spatial Clustering . . . . . . . . . . . . 14 3.5.1 SVM Margin . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5.2 Similarity from Signal and Spatial Information . . . . . . . 17 3.5.3 Margin Propagation with Spatial Clustering . . . . . . . . 18 3.5.4 The clusters in radio map . . . . . . . . . . . . . . . . . . 21 3.6 Adaptive Multi-cluster Matching . . . . . . . . . . . . . . . . . . 22 3.7 Kernel-based Localization . . . . . . . . . . . . . . . . . . . . . . 26 4 Simulation Results 29 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Performance of AP selection . . . . . . . . . . . . . . . . . . . . . 30 4.3 Pre-filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 Comparison of Different Clustering Methods and Dimension Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 Improvement of Adaptive Multi-cluster Matching . . . . . . . . . 44 4.6 Comparison of Different Indoor Localization Systems . . . . . . . 46 5 Conclusions 49 Bibliography 5