基于遗传算法的LTE下行系统资源分配算法

代悦宁， 朱国晖

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

基于遗传算法的LTE下行系统资源分配算法

代悦宁， 朱国晖

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

为改善多业务LTE下行系统的吞吐量和公平性并满足用户对多业务的需求，提出一种基于遗传算法的资源分配算法。该算法以遗传算法为基础，建立以适应度函数值之和最大化为目的的优化目标，根据用户业务的服务质量需求和信道状态信息设计适应度函数，经过选择、交叉、变异等操作，得到相对最优资源分配方案。仿真结果表明，与传统算法相比，该算法满足多种业务的服务质量需求，增加系统的公平性，对实时业务提供较小的时延，对尽力而为业务提供更大的吞吐量。

资源分配；长期演进；遗传算法

如何使用有限的资源，更好的满足用户不同的服务质量(Quality of Service，QoS)需求和提高系统通信性能，是长期演进(Long Term Evolution, LTE)的一大挑战，这个问题需要资源分配(Resource Allocation，RA)算法来解决。RA算法中，吞吐量、公平性和QoS需求是非常重要的考虑因素，但它们无法同时达到最优。文献[1]研究了正交频分多址接入(Orthogonal Frequency Division Multiple Access，OFDMA)系统中最大化系统吞吐量的资源分配算法，但没有考虑到系统的公平性。文献[2-3]提出了一种吞吐量最大化的注水算法，但计算量颇大。文献[4]的算法基于注水算法对功率进行了分配，提高了系统吞吐量，但没有考虑到公平性。文献[5-6]引入了效用函数，基于效用最大化准则推导出子载波分配和功率分配的必要条件，却只考虑了用户的公平和频谱利用率。文献[7]研究了OFDM系统中基于效应函数的动态子载波和功率分配算法，仿真结果仅针对了实时业务。文献[8]提出了一种保障了用户公平性的最大化吞吐量的算法，但只适合非实时业务，无法保障实时业务所需的QoS需求。本文提出了一种基于遗传算法的资源分配算法(Genetic Resource Algorithm， GRA)，将资源分配映射成最优化问题，在全局解空间内寻找最优解，能够在不增加计算复杂度的情况下，得到更好的系统性能。

1 系统模型

单小区多用户多业务LTE下行系统的资源分配的单位是资源块(Resource Block，RB)[9]。RB是时频资源块，时域上由7个OFDM符号组成，频域上由12个子载波组成。分配时间单位为传输时间间隔(Transmission Time Interval，TTI)，时长1ms，时域包括2个时隙。一个RB在一个TTI里只能分配给一个用户。该系统中主要考虑系统用户的业务QoS需求和用户的信道状态信息(Channel State Information，CSI)两个问题。

1.1 系统用户的业务QoS需求

系统支持实时(Real Time，RT)、非实时(Not Real Time，NRT)和尽力而为(Best Effect，BE)三种业务。假定每个用户在一个TTI内只有一种业务，每种业务有其独特的QoS需求：对于RT业务，有最大误码率BER*(Bit Error Rate，BER)，最大包时延容限D*和最大丢包率PL*；对于NRT业务，有BER*，最小传输速率R*；对于BE业务，只有BER*。

1.2 信道状态信息

假定信道相干时间大于TTI时长，可认为信道状态信息在一个TTI内是固定的。用户受到的干扰为信道衰落和白噪声。Hk,n为用户k(k=1,2,…,K)在RBn(n=1,2,…,N)上的信道增益[10]

(1)其中Plk为基站到用户k的路损，Shak为基站到用户k的阴影衰落，Lt为多径衰落的路径数(服从对数正态分布)，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满足其业务规定的最大误码率，采用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]的资源分配算法将资源分配问题映射成最优化模型，使用GA的架构，根据用户时延、平均速率等QoS需求和用户的量化CSI设计适应度函数，使用特定的遗传算子促进种群向好的方面快速收敛，尽快得到较好结果。遗传算法的根本是种群的进化，包括种群中染色体的选择、交叉和变异，这些操作均基于适应度函数值。算法流程如图1所示。

图1 算法流程

2.1 编码和初始化

编码和初始化为GA的基础。初始化时随机生成Np个染色体，即一个种群(一种可能的分配方案)采用实数编码方式，染色体中每个基因指示RB分配给哪个用户。令染色体间海明距离大于[N/5]，保证初始化得到的分配方案有明显的差别，不会得到一个局部最好的方案。

2.2 适应度函数

适应度函数[13]用于计算种群中染色体竞争力。算法的适应度函数F(v)通过对染色体上每个基因的函数f(n)之和进行指数比例变换得到，而f(n)是结合业务的QoS需求和γk,n得到。其表达式为

其中当v(n)∈RT时，有

当 v(n)∈NRT时，有

2.3 选择

算法中有两个选择操作。(1)使用最佳保留，即从上一代得到的种群中选择适应度最好的染色体(一般为Np/5)保留，不参与交叉和变异，将较好的分配方案暂时保留。(2)对剩余的染色体进行交叉和变异之后得到的染色体群组，使用无回放余数随机选择方法[14]，并引入小生境[15]排挤机制，选择出剩余的染色体(4Np/5)。两次选择后的染色体组成下次循环的初始种群，经过这两次选择，可得到本次循环内最好的分配方案组。

2.4 交叉和变异

交叉和变异可以得到更多的分配方案以供选择，增加得到最优方案的可能。交叉把两个父代染色体的部分结构加以替换重组而生成新染色体；变异对种群中的染色体的某些基因作变动，维持种群多样性。算法中共有3次交叉，即强-强交叉，强-弱交叉和弱-弱交叉，均采用简单离散算术交叉[12]。算法中有一次变异，采用均匀性变异[14]。

交叉概率Pc和变异概率Pm是交叉和变异中两个重要参数，其选择会影响算法性能和收敛性。Pc过大使优秀个体的结构很快被破坏，过小则搜索过慢；Pm过小不易产生新的个体结构，过大则变成纯粹的随即搜索。算法中采用自适应算法[14]的自适应策略使算法性能更加优越，相关表达式为

其中k1,k2,k3和k4∈(0 , 1)，Fmax为种群中最大适应度，Favg为种群平均适应度，F′为要交叉的父代中较大的适应度，F为要变异或交叉的染色体适应度。

算法中适应度函数同时考虑到了业务的QoS需求和CSI，在满足用户QoS需求的同时保持公平性和提高吞吐量。

3 仿真结果与分析

利用matlab对该算法进行仿真，将最大载干比算法(Max Carrier to Interference，MAX C/I)、轮询算法(Round Robin，RR)、比例公平算法(Proportional Fair，PF)、最大权重时延优先算法[16](Modified-Largest Weighted Delay First，M-LWDF)、简单遗传算法 (Simple GA，SGA)，与GRA进行吞吐量、公平性和丢包率对比。采用平均功率分配(Equal Power Allocation，EPA)[17]进行功率分配。

3.1 仿真环境

根据GA的一般性规定[11]可设定小区中用户数K为[2,10,18,26,34]，最大遗传代数为30，NP=20，适应度函数中参数XRT=1.5，XNRT=1，XBE=0.5。物理层参数[8]见表1。根据式(1)计算Hk,n，其中路损采用密集市区模型，且

PLk=128.1+37.6 lgd，

其中d为用户k到基站的距离，单位为km,PLk的单位为dB；阴影衰落Shak，服从的对数正态分布，标准差σSha=8；多径衰落，建模为Lt=6的瑞利衰落多径，功率时延分布为[1, 0.60653, 0.36788, 0.22313, 0.13534, 0.082085]。

表1 物理层参数

给出IP语音(Voice over Internet Protocol, VoIP)和视频(Video) 两种RT业务、超文本传输协议 (Hypertext transfer protocol, HTTP)的NRT业务、文件传输协议(File Transfer Protocol, FTP)的BE业务的QoS参数，见表2。

表2 业务QoS参数

3.2 结果分析

MAX C/I只考虑CSI，RR不考虑CSI，且其中每个用户占用RB的机会相同，PF是MAX C/I和RR的折中，但以上三种算法均未考虑到业务QoS参数。M-LWDF是在PF基础上考虑了QoS中的时延参数，而GRA和SGA同时考虑到了QoS中的所有需求，本文算法则选择了特定的遗传算子。

图2为不同用户数下系统的吞吐量。可以看出随着用户数的增加，GRA优于RR和SGA，但小于MAX C/I、PF和M-LWDF；吞吐量基本趋于稳定。

图2 系统吞吐量

图3描述不同算法的公平性参数。测量公平性的数学标准公平性参数(Jain fairness index，JFI)[13]

其中Xk为用户k所分到的总的RB数。该算法公平性优于MAX C/I、M-LWDF，低于RR，略低于SGA。由各算法性质可知，MAX C/I吞吐量最大，公平性最小；RR吞吐量最小，但公平性最高；PF吞吐量和公平性均介于MAX C/I和RR之间；M-LWDF吞吐量和公平性均低于PF；而GRA吞吐量低于PF和M-LWDF，但高于SGA；公平性高于PF和M-LWDF，但略低于SGA。

图3 算法公平性

图4为RT业务下不同用户数的丢包率曲线。可看出各算法丢包率均小于RT业务QoS需求中的丢包率参数，且随着用户数的增加，丢包率呈指数型增长。MAX C/I、RR和SGA在丢包率较高且性能类似，PF和M-LWDF丢包率较低，但由于M-LWDF考虑到了时延参数，所以其丢包率低于PF。GRA考虑了更多的QoS参数，其丢包率较PF和M-LWDF要高，但低于RR、MAX C/I和SGA。丢包率和时延是相关的，由此可知对于RT业务，GRA提供了较小的时延。

图4 RT用户丢包率

图5为BE业务下不同用户数的系统吞吐量。可以看出对于BE业务，GRA提供了更大的吞吐量，且随着用户数的增加，增加幅度变缓。

图5 BE用户吞吐量

由以上仿真结果可知GRA相对于SGA算法，吞吐量增加和丢包率降低，公平性略微降低，总体性能有所提高；相对于经典调度算法，在吞吐量和公平性间进行了平衡，丢包率升高；相对于同样考虑了QoS的算法M-LWDF，公平性提高，吞吐量降低，幅度不大，同样丢包率升高。GRA在公平性和吞吐量上性能较好，在丢包率上有改进空间。

4 结 论

经过交叉、变异和以适应度函数值(利用了CSI和业务的QoS要求)为依据的选择操作，得到相对最优资源分配方案，同时由于遗传算子选择较为简单，计算量并未大幅增加。仿真结果表明该算法较大程度的保留了对优化目标较好的基因，有效的淘汰了差的个体。在满足用户QoS需求的情况下，得到了较大的吞吐量，并保持较高的公平性，且对于RT业务能提供较小的时延，同时对BE业务提供了更高的吞吐量，达到预期目标。

[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系统资源分配方法[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系统的自适应资源分配[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] 张玉才,沈元隆.遗传算法在计算机系统优化问题中的应用[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] 雷英杰, 张善文, 李续武, 周创明. MATLAB 遗传算法工具箱及应用[M]. 西安: 西安电子科技大学出版社, 2005: 43-65.

[15] 聂聪. 多用户OFDM系统动态资源分配算法研究[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