Intelligent Routing using Ant Algorithms for Wireless Ad Hoc Networks

Published Online August 2013 in MECS (http://www. DOI: 10.5815/ijcnis.2013.10.08

Numerous algorithms like AODV, DSR and others, are being utilized at present, to provide reliable and robust communications. These techniques concentrate mainly on the network layer and are categorized into two types: table driven or proactive routing protocols [1] - where nodes in the network exchange information when the network topology changes. Each node collects and maintains information about the current topology of the network on-demand [2] , where routing information is acquired by the source node only when there is a necessity to communicate referred to as reactive routing protocols.

Swarm Intelligence [3] is the emergent collective intelligence of groups of simple agents interacting locally through the environment. Ant routing algorithm, an on-demand technique is a type of the swarm Intelligence technology possessing attractive features like, robustness, fault-tolerance, autonomy, multi-agent and collective behavior form the center for a new class of routing and difficult combinatorial optimization techniques.

Ant algorithms, a new class of routing algorithms which is based on the principles of biological swarms. They have the potential to address these problems in an autonomous and intelligent fashion. The main goal of an Ant routing protocol is to reduce the overhead for routing. Ant routing techniques were originally developed for wired networks [4] . Inspired by their success, their capability is being extended to the wireless networks, in the recent years.

The rest of the paper is organized as section 2, discusses the background of Ant algorithms, section 3 gives the description of the ant mobility model, while section 4 gives the simulation results obtained when compared with AODV [2] with section 5 giving the concluding remarks.

• II.    RELATED WORK

In this section, the basic concept of Ant routing algorithms and some of the proposed ant algorithms are discussed.

Stigmergy is a simple form of indirect communication in which all the members of the species communicate through the environment. Ants achieve Stigmergy communication by laying a pheromone (a chemical substance) on their path towards the destination. All the other ants, that arrive later in turn, use this positive feedback, smell the already laid pheromone and thus follow the same path. When it comes to the selection between two or more paths, ants select the path with more pheromone concentration than the others. Ants are capable of finding the shortest path, even when an obstacle is placed on the path from the food source to their nest.

Ant algorithms are multi-path agent systems, which are built, inspired by the behavior of the real ant colonies. These algorithms consist of agents, called ants, which exhibit the behavior of individual ants.

The first Ant algorithms introduced where the AntBased Control (ABC) [2] and the AntNet [5] [10] as proactive routing protocols for static, wired networks. They deployed small ant packets collaboratively to discover paths between pairs of nodes. In ABC, the routing tables are updated as the ants move from source to destination. In contrast, AntNet uses backward ant strategy. Once it reaches its destination, each forward ant bequeaths the traveling time information to a backward ant, which updates the routing tables as it traces the path of the forward ant in reverse.

These Ant Colony Optimization (ACO) [11] algorithms were applied successfully to discrete optimization problems like traveling salesman problem [14] and vehicle routing [15]. However, they could not be applied directly into the wireless networks where the topology is dynamic. Hence, new and interesting features were added to make these Ants algorithms desirable in Wireless networks, also.

Accelerated Ant Routing AAR is the first among these developed algorithms. It consists of ant-like agents that roam through the network without any specific destination. However, in AAR, the ants themselves resulted in a lot of overhead.

Later, Ant- like Mobile agents routing algorithms were developed which included GPS/ant-like Routing Algorithm (GPSAL) for Mobile Ad Hoc Networks[17] and Ant-AODV Hybrid Routing Protocol [6]. They use ant-like mobile agents to scan the network. While roaming in the network, these agents collect and distribute information about the network to all the nodes, which is useful for routing.

GPSAL follows ABC strategy and source routing scheme, thereby leaving the network to rely on the location information and support from the fixed infrastructure. The shortcoming of GPSAL lies in its ants, with no feedback property to reinforce routes positively, negatively, or explore new routes randomly.

Ant- AODV incorporates the features of AODV, a reactive ad hoc routing protocol with the proactive feature of ant-based routing algorithm. A fixed number of ants keep going around the network in a more or less random manner, keeping track of the last visited nodes and when they arrive at a node they proactively update its routing table. The main drawback was that these ants, not only had to roam about the network, but also keeps track of specific number of nodes recently visited.

Another class of algorithms called Ant Optimization routing algorithms were developed that use optimization method inspired by the real ant’s life. This includes recently developed multi-path, on-demand ant algorithms, Ant- Based Routing Algorithm (ARA) and Probabilistic Emergent Routing Algorithm (PERA).

ARA [18] sets up multiple paths between source and destination at the beginning of the session and reinforces the existing routes to reduce the overhead of sending ants. During the data session, data packets reinforce the paths they follow. ARA uses a simpler version of S-ACO for route maintenance. This has resulted in the downside of ARA. This is because the stability of S-ACO in finding simple paths is debatable when applied to complex systems.

PERA [7] broadcasts all the ants towards the destination. Only the path with the highest pheromone value is used by the data. When broadcasted, ants may themselves, cause overhead by proliferating quickly over the network, by choosing different paths to the destination. Hence, when an ant arrives at a node, it compares the path traveled by that ant with the previously received ants of the same colony. Only those ants that have their time factor and the number of hops traveled value falling within a pre-defined accepting factor of the best ant of this ant colony are accepted and the rest are discarded. Also, PERA never considered network survivability.

Recently developed Ant Routing Algorithm for Mobile Ad-hoc networks (ARAMA) is yet another on- demand, multi-path routing algorithm [21]. Unlike some of the above algorithms, it optimizes the number of hops and other quality of service parameters. It is also energy efficient as it makes fair use of energy across all the nodes in the network. Also, it reduces routing overheads and is network survivability algorithm. But, it has no mechanisms to avoid the congestion problems.

Ant Mobility Model (AMM) uses creative ants to find the food sources. They make it easier for the normal ants to find the destinations. When all the ants are converted into creative ones, the advantage will become a disadvantage, thereby creating the worst case in the network. Hence, AMM limits the number of creative ants to 10 [18].

The various issues addressed by Ant algorithms include the following characteristics of MANETs as:

Stagnation:

Stagnation is a situation that occurs when the ants and their successors recursively, prefer to follow a path, thereby, creating congestion in that path. This occurs when a network reaches its convergence or equilibrium state. When an optimal path is chosen by all ants, it recursively increases an ant’s preference for that path. This may lead to:

• •    Congestion on that path, and

• •    Dramatic reduction of the probability of selecting other paths.

These two are undesirable for a dynamic network since:

• •    A path may become nonoptimal if it is congested,

• •    It may be disconnected due to network failure,

• •    Other non-optimal paths may become optimal

due to changes in network topology, and

• •    New or better paths may be discovered

Pheromone deposition:

Like real ants, the artificial ants also deposit pheromone concentration on their trail to the destination. This trail helps the other ants to follow the best path at that time in the network. However, this pheromone concentration, when goes on increasing continuously can lead to congestion in that path as all the ants try to follow the same path where there seems to be more pheromone deposition

• III.    ANT MOBILITY MODEL

Ant Mobility Model (AMM) is a multi-path routing model, which depicts the ants’ behavior in the ant colony in MANETs. This model portrays the creativity of the ants in the network environment. The ants’ role is to find the shortest path from their home, namely the anthill to the food sources scattered across the network.

Similar to AntNet, this research employs the backward ant strategy. An ant never leaves a pheromone trail when in search of food. Instead once a food source is detected, it starts laying a pheromone along the path between the food source it has found and the anthill.

The ant colony uses two types of ants: creative ants and normal ants. While the creative ants’ role is to find all the food sources across the network, the normal ants are responsible for transporting the food to the anthill.

When the search is initiated, the network consists of only creative ants. These ants in search of food would also be at the minimum. As new food sources are discovered, these ants multiply gradually, till they reach the specified value set earlier. Also, the normal ants enter the network only after the creative ants have laid pheromone to the anthill.

At the start, all the creative ants in the network are in foraging mode , looking for the food sources scattered across. Once a food source is found, these ants leave a pheromone trail ( Carry Mode ) on their way back to the anthill, thereby providing a path for the other ants to follow.

On reaching home, creative ants will not backtrack to the same food source again. Instead, they roam rando mly across the network till they encounter a new food source. Also, they make sure that they don’t reach the vicinity of the previously visited food source, in order to avoid the delay incurred in setting another pheromone trail to the anthill. This helps in completing the search quicker.

Meanwhile, the normal ants roam around the network aimlessly till they smell the pheromone ( Move Mode ) laid earlier by the creative ants. They, then, take part in gathering the food ( CarryMode ) from that food source. This process continues till that particular food source is completely exhausted. Once a food source is drained of food, these ants, then, turn towards the other sources to which the pheromone trail is already laid by the creative ants from the ants’ nest or home.

Sometimes, it is possible that the normal ants may come across a new food source, accidentally. These ants will by themselves lay the initial pheromone trail to the anthill and then continue gathering food from that food source.

Once an ant comes across a pheromone trail, it pursues the trail and reaches the food source. After acquiring food, it further strengthens the path to the anthill by freshly laying new pheromone trail on the old one. This heavier concentration acts as a call to attract the nearby normal ants to that food source. These ants in turn, lay new trails on the preceding one like their predecessor.

The pheromone trail when laid continuously by these ants may cause all the other ants to follow the same path. These new ants again drop pheromone continuously and before long create a strong odor trail on that path. This trail will not only hinder the progress in the network but also, lead to stagnation and unnecessary congestion in the network.

Stagnation is a condition when all the ants try to follow the same best path to a node across the network, thereby causing unnecessary congestion at that node. The best path then becomes the worst path and hinders the progress in the network.

AMM avoids this drawback by using pheromone evaporation, also. Ants drop pheromone trails only while transporting the food back to the anthill. Once the food source is completely depleted, the ants continue to move on till they find another food source or pheromone trail to one. Thus, after some time the trail to the first food source gets weaker and weaker and eventually disappears completely.

As the ants move across the network, a TCL program is generated simultaneously from the locations of the scattered food sources, the ants’ originating at the nest and their movements in the network. This program is to be run to achieve the desired results in the Network Simulator [19], [20].

• A.    Statement of Assumptions

The present work on Ant algorithms is applicable in all wireless networks that satisfy the following requirements:

Distributed operation: Each node should own a set of pheromone counters in its routing table for a link between two nodes. Each node controls the pheromone counter independently, when ants visit the node on route searches.

Loop-free: The nodes must register a unique sequence number of route finding packets, Forward ant and backward ant, so that they do not generate loops.

Demand-based operation: Routes must be established by manipulating the pheromone counter in the nodes. Over time, the amount of pheromone will decrease to zero when ants do not visit this node. A route finding process is to be run, when a sender demands.

Sleep period operation: Nodes ought to be able to sleep when their amount of pheromone reaches a threshold. The other nodes will not consider this node.

Also, this research is applicable in the following situations:

Multipath: Each node can maintain several paths to a certain destination. The choice of a certain route depends on the environment, e.g., link quality to the relay node.

Sleep mode: In the sleep mode node snoops, only packets that are destined for it are processed, thus saving power.

• B.    System Preliminary Design

The ant algorithms initial design includes the movement of the ants across the network. This research is based on the forward ant and backward ant strategy. Hence, the source broadcasts the forward ants as shown in Fig.2 , while the destination unicasts the backward ants to the source as shown in Fig. 3. The above discussed techniques is implemented in five modules: Ant Logic Development, Ant simulation Parameters, Network Model and Ant Mobility Pattern.

Figure2 : Broadcast of Forward ants

Figure 3 : Unicast of Backward ants

• C.    System Design

The above discussed techniques is implemented in five modules: Ant Logic Development, Ant simulation Parameters, Network Model and Ant Mobility Pattern.

• 1)    Ant logic Development:

This module defines the presents the actions of ants, the special agents in selecting the best method to find the shortest path providing a better view for “Ant Simulation Parameters”.

to be deposited, the source node, and to set the color to the ants to indicate the their mode.

• 3)    Network Model:

The random placements of the destination for the ants on the map are accomplished by this component in which of the ants is to find the shortest path to all the destinations in the shortest possible time.

4)Ant Mobility pattern:

This module is used to present the output by combining the features produced in all the above modules. It, also, shows the amount of food left and the time taken till that moment by the ants.

• IV.    SIMULATIONS

The results obtained with this model are compared with those obtained with AODV (Ad-hoc Distance Vector) Routing protocol in the same network. These algorithms are compared in terms of performance metrics namely, delivery ratio, and end to end delay per packet.

• A.    Simulation Environment

  The AMM simulation is run in Network Simulator. In this setting, around 50 nodes are placed randomly in an area of 1000 X 1000 m² using flat- grid topology. The simulation is run for 250 seconds, in which all the nodes are set to have random motion.

Data is transferred at the transport layer using UDP, by the constant bit- rate (CBR) sources. Data is propagated using wireless channel with two-way ground propagation. Also, at the MAC layer, the famous 802.11 DCF protocol is used. Finally, the packets with size 512 bytes are transferred among the nodes.

Similarly, a setting of AODV, Random Waypoint Mobility model, consisting of around 40 nodes is used for comparison. In this model, the data traffic is sent from 20 CBR sources at the rate of 512- byte packets per second. Also, the node movement is set to have a minimum speed of 0 m/s and a maximum of 15 m/s. The radio propagation is a free space model. Though the number of nodes and the size of the simulation are varied, the average node density is kept to be constant (~7.8). Table 1 summarizes the simulation parameters of the network.

Table 1: Parameters for ant mobility model

Parameters	Value	Parameters	Value
Map Size	1000 X 1000 points	Food Sources	30
Nest Size	1	Particles per source	50
Nest position	(500,500)	Food Scent	50
Ant Size	50	Pheromone	64 points
Ant Speed	2~20 Points/Sec	Pheromone time	50 time slots
Trace     start time	200 time slots	Trace stop time	500 time slots

The Ant simulation parameters are set using the GUI discussed above is shown in the Fig. 4.

Figure 4 : GUI of Ant Simulation Parameters

• B.    Results and Discussion

The behavior of the algorithm, when run in increasingly dynamic environments is studied. The metrics used were suggested by the Internet Engineering Task Force (IETF) Mobile Ad hoc Network (MANET) working group for routing protocol evaluation. Three key performance metrics are evaluated, namely,Packet delivery ratio (i.e., throughput), Average end-to-end delay, andControl message load.

The simulation results are compared to the calculated results for AODV in the same scenarios.

Packet Delivery Ratio

Successful Packet delivery is the ratio of the data packets delivered to the destination to those generated by the CBR sources. Fig. 5 shows that the delivery ratio has increased with the increasing node speed. In AMM each node has to move. Also, unlike in the AODV random waypoint model, connections between the nodes are stable. AMM clearly outperforms AODV with respect to Packet delivery ratio.

Average end- to- end delay of the data packets includes all possible delays caused by buffering packets during route discovery latency, queuing, retransmission delay at the MAC, propagation and transfer times. Fig. 6 show the delay of packets in AODV is more than that in AMM that further increases in a more mobility of the nodes in the network.

Normalized routing Load

A routing message overhead is presented as the number of control messages. The total number of control packets during the entire simulation time is as shown in Fig. 7, 8, and 9 respectively. These control packets include RREQ (Route Request), RREP (Route Reply) and a RERR (Route Error). The results show that the overhead of the control packets is more in AODV random way Point model than in the Ant Mobility model.

The results illustrate that a mobility model has a largeeffect on the performance evaluation of an ad hoc network protocol. It is important to choose an appropriate mobility model for a given performance evaluation.

40 o' Ф <0

>1 ro

2 4 6 8 10 12 14 16 18 20

Maximum Velocity(m/s)

Figure 6: Average End to end delay versus Speed

D 60

5" 50

^ 30

H 20

-—g-—. AODV

-—•-.-. Ant Mobility

4000 3500

« 3000 о 2500 Л2000 о1500 s1000 500 0

----*---- AODV

----e---- Ant mobility

2 4 6 8 10 12 14 16 1820 Maximum Velocity(m/s)

2   4   6   8 10 12 14 16 18

Max Velocity(m/s)

Figure 7. Total RREQ packets

Figure 5. Packet Delivery ratio

Average Packet Delay

Max Velocity(m/s)

Figure 8. RREP versus speed

Figure 9: RERR packets versus speed

• C.    Summary of results

The behavior of the algorithm, when run in increasingly dynamic environments showthat ant routing techniques produce results that are enhanced than the other existing algorithms. The graphs plotted prove that when compared with AODV, this technique shows better packet delivery ratio, while reducing unnecessary delay and overhead. Also, it is shown that this algorithm works in the multi - path environment.

• V.    CONCLUSIONS

This paper presents the Ant Mobility Model, a multipath routing algorithm for the wireless networks. Thus, AMM can provide loop-free routes, reduces the overhead of the ants, especially forward ants. Furthermore, it offers higher throughput, also.

The good characteristics of AMM include:

• 1.    It increases the throughput and reduces delay, two of the important characteristics required in the wireless networks.

• 2.    AMM prevents stagnation problems in the network, which may further cause congestion.

• 3.    Furthermore, AMM controls congestion that occurs on a node by reducing the load at that node.