Single-sided truthful auction mechanism for heterogeneous channel allocation in cognitive radio networks

Abstract

In order to alleviate imbalances in radio spectrum usage, cognitive radio (CR) is designed as a dominant solution, which constantly senses the spectrum for free bands and opportunistically utilizes those bands to improve spectrum utilization. One of the essential functionalities of this emerging technology is to efficiently allocate licensed unused channels amongst Secondary Users (SUs). With this initiative, this paper deploys an auction theoretical model to provide transparent resource allocation. Auction offers a market-based mechanism where an auctioneer (primary owner) fairly leases its free channels to desirable buyers (SUs). In this paper, we propose a single-sided sealed-bid multi-unit auction mechanism for CR networks (CRNs) which sells temporarily available heterogeneous channels amongst SUs at suitable rates. Differences in channel availability time and dynamics in spectrum opportunities decide bid collection from SUs while reducing the possibility of disruption during SUs’ transmission using the allocated channels. Multiple auction rounds with concurrent bidding allows the mechanism to make utmost use of the scarce radio resource. The proposed model derives a winner determination algorithm and a payment rule to select the winning bidders and their respective expenses. Additionally, we provide the proofs of truthfulness and individual rationality to obtain an economically robust auction. Simulation based results indicate performance improvements in the proposed model in terms of spectrum utilization, auctioneer’s revenue, utility per buyer, user satisfaction compared to a similar approach from literature.

1 Introduction

Spectrum occupancy reports from Federal Communications Commission (FCC) [1] reveal that the licensed spectrum is being sparsely utilized across time and location, which leads to under-utilization of a significant amount of spectrum. This produces temporarily unused spectrum segments called spectrum opportunities (or spectrum holes). Contrarily, extensive use of wireless devices creates spectrum scarcity over unlicensed bands which tremendously increases with the emergence of 5 G and future generation networks. According to reports [2], global mobile devices will grow to 13.1 billion by 2023, 1.4 billion of those will be 5 G capable. Massive mobile connectivity results in subsequent growth in global data traffic which requires an efficient resource allocation and congestion management technique to improve bandwidth exploitation. Hence, to overcome this threat of inadequate spectrum usage, a novel intelligent wireless communication technology called cognitive radio (CR) [3, 4] is introduced which enables opportunistic access to temporarily available licensed bands. CR enabled users are called Secondary Users (SUs). SUs can dynamically utilize the free channels of licensed users or Primary Users (PUs) provided that there is no interference in PU’s communication.

Spectrum sensing in CR determines idle channels in terms of PU activity. Further, in order to utilize those free channels efficiently, a basic requirement of CR systems is to share the available spectrum amongst SUs in a well-planned manner [5]. Different allocation models are designed to attain an effective resource allocation in CRN which include, graph theory, game theory, auction theory, fuzzy logic etc [6,7,8]. In this paper, we incorporate auction theoretic modeling approach to develop a spectrum allocation model with transparent behavior amongst bidders. Auction as an allocation model sells goods (resources) to relevant bidders in return of a monetary profit [9]. It guarantees every player an equal opportunity to win with sealed-bids submitted privately to the auctioneer. Communication within an auction model involves minimum interaction between its users since they submit only their bids/asks for the auctioned goods. Conventional auctions are being organized worldwide by government agencies to sell licensed spectrum to wireless service providers (WSPs), where these auctions aim at revenue maximization [10, 11]. However, a well designed auction model in CR primarily intends to improve the use of free channels, and along with there is an assurance of earning at least a minimal pay for auctioneer and sellers. Researchers have already explored auction-based methods for spectrum allocation in CRNs, but there are certain CR constraints which on debarring from an allocation model can adversely affect the network performance. Two major practical CR constraints are, dynamics in Spectrum OPportunities (SOPs) and differences in availability time of free channels. Ignoring these constraints during channel allocation can interrupt the transmission process of SUs. Moreover, the literature study explores several double-sided auction mechanisms designed for resource sharing in CRN, where PUs as sellers offer ask values to decide winners. But, these double auctions provide reduced spectrum usage when auctioned channels remain unsold on not satisfying the winning allocation condition. Therefore, in this research proposal we introduce single-sided auction which increases spectrum use, but earns less revenue. Single-sided auction applies multi-party auction where multiple bidders can participate to get hold of the auctioned items. There is no participation of sellers in single-sided auction, only bidders and the auctioneer take part, where based on bidders’ bid values auctioneer decides the winners. In this type of auction, all auctioned items are guaranteed to be sold out when sufficient number of bidders exist. Single-sided auction is more advantageous and suitable for CR environment, because this network looks for improved performance of unlicensed users by providing opportunistic access to free licensed bands. Furthermore, an auction-based spectrum allocation considers that the PUs themselves hand over their free channels dynamically to SUs for better usefulness. Application of auction for resource allocation in CR can be enabled in 5 G networks [12] to impart flexibility in spectrum usage and permit operators to participate without communicating with each other. Monetary bid values are not suitable when auction is designed essentially to improve spectrum utilization in CRNs. When monetary amounts are used for bidding, it is not always necessary that the bidder with the highest bid value who wins the auction makes the best use of the assigned channel. Instead, if bids are submitted in terms of channel characteristic, such as bandwidth, data rate, etc., a better use of the spectrum bands can be achieved. Hence, to address the concerns identified in existing models, a suitable auction mechanism has to be designed for better spectrum usage.

1.1 Motivation

Cognitive radio system designed with cognitive capability and reconfigurability features is a promising solution to address both spectrum scarcity and spectrum under-utilization problems in radio spectrum by enabling opportunistic access to the spectrum holes by secondary users. Spectrum sharing is a key functionality of CR which should fairly redistribute the free channels amongst SUs to maximize spectrum utilization. Amongst different collaborative spectrum sharing approaches, auction is a market-based approach where SUs get their desired spectrum in return of revenue earned by primary owners on selling their free but otherwise unused channels. Auction applied in CRNs must be different from traditional auction due to intrinsic features of CR environment. Therefore, this work puts efforts to investigate the limitations in existing auction-based spectrum allocation schemes, and develop a truthful auction mechanism for heterogeneous channels applying Single-Channel Single-Winner (SCSW) allocation to improve spectrum efficiency while addressing those limitations. By virtue of importance of spectrum efficiency, we employ single-sided auction with multiple auction rounds in this work.

1.2 Contribution

In this paper, we propose a sealed-bid single-sided multi-unit auction mechanism to lease the free licensed channels amongst SUs. Sealed-bid auction communicates bids privately to the auctioneer. Single-sided auction allows submission of either bids or asks from buyers or sellers respectively. Multi-unit auction takes several vacant channels which are set aside for sale. In our auction model, SUs act as players (bidders), free channels as auctioned items and primary owner (base station of primary network) as auctioneer. The major contributions of this paper are mentioned below.

• Channels are assumed to be heterogeneous with respect to their maximum allowable transmission power. Channel heterogeneity can be expressed in terms of maximum allowable power, SNR, channel bandwidth, noise variance etc. Without loss of generality, here we assume that other parameters are same for all the SUs.

• Concurrent bidding is applied for heterogeneous channels to collect bids, where SUs can show their willingness or preferences for the available channels.

• Bidding language used to define the SU’s valuation comprises of the data transfer rate to be used by the SU over the channels. This helps in assigning the channels to those SUs who can efficiently utilize these channels with high data rates.

• We incorporate the two CR constraints, namely dynamics in SOPs and differences in channel availability time, during bid submission which avoids interruption in the transmission process of SUs.

• Our model formulates multiple auction rounds to exploit leftover availability times of the assigned channels so that radio spectrum can be maximally utilized.

• Single-Channel Single-Winner allocation policy is incorporated to provide a cost and time efficient model, where one channel is assigned to at most one user at a time in one auction round, and one SU can get at most one channel during the entire auction process.

• The proposed mechanism takes bids from SUs and develops a winner determination algorithm to select the winning SUs for channel allocation. The payment rule implemented for winning SUs makes the auctioneer earn at least a minimal revenue for the sold channels.

• Proofs for the two economic properties, individual rationality and truthfulness, are included to provide robustness in the designed model.

• We evaluate the proposed model through MATLAB based simulations for different performance parameters where results are compared with the model by Khaledi et al. [13].

1.3 Organization

The paper is organized as follows. In Sect. 2, the state-of- the-art related to auction-based spectrum allocation methods are discussed. The proposed model is presented in Sect. 3 which includes the system model, auction mechanism, proofs for the economic properties and an illustrative example explaining our model. The experimental evaluation of the implemented method is discussed in Sect. 4, followed by our conclusions in Sect. 5.

2 Related work

Literature study appraises that the Dynamic Spectrum Access techniques applied to CR provides a novel platform to resolve the spectrum scarcity problem. A spectrum management method for 5 G Non-Orthogonal Multiple Access (NOMA) wireless networks is discussed in [14] where users utilize licensed and unlicensed bands simultaneously based on Quality-of-Service prerequisites. However, CR focuses on usage of unused licensed bands which can satisfy transmission needs of unlicensed users. Hence, our work in this paper studies the spectrum sharing functionality of CR and proposes a spectrum allocation scheme for CR networks. With this motivation, this section summarizes about auction-based solutions for spectrum allocation, where we mainly concentrate on the state-of-art of single-sided auction methods designed by researchers for CR networks.

Sun et al. in [15] proposed an auction mechanism to compete for wireless fading channels. Second price auction is used to allocate bandwidth to users based on monetary bid such that Nash equilibrium strategies are achieved for general channel state distribution while maximizing system throughput for homogeneous channels. Another auction model which leases its spectrum resource, bandwidth or power, via a sequential second price auction is designed by Bae et al. in [16]. Efficient allocation is obtained through an equilibrium condition which requires full knowledge about bidders strategies, items sold etc. In [17] a bandwidth auction is modeled allowing the bidders to request for their desired bandwidth, where a Nash equilibrium in terms of bids is achieved using a dynamic updating algorithm to provide fairness among secondary users. Authors in [18] developed a sealed bid auction for homogeneous channel allocation using first price auction aiming to maximize network throughput. It applies concurrent bidding to collect bids from users which are in terns of Shannon’s capacity of the channels and the number of groups within the cognitive user buffer. A spectrum allocation approach applying combinatorial auction is proposed in [19] which carries out a two-phase procedure. In first phase, primary operators and secondary users form the two vertex sets of a weighted bipartite graph where pairs of primary operator-secondary user are determined using the Kuhn-Munkres algorithm. In the second phase, spectrum allocation is improved with a local search procedure. Winning buyers apply the VCG payment rule to decide their expenses. This single-sided auction aims to maximize the social welfare in SCSW allocation. In [20], the problem of maximizing auctioneer’s revenue is modeled as a spectrum trading approach where channels are auctioned using quality-price combinations to reach a feasible contract for fair spectrum allocation. A strategy-proof auction model, SATYA, is designed in [21] for spectrum sharing amongst shared and exclusive-use bidders using bucketing and ironing techniques where the bidding language is defined using probabilistic activation patterns, interference, and different requirements to show bidder’s willingness for the channels. Sofie et al. in [22] proposed a cooperative spectrum sharing auction method which deploys a modified VCG auction to choose multiple winning bidders for a single channel constrained to interference amongst SUs. Using binary integer programming non-interfering winner sets for leased channels are chosen with the modified VCG auction where it aims to maximize auctioneer’s revenue while handling the collusion problem. Another auction model which focuses on eliminating collusive behavior of SUs is discussed by Wu et al. in [23] which allows spectrum reuse for geographically separated wireless users, and seeks to lease the free channels for monetary profits. On allowing multi-winner allocation, virtual bidders are created, and on applying the second price auction winning groups and their respective payments for the channels are determined. A sealed-bid auction for revenue generation is developed in [24] which partitions the bidding region into cells. Bid submission using the concept of virtual valuation takes bids corresponding to the cells. Authors in [24] use the VCG auction to obtain optimal solution, however a sub-optimal solution solves the revenue maximization problem in polynomial time. A multi-cast routing, channel selection, scheduling and call administration algorithm, MRCSC, is designed in [25] for CR mesh networks with SUs requesting for bandwidth and the authors adopting a collision-free mechanism allowing spectrum reuse and handling both inter-flow and intra-flow interference to schedule different multi-cast transmissions. A recall-based spectrum allocation is carried out in [26] where the auctioneer can recall channels for auction to satisfy PU spectrum demand. Single-winner allocation applies the second price auction to determine winning bidders and their payments, which is further extended to multi-winner allocation using the VCG auction. VERITUS in [27] focuses on a truthful single-sided buyer-only auction where a computationally efficient greedy algorithm assigns spectrum in polynomial time. In [28], single-channel multi-winner allocation is applied in the designed model for homogeneous channels to facilitate spectrum reuse while satisfying CR constraints. But this method executes only one auction round which can result in spectrum wastage. A sequential bidding based spectrum auction is proposed in [29] which sells homogeneous channels in a single-auction round while incorporating channel availability time constraint. Another single-sided auction mechanism deploying multiple auction rounds for leasing homogeneous channels with SCSW allocation is developed in [30] which tackles the main issues arising in CR networks. Further, the only approach for heterogeneous channel SCSW allocation is proposed by Khaledi et al. in [13] which uses a weighted bipartite graph where SUs and channels represent the two vertex sets. Winner determination applies a maximal weight matching algorithm in the bipartite graph to decide SU-channel pairs for spectrum use maximization. Payments from winners are decided using the VCG auction. However, the CR constraints are ignored in this model which adversely effects the network throughput.

2.1 Discussion

Even though a large number of auction based techniques have been introduced for spectrum allocation, most of these techniques use double-sided auction [31,32,33] to improve primary users’ monetary interest. However, deployment of single-sided action can relatively improve spectrum usage in CR networks. The literature study carried out in this section shows that the single-sided auction models developed till date are few in numbers. Moreover, except [13], all other approaches deal with homogeneous channels in their system model for SCSW allocation, although it will be more realistic if channels are considered to be heterogeneous in their quality. This motivated us to focus on an allocation approach for heterogeneous channels which can opportunistically serve increasing spectrum demand of wireless users. Also, incorporation of CR constraints and carrying out multi-round auction facilitates reduced spectrum wastage while enhancing the network performance.

3 Proposed auction mechanism

3.1 Problem statement

To develop a sealed-bid single-sided auction model for leasing heterogeneous channels to SUs by deploying single-channel single-winner allocation which maximizes spectrum utilization while reducing possibility of disruption during transmission using the allocated channels. By adopting a multi-round auction with concurrent bidding strategy where SUs can express their preferences for the channels, the model will maximize spectrum utilization. Dealing with the CR constrains during bidding will assure reduction in interruption of SUs’ transmission. Truthfulness in bidding provides a dominant strategy for an economically robust auction.

3.2 Notations and symbols used

For the remainder of this paper, the symbols and notations used are summarized in Table 1.

Table 1 Notations and Symbols used

3.3 System model

We assume a cognitive radio network with both primary and secondary users. Primary Users (PUs) allow opportunistic access to their channels to SUs using an auction model. The CRN with N number of SUs denoted by $\mathcal {N}$ = {1, 2, 3,..., N}, has the Primary Owner (PO) who is willing to lease M number of unused channels denoted by $\mathcal {M}$ = {1, 2, 3,..., M}, of PUs for gaining some profit. It is further assumed that $N > M$. Buyers do not collude with each other in this model, and SUs in the network are static with respect to their location. Applying a sealed-bid auction privately collects the bids from SUs which are revealed only to the auctioneer (PO). Channels to be auctioned are heterogeneous in nature which differ in their maximum allowable transmission power. Valuation from a bidder is channel-specific which depends on the factors including channel capacity, spectrum availability and channel availability time. An SU selects a data transfer rate as its valuation which is used by the SU for data transmission over the channel. A multi-round SCSW allocation is adopted so that more number of SUs can be enabled to satisfy their spectrum demand.

Spectrum opportunities vary amongst SUs due to which an SU should not bid for a channel which it cannot sense as available for use. We assume that the energy detection method [3, 34] assists SUs to identify free channels from the licensed spectrum. The set of available channels for each SU is obtained through spectrum sensing before the bid submission starts in the first auction round. On collecting these sets of available channels from the SUs, they are managed using a channel availability matrix, denoted by $C=\{\textit{c}_{ij}\arrowvert \textit{c}_{ij}\in \{0,1\}\}_{N\times M}$. When a channel j is available at SU i, we take $c_{ij}$ = 1. Otherwise, $c_{ij}$ = 0 and SU i cannot submit a bid for channel j in the entire auction process. Channels are heterogeneous with respect to their maximum allowable transmission power. With $\lambda _j$ denoting the maximum allowable power for channel j, no SU can transmit over the channel with a power higher than $\lambda _j$. PO announces the maximum transmission power of the channels on staring the auction process. Thereafter, Eq. (1) computes the channel capacity (Shannon’s capacity) denoted by $\theta _{ij}$, of channel j for SU i. This channel capacity for SU i remains unaltered in every auction round where this channel is auctioned.

$$\begin{aligned} \theta _{ij} = W\log _2(1+ \lambda _j \cdot \frac{P_{L(i)}}{ I_i + \sigma ^2}) \end{aligned}$$

(1)

Where, W is the channel bandwidth and $\sigma ^2$ is the noise variance. $P_{L(i)}$ is the path loss factor between SU i$'$s transmitter and the receiver and $I_i$ is the interference from primary network. Without loss of generality, we assume that W and $\sigma ^2$ are identical for all SUs.

In CRN, availability of channels vary over time due to PUs’ activity. This determines the channel availability time for every free channel. Whenever a PU returns back to its licensed channel, the SU must right away vacate the channel. This disrupts the transmission process of the SU. If availability time of the channels is known to SUs, an SU would look for a channel with which it can complete its transmission. To address this concern, we assume that the availability time of channels is estimated by SUs using an ON-OFF model [35]. A free channel is modelled as an ON-OFF source which alternates between ON (busy) and OFF (idle) periods denoted by 1 and 0. A semi Markov process is used with the two possible states. Whenever the process enters an ON/OFF state, the time until the next state transition is governed by a probability density function. The times that the channel is busy transmitting correspond to the ON state, and the times for which channel remains free to be used by the unlicensed users correspond to the OFF state. This ON-OFF model provides the channel availability times in which the channels can be used by SUs for their transmission without disturbing the PUs. Moreover, we carry out multiple rounds of auction to make utmost use of the channel availability time. Availability time of channel j in round x is represented by $T^x_{A(j)}$. In the first round, availability time of a channel j is obtained using the ON-OFF model which is set as $T^1_{A(j)}$. For the remaining rounds, we compute the leftover availability time of an allotted channel from the previous round. It is assumed that the availability time $T^x_{A(j)}$ is identical for all SUs to which channel j is available in round x. To ensure disruption free transmission, an SU bids for a channel only if channel’s availability time is more than or equal to the channel requirement time of the SU. This requirement time is the time span during which SU will use the channel for its data transmission. $T^x_{R(ij)}$ denotes the channel requirement time of channel j for SU i in round x. For computing this channel requirement time, we use the transmission time and propagation delay as given in Eq. (2).

$$\begin{aligned} T^x_{R(ij)} = \frac{PSize_{i}}{DRate^{x}_{ij}} + \frac{Dist_{i}}{PSpeed} \end{aligned}$$

(2)

Where, packet size of SU i, denoted by $PSize_{i}$ and data rate to be used by SU i over channel j in round x, denoted by $DRate^{x}_{ij}$ together compute the transmission time. Propagation speed PSpeed and distance to receiver from SU i, denoted by $Dist_{i}$ compute the propagation delay.

We use the initial channel requirement time to decide whether an SU will submit a bid value for a channel or not. For SU i, the initial channel requirement time of channel j is denoted by $\Upsilon _{(ij)}$ and computed using channel capacity given in Eq. (2). We set $DRate^{1}_{ij} = \theta _{ij}$ in the first auction round to obtain $\Upsilon _{(ij)}$. Channel capacity computed using Eq. (1) varies amongst the available channels for an SU i. Accordingly, initial channel requirement time of these channels vary for the SU. But, $\Upsilon _{(ij)}$ of channel j for SU i remains unchanged in every auction round where this channel is auctioned. This is because $\theta _{ij}$ remains same in these rounds. Therefore, we compute $\Upsilon _{(ij)}$ in the first round and use it for the remaining rounds for channel j. When channel j is auctioned in round x and SU i looks for bid submission, we compare initial channel requirement time $\Upsilon _{(ij)}$ with channel availability time $T^x_{A(j)}$. If $T^x_{A(j)} \ge \Upsilon _{(ij)}$, SU i will submit a bid for channel j. Otherwise, there is no bid from SU i for channel j in this round. This CR constraint of channel availability time ensures smooth communication for the SUs without disturbance from PUs’ activity.

Once it is decided that an SU can have a non-zero bid for a channel, we determine the SU’s valuation which is related to the data rate to be used by the SU over the channel. For the data rate $DRate^{x}_{ij}$, we take a value less than or equal to the channel capacity $\theta _{ij}$, and obtain the channel requirement time $T^x_{R(ij)}$ using Eq. (2). To select $DRate^{x}_{ij}$ as SU i’s valuation for channel j, it should satisfy the condition that $T^x_{A(j)} \ge T^x_{R(ij)}$. Otherwise, SU’s transmission may get interrupted. For channel allocation in round x, we maintain the winning bidders in an allocation matrix, $\mathcal {A}^x=\{\textit{a}^x_{ij}\arrowvert \textit{a}^x_{ij}\in \{0,1\}\}_{N\times M}$. Where $a^x_{ij}=1$ if SU i wins channel j in round x, otherwise $a^x_{ij}=0$. Furthermore, SCSW allocation condition is applied in this multi-round auction mechanism. According to this condition, an SU can get at most one channel during the entire auction process, and a channel in one auction round can be assigned to at most one user at a time. When a channel is auctioned for its leftover availability time in subsequent rounds, SUs who could not get any channel in the previous rounds, and along with satisfy the CR constraints can only bid for the channel.

Further, on complying with the concurrent bidding strategy, all free channels are auctioned simultaneously in an auction round. Valuation from SU i for channel j in round x is denoted by $v^x_{ji}$, and is computed using Eq. (3).

$$\begin{aligned} v^x_{ji} = {\left\{ \begin{array}{ll} 0 &{} {\left\{ \begin{array}{ll} \text {if} c_{ij} = 0 \\ \text {if} \sum _{z=1}^{x-1}\sum _{j=1}^{M}a^z_{ij} \ne 0\\ \text {if} \Upsilon _{(ij)} > T^x_{A(j)} \end{array}\right. }\\ \theta _{ij} &{} \quad \text {if}\, \Upsilon _{(ij)} = T^x_{A(j)}\\ 0< DRate^x_{ij}< \theta _{ij} &{} \quad \text {if}\, \Upsilon _{(ij)} < T^x_{A(j)}\\ \text {s.t. } T^x_{A(j)} \ge T^x_{R(ij)} &{} \\ \end{array}\right. } \end{aligned}$$

(3)

Using Eq. (3) we set the conditions for bid submission as follows.

• 1. When channel j is not available at SU i, there is no bid (that is, bid value of 0) from the SU for this channel in any auction round.

• 2. When in an auction round carried out before round x, SU i is assigned a channel, then this SU cannot participate in the auction process in round x or in further rounds as per the SCSW multi-round allocation condition.

• 3. When initial channel requirement time of channel j for SU i is more than the availability time of the channel in round x, SU i cannot bid for channel j. This avoids interruption during the transmission process of the SU due to PU’s return.

• 4. When initial channel requirement time and channel availability time in round x are equal, SU i submits the channel capacity $\theta _{ij}$ as the valuation for channel j. Because if SU i uses a data rate value less than the channel capacity for the channel, then channel requirement time $T^x_{R(ij)}$ computed using this data rate will exceed the channel availability time $T^x_{A(j)}$. As a result, SU may need to vacate the channel in the midway of its transmission.

• 5. When availability time of channel j is more than initial channel requirement time of the channel for SU i, we use a data rate less than the channel capacity as the valuation for this round x. However, while deciding this data rate, SU should abide by the availability time constraint stating that $T^x_{A(j)} \ge T^x_{R(ij)}$.

The valuation of the SUs are private and known only to the bidder itself. It is the bid value from the bidder which is submitted to the auctioneer. A dominant strategy for an economically robust auction is to bid truthfully. With truthful bidding, the bid value from SU i for channel j in round x is given as in Eq. (4).

$$\begin{aligned} b^x_{ji} = v^x_{ji}, \forall i \in \mathcal {N}, \forall j \in \mathcal {M} \end{aligned}$$

(4)

For channel j, bids from the SUs are collected in a bid vector denoted by $B^x_j=\{b^x_{ji}\}_{1\times N}$. $b^x_{ji} = 0 \in B^x_j$ when there is no bid from SU i for channel j in round x. Taking all M bid vectors, we form a bid matrix denoted by $\mathcal {B}^x=\{B^x_1; B^x_2;...; B^x_j;\ldots ; B^x_M\}$. When there is no bid for channel j in a round x, or channel j is not auctioned in round x, we get $\sum _{N}^{i=1} b^{x}_{ji} = 0$.

For heterogeneous channels, concurrent bidding is ideal because it allows an SU to bid for its favourable channels. Figure 1 shows an example to demonstrate how sequential and concurrent bidding strategies work with heterogeneous channels. We consider two channels, $\mathcal {M}$ = {C1, C2}, and three SUs, $\mathcal {N}$ = {S1, S2, S3}, in the CR network. On bidding sequentially, bids received for the channels are given in Fig. 1(a). S3 wins channel C1 because it has the highest bid. Then, on auctioning C2, S2 wins the channel. This gives spectrum utilization = 8.17. Further, when concurrent bidding is applied in this scenario, both channels are auctioned together for which bids received are given in Fig. 1(b). On using this strategy, S2 wins C1 and S3 wins C2 giving spectrum utilization = 9.09. From this example it is clear that S3 shows more willingness towards C2 so that its data transmission gets faster. This is not possible when sequential bidding is applied, because S3 already got a channel when C2 is auctioned. Therefore, when channels are heterogeneous, concurrent bidding is preferable for efficient allocation (Fig. 1).

Fig. 1

a, b Sequential bidding and Concurrent bidding for heterogeneous channels

once channel allocation is attained, every wining SU i makes a payment $p_i$ to the auctioneer in exchange of the assigned spectrum. For the entire auction process, we maintain a payment vector denoted by $\mathcal {P}$ = ($p_1$, $p_2$,..., $p_N$) which stores the cost incurred by each SU. $p_i=0$ if SU i loses in all auction rounds, or it does not bid for any channel during the auction process. In most of the existing works [13, 15,16,17,18,19] when there is a single bidder for a channel in the auction, auctioneer earns zero revenue on selling the channel. This effects the revenue generation for PO. To ensure at least a minimal payment from every leased channel, we use a reserve price which is set by the PO. This price is computed in each round x using the bid matrix $\mathcal {B}^x$, and is denoted by $r^x_p$ as given in Eq. (5). It is a non-zero value which is less than the minimum bid value (non-zero) available in the bid matrix. The reserve price gets updated in each auction round along with the bid matrix.

$$\begin{aligned} r^x_p \le \min \{b^x_{ji} \in \mathcal {B}^x \mid b^x_{ji} \ne 0 \} \end{aligned}$$

(5)

To obtain the utility, $u_i$, of SU i on winning channel j in round x, the difference between the valuation of the channel and price paid to PO for the channel is taken as shown in Eq. (6). However, the utility is zero for those SUs who cannot be assigned any channel during the auction.

$$\begin{aligned} u_{i} = {\left\{ \begin{array}{ll} v^x_{ji} - p_i &{}\quad \text {if} a^x_{ij} = 1 \\ 0 &{} \quad \text {otherwise} \\ \end{array}\right. } \end{aligned}$$

(6)

The proposed approach aims to improve the spectrum utilization, $\mathcal {S}_u$, which is defined as the summation of total bid values gathered from the winning SUs in each round as given in Eq. (7). $\mathcal {S}_u$ represents the total data rate obtainable to the SUs from the free channels.

$$\begin{aligned} \mathcal {S}_u =\sum _{x}\sum \limits _{j=1}^{M}\sum \limits _{i=1}^{N} \textit{a}^x_{ij}b^x_{ji} , x = \{1, 2, ....\}, b^x_{ji} \in \mathcal {B}^x, a^x_{ij} \in \mathcal {A}^x \end{aligned}$$

(7)

For an efficient channel allocation, we formulate an optimization problem to maximize spectrum utilization subject to the constraints as given in Eq. (8).

$$\begin{aligned} \begin{aligned}& \max \sum _{x}\sum \limits _{j=1}^{M}\sum \limits _{i=1}^{N} \textit{a}^x_{ij}b^x_{ji}\\&\text {subject to} \\& (i) a^x_{ij}=0 \forall x, \text {if}c_{ij}=0\\& (ii) \sum _{i=1}^{N} a^x_{ij}\le 1,\forall \textit{j} \\& (iii) \sum _{x}\sum _{j=1}^{M} a^x_{ij}\le 1,\forall \textit{i}\\& (iv) \sum _{x}\sum _{i=1}^{N} a^x_{ij}=n, 0\le n \le N,\forall \textit{j}\\& a^x_{ij}\in \{0,1\}; \textit{i}\in \mathcal {N}; \textit{j}\in \mathcal {M} , \textit{x} = \{1, 2, ....\}\\ \end{aligned} \end{aligned}$$

(8)

According to Eq. (8), (i) satisfies channel availability constraint and (ii), (iii) and (iv) satisfy SCSW multi-round allocation constraint.

3.4 Auction mechanism

Here we discuss the proposed auction mechanism which develops a winner determination algorithm to decide the winning bidders by applying SCSW allocation policy. Thereafter, a payment rule is formulated using which auctioneer earns its revenue from the traded channels. The following subsections provide a detailed discussion on the proposed mechanism consisting of three phases.

3.4.1 Winner determination

We design the winner determination algorithm (Algorithm 1) to decide winning SUs for the auctioned channels in a round. It takes the bid matrix of that round as input. Bids in the matrix are sorted in non-increasing order and vector $\widetilde{B^x}$ stores the sorted bid values. TOP($\widetilde{B^x}$) represents the largest bid value in the vector. We take the bid TOP($\widetilde{B^x}$) and check whether the channel or the SU corresponding to this bid already got an assignment. If either the channel or the SU, or both of them received an allocation, then we move to the next bid value in $\widetilde{B^x}$ and get its channel and SU checked for the allocation condition. Otherwise, the channel is assigned to the SU. This is repeated until every channel gets assigned to some SU, or every SU is checked for its bid value. Thereafter, if one or more channels remain unused, the algorithm further scans to assign those channels to some SUs to improve the utilization. If channel k remains unused, we look over whether the channel receives bids from SUs. If no bids are received, then clearly that channel cannot be utilized. Otherwise, we get the bid values of channel k sorted and store them in $\widetilde{B^x_{(k)}}$. From the non-zero bid stored in $\widetilde{B^x_{(k)}}$, we take its corresponding SU i who is assigned a channel h. Due to the reason that SU i is already allotted channel h during the allocation, it cannot get the channel k. Now, we check if channel k on assigning to SU i and channel h on assigning to some other SU (who does not have any channel) gives better utilization than the previous allocation of channel h to SU i. If better spectrum use is achieved, then we apply the updated channel allocation pattern where the previously unused channel k gets assigned.

3.4.2 Payment

Once channel allocation completes in an auction round, every winner SU i makes a payment $p_i$ to the PO. When SU i wins channel j in round x, the allowance from the SU is the highest non-zero losing bid value for the channel. However, there are conditions to choose this highest losing bid. These conditions are essential to guarantee truthfulness in the model. We take the bid, which is given away as payment by SU i, from an SU who is not assigned any channel till the end of round x. Otherwise, if such a bid is unavailable, then winning SU pays the reserve price. The payment from SU i for channel j allocated in round x is given in Eq. 9.

$$\begin{aligned} p_i = {\left\{ \begin{array}{ll} b^x_{jk} &{} \text {if}\, \quad \min \arrowvert b^x_{ji}-b^x_{jk} \arrowvert , b^x_{ji} \ge b^x_{jk}, k\ne \textit{i}, b^x_{jk}\ne 0 \\ &{} s.t. \sum _{z=1}^{x}\sum _{h=1}^{M} a^z_{kh} \ne 1 \\ r^x_p &{} \text {otherwise} \\ \end{array}\right. } \end{aligned}$$

(9)

3.4.3 New auction round

After completion of an auction round, the assigned channels may be left out with their availability times. To avoid wastage of this excess availability time of the channels, we carry out the next auction round where the leftover non-zero channel availability times can be utilized. Suppose in round x, channel j is assigned to SU i whose channel requirement time is $T^x_{R(ij)}$ for the channel. Then in the next round, that is $(x+1)$, availability time of channel j is obtained using Eq. 10.

$$\begin{aligned} T^{x+1}_{A(j)} = T^{x}_{A(j)} - T^x_{R(ij)} \end{aligned}$$

(10)

In the new round, an SU who already got a channel in one of the previous rounds will not bid for any channel. This provides most SUs in the network a chance to win the spectrum. Initial channel requirement time (computed using channel capacity) is compared with the new channel availability time, and accordingly bids are received from desired SUs. This process is repeated until there is no bid for the auctioned channels, or there is no channel to be auctioned for its availability time. No bid for the channels implies that either all the SUs got a channel in some auction round, or the SUs cannot bid due to the CR constraints.

For computing the maximum number of auction rounds that can be executed, we assume that every SU provides a non-zero bid value (not equal to channel capacity) for all the free channels. We consider that the channel requirement time of all channels are same for an SU, and also this time is same amongst all SUs. That is, in round 1, $T^1_{R(11)}=...=T^1_{R(1j)}...=...= T^1_{R(1\,M)} = T^1_{R(21)} =...= T^1_{R(2j)} =...= T^1_{R(2\,M)} =... = T^1_{R(i1)}=... = T^1_{R(ij)} =... = T^1_{R(iM)} =... = T^1_{R(N1)} =... = T^1_{R(Nj)} =... = T^1_{R(NM)}$ for all N SUs and M channels. We obtain the channel requirement time of channel j for an SU i in round 1 using the following,

$$\begin{aligned} T^1_{R(ij)} = \frac{1}{n}, \text {where}, {\textit{n}} = \{1, 2, 3, ...\} \end{aligned}$$

Further, the requirement time of a channel for an SU is same in all auction rounds where the channel is auctioned. When channel j is auctioned till round x, we have $T^1_{R(ij)}= T^2_{R(ij)}=...= T^x_{R(ij)}$ for an SU i. This is true for all SUs and all channels. Therefore, maximum number of auction rounds denoted by $\tau$ is given in Eq. 11.

$$\begin{aligned} \tau = \max (T^1_{A(j)})n \end{aligned}$$

(11)

Where, $\max (T^1_{A(j)})$ represents the maximum channel availability amongst the channels available for auction in round 1, and n is the value using which we computed $T^1_{R(ij)}$. The number of SUs participating in the auction process should be $N > \sum ^{M}_{q=1} nT^1_{A(q)}$ to provide efficient allocation.

3.4.4 Time complexity of Algorithm 1

With N number of SUs participating in the auction process and M number of free channels, the computational complexity for sorting the bid matrix is O(NMlogNM) time unit using heap sort. Then on using the while loop, in worst case we visit all the bid values from the SUs. Once a bid is selected, we are to check the allocation condition for the chosen SU and the channel, for which we execute two inner loops. So, the running time is,

$$\begin{aligned} T(N)&= \sum _{k=1}^{NM}\sum _{j=1}^{M} c + \sum _{k=1}^{NM}\sum _{i=1}^{N} c \\&= c \sum _{k=1}^{NM} (M - 1 + 1) + c \sum _{k=1}^{NM} (N - 1 + 1) \\&= cM (NM -1 + 1) + cN (NM -1 + 1) \\&= cNM (N + M) \\&= \text {O}(NM (N + M)) \\ \end{aligned}$$

Hence, the outer while loop runs for O(NM) times, and the two inner loops to check allocation condition for SU and channel run for O(M) times and O(N) times respectively. Further, with M number of channels, (M-1) channels may remain unused. This runs the second outer loop for (M-1) times, where we sort the $k^{th}$ column of the bid matrix which takes O(NlogN) time unit. Then, for every $k^{th}$ iteration, the first inner loop runs, and for every $q^{th}$ iteration, the second inner loop runs giving the running time as,

$$\begin{aligned} T(N)&= \sum _{k=1}^{M-1}\sum _{q=1}^{N}\sum _{z=1}^{N} c \\&= c \sum _{k=1}^{M-1} \textit{N}^{2} \\&= c (M-1)\textit{N}^{2} \\&= \text {O}((M-1)\textit{N}^{2}) \end{aligned}$$

Finally, on aggregating the running times we get the overall time complexity of the algorithm as,

$$\begin{aligned} T(N)&= \text {O}(\textit{NM}\text {log}{} \textit{NM}) + \text {O}(\textit{NM}(N + M)) + \text {O}((M - 1)(\textit{N}\text {log}{} \textit{N})) + \text {O}((M - 1)\textit{N}^{2}) \\&= \text {O}(\textit{NM}\text {log}{} \textit{NM} + \textit{NM}(N + M) + (M - 1)(\textit{N}\text {log}{} \textit{N} + \textit{N}^{2})) \\&= \text {O}(\textit{NM}\text {log}{} \textit{M}{} \textit{N} ^{2} + 2M\textit{N}^{2} + N\textit{M}^{2}) \\&= \text {O}( \textit{NM} \text {log} {} \textit{M}{} \textit{N} ^{2} + MN(N + M)) \end{aligned}$$

3.4.5 Time complexity of proposed mechanism

The overall computational complexity of the proposed mechanism aggregates the computational complexity of the winner determination and payment steps which completes one round auction. The computational complexity of winner determination step is obtained as O(NMlogM$\textit{N}^{2}$ + MN(N + M)). In the payment step, we look for the highest losing bid value for a channel satisfying a condition to guarantee truthfulness in the model. For this, the maximum number of iterations performed is (N - 1), where N indicates the number of SUs. Therefore, the computational complexity of payment step is O(N), and the overall computational complexity of our proposed mechanism is O(NMlogM$\textit{N}^{2}$ + MN(N + M) + N).

3.5 Auction properties

Two economic properties for robust auction mechanism are defined and theoretically proved in this section.

Definition 1

Individual rationality: Auction is individually rational if every winning bidder pays a price which is less than its valuation for the assigned channel.

Definition 2

Truthfulness: Auction is truthful if no bidder can improve its utility by submitting an untruthful bid value.

Theorem 1

Proposed auction mechanism is individually rational.

Proof

According to the payment rule given in Eq. 9, when SU i wins channel j in round x, that is, $a^x_{ij}=1$, SU i pays a price $p_i$ for channel j which is decided once channel allocation completes in round x. This payment $p_i$ is obtained from a bid value $b^x_{jk}$ which is next highest to the winning bid $b^x_{ji}$, where $b^x_{jk}$ is the bid collected from an SU k for channel j in round x. However, there is a payment condition for selecting the SU k. This SU k whose bid is taken as payment $p_i$ should not be assigned any channel till the end of auction round x as per Eq. 9. And, if there exists no SU k with a non-zero bid to satisfy the payment condition, then SU i pays the reserve price, that is $p_i=r^x_p$. As per Eq. 5, $b^x_{ji}\ge r^x_p$, which is computed using the bid matrix. Therefore, no winning SU gets charged with a price more than its bid value in any auction round, meaning $b^x_{ji} \ge \,p_i$, $\forall i$, which results in $u_i\,\ge$ 0. $\square$

Lemma 1

Given the bid vector $B^x_j$ for channel j in round x. If on bidding $b^x_{ji}$ SU i wins the auction, then SU i will also win with a bid value $b^{x'}_{ji}\,>\,b^x_{ji}$.

Proof

On submitting bid $b^x_{ji}$, SU i wins channel j in auction round x. This implies that SU i submits the highest bid for channel j on satisfying the allocation condition. Or else, there can be situations where $\exists k \in \mathcal {N}$ such that $b^x_{jk}\,\ge \,b^x_{ji}$ and still SU i wins. This is because SU k is already assigned a channel in auction round x. So, with bid $b^{x'}_{ji}\,>\,b^x_{ji}$, irrespective of whether $b^{x'}_{ji}\,\ge \,b^x_{jk}$ or $b^{x'}_{ji}\,<\,b^x_{jk}$, SU i wins the channel. This is true for every winning SU in all auction rounds. $\square$

Theorem 2

Proposed auction mechanism is truthful.

Proof

On bidding with a bid equal to true valuation $v^x_{ji}$ and with an untruthful bid $b^x_{ji}\,\ne \,v^x_{ji}$ in round x, let the utilities of SU i be represented by $u_i$ and $u'_i$ respectively. According to the truthfulness property, bidding other than the true valuation cannot improve the utility value, that is $u_i\,\ge \,u'_i$. We take two different cases, $b^x_{ji}\,>\,v^x_{ji}$ and $b^x_{ji}\,<\,v^x_{ji}$, to prove this property where the possible result sets for both cases are shown in Table 2. Each possible result set for truthful and untruthful bids are discussed. Also, our proof for truthfulness considers one auction round x, and this holds for all other rounds. (All other network conditions remain unchanged)

Case 1: $b^x_{ji}\,>\,v^x_{ji}$

• 1) SU i loses channel j by bidding with both $b^x_{ji}$ and $v^x_{ji}$ in round x. This gives the utility values as $u_i=u'_i=0$ as per Eq. 6.

• 2) SU i wins channel j by bidding with $b^x_{ji}$ and loses the channel with the true value $v^x_{ji}$. When SU i loses with bid value $v^k_{ji}$, payment $p_i=0$ and utility $u_i=0$ in round x. SU i loses with $v^x_{ji}$ when there exists some SU k such that $b^x_{jk}\,\ge \,v^x_{ji}$ and SU k wins channel j giving $a^x_{kj}=1$ (according to the winner determination algorithm). This implies that SU k is not assigned any channel till round x, so it can acquire channel j in this round. Now on bidding with $b^x_{ji}$, SU i wins channel j (as in the result set in Table 2) because $b^x_{ji}\,\ge \,b^x_{jk}$. And the bid $b^x_{jk}$ from SU k is chosen as the payment value for SU i in round x as per Eq. 9 since it satisfies the payment condition. Therefore, $p'_i=b^x_{jk}$ where $p'_i$ is the payment for untruthful bid $b^x_{ji}\,\ne \,v^x_{ji}$, and we get $u'_i\,\le$ 0 using Eq. 6.

• 3) SU i wins channel j by bidding with $v^x_{ji}$ and loses the channel with untruthful bid $b^x_{ji}$. According to Lemma 1, this consideration cannot be true since $b^x_{ji}>v^x_{ji}$.

• 4) SU i wins channel j by bidding with both $b^x_{ji}$ and $v^x_{ji}$. When SU i wins with true valuation $v^x_{ji}$, there can be two cases. In one case, $v^x_{ji}$ is the highest bid received for the channel and this makes SU i win. Another case can be that there exists an SU k with its bid $b^x_{jk}\,\ge \,v^x_{ji}$, but it cannot win because SU k is already assigned a channel (other than channel j) in round x. This makes SU i win channel j. Moreover, when SU i wins with bid $v^x_{ji}$, then it also wins with bid $b^x_{ji}>\,v^x_{ji}$ as per Lemma 1. Taking $p_i$ and $p'_i$ as the payment for $v^x_{ji}$ and $b^x_{ji}$ respectively, we get $p_i$ = $p'_i$. This payment is a bid value less than or equal to $v^x_{ji}$ satisfying the payment rule given in Eq. (9) or it is the reserve price. Hence, we get $u_i$ = $u'_i$ as per Eq. (6).

Case 2: $b^x_{ji} < v^x_{ji}$

• 1) SU i loses channel j by bidding with both $b^x_{ji}$ and $v^x_{ji}$ in round x. This gives the utility values as $u_i=u'_i=0$ as per Eq. (6).

• 2) SU i wins channel j by bidding with $b^x_{ji}$ and loses the channel with true valuation $v^x_{ji}$. According to Lemma 1, this consideration cannot be true since $v^x_{ji} > b^x_{ji}$.

• 3) SU i wins channel j by bidding with $v^x_{ji}$ and loses the channel with bid value $b^x_{ji}$. When SU i loses with bid $b^x_{ji}$, then $p'_i=0$ and $u'_i=0$. But on winning with $v^x_{ji}$, payment $p_i$ cannot be more than $v^x_{ji}$ as per Theorem 1 which therefore gives $u_i \ge$ 0.

• 4) SU i wins channel j by bidding with both $b^x_{ji}$ and $v^x_{ji}$. When SU i wins using bid value $b^x_{ji}$, then there can be a bid $b^x_{jk}$ from an SU k such that $b^x_{jk} \ge b^x_{ji}$. But SU i wins (as in the result set in Table 2) which implies that SU k is already assigned some other channel. Also, SU i wins using $v^x_{ji}$ since $v^x_{ji}\,>\,b^x_{ji}$. Furthermore, in case $b^x_{jk} \ge b^x_{ji}$, payment $p_i$ cannot be equal to $b^x_{jk}$ as per the payment condition in Eq. (9). Therefore, we get $p_i$ = $p'_i$ and $u_i=u'_i$.

Hence, this proof guarantees that no bidder can improve its utility with untruthful bid values. $\square$

Table 2 Possible result sets for truthful and untruthful bidding

3.6 Illustrative example

In this section we present an example which illustrates the proposed model. For sake of simplicity, we take 6 SUs - S1, S2, S3, S4, S5 and S6, and 3 channels - C1, C2 and C3. Channels are heterogeneous and bids for all available channels from every SU are collected at the same time. Table 3 shows the bid matrix in auction round 1. For winner determination, bids in the bid matrix are sorted in decreasing order. We take the highest bid from the sorted list of bid values, which assigns C1 to S4 with bid value 7. On taking the next highest bid, that is 7, S1 wins C3 because both the channel and the SU are unassigned. Further, we take the third highest bid value 6 from the sorted list. The allocation for this bid cannot be considered because both C1 and S1 are already assigned. Similarly, there is no allocation for the next two bids. Thereafter with the next bid value 4, S2 gets the channel C2. With this allocation all channels get assigned and this completes the allocation process in round 1. For payments from winners, S4 takes the highest losing bid for C1 which is 6. But, this bid is from an SU who is allotted a channel in round 1, thus violating our payment rule given in Eq. (9). On moving to the next highest losing bid which is from S5, S4 gets its payment. Similarly, we get the payments for other winners. Winners and their respective payments in round 1 are depicted in Table 4. Table 5 contains the bid values from the SUs when channels are auctioned in round 2 for their left over availability times. S1, S2 and S4 cannot participate in further auction rounds as per SCSW allocation, and there are no bids for C1 from the SUs in round 2. To determine the winners, we take the highest bid value 5 and allocate C3 to S5. Rest of the non-zero bids cannot provide any allocation due to the imposed allocation condition. Once all the bids are visited, channel C2 remains unused and we check for its allocation if possible. We take the highest bid for C2 which is 3 from S5. However, S5 is already assigned to C3. We take the winning bid value of S5, that is 5, and the next highest bid for C3 which is 3 from S6. With this we get the total bid value from the assignments, C2 to S5 and C3 to S6, which is is more than the winning bid 5. Therefore, we update the allocation pattern to the one given in Table 6, and the payments from both these winners is the reserve price. Further, when C2 and C3 are auctioned in round 3, no bids are received for either of the channels (Table 7) and this terminates the auction process.

Table 3 Bid matrix managing bids from SUs for channels in round 1

Table 4 Winner determination and Payment in round 1

Table 5 Bid matrix managing bids from SUs for channels in round 2

Table 6 Winner determination and Payment in round 2

Table 7 Bid matrix managing bids from SUs for channels in round 3

4 Simulation results and observations

In this section we have investigated the performance of our model and compared it with a work by Khaledi et al. [13] through MATLAB based simulations. In simulation setup, we deploy a network of size 800 m$\times$800 m with randomly distributed SUs acting as the bidders. Maximum allowable transmission power of the channels varies in the range of [0.01, 1] Watts. Bandwidth is taken as 1 KHz and noise variance as $10^{-5}$ Watts which are same for all the SUs. Path loss factor and interference from primary network are assumed to be between [2, 4] dB and [0.001, 0.0001] Watts respectively. According to Eq. (3), a non-zero bid value for channel j from SU i is selected from the uniformly distributed range [$\theta _{ij}$, 0) Kbps while abiding by the availability time constraint. Firstly, we evaluate the behaviour of the proposed model with respect to different performance metrics and compare it with the model by Khaledi et al. [13]. We consider two network setups, where in one setup, the number of SUs are varied from 20 to 60 while keeping the number of channels fixed at 8. In the other setup, number of channels are varied from 4 to 14 while keeping number of SUs fixed at 40. The model in [13] also proposed a single-sided auction for heterogeneous channels where channel allocation problem is solved using the Hungarian algorithm for maximal matching in a weighted bipartite graph. Dynamics in SOPs and channel availability time constraints are ignored there which affected the network performance in [13]. A bidder in [13] takes the channel capacity as its valuation without being concerned about the data rate that the bidder would use for its transmission. Furthermore, there was no special consideration to reduce resource wastage in the model [13]. For comparison purpose, we simulate the model in [13] by computing the channel capacity (using Eq. 1) and taking the data rate as a value less than the channel capacity. Bid values submitted to the PO are the channel capacities as in the original model. Using these bid values winning SUs are determined. But, to compute the spectrum utilization (using Eq. 7), we take the data rate used by the winning SUs over their channels. With this, we observe that an SU winning a channel with high channel capacity not necessarily uses high data rate for its transmission, which thereby reduces the spectrum usage. Moreover, the data rates used by SUs in [13] do not take into consideration the CR constraints and it executes only one auction round to sell the spectrum. Secondly, we show the significance of using channel availability time during the allocation process by using a metric called successful user ratio. This CR constraint is omitted in the model by Khaledi et al. [13] for data rate computation (which is as per the original model). Thirdly, we compare the sequential and concurrent bidding strategies to measure their efficacy when channels are heterogeneous in nature. Fourth, we compute the numerical execution time of the proposed method for large sized networks. Next, the efficiency and robustness of our method are verified through simulation study where we consider different features and network topologies. Further, our proposed single-sided auction is compared with McAfee auction [36] which is a double-sided auction with SCSW allocation. And lastly, we calculate the spectrum efficiency values for our proposed model and compare it with the model by Khaledi et al. [13]. Simulation results for all scenarios are averaged over 500 rounds. The simulation parameters taken for this study are listed in Table 8.

Table 8 Values of simulation parameters

4.1 Performance metrics

Following metrics have been used for simulation based performance analysis.

• 1. Spectrum utilization ($\mathcal {S}_u$): Total of winning bid values which represents the total data rate to be utilized, as given in Eq. (7).

• 2. Revenue ($\mathcal {R}$): Total price earned by selling the channels as given in Eq. (12).

  $$\begin{aligned} \mathcal {R} = \sum _{i=1}^{N}p_i \end{aligned}$$

  (12)

• 3. User satisfaction ($\mathcal {U}_s$): Ratio of the number of SUs winning the channels to the total number of participating SUs as given in Eq. 13.

  $$\begin{aligned} \mathcal {U}_s = \frac{\sum\nolimits _{x}\sum \nolimits _{j=1}^{M}\sum \nolimits _{i=1}^{N} \textit{a}^x_{ij}}{N} \end{aligned}$$

  (13)

• 4. Utility per Buyer ($\mathcal {U}_b$): Ratio of total utility obtained from the winning SUs to the total number of participating SUs as given in Eq. 14.

  $$\begin{aligned} \mathcal {U}_b = \frac{\sum \nolimits _{i=1}^{N}u_i}{N} \end{aligned}$$

  (14)

• 5. Successful User Ratio ($\mathcal {U}_r$): This metric shows the importance of channel availability time. It is the ratio of the number of winning SUs who can complete their data transmission without interruption from the returning PUs to the total number of winning SUs as given in Eq. (15). We compare our model with the model by Khaledi et al. in [13], where channel allocation is done without paying attention to availability time of the auctioned channels. Winning SUs transmit over the channels which are at the risk of being reclaimed by their legitimate owners. Accordingly, we compute the SUs who can successfully complete their transmission.

  $$\begin{aligned} \mathcal {U}_r = \frac{\mathop {\sum \nolimits _{x}\sum \nolimits _{i=1}^{N}\sum \nolimits _{j=1}^{M}}\limits _{T^x_{A(j)}>T^x_{R(ij))}}a^x_{ij}}{\sum _{x}\sum \limits _{j=1}^{M}\sum \limits _{i=1}^{N}a^x_{ij}} \end{aligned}$$

  (15)

Fig. 2

a–d Spectrum utilization, Revenue, User satisfaction and Utility per buyer with respect to number of SUs respectively

4.2 Changing number of SUs

Figure 2 illustrates the results obtained by simulating the proposed model and comparing with a model by Khaledi et al. [13], when we vary the number of SUs keeping the number of channels fixed at 8. From Fig. 2(a) we can observe that the spectrum utilization in our proposed model improves significantly in comparison with the model by Khaledi et al. [13]. In our model these utilization values are more than 145 Kbps for all sets of SUs, and it changes to a maximum of 203.07 Kbps for the SU set with 60 SUs. Whereas in [13], spectrum utilization ranges from 63.05 Kbps to 99.94 Kbps. On increasing the number of SUs, spectrum utilization increases in both the models because the range of bid values increases. Additionally with multiple auction rounds, more number of SUs can satisfy their spectrum demand on using our model which improves the spectrum use by reducing its wastage. However, for a particular set of SUs we occasionally get reduced utilization due to the decreasing number of participating SUs on satisfying the CR constraints for the auctioned channels. This condition can also result in lesser number of auction rounds to complete the channel allocation. Bidding language in [13] uses the channel capacity. An SU winning a channel with high channel capacity not necessarily makes the best use of its channel. The data rate used by a winner SU for its transmission can be less than an SU who could not win the channel. As a result, spectrum utilization, that is total usage of the spectrum, obtained using the data rate gets reduced. Therefore in the model by Khaledi et al. [13], even though SUs with high channel capacities win, spectrum utilization is less. Moreover, since only one auction round is carried out in [13], chances of spectrum wastage is more in this model. Similar improvement is observed in Fig. 2(b) for the auctioneer’s revenue, where our model gives better performance with the revenue values ranging from 125.90 to 179.29. When number of SU increases, we get more number of winning SUs for the auctioned channels using multiple auction rounds which improves the revenue incurred by the PO in our model. Setting a reserve price in each round assures at least a minimum non-zero income for the PO. However, when some winning SUs pay the reserve price according to our payment rule, revenue generation drops in our model. In the model by Khaledi et al. [13], revenue generated is in the range of 54.93 to 91.88. This revenue is obtained only from one auction round using the payment strategy of Vickrey Clarke Groves (VCG) auction. Furthermore, when a sole bidder bids for a channel, the payment from this bidder on winning the channel is zero in [13]. With these limitations revenue obtained in the model by Khaledi et al. [13] is reduced. The user satisfaction and utility per buyer values over varying number of SUs can be observed in Fig. 2(c) and (d) respectively. We can notice that the performance of user satisfaction ranges from 0.7 to 0.316 in our model, and from 0.4 to 0.133 in [13], giving 94% better results on an average as compared to the model by Khaledi et al. [13]. SCSW allocation policy applied with multi-round auction allows more number of SUs to satisfy their transmission demand. However, on increasing the number of SUs, satisfaction values decline in both the models because for a fixed set of channels we get a moderate increase in the number of winning SUs. Likewise, we can observe a decreasing trend when utility per buyer values are obtained. These values drastically decreases from 0.936 to 0.449 in our model, as compared to 0.406 to 0.134 in the model by Khaledi et al. [13]. Competition amongst the SUs increases when the SUs are more in numbers for a given set of channels. In the proposed model, utility values are high for the winning SUs because the payment collected is either the reserve price or it is a bid value from a losing bidder satisfying the payment condition. But in [13], pricing strategy of the VCG auction model generates the revenue which thereby reduces the utility according to Eq. (7).

Fig. 3

a–d Spectrum utilization, Revenue, User satisfaction and Utility per buyer with respect to number of Channels respectively

4.3 Changing number of channels

Figure 3 depicts how the proposed model outperforms in its performance when compared with a model by Khaledi et al. [13], by varying the number of channels and keeping the number of SUs fixed at 40. From Fig. 3(a), it can be seen that with increasing number of channels spectrum utilization increases from 76.83 Kbps to 311.20 Kbps in our model, whereas in the model by Khaledi et al. [13] it increases from 45.06 to 117.92 Kbps. Increasing number of channels for a given set of SUs increases the spectrum availability amongst the SUs which enables more number of users to fulfill their spectrum requirement. Moreover, when channels are more in numbers, number of auction rounds increases allowing more number of SUs to get their spectrum and improve the spectrum use. Although, spectrum utilization increases in [13] with increasing number of channels, but the overall utilization is comparatively less. Figure 3(b) shows a similar improvement in the revenue, where in our model revenue grows from 67.01 to 283.18, whereas it grows from 37.93 to 108.34 in [13]. When number of auctioned channels increases, number of winning SUs also increases, which thereby increases the revenue of auctioneer. In the proposed model, leftover availability time of channels are utilized by carrying out multiple auction rounds which allows more than one SU to be assigned a channel in different rounds. Offering a reserve price for payment provides a minimum non-zero revenue to the PO. Altogether, these considerations improve the auctioneer’s revenue in our model. From Fig. 3(c) we get the user satisfaction values which increases by 92% on an average in our model when compared with the model by Khaledi et al. [13]. By implementing multiple auction rounds in the proposed model, channels can be assigned to more number of SUs on increasing the channel count which enhances the satisfaction values. Lastly, utility per buyer values ranges from 0.245 to 0.700 in our model, whereas we can observe its range from 0.178 to 0.243 in the model by Khaledi et al. [13] as shown in Fig. 3(d) which is due to less competition amongst the SUs for the available channels.

4.4 Successful user ratio

Figure 4(a) and (b) discuss the significance of channel availability time constraint in the performance of an allocation mechanism in CRN. We use a metric called successful user ratio defined in Eq. 15 which returns the number of winning SUs who can successfully complete their data transmission using their assigned channels. Performance of our model is compared with the model by Khaledi et al. [13] where the constraint for channel availability time is not incorporated (as in the original model). We can notice that in Fig. 4(a) when successful user ratio is obtained by varying the number of SUs, our model outperforms the model by Khaledi et al. [13] by an average margin of 9%. This is because in [13], an SU bids for a channel without bothering about the channel’s availability time, and on winning the channel SU transmits over it. However, in situations where the licensed user owing the channel returns back, SU stops its transmission and vacates the channel thus disrupting its transmission process. In [13] an SU demands only one channel due to which SU’s transmission on PU’s return cannot complete. Therefore, this deteriorates the overall successful user ratio as well as holds back the spectrum use in [13], although in certain cases (when number of SUs is 30, 40 and 60 in the simulated scenario as shown in Fig. 4(a)), winners in [13] can successfully complete their transmission because the availability time of channels is more than the channel requirement time for those winners. On the other hand, we get an improved performance in our model because a channel is assigned to an SU only if channel requirement time of the SU is less than the availability time of the channel, which permits every winning SU to complete its transmission. Similarly, when number of channels are varied in Fig. 4(b), we obtain an average increase of 17% in successful user ratio in our model compared to the model in [13].

Fig. 4

a, b Successful user ratio with respect to number of SUs and number of Channels respectively

4.5 Concurrent and sequential bidding

Figure 5(a) and (b) compare the concurrent and sequential bidding strategies applied during bid collection in one auction round in our proposed mechanism with heterogeneous channels. Figure 5(a) shows the spectrum utilization values obtained using the two bidding strategies by varying the number of SUs, where we can observe an increase from 109.37 to 130.65 Kbps in concurrent bidding, as compared to 97.22 Kbps to 124.59 Kbps in sequential bidding. With this, we can notice that the concurrent bidding policy gives better results than sequential bidding by an average margin of 5%. Similarly, on increasing the number of channels we get an increase from 47.47 Kbps to 241.26 Kbps in spectrum utilization in concurrent bidding, as compared to 43.98 Kbps to 230.92 Kbps in sequential bidding, providing 9% better utilization values on an average on using the concurrent bidding policy as shown in Fig. 5(b).

Fig. 5

a, b Spectrum utilization in Concurrent and Sequential bidding with respect to number of SUs and number of Channels respectively

Fig. 6

Numerical execution time with respect to number of SUs

4.6 Numerical execution time

Figure 6 depicts the numerical execution times for the proposed mechanism when we vary the number of SUs as $\{20, 40, 60, 80, 100\}$ for a fixed number of channels taken as 5. These values are according to the time complexity obtained for the proposed method. From this figure we can report that even for large sized networks the running times of our model is small enough to perform significantly well for utilizing the free spectrum bands. This execution time increases with increasing number of users since the winner determination step requires more time to decide the winning buyers.

Fig. 7

a, b Execution time and Spectrum utilization with respect to number of SUs for different channel sets

4.7 Efficiency of proposed mechanism

To verify scalability of our system in terms of efficiency, we have considered execution time and spectrum utilization especially when the network size grows. For this simulation study, we take different sets of SUs varying as $\{200, 400, 600, 800, 1000\}$ and 3 sets of channels varying as $\{20, 40, 60\}$ to compute the running times and spectrum usage values. Figure 7(a) displays the execution times which changes with increasing network size (number of SUs) from 4.37 to 26.76 s for 20 channels, from 5.09 to 28.59 s for 40 channels, and from 7.68 to 31.11 s for 60 channels. Hence, even for large-sized networks our proposed method achieves good performance in less time. Similarly, spectrum utilization values with increasing number of SUs are obtained from Fig. 7(b) which shows a rise from 342.51 to 398.74 Kbps for 20 channels, from 790.86 to 889.82 Kbps for 40 channels, and from 1162.63 to 1337.24 Kbps for 60 channels. Therefore, experimental results from both these figures illustrate the efficiency of our method by achieving significant improvement in spectrum use.

4.8 Robustness of proposed mechanism

Our proposed model is robust enough to be used under different network conditions. We verify this point with respect to three different features, (i) economically robust in the market, (ii) robust to time varying channel conditions, and (iii) robust to topology changes. We individually consider these features to demonstrate robustness in our method.

For the first feature, we have already proved theoretically that our proposed scheme is economically robust in terms of two properties, namely, individual rationality and truthfulness. Here, in Figs. 8,  9(a) and (b) we show the simulation results for these two properties taking one auction round. Figure 8 illustrates the individual rationality considering 5 winner SUs, implying that there are 5 channels one channel for each SU. On applying the payment rule of our model we find that the price paid by every winner is less than its bid value as can be seen from Fig. 8 which is in accordance with the property of individual rationality. Further, to show the truthfulness of our proposed scheme, we choose one SU. In Fig. 9(a), we consider that the SU wins with a true valuation 24. When bid is equal to valuation, SU wins and makes a payment of 20 giving the utility as 4. Also, any untruthful bid above or equal to 20 wins the channel and has same utility value 4. But, untruthful bids less than 20 cannot win the channel and this gives zero utility as can be seen from Fig. 9(a). This is because the SU having bid 20 (which is the payment for our chosen SU) will win the channel with greater bid value. Similarly in Fig. 9(b), we consider that the SU loses with a true valuation 24. On bidding truthfully with bid 24 SU loses and has zero utility. Again with untruthful bid 26 SU loses as shown in Fig. 9(b), but we can observe that when it has bid 27, SU wins with utility value $-3$. This implies that there is an SU with bid 27 who was winning the channel when our SU submitted bids less than 27 and earned zero utility for losing. This 27 now becomes the payment for our SU when it wins for untruthful bids equal to or above 27 where it obtains a decreased utility of $-3$ each time. Hence, from the experimental results obtained from both Fig. 9(a) and (b) we can verify that no bidder can increase its utility by submitting untruthful bids which is in accordance with the property of truthfulness.

Fig. 8

Individual rationality of proposed method

Fig. 9

a, b Truthfulness of proposed method

For the second condition of robustness, we have already simulated the successful user ratio metric in Fig. 4 (a) and Fig. 4 (b) which explains that our method is equipped to time varying channel changes. The CR constraint for channel availability time satisfies this feature for robustness where the channels are selected considering their availability times due to which all SUs in our model can successfully complete their transmissions without disruption.

Lastly, to show the robustness during topology change, we carry out our simulation taking random, clustered, and scattered topologies to obtain the spectrum utilization values in each scenario. Random topology is the default setting where nodes are randomly distributed in the network area. In clustered topology, nodes are placed in small areas forming clusters so as to create hotspots. And in scattered topology, nodes are far apart from one another. Figure 10 shows the spectrum usage values in different topologies considering 3 sets of channels when number of SUs are fixed at 60 for one auction round. From the figure we find that the spectrum utilization is relatively same in all topologies because all SUs are equally probable of winning the channels with SCSW allocation. Hence, our experimental results considering all three features clearly depicts the robustness characteristic of the proposed model.

Fig. 10

Spectrum utilization under different network topologies with respect to three sets of Channels

Fig. 11

a, b Execution time and Spectrum utilization for single-sided auction and double-sided auction with respect to number of SUs

Fig. 12

Spectrum efficiency per user with respect to number of Channels for different sets of SUs

4.9 Single-sided and double-sided auction models

In Fig. 11(a) and (b), we compare our proposed model with McAfee auction [36] which is a double-sided auction model leasing homogeneous items. For this comparative study, number of SUs are varied from 50 to 500 keeping the number of channels fixed at 10. One auction round is applied to determine these values for both the models. We consider McAfee auction for our study because there is no double auction model in literature which works with heterogeneous channels following SCSW allocation. In McAfee auction every buyer bids for only one item since auctioned items are homogeneous, and every seller contributes only one item by setting its ask value. The McAfee design matches buyers to sellers one-by-one to determine the winners where certain items may remain unsold when the allocation condition is not met. According to the McAfee design, the time complexity obtained is (NlogN + MlogM + NM), where N denotes the number of participating SUs and M denotes the number of idle channels. Figure 11 (a) shows the running times of both the models where the McAfee auction consumes lesser time than our proposed model. This is due to the design constraints applied in McAfee which reduces the sorting times and all channels as well as users need not be explored when the allocation condition is met. But in our proposed method, we consider every auctioned channel to provide its user allocation which increases the number of iterations in our model. Also, the computational complexity increases as the number of SUs increases because the number of iterations increases. However, when we solely consider our model in terms of time complexity, we can observe that even for large sized networks our model gives results in quite less time. Figure 11(b) shows the spectrum utilization values computed for the same network scenario which reveals that our model achieves relatively high spectrum utilization compared to McAfee auction.

4.10 Spectrum efficiency

In Fig. 12 we obtain the spectrum efficiency per user for our proposed model and compare the values with model designed by Khaledi et al. [13]. Spectrum efficiency provides the amount of data transmitted over a specific bandwidth. For our simulation study, bandwidth is taken as 1 KHz which is same for all SUs. Using this bandwidth value, we calculate the spectrum efficiency values for three different sets of SUs, {40, 60, 80}, while varying the number of channels from 5 to 30 in both the models. From Fig. 12 it can be stated that our model significantly outperforms the model by Khaledi et al. [13] which implies that the free licensed spectrum can be utilized more effectively by the proposed scheme. Multi-round auction and bidding in terms of data rate ensures enhanced and effective use of the radio bands. For a set of SUs, increasing number of channels increases the spectrum availability amongst users which therefore improves the spectrum efficiency of an user. On the other hand, when number of SUs are increased for a particular set of channels, spectrum efficiency per user reduces because spectrum share for each user declines with more number of users. However, due to multi-round auction in our model, more number of SUs utilize the spectrum, with which spectrum efficiency per user varies moderately in certain cases in the model. Overall, it is found that our model boosts spectrum efficiency providing better spectrum use.

5 Conclusion

In this paper, we have proposed a concurrent bidding based single-sided auction mechanism for allocation of heterogeneous channels in CRNs. Considering heterogeneous channels for spectrum allocation model makes it more suitable for real applications. We have adopted concurrent bidding for heterogeneous channels, which enables every bidder to show its willingness or preferences for the available channels in terms of its bids. We have shown to improve spectrum utilization by computing bids in terms of data rate. SCSW multi-round auction is applied to facilitate fair distribution of free licensed channels among CR users while enabling more number of SUs to exploit the spectrum resource. By incorporating CR constraints, we have shown to reduce the chances of disturbances by returning PUs during SUs’ transmission. The winner determination algorithm and the payment rule developed have provided improved spectrum utilization with appropriate pricing for sold channels. Both truthfulness and individual rationality are shown to be guaranteed in this model to avoid any market manipulation. Simulation results have validated our design and demonstrated its efficacy compared to a model by Khaledi et. al. [13], which is the only approach in literature that applies single-sided auction for heterogeneous channels. Our future research direction will investigate the current solution considering user mobility (mobility of both PUs and SUs) to provide a more general setting in realistic mobile networks.