Designing Truthful Spectrum Auctions for Multi-hop Secondary NetworksIEEE Transactions on Mobile Computing


Zongpeng Li, Baochun Li, Yuefei Zhu
Computer Networks and Communications / Electrical and Electronic Engineering / Software


Core-selecting combinatorial auction design for secondary spectrum markets

Yuefei Zhu, Baochun Li, Zongpeng Li

Design and Implementation of WDM Based Multi-Hop Local Area Network

O. Khayam, A. Masood, W.H. Khattak, K.S. Chaudhry

Auction Based Spectrum Trading for Cognitive Radio Networks

M. N. Tehrani, M. Uysal

Design of Multi-Hop Handovers for Hybrid Ad Hoc Networks in Multi-Channel Environments

Wan-Seon Lim, Dong-Wook Kim, Woo-Jae Kim, Young-Joo Suh, Young-Min Cha, Byungdeok Chung



Designing Truthful Spectrum Auctions for

Multi-hop Secondary Networks

Zongpeng Li, Senior Member, IEEE , Baochun Li, Senior Member, IEEE , and Yuefei Zhu

Abstract—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.

Index Terms—Truthful auctions, secondary spectrum allocation, secondary networks, linear programming, primal-dual algorithms 1 INTRODUCTION

RECENT years have witnessed substantial growth inwireless technology and applications, which rely crucially on the availability of bandwidth spectrum.

Traditional spectrum allocation is static, and is prone to inefficient spectrum utilization in both temporal and spatial domains: large spectrum chunks remain idling while new users are unable to access them. Such an observation has prompted research interest in designing a secondary spectrum market, where new users can access a licensed channel when not in use by its owner, with appropriate remuneration transferred to the latter.

In a secondary spectrum market, a spectrum owner or primary user (PU) leases its idle spectrum chunks (channels) to secondary users (SUs) through auctions [1], [2]. SUs submit bids for channels, and pay the PU a price to access a channel if their bids are successful. A natural goal of spectrum auction design is truthfulness, under which an SU’s best strategy is to bid its true valuation of a channel, with no incentive to lie. A truthful auction simplifies decision making at SUs, and lays a foundation for good decision making at the PU. Another important goal in spectrum auction design is social welfare maximization, i.e., maximizing the aggregated ‘happiness’ of everyone in the system. Such an • Z. Li is with the Department of Computer Science, University of Calgary,

Calgary, AB T2N 1N4, Canada. E-mail: • Y. Zhu and B. Li are with the Department of Electrical and Computer

Engineering, University of Toronto, Toronto, ON M5S 3G4, Canada.

E-mail: {yuefei, bli}

Manuscript received 28 Aug. 2012; revised 3 May 2013; accepted 10 May 2013. Date of publication 21 May 2013. date of current version 23 Dec. 2014.

For information on obtaining reprints of this article, please send e-mail to:, and reference the Digital Object Identifier below.

Digital Object Identifier 10.1109/TMC.2013.64 auction tends to allocate channels to SUs who value them the most. The focus of this work is to advance the studies of spectrum auction design from serving single-hop secondary users to multi-hop secondary networks.

A unique feature of spectrum auction design is the need of appropriate consideration for wireless interference and spatial reuse of channels. A channel can be allocated to multiple SUs provided that they are far apart, with no mutual interference. Optimal channel assignment for social welfare maximization is equivalent to the graph colouring problem, and is NP-hard [3], even assuming truthful bids are given for free. Existing works on spectrum auctions often focus on resolving such a challenge (e.g., [4], [5]) while assuming the simplest model of a SU: a single node, or a single link, similar to a single hop transmission in cellular networks [2], [4], [5].

After extensive research during the past five years, auction design for single-hop users, each requesting a single channel, has been relatively well understood. However, a practical SU may very well comprise of multiple nodes forming a multi-hop network, which we refer to as a secondary network (SN). These include scenarios such as users with multihop access to base stations, or users with their own mobile ad hoc networks. SNs require coordinated end-to-end channel assignment, and in general benefit from multi-channel diversity along its path. The SN model subsumes the SU model as the simplest special case.

Fig. 1 depicts three co-located SNs, SN1, SN2 and SN3, which have interference with one another, because their network regions overlap. The primary network (PN) has two channels, Ch1 and Ch2, which have been allocated to SN1 and SN2, respectively. Now SN3 wishes to route along a two-hop path 1 → 2 → 3. Under existing single-channel 1536-1233 c© 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.

See for more information.


Fig. 1. Secondary spectrum market with 3 SNs and 2 channels. auctions for SUs, SN3 cannot obtain a channel, because each channel interferes with either SN1 or SN2. However, a solution exists by relaxing the one channel per user assumption, and assigning Ch1 to link 1 → 2 and Ch2 to the link 2 → 3.