混合频谱共享方式下多用户动态频谱分配算法

周鑫 何攀峰 陈勇 钱鹏智

（1. 陆军工程大学通信工程学院，南京 210007；2. 国防科技大学第六十三研究所，南京 210007）

引 言

随着无线通信业务的飞速增长，频谱资源日益短缺. 基于认知无线电(cognitive radio, CR) 技术[1]的频谱共享策略作为一种能够提升频谱利用效率，缓解频谱资源紧缺的有效方法，近年来引起了人们的广泛关注. 频谱共享方式可以分为填充式(overlay)和下垫式(underlay)两种[2]. overlay 频谱共享方式中，系统将空闲信道分配给次用户，次用户能够以最大功率传输信息[3]. underlay 频谱共享方式中，若次用户发射功率传输到主用户接收机时在干扰门限以下，即可与主用户共同使用信道[4]. 文献[5]采用overlay频谱共享方式，提出了基于频谱可用性的子载波功率分配算法，但该算法需要对信道状态进行周期性感知. 文献[6] 提出了underlay 频谱共享算法，可有效进行信道选择和功率控制. 但在信道负载率较低，即主用户占用信道的时隙较少的情况下，会对频谱资源造成一定程度浪费.

综合两种共享方式的优点和不足，学者们提出了面向混合频谱共享方式的动态频谱分配策略，使系统可根据次用户的异质性和信道状态，切换频谱共享方式，最大化系统吞吐量. 文献[7]提出了在不完美感知的场景下，根据用户间距离切换频谱共享方式的分配策略，提高了次用户吞吐量，但仍然依赖信道感知. 文献[8]将混合频谱共享方式问题建模为多臂赌博机(multi-armed bandit, MAB)问题，并通过组合多个单用户MAB 策略提供了一种有效的信道分配算法，降低了用户间冲突率. 虽然系统不需要信道感知，但牺牲了系统吞吐量. 因此，混合频谱共享方式对信道感知性能提出了更高的要求. 当系统感知结果较差时，如何提高混合频谱共享模式下动态频谱分配的性能，是实际应用中亟需解决的问题.

Q 学习是一种无模型强化学习算法，能够在无信道感知的情况下，通过Q 值迭代找到最优策略. 近年来，Q 学习技术在动态频谱分配中应用比较广泛，也取得了一些进展. 文献[9]提出了ε 贪心策略下的多智能体Q 学习(multi-agent Q-learning，MAQL)算法，将多个智能体的回报函数用期望回报矩阵的形式表示，而后跟踪每个智能体在学习过程中最大Q 值对应的动作，进行频谱分配. 但该算法需要将所有动作组合枚举，系统复杂度较大. 文献[10]提出了多智能体抗干扰(collaborative multi-Agent anti-jamming,CMAA)算法，虽然该算法是解决通信抗干扰问题，但可将干扰源看成主用户，用以解决多智能体动态频谱分配问题. 该算法中多智能体依次学习外部环境，广播其选择的信道，其他智能体将其视为环境的一部分，继续学习. 但该文献研究对象是扫频干扰，系统状态转移规律性较强，易于学习. 实际应用中，主用户通常在各自信道中传输，主用户间的相关性较小，学习难度相对较大.

综上，Q 学习在解决动态频谱分配问题中，存在一定优势，但大多应用于overlay 频谱共享方式，这是因为Q 学习方法擅长学习主用户忙闲规律，从而便于系统找到频谱空洞，而且普通的Q 学习方法，只能根据信道Q 值大小决定分配哪个信道，但无法判断应以何种共享方式共享信道. 因此，在某些无法实施信道感知的场景下，针对混合频谱共享方式，如何进行动态频谱分配，是频谱分配问题中面临的一个难点.

本文在上述算法的启发下，提出一种混合共享方式下动态频谱分配算法. 该算法可在无信道检测和信道先验知识的条件下，能根据前一时隙信道状态和次用户传输速率需求，实现动态信道分配和频谱共享方式确定，避免次用户间冲突，减少主次用户间冲突，有效提升次用户总吞吐量.

1 系统模型

1.1 网络模型

本文主要研究CR 网络中的频谱分配问题，其网络模型如图1 所示.

图1 网络模型示意图Fig. 1 Schematic diagram of network model

一个小区有M个次用户和N个主用户通过基站进行通信(N≥M). 有N个带宽为B的相互独立信道，分别授权给N个主用户，主用户可随时接入授权信道，无需考虑次用户的传输情况. 同一时隙内，主用户忙闲状态保持不变，主用户在整个通信过程中只占用本授权信道. 次用户j接入信道时，若主用户未占用信道，则次用户可采用overlay 频谱共享方式，以最大发射功率传输信息；若主用户占用信道，则次用户只能选择释放信道或降低发射功率Pcj以underlay 频谱共享方式与主用户共用信道. 为便于分析，每个次用户同一时隙只能分配一个信道，且每个信道同一时隙只能分配给一个次用户.

1.2 系统共存模型

图2 系统共存模型示意图Fig. 2 Schematic diagram of system coexistence model

实际情况中，传播并不总是发生在平坦地面，而是存在多条传播路径的可能性，视距路径也往往会存在被障碍物遮挡等情况，因此理论上功率以d-2衰减. 但是由于实际信道的不同，功率以d-g衰减，g为衰减系数，根据测算，g∈(1.5,5.5)，g=4为各种环境中的一个平均值[12].

根据系统模型和香农公式，可得次用户j信噪比为

1.3 信道状态转移模型

假设主用户占用信道状态符合两状态马尔科夫过程，如图3 所示.

图3 两状态马尔科夫过程示意图Fig. 3 Schematic diagram of the two-state Markov process

主用户在空闲和忙碌状态下的持续时间，分别符合参数为λ(闲)和μ(忙)的指数分布，将传输过程离散为t个长度为τ的时隙，则可得主用户状态转移概率矩阵为[13]

2 算法设计

根据状态转移概率矩阵Pz，模拟出主用户在各时隙内忙闲状态.

系统根据信道衰落、主用户干扰门限、次用户最大发射功率、最低传输速率，以及上一时隙各信道状态等信息，为次用户分配信道和共享方式. 若以overlay 方式共享，但当前时隙信道被主用户占用，则记作主次用户间发生冲突，次用户无法传输信息. 若以underlay 方式共享，但次用户以最低速率传输仍对主用户产生有害干扰，则记作主次用户间发生冲突，次用户无法传输信息. 当不止一个次用户共用信道时，则记作该信道内次用户间发生冲突，次用户无法传输信息.

本问题的目标是在次用户之间不发生冲突，不对主用户产生有害干扰，且满足自身最低传输速率的条件下，次用户总吞吐量最大，则目标函数为

将Q 学习算法应用于动态频谱分配问题，需将上述问题建模为一个有限马尔科夫决策过程，定义智能体、状态集、动作集等要素，并通过如下迭代规则更新Q矩阵[14]：

智能体：系统中与各次用户对应的虚拟次用户.

动作集A：A∈{a1o,a1u,a2o,a2u,···,aMo,aMu}，表示智能体可以采取的动作集合. 每个智能体有N个信道可供选择，每个信道存在overlay 和underlay 两种共享方式，因此动作空间由 2N个动作构成.aio表示选择第i个信道，并以overlay 方式共享信道；aiu表示选择第i个信道，并以underlay 方式共享信道.

回报值r：回报值r是与次用户吞吐量相关的反馈值，本文定义为

3 算法实现流程

从提升次用户总吞吐量，同时尽量降低主次用户间冲突率角度出发，本文提出了针对混合频谱共享方式的基于Q 学习的动态频谱分配方案，具体算法流程如下：

步骤1 初始化. 将各虚拟次用户的Q矩阵Q={Qs,a|Qs,a∈R}2N×2N、选择概率矩阵P={ps,a|ps,a∈[0,1]}2N×2N、状态动作对访问计数矩阵V={visits,a|visits,a∈N∗}2N×2N初始化为零矩阵. 初始化传输时隙数t、折现因子 γ、退火温度T等参数以及系统初始状态s0，初始化信道状态统计向量st={s1,s2,···,sN}为s0.

步骤2 信道初选. 各虚拟次用户统计前一时隙各信道主用户的占用状态，更新信道状态统计向量st，在状态集S中找到对应的状态序号s={s1s2···sN}，根据Q矩阵和玻尔兹曼学习策略[16]，更新选择概率矩阵P中s状态下各动作的选择概率，并根据概率进行信道初选，有较高Q值的动作则有较大概率被选中. 虚拟次用户选择概率矩阵P中各元素p(s,a)通过如下规则更新：

式中：ρ(a/s)为在s状态下选择动作a的概率；Q(s,a)为Q矩阵中s状态下动作a的Q值；T为退火温度，表示Q值大小对概率的影响程度，T较大时，Q值对概率影响较小，反之则影响较大.

步骤3 信道再分配. 建立并初始化冲突统计矩阵H={hx,y|hx,y∈{0,1}}M×M为零矩阵，用来统计M个虚拟次用户信道初选的冲突情况，hx,y=1表示次用户y初选信道与次用户x初选信道冲突，hx,y=0表示次用户y初选信道与次用户x初选信道不冲突. 对没有发生冲突的虚拟次用户，按其初选信道进行分配. 对发生冲突的虚拟次用户，系统需根据其选择概率矩阵P，进行信道再分配：在发生冲突的各虚拟次用户选择概率矩阵P中，找到与其状态动作对(s,a)相对应的概率值ρ(a/s)，并进行比较，概率值最大的虚拟次用户可使用此信道，剩余虚拟次用户在剩余信道中，选择状态s下各自最大概率值对应的动作，更新冲突统计矩阵H；若仍有冲突，继续比较所选动作对应的概率值，直到无虚拟次用户冲突，本时隙信道分配结束，找到所选动作对应的信道和共享方式，并下发信道分配方案.

步骤4 得到回报值. 执行信道分配方案，根据式(11)计算本时隙各虚拟次用户的回报值.

步骤5 更新Q矩阵. 各虚拟次用户根据回报值rj、访问计数矩阵V和式(9)，更新Q矩阵.

步骤6 参数更新. 时隙结束后，传输时隙数t加1，退火温度T以倒数规律随t增加而减小，信道状态统计向量st更新为前一时隙各信道主用户的忙闲状态.

步骤7 判断t是否满足结束条件，若不满足，进入步骤2，若满足则算法结束. 算法流程如图4 所示.

图4 本文算法流程图Fig. 4 The algorithm flow chart of this paper

4 仿真结果与分析

本文考虑一个由N个主用户、M个次用户构成的CR 网络，为验证混合频谱共享方式的可行性和优越性以及本文算法的有效性，本节采用仿真对比方法分析算法的性能.

系统仿真参数设置如表1 所示.

表1 系统仿真参数Tab. 1 System simulation parameters

表2 主用户仿真参数Tab. 2 Simulation parameters of each primary user

表3 次用户仿真参数Tab. 3 Simulation parameters of each secondary user

设置退火起始温度Ts=30 000，终止温度Te=1，退火温度T随着传输时隙数t增加，以参数为1.5 的倒数规律递减，减小至终止温度后停止递减. 仿真长度为30 000 个时隙，为了便于分析，将30 000 个时隙分为100 个相等的学习阶段，每个学习阶段300 个时隙，统计各学习阶段次用户总吞吐量和用户间冲突率，同时采用蒙特卡洛实验策略，每个时隙进行200 次相互独立实验并取其平均值为最后实验结果.

4.1 不同共享方式下性能分析

将本文算法与CMAA 算法[10]和underlay 频谱分配算法[6]进行比较. CMAA 算法和underlay 频谱分配算法分别为overlay 共享方式和underlay 共享方式，且均不依赖信道检测，与本文场景相似，因此加入对比.

图5 是CMAA 算法、本文算法和underlay 频谱分配算法的次用户总吞吐量对比. 可以看出，在学习初期，三种算法吐量均较低，且CMAA 算法高于本文算法和underlay 频谱分配算法. 这是因为在学习初期，三种算法分别接近于在overlay、混合和underlay三种共享方式中随机选择，且仿真中系统各信道负载率较低. 所以在接近随机选择情况下，吞吐量方面overlay 共享方式大于underlay 共享方式，混合共享方式居中. 随着传输时隙增加，三种算法均能够不断与外部环境进行交互学习，优化信道分配策略，提升系统性能，并分别在第35、30 和40 学习阶段逐渐收敛. 收敛后，本文算法与CMAA 算法相比，次用户总吞吐量提高约6.5%. underlay 频谱分配算法受主用户发射功率和干扰门限等因素影响，总吞吐量较低，但波动较小，可保持长时间稳定通信.图6 是CMAA 算法、本文算法和underlay 频谱分配算法的主次用户间冲突率对比. 可以看出，在学习初期，三种算法冲突率较高，且CMAA 算法高于本文算法和underlay 频谱分配算法，原因与图5 类似. 在接近随机选择情况下，overlay 共享方式冲突率大于underlay 共享方式，混合共享方式居中. 随着传输时隙增加，三种算法冲突率均有所降低，并分别在第35、30 和40 学习阶段逐渐收敛. 收敛后，本文算法相对于CMAA 算法主次用户间冲突率下降约66.7%. underlay 频谱分配算法无需考虑各时隙主用户忙闲变化情况，因此当系统找到与所有次用户均匹配的信道后，主次用户间冲突率可下降为0.

图5 不同频谱共享方式下次用户总吞吐量对比Fig. 5 Comparison of throughput under different spectrum sharing modes

图6 不同频谱共享方式下主次用户间冲突率对比Fig. 6 Comparison of conflict rate under different spectrum sharing modes

综上，图5、图6 以三种可实现的强化学习算法为例，分析了混合共享方式的优势和不足. 在三种共享方式中，次用户总吞吐量方面：混合共享方式优于单一共享方式；在主次用户间冲突率方面：undelay 共享方式最低、混合共享方式其次、overlay 共享方式最高，但underlay 共享方式需要牺牲较大吞吐量.

4.2 混合共享方式下性能分析

仿真参数不变，将本文算法与MAB 算法[8]、随机算法和遍历算法进行比较. 其中，随机算法为每个时隙从N个信道中随机挑选M个信道，并随机选择共享方式分配给次用户传输信息. 遍历算法为每个时隙遍历所有信道和共享方式的组合，最终以次用户总吞吐量最大的方案进行分配，用以计算理论上吞吐量和冲突率的最优值. MAB 算法为混合共享方式，且不依赖信道检测，与本文场景相似，因此加入对比.

图7 是本文算法、MAB 算法、随机算法和遍历算法的次用户总吞吐量对比. 可以看出，在学习初期，本文算法和MAB 算法的吞吐量较低，与随机算法相近，通过不断学习交互，更新Q矩阵，优化分配策略，提升吞吐量，并分别在第30 和45 学习阶段逐渐收敛. 收敛后本文算法与MAB 算法相比，次用户总吞吐量提高约16.7%，且收敛更快；与随机算法相比，吞吐量提高78.2%；但与遍历算法的最优策略相比，总吞吐量为遍历算法的91.3%.

图7 混合共享方式下不同算法次用户吞吐量对比Fig. 7 Comparison of throughput of different algorithms under hybrid spectrum sharing mode

图8 是本文算法、MAB 算法、随机算法和遍历算法的主次用户间冲突率对比. 可以看出，各算法性能与图7 基本一致，本文算法和MAB 算法的冲突率随传输时隙增加而降低，并在第30 和45 学习阶段逐渐收敛. 收敛后，本文算法相对于MAB 算法，主次用户间冲突率下降约53.8%，且收敛更快；与随机算法相比，冲突率下降约73.9%. 但与遍历算法的最优策略相比，仍存在差距，遍历算法冲突率可逼近于0.

图8 混合共享方式下不同算法主次用户冲突率对比Fig. 8 Comparison of conflict rate of different algorithms under hybrid spectrum sharing mode

综上，本文算法相比MAB 算法和随机算法，在次用户总吞吐量和主次用户间冲突率方面均具有明显优势，但与遍历算法相比仍存在差距. 这是因为系统的状态是由N个服从马尔科夫随机过程的主用户忙闲状态构成，系统相邻状态存在一定的相关性，同时状态转移也存在不确定性，依靠学习算法无法完美预测所有时隙主用户的忙闲状态，当信道状态预测错误时，会造成冲突率升高，吞吐量降低.

4.3 不同参数λ 和μ 下性能分析

系统各主用户的参数λ 和μ分别等比例扩大3 倍和9 倍，其他参数不变，将本文算法和遍历算法进行仿真对比，如图9 所示. 可以看出，随着参数λ 和μ增大，遍历算法性能没有影响，因为各信道负载率不变，次用户在最优策略下的总吞吐量不变. 但随着系统相邻状态相关性增强，本文算法通过学习，可对信道状态预测的准确性提高，导致吞吐量增大，性能逼近遍历算法.

图9 不同参数λ 和μ 下两种算法吞吐量对比Fig. 9 Comparison of throughput between 2 algorithms with different parameters λ and μ

4.4 扩展性分析

将信道数分别设置为4 个、6 个和8 个，主用户数与信道数相等，次用户数设置为3 个，其他参数不变，对本文算法的性能进行仿真，如图10 所示. 可以看出，在不同信道数的情况下，系统均能随着传输时隙增加，优化信道分配策略，提升次用户总吞吐量，并最终收敛. 随着信道数和主用户数的增加，收敛值逐渐升高，但收敛速度下降，这是因为，信道数增多导致探索时间增加.

图10 不同信道数下本文算法吞吐量对比Fig. 10 Throughput comparison of different channel numbers

将信道数和主用户数设置为8 个，次用户数分别设置为3 个、5 个和7 个，其他参数不变，对本文算法的性能进行仿真，如图11 所示. 可以看出，在不同次用户数的情况下，系统均能随着传输时隙增加，优化信道分配策略，提升次用户总吞吐量，并最终收敛.

图11 不同次用户数的吞吐量对比Fig. 11 Comparison of throughput with different number of secondary users

4.5 复杂度分析

以系统一个时隙的分配过程为例，本文算法中状态空间为 2N，动作空间为 2N，次用户个数为M，则在信道初选过程运算次数为M×(2N)×2N，信道再分配过程运算次数为M2，由于系统中M≤N，因此本文算法信道分配过程复杂度约为O(M×(2N)×2N)+O(M2)≈O(M×N×2N+1).

CMAA 算法的状态空间为 2N，动作空间为N，次用户个数为M，与本文算法复杂度类似，但没有信道再分配过程，因此CMAA 算法复杂度约为O(M×N×2N).

underlay 频谱分配算法的状态空间为 2N，动作空间为N，次用户个数为M，与本文算法复杂度类似，但没有信道再分配过程，因此underlay 频谱分配算法复杂度约为O(M×N×2N).

MAB 算法的状态空间为1，动作空间为 2N，次用户个数为M，信道选择过程运算次数为2N×M，策略组合过程运算次数为M2，因此MAB 算法复杂度为O((2N+M)×M).

随机算法为任意选取信道和共享方式进行分配，因此复杂度为O(1).

各算法复杂度对比表4 所示.

表4 复杂度对比Tab. 4 Comparison of complexity

综上所述，本文算法与CMAA 算法、underlay频谱分配算法、MAB 算法、随机算法相比，复杂度较高，但性能有显著提升. 由于本文为多次用户和多信道场景，M≥2，N≥2，所以本文算法的时间复杂度小于遍历算法，且随着次用户和信道数量增加，复杂度差距将逐渐增大.

5 结 论

本文构建了混合频谱共享方式下的动态频谱分配模型，并将Q 学习思想加以改进，提出了一种解决混合共享方式下多次用户频谱分配问题的算法. 仿真结果表明，混合共享方式与单一共享方式相比，在主次用户间冲突率方面，低于overlay 共享方式，高于underlay 共享方式；但在次用户吞吐量方面，明显优于两种单一共享方式.

在混合共享方式的4 种算法对比中，本文算法能够在避免次用户间冲突前提下，在次用户总吞吐量、主次用户间冲突率两个方面优于MAB 算法和随机算法，且随着系统相邻状态相关性提高，算法性能可逼近遍历算法. 此外，本算法无需信道检测，并考虑了次用户传输速率需求的差异，更符合实际情况.