Advanced
Spectrum Allocation based on Auction in Overlay Cognitive Radio Network
Spectrum Allocation based on Auction in Overlay Cognitive Radio Network
KSII Transactions on Internet and Information Systems (TIIS). 2015. Sep, 9(9): 3312-3334
Copyright © 2015, Korean Society For Internet Information
  • Received : March 10, 2015
  • Accepted : July 18, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Wenhao Jiang
Wenjiang Feng
Yang Yu

Abstract
In this paper, a mechanism for spectrum allocation in overlay cognitive radio networks is proposed. In overlay cognitive radio networks, the secondary users (SUs) must first sense the activity of primary users (PUs) to identify unoccupied spectrum bands. Based on their different contributions for the spectrum sensing, the SUs get payoffs that are computed by the fusion center (FC). The unoccupied bands will be auctioned and SUs are asked to bid using payoffs they earned or saved. Coalitions are allowed to form among SUs because each SU may only need a portion of the bands. We formulate the coalition forming process as a coalition forming game and analyze it by game theory. In the coalition formation game, debtor-creditor relationship may occur among the SUs because of their limited payoff storage. A debtor asks a creditor for payoff help, and in return provides the creditor with a portion of transmission time to relay data for the creditor. The negotiations between debtors and creditors can be modeled as a Bayesian game because they lack complete information of each other, and the equilibria of the game is investigated. Theoretical analysis and numerical results show that the proposed auction yields data rate improvement and certain fairness among all SUs.
Keywords
1. Introduction
C ognitive radio (CR) technology is a promising solution to solve the problem of spectrum scarcity and low spectrum utilization associated to classical fixed spectrum assignment schemes [1] . Due to higher priority of primary users (PUs), secondary users (SUs) need to perceive the behavior of PUs in their assigned frequency bands and perform opportunistic spectrum access without or with minimal interference to them. Usually a user or a node trusted by all SUs (or a third party which shares no common interest with any SU) is introduced as an FC to collect the results of SUs’; perception. In this way the FC has a list of vacant spectrum bands which are available for a period of time.
The SUs want to access the vacant bands for transmission. How to allocate vacant bands among the SUs is one common problem in cognitive radios. To improve the spectrum efficiency, many works have been done [2 , 3] . In [2] the authors present a game theoretic model for spectrum sharing, where users seek to satisfy their quality of service demands in a distributed fashion. They also extend their model by considering the frequency spatial reuse, and consider the user interactions as a game upon a graph where players only contend with their neighbors. There are a large number of works that attempt to solve the spectrum allocation problem with economical tools such as game theory [4] , contract theory [5 , 6] , auction [7] , pricing [4 , 8] . Pricing is often used when the seller knows precisely the value of the resource being sold. In [4] the authors formulate an oligopoly market consisting of a few firms and a consumer to investigate the pricing problem. By using a Bertrand game model, they analyze the impacts of several system parameters such as spectrum substitutability and channel quality on the Nash equilibrium and propose a distributed algorithms to obtain the solution for this dynamic game. In cases where the seller only knows limited information of the buyers’ valuations of the resource, contract is more effective because by motivating the buyers truthfully reveal their private valuations, the seller can optimally allocate the resource. In [5] the authors proposed a quality−price contract for the spectrum trading to allocate the spectrum. [6] exploits the incentive effect of cooperative spectrum sharing where SUs relay traffics PUs in exchange for dedicated spectrum access time for SUs’ own communications. The PU-SU interaction is modeled as a labor market and analyzed by contract theory. It must be stressed that these mechanisms should guarantee the spectrum bands are allocated according to SUs true valuations, which is called truthfulness [9] . Truthfulness is important because if SUs can lie to obtain benefits, efficiency and fairness cannot be achieved. Auction mechanism is a suitable approach when the seller has no knowledge about the value of the resource. Many auction mechanisms [7 , 10] have been studied because they guarantee truthfulness. However fairness is often ignored or simplified [10] . The authors of this paper believe that SUs’ contribution to the CR network (such as contribution of cooperative sensing) should be rewarded and assigning higher priority of spectrum bands to more contributed SUs is a kind of fairness [11] .
In this paper, we propose a spectrum allocation mechanism similar to auction mechanisms. We first quantify the contribution of every SU in the cooperative sensing and reward it with tokens. Then the FC holds an auction for the vacant bands. An SU may use its tokens to bid for spectrum bands in the following period or it may save the tokens for future use. Since the entire vacant bands are considered as one commodity, the SUs may need to cooperate and form coalitions. During the coalition forming process, debtor-creditor relationship may occur among the SUs because of their limited payoff storage. A debtor may ask a creditor for payoff help, and in return provides the creditor with a portion of transmission time to relay data for the creditor. We model the coalition forming process as a coalition formation game and the negotiations between debtors and creditors as a non-cooperative Bayesian game. We further investigate these games with the help of coalitional game theory [12] and non-cooperative game theory, respectively.
The remainder of the paper is organized as follows: Section 2 presents the system model and the proposed auction. Section 3 presents the investigation of coalition formation in the auction through a coalitional game theoretic perspective. Section 4 introduces the potential cooperation among SUs and analyzes the Bayesian equilibria within. In Section 5 we validate our auction mechanism and our theoretical analysis through simulations. And Section 6 concludes the paper.
2. System model and proposed auction
- 2.1 Network model
We consider a CR network consists of N SUs and M potential unoccupied channels. Each SU detects the PU activities on one or more channels according to its different detection performances on different channels. SUs sense the spectrum bands cooperatively and periodically for infinite iterations. An FC is introduced in the network and we assume it could communicate with all CUs via a perfect common control channel (CCC). The FC categorizes the sensing results and obtains global decisions on the channel status. In this work we also assume that the FC is the manager of all vacant channels and it is in charge of spectrum allocation. The FC also adopts some algorithm (such as algorithm in [11] , or reputation-based algorithm) to quantify each SU’s contribution to the spectrum sensing, then pays tokens accordingly. If there are any available channels for the SUs in a sensing-transmission round, we address this round as an episode. In an episode each SU either demands some spectrum for transmission or has no data to transmit. The valuations of these spectrum for different SUs may vary due to the fact that even the same bandwidth may produce different transmission performances to different SUs. Here we assume the spectrum valuation of an SU is based on its data rate. We focus on the spectrum allocation problem in one episode. We denote spectrum demand and valuation of SU i by wi and vi respectively, and denote the total available spectrum in this episode by B . We also assume that for any i , wi B (i.e., the total available spectrum can satisfy at least one SU). A critical problem here is how to allocate the spectrum among the SUs according to their demand and valuation, while satisfying some fairness criterion.
PPT Slide
Lager Image
Transmission time division in cooperation
- 2.2 Token spectrum auction
We propose a token spectrum auction to address this problem. In this auction, the SUs bid for the spectrum using the tokens they earned in this episode or they saved from previous episodes. Because the currency here is the token which represents the contribution to cooperative sensing, the SUs always have a limited budget and thus they cannot always pay according to their valuations. We denote the token storage of SU i by αi . The token spectrum auction is deployed as follows.
Step 1: The FC announces there is a total bandwidth of B and it will be auctioned as one commodity.
Step 2: Each SU reports its spectrum demand wi and its first bid bi , where bi is calculated according to its valuation.
Step 3: The FC tells each SU the information of all SUs including: wi , bi and token storage αi . Then the FC asks the SUs to form coalitions.
Step 4: The SUs try to form coalitions. There might be negotiations between the SUs.
Step 5: All coalitions report their bid information to the FC. In particular, coalition Sk reports its final bid
PPT Slide
Lager Image
as well as the exact division of this bid among its members.
Step 6: The FC allocates the available spectrum to a coalition in a statistical manner where coalition Sk obtains the spectrum with probability
PPT Slide
Lager Image
The FC then charges all members of the winner.
We provide some notes on the proposed auction: In step 2, first bid bi reflects real spectrum valuation of SU i in form of token. bi may exceed its token storage αi and is not necessarily identical to the final payment of SU i . For instance, if bi > αi and SU i failed to get help from other SUs, the final payment of SU i
PPT Slide
Lager Image
= αi . In step 5, coalition Sk report both its final bid
PPT Slide
Lager Image
and the division in order to tell the FC how to calculate its winning probability and how to charge its members if Sk wins. Obviously
PPT Slide
Lager Image
It can be observed that coalitions with higher final bids will have higher probabilities to obtain the spectrum. The potential negotiations in step 4 will be discussed in later sections.
We propose such an auction for the following reasons:
  • 1) Coalitions with higher final bids will have higher probabilities to obtain the spectrum. Therefore in general, this auction improves the spectrum efficiency.
  • 2) Unlike the first− price or second− price auction, there is a chance to win the spectrum for SUs with low valuation or low token storage. They have an incentive to form coalitions and compete with others. Therefore the auction encourages every SU to take part in the competition.
  • 3) By using tokens as currency instead of money, the auction guarantees certain fairness. SUs which make more contribution earn more tokens, therefore hold better positions in the spectrum competition. This motivates SUs to make more effort and it is positive for the network.
  • 4) The proposed auction allows SUs to negotiate and cooperate in the coalition formation. This introduces flexibility to the spectrum allocation and further improves spectrum efficiency.
With the token spectrum auction given, we will investigate the behavior of SUs in the auction. We formulate the coalition formation process as a coalition formation game and study it in Section 3. The negotiations and cooperation between SUs are modeled as a non-cooperative game and will be investigated in Section 4.
3. Coalition formation game
In this section we formulate and analyze the coalition formation using coalition game theory. We do not consider the potential negotiations between SUs here through these negotiations might introduce some impact to the coalition formation. Before we start, some coalition game theory concepts must be introduced.
- 3.1 Coalition formation concepts
Researchers have been highly interested in coalition formation game [13 - 15] . The goal is to find algorithms for characterizing the coalitional structures that form in a network where the grand coalition is not optimal. In [14] , the authors present a generic framework for coalition formation where coalitions form and break through two simple merge-and-split rules. Follow their works, we present some definitions.
Definition 1 : A coalitional game ( N , v ) is said to have a transferable utility (TU) if the value v ( S ) can be arbitrarily apportioned between the coalition’s players. Otherwise, the coalitional game has a non-transferable utility (NTU) and each player will have its own utility within coalition S .
Definition 2 : Let N = {1, 2, …, n } be a fixed set of players called the grand coalition . Non-empty subsets of N are called coalitions. A collection is any family C = { C 1 , C 2 ,…, Cl } of mutually disjoint coalitions, and l is called its size. If additionally
PPT Slide
Lager Image
Cj = N , the collection C is called a partition of N .
Definition 3 : A comparison relation ⊲ is defined to compare two collections R = { R 1 , R 2 ,…, Rl } and T = { T 1 , T 2 ,…, Tm } that are partitions of the same set A (same players in R and T ). R T implies that the way R partitions A is preferred to the way T partitions A based on a criterion.
Many criteria (referred to as orders ) can be adopted to compare collections or partitions. In general they are divided into two types: coalition value orders and individual value orders. Coalition value orders compare two collections by using the value of the coalitions inside these collections. For instance, the utilitarian order [16] compares two collections where R T indicates
PPT Slide
Lager Image
On the other hand individual value orders compare two collections using the player’s utility, not the coalition value. An important individual order is the Pareto order. For a collection R , denote the utility of a player i in a coalition Ri R by ui ( R ). Pareto order is defined as
PPT Slide
Lager Image
with at least one strict inequality for a player j . Pareto order is an adequate comparison relation for NTU games and we will show later the coalition formation here is a NTU game in subsection 3.2 A.
We further introduce some concepts that will later be used to analyze the stability of a partition.
Definition 4 : A defection function
PPT Slide
Lager Image
is a function which associates with each partition R some partitioned subsets of the grand coalition N . A partition P = { P 1 , P 2 ,…, Pl } of N is
PPT Slide
Lager Image
-stable if no group of players have an incentive to leave P when they can only form the collections allowed by
PPT Slide
Lager Image
.
[13] presents some defection functions such as
PPT Slide
Lager Image
c and
PPT Slide
Lager Image
hp .
PPT Slide
Lager Image
c allows formation of all collections in the grand coalition while
PPT Slide
Lager Image
hp allows formation of all P- homogeneous partitions in the grand coalition. In other words, a partition P is
PPT Slide
Lager Image
hp -stable, if no players in P have an incentive to leave P through merge-and-split (we will introduce this rule later) to form other partitions, while a partition P is
PPT Slide
Lager Image
c -stable, if no players in P have an incentive to leave P through any operation to form other collections in the grand coalition.
- 3.2 Coalition formation in token spectrum auction
- A. Game formation
To investigate the behavior of the SUs in the token spectrum auction, we formulate the coalition formation process as a coalition formation game so that we can refer to coalition game theory. The process can be modeled as a ( N , v ) where N is the set of players and v is the utility function or value of a coalition.
In the proposed auction we aim to encourage players (i.e., SUs) to form coalitions to compete the bandwidth B . Each coalition is supposed to use the spectrum as much as possible, however the total spectrum demand should not exceed available bandwidth B . So we expect ∑ i S wi to be large as possible while ∑ i S wi B holds, for every coalition S . According to the auction mechanism, a suitable utility function is given by
PPT Slide
Lager Image
where p ( S ) is the probability that coalition S wins the spectrum, R ( S ) is the total data rate of coalition S and Res ( S ) is a restriction function. Again we emphasize that in this section we do not consider the potential negotiations and deals in the coalition formation. Therefore
PPT Slide
Lager Image
PPT Slide
Lager Image
where Ri is the date rate of SU i . If the total demand of a coalition exceeds available bandwidth B , the division among the coalition members cannot be done. To avoid this, we define the restriction function as follows
PPT Slide
Lager Image
Obviously v ( S ) represents the expected total data rate of coalition S in the auction if the bandwidth division can be done among its members. Coalition S will always welcome new members as long as they do not violate the bandwidth demand restriction, since new members increase v ( S ) by increasing p ( S ) and R ( S ). We define utility of SU i in coalition S as
PPT Slide
Lager Image
ui ( S ) represents the expected data rate of SU i when SU i is in coalition S. Utility -∞ indicates that SU i will not have a positive data rate when bandwidth division cannot be done in S . -∞ is used to emphasize this circumstance should never occur and to match with the definition of v ( S ). In this way utility of each SU in coalition S is a portion of value of S , and v ( S ) = ∑ i S ui ( S ) . It can be easily observed that any rational coalition would like to invite an SU to join it as long as this SU does not violate the bandwidth demand restriction, and any SU prefers to accept one of the invitations than compete alone. We also notice that v ( S ) cannot be arbitrarily apportioned between the members because S cannot alter any member’s bandwidth demand. Therefore the game we formulated is a NTU game and Pareto order is suitable here.
- B. Coalition formation algorithm
We propose a coalition formation algorithm based on two simple rules addressed as “merge” and “split” which modify a partition T of SUs set N [14] .
Definition 5 : Merge Rule: { T 1 , T 2 ,…, Tk } →
PPT Slide
Lager Image
where
PPT Slide
Lager Image
⊲ { T 1 , T 2 ,…, Tk }
Definition 6 : Split Rule:
PPT Slide
Lager Image
→ { T 1 , T 2 ,…, Tk } where { T 1 , T 2 ,…, Tk } ⊲
PPT Slide
Lager Image
With these rules, multiple coalitions can merge into one coalition, and one coalition can split into multiple coalitions if merging/splitting operation yields a better collection based on the order ⊲. Here ⊲ is the Pareto order, therefore coalitions will merge (split) only if at least one SU strictly improves its utility through this merging (splitting) without harming other SUs’ utilities.
Remark 1 : Suppose ⊲ is a comparison relation. Then every iteration of the merge and split rules terminates.
With the support of Remark 1, an algorithm can be designed based on merge and split rules without considering if it terminates. The coalition formation algorithm works as follows: At the beginning, every SU is a coalition. The FC picks an SU (referred to as the head) to start the merging process. For instance, FC may appoint the SU with the highest “bid per unit bandwidth” (i.e.,
PPT Slide
Lager Image
) to start so that this SU is given some advantage in competition. The head invites other SUs to join in its coalition Sh in a certain order. If an invited SU rejects the invitation, the head turns to the next SU. The merging ends once Sh reaches bandwidth demand restriction (i.e., ∑ i Sh wi = B ) or no SU can join in Sh with a mutual benefit. Then the FC appoints an SU j ∈ N Sh as the new head and start the merging among N Sh again. The algorithm is repeated until every SU has made its merging decisions, i.e., an SU has either played the role of head or accepted an invitation. A final partition Pfinal of the set of all SUs is formed when the algorithm terminates.
We present some notes on the algorithm. The v ( S ) and ui ( S ) we proposed have a significant fall at the edge ∑ i S wi = B , leading to an important property of the coalitions that once two coalitions decide to merge, any of their members will not be split from the large coalition. For instance, if S 1 = { SU 1 , SU 2 } and S 2 = { SU 3 , SU 4 } decide to merge into S 3 = { SU 1 , SU 2 , SU 3 , SU 4 }, S3 will not exclude any of its member. Otherwise S3 would not be formed in the first place. This property implies essentially the proposed algorithm has deployed a complete merge-and-split because even if we allow coalitions to split after Pfinal is formed, no change will occur in Pfinal . So all conclusions of merge-and-split can apply to our algorithm. It should also be noticed that the merging can be simplified because the head can filter the SUs according to bandwidth demand restriction after every acceptance of its invitation. The head only invites qualified SUs and the invited SUs have no incentive to reject in accordance with merge rule. Therefore the time of coalition formation can be significantly reduced.
In practice, every head forms a coalition Sh that maximizes its own utility. Denoting the set of SUs which belong to previous heads’ coalitions by Spre , the current head aims to find
PPT Slide
Lager Image
Solving this optimization problem is NP-complete and the complexity increases significantly with the number of SUs N . For small N , (7) may be solved by exhaustive search or iteration method. However for large N there is no practical method to find optimal solutions. We introduce a simple method to help the head with this problem. First the head arranges the available SUs (i.e., ∀ i N Spre ) decreasingly with regard to payment per unit bandwidth (
PPT Slide
Lager Image
). Without loss of generality, we assume
PPT Slide
Lager Image
The head checks if an SU satisfies the bandwidth demand restriction in the above order and invites the first qualified SU (assume it is SU j ). Then the head updates its bandwidth demand restriction and continue the search from SU j . This process repeats until the bandwidth demand restriction cannot be satisfied by any SU. The method may not obtain optimal solution for (7), but it significantly reduce time and communication overheads while yielding an acceptable performance in many scenarios. It must be stressed that the method does not take into account the circumstances where SUs negotiate and make deals. Modified method for those scenarios will be introduced in Section 4.
- C. Stability analysis
The result of the proposed algorithm is a network partition Pfinal composed of disjoint independent coalitions of SUs. The stability of Pfinal can be investigated using the concept of defection function
PPT Slide
Lager Image
in Definition 4 .
Theorem 1 : Every partition obtained from our proposed coalition formation algorithm is
PPT Slide
Lager Image
hp -stable.
Proof : A
PPT Slide
Lager Image
hp -stable can be considered as a state where no coalition has an incentive to alter the partition through merge-and-split. The termination of any merge-and-split is evidently
PPT Slide
Lager Image
hp -stable. And we have explained that essentially our algorithm has deployed a complete merge-and-split in subsection B. Therefore the resulting partition Pfinal is
PPT Slide
Lager Image
hp -stable.
Before we discuss
PPT Slide
Lager Image
c -stability, we provide some properties of a
PPT Slide
Lager Image
c -stable partition proved by the authors of [14] .
  • 1) Ac-stable partition may not exist.
  • 2) If ac-stable partition exists, it ishp-stable. And it is the unique outcome of every iteration of the merge and split rules.
  • 3) If it exists, thec-stable partitionPis ⊲-maximal, i.e.,P⊲R, ∀R≠P.
Theorem 2 : If the
PPT Slide
Lager Image
c -stable partition exists, our proposed coalition formation algorithm will converge to this unique
PPT Slide
Lager Image
c -stable partition. Otherwise, the proposed algorithm converges to one of the
PPT Slide
Lager Image
hp -stable partitions.
Proof : It can be proved by Theorem 1 and property 2).
To demonstrate the
PPT Slide
Lager Image
c -stability and
PPT Slide
Lager Image
hp -stability explicitly, we introduce two examples.
Example 1 : We assume there are 3 SUs. Their bandwidth demands w1 =4, w2 =3, w3 =2. If total available bandwidth is B =4, the
PPT Slide
Lager Image
c -stable partition exists, i.e., P = {{ SU 1 },{ SU 2 }, { SU 3 }}. If B =5, the
PPT Slide
Lager Image
c -stable partition exists, i.e., P = {{ SU 1 },{ SU 2 , SU 3 }}. Our proposed algorithm guarantees to converge to Pfinal = P .
Example 2 : We assume there are 4 SUs. w1 =3, w2 =3, w3 =3, w4 =2, and b1 =4, b2 =3, b3 =2, b4 =1. We also assume the SUs can afford their bids. If B =5,
PPT Slide
Lager Image
c -stable partition does not exist and we have three
PPT Slide
Lager Image
hp -stable partitions. They are P 1 = {{ SU 1 , SU 4 },{ SU 2 }, { SU 3 }}, P 2 = {{ SU 1 },{ SU 2 , SU 4 }, { SU 3 }} and P 3 = {{ SU 1 },{ SU 2 }, { SU 3 , SU 4 }} respectively. Our proposed algorithm converges to Pfinal = P 1 .
4. Potential cooperation between SUs
- 4.1 Cooperation model
Potential cooperation may exist in coalition formation. Some SUs may have insufficient token storage to afford their spectrum valuation and some SUs may have large token storage but suffer bad channel gains between their transmitters and receivers in this episode. These two types of SUs may cooperate to improve their transmission performance. Assume SU i has extra tokens and suffers a bad channel gain. According to Shannon formula,
PPT Slide
Lager Image
where Ri is data rate of SU i , γi is signal-noise-ratio. With a low γi , wi increment leads to very limited data rate improvement. Therefore it is not wise for SU i to invest more tokens for more spectrum. On the other hand, we assume SU j is seeking token support from other SUs to improve its probability of obtaining its demand spectrum. If SU j is willing to share a portion of its transmission time to relay for SU i , then SU i might want to lend SU j some tokens in return. If the relay time slot and lent tokens satisfy both SU i and SU j , this cooperation will bring mutual benefits to both SUs. The cooperation is shown in Fig. 2 .
PPT Slide
Lager Image
Transmission time division in cooperation
We assume SU i and SU j transmit in the amplified and forward (AF) mode, SU i achieves a data rate (bits/s/Hz) [17] :
PPT Slide
Lager Image
where Pi , Pj are transmission power of SU i and SU j respectively and hi , hj , hij , hji are channel gains shown in Fig. 3 . Notice that in the relay time slot SU i and SU j share wi + wj spectrum in their separate transmissions, therefore SU i actually achieves a data rate (bits/s):
PPT Slide
Lager Image
In this paper we assume both SU i and SU j know the relay data rate Rr through some mechanism, however SU j does not know direct transmission data rate of SU i ( Ri ).
PPT Slide
Lager Image
Cooperation between SUi and SUj
Evidently, relay time fraction θ determines the benefit of both SU i and SU j , and a bargaining about θ will be introduced. Under the proposed auction mechanism, the form of this bargaining varies depending on whether SU i and SU j are in the same coalition when bargaining occurs. It is assumed SU i would not negotiate with members of other coalitions since financing them harms its own interest, however SU i tends to finance members of the same coalition (partners) or potential partners. We will discuss the cases where SU i bargains with partners and potential partners in later subsections, respectively.
- 4.2 Token consumption strategy
We investigate the token consumption strategy before discussing the bargaining cases because the lenders must take into account the value of the tokens they will lend. For different SUs, same tokens may have different values since earning powers are usually different. In the proposed auction mechanism, tokens represent contributions to the network and can only be used to purchase spectrum utilization opportunity. Consequently every SU has a function that maps its achievable data rate in an episode to respective estimated tokens (i.e., first bid). Denote this function of SU k by fk ( Rk ), where Rk is the data rate. If SU k assumes it has a probability of
PPT Slide
Lager Image
to win in the auction, fk ( Rk ) must satisfy the following equations due to the fact that each SU prefers to consume all tokens it earns if the episodes end.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the expected data rate of SU k during all episodes and βk is the average tokens SU k earns between two episodes. We assume SU k has knowledge on the distributions of spectrum demand wk and SNR γk , then
PPT Slide
Lager Image
can be easily obtained through Shannon formula and statistical method. Although there are many functions qualified, we adopt a simple linear function for the “data rate to token” mapping as follows:
PPT Slide
Lager Image
In an episode, SU k determines spectrum demand wk , estimates Rk and uses (12) to decide its first bid. Also, when SU k bargain with others, it validates whether data rate improvement introduced by cooperation is worth the tokens lent based on (12).
- 4.3 Bargain with a partner
If SU j is already a partner of SU i , they share common interest, i.e., spectrum winning probability. In this case, it is appropriate to assume that SU j offers a deal and SU i decides whether to accept. In particular, SU j proposes a relay time slot θ and SU i validates its utility and decides whether to accept. This is a non-cooperative game and non-cooperative game theory can be applied.
Rewrite the notation p ( S ) as p ( T ), where T is the total token amount coalition S pays. The utilities of the SU i and SU j based on data rate increment are defined as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
where Tm is the total token amount of coalition S will pay if the offer is accepted. Notice that Tm T = bj αj . fi -1 (∙) is the inverse function of fi (∙) and fi -1 ( Tm T ) can be replaced by
PPT Slide
Lager Image
The expected utility of SU j can be written
PPT Slide
Lager Image
The offer SU j proposes will be accepted if and only if ui ( θ ) ≥ 0, i.e.,
PPT Slide
Lager Image
And SU j attempts to maximize its utility uj ( θ ), i.e., proposes the optimal θ *
PPT Slide
Lager Image
The problem here is SU j does not know SU i direct transmission data rate Ri . Without any prior knowledge, SU j assumes Ri follows a distribution in [ K1 , K2 ], where 0 ≤ K 1 < K 2 < Rr . We have the following theorem:
Theorem 3 : Let
PPT Slide
Lager Image
when A ≥ 0, θ * = 0 and SU i will accept this offer. When A < 0, θ * can be obtained as follows:
  • 1) Iffor anyθ∈ [0,1] the offer will never be accepted.
  • 2) If
  • 3) Ifotherwiseθ*does not exist.
where
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof : Write
PPT Slide
Lager Image
as
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
≥ 0, we have
PPT Slide
Lager Image
Obviously if
PPT Slide
Lager Image
≥ 0, (22) always holds. In that case
PPT Slide
Lager Image
Therefore if A ≥ 0, for any
PPT Slide
Lager Image
, Prob(offer accepted) = 1. Evidently SU j wants θ to be as small as possible. Thus θ * = 0. In essence, this is a circumstance where SU j reminds SU i that increasing SU i ’s bid by Tm T will significantly increase the winning probability of the coalition (as well as its own) and SU i takes this reminding.
If A ˂ 0
PPT Slide
Lager Image
˂ 0. Then
PPT Slide
Lager Image
SU j assumes Ri follows a uniform distribution in [ K1 , K2 ]. Denote by pacpt ( θ ) the probability of offer is accepted. We have
PPT Slide
Lager Image
It is a piece-wise function. Notice that 0 ≤ K 1 < K 2 < Rr , therefore
PPT Slide
Lager Image
When
PPT Slide
Lager Image
the utility of SU j is
PPT Slide
Lager Image
Differentiating (27) with respect to θ , we have
PPT Slide
Lager Image
Evidently θ p in (20) is one of the two solutions of (28) and it maximizes uj ( θ ) (without considering the boundary values). We can prove θ p > 0 and uj ( θ p ) > 0 althrough we omit the proof here due to space limitation. However the relationship between
PPT Slide
Lager Image
, θ p and
PPT Slide
Lager Image
is not constant. Notice that for any θ ∈ [0, θ p ), u'j ( θ ) > 0 and for any > θ p , u'j ( θ ) < 0. Thus we have: if θ p
PPT Slide
Lager Image
, the offer will never be accepted because uj (
PPT Slide
Lager Image
) = 0 and it decreases with θ ; if θ p ∈ (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
), θ * = θ p ; and if θ p
PPT Slide
Lager Image
, pacpt ( θ ) = 1, uj ( θ ) decreases with θ , SU j checks if P ( Tm )(1 −
PPT Slide
Lager Image
) Rj P ( T ) Rj > 0. If it holds, θ * =
PPT Slide
Lager Image
; otherwise θ * does not exist. Therefore Theorem 3 is obtained.
- 4.4 Bargain with a potential partner
If the first bid of SU j is high but its token storage is relatively low, coalitions will consider whether to invite SU j carefully. If SU j cannot get token fund from others, its contribution to the coalition is negligible. In this circumstance, a coalition S must first figure out if any of its member would fund SU j before it decides whether to invite SU j . Therefore for any coalition member SU i , SU j is a potential partner.
For SU j , its low token storage introduces great disadvantage in its spectrum competition. First, coalition S is not complete when SU j bargains with it, so SU j does not know its final form. Second, SU j does not know if it will be invited by subsequent coalitions as well as their competition power. These uncertainties put SU j in a bad position in the bargaining, therefore it is appropriate to assume in this type of bargaining, SU i will propose an offer and SU j will decide whether to acept. It is natural to assume SU j has a minimum normalized data rate
PPT Slide
Lager Image
to meet its basic communication demand. If SU i proposes a θ that results in a normalized data rate
PPT Slide
Lager Image
lower than
PPT Slide
Lager Image
, SU j will reject this offer. SU i knows this
PPT Slide
Lager Image
exists, but does not know the value. Define utility of SU j by
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Notice the coalition is not yet in its complete form, therefore Tm represents the total payment of its current members if SU j is funded. Substituting (30) into (29) we obtain
PPT Slide
Lager Image
Utility of SU i remains the same as in (13). SU i attempts to maximize its utility without prior knowledge of
PPT Slide
Lager Image
. Let ( p ( Tm ) − p ( αj )) ⋅ [ Rj (1 − θ ) −
PPT Slide
Lager Image
] > 0, we obtain
PPT Slide
Lager Image
Denote
PPT Slide
Lager Image
Evidently for any θ θ max , Rj (1 − θ ) −
PPT Slide
Lager Image
≤ 0, thereby offer will be rejected. SU i assumes θ max follows a uniform distribution in [ K1 , K2 ], where 0 ≤ K 1 < K 2 < 1. Now we rewrite utility of SU i as
PPT Slide
Lager Image
where T represents the total payment of current members (except SU j ) of the coalition and
PPT Slide
Lager Image
Here we assume Rr > Ri because a potential partner is not yet a partner. If SU j cannot improve data rate of SU i through relaying, SU i will never fund SU j . We have
1) If θ K 1 , u' i ( θ ) = p ( Tm )( Rr Ri ) > 0, therefore the optimal value θ * = K 1 .
2) If K 1 < θ < K 2 ,
PPT Slide
Lager Image
where A is defined in Theorem 3 . Let u' i ( θ ) = 0, we obtain
PPT Slide
Lager Image
that maximizes ui ( θ ). If θ p K 1 , θ * = K 1 . If K 1 < θ p < K 2 , θ * = θ p . However θ p K 2 requires both A < 0 and K 2
PPT Slide
Lager Image
which results in ui ( K 2 ) ≤ 0. Notice ui ( θ ) increases with θ , so SU i would not assume θ max to be such a value. Therefore the estimation of θ max by SU i must satisfy 0 <
PPT Slide
Lager Image
< K 1 < K 2 < 1.
Based on the above discussion, we have the following theorem:
Theorem 4 : SU j assumes θmax follows a uniform distribution in [ K1 , K2 ]. If A ≥ 0, then 0 ≤ K 1 < K 2 < 1 ; otherwise
PPT Slide
Lager Image
Then the optimal value of proposed relay time fraction θ * can be obtained as follows: calculate
PPT Slide
Lager Image
If θp K 1 , θ * = K 1 ; otherwise θ * = θp .
- 4.5 Modified coalition formation and bidding
In Section 3 we introduced coalition formation without considering potential negotiations and cooperation among SUs. Now we take into account these factors and modify the coalition formation and bidding process. An instance shown in Table 1 is used to illustrate, where total available bandwidth B = 8
Instance for modified coalition formation and bidding
PPT Slide
Lager Image
Instance for modified coalition formation and bidding
Apparently, SU 1 is the first head that picks its coalition members. Denote the coalition of SU 1 by S1 . After SU 2 joins S1 , S1 needs one of SU 5 , SU 6 and SU 7 . The member of S1 (SU 1 and SU 2 ) negotiates with SU 5 respectively. If SU 5 makes a deal with either SU 1 or SU 2 , it joins S1 ; otherwise it remains uninvited. We assume SU 5 fails to join S1 , so S1 will invite SU 6 and its final form will be S1 = {SU 1 , SU 2 , SU 6 }. In the next SU 3 will be the new head and picks SU 4 to join its coalition S2 . Again S2 tries to negotiate with SU 5 . We assume SU 4 and SU 5 have a deal, hence SU 5 joins S2 . The coalition formation terminates with S1 = {SU 1 , SU 2 , SU 6 }, S2 = {SU 3 , SU 4 , SU 5 } and S 3 = {SU 7 }. It must be stressed that potential partners will not be chosen as heads. For instance, if SU 1 , SU 2 , SU 3 and SU 4 form coalition S1 , then SU 5 will not be the head of S2 . Instead SU 6 will be the head because it has the highest payment per bandwidth even if it is not funded. Before coalitions submit their bids, a negotiation inside S1 (assume it is between SU 1 and SU 6 , and assume the negotiation is successful) is done. Therefore the final payments of coalitions are: S1 pays 24 tokens, S2 pays 21 and S 3 pays 3. The payment division inside S1 is: SU 1 pays 11, SU 2 pays 9 and SU 6 pays 4. The payment division inside S2 is: SU 3 pays 8, SU 4 pays 12 and SU 5 pays 1. In the above, SU 5 was a potential partner for SU 4 therefore discussion in subsection 4.4 applies in their negotiation. SU 6 is a partner for SU 1 therefore discussion in subsection 4.3 applies.
5. Simulation results
In this section we validate the proposed auction mechanism through simulations. We first validate the mutual benefit in the cooperation, then simulate the spectrum allocation.
- 5.1 Mutual benefit in cooperation
We simulate and illustrate the mutual benefit in cooperation between two partners. We set Ri = 1, Rj = 10, Rr = 10, bi = 10, p ( Tm ) = 0.56, p ( T ) = 0.375, Tm = 25, T = 12. Fig. 4 shows the utilities with different relay time fraction θ proposed by SU j . The blue curves are utilities of SU j estimated by itself with different parameters K1 and K2 ([1 1.6] represents K1 = 1 and K2 = 1.6). Different estimations of Ri result in different θ * therefore influence the actual utilities of SU i and SU j . We see θ * of three different estimations are 0.2739, 0.2128 and 0.2490, respectively. The corresponding actual utilities are 0.25, -0.0553 and 0.1258 for SU i , 0.2840, 0.6231 and 0.4220 for SU j . Accurate estimations of Ri may produce relatively large data rate increment of SU j while inaccurate estimations may lead to larger data rate increment of SU i . Notice the cooperation will only be done when both u i > 0 and u j > 0, therefore when SU j assumes Ri ∈ [0.5 1.5], the negotiation will fail. So the cooperation will always introduce mutual benefit for SU i and SU j .
PPT Slide
Lager Image
Utilities of cooperation between partners
To investigate the cooperation between a member of a coalition and its potential partner, we set Ri = 1, Rj = 1, Rr = 10,
PPT Slide
Lager Image
= 0.8, p ( Tm ) = 0.55, p ( T ) = 0.444, p ( αj ) = 0.022, bi =20, Tm = 50, T = 40. Fig. 5 shows the utilities with different relay time fraction θ proposed by SU i . The blue curves are utilities of SU i estimated by itself with different parameters K1 and K2 . Here
PPT Slide
Lager Image
< K 1 < K 2 . Different estimations of θmax yield different θ * leading to different utilities of SU i and SU j . Three estimations provide three θ * at 0.1494, 0.1744 and 0.2 respectively. The corresponding actual utilities are 0.2278, 0.3403 and 0.4556 for SU i , 0.0242, 0.0122 and 0 for SU j . The offer with θ * = 0.2 will be rejected because u j = 0. Once the negotiation succeeds, the cooperation will lead to a win-win situation.
PPT Slide
Lager Image
Utilities of cooperation between a member and a potential partner
- 5.2 Token spectrum auction
We investigate the proposed token spectrum auction by studying a specific case with 10 SUs. The parameters of SUs are set as in Table 2 . In Table 2 , notation [5,7] presents the corresponding variable follows a uniform distribution in [5,7] . In every episode wi , Ri / wi and
PPT Slide
Lager Image
randomly generate a value in corresponding intervals. We also randomly generate relay data rate shown in Table 3 . We run the simulation 10 times and each simulation lasts 100 episodes.
Parameters of SUs
PPT Slide
Lager Image
Parameters of SUs
Data rate for relay transmission
PPT Slide
Lager Image
Data rate for relay transmission
Two contrastive spectrum allocation mechanisms are introduced, named random allocation and token optimal allocation. The random allocation randomly chooses a set of SUs under the condition that the total spectrum demand does not exceed the total available spectrum B in current episode. The token optimal allocation is deployed at the FC. The FC allocates the available spectrum to a set of SUs that maximize its payoff (i.e., the FC aims to collect the maximum tokens in current episode).
Fig. 6 shows the average total data rate in every simulation. In our proposed auction mechanism, due to the randomness in the winner decision, it is possible that an "inefficient" coalition obtains the spectrum resulting in low data rates in some episodes. However this mechanism motivates the SUs with weak competition power. And the significant data rate gain in the relay transmissions in cooperation compensates the aforementioned data rate loss. In fact, averaging the "average total data rate" over 10 simulations we obtain 38.61, 35.85 and 35.39 for three mechanisms respectively. The proposed auction outperforms the other two.
PPT Slide
Lager Image
Average total data rate
Fig. 7 shows spectrum obtaining frequency of each SU. In token optimal allocation, SU 1 , SU 2 and SU 3 have very high obtaining frequencies because they earn more tokens every episode (i.e., high βi ). With low βi and relatively high spectrum demand wi , SU 6 and SU 10 show low frequencies (12.4 and 11.9 respectively), and may lose their incentive to participate the spectrum competition. In random allocation, SU 8 , SU 10 and SU 7 show high frequencies because w8 , w10 and w7 are significantly lower than others. The random allocation neglects the contributions of SUs represented by tokens and obliterates the SUs’ incentive to contribute the network. The proposed token auction shows balanced allocation where SU 1 obtains the highest frequency 52.3 and SU 10 obtains the lowest frequency 27.4. SUs with low βi improve their frequencies through cooperation. The data indicate all SUs have a fair and acceptable chance to obtain the spectrum in accordance with their contributions.
PPT Slide
Lager Image
Spectrum obtaining frequency of each SU
6. Conclusions
This paper proposes a spectrum allocation mechanism based on auction in overlay cognitive radio network. The proposed mechanism quantities contribution of each SU and pays them tokens. The SUs form coalitions and pay tokens to compete the available spectrum in an episode. SUs with low token storage may borrow tokens from other SUs, in return providing relay transmission for the lenders. We model the negotiation between the borrowers and the lenders as Bayesian games because of the incomplete information, and investigate the behaviors and equilibria in these games. Theoretical analysis and simulation results indicate both borrower and lender benefit from cooperation. Simulation results also show our proposed auction yields satisfactory data rate and fairness.
BIO
Wenhao Jiang received his BS degree in electrical and information engineering and MS degree in electrical and communication engineering from College of Communication Engineering, Chongqing University (CQU), Chongqing, China in 2009 and 2012 respectively. He is currently studying for his Ph.D. degree in communication and information system at College of Communication Engineering, CQU. His research interests include cognitive radio network and wireless network.
Wenjiang Feng received his Ph.D. degree in electrical engineering from Chongqing University in 2000. Currently, he is a professor at the college of communication engineering in Chongqing University. His research interests fall into the broad areas of communication theory, wireless communication.
Yang Yu received his BS degree in electrical and information engineering Chongqing University in June 2012. He is currently pursuing MS degree at College of Communication Engineering, CQU. His research fields include wireless network communication and full-duplex communication.
References
Akyildiz I.F. , Lee W.Y. , Vuran M.C. , Mohanty S. 2006 "Next generation/dynamic spectrum access/cognitive radio wireless networks: A survey," Computer Networks 50 (13) 2127 - 2159    DOI : 10.1016/j.comnet.2006.05.001
Southwell R. , Chen X. , Huang J.W. 2014 "Quality of service games for spectrum sharing," IEEE Journal on Selected Areas In Communications 32 (3) 589 - 600    DOI : 10.1109/JSAC.2014.1403008
Rawat D.B. , Shetty S. , Raza K. 2014 "Geolocation-aware resource management in cloud computing-based cognitive radio networks," International Journal of Cloud Computing 3 (3) 267 - 287    DOI : 10.1504/IJCC.2014.064765
Niyato D. , Hossain E. 2008 "Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of nash equilibrium, and collusion," IEEE Journal on Selected Areas In Communications 26 (1) 192 - 202    DOI : 10.1109/JSAC.2008.080117
Gao L. , Wang X.B. , Xu Y.Y. , Zhang Q.A. 2011 "Spectrum trading in cognitive radio networks: A contract-theoretic modeling approach," IEEE Journal on Selected Areas In Communications 29 (4) 843 - 855    DOI : 10.1109/JSAC.2011.110415
Duan L.J. , Gao L. , Huang J.W. 2014 "Cooperative spectrum sharing: A contract-based approach," IEEE Transactions on Mobile Computing 13 (1) 174 - 187    DOI : 10.1109/TMC.2012.231
Huang J. , Berry R.A. , Honig M.L. 2006 "Auction-based spectrum sharing," Mobile Networks & Applications 11 (3) 405 - 418    DOI : 10.1007/s11036-006-5192-y
Wang F. , Krunz M. , Cui S.G. 2008 "Price-based spectrum management in cognitive radio networks," IEEE Journal Of Selected Topics In Signal Processing 2 (1) 74 - 87    DOI : 10.1109/JSTSP.2007.914877
Li C.L. , Liu Z. , Geng X.Y. , Dong M. , Yang F. , Gan X.Y. , Tian X.H. , Wang X.B. 2014 "Two dimension spectrum allocation for cognitive radio networks," IEEE Transactions on Wireless Communications 13 (3) 1410 - 1423    DOI : 10.1109/TWC.2014.012814.130577
Zhang Y. , Lee C. , Niyato D. , Wang P. 2013 "Auction approaches for resource allocation in wireless systems: A survey," IEEE Communications Surveys And Tutorials 15 (3) 1020 - 1041    DOI : 10.1109/SURV.2012.110112.00125
Rajasekharan J. , Koivunen V. 2015 "Cooperative game-theoretic approach to spectrum sharing in cognitive radios," Signal Processing 106 15 - 29    DOI : 10.1016/j.sigpro.2014.06.013
Saad W. , Han Z. , Debbah M. , Hjorungnes A. , Basar T. 2009 "Coalitional game theory for communication networks," IEEE Signal Processing Magazine 26 (5) 77 - 97    DOI : 10.1109/MSP.2009.000000
APT K.R. , WITZE A. 2009 "A generic approach to coalition formation," International Game Theory Review (IGTR) (03) 347 - 367    DOI : 10.1142/S0219198909002352
Apt K.R. , Radzik T. 2006 "Stable partitions in coalitional games," in eprint arXiv:cs/0605132 5132 -
Sandholm T. , Larson K. , Andersson M. , Shehory O. , Tohme F. 1999 "Coalition structure generation with worst case guarantees," Artificial Intelligence 111 (1-2) 209 - 238    DOI : 10.1016/S0004-3702(99)00036-3
Saad W. , Han Z. , Debbah M. , Hjorungnes A. , Basar T. "Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks," IEEE Infocom 2009 - IEEE Conference on Computer Communications, Vols 1-5 2009 2114 - 2122
Laneman J.N. , Tse D.N.C. , Wornell G.W. 2004 "Cooperative diversity in wireless networks: Efficient protocols and outage behavior," IEEE Transactions on Information Theory, vol. 50 (12) 3062 - 3080    DOI : 10.1109/TIT.2004.838089