DAMW: Double Auction Multi-winner Framework for Spectrum Allocation in Cognitive Radio Networks

Abstract

Under-utilization of wireless spectrum by the licensed owners creates spectrum holes which can be opportunistically exploited by secondary users (SUs). By incorporating dynamic spectrum access techniques, Cognitive Radio (CR) emerges as a novel technology which facilitates redistribution of the spectrum holes dynamically. In this context, this paper proposes a double auction framework for CR networks which addresses the channel allocation problem to boost the spectrum utilization efficiency. Multi-winner allocation relates to the condition where a common channel can be utilized by multiple non-interfering SUs which induces spectrum reuse. However, a single SU obtains at most one channel. To avoid disturbances during data transmission, availability time of a channel plays a key role. In this paper, bid submission from SUs rely on channel availability time, and to lease the idle channels, licensed users specify certain ask values. The proposed double auction mechanism develops winner determination and pricing strategies which are proved to be truthful and significantly improves the usage of the radio spectrum. Network simulations validate the improved performance of the proposed auction model compared to the McAfee auction.

1 Introduction

Ongoing growth in the telecommunication sector drastically increases the demand for radio spectrum. Simultaneously on the other side, Federal Communications Commission (FCC) [1] declares that chunks of licensed spectrum distributed amongst the legitimate owners are left unused in different geographical locations as well as at different times. Hence, both the under-utilization and over-utilization problems collectively results in an inefficient utilization of the radio spectrum. To address this imbalance in the use of radio resource, a novel technology called Cognitive Radio (CR) [2, 3] was introduced which functions using the concept of dynamic spectrum access (DSA) [4, 5]. CR enables opportunistic spectrum access among the unlicensed users (or secondary users) where it initially senses for the vacant licensed bands (channels), and without causing harmful interference to the licensed users (or primary users), vacant channels are exploited dynamically. Spectrum allocation [2, 6] is a key feature in CR which designs allocation mechanisms for fair and efficient distribution of the unused channels. Different allocation models [7, 8] have been deployed with certain predefined network constraints to achieve some suitable allocation strategy. One of the familiar method for redistribution of the spectrum is to use auction as the allocation model.

Auction [9] is the process of leasing certain items by the sellers on receiving appropriate bids from the buyers. It provides a fair and effective allocation where there is an equal possibility of every bidder to win. Auction formulation for a CR network (CRN) takes the secondary users (SUs) as bidders (or buyers) who are willing to obtain the auctioned item, that is, the idle channels which remain unused by the primary users (PUs). Two different auction scenarios can be formulated, viz., single-sided auction and double-sided auction. In a single-sided auction [10,11,12], it is the auctioneer who sells the item without the participation of the sellers. As such, no financial profit is earned by the sellers of the items. But, a more practical scenario is where along with bidders, sellers also compete amongst them to sell their resources. This defines a double-sided auction where buyers submit bid values, sellers submit ask values and the auctioneer decides the clearing price based on the received bids and asks. Also, sellers take the opportunity of obtaining some monetary gain. To design a double-sided auction in CRN, PUs behave as sellers and the primary owner (primary base station) act as the auctioneer. Market manipulation is a common problem in any auction model. This requires designing of a truthful auction mechanism where utility of the bidder (or the seller) cannot improve on submitting an untruthful bid value (or ask value). This appears to be one of the challenging problems in developing the auction model. Another challenging problem can be to incorporate spectrum reusability in the model. Since spectrum is different from conventional auctioned items, so, non-interfering SUs can be allowed to simultaneously access a common channel which thereby helps to enhance the overall spectrum utilization. In CRN, whenever a PU wants to return back to its channel, the SU who has been utilizing the channel for its data transmission has to vacant the channel. Such a situation may interrupt SU’s transmission. So, there arises the need of channel availability time. If an SU gets a channel such that its channel availability time is less than the time duration for which the SU requires the channel, then transmission of the SU gets disturbed. Existing research works on double auction have not considered the channel availability time in their models. Therefore, this appears to be an important concern for future works concentrating on spectrum allocation in CRN. Another concern can be a situation where an SU cannot sense all the channels available for auction. This results in dynamics in spectrum opportunities (SOPs) in the network which needs to be tackled during channel allocation. Spectrum trading in 5G network [13] uses auction to rationalize the allocation process. 5G integrated with CR network can help to achieve higher capacity along with flexibility in its usage. Hence, motivated by these observations, this paper develops a double auction framework which facilitates multi-winner allocation.

In this paper, we propose a Double Auction Multi-Winner (DAMW) framework which achieves effective allocation of the radio spectrum in CRN. Multi-winner characteristic allows one channel to be assigned to more than one non-interfering SUs which in turn increases spectrum utilization and seller’s revenue. However, since each SU can acquire only a single channel, so availability time of the auctioned channels should be studied before deciding the valuation of the channels. In the seller side, every PU plans to lease more than one channel if available, and accordingly determines the ask values. Subsequently, SUs in the buyer side offer appropriate bid values to get hold of the channel required for their transmission. Finally, the auctioneer figures out the winner determination and pricing rules for channel allocation. DAMW proves to be truthful to both SUs and PUs and its evaluation depicts the performance improvement when compared with the general McAfee auction.

The rest of the paper is organized as follows. Section 2 carries out a brief study on double-sided auction-based approaches in CRN. Section 3 discusses the proposed DAMW model which includes the system model, the auction mechanism and the auction properties. Performance evaluation is described in Sect. 4. Finally, Sect. 5 concludes the paper.

2 Related Works

Double-sided auction has been applied by the researchers in CRN to achieve different network objectives. PUs possessing the vacant channels pursue to earn some financial profit by leasing the channels amongst SUs who are competing to get a channel. In [14], authors propose the McAfee auction which is considered to be the primary double-auction model for single-channel allocation. Zhou et al. designed TRUST in [15] which is the first truthful double auction with spectrum reuse. Every SU’s bid specifies the value for the channel and the demand showing number of channels required by the SU. On the other side, a PU auctions only a single unused channel by submitting its ask value. TRUST determines the winning buyers and sellers and the payment strategy by extending the McAfee auction. Another double auction mechanism enabling spectrum reuse is discussed in [16], where a bid-dependent algorithm results in the formation of non-conflicting buyer groups. Each PU can sell more than one channel with single-channel allocation amongst the SUs. To guarantee a strategyproof mechanism, bid-independent payment applies to both sellers and buyers. TAHES in [17] allows both buyers and sellers to compete amongst themselves by formulating a single-round multi-item double auction. In this approach, each SU is constrained to use a single channel and every PU can auction only one channel from its pool of unused channels. TAHES ensures truthfulness and enables spatial heterogeneity in the designed model. In [18], the double auction mechanism aims at profit maximization. But in CRN, we mainly concentrate on enhancing the spectrum utilization across the network. Authors in [18] allow a channel to be used by multiple users where the interference relationship between the users is modeled using Signal to Interference plus Noise Ratio (SINR) constraints. Dong et al. in [19] proposed a spectrum allocation approach where both buyer side and seller side are decoupled and winner determination is performed separately. Sub graphs are constructed in the buyer side whose results are merged and subsequently in the seller side, every seller leases a single channel. An auction model where PUs share the auctioned channels along with SUs is formulated in [20]. Using the concept of interference temperature, transmission of SUs, who are assigned a channel, is kept below a threshold value so that the PU owing the channel can use it without interfering with the SUs. Every PU auctions a single channel while incorporating spectrum reusability in the model. In [21], TAMES designed an auction mechanism which supports spectrum heterogeneity across the network. Bid-dependent buyer groups formulated in TAMES enabled spectrum reuse while achieving the economic properties for the auction model. Similarly, PreDA in [22] takes into account the SINR values to build the preference list according to which SUs submit bids for the channels auctioned by the PUs. Virtual group formation algorithm formulates spectrum reuse which allows one channel to be assigned to all members of a particular group.

Although auction-based models have been applied in many spectrum allocation problems in CRN, but they have not tackled certain network issues arising in CRN. Dynamics in SOPs and variation in availability time of the channels are two important CR network challenges. Existing double-auction models have not addressed any of the two challenge. In this paper, we restrict each SU to obtain a single channel and this necessitates every SU to obtain the availability time of the channels offered for auction. Also, due to different SU capabilities [23], the set of unused channels may differ in different SUs. DAMW encompasses the network concerns of CRN and aims to achieve an enhanced spectrum utilization efficiency in the network.

3 Double Auction for Spectrum Allocation

This section discusses the proposed DAMW mechanism by elaborately describing the system model, the double auction mechanism consisting of three different algorithms for bidder group formation, group bid computation and winner determination and the auction properties.

3.1 System Model

We consider a cognitive radio network where N number of SUs (bidders), $\mathcal {N}=\{1,2,3, ..., \textit{N}\}$, compete for the spectrum which is offered for auction by M number of PUs (sellers), $\mathcal {M}=\{1,2,3, ..., \textit{M}\}$ of the primary network. The responsibility of the auctioneer is taken by the primary owner (PO) who decides a clearing price to determine the winner SUs and PUs. Each PU can sell more than one channel left unused. As such, if $k_q$ represents the number of channels temporarily available for use from PU q, then total number of channels available for the auction process are $K_{(c)} = \sum _{q=1}^{M} k_q$. So, the set of channels, $\mathcal {K}$, can be shown as follows.

$$ \mathcal {K}= \mathop {\{\underbrace{1, ..., k_1}}\limits _{1^{st}\text { PU}}, \mathop {\underbrace{(k_1+1), ..., (k_1+k_2)}}\limits _{2^{nd}\text { PU}}, ..., \mathop {\underbrace{((k_1+ ...+k_{M-1})+1), ..., (k_1+ ...+k_M)}}\limits _{M^{th}\text { PU}} $$

We assume that $N>K_{(c)}$. Interference between two SUs arise if they are within the interference range of each other. To show interfering SUs, a conflict graph can be used where vertices are the SUs and an edge exists between two vertices if the SUs corresponding to the vertices interfere. Moreover, to represent the channel set available to an SU, a channel availability matrix, $X=\{\textit{x}_{ij} \arrowvert \textit{x}_{ij} \in \{0,1\}\}_{N\times K_{(c)}}$, is maintained. When SU i senses a channel $j\in \mathcal {K}$, then $x_{ij}=1$ implying that SU i can look to access the channel j. Otherwise, $x_{ij}=0$ if channel j is inaccessible to SU i. In this auction model, all the $K_{(c)}$ channels are considered to be homogeneous in their quality. This allows an SU to submit a similar bid value for all its available channels. Bid submission from an SU also depends on the channel availability time and channel requirement time. Taking $T_{A(j)}$ as the availability time of channel j and $T_{R(ij)}$ as the channel requirement time of SU i over channel j, SU i decides a valuation for the channel j only if $T_{A(j)}$ is greater than $T_{R(ij)}$. Every SU computes $T_{A(j)}$ during its sensing phase [24]. For a channel j, $T_{A(j)}$ is approximately same for all the SUs to which channel j is available. Thereafter, an SU i computes its $T_{R(ij)}$ for channel j by considering its transmission time and propagation delay. Now, on starting the auction, a PU decides a valuation for its idle channels. Valuation from a PU q, given as $v^{(s)}_q$, will be same for all the $k_q$ channels since they are homogeneous. To compete amongst the PUs in the network, the PU q will submit its ask value, $b^{(s)}_q$, to the auctioneer as shown in Eq. 1.

$$\begin{aligned} b^{(s)}_q = v^{(s)}_q, \forall q \in \mathcal {M} \end{aligned}$$

(1)

On receiving the ask values at PO, an ask vector, $B^{(s)}$, gets formed as follows:

$$ B^{(s)}= \{\underbrace{b^{(s)}_1, ..., b^{(s)}_1}_{k_1}, ...,\underbrace{b^{(s)}_q, ..., b^{(s)}_q}_{k_q}, ..., \underbrace{b^{(s)}_M, ..., b^{(s)}_M}_{k_M} \} $$

Correspondingly, each SU i decides a valuation, $v^{(b)}_{ji}$, for the channel $j\in \mathcal {K}$ available at the SU. And the bid submitted by SU i for channel j, $b^{(b)}_{ji}$, to the PO is shown in Eq. 2.

$$\begin{aligned} b^{(b)}_{ji} = {\left\{ \begin{array}{ll} \textit{v}^{(b)}_{ji} &{} \text {if }(x_{ij}=1) \wedge (T_{A(j)} \ge T_{R(ij)})\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(2)

This constructs a bid vector, $B^{(b)}_j$, for the channel j where $B^{(b)}_j = \{b^{(b)}_{j1}, b^{(b)}_{j2}, ..., b^{(b)}_{jN} \}$. Similarly, for all available channels, we get $B^{(b)}_1$, $B^{(b)}_2$, ..., $B^{(b)}_{K_{(c)}}$. Once the bids and asks are collected at the PO, it executes its winner determination strategy to find the winning SUs and PUs. Thereafter, the pricing strategy computes the clearing prices for both SUs and PUs. On wining a channel, an SU i pays a price, $p^{(b)}_i$, to the auctioneer. All the payments gathered from the SUs are stored in a bidder payment vector, $P^{(b)}=\{p^{(b)}_1, p^{(b)}_2, ..., p^{(b)}_N$}. Then, to show the winning SUs, we organize them in an allocation matrix, $A=\{\textit{a}_{ij} \arrowvert \textit{a}_{ij} \in \{0,1\}\}_{N\times K_{(c)}}$, where $a_{ij}=1$ if channel j is leased to SU i. Otherwise, $a_{ij}=0$, is SU i remains unallocated. From the allocation constraint, this model considers that one channel can be assigned to more than one non-interfering SUs at a time, but one SU can acquire at most one channel at a time. Hence, matrix A is subjected to the condition, $\sum _{j=1}^{M} a_{ij} \le 1$, $\forall i\in \mathcal {N}$. Utility of SU i, $u_i^{(b)}$, on obtaining a channel j takes the valuation of the SU, $v^{(b)}_{ji}$, minus his payment on winning the channel, $p^{(b)}_i$, as shown in Eq. 3.

$$\begin{aligned} u_i^{(b)} = {\left\{ \begin{array}{ll} v^{(b)}_{ji} - p^{(b)}_i &{} \text {if }a_{ij} = 1 \\ 0 &{} \text {otherwise} \\ \end{array}\right. } \end{aligned}$$

(3)

Subsequently on the seller side, every PU q maintains a winner vector, $W_q$, to hold the number of winning SUs for each channel of PU q. $W_q$ = {$w_{q1}$, ..., $w_{qj}$, ..., $w_{qk_{q}}$}, where $w_{qj}=m$ ($0\le m \le N$) implies that the $j^{th}$ channel of PU q is assigned to m number of non-interfering SUs. Thereafter, to get the number of channels assigned from PU q, given as $\mathcal {C}_q$, we take the count of non-zero entries in $W_q$. To represent the payment earned by a PU q, a seller payment vector, $P^{(s)}_q$, is formed at each PU. $P^{(s)}_q$ = {$p^{(s)}_{q1}$, ..., $p^{(s)}_{qj}$, ...,$p^{(s)}_{qk_{q}}$}, where $p^{(s)}_{qj}$ is the payment collected from the $j^{th}$ channel of PU q when the channel is assigned to m number of SUs as per $w_{qj}=m$. Accordingly, the utility of PU q, $u_q^{(s)}$, is the total payment earned by selling his channels minus his aggregated valuation for the assigned channels, as shown in Eq. 4.

(4)

Figure 1 shows a diagrammatic representation of the proposed DAMW model.

Fig. 1.

Diagrammatic representation of DAMW model in CRN

3.2 Auction Mechanism

The DAMW framework designed for spectrum allocation in CRN consists of three different phases to complete the allocation process and together facilitates truthfulness and individual rationality on both buyer side and seller side.

In the first phase, a bidder group formation algorithm (Algorithm 1) is developed to form groups of non-interfering SUs. $G=\{g_1, g_2, ..., g_Z\}$ represents the set of bidder groups where Z is the total number of groups formed. Every member in a group $g_h$ can be assigned a common channel which enables spectrum reuse in the network. Initially, the conflict graph constructed based on the physical distance between SUs is taken as input for the Algorithm 1. Taking every SU one-by-one, a set $\mathcal {L}\subseteq \mathcal {N}$ is created everytime by considering the interference relationship of the SUs included in $\mathcal {L}$. Thereafter, the set $\mathcal {L}$ is included in G if a similar set of SUs does not exist in G. The bidder group formation algorithm is bid-independent and is carried out once during the auction process.

The next phase is to determine a bid value for each group which is further used in the winner determination process. On auctioning a channel $j\in \mathcal {K}$ in Algorithm 2, every group in G computes a group bid. We take a group $g_h$ and look into its members in the group. If there exists any SU i such that, channel j is unavailable at SU i, then SU i is removed from $g_h$. Also, if $T_{A(j)}$ is less than $T_{R(ij)}$, SU i is removed from $g_h$. While restricting to the allocation constraint, if we find that SU i has already acquired a channel, we remove SU i from $g_h$. Then, for the remaining SUs present in $g_h$, the group bid, $\lambda _h$, is obtained and the SU with minimum bid in $g_h$ is removed to form the group $g'_h$. This is performed to guarantee a truthful auction process in the model. If more than one minimum bid appears in a group, one of the bid is picked randomly. Likewise, on performing these operations for all groups in G, we get the group set $G'_j$ for channel j which will be used in the next phase.

Finally, to decide the winners, PO executes the winner determination algorithm (Algorithm 3). On auctioning a channel j, we obtain the set $G'_j$ using Algorithm 2 and gather the group bid for each group of $G'_j$ in $\varDelta _j$. The group bids in $\varDelta _j$ are sorted in descending order to get $\varDelta '_j$ where TOP($\varDelta '_j$) implies the highest group bid. Now, if PU q owns the channel j and $b^{(s)}_q$ $\le$ TOP($\varDelta '_j$), then the group of SUs having the group bid TOP($\varDelta '_j$) are assigned the channel j. Similarly, this process is repeated for all the channels.

On completing the allocation process, winner SUs pay a price to the auctioneer and winner PUs earn a benefit from the auctioneer. When a group $g'_h$ wins a channel j, it pays the group bid, $\lambda _h$, to the PO. As such, for each SU $i\in g'_h$, payment of SU i, $p^{(b)}_i$, is shown in Eq. 5.

$$\begin{aligned} p^{(b)}_i = \mathrm{min}\{b^{(b)}_{jy} | y \in g_h\} \end{aligned}$$

(5)

For the seller side, a PU q on selling his $j^{th}$ channel to a group $g'_h$ gets a payment which is equal to the group bid. That is, $p^{(s)}_{qj}=\lambda _h$. Hence, the proposed double auction model DAMW presents a spectrum allocation mechanism by incorporating different CR network constraints which can achieve an improve spectrum utilization along with spectrum reuse across the network.

3.3 Auction Properties

To avoid any kind of market manipulation, DAMW needs to satisfy two economic properties, viz. individual rationality and truthfulness.

Definition 1

Individual Rationality: A double auction is individually rational if every winning bidder (SU) pays a price which is less than its valuation and every winning seller (PU) earns a price which is greater than its valuation. This implies that both the bidder and seller retains a non-negative utility.

Definition 2

Truthfulness: A double auction is truthful if no bidder (SU) or seller (PU) can improve its utility by submitting an untruthful bid value or ask value, no matter how other players bid in the game.

Theorem 1

DAMW is individually rational.

Proof

According to the definition of individual rationality, an SU i and a PU q should attain an utility $u^{(b)}_i\ge 0$ and $u^{(s)}_q\ge 0$ respectively.

As per the pricing strategy (Eq. 5), a winner SU i belonging to a group $g'_h$ pays a price which is the bid value of an SU y who submitted the lowest bid in the group $g_h$ and is removed from $g_h$. Every SU in the group $g'_h$ ($g'_h$ is obtained by removing SU y from $g_h$) has a valuation which is greater than or equal to the valuation of SU y. As such, SU $i\in g'_h$ on winning a channel j pays $p^{b}_i \le v^{(b)}_{ji}$ which in turn results in a non-negative utility $u^{(b)}_i\ge 0$ (Eq. 3).

A PU q on selling its channel j (1$\le j \le k_q$) to a group $g'_h$ earns a payment equal to the group bid of $g'_h$. According to Algorithm 3, a PU leases its channel only when the group bid is greater than or equal to the ask value of the PU. As such, for PU q, payment earned $p^{(s)}_{qj}\ge v^{(s)}_q$. This is performed for every assigned channel of PU q which therefore gives the utility $u^{(s)}_q\ge 0$. $\blacksquare$

Lemma 1

On submitting a bid value $b^{(b)}_{ji}$, if SU i wins the channel j, then SU i also wins the channel when it bids $b'^{(b)}_{ji}> b^{(b)}_{ji}$.

Proof

When an SU $i\in g'_h$ wins a channel j, it depends on the group bid which is the bid value of the lowest bidding SU y in $g_h$. Also SU y is removed from $g_h$ and it cannot win the channel j. As such, even on submitting a bid value $b'^{(b)}_{ji}> b^{(b)}_{ji}$, SU i wins channel j since group bid remains unaffected. $\blacksquare$

Lemma 2

On submitting an ask value $b^{(s)}_q$, if PU q wins and sells a channel, then PU q also wins and sells the channel when it submits $b'^{(s)}_q < b^{(s)}_q$.

Proof

With an ask value $b^{(s)}_q$, PU q sells a channel when the winning group has a group bid greater than or equal to $b^{(s)}_q$. So, on submitting an ask value $b'^{(s)}_q < b^{(s)}_q$, PU q still can sell the channel. $\blacksquare$

Theorem 2

DAMW is truthful.

Proof

Proof for truthfulness is carried out separately for both buyer side and seller side. In the buyer side, let $u^{(b)}_i$ and $u'^{(b)}_i$ be the utility obtained on bidding $v^{(b)}_{ji}$ and $b^{(b)}_{ji}\ne v^{(b)}_{ji}$ respectively by an SU i for channel j. An auction is truthful is $u^{(b)}_i\ge u'^{(b)}_i$.

Case I: $b^{(b)}_{ji} > v^{(b)}_{ji}$

(1) When SU i loses by bidding both $v^{(b)}_{ji}$ and $b^{(b)}_{ji}$, then according to Eq. 3, $u^{(b)}_i = u'^{(b)}_i =0$.

(2) When SU i loses by bidding $v^{(b)}_{ji}$ but wins when it bids $b^{(b)}_{ji}$, then $u^{(b)}_i=0$. SU i loses the game when it is the lowest bid SU in the winning group and it gets eliminated from the group. On bidding $b^{(b)}_{ji}> v^{(b)}_{ji}$, SU i wins when $b^{(b)}_{ji}$ is greater than or equal to the second lowest bid in the group. This implies that the payment $p'^{(b)}_i$ for $b^{(b)}_{ji}$ is the second lowest bid. So, $p'^{(b)}_i \ge v^{(b)}_{ji}$ which gives $u'^{(b)}_i \le 0$.

(3) When SU i loses by bidding $b^{(b)}_{ji}$ but wins when it bids $v^{(b)}_{ji}$, then this cannot hold as per Lemma 1.

(4) When SU i wins by bidding both $v^{(b)}_{ji}$ and $b^{(b)}_{ji}$, then $u^{(b)}_i = u'^{(b)}_i$. This is because, on winning the channel, price paid is the lowest bid value from the group which is independent of any wining SU’s bid value. As such, if $p^{(b)}_i$ and $p'^{(b)}_i$ are payment for $v^{(b)}_{ji}$ and $b^{(b)}_{ji}$ respectively, then $p'^{(b)}_i=p^{(b)}_i$ which implies $u'^{(b)}_i = u^{(b)}_i$.

Case II: $b^{(b)}_{ji} < v^{(b)}_{ji}$

(1) When SU i loses by bidding both $v^{(b)}_{ji}$ and $b^{(b)}_{ji}$, then, $u^{(b)}_i = u'^{(b)}_i =0$.

(2) When SU i loses by bidding $v^{(b)}_{ji}$ but wins when it bids $b^{(b)}_{ji}$, then this cannot hold as per Lemma 1.

(3) When SU i wins by bidding $v^{(b)}_{ji}$ but loses when it bids $b^{(b)}_{ji}$, then $u'^{(b)}_i=0$. However, on winning with $v^{(b)}_{ji}$, we obtain utility $u^{(b)}_i \ge 0$ as per Theorem 1.

(4) When SU i wins by bidding both $v^{(b)}_{ji}$ and $b^{(b)}_{ji}$, then $u^{(b)}_i = u'^{(b)}_i$. Similar reason as stated in Case I.

In the seller side, let $u^{(s)}_q$ and $u'^{(s)}_q$ be the utility obtained by a PU q on submitting its ask $v^{(s)}_q$ and $b^{(s)}_q\ne v^{(s)}_q$ respectively for its channel j (1$\le j \le k_q$). We take $\mathcal {C}_q =1$ for the utility. An auction is truthful is $u^{(s)}_q\ge u'^{(s)}_q$.

Case I: $b^{(s)}_q > v^{(s)}_q$

(1) When PU q cannot sell the channel by submitting both the ask values $v^{(s)}_q$ and $b^{(s)}_q$, then according to Eq. 4, $u^{(s)}_q = u'^{(s)}_q =0$.

(2) When PU q wins by submitting the ask $b^{(s)}_q$ but loses when it submits $v^{(s)}_q$, then this cannot hold as per Lemma 2.

(3) When PU q wins by submitting the ask $v^{(s)}_q$ but loses when it submits $b^{(s)}_q$, then $u'^{(s)}_q=0$. However, on winning with $v^{(s)}_q$, we obtain utility $u^{(s)}_q \ge 0$ as per Theorem 1.

(4) When PU q wins by submitting both the ask values $v^{(s)}_q$ and $b^{(s)}_q$, then $u^{(s)}_q= u'^{(s)}_q$. This is because, the payment earned by PU q is the group bid of the winner group. As such, payment is independent of the ask value and $p^{(s)}_{qj}=p'^{(s)}_{qj}$ where $p^{(s)}_{qj}$ and $p'^{(s)}_{qj}$ are payments for $v^{(s)}_q$ and $b^{(s)}_q$ respectively. Hence, $u^{(s)}_q= u'^{(s)}_q$.

Case II: $b^{(s)}_q < v^{(s)}_q$

(1) When PU q cannot sell the channel by submitting both the ask values $v^{(s)}_q$ and $b^{(s)}_q$, then $u^{(s)}_q = u'^{(s)}_q =0$.

(2) When PU q wins by submitting the ask $b^{(s)}_q$ but loses when it submits $v^{(s)}_q$, then $u^{(s)}_q=0$. On submitting $v^{(s)}_q$ PU q loses when the highest group bid is less than $v^{(s)}_q$. Now, for $b^{(s)}_q$ to win, $b^{(s)}_q$ should be less than or equal to the group bid. So, the payment $p'^{(s)}_{qj}$ for the ask $b^{(s)}_q$ is the winning group bid and $p'^{(s)}_{qj}< v^{(s)}_q$ which gives $u'^{(s)}_q<0$.

(3) When PU q wins by submitting the ask $v^{(s)}_q$ but loses when it submits $b^{(s)}_q$, then this cannot hold as per Lemma 2.

(4) When PU q wins by submitting both the ask values $v^{(s)}_q$ and $b^{(s)}_q$, then $u^{(s)}_q= u'^{(s)}_q$. Similar reason as stated in Case I.

Therefore, this proves that an untruthful bid value or ask value cannot improve the utility of the bidder or the seller. $\blacksquare$

4 Performance Evaluation

In this section, we study the network simulations to show the performance of DAMW in a CR environment. PUs and SUs acting as seller and buyer respectively are randomly distributed in an area of size 600 m  $\times$  600 m. Multiple channels can be available at every PU depending upon their usage. Here, it considers that every PU wants to auction 2 channels each. To facilitate spectrum reuse, interference among SUs is shaped by taking the physical distance between the SUs. MATLAB based simulation evaluates the proposed model and all the results obtained are averaged over 500 rounds. The performance metrics considered for the evaluation process are spectrum utilization, spectrum reusability and channel allocation ratio as discussed below.

Spectrum utilization: It is the number of SUs who won the channels offered for auction. Given as, $\sum _{q=1}^{M}\sum _{j=1}^{k_j} w_{qj}$

Spectrum reusability: It is the ratio of number of winner SUs to the number of allocated channels. Given as, $\frac{\sum _{q=1}^{M}\sum _{j=1}^{k_j} w_{qj}}{\sum _{q=1}^{M} \mathcal {C}_q}$

Channel allocation ratio: It is the ratio of number of channels assigned to the SUs to the total number of channels given away by the PUs. Given as, $\frac{\sum _{q=1}^{M} \mathcal {C}_q}{K_{(c)}}$

Fig. 2.

Spectrum utilization of different sets of SUs when number of PUs are varied

Fig. 3.

Spectrum reusability of different sets of SUs when number of PUs are varied

In Figs. 2 and 3, the network scenario consist of three sets of SUs where the number of SUs is varied as 20, 40 and 60 respectively. Likewise, the number of PUs vary from 2 to 6, where it is considered that each PU holds 2 channels to lease. From Fig. 2, it can be observed that with the increase in number of PUs for an SU set, spectrum utilization mostly increases since more channels are offered amongst the SUs. But, depending on the CR network constraints, if channels remain unassigned, then even on increasing the count of channels, the spectrum utilization may not show a rise. Similarly, on increasing the number of SUs for a PU set, we can obtain an improved spectrum utilization. Since this model allows spectrum reuse, so with increase in SUs, more number of SUs are capable of acquiring a channel to carry out their transmission. This in turn helps to make a good use of the unused radio spectrum. In Fig. 3, reusability of the spectrum is depicted with changing number of SUs for different PU sets. With increase in number of channels (i.e. the PUs) for an SU set, the number of winning SUs may show a moderate increase due to network constraints. This can result in a reduced spectrum utilization. But, with increase in number of SUs for a PU set, the utilization increases.

Fig. 4.

Spectrum utilization of DAMW and McAfee with respect to number of PUs

Fig. 5.

Channel allocation ratio of DAMW and McAfee with respect to number of PUs

In Figs. 4 and 5, DAMW is compared with the general McAfee auction [14] when number of PUs are varied from 2 to 6 keeping number of SUs fixed at 40. In McAfee auction, it allows a single channel allocation by sorting the ask values in ascending order and bid values in descending order to reach a point where from it decides the winning sellers and buyers. All channels may not get allocated even when the network constraints are not incorporated. Figure 4 shows the spectrum utilization for both the models where a significant increase can be seen in DAMW. This is because DAMW allows spectrum reuse where multiple non-interfering channels can get a common channel. However, with increase in number of PUs (which increases the number of channels), the performance shows a moderate increase in the value which implies that due to network constraints SUs remain unassigned to the channels. In Fig. 5, channel allocation ratio shows the fraction of allocated channels out of the channels offered for auction. A reduced allocation ratio in McAfee auction depicts the scenario where many channels are left unassigned. In comparison, DAMW proffers an improved allocation ratio which in turn effects the spectrum utilization. Similarly in Figs. 6 and 7, DAMW is compared with the general McAfee auction when number of SUs are varied from 20 to 50 keeping number of PUs fixed at 4. Here also, we can observe that DAMW gives a better performance than McAfee which accounts to the similar reasons as stated above.

Fig. 6.

Spectrum utilization of DAMW and McAfee with respect to number of SUs

Fig. 7.

Channel allocation ratio of DAMW and McAfee with respect to number of SUs

Hence, the proposed double auction mechanism significantly improves the spectrum utilization in the CR network.

5 Conclusion

In this paper, we propose DAMW, a double auction framework for spectrum allocation in CRN, which supports spectrum reusability amongst non-interfering SUs. DAMW achieves individual rationality and truthfulness in the proposed model to refrain from any kind of market manipulation which may degrade the utility of SUs and PUs. More importantly, DAMW incorporates different issues arising in a CR network, viz., dynamics in SOPs and variation in availability time of the unused channels, and accordingly plans the bid submission process from SUs. A three phase procedure builds the non-interfering bidder groups, determines the bid value from each group and finally allocates the spectrum following the allocation constraint. Experimental results obtained through network simulation specify that DAMW outperforms as a spectrum allocation model by offering an improved spectrum utilization compared to the general McAfee auction. In our future work, we plan to work on heterogeneous channel condition for a similar network scenario.