近年來，以IEEE 802.16標準為基礎的寬頻無線存取技術，儼然成為目前無線都會網路發展的主要趨勢。綜觀IEEE 802.16的系統，提供並滿足使用者不同層級的QoS是標準制訂最主要的目標。一般來說，為達到系統資源的最有效利用、服務最多用戶個數以及提供有等級差別的服務品質保證，嚴謹且有效的無線資源管理是非常重要的。在無線資源管理的議題當中，又以排程機制的設計為最主要的部分，有鑑於此，因此本論文針對IEEE 802.16網路，提出一個可適性排程演算法，稱為APS (Adaptive Priority-based Scheduling)。主要概念係針對網路中不同類型的Connection，依據服務品質的需求，動態調整連線之間享有頻寬使用權的優先順序。以達到服務品質的保證、動態分配Downlink和Uplink的頻寬, 及避免較低服務等級的Connection出現starvation的情況。
除此之外，於模擬結果中發現，將ASP與具代表性的文獻相比較後，發現ASP的確能在Average Throughput和Average Delay中獲得較佳的Performance。

Supporting QoS guarantees for diverse multimedia services is the main concern in IEEE 802.16 networks. The scheduling scheme to satisfy QoS requirements become more important issues in IEEE 802.16 networks. Therefore we propose a scheduling scheme in the thesis, called Adaptive Priority-based Scheduling (APS) scheme for provision of QoS guarantee in IEEE 802.16 networks.
APS comprises two major components, including priority assignment and resource allocation. Basically, five service types in APS are reasonably classified into the Delay-Constrained Service (UGS, ertPS, and rtPS) and the Throughput-Guaranteed Service (nrtPS and BE) categories, primarily depending on their QoS requirements. In priority assignment, each connection in the individual category is assigned a suitable priority by using a well-designed rule, based on the connection’s QoS parameters. Additionally, in order for starvation prevention, the priority of the connection with low priority in each category will be dynamically promoted. In resource allocation, the maximal and the minimal bandwidth requirements are first calculated. After comparing such bandwidth requirements and the total available bandwidth of BS, we consider the priority of a connection, and then make use of the weight-based proportional fairness scheme to achieve resource allocation of each connection.
Overall, APS is not only completely compatible with DFPQ scheme and SCSA scheme, but also achieve QoS satisfaction as well as starvation prevention. Simulation results show that APS outperforms the representative scheduling approaches in both average throughput and average delay.

第一章 緒論	- 1 -
1.1 導論	- 1 -
1.2 研究動機與目標	- 1 -
1.3 研究方法簡介	- 3 -
1.4 論文架構	- 3 -
第二章 相關技術與研究	- 5 -
2.1  IEEE 802.16 技術介紹	- 5 -
2.1.1 前言	- 5 -
2.1.2  IEEE 802.16標準的特性	- 6 -
2.1.3 實體層(PHY layer)介紹	- 8 -
2.1.4 媒體存取控制層(MAC layer)介紹	- 10 -
2.1.5 IEEE 802.16 QoS架構	- 12 -
2.2 相關研究	- 16 -
2.2.1 服務類型為主(Service-based)	- 17 -
2.2.2 連線為主(Connection-based)	- 23 -
2.2.3 小結	- 25 -
第三章 優先權為主之可適性排程機制	- 27 -
3.1 前言	- 27 -
3.2 系統架構	- 27 -
3.3 網路環境以及基本概念簡介	- 29 -
3.3.1 網路環境與假設	- 29 -
3.3.2  APS基本概念	- 30 -
3.3.3 符號定義	- 32 -
3.4 優先權的分派(PRIORITY ASSIGNMENT)	- 33 -
3.4.1 前言	- 33 -
3.4.2 連線的排序(Connection Ranking)	- 34 -
3.4.3 優先權的上升(Priority Elevation)	- 50 -
3.4.4 小結	- 56 -
3.5 資源的分配(RESOURCE ALLOCATION)	- 57 -
3.5.1 前言	- 57 -
3.5.2 頻寬需求的量化	- 58 -
3.5.3 頻寬需求的分配	- 72 -
3.5.4 小結	- 80 -
第四章 模擬結果探討	- 82 -
4.1 前言	- 82 -
4.2 模擬參數與場景介紹	- 82 -
4.3 模擬結果與比較分析	- 86 -
第五章 結論與未來研究方向	- 98 -
5.1 結論	- 98 -
5.2 未來研究方向	- 98 -
參考文獻	- 99 -
附錄一 可適性排程機制之各級演算法	- 105 -
附錄二 PUBLICATIONS LIST	- 121 -
附錄三 論文發表-WASN 2007	- 122 -
附錄四 論文發表-APWCS 2008	- 133 -
附錄五 論文發表-TAIA 2008	- 136 -
附錄六 英文稿	- 146 -
 
圖目錄
圖 1 分時多工架構圖	- 7 -
圖 2 IEEE 802.16 通訊協定層架構	- 8 -
圖 3 OFDMA 訊框結構	- 9 -
圖 4 PMP架構	- 11 -
圖 5 Mesh架構	- 11 -
圖 6兩階層式排程架構	- 19 -
圖 7 DFPQ排程架構	- 20 -
圖 8 PDFPQ排程架構	- 21 -
圖 9 IEEE 802.16系統運作示意圖	- 28 -
圖 10 TDD Frame架構圖	- 29 -
圖 11 Dynamic Priority觀念示意圖	- 31 -
圖 12 APS架構圖	- 32 -
圖 13優先權分派的架構圖	- 34 -
圖 14封包的到達時間、等待時間與間隔時間圖例	- 37 -
圖 15需求的提出時間、等待時間與剩餘等待時間圖例	- 42 -
圖 16資源分配架構圖	- 57 -
圖 17順位示意圖	- 78 -
圖 18 資源分配流程圖	- 81 -
圖 19 模擬場景示意圖	- 83 -
圖 20 UGS連線的平均Throughput (DL)	- 87 -
圖 21 UGS連線的平均Delay(DL)	- 87 -
圖 22 ERT-VR連線的平均Throughput (DL)	- 88 -
圖 23 ERT-VR連線的平均Delay(DL)	- 89 -
圖 24 RT-VR連線的平均Throughput (DL)	- 90 -
圖 25 RT-VR連線的平均Delay(DL)	- 90 -
圖 26 RT-VR連線的平均Throughput (UL)	- 91 -
圖 27 RT-VR連線的平均Delay(UL)	- 91 -
圖 28 NRT-VR連線的平均Throughput (DL)	- 93 -
圖 29 NRT-VR連線的平均Delay(DL)	- 93 -
圖 30 NRT-VR連線的平均Throughput (UL)	- 94 -
圖 31 NRT-VR連線的平均Delay(UL)	- 94 -
圖 32 BE連線的平均Throughput (DL)	- 95 -
圖 33 BE連線的平均Delay(DL)	- 96 -
圖 34 BE連線的平均Throughput (UL)	- 97 -
圖 35 BE連線的平均Delay(DL)	- 97 -
 
表目錄
表 1五種排程服務的QoS參數表	- 14 -
表 2 QoS 參數符號定義表	- 32 -
表 3 DCS連線的優先順序表	- 76 -
表 4 模擬連線號碼(a)	- 83 -
表 5 模擬連線號碼(b)	- 84 -
表 6 QoS參數表	- 85 -

[1]	ITU Telecommunications indicators update 2006, http://www.itu.int/ITU-D/ict/statistics/
[2]	In-stat Report. Paxton. The broadband boom continues: Worldwide subscribers pass 200 million, No. IN0603199MBS, March 2006.
[3]	J. G. Andrews, A. Ghosh, and R. Muhamed, Fundamentals of WiMAX — Understanding Broadband Wireless Networking. Prentice Hall, 2007.
[4]	IEEE Standard 802.16 Working Group, IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Broadband Wireless Access Systems (P802.16Rev2/D3), Feb. 2008.
[5]	Hossam Fattah, and Cyril Leung, “An overview of scheduling algorithms in wireless multimedia networks,” IEEE Wireless Communications, vol. 9, no. 5, pp. 76–83, Oct. 2002.
[6]	Claudio Cicconetti, Luciano Lenzini, and Enzo Mingozzi, “Quality of Service Support in IEEE 802.16 Networks,” IEEE Network, vol. 20, Issue. 2, pp. 50–55, March-April. 2006.
[7]	Chingyao Huang, Hung-Hui Juan, Meng-Shiang Lin, and Chung-Ju Chang, “Radio Resource Management of Heterogeneous Services in Mobile WiMAX systems,” IEEE Wireless Communications, vol. 14, Issue. 1, pp. 20–26, Feb. 2007.
[8]	Zakhia Abichar, Yanlin Peng, and J. Morris Chang, “WiMAX: The Emergence of Wireless Broadband,” IT Professional, vol. 8, Issue 4, pp. 44–48, July-Aug. 2006.
[9]	Carl Eklund, Roger B. Marks, and Kenneth L, “IEEE Standard 802.16:A Technical Overview of the WirelessMAN™ Air Interface for Broadband Wireless Access, ” IEEE Communications Magazine, vol. 40, Issue 6, pp. 98–107, June. 2002.
[10]	Arunabha Ghosh, David R and Jeffrey G, “Broadband Wireless Access with WiMax/8O2.16: Current Performance Benchmarks and Future Potential,” IEEE Communications Magazine, vol. 43, Issue 2, pp. 129–136, Feb. 2005.
[11]	Qiang Ni, Vinel A, Yang Xiao, Turlikov A.and Tao Jiang, “WIRELESS BROADBAND ACCESS: WIMAX AND BEYOND - Investigation of Bandwidth Request Mechanisms under Point-to-Multipoint Mode of WiMAX Networks,” IEEE Communications Magazine, vol. 45, Issue 5, pp. 132–138, May. 2007.
[12]	Yaxin CAC and Victor O. K. Li, “Scheduling Algorithms in Broad-Band Wireless Networks,” IEEE Proceedings of The IEEE, vol. 89, NO. 1, pp. 76–87, Jan. 2001.
[13]	Hawa, M.and Petr, D.W.,”Quality of service scheduling in cable and broadband wireless access systems,” Tenth IEEE International Workshop on Quality of Service, p247-255, May. 2002.
[14]	Kitti Wongthavarawat, and Aura Ganz, “Packet Scheduling for QoS Support in IEEE 802.16 Broadband Wireless Access Systems,” International Journal of Communication Systems, vol. 16, p81-96, May. 2003.
[15]	Sun, J, Yanling Yao, and Hongfei Zhu, “Quality of Service Scheduling for 802.16 Broadband Wireless Access Systems,” IEEE Vehicular Technology Conference (VTC), May.2006, pp.1221-1225.
[16]	Jianfeng Chen, Wenhua Jiao, and Hongxi Wang, “A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode,” IEEE International Conference on Communications (ICC), May.2005. pp. 3422-3426.
[17]	Haidar Safa, Hassan Artail, Marcel Karam, Rawan Soudah, and Samar Khayat, “New Scheduling Architecture for IEEE 802.16 Wireless Metropolitan Area Network,” IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), May.2007, pp. 203-210.
[18]	Daniele Tarchi, Romano Fantacci, and Marco Bardazzi, “Quality of Service Management in IEEE 802.16 Wireless Metropolitan Area Networks,” IEEE International Conference on Communications (ICC), June.2006, pp. 1789-1794.  
[19]	Dusit Niyato, and Ekram Hossain, “Queue-Aware Uplink Bandwidth Allocation and Rate Control for Polling Service in IEEE 802.16 Broadband Wireless Networks,” IEEE Transactions on Mobile Computing, vol. 5, NO. 6, pp. 668-679, June. 2006.
[20]	Bai. Xiaofeng, Shami. Abdallah, Meerja, Khalim Amjad and Assi. Chadi; “New Distributed QoS Control Scheme for IEEE 802.16 Wireless Access Networks,” IEEE Global Telecommunications Conference (GLOBECOM), Nov. 2006. pp. 1-5.
[21]	Bai. Xiaofeng, Shami. Abdallah and Ye. Yinghua, “Robust QoS Control for Single Carrier PMP Mode IEEE 802.16 Systems,” IEEE Transactions on Mobile Computing, vol. 7, Issue 4, pp. 416-429, April. 2008.
[22]	Alexander Sayenko, Olli Alanen, Juha Karhula and Timo H¨am¨ al ¨ainen, “Ensuring the QoS Requirements in 802.16 Scheduling”, ACM international symposium on Modeling analysis and simulation of wireless and mobile systems (MSWiM), October. 2006, pp. 108-117.
[23]	Hahne, E. L., and Gallager, R. G.,. “Round Robin scheduling for fair flow control in data communication networks,” IEEE International Conference on Communications (ICC), Jun. 1986, pp. 103–107.
[24]	Nai’an Liu, Xiaohui, Li, Changxing, and Pei, Bo Yang, “Delay Character of a Novel Architecture for IEEE 802.16 Systems,” International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Dec 2005, pp. 293–296.
[25]	Georgiadis, L., Guerin, R.,and Parekh, A., “Optimal multiplexing on a single link: delay and buffer requirements,” IEEE Transactions on Information Theory vol. 43, Issue 5, pp. 1518-1535, Sep. 1997.
[26]	Qingwen Liu, Xin Wang, and Georgios B. Giannakis, “A Cross-Layer Scheduling Algorithm With QoS Support in Wireless Networks,” IEEE Transactions on Vehicular Technology, vol. 55, NO. 3, pp. 839-847, May 2006. 
[27]	Lihua Wan, Wenchao Ma, and Zihua Guo, “A Cross-layer Packet Scheduling and Subchannel Allocation Scheme in 802.16e OFDMA System,” IEEE Wireless Communications and Networking Conference (WCNC), March. 2007, pp. 1865-1870.
[28]	Jalali A, Padovani R, and Pankaj R, “Data Throughput of CDMA-HDR, a High Efficiency High Data Rate Personal Communication Wireless System,” IEEE Vehicular Technology Conference (VTC), May.2000, pp.1854-1858.
[29]	Mehri Mehrjoo, Mehrdad Dianati, Xuemin (Sherman) Shen, and Kshirasagar Naik, “Opportunistic Fair Scheduling for the Downlink of IEEE 802.16Wireless Metropolitan Area Networks,” The Third International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine), August. 2006, pp.54-67.
[30]	Mehri Mehrjoo, Xuemin (Sherman) Shen, and Kshirasagar Naik, “A Joint Channel and Queue-Aware Scheduling for IEEE 802.16 Wireless Metropolitan Area Networks,” IEEE Wireless Communications and Networking Conference (WCNC), March. 2007, pp. 1877-1885.
[31]	Haiying Julie Zhu and Roshdy H.M. Hafez, “Novel Scheduling Algorithms for Multimedia Service in OFDM Broadband Wireless Systems,” IEEE International Conference on Communications (ICC), June 2006, pp. 772-777.
[32]	Fen Hou, Pin-Han Ho, Xuemin Shen and An-Yi Chen, “A Novel QoS Scheduling Scheme in IEEE 802.16 Networks,” IEEE Wireless Communications and Networking Conference (WCNC), March 2007, pp. 2457-2462.
[33]	Wha Sook Jeon and Dong Geun Jeong, “Combined Connection Admission Control and Packet Transmission Scheduling for Mobile Internet Services”, IEEE Transactions On Vehicular Technology, vol. 55, NO. 5, pp. 1582-1593, Sep. 2006.
[34]	3GPP, Physical Layer Aspects of UTRA High Speed Downlink Packet Access (Release 4), Mar. 2001, 3G TR25.848 V4.0.0.
[35]	H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-switching Networks,” Proc. IEEE, vol. 83, Oct. 1995, pp. 1374–96.
[36]	Wang H, Li W, and Agrawal D P, “Dynamic admission control and QoS for 802.16 wireless MAN,” in IEEE Wireless Telecommunications Symposium, Apr. 2005, pp. 60–66.
[37]	Rong B, Qian Y, and Chen H, “Adaptive power allocation and call admission control in multiservice WiMAX access networks,” IEEE Wireless Communications, vol. 14, no. 1, pp. 14–19, Feb. 2007.
[38]	Cicconetti C, Erta A, Lenzini L, and. Mingozzi E,“Performance evaluation of the IEEE 802.16 MAC for QoS support,” IEEE Transactions on Mobile Computing, vol. 6, no. 1, pp. 26–38, Jan. 2007.
[39]	Dongmei Zhao, and Xuemin Shen, “Performance of Packet Voice Transmission Using IEEE 802.16 Protocol,” IEEE Wireless Communications, vol. 14, no. 1, pp. 44–51, Feb. 2007.
[40]	Jayaparvathy R, and Sureshkumar G, “Performance Evaluation of Scheduling Schemes for Fixed Broadband Wireless Access Systems,” IEEE Malaysia International Conference on Communication Networks, Nov. 2005, pp. 16–18.