A segment-graph algorithm for two-objective wireless spectrum allocation in cognitive networks

Abstract A segment-graph algorithm is provided for wireless spectrum allocation in cognitive networks based on the cooperation of the secondary users, which aim to maximize the utilization of the limited spectrum bands and minimize the total cost of all the secondary users to buy (or lease) the spectrum bands. The segment-graph of the complement graph of the original interference graph is defined. The proposed segment-graph algorithm is based on finding the complete subgraph of the segment-graph repeatedly. It is proved that the proposed algorithm always obtains the optimal solution if one of the segment-graphs is complete in each iteration. In general cases, the proposed algorithm dramatically reduces the total cost of all the secondary users. Comparative simulations agree with the theoretical results obtained.