Short algorithm description
AntHocNet is an adaptive routing algorithm for mobile ad hoc networks (MANETs) inspired by ideas from Ant Colony Optimization (ACO). In common MANET terminology, AntHocNet could be called a hybrid algorithm, as it combines both reactive and proactive routing strategies. Specifically, the algorithm is reactive in the sense that it does not try to maintain up-to-date routing information between all the nodes in the network, but instead concentrates its efforts on the pairs of nodes between which communication sessions are taking place. It is proactive in the sense that for those ongoing communication sessions, it continuously tries to maintain and improve existing routing information.
To gather routing information, the AntHocNet algorithm uses two complementary processes. One is the repetitive end-to-end path sampling using artificial ant agents. The other is what we call pheromone diffusion, an information bootstrapping process that allows to spread routing information over the network in an efficient way. While the ant-based path sampling is the typical mode of operation of ACO routing algorithms, the pheromone diffusion process is in its working more similar to Bellman-Ford routing algorithms. AntHocNet combines both processes in order to obtain an information gathering process that is at the same time efficient, adaptive and robust. The way path sampling and information bootstrapping are combined here is very different from other combinations of these approaches to learning that exist in the reinforcement learning literature and is specifically targetted at working highly dynamic non-stationary environments.
A detailed description of the AntHocNet routing algorithm can be found in chapter 4 of my Phd thesis.
The following link contains a zipped directory with code for the use of AntHocNet in the Qualnet 4.0 network simulator. The README.txt file inside explains how to use the code.
Other implementations (not checked by us):
A general introduction to the use of swarm intelligence for routing in telecommunication networks:
References related to the AntHocNet routing algorithm.
My PhD thesis contains the most complete description of the latest version of AntHocNet. It is recommended to follow this description, as some of the versions published earlier are substantially different. It is possible to download the chapters with the algorithm description and the algorithm evaluation separately.
This was the first publication of AntHocNet. It is quite different from the version described in the thesis, and has less good performance.
This is a journal publication of that older version of AntHocNet.
This is a newer version of AntHocNet, closer to the final version described in the thesis.
This is an analysis of the internal working of the algorithm.
Di Caro G., Ducatelle F. and Gambardella L. M. (2008). A simulation study of routing performance in realistic urban scenarios for MANETs. Proceedings of the sixth International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS2008), Brussels, Belgium, September 2008.
Here, we compare AntHocNet to AODV in a detailed simulation of an urban scenario.
Here we present some videos that illustrate the working of the AntHocNet routing algorithm. In particular, they show how AntHocNet builds routes and tries to maintain, extend and improve them while a communication session is going on.
The first video shows AntHocNet at work in an open space scenario. 100 nodes move in a rectangular area of 1500 by 1000 meters with no obstacles. Radio signal propagation is simulated with the two-ray model. The IEEE 802.11 protocol is used at the physical layer and the MAC layer, and the UDP protocol is used at the transport layer. 20 different communication sessions run in parallel between randomly chosen start and destination nodes. The video shows the routing of one of the communication sessions. The route followed by data packets is indicated by blue lines. Lines of other colors are used to show alternative paths found by the routing algorithm, each with their relative quality (green, orange and red for low, intermediate and high quality). The colors of the different nodes in the network indicate how busy the radio channel is around them (again, green, orange and red are used). Finally, at the bottom three different graphs show the performance in terms of end-to-end delay, throughput and delay jitter for AntHocNet (in red) and AODV (in blue) in this scenario.
Video 1: AntHocNet at work in an open space scenario
The second video shows AntHocNet at work in an urban scenario. The setting is an area of 1000 by 1500 meters in the center of the Swiss town of Lugano. 500 nodes move along the streets of the town according to an adapted form of random waypoint mobility. Radio signal propagation is modeled using a raytracing approach. Other details are similar as in the previous video.
Video 2: AntHocNet at work in an urban scenario
Links and contacts