Skip to main content

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
Labels:

Comments

Post a Comment

Popular posts from this blog

Link State Routing Protocol

Link state routing is a method in which each router shares its neighborhood’s knowledge with every other router on the internetwork. In this algorithm, each router in the network understands the network topology and then makes a routing table depending on this topology. Each router will share data about its connection to its neighbor, who will, consecutively, reproduce the data to its neighbors, etc. This appears just before all routers have constructed a topology of the network. In LSP, each node transmits its IP address and the MAC to its neighbor with its signature. Neighbors determine the signature and maintain a record of the combining IP address and the MAC. The Neighbor Lookup Protocol (NLP) of LSP derives and maintains the MAC and IP address of every network frame accepted by a node. The extracted data can support the mapping of MACs and IP addresses. The link-state flooding algorithm prevents the general issues of broadcast in the existence of loops by having every node mainta...
Post a Comment
Read more

Matter: A next generation home standard

The smart home is evolving. To date, if you've wanted to get into developing a smart home, you've had to deal with the multitude of smart home ecosystems, and making sure that each device you buy is compatible. That, however, may soon change — thanks to new smart home standard called Matter. Matter isn't available just yet, but when it is finally released, it could completely change how you buy smart home products, for the better. All of the best smart home devices could soon support the standard, helping them all work together nicely, and ensuring that no matter what products you buy, you'll be able to use them. Matter is basically the name of a new smart home connectivity standard . But this standard is a little unlike others. That's because of the fact that it's being developed by the Connectivity Standards Alliance, which counts hundreds of companies as members. That includes the likes of Google, Alexa, and Apple. So, whether you prefer to use Google Assista...
1 comment
Read more

HP NETWORK SIMULATOR: A COMWARE OS LEARNING TOOL

  Comware v7 is a network operating system that runs on HP high-end network devices. The HP Network Simulator is an ideal Comware v7 learning tool, which allows users to create, configure, and connect simulated networks. Benefits Beginners  – The HP Network Simulator tool is helpful for users who are new to networking and want to learn how to configure network devices (switches, routers), various topologies, or different routing and switching protocols and features. Experienced users  – The HP Network Simulator learning tool is helpful for users who have experience with non-HP networking devices and want to learn the Comware CLI and features. Extra devices  – Users can create devices using the HP Network Simulator and use them with their physical devices to configure and test topologies that aren’t configurable with just the physical devices they have. For example – A user wants to configure OSPF using 3 or more devices but has only 1 physical router. User can create...
Post a Comment
Read more