Improvements to Tree-based GA Applications for QoS Routing

Genetic Algorithms (GAs) are emerging as a promis- ing instrument for quality of service (QoS) routing in Mobile Ad hoc Networks (MANETs). They implement an iterative process that can solve the NP search problem of routing with multiple QoS constraints. In each iteration new solutions are found through the mutation and crossover genetic operations. In this paper we focus on an existing GA tree-based application for QoS routing in MANETs which applies the genetic operations on a tree built from the network topology and uses fixed length chromosomes. The chromosome encodes junctions tree crossed by routes. This application suffers in convergence speed because its mutation operator does not allow deep exploration of the search space. The inefficiency of the adopted mutation operation is more evident in networks with big size and high network connectivity, i.e., networks with a larger search space. In this paper, we elaborate on the tree-based application with the main objective of improving its performance. We first introduce a criterion for junctions tree sorting based on their distance from the root. Later, we use chromosome properties due to the sorting criterion to design a sequential mutation technique with adaptive probability that allows faster convergence. We provide simulation results showing the effectiveness of the proposed enhancements while increasing the MANET size and connectivity.