Truthful Auction Mechanisms with Performance Guarantee in Secondary Spectrum Markets
Truthful Auction Mechanisms with Performance Guarantee in Secondary Spectrum Markets
复制标题
DOI：
10.1109/tmc.2014.2343976
复制
发表时间：
2015-06
影响因子：
7.9
通讯作者：
He Huang;Yu-E. Sun;Xiangyang Li;Shigang Chen;Mingjun Xiao;Liusheng Huang
中科院分区：
文献类型：
--
作者：
He Huang;Yu-E. Sun;Xiangyang Li;Shigang Chen;Mingjun Xiao;Liusheng Huang
我们研究了一个频谱拍卖问题，每个新的频谱用户的请求具有空间，时间和频谱特征。我们的目标是设计真实的拍卖机制，最大限度地提高新用户（又名买家）的整体社会效率或频谱所有者（又名卖家）的收入。鉴于最优无冲突频谱分配问题是NP难问题，本文提出了一系列基于线性规划松弛、随机舍入、去随机舍入、单调去随机化和Lavi-Swamy方法的近似拍卖机制。与现有技术相比，我们有两个显著的进步：第一，我们的拍卖机制不仅是真实的，而且还提供了理论上可证明的性能保证，这是同一拍卖模型下现有工作所不具备的重要特征。其次，我们的拍卖机制支持空间和时间的频谱重用，这使得问题比现有的工作，只处理空间或时间重用更具挑战性。我们进行了大量的模拟研究所提出的机制的性能，和模拟结果证实了我们的理论分析。
We study a spectrum auction problem where each request from new spectrum users has spatial, temporal, and spectral features. Our goal is to design truthful auction mechanisms that maximize either the overall social efficiency of new users (a.k.a buyers) or the revenue of the spectrum owner (a.k.a seller). Given that the optimal conflict-free spectrum allocation problem is NP-hard, this paper proposes a series of near-optimal auction mechanisms based on the following approximation techniques: linear programming (LP) relaxation, randomized rounding, derandomized rounding, monotone derandomization, and Lavi-Swamy method. Comparing with the prior art, we make two significant advances: First, our auction mechanisms are not only truthful but also provide theoretically-provable performance guarantee, an important feature that existing work under the same auction model does not have. Second, our auction mechanisms support both spatial and temporal spectral reuse, which makes the problem more challenging than existing work that deals with only spatial or temporal reuse. We perform extensive simulations to study the performance of the proposed mechanisms, and the simulation results corroborate our theoretical analysis.