A Truthful Bilateral Multiunit Auction for Heterogeneous Cognitive Radio Networks

Abstract

Dynamic spectrum access technology has attracted much attention for its capability of improving spectrum efficiency. For attracting primary users to participate in secondary spectrum market, an auction was proposed as an alternative for spectrum trade. Existing auction schemes are either to be unilateral trade which only supports heterogeneous cognitive radio networks without guarantee of bid truthfulness, or to be truthful single-unit auction which only supports homogeneous channels. Few of them could comprehensively take all aspects of actual spectrum trade into consideration, such as spectrum allocation and reusability, channel diversity, and economic property. A truthful bilateral multiunit auction scheme which has characteristics of supporting heterogeneous networks (TBMAH) and polynomial complexity is proposed in this paper. We do experiments with both simulation and real networks, and the results show that TBMAH trades more spectrum resources than TRUST by 13.01% on average.

1. Introduction

Many researchers are interested and engaged in solving how to dynamically utilize spectrum resources efficiently in recent years. So far many dynamic spectrum access technologies have been proposed and auction is one of the best-known market-driven mechanisms among them. In contrast to the primary spectrum market conducted by spectrum administration department like Federal Communications Commission (FCC) in the USA and its counterparts in other countries, we mainly focus on secondary spectrum market in this paper, which is different from the primary one in three major aspects. Firstly, permitted spectrum access period of secondary spectrum auction is much shorter than that of primary auction, probably to be several hours versus several years. Secondly, secondary auction is performed within a local area while primary auction is executed across a nation or state area wide. Thirdly, many sellers and buyers are involved in secondary auction which is executed periodically by an acknowledged auctioneer with high reputation while primary auction is conducted by governmental department and participated in by some competitive wireless service providers.

Zhou et al. [1] proposes the first truthful spectrum auction-VERITAS which supports diverse bidding formats and multiple units auction, but VERITAS only addresses unilateral auction. Subramanian et al. [2] presents a coordinated dynamic spectrum access architecture which is composed of multiple buyers with heterogeneous channel width and one spectrum broker. The broker takes charge of collecting spectrum supply and demand information from sellers and buyers respectively, and executing auction process periodically. This architecture adopts physical interference model during spectrum allocation and multiplexes channel among nonconflict base stations. However, it is a unilateral auction and has no guarantee of truthfulness of bidding function. Zhou puts forward a general framework, TRUST, for truthful bilateral spectrum auction in [3, 4]. For the purpose of avoiding bid manipulation, TRUST adopts a bid-independent buyer grouping method and employs a truthful auction mechanism like McAfee double auction. This framework also considers the problem of spectrum reusability among nonadjacent buyers however, TRUST is a single-unit auction and only supports homogeneous channel. Other efforts either lead to market manipulation due to loss of truthfulness like [5–8] or have no consideration of reusability like [9, 10].

In order to establish a more practical secondary spectrum market, we analyze the problem comprehensively and propose a truthful bilateral multiunit auction which supports participations of heterogeneous networks. Our contributions are mainly in the following aspects.

• (1)

For multiplexing channel among nonconflict buyers, we adopt a bid-independent grouping method with high reusability, tightly integrate spectrum allocation, and truthful auction components.

(2)

For supporting multiunit heterogeneous auction, we generate bidding series for each competitive group according to bids of its group members and devise winners determination algorithm with polynomial complexity.

(3)

For validating our auction scheme comprehensively and fairly, we compare our scheme with extended version of TRUST using different spectrum allocation algorithms, bid distributions, and real networks.

The rest of our paper is organized as follows. Section 2 describes spectrum auction problem formally and shows considerable factors in designing spectrum auction. We make detailed description of our auction scheme in Section 3 and illustrate results in Section 4 with both simulation and real networks, finally, Section 5 makes a conclusion for the full paper.

2. Spectrum Auction Problem Description

The scenario we considered consists of multiple spectrum providers and multiple spectrum demanders. Spectrum providers (probably to be licensed users with low spectrum utilization like TV stations) want to earn additional revenues by leasing spectrum at their spare time. Spectrum demanders (probably to be small wireless networks like AP or Femtocell) require more spectrum resources to alleviate their heavy business load, and accordingly they should pay spectrum providers some rental expenses. Like many literatures which pointed out that this problem is NP-complete, most researchers are pursuing its approximate algorithm. For the purpose of trading efficiently, we assume that there is one broker responsible for establishing relationship between both sides, executing spectrum allocation, charging buyers, and paying sellers in secondary spectrum market. We define spectrum auction problem of secondary market formally in the next part.

2.1. Spectrum Auction Problem Definition

For clarity of description, we define some notations first.

• (i)

Set $S=\{S_i\hspace{0.17em}|\hspace{0.17em}1\le i\le M\}$ is a collection of bids from sellers, each bid $S_i=(S_i^n,S_i^p)$ is a tuple which consists of the number of resources to sell and asking price for unit spectrum.

(ii)

Similarly, set $B=\{B_j\hspace{0.17em}|\hspace{0.17em}1\le j\le N\}$ is a collection of bids from buyers, each bid $B_j=(B_j^n,B_j^p,B_j^w)$ is a tuple which consists of the number of channels to buy, bidding price for unit spectrum and channel width of buyer j's network.

Definition 1.

In a secondary spectrum market participated in by M sellers and N buyers, both seller $S_i\hspace{0.17em}\hspace{0.17em}(1\le i\le M)$ and buyer $B_j\hspace{0.17em}\hspace{0.17em}(1\le j\le N)$ submit their declarations to the auctioneer. Spectrum auction is the process of determining winners and calculating clearing price while maximizing the total number of resources transacted. Each winning buyer $B_j$ is charged for the resources he obtained and each winning seller $S_i$ is payed for what he rented out.

Secondary bilateral spectrum auction is carried out periodically, and both spectrum owners and lessees, respectively, submit their bids to the auctioneer during each auction period. We assume that the auction is bid-sealed and neither sellers nor buyers collude, spectrum resources collected from different sellers are not necessarily continuous, and demands of all buyers are not channel-specific.

For the purpose of simplicity, we adopt coverage-based interference model during spectrum allocation like [3], that is to say, two networks interfering with each other solely depends on whether their coverages overlap or not. So we assume that the auctioneer is capable of obtaining coordinates and transmission power of each node. With conflict graph generated and bids gathered from both sellers and buyers, what the auctioneer needs to do next is allocating the right number of resources to proper buyers with the goal of maximizing spectrum utilization, while guaranteeing economic properties and getting close to real market situation. Worthy considerations in designing and implementing an auction scheme are introduced in the next part.

2.2. Considerations of Spectrum Auction Scheme Design

We assume that all participants of the auction are sane enough and no participant is allowed to go back on his words. No seller is charitable enough to sell more resources with less revenue, and no buyer prefers to pay more money without obtaining more resources.

2.2.1. Truthfulness

An auction is considered to be truthful if it can ensure that the optimal strategy for each bidder is bidding with his true valuation of the object. That is to say, for any participant who bids untruthfully, the resulting utility he received is not bigger than that if he bids truthfully, which makes him have no incentive to bid untruthfully. A truthful auction simplifies bidding strategy of each bidder by just bidding what he really estimates instead of guessing what his competitors would bid.

2.2.2. Individual Rationality

For each seller $S_i\hspace{0.17em}\hspace{0.17em}(1\le i\le M)$ , the clearing price should not be less than the income he expects, and for each buyer $B_j\hspace{0.17em}\hspace{0.17em}(1\le j\le N)$ , the clearing price should not be bigger than the payment he declares. Both the final charge and payment should be calculated with the actual transacted amount instead of the number they wish to trade. We call an auction individual rational if it meets all of the above three requirements.

2.2.3. Ex-Post Budget Balance

After finishing the auction, charges collected from winning buyers should not be less than payments to winning sellers, so that the auctioneer can make both ends meet. The auctioneer is not allowed to pay out of his own pocket for promoting resources transaction.

2.2.4. Bilateral Auction

Existing unilateral auctions assume that there is only one spectrum seller or an agent gathering spectrum resources from multiple sellers. However, these schemes ignore competition among sellers in actual spectrum trade. So we insist on devising a bilateral auction for secondary spectrum market.

2.2.5. Reusability

Different from conventional goods (e.g., porcelain and painting), spectrum resource can be accessed simultaneously by more than one network provided that they do not interfere with each other. So a well-designed spectrum auction scheme should not neglect spectrum reusability problem.

2.2.6. Support of Multiunit

Both sellers and buyers may be eager to trade more than one unit spectrum resource in order to increase their revenue or alleviate business burden, the auctioneer may satisfy their entire or partial requirements according to supply and demand situations. So the auction should be devised strategically to support multiunit trade.

2.2.7. Support of Heterogeneous Networks

Every wireless network is deployed with an orientation to specific application area. Different spectrum buyers (cognitive users) have diverse spectrum usage rules. One of the most obvious and important differences is heterogeneous channel width, which equals to 200 KHz in GSM network and 20 MHz in WiFi. So the spectrum auction scheme should support heterogeneous networks.

Seldom prior efforts on spectrum auction consider this problem comprehensively, resulting that existing schemes can meet only a few of these requirements, which motivates us to do this work.

2.3. Utilities of Each Participant

In order to meet all of the requirements listed above, we adopt a Vickrey-Clarke-Groves (VCG-) style forward auction and a McAfee-style reverse auction.

Suppose that there are T items in set $I=\{t_1,t_2,\dots ,t_T\}$ to be sold and N bidders in buyer set B competing for these items in a VCG auction, notation $V_B^I$ denotes the total social value can be achieved. If bidder $B_i$ is assigned item $t_j$ , his cost in the VCG system is defined to be $V_{B\setminus \{B_i\}}^I-V_{B\setminus \{B_i\}}^{I\setminus \{t_j\}}$ . The first term is the social value should person $B_i$ be removed from the auction, the second term is the social value should person $B_i$ and item $t_j$ be removed from the auction. So for each competitive buyer, the utility he obtains from single-unit spectrum equals to $B_i^p-(V_{B\setminus \{B_i\}}^I-V_{B\setminus \{B_i\}}^{I\setminus \{t_j\}})$ , where $B_i^p$ is buyer i's valuation for single-unit spectrum.

For a McAfee auction, sellers are sorted in nondecreasing order by their bidding prices, the utility one individual seller obtains from single-unit spectrum equals to $C^p-S_i^p$ , where $C^p$ and $S_i^p$ , respectively, represent the clearing price and seller i's valuation (asking price) for each spectrum.

What the auctioneer benefits from this auction is the difference between incomes from buyers and payments to sellers. We will give concrete utility calculation of each participant for our spectrum auction scheme in the next part.

3. Design Details of TBMAH

Design and implementation details of the truthful bilateral multiunit auction scheme with support of heterogeneous networks (TBMAH) proposed by us is composed of the following components.

3.1. Buyer Grouping Method

In order to utilize spectrum efficiently, we divide nodes which can share the same spectrum into groups. According to the coverage-based interference model we adopt, any two nodes within the same group are not interfering with each other. Buyer grouping problem can be transformed into the problem of finding chromatic number or maximum independent set of a graph, which is NP-hard and there is no efficient algorithm till now. Many approximate algorithms have been proposed, and we will make brief introduction of each algorithm and detailed comparison between them in Section 4.1.

3.2. Bidding Series Generation

After forming potential buyers into groups with a certain grouping algorithm, we generate bidding series for each bidding group. Details of bidding series generation algorithm is described as Algorithm 1, in which two notations are defined as follows.

• (i)

Set $G=\{G_i\hspace{0.17em}|\hspace{0.17em}1\le i\le \lambda \}$ is a collection of bidding groups, which are real participants of the auction.

(ii)

Set $\Pi =\{{\pi }_i\hspace{0.17em}|\hspace{0.17em}1\le i\le \lambda \}$ is a collection of bidding series, which is a two-dimensional vector with λ rows and T columns, each element ${\pi }_i^j\hspace{0.17em}\hspace{0.17em}(1\le i\le \lambda ,1\le j\le T)$ of Π represents the amount of money that bidding group $G_i$ would like to pay if j items allocated to it.

Algorithm 1: Bidding series generation algorithm.

(1) Input: Buyer group set G with each element $G_i$

  consists of a certain number of nonconflict potential

  buyers.

(2) Output: Bids of each group $G_i$ in buyer group set G.

(3) Initialize $\Pi =\varphi$ before the algorithm starts.

(4) for $G_i$ in G do

(5) Traverse each buyer $B_j\hspace{0.17em}\hspace{0.17em}(1\le j\le |G_i|)$ in group $G_i$ and

     find the largest amount of resources requested by

     members of this group and denotes it with $l_i$ .

(6)  for $k=1$ to $l_i$ do

(7)   Symbol $total=0$ and $p_i^k$ denotes the net

      increasing resource amount and least unit

      spectrum price willing to pay by this group

      when k resources assigned.

(8)   for each buyer $B_j\hspace{0.17em}\hspace{0.17em}(1\le j\le |G_i|)$ in group $G_i$ do

(9)    if $\lfloor (k-1)/B_j^w\rfloor +1=\lfloor k/B_j^w\rfloor$ then

(10)         $total\hspace{0.17em}\hspace{0.17em}+=B_j^w$

(11)     if $p_i^k>B_j^p$   then

(12)        $p_i^k\leftarrow B_j^p$

(13)        end if

(14)    end if

(15)    end for

(16)     ${\pi }_i^k\leftarrow {\pi }_i^{k-1}+total\times p_i^k$

(17)     end for

(18)     for $k>l_i$ do

(19)    ${\pi }_i^k\leftarrow {\pi }_i^{l_i}$

(20)     end for

(21)     Push ${\pi }_i$ into Π

(22) end for

As described in Algorithm 1, we first check the largest amount of resources requested by each group. For any $k<l_i$ resource, divide the k resource into channels of buyer $B_j$ . If k is wide enough to accommodate one more channel of buyer $B_j$ , the net increasing bid of group $G_i$ should be accumulated with the money that buyer $B_j$ declares to pay, that is, $B_j^w\times p_i^k$ , in which $p_i^k$ denotes the least unit spectrum price willing to pay by members of this group when k resources assigned. Assigning redundant resource is meaningless for this group, so they are not likely to pay more if allocated more resources than what they demanded. It can be calculated that time complexity of Algorithm 1 equals to $O(\lambda \times N)$ , in which λ and N are numbers of bidding groups and potential buyers, respectively. Obviously, its space complexity is $O(\lambda \times T)$ , which equals to size of bidding series set Π.

3.3. Winners Determination

Our winners determination algorithm is composed of two parts, namely, winning buyers determination and winning sellers determination respectively.

3.3.1. Winning Buyers Determination

With bidding series of competitive groups and the number of resources on sale in one auction period, the auctioneer assigns spectrum with the goal of maximizing total revenues from these bidders, which would lead to maximized number of transacted resources. Variable ${\mathrm{\Psi }}_n^t\hspace{0.17em}\hspace{0.17em}(1\le n\le \lambda ,1\le t\le T)$ is defined as the maximal revenue that can be obtained when n bidders waiting for allocation and t resources left;

${\Psi }_n^t=\stackrel{t}{\underset{i=0}{\max }}\left({\pi }_n^i+{\Psi }_{n-1}^{t-i}\right).$

(1)

In which symbol ${\pi }_n^i$ means the amount of money which bidding group $G_n$ would like to pay if it can be allocated with i resources.

We solve this problem with dynamic programming algorithm and record each intermediate state with an auxiliary two-dimensional array $\mathrm{\Psi }$ for avoiding duplicated computations. Variable ${\mathrm{\Omega }}_i^j$ denotes the optimal amount that should be allocated to bidding group $G_i$ when j resource left and ${\mathrm{\Psi }}_i^j$ means the corresponding maximal revenue. From descriptions of Algorithm 2, it is obvious that time complexity of winning buyer algorithm is $O(\lambda \times T^2)$ and space complexity equals to $O(\lambda \times T)$ , where symbol λ and T-denote the size of bidding group set G and the amount of available resources, respectively.

Algorithm 2: Winning Buyer determination algorithm.

(1) Input: Bidding series generated in Section 3.2 for bidding group

   set G and the number of resources T for sale.

(2) Output: Assignment for each group $G_i$ in buyer group

   set G, those bidding groups with the amount of

   allocated resources larger than 0 are winners.

(3) Initialize temporary two-dimensional vector $\mathrm{\Omega }$ with λ

   rows and T columns.

(4) Update this array with the following procedure:

(5) for   $i=1$ to λ do

(6)    for $j=1$ to T do

(7)     Find the proper k resources allocated to buyer

        group $G_i$ that makes revenue maximized when

        there are i buyer groups and j resources left.

(8)     for $k=1$ to j do

(9)       if ${\pi }_i^k+{\mathrm{\Psi }}_{i-1}^{j-k}>{\mathrm{\Psi }}_i^j$ then

(10)         ${\mathrm{\Psi }}_i^j\leftarrow {\pi }_i^k+{\mathrm{\Psi }}_{i-1}^{j-k}$

(11)          ${\mathrm{\Omega }}_i^j\leftarrow k$

(12)        end if

(13)   end for

(14)      end for

(15) end for

(16) Initialize final assignment result R with size of λ and set

   temporary variable $j=0$ .

(17) for $i=\lambda$ to 1  do

(18)   $N_i={\mathrm{\Omega }}_i^{T-j}$ , $j+=R_i$

(19) end for

3.3.2. Winning Sellers Determination

Our winning seller determination follows what McAfee proposed in [10], which is a VCG scheme in nature and commonly used in truthful auction. Sort sellers by their bidding price in nondecreasing order first, then find the maximal possible argument k with seller's asking price smaller than buyer's promising price, and the first $k-1$ sellers are winners.

3.4. Pricing

Corresponding to winners determination, our pricing mechanism also consists of two components.

3.4.1. Costs of Buyers

Before charging each single buyer, we need to calculate firstly how much should one bidding group $G_i$ pay for the k resources assigned to it, then compute each buyer's charge with different k. The pricing algorithm for each group with k resources allocated is stated as Algorithm 3 shows.

Algorithm 3: Pricing algorithm for bidding groups.

(1) Input: Bidding series generated in Section 3.2 for bidding groups

  set G and assignment solution R produced in

  Algorithm 2, the amount of current available

  spectrum resource T.

(2) Output: Pricing scheme $C_i^k$ for group $G_i$ with k

   resources allocated.

(3) Derive net increasing bid ${\mathrm{\Delta }}_i^k$ of group $G_i$ with k

   resources allocated from neighboring elements of

   bidding series Π.

(4) for   $G_i$ in G  do

(5)  for   $k=l_i$ to 1  do

(6)    ${\mathrm{\Delta }}_i^k={\pi }_i^k-{\pi }_i^{k-1}$

(7)  end for

(8) end for

(9) for   $G_i$ in G  do

(10)   for   $k=1$ to $R_i$   do

(11)   Replace ${\pi }_i^k$ with zero to produce new bidding

      series ${\Pi }^{\prime }$ and calculate out new net increasing

      bidding series ${\mathrm{\Delta }}^{\prime }$ .

(12)   Substitute ${\Pi }^{\prime }$ and available resource T into

      Algorithm 2, generate a new assignment $R^{\prime }$ .

(13)   Initialize temporary variables $rev1$ and $rev2$ with

      zeros. Accumulate $rev1$ and $rev2$ with revenues

      from other bidding groups when group $G_i$ is absent from

      or participates in the auction, respectively.

(14)   for   $j=1$ to λ do

(15)    for   $t=1$ to $R_j^{\prime }$   do

(16)      $rev1+={{\mathrm{\Delta }}^{\prime }}_j^t$

(17)    end for

(18)    if   $j\ne i$ then

(19)     for   $t=1$ to $R_j$ do

(20)       $rev2+={\mathrm{\Delta }}_j^t$

(21)     end for

(22)    else

(23)     for   $t=1$ to $R_j$ do

(24)      if   $t\ne k$ then

(25)        $rev2+={\mathrm{\Delta }}_j^t$

(26)      end if

(27)     end for

(28)    end if

(29)   end for

(30)   Charge of bidding group $G_i$ with k resources

       allocated equals to the difference of revenues

       obtained under these two situations.

(31)       $C_i^k=rev1-rev2$

(32)  end for

(33) end for

According to descriptions of Algorithm 3, after deriving net increasing bid of each group $G_i$ with k resources assigned from initial bidding series generated in Algorithm 1, we borrow the similar pricing scheme from VCG truthful auction, that is to say, charge of each player in a VCG auction equals to the harm he caused in the auction. It can be seen that due to call of Algorithm 2, time complexity of Algorithm 3 becomes $O({\lambda }^2\times T^2)$ , and space complexity is also $O(\lambda \times T)$ for storing return values.

Charge of each buyer $B_j$ in group $G_i$ can be computed with the following equation:

$p_{ij}={\displaystyle \sum }_{k=1,k\text{\%}{B}_j^w=0}^{\min \left(N_i,B_j^n\times B_j^w\right)}\frac{C_i^k}{{\Delta }_i^k}\times p_i^k\times B_j^w.$

(2)

In (2), we accumulate charge of buyer $B_j$ with different k which meets $1\le k\le \min \hspace{0.17em}(N_i,B_j^n\times B_j^w)$ and is exactly divisible by $B_j^w$ . Expression $C_i^k/{\mathrm{\Delta }}_i^k$   means the scaling factor between real charge and promising bid of group $G_i$ with k resources allocated, and $p_i^k$ is the least price of unit spectrum resource used in bidding series generation Algorithm 1.

Consequently, the utility that buyer $B_j$ of bidding group $G_i$ gains from unit spectrum resource can be calculated with the following equation:

$\begin{array}{cc}\hfill U_{ij}& =\hspace{0.17em}\hspace{0.17em}\frac{\left(\hspace{0.17em}\hspace{0.17em}{B}_{ij}-p_{ij}\hspace{0.17em}\hspace{0.17em}\right)}{B_j^w}\hspace{0.17em}\hspace{0.17em}\hfill \\ \hfill & \hspace{0.17em}\hspace{0.17em}={\displaystyle \sum }_{k=1,k\text{\%}{B}_j^w=0}^{\min \left(N_i,B_j^n\times B_j^w\right)}\left(1-\frac{C_i^k}{{\Delta }_i^k}\right)\times p_i^k>0.\hfill \end{array}$

(3)

As $C_i^k$ represents the real charge of group $G_i$ with k resources allocated, from calculation of $C_i^k$ in Algorithm 3, we know that $C_i^k$ is the critical value of net increasing bid ${\mathrm{\Delta }}_i^k$ . According to definition of critical value and Theorem 3.3 in [9], if bidding group $G_i$ wants to win the auction and allocated with k resources, its net increasing bid ${\mathrm{\Delta }}_i^k$ must be larger than the critical value $C_i^k$ , that is, $C_i^k<{\mathrm{\Delta }}_i^k$ . Moreover, each buyer is sane enough and will not pay more money without being allocated with more resources, so it is obvious that $U_{ij}>0$ .

3.4.2. Revenues of Sellers

For the sellers side auction, we simplify McAfee's double auction into single side auction. Revenues of each seller $S_i$ is calculated with the following equation:

$P_i=S_i^n\times {S^{\prime }}_k^p.$

(4)

In (4), $S_i^n$ denotes the number of resources which seller $S_i$ sold, and ${S^{\prime }}_k^p$ is the kth sorted price for unit spectrum resource. Utility of seller $S_i$ equals to

$U_i=S_i^n\times \left({S^{\prime }}_k^p-S_i^p\right)>0.$

(5)

As sellers are sorted in nondecreasing order by their bidding price and seller $S_i$ wins the auction, so it can be concluded that ${S^{\prime }}_k^p>S_i^p$ and $U_i>0$ .

3.5. Complexity Analysis

With detailed descriptions above, our spectrum auction scheme TBMAH can be summarized in the following steps.

Step 1.

Accumulate total number of available resource T declared by potential sellers. Substitute T into Algorithm 1 to generate bidding series.

Step 2.

Substitute bidding series Π generated by Algorithm 1 and T into Algorithm 2 to determine final winning buyers.

Step 3.

Substitute bidding series Π and the optimal assignment result with T available resources into Algorithm 3 to produce pricing scheme for each bidding group and individual buyer.

Step 4.

Accumulate charge of each bidding group and revenue of each seller. For the auctioneer, if the total revenues from winning buyers are not less than payments to winning sellers, the auctioneer finishes the auction process with an extra profit, otherwise decrease T by 1 and go back to Step 2.

So time complexity of our scheme TBMAH is $O({\lambda }^2\times T^3)$ , and space complexity is $O(\lambda \times T)$ . As our spectrum auction scheme TBMAH targets secondary spectrum market within certain area, so the number of bidding groups λ cannot be too large and the complexity is acceptable.

Theorem 1.

For each bidding group $G_i$ , sum of charges of its group members is equal to accumulation of $C_i^k$ with different k, that is,

$\begin{array}{cc}\hfill {\displaystyle \sum }_{j=1}^{\left|G_i\right|}{p}_{ij}& ={\displaystyle \sum }_{j=1}^{\left|G_i\right|}\hspace{0.17em}{\displaystyle \sum }_{k=1,k\text{\%}{B}_j^w=0}^{\min \left(N_i,B_j^n\times B_j^w\right)}\frac{C_i^k}{{\Delta }_i^k}\times p_i^k\times B_j^w\hfill \\ \hfill & ={\displaystyle \sum }_{k=1}^{\min \left(N_i,l_i\right)}{C}_i^k.\hfill \end{array}$

(6)

Proof.

Expression ${\sum }_{j=1}^{|G_i|}{p}_{ij}$ denotes sum of charges of winning buyers in group $G_i$ , according to (2) and bidding series generation Algorithm 1, for each $1\le k\le \min \hspace{0.17em}(N_i,B_j^n\times B_j^w)$ , equation ${\sum }_{j=1,k\text{\%}{B}_j^w=0}^{|G_i|}{p}_i^k\times B_j^w={\mathrm{\Delta }}_i^k$ exists. So it can be concluded that sum of charges of winning buyers is equal to ${\sum }_{k=1}^{\min \hspace{0.17em}(N_i,l_i)}{C}_i^k$ , in which $N_i$ is the amount of spectrum allocated to group $G_i$ , and $l_i=\max \hspace{0.17em}(B_j^n\times B_j^w\hspace{0.17em}|\hspace{0.17em}1\le j\le |G_i|)$ denotes the largest amount of resources requested by members of group $G_i$ . This theorem states that charges of members of each group is equivalent to accumulation of $C_i^k$ with different k in this group.

TBMAH is executed iteratively, during a certain auction period, utility of the auctioneer equals to

$U={\displaystyle \sum }_{i=1}^{\lambda }{\displaystyle \sum }_{j=1}^{\left|G_i\right|}{p}_{ij}-{\displaystyle \sum }_{i=1}^{k-1}{P}_i={\displaystyle \sum }_{i=1}^{\lambda }{\displaystyle \sum }_{k=1}^{\min \left(N_i,l_i\right)}{C}_i^k-{\displaystyle \sum }_{i=1}^{k-1}{P}_i.$

(7)

The first term means total earnings from winning buyers, and the second term indicates total payments to winning sellers, if $U\ge 0$ , the auctioneer will stop the auction, otherwise, continues to attempt to trade less spectrum resources.

3.6. Proof of Economic Properties

3.6.1. Individual Rationality

We prove individual rationality of winning buyers and winning sellers, respectively. If charges of all winning buyers are not bigger than their bids and revenues of all winning sellers are not less than their expected earnings, we say that they are rational.

Proof.

The difference between real charged value of buyer $B_j$ in group $G_i$ and his promising bid equals

${\eta }_{ij}=-U_{ij}<0.$

(8)

According to (3) and Algorithm 1, we know that $U_{ij}>0$ , so ${\eta }_{ij}<0$ , that is to say, each buyer $B_j$ of group $G_i$ is rational and will not be charged more than what he promises.

For each winning seller, the clearing price is the kth bidding price and sellers are sorted by their bidding price in nondecreasing order, so winning sellers are payed more than what they desire.

Individuals in summary, both buyers and sellers are rational in our spectrum auction scheme-TBMAH.

3.6.2. Truthfulness

In this section, we try to prove that any bidding buyer $B_j$ cannot improve its utility by bidding untruthfully, that is to say, bidding truthfully is a dominant strategy for each potential buyer. We examine four possible cases one by one when bidder $B_j$ bids truthfully or untruthfully as in Table 1.

Table 1

Case	1	2	3	4
Untruthful	L	L	W	W
Truthful	L	W	L	W

Proof.

Case 1.

Either bidding truthfully or untruthfully in this case will make buyer $B_j$ lose the auction, so buyer $B_j$ will be charged zero under both situations and his utility remains to be 0.

Case 2.

According to our winning buyers determination method as described in Algorithm 2, TBMAH always tries to maximize its revenue from potential buyers during spectrum allocation. So it is easy to infer that our auction scheme is monotonic, that is to say, there is no winner becoming a loser by raising his bid. In this case, buyer $B_j$ loses when he bids untruthfully and wins when he bids truthfully, so his untruthful bid ${B^{\prime }}_j^p$ must meet ${B^{\prime }}_j^p<B_j^p$ , because our auction is individual rational for each winning buyer, so every winner's utility is nonnegative; however, its utility equals to zero when he bids untruthfully and loses the auction.

Case 3.

For the same reason of monotonicity of our auction scheme, this case only happens when ${B^{\prime }}_j^p>B_j^p=V_j$ . Suppose that $B_j^p$ is not the lowest bidding price of unit spectrum, according to our bidding series generation method in Algorithm 1, there must be a price $p<B_j^p$ which is used for calculating bidding series. When buyer $B_j$ bids untruthfully with ${B^{\prime }}_j^p$ , bidding series and final assignment result should not change, so buyer $B_j$ loses again. However, this is in contradiction with the fact that buyer $B_j$ wins by bidding higher. So our hypothesis does not hold and $B_j^p$ is the lowest bid when he bids truthfully. Let symbol δ denote the net increasing amount of group $G_i$ with k resources assigned, according to definition of critical value, the following inequation must exist

$\begin{array}{cc}\hfill {\Delta }_i^k<C_i^k<{{\Delta }^{\prime }}_i^k& ⟹\delta \times B_j^p<C_i^k<\delta \times {p^{\prime }}_i^k\hfill \\ \hfill & ⟹B_j^p<\frac{C_i^k}{\delta }<{p^{\prime }}_i^k.\hfill \end{array}$

(9)

In the above inequation, $B_j^p$ means the estimated value $V_j$ of buyer $B_j$ , ${p^{\prime }}_i^k$ is the least unit spectrum price used for calculating bidding series,   $C_i^k/\delta$   is the clearing price of unit spectrum. So when buyer $B_j$ wins by bidding higher than its true value, his utility becomes $V_j-C_i^k/\delta$   which is negative and less than the utility when he bids truthfully which equals to zero.

Case 4.

In this case, no matter buyer $B_j$ bids truthfully or not, he always win the auction. According to our pricing scheme in Algorithm 3, winner $B_j$ will be charged with the same value which equals to his critical value under both situations. So his utility which is defined as the difference between his estimated value and payment is invariant.

In summary, neither bids lower nor higher purposely can bring extra utility, so each potential buyer has no motivation to bid untruthfully and bidding truthfully becomes his dominating strategy.

Proof of truthfulness for sellers side in TBMAH is similar to McAfee double auction, for the sake of saving space we omit this part, anyone who wants to see details, please refer to [10].

3.6.3. Ex-Post Budget Balance

From descriptions in Section 3.5, it is easy to find that the auctioneer stops spectrum auction process when its income is not less than outcome, so TBMAH keeps ex-post budget balance and the final transacted resources T is maximal under current bidding functions of potential buyers.

4. Experimental Results

In this section, we first make comparisons between different grouping algorithms, then discuss all kinds of possible scenarios encountered in practical spectrum auction and study the impact of different distributions, and finally we do some experiments with real networks.

4.1. Grouping Algorithms

Recall that each bidding group which consists of potential buyers is real participant of our spectrum auction, TBMAH. We make brief introduction of 6 buyer grouping algorithms in the following part. Potential buyers with coverage radius that equals to 50 are uniformly distributed within area $1000\hspace{0.17em}\text{m}\times 1000\hspace{0.17em}\text{m}$ , and each potential buyer with one circle coverage stands for a network. Network scale varies from 10 buyers 1 seller to 100 buyers 10 sellers. Experimental results are averaged over 500 times for each network size.

• (i)

Stripe: this algorithm first partitions interested area into stripes with each stripe $\sqrt{3}d/2$   wide (where d is the radius of unit disk). Then it finds an optimal coloring scheme for each stripe with maximal flow or maximal bipartite matching algorithm. Combine colors of adjacent stripes from left to right to obtain the final coloring scheme of the graph [11].

(ii)

Max-IS: Max-IS recursively picks a node which has the minimal size of maximum independent set, pushes it into current independent set and Repeats this procedure until all nodes are processed [12].

(iii)

Greedy-U: to form a group, it recursively chooses a node which has the minimal degree in current conflict graph and eliminates the chosen node and its neighbors and updates degree values of remaining nodes [13].

(iv)

Greedy: it is the same as Greedy-U except that it chooses the nodes based on degree values of original conflict graph without updating degree of nodes [13].

(v)

Rand: It randomly chooses a node and tries to allocate one channel while satisfying nonconflict constraints.

(vi)

Lexicographic: this algorithm orders vertices first by their X- and then by their Y-coordinates, then colors each unit disk one by one according to their coverage area. Two disks with identical color are in the same group [14].

Performance of different grouping algorithms are measured with reusability which is defined as the average number of nodes in each group. Standard deviation of reusability characterizes uniformity among different groups. The X-coordinates of both figures are case index of different network scale. From Figure 1(a) we can see that reusability of Greedy-U and Greedy algorithm are relatively lower than other four algorithms. Result shown in Figure 1(b) tells us that standard deviation of Stripe is minimum among all these algorithms, which states that Stripe groups potential buyers evenly than any other algorithms.

Figure 1

Group with different algorithms.

4.2. Performance Comparisons in Different Scenarios

In a practical spectrum auction, auction pattern can be single-unit homogeneous, single-unit heterogeneous, multiunit homogeneous, and multiunit heterogeneous. However, TRUST can only support single-unit homogeneous, for the sake of comprehensive and fair comparisons with our scheme we make minor extensions of TRUST. For supporting heterogeneous channel width, we extend TRUST by dividing the sorted potential sellers into segments and considering each segment as a super seller, with size of each segment equals to the maximal demanding channel width. Asking price of each super seller equals to sum of asking price of sellers in this segment. Accordingly, we normalize each buyer's demanding channel width with the maximal demanding channel width and modify their bidding price with a scaling factor. So TRUST becomes a single-unit homogeneous auction with each unit size equal to the maximal possible channel width instead of 1. For multiunit scenario, we firstly duplicate nodes whose requested channel amount $B_j^n$ larger than 1, now each image node has only one spectrum request. Then reconstruct the graph and any two images of the same node conflict with each other. So multiunit scenario is successfully transformed into single-unit case.

We assume that both sellers' asking prices and buyers' bids are uniformly distributed. Experimental parameters of each seller's asking price $S_i^p$ , each buyer's requested amount $B_j^n$ , bidding price $B_j^p$ , and channel width $B_j^w$ are located within intervals $[\mathrm{1,4}]$ , $[\mathrm{1,5}]$ , $[\mathrm{3,7}]$ , and $[\mathrm{1,4}]$ , respectively. For validating scalability of TBMAH, we study performances with different network size varies from 10 buyers 5 sellers to 200 buyers 100 sellers. Experimental results under each case are averaged over 500 times.

For single-unit homogeneous scenario, each buyer can only demand one unit spectrum resource, channel width of all potential buyers are identical. According to our bidding series generation algorithm described in Algorithm 1, bid of each group equals to the product of least buyer's bidding price for each spectrum resource, channel width, and group size. Each winning group will be charged with its critical bidding value [9]. So in this scenario, our spectrum auction scheme TBMAH is degraded to TRUST. Experimental result also validates that the number of resources transacted of TBMAH is the same as that of TRUST in this scenario, so we do not show result of this case. However, for the other three scenarios which are commonly seen in practical auction, TBMAH outperforms extended version of TRUST with Stripe grouping algorithm, as can be seen in Figure 2. The X-coordinate values are still case index of different network scales. In Figure 2(b), the reason of extended version of TRUST exceeds TBMAH at the beginning is that increasing nodes by duplicating nodes with request large than 1 is favor of trade with sellers. Moreover, trades with different grouping algorithms obtain similar results, and we omit results of other grouping algorithms for the sake of saving space.

Figure 2

TBMAH versus TRUST in different scenarios.

4.3. Impact of Distribution

We study the impact of bidding price, requested amount, and heterogeneous channel width distribution on transaction. For bid distribution experiment, buyer's bidding price and seller's asking price are uniformly distributed within interval $[\mathrm{1,5}]$ and $[p_{\min \hspace{0.17em}},5]$ , which parameter $p_{\min \hspace{0.17em}}$ changes from 0.5 to 5. For buyer requested amount and heterogeneous channel width distribution experiments, parameters $a_{\max \hspace{0.17em}}$ and $w_{\max \hspace{0.17em}}$ change from 1 to 10, respectively. Other parameters not mentioned are set identically to those in Section 4.2. All of these three experiments adopt a network topology with 100 buyers and 50 sellers, both TBMAH and TRUST are set to support multiunit heterogeneous channel width auction, experimental results are averaged over 500 times.

From Figure 3(a) we can see that with seller's asking price increasing from 0.5 to 5, the number of resources transacted of both TBMAH and TRUST decreases due to elevation of spectrum price goes against transaction. With the amount of spectrum buyer requested increases from 1 to 10 in Figure 3(b), the transacted amount of both TBMAH and TRUST increases at the beginning due to abundant free spectrum resources and relative few requests, then both curves go flat because of reaching system's maximal capacity and not being able to accommodate any more requests. With buyer's requested channel width increases, the number of resources transacted of TBMAH rises then becomes saturated. While the number of resources transacted of TRUST rises at the beginning due to oversupply. With increase of requested channel width, the number of super sellers decreases and asking prices of them increase, so the number of successful trade of extended version of TRUST declines afterwards.

Figure 3

TBMAH versus TRUST with different distributions.

4.4. Comparisons with Real Network

Besides making detailed comparisons between TBMAH and TRUST with simulation networks, we also study their performances with real networks. We use locations of real cellular base stations available in FCC public GIS database [15], experimental parameters are set the same as that of experiment in Section 4.2, and experimental results are averaged over 500 times. The number of sellers is 50, both TBMAH and TRUST are set to support multiunit heterogeneous channel width auction and the number of potential buyers varies from 10 to 100.

Figure 4 shows that TBMAH outperforms TRUST. With the increasing number of potential buyers, the number of transacted resources of both TBMAH and TRUST increases and gets saturated finally. It is obvious that due to limited available resources, the number of buyers required to get TBMAH saturated is less than that of TRUST. This is because that it is unnecessary for TBMAH to format diverse channel widths with the largest one and reconstruct the graph by making mirrors of nodes whose requested amount of resources larger than 1.

Figure 4

TBMAH versus TRUST with real networks.

5. Conclusion

We propose a truthful bilateral multiunit auction with characteristic of supporting heterogeneous networks (TBMAH) in this paper. We firstly describe spectrum auction problem and introduce considerable factors of designing and implementing a practical spectrum auction, then show details of bidding series generation, winners determination, and pricing algorithms in our auction scheme. Results of both simulation and real networks experiments show that TBMAH outperforms TRUST on the whole, especially in different scenarios, TBMAH trades more spectrum resources than TRUST by 13.01% in average. In future work, we will consider using aggregate interference effects instead of coverage areas to determine whether two base stations conflict.