Keywords

1 Introduction

With the growth-based networks using wireless framework, the performance of these networks leads to the reliability of Internet which in turn largely depends on how the routing protocols operate [1]. The operation of these routing protocols is dependent upon the network technology, its configuration parameters focusing upon the traffic load on the routers and its links. Specifying the concept of wireless systems routing becomes a highly challenging task due to the mobility of these types of systems. The traditional routing protocols utilized in the current networks are developed to exploit dynamic optimization by finding optimized paths based on shortest distance, minimal bandwidth and delay and limited power and capability of links, etc. Number of topology changes frequent in nature occur in wireless-based cloud systems due to mobility of wireless nodes and their energy conservation therefore, dynamic optimization problem (DOP) for route discovery becomes quite important. For finding solutions of various routing issues, traditional methodologies utilizing deterministic algorithms like shortest path tree (SPT) and search heuristics based neoteric approaches like genetic algorithm, ant colony optimization, simulated annealing, etc., are explored. Deterministic systems, on one hand, construct only on one route tree for a given route discovery request whereas meta-heuristic based algorithms search number of route trees and from them select optimized one as the final route, as these algorithms have polynomial time complexity, hence providing enhanced Quality of Service (QOS) based solutions for cloud-based wireless networks. When compared with deterministic systems (Previous Dijkstra’s Algorithm), GA-based meta-heuristic approach works on a population of possible solutions rather than on a single solution. The individual chromosomes (initial population) of the GA-based approach undergo selection operation on the basis of their fitness value followed by the natural genetic-based crossover operation for offspring generation by randomly exchanging the individual genetic data focusing on the fact that GA is stochastic in nature rather than deterministic [2–6]. This chapter exploits GA-based methodology of soft computing for optimization of various QOS parameters like packet delivery ratio (PDR), packet drop rate (pdr), end-to-end delay (EED) and hop count (HC) for wireless-based cloud networks by selection of optimal or fitness route from a given source to a given destination from a route set of different connectivity qualities. Upcoming sections of this chapter will highlight on utilizing soft computing based GA approach for optimization of QOS in wireless-based cloud networks by validation through simulated results.

2 Importance of Genetic Algorithm

Natural evolution is the main source of inspiration for genetic algorithms for becoming a heuristic and optimization methodology proving to be applied successfully for various complex and significant real-world problems. This section of the chapter focuses on utilizing the success of GA-based approach for improving the quality of service (QOS) parameters of traditional routing approaches (e.g. Dijkstra’s) being used in the current routing protocols of wireless-based networks or cloud networks. GA has been a great interest for various mathematicians, immunologists, etc. Before discussing how GA has enhanced QOS parameters of wireless and cloud networks (discussed in next section), we will first focus on the GA construction and its theoretical specific strands speculatively. Darwinian principle of evolution is the main motivation for GA-based heuristic and solution search heuristic and solution search based optimization methodology. For evolving for solutions to various problems GA utilizes evolutionary processes which are highly abstracted in version. Populations of GA operation are the chromosomes which are binary strings. Fitness function of GA-based approach is a real number in the solution representation of chromosomes specifying how good solution is for a particular problem [7–16].

The successor population or the next generation of GA is produced through fitness selection and recombination of the randomly generated population of chromosomes. Recombination process selects the genetic material of parent chromosomes which undergoes recombination to form child chromosomes and continues further inheritor population. Process iteration evolves a successive generation sequence leading to increase in the chromosomes average fitness until reaching a stopping criterion. Hence, GA evolved as a best (optimized) solution for a given problem. For computationally intractable problems, Holland [17] proposed GA for finding good solutions. The theoretical concepts of GA and its straight forward implementation were proved by Schema Theorem written by Goldberg [18] and its block hypothesis [17]. These results led to the growth of GA in solutions of practical problems of sciences, industry and engineering also discussed in this chapter for QOS-based route optimization in cloud-based wireless networks. GA-based approach is quite dynamic in nature using methodologies not utilized by traditional approaches, hence its success leads to the growth of other intelligent meta-heuristic based approaches like neural network (NN), ant colony optimization (ACO), particle swarm optimization (PSO), artificial intelligence (AI), etc. [19].

2.1 Structure of Genetic Algorithm

Implementation of GA is not very complex as it is constructed from distinct reusable components having trivial adaptation. The components of GA which form its basic structure include encoding of chromosomes, development of fitness function, selection of population based on fitness function, recombination and scheme evolution being the last operations. Figure 1 shows the evolution flow of genetic algorithm.

Fig. 1
figure 1

Evolution flow of genetic algorithm

Full size image
  1. (i)

    Chromosome Encoding

Chromosomes in a GA for a particular problem are the representation of strings represented as {A, C, G, T} which is a biological abstraction of DNA chromosome. Locus is the particular position in a chromosome called a gene, and the letter at the point of locus is called as allele value or allele. Allele values are the bit strings of chromosomes that are represented as character alphabets {0.1}. GA operates on bit strings of length around 100 for a solution space of 2100–1030 individuals.

  1. (ii)

    Fitness

Fitness function for a particular problem specifies computation by evaluating chromosomes of genetic algorithm.

  1. (iii)

    Selection

Selection process of GA utilizes fitness function for the evolution of the genetic chromosomes by applying a selective pressure. On the basis of their fitness, chromosomes are selected for recombination where better is the fitness of chromosomes greater is the chances of selection. Roulette wheel, random stochastic selection, tournament selection and truncation selection are generally utilized as traditional selection methods.

  1. (iv)

    Recombination

Members of a successor population are formed through recombination process by selected chromosomes of a given population. This is done by simulating the mixed material occurring at the tie of organisms’ reproduction. Crossover and mutation are the two basic components of the recombination process where crossover produces one/two child chromosomes by mixing genetic material of the two parent chromosomes being selected.

The given example below represents the crossover operation done over a 10-bit string.

Mutation operation of GA flips one/more allele values by acting on the various individual chromosomes. When mutation rate ≥ the random value, then the flipping of allele values takes place as 0–1 or vice versa. For better results and overcoming the problem of local/global minima, mutation rates are chosen quite small like 0.001, etc.

  1. (v)

    Evolution

Many evolutionary schemes are based upon how much the initial chromosomes are unchanged with respect to the inheritor population. Complete replacement and replacement with elitism are some of the methods utilized for the evolution.

2.2 Design of GA

The nature of the problem is the most important criterion for the design and encoding of GA. After the encoding methodology is being selected, next decision is about the type of fitness function, size of the population, respective rates of crossover and mutation operators, application of the evolutionary scheme and also the specific and appropriate start and stop conditions. The design of GA basically depends upon experience of combination, modelling which is problem specific and experimentation based upon various evolution schemes [20–25]. A typical and classical GA design based upon complete replacement using standard operators of GA includes

  1. (1)

    Random generation of a population comprising of P chromosomes.

  2. (2)

    From the source population of initial chromosomes (C), fitness function F(C) is calculated.

  3. (3)

    A vacuous successor population is created and the following steps are repeated till creation of P chromosomes takes place.

    1. (a)

      Two chromosomes c1 and c2 are selected based upon the proportional fitness function from the initial source population.

    2. (b)

      Utilizing crossover rate pc one point crossover is applied to obtain c as the child chromosome.

    3. (c)

      A consistent rate of mutation pm is applied to produce c′.

    4. (d)

      c′ is being added to the inheritor population.

  4. (4)

    Source population is then replaced with the population of successor.

  5. (5)

    Step 2 is being returned, not meeting the stopping criterion.

2.3 Approaches of GA

The basic two goals for justifying theory of GA include explaining the classes of problem to which GA is particularly suitable and if suitable, why. Next includes the optimal design and implementation of GA through various techniques and approaches.

  1. (i)

    Schema and the Building Blocks: The central result of GA theory is based upon the Schema Theorem [17]. A set of chromosomes containing the pattern specifies the schema. Schema is referred as the string symbols from the alphabet {0, 1, *}. For chromosomes of length 10 bit, schema specifies using the string

Chromosomes belonging to the schema include

Chromosomes that do not belong to the schema, not matching the pattern, include

All the chromosomes that belong to the schema are **********.

For a schema X, the length lX is specified as antithesis of the allele positions of the first bits and the last bits that are being defined of X. The numbers of bits being defined specify order of X. For example, the schema 01***100** has defined bits that has the order 5. The position of last defined bit is 8 and that of first is at position 1. So, the length of schema is 8 − 1 = 7.

Theorem is defined by taking X as schema and chromosomes as mX that belong to X that is present in the population I of the GA being evolved. Then the number of is chromosomes expected to belong to X in the population i + 1 is denoted by

mX (i + 1), is represented by the formula

$$mX\left( {i + 1} \right) = FX\left( i \right)mX\left( i \right)\left[ {1 - \text{pc}\,lX/l - 1} \right]\left[ {\left( 1 - \text{pm} \right){\text{OH}}} \right]$$
(1)

where

FX (i) is the relative fitness of the chromosomes that belong to X that is being divided by the average fitness of the population of chromosomes.

pc is the probability of crossover operation.

pm is the probability of nutation operation.

  1. (ii)

    The Simple GA (SGA): SGA provides a dynamic mathematical framework for exploring fundamental properties of GA. It answers to the various questions expected

    1. (a)

      Locus Ω in SGA at time t?

    2. (b)

      Convergence of SGA at a global optimum based on what conditions?

    3. (c)

      Design choice of GA based on conditions of point (b).

    4. (d)

      What will be the mutation and selection operators?

    5. (e)

      What will be the selection schemes?

    6. (f)

      How the evolution points correspond to local/global minima.

  2. (iii)

    Statistical mechanics: [26] developed and utilized the theory of statistical mechanics for GA evolution having a fitness function (FF) based on Ising Model that has states of low energy of a spin glass through which investigation of dynamics for GA is done.

  3. (iv)

    GA is utilized in model fitting and optimal control in various applications, e.g. cancer chemotherapy optimization by GA.

3 Genetic-Based Heuristic Approach to Optimize QOS in Networks

Depending upon the various linguistic rules, network conditions currently and the policy, GA performs evaluation of the paths; output of the routing algorithm is resulted, after evaluating all the routes having good enough route values depending upon the evaluation function [27–30]. After performance evaluation of the values, the next loops are being selected from the various neighbouring nodes. The selection of the routing by the GA-based heuristic approach is done by optimizing QOS parameters like packet delivery ratio (PDR), hop count (HC), etc. The flowchart of genetic-based heuristic approach is depicted in Fig. 2. Given below are the specific parameters required for the GA-based heuristic approach

  1. 1.

    Genetic-based representation specifying node ID’s of the path of the source node through gene’s first position and last position gene represents the destination node.

  2. 2.

    Population initialization (PI) is the randomly generated routing path from the initial population chromosomes.

  3. 3.

    Fitness function (FF) is represented by function fval containing the object function including the arguments as initial route x, a matrix containing a proactive/reactive routing table, start location and end location. Route cost is initiallized as 0 and further values of route cost are obtained on the basis of steps given below:

    1. (a)

      Value of x1 is generated by subtracting 1 from size matrix and multiplying by x.

    2. (b)

      Next round x1 is generated as x1 = (A, B), where A = absolute value of x1 rounded and mod operator applied, B = increment of size matrix by 1.

    3. (c)

      A condition is applied to generate the route cost where comparison (==) is done between x1 and x which is further incremented by 2.

    4. (d)

      A for loop is followed, then route cost is generated as x1 matrix ith value, x1 matrix (i + 1) value added to initial route cost which is considered f value of route cost. Else the final value of route cost is size of matrix multiplied by 100 and added to 100.

  4. 4.

    Selection operator selects higher quality chromosomes based on FF to get the next generation.

  5. 5.

    Crossover and mutation are utilized to exchange partial chromosomes to overcome local/global minima issue.

  6. 6.

    GA-based approach is utilized as a solution for finding the shortest path from source (S) to destination (D) dynamically in a peer-to-peer cloud network. GA considers a peer-to-peer cloud network having an upper delay bound with a source node and destination node to get an optimized least cost path in a topological area.

  7. 7.

    The QOS parameters like packet delivery ratio, packet drop rate, end-to-end delay and hop count are taken into consideration for performance analysis.

Fig. 2
figure 2

Flowchart for genetic-based heuristic approach to optimize QOS in networks

Full size image

The simulation parameters taken into analysis of the meta-heuristic based genetic approach to optimize QOS in cloud networks are simulation time, network length and width, nodes of peer-to-peer cloud network, transmission range, node speed, node data rate, node traffic and speed and angle variation factor [31–33]. Figures 3, 4, 5, 6 and 7 specify the validation of the proposed approach through a MATLAB simulator.

Fig. 3
figure 3

Genetic algorithm output showing the effectiveness of optimized QOS parameter packet drop rate with node speed in the X axis

Full size image
Fig. 4
figure 4

Genetic algorithm output showing the effectiveness of optimized QOS parameter packet delivery rate with node speed in the X axis

Full size image
Fig. 5
figure 5

Genetic algorithm output showing the effectiveness of optimized QOS parameter end-to-end delay with node speed in the X axis

Full size image
Fig. 6
figure 6

Genetic algorithm output showing the effectiveness of optimized QOS parameter hop counts with node speed in the X axis

Full size image
Fig. 7
figure 7

Background working of genetic algorithm

Full size image

Figure 3 depicts the simulation of previous (Dijkstra’s) approach and proposed (Genetic-based heuristic) approach through varying node speed, validating the proposed approach through blue line, specifying how through the application of heuristic approach, the packet drop rate has decreased significantly.

Figure 4 depicts the simulation of previous (Dijkstra’s) approach and proposed (Genetic-based heuristic) approach through varying node speed, validating the proposed approach through blue line, specifying how through the application of heuristic approach, the packet delivery ratio has increased significantly.

Figure 5 depicts the simulation of previous (Dijkstra’s) approach and proposed (Genetic-based heuristic) approach through varying node speed, validating the proposed approach through blue line, specifying how through the application of heuristic approach, the end-to-end delay has decreased significantly.

Figure 6 depicts the simulation of previous (Dijkstra’s) approach and proposed (Genetic-based heuristic) approach through varying node speed, validating the proposed approach through blue line, specifying how through the application of heuristic approach, the hop counts have decreased significantly.

Figure 7 is just a background illustration of working of genetic algorithm which validates the proposed approach.

4 Conclusions

Talking about real-world peer-to-peer wireless network, routing is considered to be the parameter that will meet the most stringent QOS performance parameters. Uncertainty that is being created through user mobility in peer-to-peer networks makes the seamless data transmission quite a challenging task. A number of conflicting issues are raised in these networks. In real-world scenario when a particular objective function is optimized, other dependent objective can be sacrificed. The results shown in Sect. 3 specify how the heuristic-based genetic approach has led to neoteric optimized results mainly exploited to finding fittest shortest path leading to optimized QOS performance parameters. The conventional shortest path selection approach like Dijkstra’s (taken as previous approach in Sect. 3 simulation) was not able to provide better performance in terms of QOS optimization. Taking into consideration number of simulation parameters, the simulated, validated approach discussed in this chapter provides a flexible network by enhancing various QOS issues.