1 引言
5G时代来临,移动数据流量呈爆炸性增长,频谱资源日益匮乏。正交多址接入(Orthogonal Multiple Access,OMA)技术已经逐渐不能满足用户的需求,具有更高频谱利用率,更低传输延时等优势的非正交多址接入(Non-orthogonal Multiple Access,NOMA)技术获得了学业界和工业界的广泛关注,成为5G中的一项关键技术。基于NOMA的系统将用户分为多个簇集,簇与簇之间保持频带资源正交,可以避免群间干扰,簇内用户共享同一个频带,并在接收端应用串行干扰消除(Successive Interference Cancellation,SIC)技术[1],以便为不同用户分离信号。这样可以有效的解决大规模用户接入时产生的阻塞问题,显著提高系统吞吐量[2]和频带利用率[3]。文献[4]和[5]详细介绍了NOMA的基本架构和基本思想,并针对NOMA中涉及的一些关键技术给出了较为详尽的概述。相较于OMA,NOMA技术能够显著提升系统用户总吞吐量以及边缘用户吞吐量。
近年来,NOMA系统中的用户聚类问题引起了有关学者的广泛研究兴趣。合适的用户分簇以及功率分配能够在一定程度上改善系统性能。文献[6]将用户按信道增益排序后,取其排序结果的中位数为信道增益阈值,把用户组分为强用户组跟弱用户组,从两组中各取一个用户完成配对,其配对后的系统性能优于随机配对的系统性能。这种方法可以挖掘出信道增益的特征,但实际应用中,如何选取合适的信道增益阈值,是一件较为困难的事情。文献[7]提出一种基于NOMA下行链路的最优用户配对方案,并证明了偶数个用户场景下算法的最优性,实验结果表明所提方案获得的系统性能优于OMA场景下的系统性能。文献[8]提出一种自适应用户配对策略,首先将蜂窝用户按照最佳信道条件分为两组,然后将一组中的每个节点与另一组中的另一个节点配对,如果最后还有多余的节点未完成配对,允许其与其他配对组之一配对,从而形成三个节点的集群,数值结果表明所提自适应用户配对策略优于传统用户配对方案。上述文献研究的都是用户两两配对的算法。文献[9]和[10]提出了几种用户动态分簇算法,其中[9]针对异构网络中的下行NOMA用户分簇,提出一种分布式的用户成簇和资源分配框架,可以有效提升系统性能。[10]提出一种用户选择算法,并配合一种新型功率分配方案,迭代出可行的用户分簇结果,来解决NOMA下行链路系统吞吐量最大化问题,仿真结果证明了该方案的有效性。相比于以上算法,经典的穷举算法能够迭代出最优的用户分簇方案,然而其计算复杂度过高,且系统开销较大。为此,很多学者研究如何在保证最优或者次优系统吞吐量的同时,降低分簇算法的计算复杂度。文献[11]提出一种区间聚类算法,实验结果证明,相比于传统的贪婪配对方法和次优配对算法,所提算法能够提供更好的系统性能。[12]基于下行链路NOMA系统,制定了最优用户分簇问题以最大化系统总吞吐量,并提出了最优和次优方案,相比于传统方案能够大大降低计算复杂度。[13]提出一种用户有序聚类方案以最大化系统性能,比较发现使用有序聚类在最小速率和总速率方面明显优于OMA。研究发现,分簇算法的本质与机器学习的聚类算法很相似[14]。因此,一些作者创新性的将机器学习算法应用于用户分簇。文献[15]将无监督机器学习算法应用于NOMA下行链路的用户分簇,首先基于固定用户场景开发了基于EM(Expectation Maximization)的用户分簇算法,然后考虑了动态用户场景,提出了一种基于OLEM(Online Expectation Maximization)的用户分簇算法,并证明了所提算法的有效性。文献[16]将机器学习中两种常见的邻居搜索算法爬山搜索[17]和模拟退火算法[18]用于用户的配对,仿真结果表明,与穷举搜索相比,它们能够显著降低系统计算复杂度,并且可以得到接近最优的系统吞吐量结果。文献[19]研究了一种基于多用户混合NOMA场景的系统吞吐量优化问题,并将遗传算法[20]用于NOMA下行链路的用户分簇。该算法的计算复杂度远低于穷举搜索,可以为任何给定数量的用户和簇提供近似最优的解决方案。仿真结果表明,该算法所得的系统总吞吐量非常接近最优结果。
本文研究NOMA下行链路的用户动态分簇问题。与文献[19]不同的是,本文簇的个数是变化的,并且不同簇中用户数可以不同。相比于先给定簇数量再进行用户分配的假定,本文的设定更符合实际环境。本文应用机器学习中的自适应遗传算法来得到一组用户分簇结果以最大化系统总吞吐量,该方案的计算复杂度远低于穷举搜索,可以为任何给定数量的用户提供接近最佳的分簇方案。
2 分簇问题的模型描述及算法分析
2.1 NOMA系统
本文考虑一个下行NOMA系统,图1为NOMA下行链路通信系统系统模型。在一个半径为R的区域D中随机分布着M个用户,基站BS处在区域D的圆心位置。假设基站和用户都是单天线。M个用户被划分为K个簇,不同簇内的用户数不一定相等。簇内用户可以共享相同的资源,簇间的资源相互正交,即假设簇间不存在干扰。
第k个簇中的第m个用户接收信号被表示为:
(1)
式中|Ck|表示第k个簇中的用户总数
表示基站BS到第k个簇中第m个用户的信道增益;
指系统分配给第k个簇中第i个用户的功率;
指第k个簇中第i个用户的传输信号;nm表示高斯白噪声,
此外,假设BS的总发射功率为Pt,且每个簇分配到的功率资源相等,因此有:
(2)
在不失一般性的情况下,假设|h1|2≥|h2|2≥…≥|hM|2。在同一簇中,信道状况较好,即离基站近的用户将始终比信道状况较差,即离基站更远的用户分配到更少的功率,以保证近用户在解码自己的信号之前,顺利解码出远用户的信号,并应用SIC消除这些干扰信号。第k个簇中的第m个用户的吞吐量被表示为:
(3)
式中s∈Ck且|hs|≥|hm|,B为系统总带宽,n0为噪声功率谱密度。系统总吞吐量被表示为:
(4)
2.2 用户分簇问题的制定
本文以系统总吞吐量为评判标准,对NOMA下行链路的用户分簇问题进行优化。不同分簇结果产生的系统吞吐量有很大的差异,众多结果中生成系统吞吐量最大的簇集即为最终选定的最优分簇结果。则该下行混合NOMA系统中用户分簇的优化问题可被表示为:
s.t. C1:pm≥0,m=1,2,…,M
C3:pm-pn≥0,m>n,
xm,k=xn,k=1,k=1,2,…,K
图1 NOMA下行链路通信系统模型
Fig.1 NOMA downlink communication system model
C4:|hn|2-|hm|2≥Δh,m>n,
xm,k=xn,k=1,k=1,2,…,K
C6:xm,k∈{0,1},m=1,2,…,M,k=1,2,…,K
(5)
由于簇间资源正交,其他簇的用户对m用户不造成干扰。式中的Inter表示m用户所在簇的其他高信道增益用户在m处产生的干扰。xm,k为表示m用户跟第k个簇从属关系的二进制变量,且同一个用户最多只能被分配到一个簇中,即:
(6)
式中C1确保用户被分配到的功率不会小于0;C2确保所有用户分配到的总功率等于系统总功率;C3表示信道增益差的用户可以分配到比信道增益好的用户更大的功率;C4确保同一个簇中用户间存在一定的信道增益差,这样有利于进行SIC;C5表示一个用户最多只能从属于一个簇。
问题(5)是一个混合整数非线性规划问题,直接求解的复杂度过高,传统用于解决该类问题的方法包括:分支定界算法,模拟退火算法,爬山算法,禁忌搜索等。遗传算法相比于上述算法具有通用性的全局搜索能力且目标解的精度以及稳定性更好,但对于多峰或者非光滑的混合整数非线性规划问题,传统的遗传算法求解时可能会陷入局部最优,浪费求解时间。为此,本文应用自适应调节参数的改进遗传算法来避免局部最优问题,进一步降低计算复杂度。
2.3 基于自适应遗传算法的用户分簇方案
由于标准遗传算法在数值方法求解时,存在收敛速度慢,容易陷入局部最优的问题。本文应用一种改进的自适应遗传算法,首先配合次优配合启发式方法生成初始种群,然后通过自适应地调节交叉和变异概率使算法能够更好更快地收敛到全局最优。
交叉、变异概率与遗传算法的性能息息相关。若交叉、变异概率过小,算法收敛速度会大大减慢;适度提升概率值,将加快算法产生新个体的速度;但如果概率值过大,算法将偏向于穷举搜索,复杂度将会大大提升。自适应遗传算法通过适应度函数值的变化来适时地调节交叉和变异概率的大小,即在算法执行过程中,如果系统吞吐量长期没有发生变化或者变化频率较低,调高交叉、变异概率;反之如果变化比较频繁,调低交叉、变异概率。同时,对于系统吞吐量高于群体均值的序列,给予较小的交叉、变异概率;反之,给予较大的交叉、变异概率。
图2为自适应遗传算法应用于NOMA下行链路用户分簇的流程图。当达到最大迭代次数或迭代出的系统最大吞吐量变化比例小于给定门限ε时,算法终止。具体的迭代次数随系统中用户数的变化而变化,用户数越多,迭代次数设定的就越大;反之越小。
图2 自适应遗传算法的用户分簇流程图
Fig.2 User clustering flowchart of adaptive genetic algorithm
具体步骤:
Step 1 利用次优配合启发式方法生成初始种群,约束条件包括:簇内用户的上限数,如果簇中用户数过多势必会影响系统总吞吐量;簇内用户的信道增益差,确保SIC的顺利进行。两个用户的信道增益差可以通过式(7)来计算:
d(i, j)=10log2||hi
-10log2||hj
(7)
Step 2 计算适应度值,即系统总吞吐量的值。
Step 3 选择操作。应用轮盘赌选择方式,以系统吞吐量为选择标准,这样产生系统吞吐量越大的序列就有更大的概率被选出放到新的群体中,以继续进行交叉和变异操作。
Step 4 交叉操作。将一个簇当作一个基因,在选择操作后生成的新群体中,随机挑选两个父类,在第一个父类中随机选择一定数量的簇插入到第二个父类的任意位置,然后删除插入后第二个父类中重复的用户所在的簇,并将删除簇中的剩余没有重复的用户利用次优配合启发式方法重新插入到第二个父类中,生成第一个子类;同样操作应用于第一个父类,生成第二个子类。具体操作如图3所示。
图3 交叉操作
Fig.3 Cross operation
Step 5 变异操作。随机删除一个簇,将这个被删除簇内的用户利用次优配合启发式方法插入回该序列中;或者在该序列中随机增加一个可行簇,将原序列中重复的用户所在簇删除,并将被删除簇中重复的用户重新添加到变换后的序列中,具体操作如图4所示。
图4 变异操作(随机增加)
Fig.4 Mutation operation (random increase)
Step 6 重复Step2～Step5,直至达到收敛条件,输出最优分簇及最优系统吞吐量的值。
3 实验仿真
本节评估了所提出的用户聚类方案在混合NOMA系统中的性能。实验在以原点为中心,半径为500 m的圆内基于泊松过程随机撒点,以模拟基站BS覆盖范围内的用户随机分布,实验结果是通过蒙特卡罗法(Monte Carlo)经过50万次仿真得到的。若无特别说明,具体仿真参数如表1所示。(在给定信号频率时,无线电波的损耗可以看作只和距离有关,此时COST-231HATA[21]可被简化为:L=38.45+10·n·log2(dm),其中n为环境因子,一般根据环境在2～5之间取值,dm为基站到用户的路径长度)
表1 系统仿真参数
Tab.1 System simulation parameters
仿真参数参数设置小区半径R/m500用户撒点模型 PPP随机撒点用户数/个n发射总功率/dBm46噪声功率σ2n/dBm/Hz-174系统带宽B/MHz20信道增益差门限值/dB3 吞吐量变化比例门限ε10-5初始种群大小2n最大迭代次数n3路损模型COST-231HATA
图5为相同功率分配方案下,不同分簇方案获得的最优系统吞吐量随用户数变化的关系图。从图中可以看出,在系统总发射功率和用户总数保持不变的情况下,本文研究的基于自适应遗传算法的用户动态分簇方案所得的系统吞吐量明显优于固定簇用户分配方案[19]下的系统吞吐量。但可以发现当用户逐渐增多时,两种方案的吞吐量差距逐渐变小,这是由于当给定固定簇个数为6时,随着用户数的增多,将有更多的用户能以NOMA的形式参与通信,其用户分簇结果将逐渐接近于所提分簇算法下得到的最优分簇结果,因此所提算法性能优势将逐渐缩小;如果用户数继续增加,对比算法簇内用户数过多,算法性能下降,所提算法的优势将被重新建立。与文献[8]的自适应配对策略相比,所提算法性能更好,这是因为遗传算法的随机搜索能力和并行计算能力有助于发现更优的结果。此外,与OMA系统和随机分配方案相比,所提算法存在明显优势,然而这种性能的提高是以增加设备和算法的复杂度为代价的。随着系统中用户数的增加,NOMA相较于OMA的优势将逐渐扩大。
图5 不同算法下系统吞吐量与用户数的关系图
Fig.5 Relationship between system throughput and number of users under different algorithms
图6为相同用户数,不同分配方案下的系统吞吐量随系统总发射功率的变化情况。从图中可以看出,本文所提方案相较于固定簇分配方案,其系统吞吐量具有明显优势,且随着系统总发射功率的增加,优势将逐渐扩大。然而随着发射功率的增大,簇内用户受到带内噪声的影响越来越小,增长速度将慢慢放缓,最终将趋于一个稳定值。对于基于OMA方式的系统来说,由于用户数目有限,所以系统总吞吐量随着发射功率增大的趋势偏缓,整体容量偏低。图中所得结果是采用蒙特卡洛仿真,为多次仿真结果取平均值,避免了单次随机撒点取值造成的数据偏差。
图6 不同算法下系统吞吐量与系统总发射功率的关系图
Fig.6 Relationship between system throughput and system total transmit power under different algorithms
遗传算法相当于是一种二重迭代,其计算复杂度不高于O(n2);穷举算法的系统计算复杂度为搜索空间的指数次幂。图7为在相同时间,等量用户且等系统总发射功率下,所提算法得到的最优吞吐量结果与穷举算法所得吞吐量结果的对比图。从图中可以明显看出,在相同时间内,基于自适应遗传算法得到的系统吞吐量相较于穷举算法有较为明显的优势。且随着迭代时间的增加,两者之间的差距将进一步扩大,这是因为穷举算法的计算复杂度是呈几何倍数增加的。两者最后都将趋近于不计时间下穷举算法迭代出的系统最优吞吐量。对比分析可知,所提算法的计算复杂度明显低于穷举算法的计算复杂度。
图7 不同算法下系统吞吐量与时间的关系图(user=128)
Fig.7 The relationship between system throughput and time under different algorithms (user=128)
4 结论
本文主要研究基于NOMA下行链路的用户动态分簇问题,目标是最大化NOMA下行链路的系统总吞吐量。本研究将机器学习中的经典自适应遗传算法配合次优配合启发式方法对NOMA下行链路用户进行分簇。仿真结果表明,该算法与经典穷举算法相比,能够在保证系统性能的前提下,有效降低系统的计算复杂度。而且相较于传统的分簇算法,该算法迭代出的最优分簇结果能够进一步提升系统吞吐量,得到一个接近穷举算法下的最优吞吐量分簇结果,且更符合实际环境。未来研究将寻求其他的优化算法来进一步降低系统的计算复杂度。
[1] 王歌, 赵知劲. NOMA系统中低复杂度的串行信号检测算法[J]. 信号处理, 2019, 35(1): 26-31.
WANG Ge, ZHAO Zhijin. Low complexity successive signal detection algorithm in NOMA system[J]. Journal of Signal Processing, 2019, 35(1): 26-31.(in Chinese)
[2] ZENG Ming, YADAV A, DOBRE O A, et al. Capacity comparison between MIMO-NOMA and MIMO-OMA with multiple users in a cluster[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(10): 2413-2424.
[3] LIU Yuanwei, QIN Zhijin, ELKASHLAN M, et al. Nonorthogonal multiple access for 5G and beyond[J]. Proceedings of the IEEE, 2017, 105(12): 2347-2381.
[4] DAI Linglong, WANG Bichai, DING Zhiguo, et al. A survey of non-orthogonal multiple access for 5G[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2294-2323.
[5] 杨一夫, 武刚, 李欣然, 等. 面向后5G的非正交多址技术综述[J]. 无线电通信技术, 2020, 46(1): 26-34.
YANG Yifu, WU Gang, LI Xinran, et al. A survey of non-orthogonal multiple access technology for beyond-5G[J]. Radio Communications Technology, 2020, 46(1): 26-34.(in Chinese)
[6] CHINNADURAI S, SELVAPRABHU P, LEE M H. A novel joint user pairing and dynamic power allocation scheme in MIMO-NOMA system[C]∥2017 International Conference on Information and Communication Technology Convergence (ICTC). Jeju, Korea (South). IEEE, 2017: 951-953.
[7] ZHU Lipeng, ZHANG Jun, XIAO Zhenyu, et al. Optimal user pairing for downlink non-orthogonal multiple access (NOMA)[J]. IEEE Wireless Communications Letters, 2019, 8(2): 328-331.
[8] RAUNIYAR A, ENGELSTAD P, ØSTERBØ O N. An adaptive user pairing strategy for uplink non-orthogonal multiple access[C]∥2020 IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications. London, UK. IEEE, 2020: 1-7.
[9] CELIK A, TSAI M C, RADAYDEH R M, et al. Distributed user clustering and resource allocation for imperfect NOMA in heterogeneous networks[J]. IEEE Transactions on Communications, 2019, 67(10): 7211-7227.
[10]WANG C L, WU Poen. User selection and power allocation for detection-performance guarantee in downlink non-orthogonal multiple access systems[C]∥2019 13th International Conference on Signal Processing and Communication Systems (ICSPCS). Gold Coast, QLD, Australia. IEEE, 2019: 1- 8.
[11]DING Tingting, XIA Xueyao, ZHANG Ningbo, et al. An interval clustering algorithm for non-orthogonal multiple access[C]∥2018 21st International Symposium on Wireless Personal Multimedia Communications (WPMC). Chiang Rai, Thailand. IEEE, 2018: 293-297.
[12]TSENG J H, CHEN Y F, WANG C L. User selection and resource allocation algorithms for multicarrier NOMA systems on downlink beamforming[J]. IEEE Access, 2020, 8: 59211-59224.
[13]IVARI S M, CAUS M, VAZQUEZ M A, et al. Power allocation and user clustering in multicast NOMA based satellite communication systems[C]∥ICC 2020-2020 IEEE International Conference on Communications (ICC). Dublin, Ireland. IEEE, 2020: 1- 6.
[14]MOSCHITTI A.Introduction to Machine Learning[J].Methods Mol Biol,2014,1107(1107):105-128.
[15]REN Jie, WANG Zulin, XU Mai, et al. Unsupervised user clustering in non-orthogonal multiple access[C]∥ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Brighton, UK. IEEE, 2019: 3332-3336.
[16]ZHANG Xinyi, WANG Jun, WANG Jintao, et al. A novel user pairing in downlink non-orthogonal multiple access[C]∥2018 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB). Valencia, Spain. IEEE, 2018: 1-5.
[17]LIGEZA A.Artificial Intelligence: A Modern Approach[J]. Applied Mechanics & Materials,2009,263(2):2829-2833.
[18]陈华根, 吴健生, 王家林, 等. 模拟退火算法机理研究[J]. 同济大学学报(自然科学版), 2004, 32(6): 802- 805.
CHEN Huagen, WU Jiansheng, WANG Jialin, et al. Mechanism study of simulated annealing algorithm[J]. Journal of Tongji University(Natural Science), 2004, 32(6): 802- 805.(in Chinese)
[19]YOU Hanliang, PAN Zhiwen, LIU Nan, et al. User clustering scheme for downlink hybrid NOMA systems based on genetic algorithm[J]. IEEE Access, 2020, 8: 129461-129468.
[20]席裕庚, 柴天佑, 恽为民. 遗传算法综述[J]. 控制理论与应用, 1996, 13(6): 697-708.
XI Yugeng, CHAI Tianyou, YUN Weimin. Survey on genetic algorithm[J]. Control Theory & Applications, 1996, 13(6): 697-708.(in Chinese)
[21]李焜, 王喆. 无线通信电波传播模型的研究[J]. 无线通信技术, 2008, 17(1): 10-12.
LI Kun, WANG Zhe. Research of wireless communications radio wave propagation model[J]. Wireless Communication Technology, 2008, 17(1): 10-12.(in Chinese)
