代悅寧， 朱國暉

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

基于遺傳算法的LTE下行系統(tǒng)資源分配算法

代悅寧， 朱國暉

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

為改善多業(yè)務LTE下行系統(tǒng)的吞吐量和公平性并滿足用戶對多業(yè)務的需求，提出一種基于遺傳算法的資源分配算法。該算法以遺傳算法為基礎，建立以適應度函數值之和最大化為目的的優(yōu)化目標，根據用戶業(yè)務的服務質量需求和信道狀態(tài)信息設計適應度函數，經過選擇、交叉、變異等操作，得到相對最優(yōu)資源分配方案。仿真結果表明，與傳統(tǒng)算法相比，該算法滿足多種業(yè)務的服務質量需求，增加系統(tǒng)的公平性，對實時業(yè)務提供較小的時延，對盡力而為業(yè)務提供更大的吞吐量。

資源分配；長期演進；遺傳算法

如何使用有限的資源，更好的滿足用戶不同的服務質量(Quality of Service，QoS)需求和提高系統(tǒng)通信性能，是長期演進(Long Term Evolution, LTE)的一大挑戰(zhàn)，這個問題需要資源分配(Resource Allocation，RA)算法來解決。RA算法中，吞吐量、公平性和QoS需求是非常重要的考慮因素，但它們無法同時達到最優(yōu)。文獻[1]研究了正交頻分多址接入(Orthogonal Frequency Division Multiple Access，OFDMA)系統(tǒng)中最大化系統(tǒng)吞吐量的資源分配算法，但沒有考慮到系統(tǒng)的公平性。文獻[2-3]提出了一種吞吐量最大化的注水算法，但計算量頗大。文獻[4]的算法基于注水算法對功率進行了分配，提高了系統(tǒng)吞吐量，但沒有考慮到公平性。文獻[5-6]引入了效用函數，基于效用最大化準則推導出子載波分配和功率分配的必要條件，卻只考慮了用戶的公平和頻譜利用率。文獻[7]研究了OFDM系統(tǒng)中基于效應函數的動態(tài)子載波和功率分配算法，仿真結果僅針對了實時業(yè)務。文獻[8]提出了一種保障了用戶公平性的最大化吞吐量的算法，但只適合非實時業(yè)務，無法保障實時業(yè)務所需的QoS需求。本文提出了一種基于遺傳算法的資源分配算法(Genetic Resource Algorithm， GRA)，將資源分配映射成最優(yōu)化問題，在全局解空間內尋找最優(yōu)解，能夠在不增加計算復雜度的情況下，得到更好的系統(tǒng)性能。

1 系統(tǒng)模型

單小區(qū)多用戶多業(yè)務LTE下行系統(tǒng)的資源分配的單位是資源塊(Resource Block，RB)[9]。RB是時頻資源塊，時域上由7個OFDM符號組成，頻域上由12個子載波組成。分配時間單位為傳輸時間間隔(Transmission Time Interval，TTI)，時長1ms，時域包括2個時隙。一個RB在一個TTI里只能分配給一個用戶。該系統(tǒng)中主要考慮系統(tǒng)用戶的業(yè)務QoS需求和用戶的信道狀態(tài)信息(Channel State Information，CSI)兩個問題。

1.1 系統(tǒng)用戶的業(yè)務QoS需求

系統(tǒng)支持實時(Real Time，RT)、非實時(Not Real Time，NRT)和盡力而為(Best Effect，BE)三種業(yè)務。假定每個用戶在一個TTI內只有一種業(yè)務，每種業(yè)務有其獨特的QoS需求：對于RT業(yè)務，有最大誤碼率BER*(Bit Error Rate，BER)，最大包時延容限D*和最大丟包率PL*；對于NRT業(yè)務，有BER*，最小傳輸速率R*；對于BE業(yè)務，只有BER*。

1.2 信道狀態(tài)信息

假定信道相干時間大于TTI時長，可認為信道狀態(tài)信息在一個TTI內是固定的。用戶受到的干擾為信道衰落和白噪聲。Hk,n為用戶k(k=1,2,…,K)在RBn(n=1,2,…,N)上的信道增益[10]

(1)其中Plk為基站到用戶k的路損，Shak為基站到用戶k的陰影衰落，Lt為多徑衰落的路徑數(服從對數正態(tài)分布)，Rayk,l為基站到用戶k第l條路徑的瑞利衰落參數，fn為RBn的頻率，τl為第l條路徑的時延。

用戶k在RBn上的信噪比(Signal/Noise)為[10]

SNRk,n=pk,n×‖Hk,n‖2/σ2，

(2)

其中pk,n為用戶k在RBn上的導頻功率，σ2為加性高斯白噪聲(0均值)方差。

若用戶k滿足其業(yè)務規(guī)定的最大誤碼率，采用M階調制所需最小信噪比[10]

(3)

γk,n指示了用戶k在RBn上所支持的最大調制階，γk,n=0，2，4和6，分別對應于無數據傳輸、四相相移鍵控(Quadrature Phase Shift Keying, QPSK)、16符號正交幅度調制(16 Quadrature Amplitude Modulation,16QAM)和64QAM。

2 算法描述

基于GA[11-12]的資源分配算法將資源分配問題映射成最優(yōu)化模型，使用GA的架構，根據用戶時延、平均速率等QoS需求和用戶的量化CSI設計適應度函數，使用特定的遺傳算子促進種群向好的方面快速收斂，盡快得到較好結果。遺傳算法的根本是種群的進化，包括種群中染色體的選擇、交叉和變異，這些操作均基于適應度函數值。算法流程如圖1所示。

圖1 算法流程

2.1 編碼和初始化

編碼和初始化為GA的基礎。初始化時隨機生成Np個染色體，即一個種群(一種可能的分配方案)采用實數編碼方式，染色體中每個基因指示RB分配給哪個用戶。令染色體間海明距離大于[N/5]，保證初始化得到的分配方案有明顯的差別，不會得到一個局部最好的方案。

2.2 適應度函數

適應度函數[13]用于計算種群中染色體競爭力。算法的適應度函數F(v)通過對染色體上每個基因的函數f(n)之和進行指數比例變換得到，而f(n)是結合業(yè)務的QoS需求和γk,n得到。其表達式為

其中當v(n)∈RT時，有

當 v(n)∈NRT時，有

2.3 選擇

算法中有兩個選擇操作。(1)使用最佳保留，即從上一代得到的種群中選擇適應度最好的染色體(一般為Np/5)保留，不參與交叉和變異，將較好的分配方案暫時保留。(2)對剩余的染色體進行交叉和變異之后得到的染色體群組，使用無回放余數隨機選擇方法[14]，并引入小生境[15]排擠機制，選擇出剩余的染色體(4Np/5)。兩次選擇后的染色體組成下次循環(huán)的初始種群，經過這兩次選擇，可得到本次循環(huán)內最好的分配方案組。

2.4 交叉和變異

交叉和變異可以得到更多的分配方案以供選擇，增加得到最優(yōu)方案的可能。交叉把兩個父代染色體的部分結構加以替換重組而生成新染色體；變異對種群中的染色體的某些基因作變動，維持種群多樣性。算法中共有3次交叉，即強-強交叉，強-弱交叉和弱-弱交叉，均采用簡單離散算術交叉[12]。算法中有一次變異，采用均勻性變異[14]。

交叉概率Pc和變異概率Pm是交叉和變異中兩個重要參數，其選擇會影響算法性能和收斂性。Pc過大使優(yōu)秀個體的結構很快被破壞，過小則搜索過慢；Pm過小不易產生新的個體結構，過大則變成純粹的隨即搜索。算法中采用自適應算法[14]的自適應策略使算法性能更加優(yōu)越，相關表達式為

其中k1,k2,k3和k4∈(0 , 1)，Fmax為種群中最大適應度，Favg為種群平均適應度，F′為要交叉的父代中較大的適應度，F為要變異或交叉的染色體適應度。

算法中適應度函數同時考慮到了業(yè)務的QoS需求和CSI，在滿足用戶QoS需求的同時保持公平性和提高吞吐量。

3 仿真結果與分析

利用matlab對該算法進行仿真，將最大載干比算法(Max Carrier to Interference，MAX C/I)、輪詢算法(Round Robin，RR)、比例公平算法(Proportional Fair，PF)、最大權重時延優(yōu)先算法[16](Modified-Largest Weighted Delay First，M-LWDF)、簡單遺傳算法 (Simple GA，SGA)，與GRA進行吞吐量、公平性和丟包率對比。采用平均功率分配(Equal Power Allocation，EPA)[17]進行功率分配。

3.1 仿真環(huán)境

根據GA的一般性規(guī)定[11]可設定小區(qū)中用戶數K為[2,10,18,26,34]，最大遺傳代數為30，NP=20，適應度函數中參數XRT=1.5，XNRT=1，XBE=0.5。物理層參數[8]見表1。根據式(1)計算Hk,n，其中路損采用密集市區(qū)模型，且

PLk=128.1+37.6 lgd，

其中d為用戶k到基站的距離，單位為km,PLk的單位為dB；陰影衰落Shak，服從的對數正態(tài)分布，標準差σSha=8；多徑衰落，建模為Lt=6的瑞利衰落多徑，功率時延分布為[1, 0.60653, 0.36788, 0.22313, 0.13534, 0.082085]。

表1 物理層參數

給出IP語音(Voice over Internet Protocol, VoIP)和視頻(Video) 兩種RT業(yè)務、超文本傳輸協(xié)議 (Hypertext transfer protocol, HTTP)的NRT業(yè)務、文件傳輸協(xié)議(File Transfer Protocol, FTP)的BE業(yè)務的QoS參數，見表2。

表2 業(yè)務QoS參數

3.2 結果分析

MAX C/I只考慮CSI，RR不考慮CSI，且其中每個用戶占用RB的機會相同，PF是MAX C/I和RR的折中，但以上三種算法均未考慮到業(yè)務QoS參數。M-LWDF是在PF基礎上考慮了QoS中的時延參數，而GRA和SGA同時考慮到了QoS中的所有需求，本文算法則選擇了特定的遺傳算子。

圖2為不同用戶數下系統(tǒng)的吞吐量。可以看出隨著用戶數的增加，GRA優(yōu)于RR和SGA，但小于MAX C/I、PF和M-LWDF；吞吐量基本趨于穩(wěn)定。

圖2 系統(tǒng)吞吐量

圖3描述不同算法的公平性參數。測量公平性的數學標準公平性參數(Jain fairness index，JFI)[13]

其中Xk為用戶k所分到的總的RB數。該算法公平性優(yōu)于MAX C/I、M-LWDF，低于RR，略低于SGA。由各算法性質可知，MAX C/I吞吐量最大，公平性最?。籖R吞吐量最小，但公平性最高；PF吞吐量和公平性均介于MAX C/I和RR之間；M-LWDF吞吐量和公平性均低于PF；而GRA吞吐量低于PF和M-LWDF，但高于SGA；公平性高于PF和M-LWDF，但略低于SGA。

圖3 算法公平性

圖4為RT業(yè)務下不同用戶數的丟包率曲線。可看出各算法丟包率均小于RT業(yè)務QoS需求中的丟包率參數，且隨著用戶數的增加，丟包率呈指數型增長。MAX C/I、RR和SGA在丟包率較高且性能類似，PF和M-LWDF丟包率較低，但由于M-LWDF考慮到了時延參數，所以其丟包率低于PF。GRA考慮了更多的QoS參數，其丟包率較PF和M-LWDF要高，但低于RR、MAX C/I和SGA。丟包率和時延是相關的，由此可知對于RT業(yè)務，GRA提供了較小的時延。

圖4 RT用戶丟包率

圖5為BE業(yè)務下不同用戶數的系統(tǒng)吞吐量?？梢钥闯鰧τ贐E業(yè)務，GRA提供了更大的吞吐量，且隨著用戶數的增加，增加幅度變緩。

圖5 BE用戶吞吐量

由以上仿真結果可知GRA相對于SGA算法，吞吐量增加和丟包率降低，公平性略微降低，總體性能有所提高；相對于經典調度算法，在吞吐量和公平性間進行了平衡，丟包率升高；相對于同樣考慮了QoS的算法M-LWDF，公平性提高，吞吐量降低，幅度不大，同樣丟包率升高。GRA在公平性和吞吐量上性能較好，在丟包率上有改進空間。

4 結 論

經過交叉、變異和以適應度函數值(利用了CSI和業(yè)務的QoS要求)為依據的選擇操作，得到相對最優(yōu)資源分配方案，同時由于遺傳算子選擇較為簡單，計算量并未大幅增加。仿真結果表明該算法較大程度的保留了對優(yōu)化目標較好的基因，有效的淘汰了差的個體。在滿足用戶QoS需求的情況下，得到了較大的吞吐量，并保持較高的公平性，且對于RT業(yè)務能提供較小的時延，同時對BE業(yè)務提供了更高的吞吐量，達到預期目標。

[1] Ying Peng, Armour S M D, Mcgeehan J P. An investigation of dynamic subcarrier allocation in MIMO-OFDMA systems [J]. IEEE Transactions on Vehicular Technology, 2007, 56(5): 2990-3005.

[2] Chung S T, Goldsmtth A J.Degrees of Freedom in Adaptive Modulation: A Unified View [J]. IEEE Transactions on Communications, 2001, 49(9):1561-1571.

[3] Wong I C, Evans B L. Optimal resource allocation in OFD-MA systems with imperfect channel knowledge [J]. IEEE Transactions on Communications, 2009, 57(1): 232-241.

[4] 劉鵬飛, 盧光躍. 一種基于注水算法的認知OFDM系統(tǒng)資源分配方法[J]. 西安郵電學院學報, 2010, 15(1): 9-12.

[5] Song Guocong, Li Ye. Cross-Layer optimization for OFDM wireless network-Part I: theoretical framework [J]. IEEE Trasctions On Wireless Communications, 2005, 4 (2):625-534.

[6] 燕紅麗, 袁佳良, 王軍選. 高公平下OFDMA系統(tǒng)的自適應資源分配[J]. 西安郵電學院學報, 2012, 17(6): 60-64.

[7] Katoozian M, Navaie K,Yanikomeroglu H. Utility-based adaptive radio resource allocation in OFDM wireless networks with traffic prioritization[J]. IEEE Transactions on Wireless Communications, 2009, 8(1): 66-71.

[8] Kela P, Puttonen I, Kolehmainen N, Ristaniemi T, et al. Dynamic packet scheduling performance in UTRA long term evolution downlink [C]//International Symposium on Wireless Pervasive Computing, (ISWPC), 2008: 203-208.

[9] 3GPP. TS 36.211, Physical Channels and Modulation [EB/OL]. (2013-06-17) [2013-08-05]. http://www.3gpp.org/ftp/Specs/html-info/36211.htm

[10] Chung Yaohsing, Chang Chungju. A Balanced Resource Scheduling Scheme With Adaptive Priority Thresholds for OFDMA Downlink Systems[J], IEEE Transactions on Vehicular Technology, 2012, 61(3): 1276-1286.

[11] Holland J H. Adaptation in Natural and Artificial Systems [M]. [s.l.]: A Bradford Book, 1992: 75-88.

[12] 張玉才,沈元隆.遺傳算法在計算機系統(tǒng)優(yōu)化問題中的應用[J].西安郵電學院學報,2005,10(1):76-78.

[13] Jain B R, Mani G S. Applying micro GA concept for problems with large and rugged solution space[C]//TENCOM 2009-2009 IEEE Region 10 Conference, Singapore, 2009: 1-5.

[14] 雷英杰, 張善文, 李續(xù)武, 周創(chuàng)明. MATLAB 遺傳算法工具箱及應用[M]. 西安: 西安電子科技大學出版社, 2005: 43-65.

[15] 聶聰. 多用戶OFDM系統(tǒng)動態(tài)資源分配算法研究[D]. 蘭州: 蘭州大學, 2008: 1-49.

[16] Lee J Y, Sorour S, Valaee S, et al. Dynamic Parameter Adaptation for M-LWDF/ M-LWWF Scheduling[J].IEEE Transactions on Wireless Communications, 2012, 11(3): 927-937.

[17] Lee H W, Song Chong. Downlink resource allocation in multi-carrier systems: Frequency-selective vs. equal power allocation[J]. IEEE Transactions on Wireless Communications, 2008, 7(10): 3738-3747.

[責任編輯:祝劍]

A resource allocation algorithm based on genetic algorithm for LTE downlink systems

DAI Yuening， ZHU Guohui

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

A resource allocation scheme based on Genetic Algorithm is proposed for the downlink of integrated services LTE system in order to improve the throughput and fireness of the system，and to satisfy users’ requirements of multi-traffic. The optimization object which maximizes the sum of the fitness functions’ value is built，and three fitness functions for Real Time, Non Real Time and Best Effort services are given by this algorithm. Fitness functions according to the services’ QoS and CSI are also designed by this algorithm, and then used to get the optimal allocation scheme after selection, crossover, mutation operations. Simulation results show that compared with the traditional algorithm, this algorithm can satisfy integrated services’ QoS, raise the fairness of system, provide smaller delay for real time services, and maintain higher throughput for the best effort services.

resource allocation, long term evolution(LTE), genetic algorithm(GA)

10.13682/j.issn.2095-6533.2014.01.010

2013-10-20

陜西省教育廳科技計劃基金資助項目(07JK377)

代悅寧(1988-)，女，碩士研究生，研究方向為移動互聯網。E-mail:qingling900421@sina.com 朱國暉(1975-)，男，碩士，副教授，從事移動互聯網研究。E-mail: zhgh@xupt.edu.cn

TN929.5

A

2095-6533(2014)01-0050-05