View article

In this report, we describe the application of Ant Colony Optimization (ACO)[14, 15] to a dynamic on-line optimization problem, namely routing in mobile ad hoc networks in urban environments. Routing is the task of finding and using paths to direct data flows through a network while optimizing one or more performance measures. This often comes down to a problem of finding minimum cost paths between pairs of source and destination nodes in the network. Hence, the problem of routing maps rather well to the solution model most commonly used in ACO, which is inspired by the ability of certain types of ants in nature to find the shortest path between their nest and a food source through a distributed process based on stigmergic communication [7]. An important aspect of routing, which sets it apart from many other applications of ACO, is that it is typically a distributed and dynamic problem, which means that the description of the problem changes over time and decentralized solutions must be adopted. This is because the situation in the network changes, eg because the traffic process at the nodes varies, or because there are link or node failures. As a consequence, the optimization algorithm for routing needs to adapt continuously. Here, we focus on routing in a specific type of communication networks, namely mobile ad hoc networks (MANETs)[31]. These are networks that consist entirely of wireless nodes, placed together an ad hoc manner (ie, on-the-fly, or with minimal prior planning) and without the support of a fixed communication infrastructure. All nodes are mobile, and can enter or leave the network at any time. Data are forwarded among …