臺灣博碩士論文加值系統

本研究使用k-最近鄰居演算法（k-Nearest Neighbors, k-NN）與人工神經網路演算法（Artificial Neural Network, ANN）兩種機器學習演算法實現了基於LoRa的室內定位系統的模擬，並比較兩種演算法對於LoRa室內定位系統的準確率。
近年來，隨著科技的進步大型建築物有逐漸增加的現象，如大型賣場、機場航廈、台北車站和台北地下街等等，為了讓消費者在室內場所中也能享受和跟室外相同的基於定位的服務（Location-Based Service, LBS），因此室內定位的相關技術也越來越受到學術界的關注。由於在複雜的室內環境下容易因為多路徑干擾（Multipath Interference）造成接收訊號強度（Signal Strength）的衰落（Fading）現象，且參考節點（Reference Points）難以長期保持與使用者的直視(Line of Sight, LoS)狀態，因此適合使用指紋定位法（Fingerprinting）來達到較佳的定位準確率。為了讓本研究的室內定位系統達到節省硬體成本以及低功耗的特性，因此本研究使用LoRa當作接收訊號強度的室內定位無線通訊技術，並使用兩種機器學習演算法來評估LoRa技術使用在室內定位系統上的準確率，並比較兩種演算法對於本定位系統的適用程度。實驗結果證實在4米的方型平面地圖中，k-最近鄰居演算法在所有的標準差的環境中有86.01%的平均準確率，而使用人工神經網路演算法能夠有效的提升定位準確率，在所有的標準差的環境中有87.1%的平均準確率，優於k-最近鄰居演算法。

This study uses the two machine learning algorithms of k-Nearest Neighbors and Artificial Neural Network to simulate the LoRa-based indoor positioning system. And compare the accuracy of the two algorithms for the LoRa indoor positioning system.
In recent years, large and complex buildings have gradually increased, such as airport terminals, Department store, Taipei station and Taipei city mall, etc. In order to allow consumers to use Location-Based Service (LBS) in indoor environments, indoor positioning technology has also attracted academic attention. It is easy to cause Signal Strength Fading phenomenon due to Multipath Interference in complex indoor environment. And the Reference Points are difficult to maintain the Line of Sight (LoS) status with the user for a long time. Therefore, it is suitable to use Fingerprinting to achieve better positioning accuracy.
In order to achieve the low-cost and low energy consumption of the indoor positioning system of this study, this study uses LoRa as the wireless communication technology for receiving signal strength. Two machine learning algorithms are used to evaluate the accuracy of LoRa for indoor positioning systems, and the applicability of the two algorithms to the positioning system is compared.
The experiment confirmed that in the 4-meter square map, k-NN has an average accuracy of 86.01% in all standard deviation noises. The use of artificial neural network algorithm can effectively improve the positioning accuracy. There is an average accuracy of 87.1% in all standard deviation noises, which is better than the k-nearest neighbor algorithm.

摘要......i
Abstract......ii
誌謝......iv
目錄......v
表目錄......vii
圖目錄......viii
第一章 緒論......1
1.1 研究背景......1
1.2 研究動機與目的......2
1.3 論文架構......3
第二章 文獻回顧......4
2.1 室內定位系統......4
2.2室內定位方法......5
2.3 LoRa......6
2.3.1 展頻技術與LoRa調變......6
2.3.2 LoRa的封包結構......7
2.4 機器學習......8
2.4.1 K-最近鄰居演算法......9
2.4.2 感知機......10
2.4.3 活化函數......11
2.4.4 人工神經網路......15
2.4.5 目標函數......17
2.4.6 優化函數......18
2.4.7 反向傳播......21
第三章 系統架構......26
3.1 系統設計......26
3.1.1電路設計......27
3.2 實驗環境......30
3.3 通道模型的量測與結果......30
3.3.1 測量環境與測量方法......30
3.3.2 通道模型......31
3.4 室內定位實驗......33
3.4.1 建構室內模擬地圖......33
3.4.2 模擬定位實驗......34
第四章 實驗與結果......35
4.1 k-NN實驗設計......35
4.2 k-NN實驗結果......35
4.2.1 k-NN初步實驗......35
4.2.2 k-NN細部實驗......36
4.2.3 實驗小結......38
4.3 神經網路實驗設計......39
4.4 神經網路實驗結果......39
4.4.1 隱藏神經元最佳化實驗......39
4.4.2 批尺寸最佳化實驗......41
4.4.3 學習率最佳化實驗......42
4.4.4 迭代次數最佳化實驗......43
4.4.5 學習率衰減率最佳化實驗......44
4.4.6 實驗小結......46
4.5 實驗總結......47
第五章 結論與未來研究......49
5.1 結論......49
5.2 未來研究......49
參考文獻......50
Extended Abstract......53

[1] R. P and M. L. Sichitiu, "Angle of Arrival Localization for Wireless Sensor Networks," 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, Reston, VA, 2006, pp. 374-382.
[2] Yiu-Tong Chan, Wing-Yue Tsui, Hing-Cheung So and Pak-chung Ching, "Time-of-arrival based localization under NLOS conditions," in IEEE Transactions on Vehicular Technology, vol. 55, no. 1, pp. 17-24, Jan. 2006.
[3] F. Gustafsson and F. Gunnarsson, "Positioning using time-difference of arrival measurements," 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03)., Hong Kong, 2003, pp. VI-553.
[4] S. Mazuelas et al., "Robust Indoor Positioning Provided by Real-Time RSSI Values in Unmodified WLAN Networks," in IEEE Journal of Selected Topics in Signal Processing, vol. 3, no. 5, pp. 821-831, Oct. 2009.
[5] Z. Farid, R. Nordin, and M. Ismail, “Recent advances in wireless indoor localization techniques and system,” J. Comput. Netw. Commun., vol. 2013, 2013, Art. no. 185138, doi: 10.1155/2013/185138.
[6] 謝坤家，“無線感測網路下使用混合式神經網路室內定位之研究”，國立虎尾科技大學電機工程碩士班碩士論文，2016，頁4，https://hdl.handle.net/11296/3kqw8d。
[7] 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)," 2016 International Conference on Computer and Communication Engineering (ICCCE), Kuala Lumpur, 2016, pp. 72-77.
[8] V. Malyavej, W. Kumkeaw and M. Aorpimai, "Indoor robot localization by RSSI/IMU sensor fusion," 2013 10th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, Krabi, 2013, pp. 1-6.
[9] C. Cheng, H. Yang, M. R. Lyu, and I. King, “Where you like to go next: Successive point-of-interest recommendation,” in Proc. Int. Joint Conf. Artif. Intell., 2013, pp. 2605–2611.
[10] P. Dickinson, G. Cielniak, O. Szymanezyk and M. Mannion, "Indoor positioning of shoppers using a network of Bluetooth Low Energy beacons," 2016 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Alcala de Henares, 2016, pp. 1-8.
[11] I. Hwang and Y. J. Jang, "Process Mining to Discover Shoppers’ Pathways at a Fashion Retail Store Using a WiFi-Base Indoor Positioning System," in IEEE Transactions on Automation Science and Engineering, vol. 14, no. 4, pp. 1786-1792, Oct. 2017.
[12] L. Yu, Y. Liu, T. Chi and L. Peng, "An iBeacon-based indoor and outdoor positioning system for the fire emergency command," 2017 Forum on Cooperative Positioning and Service (CPGPS), Harbin, 2017, pp. 326-329.
[13] A. Khalajmehrabadi, N. Gatsis and D. Akopian, "Modern WLAN Fingerprinting Indoor Positioning Methods and Deployment Challenges," in IEEE Communications Surveys & Tutorials, vol. 19, no. 3, pp. 1974-2002, thirdquarter 2017.
[14] B. Wang, Q. Chen, L. T. Yang and H. Chao, "Indoor smartphone localization via fingerprint crowdsourcing: challenges and approaches," in IEEE Wireless Communications, vol. 23, no. 3, pp. 82-89, June 2016.
[15] C. Yang and H. r. Shao, "WiFi-based indoor positioning," in IEEE Communications Magazine, vol. 53, no. 3, pp. 150-157, March 2015.
[16] H. Liu, H. Darabi, P. Banerjee and J. Liu, "Survey of Wireless Indoor Positioning Techniques and Systems," in IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 37, no. 6, pp. 1067-1080, Nov. 2007.
[17] B. Li, J. Salter, A. G. Dempster, and C. Rizos, “Indoor positioning techniques based on wireless lan,” Auswireless Conference, 2006.
[18] R. Sanchez-Iborra, J. Sanchez-Gomez, J. BallestaViñas, M.-D. Cano, and A. F. Skarmeta, “Performance Evaluation of LoRa Considering Scenario Conditions,” Sensors, vol. 18, no. 3, 2018.
[19] U. Raza, P. Kulkarni and M. Sooriyabandara, "Low Power Wide Area Networks: An Overview," in IEEE Communications Surveys & Tutorials, vol. 19, no. 2, pp. 855-873, Secondquarter 2017.
[20] T. Hadwen, V. Smallbon, Q. Zhang and M. D'Souza, "Energy efficient LoRa GPS tracker for dementia patients," 2017 39th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), Seogwipo, 2017, pp. 771-774.
[21] M. Rizzi, P. Ferrari, A. Flammini, E. Sisinni and M. Gidlund, "Using LoRa for industrial wireless networks," 2017 IEEE 13th International Workshop on Factory Communication Systems (WFCS), Trondheim, 2017, pp. 1-4.
[22] Y. Li, X. Yan, L. Zeng and H. Wu, "Research on water meter reading system based on LoRa communication," 2017 IEEE International Conference on Smart Grid and Smart Cities (ICSGSC), Singapore, pp. 248-251, 2017.
[23] Semtech Corporation, "LoRa™ Modulation Basics", May 2015. [Online]. Available: https://www.semtech.com/uploads/documents/an1200.22.pdf
[24] A. Lavric and V. Popa, "Internet of Things and LoRa™ Low-Power Wide-Area Networks: A survey," 2017 International Symposium on Signals, Circuits and Systems (ISSCS), Iasi, 2017, pp. 1-5.
[25] Semtech Corporation, "SX1276/77/78/79 - 137 MHz to 1020 MHz Low Power Long Range Transceiver", August 2016. [Online]. Available: https://www.mouser.com/ds/2/761
/sx1276-1278113.pdf
[26] Li Deng, Jinyu Li, Jui-Ting Huang, Kaisheng Yao, Dong Yu, Frank Seide, Michael Seltzer, GeojjZweig, Xiaodong He, Jason Williams, Yifan Gong, and Alex Acero, “Recent advances in deep learning for speech research at Microsoft,” in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2013, pp. 8604–8608.
[27] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural networks,” in 2012 Neural Information Processing Systems (NIPS), 2012, pp. 1097–1105.
[28] Xingbin Ge and Zhiyi Qu, "Optimization WIFI indoor positioning KNN algorithm location-based fingerprint," 2016 7th IEEE International Conference on Software Engineering and Service Science (ICSESS), Beijing, 2016, pp. 135-137.
[29] V. Sze, Y. Chen, T. Yang and J. S. Emer, "Efficient Processing of Deep Neural Networks: A Tutorial and Survey," in Proceedings of the IEEE, vol. 105, no. 12, pp. 2295-2329, Dec. 2017.
[30] X. Glorot, A. Bordes, and Y. Bengio, “Deep Sparse Rectifier Neural Networks,” in Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.
[31] S. Ruder, “An overview of gradient descent optimization algorithms,” Cornell University, vol. arXiv：1609.04747, 2016. [Online]. Available:http://arxiv.org/abs/1609.04747
[32] L. Bottou, "Large-scale machine learning with stochastic gradient descent", in 19th international conference on computational statistics, pp. 177-186, 2010.
[33] G. Hinton, N. Srivastava, and K. Swersky, “Lecture 6a overview of mini–batch gradient descent,” Coursera Lecture slides. [Online]. Available:http://www.cs.toronto.edu/~tijmen
/csc321/slides/lecture_slides_lec6.pdf
[34] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” J. Mach. Learn. Res., vol. 12, pp. 2121–2159, Feb. 2011.
[35] D. P. Kingma and J. L. Ba, “Adam: A method for stochastic optimization,” in Proc. Int. Conf. Learn. Represent., 2015, pp. 1–41.