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, debtorcreditor 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.
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 PUSU 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, debtorcreditor 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 noncooperative Bayesian game. We further investigate these games with the help of coalitional game theory
[12]
and noncooperative 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 reputationbased 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 sensingtransmission 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
w_{i}
and
v_{i}
respectively, and denote the total available spectrum in this episode by
B
. We also assume that for any
i
,
w_{i}
≤
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.
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
w_{i}
and its first bid
b_{i}
, where
b_{i}
is calculated according to its valuation.
Step 3: The FC tells each SU the information of all SUs including:
w_{i}
,
b_{i}
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
S_{k}
reports its final bid
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
S_{k}
obtains the spectrum with probability
The FC then charges all members of the winner.
We provide some notes on the proposed auction: In step 2, first bid
b_{i}
reflects real spectrum valuation of SU
_{i}
in form of token.
b_{i}
may exceed its token storage
α_{i}
and is not necessarily identical to the final payment of SU
_{i}
. For instance, if
b_{i}
>
α_{i}
and SU
_{i}
failed to get help from other SUs, the final payment of SU
_{i}
=
α_{i}
. In step 5, coalition
S_{k}
report both its final bid
and the division in order to tell the FC how to calculate its winning probability and how to charge its members if
S_{k}
wins. Obviously
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 noncooperative 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 mergeandsplit 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
nontransferable 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
. Nonempty subsets of
N
are called
coalitions. A collection
is any family
C
= {
C
_{1}
,
C
_{2}
,…,
C_{l}
} of mutually disjoint coalitions, and
l
is called its size. If additionally
C_{j}
=
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}
,…,
R_{l}
} and
T
= {
T
_{1}
,
T
_{2}
,…,
T_{m}
} 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
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
R_{i}
∈
R
by
u_{i}
(
R
). Pareto order is defined as
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
is a function which associates with each partition
R
some partitioned subsets of the grand coalition
N
. A partition
P
= {
P
_{1}
,
P
_{2}
,…,
P_{l}
} of
N
is
stable if no group of players have an incentive to leave
P
when they can only form the collections allowed by
.
[13]
presents some defection functions such as
_{c}
and
_{hp}
.
_{c}
allows formation of all collections in the grand coalition while
_{hp}
allows formation of all P homogeneous partitions in the grand coalition. In other words, a partition
P
is
_{hp}
stable, if no players in
P
have an incentive to leave
P
through mergeandsplit (we will introduce this rule later) to form other partitions, while a partition
P
is
_{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}
w_{i}
to be large as possible while ∑
_{i}
_{∈}
_{S}
w_{i}
≤
B
holds, for every coalition
S
. According to the auction mechanism, a suitable utility function is given by
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
where
R_{i}
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
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
u_{i}
(
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}
u_{i}
(
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}
,…,
T_{k}
} →
where
⊲ {
T
_{1}
,
T
_{2}
,…,
T_{k}
}
Definition 6
: Split Rule:
→ {
T
_{1}
,
T
_{2}
,…,
T_{k}
} where {
T
_{1}
,
T
_{2}
,…,
T_{k}
} ⊲
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.,
) to start so that this SU is given some advantage in competition. The head invites other SUs to join in its coalition
S_{h}
in a certain order. If an invited SU rejects the invitation, the head turns to the next SU. The merging ends once
S_{h}
reaches bandwidth demand restriction (i.e., ∑
_{i}
_{∈}
_{Sh}
w_{i}
=
B
) or no SU can join in
S_{h}
with a mutual benefit. Then the FC appoints an SU j ∈
N
∖
S_{h}
as the new head and start the merging among
N
∖
S_{h}
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
P^{final}
of the set of all SUs is formed when the algorithm terminates.
We present some notes on the algorithm. The
v
(
S
) and
u_{i}
(
S
) we proposed have a significant fall at the edge ∑
_{i}
_{∈}
_{S}
w_{i}
=
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}
},
S_{3}
will not exclude any of its member. Otherwise
S_{3}
would not be formed in the first place. This property implies essentially the proposed algorithm has deployed a complete mergeandsplit because even if we allow coalitions to split after
P^{final}
is formed, no change will occur in
P^{final}
. So all conclusions of mergeandsplit 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
S_{h}
that maximizes its own utility. Denoting the set of SUs which belong to previous heads’ coalitions by
S_{pre}
, the current head aims to find
Solving this optimization problem is NPcomplete 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
∖
S_{pre}
) decreasingly with regard to payment per unit bandwidth (
). Without loss of generality, we assume
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
P^{final}
composed of disjoint independent coalitions of SUs. The stability of
P^{final}
can be investigated using the concept of defection function
in
Definition 4
.
Theorem 1
: Every partition obtained from our proposed coalition formation algorithm is
_{hp}
stable.
Proof
: A
_{hp}
stable can be considered as a state where no coalition has an incentive to alter the partition through mergeandsplit. The termination of any mergeandsplit is evidently
_{hp}
stable. And we have explained that essentially our algorithm has deployed a complete mergeandsplit in subsection B. Therefore the resulting partition
P^{final}
is
_{hp}
stable.
Before we discuss
_{c}
stability, we provide some properties of a
_{c}
stable partition proved by the authors of
[14]
.

1) Acstable partition may not exist.

2) If acstable partition exists, it ishpstable. And it is the unique outcome of every iteration of the merge and split rules.

3) If it exists, thecstable partitionPis ⊲maximal, i.e.,P⊲R, ∀R≠P.
Theorem 2
: If the
_{c}
stable partition exists, our proposed coalition formation algorithm will converge to this unique
_{c}
stable partition. Otherwise, the proposed algorithm converges to one of the
_{hp}
stable partitions.
Proof
: It can be proved by
Theorem 1
and property 2).
To demonstrate the
_{c}
stability and
_{hp}
stability explicitly, we introduce two examples.
Example 1
: We assume there are 3 SUs. Their bandwidth demands
w_{1}
=4,
w_{2}
=3,
w_{3}
=2. If total available bandwidth is
B
=4, the
_{c}
stable partition exists, i.e.,
P
= {{
SU
_{1}
},{
SU
_{2}
}, {
SU
_{3}
}}. If
B
=5, the
_{c}
stable partition exists, i.e.,
P
= {{
SU
_{1}
},{
SU
_{2}
,
SU
_{3}
}}. Our proposed algorithm guarantees to converge to
P^{final}
=
P
.
Example 2
: We assume there are 4 SUs.
w_{1}
=3,
w_{2}
=3,
w_{3}
=3,
w_{4}
=2, and
b_{1}
=4,
b_{2}
=3,
b_{3}
=2,
b_{4}
=1. We also assume the SUs can afford their bids. If
B
=5,
_{c}
stable partition does not exist and we have three
_{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
P^{final}
=
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,
where
R_{i}
is data rate of SU
_{i}
,
γ_{i}
is signalnoiseratio. With a low
γ_{i}
,
w_{i}
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
.
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]
:
where
P_{i}
,
P_{j}
are transmission power of SU
_{i}
and SU
_{j}
respectively and
h_{i}
,
h_{j}
,
h_{ij}
,
h_{ji}
are channel gains shown in
Fig. 3
. Notice that in the relay time slot SU
_{i}
and SU
_{j}
share
w_{i}
+
w_{j}
spectrum in their separate transmissions, therefore SU
_{i}
actually achieves a data rate (bits/s):
In this paper we assume both SU
_{i}
and SU
_{j}
know the relay data rate
R_{r}
through some mechanism, however SU
_{j}
does not know direct transmission data rate of SU
_{i}
(
R_{i}
).
Cooperation between SU_{i} and SU_{j}
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
f_{k}
(
R_{k}
), where
R_{k}
is the data rate. If SU
_{k}
assumes it has a probability of
to win in the auction,
f_{k}
(
R_{k}
) must satisfy the following equations due to the fact that each SU prefers to consume all tokens it earns if the episodes end.
where
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
w_{k}
and SNR
γ_{k}
, then
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:
In an episode, SU
_{k}
determines spectrum demand
w_{k}
, estimates
R_{k}
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 noncooperative game and noncooperative 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:
where
T^{m}
is the total token amount of coalition S will pay if the offer is accepted. Notice that
T^{m}
−
T
=
b_{j}
−
α_{j}
.
f_{i}
^{1}
(∙) is the inverse function of
f_{i}
(∙) and
f_{i}
^{1}
(
T^{m}
−
T
) can be replaced by
The expected utility of SU
_{j}
can be written
The offer SU
_{j}
proposes will be accepted if and only if
u_{i}
(
θ
) ≥ 0, i.e.,
And SU
_{j}
attempts to maximize its utility
u_{j}
(
θ
), i.e., proposes the optimal
θ
^{*}
The problem here is SU
_{j}
does not know SU
_{i}
direct transmission data rate
R_{i}
. Without any prior knowledge, SU
_{j}
assumes
R_{i}
follows a distribution in [
K_{1}
,
K_{2}
], where 0 ≤
K
_{1}
<
K
_{2}
<
R_{r}
. We have the following theorem:
Theorem 3
: Let
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
Proof
: Write
as
Let
≥ 0, we have
Obviously if
≥ 0, (22) always holds. In that case
Therefore if
A
≥ 0, for any
, 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
T^{m}
−
T
will significantly increase the winning probability of the coalition (as well as its own) and SU
_{i}
takes this reminding.
If
A
˂ 0
˂ 0. Then
SU
_{j}
assumes
R_{i}
follows a uniform distribution in [
K_{1}
,
K_{2}
]. Denote by
p^{acpt}
(
θ
) the probability of offer is accepted. We have
It is a piecewise function. Notice that 0 ≤
K
_{1}
<
K
_{2}
<
R_{r}
, therefore
When
the utility of SU
_{j}
is
Differentiating (27) with respect to
θ
, we have
Evidently
θ
_{p}
in (20) is one of the two solutions of (28) and it maximizes
u_{j}
(
θ
) (without considering the boundary values). We can prove
θ
_{p}
> 0 and
u_{j}
(
θ
_{p}
) > 0 althrough we omit the proof here due to space limitation. However the relationship between
,
θ
_{p}
and
is not constant. Notice that for any
θ
∈ [0,
θ
_{p}
),
u'_{j}
(
θ
) > 0 and for any >
θ
_{p}
,
u'_{j}
(
θ
) < 0. Thus we have: if
θ
_{p}
≤
, the offer will never be accepted because
u_{j}
(
) = 0 and it decreases with
θ
; if
θ
_{p}
∈ (
,
),
θ
^{*}
=
θ
_{p}
; and if
θ
_{p}
≥
,
p^{acpt}
(
θ
) = 1,
u_{j}
(
θ
) decreases with
θ
, SU
_{j}
checks if
P
(
T^{m}
)(1 −
)
R_{j}
−
P
(
T
)
R_{j}
> 0. If it holds,
θ
^{*}
=
; 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
to meet its basic communication demand. If SU
_{i}
proposes a
θ
that results in a normalized data rate
lower than
, SU
_{j}
will reject this offer. SU
_{i}
knows this
exists, but does not know the value. Define utility of SU
_{j}
by
where
Notice the coalition is not yet in its complete form, therefore
T^{m}
represents the total payment of its current members if SU
_{j}
is funded. Substituting (30) into (29) we obtain
Utility of SU
_{i}
remains the same as in (13). SU
_{i}
attempts to maximize its utility without prior knowledge of
. Let (
p
(
T^{m}
) −
p
(
α_{j}
)) ⋅ [
R_{j}
(1 −
θ
) −
] > 0, we obtain
Denote
Evidently for any
θ
≥
θ
^{max}
,
R_{j}
(1 −
θ
) −
≤ 0, thereby offer will be rejected. SU
_{i}
assumes
θ
^{max}
follows a uniform distribution in [
K_{1}
,
K_{2}
], where 0 ≤
K
_{1}
<
K
_{2}
< 1. Now we rewrite utility of SU
_{i}
as
where
T
represents the total payment of current members (except SU
_{j}
) of the coalition and
Here we assume
R_{r}
>
R_{i}
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
(
T^{m}
)(
R_{r}
−
R_{i}
) > 0, therefore the optimal value
θ
^{*}
=
K
_{1}
.
2) If
K
_{1}
<
θ
<
K
_{2}
,
where
A
is defined in
Theorem 3
. Let
u'
_{i}
(
θ
) = 0, we obtain
that maximizes
u_{i}
(
θ
). If
θ
_{p}
≤
K
_{1}
,
θ
^{*}
=
K
_{1}
. If
K
_{1}
<
θ
_{p}
<
K
_{2}
,
θ
^{*}
=
θ
_{p}
. However
θ
_{p}
≥
K
_{2}
requires both
A
< 0 and
K
_{2}
≤
which results in
u_{i}
(
K
_{2}
) ≤ 0. Notice
u_{i}
(
θ
) 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 <
<
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 [
K_{1}
,
K_{2}
]. If
A
≥ 0, then 0 ≤
K
_{1}
<
K
_{2}
< 1 ; otherwise
Then the optimal value of proposed relay time fraction
θ
^{*}
can be obtained as follows: calculate
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
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
S_{1}
. After SU
_{2}
joins
S_{1}
,
S_{1}
needs one of SU
_{5}
, SU
_{6}
and SU
_{7}
. The member of
S_{1}
(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
S_{1}
; otherwise it remains uninvited. We assume SU
_{5}
fails to join
S_{1}
, so
S_{1}
will invite SU
_{6}
and its final form will be
S_{1}
= {SU
_{1}
, SU
_{2}
, SU
_{6}
}. In the next SU
_{3}
will be the new head and picks SU
_{4}
to join its coalition
S_{2}
. Again
S_{2}
tries to negotiate with SU
_{5}
. We assume SU
_{4}
and SU
_{5}
have a deal, hence SU
_{5}
joins
S_{2}
. The coalition formation terminates with
S_{1}
= {SU
_{1}
, SU
_{2}
, SU
_{6}
},
S_{2}
= {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
S_{1}
, then SU
_{5}
will not be the head of
S_{2}
. 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
S_{1}
(assume it is between SU
_{1}
and SU
_{6}
, and assume the negotiation is successful) is done. Therefore the final payments of coalitions are:
S_{1}
pays 24 tokens,
S_{2}
pays 21 and
S
_{3}
pays 3. The payment division inside
S_{1}
is: SU
_{1}
pays 11, SU
_{2}
pays 9 and SU
_{6}
pays 4. The payment division inside
S_{2}
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
R_{i}
= 1,
R_{j}
= 10,
R_{r}
= 10,
b_{i}
= 10,
p
(
T^{m}
) = 0.56,
p
(
T
) = 0.375,
T^{m}
= 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
K_{1}
and
K_{2}
([1 1.6] represents
K_{1}
= 1 and
K_{2}
= 1.6). Different estimations of
R_{i}
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
R_{i}
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
R_{i}
∈ [0.5 1.5], the negotiation will fail. So the cooperation will always introduce mutual benefit for SU
_{i}
and SU
_{j}
.
Utilities of cooperation between partners
To investigate the cooperation between a member of a coalition and its potential partner, we set
R_{i}
= 1,
R_{j}
= 1,
R_{r}
= 10,
= 0.8,
p
(
T^{m}
) = 0.55,
p
(
T
) = 0.444,
p
(
α_{j}
) = 0.022,
b_{i}
=20,
T^{m}
= 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
K_{1}
and
K_{2}
. Here
<
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 winwin situation.
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
w_{i}
,
R_{i}
/
w_{i}
and
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
Data rate for relay transmission
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.
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
w_{i}
, 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
w_{8}
,
w_{10}
and
w_{7}
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.
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 fullduplex communication.
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
"Geolocationaware resource management in cloud computingbased 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 contracttheoretic 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 contractbased approach,"
IEEE Transactions on Mobile Computing
13
(1)
174 
187
DOI : 10.1109/TMC.2012.231
Wang F.
,
Krunz M.
,
Cui S.G.
2008
"Pricebased 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 gametheoretic 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
(12)
209 
238
DOI : 10.1016/S00043702(99)000363
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 15
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