Abstract: A mobile ad-hoc network is a self configuring network connected by wireless links. No infrastructure or central administration is needed for these type of networks. Therefore, they are suitable only for temporary communication links. An important issue in computer network is to design the network in such a way to cope up with the speed required today. The task of routing the packets from a source to the particular destination in ad-hoc networks is hard because the network elements are mobile and there is no central control over the network elements. In any network, the data packets have to be routed to the destination with minimum loss, minimum delay and maximum packet delivery ratio. Therefore, there must be an efficient routing algorithm which satisfies all these quality of service requirements and it must also be robust and adaptive. The algorithm Multi Agent Ant Based Routing Algorithm is designed from the ACO framework, inspired by the behavior of biological ants. The algorithm consists of both reactive and proactive components. This technique increases node connectivity and decreases average end to end delay and increase packet delivery ratio. Since node connectivity increases, packet loss is reduced. The simulations are carried out by NS-2 and the results prove that Multi Agent Ant Based Routing Algorithm outperforms AntHocNet, AODV and DSR in terms of average end to end delay and packet delivery ratio.

INTRODUCTION

A Mobile Ad-hoc Network (MANET) consists of a set of mobile nodes that are equipped with wireless transmitters and receivers. These nodes communicate with each other without the help of any wired base stations. Nodes can join or leave at any time. In this network, each mobile node operates not only as a host but also as a router, forwarding packets from other mobile nodes in the network that may not be within direct wireless transmission range of each other. All nodes are equal and they do not have any centralized control. The idea of ad-hoc networking is called as infrastructure less networking, since the mobile nodes in the network dynamically establish routing among themselves to form their own network.

A challenge in the design of ad-hoc networks is the development of dynamic routing protocols that can efficiently find routes between two communicating nodes. Routing is the task of directing data flow from source to destination maximizing network performance. The routing protocol must be efficient to route the packets to the particular destination even when the nodes are mobile and the network topology changes drastically and unpredictably (Royar, 1999). This means that routing information should be updated more regularly than in wired networks. Numerous routing algorithms exist to allow networking under various conditions. These algorithms can be separated into three groups: proactive, reactive and hybrid algorithms. Proactive algorithms maintain continuously updated state of the network and the existing routes however in some cases it generates an unnecessary overhead to maintain routing tables. In the case of reactive routing algorithms, routing tables are created only on demand. Reactive routing algorithms require time consuming route creations that may delay the actual transmission of the data when sources have no paths towards their destination. Therefore hybrid routing algorithm is suitable to route packets for real time data and multimedia communication. This study provides the description of Multi Agent Ant Based Routing Algorithm, an ant inspired hybrid routing scheme based on Ant Colony Optimization to profit the advantages of both reactive and proactive algorithms. The performance of Multi Agent Ant Based Routing Algorithm is compared with the traditional algorithms and the results show that Multi Agent Ant Based Routing Algorithm performs well compared to AntHocNet, Ad-hoc On Demand Distance Vector Routing algorithm (AODV) and Dynamic Source Routing (DSR) algorithm. AntNet is an adaptive routing algorithm used to solve routing problems in wired networks (Dhillonand and van Mieghem, 2007). This algorithm is inspired by the behavior of Ants. An AntNet node maintains routing tables in which the goodness value of each output link is maintained for each destination. A forward ant packet is sent to random destinations periodically. These forward ants are used to find the feasible path between the source and destination. Once the forward ant reaches the destination, it is converted into a backward ant. The backward ant travels to the source from the destination and also updates the routing table of the intermediate nodes. The goodness value is called pheromone. The pheromone is used to route packets and ants.

MANET ROUTING PROTOCOLS

Many routing protocols have been proposed for MANETs. These protocols are separated into three groups periodic or proactive, on demand or reactive and hybrid protocols. Proactive protocols maintain a continuously updated state of the network. In case of frequent topology changes, overhead is increased to maintain the tables with updated information. Due to frequent changes in network topology, increased overhead, there may be delay in data packets or even it causes packets to be dropped. Therefore, performance of the network will be reduced. Examples of proactive protocols are Destination-Sequenced Distance Vector Routing Protocol (DSDV) and Wireless Routing Protocol (WRP). Therefore, reactive protocols are in general more scalable. Reactive protocols create and maintain routes only on demand and do not try to maintain an overview over the network.

That is routes are maintained only when there is a requirement to send data from a source to a particular destination. Route discovery is done by flooding a route request packet through the network. Examples of reactive protocols are AODV (Perkins and Royer, 1999) routing protocol and DSR (Johnson and Maltz, 1996; Kaosar et al., 2006) protocol. Hybrid algorithms like Zone Routing Protocols (ZRP) combine the best of both the proactive and reactive components. Most of the algorithms are single path and use only one path at a time.

ANT COLONY OPTIMIZATION

A colony of harvester ants has a wide range of duties like collecting food, building the nest, removing the dead ants and they have very simple 1-1 communication. Here the individual messages passed between the ants are very insignificant but the collective messages help in co-ordinate work control of ants without the presence of a centralized control system. The inspiring source of ACO is the pheromone trail laying and following behavior of real ants which use pheromone as a communication medium. The pheromone trails in ACO serve as distributed, numerical information which the ants use to probabilistically construct solutions to the problem being solved (Gunes et al., 2002; Dorigo et al., 2000).

Consider an example of food collection. Initially the ants spread out in all directions in search of food. When an ant finds a food source, it collects the food and on returning back marks the trail with pheromones. These pheromones are dropped at regular intervals to act as a trail. Also the pheromones slowly disappear over time. So, they act as a guiding train to other ants which begin to follow this path. In the same way, ants which trace a particular path strengthen the pheromone on the path. In this way, a number of paths might exist from the nest to the food source. Also the shortest path will be the one with the highest pheromone and also the path with the highest concentration of ants.

At the same time, multiple trails exist from the nest to the food source. When a previously short route get blocked due to an obstacle, the alternate short route get strengthened with higher pheromone content due to shorter average end to end travel time and more ants move to this route. Hence the path can also dynamically adapt to fast changes in the environment. This behavior of ants is used to find the shortest path in networks especially the dynamic component of this method allows a high adaptation to changes in mobile ad-hoc network topology since link changes occur very often in these networks (Mueller et al., 2004). An ant when moving from source S to destination D collects information about the quality of the path such as hop, average end-to-end delay, cost and when the same ant retraces its path back to the source uses these information to update its routing tables in the intermediate nodes.

MULTI AGENT ANT BASED ROUTING ALGORITHM

Multi Agent Ant Based Routing Algorithm (MAARA) is a hybrid algorithm that combines ant based routing and multi agent systems. In this technique node connectivity is increased which in turn decreases average end to end delay and increase packet delivery ratio. Since node connectivity increases packet loss is reduced. Route establishment in ant based routing technique is dependent on the ants visiting the node and providing it with routes. If a node wishes to send data packets to a destination for which there is no route, it keeps the data packets in the buffer till an ant arrives and then it provides a route to the destination. In ant routing algorithms implemented so far there is no local connectivity maintenance as in AODV. So, the number of packets have been dropped.

AODV takes time for connection establishment and also there is a delay in new route discovery process whereas in multiagent ant based routing if a node has a route to a destination it just starts sending data packets without any delay (Mueller et al., 2004; Ducatelle et al., 2005; Srisathapornphat and Shen, 2003).

MAARA is a routing algorithm which uses both proactive and reactive components while establishing routing paths between a source and destination pair. The algorithm is proactive, since the nodes establish path only when there is a requirement for communication between a source and destination. It is reactive in the sense that the nodes maintain routing table till the end of the communication session (Kassabalidis et al., 2001). The routing algorithm consists of 5 phases such as:

Route discovery: To start a communication, new routes are needed between a source destination pair. New routes are created in route discovery phase. The source node starts a reactive path setup phase in which ants called forward ants are spread over the network to find the destination. When the ants reach the destination, the first ant that reached the destination is the reactive backward ant which is returned back from D-S and it updates the routing table entries in each node.

The forward ant is a small packet with a unique sequence number. Nodes will distinguish duplicate packets based on the sequence numbers and source address. The backward ant enters the destination address, the next hop and the pheromone value in the routing table. Duplicate ants are identified through unique sequence number and removed. When sender receives the backward and from the destination node, the path is established and data packets can be sent.

Route updation: When a source node S starts a communication session with a particular destination D and no routing table is available in the intermediate nodes then the source node S broadcasts a reactive forward ant. The forward ant may be unicast or broadcast based on the information for D in the neighboring nodes. If the routing table contains information about the next hop to reach the destination D then the ant chooses its next hop to reach the destination D with the probability:

(1)

where, Nⁱ_d is the set of neighbors of i over which a path to D is known. β is a parameter that controls the exploratory behavior of the ants. Since the packets are broadcasted, more number of duplicate copies appears in one node if so only one copy will be taken and all others will be discarded. The copy of the ant is discarded based on the generation number. A reactive forward ant contains the following information: source address, destination address, generation number, trip time, list of visited nodes, number of nodes visited and a flag for reactive backward ant generation at the intermediate node. The ants that have the same source address, destination address and generation numbers are called as same generation ants. Using this concept, only one path is set up initially. More number of paths is added during the course of the communication session with the help of proactive path maintenance mechanism. Each forward ant maintains the list of nodes it visited. When the ant reaches its destination it is converted into a backward ant. When it retraces its path back to source S from the destination D it updates the entry T_i^nd in the i’s pheromone table. The pheromone value T_i^nd is the running average of the inverse of the cost, in terms of both estimated time and number of hops to travel to D through n. If is the traveling time estimated by the ant and h is the number of hops then is used to update the running average:

(2)

where, T_hop is the time taken for one hop in unloaded condition. The value of T_hop is the time taken for one hop in unloaded condition. The value of is updated as:

where, α is taken as 0.7 in the experiment.

Data routing: After setting up paths to the destination, data packets are forwarded based on the pheromone values in the routing table. If the node has multiple paths to the destination, it selects the next hop on random with the probability given in Eq. 1. The probabilistic routing strategy leads to data load spreading with consequent automatic load balancing. When a path is worse than others it will be avoided and its congestion will be relieved. Other paths will get more traffic, leading to higher congestion which in terms increases average end to end delay. By continuously adapting the data traffic, the nodes try to spread the data load evenly over the network. Load balancing is important in MANETs because the bandwidth of the wireless channel is very limited. Therefore, the quality of different paths is frequently monitored with the use of proactive ants (Kwang and Sun, 2003; Rajagopalan ad Shen, 2006).

Route maintenance: A source node dispatches proactive forward ants periodically at the rate according to the data sending rate to maintain the established paths and to find better paths. A proactive forward ant can be unicast probabilistically or be broadcasted. It collects up to date information about the established path and updates the pheromone values of the path by the corresponding proactive ants. A backward ant does the same for the direction from the destination back to the source. If an ant got broadcast at any point, it will leave the currently known pheromone trails and explore new paths. The ant will arrive in all the neighbors of the broadcasting node after a broadcast. If it does not find any pheromone pointing towards the destination then it will be broadcast again. The ant will quickly proliferate and flood the network, like a reactive forward ant. Here the number of broadcast is limited to two, in order to avoid proliferating.

Route failure handling: Route failures are caused especially through node mobility which is common in ad-hoc networks. Link failures are detected when unicast transmission fail or when unexpected periodic pheromone diffusion messages were not received. When a node discovers the disappearance of a neighbor it removes the neighbor from its neighbor list and all the associated entries from its routing table. All its neighbors receive the message and update their pheromone table using the new values. If they lost their best path to the destination due to failure, they will broadcast the notification further until all concerned nodes are notified of the new situation.

If a node detects link failure through the failed transmission of a data packet and it has no further paths available for the destination of this packet it starts a local route repair. The node broadcasts a route repair ant that travels to the involved destination like a reactive forward ant. It follows available routing information when it can and it broadcasts otherwise. If local repair fails, the node broadcasts a new link failure notification message to warn its neighbors.

SIMULATION ENVIRONMENT

Network Simulator, NS-2 simulation software is used. The algorithm MAARA is simulated in a number of simulation environments (Ahmed, 2005). The performance of the algorithm is compared with routing algorithms such as AODV, DSR and AntHocNet. The algorithms are evaluated in terms of average end to end delay, packet delivery ratio and packet loss. As many as 100 nodes are placed randomly in a rectangular area of 3000x1000 m². In this 20 nodes are taken as sources which transmits packet at a constant bit rate. Size of each packet is 64 bytes. Each experiment is simulated for 900 sec. Each source starts sending packets randomly between 0 and 60 sec after the start of the simulation. Two-ray signal propagation model is chosen at the physical layer. Coverage of each node is 300 m and data rate is set to 2 Mbits sec^-1. For MAC layer 802.11 b protocol is used. Random Way Point mobility model is used for the movement model where the maximum speed is varied from 1-20 m sec^-1 and the pause time is 30 sec. In Random Way Point model the nodes choose a random destination point and a random speed, move to the chosen point with the chosen speed and rest there for a fixed amount of pause time before they choose a new destination and speed. Average end to end delay for routing data packets from source to destination and packet delivery are considered as performance measures. Different levels of mobility are given by varying the pause time. When pause time is higher, it means lower mobility and also lower connectivity.

PERFORMANCE ANALYSIS

The experiments are done with 100 nodes in a rectangular area of 3000x1000 m². The number of nodes is increased from 10-700 nodes. The results shown in Fig. 1 shows that as the number of nodes in the network increases the packet delivery ratio also increases. After reaching the maximum utilization of bandwidth if the number of nodes are increased further the packet delivery ratio decreases slowly. This is because of congestion present in the network whenever there is an increase in traffic between the particular source and destination.

Fig. 1:	Number of nodes vs packet delivery ratio

Fig. 2:	Number of nodes vs average end to end delay

Fig. 3:	Pause time vs packet delivery ratio

Figure 2 shows the variation in average end to end delay when the number of nodes in the network is varied. Here when the number of nodes increases from a minimum value to a maximum value the average end to end delay also increases.

But when the number of nodes is increased beyond a certain value the delay remains almost constant. The second experiment was conducted by varying the pause time. The packet delivery ratio for various pause times is shown in Fig. 3. This graph shows that when there is an increase in pause time packet delivery ratio increases due to slow movement of the nodes.

CONCLUSION

In this study, a multi agent ant based routing algorithm for Mobile ad-hoc networks, an ACO frame work is described. It is a hybrid algorithm, combines the concepts of multi agents and ant algorithm. The concepts of routing are combined with ACO. In routing algorithm this combines both proactive and reactive components together and forms a hybrid routing algorithm. In simulation experiments it is proved that the proposed algorithm outperforms AntHocNet, AODV and DSR algorithms in terms of packet delivery ratio and average end-to-end delay, especially when the number of nodes is increased and the nodes are more mobile. From the simulation results it is clearly understood that the proposed algorithm outperforms other algorithms such as AntHocNet, AODV and DSR in terms of packet delivery ratio and average end to end delay.

ACKNOWLEDGEMENTS

The researchers like to thank the management of Arulmigu Kalasalingam College of Engineering, Krishnankoil, India for the support and facilities provided to carry out this research.