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.

Tree-Based Genetic Algorithm with Binary Encoding for QoS Routing

MANISCALCO, VINCENZO;GRECO POLITO, SILVANA;
2013

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.
9780769549743
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11387/36126
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact