一种基于改进颜色敏感图论着色的频谱分配算法*

何建强 滕志军 刘 皎

（1.商洛学院电子信息与电气工程学院 商洛 726000）（2.东北电力大学信息工程学院 吉林 132012）

1 引言

在移动通信系统某些固定频段中，授权频谱大多处于空闲状态，而一些频段的频谱却又非常拥挤［1］。枯竭的频谱资源与较低的利用率之间的矛盾日益突显，固定的频谱分配方式是导致频谱利用率低下的主要原因［2］。认知无线电技术被认为是解决频谱资源利用率低下的最有效方法，它能够根据认知用户需求，提高网络吞吐量。

在认知无线电网络中，实现频谱资源的合理有效分配是重点和难点性问题［3］。博弈论与图论是目前比较常用的频谱分配算法，博弈论能够较好地解决频谱分配中的冲突问题，图论主要是对系统总体效益实现最优分配［4］。本文主要在颜色敏感图论着色（color sensitive graph coloring，CSGC）算法的基础上，在频谱分配过程中，对认知用户的分配效益和公平性进行考虑，在保证系统总效益的前提下兼顾用户分配的公平性。

2 系统模型

假设认知无线电系统中有N个等待分配频谱的认知用户，每个认知用户的标号n∈[0，N-1]；另有M个可用的信道，则信道的标号m∈[0，M-1]。假设在一个分配周期里不存在干扰，系统中的变化远远小于外部环境的变化，各矩阵参数是保持不变的，各矩阵的定义如下［5］：

1）空闲频谱矩阵L

在认知无线通信系统中，由于同时存在着授权用户和认知用户，当授权用户使用某一频段频谱时，认知用户则不能使用，即为频谱占用，反之为空闲频谱。其中，N是认知用户数，M为总的频带数。ln，m=1表示用户n可以使用频带m，反之，ln，m=0表示用户n不可以使用频带m。

当 Cn，k，m=1时，表示认知用户 n和 k在同时使用频带 m 时会产生干扰。当 n=k时，Cn，n，m=1-ln，m，只由空闲频谱矩阵L决定。

3 本文算法模型

用最大化总带宽（Max-Sum-Bandwidth，MSB）［6］为频谱分配的最优化目标函数，其数学表达式为

它的含义为最大化频谱的效益，其中∧N，M表示所有满足条件的无干扰的频谱分配矩阵A的集合。

本文采用协作式和非协作式两种方式，相应的标号准则［7］如下：

1）协作式最大化总带宽（Collaborative-Max-Sum-Bandwidth，CMSB）准则，相应的节点标号和颜色表达式为其中，Dn，m表示认知用户n分配到频谱m，与该用户不能同时使用频谱m的有干扰冲突的用户数。定义为。认知用户使用频谱m后，对整个系统产生的效益为。

采用协作式最大化总带宽的标签准则，不仅提高频谱利用率，而且考虑到频谱分配过程中用户之间的干扰关系，使频谱利用率最大化，系统性能达到全局最优。

2）非协作式最大化总带宽（Non-Collaborative-Max-Sum-Bandwidth，NMSB）准则［8］，相应的节点标号和颜色表达式为

非协作式最大化总带宽的标签准则，没有考虑用户之间的干扰，用户与用户是非合作的关系，每个用户都是自私的，都只考虑自己的效益而忽略对整个系统产生的影响。

3）最 大 系 统 公 平（Max-Proportional-Fair，MPF）准则［9］：通过度量不同频谱单元分配结果的公平性，进行频谱分配，其数学表达式如下：

最大系统公平（Collaborative-Max-Proportional-Fair，CMPF）准则，相应的节点标号和颜色表达式［10］为

4 改进的频谱分配算法

本文继承了颜色敏感图论着色的思想，提出一种改进的频谱分配算法，系统效益与用户公平性兼顾。所提算法首先采用最大化总带宽作为颜色敏感图论着色频谱分配的目标函数，同时考虑认知用户间分配的公平性，采用最大系统公平准则对频谱二次分配，从而避免了算法只通过追求系统总效益导致分配公平性较弱的问题。兼顾系统公平性对频谱进行分配，更好改善认知用户间的公平性，提高频谱利用率，优化系统性能。

在初次对频谱进行分配时，以最大化总带宽为目标函数，若部分用户的通信要求未被满足，则根据最大系统公平准则对频谱再次分配。

算法流程如下：

步骤1初始化；

步骤2选择最大化总带宽准则，计算具有最大效益的用户；

步骤3根据准则分配频谱；

步骤4更新拓扑，在可用频谱列表中删除与获得频谱用户有冲突的用户，同时删除这些节点以该颜色相连的边。将已满足需求的用户暂时退出分配；

步骤5判断图是否为空，若图为空，结束分配；若图不为空，则执行步骤6；

步骤6根据最大系统公平准则分配频谱；

步骤7判断图是否为空，若图为空，结束分配；若图不为空，返回步骤4；

步骤8本周期分配结束。

5 本文算法的仿真验证

下面通过Matlab进行仿真验证，对本文算法和改进前的CSGC与最大系统公平算法进行比较。

设置信道数从5～30，进行10 000次仿真实验，从图1和图2中可以看出，改进算法、CSGC算法和最大系统公平算法都会随着信道数增加，系统效益增大，最大系统公平算法系统总效益最低，本文算法系统总效益明显高于其他算法，使系统得到优化。图1为协作式下系统效益，图2为非协作式下系统效益，从图中可以看出，协作式下系统性能要优于非协作式。

图1 在CMSB下系统总效益随信道数变化

设置信道数为10，认知用户数从5～20，进行10000仿真实验，从图3和图4中可以得知，改进算法、CSGC算法和最大系统公平算法都随着认知用户数的增多，系统效益呈下降趋势，本文算法下降幅度最小，与传统算法相比较，系统效益更好，分配结果更理想。图3为协作式下系统效益，图4为非协作式下系统效益，从图中可以看出，协作式下频谱利用率要高于非协作式。

图2 在NMSB下系统总效益随信道数变化

图3 在CMSB下系统总效益随认知用户数变化

图4 在NMSB下系统总效益随认知用户数变化

6 结语

本文所提算法，结合了最大化总带宽与最大系统公平两种准则，提出一种改进的频谱分配算法，仿真验证得出，改进的算法比单一算法更能提高频谱使用效率，大大提高系统效益。