Printer Friendly

Recurrent Ant Colony Optimization for optimal path convergence in Mobile Ad hoc networks.

1. Introduction

Mobile Ad Hoc Network [MANET] is a collection of mobile nodes that can be dynamically set up without any fixed infrastructure. It is an autonomous system in which the mobile hosts connected by wireless links are free to move randomly and often act at the same time. The topology of such network is likely to be highly dynamic because each network node can freely move and no pre-installed base station exists. Due to the limited wireless transmission range of each node, data packets may be forwarded along multi-hops. Route construction must be done with a minimum of overhead and bandwidth consumption. Energy Efficient Routing Protocols [1] are challenging to design as performance degrades due to scalability of mobile ad hoc network remains as an open challenge.

The MANET routing Protocols are categorized as proactive, reactive, flow oriented and hybrid routing Protocols [2,3]. Proactive Routing Protocols [4, 5] maintain a new list of destination nodes and their routes by distributing the routing tables throughout the entire network for every periodic interval of time. The main disadvantages are maintenance of respective amount of data and slow reaction towards failures. Reactive Routing Protocols [6-10] find route only on-demand by flooding route request packets throughout the network. The key motivation of this protocol is the reduction in routing load and there will be an impact on the performance for low bandwidth wireless link if high routing load exists. The main disadvantages are high latency time and excessive flooding leads to clogging. Flow-Oriented Routing Protocols [11, 12] find a route on-demand by tracking the present flows. This is achieved by unicasting consecutively while promoting a new link. The main disadvantages are it takes long time when exploring new routes without prior knowledge and may refer to estimate existing traffic to compensate for missing knowledge of routes. Hybrid Routing Protocol [13] combines the advantages of proactive and of reactive routing. The routing is initially established with some proactively prospected routes and then serves the demand from additionally activated nodes through reactive flooding. The choice for one or the other method requires predetermined for typical cases. The main disadvantages of such algorithms are reaction to traffic volume depends on number of nodes activated and the traffic demand depends on gradient of traffic volume.

Ant Colony optimization (ACO) is a meta-heuristic approach introduced by Marco in 1992 [14-20]. ACO Techniques that inspires the behaviour of natural ants [21-23] uses the computational agents as ants to determine the shortest route form from nest to food location by depositing the pheromone trails. These pheromone trails are used by the future ants towards optimal solution [24-26].

Once the ants reaches the destination, it takes the reverse path to reach the destination. The pheromone intensity gets reduced in all non-optimal paths due to pheromone evaporation factor. These Swarm intelligence techniques are used for controlling unmanned vehicles, for planetary mapping [27] and solving other combinatorial optimization problems [28-30]. Ant-based routing algorithms have a number of properties which are desirable in MANETs: they are highly adaptive to network changes, use active path sampling, robust to agent failures, provide multipath routing, and load balancing.

Autocatalysis plays an imperative role in functioning of ACO algorithm i.e., the more the ants choose a move, the more the move is rewarded by increase in pheromone intensity, the more attention-grabbing will be for the subsequent ants [16]. The amount of pheromone deposited is made proportional to the integrity of the solution an ant has built in its building.

As a result, if a move contributed to generate a high-quality solution its integrity will be increased proportionally to its involvement. Based on this terminology we designed a modified Ant colony Optimization technique that executes the ACO recursively in order to obtain optimal convergence solution.

Rest of the paper is organized as follows: Section 2 provides the literature survey and related works with various classifications of Ant colony based routing algorithms. Section 3 describes the newly framed Recurrent Ant Colony Optimization (RECACO) with detailed contents of pheromone tracking, pheromone renewal strategy and node selection based on the residual energy in the neighbor nodes. Section 4 describes the formulation of combined metric ELD (Energy Load Delay) for performance evaluation. Section 5 concludes the paper.

2. Related Works

ACO based Routing Protocols are classified as Table Driven or Proactive Ant based Routing Protocols, On-Demand or Reactive Ant based Routing Protocols and Hybrid Routing Ant based Protocols.

2.1 Table Driven or Proactive ant based Routing Protocols

2.1.1 Ant Based Control (ABC)

ABC scheme is proposed for routing in telephone network [31-33] and the network performance depends on the capacity to attend the calls. Thus ABC routing is a circuit switched routing and is merely proactive. It is appropriate for mobile ad hoc networks due to their decentralised nature, high robustness to node failures and load balancing and adaptability to highly dynamic environments. In ABC, the ants adapt the following procedure. The source node releases a group of exploratory ants. Node choice is probabilistic and route selection is deterministic. Each node maintains a routing table that contains a list of neighbor and all possible destinations that can be reached for that particular node. The amount of pheromone deposited modifies the routing table. Aging and decaying of ants are the new features of ABC. An artificial delay is incorporated in order to reduce the agents entering into congested link. Thus ABC algorithm has less failure compared to other methods [34].

2.1.2 Probabilistic Ant Routing (PAR)

PAR [35, 36] adopts both unicast and broadcasting of ants to search path towards destination. When the route to destination is available then unicasting of ant is adopted or else the ants are broadcasted. The Forward ant pushes the node ID and node traversal time in each intermediate node it visits. When the forward node reaches the destination, it transfers all the route information to Backward ant and dies. The Backward ant utilizes this information to reach the source node.

2.1.3 AntNet

In AntNet, the ants adopt the following protocols [37, 38]: The source node periodically generates Forward ants and the link selections are based on the probability value which is the function of queue length. At each intermediate node, the ant stores the node ID of the previously visited node and time stamp in a buffer. When the Forward ant reaches the destination, it becomes the backward ant and takes the reverse route to reach the source. The Backward ant updates the link probability at each node during its reverse transit to source.

2.2 On-Demand or Reactive ant based Routing protocols


PACONET is an improvised ant colony optimization algorithm for MANETs. PACONET [30, 39, 40] ensures that all possible paths from a particular node have been traversed. The Forward ant takes the next hop node to be the unvisited node based on the pheromone concentration. The routing table maintains a binary value for each node that indicates whether the node has been visited or not and the pheromone concentration value for the corresponding node pair.

2.2.2 Probabilistic Emergent Routing Algorithm (PERA)

Whenever the route to destination is unavailable, the source node broadcasts the forward ant with unique sequence number to all the neighbor nodes [40-42]. The forward ant selects the link based on the probabilistic distribution available on the routing table. The routing table at each intermediate node contains the records with the following information that is updated by the Forward ants. The IP address of the source node and destination node, unique sequence number, hop count and a dynamic stack that contains the route traversed and the timestamp that indicates the time the forward ant traverse the particular intermediate node. Here both the forward and the backward ants are broadcasted and that leads to network congestion and unnecessary energy consumption. The multiple routes to destination will be available in the routing table when the backward ant reaches the source node. The source node selects the path with higher probability to transmit the data packets. The other optional path may be used during the occurrence of link failures.

2.2.3 Ant Dynamic Source Routing (ADSR)

ADSR [43, 44] is similar to that of DSR but for the route request and route reply, the forward and backward packets are added and are used during route discovery process.

2.2.4 Ant colony based Routing Algorithm (ARA)

ARA works in three phases [45-47]: Route Discovery Phase, Route Maintenance Phase, Route Failure handling. In the Route Discovery phases, the source node broadcast the Forward ants to all its neighbors. Each Forward ant has a unique sequence number using which duplication is avoided. Forward ants while reaching each intermediate node, create a record in its routing table with the entries as destination address, next hop node and pheromone value. Once the forward ant reaches the destination node, it extracts the information from forward ant and destroys it. Then the Destination node creates a backward ant and sends it to the source node in the reverse path. In route maintenance phase the data packets are relayed from source to destination through the intermediate node and pheromone updating keeps on increasing. The same happens when the data packets are delayed in the opposite direction. In route Failure handling phase, the link failure is detected by the source through missing acknowledgement and the failed link is eliminated by resetting the pheromone value to zero. In ARA, the new route discovery actions are never initiated unless and otherwise the source receives any route error message notification.

2.3 Hybrid ant based Routing Protocols

2.3.1 AntHocNet

The Route discovery [48-50] adapts the following procedure: When a node is in need of packet transmission, it checks its routing table whether information to reach the destination is available. If yes, it unicasts the packet and if not, it broadcasts the F-ants to its entire neighbor. Once an intermediate node receives F-ant, it checks whether route to destination is available through any of its neighboring node. If so, it unicasts the F_ant. If not again the F-ant is broadcasted to the entire intermediate node. The procedure is iterated till a path to destination is determined. Once the F-ant reaches the destination, it becomes B_ant. The destination node discards the duplicate F-ants. The B_ants travels in the reverse path updating the routing table at each intermediate node. Link failure is detected with the help of timer.

2.3.2 Ant Routing Algorithm for MANET based on Adaptive Improvement (ARAII)

ARAII maintains two routing table: 1. The routing table in each intermediate node is maintained with the following information: Initial node, Last node and heuristic value. Here the Initial node represents the initial leaving place of ants; last node represents the address of previous s intermediate node and heuristic value energy information of the intermediate node. 2. The routing table that contains neighbour information with the following columns: neighbor, pheromone, time. The neighbor column to store all the neighbor node of a current node, pheromone column maintains the link reliability and time is component to monitor the connectivity between the nodes. During path establishment, the Forward ants chooses the next node randomly that is biased by the pheromone value and local heuristic value of the edge between two nodes.

2.3.3 Multi-Agent Ant based Routing Algorithm ( MAARA)

MAARA [51, 52] involves five phases: Route discovery, Route updating, Data routing, Route maintenance and Route failure handling. In MAARA, each node maintains a routing table (proactive) and the route discovery phase is initiated only when there is demand for transmission. The Forward ant with source address and unique sequence number is broadcasted by the source. Thus duplication is avoided. The first ant that reaches the destination becomes backward ant and it takes the reverse path to reach the source node. The backward ant updates the destination address, hop count and pheromone value. Data packets are transmitted based on the pheromone value in the routing table. If multiple paths to destination exist, the next hop is chosen randomly with some probability. In MAARA load balancing is achieved but it faces higher congestion that lead to high average end-to-end delay.

3. Unsupervised Clustering Design of Recurrent Ant Colony optimization (RECACO) Algorithm

Applying ACO recursively introduces an additional term profundity that decides the value of recurrent to obtain a precise optimal solution. REACO runs the actual ACO with the following three steps in each iteration: Pheromone Tracking, Pheromone Updating and Node Selection. RECACO involves four steps: Dawn of route, Route modernization, Data Steering and Route Failure Handling. Design of RECACO is shown in Table 1 and the notations used are shown in Table 2.

3.1 Dawn of route

3.1.1 Generation of ACO Feasible Solution

RECACO algorithm constructs two computational agents' namely forward ant <[F.sub.ant]> and backward ant<[B.sub.ant]>. These <[F.sub.ant]> and <[B.sub.ant]> agents work in two modes: FMode and BMode, respectively. Agents are in FMode when they are in transit from nest location to food location and agents are in BMode when they are in transit from food location to nest location. Once <[F.sub.ant]> FMode reaches its destination, it switches to BMode and travels back to the nest location. Agents in FMode construct a solution by choosing the next hop node among the neighbor nodes by implementing a probabilistic choice that is biased by the pheromone trails deposited by <[F.sub.ant]> and <[B.sub.ant]> agents in FMode and BMode respectively. <[F.sub.ant]> memorises the path and when it reaches the destination it changes to BMode. <[B.sub.ant]> agents in BMode leaves pheromone trails on the reverse path where it transits. This procedure eliminates the formation of loop in the path from destination to source.

Source node S will not broadcast the <[F.sub.ant]> agents to the entire neighbor node. Instead it will send the <[F.sub.ant]> only to the neighbor nodes whose energy level is greater than the threshold value. This threshold value represents the minimum energy required to transmit a single data packet. This procedure is iterated through all the possible paths to reach the destination. Again from the destination, the <[B.sub.ant]> will take the reverse path to reach the source. When one of the <[B.sub.ant]> agents reaches the source S, the recurrent value is decremented. Here the path establishment is done not based on the first <[B.sub.ant]> agent received at S. The procedure is iterated till the recurrent value becomes zero. So the source node S will receive multiple <[B.sub.ant]>. agents. Then it selects the path among all possible paths based on the,

1. pheromone intensity

2. Probability choice

3. Energy level of the node in the path from S to D

The node with energy less than the threshold value will not be involved in the path finding and it will enter into sleep mode in order to conserve its energy for its local routing purpose. These kinds of nodes in sleep mode may be involved or may become active if and only if there are no other possible paths to reach the destination.

3.1.2 Pheromone tracking

The Forward ants <[F.sub.ant]> choose the next hop based on probabilistic function formulated as:


[NH.sub.i] Represents set of all neighbour nodes of node i. The edge selection probability function depends on the amount of pheromone intensity [[tau].sub.<i,j>] on the edge <i, j>. [[eta].sub.<i,j>] is the local heuristic value that takes the value of 1/[[paragraph].sub.<i,j>] where [[paragraph].sub.<i,j>] is the distance between i and j.

[[alpha].sup.3] 0 and [[beta].sup.3] 0 are the values to control the influence of [[tau].sub.<i,j>] and [[eta].sub.<i,j>], respectively.

3.1.3 Pheromone Renewal

The amount of pheromone deposited is made proportional to the goodness of the solution an ant is building. So, pheromone renewal is done under two modes. Online step-by-step Pheromone renewal mode and Online delayed pheromone renewal mode. In Online step-by-step Pheromone renewal mode, <[F.sub.ant]> ants release pheromone while building the solution. In Online delayed pheromone renewal mode <[B.sub.ant]>, ants update the pheromone and builds the solution towards the source S. The pheromone is updated based on the formulation,

updated [[tau].sub.<i,j>] [logical not] (1 - [lambda])[[tau].sub.<i,j>] + [[DELTA][tau].sub.<i,j>]

l is the pheromone evaporation rate. Pheromone evaporation is needed to avoid a too rapid convergence of the algorithm toward a sub-optimal region. [[DELTA][tau].sub.<i,j>] is the amount of pheromone deposited by the <[F.sub.ant]> ants during online step-by-step pheromone mode and by the <[B.sub.ant]> in online delayed pheromone mode.

[[DELTA][tau].sub.<i,j>] = 1/[L.sub.k] if ant k travels on edge <i, j>

Where [L.sub.k] is the cost of kth ant's tour. Since pheromone updating is done both in online step-to-step and online delayed pheromone mode, the pheromone evaporation rate will be minimum compared to other ACO optimization algorithms.

3.1.4 Pheromone Adjustment Technique

The pheromone decay factor chosen is an exponential decay factor that depends on link usage.

[j.sub.<i,j>] = [j.sub.<i,j>] [*.sup.t.sub.e]

During the occurrence of link break, ants can take the next feasible path based on the pheromone intensity.

3.1.5 Daemon updates (optional)

Offline pheromone Update: the daemon can observe the path found by each ant in the colony and choose to deposit extra pheromone on the components used by the ant that build the best solution. Pheromone updates performed by the daemon are called offline pheromone updates.

3.2 Route Modernization

Each <F.sub.ant> agent maintains a routing table that contains information like source IP address, Destination IP address, number of neighbor nodes visited, Energy level of each neighbor node, Pheromone intensity of each edge, probability choice value for edge selection and threshold value. Each <F.sub.ant> updates the values in the routing table maintained at each node when it is taking its traversal from source S to destination D. When the <F.sub.ant> agent reaches the destination, the information is transferred to <B.sub.ant> agent from <F.sub.ant> agent. The destination kills the <F.sub.ant> agent and now the <B.sub.ant> agent takes its traversal from source S to destination D updating the routing table at each node.

3.3 Data Steering

Data packets are forwarded based on the pheromone intensity, probability value for edge selection and energy level of the individual node in the path from S to D. The optimal path can be chosen based on the above three parameters. This can be compared in order to find the precise optimal solution from source S to destination D.

3.4 Route failure Handling

If any of the neighbor nodes detects link failure, it will check the routing table to find the next available path to destination D. If no path is available it will send an error message back to the source. The source node S initiates the retransmission on if it receives error messages.

3.5 RECACO Algorithm

1. Assumption: S be the source node, D be the destination.

2. Initialize the network.

3. Initialize the recurrent value.

4. Initialize the population size such that population size >= recurrent value.

5. To determine the precise optimal solution from Source S to Destination D run the following procedure till the recurrent value becomes zero.

6. Initialize the pheromone intensity to zero.

7. Initially the probability of choosing any path is equal to one.

8. Broadcast ants to select the path to destination based on constraint explained under ACO_FeasibleSolution() procedure.

9. Among the neighbor nodes with required energy level, the first <[F.sub.ant]> agent select any random next hop as the probability of choosing any path is 1.

10. Edge selection by the <F.sub.ant> agents is based on the probabilistic function


11. Each <F.sub.ant> agent updates the pheromone intensity of the path based on the formulation,

updated[[tau].sub.<i,j>] [logical not] <1-[lambda]>[[tau].sub.<i,j>] + [[DELTA][tau].sub.<i,j>]

12. Repeat step 10 and 11 for each <F.sub.ant> agent until it reaches the destination D.

13. When the <F.sub.ant> agent reaches the destination, it changes its mode to BMode.

14. Edge selection by the <B.sub.ant> agent is based on the probabilistic function,


15. Each <[B.sub.ant> agent updates the pheromone intensity of the path based on the formulation, updated [[tau].sub.<i,j>] [logical not] <1-[lambda]>[[tau].sub.<i,j>] + [[DELTA][tau].sub.<i,j>]

16. Repeat step 14 and 15 for each <B.sub.ant> agent that reaches the source S.


4.1 Energy Metric

The energy dissipation rate is computed based on exhaust pace Index and Residual Energy. The Drain rate [53] at a node N at given time t in seconds is formulated as




[t.sub.1] = t - Dt

The Energy Index value is formulated as,

EI = Ex[P.sub.N]<t>/Ex[P.sub.nax]


[ExP.sub.nax] = [RE.sub.N]<t>/[t.sub.1]

[ExP.sub.N]<t> is the energy exhaust pace value at time t and [RE.sub.N]<t> is the residual energy at node t at time t.

4.2 Load Balance Metric

Evaluation of Load Balancing Index [53] is based on the Round Trip Delay.



[RTT.sub.i] is the round trip delay associated with path from intermediate node [sup.i] to destination D and hl represents the total hop count from source S to destination D.

4.3 Delay Metric

Delay Index [54] is estimated to be based on the link propagation delay, link bandwidth and packet size

[??] = [ID.sub.<i,j>] + Z


Z = [Q.sub.<i,j>] + n/[b.sub.<i,j>]

DI is the Delay Index. [LD.sub.<i,j>] is the link propagation delay between the mobile node i and j. It is the ratio of distance to signal propagation speed. [Q.sub.<i,j>] is the number of packets waiting in the queue between the mobile node i and j, [sup.m] is the size of data packet and [b.sub.<i,j>] is the bandwidth of the link between the nodes i and j.

4.4 ELD (Energy-Load-Delay) Metric

The Energy Load Delay metric is computed based on,




The constant provides the likelihood of associating different weights to the indices.


Experimental analysis [53] is done through setting up a dense wireless network topology with 100 nodes in a grid area of 1000X1000 m as mentioned in Table 3.All the 100 nodes moves randomly with a speed of 5 m/s. The simulation duration is 600 s and the packets are generated in the range of 4-12 pkts/s as mentioned in Table 4. The values of algorithm parameters used for simulation is presented in Table 5.

4.5 Average End-to-End Delay

The average end-to-end delay measured against data rate using AODV. ACO, LBE-ARAMA [53] and recurrent ant colony optimization algorithm is shown in Fig. 2. In ACO, delay increases rapidly when the packets transmitted per second increase i.e at a data rate of 8 pkts/s. In LBE-ARAMA, the delay increases smoothly when the data rate increases. But the results of the proposed algorithm shows that when the nodes determine the shortest path based on the pheromone deposit and pheromone evaporation co-efficient by executing the ant colony optimization recursively, the increase delay component is less compared to the existing algorithm. From the simulation results with respect to this end-to-end delay component we would be able to implement that proposed algorithm in real time network application that composed of very large number of mobile nodes.

4.6 Packet Delivery Ratio

The packet delivery ratio is plotted against data rate for AODV, ACO, LBE-ARAMA and recurrent ant colony optimization algorithm as shown in Fig. 3. From Fig. 2, it is clear that queue delay in AODV, ACO, LBE-ARAMA is high that results in increase in packet drop. As the rate of dropping of packets increase in LBE-ARAMA [53] the packet delivery ratio which is ratio of number of packets delivered at the destination node to the number packets transmitted by the source node is high compared to the proposed algorithm. Therefore, with respect to packet delivery ratio component the recursive ant colony optimization simulates better results. From this simulation result, it is sure that the proposed algorithm can be implemented in real time to transmit video files in dense networks

4.7 Average Node Energy

Fig. 4 shows the average node energy simulated against node speed for AODV, ACO, LBE-ARAMA and recurrent ant colony optimization algorithm. The initial node energy of the nodes is set to 2 J. Maintaining node energy is still an open challenge in mobile ad hoc networks. From the simulation results, it is clear that as the node mobility increase, the average node energy retained is high for recurrent ant colony optimization algorithm when compared to ant colony optimization algorithms.

4.8 Network Life Time

The network life time is calculated based on the number of mobile node alive during simulation time. Fig. 5 shows the number of active nodes during various simulation times for AODV, ACO, LBE-ARAMA and recurrent ant colony optimization algorithm. Higher the number of active nodes greater will be the network life time. Maintaining network life time is still an open challenge in mobile ad hoc networks. From the simulation results, it is clear that as the simulation time increase, the number of active nodes retained is high for recurrent ant colony optimization algorithm when compared to ant colony optimization algorithms.


The proposed algorithm produces better results than AODV, ACO and LBE_ARAMA algorithm because of the iterative execution of ACO till the termination criterion is met. This proposal satisfies multiple metrics like end-to-end delay, energy and load balancing. The innovative factors used for the newly designed algorithm is the renewal of pheromone during online step-by-step pheromone renewal mode and online delayed pheromone mode and Node selection is based on the pheromone intensity, probability choice value for edge selection, residual energy of the neighbor nodes and pheromone evaporation co-efficient factors. Various Simulation operations have been done to present the goodness of the recurrent ant colony optimization against various existing algorithms.


[1] Jinhua Zhu and Xin Wang, "Model and Protocol for Energy-Efficient Routing over Mobile Ad Hoc Networks," IEEE Transaction on Mobile Computing, vol.10, no.11, pp.1546-1557, 2011. Article (CrossRef Link).

[2] P. Deepalakshmi, S. Radhakrishnan, "An ant colony based multi-objective approach to source-initiated QoS multicasting method for ad hoc networks," International Journal of Advance Soft Computing Applications, vol. 3, no. 2, pp. 1-18, 2011. Article (CrossRef Link).

[3] Sampath Amritha, C. Tripti and M. Thampi Sabu, "An ACO algorithm for effective cluster head selection," Journal of Advances in Information Technology, vol. 2, no. 1, pp. 50-60, 2011. Article (CrossRef Link).

[4] A. Neumann et al., "Better Approach to Mobile Ad Hoc Networking (B.A.T.M.A.N)," April 07, 2008. Article (CrossRef Link).

[5] T. Clausen and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)," 2008. Article (CrossRef Link).

[6] N. Kettaf, et al., "Admission Control enabled On Demand Routing (ACOR)," October 2007. Article (CrossRef Link).

[7] D. Verma and D. Chandrawanshi, "Comparative performance evaluation of AODV over CBR and TCP traffic," International Journal of Computer Science and Technology, vol. 2, no. 2, pp. 181-183, 2011. Article (CrossRef Link).

[8] B. David Johnson and A. David Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Computing, vol. 353, pp. 153-181, 1996. Article (CrossRef Link)

[9] Yih-Chun Hu et al., "Flow State in the Dynamic Source Routing Protocol," February 23, 2001. Article (CrossRef Link).

[10] C. Perkins, et al., "Dynamic MANET On-Demand (AODVv2) Routing," February 25, 2013. Article (CrossRef Link).

[11] Zygmunt J. Haas et al., "The Inter zone Routing protocol (IERP) for Ad Hoc Networks," July 202. Article (CrossRef Link).

[12] George Aggelou and Rahim Tafazolli, "Relative Distance Micro-Discovery Ad Hoc Routing (RDMAR) Protocol," September, 1999. Article (CrossRef Link).

[13] Zygmunt J. Haas et al., The Zone Routing Protocol (ZRP) for Ad Hoc Networks, July, 2002. Article (CrossRef Link).

[14] M. Dorigo, "Optimization, Learning and Natural Algorithms (in Italian)," Ph.D. thesis, DEI, Politecnico di Milano, Italy, 1992. Article (CrossRef Link).

[15] M. Dorigo and G. Di Caro, "The Ant Colony Optimization meta-heuristic. New Ideas in Optimization, pp.11-32. McGraw-Hill, 1999. Article (CrossRef Link). M. Dorigo, G. Di Caro and L. M. Gambardella, "Ant algorithms for discrete optimization," Artificial Life, vol. 5, no. 2, pp.137-172, 1999. Article (CrossRef Link).

[16] M. Dorigo and L. M. Gambardella, "Ant colony system: A cooperative learning approach to the travelling salesman problem," IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66, 1997. Article (CrossRef Link).

[17] M. Dorigo, V. Maniezzo and A. Colorni, "Ant System: Optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man and Cybernetics - Part B, vol. 26, no. 1, pp. 29-41, 1996. Article (CrossRef Link).

[18] M. Dorigo and T. Stutzle, "The ant colony optimization metaheuristic: Algorithms, applications and advances," International Series in Operations Research & Management Science, vol. 57, pp. 251-285, 2002. Article (CrossRef Link).

[19] M. Dorigo and T. Stutzle, "Ant Colony Optimization," MIT Press, Boston, MA, 2004. Article (CrossRef Link)

[20] Bonabeau Eric, Henaux Florian, Guerin Sylvain, et al., "Routing in telecommunications networks with 'smart' ant-like agents," in Proc. of the 2nd Int. workshop on intelligent agents for telecommunication applications, Paris, France, 1999. Article (CrossRef Link).

[21] Gudakahriz Sajjad Jahanbakhsh, Jamali Shahram & Zeinali Esmaeel, "NISR: a nature inspired scalable routing protocol for mobile ad hoc networks," International Journal of Computer Science Engineering and Technology, vol. 1, no. 4, pp.180-94, 2011. Article (CrossRef Link).

[22] Pavani Gustavo Sousa, Zuliani Luiz Gustavo, Waldman Helio and Magalhaes Mauricio, "Distributed approaches for impairment aware routing and wavelength assignment algorithms in GMPLS networks," Computer Networks, 1905-1915, 2008. Article (CrossRef Link).

[23] Paramasiven Appavoo, "Using swarm intelligence to optimize caching techniques for ad hoc network," International Journal of Computer Science and Telecommunications, vol. 2, no. 6, pp. 15-19, 2011. Article (CrossRef Link).

[24] S. B. Wankhade and M. S. Ali, "Ant based techniques for qos routing in mobile ad hoc network: an overview," International Journal of Advanced Networking and Applications, vol. 3, no. 2, pp. 1094-1107, 2011. Article (CrossRef Link).

[25] P. B. Pankajavalli and N. Arumugam, "BADSR: An enhanced dynamic source routing algorithm for MANETS based on ant and bee colony optimization," European Journal of Scientific Research, vol. 53, no. 4, pp. 576-581, 2011. Article (CrossRef Link).

[26] J. Yan, L. Yan, A. Ali, Minai, Marios, and M. Polycarpou, "Balancing search and Target Response in Cooperative Unmanned Aerial Vehicle (UAV) Teams," IEEE Transactions systems, MAN and Cybernetics-part-B: Cybernetics, vol. 36, no. 3, 2006. Article (CrossRef Link).

[27] Al-Zurba Hiba, Landolsi Taha, Hassan Mohamed and Abdelaziz Fouad, "On the suit- ability of using ant colony optimization for routing multimedia content over wireless sensor networks," International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, vol. 3, no. 2, pp. 15-35, 2011. Article (CrossRef Link).

[28] Roy Bibhash, Banik Suman, Dey Parthi, Sanyal Sugata and Chaki Nabendu., "Ant colony based routing for mobile ad-hoc networks towards improved quality of services," Journal of Emerging Trends in Computing and Information Sciences, vol. 3, no. 1, pp. 10-24, 2011. Article (CrossRef Link).

[29] Poojary Manjula and B. Renuka, "Ant colony optimization routing to mobile ad hoc networks in urban environments," International Journal of Computer Science and Information Technologies, vol. 2, no. 6, pp. 2776-2779, 2011. Article (CrossRef Link).

[30] R. Schoonderwoerd, R., O. E. Holland and J. L. Bruten, "Ant like agents for load balancing in telecommunication networks," in Proc. of 1st ACMInt. Conf. on autonomous agents, Marina del Ray, CA, USA, pp. 209-216, 1997. Article (CrossRef Link).

[31] Stojmenovic Milos, "Swarm intelligence for routing in ad hoc wireless networks," Security and Routing in Wireless Networks, pp. 167-188, 2005. Article (CrossRef Link).

[32] Sharma Priyanka and K. Kotecha, "Optimization in stagnation avoidance of ACO based routing of multimedia traffic over hybrid MANETs," International Journal of Computer Science and Telecommunications, vol. 2, no. 2, pp. 260-265, 2011. Article (CrossRef Link).

[33] Meisel Michael, Pappas Vasileios and Zhang Lixia, "A taxonomy of biologically inspired research in computer networking," The International Journal of Computer and Telecommunications Networking, vol. 54, no. 6, 2010. Article (CrossRef Link).

[34] S. Prasad, Y. P. Singh and C. S. Rai, "Swarm based intelligent routing for MANETs," International Journal of Recent Trends in Engineering, vol. 1, no. 1, pp. 153-158, 2009. Article (CrossRef Link).

[35] K. Gupta Anuj, Sadawarti Harsh and K. Verma Anil, "MANET routing protocols based on ant colony optimization," International Journal of Modeling and Optimization, vol. 2, no. 1, pp. 42-49, 2012. Article (CrossRef Link).

[36] G. Di Caro and M. Dorigo, "AntNet: distributed stigmergetic control for communications networks," Journal of Artificial Intelligence Research, vol. 9, pp. 317-65, 1999. Article (CrossRef Link).

[37] M. Dorigo and Di Caro, "AntNet: a mobile agents approach to adaptive routing," Technical report, IRIDIA- Free Brussels University, Belgium, 1997. Article (CrossRef Link).

[38] Osagie Eseosa, Thulasiraman Parimala and K. Thulasiram Ruppa, "PACONET: Improved ant colony optimization routing algorithm for mobile ad hoc networks," in Proc. of 22nd Int. Conf. on advanced information networking and applications, pp. 204-211, 2008. Article (CrossRef Link).

[39] Kumar Arun and Singh Rajeshwar, "Mobile ad hoc networks routing optimization techniques using swarm intelligence," International Journal of Research in IT and Management, vol. 1, no. 4, 2011. Article (CrossRef Link).

[40] S. Baras John and Mehta Harsh, "A probabilistic emergent routing algorithm for mobile ad hoc networks," Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pp. 68-73, 2003. Article (CrossRef Link).

[41] V. Kumar and P. Balasubramanie, "Ant colony optimization using hierarchical clustering in mobile ad hoc networks," European Journal of Scientific Research, vol. 61, no. 4, pp. 549-60, 2011. Article (CrossRef Link)

[42] R. Asokan, A. M. Natarajan and C. Venkatesh, "Ant based dynamic source routing protocol to support multiple quality of service (QoS) metrics in mobile ad hoc networks," International Journal of Computer Science and Security, vol. 2, no. 3, 2008. Article (CrossRef Link).

[43] Modi Shweta and Prithviraj Jitendra, "Performance comparison of IACO, AODV networking routing protocols," International Journal of Smart Sensors and Ad Hoc Networks, vol. 33-37, 2011. Article (CrossRef Link).

[44] M. Gunes, U. Sorges and Buouazizil, "ARA-the ant colony based routing algorithm for MANETs," Int. workshop on Ad Hoc networking, Vancouver, Canada, 2002. Article (CrossRef Link).

[45] M. Gune, M. Kahmer and Bouazizil, "Ant routing algorithm (ARA) for mobile multi- hop ad hoc networks new features and results," in Proc. of The 2nd Mediterranean workshop on ad hoc networks, 119-127, 2003. Article (CrossRef Link).

[46] Yang Jing, Zhao Wei, Xu Mai and Xu Baoguo, "A multipath routing protocol based on clustering and ant colony optimization for wireless sensor networks," Journal of Computer Network and Information Security, pp. 49-59, 2009. Article (CrossRef Link).

[47] Ducatelle Frederick, Di Caro Gianni and Maria Gambardella Luca, "Ant Agents for Hybrid Multipath Routing in Mobile Ad Hoc Networks," work supported by the project "BISON: biology-inspired techniques for self organization in dynamic networks" (IST-2001-38923) and by the Hasler foundation through grant DICS- 1830. Article (CrossRef Link).

[48] Panisson Andre, Barrat Alain, Cattuto Ciro, Van den Broeck Wouter, Ruffo Giancarlo and Schifanella Rossano, "On the dynamics of human proximity for data diffusion in ad-hoc networks," Ad Hoc Networks, vol. 10, pp. 1532-1543, 2011. Article (CrossRef Link).

[49] M. Sailaja, R. Kiran Kumar, P. Murty, Sita Rama and Prasad Krishna, "A study on routing algorithms derived from the nature for MANETs," International Magazine on Advances in Computer Science and Telecommunications, vol. 2, 2011. Article (CrossRef Link).

[50] D. Sivakumar and R. S. Bhuvaneswaran, "Proposal on multi agent ants based routing algorithm for mobile ad-hoc networks," International Journal of Computer Science and Network Security, vol. 17, pp. 261-268, 2007. Article (CrossRef Link).

[51] O. B. Correia SergioLuis, Celestino Junior Joaquim and Cherkaoui Omar, "Mobility-aware ant colony optimization routing for vehicular ad hoc networks," IEEE Wireless Communications and Networking Conference, pp. 1125-1130, 2011. Article (CrossRef Link).

[52] Floriano De Rango and Mauro Tropea, "Swarm Intelligence based Energy Saving and Load Balancing in Wireless Ad Hoc Networks," 2009. Article (CrossRef Link).

[53] Sarbjeet Kaur, Ravinder Singh and Sawhney Rajan Vohra, "MANET link performance parameters using Ant Colony Optimization approach," International Journal of Computer Applications, vol. 47, no. 8, pp. 40-45, 2012. Article (CrossRef Link).

[54] Deli Liu, Haijun Zhang, Wei Zheng and Xiangming Wen, "The Sub-channel Allocation Algorithm in Femtocell Networks Based on Ant Colony Optimization," in Proc. IEEE MILCOM 2012. Article (CrossRef Link).

[55] Zhang Haijun, Liu Hui, Ma Wenmin, Zheng Wei, Xiangming, Jiang Chunxiao, "Mobility Robustness Optimization in Femtocell Networks based on Ant Colony Algorithm," IEICE Transactions on Communications, vol.E95-B, No.4, pp.1455-1458, Apr. 2012. Article (CrossRef Link).

[56] Bin Li, Chenglin Zhao, Haijun Zhang, Zheng Zhou and Arumugam Nallanathan, "Efficient and Robust Cluster Identification for Ultra-wideband Propagation Inspired by Biological Ant Colony Clustering," IEEE Transactions on Communications, vol. 63, no.1, pp.286-300, Jan.2015. Article (CrossRef Link).

A. Karmel is working as Assistant Professor (Sr), VIT University, Chennai and pursuing Ph.D (parttime) at Anna University of Technology, Guindy. She is doing research in the field of Optimizing Energy Consumption in Mobile Ad Hoc Networks. She received B.E (Computer Science & Engineering) and M.E (Systems Engineering and Operations Research) degrees from The Indian Engineering College, Vadakangulam and College of Engineering, Guindy in 2004, and 2008 respectively. Her research interests include Quality of Service, Routing Protocols, and Energy Efficiency in Mobile Ad Hoc Networks.

Dr C JAYKUMAR has more than 18 years of teaching and research experience. He did his Postgraduate in M.E in Computer Science and Engineering at College of engineering, Guindy, and Ph.D in Computer Science and Engineering at Anna University, Chennai. He has Received 40623 $ Grant from AICTE for RPS Project and Staff Development Program. He chaired the session at various International Conferences, National level Conferences, Staff development Program and workshop. He guided 8 Phd under Anna University Chennai, India and Bharat University, India and one student has submitted thesis under Anna University Chennai. He has published 135 research papers in International Journal, International and National conferences and visited many countries like USA and Singapore. He has guiding a number of research scholars in the area Adhoc Network, Security in Sensor Networks, Mobile Database and Data Mining under Anna University Chennai, Sathayabama University and Bharathiyar University, Bharath University. He was Advisor and Technical Committee Member for many International and National Conferences. He has Coordinated National Board of Accreditation, Anna University Affiliation, Anna University Research Nodal Centre, and TCS Accreditation at various colleges. He was the "Anna University Inspection Committee Member" for Affiliated Colleges for the academic year 2008-09. He held the Member position in Board of Studies in Meenakshi University, Chennai, Technical Committee member in SRM University and SRM Arts and Science Chennai. He conducted Various National Conference, Staff Development Program, Workshop, Seminar in associated with Industries like Infosys and TCS. He has received Laptops & other Compliments from Infosys for effective coordination of Infosys Campus Connect program at Easwari Engineering College, Chennai. Currently he is working as Professor in the Department of Computer Science and Engineering, RMK Engineering College, Tamil Nadu, India.

Karmel A (1) and Jayakumar C (2)

(1) Research Scholar (PT), Anna University of Technology Chennai, Tamil Nadu 600 025--India

(1) Assistant professor, VIT University Chennai, Tamil Nadu 600 127--India [e-mail:]

(2) Professor, Department of Computer Science & Engineering RMK Engineering College, Chennai, Tamil Nadu 601 206--India [e-mail:]

* Corresponding author: Karmel A

Received April 13, 2015; revised July 15, 2015; accepted August 17, 2015; published September 30, 2015

Table 1. RECACO Algorithm

The pseudo-code of the RECACO Metaheuristic procedure

1   Procedure RECACO_metaheuristic( )
2     WHILE (termination condition not met)
3       ACO_FeasibleSolution( )
4       Pheromone Tracking( )
5       Pheromone_Renewal( )
6         Online_step_by_step_pheromone_Renewal( )
7         Online_delayed_pheromone_Renewal( )
8       Daemon_Actions( ) {optional}

Table 2. Notations Used

Notation                  Description

<[F.sub.ant]>             Forward ant

<[B.sub.ant]>             Backward ant

[p.sub.<i,j>]             Probability that an ant move from
                          node i to j

N[H.sub.i]                Neighbor node of i

[[tau].sub.<i,j>]         Pheromone intensity on the edge <i, j>

[[eta].sub.<i,j>]         Local heuristic value on the edge <i, j>

[[paragraph].sub.<i,j>]   Distance between node i and j

1                         Pheromone evaporation rate

[updated[tau].sub.<i,j>]  Updated pheromone intensity on the
                          edge <i, j>

[[DELTA]tau].sub.<i,j>]   Amount of pheromone deposited on the
                          edge <i, j>

[alpha]                   Parameter to control the influence of
                          [[tau].sub.<i, j>]

[beta]                    Parameter to control the influence of
                          [[eta].sub.<i, j>]

[L.sub.k]                 Cost of kth ant's tour (Tour length)

[j.sub.<i,j>]             Pheromone decay factor on the edge
                          <i, j>

[RE.sub.N] (t)            Residual Energy of node N at time t

Ex[P.sub.N] (t)           Exhaust pace value of node N at time t

EI                        Energy Index

LI                        Load balancing index

RTT                       Round Trip delay

hl                        Total hop count

S                         Source node

D                         Destination node

[LD.sub.<i,j>]            Link propagation delay on the edge
                          <i, j>

[Q.sub.<i,j>]             Queued packet on the edge <i, j>

[B.sub.<i,j>]             Link bandwidth on the edge <i, j>

ELD                       Energy load delay metric

Table 3. Simulation Parameters

Simulation Parameters         Value

Number of Mobile Nodes   50
Grid Size                1000X1000 m
Simulation Time          600 s
Initial Node Energy      2 J
Medium Access Control    IEEE 801.11
Transmission Power Tx    1.4 W
Receiving Power Rx       1.2 W
Mobility Model           Random Way Point
Node Mobility            5 m/s

Table 4.Traffic Parameters

Traffic Parameters   Value

Data Rate            4 to 12 pkts/s
Connection Number    8-20

Table 5. Algorithm Parameters

Algorithm Parameters                             Value

Co-efficient [k.sub.1], [k.sub.2], [k.sub.3]]    0.3
Ant Rate                                         500 m
Decay factor                                     2

Fig. 1. Analysis of ACO Algorithms

Algorithms            Routing     Agents               Energy
                      Meehan is                        Aware

Ant Base-d Control    Proactive   Exploratory ants     --

Probabilistic Ant     Proactive   Forward Ants &       --
Routing (TAR)                     ba dcwaid Ants

AntNet                Proactive   Forward ant,         --
                                  backward ant

PACONET               Reactive    Forward ant,         --
                                  backward ant

Probabilistic         Reactive    Forward ant,         --
Emergent Routing                  backward ant
Algorithm (PERA)

Ant Dynamic Source    Reactive    Forward ant.         Energy
Routing (ADSR)                    backward ant         Aware

Ant colony based      Reactive    Forward ant,         --
Routing Algorithm                 backward ant

AntHocNet             Hybrid      Reactive forward     Link
                                  ant and backward     failure is
                                  ant, proactive       detected
                                  forward ant and      with the
                                  backward ant         help of

Ant Routing           Hybrid      Forward ant.         Energy
Algorithm for MANET               backward ant         Aware
based on Adaptive
Improvement (ARAD)

Multi-Agent Ant       Hybrid      Forward ant.         --
based Routing                     backward ants,
Algorithm (MAARA)                 reactive forward
                                  ants, route repair

Algorithms            Path     Ant Structure

Ant Base-d Control    Single   Source IP address,
(ABC)                 Path     Destination IP
                               address, Age of Ant

Probabilistic Ant     Single   --
Routing (TAR)         Path

AntNet                Single   Source IP address,
                      Path     Des tination IP
                               address, Sequence
                               number, field to
                               identify as FA or
                               BA, node addresses
                               and trip time

PACONET               Single

Probabilistic         Multi-   Source IP address,
Emergent Routing      Path     Destination IP
Algorithm (PERA)               address, Node id,
                               Node traverse time,
                               Hop count, Sequence

Ant Dynamic Source    Single   --
Routing (ADSR)        Path

Ant colony based      Multi-   Source IP address,
Routing Algorithm     Path     Destination IP
(ARA)                          address, Sequence
                               number, Hop count

AntHocNet             Multi-   Source IP address,
                      Path     Destination IP
                               address, Next Hop IP
                               address, Node id,
                               Node traverse
                               time,Hop count,
                               Sequence Number

Ant Routing           Multi-   --
Algorithm for MANET   Path
based on Adaptive
Improvement (ARAD)

Multi-Agent Ant       Multi-   --
based Routing         Path
Algorithm (MAARA)

Algorithms            Routing Table          Issues

Ant Base-d Control    Destination address,   Existence of
(ABC)                 Next hop, Pheromone    congestion in
                      value                  Optimal Route

Probabilistic Ant     --                     Occurrences of
Routing (TAR)                                Overhead

AntNet                Destination address,   Increase in delay
                      neighbor node,         while propagating
                      Pheromone value        the routing

PACONET                                      Occurrences of

Probabilistic         Destination address,   No caching
Emergent Routing      Next hop,
Algorithm (PERA)      Probability

Ant Dynamic Source    --                     Need of additional
Routing (ADSR)                               control packets to
                                             monitor the
                                             condition of the
                                             paths periodically

Ant colony based      Destination address,   The new route
Routing Algorithm     Next hop,              discovery actions
(ARA)                 Pheromone value        are never initiated
                                             unless the source
                                             node receives any
                                             route error message

AntHocNet             Goodness of next       Increase in overhead
                      hop, Destination
                      address, Next hop

Ant Routing           --                     Increase in delay
Algorithm for MANET                          during route
based on Adaptive                            discovery phase
Improvement (ARAD)

Multi-Agent Ant       --                     Higher congestion
based Routing                                leads to high
Algorithm (MAARA)                            average end-to-end
COPYRIGHT 2015 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Karmel, A.; Jayakumar, C.
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Sep 1, 2015
Previous Article:Performance comparison of MISP-based MANET strong DAD protocol.
Next Article:Road aware information sharing in VANETs.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters