全球互通微波存取(Worldwide Interoperability for Microwave Access, WiMAX)為一種無線通訊方法，可在大規模的覆蓋範圍提供寬頻網路，主要應用於都會網路。WiMAX是基於IEEE 802.16任務群組所發展針對無線都會區域網路的標準。為了保障各種多媒體的服務品質(Quality of Service, QoS)，服務流被分為五種不同類別。在IEEE 802.16標準中並沒有提供上行或下載頻寬的排程方法；因此，如何設計一個可滿足所有服務類別需求的排程演算法，是一項值得探討的議題。
輪詢是一種上傳頻道的傳送機制，在傳輸資料前，當基地台(Base Station, BS)進行輪流詢問後，被詢問的用戶端工作站(Subscribe Station, SS)才可以傳送頻寬要求訊息。在根據封包遺失率附掛的頻寬需求輪詢法(Polling According to Loss-rate Dependent Piggyback Bandwidth Request, PALDPBR)[1]中，基地台會根據工作站的即時性服務流是否有頻寬要求來調整輪詢時間間隔(Polling Interval)，當即時性服務流之延伸之即時輪詢服務(ertPS)提出頻寬要求時，輪詢間隔會維持在初始值的10ms，若無要求，輪詢時間間隔則往上加10ms，當輪詢時間間隔已為40ms，則不管有無要求，輪詢時間間隔將不再增加；而即時性服務流之即時輪詢服務(rtPS)輪詢間隔初始值為100ms，若有頻寬要求則輪詢間隔減10ms，至40ms而不再減少，反之若無頻寬要求，輪詢間隔加10ms，加至150ms後不再增加。此外，即時輪詢服務流(rtPS)可將頻寬要求附掛於延伸之即時輪詢服務流(ertPS)的頻寬要求封包上，也就是說，當基地台對該工作站的延伸之即時輪詢服務流提出輪詢時，工作站的延伸之即時輪詢服務流(ertPS)與即時輪詢服務流(rtPS)皆可向基地台提出頻寬要求，在參考的PALDPBR演算法中，即時性輪詢服務流(rtPS)不只可附掛頻寬要求於延伸之即時輪詢服務流(ertPS)上，也可根據封包遺失率的大小，在非即時性服務流(nrtPS)和盡力服務(BE)流的頻寬要求做附掛的動作。
在本論文中，我們根據PALDPBR提出了有選擇性的完全輪詢機制輪詢法(Selectively Fully Polling Scheme, SFPS)，其目的是為了改善當一訊框內，由於輪詢時間間隔的原因，導致可能沒有任一服務流於此訊框被輪詢並提出頻寬要求時，使得訊框未被充分利用。因此，此演算法中，根據輪詢間隔，當一訊框沒有任一服務流的佇列會被輪詢時，我們會比較所有服務流之下次輪詢時間，找出下次輪詢時間最接近目前時間的服務流，並讓該服務流可提早於此訊框被輪詢，也就是說，透過此演算法，可保證每個訊框內，皆有服務流佇列被輪詢並提出頻寬要求，使得每個訊框都能被充分利用，我們不只將即時性輪詢服務流(rtPS)的頻寬要求附掛於延伸之即時輪詢服務流(ertps)，也讓非即時性服務流(nrtPS)和盡力服務(BE)流可將頻寬要求附掛於上述兩種即時輪詢服務流上。模擬的結果顯示，在重載的情況下，不管是吞吐量或封包遺失率，兩種即時輪詢服務流皆比PALDPBR演算法中的，有更好的表現。

Worldwide Interoperability for Microwave Access (WiMAX) is a wireless communication schemes. It can provide broadband access to large-scale coverage and mainly used in metropolitan networks. WiMAX is a network using the family of standards of IEEE802.16. To ensure the Quality of Service (QoS) for different multimedia applications, the service flows are classified into five classes. Nevertheless, the scheduling algorithm was not defined in the standard of IEEE802.16. Therefore, it is a good issue to design a scheduling algorithm to meet the QoS requirement of all classes.
With Polling, the base station (BS) can poll subscribe stations (SS) in turn and the polled SS can send bandwidth request to the base station. In “Polling According to Loss-rate Dependent Piggyback Bandwidth Request” (PALDPBR) [1], BS changes the polling interval of extended real-time Polling Service (ertPS) and real-time Polling Service (rtPS) according to the bandwidth requests of these queues. With request upon polled, the polling interval of ertPS will be maintained at the initial value 10ms. Otherwise, polling interval will be increased by 10ms until 40ms. The initial polling interval of rtPS is set as 100ms.With request upon polled, the polling interval of it will be decreased by 10ms until 40ms. Otherwise, the polling interval will be increased 10ms until 150ms. Furthermore, the request of rtPS can be piggybacked on the bandwidth request of ertPS. In other words, the request of ertPS and rtPS of the same SS can be sent in one request if its ertPS is polled. Except this, in PALDPBR, rtPS can also be piggybacked on the request of non-real-time Polling Service (nrtPS) and Best-Effort (BE) according to the packet loss-rate.
In this dissertation, we proposed “Selectively Fully Polling Scheme” (SFPS) based on PALDPBR. Our goal is to improve the problem of wasting of frame bandwidth due to no polling. In SFPS, the next polling time of all service flow will be compared if no queue is polled in a frame. If next polling time of one queue is closest to the current time, this queue will be chosen to poll in this kind of frame. In this way, all frames will not be wasted due to no polling. Since the polled queue in this “idle” frame is chosen according to its next pooling time, the order of next polling scheme of all queues will not be changed by this scheme. In this way, the original polling scheme will not be changed greatly. The results show the throughput and packet loss rate of ertPS and rtPS are better than those in the PALDPBR.

[1] 呂富廣，「Polling according to loss-rate dependent piggyback bandwidth request for WiMAX networks」，碩士論文，國立台灣科技大學，台北市(2015)。
[2] 台灣區電機電子工業同業公會電子報。(民98年2月18日)。WiMAX與Wi-Fi無線寬頻通訊現況分析。(民103年5月24日)。取自http://www.teema.org.tw/epaper/20090218/industrial004.html
[3] 莊邵羽，「Fully Polling Scheme for Uplink of WiMAX Network」，碩士論文，國立台灣科技大學，台北市(2016)。
[4] IEEE 802.16 std., “IEEE standard for local and metropolitan networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” Oct 2004.
[5] 廖文嘉，「Emergency first MCS algorithm for WiMAX network」，碩士論文，國立台灣科技大學，台北市(2016)。
[6] OHNO, Y., SHIMIZU T., HIRAGURI, T., and NAKATSUGAWA, M., “Novel Frame Structures to Improve System Capacity and Latency Performance of a Time-Division Duplex Multihop Relay Wireless Access System,” IEEE Wireless Communications and Networking Conference, pp. 1-6, 2009.
[7] Yuh-Shyan Chen, “CH 5 無線寬頻網路”, 2012 取自：
http://www.csie.ntpu.edu.tw/~yschen/course/2012-1/WNMC/ch5.pdf
[8] Introduction to WiMAX (IEEE 802.16) and 3GPP LTE-A (2017) 取自: http://ocw.nctu.edu.tw/upload/classbfs1210030031115251.pdf
[9] IEEE Std 802.16-2012, “IEEE Standard for Air Interface for Broadband Wireless Access Systems”, August, 2012.
[10] V. Richter, R. Radeke, and R. Lehnert, “QoS Concept for IEEE 802.16-2012 Based WiMAX Networks,” in IEEE 10th Intl. Conf. Wireless and Mobile Computing, Networking and Commun. Larnaca, pp. 371–377, 2014
[11] H. Vishalakshi Prabhu, G. S. Nagaraja, “Quality of Service Guaranteed Delay Sensitive Polling Algorithm for WiMax Network: PQ_Poll” IEEE Conf., November, 2017.
[12] Gupta S. “Comparison of Various Scheduling Algorithms in WiMAX: A Brief Review,”International Conference on Advances in Management and Technology, pp. 34-36, 2013
[13] 葉秉修，「Fair packet loss rate and emergency packet first algorithm for WiMAX network」，碩士論文，國立台灣科技大學，台北市(2017)。
[14] H.C. Jang and K. C. Yang, “A QoS Aware Multi-Modulation CAC for WiMAX,” in International Symposium on Computer Science and Society, pp. 365-368, 2011.
[15] J. Chen, C. C. Wang, C. D. Tsai, C. W. Chang, S. S. Liu, J. Guo, W. J. Lien, J. H. Sum, and C. H. Huang, “The Design and Implementation of WiMAX Module for ns-2 Simulator”, Proc. of the ACM/ISCT/VALUETOOLS, October 2006.
[16] Hassan H. Elkarash, Nada M. Elshennawy, and Elsayed A. Sallam, “Evaluating QoS using Scheduling Algorithms in MPLS/VPN/WiMAX Networks,” IEEE conf., pp. 14-19, February 2017.
[17] Hann-Tzong Chern, Ynanming Liu, and Jhih-Syue Jhou, “Enhanced RED-based Scheduling (ERBS) Scheme in WiMAX Network,” IEEE conf., pp. 276-280, September 2013.