本論文考量在IEEE 802.16m OFDMA Frame架構下，提出一個Downlink頻寬管理機制來分配與規劃Downlink AAI Subframe中Burst的Subchannel 與OFDMA Symbol Time，此機制之基本概念在於針對不同使用者，配置可支援較高傳送速率的Subchannel藉以提升網路的整體傳輸效能。由於不當地分配Subchannel與OFDMA Symbol Time會造成Downlink無線資源利用率下降與Downlink AAI Subframe嚴重外部碎裂與內部碎裂，進而降低網路整體執行效能。為了解決上述之問題，本論文針對Downlink頻寬之分配與排程，提出一Subchannel-Aware Variable-Length Burst Scheduling (VLBS) Algorithm調整與分配每個排程的Burst之Subchannel位置與大小，透過適當的Subchannel配置與安排，能夠提升網路整體執行效能與增加Subchannel利用率，並能夠讓Downlink AAI Subframe中的可用資源大幅度增加。由實驗結果發現，ABS經由演算法可以有效地降低內部碎裂及外部碎裂之問題發生，提昇Downlink AAI Subframe的利用率。進而增加Downlink Subframe的產能，而且也真的提高了網路傳輸的效能。

Burst is an atomic bandwidth allocation unit in IEEE 802.16m OFDMA system. Each burst is composed of subchannels and OFDMA symbol time. This paper investigates the downlink burst allocation problem (BAP) in IEEE 802.16 OFDMA systems. In order to solve this problem, this paper proposes a subchannel-aware Variable-Length Burst Scheduling (VLBS) algorithm for throughput gains and control overhead alleviations, to schedule the position of each burst based on the rectangular mapping constraint. VLBS contains two vital schemes, including the burst allocation scheme and the burst compression scheme. The burst allocation scheme is used to schedule the position of each burst and to adjust the shape of each burst in the downlink AAI subframe. Through the burst allocation scheme, the wasted LRU caused by the external fragmentation problem (EFP) can be alleviated in an efficient manner. In the meanwhile, the utilization of downlink bandwidth can be improved. In order to achieve the rectangular mapping, the OFDMA slots will be wasted due to the internal fragmentation problem (IFP). With the increasing number of bursts. Therefore, the wasted OFDMA slots caused by IFP can be released for other bursts by burst fragmentation and the A-MAP control overhead also be reduced through burst packing. Since the A-MAP message is transmitted with the most robust burst profile, the bursts are transmitted in order of decreasing robustness. This paper is the first one to consider this transmission characteristic in the OFDMA system. The simulation results highlight that VLBS outperforms other related approaches in the throughput, the satisfaction ratio, and the downlink utilization ratio.

Table of Contents
1	Introducation	1
2	Preliminaries	4
2.1	Frame Structure	4
2.2	Burst Allocation Constraints	6
3	Problem Statement	7
3.1     Internal Fragmentation Problem  7
3.2	External Fragmentation Problem	9
3.3	Advanced-MAP Control Overhead	10
4	Related work	11
4.1	Raster Algorithm	11
4.2	Bucket Algorithm	12
4.3	SDRA Algorithm	13
5	A Subchannel-Aware Variable-Length Burst Scheduling(VLBS) Algorithm	14
5.1	Burst Observations	15
5.1.1	Burst Full Conflict	16
5.1.2	Burst Partial Conflict	16
5.1.3	Burst Conflict-Free	17
5.2	Burst Allocation Scheme (BAS)	18
5.2.1	Construction Conflict-Free Graph	18
5.2.2	Calculate Endpoint Distance	19
5.3	Burst Compression Scheme(BCS)	24
5.3.1	Burst Compression Scheme(BCS) Flow	25
6	Performance Evaluation	31
6.1	Simulation Parameters	31
6.2	Network throughput	32
6.3	Frame Average Utilization Ratio	34
6.4	Service Ratio	35
7	Conclusions	36
8	References	37
9       Appendix – English Paper  43

                   List of Figures
Figure 1、IEEE 802.16m Frame Structure 。	2
Figure 2、IEEE 802.16m Basic Frame Architecture。	5
Figure 3、Default TTI轉換為Long TTI內部碎裂問題。	7
Figure 4、外部碎裂問題。	9
Figure 5、Raster配置方式。	11
Figure 6、Bucket配置方式。	12
Figure 7、SDRA演算法示意圖。	13
Figure 8、Cross-layer scheduling algorithm。	14
Figure 9、Burst在Frame配置關係。	15
Figure 10、Burst Partial Conflict。	16
Figure 11、Burst Conflict-Free。	17
Figure 12、Subchannel Conflict-Free Graph。	18
Figure 13、Endpoint距離差距計算。	19
Figure 14、Subchannel Conflict-Free情況。	20
Figure 15、Burst Set第一組挑選步驟。	21
Figure 16、Burst Set第一組挑選結果。	22
Figure 17、Long TTI擠壓調整之判斷。	27
Figure  18、A-MAP宣告Burst位置。	29
Figure  19、Network Throughput。	32
Figure  20、Frame Average Utilization Ratio。	34
Figure  21、Service Ratio。	35


                   List of Tables
Table  1、調變可承載的資料量。	22
Table  2、實驗模擬參數設定。	31

[1]	IEEE Draft Std. P802.16TM-2009”IEEE Draft Standard for Local and Metropolitan Area Networks -Part 16: Air Interface for Broadband Wireless Access Systems”, IEEE Std.,29 May, 2009.
[2]	IEEE Draft Std.P802.16m D12,”IEEE RAFT Amendment to IEEE Standard for Local and metropolitan area Networks-Air Interface for Fixed and Mobile Broadband Wireless Access Systems”, IEEE Std., Apr.,2010.
[3]	A.Bacioccola,C.Cicconetti,C.Eklund,L.Lenzini,Li,E.Mingozzi” IEEE 802.16: History, status and future trends” Comput.Commun., vol. 33, no. 2, pp. 113-123, 2010.
[4]	S. A. Filin, S. N. Moiseev, and M. S. Kondakov, “Fast and Efficient QoS-guaranteed Adaptive Transmission Algorithm in the Mobile WiMAX System,” IEEE Transactions on Vehicular Technology (TVT), vol. 57, no. 6, pp. 3477–3487, Nov. 2008.
[5]	Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, “Two-dimensional Mapping for Wireless  OFDMA  Systems,” IEEE Transactions on Broadcasting, vol. 52, no. 3, pp. 388–396, Sep. 2006.
[6]	X. Zhu, J. Huo, X. Xu, C. Xu, and W. Ding, “QoS-Guaranteed Scheduling and Resource Allocation Algorithm for IEEE 802.16 OFDMA System,” in Proceedings of the IEEE International Conference on Communications (ICC), 2008, pp. 3463–3468.
[7]	T. Ohseki, M. Morita, and T. Inoue, “Burst Construction and Packet Scheme for OFDMA Downlinks in IEEE 802.16 Systems,” in Proceeding of the IEEE Global Telecommunications Conference (GLOBECOM), 2007, pp. 4307 – 4311.
[8]	A. Erta, C. Cicconetti, and L. Lenzini, “A Downlink Data Region Allocation Algorithm for IEEE 802.16e OFDMA,” in Proceedings of the International Conference on Information, Communications and Signal Processing (ICICS), 2007, pp. 1–5.
[9]	A. Israeli, D. Rawitz, O. Sharon, “On the Complexity of Sequential Rectangle Placement,” Information and Computation, vol. 206, no. 11, Nov. 2008, pp. 1334-1345.
[10]	T. Ohseki, M. Morita, and T. Inoue, “Burst Construction and Packet Scheme for OFDMA Downlinks in IEEE 802.16 Systems,” in Proceeding of the IEEE Global Telecommunications Conference (GLOBECOM), 2007, pp. 4307 – 4311.
[11]	A. Erta, C. Cicconetti, and L. Lenzini, “A Downlink Data Region Allocation Algorithm for IEEE 802.16e OFDMA,” in Proceedings of the International Conference on Information, Communications and Signal Processing (ICICS), 2007, pp. 1–5.
[12]	Y.-N. Lin, C.-W. Wu, Y.-D. Lin, and Y.-C. Lai, “A Latency and Modulation Aware Bandwidth Allocation Algorithm for WiMAX Base Stations,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2008, pp. 1408–1413.
[13]	B. Webb, “Broadband Fixed Wireless Accessas a Key Component of the Future Integrated Communications Environment,” IEEE Communications Magazine, vol. 39, no. 9, pp. 115–121, Sep. 2002.
[14]	T. Yahiya, A.-L.Beylot, and G. Pujolle, “Cross-Layer Multiservice Scheduling for Mobile WiMAx Systems,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2008, pp. 1531–1535.
[15]	X. Zhu, J. Huo, S. Zhao, Z. Zeng, and W. Ding, “An Adaptive Resource Allocation Scheme in OFDMA based Multiservice WiMAX Systems,” in Proceedings of the IEEE International Conference on Advanced Communication Technology (ICACT), 2008, pp. 593–597.
[16]	J. Xin, Z. Jihua,H. Jinlong,S. Jinglin,S. Yi, “An Efficient Downlink Data Mapping Algorithm for IEEE802.16e OFDMA Systems,”in Proceedings of theGlobal Telecommunications Conference(GLOBECOM), 2008, pp.1-5.
[17]	F. K. Miyazawa and Y. Wakabayashi, “An algorithm for the threedimensional packingproblem with asymptotic performance analysis,“ Algorithmica, vol. 18, pp. 122–144, 1997. 
[18]	A. Lodi, S. Martello, and M. Monaci, “Two-dimensional packing problems:a survey,” European Journal of Operational Research, vol. 141,pp. 241–252, 2002
[19]	Sarigiannidis, P.G.; Papadimitriou, G.I.; Nicopolitidis, P.; Obaidat, M.S.; Pomportsis, A.S.; “A Novel Adaptive Mapping Scheme for IEEE 802.16 Mobile Downlink Framing,”in Proceedings of theGlobal Telecommunications Conference(GLOBECOM), 2010, pp.1-5.
[20]	Andrews, M.; Zhang, L.; “Scheduling Algorithms for Multicarrier Wireless Data Systems” IEEE Transactions on Networking, vol. 19, no. 2, pp. 447–455, Sep. 2011.
[21]	Wen-Ching Chung; Li-Chun Wang; Chung-Ju Chang;; “A Low-Complexity Beamforming-Based Scheduling for Downlink OFDMA/SDMA Systems with Multimedia Traffic” in Proceedings of theGlobal Telecommunications Conference(GLOBECOM), 2009, pp.1-5.
[22]	Jia-Ming Liang.; Jia-Ming Liang.; You-Chiun Wang ; You-Chiun Wang; “A Cross-Layer Framework for Overhead Reduction, Traffic Scheduling, and Burst Allocation in IEEE 802.16 OFDMA Networks” IEEE Transactions onVehicular Technology, vol. 60, no. 4, pp. 1740–1755, 2011.
[23]	Shiann Tsong Sheu; Ming Huei Tsai; Tsung-Yu Tsai; Yi-Hsueh Tsai; “Condensed Downlink MAP Structures for IEEE 802.16e Wireless Metropolitan Area Networks (MANs)” in Proceedings of theVehicular Technology Conference (VTC 2010-Spring), 2010, pp.1-5.
[24]	Galati G., L.; Lopez-Perez, D.; Reggiani, L.; Dossi, L.; Juttner, A.; Jie Zhangi; “Two-dimensional radio resource allocation algorithms with contiguity constraint for IEEE 802.16e systems” in Proceedings of thePersonal, Indoor and Mobile Radio Communications(PIMRC), 2009, pp.2224-2229.
[25]	Desset, C.; de Lima Filho, E.B.; Lenoir, G.;  “WiMAX Downlink OFDMA Burst Placement for Optimized Receiver Duty-Cycling” in Proceedings of the IEEE International Conference on Communications (ICC), 2007, pp. 5149 - 5154.
[26]	Cohen, R.; Katzir, L.;“Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Downlink Scheduling”IEEE Transactions onNetworking, vol. 18, no. 1, pp. 15-26,2010.
[27]	Cohen, R.; Katzir, L.;“Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Scheduling” IEEE Transactions onNetworking, vol. 18, no. 1, pp. 15-26,2008
[28]	Cicconetti, C.; Lenzini, L.; Lodi, A.; Martello, S.; Mingozzi, E.; Monaci, M.;“Efficient Two-dimensional Data Allocation in IEEE 802.16 OFDMA” in Proceedings of theInternational Conference on Computer Communications(INFOCOM), 2010, pp.1-9.
[29]	Chakchai So-In; Jain, R.; Al Tamimi, A.-K.;“OCSA: An algorithm for burst mapping in IEEE 802.16e mobile WiMAX networks” in Proceedings of theAsia-Pacific Conference on Communications (APCC), 2009, pp.25-58.
[30]	Chakchai So-In; Jain, R.; Al Tamimi, A.-K.;“eOCSA: An algorithm for burst mapping with strict QoS requirements in IEEE 802.16e Mobile WiMAX networks” in Proceedings of theInternational Federation for Information Processing (IFIP), 2009, pp.1-5.