基于用户需求的改进型CSGC频谱分配算法

胡虹梅，覃玉荣

（广西大学计算机与电子信息学院，广西南宁530004）

0 引言

图论着色模型是研究认知无线电频谱分配的一个重要模型，它将认知用户和授权用户所组成的网络拓扑结构抽象成图，把频谱分配问题等效为图论着色问题。文献1基于图论模型提出了列表着色频谱分配算法，其目标是最大化频谱利用率。文献2充分考虑频谱效益的差异性和干扰性，提出了CSGC算法。还有学者提出了并行频谱分配算法，极大地减少了频谱分配的时间开销，能够更好地适应认知无线电环境快速时变的要求[3]。

以上算法主要从认知用户所获得的带宽效益进行频谱分配，但缺乏考虑认知用户本身的带宽需求因素，很可能造成带宽需求大但信道质量差的用户得不到满足，带宽需求小但信道质量好的用户却占用着大量的频谱资源，从而带来频谱资源二次浪费的不公平现象。为此，文献[4]和文献[5]基于CSGC算法分别采取了结合需求的暂时退出机制和排队方式来最小化系统未满足的带宽需求，但前者需要二次构造网络拓扑图，带来了时间开销;后者引入未知参数变量，使计算困难。2种算法均未能较好解决用户需求这一重要问题。

在上述研究基础上，主要研究了能较好解决用户需求的改进型CSGC频谱分配算法。该算法的特点是当某用户达到带宽需求后，立即用各频段收益最小非零值的一半来代替其剩余频段的带宽收益，使该用户在下一轮分配中优先级最低。通过牺牲少量系统带宽总收益来达到大幅提升满足用户需求的性能，提高系统分配公平性和频谱利用率的目的。同时算法中无新的时间开销和参数变量，易简单实现。

1 频谱分配图论模型建模

在认知无线电频谱分配的图论着色模型研究中，将认知用户组成的网络拓扑结构抽象成图，图中的每个顶点代表一个认知无线电用户，每一个顶点与一个列表相关联，这个列表代表顶点所在区域位置可以使用的频谱资源集合，如果图中的某2个顶点以某颜色边相连，则这2个顶点不能同时使用该颜色所代表的频谱。该文建立的图论着色模型，将认知用户的频谱分配问题抽象成图G=（V，E，S）对顶点的着色问题，其中:V是图G的顶点集合，代表认知用户;E是图G的边集，由干扰矩阵决定;S表示各个顶点处的可选颜色列表，即各认知用户的可用频谱。该模型具体使用可用矩阵、效益矩阵、干扰矩阵、干扰限制矩阵、带宽需求向量和分配矩阵进行描述，相关假设与定义如下:

①假设某一时刻网络中有N个认知用户需要通信，授权频段有M个空闲频谱。假设在一个分配周期内，认知用户的网络拓扑保持不变;

③效益矩阵B={bn，m}N×M，bn，m表示用户n

使用频带m能够带来的频谱效益;

2 改进型CSGC算法

2.1 算法分配目标

原有的CSGC算法以一个最优化的效益函数为目标，按照某个分配准则对顶点进行标号，选择具有最大标号值的顶点并为其分配频段。在最大化系统带宽收益效益函数下，分配准则分别为协作式最大化带宽总和（CMSB）和非协作式最大化带宽总和（NMSB）。其中，ΛN，M表示所有满足条件的无干扰分配矩阵A的集合。

原算法从用户所获得的带宽收益角度分配频谱，未考虑认知用户的带宽需求，这很可能导致带宽需求小的用户分配到大量频谱，而带宽需求大的用户却得不到满足，从而带来频谱资源的二次浪费。针对此问题，结合用户自身的带宽需求因素，提出了改进型CSGC频谱分配算法。

考虑用户在一个分配周期内的带宽需求。假设demn为用户n在一个分配周期内的带宽需求，USn为经过分配后用户n未满足的带宽需求，则其中，函数（x）+=max（0，x）。基于用户需求的CSGC改进算法的分配目标是最小化一个分配周期内系统中所有认知用户的未满足带宽需求总量，即

2.2 算法原理

为最小化系统未满足的带宽需求，在分配过程中应尽量减少未满足需求用户的数量，即某个用户的需求一旦得到满足，立即降低其分配的优先级以优先考虑尚未满足需求的用户。文献[5]采用“满足条件的某一值”将已满足带宽需求的用户置于队尾，但是“满足条件的某一值”是一个模糊的概念，难于计算。该文的做法简单明确:在某次分配循环过程中，假设用户n已满足自身的带宽需求。进行拓扑更新后，找出用户n剩余的所有可用频段，分别计算这些可用频段下各认知用户的带宽收益，取出各频段下带宽收益的最小非零值，将其倍减后作为用户n在该频段下新的带宽收益。这样就能够使得在同一可用频段下用户n的效益比其他用户的都小，即优先级最低。该文提出的算法不需要二次构图，也没有引入新参数变量，用户分配优先级的计算简单易行，在CSGC算法的基础上增加考虑用户自身的带宽需求，使得频谱分配与自身需求相匹配，提高了分配的公平性和频谱利用率。

2.3 算法分配流程

定义带宽收益矩阵R={r（n，m）}N×M。r（n，m）表示在某个目标准则下某循环阶段用户n使用频带m的带宽收益，在NMSB分配准则下r（n，m）=bn，m，在CMSB准则下，r（n，m）=bn，m/（Dn，m+1）。基于用户需求的CSGC频谱分配算法是在原有CSGC算法上做出了一定改进的算法，因此其算法流程与CSGC算法较为接近，不同的地方在于改进算法增加考虑了用户的带宽需求满足情况。

基于用户需求的改进型CSGC频谱分配算法流程如图1所示。算法每一轮分配循环只分配一个频谱给相应的用户，反复地循环分配，直至将所有可用频谱分配完毕。

图1 算法流程图

3 数值仿真与结果分析

为比较2种算法的性能，对CMSB和NMSB准则下的CSGC频谱分配算法和基于用户需求的改进型CSGC算法进行MATLAB仿真。仿真参数如表1所示，频带效益和带宽需求如表2和表3所示，其参数参照文献[4]。

表1 仿真参数

表2 频带效益等级

表3 带宽需求

未满足需求的带宽总量如图2所示，图中的横轴表示一个分配周期内所有认知用户的未满足需求总量，纵轴为经过多次实验后所获得的统计概率累积分布函数。基于用户需求的CSGC改进算法，就总体趋势而言其未满足需求总量均小于CSGC算法，在协作和非协作模式下其满足用户需求的性能比CSGC算法分别能够提高约30%和26%。此外，CSGC算法满足带宽需求的概率为4%，基于用户需求的算法满足带宽需求的概率为14%～20%，增加了约10%～16%。

图2 未满足需求的总量比较图

系统带宽总收益和分配时间开销分别如图3和图4所示。从图中可以看到，就总体趋势而言，基于用户需求的改进算法的总带宽收益在协作与非协作模式下均略小于原CSGC算法，其分配的时间开销与CSGC算法大致相当。图4中T为一次分配循环周期。

以上仿真结果表明:基于用户需求的CSGC算法有效地兼顾了频谱利用率和分配的时间开销，通过牺牲少量的系统带宽总收益，其满足用户需求的性能比CSGC算法大约提升26%～30%，提高了分配的公平性。

图3 系统带宽总收益比较图

图4 分配的时间开销

4 结束语

基于图论着色模型，研究了基于用户带宽需求的CSGC改进算法。该算法通过降低已满足需求用户的分配优先级来减少未满足需求用户的数量，较好地实现了频谱分配与自身需求相匹配。仿真结果表明，所提算法满足需求的性能比CSGC算法大约提高26%～30%，更好地满足了用户的带宽需求。

[1]WANG WEI，LIU XIN.List-Coloring Based Channel Allocation for Open-Spectrum Wireless Networks[C]//the 62nd IEEE Vehicular Technology Conference.May 2005:690-694.

[2]ZHENG Hai-tao，PENG Chun-yi.Collaboration and Fairness in Opportunistic Spectrum Access[C]//IEEE International Conferencen Communication.May 2005:3132-3136.

[4]廖楚林.认知无线电系统的频谱分配算法研究[D].成都:电子科技大学硕士学位论文，2007.

[5]莫文承.认知无线电的频谱分配算法研究[D].成都:电子科技大学硕士学位论文，2008.