臺灣博碩士論文加值系統

隨著科技的進步，行動裝置與地理資訊的結合發展出適地性服務 (Location-Based Service, LBS)，適地性服務最常用的功能為定位系統，定位的精準度也影響著適地性服務的應用層面，定位精準度越高應用層面將越廣。室外定位最常見的為全球定位系統 (Global Positioning System, GPS)，而室內定位則藉由區分不同的 Wi-Fi 訊號來源與接收強度，做出定位，由於在熱鬧的都會區街頭往往會因為過多的高樓建築物與人潮流動的動態環境，使衛星訊號與訊號強度受到多路徑效應，導致定位誤差達數十公尺至數百公尺，甚至無法定位。本論文欲使用 Wi-Fi 訊號強度定位與 GPS 結合運作提升室外定位精準度，Wi-Fi 定位採用訊號紋辨識法，結合 GPS 所收集到的經緯度，在線下階段建立 Wi-Fi 訊號資料庫，在線上階段利用常見的利用無線網路接受場強之距離估計模型(對數距離路徑損耗模型與陰影模型)接下來利用各種適用於定位系統的機器學習技術（ K 個最近鄰居演算法、K 分群演算法與 K 個最近鄰居演算法結合 K 分群演算法）進行定位與比較。
硬體設備採用 STMicroelectronics 公司的 STM32F407ZET6 嵌入式開發板，結合 UBlox NEO-6M GPS 模組與 ESP8266 Wi-Fi 模組根據此設計進行研究。

With the advancement of technology, the combination of mobile devices and geographic information has developed a Location-Based Service (LBS). The most basic function of LBS is positioning. The accuracy of positioning also affects the application level of LBS. The higher the positioning accuracy, the wider the application level. The most common outdoor positioning is the Global Positioning System (GPS), and the indoor positioning is to make a positioning by receiving different Wi-Fi signal sources and receiving strengths, because the streets in the bustling metropolitan area tend to be too much. The dynamic environment of high-rise buildings and crowds of people makes the satellite signal and Wi-Fi signal strength subject to multipath effects, resulting in positioning errors ranging from tens of meters to hundreds of meters, and even unable to locate. This thesis wants to use Wi-Fi signal strength positioning and GPS cooperative operation to improve the overall accuracy. Wi-Fi positioning uses the signal pattern identification method, combined with the latitude and longitude collected by GPS, to establish a Wi-Fi signal database online, using various applications. The positioning and comparison of the machine learning techniques ( K Nearest Neighbor Algorithm, K – Means Clustering Algorithm and K Nearest Neighbor Algorithm combined with K – Means Clustering Algorithm) of the positioning system are performed.
The hardware equipment uses STMicroelectronics STM32F407ZET6 embedded development board, combined with UBlox NEO-6M GPS module and ESP8266 Wi-Fi module to study according to this design.

摘要 i
ABSTRACT iii
誌謝 v
目錄 vi
表目錄 ix
圖目錄 xi
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究方法 2
1.3 論文架構 2
第二章　開發環境與各部硬體介紹 3
2.1 STM32ZET6 微控制器介紹 3
2.2 通訊介面 7
2.2.1 串列通訊與並列通訊 8
2.2.2 單工、半雙工與雙工 9
2.3 常見的串列通訊方式 10
2.4 常見的串列通訊接口 11
2.4.1 UART 11
2.4.2 I2C 13
2.4.3 SPI 15
2.5 使用模組介紹 19
2.5.1 NEO-6M u-blox 6 GPS 模組介紹 19
2.5.2 ESP8266 802.11b/g/n 模組介紹 20
2.6 STM32開發工具與技巧 22
第三章 室外定位原理與多重路徑效應 24
3.1 GPS 定位原理 24
3.2 GPS 定位誤差的產生 26
3.3 Wi-Fi 定位原理 29
3.3.1 三邊定位法 29
3.3.2 訊號紋定位法 30
3.4 Wi-Fi 定位誤差的產生 32
3.5 Wi-Fi 與 GPS 室外定位之相關研究 34
第四章 機器學習與定位方法之研究 36
4.1 機器學習與位置估計研究 36
4.1.1 監督式學習法與非監督式學習法 36
4.1.2 K個最近鄰居(K-Nearest Neighbor, KNN)演算法 38
4.1.3 K分群(K-means clustering)演算法 40
4.2 距離估計研究 43
4.2.1 對數距離路徑損耗模型(Log-Distance Path Loss Model) 46
4.2.2 陰影模型(Shadowing Model) 47
第五章 實驗成果與分析 49
5.1 機器學習系統開發環境 49
5.2 研究目標整體流程圖 51
5.3 環境定義 52
5.3.1 選定環境 52
5.3.2 使用模組架設訓練點 54
5.4 距離估計模型選定 75
5.5 位置估計演算法比較 94
5.5.1 Haversine 算法 94
5.5.2 加權值心定位法 (Weighted centroid location Algorithm) 96
5.5.3 K個最近鄰居(K-Nearest Neighbor, KNN)演算法 99
5.5.4 K分群(K-means clustering)演算法 104
5.5.5 K個最近鄰居(K-Nearest Neighbor, KNN)演算法+ K分群(K-means clustering)演算法 108
5.5.6 三者演算法比較 112
5.6 網路呈現 113
第六章 結論與未來展望 115
6.1 結論 109
6.2 未來展望 110
參考文獻 117
附錄
A 系統開發相關程式碼 120
A.1 STM32F407 利用 Wi-Fi 模組進行擷取 RSSI 數值程式碼 121
A.2 Arduino 利用GPS模組擷取經緯度程式碼 127
A.3 Jupyter Notebook–Python 呈現 KNN 演算法程式碼 128
A.4 Jupyter Notebook–Python 呈現 K-means 演算法程式碼 131
A.5 Jupyter Notebook–Python呈現 KNN 結合 K-means 演算法程式碼 134
B 電信研討會全文
B.1 運用無線網路接收場強進行距離之估計 138
　　 B.2 運用無線網路接收場強與機器學習演算優化 GPS 定位系統精度 144
C 研究心得 148

[1]“Google Street View logs WiFi networks, Mac addresses, Apr 2010.
[2]H. Fu, G. Xiong, S. Chen, M. Qiu, H. Xiong, Z. Shen, X. Dong, X. Su, and X. Guo,
“Design of Low-cost Position Differential Positioning System Based on STM32,”
IEEE Chinese Automation Congress (CAC), no. 6, , Jan. 2019.
[3]STMicroelectronics Inc., https://www.st.com/content/st_com/en.html.
[4]ARM., “Optimizing ARM Cortex a and Cortex-M Based Heterogeneous
Multiprocessor systemsforRich Embedded Aapplications,”
https://www.slideshare.net/ARMHoldings/optimizing-arm-cortex-a-and-
cortexm-based-heterogeneous-multiprocessor-systems-for-rich-embedded-
applications-kdave.
[5]STM32/407, “Getting Started with STM3xx MCU,” STMicroelectronics
Inc,” http://www.st.com/stonline/.
[6]STMicroelectronicsInc., “STM340x, STM340x Datasheet,”
https://www.st.com/resource/en/datasheet/dm00037051.pdf.
[7]STMicroelectronicsInc.,“STM37OnlineTraining,”
https://www.st.com/content/st_com/en/support/learning/stm32-education/stm32-online-training/stm37-online-training.html.
[8]“Simplex vs. Duplex Fibre Optic Cable: What’s the Difference?,”
https://www.black-box.de/en-de/page/25078/Resources/Technical-Resources/Black-Box-Explains/Fibre-Optic-Cable/simplex-vs-duplex-fiber-patch-cable.
[9]STMicroelectronics Inc.,“RM0090 Reference manual,” https://www.st.com/content/ccc/resource/technical/document/reference_manual////66/b4/99/40/d4/DM00031020.pdf/files/DM00031020.pdf/jcr:content/translations/en.
DM00031020.pdf.
[10]“UART vs SPI vs I | Difference between UART, SPI and I,”
https://www.rfwireless-world.com/Terminology/UART-vs-SPI-vs-I.html.
[11]ublox Inc., “NEO- u-blox 6 GPS Modules Data Sheet,”
https://www.u-blox.com/sites/default/files/products/documents/NEO-
6_DataSheet_%2PS.G6-HW-09005%29.pdf.
[12]Espressif System Inc., “ESP8266 802.1gn datasheet,”
https://www.electroschematics.com/wp-content/uploads/2015/02/esp8266-
datasheet.pdf.
[13]STMicroelectronics Inc., “ST-LINK/V2 Datasheet,”
https://www.st.com/resource/en/data_brief/st-link-slsh-v2.pdf.
[14]Seeber, G., Satellite Geodesy, d Edition, Walter de Gruyter, New York, 2003.
[15]Hofmann-Wellenhof, B., Lichtenegger, H., and Collins, J., 2001, Global Positioning System: Theory and Practice, Springer-Verlag, New York.
[16]T. Kos , I. Markezic and J. Pokrajcic , “Effects of Multipath Reception
on GPS Positioning Performance” Proceedings ELMAR-2010
[17]https://zh.wikipedia.org/zhtw/%E5%85%A8%E7%90%83%E5%
AE%%E4%BD%%E7%B3%BB%E7%BB%.
[18]H. Miao, Z. Wang* , J. Wang, L. Zhang, Z. Liu, “A Novel Access Point Selection Strategy for Indoor Location with Wi-Fi,” in Proc. The 2h Chinese Control and Decision Conference (2014 CCDC), Changsha, China, 2014.
[19]P. Bahl and V. N. Padmanabhan, “RADAR: an in-building RF-Based User Location and Tracking System,” in Proc. Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), Tel Aviv, Israel, Israel, 26-30 March 2000.
[20]M. Chen, A. Xia, and Y. Zeng, “Analysis of Multipath Effects on Accuracy of Range
Estimation Using Received Signal Strength Indicator,” in Proc. 2014 Fourth
International Conference on Communication Systems and Network Technologies
[21]Zhang, J., Li B., Dempster A.G., and Rizos C., (2011, March). “ Evaluation of High
Sensitivity GPS Receivers,” Magazine of Coordunates 7(3).Retrieved May 16,
2011 from Coordunates on the World Wide Web: http://mycoordinates.org/.
[22]J. Xiong, Q. Qin, and K. Zeng, “A Distance Measurement Wireless
Localization Correction Algorithm Based on RSSI,” in Proc. 2014 Seventh International Symposium on Computational Intelligence and Design, Hangzhou,
China, 13-14 Dec. 2014.
[23]William H. Tranter K, Sam Shanmugan, Theodore S Rappaport, and Kurt L. Kosbar, Principles of Communication Systems Simulation with Wireless Applications, PRENTICE HALL Professional Technical Reference.
[24]Drew Conway, “Machine Learning for Hackers”.
[25]L. Xuanmin, Q. Yang, Y. Wenle, and Y. Fan, “An Improved Dynamic Prediction Fingerprint Localization Algorithm Based on KNN,” in Proc. 2016 Sixth International Conference on Instrumentation & Measurement, Computer, Communication and Control (IMCCC), Harbin, China, 21-23 July 2016.
[26]S. Banerjee, A. Choudhary, and S. Pal, “Empirical Evaluation of K-Means, Bisecting K-Means, Fuzzy C-Means and Genetic K-Means Clustering Algorithms,” in Proc. 2015 IEEE International WIE Conference on Electrical and Computer Engineering (WIECON-ECE), Dhaka, Bangladesh, 19-20 Dec. 2015.
[27]N. El Agroudy, N. Joram, and F. Ellinger, “Low Power RSSI Outdoor Localization System,” in Proc. 2016 12th Conference on Ph.D. Research in
Microelectronics and Electronics (PRIME), Lisbon, Portugal, 27-30 June 2016.
[28]T.Rappaport, Wireless Communications Principle and Practice Hall, 1996.
[29]O. Abdul Aziz, and T. Abdul Rahman, “Investigation of Path Loss Prediction in
Different Multi-Floor Stairwells at 900 MHz and 1800 MHz,”,Progress In Electromagnetics Research M, Vol. 39, 27–39, 2014.
[30]Z. Jianwu, and Z. Lu, “Research on Distance Measurement Based on RSSI of ZigBee” in Proc. 2009 ISECS International Colloquium on Computing, Communication, Control, and Management, Sanya, China, 8-9 Aug. 2009.
[31]P. Kumar, L. Reddy, and S. Varma, “Distance Measurement and Error Estimation Scheme for RSSI Based Localization in Wireless Sensor Networks,” in Proc. 2009 Fifth International Conference on Wireless Communication and Sensor Networks (WCSN), Allahabad, India, 15-19 Dec.2009.
[32]Constructing box and whisker plots,
https://www150.statcan.gc.ca/n1/edu/power-pouvoir/ch12/5214889- eng.htm.
[33]中央氣象局, https://www.cwb.gov.tw/V7/forecast/.
[34]回歸分析
https://zh.wikipedia.org/wiki/%E8%BF%B4%E6%AD%B8%E5%88%86%E6% %90.
[35]Haversine 公式
https://zh.wikipedia.org/wiki/%E5%%%E6%AD%A3%E7%%A2%5
%85%AC%E5%BC%.