Truthful least-priced-path routing in opportunistic spectrum access networks

We study the problem of finding the least-priced path (LPP) between a source and a destination in opportunistic spectrum access (OSA) networks. This problem is motivated by economic considerations, whereby spectrum opportunities are sold/leased to secondary radios (SRs). This incurs a communication cost, e.g., for traffic relaying. As the beneficiary of these services, the end user must compensate the service-providing SRs for their spectrum cost. To give an incentive (i.e., profit) for SRs to report their true cost, typically the payment to a SR should be higher than the actual cost. However, from an end user's perspective, unnecessary overpayment should be avoided. So we are interested in the optimal route selection and payment determination mechanism that minimizes the price tag of the selected route and at the same time guarantees truthful cost reports from SRs. This setup is in contrast to the conventional truthful least-cost path (LCP) problem, where the interest is to find the minimum-cost route. The LPP problem is investigated with and without capacity constraints at individual SRs. For both cases, our algorithmic solutions can be executed in polynomial time. The effectiveness of our algorithms in terms of price saving is verified through extensive simulations.