Finding cheap routes in profit-driven opportunistic spectrum access networks: A truthful mechanism design approach

Tao Shu, Marwan Krunz

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In this paper, we explore the economic aspects of routing/relaying in a profit-driven opportunistic spectrum access (OSA) network. In this network, primary users lease their licensed spectrum to secondary radio (SR) providers, who in turn provide opportunistic routing/relaying service to end-users if this service is profitable, i.e., if the payment offered by the end-user (a.k.a. the price) exceeds the SR's relaying spectrum cost. This cost is considered private information known only to SRs. Therefore, the end-user has to rely on costs reported by SRs to determine his routing and payment strategy. The challenge comes from the selfish nature of SRs; an SR may exaggerate his cost to achieve greater profit. To give incentive to an SR to report the true cost, the payment must typically be higher than the actual cost. However, from the end-user's perspective, overpayment should be avoided as much as possible. Therefore, we are interested in the optimal route selection and payment determination mechanism that minimizes the price of the selected route while simultaneously guaranteeing truthful cost reporting by SRs. We formulate this problem as finding the least-priced path (LPP), and we investigate it without and with link capacity constraints. In the former case, polynomial-time algorithm is developed to find LPP and calculate its truthful price. In the latter case, we show that calculating the truthful price of the LPP is in general computationally infeasible. Consequently, we consider a suboptimal but computationally feasible approximate solution, which we refer to as truthful low-priced path (LOPP) routing. A polynomial-time algorithm is proposed to find the LOPP and efficiently calculate its truthful price. A payment materialization algorithm is also developed to guarantee truthful capacity reporting by SRs. The effectiveness of our algorithms in terms of price saving is verified through extensive simulations.

Original languageEnglish (US)
Article number6024474
Pages (from-to)530-543
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number2
StatePublished - Apr 2012


  • Least-priced-path routing
  • opportunistic spectrum access
  • truthful mechanism design

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Finding cheap routes in profit-driven opportunistic spectrum access networks: A truthful mechanism design approach'. Together they form a unique fingerprint.

Cite this