第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
认知无线电网络中的联合功率和频谱分配算法.pdf
Journal of Systems Engineering and Electronics Vol. 22, No. 4, August 2011, pp.691–701
Available online at www.jseepub.com
Joint power and spectrum allocation algorithm in
cognitive radio networks
∗
Yutao Liu
, Xuezhi Tan, and Anna Auguste Anghuwo
Communication Research Center, Harbin Institute of Technology, Harbin 150080, P. R. China
Abstract: The spectrum sharing problem between primary and
cognitive users is mainly investigated. Since the interference for
primary users and the total power for cognitive users are con-
strained, based on the well-known water-filling theorem, a novel
one-user water-filling algorithm is proposed, and then the corre-
sponding simulation results are given to analyze the feasibility and
validity. After that this algorithm is used to solve the communica-
tion utility optimization problem subject to the power constraints in
cognitive radio network. First, through the gain to noise ratio for
cognitive users, a subcarrier and power allocation algorithm based
on the optimal frequency partition is proposed for two cognitive
users. Then the spectrum sharing algorithm is extended to multi-
user conditions such that the greedy and parallel algorithms are
proposed for spectrum sharing. Theory and simulation analysis
show that the subcarrier and power allocation algorithms can not
only protect the primary users but also effectively solve the spec-
trum and power allocation problem for cognitive users.
Keywords: cognitive radio, spectrum sharing, water-filling algo-
rithm, interference constraint, communication overhead.
DOI: 10.3969/j.issn.1004-4132.2011.04.020
1. Introduction
Frequency spectrum, which is the scarcest resource for
wireless communications, may become congested to ac-
commodate diverse types of users, applications and air in-
terfaces in the next generation wireless networks. In order
to solve this problem, regulatory bodies like the Federal
Communications Commission (FCC) in the United States
and the Ofcom in UK considered introducing the mecha-
nism of dynamic spectrum access, so that the secondary
(i.e., cognitive) users can exploit the frequency bands of
primary (i.e., licensed) users when imposing sever restric-
tions on the spectrum and transmission power, so as not
to cause any harmful interferences to the active primary
users [1].
Although the technologies for power control were
the
already adopted in traditional wireless networks,
Manuscript received January 20, 2010.
*Corresponding author.
This work was supported by the National Natural Science Foundation
of China (61071104) and the National High Technology Research and
Development Program (2008AA12Z305).
interference constraints (total interferences to the primary
users) in dynamic spectrum access were not taken into
account. The power control problem for multiple cogni-
tive users in spectrum sharing networks is actually a chan-
nel/subcarrier (with interference constraints) allocation
problem, which can be divided into two cases: joint power
and rate control and joint permission and power control.
The former one allocates as much as possible transmission
rate to each user based on some fair criteria [2−3], and the
latter one assumes that the transmission rate for all cogni-
tive users is fixed, and tries to let much more users access
to the network [4].
The well known water-filling algorithm solves the prob-
lem of maximizing the throughput for the frequency
composed of several subcarriers/sub-channels (such as a
frequency-selective channel, a set of orthogonal frequency
division multiplexing (OFDM) subcarriers) with a global
power constraint. In [5,6], based on a game-theoretic for-
mulation, the authors proposed a decentralized strategy in
order to find out the optimal pre-coding/multiplexing ma-
trices for a multipoint-to-multipoint communication sys-
tem composed of a set of wideband links sharing the same
physical resources. They proved the existence and unique-
ness of the Nash equilibrium and considered two alter-
native optimization problems. The iterative water-filling
power allocation algorithm for Gaussian interference chan-
nels was investigated in [7], and the system was formulated
as a non-cooperative game.
The resources allocation problem for one user usually
aimed at maximizing the throughput with a constraint to-
tal power, which can be solved by the traditional water-
filling theorem [8,9]. Thus, the data rate in each subcarrier
for the cognitive users could be obtained from the trans-
mission power assigned. The iterative water-filling algo-
rithm can also be applied to resources allocation for multi-
users. Under this condition, in addition to considering the
channel state of each subcarrier, the cognitive users need
to compete against other users for the resources. There
are two approaches for the dynamic resources (spectrum)
sharing, namely spectrum underlay and spectrum overlay
Journal of Systems Engineering and Electronics Vol. 22, No. 4, August 2011
692
[10−13]. The spectrum overlay increases the spectrum ef-
ficiency by granting cognitive users to opportunistically
use the idle frequency bands of primary users [12].
In
this case, the cognitive users can use the available sub-
carriers with no interference power constraints.
In con-
trast, the spectrum underlay permits simultaneous sharing
of all the frequency bands available among the primary and
cognitive users, while imposing severe restrictions on the
transmission power of the cognitive users, so as not to ex-
ceed the interference constraint of the primary users [13].
On this occasion, the strategy space for one user is cou-
pled with the others, which causes extra difficulties. Wu
et al. proposed a distributed multi-channel sharing algo-
rithm in [14,15], the non-cooperative game with coupled
constraints was firstly decomposed into two sub-problems:
a traditional parameterized game and a dual optimization
problem, and then it was solved by the water-filling theo-
rem. This mechanism solves the problem of spectrum al-
location with coupled strategies to some extent, however,
the selection of the dual factors depends heavily on expe-
rience, and the updating mechanism inevitable leads to a
much higher communication overhead.
In this paper, we present solutions for the underlay spec-
trum sharing problems in cognitive radio networks. Unlike
the present researches, only one cognitive user is promised
to access to the subcarrier (the primary spectrum is divided
into multiple subcarriers) sometime and somewhere. So
we can effectively improve the efficiency of spectrum us-
age while avoiding solving the non-cooperative game with
coupled strategies.
2. Network model and assumptions
2.1 System model
We consider a spectrum underlay-based wireless network
with both primary and cognitive users. The frequency
band for the primary users is B, and the total number of
cognitive users is N . Within the constraint of interference
power for the primary users, the cognitive users can ac-
cess to the primary users’ spectrum, so as to accomplish
their communication goals. For the cognitive users, the
available spectrum can be divided into M subcarriers. For
each subcarrier j ∈ M and M = {1, 2,··· , M}, its inter-
ference constraint is Ij, however, there is no interference
constraint when the subcarrier is idle.
In this paper, no
subcarrier can support the transmissions for more than one
user, i.e., pm,j · pn,j = 0, where pm,j is the mth user’s
transmission power in the jth subcarrier, m, n ∈ N and
N = {1, 2, . . . , N}.
2.2 Wireless transmission model
According to the channel state of each subcarrier, the trans-
mission rate of the cognitive users can be dynamically ad-
justed based on the channel quality. Assume the cognitive
users adopt x-quadrature amplitude modulation (QAM)
modulation and ideal phase detection, then the ith user’s
transmission rate in the jth subcarrier can be expressed as
a function of bit-error-rate (BER) and signal-to-noise ratio
(SNR) [16,17].
ri,j =
B
M log2(1 + Ki · γi,j)
(1)
where Ki denotes the ith user’s BER requirement, which
can be taken as the SNR gap between the x-QAM modu-
lation and the Shannon capacity [17]; γi,j =
is
the SNR, the thermal noise power for each subcarrier is as-
sumed to be the same, and equals to σ2. For the Rayleigh
fading channels, Ki can be expressed as
0.2/BERi − 1
Ki ≈
pi,jHi,j
1.5
(2)
σ2
.
For the additive white Gaussian noise (AWGN) channels,
Ki can be expressed as
Ki =
1.5
− ln(5 · BERi)
.
(3)
Assume the channel gain relates to the distance between
the cognitive transmitter and receiver, which can be ex-
pressed as
δ
d0
d
Hi,j = βi,jκi
where βi,j is the ith user’s preference coefficient for sub-
carrier j, which is related to the carrier frequency; κi =
λ
d0 denotes the antenna gain at d0 and d0 is the far field
4π
recommended distance of the antenna. δ is the path loss
parameter, in this paper, we choose δ = 3.
3. Power allocation for one-user
3.1 Problem formulation
In this paper, we mainly study the multi-subcarrier and
power allocation problems for spectrum sharing under the
AWGN channel, so as to obtain the optimal total commu-
nication utility. From (1), without loss of generality, the
ith user’s utility can be expressed as [3,8]
Mi
Ui = Ri =
Mi
s.t.
B
M log2(1 + Ki · γi,j)
j=1
pi,j Pi, pi,j 0
(4)
j=1
where Ri is the ith user’s transmission rate, Mi M de-
notes the number of subcarriers assigned to user i. In this
paper, the ith user’s transmission rate Ri and the utility Ui
are interchangeable. So the optimal objective is
Yutao Liu et al.: Joint power and spectrum allocation algorithm in cognitive radio networks
693
max
pi,j
U =
Ui =
B
M log2(1 + Ki · γi,j)
N
Mi
i=1
N
Mi
i=1
j=1
pi,j Pi, pi,j 0, ∀i ∈ N
s.t.
σ2 + pjHj,0 Ij, ∀j ∈ M and j is on
j=1
(5)
where pj is the cognitive user’s total transmission power
in the jth subcarrier, and Hj,0 is the channel gain from the
cognitive user’s transmitter to the primary base station in
subcarrier j.
Because each subcarrier can support only one cogni-
tive user besides the primary users, the spectrum sharing
problems come down to: the cognitive users appropriately
allocate transmission power to the subcarriers which they
obtained in order to optimize the utilities. Next, we first
overview the water-filling theorem, and then propose a
novel one-user water-filling algorithm to solve the power
allocation problem for the cognitive users.
For the ith cognitive user, assume its subcarrier set is
{1, 2, . . . , Mi}, from (4) we can obtain the transmission
power in each subcarrier.
Ij − σ2
Hj,0
,
μ − h−1
i,j
+
pi,j = min
(6)
where the first item in the bracket denotes the interfer-
ence constraint for primary users, (x)+ = max(x, 0).
μ = λ−1B/(M · ln 2) is the water-level, λ is the Lagrange
multiplier, and hi,j = KiHi,j/σ2 denotes the ith user’s
gain-to-noise ratio in the jth subcarrier.
3.2 Water-filling algorithm
Thus, the optimal transmission rate for the cognitive users
can be obtained by power water-filling (or water-pouring),
as we can see in Fig. 1. When h−1
i,j is smaller, the cor-
responding transmission power assigned to this subcarrier
is higher; as h−1
i,j increases, the transmission power is re-
duced simultaneously. Especially when h−1
i,j μ, because
of the poor channel state, it will assign no transmission
power in the jth subcarrier, i.e., the cognitive user does
not transmit signals in this subcarrier. Distinguish from
the traditional water-filling theorem, the interference con-
straint for the primary users should be taken into account
(e.g., subcarrier 2 and 4 in Fig. 1), i.e., the transmission
power should not exceed (Ij − σ2)/Hj,0 in subcarrier j
when the primary user is on.
Mi
Obviously, when the utility for the ith user is optimal,
pi,j = Pi, from (6) we can see that pi,j is a function of
j=1
the water-level μ, so the constraint can be expressed as
Mi
j=1
f(μ) =
Ij − σ2
Hj,0
,
Mi
j=1
min
pi,j − Pi =
+
μ − h−1
i,j
− Pi
(7)
where f is a monotonic increasing function of variable
μ (subject to the interference constraint, the monotonicity
can not be strict in some subcarriers). Therefore, we can
obtain μ from (7), in this way, we propose a novel one-user
water-filling algorithm as shown in Table 1.
Table 1 The one-user water-filling algorithm
Input: Mi, Hi,j , Hj,0∀j ∈ Mi, BERi, σ2 and f.
(i) Initialization: obtain the gain-to-noise ratio hi,j = KiHi,j /σ2.
(ii) Sort the subcarriers such that {h
−1
i,j } is in increasing order,
i.e., h
(iii) Set μ = h
−1
i,j h
−1
i,Mi and obtain the function value about f according
) > 0, set Mi = Mi − 1 and return to step
−1
i,j+1 for any j ∈ {1, . . . , Mi − 1}.
−1
i,Mi
(iv) Set num = x + 1, and then search the water-level
to (7). If f (h
(iii), otherwise, set x = Mi and go to step (iv).
μ ∈ (h
set num = x and obtain the final μ.
−1
i,x+1) according to f (μ) = 0. If μ < h
−1
i,x, h
−1
i,x+1,
(v) Obtain the transmission power transmission power strategies
according to (6).
Output: power allocation strategies pi,j and the number of allocated
subcarriers num.
Next, we’ll demonstrate the effectiveness of the one-
user water-filling algorithm. Assume the number of sub-
carriers the user actually used is ˜Mi, since {h−1
i,j } is in-
creasing in j, we get
μ − h−1
>0, 1 j ˜Mi
0, ˜Mi < j Mj
< μ h−1
⇔ h−1
i, ˜Mi+1
i, ˜Mi
i,j
where
h−1
i, ˜Mi+1
→ +∞
(8)
when
Since f(h−1
i,Mi+1) > 0 and f is a monotonic increasing
function, the object for the algorithm is to find suitable
˜Mi = Mi.
Fig. 1 Water-filling theorem
694
0 < ˜Mi Mi to satisfy f(h−1
) < 0. Thus, there must
exist a suitable μ satisfying (8), then from (6) the trans-
mission power in each subcarrier can be obtained for the
cognitive user.
i, ˜Mi
Journal of Systems Engineering and Electronics Vol. 22, No. 4, August 2011
If randomly choose some subcarriers to assign to the
cognitive users, according to the number of these subcar-
riers, the complexity may reach to O(2Mi). Note that
the iteration of the proposed algorithm is no more than
Mi, and the complexity of the best sorting algorithm is
O(Mi log2
Mi), so the complexity of our algorithm is no
more than O(Mi + Mi log2
Mi). With a huge number
of the subcarriers (in practice, as the users increase, there
should be plenty of subcarriers), the proposed algorithm
can dramatically reduce the communication overhead.
3.3 Analysis for the algorithm
In order to evaluate the performance of the proposed one-
user water-filling algorithm above, we assume the primary
users operate at a few discrete frequencies around 1 GHz,
which can be divided into M subcarriers with a equal
bandwidth 20 kHz. Assume the overall transmission power
for the cognitive user is P = 20 mW, and the background
noise power in each subcarrier is σ2 = 10−11 W. For the
primary users, if the jth subcarrier is active, assume the
corresponding interference constraint power at the cogni-
tive transmitter is I = 2 mW. The distance between the
cognitive transmitter and receiver is 1 000 m, and the de-
sired BER at the receiver is BER= 10−4. In this paper, we
set d0 = 100 m.
During the simulation, we mainly compare the per-
formance about the following two scenes:
I (Overlay)
The spectrum allocation problems in a spectrum overlay-
based cognitive radio wireless system, in which the cog-
nitive user can only use the idle spectrum; II (Underlay)
The spectrum allocation problems in a spectrum underlay-
based system, which meets the proposed algorithm above.
Fig. 2 shows the power allocation when M = 10 in
the two scenes, where the 1st, 3rd and 4th subcarriers are
active. In scene I, the active subcarriers are not assigned
transmission power. In this case, the 5th, 6th and 7th sub-
carriers with better channel states obtained more transmis-
sion power, so that the cognitive user can get the optimal
system utility. In scene II, although the 1st and 3rd sub-
carriers have a better channel state, they only obtain 2 mW
powers due to the limitation of the interference constraint,
and much power is assigned to the other sub-optimal sub-
carriers. At the same time, the 4th, 8th and 9th subcarriers
are not assigned power for their poor channel states.
As we can see in Fig. 3, when the number of subcarriers
is increasing, the communication utilities for the cognitive
user in both scenes also increase. In scene II, the cognitive
user can use the active subcarriers with better channel state,
so it can obtain higher system utility than scene I. In Fig.
4, we can see that until M > 6 there exist some subcarriers
which are idle (the cognitive user does not transmit signals
in these subcarriers) in scene II, while the cognitive user
cannot use the active subcarriers regardless M in scene I.
Therefore, the proposed algorithm in this paper (scene II)
can utilize the spectrum reasonably so as to obtain the op-
timal communication utility.
Fig. 2 Transmission power in each subcarrier
Fig. 3 The user’s communication utility versus M
Fig. 4 The number of used subcarriers versus M
In Fig. 5, we show the cognitive user’s communica-
tion utility versus the overall transmission power when
Yutao Liu et al.: Joint power and spectrum allocation algorithm in cognitive radio networks
695
M = 10. As increasing with the overall power, the user’s
utilities in both scenes also increase, but the utility in scene
II is higher than scene I all the time. The larger the over-
all power is, the higher the utility gap is. When the power
assigning to subcarriers 1, 3 and 4 reaches to their inter-
ference constraint, the utility gap keeps unchangeable, and
at this moment, the increased power is assigned to the idle
subcarriers reasonably.
this time, the corresponding power in the 5th subcarrier in-
creases very quickly, so as to make up the “lost power” in
the first subcarrier. In scene I, the subcarrier 1 cannot be
used, so the 2nd and 5th subcarriers are assigned higher
power than scene II.
Fig. 5 The user’s communication utility versus overall power
As increasing with P , the number of used subcarriers
also increases. In Fig. 6, we can see that the cognitive user
uses more subcarriers in scene II because it can use the ac-
tive subcarriers in this scene. When the overall transmis-
sion power reaches a certain value, the subcarriers used by
the cognitive user will be gradually stabilized. At this mo-
ment, only the subcarriers with better channel states can be
chosen to transmit signals.
Fig. 7 The assigned power in appointed subcarriers
4. Subcarrier and power allocation
We analyze how to make the best use of the obtained
subcarriers and reach the optimal communication utility
above. Then we will research the subcarrier allocation
mechanism among multiple cognitive users and prove that
there exists an optimal (sub-optimal) allocation algorithm
from which we can get the maximum total utilities under
the constraint condition of (5).
4.1 Optimization objects
Since each subcarrier can only support one cognitive user,
the cognitive users will choose the subcarriers with better
channel state (i.e., higher gain-to-noise ratio) to transmit
signals. Thus, under the constraint condition of (5), the
optimization problem can be expressed as
Ui = Ri
max
M
pi,j
s.t.
j=1
pi,jwi,j Pi, ∀i ∈ N
(9)
where wi,j ∈ {0, 1} and wi,j = 1 means the jth subcar-
rier is used by the ith cognitive user. From the proposed
water-filling algorithm above, we can see that the optimiza-
tion problem can be equivalent to find the suitable water-
pi,jwi,j = Pi(∀i ∈ N). So there
level μi satisfying
M
j=1
exists a unique subcarrier allocation mechanism, which
satisfies (9).
Since wi,j ∈ {0, 1}, the optimization problem described
in (9) is an integer programming problem. For the conve-
nience of analysis, the constraint wi,j can be relaxed to
Fig. 6 The number of used subcarriers versus overall power
The assigned power in each subcarrier (chosen by the
cognitive user) will also increase with P . In Fig. 7, we
show the assigned power in the 1st, 2nd and 5th subcarri-
ers versus the overall power. In scene II, the power ob-
tained by the 1st subcarrier will not increase when it is
equal to 2 mW due to the interference constraint, and at
696
0 wi,j 1. Therefore, from (5) and (9) we get
max U =
M
s.t.
j=1
N
M
i=1
j=1
B
M
wi,j log2
1 + Ki · γi,j
wi,j
, ∀i ∈ N
pi,j Pi, pi,j 0, Ui Rtar
0 wi,j 1,∀i ∈ N, ∀j ∈ M
i
σ2 + pjHj,0 Ij , ∀j ∈ M and j is on.
(10)
Obviously, the optimization object max U in (10) can
be expressed as a function of pi,j and wi,j. Without loss of
generality, under the constraint in (10), we assume
1 + Ki · pi,jhi,j
wi,j
(11)
F (pi,j , wi,j) = wi,j log2
where γi,j = pi,jhi,j. Therefore, max U is a linear com-
bination of the function F (pi,j , wi,j).
Since wi,j is continuous and nonnegative, the second or-
der derivative of F with respect to wi,j can be expressed
as
(pi,jKihi,j)2
w3
i,j
< 0.
2
(12)
F2
(pi,j , wi,j) = − 1
ln 2
1 + pi,j Kihi,j
(pi,j, wi,j) < 0. So, the bi-
Likewise, we can obtain F1
nary function F (pi,j, wi,j) is convex in pi,j and wi,j, the
total utility U is also convex in (pi,j, wi,j).
wi,j
From (10) we can see that the constraint parameters
pi,j and wi,j are continuous and nonnegative, so the op-
timization problem researched is a convex programming
problem. In convex programming problems, a local op-
timization is also a global optimization, so we can adopt
the local-search algorithms to solve the spectrum alloca-
tion problems in cognitive radio networks.
4.2 Spectrum sharing algorithm
Theorem 1 For the case where the number of cogni-
tive users is two, without loss of generality, let h1,j/h2,j be
in a monotonically decreasing order such that h1,j/h2,j >
h1,j+1/h2,j+1 (j, j + 1 ∈ M). If the SNR in each subcar-
rier is much more than one, i.e., SNRi,j 1(∀j ∈ M; i ∈
{1, 2}), then there exists an optimal subcarrier partition m
(when 1 j < m, the corresponding subcarriers are as-
signed to user one; and when m < j M , the subcarriers
are assigned to user two) that maximizes the system total
utility U .
Proof As mentioned above, when the jth subcarrier is
used by ith the user alone, i.e., wi,j = 1, the SNR for the
ith user can be expressed as SNRi,j =
. For the
pi,jhi,j
wi,j
Journal of Systems Engineering and Electronics Vol. 22, No. 4, August 2011
mth subcarrier, we can analyze through the Lagrange ex-
treme method. By taking derivative of the Lagrange equa-
tion obtained from (10) with respect to wi,j, we obtain the
Karush-Kuhn-Tacker (KKT) condition [18]:
if w1,m > 0 and w2,m > 0, then
log2(1 + SNR1,m) − ln 2
log2(1 + SNR2,m) − ln 2
SNR1,m
1 + SNR1,m
SNR2,m
1 + SNR2,m
=
.
(13)
When the mth subcarrier is used exclusively by one
user, the equability above becomes inequality. If the right
hand side is smaller than the left hand side, the mth sub-
carrier should be used by user one, and vice versa by user
two.
When taking no account of the interference constraint
for the primary users, from (6) and (10) we can see that the
transmission power for the ith user in subcarrier j can be
expressed as
pi,j = wi,j · (μ − h−1
i,j )+.
Since SNRi,j 1(∀j ∈ M; i ∈ {1, 2}), thus
≈ 1, ∀i ∈ {1, 2}.
SNRi,m
1 + SNRi,m
From (13)−(15), we get
log2(μ1h1,j) − ln 2 = log2(μ1h1,j) − ln 2.
Therefore, we can obtain a function ψ:
(14)
(15)
(16)
ψ
h1,j
h2,j
= log2
h1,j
h2,j
+ log2
.
(17)
μ1
μ2
Since h1,j/h2,j is decreasing in j and the logarithm
is an increasing function, the function ψ(h1,j/h2,j) is a
monotonically decreasing function in j. So, there exists
a subcarrier partition m, such that ψ(h1,j/h2,j) > 0 for
1 j < m and ψ(h1,j/h2,j) < 0 for m < j M .
When the SNR is much larger than one, the spectrum
utility for each subcarrier is also much larger than one. At
a higher SNR, the subcarrier partition is decided chiefly by
the channel state and has a lower dependence on the overall
transmission power of the cognitive users. However, when
the SNR is low, (17) will not hold, so as Theorem 1.
According to Theorem 1, we can obtain the following
spectrum sharing algorithm for two users as shown in Ta-
ble 2, where α1 and α2 denote the impact factors of the
primary users. When the jth subcarrier is used by the pri-
mary user, due to the interference constraint, the cognitive
users can not assign power in this subcarrier freely, at this
time, αi < 1; however, when the jth subcarrier is idle,
the transmission power for the cognitive users is not con-
strained, now αi = 1.
Yutao Liu et al.: Joint power and spectrum allocation algorithm in cognitive radio networks
697
Table 2 The spectrum sharing algorithm
α2
α1
1,j /h
descending order with respect to the index.
Input: M, Hi,j, BERi, σ2, Pi and Ij.
2,j} in a
(i) Initialization: sort the subcarriers according to {h
(ii) Assume user one operates on the subcarriers 1 − m, and user two
operates on the others, calculate the transmission power in each
subcarrier separately according to the “one-user water-filling
algorithm”, then we can obtain the user’s communication utilities
from (4).
(iii) For m = 1, 2, . . . , N − 1, choose the suitable partition m, from
which we can obtain the optimal total utility.
Output: the power allocation strategiy pi,j , the actual number of
subcarriers used by each user, and the users’ utilities.
1
2
user directly in their pre-assigned subcarriers, and this al-
gorithm is called the multi-user subcarrier allocation par-
allel algorithm, which can be seen in Table 4. At this mo-
ment, we can complete all the users’ subcarrier and power
allocation one time, and the times we need to run the spec-
trum sharing algorithm are
numtotal
parallel =
1
2
C ˜N /2
˜N +
· 2x−2C2
1
2
4 +
· 21C ˜N /4
1
2
· 2x−1C1
˜N /2
2
+ ··· +
(19)
≈ O(C ˜N /2
˜N ),
when N is large (e.g., N > 10), numtotal
which means that numtotal
≈ num1
parallel
greedy.
parallel
Table 3 The multi-user subcarrier allocation greedy algorithm
Input: M, N, Hi,j , BERi, σ2, Pi and Ij.
(i) Divide all the users into two collusion rings according to the
principles mentioned above, then there are C
grouping schemes.
N/2
N /2 or C
˜N /2
˜N /2
(ii) For both collusion rings, calculate their mean gain-to-noise ratio
¯gi,j and the mean overall power ¯Pi.
(iii) According to the “spectrum sharing algorithm”, allocate the
subcarriers to both collusion rings in each grouping scheme,
then obtain the optimal divided forms and the corresponding
subcarriers assigned to each group.
(iv) Repeat step (i) to (iii), until each user obtains their pre-assigned
subcarriers.
(v) For one user (e.g., the first one), according to the “one-user water-
filling algorithm” complete the corresponding power allocation.
(vi) Remove the users completing power allocation, and repeat the
step (i) to (v) until all of the users obtain their final subcarriers.
(vii) From (4) and (6), obtain the power allocation strategies pi,j
and the user’s utility.
Output: the power allocation strategy pi,j , the actual number of
subcarriers used by each user, and the users’ utility.
Table 4 The multi-user subcarrier allocation parallel algorithm
Input: M, N, Hi,j, BERi, σ2, Pi and Ij.
(i) ∼ (iv) The same as the “multi-user subcarrier allocation greedy
algorithm”.
(v) All the cognitive users use the “one-user water-filling algorithm”
in their pre-assigned subcarriers to obtain their own power
allocation strategies.
(vi) According to (4) and (5), calculate the users’ utilities and the
total utility.
Output: the power allocation strategy pi,j, the actual number of
subcarriers used by each user, and the users’ utility.
Obviously, we cannot obtain the optimal total utility
from the multi-user subcarrier allocation parallel algorithm
because the gain-to-noise ratio for all the cognitive users
in some subcarriers may be high (compared with the other
subcarriers). However they may not be used although they
are assigned to one user in the pre-allocation (step iv). In
this case, if not re-allocation through steps (v) and (vi) in
Table 3, the total utility will be lower than the optimal. The
4.3 Allocation algorithms for multi-users
When the number of cognitive users is larger than two,
the computation complexity is very high, because the cor-
responding number of subcarriers is always huge. Next,
according to the one-user water-filling algorithm and the
spectrum sharing algorithm mentioned above, we will pro-
pose a new multi-user subcarrier allocation mechanism.
For the convenience of analysis, we first give some defi-
nitions.
Collusion Part of the cognitive users form a clique,
they negotiate with others as a body, and we call this clique
a collusion ring. If all of the users are equally divided into
two collusion rings, we call them bisected rings.
Dummy user The user that is created to make the total
number of users even, who cannot be assigned subcarriers.
For the case when the number of users is N = 2x (x
is a positive integer), we can randomly form two bisected
rings until each group has only one user; when N = 2x,
the dummy users are needed until ˜N = 2x. After group-
ing, we use the mean channel gain-to-noise ratio ¯hi,j and
the mean power ¯Pi (i = 1 or 2) for the collusion rings.
Therefore, we can obtain the following multi-user subcar-
rier allocation algorithm.
During the “multi-user subcarrier allocation greedy al-
gorithm”, we have to run the “spectrum sharing algorithm”
once in each grouping, so in order to complete one user’s
allocation, the iteration for the “spectrum sharing algo-
rithm” is
1
2
1
2
1
2
C1
2
num1
C ˜N /4
˜N /2
greedy =
C ˜N /2
˜N +
+···+
≈ O(C ˜N /2
˜N )
(18)
where ˜N is the total number of users when introducing
dummy users (if needed), and ˜N = 2x. When the num-
ber of the cognitive users is large, the computation cost for
the greedy algorithm is very huge. So as to simplify the
calculation, we propose an alternative sub-optimal algo-
rithm, through which we can skip the steps (v) and (vi) in
Table 3, instead, we calculate the power strategy for each
698
Journal of Systems Engineering and Electronics Vol. 22, No. 4, August 2011
intuition is that at the case when the subcarriers are enough
for the cognitive users, the parallel algorithm has a similar
performance to that of the greedy algorithm, but the paral-
lel algorithm has a much lower complexity.
5. Performance evaluations
The simulation results are presented in this section to show
the performance of our proposed algorithm above. At first,
a system of two cognitive users is taken into account. As-
sume the primary users operate at a few discrete frequen-
cies around 1 GHz, which can be divided into M subcar-
riers with an equal bandwidth of 20 kHz. The background
noise power in each subcarrier is σ2 = 10−11 W. For
the primary users, if the jth subcarrier is active, the cor-
responding interference constraint power at the cognitive
transmitter is I = 2 mW. The distances between the trans-
mitter and receiver for the cognitive users one and two are
1 000 m and 800 m, respectively. The desired BER at the
receiver is BER= 10−4. Without loss of generality, in the
following analysis, we assume that the subcarriers 1, 3, 4,
11−15, and 26−30 (if existence) are active, and α = 1.
When M = 10 and P1 = 2P2 = 20 mW, the subcarrier
and power allocation for the cognitive users can be seen in
Fig. 8. For the active subcarriers (1, 3 and 4), the power
assigned is limited to the interference level of 2 mW (in
this paper, the assigned powers are all equal to interference
constraint power because of the good channel state). Since
the distance between the transmitter and receiver for the
second user is shorter, it has a higher-priority during the
allocation and is assigned more subcarriers. In addition,
when the distances are equal for both users, the gain-to-
noise ratio at the same subcarrier mainly depends on the
users’ preference coefficients. In the analysis of results, we
can see that only a little power is assigned to the subcarriers
2 and 10 because of their poor channel states. Therefore,
we can predict that when there are much more subcarriers,
both the 2nd and the 10th subcarriers will be not used by
the cognitive users.
In Fig. 9, we show the cognitive users’ communication
utilities and the total utility versus the overall power con-
straint for the second user, at this time, we choose M = 10
and P1 = 20 mW. When P2 is increasing, the utility for the
second user is also increasing, while the first user’s utility
is reduced due to the competition from the second user.
When P2 13, the utility for the first user is basically
unchanged, because the subcarrier allocation between the
two users is approximately completed, and in this case, the
additional power of user two is assigned evenly among the
subcarriers obtained.
Fig. 9 Users’ utilities and total utility versus P2
In Fig. 10, we can see that, at a lower P2, the subcarrier
allocation strategy is adjusted along with the increasing of
P2, and the subcarriers obtained by the first user gradu-
ally decrease while that of the second user increase. When
P2 varies in a certain range (e.g., 3 P2 8), the cog-
nitive users can obtain a constant number of subcarriers,
and in this case, the total utility can not increase through
subcarrier re-allocation. Thus, we can predict that when
P2 reaches to a certain extent (P2 > 30), the subcarrier
re-allocation will occur again.
Fig. 8 Power and subcarrier allocation
Fig. 10 The subcarriers assigned to each user versus P2
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
