Two Dimension Spectrum Allocation for Cognitive Radio Networks

• Published in: IEEE transactions on wireless communications 2014-03, Vol.13 (3), p.1410-1423
• Main Authors: Li, Changle, Liu, Zhe, Geng, Xiaoyan, Dong, Mo, Yang, Feng, Gan, Xiaoying, Tian, Xiaohua, Wang, Xinbing
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Allocations; Applied sciences; Approximation; Approximation algorithms; Approximation methods; Auctions; Cognitive radio; Cognitive radio networks; Combinatorial analysis; combinatorial auction; Complexity; Cost accounting; Exact sciences and technology; Flexibility; Mathematical analysis; Networks; Organization, operation and development plans; Polynomials; Radiocommunication specific techniques; Radiocommunications; Resource management; Spectrum allocation; Telecommunications; Telecommunications and information theory; Time-frequency analysis
• ISSN: 1536-1276; 1558-2248
• DOI: 10.1109/TWC.2014.012814.130577

In this paper, we develop a truthful and efficient combinatorial auction scheme under a novel spectrum allocation model that can achieve a worst-case approximation ratio \sqrt{m} in social welfare. We propose to tackle the dynamic spectrum access problem in cognitive radio (CR) networks with time-frequency flexibility requirements. We model the spectrum opportunity in a time-frequency division manner and the spectrum allocation as a combinatorial auction. Then we design an auction mechanism to reach the upper bound in polynomial time and propose a combined approach to improve the bound in the cost of increasing computational complexity. A truthful payment that gives incentive to the SUs for revealing the truthful valuation of the desirable bundle of slots is presented. In order to reduce the complexity, we simplify the general model to a modified model that only allows frequency flexibility, and then present a truthful, optimal and computationally efficient auction mechanism. Extensive simulation results of the social welfare and spectrum ratio show that the performance of the combined approximation algorithm is better than the sorting based greedy algorithm.