Designing Truthful Spectrum Auctions for Multi-hop Secondary Networks

Opportunistic wireless channel access granted to non-licensed users through auctions represents a promising approach for effectively distributing and utilizing the scarce wireless spectrum. A limitation of existing spectrum auction designs lies in the over-simplifying assumption that every non-licensed secondary user is a single node or single-hop network. For the first time in the literature, we propose to model non-licensed users as secondary networks (SNs), each of which comprises of a multihop network with end-to-end routing demands. We use simple examples to show that such auctions among SNs differ drastically from simple auctions among single-hop users, and previous solutions suffer from local, per-hop decision making. We first design a simple, heuristic auction that takes inter-SN interference into consideration and is truthful. We then design a randomized auction framework based on primal-dual linear optimization, which is automatically truthful and achieves a social welfare approximation ratio that matches one achieved by cooperative optimization assuming truthful bids for free. The framework relieves a spectrum auction designer from worrying about truthfulness of the auction, so that he or she can focus on social welfare maximization while assuming truthful bids for free.