An ant colony optimization routing based on robustness for ad hoc networks with GPSs

Ant colony optimization (ACO) routing algorithm is one of adaptive and efficient routing algorithms for mobile ad hoc networks (MANETs). In ACO routing algorithms, ant-like agents traverse the network to search a path from a source to a destination, and lay down pheromone on the path. A data packet is transferred along a path selected with probability based on the amount of pheromone. The amount of pheromone laid down on a path depends on its quality, such as its number of hops and communication delay. However, in MANETs, continuous movement of nodes causes dynamic network change with time. Thus, even if a path with a small number of hops and short communication delay has much pheromone, it may become unavailable quickly due to link disconnections. Therefore, we focus on robustness of paths to construct paths that are not likely to be disconnected during a long period. In this paper, we propose a new ACID routing algorithm based on robustness of paths for MANETs with global positioning system (GPS): each ant-like agent evaluates robustness of a path using GPS information of visited nodes and decides the amount of pheromone to lay down based on the robustness. Moreover, in our algorithm, each node predicts link disconnections from neighbors' GPS information in order to adapt to dynamic network change. To keep paths available, when a node predicts a link disconnection, it redistributes the pheromone on the link to be disconnected so that construction of alternative paths can be accelerated. Simulation results show that our algorithm achieves higher packet delivery ratio with lower communication cost than AntHocNet and LAR. (C) 2009 Elsevier B.V. All rights reserved.