Binary and m-ary encoding in applications of tree-based genetic algorithms for QoS routing

摘要

Ubiquitous and Pervasive Computing (UPC) applications often have Quality of Service (QoS) requirements. These become constraints for the UPC network infrastructure. In this paper, we refer to Mobile ad Hoc Networks, one of the most important technologies supporting UPC, and investigate on Genetic Algorithms (GAs) for QoS routing. GAs are part of the soft computing paradigm and can solve the NP search of QoS routes with multiple constraints. We elaborate on tree-based GAs, which represent the set of paths from source to destination as a tree and encode them through the crossed junctions. While their most well-known applications use m-ary encoding representing single paths in the chromosomes, in this paper we discuss a binary encoding with the objective of improving the convergence speed. The binary encoding represents classes of paths in the chromosomes and allows local search on classes of paths. These classes are both collectively exhaustive and mutually exclusive. Simulation results compare convergence speed and scalability of GA applications with binary and m-ary encoding in networks with an increasing number of nodes and links per node. As the per-class processing is reason of additional computational cost, an hybrid GA application that uses both binary and m-ary encoding is introduced.