# A Resource Allocation Evolutionary Algorithm for OFDM Based on Karush-Kuhn-Tucker Conditions

Authors: Hai-Lin Liu; Qiang Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

For orthogonal frequency division multiplexing
(OFDM), resource scheduling plays an important role. In
resource scheduling, power allocation and subcarrier allocation
are not independent. So the conventional two-step method
is not very good for OFDM resource allocation. This paper
proposes a new method for OFDM resource allocation. This
method combines evolutionary algorithm (EA) with Karush-Kuhn-Tucker conditions (KKT conditions). In the optimizing
process, a set of subcarrier allocation programs are made as
a population of evolutionary algorithm. For each subcarrier
allocation program, a power allocation program is calculated
through KKT conditions. Then, the system rate of each subcarrier
allocation program can be calculated. The fitness of
each individual is its system rate. The information of optimizing
subcarrier and power allocation can be interacted with each other.
So, it can overcome the shortcoming of the two-step method.
Computer experiments show the proposed algorithm is effective.


---

## Body

## 1. Introduction

Orthogonal frequency division multiplexing (OFDM) has attracted more and more research interest because it is a potential solution for high-rate data service demands [1]. In OFDM system, the high speed data flow is divided into a lot of slow speed data flows. So, the inters symbol interference (ISI) can be reduced greatly. Meanwhile different subcarrier’s channel fading condition is independent, so, the OFDM resource allocation has high flexibility. The flexibility of multiuser access can also be improved. The principle of OFDM is described in Figure 1.Figure 1
System model of the downlink MU-OFDM.The resource allocation problems in OFDM system have two different types of analytical perspectives: one is to maximize the system capacity (RA) when the emission power is limited; the other is to minimize the transmit power (ME) under the condition that the system capacity is limited. However, in the fourth-generation mobile communication system, the main business is the users experience. Therefore, the former perspective causes more attention.Resource allocation algorithms can be classified into two categories: (a) the model can be solved directly. However, it may get an exact result; the computational complexity is too high. (b) The solving process is divided into several steps through some executive strategies. Though it cannot get such an exact solution, it is simple and easy to handle. After optimization, the progress shows the proposed solution is of acceptable accuracy. The two-step method is described as an effective algorithm. In a two-step method, we first considerate subcarrier allocation then the power allocation. This method may result in low complexity and fast solution speed.The recent research on the two-step method focuses on the rules of subcarrier allocation with the purpose to take capacity of system and fairness into account. But most attention is paid to find a good algorithm to optimize the power allocation so as to maximize the system capacity. For the optimization of the power distribution, the main methods are classical deterministic optimization algorithm and intelligent optimization algorithms.At present, most algorithms for OFDM resource allocation focus on how to improve solution efficiency based on system fairness. Algorithms proposed in [2–5] were based on the gradient information. In early research, the affusion algorithm attracted the attention of most scholars. It can maximize the system but make the system fairness worse. Making use of the gradient information, article [2] defined a kind of system throughout increase. For each power allocation, enhanced power was allocated to the user who had the maximum throughout. By introducing the constraint conditions according to the definition of throughout increase, the system can enhance throughout and meet the fairness. In paper [3], a framework of algorithm based on gradient information was presented. The model was expressed as a graph optimization problem, and it resolves the problem with dual decomposition. Considering that OFDM resource allocation model is a nonlinear optimization problem, the literature in [5–10] uses Lagrange method to measure resource allocation. Based on Lagrange method, the literature in [11] introduced a self-adaptive iterative algorithm in order to meet the system fairness. In paper [8], the model was converted into problem in graph theory and was solved with graph theory combined with Lagrange method, which gave a satisfactory result. In paper [9], the model was converted into a convex optimization problem, which could be efficiently solved by Lagrange method. Also, many algorithms were put forward by introducing some specific strategies to deal with OFDM resource allocation problem. In these algorithms, classical or intelligent optimization algorithms did not appear, as presented in the literature in [12–20]. By introducing the concept of pareto efficiency, paper [18] presented the trade-off program between operators and users’ service. The literature in [21–27] solved OFDM resource allocation problem with intelligent algorithm which takes the advantages of simple operation and convenient calculation. By introducing weight factors, paper [25] combined transmit power and system capacity to a cost function. A modified PSO algorithm was presented to solve the problem and got good performance. Paper [26] presented a multiobjective optimization model for determining the transmit power and system capacity, respectively, and used NSGA-2 algorithm to solve the problem. Due to the mutual restrictive relationship between transmit power and system capacity, a variable was optimized while the other performed worse. Therefore, it is feasible to use multiobjective algorithm for optimization.Above, most of the literature is based on two-step method. Firstly, subcarrier is allocated, and then, the model is optimized. The two-step method can significantly reduce the complexity of the algorithm. But because the subcarrier allocation and power allocation are dependent, it is unreasonable to allocate subcarrier and power separately. So, the efficiency of the algorithm is not very high. However, if subcarrier allocation and power allocation are optimized at the same time, the complexity of the algorithm is so high that it does not meet the instantaneous requirements for mobile communication system. Therefore, it is expected to improve the accuracy and efficiency of algorithm if the information of subcarrier allocation and power allocation is able to interact with each other in each iteration.A hybrid evolutionary algorithm for OFDM resource allocation is proposed in this paper. In this algorithm, the subcarrier and power allocation is optimized by turns. Because the OFDM resource allocation is a hybrid optimization problem, the discrete and continuous variables can be optimized by evolutionary algorithm and KKT conditions, respectively. This algorithm, firstly, generates a group subcarrier allocation program, and then, the corresponding power allocation program is generated by KKT conditions. The system rate of each subcarriers can be obtained. For the evolutionary algorithm, the set of subcarrier is regarded as a population. The system rate is the fitness of each individual. In the optimizing process, the subcarrier and power allocation information can be used with each other. So this algorithm is more efficient.The remainder of the paper is organized as follows: the model of OFDM resource allocation and algorithm is described at Sections2 and 3, computer simulation results are shown at Section 4, and conclusions are drawn at Section 5.


## 2. The Model of OFDM Resource Allocation

Considering that spectrum resources are limited, OFDM resource allocation plays an important role in the 4th generation mobile communication system. Each eNodeB has a lot of orthogonal subcarriers allocated to each user. The core problem of OFDM resource allocation is which subcarriers should be allocated to a user and how much each subcarrier’s power should be.Assume that there areN subcarriers shared by K users; define the channel gain of the kth user on the nth subcarrier gk,n; the noise power is σ2=(N0B)/N, where N0 is noise power spectral density. The signal-to-noise ratio (SNR) is hk,n=gk,n2/σ2. The capacity of user k on subcarrier n is normalized by rk,n=(1/N)ln(1+(pk,nhk,n/Γ)), where Γ is a constant. So, data rate of user k can be written as
(1)Rk=∑n=1N‍wk,nNln(1+pk,nhk,nΓ).
The mathematic model of resource allocation problem can be described as follows:
(2)maxF(W,P)=∑k=1K‍∑n=1N‍wk,nNln(1+pk,nhk,nΓ)(3)s.t∑k=1K‍∑n=1N‍pk,n≤PTs.t∑k=1K‍wk,n≤1∀ns.tpk,n≥0,wk,n≥0,∀k,∀n,
where wk,n∈{0,1}. It means the nth subcarrier is allocated to the kth user when wk,n is 1. If wk,n is 0, it means the nth subcarrier is not allocated to the kth user. PT is the total transmit power. P=(pk,n)K×N, W=(wk,n)K×N.


## 3. Karush-Kuhn-Tucker Theorem

KKT conditions are proposed by Karush and Kuhn and Tucker independently. KKT conditions are first-order necessary conditions to solve optimization problem with equality and inequality constraints.Consider the following maximization problem(4)maxf(x)s.tgj(x)≥0,j=1,2,…,ms.thi(x)=0,i=1,2,…,n
with f:RN→R,gj:RN→Rp,hi:RN→Rm being continuously differentiable functions.Kuhn-Tucker Theorem. If x* is a (local) optimum of the problem
(5)maxf(x)(6)s.tgj(x)≥0,j=1,2,…,m(7)s.thi(x)=0,i=1,2,…,n(8)
∇
f
(
x
*
)
+
∇
g
(
x
*
)
λ
*
+
∇
h
(
x
*
)
μ
*
=
0
,
h
(
x
*
)
=
0
,
g
(
x
*
)
≥
0
,
λ
*
≥
0
,
λ
*
g
(
x
*
)
=
0
.Equation (10) means ∇f is the linear combination of ∇g and ∇h, where λ* and μ* are called Lagrange multiplier. Equation (11) means the optimal point must meet all the constraints including equality and inequality constraints. That is to say the optimal point should be a feasible solution.


## 4. Making Use of KKT Conditions

For OFDM resource allocation problem, after the subcarrier assignment is completed, the above model becomes(9)maxF(W¯,P)=∑k=1K‍∑n=1N‍w¯k,nNln(1+pk,nhk,nΓ)(10)s.t∑k=1K‍∑n=1N‍pk,n≤PTs.tpk,n≥0,k=1,2,…,K,n=1,2,…,N,
where W¯, w¯k,n are known quantity. Equation (15) is a nonlinear equation, and it is continuous and differentiable. When pk,n>0, gk,n=hk,n/Γ, a stagnation point of the equation can be obtained by KKT conditions:
(11)∂L∂pk,n=gk,n1+pk,ngk,n-λ≤0,(12)pk,n(gk,n1+pk,ngk,n-λ)=0,k=1,2,…,K,n=1,2,…,Nλ∂L∂λ=0
Because pk,n≥0, from (10), we can get
(13)gk,n1+pk,ngk,n-λ=0,∑k=1K‍∑n=1N‍pk,n-PT=0
by (12). pk,n can be calculated by
(14)pk,n(W¯)=PT+∑k=1K‍(w¯k,n/N)∑n=1N‍gk,nK×N-1gk,n.


## 5. Hybrid Evolutionary Algorithm for OFDM Resource Allocation

Goldberg proposed the evolutionary algorithm’s commonly form. The evolutionary algorithm (EA) simulates the natural selection in biological evolution. It is essentially a random search algorithm. EA's global search ability is excellent, and EA dose not demand the objective function continuous or differentiable. In (2), the variable wk,n is discrete, so EA can be used to solve subcarrier allocation. Meanwhile, KKT conditions are used to solve the variable pk,n by (14). Since the allocation of subcarrier and power is not independent, it is rational to combine these two algorithms to solve resource allocation problem.For OFDM resource allocation, the two-step method cannot get a good solution because the allocation of subcarrier and power is not independent. In this paper, we propose a new resource allocation program based on KKT conditions. This new program combines evolutionary algorithm and KKT conditions. Firstly, we randomly generate some subcarrier allocation programW1,W2,…,Wm. For each Wi, there is F(Wi,P), (i=1,2,…,m), and each F(Wi,P) has only one variable P. F(Wi,P) can be solved by (14). Assume the solution is Pi; for each Wi, we can get a Pi, (i=1,2,…,m). When Wi and Pi are known, we can get Fi. Fi is the system rate corresponding to Wi. As previously described, Fi is not a good result. Then, the proposed algorithm optimizes Wi,(i=1,2,…,m) using evolutionary algorithm. Assume that W1(t),W2(t),…,Wm(t) is t generation population of evolutionary algorithm; through (14), the P1(t),P2(t),…,Pm(t) can be calculated. Select individuals from W1(t),W2(t),…,Wm(t) to cross over and mutate. Then, new individuals are generated. Each new individual’s power allocation can be calculated trough (14). According to every new individual’s power allocation, select next generation individuals W1(t+1),W2(t+1),…,Wm(t+1). So, the information of power and subcarrier allocation can make full use of each other. It is described in Figure 2.Figure 2
The information of optimizing subcarrier and power allocation can interact with each other.


### 5.1. Fitness Function

A hybrid evolutionary algorithm for OFDM resource allocation is proposed in this paper. This algorithm firstly generates a set of subcarrier allocation programsW1,W2,…,Wm, where Wi is ith subcarrier allocation program, i=1,2,…,m. For each Wi, its corresponding power allocation pi can be obtained through (14), then, the fitness function of Wi=(wk,ni)K×N can be calculated as follows:
(15)F(Wi,P)=∑k=1K‍∑n=1N‍wk,niNln(1+pk,nhk,nΓ).


### 5.2. Encoding of Solutions

Evolutionary algorithm has attracted more and more attentions because of its good performance in the engineering field. For evolutionary algorithm, encoding is one of the most important parts in EA. An excellent encoding method cannot only avoid generating illegal solutions but also improve the performance of the algorithm.The subcarrier allocation programW is a K×N matrix as follows:
(16)W=(100…010011…001000…100000…000………000…000).
It is clear that there is only one 1 in each column, which means each subcarrier can only be allocated to one user. When K and N are very large, the computational process expends a lot of time. What is more, the process of crossover and mutation would be very complex. So, it is necessary to encode W for simple operation. In this paper, W is encoded as follows:
(17)W=(w1,w2,…,wN),
where wi indicates the ith subcarrier allocated to with user. For example, if wi is 5, it means the ith subcarrier is allocated to the 5th user.P is also a K×N matrix as follows:
(18)P=(p1,1p1,2p1,3…p1,Np2,1p2,2p2,3…p2,N………………………pK,1pK,2pK,3…pK,N),
where pi,j is the power of the jth subcarrier allocated to ith user. When W is known, P can be simplified into
(19)P=(p1,p2,…,pN),
where pi is the power of ith subcarrier. For example, if pi=0.5, it means the ith subcarrier’s power is 0.5 w.


### 5.3. The Proposed Algorithm’s Framework

The hybrid evolutionary algorithm proposed in this paper firstly generates a set of subcarrier allocation programsW1,W2,W3,…,Wm. Then, we can obtain the power allocation program corresponding to each subcarrier allocation program from (14). Substituting Wi and Pi in (14), we can get each individual's fitness F(Wi,Pi) of Wi. These subcarrier allocation programs are regarded as a population, and each subcarrier allocation program is an individual. The fitness of each individual is the system rate obtained by (15). After crossover and mutation, we can get a new population constituted by new subcarrier allocation programs. A new power allocation program and system rate can be calculated. Repeat the above steps; the information optimizing power and the subcarrier allocation can interact with each other. Therefore, the performance of the algorithm is improved greatly. According to the above description, the framework of hybrid evolutionary algorithm for OFDM resource allocation is as follows.The Proposed AlgorithmStep 1.
Generate a set of subcarrier allocation programs{W1,W2,…,Wm} as the initial population, denoted as pop.Step 2.
Calculate the fitness of each individual according to (15).Step 3.
Select individuals from pool to crossover, and generate offspring population, denoted aschild.Step 4.
Select individuals fromchild to mutate in mutation probability and update child.Step 5.
Renewpopwith child.Step 6.
If the stopping criteria are unsatisfied, go to Step2; otherwise, stop.


## 5.1. Fitness Function

A hybrid evolutionary algorithm for OFDM resource allocation is proposed in this paper. This algorithm firstly generates a set of subcarrier allocation programsW1,W2,…,Wm, where Wi is ith subcarrier allocation program, i=1,2,…,m. For each Wi, its corresponding power allocation pi can be obtained through (14), then, the fitness function of Wi=(wk,ni)K×N can be calculated as follows:
(15)F(Wi,P)=∑k=1K‍∑n=1N‍wk,niNln(1+pk,nhk,nΓ).


## 5.2. Encoding of Solutions

Evolutionary algorithm has attracted more and more attentions because of its good performance in the engineering field. For evolutionary algorithm, encoding is one of the most important parts in EA. An excellent encoding method cannot only avoid generating illegal solutions but also improve the performance of the algorithm.The subcarrier allocation programW is a K×N matrix as follows:
(16)W=(100…010011…001000…100000…000………000…000).
It is clear that there is only one 1 in each column, which means each subcarrier can only be allocated to one user. When K and N are very large, the computational process expends a lot of time. What is more, the process of crossover and mutation would be very complex. So, it is necessary to encode W for simple operation. In this paper, W is encoded as follows:
(17)W=(w1,w2,…,wN),
where wi indicates the ith subcarrier allocated to with user. For example, if wi is 5, it means the ith subcarrier is allocated to the 5th user.P is also a K×N matrix as follows:
(18)P=(p1,1p1,2p1,3…p1,Np2,1p2,2p2,3…p2,N………………………pK,1pK,2pK,3…pK,N),
where pi,j is the power of the jth subcarrier allocated to ith user. When W is known, P can be simplified into
(19)P=(p1,p2,…,pN),
where pi is the power of ith subcarrier. For example, if pi=0.5, it means the ith subcarrier’s power is 0.5 w.


## 5.3. The Proposed Algorithm’s Framework

The hybrid evolutionary algorithm proposed in this paper firstly generates a set of subcarrier allocation programsW1,W2,W3,…,Wm. Then, we can obtain the power allocation program corresponding to each subcarrier allocation program from (14). Substituting Wi and Pi in (14), we can get each individual's fitness F(Wi,Pi) of Wi. These subcarrier allocation programs are regarded as a population, and each subcarrier allocation program is an individual. The fitness of each individual is the system rate obtained by (15). After crossover and mutation, we can get a new population constituted by new subcarrier allocation programs. A new power allocation program and system rate can be calculated. Repeat the above steps; the information optimizing power and the subcarrier allocation can interact with each other. Therefore, the performance of the algorithm is improved greatly. According to the above description, the framework of hybrid evolutionary algorithm for OFDM resource allocation is as follows.The Proposed AlgorithmStep 1.
Generate a set of subcarrier allocation programs{W1,W2,…,Wm} as the initial population, denoted as pop.Step 2.
Calculate the fitness of each individual according to (15).Step 3.
Select individuals from pool to crossover, and generate offspring population, denoted aschild.Step 4.
Select individuals fromchild to mutate in mutation probability and update child.Step 5.
Renewpopwith child.Step 6.
If the stopping criteria are unsatisfied, go to Step2; otherwise, stop.


## 6. Computer Simulation

We compare the proposed algorithm with [10, 25] in the aspects of the transmit power and system capacity in case the number of users changes from 2 to 12. In the numerical simulations, the channel is modeled as slow-varying Rayleigh and its components have independent identically distributed complex values with zero-mean and unit variance. Total transmit power, BER, and the total bandwidth are set as 0.1 w, 10-3, and 1 MHZ, respectively. The number of subcarrier is 64, and the crossover probability and mutation probability are 0.8 and 0.01.Figure3 shows the performance of the maximum data rate with growth of the number of users. Figure 4 also shows that the system total rate calculated by the three algorithms is almost the same when the number of users is less. However, as the number of users increases, the performance of the algorithm presented by this paper is better than that of the other two algorithms. Then, we test the proposed algorithm’s minimum transmit power and compare it with MPSO [25] and PFA [10]. As it is shown in Figure 4, when the number of users is less than 4, the proposed algorithm’s performance is not better than that of the other two algorithms. However, since the proposed algorithm combines evolutionary algorithm with KKT conditions, it becomes better than MPSO and PFA with the users number increasing. It is clear that the proposed algorithm has superior performance.Figure 3
System throughput versus number of users.Figure 4
Minimum transmit power versus number of users.Figure5 shows the minimum user capacity of the proposed algorithm, MPSO, and PFA with growth of the total users number. If the minimum user capacity is increased, the total system rate can also increase. From Figure 5, MPSO’s minimum user capacity is much larger than that of PFA, and the proposed algorithm’s minimum user capacity is much larger than MPSO.Figure 5
minimum user capacity for multiuser OFDM versus number of users for proposed algorithm and other methods.Then, this paper compares the capacity of the proposed algorithm, MPSO, and PFA under different SNR with 4 users. The comparison result is shown in Figure6. From Figure 6, it is clear that the proposed algorithm’s performance is better than the other two algorithms. When SNR is less than 15 dB, the performance of the proposed algorithm improves slowly, although it is also better than the other two algorithms. With the increasing of SNR, the proposed algorithm’s performance enhances more and more fast. Figure 8 shows the minimum transmit power of the proposed algorithm, MPSO, and PFA under different SNR with 8 users. From Figure 8, the proposed algorithm’s minimum transmit power is less than that of the other two algorithms.Figure 6
Capacity comparison of our algorithm and other two algorithms as the distributions of 4 users are different.Figure7 shows the capacity comparison of the proposed algorithm and the other two algorithms with different distance, and the number of user is 4. From Figure 7, the total capacity is reducing with the distance becoming longer and longer. And the proposed algorithm shows a better performance against the increase of distance.Figure 7
Capacity comparison of our algorithm and another two algorithms with different distance.Figure 8
Minimum transmit power of our algorithm and another two algorithms as the distributions of 8 users are different.In Table1, we calculate the execution time to reach the target capacity needed by the proposed algorithm, MPSO, and PFA, respectively. The target capacity is preset to 14 bit/s/Hz with 12 users. It is clear that the proposed algorithm can reach the target capacity more fast. It is more efficient to run the proposed algorithm than to run other two algorithms. It is mainly because the proposed algorithm optimizes subcarrier and power allocation at the same time, and in this algorithm, the information of subcarrier and power allocation can interact with each other. So, the proposed algorithm’s convergence is better.Table 1
Run index
Proposed algorithm
MPSO
PFA
1
1.407
3.012
1.112
2
1.507
3.105
1.203
3
1.426
3.125
1.235
4
1.620
3.106
1.135
5
1.526
2.988
1.125
6
1.458
3.241
1.109
7
1.635
3.075
1.246
8
1.425
3.005
1.106
9
1.326
3.276
1.011
10
1.427
3.006
1.189Tables2 and 4 are system rate variance for 100 experiments and minimize power variance for 100 experiments, respectively, when the users number changes from 2 to 6. Tables 3 and 5 are system rate variance for 100 experiments and minimizing power variance for 100 experiments respectively, when the users number changes from 8 to 12. They reflect the the stability of algorithm.Table 2
System rate variance for 100 experiments.
Algorithm
2 users
4 users
6 users
Proposed algorithm
0.00000
0.00060
0.00150
MPSO
0.00000
0.00220
0.00760
PFA
0.00000
0.00120
0.00550Table 3
System rate variance for 100 experiments.
Algorithm
8 users
10 users
12 users
Proposed algorithm
0.00230
0.00700
0.00960
MPSO
0.00940
0.01200
0.01820
PFA
0.00770
0.00850
0.00920Table 4
Minimize power variance for 100 experiments.
Algorithm
2 users
4 users
6 users
Proposed algorithm
0.00000
0.00000
0.00080
MPSO
0.00000
0.00060
0.00240
PFA
0.00000
0.00000
0.00120Table 5
Minimize power variance for 100 experiments.
Algorithm
8 users
10 users
12 users
Proposed algorithm
0.00085
0.00090
0.00130
MPSO
0.00270
0.00320
0.00390
PFA
0.00160
0.00200
0.00340These four tables show the stability of the proposed algorithm is similar to PFA and is better than MPSO in the case of 2 users and 4 users. In the case of more than 6 users, the stability of our proposed algorithm is better than that of MPSO and PFA.


## 7. Conclusions

Since the subcarrier and power allocation are dependent, it is reasonable to optimize them at the same time. However, because the subcarrier allocation is a discrete problem and the power allocation is a continuous problem, it is very difficult to optimize subcarrier and power allocation at the same time. This paper proposes a hybrid evolutionary algorithm for OFDM resource allocation. This algorithm can optimize subcarrier allocation and transmit power alternately. The process optimizing power allocation can take advantage of the information of subcarrier allocation, and the process optimizing subcarrier allocation can also take advantage of the information of power allocation. Therefore, the information optimizing power and subcarrier allocation can interact with each other, and the efficiency of the algorithm can be improved significantly. The computer simulation shows that the proposed algorithm increases the system rate apparently.



---

*Source: 406143-2013-04-21.xml*