基于混合遗传算法的OFDMA资源分配方法

孙 明，翟康乐，曹 伟，张 辉

(齐齐哈尔大学计算机与控制工程学院，黑龙江 齐齐哈尔 161006)

1 引言

在过去的二十年中，随着手机等电子设备的逐渐普及，人们对无线网络有了更高的需求。但频谱资源作为无线资源的稀缺资源早已成为不争的事实，因此，如何高效利用频谱资源已成为无线通信技术的重要研究内容。

正交频分多址(Orthogonal Frequency Division Multiple Access，OFDMA)[1，2]是一种多址接入技术，它是将高速传输的数据带宽划分成相互正交、互不重叠的低速传输的子载波集，能够动态将子载波分配给需要的用户并有效降低信号间的干扰[3]。目前，在速率自适应(Rate adaptive，RA)准则上，多用户OFDMA系统自适应资源分配中的系统速率和用户间公平度已经有若干成果[4-11]。例如，Shen等[8]提出的算法在实现最大化系统速率的同时也保证了速率比例的公平，仿真结果表明该算法几乎实现了绝对公平，但忽略了系统速率的提升。Wong等[9]基于Shen的算法提出了一种通过近似速率比例系数来提升系统速率的分配算法，然而该算法却牺牲了部分公平度；在Wong的基础上，袁建国、汪照等通过对功率分配采用人工蜂群算法[4]或鱼群算法[7]进一步提高系统速率。虽然文献[4，7，9]通过牺牲公平度的方式提高了系统速率，但都无法保障所要求的用户间比例公平。

设置公平度阈值可实现公平度和系统速率的折中，能够在保证公平度的同时有效地提高系统速率和系统灵活性[6，10，11]。例如，张春发等[6]基于公平度阈值在等功率子载波分配阶段对子载波采用贪婪算法进行分配，再对其功率采用粒子群算法进行分配，来保证系统的公平度阈值；然而由于粒子群算法的“早熟”，基于粒子群算法的功率分配极易降低系统的速率水平[12]。Sharma等提出一种人工蜂群算法[10]和遗传算法[11]对子载波进行分配的算法，该算法能够从全局寻优对子载波进行分配；然而，该算法随着子载波数量的增加，需要优化的维度也随之增加，增加了优化问题的难度，极易降低优化性能。

针对以上不足，本文提出一种基于混合遗传算法的OFDMA资源分配方法，该方法将基于速率比例公平的贪婪子载波分配方法有效地嵌入遗传算法中，实现了贪婪算法局部寻优能力和遗传算法全局寻优能力的有机结合。所提出的方法不仅能使种群个体在初始化时具有一定的公平度水平，还能有效减少个体待优化维度的数量并降低了计算复杂度。仿真结果表明，所提出的方法可在子载波分配阶段就能满足公平度阈值，而且还能有效提高系统速率。

2 系统模型

本文考虑如图1所示的下行多用户OFDM系统模型。在发送端，通过用户信息和对K个用户的信道估计来获取实时信道状态信息(CSI)，再利用自适应资源分配方法对各个子信道进行分配来获得不同用户的分配信息，并将信息进行OFDM调制发送到接收端，接收端利用自适应解调器对信息进行解调来得到相应信息。

图1 下行多用户OFDMA系统

假定某OFDMA系统共有K个用户和N个子载波，总的可用功率为Ptotal，且所有子载波的瞬时增益都是已知的。

系统在满足总功率约束的条件下，对子载波进行分配以最大限度的提高总容量。其中用户k的容量Rk为

(1)

RA准则下的系统容量最大化可表示为

(2)

并受以下条件约束

(3)

其中hk，n为信道增益，N0为加性高斯白噪声的功率谱密度，B为总信道宽度。C1表示子载波的功率和不超过总的可用功率Ptotal；C2表明每一个子载波分配的功率必须大于等于0；C3中ρk，n∈{0，1}表示该子载波是否分配给用户；C4表示同一个子载波只能分配给一个用户；C5表示公平度阈值约束。F为公平度计算公式；ε是公平度阈值；λk是用户k的预定数据速率比例值。F的变化范围从0到1，F的值越接近于1表示用户之间的公平度越大。如果式(4)严格成立，则F等于1。

R1：R2：R3：…：Rk=λ1：λ2：λ3：…：λk

(4)

由式(2)和式(3)可知，以上问题为一个非凸优化问题。本文将贪婪算法嵌入遗传算法中，提出了一种混合遗传算法，通过贪婪算法为遗传算法个体维持一定的公平度水平、减少遗传算法的搜索维度，以降低遗传算法的计算复杂度、提高遗传算法的优化性能。

3 基于混合遗传算法的OFDMA资源分配方法

遗传算法是一种模仿大自然生物体进化规律的启发式算法，其中一个种群个体对应一个优化问题的解，而种群个体不断进化的过程对应于优化问题的求解过程，将遗传算法用于子载波分配时，种群个体的维度大小由子载波的数量决定；然而，规模较大的子载波分配无疑会增加遗传算法优化的难度，进而降低优化解的质量。

为了使遗传算法能有效保障公平度阈值并提高OFDMA系统的子载波利用率和系统容量，本文基于速率比例公平的贪婪子载波分配方法可获得较高公平度的特点，将基于速率比例公平的贪婪子载波分配方法用于遗传算法的个体初始化上，提出了一种保障公平度阈值的基于混合遗传算法的资源分配方法，即首先对种群个体进行分组并为个体分组设置个体更新量，并在此基础上采用基于速率比例公平的贪婪子载波分配方法初始化种群个体，然后再利用所设置的个体更新量，对个体的相应维度进行搜索和更新。

本文所提出的保障公平度阈值的混合遗传资源分配算法包括种群个体初始化，个体的适应度计算，选择复制阶段，交叉变异阶段，基因突变阶段，最优个体储存等部分，现对每一部分进行阐述。

3.1 种群个体初始化

根据系统中子载波的数量N，本文将种群个体定义为维度H等于N的向量，即H=N。记V为种群的大小，xi为第i个种群个体，xi，h为第i个种群个体xi在维度h上的元素，其中xi，h∈[1，K]，i∈{1，2，…，V}，h∈{1，2，…，H}。

本文将种群个体初始化分为以下3步：

Step 2.2：

n=arg maxn∈Γ{|hk，n|2}，

Rk=Rk+log2(1+pT|hk，n|2/(N0B))，

Γ=Γ-{n}，k=k+1；}

Step 2.3：

k=arg mink∈{1，2，…，K}{Rk/λk}，

n=arg maxn∈Γ{|hk，n|2}，

Rk=Rk+log2(1+pT|hk，n|2/(N0B))，

Γ=Γ-{n}。}

(5)

式中，km∈{1，2，…，K}，nm∈{1，2，…，N}。

(6)

3.2 种群的适应度计算

由于所要求解的多用户OFDMA资源分配问题(6)-(9)是约束优化问题，因此设计的适应度函数需要考虑满足约束的可行解和不满足约束的非可行解，并能够引导遗传算法从不满足约束的非可行解空间过渡到满足约束的可行解空间。同时，设计的适应度函数应该遵循较好解具有较大适应度的原则。基于上述考虑，本文构建的适应度函数如式(7)：

(7)

其中，F(xi)是种群个体xi的适应度；x′i是对种群个体xi的元素进行四舍五入后得到的向量；f(x′i)表示为

(8)

其中，fr为一正常数；β(·)=F-ε为公平度阈值约束函数；Xi表示由向量x′i转换得到的K行N列的子载波分配矩阵，由向量x′i到矩阵Xi的转换如式(9)所示

(9)

图2 种群个体初始化结果示意图

其中[Xi]k，n为子载波分配矩阵Xi的第k行、第n列的元素，[x′i]n为向量x′i在维度n上的元素。Ζ(Xi)如式(10)所示

(10)

首先，由式(7)、(8)可以看出，满足公平度阈值约束的可行解和不满足公平度阈值约束的非可行解通过式(8)影响适应度函数式(7)，且满足公平度阈值约束的可行解的适应度值大于不满足公平度阈值约束的非可行解的适应度值；其次，由(7)、(8)、(10)不难发现，在满足公平度阈值约束的可行解中，较好的可行解有较大的系统容量，且较好的可行解有较大的适应度值；最后，由式(7)、(8)可以发现，在不满足公平度阈值约束的非可行解中，与较劣的非可行解相比，较好的非可行解也具有较大的适应度值。以上分析说明所设计的适应度函数(7)-(10)体现了较好解具有较大适应度的原则，从而有利于引导遗传算法从不满足公平度阈值约束的非可行解空间过渡到满足公平度阈值约束的可行解空间，并能在满足公平度阈值约束的可行解空间中搜索得到较好的可行解。

3.3 选择复制阶段

在选择复制阶段，首先通过式(7)-(10)计算各个种群个体的适应度函数F(xi)，然后根据个体的F(xi)值从大到小排序并选择前H/2个种群个体作为亲代以轮盘赌的方式选择复制生成V个种群个体，其中个体被选择复制概率P(xi)，如式(11)所示

(11)

3.4 交叉变异阶段

如果rn≥pc，执行：

否则，执行

图3 以图2种群个体3和12为例的个体搜索的计算和更新示意图

3.5 基因突变阶段

在基因突变阶段，种群个体中待优化的个体维度通过突变概率pm的调整，小范围内进一步搜索的计算和更新，如式(12)所示

(12)

3.6 最优个体储存

在基因突变阶段后，从种群中找出适应度最大的种群个体，并将该个体保存为当前的最优解。并判断遗传算法当前的迭代数Cycle是否等于最大迭代数Maxcycle，若等于则停止计算并输出最优解及其对应的公平度与系统和速率；否则令Cycle=Cycle+1，并转入选择复制阶段继续执行。

由以上步骤可知，本文所提出的混合遗传算法有效地结合了贪婪算法的局部寻优和遗传算法的全局寻优，因此，与遗传算法和贪婪算法相比，本文所提出的算法具有寻优能力强、灵活性高等特点。

4 仿真与分析

仿真中假设多用户OFDMA系统的无线信道采用瑞利衰落信道，信道带宽B为1M Hz，噪声的功率谱密度N0为10-8W/Hz，子载波数N为64，基站总发射功率Ptatol为1W。为了减少样本误差对算法性能的影响，本文不同用户K产生200个不同的样本实例，并取其均值比较各种算法的性能。

为了验证本文提出的算法具有保障公平度阈值的同时提高系统速率的能力，将公平度阈值ε设置为0.96，并将本文所提出的遗传算法(Proposed HGA)、Sharma等的遗传算法(GA)和人工蜂群算法(ABC)、张春发的粒子群算法(PSO-EQ)以及Wong的贪婪算法(Wong)用于资源分配当中去，其中算法Wong没有设置公平度阈值。遗传算法的参数设置为种群大小V=40、fr=1、交叉概率pc=0.7、基因突变概率pm=0.01、最大迭代数为1000，种群个体的分组V′=6，对应的个体更新力量分别为1、4、6、8、10、12；速率比例系数λ1：λ2：…：λK分别为1：1：…：1、8：1：…：1、16：1：…：1，用户数K由6逐渐增加到16。

图4 当公平度阈值ε=0.96且速率比例系数λ1：λ2：…：λK=1：1：…：1时各算法的公平度与和速率

由图4、图5和图6可知随着用户数的增加，相比于各个算法，本文所提算法(Proposed HGA)不仅公平度始终稳定在公平度阈值之上，而且系统速率始终大于其它各算法，这说明了本算法具有较强灵活性和寻优能力，有效提高了子载波的利用率；其中，算法Wong对等功率子载波采用贪婪算法进行分配，因而无法保证公平度，造成其公平度曲线有较大的震荡起伏现象；算法PSO-EQ由于其子载波分配阶段所采用贪婪算法的局限性，以及PSO在功率分配上的“早熟”，导致其无法产生较高的系统速率；算法ABC-OSA、GA随着速率比例系数的提升，逐渐无法达到公平度阈值，且容量也无法进一步提升，说明简单地将ABC-OSA、GA算法应用到子载波分配无法有效地提高系统性能。

图5 当公平度阈值ε=0.96且速率比例系数λ1：λ2：…：λK=8：1：…：1时各算法的公平度与和速率

图6 当公平度阈值ε=0.96且速率比例系数λ1：λ2：…：λK=16：1：…：1时各算法的公平度与和速率

为了体现在较高公平度阈值时本文所提算法依然具有良好性能，图7和图8中给出了本算法在公平度阈值为0.99、用户数K=8、以及λ1分别等于1、8、16时与各个算法的公平度和系统速率的比较。通过与各算法比较可知，随着速率比例系数λ1的提升，算法ABC和GA的公平度逐渐达不到公平度阈值，系统速率也逐渐降低；算法PSO-EQ始终满足公平度阈值，但系统容量却没有显著的提高；而本文所提出的算法满足公平度阈值的同时依然能保持良好的寻优能力，并有效提高对子载波的利用率。主要原因是，本文所提出的混合遗传算法能够充分利用贪婪算法局部寻优和遗传算法全局寻优的优点，既能保障种群个体有较高的公平度水平，又能降低了待优化的个体的维度数量，从而以利于提高子载波利用率和系统容量。

图7 当公平度阈值ε=0.99时各算法的平均公平度

图8 当公平度阈值ε=0.99时各算法的平均系统和速率

5 结论

为了保障公平度阈值、提高子载波利用率和系统容量，本文提出了一种基于混合遗传算法的资源分配方法，所提出的资源分配算法充分利用了贪婪算法在局部寻优和遗传算法在全局寻优的优点，既保障种群个体有较高的公平度水平，又降低了待优化的个体的维度数量，有利于提高子载波利用率和系统容量。仿真结果表明，所提出的算法能够在等功率的子载波分配阶段即可实现所要求的公平度阈值并能有效地提升系统容量。