代悅寧， 朱國(guó)暉

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

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

代悅寧， 朱國(guó)暉

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

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

資源分配；長(zhǎng)期演進(jìn)；遺傳算法

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

(2)

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

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

(3)

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

2 算法描述

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

圖1 算法流程

2.1 編碼和初始化

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

2.2 適應(yīng)度函數(shù)

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

其中當(dāng)v(n)∈RT時(shí)，有

當(dāng) v(n)∈NRT時(shí)，有

2.3 選擇

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

2.4 交叉和變異

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

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

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

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

3 仿真結(jié)果與分析

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

3.1 仿真環(huán)境

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

PLk=128.1+37.6 lgd，

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

表1 物理層參數(shù)

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

表2 業(yè)務(wù)QoS參數(shù)

3.2 結(jié)果分析

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

圖2為不同用戶數(shù)下系統(tǒng)的吞吐量?？梢钥闯鲭S著用戶數(shù)的增加，GRA優(yōu)于RR和SGA，但小于MAX C/I、PF和M-LWDF；吞吐量基本趨于穩(wěn)定。

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

圖3描述不同算法的公平性參數(shù)。測(cè)量公平性的數(shù)學(xué)標(biāo)準(zhǔn)公平性參數(shù)(Jain fairness index，JFI)[13]

其中Xk為用戶k所分到的總的RB數(shù)。該算法公平性優(yōu)于MAX C/I、M-LWDF，低于RR，略低于SGA。由各算法性質(zhì)可知，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è)務(wù)下不同用戶數(shù)的丟包率曲線?？煽闯龈魉惴▉G包率均小于RT業(yè)務(wù)QoS需求中的丟包率參數(shù)，且隨著用戶數(shù)的增加，丟包率呈指數(shù)型增長(zhǎng)。MAX C/I、RR和SGA在丟包率較高且性能類(lèi)似，PF和M-LWDF丟包率較低，但由于M-LWDF考慮到了時(shí)延參數(shù)，所以其丟包率低于PF。GRA考慮了更多的QoS參數(shù)，其丟包率較PF和M-LWDF要高，但低于RR、MAX C/I和SGA。丟包率和時(shí)延是相關(guān)的，由此可知對(duì)于RT業(yè)務(wù)，GRA提供了較小的時(shí)延。

圖4 RT用戶丟包率

圖5為BE業(yè)務(wù)下不同用戶數(shù)的系統(tǒng)吞吐量。可以看出對(duì)于BE業(yè)務(wù)，GRA提供了更大的吞吐量，且隨著用戶數(shù)的增加，增加幅度變緩。

圖5 BE用戶吞吐量

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

4 結(jié) 論

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

[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] 劉鵬飛, 盧光躍. 一種基于注水算法的認(rèn)知OFDM系統(tǒng)資源分配方法[J]. 西安郵電學(xué)院學(xué)報(bào), 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)的自適應(yīng)資源分配[J]. 西安郵電學(xué)院學(xué)報(bào), 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] 張玉才,沈元隆.遺傳算法在計(jì)算機(jī)系統(tǒng)優(yōu)化問(wèn)題中的應(yīng)用[J].西安郵電學(xué)院學(xué)報(bào),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 遺傳算法工具箱及應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社, 2005: 43-65.

[15] 聶聰. 多用戶OFDM系統(tǒng)動(dòng)態(tài)資源分配算法研究[D]. 蘭州: 蘭州大學(xué), 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.

[責(zé)任編輯:祝劍]

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

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

代悅寧(1988-)，女，碩士研究生，研究方向?yàn)橐苿?dòng)互聯(lián)網(wǎng)。E-mail:qingling900421@sina.com 朱國(guó)暉(1975-)，男，碩士，副教授，從事移動(dòng)互聯(lián)網(wǎng)研究。E-mail: zhgh@xupt.edu.cn

TN929.5

A

2095-6533(2014)01-0050-05