Immigrants-enhanced multi-population genetic algorithms for dynamic shortest path routing problems in mobile ad hoc networks

Abstract

One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time as a result of energy conservation or node mobility. Therefore, the shortest path (SP) routing problem turns out to be a dynamic optimization problem in mobile wireless networks. In this article, we propose to use multi-population genetic algorithms (GAs) with an immigrants scheme to solve the dynamic SP routing problem in mobile ad hoc networks, which are the representative of new generation wireless networks. Two types of multi-population GAs are investigated. One is the forking GA in which a parent population continuously searches for a new optimum and a number of child populations try to exploit previously detected promising areas. The other is the shifting-balance GA in which a core population is used to exploit the best solution found and a number of colony populations are responsible for exploring different areas in the solution space. Both multi-population GAs are enhanced by an immigrants scheme to handle the dynamic environments. In the construction of the dynamic network environments, two models are proposed and investigated. One is called the general dynamics model, in which the topologies are changed because the nodes are scheduled to sleep or wake up. The other is called the worst dynamics model, in which the topologies are altered because some links on the current best shortest path are removed. Extensive experiments are conducted based on these two models. The experimental results show that the proposed multi-population GAs with immigrants enhancement can quickly adapt to the environmental changes (i.e., the network topology changes) and produce high-quality solutions after each change.