隨著無線通訊技術的演進，以及一般使用者對於服務需求的增加，既有之通訊系統所能提供的資料量及服務品質逐漸不合使用者的需求。在第三代行動通訊技術發展成熟之後，符合新需求的規格也在制定當中，如IEEE標準制定團體延續WiMAX(IEEE802.16e)規格，目前正在制定中的IEEE802.16m規格；以及3GPP正在發展中的LTE(Long Term Evolution)-Advanced標準，由這兩者競逐第四代行動通訊技術規格。
就無線多重存取的技術而言，IEEE802.16m在上下行的部分皆使用正交分頻多重存取(OFDMA, Orthogonal Frequency Division Multiple Access)，而LTE在下行同樣使用OFDMA，上行則為SC-FDMA。這兩種傳輸技術皆能在同一時間上將頻率提供給不同的使用者使用，如何將頻率以及時間的資源以適當的方式分配給各個使用者成為系統設計中的一個重要課題。在本論文中，我們透過基因演算法做資源分配(Resource Allocation)，利用基因演算法的收斂性質使基地台更有效的運用傳輸資源，比較資源分配在有無使用基因演算法之下的結果，並且探討使用多載波運作(Multi-carrier operation)達到讓使用者能存取更大的頻寬(Wider bandwidth)，以及基因演算法資源分配如何應用在多載波運作的情況。

Along with the evolution of wireless communication techniques and increasing service demand of common users, the data quantity and the service quality which provided by the existing communication systems are no longer satisfied by the users. As the 3rd generation communication systems were well developed, the new standards which meet the new requirement are also being established by some standard bodies such as the IEEE which is proceeding in the establishment of IEEE802.16m standard that is the extension of the WiMAX (IEEE802.16e) specification, and LTE (Long Term Evolution)-Advanced standard that is being developed by 3GPP. These two standard bodies are competing for the 4th generation mobile communication technical standard.
From the multiplexing access point of view, the IEEE 802.16m adopts the OFDMA (Orthogonal Frequency Division Multiple Access) in both of its Downlink (DL) and Uplink (UL) accesses, while it uses OFDMA technique in its DL transmission and implements SC-FDMA (Single Carrier- Frequency Division Multiple Access) in the UL for LTE standard. Either of these two access techniques can simultaneously allocate frequency bands for users in their transmissions. It becomes an important issue in system design of how to properly allocate time and frequency resources for various classes of users. In this study, we consider the use of Genetic Algorithm (GA) technique in the processing of time and frequency resource allocations. By using the prominent convergence property of GA,the base stations can efficiently and effectively distribute their transmission resources. We are then through simulations to compute the possible amount of resource allocation when GA is exploited and compares its results with that without using GA. In this study we also consider the implementation of multi-carrier operations in the system so that to provide wider bandwidth services to users and meanwhile to investigate how to exploit the GA technique in the implementation of resource allocations in the multi-carrier operationenvironment.

目錄
第一章 緒論	1
1.1 研究動機與目的	1
1.2 章節介紹	2
第二章 系統介紹	3
2.1 IEEE802.16M系統介紹	3
2.1.1 訊框格式	3
2.1.2 資源單位形式	6
2.2 LTE系統介紹	10
2.2.1 訊框格式	10
2.2.2 資源區塊形式	12
第三章 資源分配方法	17
3.1	 基因演算法介紹	17
3.2 使用基因演算法進行資源分配	21
3.3 多載波之基因演算法資源分配	27
3.3.1 多載波模式介紹	27
3.3.2 多載波模式下之基因演算法資源分配方法	30
第四章 模擬結果與分析	34
4.1 IEEE802.16M及LTE系統效能模擬結果與分析	34
4.2 基因演算法收斂分析	49
第五章 結論與未來展望	60

 
圖目錄
圖2. 1 IEEE802.16M之基本訊框結構	4
圖2. 2 IEEE802.16M之TDD模式訊框結構(CP=1/8)	5
圖2. 3 IEEE802.16M之FDD模式訊框結構(CP=1/8)	5
圖2. 4一個資源單位與一個訊框的關係(IEEE802.16M, 頻寬=5MHZ)	7
圖2. 5下行導引信號樣式(A) 1 DATA STREAM  (B) 2 DATA STREAM	8
圖2. 6上行導引信號樣式(A) 1 DATA STREAM  (B) 2 DATA STREAM	9
圖2. 7上行導引信號樣式(PUSC MODE) (A) 1 DATA STREAM (B) 2 DATA STREAM	9
圖2.8 LTE系統之TDD訊框結構	11
圖2. 9 LTE系統之FDD訊框結構	12
圖2. 10 一個資源區塊與一個時槽的關係(LTE, NORMAL CP)	13
圖2. 11 LTE系統下行參考信號樣式(NORMAL CP)	14
圖2. 12 LTE系統下行參考信號樣式(EXTENDED CP)	15
圖2. 13 LTE上行參考信號樣式 (A) NORMAL CP  (B) EXTENDED CP	16
圖3. 1 PARTIAL-MAPPED CROSSOVER(PMX)交配方法	19
圖3. 2 二進位染色體之單點突變	19
圖3. 3 輪盤式選擇法示意圖	20
圖3. 4 基因演算法流程	20
圖3. 5 最小的使用者分配單位(A) IEEE802.16M  (B) LTE	22
圖3. 6 使用者資料的資源分配僅能分配成矩形(IEEE802.16M, 5MHZ, 1 FRAME)	23
圖3. 7單一染色體的形式	23
圖3. 8資源分配的交配步驟示意圖	24
圖3. 9資源分配的突變步驟示意圖	25
圖3.10資源分配的適應函數-剩餘資源單位/區塊對	26
圖3. 11 基因演算完畢後使用者資料再加入資源分配的動作	27
圖3. 12 LTE-ADVANCED多載波操作示意圖	29
圖3. 13 IEEE 802.16M的單載波與多載波行動台示意圖	29
圖3. 14 並行混合自動重傳請求(HARQ)的QOS排程器	30
圖3.15 多載波染色體形式	31
圖3. 16 多載波染色體交配	32
圖3. 17多載波染色體突變	32
圖3. 18 多載波染色體的適應值	33
圖4. 1 IEEE802.16M TDD單載波吞吐量比較(100 TIMES AVERAGE)	37
圖4. 2 IEEE802.16M TDD單載波封包服務率比較(100 TIMES AVERAGE)	37
圖4. 3 IEEE802.16M FDD單載波吞吐量比較(100 TIMES AVERAGE)	39
圖4. 4 IEEE802.16M FDD單載波封包服務率比較(100 TIMES AVERAGE)	39
圖4. 5 LTE TDD單載波吞吐量比較(100 TIMES AVERAGE)	41
圖4. 6 LTE TDD單載波封包服務率比較(100 TIMES AVERAGE)	41
圖4. 7 LTE FDD單載波吞吐量比較(100 TIMES AVERAGE)	43
圖4. 8 LTE FDD單載波封包服務率比較(100 TIMES AVERAGE)	43
圖4. 9 IEEE802.16M TDD，載波數為1、2和4的吞吐量(20 TIMES AVERAGE)	44
圖4. 10 IEEE802.16M TDD，載波數為1、2和4的封包服務率(20 TIMES AVERAGE)	45
圖4. 11 IEEE802.16M FDD，載波數為1、2和4的吞吐量(20 TIMES AVERAGE)	45
圖4. 12 IEEE802.16M FDD，載波數為1、2和4的封包服務率(20 TIMES AVERAGE)	46
圖4. 13 LTE TDD，載波數為1、2和4的吞吐量(20 TIMES AVERAGE)	46
圖4. 14 LTE TDD，載波數為1、2和4的封包服務率(20 TIMES AVERAGE)	47
圖4. 15 LTE FDD，載波數為1、2和4的吞吐量(20 TIMES AVERAGE)	47
圖4. 16 LTE FDD，載波數為1、2和4的封包服務率(20 TIMES AVERAGE)	48
圖4. 17 IEEE802.16M TDD多載波收斂速度比較(20 TIMES AVERAGE)	51
圖4. 18 IEEE802.16M FDD多載波收斂速度比較(20 TIMES AVERAGE)	52
圖4. 19 LTE TDD多載波收斂速度比較(20 TIMES AVERAGE)	53
圖4. 20 LTE FDD多載波收斂速度比較(20 TIMES AVERAGE)	54
圖4.21不同載波數的收斂速度 (TYPE 1, VOIP 70%) (20 TIMES AVERAGE)	56
圖4.22 不同載波數的收斂速度(TYPE 2, VIDEO 70%) (20 TIMES AVERAGE)	56
圖4.23 不同載波數的收斂速度 (TYPE 3, FTP 70%) (20 TIMES AVERAGE)	57
圖4.24 不同載波數的收斂速度 (TYPE 4, HTTP 70%) (20 TIMES AVERAGE)	57
圖4.25 不同載波數的收斂速度 (TYPE 5, VOIP 100%-1) (20 TIMES AVERAGE)	58
圖4.26 不同載波數的收斂速度 (TYPE 5, VOIP 100%-2) (20 TIMES AVERAGE)	58
圖5. 1 TYPE 1服務比例下，有無加入HARQ參數之收斂速度比較(20 TIMES AVERAGE)	63

 
表目錄
表2. 1 IEEE802.16M頻寬對應的實體資源單位數目	6
表2. 2 LTE系統TDD訊框支援的上下行比例	11
表2. 3 LTE頻寬所對應的資源區塊數量	13
表4. 1服務類別所對應的資料傳輸率及比例	35
表4. 2 IEEE802.16M TDD模擬參數	36
表4. 3 IEEE802.16M FDD模擬參數	38
表4. 4 LTE TDD模擬參數	40
表4. 5 LTE FDD模擬參數	42
表4. 6 IEEE802.16M TDD多載波平均收斂代數與估計收斂時間	51
表4. 7 IEEE802.16M FDD多載波平均收斂代數與估計收斂時間	52
表4. 8 LTE TDD多載波平均收斂代數與估計收斂時間	53
表4. 9 LTE FDD多載波平均收斂代數與估計收斂時間	54
表4.10 不同類型的服務比例	55
表4.11不同類型的服務比例下之平均收斂代數	59
表5. 1 IEEE 802.16M和LTE系統在載波數不同下之效能比較	61
表5. 2 IEEE 802.16M和LTE系統在載波數不同下之效能比較	61
表5. 3 IEEE802.16M及LTE系統在頻寬相同使用的子載波數比較	61
表5. 4 TYPE 1服務比例下，有無加入HARQ參數之收斂速度比較	62

[1] ”DRAFT Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems,” IEEE 802.16 Broadband Wireless Access Working Group, P802.16Rev2/D4, Apr.2008.
[2] “Work Plan for IEEE 802.16m Standard & IMT-Advanced Submission,” IEEE 802.16 Broadband Wireless Access Working Group, 80216m-07_001r2, Jul.2008.
[3] Shkumbin Hamiti, “IEEE 802.16m System Description Document,” IEEE 802.16 Broadband Wireless Access Working Group, 80216m-08_003r8, Apr.2009.
[4] Mark Cudak, “IEEE 802.16m System Requirements,“ IEEE 802.16 Broadband Wireless Access Working Group , 80216m-07_002r8, Jan.2009.
[5] Jeff Zhuang, Louay Jalloul, Robert Novak, Jeongho Park, “IEEE 802.16m Evaluation Methodology Document,” IEEE 802.16 Broadband Wireless Access Working Group, 80216m-08_004r5, Jan.2009.
[6] “IEEE 802.16m Amendment Working Document,” IEEE 802.16 Broadband Wireless Access Working Group, 80216m-09_0010r1a, Mar.2009.
[7] “UTRA-UTRAN Long Term Evolution (LTE) and 3GPP System Architecture Evolution (SAE),” 3GPP LTA_paper Oct.2006.
[8] “Base Station (BS) radio transmission and reception(Release 8)” 3GPP TS 36.104 V8.5.0, Mar.2009.
[9] “Physical Channels and Modulation(Release 8)” 3GPP TS 36.211 V8.6.0, Mar.2009.
[10] “Multiplexing and channel coding(Release8)” 3GPP TS 36.212 V8.6.0, Mar.2009.
[11] “Physical layer procedures(Release 8),” 3GPP TS 36.213,V8.6.0, Mar.2009.
[12] “Physical layer –Measurements(Release8),” 3GPP TS 36.214, V8.6.0, Mar.2009.
[13] Kian Chung Beh, Simon Armour, Angela Doufexi, “Joint Time-Frequency Domain Proportional Fair Scheduler with HARQ for 3GPP LTE Systems,” Vehicular Technology Conference, 2008. VTC 2008-Fall. IEEE 68th Sept 21-24, 2008 pp.1 – 5
[14] Erik Dahlman,”LTE-3G Long Term Evolution,” Expert Radio Access Technologies Ericsson Research, Mar.2007
[15] Hsien-Wei Tseng, Yen-Hsih Chou, Ming-Hsueh Chuang, Yang-Han Lee, Shiann-Tsong Sheu, Yih-Guang Jan, ”Design and Implementation of Subchannelization Scheduler in IEEE 802.16 Broadband wireless Access Systems,” Journal of the Chinese Institute of Engineers, vol. 31, 2008, No. 6, pp. 967-976.
[16] Yang-Han Lee, Yih-Guang Jan and Hsien-Wei Tseng, “Hardware Implementation of QoS Scheduling for WiMAX System by Using Genetic Algorithm,” International Journal of Fuzzy Systems, vol. 7, No. 4, 2005, pp. 191-198.
[17] Shiann-Tsong Sheu ,Yue-Ru Chuang, Yu-Hung Chen and Eugene Lai, “An Optimization Solution for Packet Scheduling: A Pipeline-Based Genetic Algorithm Accelerator,” Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), Chicago, IL, USA, vol. 2723/2003, , 2003, pp. 681-692.
[18] Tatsuhiro Tachibana, Yoshihiro Murata, Naoki Shibata†, Keiichi Yasumoto and Minoru Ito, “General Architecture for Hardware Implementation of Genetic Algorithm, ” IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM 2006 14th Annual), Napa, California, 2006, pp. 291-292.
[19] Tang, Wallace and Yip, Leslie, “Hardware Implementation of Genetic Algorithms Using FPGA,” The 2004 47th Midwest Symposium on Circuits and Systems (MWSCAS 2004), Hiroshima, Japan, vol. 1, 2004, pp. I-549-52.
[20] Thomson, P., and Miller, J. F., “Optimization Techniques Based on the Use of Genetic Algorithms (GAs) for Logic Implementation on FPGAs,” IEE Colloquium on Software Support and CAD Techniques for FPGAs, 1994, pp. 4/1-4/4.
	[21] Miguel A. Vega-Rodriguez, Raul Gutierrez-Gil, Jose M. Avila-Roman, Juan M. Sanchez-Perez, Juan A. Gomez-Pulido, “Genetic Algorithms Using Parallelism and FPGAs: the TSP as Case Study,”International Conference Workshops on Paralle Processing, (ICPP 2005), Oslo, Norway, 2005, pp. 573-579. 
	[22] Liu Zhe, Zhiqiang He, Weiling Wu, Xinglin Wang, “A Simplified Layered QoS Scheduling Scheme in OFDM Networks,” Vehicular Technology Conference, 2007. VTC-2007 Fall. 2007 IEEE 66th Sept. 30 2007-Oct. 3 2007. pp.1842 – 1846. 
	[23] Shou-Chih Lo, Yuan-Yung Hong, “A novel QoS scheduling approach for IEEE 802.16 BWA systems,” Communication Technology, 2008. ICCT 2008. 11th IEEE International Conference on 10-12 Nov. 2008 pp.46 – 49. 
	[24] Mats Wernersson, Stefan Wanstedt, Per Synnergren, “Effects of QoS Scheduling Strategies on Performance of Mixed Services over LTE,”Personal, Indoor and Mobile Radio Communications, 2007. PIMRC 2007. IEEE 18th International Symposium 3-7 Sept. 2007 pp.1 – 5. 
	[25] Fen Hou, Pin-Han Ho, Xuemin Shen, An-Yi Chen, “A Novel QoS Scheduling Scheme in IEEE 802.16 Networks,” Wireless Communications and Networking Conference, 2007.WCNC 2007. IEEE 11-15 March 2007 pp.2457 – 2462. 
	[26] Juncai Shi, Aiqun Hu, “Maximum Utility-Based Resource Allocation Algorithm in the IEEE 802.16 OFDMA System,” Communications, 2008. ICC '08. IEEE International Conference on 19-23 May 2008 Page(s):311 – 316. 
	[27] Arijit Ukil, Jaydip Sen, Debasish Bera, “A New Optimization Scheme for Resource Allocation in OFDMA Based WiMAX Systems ” Computer Engineering and Technology, 2009. ICCET '08. International Conference on vol.1, 22-24 Jan. 2009, pp.145 – 149. 
	[28] H. Hu, H.-H. Chen, K. Guo and M. Weckerle, “Cross-layer adaptive resource allocation for OFDM systems with hybrid smart antennas,”Communications, IET vol.1, Issue 5, Oct. 2007 pp.831 – 837. 
	[29] Guowang Miao, Nageen Himayat, “Low Complexity Utility Based Resource Allocation for 802.16 OFDMA Systems,” Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE March 31 2008-April 3 2008, pp.1465 - 1470. 
	[30] Hojoong Kwon, Byeong Gi Lee, “A Resource Allocation with Balanced Data Throughput and Power Consumption under QoS Constraint in MIMO Interference Systems: A Noncooperative Game Approach,”Communications, 2008. ICC '08. IEEE International Conference on 19-23 May 2008, pp.5123 – 5127. 
[31] Bo Gui and Leonard J. Cimini, Jr., “Resource allocation algorithms for multiuser cooperative OFDMA systems with subchannel permutation,” Information Sciences and Systems, 2008. CISS 2008. 42nd Annual Conference on 19-21 March 2008, pp.692 – 697.