Spectrum Allocation Based On Graph Theory In Cognitive Radio Networks

With the rapid growth of wireless communication technologies, there is growing demand for spectrum, which directly leads to the scarceness of the spectrum resource. Therefore, people focus on how to use spectrum dynamically and efficiently, and kinds of advancements in technology arise at the moment. Among such advancements, cognitive radio systems not only have the potential to make more efficient use of spectrum, but to also offer more adaptability and flexibility. Spectrum allocation is one of the key technologies of cognitive radio, which utilizes network resources efficiently, improves the system capacity, and plays a vital role in cognitive radio system performance.This paper mainly researches on spectrum allocation based on graph coloring model. Hence, firstly, the paper introduces the concept of cognitive radio, lists several common model of spectrum allocation, and illustrates the current status of spectrum allocation in cognitive radios.Then the paper introduces the relevant concepts in graph coloring theory, emphasizing the concepts of maximal independent set and maximum weighted independent set and the recursion algorithm for solving all the maximal independent sets, and builds the mathematic model for spectrum allocation based on graph coloring in cognitive radios.The third chapter lists four of the current algorithms in this model and proposes an improved algorithm considering the bad fairness of parallel algorithm, which can advance the fairness performance without increasing the time cost.In the chapter four, firstly, based on the improved algorithm above, the paper proposes joint rules algorithm which uses two different rules in the allocation process. The simulation results show that selecting the suitable coefficients, the joint rules algorithm could perform better than the algorithm using single rule. Then , the paper proposes the maximum weighted independent set spectrum allocation algorithm, whose time cost has nothing to do with the number of cognitive users, and whose fairness closes to the maximum.