# Introduction

n general case, ad-hoc networks are defined as networks formed by users or devices wishing to communicate, without the necessity for the help or existence of any infrastructure or previously established relationship between the potential network members. Ad-hoc communication can take place in different scenarios and is independent of any specific device, wireless transmission technology, network or protocol. Some examples of the possible uses of ad hoc networking include sensor networks, search and rescue operations, vehicle communication networks, and possible military applications, etc.


# a) Overview

In particular, we expect that ad hoc networks will be formed in situations where no infrastructure is available. As for the mode of operation, they are basically peer-to-peer multi-hop wireless networks where information packets are transmitted in a store and forward manner from a source to an arbitrary destination, via intermediate nodes. The network topology changes dynamically and in an unpredictable manner since the nodes can move freely. Therefore, outdated topology information must be updated or removed. Since there is no centralized entity to keep the topology up-to-date, a distributed algorithm is required.

Finding a route to a destination requires exchange of control information among the nodes. Thus, the amount of update traffic can be quite high when the number of highly mobile nodes is large. Thus, the highly dynamic nature of ad hoc networks motivates the study of routing protocols, which aim at achieving routing stability.

Again the wireless communication media has a limited bandwidth, which is susceptive to various interferences that can lead to establishment of useless routes, low throughput and other problems. Some of the protocols assume that the communication links are symmetric. Although this assumption is not always valid, it is usually made because routing in asymmetric networks is a relatively hard task. In certain cases, it is possible to find routes that could avoid asymmetric links, since it is quite likely that these links imminently fail. The issue of symmetric and asymmetric links is one among the several challenges encountered in ad hoc networks. Mobile hosts are powered by battery. Hence, energy efficient routing protocols are required to minimize power consumption.


# b) Desirable Properties of Ad-hoc Routing

As for the mode of operation, ad hoc networks are basically peer-to-peer multi-hop mobile wireless networks where information packets are transmitted in a store-and-forward manner from a source to an arbitrary destination, via intermediate nodes. In such networks, routing decision depends on many factors including topology, selection of routers, initiation of request, and specific underlying characteristic that could serve as a heuristic in finding the path quickly and efficiently. The desirable properties of a routing protocol for ad hoc networks supposed to include the following [1]:


# i. Distributed Operation

The routing algorithm should not be dependent on a centralized controlling node to cope with topological changes.


# ii. Loop Free

The routing protocol must guarantee that the routes supplied are loop-free. This avoids any waste of bandwidth or CPU consumption. iii. Demand based operation To minimize the control overhead in the network and thus not wasting network resources more than necessary, the protocol should be reactive.


# iv. Multiple Routes

To reduce the number of reactions to topological changes and congestion multiple routes could be used.


# v. Unidirectional link support

The radio environment can cause the formation of unidirectional links. Utilization of these links along with the bi-directional links can improve the routing protocol performance.


# vi. Security

The radio environment is especially vulnerable to impersonation attacks. So to ensure the wanted behavior from the routing protocol, we need some sort of preventive security measures. vii. Power Conservation viii. Quality of service support Some sort of Quality of Service support is probably necessary to incorporate into the routing protocol. It could for instance be real-time traffic support. There are several routing protocols proposed for usage in ad-hoc networks. None of the proposed protocols have all the desirable properties.


# II.


# Ad Hoc Routing Schemes

Most of these protocols are designed for IP (Internet Protocol) based homogenous, mobile adhoc networks [2]. Each node in the network has identical capability (identical communication devices and ability to perform functions from the common set of services). It is assumed that each node has a unique address (IP address for example). Number of hops is used as the only route selection criteria. These protocols focus on fast route establishment and reestablishment and route maintenance with minimal overhead.

A majority of these ad hoc routing protocols can be classified as either proactive (table-driven) protocols or reactive (demand-driven) protocols. In either case, the routing protocols typically specify that each node periodically advertise current routing information to its neighbors. The neighbor is then able to calculate routes to network nodes based on the received information. The node can also incorporate the information it has received into its own advertisements, as necessary according to the protocol. In the case of proactive protocols, the advertisements can contain information about every known link between other routing agents in the network. Reactive protocols, on the other hand, supply next-hop information about all destinations in the network. However, due to high mobility of nodes such periodic advertisements may impact route maintenance overhead of routing protocols in such a way that no bandwidth might remain leftover for the transmission of data packets. Two techniques for solving this problem are to limit the amount of information advertised and to establish routes only on demand so that periodic advertisements are no longer mandatory.

Routing schemes solely inspired from the biological swarm intelligence can adapt to the changing network requirements by means of the principle of emergence via "stigmergy". There are few routing schemes based on swarm intelligence proposed for ad hoc networks.


# III.


# Swarm Intelligence and Ad Hoc Routing

Swarm intelligence [3] refers to the "intelligent" behaviors arising from the interactions among a swarm of social insects, such as ants, when working collectively towards a common goal, e.g., food foraging. Ants can find shortest paths through a process called "stigmergy", which could be described as indirect communication between individuals through the environment.


# a) Basic ant algorithm

The basic idea of the ant algorithm is taken from the food searching behavior of real ants. When ants search for food, they start from their nest and walk toward the food. When an ant reaches an intersection, it has to decide which branch to take next. While walking ants deposit pheromone which marks the selected route. The concentration of pheromone on a certain path is an indication of its usage. Other ants are attracted by these pheromone trails and in turn reinforce them even more. As a result of this autocatalytic reaction, the shortest path emerges rapidly. .1 shows a scenario with two routes from the nest to the food. At the intersection the first ants randomly select a branch. Since the lower route is shorter than the upper one, the ants, which take this path, will reach the food place first. On their way back to the nest, the ants again have to select a path. After a while the pheromone concentration on the shorter path will be higher than on the longer path, because the ants

The nodes in an ad-hoc network are very limited in battery power. Nodes use some sort of stand-by mode to save power. The routing protocol must have support for these sleep-modes.


# Global Journal of Computer Science and Technology

Volume XIII Issue V Version I
26 ( D D D D D D D D )
Year using the shorter path will increase the pheromone concentration faster. Thus, eventually all ants will only use this path. This behavior of the ants can be used to find the shortest path in networks. Especially the dynamic component of this method provides for a high degree of adaptation to changes in mobile ad-hoc network topology, since in these networks the existence of links is not guaranteed and link changes occur frequently.

Swarm intelligence boasts a number of advantages due to the use of mobile agents and stigmergy [4]. These include: i. Scalability Population of the agents can be adapted according to the network size. Scalability is also promoted by local and distributed agent interactions.

ii. Fault Tolerance Swarm intelligent processes do not rely on a centralized control mechanism. Therefore the loss of a few nodes or links does not result in catastrophic failure, but rather leads to graceful, scalable degradation.


# iii. Adaptation

Agents can change, die or reproduce, according to network changes.


# iv. Modularity

Agents act independently of other network layers [11].


# v. Autonomy

Little or no human supervision is required.


# vi. Parallelism

Agent's operations are inherently parallel. These properties make swarm intelligence very attractive for ad-hoc wireless networks. b) A simple ant-based scheme Let G = (V, E) be a connected graph with n = |V| nodes. The simple ant colony optimization metaheuristic can be used to find the shortest path between a source node vS and a destination node vD on the graph G. The number of nodes on the path gives the path length. A variable j ij (artificial pheromone), which is modified by the ants when they visit the node is associated with an edge e(i, j) Î E of the graph connecting the nodes vi and vj . The pheromone concentration j ij is an indication of the usage of this edge. Initially j ij is constant for each edge e(i, j). An ant located in node vi uses pheromone j ij of node vj Î Ni to compute the probability of node vj being the next hop. Ni is the set of one-step neighbors of node vi. The transition probabilities Pi,j of a node vi, i.e. the probability that the ant selects node vj after it has visited vi, are defined as follows:

During the route finding process, ants deposit pheromone on the edges. In the simplest version of the algorithm, the ants deposit a constant amount Dj of pheromone, i.e. the amount of pheromone of the edge e(vi, vj) when the ant is moving from node vi to node vj is changed as follows:

Like real pheromone the artificial pheromone concentration decreases with time. In the simple ant algorithm this is described by:

The simple ant algorithm shown in this section illustrates different reasons why this kind of algorithms could perform well in mobile multi-hop ad-hoc networks. These include the following:

? Ant-based can show better adaptation to continuously changing network topologies in multihop ad-hoc networks [4,5]. ? In contrast to other routing approaches, the ant based algorithm is based only on local information, i.e. no routing tables or other information blocks have to be transmitted to other nodes of the network. ? It is possible to integrate the link quality into computation of the pheromone concentration, especially into the evaporation process. This will improve the decision process with respect to the link quality. It may be noted that the approach can be modified so that nodes can also manipulate the pheromone concentration independent of the ants, e.g. if a node detects a change of the link quality.

? Each node has a routing table with entries for all its neighbors, which also contains the pheromone concentration. The decision rule for selection of the next node is based on the pheromone concentration at the current node, which is provided for each possible link. Thus, the approach supports multi-path routing.


# c) Ant-based Routing in Ad hoc Networks

Several variations of Ant Net [5,6] have been developed but all of them rely on the same concept where forward ants are launched towards destinations and backward ants travel back and update pheromone along the backward paths. The amount of added pheromone is proportional to the goodness of the path measured by the forward ant. In the following sections some of these routing schemes are discussed. Route maintenance, and Route failure handling. Each of these phases is discussed briefly in this section.


# a. Route Discovery

In ARA new routes are created in the route discovery phase by means of a forward ant (FANT) and a backward ant (BANT). A forward ant is an agent, which establishes the pheromone track back to the source node. In analogous, a backward ant establishes the pheromone track back to its origin, namely the destination node.

The FANT is a small packet with a unique sequence number. Nodes are able to distinguish duplicate packets on the basis of the sequence number and the source address. A node that receives a FANT for the first time creates a record in its routing table. The node interprets the source address of the FANT as destination address, the address of the previous node as the next hop, and computes the pheromone value depending on the number of hops it took the FANT to reach the node. The node then relays the FANT to its neighbors. Duplicate FANTs are identified through the unique sequence number, and are removed. The destination node extracts the information of the FANT, creates a BANT and returns it to the source node. The BANT's task is to establish a track to source node. When the sender receives the BANT from the destination node, the path is established and data packets can be sent.    If there is another route to the destination it will send the packet via this path. Otherwise, the node informs its neighbors, hoping that they can forward the packet to the destination. Either the packet can be transported to the destination node or the backtracking continues to the source node. If the packet does not reach the destination, the source node has to initiate a new route discovery process.


# d. Properties of ARA

Each node controls the pheromone counter independently when ants visit the node on route search for, or when the node detects a link failure. Route finding process is performed on-demand basis when the pheromone entry for the target at sender node is below threshold.

Nodes are able to function sleep-mode when the amount of pheromone in their routing table has reached a lower threshold. Other nodes will then not consider this node, unless packets are destined to it. This saves energy and power.


# Global Journal of Computer Science and Technology

Volume XIII Issue V Version I ARA supports multipath routing. Each node can have several paths to a destination and the choice of a certain route depends on the environment, e.g. link quality to the relay node. In case of link failure the alternative routes when available can be used without going for a costly route discovery process.

ARA, however, because ants are broadcasted into the network for on-demand route-discovery, may not scale for large-scale mobile ad hoc networks.

ii. Scalable Ant-based Routing Protocols a. Adaptive-SDR Protocol

The same concept as in AntNet [6] has been extended and applied to Adaptive Swarm-based Distributed Routing (Adaptive-SDR) [8] for routing in wireless and satellite networks. Adaptive-SDR resolves the scalability limitations of AntNet by incorporating a mechanism to cluster nodes into colonies.

Clustering is performed less frequently, in the beginning stage of the algorithm and whenever the network topology changes enough to justify a reclustering of the nodes. Then, it finds routes in network by using special agents called ants and forwards the network traffic using the routes discovered by the ants. The route discovery (by ants) and the network data traffic forwarding are performed constantly as part of regular network operation.

Adaptive-SDR is scalable and can avoid routing loops. In addition this scheme performs well with high utilization of the network capacity. By monitoring the state of the queues of the links to all outgoing neighbors, the next-hop probabilities are adjusted according to the load in each queue. Then, the node with the highest adjusted probability is selected as nexthop. This probability adjustment is only temporary and for the purpose of forwarding data at that specific time instant. It does not permanently change the routing table probabilities. The advantage of this method is that the best next hop is penalized when it is congested, while it is still the best, and thus always chosen, when there is no congestion. b. GPS/Ant-Like Routing Algorithm GPS-AL is a source routing scheme in which the network relies on location information and support from fixed infrastructure [9]. The routing protocol is based on the physical location of a destination host d stored in the routing table. If there is an entry in the routing table for host d, the best possible route is chosen using a shortest path algorithm. The route comprised of a list of nodes and the corresponding TTL's, is attached to the packet, which is sent to first host in the list. If host d is not found in the routing table, the mobile node sends a message to the nearest fixed node that tries to find the destination node. GPS-AL employs ants during route discovery only to accelerate the dissemination of routing information, and hence, does not make use of the above-described "autocatalytic" effect for finding shortest paths. Hence, ants are not used as feedback agents to reinforce routes positively (in the case when a route is still good), negatively (when a route is no longer good) or explore new routes randomly -ants in this approach are unicasted to specified direction, not allowing for amplification of fluctuations, and depending on known metrics such as timestamp of a route in the routing table. Further, a shortest path algorithm is applied to determine the best possible route to a destination, therefore assuming that a node knows a lot about the links currently present in the network, and as well a lot about positions of other nodes, which certainly will not be true for the large scale ad hoc networks.


# c. Mobile Agent Based Routing (MABR)

MABR is a proactive approach [10] for routing in large-scale mobile ad hoc networks. The nodes are assumed to be aware of their position by means of a positioning service (e.g., GPS) and are able to determine other nodes position accurately enough through a location management scheme. This scheme uses a two-layered architecture, as shown in Figure 3.4, where TAP (Topology Abstracting Protocol) is used to supply a simplified topology with fixed "logical routers" and fixed "logical links". A logical router represents an aggregated collection of mobile hosts, which all together build and share among each other the same routing tables. A logical link represents a path along a roughly straight line to a distant logical router over possibly multiple hops. On top of this abstract topology the actual routing protocol MABR (Mobile Ants Based Routing) runs and is responsible for updating the routing tables of logical routers and determining logical paths for routing packets over this abstract topology. MABR Finally, the StPF (Straight Packet Forwarding) protocol is applied in order to transmit packets over a logical link. Therefore, it forwards packets along this logical link in a greedy manner.

Each node is at every moment part of a specific logical router and, hence, makes uses of the corresponding routing tables. So when a node whishes to send a packet to another node, it first discovers that node's location through any location management scheme [10] and stores these coordinates in the header fields of the packet. By applying MABR, it determines to which zone the destination coordinates belong in its view and selects any logical link with the probability given in the routing table R for that zone. The packet is tagged as well with the corresponding logical router k (geographical coordinates) as a next logical hop. Then SPF is employed in order to route the packet to these coordinates; i.e. the source node transmits the packet to a node closer to logical router k and so forth. Any node at logical router k in turn carries out the same procedure again, first determining a next outgoing logical link by MABR, and then routing the packet to these coordinates by SPF. Eventually the packet will arrive at the logical router for the destination coordinates. The receiving node finally sends the packet to the intended destination node.

The advantages include the ability to react and deal quickly with local and global changes, not only in the network topology, but as well in the communication bandwidth, in the transmission delay, etc. However, with this approach no random exploration of routes is possible. Also, in a network where the topologies change frequently, the overhead of doing proactive routing may far outweigh the benefits of doing so.

IV.


# Conclusion

In this paper, we have presented an overview of swarm intelligence applied to routing schemes in ad hoc networks. Inherent properties of swarm intelligence as observed in nature include: massive system scalability, emergent behavior and intelligence from low complexity local interactions, autonomy, and stigmergy, or communication through the environment. These properties are desirable for many types of networks. Ant-based approaches hold great promise for solving numerous problems of adhoc power aware networks. 
31![Figure 3.1 : All ants take the shortest path after an initial searching timeFigure3.1 shows a scenario with two routes from the nest to the food. At the intersection the first ants randomly select a branch. Since the lower route is shorter than the upper one, the ants, which take this path, will reach the food place first. On their way back to the nest, the ants again have to select a path. After a while the pheromone concentration on the shorter path will be higher than on the longer path, because the ants](image-2.png "Figure 3 . 1 :")
3![2 shows the establishment of the pheromone track back to the source node S. The forward ant only creates one pheromone track to the source node in node 6, but two tracks in node 5, via node 3 and node 4.](image-3.png "Figure 3 .")
3![3 depicts analogous situation for the backward ant. It only creates one pheromone track to the destination node D in node 5 and two tracks in node 6. Thus, ARA also supports multi-path routing. b. Route Maintenance For maintenance of the routes during the communication ARA does not need any special packets. Once the FANT and BANT have established the pheromone tracks for the source and destination nodes regular data packets are used to maintain the path. As in biological systems, established paths do not keep their initial pheromone values forever. When anode vi relays a data packet to destination vD to a neighbor node vj, it increases the pheromone value of the entry (vD, vj, j) by Dj, i.e. this path to the destination is strengthened by the data packet. Likewise, the next hop vj increases the pheromone value of the entry (vD, vj, j) by Dj, i.e. the backward path to the source node is also strengthened. The evaporation process of the real pheromone is modeled by decreasing the pheromone values according to equation 1.](image-4.png "Figure 3 .")
32![Figure 3.2 Route discovery phase. A forward ant (F) is send from the sender (S) toward the destination node (D). The forward ant is relayed by other nodes, which initialize their routing table and the pheromone values.](image-5.png "Figure 3 . 2")
33![Figure 3.3 Route discovery phase. The backward ant (B) has the same task as the forward ant. It is send by the destination node toward the source node. c. Handling Route Failure Routing failures, which are especially caused by node mobility, are very common in ad-hoc networks. ARA assumes IEEE 802.11 on the MAC layer. This enables ARA to recognize a route failure through a missing acknowledgement on the MAC layer. If a node receives a ROUTE_ERROR message for a certain link, it first deactivates this link by setting the pheromone value to 0. Subsequently, the node searches for an alternative link in its routing table.If there is another route to the destination it will send the packet via this path. Otherwise, the node informs its neighbors, hoping that they can forward the packet to the destination. Either the packet can be transported to the destination node or the backtracking continues to the source node. If the packet does not reach the destination, the source node has to initiate a new route discovery process.](image-6.png "Figure 3 . 3")
34![Figure 3.4 : Two layer architecture proposed for Ant based Routing in[10] ](image-7.png "Figure 3 . 4 :")
![Swarm intelligence however is a new field and much work remains to be done. Comparison of the performance of swarm based algorithms has been done by emulation. Analytic proof and models of the swarm based algorithm performance remain topics of ongoing research.](image-8.png "")
			© 2013 Global Journals Inc. (US) Ant-based Routing Schemes for Mobile Ad Hoc Networks
			© 2013 Global Journals Inc. (US)
		
		
			

				


* 
	
		Ad hoc mobile wireless networks: protocols and systems
		
			CToh
		
		
			2002
			Prentice Hall
		
	




* 
	
		Swarm Intelligence -From Natural to Artificial Systems
		
			EricBonabeau
		
		
			MarcoDorigo
		
		
			GuyTheraulaz
		
		
			1999
			Oxford University Press
			New York
		
	




* 
	
		Mobile agents in telecommunications networks -a simulative approach to load balancing
		
			SLipperts
		
		
			BKreller
		
	
	
		Proc. 5th Intl. Conf
				5th Intl. Conf
		
	




* 
	
		AntNet: A Mobile Agents Approach to adaptive Routing
		
			DiGianni
		
		
			MarcoCaro
		
		
			Dorigo
		
		IRIDIA/97-12
		
			Belgium
		
		
			Universite Libre de Bruxelles
		
	
	Technical Report




* 
	
		AntNet: distributed stigmergetic control for communications networks
		
			G
		
		
			DiCaro
		
		
			MDorigo
		
	
	
		Journal of Artificial Intelligence Research
		
			9
			1998
		
	




* 
	
		ARA: The Ant-colony Based Routing Algorithm for MANETs
		
			MesutGunes
		
		
			UdoSorges
		
		
			ImedBouazizi
		
	
	
		International Conference on Parallel Processing Workshops (ICPPW'02)
				Vancouver, B.C., Canada
		
			August 2001
		
	




* 
	
		Adaptive-SDR: Adaptive Swarm-based Distributed Routing
		
			NIoannis
		
		
			Kassabalidis
		
	
	
		IEEE WCCI 2002
				Honolulu, Hawaii
		
			May 2002
		
	




* 
	
		A GPS/Ant-Like Routing Algorithm for Ad Hoc Networks
		
			DanielCamara
		
		
			AntonioAlfredo
		
		
			FLoureiro
		
	
	
		IEEE Wireless Communications and Networking Conference (WCNC'00)
				Chicago, IL
		
			September 2000
		
	




* 
	
		Ants-Based Routing in Large Scale Mobile Ad-Hoc Networks
		
			MHeissenbttel
		
		
			TBraun
		
		
			2003
		
		
			University of Bern
		
	
	Technical report




* 
	
		An agent-based routing
		
			KOida
		
		
			MSekido