Evolutionary Algorithms are the stochastic optimization methods, simulating the behavior of natural evolution. These algorithms are basically population based search procedures efficiently dealing with complex search spaces having robust and powerful search mechanism. EAs are highly applicable in multiobjective optimization problem which are having conflicting objectives. Resource optimization in computer network is an important research problem and it can be easily handled by the use of multiobjective optimization approach. This paper reviews the work carried out for optimization in network routing.
Keywords- MOEA (Multiobjective Evolutionary Algorithms ), EMO (Evolutionary Multiobjective Optimization), Evolutionary Algorithms (EAs).
Introduction
Many optimization problems have multiple conflicting objectives. In this situation, one cannot derive a solution which is optimizing all the objectives simultaneously. Now it is required to find multiple trade-off solutions. Evolutionary Algorithms are well suited for solving multiobjective optimization problem and it leads to a burning research area called "Evolutionary Multiobjective Optimization" [1, 2, 3].
Resource optimization in computer network routing problem is an important research problem and it can be easily handled by the use of multiobjective optimization approach. As discussed in [7], the major resource requirements of the advanced computer network applications such as video conferencing, voice-over-IP etc. are bandwidth consumption, end-to-end delay, delay jitter, packet loss ratio and so on.
This paper has been divided into three sections. Section II introduces the Evolutionary Multiobjective Optimization. In section III, the review of various EMO based computer network optimization approaches are discussed. In section IV the research issues and challenges in this field are outlined. Section V is the conclusion and future scope.
Evolutionary Multiobjective Optimization
A multi objective problem can be defined as in [10] subject to k inequality constraints
……………..(1)
and q inequality constraints
……………..(2)
where n is the number of objective functions and
is called vector of decision variables. The objective is to identify all vectors from set F which are subject to satisfy constraints (1) and (2). These values would be the set of values leading to optimized values of the objective functions.
During the derivation of optimal solution of multi objective optimization, we don't get one optimized solution, instead we get a set of solutions with trade-offs in the objective functions. The commonly accepted term to deal with such optimality case is called Pareto Optimality.
One can define these Pareto Optimal solutions as a vector of decision variables if there is no another such that for all i=1,2,……….,n and for at least one j.
The above mathematical formulation gives a set of solutions called Pareto Optimal Solutions. These solutions are also called non-dominated solutions.
These Pareto Optimal Solutions in terms of objective functions are called Pareto Front. As discussed in [8], let be a multi-objective problem and it has Pareto Optimal Set , then Pareto Front would be determined by
As far as, the integration of EAs for solving the multi objective optimization problems is concerned, several EMO algorithms have been developed which are commonly applicable in the design of accurate and interpretable fuzzy systems.
Population based search procedure is the major strength of Evolutionary Algorithms (EAs) and it makes us capable to get multiple solutions a single run. EAs are perfect with very large and complicated search spaces and highly applicable in multiobjective optimization problems. Various kinds of evolutionary approaches, including genetic algorithms [4], genetic programming [5] and evolutionary strategies [6] are used to solve multiobjective optimization problem, leading to new research area, called Evolutionary Multi-objective Optimization [8-11].
Various EAs have been developed for the purpose of multiobjective optimization. In the first phase of development, the algorithms are NSGA (Non-dominated Sorting Genetic Algorithm) [12], NPGA (Niched Pareto Genetic Algorithm) [13], Multi-Objective Genetic Algorithm (MOGA) [14]. The major focus was on fitness sharing and niching integrated with Pareto Ranking. The algorithms in the second phase includes following EMO algorithms, Strength Pareto Evolutionary Approaches (SPEA) [15], SPEA2 [16], PAES [17], NSGA-II [18], NPGA-II [19], PESA [20] and Micro Genetic Algorithm [21, 22].
Evolutioary Multiobjective Optimiztion In Routing
QoS Based Approaches
Various modern network applications like e-mail, VoIP, teleconferencing are having various parameters like bandwidth, jitter, delay, reliability which are considered as Quality of Service(QoS) parameters.
A priority based evolutionary multi-objective optimization has been presented in [23] for estimating the optimized routes for data transfer. Different QoS parameters have been optimized for establishing the whole system.
In [24] three QoS constraints multicast routing algorithms have been developed. The first algorithm is NSGA based and second algorithm is NSGA II based. While in third algorithm the epsiv-dominance based NSGA-II algorithm has been utilized. The objectives in the proposed algorithms are: total cost of multicast route, mean delay between source to each destination and maximum delay in between source to destination node. The third approach has shown better solutions.
A multi objective genetic algorithm has been developed in [25] for multicast routing which satisfies QoS requirement in terms of delay and cost. This approach has been used for multicast tree topology reconstructions and the results have been found satisfactory in terms of search success ratio and computation time.
As multicast routing is NP complete problem but in [26] it has been represented as multi-objective combinatorial optimization problem. This approach is based on Discrete Particle Swarm Optimization approach named as QoS-MRP. It satisfies many QoS parameters.
A QoS routing optimization problem has been solved by a Hybrid Genetic Algorithm (HGA) in [27]. This algorithm has been developed using Genetic Algorithm (GA) and Ant Colony Optimization (ACO). GA has been used for global search and initial population generation where as ACO has been utilized for improving the quality and robustness of solution.
A QoS based routing approach has been discussed in [28] for Wireless Mesh Networks (WMN). Various QoS parameters considered are bandwidth, packet loss rates, and delay and power consumption.
A NSGA II based approach has been developed in [29] for energy efficient QoS routing in a cluster based wireless sensor network. The major focus is on the battery constraints for guarantying QoS in terms of end to end delay and reliability.
A Multi Objective Genetic Algorithm (MOGA) based approach for multicast routing has been developed in [30] named as QoS based mobile multicast routing protocol (QM2RP). This approach is responsible for determining near optimal routes on demand. Various QoS parameters like end to end delay, bandwidth requirements; residual bandwidth utilization has been utilized in this approach.
In [31] the QoS routing problem in optical fiber network has been discussed and solved by using genetic algorithm specifically titled as Optimal Maintain Operator Genetic Algorithm (OMOGA).
A Constraint-Cost-Bandwidth-Delay Genetic Algorithm (CCBD-GA) has been developed in [32]. This approach has been developed for multi- layered hybrid platform including high-altitude platforms and satellite platform. Several QoS constraints have been handled in this approach.
An Ant Colony Optimization based routing algorithm has been proposed in [33] for wireless mesh networks. It also handles QoS parameters. Whole approach is developed over Bi- level programming framework.
An Ant Colony Optimization based QoS routing algorithm for multimedia sensor networks has been developed in [34] which satisfies both energy- efficiency and QoS assurance.
In [35] an approach has been developed for multicast routing which is bandwidth- delay- constraint. This is based on Genetic Algorithm.
A GA based multi objective has been developed in [36] for QoS based routing and wavelength allocation problem.
Sensor Networks
Mobile Agents are used for data fusion in the sensor nodes. The routes followed by these mobile agents determine the cost and quality of data.
In [37] mobile agent routing problem is solved using multiobjective evolutionary algorithms like EMOCA and NSGA II optimizing the total detected energy signal, energy consumption and path loss.
Evolutionary multiobjective crowding algorithm (EMOCA) is used for mobile agent routing problem as in [38] so as to maximize the total detected energy signal and minimize the energy consumption and path loss. EMOCA shows better results as compared to combinatorial optimization.
Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) is proposed in [39] for mobile agent routing problem in distributed sensor networks. This approach is developed to minimize the path loss and energy consumption and to maximize the data accuracy.
Optimization of energy consumption is an important issue in wireless sensor networks. In [40], SPEA II and NSGA II are used to minimize the energy consumption along with optimization of other parameters such as area covered, average number of hops and network reliability. Results show SPEA II having better performance.
Simple Hybrid Routing Protocol (SHRP) is used in wireless sensor networks for finding the route towards sink node. In [41] an approach named dynamic multiobjective routing algorithm (DyMORA) is developed to increase the performance of SHRP in terms of time convergence and reliability.
To ensure QoS in wireless sensor networks, an approach based on evolutionary algorithms is proposed in [42]. This approach is used to solve the Density Control, Coverage and Routing Multi-Period problem(DCCRMP) giving better results as compared to Integer linear program model and GRASP heuristic.
Lifetime of the wireless sensor network can be increased by using the approach as proposed in [43]. This approach is named as hop-number-constrained multi-hop routing algorithm (HRM) in which energy consumption is balanced by making the higher residual energy nodes to relay more information. Maximum hop number is used as a constraint.
QoS requirements depend on the type of services offered. To ensure QoS routing in multimedia sensor networks, an approach named ant-based service aware routing (ASAR) is proposed in [44]. This model helps in choosing the best optimal solution depending on the specific QoS requirements and thus maximizes the network utilization and network performance.
Energy consumption and network lifetime are important parameters while designing a wireless sensor network (WSN). An evolutionary algorithm based approach is proposed in [45] to optimize the network stability time, network lifetime and energy consumption. This approach shows better results as compared to other competitors such as LEACH, SEP and HCR.
Many algorithms are used for wireless sensor networks such as; LEACH, which is better in terms of energy consumption and HCR gives increased lifetime. A new approach for Evolutionary based clustering Routing Problem (ERP) is proposed in [46]. This approach uses a new fitness function considering the cohesion and separation error aspects. ERP provides prolonged lifetime, prolonged stability period and reduced energy consumptions for heterogeneous WSNs.
Multicast Routing
Multicast routing is required when there is simultaneous communication between more than two users. Multicast routing is an NP complete problem.
Evolutionary algorithm based multicast routing approach is proposed in [47]. This approach minimizes the routing cost with end to end delay constraints.
Multicast routing problem has been solved using multiobjective evolutionary algorithm in [48]. In this approach 'elite library' is used, and hence approach is named as E-MOEA. A new mutation operator is used which shows improved performance.
For routing purpose in multicast overlay networks, NSGA II has been utilized as in [49] for optimizing two major objectives namely total end to end delay of multicast tree and maximum link utilization.
Generalized multiobjective multitree model (GMM-model) can be extended for dynamic multicast groups named as dynamic-GMM-model, for adding the new egress nodes. A new heuristic named Multiobjective Approximation using Shortest Path Algorithm (MASPA) is proposed in [50] to solve this model.
A quantum inspired EA has been developed for multicast routing in [51]. The individuals in the solution population are represented by multi-gene quantum bits. For enhancing the convergence property, quantum rotation gate strategy has been developed.
Multiobjective multicast routing problem (MMRP) is an NP-Complete problem. Two heuristics are proposed in [52] to be used for crossover and mutation operators of MOEAs to solve MMRP with given QoS objectives and constraints.
Based on MOEAs (SPEA and SPEA II) three heuristics are proposed in [53] for subtree reconnection for multicast flow routing. The first heuristic is based on shortest path algorithm, second is based on random search and the third combines the above two heuristics. These heuristics are used to optimize QoS parameters such as: maximum link utilization, total cost, maximum end to end delay and hops count with constraint link capacity. Results show that third heuristic is better in terms of convergence and diversity.
To improve the solution to multicast flow routing problem new model is proposed in [54] based on SPEA II and NSGA II. Shuffling strategies are proposed for Neighborhood Crossover (NC) showing better convergence.
To have a minimum cost, multicast tree routing with bounded end to end delay and link bandwidth, a heuristic genetic algorithm is proposed as in [55].
A Particle Swarm Optimization (PSO) based approach is proposed in [56] for multicast routing to optimize cost with delay and bandwidth constraints.
A GA based approach for multicast routing at application layer is proposed in [57] named ALMR-GA. This approach optimizes the cost with constraint load balancing at network and application layers.
An approach for multicast routing in multi domain configuration is discussed in [58]. A set of heuristic algorithms are proposed to solve the routing problem which gives better performance as compared to conventional methods.
An approach named Genetic Algorithm for Delay and Delay Variation Multicast Routing (GADVM) is proposed in [59]. This approach provides QoS routing in terms of end to end delay constraint and constrained delay variations along with the path from source to every destination.
Other issues
Cognitive Packet Network (CPN) protocol is used for QoS routing in Ad-hoc networks. An approach to combine CPN with GA is proposed in [60] to get new possible routes with QoS parameters.
For O-OFDM Networks an efficient two population genetic algorithm (MPGA) is proposed in [61] which allow migration of individuals among two differently evolved populations and results in efficient results.
An approach to shortest path routing problem is proposed in [62] Problem is represented by variable length chromosomes and genes. A repair function is used for infeasible chromosomes. The approach gives better convergence and diversity. Also proposed algorithm uses Gambler ruin model for sizing the population.
An NSGA based approach for shortest path routing problem is proposed in [63]. This approach uses priority based encoding for population initialization and elitism to ensure quality of solution in newer generations.
Shortest Path routing problem for MANETs is dynamic in nature. An approach is proposed in [64] wherein Genetic algorithms with immigrants and memory schemes for easy adaptation of topology changes are incorporated to solve the problem.
Anycast routing is when message is to be sent to only one member of destination group. A GA based approach for anycast routing in Delay/Disruption Tolerant Networks (DTNs) is proposed in [65] which gives reduced delay for specific delivery requirements.
Genetic algorithms can be used for WDM networks to optimize cost, link capacity, blocking probability and wavelength as proposed in [66]
OSLR protocol is used for mobile ad-hoc networks. This can be combined with multi objective approach as in [67]. Routing metrics used are mean queuing delay and energy cost for each node and link stability of each link. Objectives optimized in this approach are: minimization of average end to end delay, maximization of network energy lifetime and packet delivery ratio.
Research Issues and Challanges
Several research issues are still open problem in this area. Some of these are outlined here,
Development of theoretical framework and run time analysis of MOEA for computer network applications
Integration of preferences in MOEA to apply limits on the search for better performance
Development of MOEA for handling dynamic test functions in objective functions defined for networking applications
Development of theoretical framework and analysis of parallel MOEA in computer network
Development of new techniques for proving the convergence and diversity issues in the parallel EMO for computer network
Development of more generic objective functions for optimization in computer network applications
Conclusion
Evolutionary Multiobjective Optimization algorithms are well suited for the routing problem in a computer network which efficiently utilizes the network resources in routing problems. This paper is an attempt to review the work carried out in this area. Also, different burning research issues in this area are outlined.
