Abstract: This paper analyzes the various spectrum allocation algorithms of graph coloring theory and concerns the problem of costing too much time. It combines connected component theory with the method that divides graph into subgraphs which have one color. A new method is proposed, which can parallel process all one-colored connected branches. This method can be applied to each algorithm to divide graph into small slices. And in view of the problem of unbalanced degree of users’ satisfaction, an amendment is presented, which adjusts allocated spectrums to improve the proportion of satisfied users. The simulation results show that the proposed algorithm is fast and makes more users meet the needs of requirements effectively.

Key words: cognitive radio, spectrum allocation, graph coloring, parallel, connected branch

摘要： 针对各类图论着色频谱分配算法的时间开销过大的问题，提出了一种并行单色连通分支处理拓扑图的方法。该方法结合连通分量理论和单色子图分解法，可应用于目前所有的图论着色模型的拓扑图分解中。并且根据认知用户的需求来调整分配使满意的用户比例增大，从而解决了分配结果存在的用户满意度不均衡情况。仿真结果表明，提出的算法是一种快速且能够使更多用户满足需求的有效方法。

关键词: 认知无线电, 频谱分配, 图论着色, 并行, 连通分支