董晓庆，程良伦，郑耿忠，王涛

（1.韩山师范学院物理与电子工程学院，广东 潮州 521041；2.广东工业大学计算机学院，广东 广州 510006；3.广东工业大学自动化学院，广东 广州 510006）

1 引言

随着无线通信技术和无线业务的飞速发展，用户流量需求激增。根据Cisco 的移动数据业务预测白皮书，2021 年全球的移动流量需求将达到49 EB，是2016 年的7 倍；同时，国际电信联盟ITU（International Telecommunication Union）预测，2020 年全球移动通信频谱需求将达到1 340～1 960 MHz。但是，目前大部分的频谱资源已分配给不同机构使用，频谱资源的紧缺成为制约无线网络发展的重大瓶颈，即使第五代网络（5G 网络）增加可利用频谱资源，频谱资源仍然非常珍贵；另一方面，基于授权的静态频谱分配方法将无线频谱划分为若干固定宽度的频谱段，由政府管理部门分配给授权用户独占使用，利用率低。德国、荷兰、美国的部分地区，在20～3 000 MHz频段的频谱利用率仅为46%，新加坡部分地区在80～5 850 MHz 频段的利用率仅为4.54%[1]。因此，如何提高频谱资源利用率，以缓解激增的用户流量需求与紧缺且利用率低下的频谱资源的矛盾，是无线网络需要解决的重要问题。

认知无线网络为解决频谱资源紧缺及利用率低的问题提供了有效的技术手段。获得频谱授权的用户称为主用户，未获得频谱授权的用户称为次用户。主用户对频谱拥有优先使用权，可随时使用频谱；同时，主网络可将空闲的授权频段出让或租赁给次用户，使次用户可以共享使用授权频段[2]。在该网络中，每个认知无线设备可以感知自己所在区域的通信环境，并通过集中式或分布式的方式处理这些感知信息，最后做出最佳的传输决策。认知无线电技术主要包括频谱感知、频谱管理、频谱切换等功能。首先，通过认知无线电的频谱感知功能，周期性地监听目标频段，捕捉未被利用的空闲频谱，确定频谱的使用状态；获得频谱感知信息之后，频谱管理模块根据感知结果分析周围的频谱环境，从中提取可用频谱的相关信息，根据频谱分析的结果制定最佳的频谱使用策略[1]。在认知异构无线网络环境下，多个主网络重叠覆盖，网络频谱资源特性各异，如频谱价格、频谱宽度、时延、分组丢失率等；同时，次网络中分布多个次用户及多种业务需求，不同业务对速率、支付价格、时延等要求也不尽相同，如何同时考虑频谱资源的异构性、信道条件动态性及多次用户的不同需求，高效合理地为各个次用户选择接入匹配的频谱资源是一个挑战。

综上所述，本文基于基础设施的认知异构无线网络结构，重点关注认知无线网络感知到空闲频谱信息及用户业务需求后频谱资源分配方法的研究，综合考虑不同网络频谱资源属性、不同业务需求的差异化及信道条件动态性，以所有用户总传输速率最大化为目标，以业务需求及频谱资源为约束条件，对频谱资源进行有效分配，主要贡献如下。

1)在未来无线通信网络密集部署环境下，基于认知无线网络技术，综合考虑多主网络的异构频谱特性、多次用户的需求差异化及信道条件的动态性，以所有用户总传输速率最大化为目标，以业务需求及频谱资源为约束条件，建立了频谱资源分配的数学模型。

2)设计了一种多项式时间复杂度的化简求解方法。该方法根据用户业务需求及过往周期分配结果修正效益矩阵实现约束条件化简，将数学模型转化为标准形式的0-1 规划问题，并对传统匈牙利算法进行改进以求解该频谱分配问题。

2 相关工作

目前，异构无线网络动态频谱分配主要有基于图论[2-4]、基于频谱交易[5-7]、基于博弈论[8-11]、基于智能优化算法[12-14]等方法。王钦辉等[2]、Tragos 等[15]、Tsiropoulos 等[16]分别综述了频谱资源动态分配方面的研究进展，总结了目前一些主流方法。

基于图论的频谱资源分配方法将认知无线电网络拓扑结构抽象成无向连接图。顶点表示参与分配的次用户，每个顶点有可用信道集合，图的边集则由干扰限制决定，当且仅当2 个用户节点不能同时使用某信道时，相应顶点用一条边连接[2]。Peng 等[3]给出了频谱分配的图着色模型和算法，对分配的收益和公平性进行了较详细的探讨，并证明频谱分配是一个非确定性多项式难（NP-hard）问题。朱冰莲等[4]针对图论频谱分配模型下最优频谱分配策略搜索解困难、耗时长的问题，提出一种采用多策略离散人工蜂群的频谱分配算法，首先根据感知技术得到通信环境状况，建立频谱分配的图论模型，然后引入多策略离散人工蜂群算法进行最优频谱分配策略的搜索。基于图论的方法简单易行，多适用于静态的网络环境，这意味着拓扑结构的每次改变均需要重新计算分配，如果拓扑结构变化比较频繁，则算法的有效性将受到很大挑战[2]。

基于频谱交易的分配方法借鉴商品交易的思想，将频谱视为商品在用户之间进行交易，提供频谱资源的为频谱卖家，需要使用频谱的用户为频谱买家[2]。为协调满意度、利润及价格三者之间的关系，Ileri 等[5]利用买家接受模型描述买家满意度与价格之间的关系，买家以一定概率接受卖家的频谱服务，通过卖家利润模型来描述卖家利润与价格的关系。Gandhi 等[6]以最大化卖家利润为目标、以干扰限制为约束条件，利用线性规划对频谱分配进行了分析，由于考虑干扰限制，求解最优结果是一个NP-hard 问题，因此，文献[6]对干扰限制条件进行线性化处理，可在多项式时间内求得次优（suboptimal）解。为了提高认知无线网络中频谱共享所产生的效益，张士兵等[7]提出了一种基于代理的频谱交易算法，该算法以代理商作为频谱交易和分配的中介，减轻了多主用户、多次用户频谱交易过程中的系统开销，主用户服务提供商之间的竞争或合作和次用户之间的竞拍均采用纳什均衡作为最终的结果。基于频谱交易的方法适用于主用户与次用户之间基于租用关系的应用场景，该类方法以定价机制为切入点，基于卖家利润及买家满意度完成交易。

认知无线电网络中节点行为可能是自私和动态的，动态频谱共享算法需要对此做出相应决策。博弈论为研究主体行为直接相互作用时的决策均衡提供了决策模型和理论，为动态频谱共享问题提供了可行思路。Cao 等[8]提出一个议价博弈的分布式分配算法，通过议价博弈，使最优分配不需要在每次拓扑结构变化时重新计算，同时，为了考虑算法的公平性，还基于Feed Poverty 策略设计了博弈算法，使算法公平性更好，但文献[8]中的议价博弈交易框架假设网络节点相互合作，然而，实际系统中的节点可能是自私的。用户行为的自私性使静态博弈模型难以获得高效的纳什均衡，重复博弈常被用来分析长期动态频谱共享，由于需要多次博弈，重复博弈中的用户可根据历史行为做出更为灵活有效的决策，Etkin 等[9]针对非合作用户之间的博弈，运用Folk 定理[10]分析了重复博弈中的效率，并通过实验证明了其在长期动态频谱共享中的高效性；孙杰等[11]提出了一种适用于次用户组成的无线多跳网络的underlay 方式下的全分布式频谱分配算法，该算法将频谱分配问题建模成静态非合作博弈，证明了纳什均衡点的存在，并给出了一种求解纳什均衡点的迭代算法，然而当某个主网络对未来传输效用不够重视时，它会为了获得比垄断效用更高的传输效用而偏离当前的合作垄断，从而降低了其他主网络的当前和未来数据传输效用。

进化算法（EA,evolutionary algorithm）由于其进化操作规则的概率性、固有的并行性及充分利用适应值函数而不需要其他先验知识等特点，在搜索过程中不易陷入局部最优、不局限于单值解，适合求解传统方法难以解决的复杂优化问题。邝祝芳等[12]针对无线 Mesh 网络中多目标优化的频谱分配问题，以最大化总带宽和最小化占用频谱数为目标，利用粒子群优化（PSO,particle swarm optimization）算法在多目标优化方面的优势，提出基于 PSO 的多目标优化频谱分配算法 PSOSA，算法考虑频谱之间的差异并重新定义 PSO 的粒子及粒子的3 种运算规则。李鑫滨等[13]在人工蜂群算法中引入动态加速因子和种群自适应比例因子，提出一种新的动态加速种群自适应人工蜂群算法，并将认知无线电TV 频段频谱分配模型中的分配矩阵与动态加速种群自适应人工蜂群算法中的可行解相对应，实现了空闲TV 频段频谱的合理分配。Hasan 等[14]针对第五代网络（5G 网络）中多异构主网络重叠的场景，根据主网络的频谱特性及次用户的需求，利用改进的遗传算法及粒子群优化算法求解频谱分配问题，取得了较好的效果，但其没有考虑频谱资源的异构性，应用场景相对简单。

综上所述，异构无线网络频谱分配已经取得了较多的研究成果，但仍存在场景适应性的问题，比如基于图论的分配方法适用于静态的网络环境；基于频谱交易的分配方法适合于主用户、次用户间为租用关系的认知无线电系统，应用范围具有局限性；博弈论分配模型一般用于主体行为直接相互作用时分析频谱用户之间的竞争与合作关系；对频谱分配模型较复杂，难以在多项式时间求解的模型，可应用基于进化算法的分配方法进行求解。同时，上述方法研究对象大多是传统的信道分配问题，即频谱资源的特性较为单一，没有考虑多异构主网络频谱资源的异构性。本文考虑更多的实际应用需求，包括主网络间及主网络内频谱资源的异构性、次用户业务类型及服务质量要求差异化、信道条件的动态性，上述方法显然不能直接用于本文的频谱分配，所以本文工作具有一定的研究意义。

3 频谱资源分配0-1 规划模型

3.1 网络模型

图1 为认知异构无线网络结构，假设存在N个主网络重叠覆盖（如蜂窝网、WiMax 网络），令网络集为PN={pn1,pn2,…,pnN}，网络中的主用户均匀分布，其行为相互独立，建模为开关二状态的泊松过程。因此，频谱资源可建模为空闲及忙状态的独立随机二状态模型。空闲表示目前没有主用户占用该频谱资源，可分配给次用户，但同一时间只可分配给一个次用户；忙状态表示该频谱资源被主用户所占用，不能分配给次用户。

图1 认知异构无线网络结构

假设次网络为基于基础设施（认知基站）的认知网络，次用户为认知网络（次网络）中基站覆盖范围内的配备认知设备的用户，同一时间只能接入一个频谱，次用户集为SU={su1,su2,…,sum}。频谱资源包括主网络中空闲的授权频谱及非授权的ISM（industrial scientific medical）频谱，令频谱集为SP={sp1,sp2,…,spn}。认知用户周期性地感知识别信道条件、空闲频谱信息，并将其与用户业务请求信息发给认知基站。频谱价格可通过频谱代理获得并存储于认知基站中，相比信道条件的动态变化，频谱价格可视为静态常量。为简化计算复杂度，假设同一网络内频谱资源分组丢失率状况相近且变化相对缓慢，则分组丢失率等属性信息可通过次用户以频谱使用反馈报告的形式发给认知基站，形成各网络频谱属性数据。认知基站以次用户应用请求信息、信道条件、空闲频谱信息、过往周期的分配决策结果等作为决策依据，进行新一轮的频谱资源分配决策。这里需要注意，没有被主用户占用的频谱定义为空闲频谱，认知基站在新一轮分配决策时需根据过往周期分配决策结果，确认频谱是否已被次用户所占用，若被占用且满足用户业务需求，则该频谱不参与新一轮的分配决策。

用户的传输速率与其获得的频谱带宽、传输功率及信噪比有关，根据香农定理，用户j选择接入频谱资源k的传输速率可表示为

其中，bjk表示用户j占用频谱资源k可获得的带宽；xjk表示次用户j占用频谱资源k的概率，xjk=1 表示占用该频谱，xjk=0 表示不占用该频谱；Sjk、Njk分别表示用户j利用频谱资源k进行传输时的信号功率及噪声功率。本文研究基于overlay 模式下主网络空闲频谱的机会式接入及非授权ISM 频谱的分配，因此，次用户对主用户的干扰可忽略不计，可利用大传输功率以获得较快的传输速率；由于次用户为认知基站覆盖范围内配备认知模块的用户，相对于与主网络的距离，次用户之间的距离可忽略不计。

3.2 问题建模

不同网络间频谱的带宽、时延、分组丢失率等特征属性差异较大，同一网络内的频谱块差异较小，在一定范围内波动；次用户存在语音、视频、文件传输等多种不同的业务需求，不同业务对价格、速率、时延、分组丢失率等要求不一样，因此，本文的频谱资源分配需综合考虑频谱资源的属性、信道条件及次用户的业务需求。

根据式(1)所示用户的传输速率，可推导出所有次用户的总传输速率，如式(2)所示。

如式(2)所示，在空闲频谱资源受限情况下，根据用户业务需求及信道条件，选择不同的频谱资源可得到不同的传输速率。因此，本文以所有次用户总传输速率最大化为目标，以频谱资源受限、次用户服务需求等为约束条件，将频谱分配问题建模为非线性约束0-1 整数规划，具体如式(3)所示。

其中，式(3)表示最大化所有次用户获得的传输速率；式(4)表示接入频谱需满足用户的速率需求；式(5)表示接入网络y频谱资源的所有用户占用的带宽总和不能超过该网络空闲频谱资源总带宽，其中，By为网络y的空闲频谱资源的总带宽限制；式(6)表示次用户j接入频谱价格不大于其可支付价格；式(7)表示次用户接入的频谱时延不大于其时延要求；式(8)表示次用户接入频谱分组丢失率不大于其分组丢失率要求；式(9)表示次用户同一时间最多只能接入一个频谱；式(10)表示任一频谱资源不能同时分配给多于1 个的次用户；式(11)表示次用户j占用空闲频谱k的概率，占用值为1，否则值为0。

4 求解方法

由第3 节可知，本文频谱分配是一个非线性约束0-1 整数规划问题，是NP-hard 问题，不存在多项式时间内求解的算法，因此，本文试图通过对3.2节的数学模型进行化简，寻求简单的方法进行求解。同时，针对复杂的分配模型，本文还将利用改进的遗传算法进行求解，以比较2 种基于不同技术途径解决方法的求解思路。

4.1 化简方法

如第3 节系统模型可知，本文将复杂的频谱分配问题建模为非线性多约束条件0-1 规划问题，化简方法将通过分析约束条件及目标函数，对约束条件进行化简，并通过改进匈牙利算法进行求解。

4.1.1 构造效益矩阵及决策矩阵

不同的用户业务对频谱资源要求不一样，不同频谱资源具有不同的属性，通过次用户与频谱资源的良好匹配，可实现用户总传输速率的最大化。基于此，在每一轮频谱分配决策周期，本文首先根据认知基站获得的空闲频谱集及申请业务的次用户，构造效益矩阵及决策矩阵。由于空闲频谱资源可能在过往决策周期已被分配给其他次用户，在新一轮频谱分配决策时，需结合过往决策周期的频谱分配结果，若空闲频谱已分配且满足次用户的业务需求，则在构造矩阵时需排除该空闲频谱。效益矩阵及决策矩阵具体如表1 和表2 所示。

表1 效益矩阵

表2 决策矩阵

如表1 所示，效益矩阵表示次用户选择相应频谱资源获得的效益值。因为本文的目标函数是用户总传输速率的最大化，所以矩阵中各元素的值（效益值）直接用次用户选择对应频谱资源时的传输速率表示。如式(1)所示，传输速率取决于频谱带宽、信号功率及噪声功率。表2 所示的决策矩阵用于存储分配决策结果，表示次用户与频谱资源的匹配关系，xjk=1表示次用户j选择接入频谱资源k，xjk=0表示不接入。次用户是否接入该频谱，除了考虑该频谱对应的传输速率外，还需考虑频谱资源属性是否与用户业务需求匹配；同时，由于一个次用户最多只能接入一个频谱资源，一个频谱资源最多只能分配给一个次用户，所以决策矩阵任一行或列最多只能有一个元素为“1”。由表1 和表2 可知，化简方法即是根据表1 中各用户接入对应频谱获得的传输速率，并结合用户服务需求选择匹配的频谱，以最大化传输速率为目标，最终得到表2 所示的决策矩阵中频谱与次用户的匹配关系。

4.1.2 化简约束条件

对于多约束条件的分配问题，无法通过匈牙利算法直接求解，因此，本文试图对约束条件进行约简。

不同频谱资源属性及用户业务需求均不一样，如第3 节的数学模型，只有满足价格、速率、时延等约束条件的频谱资源才会分配给次用户。比如对于用户j及频谱资源k，比较频谱k各属性值是否满足次用户j的业务需求，若不满足用户j的价格、速率、时延等任一方面的需求，则次用户不会选择接入该频谱，即可将效益矩阵中第j行第k列的元素rjk置为0，使选择该频谱的效益值为0，确保频谱k不会分配给次用户j；若频谱资源k各方面属性均能满足用户k的需求，则效益矩阵中元素rjk值保持不变。依次类推，可将不满足用户业务需求的频谱对应效益值置为0，确保用户接入满足服务需求的频谱。基于此，本文根据频谱属性与用户业务需求关系，即式(4)～式(8)所示的约束条件，将不满足业务需求的频谱效益值置为0，改写效益矩阵，得到各次用户可用的空闲频谱资源，从而消除掉部分约束条件。具体如下，式(4)表示所选频谱速率大于或等于次用户带宽需求，因此可将速率小于次用户要求的频谱资源效益值置为0；同理，根据价格、时延及分组丢失率约束条件，分别把不符合次用户要求的频谱资源带宽效益置为0，剩下的非0 部分即为满足次用户业务需求的可用频谱资源。

通过上述处理，消除了式(4)～式(8)共5 个约束条件，3.2 节中的优化模型可简化为

【解读】 跟所有其他检测项目一样，检测前的相关解释和咨询应该充分细化和个性化。高通量测序还可能涉及比其他项目更多的隐私信息，因此很有必要对每个参与检测个体进行充分的知情同意，胎儿的父母作为共同监护人原则上应当共同接受检测前教育。

以上的优化模型可表示为如式(16)所示的标准矩阵形式。

4.1.3 标准化处理

由以上分析可知，这是一个典型的0-1 规划中的指派问题，可用匈牙利算法进行求解。由于请求服务的次用户数量跟空闲频谱数量不一定相等（n≠m），即该分配问题可能为非平衡指派问题，因此使用匈牙利算法求解前需进行标准化预处理，具体如下。

1)当n=m时，不用处理。

2)当n＜m时，增加m-n个虚拟频谱资源，并令其效益值为0，使次用户优先考虑实际存在的空闲频谱。

3)当n＞m时，增加n-m个虚拟次用户，令虚拟次用户所在行的效益值为0，使实际存在的次用户优先考虑实际存在的空闲频谱。

同时，标准化还包括把效益最大化问题转化为最小化问题，首先找到效益矩阵中的所有元素的最大值rmax，然后用该最大值减去效益矩阵的每一个元素得到新的效益βjk=rmax-rjk。

4.1.4 改进匈牙利算法

通过约束条件化简及标准化处理，将数学模型转化为标准形式的0-1 规划问题，可用匈牙利算法进行求解。传统匈牙利算法一般包括变换系数矩阵、试指派、用最少直线覆盖所有0 元素、重新变换系数矩阵并再次试指派。通常情况下，传统匈牙利算法求解时需要循环执行多次系数矩阵变换并试指派，若能减少循环次数，则可提高匈牙利算法效率。因此，本文通过对传统匈牙利算法的关键步骤“变换系数矩阵”进行改进，以提高算法效率。该改进匈牙利算法具体步骤如下。

步骤1变换系数矩阵。与传统匈牙利算法随机地从行（或列）开始逐行（或列）减去该行（或列）的最小元素以得到0 元素不同，改进方法先统计各行最小元素总个数r及各列最小元素总个数c。当r≤c时，先从系数矩阵的每行中减去该行的最小元素，再从所得系数矩阵的每列中减去该列的最小元素；当r≥c时，先处理列数据再处理行数据。通过该方法可增加0 元素的数量，提高了试指派成功的概率，从而提高了算法的执行效率。

步骤2试指派。试指派包括2 个子步骤。1)独立0 指派。依次找到各行的独立0 元素，计算该元素所属主网络k，如果接入该行对应次用户后没有超过主网络干扰阈值，则把该元素分配给次用户，并标记该元素所在行列不能再指派0 元素，更新主网络干扰值；否则把主网络在该行对应的独立0 元素去掉。同理，依次搜索各列中的独立0 元素，并与行独立0 做同样的处理。循环搜索各行列中的独立0 元素，直到没有独立0 元素。2)非独立0 指派。搜索各行列中是否还有0 元素，如有，则从0 元素最少的行列开始（如果行、列中有相同数量的0 元素，则可随机选择序数最小的行或列），计算该0元素所属主网络k，依照1)进行干扰值处理，把符合要求且未被指派的0 元素指派给该行对应次用户，并进行指派标记处理。循环执行，直到没有搜索到0 元素。

计算已分配0 元素数量num，如果num 等于效益矩阵维数n，则该分配问题的解已找到，否则转至步骤3。

步骤3用最少直线覆盖所有0 元素，设直线数量为l，若l=n，表示解已找到，转至步骤2 重新指派；若l＜n，转至步骤4。

步骤4设未被步骤3 直线覆盖的元素中的最小值为β，对未划线的行减去β，划线的列加上β，转至步骤2 再次进行指派。

化简方法

输入

SU：请求业务接入的次用户集合

PN：主网络集合

csu：次用户愿意支付的频谱价格

rsu：次用户最低速率需求

dsu：次用户时延要求

lsu：次用户分组丢失率要求

csp：空闲频谱资源价格

bsp：空闲频谱资源带宽

dsp：空闲频谱资源时延

lsp：空闲频谱资源分组丢失率

Bpn：各主网络空闲频谱资源带宽

输出

OM：最优决策矩阵

R：次用户获得总传输速率

1)初始化。根据空闲频谱信息、信道条件、应用请求、过往分配决策结果等信息，生成对应的数据表并初始化决策矩阵。

2)效益矩阵构造。在新一轮频谱分配周期，根据空闲频谱信息及请求服务的次用户构造效益矩阵，矩阵中的效益值为次用户选择相应频谱获得的传输速率，传输速率取决于带宽、传输功率及噪声功率。

3)效益矩阵修正。①若空闲频谱在过往周期中已分配给次用户且满足次用户需求，则不参与新一轮分配，并删去效益矩阵中对应的空闲频谱；②根据次用户服务质量需求csu、rsu、dsu及lsu，把不符合次用户服务质量需求的效益值置为0。

4)约束条件化简。将效益矩阵修正过程中所依据的服务质量需求对应的约束条件删去。

5)标准化处理。首先，引入|n-m|个虚拟次用户或频谱资源，使n=m，以化解非平衡指派问题；然后，将传输速率最大化问题转化为最小化问题，即利用最大效益值rmax减去效益矩阵的每一个值。

6)问题求解。通过改进传统匈牙利算法的系数矩阵变换策略提高求解速度，并将次用户与空闲频谱资源的匹配关系存放于决策矩阵中。

7)返回最优决策矩阵OM 及总传输速率R。

4.2 改进遗传算法

本文对传统遗传算法进行改进，设计了基于改进遗传算法的频谱分配方法，包括适用于本文频谱分配问题的染色体编码方式及针对用户业务需求等约束条件的染色体修正程序。改进的遗传算法具体流程如图2 所示。

图2 改进的遗传算法流程

如图2 所示，改进的遗传算法首先设计了适用于本文复杂频谱分配问题的染色体编码方案，并初始化种群；其次，将用户获得的传输速率作为评价指标计算适应度值，并依据适应度值大小优选部分染色体进行后续的交叉及变异操作；再次，计算经过交叉、变异运算的个体是否满足3.2 节中数学模型的约束条件，若不满足则进行修正操作；最后，进行适应度评价并判断是否达到最大迭代次数，达到则输出优化解，否则再次进行遗传操作。下面重点介绍适用于本文频谱分配问题的染色体编码方案及修正操作，具体如下。

4.2.1 染色体编码

用户选择接入匹配的频谱资源以满足业务需求，所有用户的频谱选择结果构成了一个完整的频谱分配方案，基于此，本文构建了基于二进制编码的频谱分配方案（染色体编码）。例如，3 个主网络重叠覆盖，每个主网络有14 个空闲频谱，次网络中有m个用户，编码示意如图3 所示。

图3 染色体编码示意

图3 中，基因与次用户对应，m个基因对应m个次用户；基因值表示选择接入的频谱，3 个主网络用2 个二进制位n1n2表示，14 个空闲频谱用5 个二进制位s1…s5表示。因此，m个基因及其值表达了所有m个次用户的频谱分配方案。

4.2.2 修正操作

由于交叉及变异操作的随机性，会出现不满足约束条件的染色体，例如同一个频谱分配给多个次用户。对于不符合要求的染色体，通常将其从种群中剔除。为避免剔除过多的不符合约束条件染色体而影响寻优效果，本文对不满足如下任一条件的染色体启动修正程序，修复不符合条件基因。

1)频谱价格大于用户可支付价格。

2)频谱带宽小于用户的带宽需求。

3)时延大于用户的时延要求。

4)分组丢失率大于用户的分组丢失率要求。

5)同一频谱分配给多个用户。

若经过交叉、变异运算的染色体符合上述任一条件则调用修正程序进行修正，染色体判断及修正过程具体如下。

步骤1计算染色体中基因所对应的网络及频谱，提取该频谱相应的带宽、价格、时延等属性值。

步骤2判断步骤1 中频谱各属性是否满足其基因对应次用户的业务需求，频谱是否分配给多个次用户等条件，如不符合要求，则执行步骤3 修正该基因；若符合要求则返回步骤1 计算下一个基因，直到全部基因都符合要求并退出。

步骤3基因修正。根据网络及频谱的取值范围，将该基因的网络及频谱值随机调整到其他网络及频谱，并返回步骤2 再次检测该基因是否符合要求。

4.3 化简方法最优性证明

由第3 节的数学模型可知，本文的频谱分配是一个多约束条件的0-1 规划问题，通过构造效益矩阵，并根据用户业务需求等约束条件修正效益矩阵，令不符合约束条件的频谱资源不会分配给对应的用户，从而简化掉部分约束条件，最终把多约束条件的0-1 规划问题转化为典型的0-1规划中的指派问题。对于指派问题，匈牙利解法是一种行之有效的方法，匈牙利解法有以下2 个重要的定理。

定理1设一个任务分配问题的效益矩阵为{aij}，若{aij}中每一行元素分别减去一个常数ui，每一列元素分别减去一个常数Vj，得到一个新的效益矩阵{bij}（其中元素bij=aij-ui-Vj），则{bij}的最优解等价于{aij}的最优解。

定理2在新效益矩阵{bij}中，令对应于不同行、不同列的那组0 元素所对应的xij=1，其余xij=0，得到可行解x*=xij，则x*为效益矩阵{bij}的最优解。

由定理1 及定理2 可知，匈牙利解法通过变换效益矩阵，找到不同行、不同列0 元素对应的可行解，该可行解就是该效益矩阵的最优解。因此，本文通过化简数学模型，将频谱分配问题转化为典型的指派问题，并利用匈牙利解法求解，可得到其最优解。

5 仿真

5.1 实验参数及方法

假设场景中存在2 种类型的空闲频谱，一类是授权频谱，包括蜂窝网络及WiMax 网络频谱；另一类是非授权的ISM 频谱资源。不同频谱资源带宽、价格、时延及分组丢失率不同。例如，蜂窝网频谱资源时延要小于ISM 频谱资源的时延；次用户占用授权频谱需支付一定费用，但可以免费使用非授权的ISM 频段频谱资源。本文频谱资源属性及业务需求相关参数参考文献[17-20]，空闲频谱资源属性具体如表4 所示，其中频谱带宽、价格、时延及分组丢失率均处于一定范围内，实验中空闲频谱资源属性值在该范围内随机选取，并独立实验200 次取结果平均值作为最后的结果，以消除随机性、增加可信度。

表4 空闲频谱资源特征属性

假设存在3 种类型业务需求：语音、视频及文件传输。认知用户到达概率服从泊松分布，不同业务对传输速率、时延、分组丢失率等服务质量要求不同，对价格的接受程度也不同，具体如表5 所示。

为评估所提方法的性能，本文通过实验对所提化简方法及改进遗传算法与粒子群优化算法进行对比。假设改进遗传算法的种群规模为60，交叉概率为0.5，变异概率为0.01，最大迭代次数500；粒子群优化算法的粒子规模为60，学习因子C1、C2均为2，惯性权重为1。同时，为消除随机性，实验进行了200 次，取平均值作为实验结果。

表5 各业务类型服务质量要求

5.2 实验结果分析

本文主要从获得的传输速率、不同业务的频谱分配接入及算法的时间效率方面进行评估，同时考察进化算法（下文中，进化算法指改进遗传算法及粒子群优化算法）的收敛性，具体如下。

5.2.1 传输速率对比

次用户根据其服务质量需求，选择接入不同的频谱，具有不同的传输速率。图4 显示了次用户总传输速率与用户数的变化关系，其中，2 种进化算法取迭代100 次时的结果。如图4 所示，3 种算法获得的总传输速率均随着次用户数量增加而增加，本文所提化简方法在各个用户数量下的传输速率都最高，改进遗传算法次之，粒子群优化算法最低。这说明化简方法在满足用户服务质量需求的同时，能有效地提高全网的传输速率，因为化简方法将不满足用户需求的频谱效益置为0，避免接入该频谱，并在试指派时将高传输速率的频谱分配给次用户。

图4 所有用户获得的传输速率

为了进一步观察2 种进化算法的收敛性，图5给出不同迭代次数下的传输速率,假设申请服务用户终端数为50。如图5 所示，在迭代次数小于50时，2 种算法获得的总传输速率增长迅速，特别是改进遗传算法；在迭代数大于50 时，总传输速率增长速度下降很快，改进遗传算法在迭代次数达到200 次时已趋于收敛，说明了改进遗传算法比粒子群优化方法具有更高的进化效率。

图5 不同迭代数的传输速率对比

5.2.2 频谱接入分析

图6给出了采用化简方法的不同业务类型在各个分配周期的频谱选择接入情况。如图6 所示，语音业务在各个不同的分配周期均选择接入蜂窝网络的空闲频谱，因为该频段频谱资源能更好地满足语音业务的低时延及低分组丢失率需求。视频业务优先接入到WiMax 网络的频谱资源，因为在满足业务的价格、时延及分组丢失率要求的情况下，WiMax 频谱资源具有更高的传输速率。文件传输服务对时延及分组丢失率要求较低，愿意支付的价格也较低，其主要接入Wi-Fi网络频谱。从图6 中可看出，当接入频谱资源不能满足用户业务需求时，化简方法能够在新一轮分配决策周期将其切换到满足需求的频谱资源。

图6 不同分配周期的频谱选择接入

为更深层次分析不同算法传输速率差异的原因，下面进一步观察分析接入不同频谱的概率。本实验中，改进遗传算法及粒子群优化算法取迭代100 次的结果，并取用户数为50 时各个用户接入不同网络频谱段的平均概率。如图7～图9 所示，对于申请语音业务的用户，3 种方案均将用户分配到蜂窝网络1 和蜂窝网络2 通信频段的空闲频谱上，这是因为语音业务的带宽要求低而时延及分组丢失率等要求高，蜂窝网络频段能更好地满足用户的服务需求，同时由于语音业务可接受支付代价较小，所以申请语音业务次用户更多地选择接入价格较低的蜂窝网络2 空闲频谱；对于申请视频业务的用户，其对带宽、时延、分组丢失率均有一定的要求，也愿意支付较高的价格，从图7 可看出，采用化简方法的用户主要接入WiMax 网络的频谱；而图8 采用改进遗传算法及图9 采用粒子群优化算法的用户则同时选择接入WiMax 及Wi-Fi 网络的频谱；对于申请文件传输业务的用户，其带宽要求较大，但对时延及分组丢失率要求低，愿支付的代价也低，因此，申请文件传输业务的用户都选择接入免费的Wi-Fi 网络频谱。

图7 基于化简方法的不同业务的网络频谱选择概率

图8 基于改进遗传算法的不同业务的网络频谱选择概率

图9 基于粒子群优化算法的不同业务的网络频谱选择概率

由以上分析可知，2 种方法申请语音及文件传输服务的用户选择接入的频谱资源大致相同；主要区别在于申请视频业务的用户，化简方法选择接入到能提供更高速率的WiMax 频谱，2 种进化算法则同时分布在WiMax 及Wi-Fi 网络的频谱，因此，化简方法获得了更大的用户传输速率。

本文同时统计了3 种方法选择接入各个网络频谱的概率，如图10 所示。从图10 中可知，蜂窝网络1 与蜂窝网络2 频谱资源的选择概率上几种方法相差不大；在ISM 频段的Wi-Fi 网络频谱资源选择上，2 种进化算法的选择概率略高于化简方法，而在提供更高速率的WiMax 网络上，化简方法接入的概率更大，这与图6～图9 中各类型业务选择接入频谱资源的结果相符，即3 种方法的语音业务都接入到蜂窝网络频谱，化简方法的视频业务及文件传输业务分别接入到速率更高的WiMax 网络及Wi-Fi 网络频谱，而2 种进化算法的视频业务则同时接入到WiMax 网络及Wi-Fi 网络频谱资源。这也进一步说明了图4 中化简算法获得更大传输速率的原因。

图10 不同策略选择接入不同网络的概率

5.2.3 执行效率比较

图11 给出了3 种方法的执行效率对比情况，其中，改进遗传算法及粒子群优化算法给出不同迭代数下的执行时间，化简方法跟迭代数无关，不随迭代次数变化。如图11 所示，化简方法的运行时间略小于40 ms，大约为2 种进化算法迭代数为30 时的运行时间，具有较高的执行效率，因其主要进行较简单的0 元素搜索运算；同时，粒子群优化算法的运行时间稍小于改进遗传算法，且两者的运行时间均随迭代次数的增加而线性增加，这是因为两者都需一代代地进化来得到更优的个体，但粒子群优化算法不需要进行遗传算法的交叉、变异运算，故其执行效率稍高于改进遗传算法。

图11 执行效率对比

从上述3 个实验可知，化简方法获得了最高的传输速率，且具有较高的执行效率；进化算法在达到一定迭代数时，可获得接近于化简方法的传输速率，但需较长的运行时间。

6 结束语

激增的流量需求与紧缺且利用率低的频谱资源是一个矛盾，如何在认知异构无线网络场景下实现频谱资源高效分配以满足用户流量需求是一个重大挑战。本文综合考虑信道条件、空闲频谱资源属性及用户服务需求，提出了基于用户业务需求的传输速率最大化频谱资源分配策略。该策略首先以用户获得的总传输速率最大化为目标，建立了频谱资源分配的优化模型。然后设计了一种多项式时间复杂度的求解化简方法，该方法在每一轮频谱分配决策周期，首先根据用户业务需求及过往周期分配结果修正效益矩阵实现约束条件化简，从而将优化模型转化为标准形式的0-1 规划模型，并通过改进传统匈牙利算法的关键步骤“系数矩阵变换”以提高算法效率，有效快速地求解出频谱分配方案。同时，设计了一种基于改进遗传算法的求解方法，以比较2 种不同技术路径的求解思路。最后，通过实验对本文所提方法与粒子群优化算法进行对比分析，从实验结果可知化简方法在获得高传输速率的同时具有较大效率优势。

本文主要针对语音、视频及文件传输等非实时业务，利用集中式网络架构进行频谱资源分配。然而，集中式网络架构信息交互和处理所带来的交互时延和开销会增加用户接入时延，对于存在大规模用户终端的场景或实时业务具有局限性。因此，设计高效的用户与基站的信息交互机制、研究分布式的频谱分配方法或集中式、分布式相结合的混合结构以提高分配效率是未来需要重点研究的问题。