臺灣博碩士論文加值系統

近年來，隨著手機使用習慣的改變，使得在大型商場、博物館或機場等場所對室內導航的需求量快速地提升。然而，綜觀國內發展中的室內導航系統，受限於資料庫與導航技術的不足，並未被廣泛地研究與討論。本論文基於前人的文獻，對室內導航技術分為兩大方向的研究與改良：第一部分，改良在已知文獻中，由於室內訊號源不足或是使用者身體移動而造成天線晃動，使得室內定位不精準的問題。第二部分，在路徑規劃時無法進行壅塞路徑迴避，而增加使用者在路徑上遭遇因壅塞所造成的等待時間。
為解決以上兩點問題，本論文提出了一個達成即時性的定位與最佳化路徑規劃的演算法，並將其實現於Android手機平台的室內導航系統。在即時性定位的部份，以傳統的fingerprinting定位方式為基礎，並利用手機上的加速規與陀螺儀等硬體裝置統計使用者因步行所造成身體晃動的頻率。將此統計結果轉化成使用者的總行走步數與行走距離，並將其用於補償原始fingerprinting定位演算法所計算的定位座標。此方式大幅地改善了因手機晃動而造成天線接收訊號不穩定的狀況，且有效地提高定位精準度。其次，本論文提出了於最短路徑中加入中繼點的壅塞資訊辨別方式，進而迴避路徑上出現的壅塞情況，讓使用者避免因等待壅塞點疏通而浪費時間，進而達成最佳化路徑規劃。
本論文乃以Android軟體平台為基礎，結合手機具備之加速規和陀螺儀等硬體裝置，完成一套具即時性定位與最佳化路徑規劃之導覽系統。經實地模擬與驗證後，本論文所完成之系統已確實達成設計目標。

In recent years, due to the rapidly changing use of mobile phones, indoor navigation for places such as large markets, museums and airports, etc. have become a global need. However, we have observed that in Taiwan the development of indoor navigation systems for the domestic market is limited in terms of database and navigation technology. Therefore, there is a paucity of research regarding the development and application of this technology. This thesis addresses two aspects crucial to the development and successful implementation of indoor navigation technology. First is inaccurate indoor positioning due to insufficient indoor signal strength or shaking of the antenna caused by user motion. Second is the known path planning methods, which cannot avoid the problem of path congestion, which increases the waiting time at congestion points in the planned walking path.
In this thesis, we propose an algorithm which can achieve real-time positioning and optimal path planning to solve the problems discussed above, and also implement it on an Android phone platform. For the real-time positioning scheme, a new method based on a conventional fingerprinting algorithm adopts the signal of the existing accelerometer and gyroscope on the smartphone to generate statistics for the body shaking frequency caused by the user's walking steps. Additionally, it transforms the frequency to the entire walking steps and distance, and compensates the original positioning coordinates, which are calculated by the conventional fingerprinting algorithm. The proposed method modifies the unstable received signals caused by shaking on the smartphone and effectively improves the positioning precision. Next, the thesis imports the congestion information of relay points to the shortest path planning model, and avoids these congestive situations on the path. Therefore, during incidences of congestion, this method saves the waiting time required for congestion points to be clear thereby achieving the optimal path planning goal.
The thesis utilizes the Android software platform, combining the accelerometer and gyroscope on the smartphone hardware platform to design and implement a navigation system that achieves real-time positioning and optimal path planning abilities. Verified by real-world simulation, the designed navigation system is complete and achieves its design goals.

摘要 I
Abstract III
誌謝 V
Contents VI
List of Figures IX
List of Tables XII
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation and Objectives 3
1.3 Thesis Organization 5
Chapter 2 Related Background 6
2.1 Wireless Sensor Network 6
2.1.1 Origin of WSN Technology 6
2.1.2 Architecture of Transmission Mechanism 9
2.2 Positioning Models 13
2.2.1 Angle of Arrival System (AOA model) 13
2.2.2 Time of Arrival System (TOA model) 15
2.2.3 Time Difference of Arrival System (TDOA model) 16
2.2.4 Received Signal Strength Indication System (RSSI model) 18
2.3 Indoor Positioning in RSSI Model 22
2.3.1 Triangulation of Single Signal Source 23
2.3.2 Fingerprinting of Single Signal Source 25
2.4 Path Planning Classification 26
Chapter 3 Architecture and Design 29
3.1 System Architecture 29
3.2 Software Architecture 32
3.2.1 User Interface of Android 32
3.2.2 Establish AP on Linux Platform 34
3.3 Dynamic Indoor Positioning 35
3.3.1 Establishing the Positioning Database 36
3.3.2 Noise Reduction 37
3.3.3 Database Matching 39
3.3.4 Second Noise Reduction - Quick Sort and Weight Method 41
3.3.5 Smoothing 44
3.4 Optimal Path Planning 50
3.4.1 Obtaining Server Information 51
3.4.2 Congestion Avoidance 53
3.4.3 Choosing the Shortest Path 58
3.5 Navigation Quality Analysis 61
3.5.1 Positioning Error Analysis 61
3.5.2 Path Planning Quality Analysis 62
Chapter 4 Experimental Results 64
4.1 Introduction of the Experimental Hardware 64
4.2 Introduction of Graphic User Interface (GUI) 65
4.2.1 Smartphone Interface 65
4.2.2 Computer Interface 68
4.3 Introduction of Testing Environment 70
4.4 Positioning Result and Analysis 73
4.4.1 Results of the Dynamic Trajectory 73
4.4.2 Error Figure between Two Positioning Algorithm 76
4.4.3 Analysis of Positioning Performance 78
4.5 Path Planning Result and Analysis 80
Chapter 5 Conclusions 83
References 85

[1]W.S. Sue, A Framework Using Fingerprinting for Signal Overlapping-Based Localization Method in WLAN, Department of Computer Science National Chiao Tung University, 2009
[2]C.W. Huang, Localization Algorithm in Wireless Sensor Network, Institute of Telecommunications and Management National Cheng Kung University, 2010
[3]T.K. Hsieh, CDMA Cellular Phone Location Positioning and its Implement, Department of Computer Science National Central University, 2006
[4]K.Z. Lin, Application of Wireless Sensor Network Modules in Indoor Geolocation, Department of Electrical Engineering National Cheng Kung University, 2007
[5]Y.W. Zhang, Positioning System Implementation by an Accelerometer, Department of Engineering Science National Cheng Kung University, 2012
[6]E.W. Dijkstra, “A note on two problems in connexion with graphs, Numerische Mathematik, 1(1) pp.269–271, 1959
[7]J. Xu, F. Hu and X. Han, “Realization of bidirectional a* algorithm based on the hierarchical thinking during the process of path planning, International Conference on Computer Science and Software Engineering, pp.415-418, 2008
[8]L. Lin, “Trends and shipment forecast for 2H 2012 smartphone market, DIGITIMES Research in Taipei, 2012
[9]I.F. Akyildiz and W. Su, “A Survey on Sensor Networks, Communications Magazine, 40(8) pp.104-112, 2002
[10]T.K. Shen, Development of a SOPC-Based Positioning System in Wireless Network Application, Department of Electrical Engineering National Cheng Kung University, 2005
[11]L. Jiang and S.Y. Tan, “Simple geometrical-based AOA model for mobile communication systems, Electronics Letters, 40(19) pp.1203-1205, 2004
[12]P. Bahl and V.N. Padmanabhan, “An In-Building RF-based User Location and Tracking System: RADAR, Microsoft Research, 2(2) pp.775-784, 2000
[13]R. Sedgewick, “Implementing Quicksort programs, Communications of the ACM, 21(10) pp.847-857, 1978
[14]N. Zhao, “Full-Featured Pedometer Design Realized with 3-Axis Digital Accelerometer, Analog Dialogue , 44(6) pp.1-5, 2010
[15]P. H. Veltink, E. G. O. Engberink, B. J. V. Hilten, R. Dunnewold and C. Jacobi, “Detection of static and dynamic activities using uniaxial accelerometers, IEEE Transactions on Rehabilitation Engineering, 4(4) pp.375-385, 1995
[16]C.J. Ding, Design and implementation of Real-Time Object Tracking System Using Gaussian Motion Model and Otsu Algorithm, Department of Engineering Science National Cheng Kung University, 2009
[17]陳湘揚，網路概論，博碩文化股份有限公司，台北:簡女娜，2011
[18]孫宏明，Android 4.X手機/平板電腦程式設計入門、應用到精通，碁峰資訊股份有限公司，台北:廖文良，2012
[19]鳥哥，鳥哥的Linux私房菜：伺服器架設篇，碁峰資訊股份有限公司，台北:廖文良，2011