物聯網(Internet of Things, IoT)的特性為大量的感測器(Sensors)同時連線上網，閘道器(Gateway)需要對收集到的感測器訊框(Frame)做排程，但是常見的演算法都沒有考慮感測器過去一段時間的平均資料傳輸率(Average Data Rate)，所以這些演算法會造成訊框在佇列中等待的時間增加而導致訊框遺失的現象，為了解決這個問題，本論文在閘道器中提出一個革新式成比例公平的排程(Novel-Proportional-Fair Queuing, NPFQ)演算法。為了進一步驗證此演算法的效能，首先，我們在Modbus遠端終端單元(Modbus Remote Terminal Unit, Modbus RTU)通訊協定中設計兩個欄位，閘道器會根據這兩個欄位來區分訊框的即時性(Real-Time)與非即時性(Non-Real-Time)、感測器資料產生的頻率(Generated Frequency)，接著，我們在閘道器中建立四條佇列來對這些被分類後的訊框進行排程，如果閘道器在一段時間內的訊框遺失率(Frame Loss Ratio, FLR)上升且佇列的使用率(Utilization)超過一個閾值(Threshold)時，NPFQ就會計算瞬間資料傳輸率與平均資料傳輸率的比值(Ratio of Instantaneous Data Rate to Average Data Rate, RIA)，RIA的值可以用來動態改變佇列的權重。為了比較與分析此演算法，我們在閘道器使用樹莓派(Raspberry Pi, RPi)實作NPFQ，我們比較NPFQ與其他演算法的訊框遺失率與平均資料傳輸率，最後，我們驗證NPFQ相比其他演算法的訊框遺失率與平均資料傳輸率確實有顯著的改善。

Internet of Things (IoT) is characterized by a large number of sensors connected to Internet at the same time. The gateway to Internet needs to schedule the arriving frames from data-collecting sensors. Most algorithms from literatures do not consider the average data rate of the sensors over a period of time. Thus, these algorithms will cause some frames to wait longer in the queue and lead to frame loss. To solve this problem, we propose a revolutionary Novel-Proportional-Fair Queuing (NPFQ) algorithm. To further validate the performance of the proposed algorithm, we design two frame formats in the Modbus Remote Terminal Unit (Modbus -RTU) protocol. The first format allow the gateway to distinguish the frames between real-time and non-real-time. The second format can record the data collection frequency of sensors in the frame header. We design four queues in the gateway to schedule these arriving frames. If frame loss ratio (FLR) of the gateway rises over a period of time and utilization of the queue exceeds a certain threshold, NPFQ will calculate the Ratio of Instantaneous Data Rate to Average Data Rate (RIA). The value of RIA can be used to dynamically change the weights of the queues. To analyze and evaluate the proposed algorithm, we use Raspberry Pi (RPi) to implement NPFQ algorithm in the gateway. We compare FLR and average data rate of NPFQ with the algorithms from the literatures. Finally, we verify that NPFQ have a significant improvement in FLR and average data rate compared with other existing algorithms.

論文審定書i
致謝ii
摘要iii
Abstractiv
目錄v
圖目錄vii
表目錄ix
第一章 導論1
1.1研究動機1
1.2研究方法1
1.3章節介紹2
第二章 物聯網的通訊協定與排程3
2.1物聯網實體層與通訊協定3
2.1.1 EIA-4853
2.1.2 Modbus RTU4
2.2物聯網的MQTT通訊協定6
2.3物聯網的閘道器7
2.3.1協定的轉換8
2.3.2 Random Early Detection8
2.3.3排程演算法9
2.4物聯網的即時性13
2.5相關研究13
第三章 成比例公平的排程演算法16
3.1感測器的分群16
3.2 NPFQ演算法19
第四章 實驗與結果分析28
4.1實驗環境與設備規格28
4.2參數的設定31
4.3實驗的虛擬碼31
4.3.1訊框進入佇列的虛擬碼32
4.3.2五種排程演算法37
4.4結果與分析48
4.4.1訊框遺失率的分析48
4.4.2資料傳輸率的分析51
第五章 結論與未來工作54
5.1結論54
5.2遭遇問題55
5.3未來工作55
Reference56
Acronyms60
Index62

[1] V. Ajay Kumar, “Overcoming Data Corruption in RS485 Communication,” International Conference on Electromagnetic Interference and Compatibility (INCEMIC), Madras, India, pp. 9-12, Dec. 1995.
[2] “Electrical Characteristics of Generators and Receivers for Multipoint Systems,” Telecommunications Industry Association (TIA), TR-30.2, Mar. 1998.
[3] A. K. Gupta, A. Raman, N. Kumar, and R. Ranjan, “Design and Implementation of High-Speed Universal Asynchronous Receiver and Transmitter (UART),” 7th International Conference on Signal Processing and Integrated Networks (SPIN), Noida, India, pp. 295-300, Feb. 2020.
[4] P. Sharma, A. Kumar, and N. Kumar, “Analysis of UART Communication Protocol,” International Conference on Edge Computing and Applications (ICECAA), Tamilnadu, India, pp. 323-328, Oct. 2022.
[5] D. Slaughter, “The Emitter-Coupled Differential Amplifier,” in IRE Transactions on Circuit Theory, vol. 3, no. 1, pp. 51-53, Mar. 1956.
[6] G. Gabor and G. Livint, “Solution for Monitoring and Remote Control Based on Modbus RTU and S7-1200 PLC,” International Conference on Electromechanical and Energy Systems (SIELMEN), Iasi, Romania, pp. 462-465, Oct. 2021.
[7] V. G. Găitan and I. Zagan, “Modbus Protocol Performance Analysis in a Variable Configuration of the Physical Fieldbus Architecture,” in IEEE Access, vol. 10, pp. 123942-123955, Nov. 2022.
[8] “MQTT Version 3.1.1 Plus OASIS Standard Incorporating Approved Errata 01,” Organization Advancement Structured Information Standards (OASIS), Dec. 2015.
[9] E. Longo, A. E. C. Redondi, M. Cesana, and P. Manzoni, “BORDER: A Benchmarking Framework for Distributed MQTT Brokers,” in IEEE Internet of Things Journal, vol. 9, no. 18, pp. 17728-17740, Sept. 2022.
[10] B. Oniga, A. Munteanu, and V. Dadarlat, “Open-Source Multi-Protocol Gateway for Internet of Things,” 17th RoEduNet Conference: Networking in Education and Research (RoEduNet), Cluj-Napoca, Romania, pp. 1-6, Sept. 2018.
[11] I. Cidon, A. Khamisy, and M. Sidi, “Analysis of Packet Loss Processes in High-Speed Networks,” in IEEE Transactions on Information Theory, vol. 39, no. 1, pp. 98-108, Jan. 1993.
[12] S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,” in IEEE/ACM Transactions on Networking, vol. 1, no. 4, pp. 397-413, Aug. 1993.
[13] S. B. Danladi and F. U. Ambursa, “DyRED: An Enhanced Random Early Detection Based on a New Adaptive Congestion Control,” 15th International Conference on Electronics, Computer and Computation (ICECCO), Abuja, Nigeria, pp. 1-5, Dec. 2019.
[14] A. Proskochylo, M. Zriakhov, and A. Akulynichev, “The Effects of Queueing Algorithms on QoS for Real-Time Traffic in Process of Load Balancing,” International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, pp. 575-580, Oct. 2018.
[15] S. Gupta and M. El Zarki, “Traffic Classification for Round-Robin Scheduling Schemes in ATM Networks,” IEEE INFOCOM '93 The Conference on Computer Communications, Proceedings, San Francisco, CA, USA, vol.2, pp. 820-827, Mar. 1993.
[16] A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” in Journal of Internetworking Research and Experience, pp. 3-26, Oct. 1990.
[17] Jen-Yi Huang, Yu-Kuo Tseng, Mao Sheng Lin, and Wen-Shyong Hsieh, “Error Rate-Based Dynamic Weighted Fair Queuing in Wireless Networks,” The IEEE Conference on Local Computer Networks 30th Anniversary (LCN'05), Sydney, NSW, Australia, pp. 546-553, Nov. 2005.
[18] S. B. Lee, I. Pefkianakis, A. Meyerson, S. Xu, and S. Lu, “Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink,” IEEE INFOCOM, Rio de Janeiro, Brazil, pp. 2611-2615, Apr. 2009.
[19] I. Budhiraja, N. Kumar, and S. Tyagi, “Deep-Reinforcement-Learning-Based Proportional Fair Scheduling Control Scheme for Underlay D2D Communication,” in IEEE Internet of Things Journal, vol. 8, no. 5, pp. 3143-3156, Mar. 2021.
[20] “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Study on New Radio Access Technology: Radio Access Architecture and Interfaces (Release 14),” 3GPP, TR-38.801, Ver. 14.0.0, Apr. 2017.
[21] S. C. Mukhopadhyay, S. K. S. Tyagi, N. K. Suryadevara, V. Piuri, F. Scotti, and S. Zeadally, “Artificial Intelligence-Based Sensors for Next Generation IoT Applications: A Review,” in IEEE Sensors Journal, vol. 21, no. 22, pp. 24920-24932, Nov. 2021.
[22] S. Khriji, D. El Houssaini, R. Barioul, T. Rehman, and O. Kanoun, “Smart-Lab: Design and Implementation of an IoT-Based Laboratory Platform,” IEEE 6th World Forum on Internet of Things (WF-IoT), New Orleans, LA, USA, pp. 1-5, Jun. 2020.
[23] A. Pughat and V. Sharma, “Queue Discipline Analysis for Dynamic Power Management in Wireless Sensor Node,” IEEE India Conference (INDICON), New Delhi, India, pp. 1-5, Dec. 2015.
[24] T. D. Lagkas, P. Angelidis, D. G. Stratogiannis, and G. I. Tsiropoulos, “Analysis of Queue Load Effect on Channel Access Prioritization in Wireless Sensor Networks,” IEEE International Conference on Distributed Computing in Sensor Systems Workshops (DCOSSW), Santa Barbara, CA, USA, pp. 1-62010, Jun, 2010.
[25] L. Karim, N. Nasser, T. Taleb, and A. Alqallaf, “An Efficient Priority Packet Scheduling Algorithm for Wireless Sensor Network,” IEEE International Conference on Communications (ICC), Ottawa, Canada, pp. 334-338, Jun, 2012.
[26] K. Dhote and G. M. Asutkar, “Optimization of Routing Techniques in Wireless Sensor Network using Queue Management,” Devices for Integrated Circuit (DevIC), Kalyani, India, pp. 500-504, Mar, 2017.
[27] Z. Zhou, J. Lee, M. S. Berger, S. Park, and Y. Yan, “Simulating TSN Traffic Scheduling and Shaping for Future Automotive Ethernet,” in Journal of Communications and Networks, vol. 23, no. 1, pp. 53-62, Feb. 2021.
[28] G. P. Sunitha, S. M. D. Kumar, and B. P. V. Kumar, “A Pre-Emptive Multiple Queue Based Congestion Control for Different Traffic Classes in WSN,” International Conference on Circuits, Communication, Control and Computing, pp. 212-218, Bangalore, India, Nov. 2014.