臺灣博碩士論文加值系統

無線網路傳輸的服務，已經由早期使用的文字傳輸型態，提昇到現今多媒體應用的服務等級，隨著多媒體應用環境的普及率越高，使用者對於高速率資料的傳輸需求也相對增加，然而可以使用的頻寬資源仍然有限，為了增加無線頻寬資源的使用效率，並同時根據各個使用者不同的通道品質狀況狀態調整配置，就需要一套有效的資源分配方法進行頻寬資源的管理與配置。
本研究目的在於以正交分頻多工擷取之無線網路環境中，設計出一套方法來提供子通道的配置準則，對於各個使用者所使用之資源與環境做出權衡的機制，希望能夠讓系統整體的流量產出增加，利用基因演算法收斂速度快與全局處理之優勢，期望發展出一套即時之配置演算法，達到系統流量產出以及服務品質的權衡。
在本研究中針對兩種基因演算法的參數設定，採用了田口式正交表的設計分析方式，將實驗的次數有效減少，並且分析其各別變數與階層之間對於實驗之影響分析。此外本實驗也針對配置之方式作一分析，提出較為有效率之配置方式，減少資源的浪費。
而根據本研究實驗之結果，利用數學最佳化技巧為基礎之方略，對於服務提供者的頻寬資源，能夠提供一個即時之分配策略的參考方針，並且根據配置之結果，發展出一更快之演算機制，使服務提供者在面對WiMAX網路資源管理的問題時，可以有一可參考配置資源模式的準則來依循。

In recent years, the rapidly growing demands for high data rate and multimedia have driven the great development of the wireless mobile internet access. So Internet service providers needs an effective resource allocation algorithm to increase the resource utilize ratio according to every user’s channel quality by modifying the resource allocation scheme.
The objective of this thesis is to design a novel genetic algorithm, which provides a rule for sub-channel allocation in OFDMA networks. The algorithm can increase the throughput of OFDMA networks. This study proposed a MTGA(Mutual Therapeutic Genetic Algorithm) to solve the resource allocation problem and analyze the influence of variables in experimental result by using Taguchi experiment design in two genetic algorithms.
The experimental results show that our approach can increase the resource utilization for downlink Band AMC in WiMAX Networks. According to the resource allocation results, we also developed a real-time heuristic for Internet service providers to handle the resource allocation problems.

目錄
論文摘要 ............................................................................................................................................. I
Abstract ............................................................................................................................................. II
致謝 .................................................................................................................................................. III
目錄 ................................................................................................................................................... IV
圖目錄 ............................................................................................................................................... VI
表目錄 ............................................................................................................................................. VII
第一章 緒論 ....................................................................................................................................... 1
1.1 研究背景 ............................................................................................................................... 1
1.2 研究動機 ............................................................................................................................... 1
1.3 研究目的 ............................................................................................................................... 2
1.4 論文內容架構 ....................................................................................................................... 3
第二章 文獻探討 ............................................................................................................................... 4
2.1 正交分頻多工擷取 ............................................................................................................... 4
2.1.1多載波系統 ................................................................................................................. 5
2.1.2自適性調變 ................................................................................................................. 7
2.1.3編碼技術 ..................................................................................................................... 8
2.1.4 OFDMA系統運作流程 ............................................................................................ 10
2.1.5 OFDMA的優缺點 .................................................................................................... 11
2.2 資源分配 ............................................................................................................................. 12
2.2.1功率配置 ................................................................................................................... 13
2.2.2載波分配 ................................................................................................................... 14
2.2.3等價容量計算 ........................................................................................................... 17
2.2.4 OFDMA子載波排列模組 ........................................................................................ 19
2.2.5 OFDMA資源配置考量觀點 .................................................................................... 21
2.3 服務品質要求 ..................................................................................................................... 23
2.3.1服務品質 ................................................................................................................... 23
2.3.2資料傳輸速率要求 ................................................................................................... 26
2.3.3位元錯誤率需求 ....................................................................................................... 28
2.3.4服務品質相關研究 ................................................................................................... 29
第三章 研究設計 .............................................................................................................................. 32
3.1 問題描述 ............................................................................................................................. 32
3.2 數學模式之建立 ................................................................................................................. 35
3.3 解決方案 ............................................................................................................................. 38
第四章 研究方法規劃 ...................................................................................................................... 39
4.1基因演算法 .......................................................................................................................... 39
4.1.1 基因演算法基本流程 .............................................................................................. 40
4.1.2 產生初始族群及適應值評估 .................................................................................. 41
4.1.3 選擇 .......................................................................................................................... 41
4.1.4 交換 .......................................................................................................................... 41
4.1.5 突變 .......................................................................................................................... 43
4.2 基因演算法之研究方法設計 ............................................................................................. 43
4.2.1 基因演算法之染色體表示方式 .............................................................................. 43
4.2.2 適應值 ...................................................................................................................... 44
4.2.3 選擇 .......................................................................................................................... 44
4.2.4 交換 .......................................................................................................................... 44
4.2.5 突變 .......................................................................................................................... 46
4.2.6 取代 .......................................................................................................................... 46
第五章 實驗數據分析 ...................................................................................................................... 47
5.1實驗方法設計 ...................................................................................................................... 47
5.1.1資源配置演算法 ....................................................................................................... 47
5.1.2田口式基因演算法參數設定 ................................................................................... 49
5.1.3實驗環境 ................................................................................................................... 52
5.1.4使用者環境 ............................................................................................................... 52
5.2正交表實驗數據分析 .......................................................................................................... 53
5.2.1 HTGA正交表實驗.................................................................................................... 54
5.2.2 MTGA正交表實驗 ................................................................................................... 60
5.3實驗比較與分析 .................................................................................................................. 66
5.3.1實驗比較 ................................................................................................................... 66
5.3.2即時啟發性演算法 ................................................................................................... 69
第六章 結論與未來展望 .................................................................................................................. 70
參考文獻 ........................................................................................................................................... 71

圖目錄
圖2.1 FDM與OFDMA系統頻寬使用................................................................................................ 4
圖2.2 OFDMA系統下行頻寬分配圖例 ............................................................................................ 5
圖2.3 Convolutional code ................................................................................................................... 8
圖2.4偶數位元的mapping方式 ......................................................................................................... 9
圖2.5 BPSK, QPSK, 16-QAM, 64-QAM編碼示意圖 ..................................................................... 10
圖2.6 OFDMA系統運作流程 .......................................................................................................... 11
圖2.7適應性跳頻與固定頻率之範例 ............................................................................................. 15
圖2.8適應性跳頻與固定頻率之訊號強度比較 ............................................................................. 15
圖2.9 Comb spread carriers示意圖 .................................................................................................. 16
圖2.10三個資料流的Statistical multiplexing及其equivalent capacity .......................................... 18
圖2.11 data region示意圖 ................................................................................................................. 21
圖2.12根據不同的需求決定連線方式 ........................................................................................... 24
圖2.13隨時段變化的頻寬需求 ....................................................................................................... 24
圖3.1 IEEE 802.16e OFDMA AMC子通道架構 ............................................................................. 33
圖3.2根據各使用者之狀況來分配資源 ......................................................................................... 34
圖3.3問題描述範例步驟一 ............................................................................................................. 34
圖3.4問題描述範例步驟二 ............................................................................................................. 34
圖4.1簡單基因演算法流程圖 ......................................................................................................... 40
圖4.2單點交換示意圖 ..................................................................................................................... 42
圖4.3雙點交換示意圖 ..................................................................................................................... 42
圖4.4單點突變示意圖 ..................................................................................................................... 43
圖4.5基因演算法之染色體表示方式 ............................................................................................. 44
圖4.6交換時染色體之評估 ............................................................................................................. 45
圖4.7多點隨機交換方式示意 ......................................................................................................... 45
圖4.8基因演算法之基因突變表示方式 ......................................................................................... 46
圖5.1 HTGA演算法進行流程.......................................................................................................... 48
圖5.2實驗環境 ................................................................................................................................ 52
圖5.3 HTGA(1 subchannel × 6 symbols)正交表實驗結果與最佳值 ............................................. 55
圖5.4 HTGA(2 subchannels × 3 symbols)正交表實驗結果與最佳值 ............................................ 58
圖5.5 MTGA(1 subchannel × 6 symbols)正交表實驗結果與最佳值 ............................................. 61
圖5.6 MTGA(2 subchannels × 3 symbols)正交表實驗結果與最佳值 ........................................... 64
圖5.7依序配置步驟一 ..................................................................................................................... 67
圖5.8依序配置步驟二 ..................................................................................................................... 67
圖5.9隨機配置步驟一 ..................................................................................................................... 67
圖5.10隨機配置步驟二 ................................................................................................................... 67

表目錄
表2.1調變及編碼方式與接收端雜訊比值 (SNR) 之對照表 ...................................................... 10
表2.2 OFDMA中slot定義 ................................................................................................................ 20
表2.3子通道瞬間資料率 (kb/s) ..................................................................................................... 21
表2.4四種WiMAX所定義服務之服務品質需求 ........................................................................... 26
表2.5調變及編碼模式與Bits/symbol對照表 ................................................................................. 27
表3.1研究假設 ................................................................................................................................ 35
表3.2參數的定義 ............................................................................................................................. 36
表5.1 HTGA水準/因素表 ................................................................................................................ 50
表5.2 MTGA水準/因素表 ................................................................................................................ 50
表5.3 L’16正交表 .............................................................................................................................. 50
表5.4 HTGA加入水準./因素的L’16正交表 ..................................................................................... 51
表5.5 MTGA加入水準./因素的L’16正交表 .................................................................................... 51
表5.6 Modulation and Coding Schemes ........................................................................................... 53
表5.7調變方式與SNR之關係 ......................................................................................................... 53
表5.8 HTGA(1 subchannel × 6 symbols) L’16正交表數據 .............................................................. 54
表5.9 HTGA(1 subchannel × 6 symbols)正交表數據分析 ............................................................. 56
表5.10 HTGA(1 subchannel × 6 symbols)正交表最佳參數組合分析 ........................................... 56
表5.11 HTGA(1 subchannel × 6 symbols)固定其餘參數調整精英解 ........................................... 57
表5.12 HTGA(2 subchannels × 3 symbols) L’16正交表數據 .......................................................... 57
表5.13 HTGA(2 subchannels × 3 symbols)正交表數據分析 .......................................................... 59
表5.14 HTGA(2 subchannels × 3 symbols)正交表最佳參數組合分析 .......................................... 59
表5.15 HTGA(2 subchannels × 3 symbols)固定其餘參數調整精英解 .......................................... 60
表5.16 MTGA(1 subchannel × 6 symbols) L’16正交表數據 ........................................................... 61
表5.17 MTGA(1 subchannel × 6 symbols)正交表數據分析 ........................................................... 62
表5.18 MTGA(1 subchannel × 6 symbols)正交表最佳參數組合分析 ........................................... 62
表5.19 MTGA(2 subchannels × 3 symbols) L’16正交表數據 ......................................................... 63
表5.20 MTGA(2 subchannels × 3 symbols)正交表數據分析 ......................................................... 64
表5.21 MTGA(2 subchannels × 3 symbols)正交表最佳參數組合分析 ......................................... 65
表5.22 MTGA(2 subchannels × 3 symbols)固定其餘參數調整交換率 ......................................... 65
表5.23 實驗方法比較 ...................................................................................................................... 66
表5.24 配置方式實驗比較(1 subchannel × 6 symbols) ................................................................. 68
表5.25 配置方式實驗比較(2 subchannels × 3 symbols) ................................................................ 68
表5.26各配置方式結果分析 ........................................................................................................... 68
表5.27 即時啟發性演算法結果比較(1 subchannel × 6 symbols) ................................................. 69
表5.28 即時啟發性演算法結果比較(2 subchannels × 3 symbols) ................................................ 69

[1]
Alasti, M., Farrokhi, F.R., Olfat, M., and Liu, K.J.R., “Service level agreement (SLA) based scheduling algorithms for wireless networks,” in Proc. IEEE International Conference on Communications, vol. 2, 2004, pp. 1028-1032.
[2]
Ali, S.H., Lee, K.D., and Leung, V.C.M., “Dynamic resource allocation in OFDMA wireless metropolitan area networks,” IEEE Wireless Communications, vol. 14, no. 1, 2007, pp. 6-13.
[3]
Chan, P.W.C., Lo, E.S., Lau, V.K.N., Cheng, R.S., Letaief, K.B., Murch, R.D., and Mow, W.H., “Performance comparison of downlink multiuser MIMO-OFDMA and MIMO-MC-CDMA with transmit side information - multi-cell analysis,” IEEE Transactions on Wireless Communications, vol. 6, no. 6, 2007, pp. 2193-2203.
[4]
Farrokhi, F.R., Olfat, M., Alasti, M., and Liu, K.J.R., “Scheduling algorithm for quality of service aware OFDMA wireless systems,” in Proc. IEEE Global Telecommunications Conference, vol. 4, 2004, pp. 2689-2693.
[5]
Gotsis, A.G., Koutsokeras, N.T., and Constantinou, P., “Radio resource allocation and packet scheduling strategies for single-cell OFDMA packet networks,” in Proc. IEEE Vehicular Technology Conference, 2007, pp. 1847-1851.
[6]
Guerin, R., Ahmadi, H., and Naghshineh, M., “Equivalent capacity and its application to bandwidth allocation in high-speed networks,” IEEE Journal on Selected Areas in Communications, vol. 9, no. 7, Sep. 1991, pp. 968-981.
[7]
Han, Z., Ji, Z., and Liu, K.J.R., “Fair multiuser channel allocation for OFDMA networks using Nash bargaining solutions and coalitions,” IEEE Transactions on Communications, vol. 53, no. 8, 2005, pp. 1366-1376.
[8]
Holland, J.H., Adaptation in Natural and Artificial Systems, University of michigan press, Ann Arbor, MI, 1975.
[9]
Hosein, P., “Adaptive subchannel allocation in an OFDMA-based wireless network,” in Proc.
[10]
Jang, J.H. and Lee, K.B., “Transmit power adaptation for multiuser OFDM systems,” IEEE Journal on Selected Areas in Communications, vol. 21, no.2, 2003, pp. 171-178.
[11]
Jeong, J.H., “System technology for portable Internet,” in Proc. KRnet 2004, June 2004.
[12]
Kim, K.Y., Kim, H. and Han, Y., “Subcarrier and power allocation in OFDMA systems,” in Proc. IEEE Vehicular Technology Conference, vol. 2, 2004, pp. 1058-1062.
[13]
Kittipiyakul, S., and Javidi, T., “Subcarrier allocation in OFDMA systems: beyond water-filling,” IEEE Conference on Signals, Systems and Computers, vol. 1, 2004, pp. 334-338.
[14]
Kivanc, D., Li, G.Q., and Liu, H., “Computationally efficient bandwidth allocation and power control for OFDMA,” IEEE Transactions on Wireless Communications, vol. 2, no. 6, 2003, pp. 1150-1158.
[15]
Kulkarni, G., Adlakha, S., and Srivastava, M., “Subcarrier allocation and bit loading algorithms for OFDMA-based wireless networks,” IEEE Transactions on Mobile Computing, vol. 4, no. 6, 2005, pp. 652-662.
[16]
Kumaran, K., and Viswanathan, H., “Joint power and bandwidth allocation in downlink transmission,” IEEE Transactions on Wireless Communications, vol. 4, no 3, May 2005, pp. 1008-1016.
[17]
Lawrey, E., “Multiuser OFDM,” in Proc. the Fifth International Symposium on Signal Processing and Its Application, vol. 2, Aug. 1999, pp. 761–764.
[18]
Li, G.Q., and Liu, H., “Dynamic resource allocation with finite buffer constraint in broadband OFDMA networks,” IEEE Wireless Communications and Networking, vol. 2, 2003, pp. 1037-1042.
[19]
Mao, Z.W., and Wang, X.M., “Efficient optimal and suboptimal radio resource allocation in OFDMA system,” IEEE Transactions on Wireless Communication, vol. 7, no. 2, 2008, pp. 440-445.
[20]
Mohanram, C., and Bhashyam, S., “A sub-optimal joint subcarrier and power allocation algorithm for multiuser OFDM,” IEEE Communications Letters, vol. 9, no. 8, Aug. 2005, pp. 685-687.
[21]
Nguyen, T.D., and Han, Y., “Schemes for maximal throughput and fairness in downlink OFDMA systems,” in Proc. First International Conference on Communications and Electronics, 2007, pp. 188-192.
[22]
Qin, Z.B., and Kuo, G.S., “Cross-layer design for QoS-oriented resource allocation with fairness provision in IEEE 802.16 OFDMA networks,” in Proc. The 2007 International Conference on Next Generation Mobile Applications, Services and Technologies, 2007, pp. 287-291.
[23]
Tsai, J.T., Liu, T.K., and Chou, J.H., “Hybrid taguchi-genetic algorithm for global numerical optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 4, 2004, pp. 365-377
[24]
Wahlqvist, M., Ostberg, C., Beek, J., Edfors, O., and Borjesson, P., “A conceptual study of OFDM-based multiple access schemes,” Technical Report Tdoc 117/96, Helsinki, Finland, May 1996.
[25]
Wan, L.H., Ma, W.C., and Guo, Z.H., “A cross-layer packet scheduling and subchannel allocation scheme in 802.16e OFDMA system,” in Proc. IEEE Wireless Communications and Networking Conference, 2007, pp. 1865-1870.
[26]
Wang, W., Hwang, K.C., Lee, K.B., and Bahk, S.W., “Resource allocation for heterogeneous services in multiuser OFDM systems,” in Proc. IEEE Global Telecommunications Conference, vol. 9, 2004, pp. 3478-3481.
[27]
Wong, C.Y., Cheng, R.S., Letaief, K.B., and Murch, R.D., “Multiuser OFDM with adaptive subcarrier, bit, and power allocation,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 10, 1999, pp. 1747-1758.
[28]
Wong, I.C., Shen, Z.K., Evans, B.L., and Andrews, J.G., “A low complexity algorithm for
proportional resource allocation in OFDMA systems,” in Proc. IEEE Workshop on Signal Processing Systems, 2004, pp. 1-6.
[29]
Yu, Y., and Zhou, W., “Resource allocation for OFDMA system based on genetic algorithm,” in Proc. International Workshop on Cross Layer Design, 2007, pp. 65-69.
[30]
Zhang, G., “Subcarrier and bit allocation for real-time services in multiuser OFDM systems,” in Proc. IEEE International Conference on Communications, vol. 5, 2004, pp. 2958-2989.
[31]
Zhang, Y.J., and Letaief, K.B., “Adaptive resource allocation and scheduling for multiuser packet-based OFDM networks,” in Proc. IEEE International Conference on Communications, vol. 5, 2004, pp. 2949-2953.
[32]
Zhang, Y.J., and Letaief, K.B., “Energy-efficient MAC-PHY resource management with guaranteed QoS in wireless OFDM networks,” in Proc. IEEE International Conference on Communications, vol. 5, 2005, pp. 3127-3131.