5G通信组播传输分组策略与资源分配算法研究

张文倩 倪 菊 刘小兰 毛淑霞 肖海林

1(桂林电子科技大学信息与通信学院 广西 桂林 541004)2(桂林电子科技大学图书馆 广西 桂林 541004)

0 引 言

新兴的第五代(5G)无线通信系统通过高数据速率、低延迟和巨大的网络灵活性等特点来满足用户需求[1]。在5G多媒体数据传输场景下，为同时向大量观众发送信息，组播技术成为5G系统的关键技术之一，其通过点对多点(Point-to-Multipoint，PtM)同时将数据传输到一组终端进行通信，减少点对点单播传输机制带来的资源消耗，提高蜂窝系统的频谱效率[2]。

然而，组播传输的可达数据速率受信道条件最差用户的数据速率限制，导致较低的系统吞吐量[3]。近年来，一些文献对组播传输速率受限问题展开研究。文献[4]提出一种机会主义方案，该方案通过服务信道质量最好的组播用户，来平衡组播增益。文献[5]对文献[4]进行改进，提出了一种基于自适应用户选择的机会组播调度方法，通过自适应地选择最优用户比例，提高吞吐量。以上文献均是采用单速率来进行组播传输，虽然保证了一定的公平性，但频谱效率低。文献[6]提出了一种多速率方案，将组播用户划分为更小的子组来提高系统容量。一般的随机分组方法将用户随机划分为若干组，算法易实现，但组内用户接收数据的能力差异较大，系统整体性能较低。文献[7]提出一种低复杂度的联盟博弈理论，通过用户与其他用户自主联盟来形成子组。文献[8]提出一种固定组大小的分组方法，该方法根据SNR值对用户进行分组，但需要人为设定组播组的个数，若组播组个数设定不合理，会影响组播系统的整体性能。

尽管以上文献采用分组策略来提升组播系统吞吐量，但并未考虑资源的充分利用。在这基础上，正交频分多址(Orthogonal Frequency Division Multiple Access，OFDMA)被提出并广泛应用于组播系统，以灵活管理频谱资源[9]。基于OFDMA技术，文献[10]提出一种基于低复杂度子组的资源分配方案，在保证系统容量最大化前提下，通过调整系统性能函数来选择不同的调度策略。文献[11]提出一种约束团队进化算法实现每个组的子载波分配。事实上，组播组的资源分配问题是非确定性多项式约束优化问题，求解难度为NP-hard，虽然通过穷举法可以获得最优解，但其复杂度随着问题规模的增大而呈指数增长。精确算法在求解该类问题时，求解效率低、运行速度慢，在实际中往往不可行。相比之下，智能算法能够全局寻优， 可以在较短时间内求得大规模问题的可行解， 因此成为了非确定性多项式约束优化问题的主要求解算法[12]。

近年来，一些智能算法被广泛地应用于子载波分配[13]。文献[14]利用遗传算法进行子载波分配，将子载波分配变量映射为染色体上的基因，系统吞吐量转化为染色体的适应度函数。该方法较传统组播机制提高了系统吞吐量，但算法效率低且易陷入局部最优值。文献[15]采用粒子群算法进行子载波分配，该算法所需参数较少且收敛速度快，过程较易实现，但其种群收益所对应的系统吞吐量较低[16]。人工鱼群算法(Artificial Fish Swarm Algorithm，AFSA) 是一种基于动物行为的群体智能优化算法，用于解决非确定性多项式约束优化问题，在参数估计、神经网络训练和组合优化中得到广泛的应用，具有很强的鲁棒性。并且人工鱼群算法对初始值和参数的选择要求不高，简单易操作，收敛速度快，能使搜索行为跳出局部最优点，获得全局最优解[17-18]。文献[19]采用人工鱼群算法来解决非确定性多项式约束的能源优化问题，利用人工鱼群算法的全局搜索能力，获得全局最优解。

综合以上考虑，本文提出一种动态聚类分组策略与子载波分配方法，该方法将组播用户通过SNR值自动分成合适数量的组。并在该分组策略下，采用改进的人工鱼群算法进行子载波分配，将子载波分配变量映射为人工鱼的位置，系统吞吐量转化为人工鱼在某一位置的食物浓度进行迭代寻优，以最大化系统吞吐量。

1 模型分析

1.1 系统模型

信道模型包括大尺度衰落模型和小尺度衰落模型，因此，第k个用户在子载波n上的信道增益可表示为[21]：

(1)

式中：Dk为用户k到基站的距离；α为路径损耗因子；φk,n为用户k在子载波n上服从对数正态分布的阴影衰落；φk,n为用户k在子载波n上服从瑞利分布的多径衰落。用户k的接收信噪比表示为：

(2)

图1 组播系统模型

1.2 问题建模

为了保证组内所有用户都能成功解码接收信号，基站被限制使用最低的数据速率，通常由最低的信道增益来决定[7]，则组播子组s的信道增益可表示为：

(3)

式中：Hk,n为第k个用户在子载波n上的信道增益。用户k在子载波n上的数据传输速率表示为：

rk,n=wlog2(1+η)

(4)

式中：w为每个子载波的带宽。第s个组播子组在子载波n上的数据传输速率如下：

(5)

根据组播系统吞吐量的定义[14]，组播系统总吞吐量可表示为：

(6)

式中：αs,n为二进制变量，αs,n=1表示第n个子载波分配给第s组，否则αs,n=0。因此，本文构建的系统优化问题表示如下：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(8)表示用户k是否分配到组播子组s；式(9)表示子组s是否分配了子载波n；式(10)表示每次只能将特定的用户分配给一个子组；式(11)表示每次只能将特定的子载波分配给一个子组；式(12)表示属于不同组播子组的两个用户不能分配到相同的子组中。式(13)表示系统所消耗的子载波数不超过系统子载波总数。式(14)表示基站向每个组播子组传输数据速率须大于等于子组的最小数据速率，其最小数据速率Rmin为1 Mbit/s[8]，保证组内用户正确解码。

从式(7)可以看出，这是一个非线性约束规划问题，求解复杂度较高。因此本文将式(7)问题转换为组播用户分组和子载波分配两个子问题，从而求得次优解。

2 组播分组策略与子载波分配方法

2.1 基于最大最小距离K-means组播分组

本节采用最大最小距离K-means聚类算法[22]对组播用户进行分组，分组算法的思想是根据用户反馈给基站的信噪比值将相近或者相同的信噪比尽可能地分在一组，实现组播用户分组。本节的优化目标是最大化组播系统的可达速率，其由组播子组的容量及组播子组的个数共同决定，通过分组策略将其分为合适的组播子组，即该优化目标等价于最大化子组内用户的最小数据速率[23]。因此，可建立组播分组子问题P1如下：

(15)

s.t. 式(8),式(10),式(12)

基于最大最小距离K-means算法进行组播分组的步骤如下：

(1) 初始化参数。基站通过用户反馈的信道状态信息获得k个用户的信噪比η，这些信噪比η组成的样本数据集为M={x1,x2,…,xk}。

(2) 随机选取任意一个样本Z1=x1作为第一个聚类中心，并选取距离Z1最远的样本数据Z2作为第二个聚类中心。

(3) 计算剩余样本数据到现有初始聚类中心的距离di,1,di,2,…,di,k′，找出其中最小值di。

(4) 从所有最小值中找到最大值Dmax。

(6) 若不满足步骤(5)，则k=k′。

(7) 计算剩余样本与k个初始聚类中心的距离，使每个样本分配到距离聚类中心最近的组中。

2.2 人工鱼群算法求解子载波分配问题

(16)

(17)

(18)

(19)

(20)

式(17)表示子组是否分配了子载波n；式(18)表示只能将特定的子载波分配给一个子组；式(19)表示系统所消耗的子载波数不超过总载波数。式(20)表示基站向每个组播子组传输数据速率须大于等于子组的最小数据速率，其最小数据速率Rmin为1 Mbit/s[8]，保证组内用户正确解码。

子问题P2的目标是求解子载波分配矩阵A，由于分配矩阵A受到式(17)-式(20)的限制，则产生的分配矩阵必须满足约束条件。首先若对整个A进行求解，求解维数为G×N，求解维数过高降低了求解速度。为了降低求解复杂度，本文采用文献[24]提出的编码方式作为人工鱼的位置编码方式。如图2所示，构造一个G=5、N=8的子载波分配模型。L中有9个值为1的元素，检查L的第i行n列，以及L的第c行n列是否有多个1元素。如果是，则随机将其中为1的元素置0，仅保留一个为1元素，形成L1。然后按先行后列的顺序抽取对应L1中值为1的元素位置的A中元素进行编码，得到编码解行向量X(xi∈{0,1})，使用编码解行向量X进行优化。之后，再将优化后的行向量X按照L1中先行后列的顺序还原成分配矩阵A。

图2 人工鱼的编解码结构

分配矩阵A所对应的解的优化长度D，由L1中1元素的个数决定。假设人工鱼的数目为P，则每条人工鱼将分布在一个D维空间。每条人工鱼代表优化问题的一个解，人工鱼的位置对应一种子载波分配方式，以Xi=(xi1,xi2,…,xiD)代表第i条人工鱼的当前位置。该人工鱼在某一位置的食物浓度为目标函数，在寻优过程中，搜索到某一位置的人工鱼食物浓度最大，则该位置所对应的解为最优的子载波分配方式。

基于人工鱼群算法求解βg,n的步骤如下：

1) 初始化算法各参数：人工鱼群大小P，可视范围v，拥挤度因子d，迭代次数m，移动步长st，人工鱼每次觅食最大试探次数t。

2) 依据人工鱼的编码结构，产生可用子载波分配矩阵L1来确定优化维数D，然后随机产生人工鱼向量Xi=(xi1,xi2,…,xiD)，i=1,2,…,P。

3) 根据式(16)计算每条人工鱼的食物浓度Yi，即系统总吞吐量。每次迭代后，选出最大的食物浓度值，其对应的人工鱼位置为当前最优人工鱼位置，并将最优的人工鱼位置BX及其值赋予公告板。

4) 人工鱼的行为定义：

(1) 觅食行为：在人工鱼Xi的可视域内随机选择一个状态Xj，其表示如式(21)所示，记录其食物浓度为Yj。若YiYj，则采用式(23)进行随机搜索。

Xj=Xi+v·rand()

(21)

(22)

Xnext=Xi+st·rand()

(23)

式中：rand()表示产生随机数的函数。

(2) 聚群行为：对人工鱼Xi的有效区域进行搜索，记录其邻居的其他人工鱼Xj个数nf。若nf>0，计算有效搜索区域内的中心位置为Xc，其表示如式(24)所示，计算相应食物浓度为Yc。若Yc/nf>dYi，则人工鱼向最大食物浓度的位置移动执行式(25)；否则执行觅食行为。

(24)

(25)

(3) 追尾行为：对人工鱼Xi的有效区域进行搜索，记录其邻居的其他人工鱼Xj个数nf。若nf>0，找到其中食物浓度最大的人工鱼Xmax，计算最大食物浓度Ymax。若Ymax/nf>dYi，则人工鱼向最大食物浓度位置移动，执行式(26)；否则执行觅食行为。

(26)

5) 对人工鱼个体Xi分别进行觅食、聚群、追尾和随机行为，通过行为评价，选择执行食物浓度较大的行为。

6) 通过择优后得到人工鱼向量Xi，并且将公告牌更新为该个体BX。

7) 若达到最大迭代次数m或公告牌上最优解达到满意误差界内，算法结束，由BX逆映射回βg,n；否则转到步骤5)继续进行。

2.3 算法复杂度分析

若对每个组播组用户直接进行子载波分配求解目标函数，计算复杂度为O(GN)，其需要对所有种组合情况进行分析以找到最优解。随着组播用户规模增大，其复杂度呈指数增长，复杂度较高。文献[14]采用遗传算法求解，计算复杂度为O(PGNK)，其复杂度呈线性增长。本文采用人工鱼群算法求解目标函数时，每条人工鱼执行一次觅食行为、聚群行为、追尾行为时最多计算t次系统吞吐量，所以人工鱼群算法在求解最优解时计算复杂度为O(3Pmt)，复杂度较低。

3 仿真结果与分析

3.1 仿真参数

仿真实验中，考虑基于OFDMA组播无线系统的单小区网络，本文设置组播用户随机分布在500 m×500 m小区范围内，信道模型的仿真参数设置参考文献[7]，K-means聚类分组的比例系数为0.32。人工鱼群算法的控制参数设置为：人工鱼数目P=50，最大迭代次数m=100，视野范围v=7，拥挤度因子d=2，尝试次数t=10，移动步长st=a×v，a∈(0,1)为视步系数[25]，具体仿真参数如表1所示。

表1 仿真参数

3.2 性能分析

图3显示了基于最大最小距离K-means算法的分组结果。可以看出，根据信噪比值的不同，小区内随机分布的20个用户被自动划分为三组。

图3 分组结果

图4显示了不同分组方案下，组播组个数与系统吞吐量的关系。可以看出，三种分组算法的系统吞吐量先随组播组的个数增大而呈上升趋势，这是因为通过对组播组分组之后，组播组内用户间的信道质量相近，使组播组内信道质量最差的用户得到改善，从而使系统吞吐量增大；当组播组的个数大于3时，系统吞吐量略有下降，这是因为随着组播组个数的不断增加，每个组所分到的资源减少。当G=3时，本文的分组算法系统吞吐量达到了最大2.23 Mbit/s。由于所提分组算法得到的组播组个数也是3，这验证了该分组方法能够合理的计算G值，使系统吞吐量达到最佳。因此，本文选择G=3作为该场景的分组数以实现系统吞吐量最大化。数值仿真结果表明，本文算法相比于文献[8]固定组大小的分组方案和随机分组方案性能提升了2%和4.5%。

图4 组播组个数与系统吞吐量关系

图5显示了AFSA子载波分配方法的收曲线。分别考虑K=20、N=16和K=20、N=32两种情况下，AFSA子载波分配算法的收敛性。可以看出，随着子载波数量N的增大，本文方法在10次迭代内可以得到最优解，体现出良好的收敛性能。

图5 AFSA子载波分配方法的收敛曲线

图6显示了AFSA、GA和CMS的系统吞吐量对比图。可以看出，对于不同的N值，AFSA的性能优于GA和CMS，原因是在传统组播中子载波的数量越大，用户遇到不可用的子信道的概率就越高，从而限制了系统吞吐量。相反，本文通过在聚类分组策略下，进行子载波分配，可以将信道条件较差的用户分隔到某些子组，提高系统吞吐量。仿真结果表明，AFSA相比较GA和CMS系统吞吐量提升了5.3%和16%。因此，证明了本文方法的有效性。

图6 AFSA、GA和CMS的系统总吞吐量比较图(G=3)

4 结 语

针对传统组播在5G通信系统中吞吐量较低的问题，提出一种最大最小距离K-means组播分组策略与改进的人工鱼群算法的子载波分配方法。数值仿真结果表明，相对于传统组播和遗传算法，本文算法的系统吞吐量分别提升16%和5.3%。