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

Burst is an atomic bandwidth allocation unit in IEEE 802.16 OFDMA system. Each burst is composed of subchannels and symbol time. This paper investigates the downlink burst scheduling problem (BSP) in IEEE 802.16 OFDMA systems. In order to solve this problem, this paper proposes a subchannel-aware burst fragmentation, packing and scheduling (BFPS) algorithm for throughput gains and control overhead alleviations, to schedule the position of each burst based on the rectangular mapping constraint. BFPS contains three vital schemes, including the burst allocation scheme, the burst fragmentation and packing scheme and the burst swapping 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 subframe. Through the burst allocation scheme, the wasted OFDMA slots 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, the DL-MAP control overhead also degrades the available downlink bandwidth.  Therefore, the wasted OFDMA slots caused by IFP can be released for other bursts by burst fragmentation and the DL-MAP control overhead also be reduced through burst packing.  Since the DL-MAP message is transmitted with the most robust burst profile, the bursts are transmitted in order of decreasing robustness. Therefore, swapping the scheduled bursts in the final scheme can satisfy the transmission characteristic in the OFDMA system. This paper is the first one to consider this transmission characteristic in the OFDMA system. The simulation results highlight that BFPS outperforms other related approaches in the throughput, the DL-MAP IE efficiency, the satisfaction ratio, and the downlink utilization ratio.

List of figures	V
        List of tables	VII
1	Introduction	1
2	Preliminaries	4
2.1	IEEE 802.16 OFDMA Frame Structure	4
2.2	Burst Allocation Problem	6
2.3	Slots Wastage Caused by the Inappropriate Burst Allocations	9
2.4	Related Work	13
3	Burst Fragmentation, Packing and Scheduling(BFPS) Algorithm	18
3.1	Burst Allocation Scheme	19
3.2	Burst Fragmentation and Packing Scheme	27
3.3	Block Swapping (option)	34
4	Performance Evaluation	35
5	Conclusions	46
Reference	47
附錄—英文論文	49

List of figures
Figure 1. IEEE 802.16 OFDMA frame架構。	2
Figure 2. MS在不同的Subchannel上能使用的調變等級。	6
Figure 3. MS在不同Subchannel上可使用的調變等級示意圖。	7
Figure 4. Burst配置時跨多個調變時所產生的影響。	7
Figure 5. 規格書所建議的傳輸調變順序。	8
Figure 6. 不當地分配Subchannels與Symbol Time可能衍生的問題。	12
Figure 7. Raster burst配置方式。	14
Figure 8. Fixed burst配置方式。	14
Figure 9. T. Ohseki[12]等作者所提出的作法。	15
Figure 10. A. Erta[7]等作者提出SDRA演算法。	16
Figure 11. Cross-layer scheduling algorithm。	18
Figure 12. Burst conflict。	19
Figure 13. Full conflict、non-conflict與partial conflict配置後所產生的影響。	20
Figure 14. Subchannel conflict graph (1) 。	22
Figure 15. Subchannel conflict graph (2) 。	23
Figure 16.可用區域示意圖。	24
Figure 17. Burst allocation (1) 。	25
Figure 18. Burst allocation (2) 。	27
Figure 19. IFP資源釋放示意圖。	29
Figure 20. Block示意圖。	30
Figure 21.切割判斷示意圖。	30
Figure 22. Gap移動終止示意圖。	31
Figure 23.上下Burst合併。	31
Figure 24.左右Burst合併。	32
Figure 25. Burst合併序列。	33
Figure 26. Burst合併結果。	33
Figure 27. Non-robust order。	34
Figure 28. Robust order。	34
Figure 29. Network throughput。	36
Figure 30. IE efficiency。	37
Figure 31. Service ratio。	38
Figure 32. Average utilization ratio。	39
Figure 33. Average Delay。	40
Figure 34. 64QAM調變佔用25%時的Throughput。	40
Figure 35. 64QAM調變佔用25%時的IE efficiency。	41
Figure 36. 64QAM調變佔用25%時的Service Ratio。	41
Figure 37. 64QAM調變佔用25%時的Average Utilization Ratio。	42
Figure 38. 64QAM調變佔用25%時的Average Delay。	42
Figure 39. 64QAM調變佔用75%時的Throughput。	43
Figure 40. 64QAM調變佔用75%時的IE efficiency。	43
Figure 41. 64QAM調變佔用75%時的Service Ratio。	44
Figure 42. 64QAM調變佔用75%時的Average Delay。	44
Figure 43. 64QAM調變佔用75%時的Average Utilization Ratio。	45

List of tables
Table 1. 實驗相關參數。	35

[1]	IEEE Draft Std. P802.16 Rev2/D9a, ”IEEE Draft Standard for Local and Metropolitan Area Networks -Part 16: Air Interface for Broadband Wireless Access Systems”, IEEE Std., May, 2009.
[2]	T. Wang, H. Feng, and B. Hu, “Two-Dimensional Resource Allocation for OFDMA System,” in Proceedings of the IEEE International Conference on Communications (ICC), 2008, pp. 1 – 5.
[3]	A. Biagioni, R. Fantacci, D. Marabissi, and  D. Tarchi, “Adaptive Subcarrier Allocation Schemes for Wireless OFDMA Systems in WiMAX Networks,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 27, no. 2, pp. 217–225, Feb.,2009.
[4]	H. Bolcskei, A.J. Paulraj, K.V.S. Hari, R.U. Nabar and W.W. Lu, “Fixed Broadband Wireless Access: State of the Art, Challenges, and Future Directions,” IEEE Communications Magazine, vol. 39, no. 1, pp. 100–108, Jan. 2001.
[5]	C. So-In, R. Jain, and A.-K. Tamimi, “Scheduling in IEEE 802.16e Mobile WiMAX Networks: Key Issues and a Survey,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 27, no. 2, pp. 156–171, Feb., 2009.
[6]	S.-I. Chakchai, J. Raj, and A.-K. A. Tamimi, “eOCSA: An Algorithm for Burst. Mapping with Strict QoS Requirements in IEEE 802.16e Mobile WiMAX,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2008, pp. 1–5.
[7]	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.
[8]	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.
[9]	H. Gowda, R. Lakshmaiah, M. Kaur, C. Mohanram, M. Singh, and S. Dongre, “A Slot Allocation Mechanism for Diverse QoS Types in OFDMA Based IEEE 802.16e Systems,” in Proceedings of the IEEE International Conference on Advanced Communication Technology (ICACT), 2007, pp. 13–17.
[10]	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.
[11]	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.
[12]	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.
[13]	T. Ali-Yahiya and a. G. P. A.-L.Beylot, “Radio Resource Allocation in Mobile WiMax Networks using Service Flows,” in Proceedings of the IEEE Internatonal Symposium on Personal Indoor and Mobile Radio Communications (PIRMC), 2007, pp. 1-5.
[14]	L. Wan, W. Ma, and Z. Guo, “A Cross-layer Packet Scheduling and Subchannel Allocation Scheme in 802.16e OFDMA System,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), 2007, pp. 1865–1870.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	J. Xin, Z. Jihua, H. Jinlong, S. Jinglin, S. Yi, “An Efficient Downlink Data Mapping Algorithm for IEEE802.16e OFDMA Systems,” in Proceedings of the Global Telecommunications Conference (GLOBECOM), 2008, pp.1-5.