Sage Journals: Discover world-class research

Abstract

Spectrum resource is experiencing a rapid growth, which cannot meet the demand of the ever-increasing wireless communications technologies in recent years. Spectrum auctions in the secondary market have been considered as a prominent way to solve this challenge due to its fairness and effectiveness. However, most of the existing studies mainly focus on allocating spectrum in units of channels without considering allocate spectrum with variable bandwidths to the secondary users, which has been supported by the software-defined radio technologies. Variable bandwidth trading can make the usage of spectrum more flexible and efficient. Thus, we study the spectrum auction problem where the primary user wants to share a continuous spectrum with the secondary users, and each secondary user has a fixed transmission demand. The target of this work is to design a truthful auction mechanism, which can allocate spectrum with variable bandwidths to the secondary users and maximize the social efficiency at the same time. We first propose a bid-monotone winner determination mechanism to decide the winning secondary users in the auction. Since the optimal winner determination problem is NP-hard, we prove that the proposed mechanism has an approximation factor of 10. Then, a channel allocation mechanism is proposed, which can allocate spectrum to winners without interference. Finally, we compute the critical value for each winner to ensure truthfulness. We can demonstrate that the proposed auction mechanism is truthful through theoretical analysis. We also perform extensive simulations to study the performance of the proposed auction mechanism, and the simulation results corroborate our theoretical analysis.

Keywords

Spectrum auction performance guarantee social efficiency maximization variable bandwidth

Introduction

With the fast development of emerging wireless networking technologies and applications,^1–4 the limited spectrum resource is becoming more and more scarce. However, many new spectrum demanders cannot access the limited spectrum licensees in time, while a large number of licensed channels are underutilized. This is mainly because the licensed channels have been allocated to some big companies in long-term lease way by the management organizations (e.g. Federal Communications Commission (FCC)). This fixed long-term spectrum allocation method leads to significant spectrum white spaces and artificial shortage of spectrum resources.⁵ Spectrum auction is one of the most promising ways to solve this challenge, which provides enough incentive for the primary user (i.e. the spectrum user holds the licensed channels) to sublease the white space of spectrum to the secondary users (i.e. the new spectrum demanders). To design an efficient spectrum auction mechanism, we may face two major challenges. The first one is that the spectrum channels can be reused in spatial, temporal, and spectral domains, which usually make the optimal spectrum allocation problems NP-hard. It is not a trivial job to design spectrum auction mechanisms with performance guarantee. The second challenge is to ensure the truthfulness of the proposed auction mechanism, especially when we consider the multidimensional reuse of spectrum.

In recent years, many spectrum auction mechanisms have been proposed. Most of these studies only consider spatial or temporal reuse of spectrum, and only few of them consider these two factors at the same time.⁶ We also note that the existing studies which consider temporal reuse assume that the spectrum demands from the secondary users can only be allocated in one channel, which means that the spectrum allocated to the secondary user can only be units of channels or a part of one channel with fixed bandwidth. Obviously, this assumption will strictly limit the utilization of spectrum. If we allocate spectrum to the secondary users with variable bandwidths, the spectrum can be utilized more flexibly and efficiently. In fact, there are already many technologies that enable the wireless communication devices to operate with variable bandwidths, such as the software-defined radio technologies and the 802.22 draft that has already included the support for variable bandwidths.⁷ At the same time, there have been some studies that focused on designing new wireless networks in which the channel bandwidth can be adaptively changed.^8,9 To meet this demand, we need to design new spectrum auction mechanisms which can allocate variable bandwidth spectrum to the secondary users. The variable bandwidth auction allows the primary users to allocate spectra in variable bandwidths, not just channels with a fixed bandwidth, which provides a flexible trading framework.

In this work, we will propose a truthful auction mechanism for continuous spectrum, which can allocate spectrum channels with variable bandwidths to the secondary users and maximize the social efficiency (i.e. the total bid values of the winning secondary users). Chen and Zhong^10,11 have proposed two truthful auction mechanisms for continuous spectrum with variable bandwidths separately for the case of no spectrum reuse (spatial and temporal domains) and the case of that the spectrum can be reused only in spatial domain. In this study, we assume that the spectrum channels can be reused in both spatial and temporal domains, which can utilize the spectrum more flexibly. In Chen and Zhong,¹¹ the authors assume that the bandwidth that each secondary user need is not a fixed one, and the bid of each secondary user is a function of the bandwidth that is allocated to this secondary user. This assumption has some limitations. In some situations, the transmission demand of each secondary user is fixed in each round of auction, such as in the cognitive radio networks (CRNs). Thus, we assume that the transmission demands of both the primary and the secondary users are fixed and are known at the beginning of each round of auction. Given a continuous spectrum, we will allocate spectrum channels with variable bandwidths to the secondary users in the consideration of spatial and temporal reuse. To the best of our knowledge, this is the first work to study the variable bandwidth spectrum model with both spatial and temporal reuse.

To achieve the design targets, we first focus on the spectrum channel allocation issue. When we allocate spectrum, we need to decide the bandwidth, frequency, and time slices that are allocated to each secondary user. Since the bandwidth and frequency are also variable in our model, this problem will become too complicated. To tackle this, we separate this issue into two sub-problems. The first one is how to choose the secondary users as winners which can maximize the social efficiency. For this problem, we design a near-optimal mechanism with an approximation factor of 10. The second one is how to allocate spectrum to winners. Since the winner determination mechanism ensures that the total transmission demands of the interference users are less than the transmission ability of the spectrum for each winner. Thus, we can find a way to allocate spectrum to winners without interference. To solve the second problem, we further design a channel allocation mechanism to allocate spectrum channels to the users without interference. We also prove that our winner determination mechanism is bid-monotone, thus there exists a critical value for each winner. The definition of bid-monotone and critical value are depicted in section “Preliminaries.” It has been proved that if the allocation mechanism is bid-monotone and we charge each winner its critical value, the designed auction mechanism is truthful. Thus, we design a payment calculation mechanism to find the critical value of each winner and prove that the proposed auction mechanism is truthful.

The rest of this article is organized as follows: We first explain the variable bandwidth spectrum auction model, the problem formulation, and the design targets in section “Preliminaries.” Then, we present the details of auction mechanism in section “Mechanism design.” Section “Simulation results” evaluates the performance of our mechanisms. Section “Literature reviews” reviews the related work, and section “Conclusion” concludes this article.

Preliminaries

In this section, we first explain the variable bandwidth spectrum auction model. Then, we will explain a formal definition of the problem we studied and the design targets of this work.

Variable bandwidth spectrum auction model

We consider spectrum auctions in which one primary user holds a continuous spectrum and willing to sell or sublease it to a set of secondary users. The auctions are executed periodically. In each round, the primary user has a fixed location, denoted by $L_{p} = (x_{p}, y_{p})$ , and a transmission traffic demand, $D_{p}$ . Assume that the primary user is willing to share the usage of spectrum $S = [f_{l}, f_{h}]$ during time interval $[0, T]$ . Note that we also assume the need of the primary user must be satisfied first in this article. Suppose W is the bandwidth of S, r denotes the per time slot per bandwidth transmission rate of S, thus we can obtain $W = f_{h} - f_{l}$ and rWT is the upper bound transmission capacity of spectrum S during time interval $[0, T]$ . We also assume that there are n secondary users who request the usage of channel in fixed locations and transmission demand. Our goal is to allocate these secondary user requests in spectrum S, such that the transmission demand of the primary user is guaranteed and the social efficiency is maximized.

Let $B = {1, 2, \dots, n}$ be the set of secondary users, in which $i \in B$ has a request $r_{i}$ and a true valuation $v_{i}$ for the $r_{i}$ . We use $R$ to denote the set of requests from the secondary users. Each $r_{i} \in R$ can be defined as $r_{i} = {L_{i}, D_{i}, b_{i}}$ , where $L_{i}$ is the geographical location where i wants to access the channel, $D_{i}$ is the transmission demand of i, and $b_{i}$ is the bid of i for the demand. Note that the auction model we studied in this article is a sealed-bid auction, thus each secondary user only knows his or her own bids and has no idea of others’ bids. Furthermore, the bid $b_{i}$ may not always equal the true valuation $v_{i}$ of the secondary user i, which indicates that we need to judiciously design the auction mechanism to ensure that each secondary user will bid the true valuation.

When allocating spectrum to the secondary users, the primary user adopts the well-known interference graph to model the interference relationships among the secondary users. We say two users i and j interfere with each other if and only if the distance of their locations is less than twice the interference radius. Then, there will be an edge between user i and user j in the interference graph. We further use $y_{i, j} = 1$ to represent i and j are interference, and $y_{i, j} = 0$ otherwise.

Problem formulation

This work is aiming at designing a truthful auction mechanism for spectrum trading with variable bandwidth. In the proposed auction mechanism, the secondary users first send their concealed requests to the primary user, who will then determine how to allocate the requests to spectrum as well as the payment of each winner. An auction mechanism mainly includes two parts: allocation mechanism design and payment calculation mechanism design. The allocation mechanism mainly decides which requests from the secondary users can access the idle spectrum resource from the primary user, such that the social efficiency is maximized. Our payment calculation mechanism computes the payment of each secondary user who successfully accesses the spectrum in our allocation mechanism. Truthful (or strategyproof) is one of the most critical properties of auction mechanism. We say an auction mechanism is truthful if and only if the dominant strategy of each secondary user is to bid the true valuation (i.e. $v_{i} = b_{i}$ ). It has been proved that an auction mechanism is truthful if the proposed allocation mechanism is bid-monotone and the payment of each winner is his critical value. In the following, we will explain the formal definition of bid-monotone allocation, critical value, and social efficiency.

Bid-monotone allocation. We say an allocation mechanism is bid-monotone, if and only if, when each secondary user i wins by bidding $b_{i}$ , he or she will always win by bidding $b'_{i} > b_{i}$ .

Critical value. The critical value for each bidder i is such a bid value—given the bids of all other participants, bidder i always wins if he bids no less than this value; otherwise, he will always lose. To ensure the truthfulness of auction mechanism, we need to find the critical value of each winner as the payment.

Social efficiency. The social efficiency in this work is defined as the total true values from winners $\sum_{r_{i} \in R} v_{i} x_{i}$ , where $x_{i} = 1$ if i wins; otherwise, $x_{i} = 0$ . As $v_{i} = b_{i}$ in a truthful auction mechanism, the social efficiency of a truthful auction mechanism can also be defined as $\sum_{r_{i} \in R} b_{i} x_{i}$ .

The objective of this work is to design a truthful auction mechanism for spectrum with variable bandwidth, which can maximize the social efficiency. The maximization of the social efficiency can also be denoted by maximizing the value of $\sum_{r_{i} \in R} b_{i} x_{i}$ under some constraints. In other words, we need to design a bid-monotone allocation mechanism which can maximize the social efficiency and a payment calculation mechanism which charge each winner his critical value. To facilitate reading, we summarize some symbols that are used in this article in Table 1.

Table 1.

Some symbols used in this article.

Symbol	Symbol meaning
n	Number of secondary users
$B$	Set of secondary users
$r_{i}$	ith secondary user’s request
$v_{i}$ , $b_{i}$ , $L_{i}$	True valuation, bid value, and request location of bidder i
$D_{i}$	Transmission demand of bidder i
$x_{i}$	Bidder i wins or not
$y_{i, j}$	Interference relationship between two users i and j
$D_{p}$ , $D_{i}$	Transmission demand of the primary user and the secondary user i
S	Continuous spectrum hold by the primary user
W	Bandwidth of S

Mechanism design

In this section, we will show the details of the proposed variable bandwidth spectrum auction mechanism, which is proved to be truthful and can maximize the social efficiency at the same time. We will first prove that the optimal spectrum allocation problem studied in our model is NP-hard and then give an approximation solution instead. After this, we will show the details of how to find the critical value of each winner. Finally, we prove that the proposed allocation mechanism and payment calculation method will induce a truthful spectrum auction mechanism.

The optimal spectrum allocation problem

To allocate the secondary users in a continuous spectrum with variable bandwidths optimally, we need to decide the frequencies, time slots, and bandwidth for each winning secondary user. This issue can be regarded as a three-dimensional allocation problem. It is not a trivial job to propose an efficient solution to tackle this issue. To reduce the complexity of our optimal spectrum allocation problem, we divided it into two sub-problems. The first one is to decide that allocate spectrum resources to which the secondary users can maximize the social efficiency (i.e. winner determination problem), and the second one is to decide the specific allocated bandwidth and time slots for each chosen secondary user (i.e. winner spectrum allocation problem).

We first concentrate on the winner determination problem, which determines the winning secondary users to maximize the social efficiency. In the optimal spectrum allocation, we need to match the requests from all secondary users and the spectrum provided by the primary user optimally under some constraints. To ensure that we can allocate the demands of winners in spectrum without interference, the total transmission demand of winner i and the other winning users (including the primary user) who are conflicted with user i should be less than the upper bound transmission capacity of spectrum S (i.e. rWT).

From the analysis mentioned above, the optimal allocation issue can be formulated as an integer programming (IP) as follows: In order to facilitate discussion, we use IP (1) to replace this IP below

maximize \sum_{r_{i} \in R} b_{i} x_{i}

(IP (1))

subject to

{\begin{matrix} D_{p} y_{i, p} + D_{i} x_{i} + \sum_{j \in B} D_{j} x_{j} y_{i, j} \leq rWT, \forall i \\ x_{i} = {0, 1}, \forall i \end{matrix}

Unfortunately, we can prove that the optimal winner determination problem studied in this article is NP-hard. To tackle this NP-hardness, we need to design an approximation mechanism which can be solved in polynomial time.

Theorem 1

The optimal winner determination problem studied in this article is NP-hard.

Proof

Consider a simple case where all the users are conflicted with each other. That is to say, for all parameter i and j, $y_{i, j} = 1$ always holds. In this case, our winner determination problem is equivalent to the classical 0−1 knapsack problem, where the transmission demand of the secondary users can be viewed as the weight of goods in the 0−1 knapsack problem, the capacity of the knapsack is the $rWT - D_{p}$ in our model, and the values of goods in 0−1 knapsack problem are the bids of the secondary users in our problem. Thus, the social efficiency maximize problem can be reduced to find a set of items with the maximum value in 0−1 knapsack problem. Since 0−1 knapsack problem is a typical NP-hard problem, the optimal task assignment problem studied in this article is also NP-hard.

As is known to all, there exists a polynomial-time approximation scheme (PTAS) mechanism which can solve the 0−1 knapsack problem. However, this PTAS mechanism is only suitable for the case that all the users are conflicted with each other in our model. For other cases, we cannot use this PTAS directly, and some new techniques are needed. ▪

Approximation spectrum allocation mechanism design

Since the optimal spectrum allocation problem is NP-hard, we employ the greedy method to design a polynomial-time spectrum allocation mechanism with approximation factor of 10. As we mentioned before, the spectrum allocation problem can be divided into two sub-problems: winner determination and winner spectrum allocation problem. If we can obtain the optimal solution of IP (1), the first problem will be solved. However, we have proved that solving IP (1) optimally is NP-hard; thus, we will turn to find an approximation mechanism instead.

The proposed winner determination mechanism, as shown in Algorithm 1, determines how to allocate spectrum to the secondary users. As the transmission demand of the primary user should be satisfied first, Algorithm 1 first allocates spectrum to the primary user and sets $x_{i} = 0$ for each secondary user. Then, we sort the secondary users in descending order according to their unit bids $b_{i} / D_{i}$ . After this, we scan the sorted secondary users one by one to decide whether we can allocate the spectrum to this demander. When secondary user i was scanned, we check whether there are enough available spectrums for i according to equation (1)

D_{P} y_{k, p} + D_{i} y_{k, i} + \sum_{j \in B} D_{j} x_{j} y_{k, j} \leq rWT

(1)

If equation (1) stands for all the $k \leq i$ in the sorted list, that means all the secondary users who win the auction still have enough spectrum to use if i wins the auction, thus we can find a way to allocate spectrum to i without interfering with any other users. In this case, we set $x_{i} = 1$ ; otherwise, we keep $x_{i} = 0$ . To further improve the performance of our mechanism, Algorithm 1 scans all the $x_{i} = 0$ to check whether the bid of i is larger than the total bids of its interference secondary users who have been allocated in spectrum. If $\sum_{r_{j} \in R} b_{j} y_{i, j} x_{j} < b_{i}$ , we will set $x_{i} = 1$ and release the spectrum that is occupied by some secondary users who are interfered with i. The time complexity of the proposed Algorithm 1 is $O (n^{2})$ , where n denotes the number of secondary users.

Algorithm 1: Winner determination mechanism
Input: the set of requests $R$ , and the interference graph G;
Output: the spectrum allocation vector $X = {x_{p}, x_{1}, x_{2}, \dots, x_{n}}$ ;
1: Set $x_{p} = 1$ ;
2: for each $r_{i} \in R$ do
3: $x_{i} = 0$ ;
4: Sort secondary users in descending order according to their unit bids $b_{i} / D_{i}$ ;
5: $b_{1} / D_{1} \geq b_{2} / D_{2} \geq \dots \geq b_{N} / D_{N}$
6: for each i in the sorted list do
7: Set win = true;
8: for each $k \leq i$ in the sorted list do
9: if $D_{P} y_{k, p} + D_{i} y_{i, k} + \sum_{j \in B} D_{j} x_{j} y_{k, j} > rWT$ then
10: Set $win = false$ ;
11: break;
12: if win = true then
13: Set $x_{i} = 1$ .
14: for each $x_{i} = 0$ do
15: if $\sum_{r_{j} \in R} b_{j} y_{i, j} x_{j} < b_{i}$ then
16: Set $x_{i} = 1$ ;
17: for each secondary user i with $y_{i, j} = 1$ and $x_{j} = 1$ in the user list sorted in ascending order according to their bids do
18: Set $x_{j} = 0$ ;
19: if $\sum_{r_{j} \in R} D_{j} y_{i, j} x_{j} \leq rWT$ then
20: break;
21: return $X$ ;

After determining the winners by Algorithm 1, we will discuss how to allocate spectrum to them. To achieve this, we first divide the spectrum into k channels, and the bandwidth of each channel is $W / k$ . We use $c_{l}$ to denote the lth divided channel which is sorted by its frequencies. Assume that the time slots of the primary user allocated to winner i are $t_{i}$ . To satisfy the transmission demand of each winner, we can obtain that

t_{i} r \frac{W}{k} \geq D_{i}

(2)

Thus; we can easily obtain $t_{i} \geq D_{i} k / Wr$ .

We assume that each channel $c_{l}$ has T unit time slots and set $z_{l, q}^{i} = 1$ if the qth time slot of $c_{l}$ is allocated to user i; otherwise, we set $z_{l, q}^{i} = 0$ . We further use $z_{l, q}$ to denote whether the qth time slot of $c_{l}$ has been allocated to users or not. Thus, the details of our channel allocation mechanism are shown in Algorithm 2. ▪

Algorithm 2 Channel allocation mechanism for winner
Input: the set of requests $R$ , and the interference graph G, the spectrum allocation vector $X$ ;
Output: the channel allocation vector $Z$ ;
for each $r_{i} \in R$ do
for $l = 1$ to kdo
for $q = 1$ to Tdo
Set $z_{l, q}^{i} = 0$ ;
for each $x_{i} = 1$ do
for $l = 1$ to kdo
for $l mod 2 = = 1$ do
for $q = 1$ to Tdo
if $\sum_{r_{j} \in R} z_{l, q}^{j} y_{i, j} < 1$ then
Allocate the $q th$ time slot of $c_{l}$ to user i;
Set $z_{l, q}^{i} = 1$ ;
if $\sum_{l = 1}^{k} \sum_{q = 1}^{T} z_{l, q}^{i} rW / k \geq D_{i}$ then
break;
else
for $q = T$ to 1 do
if $\sum_{r_{j} \in R} z_{l, q}^{j} y_{i, j} < 1$ then
Allocate the $q th$ time slot of $c_{l}$ to user i;
Set $z_{l, q}^{i} = 1$ ;
if $\sum_{l = 1}^{k} \sum_{q = 1}^{T} z_{l, q}^{i} rW / k \geq D_{i}$ then
break;
if $\sum_{l = 1}^{k} \sum_{q = 1}^{T} z_{l, q}^{i} rW / k \geq D_{i}$ then
break;
return $Z$ ;

In Algorithm 2, we scan the channels one by one when we allocate channels to user i. When channel $c_{l}$ is scanned, we check each time slot of this channel whether it can be allocated to secondary user i. If this time slot has not been allocated to the users who interfere with i (i.e. $\sum_{r_{j} \in R} z_{l, q}^{j} y_{i, j} < 1$ ), we allocate this time slot of $c_{l}$ to i and check the next time slot until the transmission demand of i has been satisfied (i.e. $\sum_{l = 1}^{k} \sum_{q = 1}^{T} z_{l, q}^{i} rW / k \geq D_{i}$ ). We can easily obtain that the time complexity of Algorithm 2 is $O (nkT)$ , where k stands for the number of channels and T denotes the time slots.

Theorem 2

Algorithm 2 can allocate spectrum to winners without interference.

Proof

Since our winner determination mechanism can ensure that the total transmission demand of i and all the winning users who are interfered with i is less than the upper bound transmission of spectrum s (i.e. rWT), the demand of i will always be satisfied in Algorithm 2.

Theorem 3

Our winner determination mechanism has an approximation factor at most 10.

Proof

Let $O_{IP 1}$ be the set of winning secondary users accepted by the optimal solution of IP (1), $P$ be the set of winning secondary users accepted by Algorithm 2. If a secondary user in $O_{IP 1}$ is not accepted by Algorithm 2, we say it is rejected by some secondary users in $P$ .

For each secondary user $i \in O_{IP 1}$ , if i is rejected by $j \in P$ , we say that j should “account for” the bid of i. In the following, we would like to analyze the upper bound of bids that an arbitrary request $j \in P$ should account for, which is the approximation factor of our mechanism.

In Algorithm 1, we assume that the secondary user can share the spectrum in transmission and spatial domains. To analyze the approximation ratio, we first focus on the reuse of transmission domain and assume all the secondary users are interfered with each other. In this case, the problem studied in this article is a bin packing problem. We allocate the spectrum to a secondary user j with lower unit bid value if $\sum_{r_{i} \in R} b_{i} y_{i, j} x_{i} < b_{j}$ . Thus, $b_{j}$ should larger than 1/2 times of the total bid value of the secondary users that j should account for. Then, we only focus on the spatial reuse. In this case, all the secondary users that j should account for should be interference-free in spatial domain. We can take the location of the secondary users as the center of the interference circles. As shown in Figure 1, for an arbitrary couple of secondary users $i 1$ and $i 2$ , we can obtain that $∠ L_{i 1} L_{j} L_{i 2} > π / 3$ . Therefore, we can conclude that there are no more than 5 secondary users whom i should account for. According to lines 10 and 11 of Algorithm 1, we can further obtain that the bid value of j should be larger than all of them.

Figure 1.

An instance of interference free in spatial domain.

Finally, we consider the reuse of both transmission and spatial domains. From the above analysis, we can obtain that the total bid values of the secondary users that j should account for is <10 times of $b_{j}$ . Since the 10 bound holds for all the secondary users in our winner determination mechanism, the approximation factor is 10. ▪

Lemma 4

The winner determination mechanism is bid-monotone, which means that if secondary user i wins by bidding $b_{i}$ , it will always win by bidding $b'_{i} > b_{i}$ .

Proof

In Algorithm 1, we scan the secondary users in descending order according to their unit bids $b_{i} / D_{i}$ . If i wins by bidding $b_{i}$ , the total transmission demand of all the secondary users who are interfered with i and their unit bid value are larger than i should be less than $rWD - D_{p} \times y_{p, i} - D_{i}$ . When i bids $b'_{i} > b_{i}$ , the unit bid value of i is increased. According to Algorithm 1, the order i is scanned and will also increase. Thus, there will be enough spectrum for i when i is scanned with bid value $b'_{i} > b_{i}$ , and i will always win in this case.

This finishes our proof. ▪

Payment calculation and analysis

Bid-monotone allocation implies that there is a critical value $b_{i, c}$ for each secondary user i such that if i bids higher than $b_{i, c}$ , it always wins, and if i bids lower than $b_{i, c}$ , it always loses. It has been proved by Myerson that the auction mechanism is truthful if we charge each winner its critical value.¹² Therefore, we need to find the critical value for each winner.

Suppose i wins in Algorithm 1 by bidding $b_{i}$ . If i decrease its bid to $b'_{i}$ , there are two cases that the secondary user i will lose the auction.

Case 1

There is no enough spectrum for i when i was scanned in line 7 of Algorithm 1, and secondary user i cannot preempt the spectrum occupied by the interference users (i.e. $b'_{i} < \sum_{r_{j} \in R} b_{j} y_{i, j} x_{j}$ ). We first consider the critical value of i that Algorithm 1 will set $x_{i} = 0$ in line $7$ , and use $p_{i}^{1'}$ to denote it. According to Algorithm 1, there exists a secondary user j, $x_{i}$ always equals to 1 in line 7 when $b_{i} / D_{i} > b_{j} / D_{j}$ and equals to 0 otherwise. Thus, we can easily obtain that

p_{i}^{1'} = \frac{b_{j} D_{i}}{D_{j}}

(3)

Then, we consider the critical value of i can preempt the spectrum occupied by its interference users, and we use $p_{i}^{1 ″}$ to denote this critical value. We use $R / {i}$ to denote the request set that delete $r_{i}$ from $R$ . To obtain $p_{i}^{1 ″}$ , we can first run Algorithm 1 using $R / {i}$ as input and compute the allocation vector $X' = {x'_{j}}_{r_{j} \in R / {i}}$ . Then, we can obtain that

p_{i}^{1 ″} = \sum_{r_{k} \in R / {i}} b_{k} x'_{k} y_{i, k}

(4)

Combining $p_{i}^{1'}$ and $p_{i}^{1 ″}$ , we can obtain that the critical value of case 1 is

p_{i}^{1} = min (p_{i}^{1'}, p_{i}^{1 ″})

(5)

Case 2

The spectrum that is allocated to i is preempted by j in line 13 of Algorithm 1. We use $p_{i}^{2}$ to denote the critical value of i in this case. We first sort secondary users in descending order according to their unit bids $b_{i} / D_{i}$ : $b_{1} / D_{1} \geq b_{2} / D_{2} \geq \dots \geq b_{N} / D_{N}$ . If $D_{j}$ is no more than $\sum_{i < e < j} D_{e} y_{e, j} x_{e}$ , there must exist a secondary user $i < w < j$ , and i always wins when $b_{i} > b_{w}$ and loses otherwise. In this subcase, we can obtain that

p_{i}^{2} = b_{w}

(6)

If $D_{j}$ is larger than $\sum_{i < e < j} D_{e} y_{e, j} x_{e}$ , i will win if and only if $b_{j} \leq \sum_{e = 1}^{j} b_{e} y_{e, j} x_{e} - b_{i} + b'_{i}$ . Thus, we can obtain that

p_{i}^{2} = b_{j} - \sum_{e = 1}^{j} b_{e} y_{e, j} x_{e} + b_{i}

(7)

The details of our payment calculation mechanism are shown in Algorithm 3. It is clear that the time complexity of Algorithm 3 is $O (n^{2})$ .

Algorithm 3: Payment calculation mechanism
Input: the set of requests $R$ , and the interference graph G, the spectrum allocation vector $X$ ;
Output: the payment vector $P = {P_{1}, P_{1}, P_{2}, \dots, P_{n}}$ ;
Sort secondary users in descending order according to their unit bids $b_{i} / D_{i}$ ;
$b_{1} / D_{1} \geq b_{2} / D_{2} \geq \dots \geq b_{N} / D_{N}$
for each i in the sorted list do
if $x_{i} = 1$ then
Set label = false;
for each j in the sorted list do
if $D_{P} y_{i, p} + \sum_{e = 1}^{j} D_{e} x_{e} y_{i, e} \geq rWT$ and label = false then
Set $p_{i}^{1'} = b_{j} D_{i} / D_{j}$ ;
label = true;
Set $R' = R / {i}$ ;
Run Algorithm 1 using $R'$ as input and obtain the allocation vector $X'$ ;
Set $p_{i}^{1''} = \sum_{r_{k} \in R'} b_{k} x'_{k} y_{i, k}$ ;
Set $p_{i}^{1} = min (p_{i}^{1'}, p_{i}^{1''})$ ;
Set $\max_pay = p_{i}^{1}$ ;
else if $D_{P} y_{i, p} + \sum_{e = 1}^{j} D_{e} x_{e} y_{i, e} \geq rWT$ and $y_{i, j} = 1$ and $x_{j} = 0$ then
if $b_{j} \geq \sum_{e = 1}^{j} b_{e} y_{e, j} x_{e} - b_{i} + b_{j} D_{i} / D_{j}$ then
if $D_{j} > \sum_{i < e < j} D_{e} y_{e, j} x_{e}$ then
$p_{i}^{2} = b_{j} - \sum_{e = 1}^{j} b_{e} y_{e, j} x_{e} + b_{i}$ ;
else
forw = j − 1 to ido
if $D_{j} \leq \sum_{e = j - 1}^{w} D_{e} y_{e, j} x_{e}$ then
Set $p_{i}^{2} = b_{w}$ ;
break;
$\max_pay = max (\max_pay, p_{i}^{2})$ ;
$P_{i} = \max_pay$ ;
else
Set $P_{i} = 0$ ;
return $P$ ;

With the proof that our winner determination mechanism is bid-monotone, we can compute the critical value for each winner. Then, we can easily obtain the following.

Theorem 5

Our auction mechanism is truthfulness.

Simulation results

Simulation setup

In the simulation, we assume that there is one continuous spectrum S with frequency from 2000 to 2100, and the transmission rate of S is 5 per bandwidth per time slot. In each round of auction, the primary user is willing to share S with the secondary users during time interval $(0, 36]$ . We set the locations of all the secondary users are uniformly or Gaussian distributed in a $100 \times 100$ square area. Assume the transmission demand of the primary user is 1, and the transmission demands of the secondary users are randomly distributed in $(100, 200]$ . We also assume that the bids of secondary users are randomly distributed in $(0, 1]$ . The interference radius of S is set to be 25. All the simulation results are the average of 100 runs.

We carry out three sets of experiments with different objectives separately in uniformly and Gaussian location distribution setting:

We defined the social efficiency ratio as the ratio of the social efficiency of our mechanism and the optimal one. By computing the social efficiency ratio of our mechanism, we can evaluate the social efficiency performance of our mechanism in the first set of experiments.

The second and the third experiments are separately focused on the utilization and trading rate performance of our mechanism.

Performance analysis

We first evaluate the social efficiency performance of the proposed mechanism. In each type of location distribution, we record the social efficiency ratio of our mechanism, with respect to the number of secondary users. As shown in Figure 2, the social efficiency ratio of our mechanism is decreased with the increasing number of secondary users. Moreover, our mechanism performs better in the Gaussian location distribution setting than in the uniform location distribution setting. However, the result of our mechanism is >71% of the optimal solution even in the worst case of Figure 2, which is much better than the theoretical bound.

Figure 2.

Social efficiency ratio under two distributions.

We define the utilization of spectrum as the ratio of the total demand of users that wins the auction and the upper bound transmission of the spectrum without reuse. From Figure 3, we can see that the utilization of spectrum is increased with the increasing number of secondary users. Because the spectrum can be reused in spatial domain, the spectrum utilization can be >1. We find that the utilization of our mechanism in the uniform distribution setting is larger than that in the Gaussian distribution setting. This is because most of the secondary users are located in a small area in the Gaussian distribution setting, which will decrease the number of interference-free users for each secondary user.

Figure 3.

Utilization comparison under two distributions.

The trading rate of our mechanism is the ratio of number of winning secondary users and the number of secondary users in the spectrum market. Obviously, the more secondary users will cause fierce competition and lower trading rate, which are verified in Figure 4. As the analysis of Figure 3, the competition in the Gaussian distribution setting is higher than that in the uniform distribution setting, thus more secondary users lose auction in the Gaussian distribution setting. This is also the reason why the trading rate of our mechanism in the Gaussian distribution setting is lower than that in the uniform distribution setting.

Figure 4.

Trading rate comparison under two distributions.

Literature reviews

Studies on auction theory for wireless communications

Auction theory has been regarded as an important and attractive subfield of economics and game theory and serves as an efficient and fair way to allocate scarce resources among strategic users. Recently, some improved auction models have been widely used in the field of communication and networking, such as cooperative communication, CRNs, cloud computing, and crowdsensing.^13–19 In the application of cooperative communications, Yang et al.¹⁶ proposed a double auction–based incentive mechanism to encourage more wireless nodes to serve as relay nodes. Zhang et al. proposed an online auction in IaaS clouds to maximize the social efficiency or the cloud provider’s profit. For crowdsensing applications, in order to encourage more participants get involved in mobile phone sensing, a computationally efficient auction mechanism is proposed in Yang et al.¹⁷

Studies on truthful spectrum auction without considering variable bandwidth

With the ever-increasing spectrum-based services in recent years, the remaining available spectrum resource is being exhausted. To tackle this challenge, many state-of-art auction mechanisms are proposed for solving spectrum scarcity. Some previous research studies mainly focus on maximizing the total profit or minimizing the spectrum interference when coping with the dynamic spectrum access issue.^20–22 However, these works have not considered truthfulness in the designing of the auction mechanisms.

Truthfulness (aka strategyproofness) is considered as one of the essential and most critical properties for the auction mechanism design. Truthful auction mechanism design has been well studied due to its economic importance, and a large number of auction mechanisms have been proposed to achieve the truthfulness.^23–28 Unfortunately, we cannot simply introduce these well-known mechanisms into spectrum allocation without any changes due to some constraints, such as spatial and temporal reuse and suboptimal algorithm design. Therefore, some judiciously designed algorithms were proposed to solve the above challenges.

Truthfulness is mentioned in some prior literatures^29,30 for spectrum assignment. Li et al.²⁹ proposed a series of PTAS or efficient approximation truthful algorithms for spectrum assignment problems such that overall social benefit is maximized. Zhou et al.³⁰ proposed a truthful and computationally efficient spectrum auction VERITAS to support dynamic spectrum trading market in their work. In order to fully exploit the potential of spectrum utilization, spectrum often reused in both spatial and temporal domains. Most of the existing literatures of spectrum auction mainly concentrate on mechanism design with consideration of spatial reuse.^30–39 Social efficiency maximization and revenue maximization are the two main optimization goals in the auction design. Al-Ayyoub and Gupta⁴⁰ and Jia et al.³⁵ focus on the revenue maximization for the auctioneer in the mechanism design. Gopinathan et al.³² choose to work on the trade-off between social efficiency maximization and fairness while designing truthful auction mechanism. Zhou and Zheng³⁹ first proposed a double auction–based spectrum auction model by revising the well-known McAfee double auction scheme. As another line of spectrum reuse, temporal reuse is considered in some online-auction-model studies.^41–45 However, there are very few work that pay attention on both spatial and temporal reuse. Huang et al.^6,46 first proposed a near-optimal truthful spectrum auction mechanism with performance guarantee, which jointly considered spatial and temporal reuse. In addition, some researchers proposed many truthful auction schemes based on some specific auction models. For instance, Feng et al.,³¹ Huang et al.,³⁴ Zhou et al.,³⁹ Wang et al.,⁴¹ and Li et al.⁴⁷ mainly considered double spectrum auction model, while Dong et al.⁴⁸ tackle spectrum auction by introducing the combinatorial auction model, which achieves the spectrum temporal reuse. Huang et al.³³ proposed a privacy preserving truthful auction mechanism which can achieve good social efficiency and with low computation and communication overhead.

Studies on variable bandwidth spectrum auction

Most of the existing studies assume that the spectrum allocated to the secondary user can only be units of channels or a part of one channel with fixed bandwidth. Up to now, only Chen and Zhong^10,11 and their extended version allow to allocate variable bandwidth instead of fixed channels. However, Chen and Zhong^10,11 assume that the secondary users can only share one channel in spatial domain, which is not very efficient. Thus, we will propose a variable bandwidth spectrum auction mechanism with both spatial and temporal reuse in this article.

Conclusion

In this work, we have studied the problem of spectrum allocation with variable bandwidth, where spectrum can be reused in both spatial and temporal domains. To deal with this problem, we first designed an approximation winner determination mechanism with performance guarantee. Then, the spectrum allocation mechanism was proposed to decide the specific allocated frequency, bandwidth, and time slots for each winner. Finally, we designed a payment calculation mechanism that charges each winner its critical value. We prove that the spectrum auction mechanism proposed in this article is truthfulness.

Some interesting questions are left for future research. First, we plan to study the spectrum auction model where there are multi-heterogeneous spectrums in the market. Second, we plan to design truthful mechanisms for online auctions, which also support for allocating spectrum with variable bandwidth to the secondary users.

Footnotes

Academic Editor: Zhipeng Cai

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is partially supported by National Natural Science Foundation of China (NSFC) under grant No. 61572342 and 61303206, Natural Science Foundation of Jiangsu Province under grant nos BK20151240 and BK20161258, China Postdoctoral Science Foundation under grant nos 2015M580470 and 2016M591920, and Shenyang Normal University Project under grant no. L201512. Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD) and Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology (CICAEET). Any opinions, findings, conclusions, or recommendations expressed in this article are those of author(s) and do not necessarily reflect the views of the funding agencies (NSFC).

References

Guo

Wang

. A variable threshold-value authentication architecture for wireless mesh networks. J Internet Technol 2014; 15(6): 929–936.

Shen

Tan

Wang

. A novel routing protocol providing good transmission reliability in underwater sensor networks. J Internet Technol 2015; 16(1): 171–178.

Yang

Wang

. Online sequential channel accessing control: a double exploration vs. exploitation problem. IEEE T Wirel Commun 2015; 14(8): 4654–4666.

Yang

Yan

X-Y

. Taming cross-technology interference for Wi-Fi and ZigBee coexistence networks. IEEE T Mobile Comput 2016; 15(4): 1009–1021.

Sun

Y-E

Huang

X-Y

. Spectrum allocation mechanisms in wireless networks with performance guarantee. Ad Hoc Sens Wirel Ne 2015; 27(1–2): 111–134.

Huang

Sun

Y-E

X-Y

. Truthful auction mechanisms with performance guarantee in secondary spectrum markets. IEEE T Mobile Comput 2015; 14(6): 1315–1329.

IEEE 802.22. IEEE standards for wireless regional area network (WRAN) using white spaces, http://www.ieee802.org/22/

Bahl

Chandra

Moscibroda

. White space networking with wi-fi like connectivity. Comput Comm Rev 2009; 39(4): 27–38.

Yuan

Bahl

Chandra

. Allocating dynamic time-spectrum blocks in cognitive radio networks. In: Proceedings of the 8th ACM international symposium on mobile ad hoc networking and computing (MobiHoc 2007), Montreal, QC, Canada, 9–14 September 2007, pp.130–139. New York: ACM.

10.

Chen

Zhong

. On designing truthful spectrum auctions for variable bandwidths. In: Proceedings of the IEEE ICC 2013, Budapest, 9–13 June 2013, pp.1434–1438. New York: IEEE.

11.

Chen

Zhong

Truthful auctions for continuous spectrum with variable bandwidths. IEEE T Wirel Commun 2014; 13(2): 1116–1128.

12.

Myerson

RB.

Optimal auction design. Math Oper Res 1981; 6(1): 58–73.

13.

Shi

. RSMOA: a revenue and social welfare maximizing online auction for dynamic cloud resource provisioning. In: Proceedings of the IEEE/ACM IWQoS 2014, Hong Kong, 26–27 May 2014, pp.41–50. New York: IEEE.

14.

Wang

Liang

Revenue maximization with dynamic auctions in IaaS cloud markets. In: Proceedings of the IEEE/ACM IWQoS 2013, Montreal, QC, Canada, 3–4 June 2013; 1–6. New York: IEEE.

15.

Wang

Huang

. Truthful auction for resource allocation in cooperative cognitive radio networks. In: Proceedings of the IEEE ICCCN 2015, Las Vegas, NV, 3–6 August 2015, pp.1–8. New York: IEEE.

16.

Yang

Fang

Xue

. Truthful auction for cooperative communications. In: Proceedings of the ACM MobiHoc 2011, Paris, 16–20 May 2011, Article no. 9. New York: ACM.

17.

Yang

Xue

Fang

. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In: Proceedings of the ACM Mobicom 2012, Istanbul, Turkey, 22–26 August 2012, pp.173–184. New York: IEEE.

18.

Zhang

Dynamic resource provisioning in cloud computing: a randomized auction approach. In: Proceedings of the IEEE INFOCOM 2014, Toronto, ON, Canada, 27 April–2 May 2014, pp.433–441. New York: IEEE.

19.

Zhang

Huang

. Online auctions in IaaS clouds: welfare and profit maximization with server costs. In: Proceedings of the ACM SIGMETRICS 2015, Portland, OR, 15–19 June 2015, pp.3–15. New York: ACM.

20.

Gandhi

Buragohain

Cao

. A general framework for wireless spectrum auctions. In: Proceedings of the IEEE DySPAN 2007, Dublin, 17–20 April 2007, pp.22–33. New York: IEEE.

21.

Huang

Berry

Honig

ML.

Auction-based spectrum sharing. Mobile Network Appl 2006; 11(3): 405–418.

22.

Ryan

Aravantinos

. A new pricing model for next generation spectrum access. In: Proceedings of the first international workshop on technology and policy for accessing spectrum, Boston, MA, 2–5 August 2006, Article no. 11. New York: ACM.

23.

Babaioff

Nisan

. Concurrent auctions across the supply chain. In: Proceedings of the 3rd ACM conference on electronic commerce, Tampa, FL, 14–17 October 2001. New York: ACM.

24.

Clarke Edward

. Multipart pricing of public goods. Public Choice 1971; 11(1): 17–33.

25.

Deshmukh

Goldberg

Hartline

. Truthful and competitive double auctions. In: Proceedings of the European symposium on algorithms (ESA 2002), Rome, 17–21 September 2002, pp.361–373. New York: ACM.

26.

Groves

Incentives in teams. Econometrica 1973; 41: 617–631.

27.

McAfee

RP.

A dominant strategy double auction. J Econ Theory 1992; 56(2): 434–450.

28.

Vickrey

Counterspeculation, auctions, and competitive sealed tenders. J Financ 1961; 16(1): 8–37.

29.

X-Y

Tang

. Spectrum bidding in wireless networks and related. In: Hu

Wang

(eds) Computing and combinatorics. Berlin, Heidelberg: Springer, 2008, pp.558–567.

30.

Zhou

Gandhi

Suri

. ebay in the sky: strategy-proof wireless spectrum auctions. In: Proceedings of the ACM Mobicom 2008, San Francisco, CA, 14–19 September 2008, pp.2–13. New York: ACM.

31.

Feng

Chen

Zhang

. TAHES: truthful double auction for heterogeneous spectrums. In: Proceedings of the IEEE INFOCOM 2012, Orlando, FL, 25–30 March 2012, pp.3076–3080. IEEE.

32.

Gopinathan

. Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets. In: Proceedings of the IEEE INFOCOM 2011, Shanghai, China, 10–15 April 2011, pp.2813–2821. New York: IEEE.

33.

Huang

X-Y

Sun

. PPS: privacy-preserving strategyproof social-efficient spectrum auction mechanisms. IEEE T Parallel Distr 2015; 26(5): 1393–1404.

34.

Huang

Sun

Xing

. Truthful multi-unit double auction for spectrum allocation in wireless communications. In: Proceedings of the 7th international conference on wireless algorithms, systems, and applications (WASA 2012), Yellow Mountains, China, 8–10 August 2012. Berlin, Heidelberg: Springer.

35.

Jia

Zhang

. Revenue generation for truthful spectrum auction in dynamic spectrum access. In: Proceedings of the ACM Mobihoc 2009, New Orleans, LA, 18–21 May 2009, pp.3–12. New York: ACM.

36.

Wang

Liang

District: embracing local markets in truthful spectrum double auctions. In: Proceedings of the IEEE SECON 2011, Salt Lake City, UT, 27–30 June 2011, pp.521–529. IEEE.

37.

Vaidya

. SMALL: a strategy-proof mechanism for radio spectrum allocation. In: Proceedings of the IEEE INFOCOM 2011, Shanghai, China, 10–15 April 2011, pp.3020–3028. New York: IEEE.

38.

Zheng

Chen

. SMASHER: a strategy-proof combinatorial auction mechanism for heterogeneous channel redistribution. In: Proceedings of the ACM MobiHoc 2013, Bangalore, India, 29 July–1 August 2013, pp.305–308. New York: ACM.

39.

Zhou

Zheng

. TRUST: a general framework for truthful double spectrum auctions. In: Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 19–25 April 2009, pp.999–1007. IEEE.

40.

Al-Ayyoub

Gupta

Truthful spectrum auctions with approximate revenue. In: Proceedings of the IEEE INFOCOM 2011, Shanghai, China, 10–15 April 2011, pp.2813–2821. New York: IEEE.

41.

Wang

. TODA: truthful online double auction for spectrum allocation in wireless networks. In: Proceedings of the IEEE Dyspan 2010, Singapore, 6–9 April 2010, pp.1–10. New York: IEEE.

42.

X-Y.

TOFU: semi-truthful online frequency allocation mechanism for wireless network. IEEE/ACM T Network 2011; 19(2): 433–446.

43.

Tang

Efficient and strategyproof spectrum allocations in multichannel wireless networks. IEEE T Comput 2011; 60(4): 580–593.

44.

Wang

XY.

SALSA: strategyproof online spectrum admissions for wireless networks. IEEE T Comput 2010; 59(12): 1691–1702.

45.

Tang

. Truthful online spectrum allocation and auction in multi-channel wireless networks. In: Proceedings of the IEEE INFOCOM 2011, Shanghai, China, 10–15 April 2011, pp.26–30. New York: IEEE.

46.

Huang

Sun

X-Y

. Near-optimal truthful spectrum auction mechanisms with spatial and temporal reuse in wireless networks. In: Proceedings of the ACM MobiHoc 2013, Bangalore, India, 29 July–1 August 2013, pp.237–240. New York: ACM.

47.

Cheng

Bie

. An extensible and flexible truthful auction framework for heterogeneous spectrum markets. In: Proceedings of the ACM MobiHoc 2014, Philadelphia, PA, 11–14 August 2014, pp.175–184. New York: ACM.

48.

Dong

Sun

Wang

. Combinatorial auction with time-frequency flexibility in cognitive radio networks. In: Proceedings of the IEEE INFOCOM 2012, Orlando, FL, 25–30 March 2012, pp.2282–2290. New York: IEEE.

A Variable bandwidth spectrum auction mechanism with performance guarantee

Abstract

Keywords

Introduction

Preliminaries

Variable bandwidth spectrum auction model

Problem formulation

Mechanism design

The optimal spectrum allocation problem

Theorem 1

Proof

Approximation spectrum allocation mechanism design

Theorem 2

Proof

Theorem 3

Proof

Lemma 4

Proof

Payment calculation and analysis

Case 1

Case 2

Theorem 5

Simulation results

Simulation setup

Performance analysis

Literature reviews

Studies on auction theory for wireless communications

Studies on truthful spectrum auction without considering variable bandwidth

Studies on variable bandwidth spectrum auction

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References