簡易檢索 / 詳目顯示

研究生: 張哲維
Chang, Che-Wei
論文名稱: 結合KNN與CART概念輔助之Wi-Fi Coarse-Fine三邊定位演算法的建立與其於Super-Giga Fab之應用
Development of KNN and CART Assisted Wi-Fi Coarse-Fine Trilateration Localization Schemes for Super-Giga Fab Applications
指導教授: 陳國聲
Chen, Kuo-Shen
學位類別: 碩士
Master
系所名稱: 工學院 - 機械工程學系
Department of Mechanical Engineering
論文出版年: 2023
畢業學年度: 111
語文別: 中文
論文頁數: 204
中文關鍵詞: 三邊定位KNN演算法CART演算法Wi-Fi定位超大型晶圓廠
外文關鍵詞: Super-Giga Fab, KNN algorithm, CART algorithm, Wi-Fi localization, Trilateration
相關次數: 點閱:70下載:6
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 近年來隨著全球化的發展及製程的技術與複雜度上升,工廠的規模逐漸增大且複雜化,到達了僅依靠人力無法顧及全部的程度。而為了因應此種情形,科技業逐漸以機器自動化運作的方式進行製成,以高效率且低失誤率的方式代替人力減少生產成本,並結合了資訊傳輸使各個機台之間能夠互相進行溝通進行協調,同時為了企業本身技術的機密保護,對於資訊安全的要求亦有了重大的提升。而在半導體產業中,此情形產生了Super-Giga Fab的概念。而在Super-Giga Fab中,人員的主要負責項目即為機台的維護與整修,避免機台的故障而導致生產延宕的情形發生,然而,由於廠區裡複雜且廣闊的空間,導致維修工具和零件的使用群體的重疊度跟使用範圍增加,使得工件容易發生被取用後無法確定取用的人員和工件目前所處的位置不明的情形發生,導致當要使用時,無法順利地取得工件,造成工作效率低落。目前多以無線定位系統如UWB或RFID的方式避免上述情形發生。然而,由於Super-Giga Fab中嚴密的資安政策,通常的無線系統難以被應用於工廠之中。而為了建立無線網路系統,在路由器廣泛的分布Super-Giga Fab中以作為信標發送Wi-Fi訊號,同時若是對於目標物的定位精準度並無太高的要求,利用Wi-Fi進行無線定位的方式會成為較佳的選擇。因此本文利用智慧工廠中廣泛分布的路由器的訊號做為依據,利用三邊定位的方式對訊號蒐集模組進行定位,同時以KNN演算法、CART演算法、機器學習與距離校正的方式對定位流程進行輔助,提高定位結果的精確度,並將定位結果以繪圖的方式進行呈現,增加資料的可讀性。最終成功的將定位結果的平均誤差限縮在約1.5m,足以輔助員工對於工具的搜尋。以此,本論文透過蒐集Wi-Fi訊號的方式進行定位,使在進行工件尋找時能夠更容易的取的工件目前所處的大致位置,減少不必要的搜尋時間並增加工作時的效率。

    With the rapid development of factory and rise in needs in technology of production in recent years, the scale of the factory gradually increases, becoming more complex to a level where manpower alone cannot take care of everything. In order to cope with this situation, the technology industry is gradually adopting the automatic operation of machines to replace manpower to reduce production costs with high efficiency and low error rate, and to combine information transmission to enable each machine to communicate with each other to coordinate. At the same time, in order to protect the confidentiality of the company's own technology, the requirements for information security have also been greatly improved. In this condition, the concept of Super-Giga Fab was born in semiconductor factory. In Super-Giga Fab, the workers are mainly responsible for the maintenance and repair of the machine, so as to avoid the production delay caused by the failure of the machine. Yet, due to the complex and enormous space in the factory area, the overlapping degree and possibility of use of maintenance tools and parts have increased, making it easier for the workpiece to be taken and the person who took it and the current location of the workpiece to be unknown. Circumstances occur, resulting in the inability to obtain the workpiece smoothly when it needs to be used, resulting in low work efficiency. Currently, wireless positioning systems such as UWB or RFID are mostly used to avoid the occurrence of the above situation. However, due to the strict information security policy in Super-Giga Fab, it is difficult to apply the usual wireless system in the factory. In order to establish a wireless network system, routers are widely distributed in Super-Giga Fab to send Wi-Fi signals as beacons. At the same time, if the positioning accuracy of the target is not too high, use Wi-Fi for wireless as the way of positioning will become a better choice. As a result, this article uses the widely distributed router signals in the super-giga fab as a basis and applies the trilateration positioning method to locate the signal collection module. At the same time, the positioning process are assisted by KNN algorithm, CART algorithm, machine learning and distance correction to improve the accuracy of the localization results. After the calculation process, the localization result is presented in the form of graphics to increase the readability of the data. In the end, the average error of the positioning results was successfully limited to about 1.5m, which is enough to assist employees in searching for tools. In summary, this thesis locates by collecting Wi-Fi signals, so that it is easier to get the approximate location of the workpiece when searching for the workpiece, reducing unnecessary search time and increasing work efficiency.

    摘要 I Abstract II Extend Abstract III 致謝 III 目錄 XXXVII 圖目錄 XLII 表目錄 XLIX 符號說明 L 第一章 緒論 1 1.1 前言 1 1.2 文獻回顧 8 1.2.1 無線定位於室內之應用 8 1.2.2 資訊安全系統 10 1.2.3 人機介面顯示 10 1.2.4 定位演算法之輔助 11 1.3 研究動機與目的 13 1.4 實驗室相關研究 15 1.5 研究方法 17 1.6 全文架構 18 第二章 無線定位技術相關背景介紹 20 2.1 本章介紹 20 2.2 無線定位方式 21 2.2.1 Angle of Arrival (AOA) 21 2.2.2 Time of Arrival (TOA) 24 2.2.3 Received Signal Strength Index (RSSI) 定位 27 2.3 無線定位系統 31 2.3.1 Ultra-Wide Band (UWB) 31 2.3.2 Radio frequency identification system (RFID) 32 2.3.3 Wi-Fi 35 2.4 討論與本章結論 38 第三章 Wi-Fi訊號於定位應用之介紹 39 3.1 本章介紹 39 3.2 Wi-Fi訊號應用於定位之資訊 40 3.2.1 Media Access Control Address (MAC Address) 40 3.2.2 Receive Signal Strength Index (RSSI) 43 3.3 定位演算法與定位輔助演算法 47 3.3.1 三邊定位 47 3.3.2 K- Nearest-Neighbor(KNN) 演算法 50 3.3.3 Classification And Regression Tree(CART) 演算法 53 3.3.4 Support Vector Machine 演算法 54 3.3.4.1 One-against-All ( OaA) 55 3.3.4.2 One-against-One (OaO) 56 3.3.5 Super Resolution(SR) 演算法 57 3.4 討論與本章結論 59 第四章 整體研究概念設計 60 4.1 本章介紹 60 4.2 情境設計 62 4.2.1 場地建立概念 64 4.2.2 定位測試概念 65 4.2.3 定位輔助概念 66 4.3 路由器訊號蒐集流程設計 68 4.4 本章結論 72 第五章 定位系統之建立 73 5.1 本章介紹 73 5.2定位系統整體設計 75 5.3 應用於實驗系統之設備介紹 77 5.3.1 AmebaD RTL8722DM 77 5.3.2 Aruba instant on 79 5.4 Wi-Fi訊號抓取、分析與傳輸 80 5.4.1 訊號分析 80 5.4.2 訊號傳輸 80 5.5 Wi-Fi定位計算程式建立 83 5.5.1 Coarse定位建立概念 84 5.5.2 Fine定位建立概念 84 5.5.3 KNN與CART演算法於定位輔助之概念 85 5.6 本章結論 87 第六章 Coarse-Fine定位流程於Wi-Fi定位之發展 88 6.1 本章介紹 88 6.2 RSSI浮動對於定位系統之影響與改善方式 90 6.3 Coarse定位法之建立 93 6.4 Fine定位法之建立 99 6.4.1 RSSI求得距離之方式 99 6.4.1.1 曲線分段流程 100 6.4.1.2 Support Vector Machine (SVM)演算法於距離計算之應用 102 6.4.2 三邊定位演算法之建立 103 6.5 Coarse-Fine定位流程建立 110 6.6 本章結論 112 第七章 結合KNN與CART演算法增加系統之強健性 113 7.1 本章介紹 113 7.2 環境干擾於定位流程之影響 115 7.3 KNN演算法於Wi-Fi定位之應用 118 7.3.1 KNN演算法之流程設計 118 7.3.2 KNN演算法之驗證 122 7.3.3 KNN演算法於Coarse定位之輔助 126 7.3.4 Super Resolution演算法輔助KNN演算法指紋庫建立 127 7.3.5 KNN指紋地圖精細化之驗證 129 7.4 Classification And Regression Tree(CART) 演算法 134 7.4.1 CART演算法校正情境 134 7.4.2 CART演算法於Wi-Fi定位之應用 135 7.4.3 CART演算法之驗證 138 7.5 KNN、CART演算法於Wi-Fi定位之輔助結果 140 7.6 本章結論 143 第八章 Wi-Fi定位流程之實驗驗證 144 8.1 本章介紹 144 8.2 Wi-Fi定位測試場地、環境與路徑之建立 146 8.3 Wi-Fi訊號蒐集與分析之結果 150 8.4 Coarse-Fine定位流程求得之結果 154 8.5 KNN與CART演算法輔助於定位之結果 159 8.5.1 KNN演算法之輔助結果 159 8.5.2 KNN與CART演算法整合之輔助結果 160 8.6 定位結果之探討 163 8.7 討論與本章結論 166 第九章 研究結果與討論 167 9.1 全文歸納 167 9.2 研究成果討論 171 9.3 未來工作 175 第十章 結論與未來展望 179 10.1 本文結論 179 10.2 本文貢獻 182 10.3 未來工作 184 參考文獻 185 附錄A KNN演算法之模擬程式 190 附錄B CART演算法之模擬程式 192 附錄C 本研究所建立之定位程式 193

    [1] L. Lin, H. Chu, C. Hung, Y. Lee, and P. Yeh, “Factory automation migration experience for foundry fab from 200 mm to 300 mm,” Semiconductor Manufacturing Technology Workshop, pp. 278-281, Hsinchu, Taiwan, Dec. 2002.
    [2] T. V. Karlova, A. Y. Bekmeshov, S. A. Sheptunov, and N. M. Kuznetsova, “Methods dedicated to fight against complex information security theats on automated factories systems,” IEEE Conference on Quality Management, Transport and Information Security, Nalchik, Russia, Oct. pp. 72-76, 2016.
    [3] B. Rahmadya, J. Wang, F. Kong, S. Takeda, K. Kagoshima, and M. Umehira, “Ultra-high frequency band radio frequency identification tag enabling color-change for inventory management systems: a color-change tag,” IEEE Journal of Radio Frequency Identification, vol. 4, no. 2, pp. 101-106, 2019.
    [4] L. Liu, H. Zhao, T. S. See, and Z. N. Chen, “A printed ultra-wideband diversity antenna,” IEEE International Conference on Ultra-Wideband Fall, Waltham, USA, Sept. pp. 351-356, 2006.
    [5] D. Bandyopadhyay, S. De, S. H. Roy, D. Biswas, M. Bhose, and R. Karmakar, “Network throughput improvement in Wi-Fi 6 over Wi-Fi 5: A comparative performance analysis,” International Conference on Computer, Electrical & Communication Engineering, Kolkata, India, Jan. pp. 1-6, 2023.
    [6] “IEC/IEEE international standard-systems and software engineering–system life cycle processes,” ISO/IEC/IEEE 15288 First edition 2015–05–15 ,2015.
    [7] M. Ivanić and I. Mezei, “Distance estimation based on rssi improvements of orientation aware nodes,” Zooming Innovation in Consumer Technologies Conference, Novi Sad, Serbia, May. pp. 140-143, 2018.
    [8] M. Cypriani, F. Lassabe, P. Canalda, and F. Spies, “Open wireless positioning system: A wi-fi-based indoor positioning system,” IEEE 70th Vehicular Technology Conference, Anchorage, USA, Sept. pp. 1-5, 2009.
    [9] J. Xiao, Z. Liu, Y. Yang, D. Liu, and X. Han, “Comparison and analysis of indoor wireless positioning techniques,” International Conference on Computer Science and Service System, Nanjing, China, June. pp. 293-296, 2011.
    [10] 陳維倫, 基於微控制器之無線感測網路系統於智慧工廠之應用發展:邊緣運算、網路資安、及工業機聯網, 國立成功大學機械工程學系碩士論文, 2022.
    [11] 盧尚毅, 設計APP輔助至工廠機具與工具的行動管理與狀態監控, 國家科學及技術委員會大專學生研究計畫成果報告, 2023.
    [12] M. M. Butt, A. Rao, and D. Yoon, “RF fingerprinting and deep learning assisted UE positioning in 5G,” IEEE 91st Vehicular Technology Conference, Victoria, Canada, May. pp. 1-7, 2020.
    [13] R. Peng and M. L. Sichitiu, “Angle of arrival localization for wireless sensor networks,” 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, vol. 1, pp. 374-382, 2006.
    [14] M. Bocquet, C. Loyez, and A. Benlarbi-Delai, “Using enhanced-TDOA measurement for indoor positioning,” IEEE Microwave and Wireless Components Letters, vol. 15, no. 10, pp. 612-614, 2005.
    [15] RSSI-距離理論之關係圖
    https://iot-book.github.io/0_%E5%89%8D%E8%A8%802/
    [16] S. Boonsriwai and A. Apavatjrut, “Indoor WIFI localization on mobile devices,” 10th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, Krabi, Thailand, May. pp. 1-5, 2013.
    [17] N. Hernández, M. Ocaña, J. M. Alonso, and E. Kim, “WiFi-based indoor localization and tracking of a moving device,” Ubiquitous Positioning Indoor Navigation and Location Based Service, Corpus Christi, USA, Feb. pp. 281-289, 2014.
    [18] J. Zhang, P. V. Orlik, Z. Sahinoglu, A. F. Molisch, and P. Kinney, “UWB systems for wireless sensor networks,” Proceedings of the IEEE, vol. 97, no. 2, pp. 313-331, 2009.
    [19] X. Jia, Q. Feng, T. Fan, and Q. Lei, “RFID technology and its applications in Internet of Things (IoT),” 2nd International Conference on Consumer Electronics, Communications and Networks, Yichang, China, Apr. pp. 1282-1285, 2012.
    [20] 路由器發布訊息格式
    https://www.tsnien.idv.tw/Network_WebBook/chap15/15-6%20%e8%a8%8a%e6%a1%86%e6%a0%bc%e5%bc%8f.html
    [21] MAC Address之組成格式
    https://course-net.com/blog/mac-address-adalah/
    [22] J. Martin et al., “A study of MAC address randomization in mobile devices and when it fails,” arXiv preprint arXiv:1703.02874, 2017.
    [23] R.-H. Wu, Y.-H. Lee, H.-W. Tseng, Y.-G. Jan, and M.-H. Chuang, “Study of characteristics of RSSI signal,” IEEE International Conference on Industrial Technology, Chengdu, China, Apr. pp. 1-3, 2008.
    [24] M. Shchekotov, “Indoor localization method based on Wi-Fi trilateration technique,” Proceeding of the 16th Conference of Fruct Association, Oulu, Finland, Oct. pp. 177-179, 2014.
    [25] M. E. Rusli, M. Ali, N. Jamil, and M. M. Din, “An improved indoor positioning algorithm based on rssi-trilateration technique for internet of things (iot),” International Conference on Computer and Communication Engineering, Kuala Lumpur, Malaysia, Jul. pp. 72-77, 2016.
    [26] KNN演算法示意圖
    https://ithelp.ithome.com.tw/articles/10269826?sc=iThelpR
    [27] S. Zhang, X. Li, M. Zong, X. Zhu, and R. Wang, “Efficient KNN classification with different numbers of nearest neighbors,” IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 5, pp. 1774-1785, 2017.
    [28] W. Y. Loh, “Fifty years of classification and regression trees,” International Statistical Review, vol. 82, no. 3, pp. 329-348, 2014.
    [29] SVM演算法區分類別示意圖
    https://rstudio-pubs-static.s3.amazonaws.com/290039_68d95ec88f41401 390a2329fb92fdf64.html
    [30] J. Milgram, M. Cheriet, and R. Sabourin, ““One against one” or “one against all”: Which one is better for handwriting recognition with SVMs?,” Tenth International Workshop on Frontiers in Handwriting Recognition, Suvisoft, 2006.
    [31] SR演算法流程示意圖
    https://ithelp.ithome.com.tw/m/articles/10248547
    [32] S. C. Park, M. K. Park, and M. G. Kang, “Super-resolution image reconstruction: a technical overview,” IEEE Signal Processing Magazine, vol. 20, no. 3, pp. 21-36, 2003.
    [33] Y. Ngoko and C. Cérin, “An edge computing platform for the detection of acoustic events,” IEEE International Conference on Edge Computing, Honolulu, USA, Jun. pp. 240-243, 2017.
    [34] Moving Average平滑概念圖
    https://www.aranacorp.com/en/tag/programming/page/2/
    [35] CART演算法分類示意圖
    https://www.mdpi.com/2227-7390/11/3/566/htm

    下載圖示 校內:立即公開
    校外:立即公開
    QR CODE