覃玉荣 胡虹梅

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

引 言

认知无线电是有效解决当前频谱资源紧缺问题的最佳方案［1-2］。为适应快速时变的认知无线电环境，动态频谱分配是必然要求。如何快速无干扰地分配频谱资源，是认知无线电频谱分配算法研究的关键。

图论着色模型是目前国内外动态频谱分配研究的热点模型之一，其特点是将认知无线电用户所组成的网络拓扑结构抽象成图，则频谱分配问题可转化为对图的着色研究。2005年，有学者在IEEE车载技术会议（VTC）上提出了避免干扰的List-Coloring频谱分配算法，研究目标为最大化系统频段分配数［3］。同年5月，其他学者在IEEE Communica-tions提出了颜色敏感的图论着色（CSGC）算法［4］，该算法考虑干扰和频带的差异性，以不同效益函数为分配目标来提高频谱利用率。2010年，Zhang Beiwei等在频谱分配过程中引入群智能技术，探究系统带宽收益与认知用户接入公平性之间的均衡［5］。此外，还有学者提出了局部议价算法，基于服务需求的分配算法等［6-11］。

目前国内外基于图论着色模型算法的基本特点是:在频谱分配过程中，按照效益目标函数逐次分配频段给满足条件的某单个认知用户，因此，存在时间开销过大瓶颈问题。有学者采用频谱并行分配（SAP）算法，即同时分配正交频带以尝试缩短分配的循环周期，在一定程度上缩短了系统的频谱分配时间开销［12］。但该方法分配频谱时仍然依次考虑整个系统中的认知用户，这是制约系统频谱分配速率有效提高的一个重要因素。……