Comparison of computational complexity for CCDF=1e-3 among different PTS Schemes

## 1. Introduction

Several evolutionary algorithms (EAs) have emerged in the past decade that mimic biological entities behavior and evolution. Darwin’s theory of evolution is the major inspiration source for EAs. The foundation of Darwin’s theory of evolution is natural selection. The study of evolutionary algorithms began in the 1960s. Several researchers independently developed three mainstream evolutionary algorithms, namely, genetic algorithms [1, 2], evolutionary programming [3], and evolution strategies [4]. EAs are widely used for the solution of single and multi-objective optimization problems. Swarm Intelligence (SI) algorithms are also a special type of EAs. SI can be defined as the collective behavior of decentralized and self-organized swarms. SI algorithms among others include Particle Swarm Optimization (PSO) [5], Ant Colony Optimization [6], and Artificial Bee Colony (ABC) [7].

PSO is an evolutionary algorithm that mimics the swarm behavior of bird flocking and fish schooling [5]. The most common PSO algorithms include the classical Inertia Weight PSO (IWPSO) and Constriction Factor PSO (CFPSO) [8]. PSO is an easy to implement algorithm with computational efficiency. The PSO algorithm is inherently used only for real-valued problems. An option to expand PSO for discrete valued problems also exists. Among others PSO algorithms include, the barebones (BB) and the exploiting barebones (BBExp). BBPSO has been successfully applied to the cell to switch assignment problem [9].

Artificial Bee Colony (ABC) [7] is a recently proposed SI algorithm, which has been applied to several real world engineering problems. The ABC algorithm models and simulates the honey bee behavior in food foraging. In the ABC algorithm, a potential solution to the optimization problem is represented by the position of a food source while the food source corresponds to the quality (objective function fitness) of the associated solution. The ABC algorithm has been successfully applied to several problems in wireless communications [10]. ABC variants that improve the original algorithm have also been proposed [11].

Ant Colony Optimization (ACO) is a population-based metaheuristic introduced by Marco Dorigo [12]. This algorithm was inspired by the behaviour of real ants. The algorithm is based on the fact that ant colonies can find the shortest path between their nest and a food source just by depositing and reacting to pheromones while they are exploring their environment. ACO is suitable for solving combinatorial optimization problems, which are common in wireless communications.

Differential evolution (DE) [13, 14] is a population-based stochastic global optimization algorithm, which has been used in several real world engineering problems. Several DE variants or strategies exist. One of the DE advantages is that very few control parameters have to be adjusted in each algorithm run. However, the control parameters involved in DE are highly dependent on the optimization problem. Moreover, the selection of the appropriate strategy for trial vector generation requires additional computational time using a trial-and-error search procedure. Therefore, it is not always an easy task to fine-tune the control parameters and strategy. Since finding the suitable control parameter values and strategy in such a way is often very time-consuming, there has been an increasing interest among researchers in designing new adaptive and self-adaptive DE variants. Self adaptive DE (SaDE), is a DE algorithm that self-adapts both control parameters and strategy based on learning experiences from previous generations is presented in [15-17]. SaDE has been applied to microwave filter design, [18], and to antenna arrays synthesis [19].

The purpose of this chapter is to briefly describe the above algorithms and present their application to wireless communications optimization problems found in the literature. This chapter also presents results from different cases using PSO, ABC, ACO and DE. These include the cell to switch assignment problem in cellular networks using PSO algorithms, peak to average power ratio (PAPR) reduction of OFDM signals with the partial transmit sequences (PTS) approach using ABC and ACO algorithms [7, 11], and dual-band microwave filter design for wireless communications using SADE.

This chapter is subdivided into four sections. Section 2 presents the different evolutionary algorithms. Section 3 reviews the related work in wireless communications problems from the literature. Section 4 describes the design cases and presents the numerical results. Finally section 5 contains the discussion about the advantages of using a EA-based approach and the conclusions.

## 2. Methods

A population (or swarm) in PSO, ABC, ACO and DE consists of *D*-dimensional vector represents a possible solution, which is expressed as:

The population is initialized as follows:

where *D*-dimensional vectors of the lower and upper bounds respectively and

### 2.1. Particle Swarm Optimization (PSO)

In PSO, the particles move in the search space, where each particle position is updated by two optimum values. The first one is the best solution (fitness) that has been achieved so far. This value is called *pbest*. The other one is the global best value obtained so far by any particle in the swarm. This best value is called *gbest*. After finding the *pbest* and *gbest*, the velocity update rule is an important factor in a PSO algorithm. The most commonly used algorithm defines that the velocity of each particle for every problem dimension is updated with the following equation:

where ^{th} particle velocity in the n^{th} dimension, *G+1* denotes the current iteration and *G* the previous,

The parameter

Clerc [8] suggested the use of a different velocity update rule, which introduced a parameter

where

### 2.2. Barebones PSO

Kennedy [20] proposed a new PSO approach, the BB PSO, where the standard PSO velocity equation is replaced with samples from a normal distribution. In this method, the position update rule for the *i*th particle in the n^{th} dimension becomes

*N*( , ) denotes the normal distribution. The method allows particles with *pbest* significant different from *gbest* to make large step sizes towards it. When *pbest* is close to *gbest*, step size decreases and limits exploration in favor of exploitation.

In [20], a variation of BB PSO, the BBExp PSO, was also proposed. In this method, approximately half of the time velocity is based on samples from a normal distribution; for the rest of the time, velocity is derived from the particle's personal best position. The position update rule, (6), is modified into

where *U*( , ) denotes the uniform distribution. In BBExp PSO, position updates equal *pbest*_{n} for half of the time resulting in the improved exploitation of *pbest*_{n} compared to the BB PSO. One may notice

that the barebones PSO algorithms do not require parameter tuning. More details can be found in [20, 21].

### 2.3. Artificial bee colony optimization

The ABC algorithm models and simulates the honey bee behavior in food foraging. In ABC algorithm, a potential solution to the optimization problem is represented by the position of a food source while the nectar amount of a food source corresponds to the quality (objective function fitness) of the associated solution. In order to find the best solution the algorithm defines three classes of bees: employed bees, onlooker bees and scout bees. The employed bee searches for the food sources, the onlooker bee makes a decision to choose the food sources by sharing the information of employed bee, and the scout bee is used to determine a new food source if a food source is abandoned by the employed bee and onlooker bee. For each food source exists only one employed bee (i.e. the number of the employed bees is equal to the number of solutions). The employed bees search for new neighbor food source near of their hive. A new position of the *D* is the problem dimension, is generated using

where

where

An onlooker bee chooses a food source depending on the probability value associated with that food source,

where

where

### 2.4. Ant colony optimization

Ant colony optimization (ACO) [6, 12, 22] is a meta-heuristic inspired by the ants’ foraging behavior. At the core of this behavior is the indirect communication between the ants by means of chemical pheromone trails, which enables them to find short paths between their nest and food sources. Ants can sense pheromone. When they decide path to follow a path, they tend to choose the ones with strong pheromone intensities way back to the nest or to the food source. Therefore, shorter paths would accumulate more pheromone than longer ones. This feature of real ant colonies is exploited in ACO algorithms in order to solve combinatorial optimization problems considered to be NP-Hard.

### 2.5. Differential Evolution (DE)

The initial population evolves in each generation with the use of three operators: mutation, crossover and selection. Depending on the form of these operators several DE variants or strategies exist in the literature [14, 23]. The choice of the best DE strategy depends on problem type [24]. In SaDE the following four strategies are used for trial vector generation. These include *DE/rand/1bin*, *DE/rand-to-best/2/bin*, *DE/rand/2/bin*, and *DE/current-to-rand/1* [25]. In these strategies a mutant vector

where *i*, *K* a coefficient responsible for the level of recombination that occurs between

where

where

### 2.6. Self-Adaptive DE (SADE)

In the SaDE algorithm both the trial vector generation strategies and the control parameters are self-adapted according to previous learning experiences. SaDE maintains a strategy candidate pool, consisting of the four strategies given in (2). Each strategy is assigned a certain probability. The sum of all probabilities is equal to one. These probabilities are initialized with a value of 0.25 and gradually adapted during evolution. The probability of applying the *m-th* strategy is *M* is the total number of strategies. At generation *G*, the number of successful trial vectors generated by the *m-th* strategy is denoted as

where *m-th* strategy within the previous LP generation and

The control parameters are self-adapted in the following way. The mutation control parameter *K* is a random number in the interval [0, 1] generated by a uniform distribution. The crossover rate control parameter *m-th* strategy is also approximated by a normal distribution with mean value *m-th* strategy

## 3. Related work

This section presents a brief literature review of applications of evolutionary algorithms and their variants to wireless communications problems.

Genetic algorithms (GAs) are among the widely used optimization techniques for addressing design problems in wireless communications. In [26] a Smith prediction filter is proposed for power control design of direct-sequence code-division multiple-access cellular mobile radio systems. A fixed-order robust H∞ loop filter is developed using a genetic algorithm to minimize the worst-case variance of the received SINR from the minimax perspective. The authors in [27] present an antenna selection method for multiple-input multiple-output wireless systems based on a GA that seeks the best subset of antenna elements. The problem of receive antenna selection and symbol detection for multiple-input, multiple-output (MIMO) systems is solved in [28] by applying a genetic algorithm (GA) variant. The paper in [29] addresses the problem of joint transmit/receive antenna selection for MIMO systems using a real-valued genetic algorithm (RVGA). The optimization objective is to improve the channel capacity of multiple-input/multiple-output (MIMO) systems. The study in [30] presents a pattern discovery algorithm for multi-streams mining in wireless sensor networks. This algorithm adapts genetic operators with Elitism Strategy.The paper in [31] studies joint multiuser linear precoding design in the forward link of fixed multibeam satellite systems. The authors use a generic optimization framework for linear precoding design to handle any objective functions of data rate with general linear and nonlinear power constraints. In [32] an energy-efficient genetic algorithm mechanism is presented to resolve quality of service (QoS) multicast routing problem: The proposed genetic algorithm depends on bounded end-to-end delay and minimum energy cost of the multicast tree.

SI algorithms are among the most commonly used algorithms for solving problems in wireless communications. PSO and several PSO variants have been used in the literature to solve different problems. In [33] optimal power scheduling for distributed detection in a Gaussian sensor network is addressed for both independent and correlated observations. A PSO based technique is developed to find the optimal power allocation for arbitrary correlations. The authors in [34] apply PSO to solve the constrained nonlinear optimisation problem for the minimum bit error rate (MBER) multiuser transmitter (MUT). The proposed PSO aided symbol-specific MBER-MUT and average MBER-MUT schemes provide improved performance in comparison to the conventional minimum mean-square error MUT scheme. Several issues in Wireless Sensor Networks (WSNs) can be formulated as multidimensional optimization problems, and addressed using bio-inspired algorithms. In [35] the authors present a brief survey of how PSO is used to address these issues. The authors in [36] propose a new approach to estimate the location of a sensor in a wireless sensor network based on a new PSO algorithm with a log-barrier approach. The paper in [37] presents a predistorter based on a cluster-based implementation particle swarm optimization technique with embedded model-size estimation capability and validates the proposed technique on a Doherty power amplifier prototype.

The ABC algorithm and its variants have been successfully applied to several optimization problems in wireless communications. Among others these include issues in WSN [38-41], WiMax network planning [42] and channel assignment [43].

The ACO algorithm has also been applied to several combinatorial problems in wireless systems which include problems in mobile ad hoc networks [44-46], problems in WSN [47-51], cognitive radio [52], resource allocation in multiuser OFDM systems [53] and MIMO problems [54, 55].

DE variants have also been applied to variety of optimization problems like multi-user detection in multi-carrier CDMA [56], WSNs issues [57, 58], urban area path loss prediction [59], spectrum sharing [60], optimization of interleave-division multiple-access communication systems [61]. Other papers use a number of different optimization algorithms and compare results. For example in [62] spectrum allocation methods for cognitive radio based on GA, quantum genetic algorithm (QGA), and PSO, are proposed.

## 4. Results and discussions

In this section we present numerical results from different optimization problems in wireless communications using different algorithms.

### 4.1. Cell to switch assignment in cellular networks using barebones PSO

Cell assignment is an important issue in the area of resource management in cellular networks. The problem is an NP-hard one and requires efficient search techniques for its solution in real-time. We briefly present an example case of solving this problem using the barebones PSO [9]. The effective assignment of cells to switches in order to minimize the cost of network deployment is a challenging issue in cellular networking.

The cell-to-switch assignment (CSA) problem consists of optimally assigning cells to network switches while respecting certain constraints such as the call volume of each cell and the switches capacity [63]. The objective of the optimization is the reduction of implementation and operational costs. Usually, the cost function considers the cost of linking cells to switches (cabling cost) and the cost of handoff between different cells (handoff cost). The problem is an NP-hard one with exponential complexity and cannot be solved analytically in real size networks. Other evolutionary techniques like tabu search [64], ACO [65] and GAs [66] have been used in the literature for solving this problem. The problem formulation is given below.

We consider *n* unique and distinct cells in a given service area and *m* switches with known location and traffic parameters. The objective is the optimum assignment of cells to switches in order to minimize the total cost that comprises the handoff and cabling costs.

In single-homing CSA, each cell belongs to one cluster and it is assigned to one switch at a time. In this case, the objective function to be minimized is [63]:

where *c*_{ik} is the cabling cost per time unit between cell *i* and switch *k*, *x*_{ik} is a parameter that takes the value one when cell *i* is assigned to switch *k* (otherwise, *x*_{ik}=0) and *h*_{ij} is the cost per time unit for the handoffs that occur between cells *i* and *j*. The first term in (16) gives the total cabling cost and the second one is the total handoff cost per time unit among cells. Therefore, *y*_{ij} is defined as

where *y*_{ij} is one when cells *i* and *j* are connected to the same switch, otherwise it is zero. The product *x*_{ik}*x*_{jk} in (17) defines the variable

that is zero unless cells *i* and *j* are connected to switch *k*. In this case, it is one.

Cell assignment is subject to further constraints. The call handling capacity of each switch should not be violated at any time, i.e.

where *i* handles per unit time and *M*_{k} is the call handling capacity of switch *k*. Also, each cell is assigned only to one switch, i.e.

The optimization problem defined by (16) and subject to (17)-(20), can be converted [63] to an integer programming one by replacing (18) with the

We compare BB and BBExp PSO with ACO [65] and binary PSO (BPSO) [67]. We run 100 independent trials for each algorithm. The statistical results are presented and compared In the proposed barebones PSO variants, the only parameter we set was the swarm size. In the examples presented here, this was set to 5 particles. The ACO parameters were the same as in [65]. For the BPSO, we set the learning factors *c*_{1} and *c*_{2} equal to two. Systems with varied number of cells and switches that range from 15 to 200 and from 2 to 7, respectively, were considered.

The percentage of successfully obtained solutions as a function of the number of cells and switches indicates the solution accuracy of the algorithms. Figure 1 shows the results of the application of BB PSO, BBExp PSO, BPSO and ACO in a single-homing system for swarm size equal to 5 particles. In the first case, BB PSO outperforms the other methods in systems with small complexity but as the complexity increases (*n*/*m*=150/6 and 200/7) BBExp gives the best results. As it was expected, solution accuracy decreases with system complexity. In general, BB PSO outperforms the other methods for small *n* and *m*. However, its performance degrades with system complexity; in this case, BBExp gives better results. In any case, at least one of BB and BBExp PSO is better than BPSO and ACO. We have also evaluated the different algorithms in terms of the computational time required for the derivation of the previous results. Figure 2 shows small differences in results between the four algorithms. In all cases, barebones PSO algorithms are slightly faster. BBExp outperforms BB as system complexity increases. The computational cost of the methods grows exponentially with *n*/*m* and increases with the swarm size. More details about this problem can be found in [9].

### 4.2. A PTS technique based on ACO and ABC for PAPR reduction of OFDM signals

A major drawback of OFDM signals is the high value of peak to average power ratio (PAPR). Partial transmit sequences (PTS) [68], is a popular PAPR reduction method with good PAPR reduction performance. However, PTS requires an exhaustive search in order to find the optimal phase factors. Thus, the search complexity is high. Several methods have been published in the literature for PAPR reduction using PTS with low search complexity [10, 69, 70]. The problem description is given below.

In an OFDM system, the high-rate data steam is split into N low-rate data streams that are simultaneously transmitted using N subcarriers. The discrete-time signal of such a system is given by

where *L* is the oversampling factor,

The PAPR of the signal in (22) is defined as the ratio of the maximum to average power and is expressed in dB as

where

In the PTS approach the *M* disjointed subblocks represented by the vector

Next, the subblocks are converted to time domain using *LN* point inverse fast fourier transform (IFFT). The representation of the OFDM block in time domain is expressed by

The PTS objective is to produce a weighted combination of the M subblocks using

In order to reduce the search complexity the phase factor possible values are limited to a finite set. The set of allowable phase factors is

where *W* is the number of allowed phase factors. Therefore in case of *M* subblocks and *W* phase factors the total number of possible combinations is

The optimization goal of the PTS scheme is to find the optimum phase combination for minimum PAPR. Thus, the objective function can be expressed as

Minimize

subject to

We have evaluated objective function above using evolutionary algorithms and methods found in the literature. We have used two main measurement criteria namely the complementary cumulative distribution function (CCDF) and the computational complexity. In all our simulations, 10E5 random OFDM blocks are generated. The transmitted signal is oversampled by a factor L=4. We consider 16-QAM modulation with N=256 sub-carriers which are divided into M=16 random subblocks. The phase factors for W=2 are selected. We consider the first phase factor to be fixed so the total number of unknown phase factors is M-1.

The control parameters in all simulations are given below. In the PSO algorithm

Figure 3 presents the comparison between the CCDF by different PTS reduction techniques. For

Method | Computational Complexity | PAPR (dB) |

Original | 0 | 10.84 |

Exhaustive | 5.86 | |

IPTS | (M-1)W=30 | 7.55 |

GD | 6.96 | |

PSO | 7.13 | |

ABC | 7.01 | |

ACO | 6.52 |

### 4.3. Dual-band microwave filter design using SADE

Microwave filters are among the important components of a modern wireless communication system. Several papers exist in the literature that address the filter design problem [73]. Open Loop Ring Resonator (OLRR) filters, which consist of two uniform microstrip lines and pairs of open loops between them, are widely used as the building block in several multiband bandpass filter design cases [74]. In [74], two pairs of folded OLRRs operating at two passbands are proposed to produce dual-band response.

A dual band OLRR filter is shown in Figure 4. The frequency response of such a filter depends on the filter dimensions and spacings between microstrip lines [74, 75]. The design parameters for this case are the ones shown in Figure 4,

Such a filter design problem can be defined by the minimization of

where

The filter is designed for operation in two WiMax (IEEE 802.16) frequency bands. These are the 3.5GHz and the 5.8GHz frequency bands. For this case, we set

## 5. Conclusion

A brief survey of different evolutionary algorithms and their application to different problems in wireless communications has been presented. It must be pointed out that several evolutionary algorithms exist in the literature. GAs and SI algorithms are among those most commonly used. In order to select, the best algorithm for every problem one has to consider the problem characteristics. Another key issue is the selection of the algorithm control parameters, which is also in most cases problem-dependent. One may also use at first the control parameters for these algorithms that commonly perform well regardless of the characteristics of the problem to be solved. The example of the CSA problem in cellular networks showed the better performance of BB and BBExp compared to BPSO and ACO in terms of successfully obtained solutions and execution time. In the PTS optimization problem ACO outperformed ABC and PSO.

The selection of the SADE technique for microwave filter design has lead to a successful filter design which exhibits low loss in the passbands and high isolation between the passbands. The DE algorithms are also robust optimizers. In classical DE algorithms, the selection of the appropriate strategy for trial vector generation and control parameters requires additional computational time using a trial-and-error search procedure. Therefore, it is not always an easy task to fine-tune the control parameters and strategy given also that commonly the appropriate control parameters and strategy selection are problem dependent. The SaDE advantage though, is the fact that no additional time for solving a given problem is required. SaDE requires only the adjustment of two parameters: the population size and the number of iterations.

The practical examples subject to several constraints presented in this chapter show the applicability and the efficiency of using such algorithms.