NS2 MODULE FOR ANT COLONY OPTIMIZATION

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis,the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants.

In the natural world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food.

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over more frequently, and thus the pheromone density becomes higher on shorter paths than longer ones. Pheromone evaporation also has the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.

Thus, when one ant finds a good (i.e., short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads to all the ants' following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the graph representing the problem to solve.

This post contains extensions to NS-2 (versions 2.27 and 2.28) which enables the ACO behavior in WSNs. The module is adaptable to the current version of NS-2 since it is installed as a new routing protocol. Written mainly in C++ the ACO module (AntSense) produces the main attributes, however it was design in order to be used by any other technology supported by this simulator.

When designing a routing protocol for WSNs it is important to consider the packet length of each type of packets used by our protocol, since, as already explained communication is an energy-expensive function. In AntSense development, several approaches were used concerning types of packets and different lengths, the configuration illustrated in this section refers to the best pattern found by the results. In ACO approach ants are considered as packets that travel the network changing routing information in order to find the best path towards the anthill, in this case towards the sink-node. The ant packet structure is composed by:

1. pkt_src: the node that originated the ant packet;
2. antpath[3]: the three previous nodes visited by the ant;
3. energy: the average energy per path;
4. pheromone: the pheromone level that should be dropped by the return ant;
5. toSinkNode: a boolean variable that informs if the ant is a forward or a return ant;

All the nodes that belong to the ant path are responsible to update the packet with the proper data, and should update also their internal information regarding the neighbor devices and pheromone levels always taking in consideration the direction of the s ant packet. As a normal protocol AntSense also requires a Hello type packets, in order for the nodes know which are the sensor nodes that are contactable with only one hop. The following structure were used in the hello packet:

1. rp_src: the node that originated the hello packet;
2. node_energy: the energy of the source node;

ANT Structure

It is important to emphasize that the node energy of the source is also exchange, this procedure allows a to increase the update rate in order to help ants to decide the best route based in available energy.

The AntSense file structure is divided in three different files (Figure): antsense.cc, queue.cc, and table.cc. The first one is the main file, where the routing protocol is written, functions like ant receive and ant forwards are describe here. This main file requires the functions described in the last two files, it uses the queue.cc to manage the data packet queuing, and table.cc to decide the best neighbor device to forward ant packets and data packets.

All the main and “hard” equations are described in the table.cc, where a routing table is kept and updated every time a ant packet is received.

The AntSense model in a first phase was build to behave as a normal ACO approach, however as the integration in WSNs was being designed the final solution reflects several aspects of the WSN integration, i.e. reduce the ant memory to three slots, which allows us to reduce communication time.

For Script, Click here

For More, Click here