A Memetic Algorithm for Dynamic Shortest Path Routing on Mobile Ad-hoc Networks

摘要

The shortest path routing (SPR) problem is a well-known challenge in the field of mobile network routing. The aim is to find the least cost path that connect a specific source node with a specific destination node. Although there are numerous algorithms to solve SPR, most of them consider only static environments in which the network topology and link-cost never change. A network with dynamic topologies and cost are indeed more challenging but more practical in real world applications. This paper presents a memetic algorithm for dynamic SPR (DSPR) problems in a mobile network. The proposed approach consists of three stages: genetic algorithm, local search and elitism-based immigrants procedure. Genetic algorithm (GA) is applied in the first stage to explore the search space and generate a new set of solutions. The generated solutions are further improved in the second stage by a local search algorithm. In third stage, an elitism-based immigrants procedure is activated to handle the dynamic changes by maintaining the diversity of the search process. The performance of the proposed algorithm has been evaluated on dynamic shortest path routing problem instances under both cyclic and acyclic environments. The study shows that, on both circumstances, the proposed algorithm is very stable with regards to dynamic network changes. This method is highly competitive compared to state-of-the-art algorithms in the literature as it outperformed these algorithms on all instances of dynamic routing during evaluation.