TY - JOUR
T1 - Finding cheap routes in profit-driven opportunistic spectrum access networks
T2 - A truthful mechanism design approach
AU - Shu, Tao
AU - Krunz, Marwan
N1 - Funding Information:
Manuscript received December 28, 2009; revised January 10, 2011; accepted July 17, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor S. Sarkar. Date of publication September 22, 2011; date of current version April 12, 2012. This work was supported in part by the NSF under Grants CNS-1016943, CNS-0721935, CNS-0904681, and IIP-0832238, Raytheon, and the “Connection One” Center. A preliminary version of this paper was presented at the IEEE Conference on Computer Communications (INFOCOM), San Diego, CA, March 15–19, 2010.
PY - 2012/4
Y1 - 2012/4
N2 - 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.
AB - 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.
KW - Least-priced-path routing
KW - opportunistic spectrum access
KW - truthful mechanism design
UR - http://www.scopus.com/inward/record.url?scp=84860004658&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860004658&partnerID=8YFLogxK
U2 - 10.1109/TNET.2011.2166274
DO - 10.1109/TNET.2011.2166274
M3 - Article
AN - SCOPUS:84860004658
SN - 1063-6692
VL - 20
SP - 530
EP - 543
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 2
M1 - 6024474
ER -