Archive for October 2010
I’ve been considering to write about this topic for some time. After discussing about it with @jcordovag one day, my curiosity towards these swarm-based ad-hoc routing protocols grew up as I digged deeper for more information.
Although Swarm Intelligence isn’t really a new concept, it has been used more frequently in MANETs (research) in the past few years. The idea of using animal behavior to deal with network routing sounds great, but results could be even more impressive in terms of saving node power, reducing jitter and updating the topology, in some cases, even more proficiently than other state-of-art routing protocols, such as SDR, AODV, etc.
Ant Colony Optimization (ACO)
ACO (1992) is basically an algorithm that initially aimed to search for an optimal path in a graph, based on a behavior of ants seeking a path between their colony and a source of food. In the last few years, it has been taken into consideration for developing MANET routing protocols. Some of their best examples are: ARA, AntHocNet and ARMA.
The main idea behid ACO
The routing protocols might differ on some small details, but they all follow on one single idea: emulating the behavior of ants.
In order to collect food, ants set trails of pheromones that other ants will follow. Initially, they spread in all directions. When an ant finds a food source, it collects the food and sets a trail on its way back. The pheromones slowly disappear over time, so the shortest path will be the one with the highest pheromone scent, ie. the path with the highest concentration of ants. When a previously short route gets blocked/lengthened due to an obstacle en route, the alternate short route get strengthened with higher pheromone content due to shorter end-to-end travel time and more ants move to this route. Hence the path can also dynamically adapt to fast changes in the environment.
Ant Colony Optimization for MANETs, Figure taken from this paper.
The Ant-based Ad-Hoc routing algorithm is an on-demand reactive algorithm similar to DSR/AODV, but it has been built to address the challenges experimented in MANETs. Details of how the algorithm works varies between each solution. I strongly recommend reading this paper about a generic perspective of how Ant Colony Optimization could be used to solving MANETs routing issues. Again, although they differ on details, they pretty much define similiar ways of route discovery and route maintenance.
I guess this would be it for this post! I’m willing to try them on a simulation enviroment. I’ll post more about it later!. In the meanwhile, keep reading about the topic!