一种改进的CSGC频谱分配算法

滕志军，李 可

（东北电力大学信息工程学院，132012吉林吉林）

一种改进的CSGC频谱分配算法

滕志军，李 可

（东北电力大学信息工程学院，132012吉林吉林）

基于图论着色的频谱分配算法未充分考虑用户实际带宽需求，针对这一问题，本文在原算法基础上提出了一种改进的CSGC频谱分配算法.该算法引入了空闲频谱和用户请求两个时间因子，通过设置用户优先级函数，在进行二次频谱分配时最大限度地满足用户需求.仿真结果表明，该算法不仅保留了原CSGC算法的性能，而且大幅度提高了频谱利用率.

图论；频谱；分配；CSGC；用户优先级

随着无线通信技术的快速发展，无线用户日益增加，使得频谱资源变得越来越紧缺.由于频谱资源是一种不可再生资源，因此如何更好的利用现有频谱资源已经成为人们亟待需要解决的问题［1］.认知无线电概念的提出，有效的解决了频谱资源紧缺的问题，提高了频谱利用率.

目前，频谱分配的经典算法有博弈论、图论和竞价拍卖.由于图论着色算法有较好的灵活性和更高的实用性，因此，受到更多研究者的关注.文献［2］提出了列表着色（list⁃coloring，LC）算法的频谱分配模型，LC算法采用开放式频谱接入的方式，在现有的干扰约束条件下，其目标是追求最大的频谱分配数量.文献［3］提出了颜色敏感图论着色（color sensitive graph coloring，CSGC）算法的频谱分配模型，CSGC算法考虑了频谱分配中频谱效益的差异性和干扰性，明显地减少了干扰，提高了网络吞吐量，使系统带宽得到最大利用.文献［4］提出了并行算法，将图分解成多个子图，通过同时对多个子图着色方法来缩短频谱分配周期，使其能够更好适应外部无线通信环境的快速变化.

上述分配算法主要是对频谱分配数量最大化研究，但缺乏对用户实际带宽需求的考虑，容易导致带宽需求大的用户分配到较小的频谱，而带宽需求小的用户分配到较大的频谱，不能更好的满足用户需求，从而造成频谱资源的严重浪费.因此，本文在图论的基础上，提出一种基于用户优先级的频谱分配算法，在对频谱进行二次分配时，通过设置认知用户的优先级函数，最大限度满足用户需求，从资源分配和用户需求双重角度出发，提高频谱分配的公平性和频谱利用率，优化系统性能.

1 传统CSGC算法概述

1.1 CSGC算法模型的数学描述

颜色敏感图论着色算法中包含空闲频谱矩阵、效益矩阵、干扰矩阵和无干扰的频谱分配矩阵，本文在此基础上，加入了频谱空闲时间矩阵和用户需求时间矩阵.

假设认知无线电系统中有N个等待分配频谱的认知用户，则认知用户的标号n∈［0，N-1］，有M个可用的空闲频谱，则空间频谱的标号m∈［0，M-1］．相对于外界通信环境变化时间而言，频谱分配时间很短暂，则假设各矩阵在一个分配周期内是保持不变的，各矩阵的定义如下［5］：

1）空闲频谱矩阵L

在认知无线通信系统中，同时存在着授权用户和认知用户，当授权用户使用某一频段频谱时，认知用户则不能使用，用空闲频谱表示某个时间没有授权用户使用该频段的频谱．L＝｛ln，m｜ln，m∈｛0，1｝｝N×M，N为认知用户数，M为总频带数．ln，m＝1为用户n可以使用频带m，反之，ln，m＝0为用户n不可以使用频带m．

2）效益矩阵B

B＝｛bn，m｝N×M，bn，m为认知用户n使用可用频谱m所获得的效益．

3）干扰矩阵C

C＝｛Cn，k，m｝，Cn，k，m∈｛0，1｝N×N×M，为认知用户n和k同时在信道m上产生的干扰．

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

4）无干扰的频谱分配矩阵A

A＝｛an，m｜an，m∈｛0，1｝｝N×M，an，m＝1为将频带m分配给认知用户n使用．A必须满足无干扰条件：an，m·ak，m＝0，if Cn，k，m＝1；∀n，k＜N，m＜M．

5）频谱空闲时间矩阵W

W＝｛wm｝1×M为授权频谱m的空闲时间．本文假设在一个分配周期内，每个授权频谱m的空闲时间不发生变化．

6）认知用户请求时间T

T＝｛tn｝N×1为认知用户n的请求时间．本文假设在一个分配周期内，每个认知用户n的请求时间不发生变化．

1.2 CSGC算法准则

采用最大化带宽总和（max⁃sum⁃bandwidth，MSB）［6］为频谱分配的最优化目标函数，其数学表达式为

式（1）为最大化频谱的效益，其中A∈∧N，M为所有满足条件的无干扰的频谱分配矩阵A的集合．

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

1）协作式最大带宽总和（collaborative⁃max⁃sum⁃bandwidth，CMSB）准则［7］，相应的节点标号和颜色表达式为

式中，Dn，m表示认知用户n分配到频谱m，与该用户不能同时使用频谱m的有干扰冲突的用户数．定义为认知用户使用频谱m后，对整个系统产生的效益为bn，m／（Dn，m＋1）．

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

2）非协作式最大带宽总和（non⁃collaborative⁃max⁃sum⁃bandwidth，NMSB）准则［8］，相应的节点标号和颜色表达式为

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

2 基于用户优先级的改进型CSGC频谱分配算法

在频谱分配过程中，干扰关系决定着认知用户所获得的效益［9］，为避免干扰和冲突，提出了颜色敏感图论的频谱分配算法，减少了干扰［10］，但是却没有考虑用户需求.本文继承了颜色敏感图论着色的思想，并考虑到用户的需求，提出一种改进的CSGC频谱分配算法.该算法的基本思想首先采用最大化带宽总和作为颜色敏感图论着色频谱分配的最优目标函数，同时考虑认知用户的频谱需求，提出用户满意度，根据认知用户对当前频谱分配的满意程度设置用户优先级函数，通过认知用户对频谱需求的优先程度进行频谱的再次分配.

2.1 定义

定义1 用户满意度sn

认知用户满意程度与用户的需求紧密相连，影响系统的稳定性，决定这个系统是否是最优.本文提出用户满意度的概念，用来衡量认知用户需求是否得到满足.根据用户满意度设置用户优先级，对频谱进行再次分配时可以满足更多用户需求，从而提高频谱利用率.

用户满意度为认知用户对当前频谱分配的满意程度［11］.用户满意度定义为频谱空闲时间与认知用户请求时间之比，即

sn＝wn／tn．（6）

从式（6）可以看出，当sn≥1时，用户需求得到满足，空闲频谱时间与认知用户请求时间之比越大，用户的满意度就越高；当0≤sn＜1时，用户的需求未能得到满足，空闲频谱时间与认知用户请求时间之比越小，用户的满意度就越低．

定义2 用户的优先级pn

目前研究中，大多没有考虑到用户的需求，容易导致系统的频谱分配达不到最优．本文根据用户满意度设置用户优先级，使频谱在再次分配的过程中，按照用户的优先级进行分配，即

当用户的需求被满足时，用户满意度就大，相应的频谱分配优先级就降低，反之，用户满意度小，频谱分配的优先级就升高.

2.2 改进的CSGC算法描述

本文算法分为两个阶段，第一阶段，以最大化带宽总和为目标进行初次频谱分配，若部分用户的需求仍不能被满足，则根据用户的优先级进行第二阶段频谱分配.

改进的CSGC算法，在频谱分配的第一阶段，通过标签规则标记每个节点的标号值（label），每一个标号对应一个频段.每次分配时，将选取具有最大标号值的节点，把相应的频谱分配给该节点.更新拓扑，在可用频谱列表中删除与获得频谱用户有冲突的用户，同时删除这些节点以该颜色相连的边.进行拓扑更新时，每个节点的邻居节点也将发生变化，所以节点干扰限制情况一直是变化的，相关节点的标号值和干扰限制矩阵也随之进行更新，若空闲频谱列表不为空，则进行第二阶段的频谱分配，根据第一阶段用户对当前频谱分配的满意程度，得到用户优先级，按优先级由高到低的顺序进行频谱的再次分配.首先对具有最高优先级用户进行分配，用户要求一旦被满足，立即降低其优先级.若有多个认知用户拥有相同的优先级，则将频谱分配给干扰节点数最少的认知用户.若图为空，本周期分配结束.执行过程如下步骤：1）进行初始化设置，设置参数和仿真模型；2）选择初始分配准则，即最大化带宽总和准则，利用式（1）搜索具有最大效益的用户；3）根据准则进行频谱分配；4）更新拓扑，在可用频谱列表中删除与获得频谱用户有冲突的用户，同时删除这些节点以该颜色相连的边.将已满足需求的用户暂时退出分配；5）判断图是否为空，若图为空，则执行步骤9；若图不为空，则执行步骤6；6）根据用户的满意度，即式（6），设置用户分配频谱的优先级；7）根据用户优先级进行频谱分配，搜索具有最高优先级的用户进行分配，若优先级相同，选取干扰节点数最少的认知用户进行分配；8）判断图是否为空，若图为空，则执行步骤9；若图不为空，则返回步骤4；9）本周期分配结束.

3 算法仿真与分析

本文采用matlab仿真软件，对改进后的CSGC算法和传统算法进行仿真，采用协作式下最大带宽准则和非协作式下最大带宽准则，对算法的分配目标进行分析比较.设置参数如表1所示.

根据算法的执行过程和仿真参数设置，当用户数固定，信道数从5到30依次取值，进行20 000次仿真实验，比较CMSB、NMSB准则下改进的CSGC算法和传统算法的性能.仿真结果如图1～2所示.

表1 仿真参数设置

图1、2为协作与非协作方式下系统总效益与频谱数量的变化曲线.由图可知，在用户数固定的情况下，随着频谱数量的增加，系统效益都成上升趋势.而且随着频谱数量的增加，新算法下系统总效益的增加幅度明显变大.在协作式和非协作式准则下新算法的系统性能与传统CSGC算法相比，提高了约31%和25%.

根据算法的执行过程和仿真参数设置，当信道数固定，用户数从5到20依次取值，进行20 000次仿真实验，比较CMSB、NMSB准则下改进的CSGC算法和传统算法的性能.仿真结果如图3～4所示.

图1 用户数不变协作式最大化带宽准则下系统总效益

图2 用户数不变非协作式最大化带宽准则下系统总效益

图3 信道数不变协作式最大化带宽准则下系统总效益

图4 信道数不变非协作式最大化带宽准则下系统总效

图3 、4为两种协作方式下认知用户数量与系统总效益的变化曲线.由图可知，在信道数一定的条件下，随着认知用户数量增多，用户需求增加，系统总效益呈现出下降的趋势.但新算法下的系统总效益要明显高于传统算法.换言之，在相同带宽条件下，改进后的算法可以支持更多的认知用户接入.协作式与非协作式条件下，新算法均表现出较高的性能.

4 结 语

本文在深入研究经典图论模型的基础上，从认知用户需求的角度出发，提出了一种改进的CSGC频谱分配算法，该算法通过考虑用户的需求，据此快速进行二次频谱分配.由仿真结果分析可知，与传统CGSC算法相比，改进算法能够更好地满足各认知用户当前的需求，极大的提高了频谱分配的系统效益.

［1］THAKKER P，SARKANI S，MAZUCHI T.A system dynamics approach to demand and allocation of wireless spectrum formobilecommunication［J］.Procedia Computer Science，2012，8：118-123.

［2］BARNES S D，MAHARAJ B T.Prediction based channel allocation performance for cognitive radio［J］.AEU⁃International Journal of Electronics and Communication，In Press，Uncorrected Proof，2013，4.

［3］LUNDBORG M，REICHL W.RUHLE E O.Spectrum allocation anditsrelevanceforcompetition［J］. Telecommunications Policy，2012，36（8）.

［4］廖楚林，陈劼，唐友喜.认知无线电中的并行频谱分配算法.［J］电子与信息学报，2007，29（7）：1608-1611.

［5］谢玉鹏，谭学治，马琳，等.两种标准联合的认知无线电频谱分配算法［J］.哈尔滨工业大学学报，2013，45（5）：30-34.

［6］贾杰，王闯，张朝阳，等.认知无线电网络中基于图论着色的动态频谱分配［J］.东北大学学报，2012，33（3）：336-339.

［7］胡庆，常迪，海力群.认知无线电中基于频谱聚合的需求改进型频谱分配算法［J］.重庆邮电大学学报（自然科学版），2014，36（1）：8-12.

［8］朱冰莲，裴光术，张磊，等.认知无线电网络中系统效益最大化的频谱分配［J］.计算机工程，2012，38（3）：107-109.

［9］何利，郑湘渝，刘振坤.基于图着色理论的最大效用频谱分配算［J］.计算机工程，2011，19（10）：93-95.

［10］李一兵，杨蕊，高振国.基于着色理论的认知无线电频谱分配算法［J］.系统工程与电子技术，2010，32（6）：1109-1112.

［11］张玉兵，薛伟，林法杰.基于用户间公平性的改进型频谱分配算法［J］.计算机与数字工程，2013，41（7）：1062-1064.

（编辑 苗秀芝）

A CSGC improved algorithm of spectrum allocation

TENG Zhijun，LI Ke

（Dept.of Information Engineering，Northeast Dianli University，132012 Jilin，Jilin，China）

To solve the problem that the spectrum allocation algorithm based on graph theory coloring algorithm has not fully considered the actual bandwidth needs of users，this paper proposes a spectrum allocation based on user priority algorithm improved CSGC and the original algorithm.The algorithm introduces two time factors that are respectively called idle spectrum and user demand，by setting the user priority，the function can meet the needs of users during the second spectrum allocation.Simulation results show that the algorithm not only retains the performance of the original algorithm CSGC，but also greatly improves the spectrum utilization.

graph；spectrum；allocation；CSGC；user′s priority

TN923

：A

：0367-6234（2014）11-0119-04

2014-01-02.

国家自然科学基金（51077010）.

滕志军（1973—），男，博士，教授.

李 可，likelike1227＠126.com.