淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-1606201110060800
中文論文名稱 基植於IEEE 802.16m正交分頻多工多重存取系統下,一個具子通道感知的變動長度下行頻寬配置機制
英文論文名稱 A Subchannel-Aware Variable-Length Burst Scheduling Algorithm for Downlink Traffic in IEEE 802.16m OFDMA Systems
校院名稱 淡江大學
系所名稱(中) 資訊工程學系資訊網路與通訊碩士班
系所名稱(英) Master's Program in Networking and Communications, Department of Computer Science and Information Engineering
學年度 99
學期 2
出版年 100
研究生中文姓名 江致平
研究生英文姓名 Chih-Ping Chiang
學號 698420089
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2011-05-20
論文頁數 48頁
口試委員 指導教授-石貴平
委員-王三元
委員-廖文華
委員-陳弘璋
委員-石貴平
中文關鍵字 IEEE 802.16m  排程  資源配置  正交分頻多工多重存取 
英文關鍵字 IEEE 802.16m  Scheduling  Resource Allocation  OFDMA 
學科別分類 學科別應用科學資訊工程
中文摘要 本論文考量在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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2016-06-29公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信