The IPW algorithm under Sum Transmit Power Constraint.
1. Introduction
Spectrum scarcity is becoming a serious problem as the rapid developments of wireless communications. However, recent spectrum measurements show that the licensed spectrum is severely underutilized by the primary users (PUs) in both the time domain and the spatial domain (FCC, 2002, Mchenry, 2005). The secondary users (SUs) are introduced to exploit the spectrum opportunities left by the PUs in order to improve the spectrum utilization. The transmission of SU is required to satisfy the PU's interference limits to protect the PU's performance. Cognitive radio (Mitola, 1999, Haykin, 2005, Zhao & Sadler, 2007) is the key technology enabling flexible, efficient and reliable spectrum utilization by adapting the radio's operating characteristics to the realtime conditions of the environment. The SUs with cognitive radio technology are able to cleverly detect and utilize the spectrum opportunities and thus realize efficient reuse of the licensed spectrum
It is extremely important to guarantee the transmission of the SU satisfy the interference limits of the PUs for the cognitive radios to be acceptable. Generally, the interference limits can be described by two metrics: the maximum allowable collision probability and the interference power limit (Zhao & Sadler, 2007). The former one is related to the spectrum sensing mechanism of the cognitive radios, which has been widely studied in both the physical (PHY) layer (Sahai et al., 2004, Oner & Jondral, 2007, Cabric et al., 2004) and the medium access control (MAC) layer (Zhao et al., 2007, Kim & Shin, 2007, Ghasemi & Sousa, 2007) in the literature. The latter one introduces power restrictions on the channel output signals in cognitive radio systems, which is different from the conventional wireless systems where the power constraints are only placed on the channel input signals. This feature motivates the studies on how to efficiently utilize the spectrum opportunities under the interference power limits of the PUs (Zhang et al., 2008, Shu et al., 2006, Sudhir & Jafar, 2007, Le & Hossain, 2007).
A cognitive radio system needs to be highly flexible in terms of the spectral shape of the transmit signal. Orthogonal frequency division multiplexing (OFDM) modulation is a promising candidate for such a flexible system because of its reconfigurable subcarrier structure (Weiss & Jondral, 2004, Berthold & Jondral, 2005). With OFDM, the SU has the ability to flexibly fill the spectral gaps left by PUs. Also, the fast Fourier transform (FFT) components at the OFDM system's receiver may also be used for the SU to execute the channel detection. In
(Weiss & Jondral, 2004), Weiss and Jondral proposed that the band of the SU covers multiple PUs' licensed spectrum, then the SU modulates zero on the subcarriers which belong to the detected PUs's licensed spectrum while utilizing other subcarriers for transmission. In OFDMbased cognitive radio systems, the adaptive subcarrier configuration should consider not only the channel state information (CSI) as in conventional OFDM systems, but also the sensing results of the SU and the interference limits of the PUs. This chapter focuses on investigating the research challenges involved in the power allocation for OFDMbased cognitive radio systems.
The optimal power allocation algorithm for conventional OFDM systems that maximizes the channel capacity is the wellknown
The transmit power in each subchannel is comprised of the power allocated to the subcarriers inside the subchannel and the sidelodes power of the subcarriers in other subchannels. In this chapter, we first formulate the power allocation problem in the case where the effects of subcarrier sidelobes can be ignored, i.e., there is sufficient guard band between any two neighboring subchannels. Based on the convex optimization theory, an algorithm named
2. System Model
2.1. Cognitive radio system and interference power limit
One of the typical cognitive radio systems is shown in Figure 1. A certain channel is licensed to the PU system. Since the PU system does not occupy the channel anywhere at any time, the channel is underutilized in both the spatial domain and the time domain. A channel is said to be a spectrum opportunity if the interference to the PU receivers caused by the SU's transmission is tolerable. The SU is permitted to access the channel if the channel is detected to be a spectrum opportunity. With the participance of the SU, the spectrum
opportunities can be identified and exploited and thus the overall spectral efficiency can be improved.
To guarantee the interference to the PU tolerable is an extremely important problem in the implementation of cognitive radio systems. Generally, the SU has to sense the channel in order to determine whether a spectrum opportunity exists before the transmission. The SU is permitted to transmit on a licensed channel unless the corresponding PU's signal is seen as absent. A detection probability has to be achieved to reduce the collisions between the SU and the PU caused by the detection errors. As in Figure 1, PU_{1}'s signal can be detected when active and thus the interference to PU_{1} receiver caused by the SU's transmission can be avoided. However, due to the signal to noise ratio limit, the SU can only detect the signal of the PU with the required detection probability within a certain region, as the reliable sensing region shown in Figure 1. Therefore, for the PU_{2} transmitter that is outside the SU's reliable sensing region, the SU is unable to detect PU_{2}'s signal with the required detection probability, as depicted in Figure 1. In this situation, as in (Zhao & Sadler, 2007), PU_{2} defines a protection area whose radius is
where
in (1). We note that if the SU is unaware of the PU's location, some conservative scheme may be used to estimate
2.2. OFDMbased cognitive radio systems and subchannel transmit power constraints
In order to efficiently exploit the spectrum opportunities left by different PU systems, a cognitive radio system needs to be highly flexible with respect to the spectral shape of the transmit signal. OFDM modulation is a promising candidate for such a flexible system because of its reconfigurable subcarrier structure. Also, the FFT component at the OFDM receiver can be used for spectrum sensing, which reduces the overhead for the implementation of the cognitive capability.
As in Figure 2, in an OFDMbased cognitive radio system, the spectrum that can be potentially used by the SU is divided into
Before the transmission, the SU senses whether each subchannel is occupied firstly, by proper spectrum sensing methods. Then according to the sensing results and the CSI of each subcarrier over SU transmission link, the SU can decide the proper power allocation scheme, modulation type and other parameters for SU's transmission. Therefore, the total transceiver diagram can be shown in Figure 3. At the transmitter in Figure 3, the transmission parameters should be decided before serialtoparallel (S/P) conversion, IFFT operation, paralleltoserial (P/S) conversion, insertion of a Cyclic Prefix (CP) and filtering. Accordingly, at the receiver, the information on transmission parameters over the link should be obtained through signaling to receive and demodulate OFDM signals. Then the received signal of the
where
but with a certain power constraint which has been described in Section 2.1. Assume
where
3. Power Allocation for OFDMbased Cognitive Radio Systems without Considering Subcarrier Sidelobes
In conventional OFDM systems, given the sum transmit power constraint or the target rate, the optimal power allocation that aims at maximizing the sum rate or minimizing the required power can be achieved by the wellknown waterfilling algorithm. In OFDMbased cognitive radio systems, the power allocation should also satisfy the subchannel transmit power constraints which are introduced by the interference power limits of the PUs. Therefore, the waterfilling algorithm needs to be modified. In this section, we first review the power allocation problem in conventional OFDM systems and then formulate that in the
cognitive radio scenario.
3.1. Power allocation in conventional OFDM systems
The signal model for conventional OFDM systems is as (2) shows. The power allocation problem can be classified into two categories in conventional OFDMbased systems. The first one is to optimize the power allocation across the subcarriers such that the sum rate is maximized with a given sum transmit power constraint. Assume the sum transmit power constraint of an OFDM block is P
where (^{.})^{+} denotes max{^{.},0} and
The algorithm to obtain the optimal solution is the wellknown waterfilling, where the socalled waterlevel is calculated based on (5). The other category of power allocation problem can be formulated as optimizing the power allocation across the subcarriers such that the required transmit power is minimized while a given target rate is satisfied. Assume the target rate is R_{t}. The optimal power allocation has the same expression of (4) while the waterlevel
The algorithm to obtain the optimal solution is also the waterfilling, where
3.2. Power allocation in OFDMbased cognitive radio systems
The power allocation problem in OFDMbased cognitive radio should consider the subchannel transmit power constraints in addition to the sum transmit power constraint or the target rate. Assume
Here, without considering subcarrier sidelobes, the allocated power is exactly the transmit power.
The power allocation problem with the sum transmit power constraint P_{t} can be formulated as the following optimization problem:Similarly, the power allocation problem with the target rate R_{t} can be formulated as
Note that the SU also suffers interference caused by the PU. The interference can be regarded as white noise by the SU, which may lead to different noise levels in different subchannels. However, although the noise power in each subchannel is set to be equal to each other, this fact does not affect our problem formulation since we can rescale the channel gain. Obviously, the above two optimization problems are convex optimization problems with linear constraints, which can be numerically solved by the standard optimization algorithms. However, we intend to develop analytical as well as more efficient algorithms rather than numerical methods in the following two subsections.
3.3. Iterative Partitioned Waterfilling: Sum Transmit Power Constraint
We first consider (7), i.e., the power allocation problem with the sum transmit power constraint. The algorithm is developed by three steps. The fist step is to analyze the structure of the optimal solution of (7) based on the convex optimization theory. Then the algorithm is proposed heuristically based on the analysis in the first step. The algorithm is proved to converge to the optimal point at last. We begin with the first step in this subsection.
3.3.1. Analysis of the structure of optimal solution
In (7), if
constraints and the solution is simply waterfilling on the subcarriers in each subchannel individually with the corresponding subchannel transmit power constraint. Therefore, we only emphasize on the situation that
where i = 1, 2, …,N and j is the index of the subchannel which the ith subcarrier belongs to. Assume
2. for j ∈ B:
Proof: The problem (7) can be reformulated into a standard convex optimization form:
The constraint conditions obviously satisfy the Slater's conditions, so the KarushKuhnTucker(KKT) conditions are sufficient and necessary for the optimal vector P (Boyd & Vandenberghe, 2004). The first two KKT conditions are the constraint conditions of (12) and the others are given by
where i =1,2,...,N, j =1,2,...,M
where i =1,2,...,N, j =1,2,...,M
where i =1,2,...,N and j is the index of the subchannel which the ith subcarrier belongs to.
I. Proof of only if part
(15) can be written as
Substituting (16) into (13a) and (14a) yields
P_{t} = 0. From (16), we also have
where i = 1, 2, …,N and j is the index of the subchannel which the ith subcarrier belongs
to.The subchannels are divided into two sets A and B. Since we assume
1) For all j ∈ A, since Fj < Gj, we have α_{j} = 0 based on (14b). Let
Therefore, we come to the equation (10b)
2) For all j ∈ B, the condition (11a) is obviously satisfied. Since α_{j}≥0, we have
Therefore, the inequality (11b) also holds.
So far, we have proved the only if part in Theorem 1.
II. Proof of if part
We need to prove that all the KKT conditions can be derived by the power allocation vector defined in Theorem 1. It is easy to see that the first two KKT conditions, i.e., the constraint conditions in (12), hold inherently.
1) Based on (10b) and A≠∅, we have
Therefore, (13c) and (14c) both hold.
2) Define
Therefore, (13b) holds. Since for j ∈ B, we have Fj = Gj, (14b) also holds.
3) Define
subcarrier belongs to.Then (15) holds inherently. If
Since we can derive
Then, λ=0. Therefore, given
Hence, given
In conclusion, we have derived all of the KKT conditions and thus the if parts also holds. This completes the proof of Theorem 1. □
Comparing (9) with (4), we can find that the power allocation within each subchannel is the same to the conventional waterfilling result. However, the waterlevels of different subchannels may be different in (9). From Theorem 1, we know that the subchannels with the optimal power allocation can be divided into two sets: the set A, i.e., the subchannels whose allocated power is strictly smaller than the corresponding subchannel transmit power constraint and the set B, i.e., the subchannels whose allocated power is equal to the corresponding subchannel transmit power constraint. For the subchannels in A, the allocated power is the result of waterfilling on all the subcarriers that belong to these subchannels with the power
A power allocation result satisfying Theorem 1 is shown in Figure 5. Within each subchannel, it is the same to the conventional waterfilling result. However, the waterlevel of each
subchannel is not equal to each other compared to Figure 4. Subchannel 1 and 3 have the same waterlevel W, as each allocated power is strictly lower than the corresponding subchannel transmit power constraint. Subchannel 2 and 4 have their unique waterlevels w_{2} and w_{4} respectively, as each allocated power is equal to the corresponding subchannel transmit power constraint. Also, as in Figure 5, we see that the unique waterlevels w_{2},w_{4} are lower than the common waterlevel w.
3.3.2. Iterative partitioned waterfilling
From the above analysis, we can infer that if the partition of the subchannels, i.e., the elements of A and B, is known, the optimal power allocation can be obtained by first waterfilling on the subcarriers in each subchannel that belongs to the set B individually with the corresponding subchannel transmit power constraint, and then waterfilling on the rest of the subcarriers with the power
Divide the subchannels into two sets, say A and B and there are 2^{M} kinds of partitions in total.
For each partition, perform the conventional waterfilling on the subcarriers in each subchannel that belongs to the set B individually with the corresponding subchannel transmit power constraint. Then the waterlevels wj where j∈ B can be obtained.
3.Remove such partitions that
4.Verify each partition whether F_{j}< G_{j} where j ∈ A and
I. Initialization : 

II. Iterations: 1. Perform the conventional waterfilling on the subcarriers in all the subchannels that belong to the set A with the target rate 
2. 
III. End 
However, the complexity of the exhaustive search algorithm is far too high. In the extreme situation, we need to consider 2^{M} kinds of partitions throughout the algorithm. Therefore, we develop a more efficient algorithm named as iterative partitioned waterfilling (IPW). The basic idea is to determine the elements of A and B iteratively rather than by exhaustive search. The IPW algorithm is described in Table 1.
In the beginning of each iteration, the conventional waterfilling with only sum transmit power constraint P is done on the subcarriers in all the subchannels that belong to the set A. Then those subchannels whose power exceeds its subchannel transmit power constraint are taken out from the set A and then be performed by waterfilling with the corresponding subchannel transmit power constraints individually. The iteration stops when each subchannel satisfies its subchannel transmit power constraint. The IPW algorithm is more efficient than the exhaustive search algorithm. In the worst case, the algorithm converges after M iterations.
3.3.3. Proof of optimality
In order to prove the optimality of the IPW, we need to explain that the IPW algorithm converges to the point that satisfies the conditions in Theorem 1. Actually, we only need to prove the inequality (11b) as other conditions are inherently satisfied.
We outline two simple lemmas about the conventional waterfilling before the proof. Assume P is the power allocation vector of waterfilling on N subcarriers with power 1^{T}P and the waterlevel is w, where 1 is the column vector of all ones.
Proof: Assume in the fcth iteration, the power
after the kth iteration.
Based on Lemma 1, for the rest of the subchannels in the set A satisfying F_{j}< G_{j}, if the conventional waterfilling is done on the corresponding subcarriers with the power
When the algorithm converges after
So far, we have proved that the IPW algorithm converges to the point satisfying the conditions in Theorem 1 and thus the optimal power allocation can be obtained by the IPW algorithm.
3.4. Iterative Partitioned Waterfilling: Target Rate Constraint
In this subsection, we consider (8), i.e., the power allocation problem with the target rate constraint. If the target rate is given, we should first verify if the target rate can be achieved under the subchannel transmit power constraints. It is easy to see that the maximum rate that can be achieved under the subchannel transmit power constraints is the result of waterfilling on the subcarriers in each subchannel with the corresponding subchannel transmit power constraint individually. Therefore, the maximum achievable rate can be expressed as
where Pi is determined by
where i = 1, 2,…, N and j is the index of the subchannel which the ith subcarrier belongs to. wj can be determined by
Then, if R_{t}> R_{max}, Rt can not be achieved by any power allocation vector under the subchannel transmit power constraints. Also, the optimal power allocation can be determined by (32) and (33) when R_{t} = R_{max}. In the case R_{t}< R_{max}, the algorithm for solving (8) can be developed following the similar derivation as that in Section 3.3. A similar theorem as Theorem 1 can be described as follows.
Theorem 3 Under the assumption that R_{t}< R_{max}, a power allocation vector P is the solution for (8) if and only if it satisfies:where i = 1, 2, …,N and j is the index of the subchannel which the ith subcarrier belongs to. Assume
where Rj is determined by
2. for j 𝜖 B:
The proof of Theorem 3 is also similar to that of Theorem 1 and thus is omitted in this paper. Based on Theorem 3, the IPW algorithm for solving (8), which can be developed in a similar way as that in Section 3.3, is described in Table 2.
In each iteration, the conventional waterfilling with only target rate constraint
I. Initialization : 

II. Iterations: 1. 1. Perform the conventional waterfilling on the subcarriers in all the subchannels that belong to the set A with the target rate 
2. 
III. End 
4. Power Allocation for OFDMbased Cognitive Radio Systems Considering Subcarrier Sidelobes
The iterative partitioned waterfilling (IPW) algorithm proposed in the above section can obtain the optimal power allocation for OFDMbased cognitive radio systems in the case where only the interference to the PU caused by the subcarriers inside the corresponding subchannel was considered. However, it is clear that the PU also suffers interference introduced by the subcarrier sidelobes of the neighboring subchannels. Therefore, the assumption in the above section actually implied that there is sufficient guard band between any two subchannels so that the effects of subcarrier sidelobes could be ignored. In this section, we extend the results in the above section and address the power allocation problem in general OFDMbased cognitive radio systems. The effects of subcarrier sidelobes are specially considered in the optimization problem. We propose the power allocation algorithm that maximizes the capacity while satisfying both the sum and subchannel transmit power constraints.
The effects of subcarrier sidelobes in OFDMbased cognitive radio systems were first addressed in (Weiss et al., 2004). The subcarrier sidelobes suppression techniques were further studied in (Cosovic et al., 2005, Pagadarai et al., 2008, Mahmoud & Arslan, 2008). In (Bansal et al., 2007), the authors proposed a power loading algorithm for OFDMbased SU systems whose bands are not overlapped with any PU's. The aim was to maximize the capacity while keeping the interference to the PUs whose licensed bands are in the proximity of the band of SU below a certain threshold.
In the following, we will firstly reformulate the system model and the optimization problem with subcarrier sidelobes in consideration. Then an algorithm will be proposed for a special case with only two nonzero weighted linear inequality constraints. Finally, this algorithm mentioned above will be extended to general cases with multiple nonzero weighted linear inequality constraints, where the extended algorithm is called recursive power allocation (RPA) algorithm.
4.1. Power allocation problem reformulation
The basic system model used in this section is the same as that in Figure 1 and Figure 2. The SU's
transmit power on the PU's licensed channel P_{tx} should still be subject to the power constraint as (1). However, considering the effects of subcarrier sidelobes, it is not proper to require the transmit power in the unavailable subchannel to be zero as (3), since the sidelobes of the subcarriers in other subchannels certainly lead to nonzero transmit power in the unavailable subchannel. So we set a transmit power threshold for the jth subchannel when PUj is detected, say
As mentioned in Section 3, in OFDMbased cognitive radio systems, the subchannel transmit power constraints impose further restrictions on the power allocation in addition to the sum transmit power constraint. In fact, the transmit power in one subchannel is comprised of not only the power allocated to the subcarriers inside the subchannel but also the sidelobes power of the subcarriers in other subchannels. We define Jij as the transmit power in the jth subchannel caused by the ith subcarrier with unit power. According to (Weiss et al., 2004), we have
Assume P_{i} be the power allocated to the ith subcarrier. Then the transmit power on the jth subchannel can be expressed as
Then, the original optimization problem as (7) for optimal power allocation in OFDMbased cognitive radio systems can be modified as the following one:
where P* is the optimal power allocation vector, h_{i} is the ith subcarrier's channel gain, and Pt is the maximum transmit power of the SU transmitter.
Section 3, the subchannel power constraints are approximated by ignoring the subcarrier sidelobes, i.e.,
When (41) is satisfied, it can be seen that the M subchannel power constraints in (40) are actually decoupled with each other in terms of the optimization variables. Based on this
characteristic, we manage to find an efficient algorithm named iterative partitioned waterfilling. In the case where the subcarrier sidelobes are considered, however, the problem turns to be more complicated.
It is clear that (40) is a convex optimization problem with linear inequality constraints. (40) can be expressed in a compact form:
where J_{i,0} = 1 for any i = 1, 2,…,N and G_{o} = P_{t}. While the N positivity constraints are easy to handle, the remaining M + 1 constraints, which are named nonzero weighted linear inequality constraints for ease of description, introduce the main difficulties for the algorithm development.
In order to find the power allocation algorithm for (42), we start with the problem with only two nonzero weighted linear inequality constraints. Then the recursive power allocation (RPA) algorithm is proposed for the general cases, which is a recursive extension from the above simple problem.
4.2. Power allocation for the case of two nonzero weighted linear inequality constraints
The problem with two nonzero weighted linear inequality constraints can be expressed as
The two nonzero weighted linear inequality constraints are numbered with C_{k} and C_{l} respectively for ease of derivation.
4.2.1. Degraded cases
We begin with solving the problem with C_{k} excluded. Solving this degraded problem is similar as the derivation of the conventional waterfilling algorithm. The solution, which satisfies the constraint C_{l} with equality, can be expressed as
where
Substituting (44) into the excluded constraint C_{k}, if C_{k} is also satisfied, i.e.,
then (44) is also the solution of the original problem (43).
If (45) is not satisfied, we turn to consider the problem with Ci excluded. Similarly, the solution for this degraded problem can be expressed as
where
If the constraint C_{l} is also satisfied with (46), i.e.,
then (46) is also the solution of the original problem (43).
Therefore, the optimal power allocation for (43) is easy to find in the above two degraded cases, i.e., either (45) or (47) is satisfied.
4.2.2.Algorithm for general cases
In order to obtain the solution in the case that neither (45) nor (47) is satisfied, we first propose the following lemma.
Lemma 3 Define a convex optimization problem (OP_{0}) with differentiate objective function and inequality constraints satisfying Slater's conditions:and let x_{0} be any optimal point of OP_{0}. Assume x_{k} is any optimal point of a subproblem (OP_{k}) of OP_{0} with n — 1 inequality constraints h_{i}(x) ≤ 0,i = 1,...,k — 1,k + 1,...,n. Then if h_{k}(x_{k}) ≥ 0, we have h_{k}(x_{0}) = 0.
Proof: If h_{k}(x_{0}) ≠ 0, then we have h_{k}(x_{0}) < 0. Since x_{0} is an optimal point of the convex optimization problem OP_{0}, x_{0} satisfies all the KKT conditions of OP_{0}, which are given by
where α_{i} is the Lagrange multiplier. Since h_{k}(x_{0})<0 according to α_{k} h_{k}(x_{0}) = 0 in (49a), we have 𝛼_{k} = 0. Then (49b) can be expressed as
Based on (49a) and (50), it is clear that x_{0} also satisfies the KKT conditions of OP_{k}. Therefore, x_{0} is also an optimal point of OP_{k}. Consequently, we know that there is an
Step1. Calculate the optimal power allocation P* with C k excluded based 
on (44); 
Step2. Check if P* also satisfies C k. If C k is satisfied, exit; 
Step3. Calculate the optimal power allocation P* with C l excluded based 
on (46); 
Step4. Check if P* also satisfies C l . If C l is satisfied, exit; 
Step5. Calculate the optimal power allocation P* based on (53 ) 
optimal point of OP_{k} satisfying h_{k}(x_{k}) < 0, which contradicts the premise that h_{k}(x_{k}) > 0. Finally, we come to the conclusion that h_{k} (x_{0}) = 0.D
Based on Lemma 3, the optimal solution of (43) must satisfy the two constraints C_{k} and Ci with equalities in the case that neither (45) nor (47) holds. Therefore, solving (43) in this case is equivalent to solving the following problem:
To find the solution, we form the Lagrangian:
The optimal power allocation can be obtained by solving the first order KKT condition
where
Combining the derivations above, the power allocation algorithm for the problem with two nonzero weighted linear inequality constraints is shown in Table 3.
4.3. Recursive power allocation algorithm for general cases
The above algorithm can be further extended to the problem (42) including M + 1 nonzero weighted linear inequality constraints. Similarly, we first consider M + 1 degraded cases each of which excludes one nonzero weighted linear inequality constraint. Each of the M + 1 degraded optimization problems can be solved by the algorithm for the problem with M nonzero weighted linear inequality constraints. If the solution of one of these M + 1 degraded
I. Initialization : 
Number the M +1 nonzero weighted linear inequality constraints as C 0 ,C 1 ,...C M , m= M +1, A={ C 0 ,C 1 ,...C M }. 
Begin P* = PAA ( m, A ) . end function:PAA (m, A ) begin Case m =1 : Return 
problems also satisfies the corresponding excluded constraint, the optimal power allocation is obtained. Otherwise, the optimal solution of the original problem must satisfy the M + 1 constraints with equalities based on Lemma 3. Similar as that in Section 4.2.2, we form the Lagrangian:
The optimal power allocation can be obtained by solving the first order KKT condition
where
Since the algorithm for the problem including two nonzero weighted linear inequality constraints has been obtained in Section 4.2.2, the problem for the general case including multiple nonzero weighted linear inequality constraints can be solved in a recursive way, i.e., recursive power allocation (RPA) algorithm.
For ease of derivation, we define the function f (A) where A is a set comprised of all the nonzero weighted linear inequality constraints of the optimization problem with the form as (42). f (A) returns the optimal solution that satisfies all the constraints contained in A with equalities. For example, f(A) returns the value determined by (44) when A = {C_{k}} and the value determined by (53) when A = {C_{k},C_{l}}. We further assume that 𝛼_{i} denotes the ith element of A. The power allocation algorithm for general cases is shown in Table 4.
5. Simulation Results
In this section, two parts of simulation results are presented to verify our proposed algorithms of power allocation for OFDMbased cognitive radio systems. The first part focuses on the
IPW algorithm (as in Table 1)
Using the IPW algorithm in Table 2 has the similar results as mentioned in Section 3.4.
for OFDMbased cognitive radio systems without considering subcarrier sidelobes. The second part focuses on the RPA algorithm (as in Table 4) for OFDMbased cognitive radio systems considering subcarrier sidelobes. Part A: IPW algorithm without considering subcarrier sidelobes In this part, we set N = 16, M = 4, i.e., each subchannel has 4 subcarriers. The IPW process is shown in Figure 6. Figure 6(a) illustrates the reciprocal of the channel gain given a realization of a frequency selective fading channel, i.e., the bottom of the pool for waterfilling. The power allocation result after Step in Table 1 in the first iteration is shown in Figure 6(b), where the power allocation is just the result of the conventional waterfilling with only sum transmit power constraint. At Step II2 in Table 1, we find that the power allocated to Subchannel 1 exceeds its subchannel transmit power constraint Gj.. Therefore, Subchannel 1 should be taken out from the set A and the conventional waterfilling is performed on the corresponding subcarriers with the power G_{1} at the last step of the first iteration. At Step in Table 1 of the second iteration, the conventional waterfilling is performed on the subcarriers in the rest of the subchannels in the set A with the power P_{t} — G_{1} and the resulting power allocation is shown in Figure 6(c). Then the power constraint on Subchannel 3 is found to be destroyed at Step II2 in Table 1. As a result, we execute Step II3 and Step II4 in Table 1 again and then enter the third iteration. Figure 6(d) illustrates the power allocation after Step II1 in Table 1 in the third iteration, where only Subchannel 2 and 4 are still remained in the set A. At Step II2 in Table 1, each subchannel transmit power constraint is found to be satisfied and thus we may end the iterations with C = 0. Finally, the power allocation in Figure 6(d) is the optimal one that maximizing the sum rate while satisfying both the subchannel transmit power constraints and the sum transmit power constraint. Part B: RPA algorithm considering subcarrier sidelobesIn this part, the frequency selective fading channel is generated according to the Typical Urban (TU) channel model, which is comprised of six paths whose delay parameters are [0.0 0.2 0.5 1.6 2.3 5.0]ßs and power profile is [0.189 0.379 0.239 0.095 0.061 0.037]. The SU's bandwidth is 5 MHz, which is equally divided into M = 4 subchannels. The number of the subcarriers is supposed to be N = 64 and each subchannel has 16 subcarriers. We use the values 640 for P_{t}, which implies that the signal to noise ratio is about 10 dB as the noise power on each subcarrier is set to be 1. The four subchannel power constraints are specified as 80, 480, 1.6, 480 respectively. The power constraint on Subchannel 3 is about 25 dB below its neighboring subchannels, which implies that the SU may be very close to or even just inside PU_{3}'s protection area. Thus, the constraint on the transmit power in Subchannel 3 should be very rigorous in order to satisfy PU_{3}'s interference power limit. The optimal power allocation is shown in Figure 7 for a given realization of the TU channel. For comparison, the power allocation result using the IPW algorithm ignoring the effects of subcarrier sidelodes is also given in Figure 8. Though it can be seen in Figure 8 that the allocated power on each subchannel is lower than the corresponding subchannel's transmit power constraint, the actual transmit power on Subchannel 3, including the allocated power on Subchannel 3 and the sidelobe power from neighboring subchannels, is about 6 times of its transmit power constraint, which induces to serious destruction to the PU3's interference constraint. Therefore, the IPW algorithm cannot be applicable for such Subchannel 3 and its neighboring subchannels in this case. On the contrary, the RPA algorithm as shown in Figure 7 can maximize the capacity while satisfying the subchannel transmit power constraints. Comparing Figure 7 with Figure 8, we can see that the power allocated to the subcarriers near Subchannel 3 is suppressed even if the channel states are fine while more power is allocated to the subcarriers that are far away from Subchannel 3. On the other hand, it can also be found that the power allocation in Subchannel 1 is almost the same as that without considering subcarrier sidelobes, which implies that it is reasonable to ignore the effects of subcarrier sidelobes when sufficient guard band between two subchannels is present. Therefore, the IPW algorithm, with higher efficiency compared to the RPA algorithm, can be applied to the subchannels such as Subchannel 1.
6. Conclusions
In this chapter, we study the power allocation problem in OFDMbased cognitive radio systems.
In the cognitive radio scenario, the interference limits of the primary users introduce subchannel power constraints for the transmission of the SU. Therefore, the power allocation among the subcarriers should satisfy both the sum transmit power constraint, as that in conventional OFDM systems, as well as the subchannel power constraints, which leads to the unavailability of the wellknown waterfilling algorithm applied in conventional OFDM systems.
In order to find the optimal power allocation, we first propose the IPW algorithms, whose basic computation units is the conventional waterfilling. The algorithm is proved to converge to the optimal power allocation, which maximizes the sum rate when the sum transmit power constraint is given or minimizes the required power when the target rate is given, after a finite number of iterations.
Furthermore, we consider the effects of subcarrier sidelobes on the power allocation in practical systems. We note that the actual transmit power in one subchannel is comprised of the allocated power as well as the subcarrier sidelobes power from the neighboring subchannels. The RPA algorithm is proposed for this scenario. The algorithm finds the optimal power allocation recursively by decoupling the subchannel power constraints phasebyphase. Simulation results show that the IPW algorithm is unavailable when the guard bands between the subchannels are not wide enough, while the RPA algorithm can be applied in such scenario. In conventional OFDM systems, bit loading is a more practical technique for the system design. Therefore, it is interesting to study bit loading algorithms in OFDMbased cognitive radio systems, where the subchannel transmit power constraints should be considered.
This work is partially supported by International Science and Technology Cooperation Program (2008DFA12160) and National Basic Research Program of China (2007CB310608).
References
 1.
Bansal G. Hossain J. Bhargava V. 2007 Adaptive power loading for OFDMbased cognitive radio systems. ,  2.
Berthold U. Jondral F. 2005 Guidelines for designing OFDM overlay systems. ,  3.
Boyd S. Vandenberghe L. 2004  4.
Cabric D. Mishra S. Brodersen R. 2004  5.
Cosovic I. Brandes S. Schnell M. 2005  6.
Federal Communications Commission Spectrum Policy Task Force. 2002  7.
Ghasemi A. Sousa E. 2007 Spectrum sensing in cognitive radio networks: the cooperationprocessing tradeoff. ,  8.
Haykin S. 2005 Cognitive radio: brainempowered wireless communications. ,  9.
Kim H. Shin K. 2007 Efficient discovery of spectrum opportunities with MACLayer sensing in cognitive radio networks. ,  10.
Le L. Hossain E. 2007  11.
Mahmoud H. Arslan H. 2008 Sidelobe suppression in OFDMbased spectrum sharing systems using adaptive symbol transition. ,  12.
Mc Henry M. 2005 NSF spectrum occupancy measurements project summary. ,  13.
Mitola J. 1999 Cognitive radio for flexible mobile multimedia communications. ,  14.
Oner M. Jondral F. 2007 On the extraction of the channel allocation information in spectrum pooling systems. ,  15.
Pagadarai S. Rajbanshi R. Wyglinski A. Minden G. 2008  16.
Zhao Q. Sadler B. 2007 A survey of dynamic spectrum access: signal processing, networking, and regulatory policy. ,  17.
Sahai A. Hoven N. Tandra R. 2004 Some fundamental limits on cognitive radio,  18.
Shu T. Cui S. Krunz M. 2006 Medium access control for multichannel parallel transmission in cognitive radio networks,  19.
Sudhir S. Jafar S. 2007 Soft sensing and optimal power control for cognitive radio,  20.
T. S. E. D. Viswanath P. 2005  21.
Weiss T. Jondral F. 2004 Spectrum pooling: an innovative strategy for the enhancement of spectrum efficiency. ,  22.
Weiss T. Hillenbrand J. Krohn A. Jondral F. 2004 Mutual interference in OFDMbased spectrum pooling systems,  23.
Zhang L. Liang Y. Xin Y. 2008 Joint beamforming and power allocation for multiple access channels in cognitive radio networks. ,  24.
Zhao Q. Tong L. Swami A. Chen Y. 2007 Decentralized cognitive MAC for opportunistic spectrum access in Ad Hoc networks: a POMDP framework. ,
Notes
 Here, without considering subcarrier sidelobes, the allocated power is exactly the transmit power.
 Using the IPW algorithm in Table 2 has the similar results as mentioned in Section 3.4.
 This work is partially supported by International Science and Technology Cooperation Program (2008DFA12160) and National Basic Research Program of China (2007CB310608).