基于NC⁃OFDM系统的快速资源分配算法

叶中付，王鹏宇，杨会超，王 勇

（1.中国科学技术大学信息科学技术学院，合肥 230027；2.国防科技大学电子对抗学院，合肥 230037）

引 言

无线频谱是不可再生的宝贵资源，大量研究表明［1⁃3］，在静态频谱分配策略下，全球频谱资源利用呈现出高度的不均衡，非授权频段的占用拥挤与授权频段的大量频谱空洞（Spectrum hole）并存，整体频谱资源浪费严重。认知无线电技术通过在不影响已接入用户通信质量的前提下对授权频谱的二次利用，提高了频谱利用率，有效缓解了用户数量剧增与频谱资源短缺的矛盾［4⁃5］。

非连续正交频分复用（Non⁃continuous orthogonal frequency division multiplexing，NC⁃OFDM）技术是传统正交频分复用（Orthogonal frequency division multiplexing，OFDM）技术的改进。NC⁃OFDM通过认知无线电（Cognitive radio，CR）技术感知通信环境中的频谱占用情况，使认知用户只占用空闲频段进行通信，并在授权用户开始使用该频段时立即退出，实现认知用户与授权用户的频谱共享。

资源分配是多信道无线通信系统的一项关键任务，通信系统根据子信道的信道状况分配功率资源与比特资源，以降低发射功率、增加系统容量或降低误比特率［6］。文献［7］改进了传统的Fischer算法［8］，通过计算子信道可传输信息的最大噪声门限，一次性排除了所有不可用的子信道，并在比特分配时采用次优思想进行调整优化，降低了资源分配问题求解的复杂度。文献［9］以功率最小化为目标，将资源分配问题转化为注水问题，利用注水性质快速调整注水线，实现了比特率与误比特率约束下的快速资源分配。文献［10］从噪声功率出发，提出了在认知环境下的线性注水法。文献［11］考虑多用户资源分配，通过引入调度因子、衰减因子，在比例公平的原则下保证每个用户都能满足一定的通信要求。文献［12］考虑多输入多输出通信系统中子信道状态信息不完全已知的情况，利用部分已知子信道状态对未知子信道进行估计，在保证用户间比例公平性的同时，最大化系统容量并有效减小了系统的反馈开销。

在单用户前提下，根据优化目标不同，传统OFDM系统的资源分配算法可分为功率自适应、速率自适应与误比特率自适应3类［13］。由于NC⁃OFDM通信系统利用授权频段的频谱空洞进行通信，频谱空洞的数量与噪声电平无法预知，因此在总发射功率和误比特率约束下最大化总比特率的速率自适应准则更为适合。经典的速率自适应资源分配算法主要有贪婪算法［14］和理想注水算法［15］。实用注水算法［16］在理想注水算法进行初始资源分配的基础上使用贪婪算法进行剩余资源分配，解决了理想注水算法的粒度问题，是一种适用于实际情况的资源分配算法。贪婪算法与实用注水算法是多信道无线通信系统中采用的两种最优资源分配算法。然而，在NC⁃OFDM通信系统的工作环境中，无线环境是变化的，因此需要动态地调整各子信道分配的资源。为不干扰授权用户通信，NC⁃OFDM通信系统中认知用户需要在授权用户接入通信时立即退出，这使得NC⁃OFDM通信系统的资源分配算法与固定子信道的OFDM通信系统的资源分配算法相比有更高的实时性要求，贪婪算法与实用注水算法的实时性不足，有必要研究资源分配的快速算法。

本文提出的基于NC⁃OFDM通信系统的快速资源分配算法使用速率自适应准则，首先通过一次判断得到认知用户使用的子信道（以下简称认知子信道）集合，降低解空间的维数；接着直接计算注水常量，完成初始比特与功率分配；最后基于二分思想，对已排序的认知子信道（方法1）或未排序的认知子信道（方法2）进行剩余资源的分配。理论分析与仿真实验表明，本文算法与最优算法的资源分配结果相同（方法1）或相近（方法2），但所需迭代次数更少，复杂度更低，资源分配的速度更快。

1 频谱感知与NC⁃OFDM通信系统

1.1 频谱感知

在NC⁃OFDM通信系统中，进行无线资源分配的前提是对空间中频谱状态的精准感知。假设与分别表示频点f被其他用户占用以及频点f空闲，在t时刻频点f的感知信号可表示为

式中：s(f，t)为在t时刻频点f上的已接入用户信号，n(f，t)为在t时刻频点f上的加性噪声。

基于式（1）中的信号模型，可使用能量检测法［17］、循环谱估计方法［18］、压缩感知方法［19］和阵列信号处理方法［20］等一系列方法进行频谱感知。将待检测的频谱空间分为L个子信道，假设子信道i的中心频率为fi、带宽为B，将已接入用户信号s(f，t)视为大功率噪声，则子信道i的噪声功率估计值为

式中T为频谱感知的检测周期。结合子信道的增益先验hi，子信道i的增益噪声比可表示为

对于认知用户来说，被占用的子信道的噪声功率较大、增益噪声比较小，而空闲子信道的噪声功率较小、增益噪声比较大。空闲子信道与被占用的子信道之间增益噪声比的差异为资源分配算法提供了依据。在后续的资源分配算法中，将每个子信道的增益噪声比视为已知量。

1.2 NC⁃OFDM通信系统

NC⁃OFDM是一种特殊的多载波传输方案，NC⁃OFDM通信系统发射与接收的基本模型如图1所示［21⁃23］。

在NC⁃OFDM发射系统中，认知用户根据频谱感知结果进行资源分配，将原始数据经过串并转换后以不同的功率、比特分配到高频空闲子信道上，并行数据经过信道编码、调制、插入循环前缀、频谱搬移、并串转换、插入导频和上变频后发射到空间中。

在NC⁃OFDM接收系统中，接收高频信号经过下变频、串并转换、频谱搬移、低通滤波、去除循环前缀、解调、信道译码和并串转换后还原为原始的二进制数据。

由图1可见，NC⁃OFDM通信系统模型与OFDM通信系统模型类似，二者区别在于作为OFDM通信系统的扩展，在NC⁃OFDM通信系统中使用的子信道不是固定且连续的，NC⁃OFDM通信系统需要依据频谱感知的结果对子信道分配的资源进行实时调整，通过仅在空闲子信道分配正的功率、比特实现空闲频带的再利用，提高频谱空间的利用率。

图1 NC-OFDM通信系统发射和接收模型Fig.1 Transmission and receiving model of NCOFDM communication system

2 资源分配算法

2.1 资源分配问题描述

资源分配算法通过对功率、比特的合理分配达到节省功率、增大通信系统容量、减小误比特率等效果。在单用户前提下，根据优化目标不同，传统OFDM通信系统的资源分配算法可分为功率自适应、速率自适应与误比特率自适应3类。在NC⁃OFDM通信系统中，为不影响已接入用户与新接入授权用户的通信质量，认知用户需要根据信道状况动态调整发射的总比特数。因此，约束发射功率与误比特率并自适应调整比特率的速率自适应资源分配算法更为适用。基于速率自适应准则的单用户资源分配问题可表示为

式中：L为子信道总数；bi为第i个子信道单位符号的比特数（与调制方式对应）；pi为第i个子信道的发射功率；Ptot为总发射功率上限；Γ≈-ln(5BER)/1.5为使用多进制正交振幅调制（Multiple quadrature amplitude modulation，MQAM）与格雷码联合调制时的信噪比差异［24］，BER是目标误比特率上限约束。

经典的速率自适应资源分配算法主要有贪婪算法和注水算法。贪婪算法［14］的资源分配是逐比特的，每个比特的迭代过程都需要重新计算功率增量并寻找最小功率增量的子信道，资源分配的结果是最优的，但运算复杂度非常高，在系统总发射功率与子信道数目很大的情况下，贪婪算法的迭代次数难以被实际系统所接受。理想注水算法［15］的基本思想是为增益噪声比较高的子信道分配更多的功率和比特，使系统容量最大。然而，在实际系统中，比特分配必须是有限粒度的，理想注水算法不适用。实用注水算法［16］首先利用理想注水算法求解功率与比特分配的初始值并对比特向下取整，得到初始的资源分配；再使用贪婪算法完成剩余资源分配。实用注水算法与贪婪算法的资源分配结果一致，是最优的资源分配算法，其计算复杂度主要来源于初始资源分配中注水线的迭代求解与剩余资源分配中贪婪算法的迭代求解。由于NC⁃OFDM通信系统对实时性有较高的要求，贪婪算法与实用注水算法的实时性难以满足，有必要提出资源分配的快速算法。

2.2 快速资源分配算法

本文提出两种速率自适应准则下的快速资源分配算法。算法的思路是，首先根据NC⁃OFDM通信系统的频谱环境计算功率门限，一次性选出认知子信道，降低解空间的维数；然后基于注水思想，直接计算出注水线，完成功率和比特资源的初始分配；最后依据二分思想，对已排序的认知子信道（方法1）或未排序的认知子信道（方法2）进行剩余资源的分配。

快速资源分配算法具体步骤如下：

步骤1认知子信道的选取

（1）根据总发射功率限制Ptot计算子信道平均发射功率pav=Ptot/L。结合误比特率要求计算最差子信道传输1比特数据所需要的功率门限

（2）对每个子信道进行判断，若ti>pav，表明子信道i状况较差，不对其分配功率和比特；否则，子信道i为认知子信道，每个认知子信道至少可以分配1 bit。设选取出N个认知子信道，认知子信道的序号记为1，2，…，N。

步骤1利用NC⁃OFDM通信系统频谱环境中的认知子信道与被占用的子信道之间增益噪声比差别较大的特点，通过一步比较直接选出认知子信道，加快了算法运算速度。

步骤2资源的初始分配

（1）对所有认知子信道使用理想注水算法分配功率。由于认知子信道已经选出，并且每个认知子信道必然被分配至少1 bit，因此注水常量K可由下式直接计算

由于步骤1选出的认知子信道至少分配1 bit，因此步骤2中的注水常量与初始分配的比特、功率可直接计算得出，本文算法在初始资源分配结果与实用注水算法相同的前提下，避免了实用注水算法初始资源分配的反复迭代操作。

步骤3剩余资源的分配方法1

（1）计算认知子信道增加1比特的功率增量为

（2）将功率增量从小到大排序，得到

（4）调整子信道分配的比特

步骤3完成对剩余资源的分配。考虑到在理想注水算法中，每个子信道的最终分配比特至多较初始分配比特多1 bit，本算法基于二分思想搜寻可增加比特的认知子信道，完成剩余资源的分配。所提出的方法1使用已排序增量功率求解满足剩余可分配功率约束的最大总增量比特，其效果相当于最优算法；所提出的方法2使用未排序增量功率直接求解满足剩余可分配功率约束的最大总增量比特，其分配结果与最优算法相近，但计算复杂度显著降低。

2.3 性能分析

本小节对资源分配算法进行性能分析，分别将剩余资源分配步骤采用方法1与方法2的两种情况记为本文算法1与本文算法2。

在认知子信道选取步骤中，本文算法通过门限比较一次选出所有认知子信道，每个认知子信道至少分配1 bit。在NC⁃OFDM系统的应用环境中认知子信道与被占用的子信道增益噪声比相差较大的前提下，本文算法选取的认知子信道最优。

在资源的初始分配步骤中，本文算法首先使用理想注水算法完成功率、比特的预备分配，对功率最高效率的利用。在功率、比特预备分配的基础上，本文算法通过比特的向下取整得到比特的初始分配，通过计算得到功率的初始分配。取整操作产生了剩余功率，剩余功率可分配到部分认知子信道上，以增大对应认知子信道分配的比特。根据理想注水算法的原理，对于每一个认知子信道，剩余功率最多可以额外为其分配1 bit。

在剩余资源的分配步骤中，本文算法将剩余功率分配到部分认知子信道上。本文算法1首先将所有认知子信道的功率增量进行排序，并在排序结果基础上使用二分思想选出所有可以增加比特的子信道。本文算法1可以保证在功率约束下，所增加的总比特数最多，即本文算法1最优。本文算法2计算未排序的认知子信道的功率增量，并使用二分思想选取可增加比特的子信道。由于本文算法2中认知子信道功率增量的排列有随机性，无法保证其增加的总比特数最多。在最差情况下，本文算法2与本文算法1最终分配的总比特数最多相差（N-1）bit，因此本文算法2次优。

2.4 复杂度分析

本小节分析本文提出的两种快速资源分配算法的时间复杂度，并与贪婪算法、实用注水算法进行比较。假设4种算法划分的子信道总数为L，认知子信道个数为N，最终分配的比特总数为在实际应用中通常有Rt≥L≥N。

贪婪算法对每个分配的比特，每次迭代在L个子信道中寻找增加1比特所需功率最小的子信道，初始化过程计算功率需要L次乘法，后续每次迭代需要1次乘法、L次比较，迭代过程重复Rt次。贪婪算法共进行L+Rt次乘法、RtL次比较。贪婪算法的渐进时间复杂度为O(RtL)。

实用注水算法首先依据增益噪声比对子信道排序，需要L log2L次比较，迭代求解可用子信道与计算注水线需要L-N次乘法与比较，初始资源分配需要N次乘法。在剩余资源分配步骤中，使用贪婪算法每次在N个子信道中寻找增加1比特所需功率最小的子信道，每次迭代需要1次乘法与N次比较，迭代过程至多重复N次。因此实用注水算法共需要L+N次乘法、L log2L+L+N2-N次比较。实用注水算法的渐进时间复杂度为O(L log2L+N2)。

本文提出的快速资源分配算法，在认知子信道选取步骤，需要进行L次乘法与比较。在初始资源分配步骤，求解注水线与初始资源分配需要N次乘法。在剩余资源分配步骤，若采用方法1，认知子信道排序需要进行N log2N次比较，迭代计算需要进行log N次比较；若采用方法2，迭代计算需要进行log2N次比较。因此本文算法1共需要L+N次乘法、L+N log2N+log2N次比较，渐进时间复杂度为O(L+N log2N)；本文算法2共需要L+N次乘法、L+log2N次比较，渐进时间复杂度为O(L)。

综上所述，本文提出的两种快速资源分配算法较最优的实用注水算法与贪婪算法具有更低的时间复杂度。

3 仿真结果分析

3.1 仿真环境

仿真实验使用的软件为MATLAB R2019b，硬件为配有Intel i5⁃4440、3.10 GHz的处理器和8.00 GB内存的个人计算机。

3.2 仿真结果分析

假设子信道总数为20，总发射功率20 W，误比特率10-4。空闲子信道占子信道总数的50%，空闲子信道的增益噪声比服从[8.5，11.5]d B范围内均匀分布，被占用的子信道的增益噪声比服从［-1.5，1.5］d B范围内均匀分布。图2、3分别展示了同一次蒙特卡洛实验中贪婪算法、实用注水算法、本文算法1和本文算法2的功率、比特分配结果，图2、3中各子信道的增益噪声比以虚线标注。

由图2、3可见，提出的两种快速资源分配算法与最优算法所使用的子信道一致。同时，本文算法1的功率、比特分配结果与贪婪算法、实用注水算法一致，表明本文算法1为最优资源分配算法。由于本文算法2在剩余资源分配步骤与最优算法采取的策略不同，本文算法2与最优算法的资源分配结果略有区别，但其分配的总比特数与最优算法接近。

图2 功率分配结果Fig.2 Power allocation results

假设子信道总数为200，总发射功率200 W，误比特率10-4。空闲子信道占子信道总数的50%，空闲子信道的增益噪声比服从以某个均值为中心、3 d B范围内的均匀分布，被占用的子信道的增益噪声比服从［-1.5，1.5］d B范围内均匀分布。进行100 000次蒙特卡洛实验，贪婪算法、实用注水算法与本文提出的两种快速算法所分配的平均总比特数、平均迭代次数与平均运行时间随空闲子信道平均增益噪声比的变化曲线如图4~6所示。

由图4可见，本文算法1分配的平均总比特数与最优的贪婪算法、实用注水算法完全一致，表明本文算法1是最优的资源分配算法；本文算法2分配的平均总比特数略低于最优算法，表明本文算法2为次优的资源分配算法。图5表明在所有对比算法中，贪婪算法需要的迭代次数最多，实用注水算法次之，本文提出的两种算法的平均迭代次数最少，仿真实验结果与理论分析相符。图6表明由于本文提出的两种算法的迭代次数更少，所需要的平均运行时间较经典算法更少，表明了本文算法的实时性更好；由于本文算法1在剩余资源分配阶段需要一次排序，本文算法2不需要排序，因此本文算法2的实际运行时间少于本文算法1。

图3 比特分配结果Fig.3 Bit allocation results

图4 平均总比特数随空闲子信道平均增益信噪比变化曲线Fig.4 Average bit number versus the average gain-noise ratio of idle sub-channels

图5 平均迭代次数随空闲子信道平均增益信噪比变化曲线Fig.5 Average number of iterations versus the average gain-noise ratio of idle sub-channels

图6 平均运行时间随空闲子信道平均增益信噪比变化曲线Fig.6 Average running time versus the average gain-noise ratio of idle sub-channels

4 结束语

NC⁃OFDM是认知无线电技术的应用，认知用户通过认知无线电技术感知通信环境中的频谱空洞，利用空闲频段进行通信，并在授权用户开始接入通信时立即退出，达到增大频谱利用率的效果。本文基于速率自适应准则提出了两种适用于NC⁃OFDM通信系统的资源分配算法，其包含认知子信道选取、初始资源分配和剩余资源分配3个步骤。在认知子信道选取步骤，通过子信道的增益噪声比与误比特率要求计算功率门限，一次性选出认知子信道，降低了解空间的维数；在初始资源分配步骤，基于注水思想，通过直接计算注水线、向下取整预备分配的比特，得到初始的功率和比特分配结果；在剩余资源分配步骤，基于二分思想对已排序（方法1）或未排序（方法2）的认知子信道求解应调整的子信道序号，并完成剩余资源的快速分配。理论分析与仿真结果表明，本文提出的算法与最优算法的资源分配结果相同（方法1）或相近（方法2），显著加快了资源分配的速度。