基于禁忌搜索和Q-learning的CR-NOMA系统的功率分配算法

周 烁，仇润鹤，唐旻俊

（1.东华大学信息科学与技术学院，上海 201620；2.数字化纺织服装技术教育部工程研究中心（东华大学），上海 201620）

0 引言

近年来，随着无线移动通信的飞速发展以及5G网络的兴起，尤其是智能移动终端数量和功能的急剧增长，导致了人们对于移动通信的需求变得越来越高，如低时延、高速率、高可靠性等。为了满足这些通信需求并提供高质量的通信服务，非正交多址接入（Non-Orthogonal Multiple Access，NOMA）技术应运而生。尤其是在最近的研究中，NOMA 已经成为5G 无线网络中可以提供高吞吐量、高可靠性、低时延、优化覆盖和大规模连接的有效技术［1-2］。NOMA 通过功率复用技术可以同时服务多个用户，通过在发送端应用叠加编码技术将不同用户的信号叠加在不同的功率等级上从而实现多用户接入，而用户则共享同一时间和频段上的无线网络资源［3］。在接收机端应用连续干扰消除（Successive Interference Cancellation，SIC）技术来解码用户所需要的信息。认知无线电（Cognitive Radio，CR）网络中，允许次用户在不影响主用户正常通信的条件下接入主用户授权信道来共享主用户的频谱资源，从而提高频谱效率［4］。由此将CR 和NOMA 这两种关键技术相结合构建CR-NOMA 混合系统，即在CR 场景下，次用户通过NOMA 技术接入授权信道，可以显著提升频谱效率和系统性能。

目前已经有将CR 和NOMA 相结合的研究与工作。文献［5-7］中研究了在CR-NOMA 系统中功率分配和中继节点选择对系统性能的影响，推导了次用户中断概率的封闭表达式并通过仿真验证了结论。文献［8］中针对在CR-NOMA 系统接收端解码顺序的不同，提出了一种次用户预解码（Secondary user First Decode Mode，SFDM）联合优化算法来最大限度地提高次用户的归一化吞吐量，仿真结果显示了CR-NOMA 系统具有优越的性能；但该方案只考虑了单个主用户和次用户的情况，缺乏普遍性。在文献［9］中讨论了基于NOMA的认知异构网络在交互模式下的资源分配问题，以最大化次级网络的总吞吐量为目标，提出了一种新的分步式优化算法来解决该问题；但是考虑的用户数量较少，不具有一般性。在文献［10］中考虑了在下垫式模式下的CR-NOMA 系统中的资源分配问题，提出了新的参数变换法来求解优化问题，仿真结果表明，与传统的NOMA方案和非鲁棒的NOMA方案相比，所提出的方案具有更好的能效和中断性能。在文献［11］中为了提高CR-NOMA 异构网络相对于信干噪比的频谱利用率和非检测概率，提出了一种新的认知移动无线网络（Cognitive Mobile Radio Network，CMRN）算法并推导了最优功率分配因子，仿真结果验证了该方案在提高频谱效率和降低中断概率方面的有效性。文献［9-11］中所提算法在求解优化问题时均会出现陷入局部最优的情况，对系统性能会产生较大的影响。文献［12-15］中考虑了具有能量收集传输节点的CR-NOMA 方案来提升系统性能，并通过仿真对比实验验证了所提方案有效性。

上述算法在研究CR-NOMA 混合系统时没有将主用户的服务质量（Quality of Service，QoS）考虑在内，考虑接入系统的用户数量较少［8-9］，并且采用的优化算法在求解时容易出现陷入局部最优解的情况［9-11］。本文结合上述分析，在CR-NOMA系统中考虑多个主用户和多个次用户。对于求解该优化问题以及避免陷入局部最优，提出了基于禁忌搜索（Tabu Search，TS）和Q-learning［16］的功率分配（Power Allocation based on Tabu Search and Q-learning，PATSQ）算法。PATSQ 算法将系统中的用户功率分配问题表述为马尔可夫决策过程（Markov Decision Process，MDP），通过采用Q-learning方法来求解MDP问题，认知基站执行使得次用户总速率提高的动作时会得到正向的奖励，反之则得到负向的奖励，通过不断尝试和学习后，认知基站会得到一个包含所有状态下最优的功率分配表。但是单独采用Q-learning 方法复杂度过高，因此引入TS 来解决该问题，将已尝试或学习过的动作标记为禁忌对象，从而避免不必要的重复动作来显著降低算法复杂度。将认知基站在系统环境中采用PATSQ 算法学习用户的功率分配最终得到的最优功率分配表命名为禁忌Q 表。得到禁忌Q 表后，认知基站可以通过查找禁忌Q表来对用户给出最优的功率分配因子，从而使系统中次用户总传输速率最大化。

1 系统模型

对于本文中的CR-NOMA 系统，选择了下垫式的接入模式，即次用户可以在不影响主用户正常通信的情况下与主用户共享频谱资源，通过调整自身功率大小，次用户可以与主用户同时存在于授权信道中，并且次用户采用NOMA 的方式接入系统实现多用户接入。系统模型如图1 所示，考虑小区中有一个主基站、N个主用户，次级小区中有一个认知基站、M个次用户，所有终端均配备单天线。主用户之间仍采用正交频分复用的方式接入系统，即主用户之间互不干扰，而次用户接入主用户信道会对其产生不可避免的干扰。

图1 系统模型Fig.1 System model

1.1 主用户通信

认知基站在总功率的约束下向所有次用户发送数据。所有无线信道历经独立同分布的瑞利衰落和加性高斯白噪声。假设认知基站可以获取所有用户的瞬时信道状态信息（Channel State Information，CSI）。主用户PUi的接收信号可以表示为：

在传统的CR网络中，次用户采用下垫式模式接入主用户信道时，在不影响其正常通信的情况下也可以允许多个次用户同时接入，但是这些次用户必须通过正交的方式来区分；并且次用户对主用户的干扰要通过分时、分频或者分码来分析，极大地增加了计算复杂度。本文中次用户采用NOMA的方式接入空闲授权信道，次用户之间的信号在发射端经过叠加编码，从而对于主用户而言，考虑次用户干扰时可以将所有次用户看作一个整体。主用户PUi的信干噪比可以表示为：

其中B表示系统带宽。为了保证主用户的通信质量，必须满足以下条件：

其中Rmin为主用户满足正常通信的最小传输速率。

1.2 次用户通信

其中：αi表示次用户i的功率分配因子。

本文中次用户在功率域中实现多路复用，如图2 所示。在接收端应用SIC 消除了多用户信号之间的干扰。实际上，根据下行NOMA 链路的准则，当i≤j时，第j个用户首先对第i个用户的信息进行编码，然后从接收信号中消除这个信息，最后对第j个用户的信号进行编码；当i＞j时，第i个用户的信息被视为噪声。第i个次用户的信干噪比可以表示为：

图2 CR-NOMA系统中次用户的功率分配Fig.2 Power allocation of secondary users in CR-NOMA system

其中，当i=M时，其信干噪比为：

第i个次用户的传输速率可以表示为：

为了保证此用户的正常通信，同样必须满足：

其中rmin为次用户满足正常通信的最小传输速率。则系统中次用户总的传输速率为：

1.3 问题描述

本文将CR-NOMA 系统中的功率分配问题转化为在满足主用户和次用户QoS 以及最大总发射功率等约束条件下，获得最大的次用户总传输速率的问题。由于NOMA技术采用功率复用技术来实现多用户接入，本文通过优化认知基站分配给次用户的功率分配因子αi(∀i=1，2，…，M)来最大化次用户的总传输速率。由认知基站分配给各个用户的功率必须满足最大发射功率的约束。因此，这个优化问题可以由下式描述：

其中：pi=αiP；Pmax为认知基站最大发射功率；C1表示分配给用户的功率为非负，C2表示最大发射功率约束，C3和C4分别为主用户和次用户的QoS约束。该优化问题的目标函数为次用户的总传输速率。

CR-NOMA 系统能够正常工作的条件是必须确保主用户的QoS，要求主用户的传输速率必须大于其满足正常通信的最小传输速率门限，因此，主用户i对总发射功率P的约束为：

这样就得到了认知基站的总发射功率，也就是次用户可以获取的最大总功率P，并且确保了次用户接入授权信道不会干扰主用户正常通信。

同样，为了确保次用户的QoS，要求次用户的传输速率必须大于其满足正常通信的最小传输速率门限，因此次用户i的功率分配因子必须满足：

为了确保SIC 能够正常执行，给信道条件较差的次用户分配较大的功率，于是次用户i的功率分配因子可以由下式得到：

不满足最小传输速率约束的用户视为不能接入信道。

2 基于TS和Q-learning的功率分配

2.1 认知基站学习模型

为了求解CR-NOMA 系统中次用户总传输速率最大化的优化问题，本文使用TS 和Q-learning 相结合的方法来寻求合适的功率分配策略。Q-learning 方法常用智能体/环境接口来研究。智能体是整个系统中的决策者和学习者，本文系统中的智能体为认知基站，它通过观测来获取系统环境（如信道增益、噪声功率、功率分配因子等）当前的状态s后，对环境施加动作a，即进行功率分配，环境受所执行动作的影响，状态由s变为下一状态s′，并且通过总传输速率奖励r的形式反馈给认知基站来评价所执行动作的好坏。若某个动作a执行后得到的奖励为正，那么往后执行该动作的概率会增大；反之若得到的奖励为负，那么往后执行该动作的概率会减小。为了使系统性能达到最佳并且减少算法复杂度，引入TS将已执行过的动作标记为禁忌对象来加快算法收敛速度，PATSQ 算法通过将TS 中的禁忌表和Q-learning 中的Q 表相结合来减少系统进行不必要的尝试和试错的运行次数。认知基站在系统中的学习过程如图3所示。

图3 认知基站学习模型Fig.3 Cognitive base station learning model

本文中CR-NOMA 系统的优化目标是最大化系统中次用户总传输速率。在执行过程中，不同的用户数量会导致不同的功率分配策略，将来的总传输速率取决于当前的功率分配策略，系统无法确定将来接入的用户数量，但是可以明确历史用户数量以及功率分配策略。本文中的功率分配问题可以看作是一个连续马尔可夫过程，因此可以使用MDP 问题解决［17］。为了解决MDP 问题，本文将CR-NOMA 系统中的参数做出如下转换：

令s={s1，s2，…，sK}表示系统的信道状态空间，并且第t步的状态st由信道增益hi、功率分配因子αi和AWGN 的功率来表示任意一个用户t时刻的信道状态信息。因此，状态st可以定义为：

对于连续状态空间s，状态转移概率密度函数用来描述向后续状态区域转移的概率。当第t步采取了一个动作at∈a后，状态从st变为st+1的转移概率定义为：

2）功率分配动作a。

在该问题中，增加或减少分配给各个用户的功率都被视作CR-NOMA 系统功率分配问题的动作空间。令a={a1，a2，…，aK}表示系统进行功率分配的动作空间，并且，由认知基站决定选择哪一个动作。因此，动作at可以表示为：

其中：-1表示减少由认知基站分配给各个用户的功率，1则表示增加分配给用户的功率。

3）次用户总传输速率奖励r。

奖励函数为环境根据执行动作后状态的变化反馈给认知基站的信号，表示在该状态下执行该动作的好坏，于是认知基站就能根据奖励函数的大小来改变动作，从而得到越来越好的策略。

从定义上来看，地理信息生成系统中的数据反映的是空间地理实体位置、属性和拓扑关系，侧重点在于空间信息和属性信息；地图制图中的数据最终会以地图产品输出，更侧重形象、直观地描述地球表面的自然地理和社会人文等要素。

本文的目标是实现在CR-NOMA 系统中的次用户总传输速率的最大化，这与MDP 问题中要求的奖励最大化相一致。于是本文中将次用户总传输速率作为奖励函数，即为：

其中：rt和Rt分别表示第t步的奖励和次用户总传输速率。为了使得奖励函数更加稳定和有效，将平均总传输速率作为新的奖励函数，新的奖励函数定义如下：

其中次用户平均总传输速率由下式计算：

其中L为重复计算次数。新的奖励函数在保证总传输速率平稳性上有更好的表现。

2.2 PATSQ算法

在给出了状态、动作和奖励函数的定义后，本文中结合TS中的禁忌表和Q-learning中的Q表来获得一个禁忌Q表，其中，每一项Q(st，at)表示在状态st下执行动作at可以获得的奖励。这个禁忌Q表通过下述方式更新：

其中：β∈[0，1]表示加权前一步奖励和后一步奖励的学习率；γ∈[0，1]表示决定未来奖励重要性的折扣因子。在选择并执行动作at后，状态由st变为st+1，并且将已执行的动作at标记为禁忌对象，被列为禁忌对象的动作往后不能继续选择执行，随后将得到奖励和禁忌对象一同更新至禁忌Q表中。随着算法的不断执行，认知基站可以学习所有状态下采取任何一个动作得到的奖励。当禁忌Q 表收敛于一个最佳的值时，就得到了最佳功率分配策略。本文中可以得到的最佳功率分配策略为：

对于有限马尔可夫决策过程，这是对于最佳功率分配策略的保证。即，在任何状态s下，认知基站总是选择使得禁忌Q表中的值最大的最佳动作a*。

算法1 PATSQ算法。

算法1提出了PATSQ 算法。为了确保算法不陷入局部最优解，采用了ε-greedy 策略［18］。该策略不仅可以从禁忌Q 表内得到最佳动作，还可以选择其他可能更好的动作。在ε-greedy 策略中，以概率为ε∈(0，1)的情况来随机选择动作，以1-ε的概率从禁忌Q 表内选择最佳动作。一般情况下，通常设置ε=0.1，即认知基站有90%的可能根据禁忌Q 表来选择当前状态下的最佳动作，还有10%的可能随机选择动作。由此可见，采用ε-greedy策略在陷入局部最优时，由于10%的概率选择随机动作而不是最佳动作，PATSQ 算法可以根据这10%的随机概率跳出局部最优的情况，重新开始寻找全局最优解。

2.3 复杂度分析

对于传统TS 来说，其时间复杂度一般为O(tmaxN(M2+M+Tsize))，其中Tsize为禁忌表长度；对于Q-learning方法，其时间复杂度一般为其中T表示运行次数，Ssize和Asize分别表示状态个数和动作个数：可见单独使用TS或Q-learning 方法复杂度较大。本文的PATSQ 算法将两者结合，即将TS 中的禁忌表和Q-learning 中的Q 表相结合，将已执行过的动作标记为禁忌对象并存储到禁忌Q 表中，从而避免了在寻找最优解过程中不必要的重复计算，显著降低了算法的复杂度。在时隙tmax内，在每个状态下进行不同的动作，由于禁忌对象的标记，各个状态下每个动作只需要执行一次，而执行一次需要为M个主用户和N个次用户进行功率分配，于是在tmax需要执行Ssize次状态选择和Asize次动作选择，动作选择后首先为M个主用户分配功率然后为N个次用户分配功率，即在tmax次循环内，需要首先执行Ssize次状态选择，然后执行Asize次动作选择去为主次用户分配功率，其复杂度可以表示为O(tmaxNMSsizeAsize)。

3 仿真与分析

假设在CR-NOMA 系统中，主基站位于小区中心，主用户分布于主基站附近，认知基站位于次级小区，次用户在其中随机分布，只考虑下行链路的通信，用户的信道增益与其到基站的距离d成反比。在仿真中，设置归一化带宽B为1Hz，高斯白噪声的功率为σ2=0.01W，主基站的归一化发射功率为1W，次用户最大可用功率Pmax=1W，主次用户的最小传输速率门限分别为0.5 b/s 和0.3 b/s。其他重要参数设置为：根据算法在不同学习率β和折扣因子γ下的性能表现，设置β=0.5，γ=0.8。将本文所提出的PATSQ 算法与下述三种算法进行比较：

1）等功率分配算法。

2）SFDM 算法［7］：该算法通过KKT 条件、梯度下降法以及参数变换来使得系统中次用户的总吞吐量最大化。

3）CMRN 算法［10］：该算法考虑到用户之间的信道条件差异性，通过参数变换并且分步优化来推导最优功率分配因子从而提高系统性能。

本文算法的迭代过程如图4、5 所示。可以看出，随着迭代次数的不断增加，认知基站在系统中不断学习最佳功率分配动作来为次用户进行功率分配，在迭代次数较少的阶段，系统次用户总传输速率波动较大，经过大约70 次迭代后，从图4、5 均可以看出，次用户总传输速率开始趋于稳定，也就是次用户此时可以达到的最大总传输速率。

图4 PATSQ算法迭代过程Fig.4 Iteration process of PATSQ algorithm

图5 不同迭代次数时次用户总传输速率随功率的变化Fig.5 Total transmission rate of secondary users varying with power under different numbers of iterations

次用户总传输速率比较如图6 所示，默认接入系统的次用户数量为4。比较随着CR-NOMA 系统中主基站发射功率的不断增加，本文提出的PATSQ 算法与其他三种算法在次用户总传输速率上的变化情况。

由图6 可以看出，本文算法与其他三种算法相比，次用户总传输速率显著增加。等功率分配算法由于几乎没有采用优化方法来对功率进行优化分配，所以随着功率的增加，按照NOMA 的准则越往后的用户信道增益越差，所有用户分配相等的功率会导致那些信道条件差的用户传输速率较低甚至无法满足用户的QoS 而无法接入信道，所以随着功率的增加而总传输速率变化不明显。SFDM 算法对接入用户同时进行功率优化分配，所以其性能对比等功率分配算法有较大的提升，但是采用梯度下降法很有可能会陷入局部最优解。CMRN 算法通过分步的方式逐步确定每个用户的功率，对功率的利用率要高于同时分配，因此其次用户总传输速率要略优于SFDM 算法。而随着功率的不断增加，两种算法都有足够的功率对次用户进行功率分配，因此在曲线末尾处两种算法的性能比较接近。本文算法通过训练可以使得认知基站在任意状态下总是选择使得次用户总传输速率最大的功率分配策略，因此可以显著提升系统性能。

图6 不同算法下次用户总传输速率随功率变化比较Fig.6 Comparison of total transmission rate of secondary users varying with power by different algorithms

在不同主用户数量情况下系统的次用户总传输速率比较如图7所示，比较在CR-NOMA 系统中随着接入主用户数量的不断增加，本文算法和其他算法次用户总传输速率的变化情况。

由图7 可以看出，随着接入主用户数量的增加，四种算法的次用户总传输速率均呈现快速下降的趋势，这是因为次用户接入主用户信道的前提条件就是不能影响主用户的正常通信，随着主用户占用的系统功率越来越大，次用户必须降低自身功率或者退出所占用信道。可以看出由于等功率分配算法必须给每个接入用户分配均等的功率，其总传输速率是最小的，并且在接入主用户数为4 时次用户无法再接入信道。SFDM 算法和CMRN 算法在该条件下的表现差不多，后者略优于前者。本文算法可以从禁忌Q表中选择当前状态下最优的功率分配策略，因此不管是在次用户总传输速率还是在系统可容纳主用户数量上均优于前三种算法。

图7 不同算法下次用户总传输速率随主用户数量的变化Fig.7 Total transmission rate of secondary users varying with the number of primary users by different algorithms

图8 分析了在不同请求接入次用户数量下的总传输速率，比较在CR-NOMA 系统中随着请求接入的次用户数量的不断增加，本文算法和其他三种算法次用户总传输速率的变化情况。

由图8 可以看出，随着请求接入的次用户的数量的不断增加，四种算法的次用户总传输速率均先增加后趋于平缓，这是由于随着系统中次用户数量的增加，系统总传输速率会随之增加，但是在总功率的限制下，接入用户数不可能一直增加，次用户总传输速率平缓后说明系统中接入的用户数量已达到最大。从最开始接入次用户数量较少时，SFDM 算法和CMRN 算法均有足够的功率来对次用户进行功率分配，而在接入次用户数量达到饱和以后，CMRN 算法分步式求解的优势就不再明显，并且复杂度也会相应增加，因此两种算法的仿真曲线在首尾性能比较接近，总体来说CMRN 算法要略优于SFDM 算法。不难看出，在相同请求接入次用户数量的条件下，本文算法的次用户总传输速率总是比其他三种算法高。

图8 不同算法下次用户总传输速率随次用户数量的变化Fig.8 Total transmission rate of secondary users varying with the number of secondary users by different algorithms

在不同请求接入次用户数量下实际接入次用户数量的分析如图9所示，比较在CR-NOMA 系统中随着请求接入用户数量的不断增加，本文算法与其他三种算法实际接入用户数量的变化情况。

由图9 可以看出，CMRN 算法在容纳次用户数量上的表现与等功率分配算法相同，SFDM 算法略优于前面两种算法，随着请求接入用户数量的不断增加，系统中的用户数量达到最大，本文算法对每个用户分配最优功率分配因子使得更多的次用户可以接入授权信道，系统功率利用率提升。采用本文算法的系统可容纳用户数要优于其他三种算法。

图9 不同算法下实际接入次用户数随请求接入次用户数量的变化Fig.9 Number of actual access users varying with the number of requested access users by different algorithms

在不同的主用户数量下实际接入次用户数量的比较如图10 所示，比较系统中随着主用户的不断增加，本文算法和其他三种算法实际接入次用户数的变化情况。主用户采用正交的方式接入系统，避免主用户之间的相互干扰对系统性能产生影响。可以看出，随着主用户数量的增加，等功率分配算法的接入次用户数量变化最快并且最快变为0，SFDM 算法和CMRN 算法变化曲线差不多，而本文算法由于对每个用户的功率都进行了优化分配，因此在相同主用户数量下比其他三种算法具有更好的表现。

图10 不同算法下接入次用户数量随主用户数量的变化Fig.10 Number of access secondary users varying with the number of primary users by different algorithms

通过上述两个方面（次用户总传输速率和接入次用户数量）的仿真，对本文提出的PATSQ 算法的性能进行了分析。仿真结果显示，相较于其他三种方法（CMRN 算法、SFDM 算法、等功率分配算法），在占用相同带宽的条件下，本文算法通过学习获得的功率分配策略可以得到更大的总传输速率以及更多的接入用户数量，显著提升了系统的频谱效率。随着算法执行的次数越来越多，禁忌Q表中的值不断更新，认知基站可以学习所有状态下采取任意动作后得到的奖励。在已知当前状态时，认知基站通过访问禁忌Q 表得到当前状态下应采取的最佳动作，从而实现次用户总传输速率的最大化。

4 结语

本文针对CR-NOMA 系统中通过功率优化分配来提高次用户总传输速率的问题进行了研究，提出了基于TS 和Qlearning 的PATSQ 算法。认知基站通过采用TS 和Q-learning方法在系统环境中学习用户在不同信道条件下的功率分配策略得到禁忌Q 表，通过查找禁忌Q 表得到用户在任意状态下的最佳功率分配策略，并且避免了陷入局部最优的情况。本文中的功率分配问题采用MDP 问题解决，在设计奖励函数时使用次用户平均总传输速率来代替瞬时总传输速率，这样不仅可以反映次用户的最大总传输速率，而且由于更新过程中历史信息以及TS的引入，可以明显提高系统的学习效率和稳定性。通过仿真分析验证了本文算法对于提高CR-NOMA 系统中次用户总传输速率的有效性，并且总功率相同条件下可以让更多的次用户接入系统。在后续的工作中，将进一步讨论不完全连续干扰消除条件下CR-NOMA 系统的功率优化分配，分析本文算法的抗干扰能力。