《电子技术应用》
您所在的位置:首页 > 通信与网络 > 设计应用 > 基于图着色理论的认知网络频谱分配策略研究
基于图着色理论的认知网络频谱分配策略研究
2017年电子技术应用第3期
陈剑斌1,赵志远2,陈 章1,杨 霖1
1.南京电讯科技研究所,江苏 南京210007;2.国防信息学院,湖北 武汉430010
摘要: 为了解决认知网络下的动态频谱分配问题,结合图着色理论分析构建了认知系统频谱分配模型。在此基础上结合极大独立集(MIS)算法,通过设计综合分配权重,提出了一种基于信道效益的认知网络动态频谱分配算法。仿真结果表明,相比现有的MIS、Greedy算法,该算法能够有效提升实际认知网络系统的频谱利用率和公平性指标。
中图分类号: TN912.6
文献标识码: A
DOI:10.16157/j.issn.0258-7998.2017.03.023
中文引用格式: 陈剑斌,赵志远,陈章,等. 基于图着色理论的认知网络频谱分配策略研究[J].电子技术应用,2017,43(3):92-95.
英文引用格式: Chen Jianbin,Zhao Zhiyuan,Chen Zhang,et al. The research of spectrum allocation strategy for cognitive radio network based on graph coloring theory[J].Application of Electronic Technique,2017,43(3):92-95.
The research of spectrum allocation strategy for cognitive radio network based on graph coloring theory
Chen Jianbin1,Zhao Zhiyuan2,Chen Zhang1,Yang Lin1
1.Nanjing Telecommunication Technology Institute,Nanjing 210007,China; 2.National Defense Information Academy,Wuhan 430010,China
Abstract: In order to solve the problem of dynamic spectrum allocation in cognitive radio network, the spectrum allocation model for cognitive radio network was analyzed and put forward by using the graph coloring theory. Then based on the Maximal Independent Set algorithm(MIS), the integrated allocation weight was introduced in this paper. According to the weight, a dynamic spectrum allocation algorithm based on the channel benefit was proposed. Simulation results show that the proposed algorithm has better performance in utilization and fairness of spectrum allocation compared to MIS and Greedy algorithm.
Key words : cognitive radio network;spectrum allocation;maximal independent set;benefit matrix;integrated allocation weight

0 引言

    随着无线网络技术的快速发展,有限的频谱资源成为制约未来无线网络性能的主要瓶颈。为了更有效地利用频谱资源,MITOLA J提出了认知无线电(Cognitive Radio,CR)的概念[1]。在认知无线网络(Cognitive Radio Network,CRN)中,同时存在着主用户(Primary User,PU)和认知用户(Cognitive User,CU)。CU通过感知并接入当前未被PU使用的授权频段来提高频谱利用率。其中认知环境下CU的动态频谱分配是认知无线电技术需要解决的一个重要问题和难题。

    近年来,认知无线电中的动态频谱资源分配问题得到了广泛关注和研究。在基于图着色理论模型的认知网络动态频谱资源分配方面,文献[2,3]分别以最大化频谱利用率和公平性为目标,首次在认知无线电动态频谱分配中引入了图论的相关概念。在此基础上,文献[4]提出了基于极大独立集(MIS)的频谱分配算法,大大降低了频谱分配的收敛时间。但上述几种算法都未考虑信道频谱效益在各CU间的差异性,无法准确模拟无线信道实际情况,因此不适用于实际认知网络。以上述研究内容为基础,本文首先介绍了认知网络系统架构,在此基础上引入效益矩阵[5]构建了基于图着色理论的认知网络频谱分配模型,并提出改进算法实现了该模型下的频谱分配。

1 认知网络频谱分配模型

    本文考虑如图1所示的认知网络系统[6],系统中包含了K个PU和N个CU,各用户共用M个信道与认知基站(Cognitive Based Station,CBS)进行通信。系统中,CBS保持静止,PU和CU可以随机运动。任一时刻,PU占用一个信道或保持静默状态。CU根据当前临近频谱空间中的可用信道与CBS进行通信。

tx1-t1.gif

    图2将图1认知网络系统抽象成图,每个用户对应一个顶点。图中虚线圆表示PU的功率覆盖范围。当PU工作于信道m时,信道m对于虚线圆内的所有CU都是不可用的。图中CU顶点间的虚线边代表CU间的干扰冲突,亦即虚线两边的CU不能分配相同的信道资源。

tx1-t2.gif

    每个PU的标号代表当前时刻PU的工作信道;每个CU的标号集合代表当前时刻该CU的可用信道资源。假设CBS可以完整获得这些信息,并据此为各CU分配通信信道。文献[2-4]引入图着色理论对认知网络建模,将认知网络频谱分配问题转化为已知空闲矩阵L和干扰矩阵C条件下,分配矩阵A的求解过程。但模型中没有体现信道对于不同CU的效益差异,不符合认知网络的实际情况,因此无法适用于实际认知网络系统。

    基于此,在认知网络频谱分配模型中引入效益矩阵B={bn,m}N×M[5],其中bn,m代表认知用户n使用信道m时获得的效益权重。该矩阵衡量了信道m对于不同用户n的通信性能差异。本文以第n个用户在信道m上的传输率rn,m(t)作为效益指标。定义第n个CU的误比特率要求为Pn,t时刻其在信道m上的信噪比为βn,m(t),则有:

    tx1-gs1.gif

    这样在完成频谱分配后,认知网络的频谱总效益为:

    tx1-gs2.gif

其中an,m∈A,代表认知无线网络的信道分配结果。

2 基于信道效益的MIS算法(CB-MIS)

    图论中,存在边的节点称为相邻节点,两两不相邻的顶点所构成的极大集合称为极大独立集[2]。图2所示拓扑对应的极大独立集划分结果如图3所示。

tx1-t3.gif

    在划分极大独立集基础上,文献[4]设计了MIS算法为各极大独立集分配信道,从而获得分配矩阵A。但MIS算法在分配过程中,将信道在图中出现的总次数作为信道分配优先级的唯一考虑因素。而在实际认知网络中,由于用户所处的环境以及采用的调制编码技术不同,同一信道对于不同认知用户具有不同的通信效益。因此MIS算法应用在实际认知网络下显然是不合理的。针对这一点,首先定义信道效益指标:

    tx1-gs3.gif

    信道效益指标Ei,m代表了将信道m分配给极大独立集MISi对网络中各CU信道效益的影响。分子表示将信道m分配给极大独立集MISi时,极大独立集MISi内所有节点的传输速率总和;分母表示将信道m分配给极大独立集MISi时,极大独立集MISi以外的所有节点传输速率损失。该指标越大,表示当前分配方案在最大化MISi内节点信道效益与最小化MISi外节点信道效益损失方面能够得到更好的平衡。

    在此基础上,定义极大独立集MISi中共有信道m的综合分配权重

    tx1-gs4.gif

    式(4)中,前半部分利用空闲矩阵信息,反映了信道m在图中出现的次数对分配权重的影响:信道m出现次数越多,此时将该信道分配给极大独立集MISi对其他CU的影响越大,因此对应的分配权重也就越小。后半部分考虑了信道效益对分配权重的影响,0≤α≤1为调节系数。当α=1时,综合分配权重只关注信道出现次数,此时CB-MIS算法退化为MIS算法。这样,CB-MIS算法在考虑信道效益差异的同时实现了与MIS算法的兼容。

    改进后的算法流程图如图4所示。CB-MIS算法首先根据空闲矩阵L、干扰矩阵C得到图中所有的最大独立集。在此基础上执行基于极大独立集的分配过程。与MIS算法不同,CB-MIS算法在为极大独立集MISi分配信道资源时,用综合分配权重代替信道出现总次数作为优先级参考指标。在此基础上,CB-MIS算法将可用信道集合中具有最大综合分配权重的信道分配给独立集MISi。需要注意的是,式(3)、(4)中用户可用信道情况ln,m与空闲矩阵L相关联,其随着分配进程动态变化。

tx1-t4.gif

    当执行完基于极大独立集的分配过程后,若网络中还有可用频谱资源,则按照已分配频谱数和连接度数由低到高的顺序依次选择CU执行信道分配。此时,每个CU等效于一个极大独立集。

    针对图1、图2所示认知网络系统拓扑,利用CB-MIS算法(α=0)得到的信道分配结果如图5所示。

tx1-t5.gif

3 仿真分析

    构建如图1、图2所示的认知网络仿真场景。场景中,系统无线信道数目为M,包含5个PU以及N个CU,各用户随机分布于1 000 m×1 000 m区域范围内。PU的功率覆盖半径为300 m;CU之间的干扰冲突距离为200 m。在各用户位置拓扑确定后,根据上述参数,首先可以得到系统的空闲矩阵L和干扰矩阵C。

    与系统效益矩阵B相关的参数如下:信道采用6径时频双选瑞利衰减模型;根据节点与CBS的距离,其可用信道SNR在30~40 dB之间变化。系统误比特率要求为10-3。频谱平均利用率U和公平性F分别定义如下[4]:

     tx1-gs5-6.gif

    仿真中,首先固定系统信道数M=24,分析不同CU数量下的算法性能。为了提高仿真准确性,对于特定的CU数量,仿真结果取100个随机拓扑下的均值。

    从图6的仿真结果可以看出,在频谱平均利用率上Greedy算法要优于MIS算法,但其公平性更差,这与文献[3,4]的结论一致。对于CB-MIS算法,当α=1时其指标性能与MIS算法完全一致,这验证了前文的分析。当α=0时,由于在信道分配过程以信道效益指标作为分配优先级的确定依据,因此CB-MIS算法在频谱平均利用率和公平性上都优于Greedy和MIS算法。从仿真结果中还可以看出,在系统信道数目一定的条件下,随着用户数量的增加,信道分配过程中用户之间的需求冲突愈发明显,从而导致3种算法的频谱平均利用率和公平性都有所下降。其中由于Greedy算法只关注最大化频谱平均利用率,因此其公平性下降最为明显。

tx1-t6.gif

    下面通过固定系统CU数N=12,分析可用信道数量变化情况下的算法性能。根据前面的仿真结果及分析,α=1时CB-MIS等价于MIS算法,因此这边只给出CB-MIS算法在α=0的结果。对应的仿真结果如图7所示。

tx1-t7.gif

    从图7可以看出,3种算法下的系统频谱利用率及公平性相对关系与图5中的仿真结果基本一致。同时注意到当系统中信道数目较少时,CB-MIS算法与MIS算法之间的差别很小。这说明在频谱资源受限时,极大独立集内各CU的共有信道资源较少,因此此时信道效益对两种基于极大独立集的频谱分配算法的影响较小。随着信道数目的增加,极大独立集内各CU可能有多个共有信道,此时信道效益对频谱分配方案的影响越加明显。

    在CU数目固定的情况下,对于Greedy算法,其公平性与系统可用信道数量之间没有必然的相关性。而对于CB-MIS算法和MIS算法,随着系统可用信道数量增加,用户间分配冲突减少,因此其公平性有所提升。另一方面,由于考虑了信道增益指标,因此CB-MIS算法公平性优于MIS算法。

4 结语

    本文研究了基于图着色论模型的认知网络频谱分配策略。文章首先构建了基于图着色理论的认知网络频谱分配模型。最后考虑实际认知网络中信道在不同CU间的通信效益差异,基于MIS算法设计了CB-MIS算法。仿真结果表明,通过设置不同的调节系数,CB-MIS算法在兼容MIS算法的同时能够方便地实现对实际认知网络的适用。在实际认知网络下,CB-MIS算法在频谱利用率和公平性指标上都优于现有MIS、Greedy算法。

参考文献

[1] MITOLA J,MAQUIRE G Q.Cognitive radio:making software radios more personal[J].IEEE Personal Communications,1999,6(4):13-18.

[2] Wang Wei,Liu Xin.List-coloring based channel allocation for open-spectrum wireless networks[C].The 62nd IEEE Vehicular Technology Conference(VTC),2005,1:690-694.

[3] 廖楚林.认知无线电系统的频谱分配算法研究[D].成都:电子科技大学,2007.

[4] 樊路,刘玉涛,谭学治,等.认知无线电中基于极大独立集的频谱分配算法[J].科学技术与工程,2009,9(16):4645-4648.

[5] 段瑞杰,姚富强,李永贵,等.基于图着色理论的短波无线接入网动态频谱分配方法[J].计算机工程,2016,42(4):94-100.

[6] 陈剑斌,朱磊,赵莺,等.适用于频谱重叠共享CRN的分组调度算法[J].计算机工程,2012,38(3):93-96.



作者信息:

陈剑斌1,赵志远2,陈  章1,杨  霖1

(1.南京电讯科技研究所,江苏 南京210007;2.国防信息学院,湖北 武汉430010)