Truthful spectrum auction design for secondary networks

Opportunistic wireless channel access by non-licensed users has emerged as a promising solution for addressing the bandwidth scarcity challenge. Auctions represent a natural mechanism for allocating the spectrum, generating an economic incentive for the licensed user to relinquish channels. A severe limitation of existing spectrum auction designs lies in the over-simplifying assumption that every non-licensed user is a single-node or single-link secondary user. While such an assumption makes the auction design easier, it does not capture practical scenarios where users have multihop routing demands. 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 aim to design truthful auctions for allocating channels to SNs in a coordinated fashion that maximizes social welfare of the system. We use simple examples to show that such auctions among SNs differ drastically from simple auctions among single-hop users, and previous solutions suffer severely 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 based on primal-dual linear optimization, with a proven performance guarantee for approaching optimal social welfare. A key technique in our solution is to decompose a linear program (LP) solution for channel assignment into a set of integer program (IP) solutions, then applying a pair of tailored primal and dual LPs for computing probabilities of choosing each IP solution. We prove the truthfulness and performance bound of our solution, and verify its effectiveness through simulation studies.