許多學者提出各種IEEE 802.16 正交分頻多工存取(OFDMA)系統之二維頻寬分配演算法來提升IEEE 802.16網路吞吐值(throughput)。然而這些演算法未遵循IEEE 802.16標準，導致承受較差的吞吐值，甚至無法適用於IEEE 802.16網路。本論文因此提出最佳角落啟發式演算法(Best Corner Oriented, BCO)和最佳區塊啟發式演算法(Best Block Oriented, BBO)，寄望能在IEEE 802.16標準的限制下，且同時考慮外部破碎(external fragment)、內部破碎(internal fragment)、以及子頻道異質性(subchannel diversity)等三個議題，以提高IEEE 802.16網路的吞吐值。BCO主要透過處理外部破碎來提升吞吐值，亦即將突衝(Burst)放置於可用頻寬的角落以確保可用頻寬的連續性，進而讓後續尚未建置的突衝能充分利用尚未使用的頻寬資源。BBO偏重於尋找較佳調變編碼機制來提高吞吐值，亦即計算各種可用的子頻道(subchannel)組合，並將突衝放置在能提供最高吞吐值之子頻道組合。同時，當所需傳送的資料量獲得滿足的前提下，BCO與BBO皆會縮小突衝的面積以降低內部破碎，進而提昇頻寬的使用率。模擬數據顯示BBO與BCO分別擁有傳統上行鏈結(uplink)頻寬分配演算法的2倍與1.5倍的吞吐量，且BBO與BCO擁有傳統下行鏈結(downlink)頻寬分配演算法的9倍吞吐量。需注意的是，BBO需付出較高時間複雜度來達到高於BCO的吞吐量。

Several two-dimensional bandwidth allocation algorithms in IEEE 802.16 OFDMA system were proposed. These algorithms, however, did not meet the bandwidth allocation specification described in the IEEE 802.16 standards, and they therefore suffer inferior throughput or are furthermore inappropriate to be applied. This thesis therefore proposes two heuristic algorithms, Best Corner Oriented (BCO) and Best Block Oriented (BBO), to comply with the IEEE 802.16 specification and provide high throughput in IEEE 802.16 networks considering the external fragmentation, internal fragmentation, and subchannel diversity. BCO mainly intends to avoid external fragmentation by constructing each burst from one of the two ending slots of the free bandwidth area to ensure that all free slots are within a continuous area. BBO mainly intends to use a better modulation coding scheme (MCS), that is, it places each burst in its best quality subchannels to adopt a better MCS. To avoid internal fragmentation, both BCO and BBO shrink the area measurement of the burst if the requested bandwidth is satisfied, so that unused slots internal to this burst can be used by other bursts. The simulation results under a heavy load indicate that BBO and BCO achieve 2 and 1.5 times, respectively, the throughput achieved by the conventional algorithm in the uplink. For the downlink, both algorithms achieve 9 times the throughput achieved by the conventional algorithm. Notably, the superior performance of BBO, comparing with that of BCO, is achieved at the expense of increased time complexity.

[1] Q. Lu and M. Ma, Group mobility support in mobile WiMAX networks, Journal of Network and Computer Applications, vol. 34, no. 4, July 2011, pp. 1272–1282.
[2] M. C. Batistatos, G. V. Tsoulos, and G. E. Athanasiadou, Mobile telemedicine for moving vehicle scenarios: wireless technology options and challenges, Journal of Network and Computer Applications, vol. 35, no. 3, May 2012, pp. 1140-1150.
[3] M. C. Domingo, An overview of the internet of underwater things, Journal of Network and Computer Applications, vol. 35, July 2012, pp. 1879-1980.
[4] IEEE P802.16Rev2/D1, DRAFT standard for local and metropolitan area networks—part 16: air interface for broadband wireless access systems, IEEE 802.16 Working Group, 2007.
[5] M. Einhaus, B. Wolz, and B. Walke, The influence of subchannel diversity on the performance of OFDMA systems based on IEEE 802.16, Proceedings of IEEE International Conference on Circuits and Systems for Communications, May 2008, pp. 20-24.
[6] Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, Two-dimensional mapping for wireless OFDMA systems, IEEE Transactions on Broadcasting, vol. 52, no. 3, 2006, pp. 388-396.
[7] S.-T. Sheu, C.-C. Yang, and H.-S. Chang, A dynamic frequency allocation scheme for IEEE 802.16 OFDMA-based WMANs using Hungary algorithm, Proceedings of Emerging Direction in Embedded and Ubiquitous Computing, Dec. 2007, pp. 205-214.
[8] I. Toufik and R. Knopp, Channel allocation algorithms for multi-carrier systems, Proceedings of IEEE 60th Vehicular Technology Conference, vol. 2, Sept. 2004, pp. 1129-1133.
[9] Y. Chen, S. H. Shon, S.-J. Yoo, and J. M. Kim, Dynamic frequency selection in OFDMA, Proceedings of The 8th International Conference on Advanced Communication Technology, vol. 1, Feb. 2006, pp. 574-578.
[10] S. Najeh, H. Besbes, and A. Bouallegue, Greedy algorithm for dynamic resource allocation in downlink of OFDMA system, Proceedings of The 2nd International Symposium on Wireless Communication Systems, Sept. 2005, pp. 475-479.
[11] D. Kivanc, G. Li, and H. Liu, Computationally efficient bandwidth allocation and power control for OFDMA, IEEE Transactions on Wireless Communications, vol. 2, no. 6, Nov. 2003, pp. 1150-1158.
[12] M. Ergen, S. Coleri, and P. Varaiya, QoS aware adaptive resource allocation techniques for fair scheduling in OFDMA based broadband wireless access systems, IEEE Transactions on Broadcasting, vol. 49, no. 4, Dec. 2003, pp. 362-370.
[13] C. So-In, R. Jain, and A.-K. Al Tamimi, eOCSA: an algorithm for burst mapping with strict QoS requirements in IEEE 802.16e mobile WiMAX networks, Proceedings of IFIP Wireless Days Conference, Dec. 2009, pp. 1-5.
[14] T. Wang, H. Feng, and B. Hu, Two-dimensional resource allocation for OFDMA system, Proceedings of IEEE International Conference on Communications Workshops, May 2008, pp. 1-5.
[15] K.-P. Shih, H.-C. Chen, C.-T. Chiang, and T.-H. Hsieh, Channel-aware subchannel renumbering and downlink burst allocation for IEEE 802.16 OFDMA systems, Proceedings of IEEE Wireless Communications and Networking Conference, April 2010, pp. 1-6.
[16] Y.-C. Lai and Y.-H. Chen, A channel quality and QoS aware bandwidth allocation algorithm for IEEE 802.16 base stations, Proceedings of the 22nd International Conference on Advanced Information Networking and Applications, March 2008, pp. 472-479.
[17] E. Hopper and B. C. H. Turton, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, vol. 128, 2001, pp. 34-57.
[18] D. Pisinger and M. Sigurd, The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, vol. 2, 2005, pp. 154-167.
[19] J. Egeblad and D. Pisinger, Heuristic approaches for the two- and three-dimensional knapsack packing problem, Computers & Operations Research, vol. 36, 2009, pp. 1026-1049
[20] P. G. Sarigiannidis, M. Louta, D. G. Stratogiannis, and G. I. Tsiropoulos, Towards a QoS-aware IEEE 802.16 downlink sub-frame mapping scheme, Proceedings of IEEE GLOBECOM Workshops, Dec. 2010, pp. 1243-1247.
[21] A. Erta, C. Cicconetti, and L. Lenzini, A downlink data region allocation algorithm for IEEE 802.16e OFDMA, Proceedings of the 6th International Conference on Information, Communications & Signal Processing, Dec. 2007, pp. 1-5.
[22] T. Ohseki, M. Morita, and T. Inoue, Burst construction and packet mapping scheme for OFDMA downlinks in IEEE 802.16 systems, Proceedings of IEEE Global Telecommunications Conference, Nov. 2007, pp. 4307-4311.
[23] T.-H. Lee, C.-H. Liu, J. Yau, and Yaw-Wen Kuo, Maximum rectangle-based down-link burst allocation algorithm for WiMAX systems, Proceedings of 2011 IEEE Region 10 Conference, Nov. 2011, pp. 530-534.
[24] C. Cicconetti, L. Lenzini, A. Lodi, S. Martello, E. Mingozzi, and M. Monaci, Efficient two-dimensional data allocation in IEEE 802.16 OFDMA, Proceedings of IEEE INFOCOM, March 2010, pp. 1-9.
[25] O. M. Eshanta, M. Ismail, and K. Jumari, OBBP: an efficient burst packing algorithm for IEEE802.16e systems, ISRN Communications and Networking, article ID 734297, 2011. (doi:10.5402/2011/734297)
[26] J.-M. Liang, J.-J. Chen, Y.-C. Wang, and Y.-C. Tseng, A cross-Layer framework for overhead reduction, traffic scheduling, and burst allocation in IEEE 802.16 OFDMA networks, IEEE Transaction on Vehicular Technology, vol. 60, no. 4, May 2011, pp. 1740-1755.
[27] J.-Y. Baek and Y.-J. Suh, Heuristic burst construction algorithm for improving downlink capacity in IEEE 802.16 OFDMA systems, IEEE Transactions on Mobile Computing, vol.11, no.1, Jan. 2012, pp.155-168.
[28] J. Vanderpypen and L. Schumacher, Treemap-based burst mapping algorithm for downlink mobile WiMAX systems, Proceedings of 2011 IEEE Vehicular Technology Conference, Sept. 2011, pp. 1-5.
[29] H.-C. Chen, K.-P. Shih, C.-T. Chiang, and C.-L. Chen, A subchannel-aware burst fragmentation, packing and scheduling (BFPS) algorithm for downlink traffic in IEEE 802.16 OFDMA systems, Proceedings of 2011 7th International Wireless Communications and Mobile Computing Conference (IWCMC), 2011, pp. 1141-1146.
[30] A. Nusairat and X. Li, WiMAX/OFDMA burst scheduling algorithm to maximize scheduled data, IEEE Transactions on Mobile Computing, vol. 11, no. 11, 2012, pp. 1692-1705.
[31] Yuan-Cheng Lai and Yen-Hung Chen, Designing and implementing an IEEE 802.16 network simulator for performance evaluation of bandwidth allocation algorithms, Proceedings of High Performance Computing and Communications (HPCC), South Korea, June 2009, pp. 432-437.