Truthful Multi-Unit Multi-Broker Auction Mechanism with Approximate Social-Welfare in Ad Hoc Cognitive Radio Networks
Nour Abu Riala, Yaser Jararweh, Mahmoud Al-Ayyoub and Haythem Bany Salameh
In this paper, we consider the cooperative relay problem in an ad hoc cognitive radio (CR) network consisting of two types of CR nodes: continuous power nodes (CPN) and limited/intermittent power nodes (LPN). All CR nodes are associated with a Secondary Base Station (SBS). To improve energy efficiency and extend the lifetime of LPNs, we allow LPNs to cooperate with neighboring “idle” CPNs to deliver/relay their packets to the SBS while providing incentives to relay CPNs. A crucial challenge in enabling such type of cooperative relay lies in resolving the competition between LPNs on the potential relay opportunities. To regulate such a competitive environment, we develop an auction-based market model consisting of a set of brokers (idle CPNs) and a set of available frequency channels. The brokers iteratively issue short-term dynamic spectrum leases of these channels to competing LPNs. The SBS receives the LPNs’ bids and computes the output of the auction such that the maximum social-welfare (SW) is achieved by effectively allocating the available channels to the CR nodes. Computing a solution with maximum SW is, in general, NP-hard (even for one broker), but can be solved optimally using a pseudo polynomial time algorithm. Thus, we devise a polynomial time auction mechanism with near-optimal SW. Our mechanism enforces the very valuable property of strategy-proofness to mitigate the market manipulation problem resulting from untruthful behavior of the bidders (enforcing truthful bidders behavior). Simulation results are provided, which verify the effectiveness of our mechanism and demonstrate the significant gain achieved over a reference greedy solution.
Keywords: Spectrum Auctions; Multi-Unit Multi-Broker Auction; Polynomial Dynamic Programming; Pseudo-Polynomial Dynamic Programming; Branch and Bound