IEEE 802.16標準是一種新興的無線都會網路技術，其具有高傳輸速率、較廣的訊號覆蓋與支援多媒體服務等優點。為了滿足不同需求的資料服務，IEEE 802.16定義了多種服務品質(Quality of Service, QoS)服務類別。然而，在IEEE 802.16標準中並沒有規定頻寬分配的排程法。因此，如何設計一個好的排程演算法來滿足所有服務品質類別的需求就成為了主要探討的議題。
一個即時性的封包必須在限制的時間內傳送出去，一旦封包的傳送延遲超過可容忍的最大值，封包就會被丟棄。本論文中我們提出根據即時性服務(ertPS與rtPS)佇列中封包剩餘時間的排程演算法。第一回合將每個即時性服務佇列中緊急的封包(剩餘時間小於或等於一個訊框的時間)在當前的訊框排程傳送。第二回合再根據當前佇列的情況計算封包的平均剩餘時間(Average Remaining Time)，針對即時性服務的優先權，個別給予平均剩餘時間不同的比率 α 並設定該服務類型的閾值t。佇列中封包的剩餘時間小於等於t就在當前訊框將它排程，直到所有的即時性服務佇列都被服務完為止。如果第二回合排程結束仍然有剩餘頻寬，第三回合使用輪詢式(Round Robin, RR)演算法將剩餘頻寬分配給所有的佇列。模擬結果顯示出，選擇適當的 α 即時性服務的封包丟失率是令人滿意的。

IEEE 802.16 Standard is a new technology for Wireless Metropolitan Area Network (WMAN). It has the advantages of high transmission rate, wide signal coverage and multimedia services. IEEE 802.16 defines several service classes for Quality of Service (QoS) which will meet a variety of data service demands. However, it does not define the scheduling algorithm to allocate bandwidth. Therefore, it becomes a major of exploring to design an good bandwidth allocation algorithm to meet the QoS requirement of all classes.
A constraint on a real-time packet is its transmission time. If its transmission delay is over a tolerated value, this packet will be discarded. In this thesis, we propose a scheduling algorithm according to the remaining time of the packet in queues of real-time services (ertPS and rtPS). In the first round of one scheduling, the urgent packets (the packets whose remaining time are smaller than one frame) will be scheduled for transmission in this frame. In the second round, average remaining time t will be computed for each queue and a threshold is set according to this value and the ratio α of its class. A packet in this queue will be scheduled in this frame if its remaining time is less than or equal to the α. This scheduling will be done on all queues of real-time services. If there is remaining bandwidth after the second round, Round Robin (RR) would be used in the third round to allocate bandwidth for all queues. The simulation result shows the loss rate of real-time services will be satisfied with a good choice of α.

[1] RFiD Centre(n.d.). Wireless Standards. Retrieved June 1, 2013, from http://www.rfidc.com/docs/introductiontowireless_standards.htm
[2] The Future of Things(n,d.). The Future of WiMAX. Retrieved June 1, 2013, from http://thefutureofthings.com/3898-the-future-of-wimax/
[3] Oktay, M. and Mantar, H. A., “A Real-Time Scheduling Architecture for IEEE 802.16 - WiMAX Systems,” 2011 IEEE 9th International Symposium on Applied Machine Intelligence and Informatics (SAMI), pp. 189-194 (2011).
[4] D. Pareek。藍海商機WiMAX通訊技術與策略佈局(初版) (李蔚澤譯)，碁峰資訊，台北(2006)。
[5] IEEE Std 802.16-2012, “IEEE Standard for Air Interface for Broadband Wireless Access Systems” , August 2012.
[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] Andrews, J. G., Ghosh, A., and Muhamed, R., Fundamentals of WiMAX: Understanding Broadband Wireless Networking. Prentice Hall, NJ. (2007).
[8] IEEE Std 802.16-2004, “IEEE Standard for Local and Metropolitan Area Networks - Part 16: Air Interface for Fixed Broadband Wireless Access Systems” , October 2004.
[9] IEEE Std 802.16e-2005, “IEEE Standard for Local and Metropolitan Area Networks - Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands” , February 2006.
[10] Shreedhar, M. and Varghese, G., “Efficient Fair Queuing Using Deficit Round Robin” , IEEE/ACM Transactions on Networking, Vol. 4, No. 3, pp.375-385 (1996).
[11] Chen, J. F., Jiao, W. H., and Wang, H. X., “A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode,” 2005 IEEE International Conference on Communications(ICC), Vol. 5, pp. 3422- 3426 (2005).
[12] Georgiadis, L., Guerin, R., and Parekh, A., “Optimal Multiplexing on a Single Link: Delay and Buffer Requirements,” IEEE INFOCOM 94, Vol. 2, pp. 524-532 (1994).
[13] Chen, J. H., Wang, C. C., Tsai, C. D., Chang, C. W., Liu, S. S., Guo, J. H., Lien, W. J., Sum, J. H., and Hung, C. H., “The Design and Implementation of WiMAX Module for ns-2 Simulator,” Proc. of the ACM/ISCT VALUETOOLS (2006).