最大效益准则下基于分配公平性的CSGC改进算法

徐 嵩，李玉峰

（沈阳航空航天大学 电子信息工程学院，辽宁 沈阳110136）

最大效益准则下基于分配公平性的CSGC改进算法

徐 嵩，李玉峰

（沈阳航空航天大学 电子信息工程学院，辽宁 沈阳110136）

针对传统基于图论着色原理的频谱分配算法公平性较差问题进行研究，提出一种在最大效益准则下基于分配公平性改进的CSGC频谱分配算法。该算法在最大化系统效益准则下，充分考虑了用户对频谱资源占用因素，改进了原有CSGC算法。尤其是在频谱资源紧张情况下，保证了分配的公平性，保障了弱势用户的需求。MATLAB仿真实验结果表明，该算法在保障系统效益牺牲不大的前提下，提高了频谱资源分配公平性。

认知无线电；图着色；频谱分配；CSGC；分配公平性

随着当前无线通信技术的高速发展，人们对于无线频谱资源的需求越来越大，频谱资源紧缺问题日益严重。而由于无线频谱资源的不可再生性，人们将研究的重点放在了如何更加合理的利用现有频谱资源上。在此背景下，认知无线电技术[1-2]应运而生。认知无线电通过频谱感知技术，感知空闲频谱特性并分析空闲频谱特性及认知用户特征，将无线频谱资源合理分配给认知用户，以此方法来提高频谱的利用率。

目前的频谱分配方法多种多样，有博弈论、图着色、遗传算法和比例公平分配算法等[3-5]。在这些算法当中，图着色算法相对来说复杂度低，便于理解并且具有良好的实用性，所以广大研究者极为重视。文献[6-7]提出了基于比例公平的频谱资源分配算法，此算法结合注水算法可以完成频谱分配的次优方案，算法复杂度较高。文献[8]提出了基于图论着色模型的列表着色频谱分配算法。文献[9]则是在图着色理论基础上提出了优先改进最小邻居算法（Progressive Minimum Neighbor First，PMNF）分配模型，此算法的基本思想就是将最难着色的点优先进行着色处理，基于此思想，PMNF算法给每个顶点分配了一个独立的标签，用在限制条件约束下的最低的索引颜色中的最高标签来给顶点着色。文献[10]根据PMNF算法的思想提出了颜色敏感图着色算法（color sensitive graph coloring，简写CSGC）模型，其核心思想是将PMNF算法的最难着色点优先着色改为了将“价值”最大的点优先着色。文献[11]提出了基于CSGC算法的并行分配改进算法，在保证最优分配的前提下减少了分配算法所消耗的时间，减少了系统资源消耗。文献[12]则是在CSGC算法的基础上，考虑了用户等待时间因素，引入了之前的分配情况参数，减少了在资源紧张条件下的用户等待时间，尤其是降低了弱势用户等待分配响应所耗时间。文献[13]将CSGC算法与遗传算法进行了结合，更有效的实现了网络效益的最大化。文中的重点是研究在无线频谱资源紧张情况且保证系统效益前提下，提高系统频谱资源分配的公平性，引入已分配用户对于资源占用的状态参数，并根据这个参数定义用户优先级，确定分配时的用户优先级顺序，保障了未分配的弱势用户的权益，并减少了强势用户对于系统资源的过度消耗，在保证系统效益的前提下，提高了系统分配的整体公平性。

1 基于CSGC的频谱分配模型

假设在进行频谱资源分配时，用户的位置，可用的频谱资源等环境条件都是静态的。假设在一个认知网络中，次级用户（secondary user，简写为SU）的数量为N个（标号为0——N-1），频谱信道的数量为M个（0——M-1）。则分配模型的构成如下：

1）空闲频谱矩阵L：L={1n，m|1n，m∈{0，1}}N×M，L是一个N乘M阶的二进制矩阵。该矩阵体现了信道的可用性状态：当ln，m=1时，对于次级用户n来说信道m是可用的；当ln，m=0时，信道m对于次级用户n不可用。

2）信道效益矩阵B：B={bn，m}N×M，B也是一个N乘M阶的矩阵。bn，m表示次级用户n使用信道m（假设相邻的用户间无干扰）时可获得的效益。

3）干扰限制条件矩阵C：C={cn，k,m|cn，k,m∈{0，1}}N×N×M，C是一个阶矩阵N×N×M，该矩阵表述了次级用户之间的干扰限制条件。如果cn，k，m=1，次级用户n与次级用户k在同时使用信道m时将会互相干扰。限制条件由信道可用性决定， 例如 cn，k，m≤ln，m×lk，m且 cn，n，m= 1-ln，m。

4）无干扰的频谱分配矩阵A：A={an，m|an，m∈{0，1}，an，m≤1n，m}N×M为表示频谱分配情况的N乘M 阶二进制矩阵：如果信道m分配给用户n，an，m=1。此矩阵要满足无干扰条件：an，m·ak，m=0，if Cn，k，m=1；∀n，k＜N，m＜M。

5）用户频谱资源占用矩阵SU：SU={sun|sun∈N}1×N，SU为表示次级用户对于频谱资源占用情况的1乘N阶二进制矩阵：在初始化状态时，SU为全1矩阵，在分配过程中，当用户占用频谱资源时，sun递增1，否则sun维持当前值不变。

在经过上述数学建模之后，认知无线电网络频谱资源分配问题即被转化为双向图G=（V，L，E）着色问题[14-15]。V表示共享频谱资源的点集（即次级用户集合），L表示每个顶点的可用颜色列表（即可用的频谱信道资源），E表示两个顶点之间冲突的无向边集。对于任意的两个顶点u，v∈V，当cu，v，m=1时，顶点u和顶点v之间存在着一条m色边。这些边取决于相邻主用户的频谱使用状态以及次级用户u与v在信道m上的传输功率所决定的干扰条件C。

在本文中采用最大化总效益（Max-Sum-Reward）为频谱分配的最优化目标函数，其可以表述为：

式（1）表示最大化频谱效益，A∈∧N，M为满足条件的全部A的集合。本文中分别采用协作最大化总效益 （Collaborative-Max-Sum-Reward，CSUM）准则[10]与非协作最大化总效益（Non-collaborative-Max-Sum-Reward，NSUM）准则[10]。

1）CSUM准则的标签及着色表达式为：

式中，Dn，m为顶点n的m颜色特异度。Dn，m表示顶点n在颜色m上与其他相邻用户的冲突边的数目，也就是不能与n同时使用信道m的相邻的次级用户的数量。

bn，m/（Dn，m+1）为认知用户使用频谱信道m之后，对于整个系统的效益贡献。此规则充分考虑了频谱利用与相邻用户干扰之间的平衡，可以使系统性能达到全局最优。

2）NSUM准则的标签及着色表达式为：

与CSUM规则相比，由于每个顶点只考虑自己的效益并忽略了对于整个系统的影响，此规则的表现较为自私，是非协作的。

2 基于分配公平性的CSGC频谱分配改进算法

本算法的目标是在系统资源相对紧张时，在保证系统总效益损失不大的前提下，动态调节用户分配的优先级顺序，改善弱势用户分配地位并降低强势用户对于频谱资源的占用，从而提高系统整体公平性，减少认知用户间的“贫富差距”。基于此目标，在本算法中引入用户频谱资源占用参数，并根据此参数进行如下定义。

2.1 定 义

定义 次级用户分配优先级P

文中根据用户频谱资源占用状态来定义次级用户的分配优先级，在每轮分配过程中按照用户分配优先级顺序进行频谱分配，次级用户分配优先级P的定义为：

根据公式（5）的定义，次级用户的分配优先级与用户信道占用状态成反比。即用户频谱占用状态越大则优先级越低，用户频谱占用状态越小优先级则越高。通过调节SU，在频谱资源分配过程中动态调节次级用户的分配优先级P。

2.2 基于分配公平性的CSGC频谱分配改进算法

本算法充分结合用户对频谱资源占用状态信息进行频谱分配。即根据式（5）定义的分配优先级P来进行分配，分配优先级高的用户优先分配。当次级用户的分配优先级一样时，则采用经典CSGC频谱分配算法中的某个准则 （如CSUM协作最大化总效益准则；NSUM非协作最大化总效益准则等）来计算次级用户的标签值，标签值大的次级用户将进行优先分配。其中在CSUM准则下，标签值按照式（2）进行计算；在NSUM准则下，标签值按照式（3）进行计算。次级用户n分配完成后，退出本次分配，用户频谱资源占用参数SUn递增1。次级用户n未分配时，用户频谱资源占用参数SUn不变。这样，随着用户频谱资源占用参数的动态变化，本算法可以动态的调整次级用户的分配优先级，这样既提高了弱势用户的分配权限，也降低了强势用户对于频谱资源占用的权重，在对系统总效益影响较小的情况下保证了系统的整体公平性。

本算法考虑了用户频谱资源占用参数，减少了强势用户对于频谱资源占用的权重，降低了系统中用户的“两极分化”。在频谱资源进行分配时，用户优先级受用户频谱资源占用参数影响，被分配到频谱资源越多的用户优先级越低，被分配到频谱资源越少的用户优先级越高，未分配到的用户优先级最高维持1不变。

算法流程图如图1所示，算法步骤如下：

步骤1 系统进行初始化，更新各个节点的信息，检测用户状态，进行相关的建模。

步骤2 计算用户分配优先级别矩阵P，找出用户分配级别最高的顶点（认知用户），并按照某种分配准则（如CSUM或者NSUM等）计算标签值及其可用颜色（信道）。

步骤3找出标签值最大的顶点n，并判断顶点n是否唯一。若顶点n唯一，对其分配相对应颜色m。若顶点n不唯一，则随机选取一个顶点进行分配。

步骤4 更新用户频谱资源占用参数矩阵SU，更新用户表单及可用频谱资源表单，若同一分配优先级用户已全部完成分配或者该级别用户已无可用频谱资源，则进行下一级别用户的分配，否则返回步骤2。该级别中已分配用户的用户频谱资源占用参数递增1；未分配用户的用户频谱资源占用参数保持不变。

步骤5 次一分配级别的次级用户分配重复步骤2至步骤4。

步骤6 当最低级别的用户完成分配后，本轮分配结束。

图1 算法流程图

3 算法仿真及仿真结果分析

3.1 仿真参数与环境设定

在本文中利用Matlab软件对本文算法与原始CSGC算法分别在CSUM准则与NSUM准则下进行仿真比较，比较不同算法下的系统总效益与系统整体公平性情况。

仿真环境假设建立在一个无噪声，固定的无线网络上。当主用户占用一个频谱m时，该主用户的保护范围半径为dp（x，m），即在此范围内的所有次级用户不可以使用频谱m。次级用户n通过改变其在信道m上的传输功率来改变其干扰范围ds（n，m）的大小，从而避免对主用户的干扰。一个次级用户n使用主用户x所占用的频谱m的条件为满足ds（n，m）≤Dist（n，x）-dp（x，m），Dist（n，x）为次级用户 n与主用户x之间的距离。干扰范围ds可以用最小与最大传输[dmin，dmax]功率来限定。当ds小于dmin时，次级用户n即使未处于主用户的保护范围内，同样不可以使用频谱m。在指定区域中（10×10），设置一定数量的主用户与次级用户，由于本文算法重点考虑的是频谱资源紧张环境，所以在仿真中设定主用户数量为20个，频谱资源数M为10个，次级用户的数量N为20个。在仿真中，每个主用户随机的从10个频谱中选取一个占用。为简化问题，在仿真中假设每个主用户具有相同的保护范围Dp=const。在本算法中设定cmax=10，Dp=2，dmin=1，dmax=4。另外在仿真中用平均效益代替总效益来使仿真变得更容易：

3.2 仿真结果及结果分析

在完成上述仿真参数及环境设定之后，分别在CSUM准则与NSUM准则下对原始CSGC频谱分配算法和本算法进行仿真实验，最终仿真结果如图2～4所示。

图2和图3分别为次级用户分配到的频谱资源数统计图与系统效益统计图。在图2中横轴为用户标号，纵轴为各个次级用户被分配到的频谱资源数。虚线表示原始CSGC频谱分配算法，实线表示本算法。通过图2（a）中可以非常直观的看出虚线波动非常大，最大值和最小值分别为76与30，跨度达到了46；实线波动非常小，其最大值和最小值分别为58与48，跨度为10。图2（b）中同样可以观察到虚线波动大，其最大值与最小值分别为62与22，跨度为40；实线波动非常小，其最大值与最小值分别为43与36，跨度为7。图3中的曲线表示系统的效益，其中横轴为实验标号，纵轴为系统效益（为简化仿真，采用上文定义的平均效益）。虚线代表CSUM准则与NSUM准则下的原始CSGC频谱分配算法，实线为本算法。如图3所示，原始CSGC频谱分配算法的系统效益最好，本算法效益低于原始CSGC频谱分配算法，但差距不大。

图2 用户被分配的频谱资源数折线图

图4为次级用户分配的频谱资源柱形统计图，横轴为用户被分配的频谱资源数分组，纵坐标为用户数量分布统计。图4中的 4个子图分别对应CSUM准则与NSUM准则下的两种算法，通过对比，本算法的跨度小于原始CSGC频谱分配算法且次级用户的数量分布更加集中。这证明本算法很好的减少了频谱分配分配过程中产生的“边缘用户”，即减少了“弱势用户”数量与“强势用户”数量，提高了频谱资源的分配公平性。

通过对算法的仿真结果进行分析对比，总体来讲，本算法在频谱资源紧张的环境中，在保证系统效益变化不大的前提下，引入了用户频谱资源占用因素，通过自适应的改变次级用户分配优先级，有效减少了分配过程中的“边缘用户”数量，降低了系统中用户的“贫富差距”，提高了系统的公平性。

4 结 论

在频谱资源日趋紧张的大环境下，认知无线电技术为广大研究者指明了方向，提供了可行方案。在频谱分配过程中，尤其是在频谱资源紧张时，在系统中难以避免的会出现用户的“两极分化”现象，此现象极大的造成了分配的不公平性。这会导致在现实情况中，部分处于弱势地位的次级用户无法分配到频谱资源或者分配到的频谱资源过少，进而导致无法进行有效通信，而另一部分处于强势地位的次级用户却又被分配到大量的频谱资源，长期占用系统进行通信的不公平现象。在本文中第一次引入了基于用户频谱资源占用参数定义的优先级，通过在分配过程中动态的调整次级用户的分配优先级，降低了“强势用户”的分配权，提高了“弱势用户”分配权，改善了系统的“两极分化”现象。最后通过仿真分析结果证明：文中算法在频谱资源紧张的环境中，保证了系统效益，且充分提高了系统公平性。

图3 系统效益折线图

图4 用户分配频谱资源柱形统计图

参考文献：

[1]Joseph MitolaⅢ，Gerald Q.Maguire cognitive Radio:making software radios more personal[J].IEEE Personal Communications，1999，6（4）：3-18.

[2]Cordeiro C，Challapali K，Birru D.IEEE 802.22:The first worldwide wireless standard based on cognitive radios[C]//New Frontiers in Dynamic Spectrum Access Networks，11.2005:328-337.

[3]王钦辉，叶保留，田宇等.认知无线电网络中频谱分配算法[J].电子学报，2012，40（1）:147-154.

[4]莫文承．认知无线电频谱分配算法研究[D]．西安:西安电子科技大学，2008．

[5]杨铁军，林培培.改进遗传算法的认知无线电频谱分配[J]．计算机仿真，31（2）:250-254.

[6]Wong I C，Zukang Shen，Evans B L，et al.A low complexity algorithm forproportionalresource allocation in OFDMA systems[J].IEEE Workshop on Signal Processing Systems，2004:1-6.

[7]SHEN Zu-kang，Andrews J G，Evans B L，Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints[J].IEEE Transactions on Wireless Communication，2005，4（6）:2726-2737.

[8]WANG Wei，LIU Xin.List-Coloring based channel allocation for open-spectrum wireless Networks[C]// The 62nd IEEE Vehicular Technology Conference（VTC），2005：690-694.

[9]Ramanathan S，A unified framework and algorithm for channel assignment in wireless networks[J].Wireless Networks March 1999，5（2）：81-94.

[10]Peng C，Zheng H，Zhao B．Utilization and fairness in spectrum assignment for opportunistic spectrum access[J]．ACM mobile networks and applications（MONET），2006，11（4）:554-576.

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

[12]柳平，张敏．基于用户等待时间的频谱分配改进算法[J]．广东通信技术，2009，11（6）:17-20．

[13]郑志刚，薛菲，周井泉.网络效益最大化的认知无线电频谱分配方法[J]．计算机技术与发展，2013，23（8）:91-94.

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

[15]West D B.图论导引[M].骆吉洲，李建中，译，北京：电子工业出版社，2014.

An improved CSGC algorithm based on distribution fairness under the principle of Max-Sum-Reward

XU Song，LI Yu-feng
（College of Electronic and Information Engineering，Shenyang Aerospace University，Shenyang 110136，China）

For the problem of that the worse fairness of the allocation algorithm based on the traditional graph coloring，proposed a CSGC improved algorithm.Under the principle of Max-Sum-Reward，this algorithm improves the traditional CSGC algorithm by considering the factor of spectrum utilization.Especially in the cases of limited spectrum resource，this algorithm ensures the fairness of allocation and the needs of vulnerable users.The simulation results show that under the premise of system's reward this algorithm improves the overall fairness of the system.

cognitive radio；graph coloring；spectrum allocation；CSGC；fairness of allocation

TN929.5

：A

：1674－6236（2017）05-0097-06

2016-03-04稿件编号：201603036

徐 嵩（1986—），男，吉林公主岭人，硕士研究生，助理工程师。研究方向：信息与通信工程。