適用於KNN定位系統之相對定位誤差估測方法

Relative Location Error Prediction for KNN-based Fingerprinting Localization System

蔡文誠(Wen-Cheng Tsai)

指導教授 ： 黃寶儀

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.02173

摘要

使用RSSI(Received Signal Strength Indicator)當作環境特徵的室內定位系統，因多重路徑傳遞(multipath)、環境或是其他原因的影響，使得在同一個地點量測的訊號都不一定相同，當兩個位置環境特徵相似度很高時，誤判就容易發生，隨著誤判的距離越遠定位誤差就越高，為了降低事前量測資料(survey data)對定位誤差帶來的影響，重新檢視事前量測資料並對有問題的地方做適當的處理是必須的。
為了幫助檢視事前量測資料找出易產生高定位誤差的位置環境特徵(location fingerprint)，本篇論文裡提出一個相對定位誤差估計方法，參考誤判的機率與距離來估計一個使用KNN定位方式的定位系統，在不同位置會產生定位誤差的關係為何。在我們真實佈建的室內定位系統中的自我測試(self-test)條件下，其估計結果與實際誤差的相關係數可達0.6~0.8，然而在較符合實際使用的交互驗證(cross-test)相關係數僅有0~0.2，原因是不同時間量測的位置環境特徵不同所致，在分析連續30天的量測訊號樣本後，隨著製作位置環境特徵的訊號樣本數量增加可以降低位置環境特徵訊號間的差異，但是需量測的訊號樣本數量會因不同環境而有所增減。為了從相對定位誤差找出有問題的位置環境特徵並加以改善，我們使用凝聚階層式集群分析的分群方法(agglomerative hierarchical clustering)挑出會產生較大定位誤差的位置環境特徵，從實驗的結果來看，若直接移除這些位置環境特徵對改善定位誤差是沒有幫助的，進一步的分析後發現，要改善定位誤差不能只將有問題的位置環境特徵移除，而是要考慮這些距離遠並容易產生誤判的位置環境特徵發生的原因為何。

關鍵字

室內定位 ； 位置環境特徵 ； 定位誤差估計

並列摘要

For a RSSI fingerprinting localization system, due to the multipath transmission, environment or other impacts, measured signals are different each time at the same place. When two location fingerprints are similar in signal, selecting wrong location fingerprints happened easily. The longer distances with the wrong selected location fingerprints the higher location errors. To reduce the impact of location error coming from survey data, reexamining survey data and properly dealing with the problem parts are needed.
In order to examine survey data for finding location fingerprints which may cause high location error, we propose a relative error prediction method in this thesis. It considers probability of selecting wrong fingerprints and error distance to finds a correlation of location error between grids based on KNN localization system. In our deployed indoor localization system, the correlation coefficients of estimations and location error can achieve 0.6 to 0.8 for self-test data. However, the correlation coefficients are only 0 to 0.2 in cross-test data. The reason is the measured location fingerprints are not identical in the same location at different time. After we analyze a 30-day RSSI measurement, using more samples to make location fingerprints can decrease the difference of two location fingerprints in the same location at different time. Furthermore, the result shows that the number of samples needed to from the location fingerprints depends on different environments. For picking problematic location fingerprints from relative error and deal with them, we use a cluster method which is called agglomerative hierarchical clustering to pick the outliers of relative error. In our experiment result, location error is not improved by removing the selected location fingerprints. In detail analysis, to improve location error can not only remove the problematic location fingerprints, but also need to figure out why there are some distant location fingerprints with high similarity in signal.

並列關鍵字

Indoor Localization ； Location Fingerprint ； KNN ； Error Estimation

參考文獻

for Wireless Sensor Network Localization”, Workshop on Intelligent Solutions in

[2] N. B. Priyantha, A. Chakraborty, H. Balakrishnan, “The Cricket Location-support

[3] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) using AOA.”, in

Proceedings of IEEE International Conference on Computer Communication

(INFOCOM), pp. 1734-1743, March, 2003.