一個基於GA與KNN指紋辨識演算法的室內定位

Abstract

近年來隨著無線通訊的快速發展，室外及室內定位方法一直是熱門研究的議題。室外定位通常是以全球定位系統(GPS, Global Positioning System)以及蜂巢式網路系統(Cellular Network System)為基礎的定位系統，然而將其應用在室內定位時，環境上的限制會造成定位的誤差範圍較大。因此許多通訊技術被提出作為室內定位的方法，其中以IEEE 802.11無線區域網路技術最為普及。因此本論文用無線區域網路技術為基礎，提出以指紋辨識定位方法結合最鄰近節點演算法(KNN, K-Nearest Neighbor Algorithm)以及基因演算法(GA, Genetic Algorithm)，作為室內定位的方法。在實驗案例研究中，我們將提出的室內定位方法所產生的結果，分別與單純使用最鄰近節點演算法及基因演算法定位所產生的結果比較，數據顯示本論文提出的方法有效降低定位結果的誤差：平均誤差改善約32%；最大誤差改善約33%，此外也避免定位結果超出測試的區域。實驗也同時顯示出提出的方法能夠減少參考點的收集，從而減少室內定位的資料蒐集量。

With the rapidly development of wireless communication, the method of outdoor and indoor positioning are always popular research issues. Outdoor positioning is based on GPS (Global Positioning System) and cellular network system. However, it will cause high distance error rate when using them for indoor positioning. Therefore, the other researches propose another communication technology as indoor positioning method. Because of popularization of IEEE 802.11, we choose it as wireless communication technology to propose a method which uses fingerprinting combined with KNN (K-Nearest Neighbor Algorithm) and GA (Genetic Algorithm) as positioning method. In the simulation cases, we compare the result produced by our method with the result produced by pure KNN and pure GA. The result shows our method effectively lower the distance error. It improves average distance error about 32% and max distance error about 33%. In addition, the positioning result will not exceed the boundary of the test area. The study shows the proposed algorithm decrease the quantity of reference points and it reduces the collection of data.