NOMA下行链路中用户匹配和功率分配算法

杨路; 吴芳炜; 龙恳; 陈德建

【期刊名称】《《计算机工程与设计》》 【年(卷),期】2019(040)011 【总页数】7页(P3061-3066,3157)

【关键词】非正交多址; 加权二分图; 用户匹配; 比例公平; 功率分配 【作 者】杨路; 吴芳炜; 龙恳; 陈德建

【作者单位】重庆邮电大学通信与信息工程学院 重庆400065 【正文语种】中 文 【中图分类】TN929.5 0 引 言

非正交多址接入技术(non-orthogonal multiple access，NOMA)通过将多个用户叠加在同一资源块上传输，可以提升系统设备接入量，提高频谱效率[1,2]，而在实际的NOMA下行链路中，合理的用户匹配和功率分配算法影响着系统的和速率和用户间的公平性[3,4]。目前关于NOMA下行链路用户匹配的研究中，文献[5,6]介绍了一种随机用户配对方法，算法将小区中所有用户分为若干个用户数相等的集合，然后在每个用户集合中选出信道增益差异最大的用户进行配对。由于该算法中用户集合通过随机选择得到，不能保证总体系统性能较优。文献[7]通过设置限制条件对候选用户集进行筛选,减小用户集的范围,降低算法复杂度,但不能保证

每个用户的数据速率。文献[8]提出一种基于用户信道状态排序的用户匹配算法(channel state sorting-pairing algorithm，CSS-PA)，首先对所有用户信道状态信息按升序或者降序排列，然后按照折半配对的方式进行用户配对，算法的复杂度较低，也可以保证配对用户间具有一定的信道状态差异，但无法保证每次都可以使系统总吞吐量达到较优。当用户完成匹配后，发射端需要在配对用户间要进行功率分配。全搜索功率分配算法FSPA(full search power allocation)[9]通过对候选用户集遍历所有的功率分配方案，来达到最优的系统和速率，但算法的复杂度较高。分数阶功率分配法FTPA(fractional transmit power allocation)[10]和固定功率分配算法FPA(fixed power allocation)[11]都是通过系统定义的衰落因子对不同信道增益的用户进行功率分配，复杂度相对于FSPA较小，但衰落因子的选取受人为因素的影响较大，无法保证边缘用户的公平性。文献[12]介绍了一种Fair-NOMA功率分配方案，通过对比OMA下用户的数据速率，得到用户间功率分配因子的取值范围，来保障边缘用户的公平性。文献[13]介绍了一种基于比例公平的功率分配方法，通过最大化复用用户中公平性最差用户的比例公平因子，用KKT最优约束条件求出问题的最优解，但是算法为了保障边缘用户的公平性而牺牲了一部分系统性能。

上述用户匹配算法的研究，或者存在复杂度较高的问题，或者虽然一定程度上降低了复杂度，但是以牺牲系统总吞吐量性能为代价。而功率分配算法仍然不能在用户公平性和系统和数据速率之间达到平衡。对此，本文考虑将用户匹配问题转化为加权二分图的最优匹配问题来达到降低算法复杂度的目的；而使用比例公平算法，通过与相同条件下OMA系统用户数据速率的对比来保证边缘用户的数据速率。 1 系统模型

如图1所示，单基站下行链路蜂窝系统中，包含K个用户，基站的发射功率为PT， 基站和用户均为单天线，系统总带宽为WT， 子带间带宽均匀分配，分为Nsc个

子带，则每个子带的带宽为 每个子带最多叠加mmax个用户数据传输。其中，当基站向第n个子带 (n∈{1,2,3,…Nsc}) 中第m个用户发送信息xm,n时，用户发射功率记为Pm,n。

图1 NOMA下行链路的系统模型

由于基站总发射功率一定 则用户m的接收信号为 (1)

其中，为用户m需要的信息，为子带中其他用户的干扰信息， Ni表示加性高斯白噪声。假设用户信道状态信息(channel state information，CSI)在基站侧已知，则可得

hm,n=gL,nPL-1(d) (2)

式中： gL,n表示瑞利衰落信道增益， PL-1(d)表示路径损耗方程，d表示用户与基站的距离， gm,n表示噪声归一化信道响应，定义式为 (3)

由于考虑叠加用户数对接收端SIC复杂度的影响，因此一般叠加两个用户在同一子带中传输[4]。图2表示了NOMA下行链路两个用户叠加传输的基本原理图。其中UE1和UE2数据叠加在同一子带中传输，UE2与基站覆盖域中心存在较远距离，由此将产生较大的路径损耗。

图2 NOMA下行链路两个用户叠加传输的基本原理

为保证数据的有效传输，UE2需分配较大的发送功率使得接收端可以有效解调。由于UE2数据的信噪比较大，此时可直接解调得到UE2数据。对于UE1，与基站距离较近使其在数据传输时只需分配较小的发送功率，接收端先通过SIC将UE2

信息解调，再消除解调得到的UE2信息，最后得到UE1信息。若mmax个用户在第n子带中叠加传输，可根据式(2)和式(3)时计算噪声归一化信道增益，排序为g1,n≥g2,n≥g3,n≥…≥gmmax,n。 根据香农公式，则用户1和用户2的数据速率分别为

R1,n=Wsclog2(1+P1,ng1,n) (4) (5)

其中，第k个用户的数据速率为 (6)

而对于边缘用户的公平性的研究，本文以在相同条件的OMA系统中用户的数据速率作为最低速率基准，而在相同条件下的OMA的第k个用户数据速率为 (7)

另外，在保证边缘用户的数据速率的同时，若要最大化系统总吞吐量，则优化目标函数为 Objective (8) s.t. (9) Pi,j≥0

(10) (11)

总结以上式(8)～式(11)，其中式(8)为系统模型需达成的目标，即最大化所有用户的和速率，而式(9)表示达成此目标的前提条件为总发射功率恒定。式(10)保证每个用户分配的功率不少于0，式(11)要求用户在NOMA系统中的数据速率不低于在相同条件下用户在OMA系统中的数据速率，以此保证边缘用户的数据速率。由于系统优化目标函数是一个非凸优化问题，其计算复杂度是一种NP-hard问题，为了求解上述问题，本文将总优化目标分解为用户配对和功率分配这两个子问题来设计相应算法分别求解，以获得问题的最优解。 2 NOMA用户配对和功率分配

本节对NOMA下行链路中用户配对和功率分配算法分别进行研究设计。本文首先对所有用户的信道增益进行排序，并将用户从中间位置分为两组，为了降低复杂度，设计采用加权二分图中最优匹配中的Kuhu-Munkres算法进行用户匹配，并进一步对配对用户采用比例公平算法进行配对用户的功率分配，来保证信道条件较差用户的数据速率。

2.1 低复杂度用户配对算法

已有研究结果表明，配对用户的信道增益差异越大，SIC的效果越好，系统吞吐量总和越高[4-6]，据此建立信道增益用户配对模型，目标为最大化所有用户间噪声归一化信道增益差的绝对值之和，即有 (12)

式中： M表示用户配对完成后的矩阵， gj和gi表示配对用户的噪声归一化信道增益。为求解上述匹配目标，通过将用户匹配问题转化为加权二分图的最优匹配问

题，采用Kuhu-Munkres算法对用户匹配进行求解。用户二分图如 图3 所示，具体方法为：先将用户信道状况从小到大排序，从中间用户位置将用户分为两组，如果总用户数为奇数，则中间用户不参与匹配，单独占用一个子带进行传输。如此将所有用户按照信道增益前后顺序分为两组，组成二分图。 图3 用户信道信息二分图

其中二分图的权值为配对用户噪声归一化信道差的绝对值 |gj-gi|， 通过加权二分图的最优匹配中Kuhu-Munkres算法则可以求出所组成二分图的最优匹配。 根据该算法思路，实现低复杂度用户配对的主要伪代码见表1。 表1 低复杂度用户配对算法伪代码Algorithm:低复杂度用户配对算法

(1)Input:U,k,Group1={ϕ},Group2={ϕ},M=[ϕ](2)Begin:(3)G=sort(U)={g1,…,gk}(4)Ifk%2!=0(5) u=g(k+1)/2(6)Assignuseparately(7) Group1={g1,…,g(k-1)/2}(8) Group2={g(k+1)/2+1,…,gk}=={u1,…,u(k-1)/2}(9)Else(10)Group1={g1,…,gk/2}(11)Group2={gk/2+1,…,gk}={u1,…,uk/2}(12)End(13)Ifk%2!=0(14) Fori=1∶(k-1)/2(15) Forj=1∶(k-1)/2(16) Mij=|gi-uj|(17) End(18) End(19)Else(20) Fori=1∶k/2(21) Forj=1∶k/2(22) Mij=gi-uj(23) End(24)

End(25)End(26)CalculatetheoptimalmatchofMthroughtheKuhu-Munkresalgorithm[14]

表1中，第(1)行输入U表示基站下所有用户噪声归一化信道增益集合，k为用户总数，Group1、Group2初始化为空集，M为空矩阵，第(3)行根据噪声归一化信道增益对用户进行升序或降序排序，排序后用户集合记为G。第(4)～(12)行，若用户数为奇数，则中间用户单独分配，剩余用户按中间用户前后顺序分为两组；若为偶数，则直接按噪声归一化信道增益顺序分为两组。第(13)～(25)行，通过循环计算两两用户配对权矩阵的值，配对权矩阵中的值即为对应用户间噪声归一化信道

增益差的绝对值，如用户1和另一组中用户3之间噪声归一化信道增益差的绝对值对应于配对权矩阵1行3列的值，通过两组用户两两之间的信道增益差的绝对值，得到整个用户配对的权矩阵。第(26)行采用图论中Kuhu-Munkres算法对所得权矩阵进行运算可以得到此二分图的最大匹配[14]，即最大化所有用户噪声归一化信道增益差异之和，匹配结果对应于用户配对结果，计算复杂度为O(K3)。 而采用全搜索的方式进行用户配对时计算复杂度为O(K!)， 相比而言，本文提出的用户配对算法在用户数相同的情况下计算复杂度将大大降低。 2.2 比例公平功率分配算法

比例公平(proportional fairness，PF)算法通过最大化用户吞吐量的对数和，在保证系统较高频谱效率的同时保障用户间公平性[12,13]。因此，当用户完成匹配后，本文采用比例公平算法，并以相同条件下OMA系统用户数据速率作为每个用户的最小数据速率，以此最大化配对用户的和速率。为了达到此目的，通过将非凸问题转化为凸问题，利用函数单调性判定求得配对用户最大化和速率的最优解。 比例公平算法需要同时考虑用户的平均数据速率和瞬时数据速率，其定义式如下 n=1,2,…,Nsc, m=1,2,…,mmax (13)

其中， Rm,n(t) 表示第n个子带中，第m个用户在第t帧时间的瞬时数据速率； tc表示平均窗长， xm,n(t) 表示用户调度的0-1序列； xm,n=1表示第m个用户在第t帧时间、第n个子带中被调度，否则值为0。

比例公平算法的目标是最大化一段时间内用户平均数据速率的对数和，为了满足这个目标，用户调度和功率分配需要最大化下式 (14)

由于tc≫1， N表示频域上连续的12个子载波，上式可以近似表示为

(15)

不同于文献[13]的损失一部分系统和速率来保障信道较差的用户数据速率，本文优化目标为最大化同一子带内叠加用户的和速率，同时设置用户数据速率不低于相同条件下OMA数据速率来保障信道较差用户的公平性。对此，通过所提出的用户配对算法选择出两个用户叠加在同一子带中进行传输，若对叠加用户进行功率分配，则可以得到优化表达式为 Objective (16) s.t.

R1,NOMA≥R1,OMA, R2,NOMA≥R1,OMA (17)

通过式(4)、式(5)、式(7)、式(17)可以计算得到 (18) 其中

θi=Pscgi,i=1,2 (19)

令 则式(4)、式(5)、式(14)代入f(a) 可得 (20)

对f(a) 进行求导可得

(21)

当f′(a)=0时， a*的值取决于T1和T2的大小关系： (1)当T1≠T2时，令式(21)为0，可解得 (22)

若a*≥0， 则有 T1θ2/θ1≤T2≤T1 (23)

根据式(23)的大小关系，可得 (24)

因此， a*为f(a) 的极大值点。由于f(a) 是一个连续可微函数且只有一个极值点，所以a*既是极大值点，又是最大值点，考虑到a取值范围的约束，分情况讨论有：①若 amin≤a*≤amax， 则aopt=a*； ②若a*≥amax， 则aopt=amax； ③若0≤a*≤amin， 则aopt=amin； ④若a*<0， 则T1/θ1>T2/θ2或T2>T1。 当为情况①时， a*位于a取值范围中，最优功率分配因子aopt取值为a*； 当为情况②时， a*≥amax， 取值范围中amax离a*距离最近，最优功率分配因子aopt取值为amax； 当为情况③时，a*位于0点和amin之间， a*距离amin最近，最优功率分配因子aopt取值为amin； 当为情况④时，若T1/θ1>T2/θ2， f′(a)<0， f(a) 单调递减，可以得出最优功率分配因子为aopt=amin； 若T2>T1， f′(a)>0， f(a) 单调递增，最优功率分配因子为aopt=amax。 (2)当T1=T2时，可以得到 (25)

由于f″(a) 恒大于等于0， f′(a) 单调递增，且f′(0)≥0， 所以f(a) 单调递增，最优解aopt=1， 说明用户1占用全部的发射功率，用户2此时功率为0，不满足要求。

综上，可以得出采用比例公平算法进行配对用户间功率分配时功率分配因子aopt的取值情况 (26)

通过式(26)可以计算得出配对用户间的功率分配因子aopt， 当f(a) 极值点a*位于amin和amax之间时，用户间功率分配因子aopt就为a*， 当f(a) 极值点a*大于amax时或者配对用户平均数据速率相同时，用户间功率分配因子aopt为amax， 其它情况下，用户间功率分配因子aopt为amin。 3 仿真与结果分析 3.1 实验条件设定

使用Matlab编程对本文提出的用户配对和功率分配算法进行了仿真验证。实验环境设置的是覆盖半径为500 m的单基站下的多用户随机分布场景，其中基站和用户均配备有一根天线，信道选择Rayleigh衰落信道，噪声功率为-174 dbm。具体仿真参数见表2。

表2 仿真参数参数名值总带宽(WT)25M子频带数量(Nsc)5阴影标准差8dB噪声功率谱(No)-174dbm小区半径(D)500m路径损耗指数(V)4平均用户吞吐量间隔(tc)100ms调度间隔1ms路径衰落128.1+37.6log(d)信道模型Rayleigh衰落信道

3.2 实验结果及分析 3.2.1 用户配对算法仿真

为了验证不同用户配对算法对系统性能的影响，分别从系统吞吐量随发射功率和用

户数的变化这两个方面进行了仿真。图4是针对采用不同用户配对算法时，系统吞吐量随发射功率增大而变化的仿真结果图。仿真用户设定为单基站下随机分布的10个用户，其中功率分配算法采用比例公平功率分配算法。从结果可以看出，穷举搜索算法的系统吞吐量最优，但计算复杂度也最大。而本文采用的Kuhu-Munkres算法在信噪比较低时性能要次于最优的FSPA算法，但要优于文献[7]中所提出的用户信道状态排序配对算法(CSS-PA)和随机配对算法(RPA)。这是因为在低信噪比环境下，数据速率受配对用户的信道差异影响较大[6]。当发射功率较大时，系统吞吐量受发射功率的影响较大，用户信噪比较高，不同配对方式对系统吞吐量的影响减小，系统总吞吐量受发射功率的影响较大。仿真结果同时表明NOMA的性能明显优于同条件下的OMA性能。 图4 系统总吞吐量随发射功率变化趋势

由图5可以看出不同用户配对算法在发射功率为10 dbm时系统总吞吐量随用户数的变化情况。在用户数相同的情况下，穷举搜索配对得到的总吞吐量最高，本文所提算法优于信道状态排序配对算法和随机用户配对算法。由于配对用户间都采用比例公平功率分配算法，用户数增多将带来用户分集增益，使系统总吞吐量逐渐增大。但由于发射功率和系统总带宽受限，当用户数增大到一定程度时，总吞吐量还受到发射功率和带宽的限制，系统总吞吐量逐渐稳定。此时，本文所提算法和穷举搜索算法和信道状态排序算法得到的总吞吐量相接近。同时也可以看出NOMA系统总吞吐量明显大于同条件下OMA系统总吞吐量。 图5 系统总吞吐量随用户数变化趋势 3.2.2 比例公平算法仿真

为了验证随着发射功率的变化，不同功率分配算法对用户公平性可能产生的影响，对配对用户的数据速率进行了仿真。图6给出了在子频带带宽为5 Mbit·s-1、发射功率从0 dbm～40 dbm逐渐增大时，分别采用比例公平功率分配、分数阶功

率分配和固定功率分配3种不同的功率算法对同一子信道中两个用户间进行功率分配时，得到配对用户各自的数据速率情况。

图6 不同功率分配算法下的同一子信道用户数据速率对比

其中采用FPA功率分配算法时，强用户占用总发射功率的40%，而FTPA的功率分配算法中a因子设置为0.3。在同一子信道叠加用户信道条件相同的前提下，3种功率分配方式的配对用户总数据速率几乎相同。但从两个用户各自的数据速率可以看出，本文采用的PF功率分配算法得到的配对用户数据速率更为接近，可以实现更好的公平性。 3.3 复杂度分析

表3为在发射功率为20 dbm、单基站下接入10个用户时，不同算法复杂度的情况。

表3 算法复杂度和性能对比算法名称复杂度吞吐量/bps穷举搜索配对O(K!)6.26×108本文所提算法O(K3)6.17×108信道状态排序配对[7]O(K)5.89×108随机用户配对O(K)5.76×108

从表3中可知，最优的穷举搜索算法进行用户配对的计算复杂度为O(K!)， 而本文将加权二分图中最优匹配的Kuhu-Munkres算法用于用户配对，算法复杂度为O(K3)， 虽然它们在相同信噪比条件下系统总吞吐量接近，但后者计算复杂度大大降低。文献[7]中的信道状态排序配对算法的复杂度和随机用户配对算法的复杂度皆为O(K)， 相对于本文算法复杂度较低，但算法性能都不及本文算法。 4 结束语

本文针对现有NOMA下行链路用户匹配算法存在复杂度较高的问题，将加权二分图最优匹配的Kuhu-Munkres算法应用于用户配对过程，再使用比例公平算法进行配对用户间的功率分配，有效降低了计算复杂度，保证了系统总吞吐量和边缘用户数据速率。但目前算法是在CSI完全可知的前提下得到的，而在实际系统中CSI

往往不能完全得到，因此，考虑如何在不完美CSI的情况下进行用户配对和功率分配将是下一步研究的重点。 参考文献：

【相关文献】

[1]Islam S M R,Avazov N,Dobre O A,et al.Power-domain non-orthogonal multiple access (NOMA) in 5G systems:Potentials and challenges[J].IEEE Communications Surveys & Tutorials,2016,19(2):721-742.

[2]Dai Linglong,Wang Bichai,Yuan Yifei,et al.Non-orthogonal multiple access for

5G:Solutions,challenges,opportunities, and future research trends[J].IEEE Communications Magazine,2015,53(9):74-81.

[3]LI Zhao,DAI Xiaoqin,CHEN Keyu,et al.Non-orthogonal multiple access downlink user matching and power optimization algorithm[J].Journal of Electronics and

Information,2017,39(8):1804-1811(in Chinese).[李钊,戴晓琴,陈柯宇,等.非正交多址接入下行链路用户匹配与功率优化算法[J].电子与信息学报,2017,39(8):1804-1811.]

[4]Zhiguo Ding,Fan P,Poor H V.Impact of user pairing on 5G non-orthogonal multiple-access downlink transmissions[J].IEEE Transactions on Vehicular Technology,2014,65(8):6010-6023.

[5]Jie Mei,Lei Yao,Hang Long,et al.Joint user pairing and power allocation for downlink non-orthogonal multiple access systems[C]//IEEE International Conference on Communications.Chengdu:ICC,2016:1-6.

[6]Nain G,Das S S,Chatterjee A.Low complexity user selection with optimal power

allocation in downlink NOMA[J].IEEE Wireless Communications Letters,2018,7(2):158-161. [7]Zhang Han,Zhang De-Kun,Meng Wei-Xiao,et al.User pairing algorithm with SIC in non-orthogonal multiple access system[C]//IEEE International Conference on Communications.Kuala Lumpur:ICC,2016:1-6.

[8]Liu Yang,Pan Gaofeng,Zhang Hongtao,et al.On the capacity comparison between MIMO-NOMA and MIMO-OMA[J].IEEE Access,2017,4(5):2123-2129.

[9]El-Sayed M M,Ibrahim A S,Khairy M M.Power allocation strategies for non-orthogonal multiple access[C]//International Conference on Selected Topics in Mobile & Wireless Networking.Cairo:MoWNeT, 2016:11-13.

[10]Hojeij M R,Farah J,Nour C A,et al.Resource allocation in downlink non-orthogonal

multiple access (NOMA) for future radio access[C]//IEEE 81st Vehicular Technology Confe-rence.Glasgow:VTC Spring,2015:11-14.

[11]Oviedo J A,Sadjadpour H R.A fair power allocation approach to NOMA in multi-user SISO systems[J].IEEE Transactions on Vehicular Technology,2017,66(9):7974-7985. [12]Liu F,Mähönen P,Petrova M.Proportional fairness-based user pairing and power allocation for non-orthogonal multiple access[C]//IEEE 26th Annual International Symposium on Personal,Indoor,and Mobile Radio Communications.Hong Kong:PIMRC,2015:1127-1131.

[13]CAO Yong,YANG Zhen,FENG Youhong.New NOMA power distribution

strategy[J].Journal of Communication,2017,38(10):157-165(in Chinese).[曹雍,杨震,冯友宏.新的NOMA功率分配策略[J].通信学报,2017,38(10):157-165.]

[14]Wang Niwei,Fei Zesong,Kuang Jingming.QoE-aware resource allocation for mixed traffics in heterogeneous networks based on Kuhn-Munkres algorithm[C]//IEEE International Conference on Communication Systems.Shenzhen:ICCS,2016:14-16.