臺灣博碩士論文加值系統

近年來隨著無線通訊的快速發展，室外及室內定位方法一直是熱門研究的議題。室外定位通常是以全球定位系統(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.

Contents
摘要 I
Abstract II
致謝 III
Contents IV
Chapter 1 Introduction 1
1.1 Research Background and Motivation 1
1.2 Research Objective 1
1.3 Research Approach and Case Study 1
1.4 Organization 2
Chapter 2 Related Works 3
2.1 Wireless Communication Technology 3
2.1.1 Bluetooth 3
2.1.2 RFID (Radio Frequency IDentification) 4
2.1.3 IEEE 802.11 4
2.2 Localization Techniques 5
2.2.1 Distance Measurement 5
2.2.2 Trilateration 9
2.2.3 Fingerprinting 9
2.3 K-Nearest Neighbor Algorithm 10
2.4 Genetic Algorithm 11
Chapter 3 A GA-and-KNN-based Fingerprinting Algorithm for Indoor Positioning 17
3.1 Problem Definition 18
3.2 The Proposed GA-and-KNN-based Fingerprinting Algorithm 22
3.2.1 Phase 1: Training Phase 23
3.2.2 Phase 2: Positioning Phase 25
3.3 Discussion 28
Chapter 4 Simulation and Results Analyses 30
4.1 Simulation Environment 30
4.1.1 Simulation Design 31
4.1.2 Simulation Cases 33
4.1.3 Performance Metrics 34
4.2 Simulations Results and Analyses 35
4.2.1 Case1 36
4.2.2 Case2 38
4.2.3 Case3 41
4.2.4 Case4 43
4.2.5 Case5 45
4.2.6 Summary 47
4.3 Discussion 50
Chapter 5 Conclusion and Future Works 51
5.1 Conclusion 51
5.2 Future Works 52
REFERENCES 53

1. K. Whitehouse, C.K., D.Culler, "A Practical Evaluation of Radio Signal Strength for Ranging-based Localization". ACM SIGMOBILE Mobile Computing and Communications Review, Vol.11, 2007: p. 41~46.
2. Timea Bagosi, Z.B., "Indoor Localization by WiFi". Intelligent Computer Communication and Processing (ICCP), 2011 IEEE International Conference on, 2011: p. 449~452.
3. Seco, F.P., C. ; Jimenez, A.R. ; Burgard, W. , "Improving RFID-based indoor positioning accuracy using Gaussian processes". Indoor Positioning and Indoor Navigation (IPIN), 2010 International Conference on 2010: p. 1~7.
4. Baniukevic, A.S., D. ; Jensen, Christian S. ; Hua Lu "Improving Wi-Fi Based Indoor Positioning Using Bluetooth Add-Ons". Mobile Data Management (MDM), 2011 12th IEEE International Conference on, Vol1 2011: p. 246~255.
5. Per Enge, P.M., "Special Issue on Global Positioning System". PROCEEDINGS OF THE IEEE, Vol 87, 1999: p. 3~172.
6. Liu, X.L.X.G.Y., "Fingerprint-based location positoning using improved KNN". Network Infrastructure and Digital Content (IC-NIDC), 2012 3rd IEEE International Conference on 2012: p. 57~61.
7. Wu, C.-C., "Enhancing Sensor-based Indoor Location by Genetic Algorithms". Department of Information Engineering I-Shou University, 2009: p. 31~38.
8. Home of http://en.wikipedia.org/wiki/Bluetooth.
9. Perez Iglesias, H.J.B., V. ; Escudero, C.J. , "Indoor person localization system through RSSI Bluetooth fingerprinting". Systems, Signals and Image Processing (IWSSIP), 2012 19th International Conference on 2012.
10. Home of http://spaces.isu.edu.tw/interface/showpage.php?dept_mno=rf9548&;dept_id=1&;page_id=947.
11. Chiou, Y.-S., "Adaptive Location Estimation Techniques for Indoor Wireless Local Area Networks". Institute of Communcations Engineering National Tsing Hua University 100.
12. M. Ciurana, F.B.-A., F. Izquierdo,, "A Ranging Method with IEEE 802.11 Data Frames for Indoor Localization". IEEE Wireless Communications and Networking Conference, 2007: p. 2092~2096.
13. A. El Moutia, K.M., "Time and Power Based Positioning Scheme for Indoor Location Aware Services". IEEE Consumer Communications and Networking Conference 2008: p. 868~872.
14. M. Garcia, C.M., J. Tomas, J.Lloret "Wireless Sensors Self-Location in an Indoor WLAN Environment". International Conference on Sensor Technologies and Applications, 2007: p. 146~151.
15. M. Emery, M.K.D., "IEEE 802.11 WLAN Based Real-Time Location Tracking in Indoor and Outdoor Environments". Canadian Conference on Electrical and Computer Engineering, 2007: p. 1062~1065.
16. Ting Wei, S.B., "Indoor localization method comparison: Fingerprinting and Trilateration algorithm". 2011: p. 1~3.
17. J.B. Andersen, T.S.R., S. Yoshida, "Propagation measurements and models for wireless communications channels". IEEE Communications Magazine 1995: p. 42~49.
18. Lin, T.-N.L.P.-C., "Performance comparison of indoor positioning techniques based on location fingerprinting in wireless networks". Wireless Networks, Communications and Mobile Computing, 2005 International Conference on, Vol2, 2005: p. 1569~1574.
19. Yang, C.-H., "Indoor Localization for Wireless Sensor Networks". Graduate Institute of communication Engineering College of Electrical Engineering and Computer Science National Taiwan University, 2007.
20. H.Lim, L.-C.K., Jennifer C. Hou, and H. Luo, "Zero-Configuration Robust Indoor Localization: Theory and Experimentation". 25th IEEE International Conference on Computer Communications, 2006: p. 1~12.
21. Binghao Li1, J.S., Andrew G. Dempster1, Chris Rizos, "Indoor Positioning Techniques Based on Wireless LAN". School of Surveying and Spatial Information Systems, 2007: p. 1~7.
22. Gui, W.N.G.S.X.L.L., "An Indoor Location Algorithm Based on Taylor Series Expansion and Maximum Likelihood Estimation". 2006: p. 1~4.
23. Shirahama, J.O., T. , "RSS-Based Localization in Environments with Different Path Loss Exponent for Each Link". 2008: p. 1509~1513.
24. Toh, W.X.W.N.Y.K., "Integrated Wi-Fi fingerprinting and inertial sensing for indoor positioning". Indoor Positioning and Indoor Navigation (IPIN), 2011 International Conference on 2011: p. 1~6.