Genetic algorithms in wireless networking: techniques, applications, and issues

Abstract

In recent times, wireless access technology is becoming increasingly commonplace due to the ease of operation and installation of untethered wireless media. The design of wireless networking is challenging due to the highly dynamic environmental condition that makes parameter optimization a complex task. Due to the dynamic, and often unknown, operating conditions, modern wireless networking standards increasingly rely on machine learning and artificial intelligence algorithms. Genetic algorithms (GAs) provide a well-established framework for implementing artificial intelligence tasks such as classification, learning, and optimization. GAs are well known for their remarkable generality and versatility and have been applied in a wide variety of settings in wireless networks. In this paper, we provide a comprehensive survey of the applications of GAs in wireless networks. We provide both an exposition of common GA models and configuration and provide a broad-ranging survey of GA techniques in wireless networks. We also point out open research issues and define potential future work. While various surveys on GAs exist in the literature, our paper is the first paper, to the best of our knowledge, which focuses on their application in wireless networks.

1 Introduction

The study of nature is a rich source of inspiration for researchers working in the area of artificial intelligence and machine learning. In particular, the human brain and the biological process of evolution have helped develop and guide research in the neural network and the evolutionary algorithm communities. A genetic algorithm (GA) is a metaheuristic computational method (Hillier and Lieberman 2001), inspired from biological evolution (Ridley 2004), that aims to imitate the robust procedures used by various biological organisms to adapt as part of their natural evolution. GAs have been successfully used in fields as diverse as aircraft industry, chip design, computer animation, drug design, telecommunications, software creation, and financial markets (Mitchell 1998).

The field of GA was established by John Holland who investigated the evolution of complex adaptive systems (CAS) comprising interacting genes, starting in the early 1960s, and culminating in the publication in 1975 of his seminal book on this topic (Holland 1975). The idea of embedding computers with learning inspired from evolution goes back even further as Alan Turing proposed a “learning machine” which would parallel the principles of evolution in his landmark 1950 paper on machine intelligence (Turing 1950). Holland used the biological metaphor of chromosomes to refer to strings of binary symbols encoding a candidate solution to the given problem. Holland proposed using the computational analogues of the biological evolutionary processes of random mutation, crossover, and natural selection (Goldberg and Holland 1988) to enable populations of chromosomes to get increasingly better at problem solving. The underlying premise is that given enough time, the process would converge towards a population that contains a chromosome (or chromosomes) that solves the given problem. Apart from the mutation and crossover operators, The design of a GA framework also involves other design issues such as genetic representation (encoding), population initialization, fitness function formulation, and a selection mechanism. More recently, researchers have also proposed the use of altruistic techniques in an evolutionary framework that involve cooperation as a fundamental primitive (Highfield and Nowak 2011).

1.1 Motivations for using GA

1.1.1 Generality and versatility

Genetic algorithms apply in a wide variety of settings and can be easily molded to particular problems. GAs constitute a very general meta-heuristic technique which can be thought of as the sledgehammer of the craft of algorithms, much like the technique of artificial neural networks (ANNs). In particular, GAs can be readily invoked in areas that do not yield readily to standard approaches or when more specialized techniques fail. GAs are capable of solving extremely large problems that have large search spaces. GAs are very good at navigating through huge search spaces to heuristically find near-optimal solutions in quick time. In addition, GAs can work even when the objective function is not exactly known since GAs rely only on an objective function’s evaluation (without necessarily knowing the objective function explicitly). Although GAs do not guarantee optimality, GAs are generally useful in practice. Bhandari et al. 1996 showed that although GAs do not guarantee convergence to an optimal solution, GAs avoid local optimas with a high probability through the use of mutation and crossover operators.

1.1.2 Adaptiveness and online problem solving

An important feature of GAs is that they define online adaptive algorithms that can operate in unknown environments. Such an ability is crucial in various control settings in wireless networks in which decisions have to be made automatically in run-time to cater to dynamic channel parameters. In dynamic channel conditions that typically exist in most wireless networking configurations, optimization is an elusive moving target since the optimal solution keeps changing as the conditions change.

In online adaptive optimization algorithms, there is a fundamental tradeoff between exploration—which involves looking for potentially better previously unexplored solutions—and exploitation that implies the use of previously known good solutions. Exploration in effect is an attempt to find good adaptive building blocks and exploitation is the use and propagation of adaptations that are known to perform well. We can envision mutation and recombination of genes as analogous to exploration, whereas natural selection can be envisioned as a form of exploitation. In ever-changing dynamic environments, such as wireless networks, it is important to always keep on exploring. Holland’s original GA work used schema analysis to show that, under qualifying assumptions, GAs can achieve near-optimal exploration and exploitation tradeoff.

1.1.3 Ability to find good building blocks

By working in terms of a population of candidate solutions, genetic algorithms can exploit the diversity of solutions to find building blocks—known as schemas in literature—which are substrings of chromosomes that denote high-performing elements of the overall solution (Holland 1975). In the context of biological genetics, schemas correspond to constellations of genes working together to help an organism adapt; evolution proceeds by selecting these constellations (or building blocks) through natural selection. Using genetic operators such as recombination and crossover, GAs can evolve better solutions through mixing of the high-performing basic building blocks.

1.1.4 Parallel nature and scalability

Traditional theory of GAs presumes that GAs accomplish the culmination by discovering, emphasizing, and recombining the good traits of chromosomes in a vastly parallel manner. GAs incorporate multiple solutions together in a ‘population’ of solutions. GAs use evolutionary techniques to test and improve the solutions using techniques such as mutation, crossover, selection, and recombination. The parallel nature of GAs renders it as a suitable optimization framework for scalable problem solving in a wide range of applications.

1.1.5 Support for multiobjective optimization

Many practical problems in wireless networks require optimizing for multiple parameters (that may potentially conflict with each other). An important characteristic of GAs is that it can easily support joint optimization of multiple objectives. Support for multi-objective optimization—in which the considered objectives may potentially conflict with each other—is of significant practical interest in wireless networks. Issues related to multi-objective optimization are introduced in Konak et al. (2006).

1.1.6 Support for global optimization

Unlike network models such as the multi-layered perceptrons (which make local changes so as to find the local minima), GAs are suited to finding the global optima due to a number of properties: (i) they search by means of a population of individuals; (ii) they work with an encoding of the multiple parameters; (iii) they use a fitness function that does not require the calculation of derivatives; and, finally (iv) they search probabilistically.

1.1.7 Easy implementation

Genetic algorithms are computationally simpler compared to other complementary AI techniques such as neural networks since they require only swapping and shifting of genes in chromosomes (unlike neural networks that require adders for its multiple hidden layers). GAs are easily implemented and can be rapidly prototyped in digital signal processors (DSPs) or field programmable gate arrays (FPGAs). In addition, GAs are highly amenable to successful implementation on modern parallel and cloud computing architectures due to its inherently parallel nature.

1.2 Contributions of this paper

This paper offers a comprehensive survey of the applications of GAs in wireless networking. In addition, we also provide a self-contained introduction to the GAs. The aim of this paper was not to provide an exhaustive survey,¹ but to provide a representative sample of important works along with a comprehensive listing of the various applications of GAs. We also highlight the application of GAs in wireless networking configurations such as wireless mesh networks (WMNs), mobile ad-hoc networks (MANETs), cellular networks (CNs), wireless sensor networks (WSNs), and cognitive radio networks (CRNs). While a lot of material exists on GAs—including various textbooks (Goldberg and Holland 1988; Davis et al. 1991; Pedrycz and Vasilakos 2010), as well as generic survey papers (Srinivas and Patnaik 1994; Man et al. 1996)—a focused survey article on the applications of GAs in wireless networking is missing in literature. This paper will be useful to networking researchers interested in applying GAs in particular, and metaheuristic and evolutionary techniques more generally, in the context of wireless networks. According to the best of our knowledge, this is the first survey paper that provides an extensive survey of the applications of GAs in general wireless networks.

1.3 Organization of this paper

We provide the necessary background on GA theory, working and common techniques used to carry out the evolutionary process in Sect. 2. The applications of GAs in wireless networks—such as routing, channel allocation, load balancing, localization, and quality of service (QoS)—are listed in Sect. 3. We highlight the various lessons learnt through years of GA research, in terms of common pitfalls as well as guidelines for successful implementation, in Sect. 4.3. In Sect. 5, we highlight open issues and suggest directions for future work. Finally, this paper is concluded in Sect. 6.

Table 1 Acronyms used in this paper

To facilitate the reader, acronyms used in this paper are collected in Table 1 as a convenient reference.

2 Background: genetic algorithms

A detailed GA taxonomy is provided in Fig. 1. This taxonomy diagram exhibits the breadth of GA’s applications as described in this section.

2.1 GA terminology

Since the field of GA is inspired from the biological genetic evolution, the field uses a number of biological metaphors in its terminology. The purpose of this short subsection was to introduce these biological metaphors in the context of applications of GAs in wireless networking. We introduce the terminology through the following list:

• Organism: It represents the entity (e.g., a radio parameter, or a wireless resource) being optimized.

• Population: It refers to the ensemble or collection of organisms undergoing simulated genetic evolution.

• Chromosome: It encodes a particular solution to the problem under study. (Biologically, a chromosome contains an organism’s genetic makeup).

• Fitness: It represents the utility of the current chromosome. (In evolutionary theory, fit chromosomes are passed on through heredity while unfit chromosomes die out due to the natural phenomenon of the ‘survival of the fittest’).

• Gene: It is the basic building block of the chromosome defining a particular feature of the simulated organism. (Each chromosome can contain a number of genes).

• Allele: Each gene can take several alternative forms, each of which is called an allele.

• Locus: It is the position on the chromosome containing a particular gene of interest.

• Mutation: It represents a random change of an allele (or the value of a gene).

• Selection: The process through which the ‘fittest’ simulated organism survives while the unfit solutions are weeded out.

Fig. 1

Taxonomy of genetic algorithms

2.2 Number-of-objectives based classification

2.2.1 Single-objective GAs

Single objective GAs (SOGAs) are popular when it comes to optimize single objective with scalar fitness function. They are computationally less exhaustive but are required to run multiple times using different weight vectors to optimize multiple objectives as in case of multi-objective GAs (Ishibuchi et al. 2006).

2.2.2 Multi-objective GAs

In a multi-objective optimization, there are multiple objectives that need to be simultaneously optimized. For example, there can be multiple objectives in wireless networking—such as the signal to interference and noise ratio (SINR), the power consumption, and the bit error rate (BER)—that we could be interested in optimizing. In such a scenario, a single solution may not be suitable to multiple objectives. A solution may be best in one objective but worst in other cases. The overall system is optimized, in all directions, by multiple solutions. These categories of solutions are non-dominated solutions that lie on the Pareto front. Each point in Pareto front is optimal, since no single solution exists that may improve one objective vector without degrading at least one other objective. Almost all the solutions lying on the Pareto front would be compromises relative to multiple objectives.

Multi-objective GAs (MOGAs) can be employed in almost every optimization setting provided that chromosomes encoding and objective function are appropriately accounted for. Details and applications of MOGAs are discussed next in Sect. 3. In this section, we will describe one particular instance of a MOGA framework known as non-dominated sorting genetic algorithm (NSGA).

2.2.2.1 Non-dominated sorted genetic algorithm (NSGA)

Non-dominated sorted genetic algorithm is a class of multi-objective optimization algorithm that works at improving the adaptive fit of a population to the Pareto front constrained by a set of objective functions. NSGA can also be seen as a case of an evolutionary algorithm from the domain of evolutionary computation. The population within the algorithm is sorted into levels or sub-populations, which are based on the arrangement of the Pareto dominance. Major similarities between the population members of each sub division are calculated against the Pareto front, and the resulting class, along with its similarity measure, is then utilized to promote a solutions front that is non-dominated. Non-dominated sorting genetic algorithm-II (NSGA-II) is a widely used computationally fast and elitist MOGA approach (Deb et al. 2002).

2.3 Other types of GAs

2.3.1 Adaptive GA

To prevent GAs from suboptimally converging to a local optima, a number of adaptive techniques have been recommended for adjusting parameters such as crossover probability, mutation probability, and population size. These techniques constitute adaptive GAs. In contrast to simple GAs that rely on fixed control parameters, adaptive GAs utilize information about the population in each generation to adaptively adjust the probability of crossover and mutation.

2.3.2 Parallel GA

Parallel GA (PGA) can be categorized into three subcategories: (i) master–slave GA; (ii) island GA (also referred to as distributed GA or coarse-grained GA); and (iii) cellular GA (also called fine-grained GA). Amongst these three configurations, the Island PGAs (island GA, or iGA, for short) are best suited to wireless networking since they allow control of the migration policy unlike the cellular PGAs—which require local communication at all agents during each generation of the PGA—and the master–slave PGAs that require the master and slaves to constantly communicate.

2.3.3 Distributed or island GA

Distributed GAs divide a large population into several smaller subpopulations that interact weakly. Parallel GAs, on the other hand, are primed to speed up execution by implementing the sequential GA on several computation engines. Amongst the distributed GA approaches, the island GA approach is important and is popularly used in wireless networks (Friend et al. 2008; ElNainay et al. 2009). It works by separating the population into sub-populations, called islands. These islands cooperate with other islands through the migration of individuals. In island GA, the GA runs on each node with the possibility of good solutions migrating between nodes. These migrations are performed in accordance with the migration policy that controls the ‘when’ and ‘how’ of the individual movement. In the island GAs, there is relatively infrequent migration between island models thereby implying reduced inter-agent communication requirements compared to master–slave GA and cellular GA Alba and Troya 1999.

Fig. 2

A flow chart of a typical genetic algorithm (Qadir 2015)

2.4 GA components and operators

A flow chart of a typical GA is provided in Fig. 2. The operation of a GA-based framework starts by initially defining a population of candidate solutions. While it is acceptable, and indeed commonplace, to define the population randomly, the convergence process can be accelerated by starting with an appropriately defined population. Each candidate solution defined in the population is known as an individual, with each individual encoded in an abstract format named as a chromosome (in a metaphorical reference to the encoding role of chromosomes in biological genetics). Various evolutionary techniques (mutation, crossover, etc.) are then applied on the population. In every generation, multiple individuals are stochastically selected from the current population with fitter individuals being more likely selections (due to the genetic principle of ‘survival of the fittest’). The selected individuals are then genetically modified (mutated or recombined) to form the next generation of the population. The usage of genetic operators and stochastic selection allow a gradual improvement in the ‘fitness’ of the solution and allow GAs to keep away from local optima.

In the following subsections, we will provide more details about the various steps involved in problem solving through GAs.

2.4.1 Encoding into chromosomes

Genetic algorithms operate by initially defining a population of candidate solutions (each of which is called an individual). Individuals are encoded in an abstract representation, known as a chromosome, (which may be problem specific although representation in strings of 1s and 0s is common; in the related field of ‘genetic programming’, the encoding is in terms of snippets of computer code). The population size can be a significant factor in GA performance and efficiency. In particular, the performance of GAs can be poor when the population size is very small (Grefenstette 1986).

The encoding of candidate solutions in the form of chromosomes can also be of variable length. Such variable length encoding is well suited to problems such as shortest-path routing problem that compares paths of different lengths. As an example of variable length chromosome encoding, refer to the work of Ahn and Ramakrishna (2002) in which the routing path is encoded in the chromosome as a sequence of positive integers representing node IDs of the nodes enroute the end-to-end routing path. Each locus of the chromosome corresponds to the order of the node in the end-to-end routing path with the source node always represented by the gene of first locus. The length of the chromosome is variable but is upper bounded by N (the total number of network nodes).

Several encoding schemes for GA exist:

• (a) Binary encoding: Binary encoding is the most common approach, mainly because initial GA-based works used this encoding. In binary encoding every chromosome is a string of bits, i.e. 0 or 1. Binary encoding provides many possible chromosomes even for a small amount of alleles. On the other hand, this encoding is in some cases not natural for many problems and in other cases corrections need to be made after mutation or crossover.

• (b) Octal encoding: The chromosome is represented in octal numbers (0–7).

• (c) Hexadecimal encoding: The chromosomes are represented using hexadecimal numbers. (0–9, A–F).

• (d) Permutation encoding: Permutation encoding can be used in GA for ordering problems, such as task ordering problems, or the ‘traveling salesman’ problem. In permutation encoding, each chromosome is a represented as a string of numbers, which is actually a number in a sequence. In some problems, for some types of mutation and crossover, corrections must be inculcated to leave the chromosome in a consistent form, viz. it should be corrected to ensure that it has a real sequence in it.

• (e) Value encoding: Direct value encoding is useful in problems that deal with complicated values (such as a real number). Use of binary encoding method in this case would be very difficult. In value encoding, every chromosome is a string of some values. Values can be in any arbitrary form including numbers, characters, or any other complicated object. While value encoding is a good approach for some problems, it often requires new crossover and mutation operators defined specifically for the problem.

• (f) Tree encoding: Tree encoding is used for expressions or evolving programs, specifically for genetic programming (GP). In tree encoding, every chromosome or gene is in a tree form of some objects, like commands in programming language or a function. Programming language like LISP is mostly used for this, because genetic programs in it are encoded in this form and can be easily parsed as a tree structure, thereby facilitating mutation and crossover to be performed relatively easily.

For illustrative purposes, an example binary encoding, permutation encoding, value encoding, and tree encoding is presented in Fig. 3.

Fig. 3

Illustration of basic types of encoding schemes used by GA (Adapted from Sivanandam and Deepa (2008))

Encoding example: Consider an example encoding of radio parameters in chromosomes and genes for GAs. The inherent difficulty in such a representation is the large relative difference between radio parameters. For example, frequency range of 1 MHz–6 GHz with step size of 1 Hz would require more than 30 bit genes, while modulation has only handful of techniques so it would require far less bits. Chromosomes can, therefore, utilize large number of bits for frequency while utilizing small number of bits for the modulation gene. To make GAs independent of which radio it is optimizing, the variable bit chromosome representation is suggested by Scaperoth et al. (2006) in the context of software-defined radios (SDR).

2.4.2 Fitness function

The fitness function, sometimes called the objective function, offers a mechanism for the evaluation of the individual chromosomes. Fitness function can be single objective, or multi-objective. The fitness function is devised in a way that the individual chromosome is its variable input parameter. Fitness function ensures that the chromosomes passed on to the next generation are not violating any constraints. It assigns a fitness score to each individual depending on the quality of the individual in terms of the optimization goals and objectives. In particular, for the fields of both GAs and genetic programming, each design solution is represented as a string of numbers referred to as the chromosome. In fitness evaluation, after each round of completed simulation or testing, N worst design solutions are deleted, and N new ones from the best design solutions are created. Each design solution thus needs to be awarded a figure of merit, which indicates how close it came to meet the overall specification. This is achieved by applying the fitness function to the simulation or test results obtained from that solution.

Genetic algorithms require much effort in designing a workable fitness function. Though a computer might generate the final form of the algorithm, it takes a human expert to define the fitness function since an inefficient function can result in convergence to an inappropriate solution, or no convergence at all. Speed of execution of the fitness function is very important, since a typical GA needs to be iterated many times to produce a usable result for a non-trivial problem. Hence, fitness function requirements include the following:

• Minimum fitness computation time of candidate solution.

• Precise model definition for fitness computation.

• Removal of noise from the fitness function values.

Two main categories of fitness functions exist: one where the fitness function does not change over time (as in the case of optimizing a fixed function, or testing with a fixed set of test cases) and the other where the fitness function is mutable (as in the case of co-evolving the set of test cases or in niche differentiation). Another way of defining fitness functions is in terms of a fitness landscape that depicts the fitness level for each possible chromosome. Definition of the fitness function may not be straightforward in many cases. In some scenarios, it becomes very hard or impossible to come up even with a guess of what fitness function definition might be. This difficulty is solved by ‘interactive GA’, which outsources evaluation to external agents including humans. The function is calculated iteratively if the fittest solutions produced by GA are not in the desired range.

There are various strategies for assignment of fitness values to the subject population. The ‘aggregation-based’ strategy sums the objectives into a single parameterized objective value, e.g., an aggregation of weighted-sum. The ‘criterion-based’ method transitions between the objectives during the selection phase of the algorithm. Every time an individual is chosen for reproduction, a potentially different objective will dictate which member of the population will be copied into the mating pool. In the ‘Pareto dominance based’ methods, different approaches like dominance depth, dominance count, and dominance rank are used. The dominance rank dictates the number of individuals by which certain individual is dominated. In the dominance depth, the population is divided into several fronts and the dominance depth reflects the front to which an individual belongs. The dominance count is the number of individuals that are dominated by a certain individual.

Fitness function example: The evaluation of the solution is at the heart of GAs since it is on the basis of fitness values that GAs evolve solutions and remove poor individuals. It can be thought of as the performance metric for the optimization algorithm. As an example, for the routing problem, the fitness can be equated with high average throughput ($f_i = t_i$: where $f_i$ is the fitness of i${\mathrm{th}}$ individual and $t_i$ is its average throughput), low delay ($f_i = -d_i$) where $d_i$ is delay perceived by the ith individual. For classification problems, the fitness function can be some measure of the error. Realistic fitness functions are typically much more complex than this toy example, and can depend on many factors.

2.4.3 Mutation

The mutation operator is used for exploration with randomly altering genes in chromosomes to discover new horizons and new traits. Mutation helps to diversify the population, thus helping GAs to avoid local optima and pave the way towards global optima. Several types of mutation techniques exist including:

• Bit-string mutation: The mutation of bit strings occurs, through bit flips at random positions of chromosomes (as illustrated in Fig. 4).

• Flip bit: This mutation operator takes the chosen genome chromosome and inverts the bits, i.e. if the genome bit is 0, it is changed to 1 and vice versa.

• Boundary: This mutation operator replaces the chromosome with either upper or lower bound in a random manner. This can be used for float and integer representation of chromosomes.

• Non-uniform: The probability that the extent of mutation will go down to 0 with the next generation of chromosome is increased by using non-uniform mutation. This keeps the population from stagnating at early stages of the evolution process. It also alters solution in later stages of evolution. The mutation operator can only be used for float and integer chromosome genes.

• Uniform: This operator replaces the score of the chosen chromosome with a uniform random value selected in the range of the user-specified upper and lower bounds. This mutation operator can only be used for integer and float genes.

• Gaussian: This operator adds a unit Gaussian distributed random value to the selected chromosome. If it falls outside of the boundary of user-specified upper or lower bounds for that chromosome, the new value is clipped. This mutation operator is used for integer and float strings.

Fig. 4

Illustration of mutation and crossover operation

2.4.4 Crossover

The crossover process is essentially an attempt to exploit the best traits of the current chromosomes and to mix them in a bid to improve their fitness. This operator randomly chooses a locus and exchanges the sub-sequences before and after that locus between two parent chromosomes to create a pair of offspring. A crossover point is randomly chosen. There can be multiple crossover points to aid more exploration. In biological systems, crossover is much more rampantly observed than mutation, often as much as a million times more frequent (Holland 1995). Crossover along with mutation provides the necessary ‘evolutionary mix of small steps and occasional wild gambles’ to facilitate robust search in complex solution spaces (Harford 2011).

In GAs, crossover is viewed as synthesis of best practices and mutation is viewed as a method of spontaneous inspiration and creativity. The evolution can start from a population of completely random individuals and can evolve to better solutions through survival of the fittest after application of genetic operators. The selected individuals (or chromosomes) are genetically modified (mutated or recombined) to form the next generation of the population. The usage of genetic operators and stochastic selection allow a gradual improvement in the fitness of the solution and allow GAs to keep away from local optima.

Several methods exist for crossover of chromosomes which use different data structures (Goldberg and Holland 1988):

• One-Point crossover: A single crossover point on both parent’s chromosome strings is selected. All data beyond that point, in either organism chromosome are swapped between the two parent strings. The resulting strings are the new children chromosome.

• Two-Point crossover: Two-point crossover requires two points to be selected on the parent chromosome strings. Everything between the two points is swapped between the parent chromosome strings, producing two child chromosomes.

• Uniform crossover and half uniform crossover: The uniform crossover approach uses a fixed mixing ratio between two parents strings. Unlike one-point and two-point crossover, this approach enables the parent chromosomes to contribute at the whole chromosome gene level rather than at the segment level. For example, if the mixing ratio is 0.5, the offspring chromosome has approximately half of the genes from first parent and the other half from other parent, although crossover points can also be randomly chosen instead. In the half uniform crossover method, exactly half of the non-matching bits are swapped between the chromosomes. First the number of differing bits, or the Hamming distance, is calculated. This number is then divided by two; the resulting number depicts the number of bits that do not match between the two parents, and will thus be swapped. An illustrative example comparing one point, two points, and uniform crossover is presented in Fig. 5.

• Cut and splice: In the crossover variant called the ‘cut and splice’ approach, a change in length of the children strings occurs. The reason for this difference in length is that each parent string has a separate choice of deciding crossover point.

• Three parent crossover: In this method, the child chromosome is derived from three parents which can be randomly chosen. Each bit of first parent is compared with bit of second parent to see if they are the same. If the bits are same then that corresponding bit is taken for the offspring; otherwise, the bit from the third parent is taken for the offspring chromosome.

• Ordered chromosome crossover: In some cases, a direct swap may not be possible. One such case is when the chromosomes are in an ordered list. The N-point crossover can be used for ordered chromosomes, but always requires a corresponding repair process. Some of the approaches for ordered pair crossover include cycle crossover, position-based crossover, alternating position crossover, edge recombination crossover, sequential constructive crossover, and voting recombination crossover.

Fig. 5

Illustration of examples of one point, two points, and uniform crossover methods (Adapted from Sastry et al. (2005))

2.4.5 Selection

Selection in GA allows individual genomes to be chosen from a population for later recombination or crossover (breeding). This operator performs the selection of chromosomes from population for reproduction. The fitter the chromosomes, the more likely they are to be passed on to the next generation. A number of selection techniques has been employed in GAs to carry out the survival of the fittest from a pool of individuals (Fette 2009).

A common selection procedure may be implemented in the following way:

• The fitness function is evaluated for each individual and is then normalized for algorithm use. The fitness value of each individual chromosome is typically normalized by the aggregation of all fitness values to ensure that all the resulting fitness values sums up to 1.

• The population is then sorted in descending order of fitness values.

• Accumulated normalized fitness scores are calculated. Accumulated fitness value of an individual equals the sum of fitness scores of all the previous individuals and its own fitness score. Accumulated fitness of the previous individual must always be 1—any other value can be used as indication of a wrong normalization procedure.

• A random number R is chosen in the range 0 to 1. The first individual whose summed up normalized value is greater than the number R is selected.

This selection method is called fitness proportionate selection or roulette-wheel selection, since the procedure is repeated until there are enough selected individuals. If instead of using a single pointer that is spun a number of times, multiple equally spaced pointers are used on a wheel that is spun once, the selection process will be called ‘stochastic universal sampling’. The selection process will be a tournament selection process once there is repeated selection of the best-fitted individual from a randomly chosen subset pool. This will be further called truncation selection once we take the best half, third or some other proportion of the individuals.

There are also other selection mechanisms that do not take into account all individuals for the selection process, but only those that have a fitness value, greater than a given constant. Other algorithms select the individual from a restricted pool where only a constrained percentage of the individuals is allowed, based on their fitness scores. Retaining the best individual chromosomes in a generation unaltered, in the next set of generation, is called elitist selection or elitism. It is considered a successful variant of the general procedure of constructing a new population pool.

The main selection techniques used by GAs are summarized in the following list:

• Relative tournament evaluation: In relative tournament, two parents are compared randomly and the one with high fitness value is selected to be the parent of next generation. Winning chromosomes are awarded by adjusting their weight corresponding to the objective function. This weighting increases the importance of that chromosomes relative to others.

• Roulette wheel selection: Roulette wheel selection is a way of choosing mother and father chromosomes from the population in a way that is proportional to their fitness. The chromosomes with higher fitness have high chances of being selected using this technique.

• Relative pooling tournament evaluation: In this technique, each parent is thrown in a competition with the individual chromosomes in population, independently. The individual that is the winner of maximum number of tournaments gets a chance to be passed into next generation through reproduction.

• Elitism: Elitism is a method to store and use previously found best-suited solutions in subsequent population generations of GA. In a GA approach that uses elitism, the statistic related to the population’s best solutions does not degrade with generation. Maintenance of archives for non-dominated solutions is an important and critical issue. The final contents of archive usually represent the result returned by applying the optimization process. It is highly effective and common to employ the archive as a pool, from which guidance is taken for the generation of new solutions.

3 Applications of GAs in wireless networking

After providing background on GAs in the last section, we are now in a position to survey the applications of GAs in wireless networking. GAs have been applied in wireless networking in a wide variety of contexts. We will first describe the various applications of GAs in wireless networking in Sect. 3.1. We will then provide a network-type based classification of GA application in Sect. 3.2. Finally, we will discuss ‘hybridization’ proposals that combine GAs with other techniques in Sect. 3.3.

Table 2 Applications of genetic algorithms in wireless networking (covered in Sect. 3.1)

3.1 Application-based classification

In this section, we will discuss the applications of GAs in wireless networking. In particular, we will discuss routing, QoS, load balancing, channel allocation and assignment, localization, WLAN AP placement, and other general applications, in this particular order. The organization of this section is summarized in the Table 2.

Table 3 Using genetic algorithms for routing in wireless networks

3.1.1 Routing

The problem of shortest path routing problem is a well-studied problem in literature. GAs are well suited to the routing problem allowing convenient mechanisms for developing adaptive routing solutions. GAs have been used for developing routing solutions in a variety of wireless settings as summarized in Table 3. Ahn and Ramakrishna (2002) have tackled this problem through GAs. The routing table for each source–destination pair needs to be constructed first. Obviously, the number of possible routes between two nodes heavily depends on the network topology. If the network is densely connected or the size of the network is large, the number of possible routes of a source–destination pair becomes huge. Hence, it is impossible to list all the possible paths in the routing table. A predefined number of routes are randomly generated and fed to population pool, and chromosomes are then optimized. In the simulation, crossover and mutation are run on variable length chromosomes. Infeasible solutions are also kept in check. The paper discussed the issues of path-oriented encoding, and path-based crossover and mutation, which are relevant to the routing problem.

Yang et al. (2010) studied how GAs can be used for dynamic shortest path routing problem (DSPRP). Algorithms like Bellman-Ford and Dijkstra perform well in fixed infrastructure but on dynamic scale, high computational complexity renders them unacceptable. A DSPRP model is built up in this paper using GAs. A specialized GA is designed for the shortest path problem in MANETs. Several immigrants and memory schemes that have been developed for GAs for general dynamic optimization problems are adapted and integrated into the specialized GA to solve the DSPRP in MANETs. The experimental results indicate that both immigrants and memory schemes enhance the performance of GAs for the DSPRP in MANETs.

In MANETs, all the nodes communicate over wireless links without any established infrastructure. MANETs are well suited to environments in which there is no fixed infrastructure or when the infrastructure is not trusted. In such networks, a common strategy is to form clusters where each node is linked to a clusterhead for efficient routing with other nodes that are not in its direct range. GAs have been used in such cluster-based routing schemes for MANETs. Al-Ghazal et al. (2004) have proposed a GA-based protocol named ‘cluster gateway switch routing protocol’ (CGSRP) to select the clusterhead to carry out communication between nodes. Clusterhead must have enough resources, power, and bandwidth to avoid dangers of bottlenecks. This scheme works by encoding each node’s unique ID in the chromosomes. The chromosomes have information about cluster-head, members, and number of links in each cluster-head. The encoded chromosomes are then evaluated against certain criteria as defined by the fitness function (which may incorporate features such as load balancing and bandwidth conservation). Each chromosome’s fitness is then evaluated. The process of the survival of the fittest leads to an optimum selection of nodes as cluster-heads that optimally utilize resources.

Genetic algorithms have also been proposed for use in multicast and broadcast routing in wireless networks. A study on multicast routes optimization using GAs is done by Banerjee and Das (2001). An on demand routing scheme with GAs is discussed to meet bandwidth, delay constraints while maintaining the QoS in wireless networks. Chromosomes from different pools are randomly concatenated to obtain a multicast solution. In doing so, all possible routes between source and destination nodes are encoded and fed to GA in the form of population chromosomes. GA then uses evolutionary techniques to select the best chromosomes by evaluating them against a particular fitness function, which can be in the form of different constraints related to bandwidth, QoS, and channel allocation, etc. In another work, Salcedo-Sanz et al. (2003) proposed mixed neural-genetic algorithm for the ‘broadcast scheduling problem’ (BSP). The algorithm solves this optimization problem in two stages: first, it finds a feasible solution, and second it obtains maximal transmission throughput by employing fittest chromosomes through GAs. A track of interference and frame matrix are kept and the channel slots are assigned accordingly. Nodes that are 1-hop away are not assigned the same slot to avoid mutual interference. After finding feasible solutions, these solutions are encoded in chromosomes. Multiple GA operators—such as mutation, crossovers—are then applied leading to maximized throughput.

The use of hybrid GAs have been proposed for routing in wireless networks. NK and Viswanatha (2009) proposed using ant algorithms, combined with GAs, for route discovery. It was observed that the use of ant algorithm leads to reduction in the size of the routing table. We note here that ant-colony-optimization (ACO) algorithms belong to the broader class of AI known as swarm intelligence. While GAs cannot use global information of the network, the use of ACO and GA techniques in tandem leads to independent exploration of the network helping in effective computation of routes between any pair of nodes. The proposed algorithm creates an initial population, determines the forward-ants, generates new populations using genetic operators and fitness evaluation, and finally updates routing table. The hybrid algorithm performs well in not only generating routes between pair of nodes but also for achieving efficient load balancing.

Table 4 Using genetic algorithms for QoS optimization in wireless networks

3.1.2 Quality of service (QoS)

With increasing prevalence of multimedia applications (such as video conferencing and streaming), and the development of high-speed wireless communication technologies, efficient and reliable QoS provisioning has become increasingly important. Modern multimedia applications place rigorous QoS demands for different parameters like bandwidth, delay, and jitter (Malik et al. 2014). This motivates the development of effective resource allocation schemes that can ensure QoS while also satisfying these strict QoS constraints. In this section, we will describe the various GA-based QoS solutions that have been proposed in literature. This information is presented in summarized form in Table 4.

Various analytic approaches have been proposed in literature including those that rely on Semi-Markov decision process (SMDP) theory for optimal call admission control (CAC) (Choi et al. 2000). These methods unfortunately fail to scale to large-scale networks where the decision and action space is large. GAs can provide near optimal solutions in large-scale complex networks. Xiao et al. (2000) presented an effective near-optimal GA-based CAC approach for large-scale wireless/mobile networks. The chromosomes encoded are binary strings where 1 and 0 represent the acceptance and rejection of calls by CAC. These chromosomes are randomly generated and then evaluated against fitness function of channel utility and constraints. Evolution of best traits leads to near-optimal solutions for QoS. This scheme offers adaptive QoS to multi-class users while being computationally less intensive compared to the SMDP approach.

A multi-objective GA (MOGA) approach on multicast QoS routing is proposed by Roy et al. (2002). To deliver on-demand QoS, different solutions are kept in an optimized pool. Multiple solutions are offered depending upon the service demands. A MOGA approach optimizes the prioritized objectives as stated in the user QoS requirements. A similar approach for QoS-aware web-based service under strict constraints and optimizing the targeted QoS parameters is done by Canfora et al. (2005). It is shown in this study that the widely adopted optimization approach of linear integer programming is unable to offer non-linear QoS functions. GAs can be employed to work with non-linear QoS attributes. In yet another MOGA work, Roy et al. have proposed QM$^2$RP as a QoS-based multicast routing protocol framework for mobile wireless cellular networks (Roy and Das 2004). The proposed protocol determines near-optimal routes on demand while working with potentially inaccurate network state information. The protocol considers a number of QoS optimization metrics including end-to-end delay, bandwidth, and residual capacity.

With the increase in number of service candidates, the traditional chromosome model for QoS optimization becomes cumbersome in web services. To address this, Gao et al. (2007) studied a ‘tree based GA’ for optimizing QoS. This model is faster than traditional GA since it offers impulsive chromosome coding and decoding and present run time integration of QoS resources. Chromosomes are represented in series of nodes and all the leaf nodes execute the process. A tree characterizes the structured model for different QoS composition and requires less computation for large networks. Sub-tree crossover exchanges the task nodes and updates the QoS vector from the leaf nodes to the tree’s root. A standardized and comprehensive fitness function verifies the whole QoS process plan. Results have showed that the tree-based models have lesser overhead than the traditional GAs with serial chromosomes while offering excellent replanning and service composition.

Table 5 Using genetic algorithms for load balancing in wireless networks

3.1.3 Load balancing

GAs have been proposed for use in various load balancing solutions for various wireless networking configurations in literature (as shown in Table 5).

There are three main types of load balancing categories: (i) strongest ‘received signal strength indicator’ (RSSI); (ii) least loaded first (LLF); (iii) hybrid load balancing (HLB) incorporating RSSI and LLB. These techniques fall under the category of network-centric load balancing, and are applied on a network scale to achieve global optima, unlike user-centered techniques that are more likely to achieve local optima only. Chromosomes consist of randomly assigned individuals to an access point. Crossover and mutation are performed on individuals and fitness evaluation is done. Both load balancing and congestion control problems have been addressed. QoS has also been addressed by assigning different weight to users, depending on its service requirement like streaming and media, etc. Experimental results and analysis showed that microGA outperforms macroGA at first but in the long run macroGA does better load balancing by pushing more congested users towards peripheral APs.

Ozugur et al. (2001) proposed the multi-objective hierarchical mobility management optimization for UMTS networks to distribute the load among different parts of network such as serving GPRS nodes (SGSN), radio network controllers (RNC), and mobile switching centers (MSC) in addition to performing the role of minimizing cost for location update in these intricate networks.

Selecting resource-rich nodes for trivial tasks creates an imbalance in energy distribution among nodes resulting in the demise of multicast service. To mitigate such a possibility, Yen et al. (2008) have proposed an energy-efficient GA routing in MANETs. The algorithms proposed in Yen et al. (2008) continuously observe the condition at various nodes and improve the energy balance by replacing the weaker nodes with energy-rich nodes. An extended Prüfer encoding scheme is proposed for energy-efficient exchange of leaf nodes through mutation and crossover. In this way a substantial reduction in convergence time is achieved, thus prolonging the service duration efficiently.

Genetic algorithms have also been proposed for load balancing at APs in IEEE 802.11 WLANs for efficient distribution of bandwidth among users. Scully and Brown (2009) have discussed MicroGAs and MacroGAs to address the problem of load balancing. A comparison of MicroGAs and MacroGAs has been done by Krishnakumar (1990). MicroGAs has a population of five individuals leading to brisk evolution.

Table 6 Using genetic algorithms for bandwidth allocation in wireless networks

3.1.4 Bandwidth allocation

The problem of bandwidth allocation under QoS constraints in wireless networks is typically a complex task. A proper bandwidth allocation scheme must be adopted to overcome the problem of limited wireless resources and utilize the channel allocation efficiently. Various GA-based approached have been proposed in literature as solutions to the problem of bandwidth allocation in wireless networks. We will describe a sample of these works (a tabulated summary is presented in Table 6.

An accelerated GA approach with dynamic adjusting of mutation and inheritance probability is proposed in Lin and Labeau (2012) as a solution to the bandwidth allocation problem in WLANs. The probability of mutation and crossover is made dependent on the individual chromosomes fitness. This approach is shown to quickly converge to global optima while substantially reducing the number of generations as well as the computation time. In another work, Sherif et al. (2000) proposed a GA-based approach to analyze the network bandwidth allocation using a predetermined range of QoS levels (high, medium, low) declared by each multimedia substream. The proposed algorithm assigns the best available QoS level to each substream depending upon the availability of bandwidth resources in network. In the case of network congestion, the algorithm tries to preserve resources by degrading the quality of some admitted calls. Using this technique, the algorithm attempts maximum resource utilization and fair distribution of bandwidth in all the networks while keeping in view the network constraints.

3.1.5 Channel allocation and assignment

With the rapid proliferation of wireless and cellular networks, and the problem of limited frequency spectrum, the problem of channel assignment and reuse has become very important. The recent advancement in wireless technology has enabled many high-speed data services leading to an upsurge in number of wireless users. Since the frequency spectrum is a limited resource, there is a great emphasis on the reuse and sharing of frequency amongst the ever-increasing user base. The goal of channel allocation is to maximize frequency reuse by minimizing the number of channels required to cover all the network cells.

There has been a lot of GA-based work done in the area of channel allocation and assignment in wireless networks (a summary of which is provided in Table 7). We discuss some important GA-based channel allocation/ assignment works below.

Broadly speaking, there are three main constraints that channel assignment algorithms in wireless networks must consider: (i) co-channel interference constraints—which requires that the same frequency or channel cannot be assigned to two different radios simultaneously; (ii) adjacent channel interference constraints—which requires that adjacent frequencies not be assigned to adjacent channels simultaneously; and, (iii) co-site interference constraints—that requires minimum spacing between a pair of frequencies assigned to a channel must have minimum spacing.

Kassotakis et al. have proposed an approach based on hybrid genetic approach—that combines GAs with local improvement operator—for channel reuse in multiple access telecommunication networks Kassotakis et al. (2000). The proposed scheme aims to establish the maximal number of connections while minimizing the number of isochronous channels. Wong and Wassell (2002) investigated the channel allocation for a ‘broadband fixed wireless access’ (BFWA) networks. A channel allocation matrix keeps track of channel parameters for conflict-free assignments. It is observed that as the network grows, centralized scheme would offer unacceptable signaling overhead. GA is used for distributed channel where each access point (AP) transmits the interference power of the entire available channel to a control unit. Control unit employs GAs and ranks the chromosomes of channel priorities according to fitness value of interference. Crossover and mutation rate are also set to promote the best channels and explore the new channels. Experimental Statistics have revealed that better SNR gain (more than 14.5 dB) and throughput is achieved with GAs in comparison with the other two dynamic channel assignment methods: (i) least interference (Cheng and Chang 1999), and (ii) channel segregation (Akaiwa and Andoh 1993).

Table 7 Using genetic algorithms for channel allocation/assignment in wireless networks

A study on GAs in channel assignment in cellular networks is performed by Kim et al. (1996). This paper reports that neural networks are more likely to get trapped on a local optima since a neural network’s output critically depends on the initial values. In the case of GAs, they possess crossover and mutation as their key strength to escape local optimas. GAs, therefore, have far better chances to overcome the channel allocation problems such as (i) co-channel interference (ii) adjacent channel interference, and (iii) co-site interference. GAs are applied on clusters in cellular networks and it is showed that if the number of cells in one cluster are increased, the convergence rate is decreased leading to an increase in the number of generations due to the reuse of the same frequency among different cells. GA comes handy in keeping the cluster size optimum for efficient frequency distribution among cells.

Ngo and Li (1998) presented a modified GA to contribute in conflict free channel allocation and spectrum efficient assignment in cellular radio networks. There are generally two kinds of channel assignments: (i) fixed channel assignment (FCA)—where channel slots are pre-allocated to cells, and (ii) dynamic channel assignment (DCA)—where channels are assigned upon request. FCA generally outperforms DCA under heavy traffic load. This algorithm, called the genetic-fix algorithm, generates and manipulates individuals with fixed size, and hence greatly reduces the search space. Furthermore, using the minimum-separation encoding scheme, the required number of bits for representing solutions is substantially reduced.

3.1.6 Localization

The task of determining the location of a wireless node is known as localization. Localization is important in many different settings (such as military monitoring services and disaster management) for providing location-aware services. GAs have been used to assist the localization process in various wireless settings. In this section, we will provide an overview of such work. A tabulated summary of some sample works is presented in Table 8.

Table 8 Using genetic algorithms for localization in wireless networks

A simple way to localize the nodes is to deploy GPS, but installing GPS in thousands of closely placed nodes is impractical. A better approach is to employ GPS in a few nodes, called anchor nodes, and apply techniques to locate all the other nodes relatively, with reference to multiple anchor nodes. Tam et al. (2006) proposed localization technique in which each node finds its position relative to three anchor nodes, thus enabling each node to locate itself through triangulation. This information is then broadcasted to base station where a centralized GA works as a post-optimizer, thus, leading to precise network graph with each node’s location known. Zhang et al. presented the centralized GA with simulated annealing Zhang et al. (2008) to minimize the error in position estimation of nodes in WSNs. This approach is also based on anchor nodes localization scheme. Simulated annealing is local search technique and it avoids pre-mature convergence, by mixing inferior and sub-optimal solutions with the optimal ones. In the approach of centroid localization (Yun et al. 2008), proposed in Yun et al. (2008), GAs and fuzzy logics are used by each node to perform self-localization by estimating the edge weights based on the received signal strength (RSS).

3.1.7 WLAN AP placement

Since the arrival of IEEE 802.11, WLAN services are widely adopted with the predominant WLAN setting being infrastructure mode (in which the topologies around APs). Optimizing the placement of WLAN APs plays a substantial role in maximizing the throughput and data rate of WLANs. In this section, we will summarize the various proposals for using GAs in WLAN AP placement. A tabulated summary is presented in Table 9.

A multi-objective GA (MOGA) approach for WLAN AP placement (with the objectives of minimizing the number of APs and maximizing SNR) has been described by researchers in Maksuriwong et al. (2003). GA-provided solutions have lesser variance implying that a larger number of area points within the network would have average SNR. Statistical analysis reveals that MOGA approach generate solutions with a high SNR data profile.

Optimizing the radio coverage inside buildings is as important as outdoors radio optimization. WLANs are mostly used inside homes and offices to provide mobile and Internet coverage to subscribers. Nagy and Farkas (2000) have studied the problem of optimizing the placement of indoor base stations (BS) while taking in account the effects of floors, ceiling, and walls on signal propagation and path losses. GA used the microwave propagation model to account for the effect of influence of brick, concrete, wood, furniture, and glass obstacles. Different weighting coefficients were assigned to each obstacle and parallel heuristic approach of GA is used to optimize the coverage results within indoor environment.

Another important application of GAs is in the optimization of AP placement in cellular and mobile networks. Since finding the set of coverage areas whose sum is the maximum covered area is an NP-hard problem, GAs come handy. Lieska et al. (1998) have explored in their study the combination of simulation and evolutionary techniques. Radio coverage areas are obtained by the series of BS with received power greater than $-$60 dbm. Algorithm works by selecting the chromosomes based on required BS. The chromosomes are than evaluated against constraints of power and SNR; afterwards, the healthy chromosomes are allowed to reproduce leading to global convergence of the entire network. This fitness function can be modified to include other constraints based on network requirement. A major advantage of a GA, therefore, is its ability to adapt to multiple situations and problems.

Table 9 Using genetic algorithms for wireless AP placement optimization

Table 10 Using genetic algorithms for general applications in wireless networks

3.1.8 General applications

A survey for solving computationally difficult problem, through GAs, in wireless networks is presented by Das et al. (2006) in his book “Handbook of Bio-Inspired Algorithm and Applications”. It has been shown that GAs have the potential to solve any optimization problem provided that proper modeling and chromosomes encoding has been performed. In this section, we will cover some of the other miscellaneous applications of GAs in wireless networking (that we have not covered in previous sections). A tabulated summary of these applications are presented in Table 10. We describe some of these applications here; some other applications are discussed when we cover network-configuration based categorization of GA applications in Sect. 3.2).

GAs have been proposed for energy efficient planning and management of cellular networks by enabling sleep modes in base stations (Chiaraviglio et al. 2012). Johnson and Rahmat-Samii (1995) have proposed a GA-based approach to find the best node distribution with optimized antenna pattern and SNR. The authors have employed simple binary coding scheme for a pool of randomly generated chromosomes for different nodes’ distribution and evaluated their fitness against the fitness function (in which N is the total number of nodes):

$$\begin{aligned} \mathrm{Fitness}=\mathrm{max}-\frac{1}{N} \sum _{i} \mathrm{Path}\_\mathrm{length}_{i} \end{aligned}$$

(1)

The winner chromosomes (having minimum cost of path length) are more likely to be inherited in the next generation. This approach is also applied for random encoding of antenna pattern and transmission power.

Churn prediction and forecasting have application in almost all the real-world phenomenon including medical, finance, products sale, telecommunications and network. Forecasting the future sale and growth in turbulent markets like telecommunications is always a big issue for product managers. Even approximate insights can yield large profit return in the long run. Venkatesan and Kumar studied GAs for forecasting (Venkatesan and Kumar 2002) the magnitude of future sales, time period to peak sales, and the value of sales during peak time. Considering the significant advantages of accurate forecast of product lifecycle, GAs are used to estimate the diffusion model based on previous data points. GAs are fed with several critical factors like price, competitive intensity, and network effects in obtaining better predictions during growth phase. Since GAs are inherently parallel, different scenarios can be taken care of while making predictions. Studies show that predictions by GAs are robust and accurate in predicting the future growth of a market. Pendharkar (2009) presented the hybrid GA with neural networks to forecast the churn in cellular network services. The hybrid algorithms optimize the objectives after learning and assigning weights to certain parameters. Results obtained from GA method are shown to be more accurate than statistical models but are computationally expensive.

3.2 Network type based classification

In this section, we will describe the applications of GAs in wireless networking categorized according to the type of wireless network. In particular, we will present GA applications in the networking configurations of wireless sensor networks (WSNs), wireless mesh networks (WMNs), cognitive radio networks (CRNs), cellular networks (CNs), and software-defined wireless networks (SWNs).

3.2.1 Wireless sensor networks (WSN)

Wireless sensor networks have emerged as an exciting technology that can be used to monitor the physical world. WSN is composed of self-organizing, miniaturized sensors nodes, running on batteries, and communicating over wireless links. The major challenge in WSNs is to provide area coverage with minimum WSN nodes while preserving the resources and energy consumption.

Jia et al. (2009) addressed this problem through MOGA for energy-efficient coverage control in WSNs. The algorithm provides a mechanism to cover the maximum deployed area with minimum number of WSN nodes. Since connectivity and coverage are both dependent on each other, this problem is addressed by MOGA approach by achieving the Pareto optimal front. This is a non-dominated problem, so it comprises of multiple solution individuals that are evaluated against two fitness function coverage area and sensor used rate. The MOGA approach applied performs well in maximizing the area covered with least computation. Another advantage is that it avoids partial solutions in whole search space and reset sensor nodes once in whole network simulation.

Ferentinos and Tsiligiridis (2007) studied an adaptive WSN design based on MOGA. Individuals with random placement of nodes are utilized as population and GAs decide which sensors would be active and which would act as clusterhead. Random designs are encoded and fed to GAs and the winner chromosomes are going to decide the network infrastructure including clusterheads and active or passive nodes along with signal strengths. From evolution of characteristics, it was shown that generally it is more favorable to have large number of sensor nodes with low energy rather than having lesser number of sensors with high energy consumption. This application of adaptive GA in WSN can lead to increase in network life span while maintaining network properties close to optimal value as well as it helps in adapting sophisticated decisions about operating modes (clusterheads, active nodes with optimal signal range).

Extending the life span of any WSN network is active area of research. Different schemes have been proposed like centralized monitoring GA for keeping active and passive nodes in network. A similar approach has been discussed by Jin et al. (2003) to cut the energy consumption in WSNs. A GA is used for independent cluster formation to reduce the communication distances thus bringing the route cost down. Experimental results showed that keeping the number of cluster to 10 % of total nodes results in 80 % reduction in path cost and communication distance as compared to random distribution of WSNs. In another work, Sengupta et al. (2012) have proposed an evolutionary multiobjective sleep-scheduling scheme for differentiated coverage in WSNs.

Zhang et al. (2008) used GA to extend the work of Niculescu and Nath on network localization in WSNs (Niculescu and Nath 2003). The central idea is to employ GPS-enabled nodes, called anchor nodes, in the network and to have all the other network nodes estimate their position through 1-hop distances to the anchor nodes. The locations are then flooded by each node to the clusterhead which uses the location information to construct the graph of the entire network. By using standard GA operators like mutation and crossover, the proposed GA-based approach was able to better estimate locations resulting in lesser mean position error than other algorithms in literature such as the ‘semi-definite programming with gradient search localization’ (SDPL) (Liang et al. 2004) and the ‘simulated annealing based localization’ (SAL) (Kannan et al. 2005).

In another work, Hussain et al. (2007) have studied and simulated GAs for centralized hierarchical WSNs. The proposed scheme comprises a hierarchy of layers with the BS being at the top layer and the clusterheads and the sensor nodes occupying the bottom layer. GAs are used to construct clusters with clusterheads and other nodes. The BS layer keeps track of the entire cluster through their clusterheads. A GA approach minimizes the average cluster distances while simultaneously increasing the total number of transmissions. After configuring sensor nodes in optimized formation, the data transmission phase follows.

3.2.2 Wireless mesh networks (WMNs)

Wireless mesh networks provide a popular mechanism for the provisioning of cost-effective wireless broadband connectivity. WMNs are composed of (potentially mobile) mesh clients and (typically fixed) mesh routers that connect over a relatively static multihop wireless network (Chou et al. 2006). To address the issue of efficient placement of mesh routers, Xhafa et al. (2010) employed GAs to optimize the user coverage area and connectivity of mesh network through optimal placement of nodes in an area. Chromosomes are designed in rectangular grids having information of both clients and mesh router nodes. Crossover is implemented to preserve the chromosome traits by randomly exchanging parent and child router nodes from one cell to another in grid area, thereby promoting high-scoring chromosomes. Mutation is then utilized to randomly migrate a router to another grid and recalculating the fitness. Various models can be adopted for distributing client nodes such as the normal, uniform, and exponential distribution. GAs are excellent in computing the mesh router placements and always succeed in achieving the connectivity, irrespective of client distribution; however, area coverage is subjected to client nodes in network area.

3.2.3 Cognitive radio networks (CRNs)

Cognitive radio networks (CRNs) offer a potential solution for improving the spectrum utilization in the world of limited spectrum. In dynamic spectrum access (DSA) based CRNs, the secondary users of a network aim to utilize the spectrum opportunistically to offer QoS for secondary users without causing any interference to licensed primary users. Such DSA-based CRNs utilize cognitive radios (CRs) that incorporate various AI techniques for intelligent decision making (Qadir 2015). The main benefits of applying GA in CRNs are as follows: (i) it is conceptually easy to understand; (ii) it is inherently amenable to parallel solutions and, therefore, can be easily distributed; and that (iii) GAs lend support to multi-objective optimization and perform well in noisy unknown environments.

An early application of GA techniques to CRNs is documented in a paper authored by Rondeau et al. (2004). This paper presented the adaptation mechanism of a cognitive engine, implemented by the authors, that used GAs to evolve radio parameters to make them best for the user’s current needs. A ‘wireless system genetic algorithm’ (WSGA) is also proposed to realize adaptive waveform control and cross-layer optimization Rondeau et al. (2004). GAs have also been used for building distributed parallel solutions, using the technique of island GAs, to mitigate the channel assignment problem in CRNs (Friend et al. 2008). An island GA divides the overall population into subpopulations, known as islands, which then interact by migrating individuals to the other island. More details of parallel GAs, and of general parallel meta-heuristics, can be found in the survey Alba and Troya (1999) and Alba (2005), respectively.

(a) MOGAs for optimization of CRNs: Multi-objective optimization aims at estimating a true Pareto front optimization in wireless medium depending upon the external environment parameters. These radio environment parameters serve as genes and are encoded in binary strings, which form chromosomes. These chromosomes are evaluated against fitness function regularly in successive generations. After realizing sufficient fitness or completing predefined number of generation, these sets of transmission parameters are sent for updating new radio configuration. Due to variation in radio channel characteristics and spectrum availability, a cognitive radio has to maintain time-varying QoS while optimizing different parameters such as BER, throughput, power consumption, and interference.

Multi-objective genetic algorithms have been used extensively for optimization of cognitive radio networks (CRNs) (Fette 2009). The foremost aim of cognitive engine (CE) was to optimize the radio parameters for best QoS and the secondary goal to observe and learn for adaptation. To achieve these goals cognitive engines have (i) cognitive system module (CSM)—for modeling and learning (ii) wireless system genetic algorithm (WSGA)—for actions (iii) wireless channel genetic algorithm (WCGA)—for hardware implementation of radio parameters. These parameter and radio traits (called genes) represent chromosomes such as modulation, frequency, spreading, filtering, and FEC coding. Different objectives are optimized based on relative weights assigned to them using multi-objective approach. These objectives—including optimizing BER, power consumption, interference and MOGA approach—are applied on the population; the best-performing chromosomes are then chosen as the new set of radio parameters.

Case base decision theory (CBDT) for initialization of GAs: Since the secondary objective of CR is to adapt and evolve with changing environmental parameters by updating radio configurations, a CR system must be provided with a memory database that continuously monitors and learns GA outcomes in real-time optimization. As the system matures, with the passage of time, each new optimization would take less time to achieve global optima. To be more precise, CE keeps track of previous objectives and the winner chromosomes. So whenever a new objective or case is encountered, it is compared to previous cases in memory and chromosomes of the case/objective having maximum similarity and utility are used to partially initialize the GA population for current objective. Rest of the population is randomly generated to not only maintain diversity but also to help in achieving optima in lesser number of iterations. This adaptation scheme is carried out through algebraic manipulations with the independently constructed channel availability matrix, the interference matrix, and the channel reward matrix (which are each kept up to date about the external radio environment conditions) (Ye et al. 2010).

Rieser (2004) presented a biologically inspired cognitive radio model, using modern AI techniques. This model is based on adaptive cognitive engine that learns the radio environment, optimizes the radio parameters, and presents the best possible experience to secondary user. He built his foundation of GA-based technique on original Mitola (2006) proposed technique of software radios. He gave insights into all the popular AI Algorithms and how ineffective they are in evolving as compared to GAs, when faced with unanticipated radio channel environment. He applied GA to hidden Markov model for error modeling in uncertainties in radio channel environment. Wireless channel GA has its foundation on these radio environmental modeling.

The biologically inspired cognitive engine serves and evolves well in unanticipated radio channel environment, which makes it usable for military purpose and emergency situation. This whole cognitive architecture works in multiple steps. First, the engine gathers the channel information which is then subjected to machine learning techniques such as learning classifiers. After learning and modeling, these information are taken up to alter the radio configurations for tweaking appropriate settings (Fette 2009). Wireless system GA treats the radio as the analogue of a biological creature and makes optimized discoveries to keep the appropriate balance of radio parameters.

(b) Cognitive radio (CR) testbeds: Rieser (2004) developed a biologically inspired cognitive radio CR testbed. A number of cognitive theories are developed and evaluated in parallel through the use of GA operators. This developed testbed consists of multilayered cognitive engine inspired by human brain evolution. The architecture is shown in figure. It provides multilayered scaled functionality with sensing radio parameters at both MAC and physical layers. It uses three algorithms that can be co-located in same radio or distributed to multiple radios. Another GA-based software testbed for cognitive engine (CE) is proposed by Kim et al. (2008). A two-step GA is used to avoid problem of optimizing the biased dominant parameters. To implement this, GA-based iteration is run for channel selection and transmitter parameter selection separately. Simulation of this testbed demonstrates that bandwidth and transmit power converge to optimal values with in few iterations of GAs.

3.2.4 Cellular networks (CNs)

Next-generation wireless networks have to cope with the massive increase in multimedia service along with cellular data. This motivates the development of self-consolidating networks that are capable of making intelligent decision to offer the best user quality of experience (QoE). Ayyadurai et al. (2011) presented an adaptive GA to optimize the cellular networks’ spectral efficiency through dynamic allocation of resources, between the relay stations and the base stations. Population adjustment came along the way to improve the search capabilities leading to quick optimum. Chiaraviglio et al. (2012) presented the energy efficient deployment of cellular networks by leveraging GA to minimize the power consumption and number of transmitters in cells. This involves employing sleep modes, where a base station decides which nodes should be powered on, depending on number of active users in given cell.

A conflict-free channel assignment is an NP-hard problem. A powerful GA incorporating immune operators including immune clone, immune vaccination, and immune selection has been proposed by Zhenhua et al. (2010) to mitigate the interference constraints and obtain a conflict free channel assignment. Vaccination involves changing some bits of a gene to have an improved fitness value. Elitism keeps the population diversity and minimum separation encoding helps in keeping a frequency distance among individual channels. A similar approach has been studied by Pinagapany and Kulkarni (2008) for solving both dynamic and fixed channel assignments in cellular networks. Channel compatibility matrix is constructed first to record the violation of individuals. After that, cell and bandwidth information is encoded in individual chromosomes and then subjected to crossover and mutation. José-Revuelta et al. (2007) offered low computational micro GA with elitism strategy to solve the fixed channel assignment (FCA) problem. The proposed algorithm spotlighted how to keep diversity by varying mutation probability to avoid local optima.

In cellular networks, it is desirable to minimize the call drop and call blocking probability. Mobile cellular networks are often evaluated against the criteria of dropping probability of current calls and the blocking probability of new calls. Lima et al. (2007) studied two adaptive GAs for locking and switching channel to solve the dynamic spectrum access problem in cellular networks. The proposed fitness function evaluates the capacity of each channel for new calls and also keeps track of existing calls. The algorithm takes care of randomness by allowing random immigrants and parameter adaptation to keep exploring new option for each channel.

3.2.5 Software-defined wireless networks (SWNs)

In recent times, software-defined networking (SDN) has been proposed as a new architecture for conveniently operating and managing diverse wireless networks. SDN is generally understood to entail (i) the separation of the control and data plane; (ii) the control of multiple data planes by a single controller; and the (iii) development of new sophisticated control abstractions (Qadir et al. 2014). Wireless networks using SDN principles are referred to as software-defined wireless networks (SWNs). Although this networking configuration is relatively new, the use of GA has been proposed in SWNs. For example, Bojic et al. have proposed a small-cell mobile backhaul resource manager, based on GA, that interworks with software defined management (Bojic et al. 2013).

3.3 Hybridization: GA with other techniques

Genetic algorithms is a useful framework that can be profitably used in a wide variety of settings. It is also possible to use GAs with other adaptive algorithmic approaches such as game theory, reinforcement learning (RL), graph theory, fuzzy logic-based, and quantum theory-based systems. Such a symbioses is not at all antithetical from the theme underlying the GA framework which encourages pluralism in preference to relying on any one solution; it is often the case that we can perform better by combining the best parts of different solutions as building blocks. In this section, we will describe hybrid approaches that combine various techniques with the principles of GAs. We will not only identify the GA hybrid technologies, but will also describe their application specifically for wireless networks. We note here that some of the various applications of hybrid techniques involving GAs have already been presented in earlier sections (such as in Sect. 3.1) and tables in this paper. The interested reader can also refer to these places for specific pointers to hybrid techniques involving GA in wireless networking literature.

3.3.1 Combining GAs with game theory

Game theory is a mathematical decision framework through which we can study and analyze competitive interaction between two or more self-interested rational agents. The field of evolutionary game theory utilizes the concepts of evolutionary computing and GAs in the backdrop of a game-theoretic background (Weibull 1997).

Applications of GAs with game theory in wireless networks: Evolutionary games have been used in a wide variety of contexts in networks including cooperative sensing (Wang et al. 2010), multiple-access-control and power control (Tembine et al. 2010), routing games (Altman et al. 2007), network selection games (Niyato and Hossain 2009), congestion control (Altman et al. 2008), adaptive TCP (Anastasopoulos et al. 2010), and for dynamic bandwidth allocation (Zhu et al. 2010). The interested reader is referred to a chapter on this topic in a recently published book on game theory in wireless and communication networks (Han 2012) for a detailed treatment.

3.3.2 Combining GAs with reinforcement learning

Reinforcement learning (RL), unlike supervised learning, is a technique where agent has no prior knowledge of transitions and learns along the way through experience and interaction with the environment. We note that evolutionary algorithms like GAs are related to reinforcement learning as they rely on exploration and exploitation (Črepinšek et al. 2013).

More specifically, GA utilizes the genetic operators of mutation and recombination as procedures for exploration along with selection procedures to exploit known good solutions. RL can be carried out both by searching through the policy space or the value-function space. GAs can be thought of as a RL scheme of the policy space searching variety. Policies are encoded in chromosomes and deterministic procedure is used to evaluate the cumulative fitness of the agent that follows a given policy. According to evolutionary principle of survival of the fittest, only good policies are adopted while failed or weaker policies are relinquished (Moriarty et al. 1999).

Applications of GAs with RL in wireless networks: Generally speaking, RL algorithms are well suited for distributed problems like routing and localization and they can be used with GA to solve NP-hard problems (that are difficult to solve optimally) heuristically. While there is limited deployment of RL-based GA solutions in wireless networks, in principle an RL-based GA can be implemented where RL is responsible to construct multi-individual crossover operator to facilitate search of global traits (Črepinšek et al. 2013).

3.3.3 Combining GAs with graph theory

In order to produce robust dynamic graph-theoretic solutions, graph theory can be combined with GAs in particular, and with evolutionary algorithms more generally. The combination of graph theory with evolutionary algorithms is known as evolutionary graph (EG) theory in literature.

Applications of GAs with graph theory in wireless networks:Ferreira et al. (2010) have applied EG theory in MANETs with known connectivity pattern for developing efficient practical routing protocols. The dynamic behavior of network is captured through evolving graphs. There are various metrics that can be used for determining optimal routes in EG-based models with known connectivity patterns, including the three metrics: shortest, fastest, and foremost as proposed in Xuan et al. (2003). These metrics determine, respectively, the minimum number of hops, the minimum time span, and the earliest arrival data. Ferreira et al. (2010) utilized the foremost journey metric along with the EG theory. The proposed algorithm can estimate the congested nodes and suggest the parallel paths. In another work, a bio-inspired graph theoretic solution for ensuring energy efficiency in cooperative communication networks has been proposed in Gajduk et al. (2014). The presented algorithm combines graph theory with evolutionary techniques to allow the nodes to intelligently operate in a decentralized fashion, and do forwarding by selecting nodes that conserve energy.

3.3.4 Combining GAs with fuzzy logic

Fuzzy logic is a logical system that can entertain logical variables that take continuous values between 0 and 1 instead of discrete values of either 0 or 1 (as in classical digital logic). Fuzzy logic is as an effective method for knowledge representation, control implementation, and cross-layer optimization in wireless networks (Baldo and Zorzi 2008). Fuzzy logic is well suited for knowledge representation in wireless networks since network conditions in wireless networks are often incompletely and imprecisely known. Fuzzy systems that utilize fuzzy logic are highly suited to problems with imprecise, noisy, and incomplete input information. GA can be used for both optimizing the fuzzy membership function as well as the fuzzy rules that drive the fuzzy control system. The intersection of hybrid technologies of GA, fuzzy logic, and other AI techniques (most prominently neural networks) is studied in the research theme of ‘soft computing’ Zadeh (1994). The trend of genetic fuzzy systems for soft computing applications is less developed than the trend of neuro-fuzzy systems, especially in the context of industrial control applications.

Applications of GAs with fuzzy logic in wireless networks: The use of genetic fuzzy techniques is popular for both communication systems (Wang 2003) and wireless networks. A localization scheme (Yun et al. 2009) based on RSS is designed using fuzzy logics and GAs. Fuzzy logic is used to model the edge weights and GAs play its part in optimizing the node placement. It is a distributed scheme since each node independently estimates its position. This scheme is particularly useful in large-scale networks. In a similar way, Saeedian et al. (2011) proposed a hybrid approach of fuzzy logics with GAs to select the clusterhead in WSN. This approach is a trade off between network-life and load. GA is used at base station to select nodes that have least energy metrics for their communication channel with clusterheads.

3.3.5 Combining GAs with quantum theory

Quantum theory derives its root from quantum mechanics, i.e., mechanics of atoms. A comparative study has been performed in Narayanan and Moore (1996) between quantum GA and classical GA. Quantum GA proves to be faster and more robust then classical GA for traveling sales person problem. Quantum GA operates on qubit as a smallest unit of information that serves as a linear superposition of two states, i.e., 1 and 0. A rotation gate is applied to keep the diversity of population in quantum GA. Quantum GA behaves more effectively than traditional GA for larger input set owing to its linear superposition states.

Applications of quantum GAs in wireless networks: A quantum GA is proposed in Luo (2010) to solve the NP-Complete QoS metrics problem in WSNs. The quantum GA performs more efficiently as compared to traditional GAs, especially for large-scale networks. To solve multicast QoS problem in WDM networks, a robust quantum GA is proposed (Xing et al. 2009) which incorporates multiple rotation angle steps (RAS) to foster the evolution process. Using multiple RAS schemes combined with repair methods helps faster convergence and elimination of unfits. In the cognitive radio domain, Zhao et al. (2009) used quantum GA along with particle swarms to solve the channel allocation problem.

3.3.6 Combining GAs with local search

A very common form of a hybrid GA, sometimes referred to as memetic algorithms (Moscato and Cotta 2010) in literature, is created by combining GAs with local search techniques and to incorporate domain-specific knowledge in the search process (Sastry et al. 2005). This can help produce stronger results but at the cost of higher computational costs. The local search operator is applied to each member of the population after each generation.

Applications of GAs with local search in wireless networks: Memetic algorithms have been extensively used in the context of wireless networks for various tasks such as energy-aware topology control (Konstantinidis et al. 2007) that solves the minimum energy network connectivity problem in WSNs better than spanning tree methods. The fitness function is designed to promote the least energy-consuming solution. Ting and Liao (2010) used memetic algorithms to increase the lifetime of WSN networks. The algorithm uses a compact operator that places the redundant sensors to get maximum coverage and minimum energy consumption. In cellular networks, assigning cells to switches is NP-hard problem. A multi-population memetic algorithm proposed by Quintero and Pierre (2002) outperforms the traditional tabu-search method with a considerable deduction in maintenance cost of WSN network for a 10-year period.

3.3.7 Combining GAs with other metaheuristics

A popular area of research is combining GAs with heuristic methods like ant colony optimization (ACO), artificial neural networks (ANN), and fuzzy logic to solve the dynamic constrained multi-objective optimization.

Applications of GAs and metaheuristics in wireless networks: GAs have been combined with various metaheuristic techniques in wireless networks. For example, there is ongoing research in wireless networks to use GAs to (1) discover the optimum mathematical models for grouping the cellular networks (Zhu and O’Connor 2013; Chiaraviglio et al. 2012; 2) train other algorithms like Recurrent Neural Networks (Syed 1995); and to (3) set optimal fuzzy parameters (Saeedian et al. 2011; Di Fatta 2003; Yun et al. 2008). In another work, Cauvery and Visvanatha (2009) have proposed a solution that combines GAs with ACO to reduce the size of routing table and help in routing among autonomous peers. ANNs, combined with GAs, have been used to forecast the churn in cellular network services (Pendharkar 2009) and for providing localization services (Chagas et al. 2012). There also has been a lot of work in applying GAs for adjusting the connection weights and the connectivity itself in ANNs (Whitley et al. 1990). In particular, a common application is to evolve ANN structures through the GA’s fitness function to select optimum parameters for the underlying network (Kulkarni et al. 2011). There is also research interest in combining GAs with other metaheuristic techniques such as swarm intelligence to provide wireless solutions along with limited computation overhead. Notwithstanding the amount of work done, there is a lot of scope for further optimization and improvement.

4 Practical issues and lessons learnt

In this section, we will summarize the main insights and lessons learnt through decades of GA research that can guide successful problem solving through GAs. We first describe insights about when and where to apply GAs in Sect. 4.1. We follow this up by a discussion on common pitfalls in Sect. 4.2 and finally describe guidelines and insights for successful GA implementations in Sect. 4.3.

4.1 When/where to apply GAs?

4.1.1 Comparison with other techniques

The metaheuristic technique of GAs can be compared to optimization techniques that guarantee globally optimal solutions. Optimization problems can be divided into continuous optimization problems and discrete optimization problems (that are also known as combinatorial optimization algorithms). Convex optimization problems are generally held to be tractable whereas nonlinear optimization problems can become intractable, especially when we consider large problems.

Apart from GA, there are a number of metaheuristic techniques, and many of them have been applied in the context of wireless networks. For instance, there are both nature-inspired algorithms—such as GAs, ant algorithms, simulated annealing—and non nature-inspired algorithms such as tabu search and iterated local search. Many of these metaheuristic techniques rely on iterative search. Metaheuristics can also be compared based on the number of solutions used at the same time. GAs use a population of solutions, whereas other techniques (known as trajectory methods) such as simulated annealing use a single solution at a time. A comparison of metaheuristic methods can be found readily in existing literature (Osman and Kelly 1996; Blum and Roli 2003; Glover and Kochenberger 2003). In this section, we will consider the restricted subset of metaheuristics comprising hill-climbing and simulated annealing.

Hill-climbing is trivial to program and does not require any memory (since no backtracking is involved), but such algorithms can get caught in local optima easily. Hill-climbing is a good option for finding local optima, which makes it optimal for convex problems (since for convex problems, the local optima is the global optima). For example, the simplex algorithm for the convex problem of linear programming uses hill climbing for exploring the solution space. Since hill-climbing can only guarantee finding of local optimas, hill-climbing is often complemented with a scheme that uses memory-based search optimization using the tabu search, or memoryless stochastic modifications such as simulated annealing.

Simulated annealing like GA is a nature-inspired stochastic search technique. While GA is modeled on the natural evolution, SA takes inspiration from thermodynamics and statistical mechanics (Blum and Roli 2003). The fundamental idea of SA is to tolerate moves that result in temporarily worse-quality solutions compared to the current solution to escape the local minima. The probability of adopting such myopically suboptimal moves is reduced during the search. Simulated annealing and GAs both are well suited to high-dimensional spaces. Simulated annealing is used mostly when the search space is discrete. Simulated annealing has been applied in wireless networks for various problems such as localization (Kannan et al. 2005), power control (Montemanni et al. 2005), etc. Simulated annealing has also been used together with GA, and ant colony optimization, for high-performance multicast routing in QoS constraints that has a high convergence speed (Damanafshan et al. 2014).

Apart from GAs, ANNs are also widely deployed in wireless networks. Compared to GAs (which are essential search tools for metaheuristic optimization), ANNs are best suited for the task of classification and prediction of pattern (and find wide application in intrusion detection and spectrum sensing systems). ANNs, unfortunately, can be quite brittle in the presence of unknown environments that characterize wireless networks and can suffer from the problem of requiring extensive training.

In the particular context of wireless networks, while optimization has been extensively applied for resource allocation in wireless networks (Lin et al. 2006), optimization algorithms typically make the assumption of complete network information. In addition, optimization problems assume a static unchanging environment that is not realistic for wireless networks. A key benefit of GAs is that they are well suited to the optimization task in the ever-changing environments that characterize wireless networks (in which there is interaction between the various adaptive wireless nodes and interdependency between the various node’s decisions). GAs are well suited for building metaheuristic adaptive algorithms that can provide satisfactory performance in changing network conditions. Compared to local optimization methods (e.g., gradient descent), GAs have the advantage that they can escape suboptimal local maximum/minimum of the target function. Since GAs rely on a population of solutions along with various genetic operators, GAs do not necessarily remain trapped in a suboptimal local region. As discussed above, various other metaheuristic techniques have also been proposed for use—some of them in concert with GAs—in wireless networks. Their deployment for wireless solutions should be planned in light of the pros and cons of these solutions (which has been briefly discussed above).

4.1.2 Recommendations for using GAs in wireless networks

Genetic algorithms are not ideally suited for a distributed implementation in wireless networks (especially in energy-conscious wireless networking configurations such as WSNs) since running GA on each node would cause energy overhead and reduction in network lifetime. In problems that require distributed network solutions (like localization and routing), reinforcement learning can be a better choice.

Genetic algorithms perform best in a centralized setting (e.g., at a cellular network’s base station) for optimization of outputs and making optimal decisions while algorithms like Q-learning (Watkins and Dayan 1992) (a type of reinforcement learning) could be working in distributed manner on individual nodes. Use of GAs is better suited to MANETs than WSNs because of limited energy resources on individual WSN nodes. Using GAs in combination with other intelligent systems like ANN and fuzzy systems can also give better optimization results. Abu Alsheikh et al. (2014) have presented a comprehensive review article of all machine-learning (ML) techniques (including a discussion on GAs). While this paper focused on the use of ML techniques in WSNs, the interested reader can consult (Abu Alsheikh et al. 2014) for a comparative analysis of GAs with other comparable ML and metaheuristic techniques.

4.1.3 Tasks for which GAs are most suitable

The major strength of GAs, offsetting their inability to provide optimal solutions, is their great generality. GAs are the algorithmic workhorses that can be applied to a wide variety of problems. GAs can be applied wherever the corresponding search space is defined, and the desired solution could be quantified through an appropriate formulation of a fitness function. It has been said that “neural networks are the second best way of doing just about anything, and genetic algorithms are the third” (as quoted in Russell and Norvig (1995)). This highlights the fact that in most scenarios, optimal niche solutions will return better performance than GAs. Thus GAs should not adopted for problems that can be optimally solved by techniques such as linear programming, A-star search or constraint propagation.

In the context of wireless networks, GAs hold a lot of promise for efficiently solving complex (typically NP-hard) problems that are not amenable to efficient optimal solutions. It is worth pointing out that many problems in wireless networks—including those that focus on channel assignment (Mir et al. 2012) and routing [especially when we consider multi-rate (Qadir et al. 2006) and multi-interface wireless networks (Hassan et al. 2013)]—are NP-hard and thus obtaining the optimal solution is considered computationally complex. GAs are well suited to such complex problems for which an optimal solution is not known or is too complex; in such circumstances, GAs may be the “best” practical solution. GAs—unlike traditional optimization algorithms—are also well suited to the dynamic environments that characterize wireless networks.

4.2 Common pitfalls

While GAs provide a useful framework for problem-solving in a wide variety of domains, they also suffer from various deficiencies that have been identified in literature. GA-based solutions for wireless networking also inherit these problems. In this section, we will highlight these general deficiencies that GA-based solutions will suffer from. In addition, we also identify and highlight common pitfalls regarding implementing GAs in wireless networks.

4.2.1 Genetic drift or bias

In GAs, there is a risk of slow convergence and settling for local minimas, especially with inappropriate choice of model parameters. While GAs can often converge to the global optima in the majority of applications, there are no mathematical guarantees to this effect. In particular, a GA can get stuck in the vicinity of a suboptimal point if it lacks population diversity, or if has an inappropriately small population. Such a phenomenon is known as ‘genetic drift’ or ’genetic bias’. Certain problems cannot be solved by means of simple genetic operations. This is mainly due to the choice of poor fitness functions that generate poor chromosome blocks. There cannot be an absolute assurance that a GA will be able to find a global optimum—this can especially be a problem when the population has a lot of subjects.

4.2.2 Using GAs for real-time applications

Like most other AI techniques, GAs are not well suited to real-time application that require guaranteed response times due to its stochastic and heuristic nature. In addition, the response time of GA can have significant variance depending on the various control parameters and population initialization. This potential pitfall should be kept in mind if GAs are used for online learning and optimization in wireless networks. In particular, Qo requirements in wireless networks may put constraints on achieving the optimum decision in limited time forcing GAs to terminate after predefined number of iterations.

Table 11 Summary of GA paramater settings guidelines generally accepted by the GA community

4.2.3 GA deception

It has been reported in literature that certain objective functions, referred to as GA-deceptive functions, can be very difficult to optimize. With such deceptive functions, combination of good building blocks may result in very bad chromosomes, causing the building block theory to fail. A potential solution to this problem is using messy GAs (Mitchell 1998).

4.3 Implementation insights

There are numerous challenges in devising an appropriate GA-based solution including suitable definitions of population size and evaluation function (which is typically non-trivial to define). In this section, we highlight some general implementation insights that have been gleaned from the body of knowledge representing GA research. Wireless practitioners can use the insights presented in this section for designing efficient GA-based algorithms.

4.3.1 Setting population size

The size of the population in a GA can be a major factor in determining its quality and convergence speed. Generally speaking, larger populations result in better solutions. A few studies have addressed the problem of determining exactly how large a population should be to ensure a certain quality (Goldberg 1989; Goldberg et al. 1991; Harik et al. 1999). For a moderately complex problem, a population of 50–100 chromosomes can serve as a good default value (Cox 2005). The precise choice of the population size depends on the problem complexity and the number of search variables. While it is typical for the population size to remain fixed from one generation to the next, it can also be made to grow or contract depending on the rate of convergence, and other factors such as the current genetic diversity.

4.3.2 Designing solution encoding and fitness function

The efficiency, processing power, and the convergence of GAs depend critically on how the solution is encoded in the form of chromosomes and on the formulation of an appropriate fitness function. This is the first necessary step towards an efficient implementation. There is no one-size-fits-all solution here, and the correct model choice depends on what is most useful for the problem at hand. The encoding of chromosomes should be carefully considered. While a majority of implementations utilize bit representation, due to the ease with which crossover and mutation can be implemented, other representations, utilizing data structures, may be appropriate for the considered problem and should also be considered (Sastry et al. 2005). Since there can be numerous encoding and formulations, this step involves considerable ingenuity. Some guidelines on these issues are provided in Grefenstette (1986), De Jong and Spears (1991).

4.3.3 Setting of mutation and crossover rates

The optimization of the control variables of GAs (such as the setting of mutation and crossover rates) plays an important role in the performance of a GA-based framework. A GA framework can avoid prematurely settling in a suboptimal rut by emphasizing exploration using mutation. Various solutions have been proposed to the problem of genetic drift/bias including fitness sharing (Fonseca and Fleming 1995), crowding, and pre-selection (Mahfoud 1992). Bhandari et al. (1996) showed that the probability of fast convergence increases by seeding the initial population with high-scoring chromosomes. As a general rule-of-thumb, crossover and mutation rates of 0.6 and 0.001 have been proposed for large population sizes (of $\sim$100), with corresponding values of 0.9 and 0.01 proposed for small population sizes (of $\sim$30) (Grefenstette 1986; De Jong and Spears 1991). Sastry et al. (2005) similarly recommend a mutation probability of 0.05 and a crossover rate of 0.6 with a population size of $\sim$50. A tabulated summary of mutation and crossover rates generally recommended by the GA community and accepted as de facto ‘standards’ are presented in Table 11.

4.3.4 Computation of fitness values

In many problems, the computation of the fitness function can be extremely computationally intensive, thus motivating research in fitness approximation (Jin 2005). An important practical issue is to determine ways of modeling large complex systems so that the fitness value can be computed without executing the real-world system itself (which can be impractical in many situations).

4.3.5 Setting of termination criteria

Assuming the population, and the various GA control variables, have been set up properly, the GA will improve towards the optimal solution over successive generations. In light of potentially slow convergence, it is very important to for timely problem solving with GAs to devise a suitable termination criterion that defines a ‘good enough’ solution. Defining these criteria is non-trivial and context-dependent. While this criteria depends on the number of objective functions, and the number of variables, a default value of 2.5 times the population size can be used as a reasonable maximum generation count estimate (Cox 2005).

5 Open issues and future work

In this section, we provide the recommendation on scope of future research on GAs in the field of networking. In Sect. 5.1, we will highlight the common issues that GAs generally face. Since any progress towards resolving these open research problems will benefit all GA-based solutions, it is worth highlighting these problems. In Sect. 5.2, we will highlight open research issues and future work specific to the application of GAs for wireless networking.

5.1 General issues with GAs (not specific to wireless)

5.1.1 Theoretical results for GAs

A lot of effort has focused on providing theoretical understanding of why and how GAs work but rigorous results have been slow in coming. Some of the results, such as “No Free Lunch”, have sobering implications. Simply stated, no free lunch implies that all search algorithms perform equally when averaged over all problems. This further entails that if we are comparing GAs with other search heuristics (such as hill climbing or simulation annealing), even if GA performs better for some class of problems, the other algorithms will necessarily perform better on some problems outside this class. GAs are also population-based heuristics; even as the entire population is improved by GAs, the same cannot be guaranteed for an individual existing within that population. There is a need for enhanced theoretical understanding of various facets of GAs to lay a strong foundation upon which the GA user’s trust can be safely placed.

5.1.2 Efficient multi-objective and distributed GAs

The development of practical algorithms for wireless networks often requires the use of multi-objective optimization performed in a distributed fashion. Currently, the most popular approaches in wireless networks depend on centralized GA (Lai et al. 2007): e.g., in mobile cellular networks, the GA runs on the BS and helps decide the cluster size and nodes deployment. In wireless networks, there is often a need to distribute the computational load to various network nodes. This can be done by a locally run GA on each node combined with local search techniques for robustness.

5.1.3 Using big data techniques for scaling GAs

Big data techniques have the ability to scalably and reliably process massive amounts of data using a cluster of commodity servers (Qadir et al. 2014). Big data processing techniques, such as Google’s MapReduce and other frameworks of its ilk, hold a lot of promise for processing large problems in quick time. This is done by horizontal scaling, or ‘scaling out’, through which more and more computers are employed to attack a given problem in parallel. There is potentially a lot of scope in employing these big data processing techniques to accelerate the convergence of GAs. A steady trickle of research has started emerging that is proposing the use of big data tools (such as the open-source Apache Hadoop platform which is built on Google’s MapReduce paradigm) to scale up GAs (Verma et al. 2009; Llora et al. 2010). More research needs to be done to determine how to best utilize big data tools and techniques for improving GA performance.

5.2 Using GAs in wireless (wireless-specific issues)

5.2.1 Exploiting problem-specific knowledge

Genetic algorithms are often resorted to as black-box solutions to complex problems where the mechanisms to be used for problem solving are not well understood. Even without problem-specific knowledge, GAs can allow insights to develop thorough identification of similarities between highly fit individuals (Goldberg and Holland 1988). When the subject knowledge is available, in the form of good understanding of the underlying problem and plausible candidate solutions, it is desirable to exploit this information to expedite GA’s progression towards a solution. The question of how to embed wireless-specific subject knowledge into the GA frameworks is very much an open research issue requiring further exploration. One way of embedding problem-specific information in the GA system is by seeing GAs with good structures and populations thereby accelerating search and learning progress. However, the use of problem-specific knowledge to generate specialized heuristics or operators can entail some loss of generality of the GA system (Goldberg and Holland 1988).

5.2.2 Niche applications of GAs for wireless networks

GAs can be useful for optimizing new applications for wireless networks. As an example, there has been a lot of ongoing work in hierarchical clustering for scalable networking (Shurman et al. 2013; Pandey et al. 2007; Huruiala et al. 2010) in which GA has provided promising solutions; there is also an ongoing research on GA-based dynamic cluster design based on multiple metrics (Quintao et al. 2005). There is also room for improving the throughput by extending the GAs from single cell to multi-cell optimization and by working on inter-channel noise cancellation (Ayyadurai et al. 2011). Finally, there is a need to discover GA-based low-energy-consuming distributed schemes that can provide maximum disjoint covers to enhance the coverage area and network life.

6 Conclusions

We have provided a survey of the applications of genetic algorithms (GAs) in wireless networking. In addition to providing a self-contained introduction to common models and configurations of GAs, we have also provided a detailed survey of applications of GAs in wireless networking. We have categorized the applications of GAs in wireless networking both according to the wireless networking configuration and according to the different kinds of GA techniques. We have also highlighted pitfalls and challenges in successfully implementing GAs in wireless networks. Finally, we have highlighted a number of open issues and have identified potential directions for future work.