1 Introduction

The twenty-first century has seen an explosion in wireless technology. From mobile phones to wireless local area networks, users want always to be connected to the internet no matter where they are [1, 2]. Wireless Mesh Networks (WMNs) help to solve spectrum scarcity problem by providing high-bandwidth network and extending internet access and other networking services. Although WMNs improve performance, some factors degrade the network performance. These factors include spectrum scarcity, large fluctuation of spectrum demand and the inefficiency in the spectrum usage [2]. To overcome spectrum scarcity problem, Federal Communications Commission (FCC) has already started work on the concept of spectrum sharing where secondary users (SUs) can access the unused spectrum if they get permission from primary users (PUs) [1].

Dynamic spectrum access (DSA) is proposed to solve spectrum scarcity problem. It enables SUs to adjust communication parameters (such as operating frequency, transmission power, and modulation scheme) in response to the changes in the radio environment [1–5]. DSA enables implementation of cognitive radio (CR). CR allows SUs to access the unused licensed spectrum using underlay, overlay or spectrum trading approaches [1–5]. In this paper, we focus on spectrum trading approach where PUs rent free spectrum for SUs. PUs need to determine how spectrum can be optimally priced for SUs, so that the profit is maximized. In our scheme, SUs periodically submit bids for PUs (sellers), who in turn post spectrum prices for each auction session. The highest bidders (SUs) win the auction and their requests are fulfilled in this session. Our auction scheme adapts quickly to the changes in the spectrum market. A sequence of auctions is carried out periodically in the spectrum market to meet spectrum demand. The winners are charged a constant usage price specified by the auction scheme.

Two challenges should be considered for the optimal design of dynamic auction:

  • Designing auction mechanism over different auction session with service guaranteed where the rented spectrum should not be offered for the next sessions until the current requests are served. Our optimal design allows the PU to keep some available spectrum for the future profitable request. The scheme rejects some requests (low bidders) even the available spectrum is sufficient to accommodate these requests.

  • Making sure the auction design is truthful where each SU submits its true valuation of spectrum with no incentive to lie. Truthful auction eliminates the SUs’ incentive for strategic behavior that may harm the integrity of auction and provides accurate information about spectrum demand for PUs. Demand information helps PUs to predict market dynamics in the future.

To address these challenges, we propose optimal auction scheme that determines the size of spectrum that should be offered for each auction session. For SUs, we specify dynamic truthful payment based on the offered spectrum size over time. The main objective of our scheme is to maximize the generated profit of PUs. Unfortunately, this objective alone encourages SUs to lie about their real valuations (i.e. an “untruthful” auction), instill fear of market manipulation, and indirectly possibly decrease the reported profit. Moreover, in a competitive spectrum market, PUs spend a lot of time/effort for predicting the behavior of other SUs and planning against them. In our work, our main concern is designing a spectrum auction mechanism that encourages truthful behavior of SUs.

The rest of this paper is organized as follows. Section 2 describes the spectrum market and auction model. Related works are reviewed in Section 3. The auction mechanism is presented in Section 4. Section 5 presents the performance evaluation results. Finally the paper is concluded and future research directions are given.

2 Network Overview

In this section, we present our assumptions. The secondary network consists of two types of nodes: mesh routers (MRs) and mesh clients (MCs). A wireless mesh network has several MRs that jointly form a cluster [26]. Each cluster is a WLAN, where MRs (SUs) play the role of access point and the MCs act as nodes served by them. The algorithm proposed in [26] is used to form and maintain clusters. Moreover, the proposed signaling protocol in [26] is used to manage communication among the PUs and the SUs. MRs have fixed locations whereas MCs are moving and changing their places arbitrarily. SUs form the CR which is overlaid on a PU’s network. This new network relays MCs traffic to the destinations using the rented spectrum from PUs. In our work we refer to MR as a SU.

The spectrum market consists of E PUs and N SUs. We define a PU as a spectrum owner that may rent a spectrum to other users. Each PU has K channels and it offers these channels to MRs (SUs). The total capacity of the network is given as:

$$ F = KE $$
(1)

MRs use the rented channels to serve MCs. Each jth PU, j = 1, 2,….,E, specifies S j the spectrum size for renting, and the price of spectrum. We assume that these parameters are changed over time corresponding to the network conditions, such as traffic load, spectrum demand, and spectrum cost. The PU therefore needs to change the price and the size of the offered spectrum when needed.

We use auction theory in our network to extract an optimal control policy for managing spectrum size and price for all SUs. From PUs point of view, the optimal resource management scheme is the one which maximizes their revenue. However, some constraints prevent PUs from maximizing their profits such as resource constraint, SUs budget and competition among SUs. In this paper, we address the problem of optimizing spectrum trading in the secondary spectrum market for satisfying SUs and for PUs and maximizing the profit of PUs. SUs pay the PUs for their spectrum usage based on short term contract. PUs serve different SUs to maximize their profits while considering the trading constraints.

Since spectrum usage charges differ between SUs, serving new SUs whenever there is available spectrum may not maximize the PU’s revenue. The PU has to compute the gained reward and decide whether to serve the request or reject it and wait till a user with worthy reward arrives. Therefore, the optimal resource management scheme is mandatory in our system. A policy for maximizing the profit for the PUs plays an important role in the spectrum market.

For SUs, we assume that spectrum requests arrival follows Poisson distribution and each spectrum request has arrival rate λ The service time μ for each request is assumed to be exponentially distributed. These assumptions capture some reality of wireless applications such as phone call traffic [27–29]. The problem of optimal resource allocation for maximizing PUs’ revenue is a challenging problem in the design of our network. The main motivation for the research in this problem is to adapt the services to the changes in the structure of the spectrum secondary market.

3 Related Work

Using auction for spectrum trading is not a new idea. The first spectrum auction was conducted in New Zealand for selling television (TV) spectrum bands. Since then, spectrum trading evolved into a very popular method for renting spectrum and many countries have run spectrum auctions to generate extra revenue.

Authors in [5] introduce a new optimal auction mechanism, called the generalized Branco’s mechanism (GBM). The GBM is used to rent spectrum and to determine the prices for spectrum. Spectrum market consists of selfish buyers. A noncooperative game is used to model the interaction among buyers and sellers. Authors in [6] model a spectrum market where wireless service providers (WSPs) lease chunks of spectrum on a short-term basis. WSPs compete to acquire spectrum and to attract clients for renting it. An economic framework is proposed for leasing spectrum and to specify spectrum price. A knapsack based auction model is used to allocate dynamically spectrum for WSPs such that revenue and spectrum usage are maximized.

Jia et al. [7] propose a new auction mechanism for renting underutilized spectrum. Each buyer submits its bid which consists of the number of requested channels and the price that the buyer is willing to pay. The auction mechanism is strict in that no partial allocation of request is permitted. Weighted graph is used in the proposed auction mechanism for spectrum allocation [8]. Moreover, a polynomial-time dynamic programming algorithm is designed to optimally solve the access allocation problem when the number of possible cardinalities of the set of secondary networks on a channel is upper-bounded. A low-complexity auction framework is used in [9] to distribute spectrum in real-time among a large number of wireless users with dynamic traffic. The framework consists of a highly-expressive bidding format, two pricing models, and auction clearing algorithms for spectrum allocation. In [10], a new truthful auction mechanism is proposed based on the SUs’ needs. Authors design general framework for truthful double spectrum auctions. The proposed framework takes as input any reusability-driven spectrum allocation algorithm. A novel pricing mechanism is used to achieve truthfulness and other economic properties while significantly improving spectrum utilization. Spectrum auction with multiple auctioneers (PUs) and multiple bidders (SUs) is studied in [11]. A new mechanism called MAP, a Multiauctioneer Progressive auction mechanism, is proposed where each PU gradually raises the spectrum price and each SU subsequently selects one PU for bidding. The mechanism converges to an equilibrium state after several bidding rounds where no PU and SU would like to change their decision. In [12], spectrum sharing among users is studied using auction mechanisms. The utility function for each user is defined as the received signal-to-interference ratio. Auction mechanism is used for allocating the signal power for each SU. The users are charged for the received signal-to-interference plus ratio (SINR).

Authors in [13] propose new auction mechanism for trading the spectrum. The proposed auction mechanism considers the exclusive use of spectrum while sharing it. It supports sharing alongside quality-of-service protections. The problem of spectrum trading is formulated based on bandwidth auction in [14]. Each SU makes a bid for the amount of spectrum and each PU rents the free spectrum according to the SUs’ bids. A noncooperative game is used for modeling the auction. The auction problem is solved by finding the Nash equilibrium (NE). A single-PU network is considered to investigate the existence and uniqueness of the NE. In [15], a novel auction-based algorithm is proposed to allow users to fairly compete for a wireless fading channel. The second-price auction mechanism is used for modeling the auction where each user bids for the channel, during each time-slot, based on the fade state of the channel. The user who makes the higher bid wins and it can access the spectrum by paying the second highest bid. The authors show existence of the Nash equilibrium strategy which leads to a unique allocation under certain common channel distribution.

Authors in [16] introduce a new auction-based mechanism for nearly consistent reservation of the resources of a UMTS (or GPRS) network. Generalized Vickrey Auctions is used and a set of predefined user utility functions are proposed. Each user selects one of the utility functions and submits its bid for the spectrum owner.

Two auction mechanisms are proposed in [17]: the SNR auction, and the power auction. These mechanisms determine relay selection and relay power allocation in a distributed fashion. The existence and uniqueness of the Nash Equilibrium are proved for a single-relay network. Moreover, authors extend the model to networks with multiple relays, and the existence of the Nash Equilibrium is shown under appropriate conditions. Authors in [18] consider the risk of imperfect spectrum sensing which causes the SUs miss the presence of PUs and interfere with them. To tackle this problem, a multi-unit sealed-bid auction is proposed. The main concern of the proposed scheme is to optimize the payoff of each SU. An expression for the total revenue for PU is derived. A parallel repeated auction scheme is proposed in [19] for spectrum trading. A novel bid scheme is developed to balance the system utility and allocation fairness. Each SU decides whether or not to participate in spectrum auction based one limited entry budget. SU compares the possible bid with access threshold and then decides the bidding price.

The problem of multimedia streaming over CR networks is tackled in [20]. Spectrum market consists of one PU and multiple SUs. The uniquely scalable and delay-sensitive characteristics of multimedia data and the resulting impact on users’ viewing experiences of multimedia content are integrated in the utility function. Spectrum renting is formulated as an auction game. Authors propose three distributed auction-based schemes, which are spectrum allocation using Single object pay-as-bid Ascending Clock Auction (ACA-S), spectrum allocation using Traditional Ascending Clock Auction (ACA-T), and spectrum allocation using Alternative Ascending Clock Auction (ACA-A). In [21], authors propose a repeated spectrum sharing game with cheat-proof strategies. The punishment-based repeated game is used to enforce users to share the spectrum in a cooperative way; and through mechanism-design-based and statistics-based approaches, user honesty is further enforced. The collusion problem among selfish network users for spectrum is tackled in [22]. Selfish behavior may seriously deteriorate the efficiency of dynamic spectrum sharing. This behavior of user should be taken into consideration for efficient and robust spectrum trading. Authors model the spectrum allocation in wireless networks with multiple selfish legacy spectrum holders and unlicensed users as multi-stage dynamic games.

A pricing-based collusion-resistant is proposed to combat user collusion. Spectrum renting problem is formulated in [23] by developing a general game-theoretic framework and by carefully identifying requirements for the coexistence of PUs and SUs in spectrum market. PUs dynamically adjust the amount of secondary interference that they are willing to tolerate in response to the demand from SUs. SUs attempt to achieve maximum possible throughput while not violating the interference threshold that is set by the PUs. PUs control spectrum price based on their requirements of quality of service (QoS). Authors proof the existence and uniqueness of Nash equilibrium. A new mechanism is proposed in [24] to encourage PUs to lease their free spectrum for SUs. SUs submit their bids indicating how much power they are willing to spend for relaying the primary signals to their destinations. The PUs achieve power savings due to asymmetric cooperation.

In [25], authors propose and analyze an implementation of a framework for spectrum leasing, whereby a primary link has the possibility to lease the free spectrum to an ad hoc network of SUs in exchange for cooperation in the form of distributed space–time coding. The PU attempts to maximize its QoS in terms of either rate or probability of outage, accounting for the possible contribution from cooperation. On the other hand, SUs compete among themselves for spectrum. The problem is modeled using the framework of Stackelberg games. New cooperative communication-aware spectrum leasing framework is proposed in [33] for spectrum leasing. The PU selects SUs as cooperative relays to help for transmitting information. SUs have the right to decide their bids. Spectrum allocation problem is formulated as a Nash bargaining game to avoid the ineffective solution obtained by Stackelberg game. The Nash Bargaining Solution (NBS) is used to fairly and efficiently lease the spectrum. Authors in [34] consider a three-layered spectrum trading market. This market consists of the spectrum holder, the spectrum owners and the SUs. Authors jointly study the strategies for the three parties. The PU (spectrum holder) determines the auction scheme and size of spectrum to optimize its revenue. A novel auction mechanism is proposed to enable dynamic supplies and demands in the auction. The problem of online spectrum auction is tackled in [35]. SUs bid for spectrum at any time when they need spectrum. Authors in [36] propose a Truthful double Auction mechanism for HEterogeneous Spectrum, called TAHES. TAHES allows buyers to explicitly express their personalized preferences for heterogeneous spectrums and also addresses the problem of interference graph variation. Authors show that TAHES has nice economic properties such as truthfulness, individual rationality and budget balance. In [37], authors develop a novel truthful double auction scheme to enable spectrum owner to sell to free spectrum for SUs. First double auction is designed for spectrum allocation. The scheme explicitly decouples the buyer side and seller side auction design while achieving: truthfulness, individual rationality, and budget balance. To avoid interference and support spectrum reuse, the conflict graph is used so that buyers with strong direct and indirect interference are put into the same subgraph and buyers with no or weak interference are put into separate subgraphs and finally spectrum price is computed independently within each subgraph. A merge scheme is proposed to combine spectrum allocation results from all subgraphs. An auction approach is proposed in [38] to enhance spectrum utilization. The proposed scheme leverages dynamic spectrum access techniques to allocate spectrum in a secondary market. In this market, spectrum is shared among some bidders while respecting the needs of others for exclusive use. SATYA (Sanskrit for “truth”) is developed to enable scalable spectrum auction algorithm. SUs’ optimal bid strategies are derived in [39]. These strategies maximize the profits of SUs. Authors relax the limitation of SU’s value on spectrum band and they introduce the affiliated value which considers the impacts from other SUs. In [40], authors propose a new market-based channel allocation scheme. The main objective of this scheme is to maximize the winning SUs’ service satisfaction degree while enhancing the utilities of winning PUs and SUs.

However most of these schemes neglects spectrum trading over time. The entire spectrum may be rented without considering the future demand of spectrum. Moreover, the whole future requests may be rejected since there is no longer available spectrum. These requests should wait until the spectrum is terminated by SUs. Our scheme allows the PU to optimally reserve some available spectrum for future high-bid requests while rejecting current low requests.

4 Optimal Auction Design for Spectrum Trading

Each SU has maximum cash that can bid. Assume B i is the budget for ith SU. The budget constraint is expressed as follows:

$$ b_{i} \le B_{i} $$
(2)

where b i is the ith SU bid. The reservation value v i is the maximum bidding price for ith SU. Each ith SU wishes to access s j channels. Each ith SU submits its bid R i (b i ,d i , r t ) where d i is number of the requested channels, and r t is the rental period.

The PU carries out the auction at the beginning of each session and it selects the winners based on the bids. After deciding the winners, the charged prices are fixed for all SUs until the next session. SUs’ request is either rejected or served and no partial fulfillment is accepted. Let p i is the charged price for ith SU. The utility for ith SU is defined by:

$$ u_{i} = \left\{ {\begin{array}{*{20}l} {\sum\limits_{i = 1}^{{d_{i} }} {\left( {v_{i} - p_{i} } \right)} \mu ,} \hfill & {i \in W} \hfill \\ {0,} \hfill & {O.W} \hfill \\ \end{array} } \right\} $$
(3)

where W is the set of the winners. For the losers, the charged price and the utility are zero. There are two major reasons for selecting this utility function. First, since the function is concave, it is able to model the saturation of SUs satisfaction as the reservation price (v i ) increases. Second, the adjustable parameters v i and p i provide flexibility to model different types of SUs behaviors. Each SU attempts to find the optimal bid v i that maximizes the SU utility.

We assume the PU may predict the spectrum demand in the near future. The PU knows the distribution of d i , and the number of SUs at time t where t ≤ t + ∆, where Δ is the prediction window. For the jth PU, the maximum net revenue from t to t + ∆ using auction policy π is computed as follows:

$$ V_{j}^{*} \left( \pi \right) = \mathop \sum \limits_{i \in W}^{|W|} p_{i} \mu - C $$
(4)

where C is the cost of renting the spectrum. The total revenue for the jth PU is computed as follows:

$$ R_{j} (\pi ) = \mathop {\lim }\limits_{M \to \infty } \mathop \sum \limits_{t = 1}^{M} V_{j}^{*} \left( \pi \right) $$
(5)

where M is the time horizon. The auction problem can be formulated as follows:

$$ \max_{\pi } \;\mathop \sum \limits_{t = 1}^{M} V_{j}^{*} \left( \pi \right) $$
(6)

subject to

$$ \begin{aligned} \sum _{i \in W} d_{i} \le & K, \\ b_{i} \le & B_{i} , \\ \end{aligned} $$

where K is the size of spectrum allocated to accommodate SUs’ demand for spectrum. Policy π should have some salient economic properties especially truthfulness. Each bidder should submit the true reservation value and the number of required channels regardless of others SUs’ bids. Truthfulness provides accurate information for the PU where it can predicate the future spectrum demand. Furthermore, truthfulness eliminates the users’ behaviors that may harm the PUs’ revenue. For discrete settings, the service time follows geometric distribution and its probability is computed as follows:

$$ P\left( {\mu = t} \right) = f(1 - f)^{t - 1} $$
(7)

where f is the probability that SU request which is served currently will be terminated in the next auction session. This exponential usage pattern captures some reality of wireless applications such as phone call traffic [22–24]. We assume Q t is the requested spectrum at time t. Let S t is the spectrum size allocated to meet the current spectrum demand at time t. Assume the PU has S channels for serving SUs. Suppose SUs release x channels at time t. Then the available spectrum at time t + 1 is computed as follows:

$$ A_{t + 1} = S - S_{t} + x $$
(8)

Since each request has a probability f to be served in the next session. Assume x follows binomial distribution, \( x \sim B ( A_{t + 1} , f) \), where \( B ( A_{t + 1} , f) \) is computed as follows:

$$ B \left( { A_{t + 1} ,x, f} \right) = \left( {\begin{array}{*{20}c} { A_{t + 1} } \\ x \\ \end{array} } \right)f^{x} (1 - f)^{{ A_{t + 1} - x}} $$
(9)

Lemma 1

Let Z(x) be decreasing and concave function. Assume the function \( L( A_{t + 1} ) \) is defined as follows:

$$ L\left( { A_{t + 1} } \right) = \mathop \sum \limits_{x = 0}^{{ A_{t} }} B \left( { A_{t} ,x, f} \right)Z(x) $$
(10)

The function \( L\left( { A_{t + 1} } \right) \) is decreasing and concave.

Proof

Assume L(0) = 0. Using (9), we obtain:

$$ \frac{1}{f}\nabla L\left( { A_{t} } \right) = \mathop \sum \limits_{x = 0}^{{ A_{t} }} B\left( { A_{t} ,x, f} \right)\nabla Z(x) $$
(11)

and

$$ \mathop \sum \limits_{x = 0}^{{ A_{t} }} B \left( { A_{t} ,x, f} \right)\nabla Z(x) \le 0 $$
(12)

Therefore, we conclude that \( L\left( { A_{t + 1} } \right) \) is decreasing and concave.

Lemma 2

Let \( Z_{i} \left( { A_{i - 1} - x} \right) \) be function that is increasing and concave for each \( i, Z_{i} \ge 0 \) . Assume the function Z(x) is defined as follows:

$$ Z\left( { A_{t + 1} } \right) = \mathop {\hbox{max} }\limits_{{x = 1,2, \ldots ., A_{t} }} \{ Z_{0} \left( { A_{0} } \right) + Z_{1} \left( { A_{0} - x} \right) + \cdots + Z( A_{t + 1} - x)\} $$
(13)

The function \( Z\left( { A_{t + 1} } \right) \) is concave and increasing.

Proof

Consider any \( A_{i - 1} ,x \in K \) and λ ∈ (0, 1). For each Z i concave, we have the following:

$$ Z_{i} ( \lambda A_{i - 1} - (1 - \lambda )x) \ge \lambda Z_{i} ( A_{i - 1} ) - (1 - \lambda ) Z_{i} (x) $$
(14)

Therefore,

$$ Z\left( { \lambda A_{t + 1} + \left( {1 - \lambda } \right)x} \right) = \mathop \sum \limits_{i = 0}^{t + 1} Z_{i} \left( {\lambda A_{i - 1} - \left( {1 - \lambda } \right)x} \right) \ge \mathop \sum \limits_{i = 0}^{t + 1} \lambda Z_{i} ( A_{i - 1} ) - (1 - \lambda ) Z_{i} (x) $$
(15)
$$ Z\left( { \lambda A_{t + 1} + \left( {1 - \lambda } \right)x} \right) = \lambda \mathop \sum \limits_{i = 0}^{t + 1} Z_{i} \left( { A_{i - 1} } \right) - \left( {1 - \lambda } \right)\mathop \sum \limits_{i = 0}^{t + 1} Z_{i} \left( x \right) \equiv \lambda Z_{i} \left( { A_{i - 1} } \right) + (1 - \lambda )Z_{i} \left( x \right) $$
(16)

Since both \( Z_{i} \left( { A_{i - 1} } \right) \) and \( Z_{i} \left( x \right) \) are increasing and concave, we conclude that \( Z\left( { A_{t + 1} } \right) \) is concave.

5 Maximizing the PUs Revenue Using Optimal Auction Mechanism

Truthful auction generates the maximum revenue among all auction [30, 31]. The total revenue for the jth PU is computed as follows:

$$ \begin{aligned} R_{j} \left( \pi \right) = & \,\mathop {\lim }\limits_{M \to \infty } \mathop \sum \limits_{t = 1}^{M} \mathop \sum \limits_{i \in W}^{\left| W \right|} p_{i} \mu {-}C \\ = & \,\frac{1}{f}\mathop {\lim }\limits_{M \to \infty } \mathop \sum \limits_{t = 1}^{M} \mathop \sum \limits_{i \in W}^{\left| W \right|} p_{i} - C \\ \end{aligned} $$
(17)

Partial fulfillment for SU’s request is not allowed in our system. Hence, the revenue for truthful auction is computed as follows:

$$ T_{r} \left( \pi \right) = \mathop \sum \limits_{i \in W} d_{i} \varphi \left( {b_{i} } \right)\delta_{i} (d_{i} ,b_{i} ) $$
(18)

where φ(b i ) is virtual valuation which is computed as follows [30]:

$$ \varphi \left( {b_{i} } \right) = b_{i} - \frac{{1 - Y(b_{i} )}}{{y(b_{i} )}} $$
(19)

The true value is private information for the SU. b i is drawn from the distribution Y. y is computed as follows [7]:

$$ y = \frac{d}{db}Y(b_{i} ) $$
(20)

δ i (d i , b i ) takes the value 0 or 1 depending on whether SU wins the auction or loses it. We assume Y(b i ) satisfy the monotone hazard rate assumption. With this assumption, φ(b i ) (virtual valuation function) is a monotone non-decreasing function. The auction mechanism associates the SUs who offer high reservation price with high valuation distribution and the SUs with low reservation price are associated with low valuation distribution.

Lemma 3

The virtual valuation function is monotonic increasing if the SU increases its bid on the request. Moreover, the utility function for the SU is monotonic increasing.

The expected revenue of the auction policy depends on the winners. Hence, the auction mechanism should select the winners who pay more. The problem of maximizing the PUs’ revenue can expressed as follows:

$$ \max_{{\delta_{i} (d_{i} ,b_{i} )}} \;\sum _{i \in W} \delta_{i} \left( {d_{i} , b_{i} } \right)d_{i} \varphi \left( {b_{i} } \right) $$
(21)

subject to

$$ \begin{aligned} \sum _{i \in W} d_{i} \le & S_{t} , \\ b_{i} \le & B_{i} , \\ \end{aligned} $$

At time t, the instantaneous revenue is computed as follows:

$$ V_{t} = \mathop \sum \limits_{i \in W} \delta_{i}^{*} d_{i} \varphi \left( {b_{i} } \right) $$
(22)

where δ * i solves the problem in (5). The problem of maximizing the jth PU revenue’s is formulated as follows:

$$ V_{j}^{*} \left( \pi \right) = \max_{{0 \le S_{t} \le Q_{t} }} \;\frac{1}{f}V_{t} (Q_{t} ) + V_{t + 1} \;\left( {Q_{t} - S_{t} } \right) $$
(23)

Unfortunately, solving (23) requires solving the problem in (22). The problem in (22) is NP-Hard. We use linear programming to find approximate value of \( \overline{V}_{t} (Q_{t} ) \). The value of \( \overline{V}_{t} (Q_{t} ) \) is calculated as follows. The PU sorts all bids in decreasing order, i.e. b 1 ≥ b 2… ≥ b n . The PU serves requests in the list from the highest bid (bidder 1) until all the spectrum is allocated. The PU needs to solve the following problem:

$$ \bar{V}_{t} (Q_{t} ) = \max_{{0 \le S_{t} \le Q_{t} }} \frac{1}{f}\bar{V}_{t} (Q_{t} ) + \bar{V}_{t + 1} \;\left( {Q_{t} - S_{t} } \right) $$
(24)

The boundary conditions are \( \overline{V}_{M + 1} \left( x \right) = 0 \) for all x = 1,2,3,…,Q t .

Theorem 1

\( \overline{V}_{t} (Q_{t} ) \) is increasing and concave for a given b i , d i , i.e. \( \nabla \overline{V}_{t} (Q_{t} ) = \overline{V}_{t} (Q_{t} ) - \overline{V}_{t - 1} (Q_{t - 1} ) \).

Proof

Since both \( \overline{V}_{t} (Q_{t} ) \), and \( \overline{V}_{t + 1} (Q_{t} - S_{t} ) \) are concave, applying Lemma 2 to Theorem (1) leads to the statement.

Lemma 4

For each b, d the optimal spectrum size that are rented for SUs is computed as follows:

$$ Q_{t} (d) = \left\{ {\begin{array}{*{20}l} {\max_{0 \le d \le K} } \hfill & {\left\{ {d:\frac{1}{f}\nabla \bar{V}_{t} (d) > \nabla \bar{V}_{t + 1} \left( {Q_{t} - d} \right)} \right\},\,\,if \frac{1}{f}\nabla \bar{V}_{t} (1) > \nabla \bar{V}_{t + 1} (d)} \hfill \\ {0,} \hfill & {o.w} \hfill \\ \end{array} } \right.. $$
(25)

Proof

Let the spectrum is allocated one by one. The marginal profit increases by \( \frac{1}{f}\nabla \overline{V}_{t} \left( d \right) \). However, the PU suffers gain loss of \( \nabla \overline{V}_{t + 1} \left( {Q_{t} - d} \right) \) since the rented spectrum at time t (d) will be temporarily unavailable for serving the new spectrum requests at time t + 1. Because of the concavity of \( \overline{V}_{t} (Q_{t} ) \) (Theorem 1), as more spectrum is rented for SUs, the profit of the PU decreases while the opportunity cost of renting spectrum (\( \nabla \overline{V}_{t + 1} \left( {Q_{t} - d} \right) \)) decreases. Hence, the PU should stop renting more spectrum before the opportunity cost of renting spectrum exceeds the instantaneous revenue.

Assume there are N bidders. The PU selects the top W bidders subject to the capacity condition that is expressed as follows:

$$ \mathop \sum \limits_{i = 1}^{W} d_{i} \le Q_{t + 1} $$
(26)

ith SU wins if:

  1. (1)

    it is among the top W where bi > b w+1.

  2. (2)

    The rented spectrum is sufficient to accommodate all the accepted requests.

Lemma 5

The bidding price is monotone function. If the ith SU wins by bidding b i then it wins by bidding b * i where b * i  > b i . However, the ith SU loses if b * i  > b w .

Auction mechanism is truthful if and only if the bid is monotonic and the PU selects the highest bids.

Proposition 1

The expected revenue for the jth PU \( \overline{V}_{t} \to V_{j}^{*} \) is optimal if the SUs number \( N \to \infty \) and \( K \to \infty \).

Theorem 2

Average revenue for jth PU is sensitive to the charged spectrum price p i and this sensitivity can be calculated as follows:

$$ \frac{{\partial \overline{R}_{j} }}{{\partial p_{i} }} = E\left[ {g_{j} (t)} \right] $$
(27)

Proof

the net gain for jth PU at time t can be expressed as follows:

$$ g_{j} \left( t \right) = g_{j} \left( {t - 1} \right) + \varDelta_{i} $$
(28)

where Δ i denotes the new state of the system after accepting the i requests. The right-hand side of Eq. (27) can be written as [32]:

$$ \frac{{\partial \overline{R}_{j} }}{{\partial p_{i} }} = \mathop {\lim }\limits_{H \to \infty } E\left[ {\mathop \smallint \limits_{{t_{0} - M}}^{{t_{0} + M}} \left( {R_{j} \left( {t + 1} \right) - R_{j} \left( t \right)} \right)dt} \right] $$
(29)

where R j (t + 1) denotes the revenue rate after serving Δ i at time t. By using Eq. (28) it can be shown that (29) is equivalent to:

$$ \frac{{\partial \overline{R}_{j} }}{{\partial p_{i} }} \; = E\left[ {g_{j} \left( t \right)} \right] $$
(30)

Analogous proof holds if one request is served. This analysis is helpful for a PU to decide if a request is to be admitted or rejected based on the sensitivity of the net gain to the bidding price.

6 Performance Evaluation

In this section, we conduct simulation experiments to evaluate the performance of the proposed auction scheme. Our simulation is developed using MATLAB. First, we set up a random graph by creating |N| = 100 SUs in [1000 m, 1000 m] area. We set the radio range to 200 m and the interference range to 500 m. There are 10 different PUs coexist geographically. The status of a PU channel is determined according to the ON/OFF channel model. Our simulations are averaged over 1000 runs, each last for 500 s.

For comparison purpose, the greedy auction scheme is also simulated. For the greedy policy, spectrum renting is asynchronous where SUs send their requests at any time and PUs start renting spectrum upon receiving these requests without waiting other SUs. If more than one SUs submit their requests at the same time, the PU checks the available spectrum to see if all the requests can be served. If they can be served, the spectrum is rented. However, if all the requests cannot be granted, then the PU selects the requests that offer the highest prices regardless of future requests. Each SU should specify the rental duration for the PU with the price and the required size of spectrum.

6.1 Impact of Spectrum Demand on the Revenue

In this section, we study the impact of the spectrum demand on PUs’ revenue for both schemes: greedy, and our proposed scheme (i.e. capacity-aware scheme). The SUs traffic (spectrum demand) varies over time from λ = 2 (low traffic) to λ = 10 (high traffic). Figure 1 shows a comparison of the reported revenue under different spectrum demand for the two auction schemes. The figure depicts that, as the SUs traffic increases the PUs’ revenue increases for both schemes. This is because the chance of serving more SUs’ requests and generating more money becomes higher. For higher traffic, many SUs requests are arrived and the chance for serving more SUs and generating extra revenue is increased. It is clear from the figure the capacity-aware scheme outperforms the greedy policy for all spectrum demands.

Fig. 1
figure 1

Revenue comparison for the two schemes under different values of spectrum demand

Full size image

Capacity-aware scheme considers the future profitable requests. It gives more time for these requests to arrive. However, the reported revenue for the greedy policy is very close to our scheme for high traffic loads. For high traffic loads, the competition among SUs is high and the likelihood of client’s migration is less. Hence, both schemes serve most of the arrived requests.

We evaluate the proposed auction scheme by comparing its reported revenue against greedy scheme over time. From Fig. 2, we notice that the reported revenue for both schemes is observed to be linearly increasing over time. The revenue is increased as the traffic load increases in the spectrum market. As time elapses, our scheme outperforms greedy scheme. The justification is that our scheme gives more time for the highest bids to arrive. However, greedy scheme serves the current requests without considering the dynamic nature of the spectrum demand. For high demand, the likelihood of serving more requests increases. Therefore, the greedy scheme performs very close to our proposed scheme for high demand. For high spectrum demand, SUs have not choice to switch for others PUs because they are busy with serving their clients.

Fig. 2
figure 2

Revenue comparison for the two schemes over time

Full size image

6.2 Impact of Spectrum Size on the Revenue for the PU

In this section, we study the impact of the spectrum size on the PUs’ revenue. We also examine what happens when several PUs adopt greedy scheme for auction; there are no theoretical guarantees that this strategy would outperform our strategy. We simulate spectrum market where different sizes of spectrum are offered for SUs. Figure 3 shows that the reported revenue of our scheme is greater than the revenue of the greedy scheme for all sizes. Our scheme serves the requests that give more reward over time. Furthermore, the figure depicts that, as the SUs demand for spectrum increases, the PUs’ revenue increases due to the competition among SUs for the spectrum. For high demand, the likelihood of offering lower price and find a PU who accept to rent its spectrum with this price becomes lower.

Fig. 3
figure 3

Revenue comparison for different values of spectrum size and demand

Full size image

We compare analytical results obtained by solving (23) with simulation results. Figure 4 illustrates the results. We notice from the figure that analytical results are in good agreement with simulation results. We can see that the approximation design is almost optimal and very close to simulation results: in all cases, the revenue gap between the analytical results and simulation results is less than 5 %. Furthermore, the gap is decreasing when more spectrum is offered in the spectrum market. These results suggest that our scheme is appropriate for large spectrum market.

Fig. 4
figure 4

Comparing simulation results with analytical results

Full size image

Figure 5 shows the winning price for different arrival rates of spectrum requests. Clearly, the SUs are enforced to increase the price for high spectrum demand because of competition with other SUs. However, SUs have more freedom to offer less prices for spectrum when the demand for spectrum decreases.

Fig. 5
figure 5

Winning price for different values of spectrum demand (λ)

Full size image

For high spectrum demand, the SUs cannot keep increasing the prices forever because of the budget constraint. Clearly, if the SUs have extra cash they bid more for renting spectrum. Figure 6 shows the winning price for different values of clients’ budget. It can be observed that in any period when the SU has more cash, the winning price is increased significantly. For high cash, the likelihood of offering high price and find PU who accepts the offered price becomes high. Large values of the budget promote SUs to increase the bids. Large values of the budget model the SUs who are wealthy and they concern more for the service instead of the satisfaction level they may get from the product (spectrum).

Fig. 6
figure 6

PU’s revenues under different SUs budget

Full size image

6.3 Impact of Spectrum Size on the Bidding Prices for the SU

Although PUs generate more revenue for larger spectrum sizes, SUs bid less since they have more chances for switching to another PU who may accept low prices. Therefore, the bidding price for SU becomes more dynamic as capacity increases. Figure 7 shows the average of bidding prices for different system capacities. We notice from the figure that with the same demand level, a low capacity (spectrum size = 50) intensifies the bid competition among SUs. In this case, only those who bid very high win and have their requests served. As a result, over 80 % of the prices are higher than 20. However, this situation changes when more spectrum is offered for SUs. As supplies become more abundant, the intensity of bid competition among SUs decreases, resulting in more dynamic clearing prices (spectrum size = 150).

Fig. 7
figure 7

Average bid price for different values of spectrum size

Full size image

Our scheme does not offer the entire spectrum for SUs and this enforces the SUs to offer high bids all the time. For greedy scheme, the whole spectrum is offered and this makes supplies more abundant, the intensity of bid competition among SUs decreases. Hence, SUs offer less prices.

7 Conclusion

In this paper, we presented a general spectrum trading framework, and in particular, an auction mechanism, for trading free spectrum. The PU can rent free spectrum using this mechanism. We motivated this mechanism and present some of the design principles. How to maximize PUs’ revenue while enforcing truthful bidding, and how to offer the optimal size of spectrum at each auction session are two key challenges we addressed in this work. The optimal auction strategy of the PU is obtained under dynamic spectrum market where the spectrum demand is “uncertain.

The proposed model has two contributions to spectrum trading in the secondary spectrum market. From the application side, the main contribution is developing a spectrum pricing policy that considers different requirements such as revenue for PU, the dynamic nature of the spectrum market, and the requirements for the SUs. All basic functions are integrated and optimized into one homogenous, theoretically based model. From the modeling side, we formulate trading of free spectrum problem as a revenue maximization problem. Such a formulation allows auction scheme to optimize the trading problem. The approach presents a general framework for studying, analyzing, and optimizing other resources trading in the spectrum market. The future work includes extension of the auction model and considering the competition among PUs in the spectrum market.