Received Date: February 10, 2017; Accepted Date: March 02, 2017; Published Date: March 15, 2017
Citation: Batth KK, Singh R (2017) Performance Evaluation of Ant Colony Optimization Based Routing Algorithms for Mobile Ad Hoc Networks. Int J Adv Technol 8:181. doi:10.4172/0976-4860.1000181
Copyright: © 2017 Khushneet, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License; which permits unrestricted use; distribution; and reproduction in any medium; provided the original author and source are credited.
Visit for more related articles at International Journal of Advancements in Technology
Mobile Ad Hoc Network is a collection of autonomous mobile nodes that communicate with each other over wireless links without any fixed infrastructure. The nodes use the service of other nodes in the network to transmit packets to destinations that are out of their range. Such networks are expected to play increasingly important role in future organizations, University, Civilian and Military settings, being useful for providing communication support where no fixed infrastructure exists. Also, in case of disaster or natural calamities, the deployment of a fixed infrastructure is neither feasible nor economically profitable for establishing communication among the rescue members. In order to accomplish this, a number of routing protocols are being proposed by researchers. Ants based routing is gaining more popularity because of its adaptive and dynamic nature. A number of Swarm Intelligence (SI) based, more specially Ant Colony Optimization (ACO) based routing algorithms are proposed by researchers. Each one is based on different characteristics and properties. In this paper, we take up three ACO based algorithms and simulate the proposed algorithms using NS-2 and compare the performance matrices as Packet Delivery Fraction (PDF), throughput and routing overhead for varying simulation time.
Ant colony optimization; Mobile Ad Hoc networks; Packet delivery fraction; Throughput
Swarm intelligence (SI) based, more specially Ant Colony Optimization (ACO) [1-15] based routing algorithms are novel evolutionary algorithms, which have the characteristics such as positive feedback, negative feedback, distributing computing, stigmergy etc. Swarm Intelligence based techniques like ACO and PSO are inspired from real biological insects like ants, bees, bats, elephants, birds to and is being applied be researchers to solve complex engineering problems. They possess following characteristics:
The population changes by local and distributed agent interactions. Fault tolerance - There is no centralized control for the agents, so they are able to sustain even in case of small failure in the links.
The agents change, reproduce or die as per requirement in the colony. Speed - The agents communicate very fast through pheromone and others follow. Modularity - Agents act independently.
No supervision is needed because each agent follow simple rule.
Agents perform the operations parallelly.
Mobile Ad Hoc Networks (MANETs) are built up of a collection of mobile nodes which have no fixed infrastructure. The nodes communicate through wireless network and there is no central control for the nodes in the network. Routing is the task of directing data packets from a source node i.e., transmitter to a given destination node i.e., receiver. The surrounding physical environment significantly attenuates and distorts the radio transmissions since signal quality degrades with distance. Hence, it may be needed for one mobile node to take the assistance of other nodes in forwarding its packets to the desired destination. A node can move anytime in an ad hoc scenario and, as a result, such a network needs to have routing protocols which can adapt dynamically changing wireless topology. However, since there is no fixed infrastructure in a network, each mobile node operates not only as a node but also as a router, forwarding packets from one node for other mobile nodes in the network, that may not be within direct wireless transmission range of each other [8,9,15]. It is very challenging for the researchers and engineers to develop and implement a routing algorithm to accomplish the task of routing in changing topology of Mobile Ad Hoc Networks.
Further, in this research paper, Section 2 comprises of review of ACO based routing algorithms for MANETs. In Section 3, we discuss experimental setup used for evaluation of performance matrices. In Section IV, we present the performance matrices and result analysis of ANTALG, Ant Chain and IACR algorithms, and Section V is presented with Conclusion.
Ad hoc Networking with Swarm Intelligence (ANSI) is a reactive algorithm which finds out path only when demanded that is, when node has data to send to other nodes it finds out the path . The Multicast for Ad hoc Network with Swarm Intelligence (MANSI) protocol provides multicast support for Ad hoc Networks. Within a multicast group, each member launches a forward ant in order to find an existing forwarding node where it can be used to establish connectivity to the group with lower cost . The Multicast for Ad hoc Network with hybrid Swarm Intelligence (MANHSI) utilizes small control packets equivalent to ants in the physical world. These packets, traveling like biological ants, deposit control information at nodes they visit similar to the way ants laying pheromone trails on the path . Ants Hybrid Routing (ACO-AHR) Hybrid routing algorithm . It introduces the service agents to reduce expense of network. It uses two artificial ant agents that is, forward ant agent which travels from source to destination and find out information about quality of the path. Backward ant agent travels from destination to source and collect information about pheromone deposited. There are other types of agent that is called service agent (sagent). Improved Ant Colony Optimization algorithm for mobile ad hoc network (PACONET) is a reactive algorithm. It is a very dynamic algorithm which takes into account the mobility, route maintenance, Link Failure-Handling . Position based on Ant colony routing algorithm for MANETS. (POSANT) is reactive that is, route is established only when there are some data to send. It is position based routing means each node has information about its own position, position of its neighbors, position of destination node . Also, Swarm Intelligence: An emerging solution for Quality of Service (QoS) provisioning in Mobile Ad Hoc Networks is described in Singh et al. . Probabilistic Ant Routing (PAR) is proposed for routing in MANET . Each node maintains a list of neighbors according to HELLO MESSAGE received. Forward ant agents (FANT) are probabilistic and explore the network to collect network traffic information. They are routed on normal priority queue. If route to destination is available as present node, the FANT is unicast otherwise it is broadcasted. Saleem et al. in their paper Swarm Intelligence based routing protocol for wireless sensor networks: Survey and future directions , state extensive review of area of Swarm Intelligence especially with regard to Ant Colony Routing and Bee-Inspired routing protocols with regard to SI in WSN along with analysis of various issues surrounding SI based routing protocols and future directions to overcome these issues. Fatih et al. in research paper - A survey on swarm intelligence based routing protocols in wireless sensor networks , mention various issues with regard to complexity, scalability and adaptability issues and comprehensive review of routing protocols being proposed to solve these issues. Babu et al. in the research paper titled, Swarm Intelligence based Energy Efficient Routing Protocol for Wireless Ad-hoc Networks , define various energy efficient routing protocols based on Swarm Intelligence network and propose Ant Colony Optimization meta heuristic to overcome routing issues and proposes Energy Efficient Ant Based Routing Protocol for finding optimal paths between sender and sink nodes. Zungeru et al. in their paper - Classical and swarm intelligence based routing protocols: A survey and comparison , mention comprehensive review of classical to swarm intelligence based routing protocols based on complexity, structure and energy efficiency along with a proper comparison of protocols cum simulation of these protocols on MATLAB based Simulator for determining performance metrics. Chandra Mohan B, and R Baskaran in a paper titled - A survey: Ant Colony Optimization based recent research and implementation on several engineering domain , present review of various research and implementations of ACO and proposed a modified ACO model which overcomes various routing issues as compared to other traditional ACO algorithms. Shtovba and SD in paper - Ant algorithms: theory and applications , explain theory and applications of ant algorithms and various new methods of discrete optimization on the simulation of self-organized colony of biologic ants; travelling salesman problem on basis of combinatorial optimization and various methods for improvising ant algorithms. Al Salami and Nada MA in their paper, Ant colony optimization algorithm  propose hybrid algorithm for solving various combinatorial optimization problem via usage of ant colony and genetic programming and to propose various effective solutions for organized networks.
Dorigo et al. in paper, Ant colony optimization,  describe in detail the concept of ACO along with its variants, various theoretical results survey along with various other research issues. Yan et al. in research paper - Ant colony optimization for wireless sensor networks routing  state heuristic way for reducing energy consumption in routing and highlights three ACO Algorithms: Ant System, Ant Colony System and Improved AS and doing comparison among three via simulation to highlight reduction in energy consumption.
Dorigo et al. in research paper, Ant colony optimization theory: A survey  describe in detail concept of ACO along with relations between ACO optimization algorithms and other approximation methods.
Monteiro et al. in research paper, Ant Colony Optimization: a literature survey , define ACO along with its various algorithms to determine the behavior of natural ants.
Rault et al. in research paper, Energy efficiency in wireless sensor networks: A top-down survey , highlight in detail the issue of energy efficiency in WSN along with survey of various energy conservation schemes to enhance network lifetime.
Ali et al. in research paper, Analysis of Routing Protocols in AD HOC and Sensor Wireless Networks Based on Swarm Intelligence , mention critical analysis of comparison of routing protocols of AdHoc and Swarm Intelligence in terms of routing overhead, route optimality and energy consumption. Okdem et al. in research paper, Routing in wireless sensor networks using ant colony optimization , define a new routing scheme and adapted ant colony optimization (ACO) algorithm and results are tested via Proteus Simulation Program. Kannan et al. proposed MAARA (Multiagent Ant Based Routing Algorithm)  which is a hybrid algorithm that combines ant algorithm and multi agent systems. The algorithm is simulated over ns 2 and the results are better than AODV, DSR, ANTHOCNET, in terms of delay, packet delivery ratio, more connectivity, and less packet loss. Sehi and Siba KU, ”Efficient ant routing protocol for MANET proposed an ANT-E : Efficient Ant Routing Protocol . The paper shows a protocol which is reactive and multipath routing that combines blocking expanding ring search (blocking ERS) with ACO. The protocol can be simulated with NS2. It out performs AODV and DSR in terms of packet delivery ratio, reliability, overheads, end to end delay etc. There are three types of overheads in the protocols, Data packets, control packets (FANT and BANT) and neighbor control packets (broadcast hello messages). Also birth and arrival time is measured.
The algorithm has following phases
Route discovery phase: The phase is to create new paths. The source can disseminate Forward ant with destination node address, next hop and pheromone value, to its one hop neighbors. The neighbors forward FANTS to their neighbors until a route is found by blocking ERS. Otherwise source is informed by reply message. Duplicate FANTS are discarded because of unique sequence number, loops are avoided by buffering route requests, duplicate packets are discarded based on sequence number and source address. When ant reaches at destination backward ant is created to retrace the path in backward direction.
The second phase is route maintenance phase: Established paths do not maintain same pheromone value. When a data packet is relayed on path, it increases pheromone on path by 1 unit and strengthen the paths. The pheromone exploration takes place side by side.
The next is route failure handling: If the node gets a route error message (rerr) for a certain link, it deactivates the link by setting the pheromone value to 0. The node searches for alternate link if packet does not reach the destination then source initiates a new routs discovery phase. The unsuccessful packets are retransmitted by intermediate nodes when they receive NACK from receiver node.
Ashima et al. in the research paper  discussed ant based routing protocol to optimize the route discovery and maximize the efficiency of routing in terms of packet delivery ratio (PDR) using the blocking expanding ring search (Blocking-ERS), third party route reply, local route repair and n-hop local ring techniques. These techniques control the overhead and minimize the end-to-end delay with improvement of PDR. The Optimized-Ant routing protocol is based on Ad Hoc On- Demand distance Vector (AODV) and inspired by the Ant-Colony Optimization (ACO) used to solve complex optimization problems and utilizes a collection of mobile agents as ANTS to perform optimal routing activities. Shivakumar D and Ganeshan S proposed a new On- Demand Ant-based Multiagent Routing Algorithm (ODAMRA)  for Mobile Ad hoc Networks (MANETs), which combines the ondemand routing capability of Ad hoc On-demand Distance Vector (AODV) with some modifications in the existing ant colony optimization mechanism using ant-like mobile agents. In the conventional AODV algorithms, the actual communication is to be delayed until the route is determined. Therefore, this is not suitable for real-time data as well as multimedia communication applications. The proposed algorithm provides high connectivity, reducing the number of route discoveries before starting new connections. Hence, this may lead to elimination of the delay before starting the actual communication and it can be suitable for real-time communication in MANETs. Zheng YW and Han TS in research paper titled Ant-based Energy-aware Disjoint Multipath Routing Algorithm for MANETs  present a novel approach called ant-based energy-aware disjoint multipath routing algorithm (AEADMRA). It is based on swarm intelligence and especially on the ant colony-based meta heuristic. It can discover multiple energy-aware node-disjoint routing paths with a low routing overhead. Authors use combination of Swarm Intelligence and node-disjoint multipath routing to overcome the problems of routing in MANETs. Kumar RR and Damodaram A in research paper titled A Novel on Demand Ant Based Security Alert Routing Algorithm for MANET in Grid Environment  present on Demand Ant based security alert routing Algorithm (ODASARA) for mobile adhoc networks in grid environment, which combines the on-demand routing capability of Ad Hoc On-Demand Distance Vector (AODV) routing protocol with a Ant Colony Optimization mechanism using ant like mobile agents.
Singh et al. in their research paper “ANTALG: An Innovative ACO based Routing Algorithm for MANETs “ conclude that MANETs have been used in wide areas of applications such as disaster management, video transmissions, secure communication etc. Due to the constant topological changes, it is a challenging task to route the packets to their final destination in MANETs. Keeping in view of the same, propose a new Innovative ACO based Routing Algorithm (ANTALG) which has considered the random selection of source and destination node and exchanges the Ants (agents) between them. In general, ANTALG algorithm operates using reinforcement learning to define a model of optimal routing behavior in MANETs. In such a model, optimal behavior is not merely searching shortest-hop paths, but also considers the quality of the links which make up those paths. The learning strategy that designed is based on Ant Colony Optimization (ACO) algorithms. It has some of the unique features. They find the ANTALG has better performance in comparison to HOPNET, AODV and ADSR protocols as shown in the results section using various performance evaluation metrics . We consider this ANTALG routing algorithm as one of the ACO based algorithm for performance evaluation in our research paper. Peng et al. in their research paper propose improved QoS for Routing. The proposed routing algorithm is energy and QoSaware. It solves the multi-constrained routing problem in wireless sensor networks based on a biological evolution algorithm like ant colony optimization. The lightweight ants are used to find routing paths between the sensor nodes and the sink nodes, which are optimized in terms of distance, delay, packet loss, bandwidth, and energy levels. These special ants minimize communication loads and maximize energy savings, contributing the extended lifetime of the wireless sensor networks. The simulation results show that the IACR algorithm has good performances in different WSN scenarios . We consider this proposed IACR algorithm as second ACO based algorithm for performance evaluation in our research paper. Ding N and Liu PX in their research paper propose an ACO based Algorithm, They mention in their conclusion that the comparison of simulation results, Ant Chain algorithm can construct a more elegant routing path for a randomly deployed sensor network. It provides the least total cost and relatively better positioning for each node. The centralized optimization provides an energy-efficient solution to the applications in which the base station is not far away. In addition, the advantages of the Ant Chain algorithm become more evident when sensor nodes are more sparsely distributed, in which case, it can not only provide a longer lifetime, but also show much higher reliability. Ant Chain algorithm is able to provide a flexible, reliable and energy-efficient data-gathering and communication solution to sensor networks, especially for civilian applications that require low cost, steady performance and high data quality . We considered this Ant Chain algorithm as an ACO based algorithm as third paper for performance evaluation in this paper.
The experimental setup is used for performance evaluation of these three ACO based ANTALG, Ant Chain and IACR routing algorithms. It measures the ability of protocols to adapt to the dynamic network topology changes while continuing to successfully deliver data packets from source to their destinations. In order to measure this ability, different scenarios are generated by varying the number of nodes. We use following scenario generation commands for generating cenario file:
./setdest –v 1 –n 20 –p 2.0 –M 10.0 -t 200 -x 500 -y 500; ./setdest –v 1 –n 50 –p 2.0 –M 10.0 -t 200 -x 500 -y 500; ./setdest –v 1 –n 80 –p 2.0 –M 10.0 -t 200 -x 500 -y 500; ./setdest –v 1 –n 100 –p 2.0 –M 10.0 -t 200 -x 500 -y 500.
Similarly, for connection pattern generation we use, cbrgen.tcl file. By using following commands the onnection pattern is generated:
ns cbrgen.tcl -type cbr -nn 20 -seed 1.0 -mc 16 –rate 4.0; ns cbrgen.tcl -type cbr -nn 50 -seed 1.0 -mc 16 –rate 4.0; ns cbrgen.tcl - type cbr -nn 80 -seed 1.0 -mc 16 –rate 4.0; ns cbrgen.tcl -type cbr -nn 100 -seed 1.0 -c 16 –rate 4.0;
The trace file is created by each run and is analyzed using a variety of scripts, particularly one called file *.tr that counts the number of successfully delivered packets and the length of the paths taken by the packets, as well as additional information about the internal functioning of each scripts executed. This trace file is further analyzed with AWK file and Microsoft Excel is used to produce the graphs.
Simulations are run by considering three ACO based ANTALG, Ant Chain and IACR routing algorithms. In order to get realistic performance, the results are averaged for a number of scenarios. We tried to measure the protocols performance on a particular terrain area of 500 m × 500 m from real life scenario at a speed of 10 m/s. The simulation time was taken to be of 25, 50, 75, 100, 125 and 150 seconds for Constant Bit Rate (CBR) traffic type with a packet size of 512 Byte. Also, we have considered nodes with Omni-Antenna and Two Ray Ground Radio Propagation method. Simulation parameters are appended in Table 1.
|Protocols studied||ANTALG, Ant Chain and IACR|
|Simulation time||25, 50, 75, 100, 125 and 150 seconds|
|Simulation area||500 x 500|
|Transmission range||250 m|
|Node movement model||Random waypoint|
|Traffic type||CBR (UDP)|
|Data payload||512 Bytes / packet|
Table 1: Simulation Parameters.
In this paper, we have considered Packet Delivery Fraction (PDF), throughput in Bytes per second, and percentage routing overheads for evaluation of ANTALG, Ant Chain and IACR routing protocols. The simulation results obtained with the above mentioned simulation parameters are appended in Tables 2-4. The graph showing comparison between ANTALG, Ant Chain and IACR is shown in Figures 1-3.
|Simulation Time||Ant Chain||IACR||ANTALG|
Table 2: Packet Delivery Fraction with varying Simulation Time.
|Simulation Time||Ant Chain||IACR||ANTALG|
Table 3: Throughput (Bytes/sec) with varying Simulation Time.
|Simulation Time||Ant Chain||IACR||ANTALG|
Table 4: Percentage Routing Overhead with varying Simulation Time.
Packet delivery fraction (PDF)
It is the ratio of the data packets delivered to the destinations to those generated by the sources.
Packet Delivery Fraction (PDF)=Total Packets Delivered to destination / Total Packets Generated.
Mathematically, it can be expressed as:
Where, P is the fraction of successfully delivered packets, C is the total number of flow or connections, f is the unique flow id serving as index, Rf is the count of packets received from flow f and Nf is the count of packets transmitted to f.
Throughput of the routing protocol means that in certain time the total size of useful packets that received at all the destination nodes. The unit of throughput is MBytes/s, however we have taken bytes per second. The throughput values obtained for the simulation parameters of Table 1 is tabulated in Table 3. The graph shown in Figure 2 indicates the throughput comparison of ACO based routing algorithms Ant Chain, IACR and ANTALG.
Routing Overhead of the routing protocol means Ratio of number of control packets to number of messages sent. Nodes typically have low computational capability and memory, and could not support diffusion communication which is widely deployed in the wired networks.
For example, distance-vector routing protocol uses the Bellman- Ford algorithm and link-state protocol use the Dijkstra's algorithm to calculate shortest (lowest cost) paths. So not only the network bandwidth consumed by the routing messages must be considered, but also how much processing power and memory is required in the nodes. The Routing Overhead values obtained for the simulation parameters of Table 1 is tabulated in Table 4. The graph shown in Figure 3 indicates percentage routing overhead of ACO based routing algorithms Ant Chain, IACR and ANTALG.
In this paper we have compared the performance of ACO based Ant Chain, IACR and ANTALG routing algorithms for routing using NS-2 event simulator keeping packet size of 512 Byte. It is found that ACO based IACR Routing Algorithm performs best for packet delivery fraction for increasing simulation time. However, PDF decreases with much increase in simulation time. For low simulation time ANTALG provides better PDF than Ant Chain Algorithms, however for higher simulation time PDF of ANTALG worsens. Therefore, it can be concluded that in terms of performance matrix Packet Delivery Fraction, IACR is to be preferred. Throughput for ACO based IACR and ANTALG is better than Ant Chain routing Algorithms. Also, throughput worsens for Ant Chain routing Algorithm for larger simulation time. Routing overhead is also very high for Ant Chain routing algorithms. ANTALG also has higher routing overhead than IACR but less than Ant Chain. But average routing head for varying simulation time it is found that IACR performs better than ANTALG. The observation from the experiments on Ant Chain, IACR and ANTALG, with an increase in simulation time for a fixed number of nodes and area of 500 m × 500 m illustrates that even if the terrain area of the network scenario is kept constant, the behavior of these routing protocols changes. It has also been found that the overall performance of IACR routing protocol for performance matrices, Packet Delivery Fraction as well as Throughput is better than that of ANTALG and Ant Chain routing protocols. In our experimental evaluation, we have taken up comparison of Ant Chain, IACR and ANTALG algorithms with varying simulation time. We shall consider the comparison of Ant Chain, IACR and ANTALG by varying packet size and number of nodes.
We shall be very thankful to referee’s comments for their valuable and helpful suggestions. Also, we are thankful to CMU Monarch Project Group for providing Wireless and Mobility Extensions to NS-2 Simulator.