基于改进遗传算法的C-RAN网络动态无线资源分配*

徐东明，谭静茹，关文博

(1.西安邮电大学 通信与信息工程学院，西安 710121；2.西安电子科技大学 微电子学院,西安 710071)

0 引 言

云无线接入网(Cloud Radio Access Network,C-RAN)主要由分布式无线射频拉远部分(Remote Radio Head,RRH)、集中式基带处理池(Base Band Unit Pool,BBU)和连接两者的前传网络(Frounthaul)三部分构成[1]。不管是C-RAN基本特点的实现还是未来无线接入网络各种要求的满足，都离不开的主题就是对接入网络中各种资源的分配。目前国内外学者对C-RAN架构下的资源管理策略的研宄可分为两个方面，即基于RRH的无线资源分配和基于BBU池的计算资源分配[2]。在无线资源分配问题中，又分为一维资源分配与多维资源分配。当只考虑RRH中的单个无线资源优化时，文献[3]使用遗传算法(Genetic Algorithm,GA)研究了C-RAN中BBU和RRH之间的网络功能划分问题，通过合理的划分来降低C-RAN的运营成本。文献[4]研究了泊松到达的C-RAN网络中的呼叫阻塞概率，将RRH根据容量不同形成集群服务于网络中的泊松到达用户，通过卷积算法对阻塞概率进行分析。文献[5]研究了RRH的边缘缓存问题，提出了一种基于成本调度的方案来进行RRH处的缓存资源调度，以改善用户体验。在联合考虑多维无线资源优化时，文献[6]针对毫米波信道模型下的RRH的选择方案做了研究，基于RRH发射功率，覆盖范围和毫米波最大传输距离这三个约束条件得到了一个最优的RRH分配方案，提高了系统的能量效率。文献[7]提出了一种基于吞吐量感知的RRH聚类模型，提高了系统吞吐量，但对信道条件要求较高。

在服务质量(Quality of Service,QoS)约束的选择上，网络资源的低效利用往往导致负载失衡、呼叫阻塞事件增多和用户服务质量的下降。已有文献对C-RAN场景下QoS约束的考虑大多集中在中断概率方面，对系统时延研究较少。文献[8]考虑了时延约束和前传链路约束，文献[9]将包含处理时延和传输时延的队列模型按照M/M/1型串联在一起进行讨论。

在算法研究中，相较于传统的优化算法，群体智能算法对目标函数和可行域的要求更低，在操作上具有很高的可行性。遗传算法作为群体智能算法的一种，在通信领域的资源分配问题中常常被使用，算法的结果不依赖于初始值的选取，同时不会产生精度波动[10]。文献[11]提出将GA和多主体优化算法(Multi-agent Optimization,MAO)进行结合，最大限度地提高了云计算中的资源利用率。文献[12]提出了一种安全的嵌入式动态资源分配模型，并通过非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm,NSGA-II)提高了虚拟机在任务迁移和部署期间的安全性和资源分配效率。文献[13]使用粒子群优化算法(Particle Swarm Optimization,PSO)与GA研究了云计算中软件服务的自适应资源分配问题，在所提资源分配策略下，相较于传统遗传算法，PSO-GA算法能够在服务质量和资源成本之间能取得更好的折中效果。文献[14]研究了移动多用户通信系统中的中断概率，提出了基于增强灰狼算法的功率分配算法，同时与多种群体智能算法进行了对比，验证了所提算法的优越性。

基于以上研究，本文将C-RAN系统中的无线资源分配作为研究对象，运用改进遗传算法(Improved Genetic Algorithm,IGA)对具体分配方案进行了研究。本文主要贡献有：将RRH的无线资源映射为RRH选择、子载波分配、功率分配；在约束条件上，将用户请求的数据从处理到完成发送的总时延定义为QoS约束，并将时延队列用M/G/1型排队系统串联在一起进行研究，在QoS约束和系统传输模型下建立了以吞吐量最大化为优化目标的优化问题，对三种维度的无线资源进行了合理的分配；在算法选择上，由于目标函数是非线性的，优化问题是一个NP-hard问题，因此提出了IGA算法，将RRH选择、子载波分配、功率分配作为染色体的三个部分的分配进行了优化，从而达到提高吞吐量的目的。

1 系统模型与问题建立

1.1 系统传输模型

图1 C-RAN系统架构

由于无线信道传输存在不稳定性，信息传输时的瞬时速率并不能总保持一个稳定值。为了提高算法的稳定性，本文在后续仿真中设定信道环境为完美信道状态信息(Channel State Information,CSI)，在所有信息传输过程中速率为一均值。RRH与BBU池通过一个理想光纤链路进行连接，由于信号通过光纤传输时损耗很小，因此对所有传输链路来说，噪声功率谱密度N0是相同的。

(1)

根据香农公式，用户m的可达速率为

(2)

1.2 系统QoS约束

图2 M/G/1型排队系统

(3)

根据上述公式，当t→∞时，系统平均剩余服务时间为

(4)

当第m个用户连接第k个RRH时，平均等待时间为

(5)

在系统QoS约束的前提要求下，用户在队列中的传输时延和处理时延必须低于其能够等待的最大时延，即

(6)

1.3 系统优化问题建立

在C-RAN网络中，系统的吞吐量之和为

(7)

(8)

在一个时隙τ中，为了限制UEm与RRHk之间一一对应的映射关系，子载波分配应满足

(9)

(10)

根据前文中提到的条件，目标函数可以表示为

(11)

式中：C1为QoS约束，C2为子载波分配情况，C3为系统最大发射功率约束，C4表示一个子载波只能分配给单个用户，C5为最小传输速率限制。

2 算法设计

C-RAN网络中无线资源的存在形式与种类多种多样，如何将这些资源进行更加有效的分配，是一个具有不确定性和复杂性的问题。特别是在优化过程中，如何提高系统利用率、联合考虑多重无线资源、克服信道条件以及无线传输的不稳定性，使用传统的数学工具已经不能精准解决如上问题。

遗传算法(Genetic Algorithm,GA)由美国计算机学家Holland提出，它的主要思想是用生物进化理论模拟自然选择和遗传机制的进化过程，并进行数学建模，寻找科学研究中疑难问题的解决方案。经过Goldherg等人的总结与改进，最终发展成一种启发式算法。参数编码、设定初始群体、设计适应度函数、设计遗传操作、控制参数等则构成遗传算法的核心要素。

本文对遗传算法进行改进，将RRH选择、子载波分配、RRH功率分配同时优化，以达到原优化方案中最大化吞吐量的优化目标。

2.1 编码与产生初始群体

编码是遗传算法首要的解决问题，为了克服常用的二进制编码的固有缺陷，即编码的精确度和普适度，本文采用实数编码，避免了编码的复杂性，缩短了染色体的长度，提高了计算效率。本文将系统中无线资源分配次数的集合作为改进遗传算法中的种群，一次无线资源的分配作为一个个体，每个个体的染色体由三部分构成，包括RRH选择、子载波分配、RRH功率分配，每个染色体的基因值为其资源分配的结果。

2.2 适应度函数设计

适应度函数能够反映种群里所有个体对环境的适应性。简而言之，决定一个个体能否生存并将基因繁衍到下一代的因素就是其适应度值的大小。传统遗传算法一般将目标函数f(x)设为种群的适应度函数Fitness(x)，由于这种构造方式可能产生负的适应度值，不能满足轮盘赌算子中非负适应度的条件[16]，因此对适应度函数进行改进。本文中优化目标为系统总吞吐量最大，所以算法的适应度函数为

(12)

2.3 选择操作

在遗传算法中，轮盘赌算子是一种常用的选择方法，它的缺点是容易导致早熟现象，因此对选择操作进行改进。

首先,采用保留最佳个体算子，使得包含优良基因且适应度值排名前5%的个体被保留[17]，让其直接演化到下一代；其次，采用轮盘赌算子，将其余适应度相对较高的个体通过轮盘赌进行选择，随后将它们复制并随机与两个亲本染色体进行之后的操作。本方案可直接减少拥有优良基因的劣势个体被淘汰的概率，使种群能够更加适应生存环境。

个体i被选择的概率为

(13)

个体i的累计概率为

Oi=∑Pi。

(14)

式中：Fi为个体i的适应度值，Q为种群规模。

2.4 交叉操作

经典的交叉算法在交叉过程中容易产生局部极小，因此本文提出新的交叉算子。

首先对RRH选择、子载波分配提出多点简单交叉算子。算法首先产生一个长度为2M的屏蔽字，其中每个元素由等概率的0和1构成，前M个元素对应RRH选择，第M+1～2M个元素对应子载波分配，当元素值为1时，相对应的两个染色体的基因以交叉概率Pc进行交叉，为0时保持不变。对于功率分配提出多点非均匀算数交叉算子。首先产生一个长度为M的屏蔽字，其中每个元素由等概率的0和1组成并分别对应功率分配的每一个基因。当元素值为1时，两个相对应点的父代基因值以交叉概率Pc进行交叉得到新的子代基因，为0时保持不变。该交叉算子产生新的子代染色体方法为

childXi=r×parentXi+(1-r)×parentYi，

(15)

childYi=r×parentYi+(1-r)×parentXi。

(16)

式中：r为[0,1]之内的均匀随机数。

图3为M=6、N=4、K=4、r=0.4时改进的交叉操作过程。其中，RRH选择、子载波分配的亲本基因值具体参数从[1,2,3,4]中随机选取，RRH功率分配的亲本基因值具体参数从(0，1)中随机选取。由于RRH选择和子载波分配均采用同一交叉算子，因此图中RRH选择部分的交叉过程同样适用于子载波分配，只不过两者随机所产生的屏蔽字序列有所不同。

图3 交叉操作

2.5 变异操作

在遗传学中，变异指基因突变导致新染色体的产生和新性状的获得。常见的变异算子都有两个不确定性：一方面，当前种群中拥有最高适应度值的基因可能会进行突变，从而破坏了目标函数的最优解；另一方面，当前种群中适应度值较低的一些基因可能不会做任何变异，从而不能改善种群的多样性，并容易导致种群早熟。为此，提出新的变异操作。

对于RRH选择和子载波分配部分，首先设置一个2×1的屏蔽字，其由等概率的1和0产生并且分别对应RRH选择和子载波分配，元素值为1时，随机选择2个基因值以变异概率Pm=0.001进行变异，否则不变。对于功率分配部分，文献[18]提出了一种粒子群变异算子，实验表明该变异算子展现了良好的局部搜索能力。本文依照实际进化要求对其做了调整，首先将当前种群中的所有基因按照适应度大小排序，然后只对适应度较低的基因以变异概率Pm=0.001进行变异。具体计算公式如下：

(17)

图4 变异操作

2.6 终止

循环执行选择、交叉、变异的工作，直到种群数量达到设定值Q，选择第G代中适应度值最高的染色体个体，其各部分的基因值即为使吞吐量最大的RRH选择、子载波分配和RRH功率分配。

改进的遗传算法伪代码如下：

Step1 产生初始群体

For(i=1 to MaxGeneration)do

G=(RRH Selection,Subcarrier Allocation,Power Allication)

Step2 计算适应度值

Calculate all fitness values according to the formula(12)

Step3 选择操作

Keep the high fitness vales individuals from population

Step4 交叉操作

for(j=1 to PopulationNumber/2*Cross Rate)do

choose two individualsXandY；

(X′,Y′)=Crossover(X,Y)；

Calculate the new fitness values；

end for

Step5 变异操作

for(j=1 to PopulationNumber*Mutation Rate)do

choose two individualsX；

X′=Mutation(X)；

Calculate the new fitness values；

end for

Step6 终止条件判断

if(i=MaxGeneration)break；

else

i+1；

end if

end for

Output：MaxThroughput

3 数值仿真与结果分析

3.1 仿真参数设计

为了验证所提无线资源分配算法有效性，本节使用Matlab仿真平台进行数值仿真，具体仿真参数[19-20]如表1所示。

表1 仿真参数

3.2 仿真结果分析

3.2.1 算法复杂度

本文以种群规模为变量，在时间复杂度上将IGA算法同差分进化算法(Differential Evolution,DE)、GA算法、PSO算法、文献[7]算法进行了比较。从图5中可以看出各个算法的复杂度排序依次为DE>GA>文献[7]>IGA>PSO，本文算法复杂度相对较低。

图5 算法时间复杂度对比

3.2.2 算法稳定性

在实验过程中，设置交叉概率pc=0.8，变异概率pm=0.001，系统吞吐量与种群演化代数G的关系如图6所示。从图中可以看出，在种群规模不变的情况下，吞吐量随着演化代数的增加而逐渐增大。这是由于演化代数越多，与前一代种群相比，后一代种群的优良个体总是更加容易生存，进而增加系统吞吐量。在演化代数固定时，吞吐量随着种群数量的增加而增加。这是由于种群数量越大，优良个体的数量就越多，所求次优解就越接近于最优解。同时，不论种群规模如何变化，当种群演化到G=200时，吞吐量基本趋于稳定，表明算法具有很好的稳定性。因此，在后续的仿真中，设置最大演化代数G=300，种群规模Q=200。

图6 系统吞吐量和种群演化代数的关系

3.2.3 吞吐量

由图7可见，随着RRH数量的增加，系统吞吐量也在大幅增加。这是由于当安置更多RRH时，RRH将分别与BBU和用户端进行更多的信息交互，提高系统的吞吐量。在RRH数量较大时，本文所提算法达到的系统吞吐量高于文献[7]，且后者对信道条件与路网状况要求较高，在实际情况中难以达到其实验值。在本文算法下，当RRH数量为30时仿真得到系统吞吐量为291 Mb/s，文献[7]吞吐量为232 Mb/s，此时吞吐量增益为25%。

图7 系统吞吐量和RRH数量的关系

图8给出了系统吞吐量和子载波数量的关系，可以看出，子载波数量一定时，本文所提算法明显比已有算法更能使系统吞吐量增大。子载波数量较少时，系统吞吐量与子载波数量呈正相关。这是由于子载波数量的增加提高了系统传输速率和频谱资源分配的灵活度，使得传输质量增加，因此吞吐量增大。当子载波超过一定数量时，系统吞吐量将逐渐趋于平稳。这是因为RRH可传递的信息容量有限，无法利用剩余的子载波和用户进行信息交互，所以吞吐量不再增大。当子载波数量相同且吞吐量趋于平稳时，此时系统吞吐量为233 Mb/s，文献[7]算法所得吞吐量为199 Mb/s，吞吐量增益为17%。

图8 系统吞吐量和子载波数量的关系

从图9可以看出，RRH发射功率较低时，系统吞吐量随RRH发射功率的增加而增加，而当RRH发射功率继续增加时，系统会接入更多的可服务用户，使得部分RRH处于超负荷状态，会增大用户队列的等待时延，降低传输速率，因此系统吞吐量减小。当RRH发射功率达到峰值时，吞吐量为142 Mb/s，文献[7]算法所得吞吐量为130 Mb/s，吞吐量增益为9%。由此可以得出整个系统的平均吞吐量增益为17%，同时也很容易得出，当RRH发射功率和子载波数量受限时，可以通过部署更多的RRH来提高系统的吞吐量。

图9 系统吞吐量和RRH发射功率的关系

4 结束语

本文在C-RAN网络下行链路场景下针对动态无线资源分配提出了基于QoS约束分配方案，将时延队列用M/G/1型排队系统串联在一起进行研究，运用改进的遗传算法，联合考虑了对RRH选择、子载波和RRH发射功率的分配问题。实验结果验证了本文提出的动态资源分配方案明显提高了C-RAN系统的性能，缓解了最优信道分配方案的饥饿现象。同时结果也表明，RRH数量是对系统吞吐量影响最大的一种无线资源。

本文分配方案对于较小的网络规模可以得到最优解，网络规模较大时，由于C-RAN网络没有接入智能电网，因此还需考虑整个网络中的电能消耗以及支出成本等因素。此外，对于大规模用户的C-RAN网络场景有待进一步的研究。