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

代悅寧， 朱國暉

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

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

代悅寧， 朱國暉

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

用戶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，分別對應(yīng)于無數(shù)據(jù)傳輸、四相相移鍵控(Quadrature Phase Shift Keying, QPSK)、16符號正交幅度調(diào)制(16 Quadrature Amplitude Modulation,16QAM)和64QAM。

2 算法描述

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

圖1 算法流程

2.1 編碼和初始化

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

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

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

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

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

2.3 選擇

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

2.4 交叉和變異

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

交叉概率Pc和變異概率Pm是交叉和變異中兩個重要參數(shù)，其選擇會影響算法性能和收斂性。Pc過大使優(yōu)秀個體的結(jié)構(gòu)很快被破壞，過小則搜索過慢；Pm過小不易產(chǎn)生新的個體結(jié)構(gòu)，過大則變成純粹的隨即搜索。算法中采用自適應(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ù)同時考慮到了業(yè)務(wù)的QoS需求和CSI，在滿足用戶QoS需求的同時保持公平性和提高吞吐量。

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

利用matlab對該算法進(jìn)行仿真，將最大載干比算法(Max Carrier to Interference，MAX C/I)、輪詢算法(Round Robin，RR)、比例公平算法(Proportional Fair，PF)、最大權(quán)重時延優(yōu)先算法[16](Modified-Largest Weighted Delay First，M-LWDF)、簡單遺傳算法 (Simple GA，SGA)，與GRA進(jìn)行吞吐量、公平性和丟包率對比。采用平均功率分配(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]見表1。根據(jù)式(1)計(jì)算Hk,n，其中路損采用密集市區(qū)模型，且

PLk=128.1+37.6 lgd，

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

表1 物理層參數(shù)

給出IP語音(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ù)，見表2。

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

3.2 結(jié)果分析

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

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

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

圖3描述不同算法的公平性參數(shù)。測量公平性的數(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吞吐量最大，公平性最小；RR吞吐量最小，但公平性最高；PF吞吐量和公平性均介于MAX C/I和RR之間；M-LWDF吞吐量和公平性均低于PF；而GRA吞吐量低于PF和M-LWDF，但高于SGA；公平性高于PF和M-LWDF，但略低于SGA。

圖3 算法公平性

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

圖4 RT用戶丟包率

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

圖5 BE用戶吞吐量

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

4 結(jié) 論

經(jīng)過交叉、變異和以適應(yīng)度函數(shù)值(利用了CSI和業(yè)務(wù)的QoS要求)為依據(jù)的選擇操作，得到相對最優(yōu)資源分配方案，同時由于遺傳算子選擇較為簡單，計(jì)算量并未大幅增加。仿真結(jié)果表明該算法較大程度的保留了對優(yōu)化目標(biāo)較好的基因，有效的淘汰了差的個體。在滿足用戶QoS需求的情況下，得到了較大的吞吐量，并保持較高的公平性，且對于RT業(yè)務(wù)能提供較小的時延，同時對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)化問題中的應(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)動態(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)橐苿踊ヂ?lián)網(wǎng)。E-mail:qingling900421@sina.com 朱國暉(1975-)，男，碩士，副教授，從事移動互聯(lián)網(wǎng)研究。E-mail: zhgh@xupt.edu.cn

TN929.5

A

2095-6533(2014)01-0050-05