Tree-Based Genetic Algorithm with Binary Encoding for QoS Routing
Authors:
- Vincenzo ManiscalcoVMVincenzo Maniscalco
- Silvana Greco PolitoSPSilvana Greco Polito
- Antonio IntagliataAIAntonio Intagliata
- 1 July 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 101-107
Abstract
Mobile ad Hoc Networks (MANETs) are one of the most important technologies supporting Ubiquitous and Pervasive Computing (UPC). As many UPC applications pose Quality of Service (QoS) constraints, their implementation in MANETs becomes dependent on the MANET algorithms for QoS routing. In this paper Genetic Algorithms (GAs) for QoS routing in MANETs are considered. GAs can solve the NP search of QoS routes with multiple constraints, and then address the UPC QoS requirements. The focus is on tree-based GAs, which represent the set of paths from source to destination as a tree and encode them through the crossed junctions. They encode single paths in the chromosome. We investigate on the effects of binary encoding schema on tree-based GAs. To this purpose we design a GA with binary encoding that maps classes of paths in single chromosomes. These classes are both collectively exhaustive and mutually exclusive. The GA with binary encoding uses an adaptive mutation probability for deeper exploration of the search space, and local search on classes of paths. Simulation results compare the GA with binary encoding with two applications of GAMAN, the main existing tree-based GA. They show that the binary encoding allows the GA to converge faster although it introduces additional computational costs.Keywords
This publication has 8 references indexed in Scilit:
- Application of GA and Multi-objective Optimization for QoS Routing in Ad-Hoc Networks2011
- Application of Genetic Algorithms for QoS Routing in Mobile Ad Hoc Networks: A Survey2010
- A Robust GA-based QoS Routing Algorithm for Solving Multi-constrained Path ProblemJournal of Computers, 2010
- Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc NetworksIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2009
- Effect of mobility on the performance of GA-based QoS routing in mobile ad hoc networks2007
- Impact of QoS Routing Metrics for MANETs in the Pervasive Computing Environment2007
- A QoS routing method for ad-hoc networks based on genetic algorithm2004
- A genetic algorithm for shortest path routing problem and the sizing of populationsIEEE Transactions on Evolutionary Computation, 2002