Survey of reactive and hybrid routing protocols for Mobile Ad Hoc Networks.
Mobile Ad Hoc Networks (MANETs) are wireless networks formed by several nodes communicating on a peer-to-peer basis without being connected to any fixed infrastructure. These nodes could be laptop computers, personal digital assistants, mobile phones or sensors dispersed in an area to measure certain data and send the information to a larger node. Where a source node and a destination node are not within direct range, they communicate through multi-hop routing, i.e. nodes in between them relay messages between source and destination. There are numerous situations in which MANETs can be very useful, some of these are: emergency and rescue situations, military applications, conferences and sensor networks [1,2]. There are characteristics of MANETs that make their operations more complicated than ordinary infrastructure networks, these include: mobility, limited resources, high error rates due to broadcast nature of radio channel, limited bandwidth, hidden and exposed terminal problem and of particular interest here routing [1,3,12,21].
The rest of the paper is organized as follows. Section 2 presents routing in MANETs. A closer look at the selected protocols is discussed in Section 3. Comparison of the selected protocols is presented in Section 4 and concluding remarks are made in Section 5.
2. Routing in MANETs
Routing protocols in MANETs are responsible for deciding on the best (multi-hop) paths to send data across from source to destination. Soon after the introduction of MANETs, it became evident that routing protocols used for wired networks are not suitable for MANET applications, because of the constraints described in Section 1. Initially, MANET-versions of popular wired network routing protocols were introduced, but these were not very efficient. Examples include Destination-Sequenced Distance Vector (DSDV) protocol and Optimized Link State (OLSR) protocol, which are optimized versions of distance vector and link state routing protocols commonly used in wired networks. Numerous MANET-specific routing protocols were later developed to provide more efficient routing. In the remainder of this section, the different ways of classifying MANET routing protocols will be discussed, as well as the main routing approaches commonly used.
Because there are so many routing protocols used in MANETs, using different operating principles, there are several ways of classifying them, and each protocol does not necessarily have to belong to only one category. A detailed hierarchical categorization is presented in , based on the communication model (whether the protocol is multi channel or single channel), structure in terms of whether all nodes are treated uniformly, state information (i.e. whether nodes maintain information about the whole network topology, or a limited amount of information about their neighbors) and finally routing information update mechanism. This classification approach is illustrated in Figure 1.
2.1 Communication Model
A routing protocol can be either designed for single channel or multi channel communications. Multi channel communications are used mainly in Time Division Multiple Access (TDMA) and Code Division Multiple Access (CDMA). Single channel communications refer to networks that use Carrier Sense Multiple Access--Collision Avoidance (CSMA/CA), such as IEEE 802.11 wireless networks. The scope of this paper is limited to single channel networks .
[FIGURE 1 OMITTED]
This includes two protocol categories; uniform protocols treat all nodes in the same manner, unlike non-uniform protocols. Non-uniform protocols are further divided into neighbor selection and partitioning. In neighbor selection, such as Zone Routing Protocol (ZRP) nodes treat other nodes differently depending on whether they are classified to be "nearby" or "distant" nodes. Partitioning protocols, such as Cluster Based Routing Protocol (CBRP) assign or select "special" nodes, which are often ones with more resources, to perform additional tasks or have access to more routing information .
2.3 State Information
State information involves the scale or scope of the topology information nodes are required to maintain. This includes topology based protocols, such as DSR, where nodes are required to know large scale routing information about the network, and destination based protocols, such as DSDV and AODV, where nodes only have to know routing information related to the next hop . Source routing protocols come under topology based protocols, because a source node has to know the whole route to the destination.
2.4 Routing Information Update Mechanism
This includes the three main categories of MANET routing protocols; proactive, reactive and hybrid. Proactive protocols (also called table-driven) attempt to maintain routing information for all nodes in the network at all times, whether this information is required or not. To do so, nodes using proactive protocols have to exchange periodic hello messages to update their routing tables. The advantage of the proactive approach is that it eliminates the initial delay that occurs before data transmission begins as the source node looks for a route to the destination. However, it has the disadvantage of unnecessarily loading the network and using up resources by maintaining information that might not be used. Examples of proactive protocols are DSDV and OLSR . Reactive protocols (also called on-demand protocols) discover routes on the fly whenever they are required. This way, they do not have to exchange update messages regularly, but may suffer from additional latency as a route to the destination has to be discovered before data transmission begins. Examples of popular reactive protocols are DSR and AODV. Hybrid protocols try to combine the best of both worlds; they maintain routing information proactively for nodes within their "routing zones", and reactively for nodes outside their routing zones. These routing zones could be based on hop distance or geographical locations. Popular hybrid protocols include Zone Routing Protocol (ZRP) and Fisheye State Routing (FSR) .Some protocols also set up paths to destinations reactively, and then once a path is set they update it proactively. This approach is used in AntHocNet.
3. Selected Protocols
This section takes a closer look at some of the famous, more efficient and more interesting MANET routing protocols, particularly the reactive ones. These are DSR, AODV, SMR, SMS and AntHocNet. Besides AntHocNet, which is a hybrid protocol, all other protocols discussed here are reactive. Other protocols of interest are DYMO [5,19], EARA-QoS  and HOPNET .
3.1 Dynamic Source Routing (DSR)
Dynamic Source Routing (DSR) is one of the most popular MANET routing protocols, and several newer protocols are based on its operation. It is a reactive source routing protocol, i.e. it only discovers routes when they are required, and the source knows the whole path to the destination, not just the next hop because the routing and data packets include the whole path from source to destination [1,3,8]. DSR consists of route discovery and route maintenance phases .
3.1.1 Route Discovery
When a source wants to send data to a destination, it first checks its routing cache for a valid route to the destination. If it finds a route it uses it to unicast the data packet(s) to the destination. If not, it starts a route discovery process by sending a Route Request packet (RREQ) to its neighbors. Each RREQ contains the source and destination addresses, a unique RREQ sequence ID and a list of all the nodes it traverses on its way to the destination. An RREQ is uniquely identified by the source address and its sequence ID. Each neighboring node checks if it has received the RREQ before, and discards it if it has. If it hasn't received it before it adds its address to the path recorded in the RREQ and forwards it to its neighbors. The RREQ is flooded through the network until it reaches the destination, or an intermediate node that has a fresh route to the destination [1,3,8]. The source may also use the time to live (TTL) field in the IP header to limit the number of hops it is allowed to travel so that the RREQ will not be flooded uncontrollably through the network [1,8].
The destination, or an intermediate node that has a route to the destination, replies to the source using a Route Reply packet (RREP), which contains the complete route from destination to source. Before sending an RREP, the node is responsible for making sure there are no loops in the path. Intermediate nodes along the path of the RREP update their routing caches with the routing information included in the RREP. When the source receives the RREP, it stores the route in its routing cache, and starts sending data packets.
In DSR, nodes store routing information in routing caches. A routing cache lists all routing information the node gathers about the network. This information can be gathered when the node receives or forwards routing messages (such as RREQ or RREP) received from other nodes. RFC 4728 suggests two methods of organizing the routing cache; a path cache organization or a link cache organization. In the former, routing information is listed by destination address, along with the corresponding path or paths to the destination. In link cache, the node breaks up any paths it knows of into links, and uses these links to establish a graph which reflects the topology of the network as seen by the node. To determine paths from the links stored in the routing cache, an algorithm such as Djikstra's algorithm has to be used to determine an optimal path to the destination. Clearly, the path cache approach is simpler to implement and use, while the link cache approach is more complex, and requires more processing and resources. However, the link cache approach may be more efficient in the sense that it allows the selection of the 'best' paths through the network .
Whichever way the routing information is arranged in the cache, it is preferable to assign a timeout to each entry in the routing cache so that it expires if not used within a certain time . However, DSR does not require cache entries to expire, and so they may remain in the cache for a long time . Requiring cache entries to expire prevents the use of stale routes, and reduces caching capacity required. Since nodes store routing information in routing caches rather than routing tables, it is possible to store more than one route per source and destination, i.e. DSR supports multipath operation [3,8;9], in which case any method or metric can be used to choose from amongst different routes available to a destination, for instance least number of hops .
3.1.2 Route Maintenance
Route maintenance in DSR does not involve periodic "Hello" messages, i.e. DSR is beaconless. The responsibility of making sure the link is functional lies with the sending node . Which is why if a link breaks, the upstream node sends a route error packet (RERR) to the source and to any other nodes sending data on paths that include the broken link. The node generating the RERR and all nodes receiving (and overhearing) it remove the broken link from their route caches. The source can then either use an alternative route to the destination, if it has one in its routing cache, or it can discover a new one by initiating a new route discovery process [1,8].
A link is considered broken if the sending node does not receive an acknowledgement after sending a packet a certain number of times. Acknowledgement can be active, such as acknowledgement messages exchanged by the MAC protocols, or passive for example when the sending node overhears the receiving node transmitting the packet to the next hop on the path. In some cases the sending node may specifically request an acknowledgement .
[FIGURE 2 OMITTED]
[FIGURE 3 OMITTED]
If an intermediate node that has detected a broken link has an alternative route in its routing cache it should salvage the packet, after sending the RERR to the source. Salvaging the packet involves sending it over the alternative route to the node at the other end of the broken link, instead of just dropping it .
3.1.3 Additional Options / Optimizations
There are several optimizations that can be used to improve the performance of DSR. There include the following:
* Allowing intermediate nodes to use routing data in data packets they forward to populate their routing caches .
* Promiscuous listening. This allows nodes to listen, receive and process packets that are not sent to them and extract useful information about the network, such as broken links, that do not directly affect any of their data transmissions [1;3].
* DSR allows piggybacking data and routing packets to reduce overhead .
* Flow state extension. This is an extension to DSR that allows most packets to be routed through intermediate nodes without being required to carry the whole route from source to destination, reducing overhead [3;8].
3.2 Ad Hoc On-Demand Distance Vector (AODV)
The Ad Hoc On-Demand Distance Vector (AODV) routing protocol seems very similar to DSR in many respects, but there are some important differences in the operation of the two protocols. Both protocols are on-demand, and both use route discovery and route maintenance procedures. However, AODV is not a source routing protocol, and it uses periodic "Hello" messages to maintain routes. Furthermore, AODV uses sequence numbers to prevent loops in routes, which is not required in DSR. Moreover, AODV uses routing tables to store routing information, where only one route is allowed per destination, and entries expire if they are not used for a certain time. Finally, AODV does not support multipath operation, but it supports multicasting [1,3,10,19,20,21,22].
AODV uses routing tables to store routing information, rather than the routing caches used in DSR. AODV's routing tables can only accommodate one entry per destination. Since AODV is not a source routing protocol, the routing table lists the destinations the node is aware of and the next hop IP address to each, not the complete path. Each entry also has a timeout assigned to it, its latest known sequence number, and a set of precursors (also called predecessors), which are nodes that may be using that link, i.e. nodes that receive or sent control packets concerning the destination. In case of an error on the link, the node will forward the RERR message to all relevant precursors as well, so that they may remove the broken link from their routing tables [3,11]. Finally, a routing table entry also indicates the number of hops to the destination, i.e. hop count.
AODV uses sequence numbers to prevent the use of outdated routing information. Each node must have a monotonically increasing sequence number, which it is responsible for incrementing as required. A node has to increase its own sequence number before it initiates a route discovery process, and before it replies to a route request . As mentioned earlier, for each destination node in the routing table, the last known sequence number is stored. Whenever a node receives routing messages (called control packets) relating to a destination node, it decides whether to use the information in the control packet or discard it by comparing the destination sequence number in the control packet to the last known sequence number stored in its routing table. It updates its routing table with the information contained in the control packet if the sequence number in the control packet is higher than that stored in the routing table, or if the sequence numbers are equal, but the hop count to the destination in the control packet is smaller than the hop count in the routing table minus one, or if the sequence number is not known .
3.2.1 Route Discovery
Route discovery in AODV is quite similar to than in DSR. A source node generates a RREQ packet when it needs to send information to a destination it has no route for. The format of an AODV RREQ is shown in Figure 2.
It identifies the Type of the control packet, which is always 1 for RREQ messages. The letters J, R, G, D, U are flags. J and R are used for multicast messages. G indicates whether a gratuitous RREP should be sent to the destination, this is set when it is important for the destination to be aware of a route to the source, even if an intermediate node replies to the RREQ. If it is set, the intermediate node would send two RREPs, one to the source and one to the destination. Flag D is set when the source requires that only the destination node replies with an RREP, not an intermediate node, and flag U is used when the sequence number is unknown. The 'Reserved' field is set to zero, and the hop count is initially set to zero at the source node, and incremented at each hop.
Rather than flooding the RREQ message, an expanding ring search is usually preferred. In an expanding ring search the source attempts to search for the destination within a limited area within its neighborhood, which is incrementally increased if the destination is not found. This prevents uncontrolled flooding of RREQ messages throughout the network. The "search area" and "neighborhood" are defined in terms of the hop count from the source, and the expanding ring search is implemented using the TTL field in the IP header of the RREQ packet .
When a source node generates an RREQ, it is required to wait for a certain time (determined depending on the network) before generating another RREQ for the same destination. After a number of retries (also determined depending on the network) it can declare the destination unreachable, drop packets waiting to be sent and notify the application .
A node receiving an RREQ discards it if it has received an RREQ with the same ID from the same source recently ("recently" would depend on the definition of "path discovery time" specified for the network). Otherwise it processes the RREQ. Processing the RREQ by the node involves incrementing the hop count in the RREQ by one, searching for a route to the RREQ source in the routing table. If an entry is found it is updated with the source's sequence number, next hop to the source (which is the source IP address in the IP header) and hop count to the source. Also, the lifetime field of the entry (its expiry timeout) is refreshed. If no entry is found a new one is created to include the same information. Now that the node has a reverse path to the source, it proceeds to determine whether it will send an RREP or forward the RREQ. A node can reply with an RREP if it is the destination, or if its routing table contains a route to the destination. Otherwise, it checks that the TTL field in the IP header is greater than 1. If it is, it decrements the TTL field by one, updates the destination sequence number in the RREQ if the destination sequence number in its routing table is larger, and having already incremented the hop count in the RREQ, it broadcasts it to all nodes in range using the IP address 255.255.255.255.
If the node is the destination node, or knows a route to the destination, it has to reply to the source node with an RREP. The format of an AODV RREP is shown in Figure 3.
In AODV, RREP messages are Type 2. The R flag is used for multicast routing, while the A flag indicates whether an acknowledgement is required, this option is used when the link is known to be unreliable or might not support bidirectional communication. The Reserved bits are assigned a value of zero. The Prefix Size field can be either zero, or it can indicate that it is possible to use the same route for other addresses that starts with the same bits as the destination address. In this case, the Prefix Size is the number of address bits that have to match to be able to use the same route, this is useful in subnetting. The originator sequence number and IP address are those of the source node that generated the RREQ, and the destination sequence number and IP address are those of the destination node generating the RREP. The Hop Count is the number of hops between source and destination, and the Lifetime indicates the amount of time (in milliseconds) that the RREP should be considered valid by the receiving nodes .
If the destination node is replying to the RREQ, it compares the destination sequence number in the RREQ with its sequence number, and increments its sequence number if it is smaller than the one in the RREQ, inserting the final sequence number in the RREP. The default value of the Lifetime field in this case is 6000 ms, but that could be changed depending on the network . After setting the RREP Hop Count to zero and inserting its IP address and that of the originator, the destination can send the RREP to the next hop towards the source node.
If an intermediate node is replying to the RREQ, then the Hop Count field in the RREP is the number of hops from itself to the destination, and the Destination Sequence Number field is the most recent sequence number it knows for the destination. The Lifetime in this case is remaining time for which its routing table entry for the destination will be valid. The RREP is ready to be sent once the originator and source IP addresses are entered. In addition to sending the RREP, the intermediate node will have to update the precursors in its routing table by adding the next hop to the destination in the set of precursors corresponding to the destination's entry, and the next hop to the source in the set of precursors corresponding to the source's entry. Finally, if the 'G' flag in the RREQ is set, the intermediate node would also have to send an unsolicited Gratuitous Reply. This has the same format and carries the same information as an ordinary RREP message, but the Hop Count is the number of hops from the intermediate node to the source, the Destination IP address and Sequence Number refer to the source node (the node that generated the RREQ) and the Originator IP address refers to the destination to which the Gratuitous RREP is addressed .
Each intermediate node along the path to the originator increments the hop count by one and forwards the RREP to the next hop. It also updates its routing table by adding a forward path entry, which includes the IP address of the destination and the previous hop (the node from which it received the RREP), the hop count to the destination and the lifetime of the entry, which is equal to the Lifetime field of the RREP. If an intermediate node receives more than one RREP for the same source and destination, it forwards the first RREP it receives, and only forwards any other RREPs if the destination sequence number is greater than the one stored in its routing table, or the hop count is less. Once the RREP reaches the source, it can start sending data. If more RREPs reach the source later, it can select the best route and use that for the data transmission. However, each entry in the routing table can only have one route associated with it .
3.2.2 Route Maintenance
In AODV, if any link along the established route breaks the upstream node has to send a RERR to the source node. The RERR message contains the IP address of the link on the other side of the broken link. An advantage of AODV is that the upstream node (the node that failed to send data over a link towards the destination) also forwards the RERR to any other nodes it thinks are using the broken link (i.e. the link's precursors). These nodes in turn update their routing tables, setting the hop count to the destination to infinity and forward the RERR to any other nodes using the broken link, if there are any. This way, concerned nodes know very quickly when a link breaks. However, an entry for a broken link is not immediately removed from routing tables, as it often contains useful information. After receiving the RERR, the source can send a new RREQ to find a new route if it still has data to send .
The other situation where a node generates a RERR is when it receives a data packet destined for a node it does not have a routing table entry for. In this case, the RERR contains the IP address of the destination, and it is sent to the previous hop, i.e. the node that the data packet was received from .
AODV nodes send periodic "Hello" messages to their neighbors (TTL field is set to 1). These are used to confirm that neighbors a node is aware of are still within range, and to know if any new nodes have moved to the vicinity recently. Not all nearby nodes have to send "Hello" messages; these messages are not required if the node has sent any data packets within the past "Hello Interval", which is by default 1 second. A Hello message is a special RREP message, unprompted by an RREQ that contains the sending node's IP address and sequence number .
3.2.3 Rebooting nodes
When a node reboots, it loses information about its own sequence number and that of some of its routing table entry. To avoid that, a "delete period" is specified for the network during which a node that was rebooted has to ignore any control packets it receives, and send out RERR messages whenever it receives data packets. Using the "delete period" approach also ensures that no routing loops would result if the node was part of an active path before rebooting .
3.3 Split Multipath Routing (SMR)
Split multipath routing, SMR,  attempts to improve performance of on-demand routing protocols by allowing the destination (receiving node) to select multiple paths to the source that are as disjoint as possible, to avoid overloading some (popular) nodes, and to make the paths as robust as possible by avoiding the weakness introduced by using different paths that use common nodes or links. SMR can be seen as a development on DSR, in that it is a source routing on-demand protocol, even though it does not use DSR's aggressive caching approach. Its operation is divided into route discovery and route maintenance phases.
3.3.1 Route Discovery
Just like in DSR and AODV, the route discovery process is initiated by a source node when it wants to send data to a destination for which it has no route. The source floods a RREQ packet, which traverses the network until it reaches the destination. Unlike DSR and AODV, however, an intermediate node cannot reply to RREQs, even if it knows a path to the destination. It is important that only the destination node replies to the RREQ since it is required to select maximally disjoint paths, and so it has to know the complete available routes to the source.
On determining that an RREQ it received is a duplicate, an intermediate node does not immediately discard it, instead it checks the previous node from which the RREQ was received and the hop count to the source. The duplicate RREQ is forwarded if it arrived on a different link, travelling through an equal or smaller number of hops than the previous RREQ. If the second RREQ arrived from the same previous hop, or travelled through more hops it is discarded. This approach helps find more maximally disjoint paths, although it means that more RREQs travel through the network. Thus, since it cannot generate RREP messages, the role of an intermediate node is now limited to determining whether a RREQ is a duplicate or not, and forwarding it where appropriate.
Once a destination receives an RREQ it quickly replies with an RREP, so that the path can be established and data transmission can begin. In the meantime, the destination also receives other RREQs from other routes. The destination waits for a certain amount of time, then selects from among the alternative routes it knows of. In , the algorithm is limited to selecting two maximally disjoint paths, such that the first corresponds to the first RREQ received by the destination, and the second is as disjoint as possible compared to the first path. However, the number of paths can be increased as required.
The destination "selects" a second path by sending the source another RREP containing the addresses of all intermediate nodes along the second path. On receiving the second RREP, the source adds the new route to its routing table. It can now split the load over the two paths. Although more complex load balancing schemes can be used, in  a simple per packet allocation approach is used. This is a simple approach that avoids the need for complex processing, and does not require additional information about the state of the network (for instance available bandwidth) but has the disadvantage of the packets arriving out of order at the destination, requiring resequencing.
3.3.2 Route Maintenance
SMR does not require periodic Hello messages to maintain active paths. Like DSR, route maintenance here is limited to dealing with a broken link along a route. When a node is unable to send a packet across a link, it generates a RERR message and sends it to the source node. The RRER includes the addresses of all nodes along the path from the node discovering the broken link to the source node, as well as the addresses of the two nodes on either side of the broken link. On receiving a RERR message, the source node deletes all occurrences of the broken link from its routing table, even if they are being used to send data to another destination.
At this point there are two approaches: the source can either immediately search for another route, while it uses the remaining route to transmit data, or it can continue sending data along the remaining path to the destination without initiating a route discovery process until that second route breaks as well. The first approach, referred to as SMS-1, results in more route discoveries being initiated, and more overhead, but ensures that data transmission is less likely to be interrupted if the second route breaks. The second approach, SMS-2, is less resilient, but reduces the load on the network resulting from control packets.
3.4 Shortest Multipath Source (SMS) routing
The Shortest Multipath Source (SMS) routing protocol is another reactive source routing scheme that is designed to build on the strengths of DSR and SMR, while reducing the restrictions on the route selection scheme used in SMR to increase the number of multipaths possible. Rather than selecting routes that are node disjoint throughout as in SMR, SMS increases the number of routes possible between a source and destination by requiring that the alternative routes be partially disjoint only, i.e. that they "bypass at least one intermediate node on the primary path" . The primary path here is simply the first path to be established, i.e. the path for which the source receives the first route reply message. Increasing the number of paths possible between a source and a destination makes the protocol more resistant to faults, and helps speed up recovery when a link along the path breaks. In , a mathematical analysis is used to prove that using a larger number of partially disjoint paths increases the network's tolerance to faults, compared to link or node disjoint multiple paths. The operation of SMS is also divided into route discovery and route maintenance phases.
3.4.1 Route Discovery
When a source node wants to send data to a destination node it first checks its cache for a route. If it finds a route it can start sending data directly. Otherwise it will have to initiate a route discovery process by sending out several route request messages (RREQ) to its neighbors .
In SMS not all duplicate RREQs are discarded, instead an intermediate node only forwards an RREQ if the number of hops the RREQ has traversed from the source to itself is less than or equal to the number of hops traversed by the first RREQ it received. On deciding whether to forward a duplicate RREQ, SMS nodes do not consider the incoming link on which the RREQ was received (as in SMR), since the protocol aims to build partially disjoint paths. Instead, it compares the number of hops from the source to itself in the route of the previous RREQ to the number of hops of the new RREQ, and only forwards the RREQ if the latter is less than or equal to the former .
In SMS, as in SMR, only the destination is allowed to reply to a RREQ. Again, this limits the role of intermediate nodes to determining whether to forward a RREQ or not, and actually forwarding the control messages. However, in SMS it is the source node that selects the paths, not the destination node. The destination node simply replies to the first few RREQs it receives. In , this threshold value is five, although a different threshold could be set, as mentioned in the paper. The RREP contains the path the RREQ has traversed to reach the destination, including the destination address. The destination node also saves the route path for each RREP it sends in its cache, and finally unicasts the RREP to source. When the source receives the RREP, it adds the new route to its cache and can now start sending data .
When the source receives more than one RREP, it is responsible for selecting paths that are partially disjoint, i.e. that are at least different in one link. It records these routes in its routing cache, after which it can start sending data. Once the source node has two or more paths to a destination, it can divide the traffic load amongst the two. In  a simple per-packet allocation scheme is used.
3.4.2 Route Maintenance
SMS is beaconless, like DSR and SMR. When an intermediate node along a route is unable to send data to the node on the other end of the link, it declares the link broken and generates a RERR message destined to the source node. The intermediate node does not attempt to use an alternative to the broken link. When the source receives the RERR message, it removes the broken link from its routing cache, even if it is used to route data to another destination. It then randomly selects another route from the remaining alternative routes and uses it to send data.
3.5 Ant based routing protocols
This category of MANET routing approaches includes a wide variety of protocols that are inspired by swarm intelligence, i.e. the way ants co-operate to find the shortest path to a destination, even when faced with an obstacle. Ants communicate with each other indirectly by modifying their surroundings, this is called stigmergy. Specifically, they modify their environment by dropping off substances called pheromones as they travel through a path. This way, other ants can follow them. When ants have to crawl around some obstacle to get to their destination, which could be their nest or food source, they initially choose a random path, leaving pheromone trails. The ants that reach the destination first travel back in the reverse direction, leaving off more pheromones, encouraging other ants to use that path. This way, the shorter path soon has a higher pheromone concentration, so that ants arriving later can tell which route to take . This process is illustrated in Figure 4.
[FIGURE 4 OMITTED]
Despite some differences between the different protocols, the basic approach behind ant-based routing protocols is the use of small control packets, referred to as ants, to discover new routes and gather information about the network, then return to the node that generated them. These ants are referred to as forward ants as they travel on the forward path to discover the network, and backward ants as they travel along the reverse path with the information they gathered. This information is used to populate routing tables or other data structures where information is stored and later on used to determine the best paths through the network .
Ant based protocols also define ways of calculating artificial pheromone concentration along a path as a measure of how good it is. Pheromone concentrations, along with other factors such as congestion or distance, determine which path is selected from amongst several available alternatives. In ant based protocols, it is important to define the data structures (i.e. the metrics used, routing tables etc) as well as the operation of the protocol. In what follows, the principles behind AntHocNet will be presented.
AntHocNet  is a widely cited ant-based routing protocol. It is a hybrid protocol, in the sense that it discovers routes whenever they are required, but once the routes are established, it maintains them proactively and even attempts to improve them for as long as they are required. The operation of AntHocNet is divided into a reactive path setup phase, stochastic data routing, proactive path maintenance and exploration phase and dealing with link failures.
3.5.1 Reactive path setup
To discover a route for a destination node a source node floods a forward ant, [F.sup.S.sub.d]. Each of the source node's neighbors receives a copy of the forward ant, each traversing the network through a different path aiming to find a path to the destination. The different copies of the same forward ant generated during the same path setup cycle are called an ant generation. When an intermediate node receives a forward ant, it checks whether it has a route to the destination, and only broadcasts the ant to its neighbors if it does not have one. If it does, it unicasts the ant to the destination using that route. If it has multiple routes to the destination then it has to decide which one to use for the forward ant, i.e. it has to select from a set of possible next-hop nodes on the route to the destination. This selection is done based on the pheromone values of each of the possible next hop nodes stored in the intermediate node's routing table.
In the case where the intermediate node does not have a route to the destination, AntHocNet tries to control ant flooding by setting a maximum number of hops (depending on the network diameter)for ants, so that if an ant does not find the destination by then, it is dropped. This prevents ants from circling around the network indefinitely, and reduces control overhead. Furthermore, AntHocNet tries to strike a balance between discovering new routes and maintaining an acceptable control overhead by controlling when intermediate nodes are allowed to forward duplicate ants (of the same generation) and when to delete them. Specifically, a duplicate ant is only forwarded if its hop count and the time it took to reach the intermediate node are within a factor, [a.sub.1], of the hop count and time delay of the most efficient ant in the generation. Moreover, to encourage the discovery of more disjoint paths a second factor, [a.sub.2], which is larger than [a.sub.1], is specified. If an ant travelled through a different first hop from the source than other ants of the same generation received by the intermediate node, then it will still be forwarded if its hop count and time delay are within [a.sub.2] from those of the most efficient ant. In the experiments presented in , [a.sub.1]=0.9 and [a.sub.2]=2.
3.5.2 Pheromone values
If an intermediate node i has n possible next-hop nodes leading to the destination d, then its pheromone table, [[tau].sup.i] would have a pheromone value, [[tau].sup.i.sub.nd], that specifies how good node n is as a next hop to the destination. The intermediate node randomly decides on the next hop, with a probability of selecting node n,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
Where [[beta].sub.1] [greater than or equal to] 1 is a parameter that influences the extent of the exploratory behavior of the ants and [N.sup.i.sub.d] is the set of possible next hop nodes. In the experiments in  [[beta].sub.1] = 1 was used.
3.5.3 Data gathered by ants
The forward ant keeps a list of the nodes P it travels through until it reaches the destination. The destination then unicasts a backward ant to the source. At each node i along the path (whether forward path or reverse path), the ant incrementally calculates the approximate time delay [[??].sub.p] involved when a data packet travels from the source to the destination along P. In the forward ant, the value of [[??].sub.p] is used by intermediate nodes to decide whether to forward or discard a duplicate ant, as mentioned earlier. In the backward ant, the value of [[??].sub.p] calculated at each hop is used to update the current node's routing table.
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)
And [[??].sup.i.sub.i+1], the time delay incurred in travelling from node i to node i+1, is
[[??].sup.i.sub.i+1] = ([Q.sup.i.sub.mac] + 1) [[??].sup.i.sub.mac] (3)
Where [Q.sup.i.sub.mac] is the number of queued packets to be sent at the MAC layer, and [[??].sup.i.sub.mac] is the mean time to send one packet, which is numerically a running average of the time between the arrival of a packet at the MAC layer, and its transmission. Defining the time it takes to send one packet from node i, [[??].sup.i.sub.mac] then becomes
[[??].sup.i.sub.mac] = [alpha][[??].sup.i.sub.mac] + (1 - [alpha]) [t.sup.i.sub.mac], where [alpha] [member of] [0,1] (4)
The backward ant also updates or creates pheromone values, [[tau].sup.i.sub.nd], which are stored in the pheromone table, [[tau].sup.i]. [[tau].sup.i.sub.nd] is calculated as the running average of the inverse of the cost, i.e. the time delay and hop count, incurred when a packet travels from source to destination via node n. Defining [[??].sup.i.sub.d] as the estimated travelling time, h as the hop count and [T.sub.hop] as the time taken to travel through one hop in unloaded conditions, then [[tau].sup.i.sub.d] can be calculated as
[[tau].sup.i.sub.d] = [([[??].sup.i.sub.d] + h[T.sub.hop]/2).sup.-1] (5)
[[tau].sup.i.sub.d] is then used to update the running average [[tau].sup.i.sub.nd] using the following equation
[[tau].sup.i.sub.nd] = [gamma][[tau].sup.i.sub.nd] + (1 - [gamma]) [[tau].sup.i.sub.d], where [gamma] [member of] [0,1] (6)
In the experiments in , [gamma] = [alpha] = 0.7.
3.5.4 Stochastic Data Routing
By the time the backward ants reach the source, the source, and intermediate nodes, would have multiple paths to the destination. Every time a node has to send data, it can choose from among the available next hops randomly, but with a certain probability, [P.sub.nd], of selecting a node n as a next hop towards destination d. For data packets, this probability is calculated in a similar fashion to the [P.sub.nd] used to route forward reactive ants, but a higher exponent, [[beta].sub.2] is used instead of [[beta].sub.1]. Increasing the exponent discourages or reduces the probability of packets taking more exploratory routes, and instead places higher emphasis on better paths. So,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)
Using this approach to select routes for data packets the network continuously adapts to the state of the network and the load is balanced accordingly. The state of the active links is continuously sampled by the proactive path maintenance process, and routing adjustments made accordingly.
3.5.5 Proactive path maintenance and exploration
Once the route from source to destination is established, the source generates proactive forward ants to  gather updated information about the status of the route to the destination and  explore the possibility of finding better paths. They do this by travelling to the destination using pheromone values stored in intermediate nodes' tables, just like data packets. However, the exploratory behavior is incorporated by mandating that intermediate nodes may broadcast the proactive ants with a certain probability. In which case the ants stop following the established paths and try to find better paths to the destination. However, since the role of proactive ants is to improve the existing paths rather than discover new ones altogether, a limit is placed on the number of times a proactive ant can be broadcast, [n.sub.b]. If it is unable to find a route back to the destination after being broadcast [n.sub.b] times the proactive ant is discarded. This way, the proactive ants are restricted to finding improved paths in the vicinity of the established paths. The frequency of these proactive ants is determined by the rate at which data is transmitted. In the experiments in , [n.sub.b] = 2.
Furthermore, nodes in AntHocNet send one-hop Hello messages to their neighbors regularly, containing only the address of the node generating the Hello message. This way, nodes know when new nodes move within range, or when existing neighbors move out of range and update their routing tables accordingly. The frequency of Hello messages, [t.sub.hello], is determined depending on the network. A maximum time period, [t.sub.max] = allowed-hello-loss x [t.sub.hello], is also set so that if no Hello messages are received from a neighboring node within that time it is assumed to be out of range. In the experiments in , allowed-hello-loss=2.
3.5.6 Dealing with Link Failures
A link is considered broken either when the node on the other end of the link does not send Hello messages within [t.sub.max], or when the upstream node is unable to send data over the link. When a link is broken, the upstream node n/takes the following actions:
* It removes the broken link from its routing and pheromone tables
* It sends a link failure notification message to its neighbors, which lists the destination nodes affected by the broken link, and if available, details (expected delay and hop count) of the best alternative path available. Neighboring nodes receiving the link failure notification message delete the broken link from their tables, update their routing information and, if the broken link affects their ability to communicate with a destination, they forward the link failure notification message to their neighbors as well.
* If the upstream node has no alternative path to the destination, and it still has data to send it can attempt to locally repair the path using a route repair ant. If it attempts to repair the path locally, the path is not included in the link failure notification message. The route repair ant, which is broadcast by the node that generates it, travels through the network, attempting to find the destination. Intermediate nodes either unicast or broadcast it, depending on whether they have routes to the destination. On receiving a route repair ant, the destination unicasts a backward repair ant to the source, which can then resume data transmission. To prevent a route repair ant from circling the network forever in search of a destination, a route repair ant is allowed to be broadcast a maximum number of times (this is set to 2 in ) along its path to the destination, after which it is discarded. Moreover, to enable the node generating the repair ant to decide when to stop looking for an alternative path, the node waits for a certain time (set to five times the expected delay of the broken path) before declaring the link irreparable. In that case, a link failure notification message is sent out, and any buffered packets are deleted.
In the case where an intermediate node receives a data packet for which it has no path to the destination, the intermediate node will delete the packet, and send a warning message to the upstream node it received it from so that it can update its routing table.
4. Evaluation of Selected Protocols
In this section, a basic discussion of the relative merits of each protocol and its performance in terms of the other protocols is presented. A major limitation of this discussion is that it is not based on independent simulations, but rather on a review of performance evaluations presented in the available literature. Drawing conclusions about performance of the different protocols is quite difficult, due to the use of different simulation software or techniques etc in different experiments. Furthermore, not all of the newer protocols have been evaluated against the same older protocols, for instance, while the performance of AntHocNet has been compared to that of AODV, both SMR and SMS have been compared to DSR. Such factors, and their potential effects, will be pointed out.
Different metrics are used to compare protocol performance, the most common ones are:
* Packet delivery ratio (also referred to as Goodput): ratio of data packets delivered to their destination, to the data packets generated by the sources.
* Routing overhead: The number of routing (control) packets sent during the simulation. This is used in . An alternative measure of protocol efficiency is normalized routing load, which is the number of routing packets sent divided by the total number of data packets received during the simulation. This is used in [10,13,14,16]. When routing overhead is measured in packets (not bytes), then the additional routing load caused by source routing (i.e. control and data packets are larger because they include the addresses of every node along the path to the destination) is not directly considered, in which case source routing protocols may not appear to load the network as much as they actually do, and a feature of non-source routing protocols is unaccounted for. However, the counter argument to that is that the effect of bigger packets may not have a very significant effect on overall performance, since nodes mainly compete for the wireless medium in MANETs, once a node has access to it and no collisions occur, the actual cost of sending a few extra address bytes is not that significant.
* Average end-to-end delay: This is the sum of all delay experienced by a packet from the time it is generated by the source, till it is received by the destination. It includes delay experienced at the send buffer while the packet waits for a route to be established, delays experienced as the packet is queued at the interface queue, delays at the MAC layer caused by retransmission due to errors and propagation delay [10, 14].
* Delay Jitter: Usually used in Quality of Service (QoS) applications and can be used to quantify a protocol's response to changes in network topology in terms of stability. It is measured by taking the average of the time gap between the arrival of three packets; for three packets arriving at times [t.sub.1], [t.sub.2] and [t.sub.3], the delay jitter is the arithmetic average of ([t.sub.3]-[t.sub.2])-([t.sub.2]-[t.sub.1]) calculated for each three consecutive packets received in a session. This metric is only considered in AntHocNet experiments .
* Packet Loss: Packets that are transmitted by the source, but do not reach the destination, measured in/percent and used in  only.
* Path Optimality: This compares the distance a packet travelled from source to destination in hops, to the shortest route available at the time. This metric is used in  only.
Justifying protocol performance in terms of specific performance metrics above becomes easier if these metrics are related to certain characteristics of the protocols in question. Table 1 and Table 2 list the specific characteristics (positive and negative) that would affect each protocol's performance in terms of each of the above metrics. In some cases, features of a protocol that usually result in favorable results may end up hindering its performance, for instance, DSR's aggressive routing approach often enables it to know more about the network, thus saving some route requests and quickly shifting packets to be transmitted to an alternative route when the original one breaks etc. However, if the routing cache data is stale, (which is likely since DSR does not use lifetimes or sequence numbers to identify and remove outdated information) a source node may try to send data to a destination over a route that is no longer valid. After several failed attempts, the source would declare the link or route invalid, and will either send data over an alternative path or initiate a route request. In a situation like this DSR's aggressive routing strategy and its inability to distinguish outdated routing data, would result in unnecessary delays and possibly packet loss, instead of speeding up the process. The same applies for periodic "Hello" messages used in AODV and AntHocNet; they help ensure routing data is up to date, but at the same time they increase overhead. Where the same characteristic can have positive and negative effect, both are shown on the same row in the respective tables.
In experiments used to evaluate the performance of routing protocols, different scenarios are used to test the protocol's performance in terms of some performance metrics. The aim is to determine whether the strengths of the protocol's design will enable it to perform better in different situations, for instance, whether DSR's aggressive caching strategy is advantageous in realistic situations, when is the additional overhead required for "Hello" messages justified etc. In this report, the results of experiments carried out in [10;13;14;16;17] are presented and discussed. Only minimum details of how the simulations were carried out are considered, and instead, the focus of this report is how each protocol performs when compared to other protocols.
4.1 DSR Vs. AODV
This section is based on the experiments carried out in  using Network Simulator-2, in which the performance of TORA, DSDV, DSR and AODV are evaluated in terms of packet delivery ratio, routing overhead and path optimality. The experiments are carried out with 50 nodes moving at an average speed of 10m/s (maximum speed 20m/s) and the results discussed when there are 10 sources, 20 sources and 30 sources. Next the experiments are repeated with 20 sources and a maximum speed of 1m/s. Details of the experiment set up are provided in . Table 3 tabulates the results of the experiments, along with possible justifications and comments on factors that might affect the performance of the protocols. Since TORA and DSDV were not discussed in detail in this paper, they will be excluded from this discussion.
4.1.1 Notes on protocol implementation
The implementation of AODV is referred to as AODV-LL, since it only relies on link layer feedback in 802.11, i.e. it does not use periodic Hello messages. AODV-LL also uses a RREP_WAIT_TIME of 6 seconds instead of 120 seconds as specified in . As reported in , these modifications were found to improve performance.
4.1.2 Notes on simulation results
As indicated in Table 3, AODV-LL as implemented in the simulations does not use expanding ring search, which was later specified in  to control the flooding of RREQs, while DSR source nodes use the TTL field in the IP header to send out non-propagating RREQ to their neighbors first to see if they have routes to the destination. If they don't a propagating RREQ is used. This helps keep routing overhead low. Enabling the expanding ring search feature in AODV is expected to reduce its routing overhead.
[FIGURE 5 OMITTED]
[FIGURE 6 OMITTED]
[FIGURE 7 OMITTED]
Also, as mentioned earlier, the routing overhead results in Table 3 do not consider the effect of DSR's additional source routing overhead since they are measured in packets, not bytes. An additional simulation is run in  showing overhead in bytes. In the latter case, AODV-LL's overhead is significantly lower than DSR's except at pause times less than 100 sec, where the gap between the two is not very large. Figure 5 and Figure 6 show the routing overhead in packets for DSR and AODV-LL, respectively, when 20 sources are used and nodes move at a maximum speed of 20m/s. Figure 7 compares the routing overhead of the two protocols in bytes on a log scale. From the figures, it seems that including the overhead that results from source routing significantly affects overhead. However, the effect of source routing on overall performance may not be as profound as it seems, since wireless nodes compete over the medium, and once a node starts transmitting the cost of a few additional bytes is not that significant. This is further explored in the simulations carried out in  the results of which are discussed in the next section.
The results of the simulations carried out in  suggest that the overall performance of DSR and AODV-LL are very close, with DSR outperforming AODV-LL slightly in terms of packet delivery ratio and path optimality, and more significantly in terms of routing overhead measured in packets.
4.2 DSR Vs. AODV
Although this section might initially seem as a repetition of the results presented in the previous section, the experiments carried out in  provide added insight into the performance of DSR and AODV for several reasons. First, an additional important metric, average end-to-end delay is considered. Also, DSR is implemented as a multipath protocol and AODV uses an expanding ring search to control flooding of RREQ packets. Finally, the discussion in  provides further insight into the issue of the relative routing overhead of both protocols (Table 4).
4.2.1 Notes on simulation results
The simulations carried out in  build on the experiments presented in  for DSR and AODV. An important addition is the inclusion of average end-to-end delay as a performance metric, which is a more tangible indication of overall performance than path optimality. The inclusion of additional AODV features like expanding ring search makes the comparison fairer. Moreover the implementation of DSR as a multipath protocol measures its performance better.
As in , the additional source routing overhead introduced by DSR is disregarded. This is because even though more bytes may be transmitted, nodes compete for the medium in wireless networks, once a node has permission to transmit, sending a few extra bytes will not have a significant impact on overall performance. On the other hand, the authors of (10) argue that even though DSR generates less routing overhead, this does not necessarily mean that it creates less load on the network. It was observed that a large proportion of DSR's routing load (up to 50% in some cases) was made up of RREPs, while most of AODV's routing load (up to 90%) was a result of RREQs. Noting that RREPs and RRERs use the Request to Send (RTS)/Clear to Send (CTS)/Data/Acknowledgement (ACK) control messages of the 802.11 MAC protocol, while RREQs do not use them, clarifies why the savings on RREQs in DSR may not result in much less network load. So overall, when MAC control packets were included, the overhead load of both DSR and AODV was found to be nearly the same.
The results presented in  indicate that AODV performs better in more demanding conditions (higher mobility rates and larger number of sources) in terms of "application-oriented" metrics, i.e. packet delivery ratio and average end-to-end delay, possibly due to its emphasis on using up to date routing information, and selecting fresher routes. DSR maintains a lower routing overhead (measured in packets) throughout, mainly due to its aggressive caching strategy, which allows it to gather a lot of information about the network, and save some route requests.
4.3 SMR-1 Vs. SMR-2 Vs. DSR
This section is based on experiments presented in  comparing SMR-1 and SMR-2 with DSR in terms of packet delivery ratio, dropped packets, normalized routing load, average hop distance and average end-to-end delay. Details of the results, along with possible justifications are tabulated in Table 5. Details of the simulation environment, movement models etc are provided in .
4.3.1 Notes on simulation results
DSR is implemented as a unipath protocol. It is also unclear from  whether any of its optimizations or extra features, such as expanding ring search or automatic route shortening, are implemented.
The results in Table 5 indicate that SMR-2 performs better than unipath DSR almost always, particularly at high stress conditions. However, it cannot be automatically concluded from these results and the results in section A that SMR-2 will outperform AODV, particularly that DSR implemented in section A has a lot of additional features or optimizations, such as expanding ring search which are not mentioned in , and which may improve its performance.
4.4 SMS Vs. SMR-2 Vs. DSR
This section is based on the results of simulations presented in  and . Three sets of simulations were carried out, where the parameters varied were mobility (speed of the nodes), offered load (number of sources) and network size (number of nodes and size of network area). In all three cases, the performance parameters measured were goodput (packet delivery ratio), average end-to-end delay, normalized routing load and packet loss. Details of the simulation scenarios and set up are described in . The results of the three sets of simulations are shown in Tables 6, 7 and 8 respectively.
4.4.1 Notes on simulation results
As confirmed by one of the authors of , SMR-2 was implemented in these simulations, since it outperformed SMR-1 in the experiments presented in . As implemented here, DSR is a unipath protocol. Additional features like expanding ring search are not implemented, since  states that DSR floods RREQs through the network.
From the simulation results, is evident that SMS performs better than SMR-2 mainly because it is able to identify more alternative partially disjoint paths, and because it prefers shorter paths. SMR-2's maximally disjoint path property have the advantage of choosing paths that are as different as possible from each other, so that if one link fails there is very little chance that the second path would be invalidated as well as a result. It might seem that maximal disjointedness is more of an overkill. The fact that path length is not considered in selecting the second path probably affects performance significantly. It might be the case that the maximally disjoint path is very long, and since a per-packet assignment is used to balance the load, a longer alternative path will affect goodput, delay and packet loss.
No inferences can be made about the performance of SMS or SMR-2 with respect to AODV, since the implementation of DSR here is unlike that used in  and . However, it is clear that both SMS and SMR-2 perform better than "basic" DSR (i.e. unipath and without additional features like expanding ring search).
4.5 AntHocNet Vs. AODV
This section is based on experiments carried out in . Two sets of simulations are carried out; in the first, a sparse network is used where 100 nodes move within an area of 3000x1000m2 and both the random way point model and Gauss-Markov model are used. In the second set, the number of nodes and network areas are varied while keeping the overall network density constant. The setup of both sets of simulations is described in more detail in . The performance metrics considered are packet delivery ratio, average end-to-end delay, delay jitter and routing overhead.
4.5.1 Sparse Network, random way point model
Mobility is varied both by varying the speed at which nodes move and by varying the pause times. The results for varying node speeds are shown in Figures 8 and 9, while the results for varying pause times are shown in Figures 10 and 11. AntHocNet performs better than AODV in both cases in terms of packet delivery ratio, average-end-to-end delay and average delay jitter particularly at higher mobility levels. However, it generates much more routing overhead as a result of the different types of ants generated, and because it maintains paths proactively. Performance when speed is varied is as expected; it worsens with increasing speed. On the other hand, the results for varying pause times seem to be strange; performance is better at lower pause times (higher mobility). This seems to be a result of using a sparse network; when a node is out of range, at higher pause times it remains so for a longer time, increasing packet drops, delay, jitter and overhead.
4.5.2 Sparse Network, Gauss-Markov model
Compared to the varying node speed results obtained with the random waypoint model, in the Gauss-Markov model packet delivery ratios decrease while delays increase, with AntHocNet outperforming AODV. Also, the gap between the two seems to widen. This indicates that AntHocNet's learning approach allows it to exploit the inherent correlation in the node movements of the Gauss-Markov model. The results are shown in Figure 12.
4.5.3 Increasing network size, random waypoint model
The results in terms of packet delivery ratio and average end-to-end delay when the network size is varied as detailed in  are shown in Figure 13. In terms of packet delivery ratio, while AODV delivers slightly higher fraction of packets with the smallest network size (100 nodes), AntHocNet delivers more packets in larger networks, with the gap between the two widening as the network size is increased. In terms of average end-to-end delay AntHocNet has lower delay for all network sizes, with the gap widening between the two as the network size increases. This indicates that AntHocNet has good scalability as a result of its multipath approach, information gathering, link maintenance features etc.
The above experiment results show that AntHocNet performs better than AODV in terms of packet delivery ratio, average end-to-end delay, and average jitter, but at the cost of higher routing overhead. It is also more scalable than AODV. However, it would be more challenging for AntHocNet, being an ant-based hybrid routing algorithm, to have its performance compared with another hybrid and/or ant-based routing protocol, to really see its strengths and weaknesses.
5. Conclusion and Future Work
This paper started with an overview of MANET routing protocols and their classification, followed by a detailed discussion of the operation and performance of selected protocols. The discussion started with DSR and AODV, which are two of the oldest and most popular reactive routing protocols designed for MANETs. Comparing DSR and AODV shows that although their performance is very close, each one of them has strengths and weaknesses which are visible depending on the network or application. This was followed by a discussion of the principles behind SMR, a source routing reactive protocol designed to improve on DSR. Next, the principles behind SMS, which was designed to improve on SMR, were presented. On comparing SMR and SMS, it is evident that SMS can outperform SMR in a lot of applications. Next, AntHocNet was discussed and compared to AODV. AntHocNet is a hybrid ant-based protocol, it is relatively complex in terms of processing requirements, and has higher overhead than AODV, but its performance in terms of packet delivery ratio and delay is much better in most scenarios. In conclusion, it is evident that each protocol has advantages and disadvantages and there is no one "best" routing protocol. Moreover, protocol characteristics that may be an advantage in one situation may also turn into a disadvantage in other situation. A clear example of that is DSR's aggressive caching approach, which helps it gather a lot of information about the network, but can turn into a liability if the network topology changes too often. The same applies to the different types of ants used in AntHocNet, which usually strengthen the protocol, but can also increase overhead significantly.
As a next stage, it would be interesting to compare the performance of AntHocNet with that of other ant-based protocols, such as EARA-QoS and HOPNET.
Following a review of MANET routing protocols it is also important to note that in some situations routing may not always be advantageous and alternatives such as Key Based Broadcast Routing (KBBR)  may be more efficient, particularly in sensor networks. Another area with potential for future work is the design and implementation of simulations to compare the performance of KBBR to some of the popular routing protocols which may be used in sensor networks to help determine the type of situations in which routing would be beneficial, and when it would not be.
[FIGURE 8 OMITTED]
[FIGURE 9 OMITTED]
[FIGURE 10 OMITTED]
[FIGURE 11 OMITTED]
[FIGURE 12 OMITTED]
[FIGURE 13 OMITTED]
 C.S. Murthy, B.S. Manoj, Ad hoc Wireless Networks Architectures and Protocols, Prentice Hall, NJ, USA, 2004.
 A. Boukerche, Algorithms and Protocols for Wireless and Mobile Ad Hoc Networks. John Wiley & Sons, Inc., Hoboken, New Jersey, 2009.
 S. Basagni, M. Conti, S. Giordano, I. Stojmenovic, Mobile Ad Hoc Networking, John Wiley & Sons, Inc., Hoboken, New Jersey, 2004.
 L.M. Feeney, "A Taxonomy for Routing Protocols in Mobile Ad hoc Networks", SICS Technical Report T99/07, October 1999.
 I. Chakeres, C.E. Perkins, "Dynamic MANET On-demand Routing Protocol (DYMO)", Internet Draft <draft-ietf-manet-dymo-21.txt>, July 2010.
 Z. Liu, M. Kwiatkowska, C. Constantinou, "A Biologically Inspired QoS Routing Algorithm for Mobile Ad Hoc Networks". International Journal of Wireless and Mobile Computing. vol. 4, no. 2, 2010, pp. 64-75.
 J. Wang, E. Osagie, P. Thulasiraman, R.K. Thulasiram, "HOPNET: A hybrid ant colony optimization routing algorithm for mobile ad hoc network", Ad Hoc Networks, vol. 7, no. 4, June 2009, pp. 690-705.
 D.B. Johnson, Y. Hu, D.A. Maltz, "Dynamic Source Routing in Ad hoc Wireless Networks", RFC 4728, February 2007.
 H. Zafar, D. Harle, I. Andonovic, M. Ashraf, "Performance Evaluation of On-demand Multipath Routing Protocols for Mobile Ad hoc Networks", Proc. Seventh IASTED International Conference of Wireless & Optical Communications (WOC), Montreal, Canada, May 2007, pp. 325-329.
 S.R. Das, C.E. Perkins, E.M. Royer, "Performance comparison of two on-demand routing protocols for ad hoc networks", Proc. INFOCOM 2000 Conference, Tel-Aviv, Israel, March 2000.
 C.E. Perkins, E.M. Royer, S. Das, "Ad hoc On-demand Distance Vector (AODV) Routing", RFC 3561, July 2003.
 C.E. Perkins, Ad hoc Networking, Addison-Wesley, 2001.
 S. Lee, M. Gerla, "Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks", Proc. IEEE International Conference on Communication, Helsinki, June 2001, pp. 3201-3205.
 H. Zafar, D. Harle, I. Andonovic, Y. Khawaja, "Performance Evaluation of Shortest Multipath Source Routing Scheme", IET Communications in Special Issue on Wireless Ad hoc Networks, vol. 3, no. 5, May 2009, pp. 700-713.
 H. Zafar, D. Harle, I. Andonovic, M. Ashraf, "SMS: Shortest Multipath Source Routing for Mobile Ad hoc Networks", Proc. 2007 IEEE International Conference on Signal Processing and Communications (ICSPC), Dubai, UAE, November 2007, pp. 97-100.
 G. Di Caro, F. Ducatelle, L. Gambardella, "AntHocNet: An Adaptive Nature-inspired Algorithm for Routing in Mobile Ad Hoc Networks", European Transactions on Telecommunications, vol. 15, no. 4, 2005.
 J. Broch, D.A. Maltz, D.B. Johnson, Y. Hu, J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols", Proc. Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, TX, October 1998, pp. 85-97.
 A.G. Jamieson, "A novel systems design approach to wireless sensor networks for industrial applications", PhD. thesis, Department of Electrical & Electronic Engineering, University of Strathclyde, Glasgow, 2008.
 E. Spaho, L. Barolli, G. Mino, F. Xhafa, V. Kolici, R. Miho, "Implementation of CAVENET and its usage for performance evaluation of AODV, OLSR and DYMO protocols in vehicular networks", Mobile Information Systems, vol. 6, no. 3, 2010, pp. 213-237.
 E. Kulla, M. Hiyama, M. Ikeda, L. Barolli, V. Kolici, R. Miho, "MANET performance for source and destination moving scenarios considering OLSR and AODV protocols", Mobile Information Systems, vol. 6, no. 4, 2010, pp. 325-339.
 S. Misra, I. Woungang, S.C. Misra (Eds.), Guide to Wireless Ad Hoc Networks, Springer, 2009.
 N. Meghanathan, "Survey of Topology-based Multicast Routing Protocols for Mobile Ad hoc Networks", International Journal of Communication Networks and Information Security (IJCNIS), vol. 3, no. 2, August 2011, pp. 124-137.
Haseeb Zafar (1,2), Nancy Alhamahmy (1), David Harle (1) and Ivan Andonovic (1)
(1) Department of Electronic & Electrical Engineering University of Strathclyde, Glasgow, UK
(2) Department of Computer Systems Engineering University of Engineering & Technology, Peshawar, Pakistan firstname.lastname@example.org
Table 1. Characteristics (strengths and weaknesses) of DSR, SMR and SMS that may affect their performance in terms of the three main metrics used in experiments; packet delivery ratio, routing overhead and average end-to-end delay. Where a characteristic may be strength or a weakness, depending on the situation / application, both possibilities are shown in the same row. DSR Metric Strengths Weaknesses Packet Aggressive caching and As DSR lacks a clear delivery multipath support enables policy of expiring ratio nodes to know more outdated cache entries, alternative routes. Which cached data may be based speeds up recovery from on stale routes, leading link breaks and reduces to transmission errors, chances of having to unsuccessful drop packets when retransmission attempts buffers are full. followed by new route requests. Such delays Intermediate nodes can increase the probability salvage packets, i.e. of packets having to be local link repair dropped due to limited possible. buffer capacities. Routing Aggressive caching makes Without a clear strategy overhead / it more likely for source for removing outdated normalized node to find a route in cache entries, there is routing load its cache to the a higher risk of nodes destination without acting based on stale initiating an RREQ. information, this results in increased network Intermediate nodes can load in the form of generate RREPs. retransmissions, error messages, route setup Intermediate nodes can etc. salvage packets, i.e. local link repair. Source routing protocol. Control and data packets TTL in IP header can be have higher overhead. used to control flooding of RREQ packets. Automatic route shortening involves more Duplicate RREQs are routing packets deleted. (gratuitous reply etc) being generated. No periodic hello messages required i.e. beaconless. Automatic route shortening possible. Shorter paths for routing and data packets result in reduced overhead. Average Aggressive caching However, as DSR lacks a end-to-end approach helps reduce clear policy of expiring delay the number of route outdated cache entries, requests required; cached data may be based speeds up route set up. on stale routes, leading to transmission errors, Intermediate nodes can unsuccessful reply to RREQs if they retransmission attempts know routes to the followed by new destination; helps speed route requests. up route establishment. Multipath supported; helps speed up recovery after a route breaks. Automatic route shortening possible. Shorter paths mean reduced propagation delay and probability of route breaks. SMR Metric Strengths Weaknesses Packet Multipath protocol. Using the relatively delivery Minimizes effect of restrictive criterion ratio broken path on data of "maximum transmission. Also allows disjointedness" reduces load balancing, which the number of prevents traffic from alternative paths that being concentrated over can be found. highly popular links, congesting them and More route requests increasing the initiated which add probability of packet (unnecessary) load to drops. the network, increasing congestion and Selecting maximally probability of dropping disjoint paths makes packets. protocol more robust; alternative path is less likely to be affected if a link breaks on first path. Local link repair is possible, this reduces probability of dropping packets if buffers get full as they wait for an alternative path to be found. SMR-1 is more robust; it launches an RREQ whenever one of the alternative paths breaks. Routing Intermediate nodes only Intermediate nodes overhead / forward duplicate RREQs cannot reply to RREQs. normalized if they arrive on routing load different link than This might introduce first RREQ received, and delay if the remaining do not have a larger hop route breaks, since count. packets have to be buffered until a new Local link repair route is set up. possible. Upstream node still has to send an Source routing protocol. RRER to the source, but Control and data packets it saves a potential have higher overhead. route request. No periodic hello messages required i.e. beaconless. SMR-2 does not start a new route request as long as it still has a path to the destination. Average The first path set up Alternative path(s) is end-to-end is the shortest path. not necessarily short, delay since the only criterion In case 2 paths are is disjointed-ness. equally disjoint, the one with the shortest Intermediate nodes hop count is selected. cannot reply to RREQs, If hop counts are equal, which means even if a the one with lower delay path is available, the is selected. RREQ still has to travel to the destination and Local link repair back. possible. Minimizes delay when route breaks; data transmission can resume without waiting for a new path to be found. SMS Metric Strengths Weaknesses Packet Multipath protocol. Selecting partially delivery Minimizes effect of disjoint routes means ratio broken path on data that several routes may transmission. Also be invalidated at once allows load balancing, if one common link which prevents traffic breaks. If no other from being concentrated routes exist the source over highly popular will have to find new links, congesting them route while packets are and increasing the buffered. probability of packet drops. More likely to find alternative paths since it considers partial disjointedness. Local link repair is possible, this reduces probability of dropping packets if buffers get full as they wait for an alternative path to be found. Routing Intermediate nodes only Intermediate nodes overhead / forward duplicate RREQs cannot reply to RREQs. normalized if they travelled routing load through a shorter number Source routing protocol. of hops than Control and data packets previously-received have higher overhead. RREQs. Local link repair possible. Upstream node still has to send an RRER to the source, but it saves a potential route request. No periodic hello messages required i.e. beaconless. Average Favors shorter paths. Selecting partially end-to-end Source selects paths disjoint routes means delay from the RREPs that several routes may corresponding to the 1st be invalidated at once few RREQs the if one common link destination receives, breaks. Route set up i.e. the shortest paths. delay is introduced if source has no other Multipath protocol. routes to destination Quick recovery after and a new one has to be route breaks. Also established. allows load balancing, which prevents traffic from being concentrated over highly popular links, congesting them and increasing delay. More likely to find alternative paths since it considers partial disjointedness. Table 2. Characteristics (strengths and weaknesses) of AODV and AntHocNet that may affect their performance in terms of the three main metrics used in experiments; packet delivery ratio, routing overhead and average end-to-end delay. Where a characteristic may be strength or a weakness, depending on the situation / application, both possibilities are shown in the same row. AODV Metric Strengths Weaknesses Packet Diligent book-keeping Unipath protocol. If a delivery (such as sequence numbers, route breaks, packets may ratio hello messages) prevent be dropped if buffers get the use of outdated full while an alternative routing information, and path is being set up. the possibility of dropping packets as a result of buffers getting full. Routing Not a source routing Intermediate nodes do not overhead / protocol, this keeps know as much about the normalized control packets smaller. network, so they are more routing likely to initiate RREQs RERRs are efficiently etc. sent to precursors only. Intermediate nodes can reply to RREQs if they know of routes to the destination, reducing routing overhead. An expanding ring search can be implemented using IP header TTL field to control flooding of RREQ packets Duplicate RREQs are only forwarded by intermediate nodes if they have travelled through a shorter path in terms of hop number and destination has higher sequence number (i.e. more up to date) Average Sequence numbers, end-to-end explicit routing table delay entry timeouts prevent use of stale routing data and the associated delays. Hello messages keep routing tables up to date Keeping track of precursors in routing tables ensures that RERRs are propagated more efficiently. Intermediate nodes can reply to RREQs if they know of routes to the destination, speeding up the set up of new routes. AntHocNet Metric Strengths Weaknesses Packet Multipath protocol, AntHocNet seems more delivery minimizes recovery time computationally complex ratio after a link fails. If than other protocols. If finding another path nodes do not have takes too long, buffered sufficient processing packets maybe dropped. capacity, this may result in overloading nodes, Goodness of a link congestion, packet loss (pheromone values) etc. determined by delay, congestion and distance These messages add (hop count), increases additional load to the robustness. network. Stochastic routing (with Link notifications may proactive ants & hello leave "dangling links", messages) allows whereby packets may be automatic load balancing, routed over non- existent which prevents some links links, possibly causing from being overloaded delay and packet loss. Intermediate nodes apply a higher factor in determining whether to delete or broadcast duplicate forward ants that arrive over different links, encouraging the use of diverse paths and increasing robustness. Proactive ants and hello messages keep nodes' routing information updated, avoiding the use of stale routes and packet drops that may result. Failure notification is quite efficient, making sure concerned nodes are informed of a link break promptly to avoid the use of outdated links, which may result in packets being dropped. Local link repair is possible, with intermediate nodes not only checking for alternative routes in their cache but also generating local repair ants. Routing Duplicate reactive ants A lot of different types overhead / are forwarded if they of control messages are normalized are within a certain exchanged. High overhead routing limit from previously reduces the efficiency of received ants. the protocol. Proactive ant broadcasts limited to a certain number, after which if it does not find the destination, the ant is deleted. Average Multipath protocol, Link notifications may end-to-end minimizes recovery time leave "dangling links", delay after a link fails. whereby packets may be routed over non-existent Goodness of a link links, possibly causing (pheromone values) delay. determined by delay, congestion & distance (hop count), so that the most efficient paths are used. Stochastic routing (with proactive ants & hello messages) allows automatic load balancing, preventing overloading some links & delaying transmission. Failure notification is quite efficient, making sure concerned nodes are informed of a link break promptly to avoid the use of outdated links. Local repair allowed, where intermediate node sends local repair ant to find an alternative path if it does not have one. Speeds up recovery following link break. Table 3. Results of simulations run in  comparing DSDV-SQ, DSR and AODV-LL, with possible justification for the observed performance and comments. Protocol Variable Metric Results / Observations DSR Vs. Node mobility Packet Packet deliver ratio in AODV  (pause time) delivery DSR and AODV-LL are and network ratio unaffected by the number load (number of sources. DSR maintains of sources) a packet delivery ratio of about 0.98 and above for all pause times. AODV-LL ratio remains above 0.95 for all pause times. Routing DSR has lower overhead overhead than AODV-LL. Both protocols respond in a similar manner to variations in network load and mobility, although DSR has much lower absolute overhead. In both protocols, incremental overhead resulting from an addition of one more source decreases with the number of sources. Path DSR uses optimal paths optimality most of the time. Performance of AODV-LL degrades significantly at higher mobility rates, while the performance of DSR is not affected much by mobility. max speed Packet Packet delivery ratio 1m/s, number delivery for both protocols is of sources=20 ratio above 0.985 and packet delivery ratios are close. Routing Performance of both overhead protocols improves at lower node speeds. The gap between DSR and AODV-LL widens, with DSR having much lower overhead. Protocol Variable Metric Possible Justification DSR Vs. Node mobility Packet In terms of packet AODV  (pause time) delivery delivery ratio, the and network ratio results show that DSR's load (number aggressive routing of sources) approach results in little improvement over AODV-LL's careful bookkeeping approach. Routing Routing load in DSR and overhead AODV increases as the number of sources is increased, since they are on-demand protocols. The incremental cost of adding sources decreases with a higher number of sources because both protocols use routes discovered efficiently to complete routes to other destinations. DSR's aggressive caching allows it to avoid some route requests. Being a multipath protocol helps it switch over to an alternative route when the one in use breaks. As implemented here, RREQs are flooded in AODV-LL, but not in DSR, which uses non-propagating RREQs first. Path DSR's gathers a lot of optimality information about the network, through aggressive routing, promiscuous listening etc, enabling it to select better paths. The automatic route shortening option of DSR may be helpful here too. max speed Packet The performance of both 1m/s, number delivery DSR and AODV-LL improves of sources=20 ratio in this less-challenging environment. Routing Protocol performance overhead improves when node mobility is decreased, since the environment becomes less challenging. DSR's routing cache becomes more efficient, as network status changes less often. The same applies to AODVLL's routing table entries, which require less frequent updates. Nonpropagating RREQs are used in DSR, while AODV-LL floods RREQs. Protocol Variable Metric Comments on results DSR Vs. Node mobility Packet AODV  (pause time) delivery and network ratio load (number of sources) Routing The results here may be overhead affected by the fact that non-propagating RREQs are used in DSR, while no similar features are used in AODV-LL, where RREQs are simply flooded. Path optimality max speed Packet 1m/s, number delivery of sources=20 ratio Routing The results here may be overhead affected by the fact that non-propagating RREQs are used in DSR, while no similar features are used in AODV-LL, where RREQs are simply flooded. Table 4. Results of simulations carried out in , with possible justifications and comments Protocol Variable Metric Results / Observations DSR Vs. 50 nodes, Packet For 10 and 20 sources, AODV  10, 20, delivery the 2 protocols deliver 30 & 40 fraction nearly the same ratio of sources packets. When the number of sources is increased to 30 and 40, AODV delivers a significantly higher number of packets, increasingly so at higher mobility. Average AODV has higher delay when end-to-end 10 and 20 sources are used, delay of especially at higher packets mobility. But when 30 and 40 sources are used, DSR has much higher delay, particularly at higher mobility. Both protocols exhibit significantly higher delays with 40 sources. Normalized DSR maintains a much lower routing routing load throughout, load with the gap between the 2 protocols widening with higher mobility and a larger number of sources. DSR's routing overhead increases proportionally with as the number of sources is increased. 100 nodes, Packet DSR's packet delivery ratio 10, 20 & delivery is slightly higher with 10 40 sources fraction sources, but its performance gets much worse with increased network load. In the toughest scenario (highest mobility and 40 sources), DSR delivers about 50% of the packets, while AODV delivers 75%. Average For 10 sources, DSR has end-to-end lower delay than AODV. But delay of its delay quickly increases packets with higher network load. In the toughest scenario, DSR experiences roughly double the average delay of AODV. Normalized DSR always keeps its routing routing overhead lower than load that of AODV, although the gap between the two is not as wide as it was for the 50 node case. The increase in DSR's overhead with increasing number of sources is not as linear as it was for the 50 source case. 100 nodes, Throughput Using both 10 sources and 10 & 40 40 sources, AODV has higher sources, throughput than DSR zero pause time Average At lower offered load, up delay to 210 Kbits/sec, AODV has higher delay than DSR. At higher loads DSR's delay becomes higher, with the gap between the two protocols widening with increasing offered load. Routing Although routing load of load both protocols increases as a result of increasing the number of sources, DSR has lower routing overhead at both 10 and 40 sources. Protocol Variable Metric Possible Justification DSR Vs. 50 nodes, Packet Higher mobility causes AODV  10, 20, delivery frequent network topology 30 & 40 fraction changes, making DSR more sources likely to route data based on outdated cache data. After several unsuccessful attempts the source would have to initiate a new route request. In the meantime more packets would have to be buffered, and even dropped if buffers get full. The situation is aggravated with an increased number of sources, since that increases congestion and probability of packets being dropped. Average Again, at higher mobility end-to-end DSR is more likely to route delay of packets based on outdated packets routing information, unlike AODV which periodically expires unused routing table entries and prefers fresher routes. The difference is more visible at higher congestion. Normalized Aggressive caching allows routing DSR to save some route load requests and allows nodes to gather more information about the network without adding to the overhead. 100 nodes, Packet As expected, higher network 10, 20 & delivery load worsens the performance 40 sources fraction of both protocols. DSR being more likely to route data based on outdated information is more likely to drop packets. Average Again, the performance of end-to-end both protocols worsens with delay of an increased number of packets nodes. Increasing mobility makes DSR more likely to exhibit higher delay because it has no clear mechanism of ensuring its routing information is fresh. Using outdated information results in retransmissions, congestion and possibly packet drops. Normalized Aggressive caching allows routing DSR to save some route load requests and allows nodes to gather more information about the network without adding to the overhead. However, low routing overhead is affected by the congestion resulting from the increase in the number of sources 100 nodes, Throughput This reflects AODV's higher 10 & 40 packet delivery ratio at sources, higher mobility and zero pause congestion levels. time Average This reflects DSR's higher delay delay, which is mainly caused by its use of outdated routing information especially at higher mobility and congestion rates. Routing Aggressive routing helps load keep DSR's routing load lower than that of AODV Protocol Variable Metric Comments on results DSR Vs. 50 nodes, Packet AODV  10, 20, delivery 30 & 40 fraction sources Average end-to-end delay of packets Normalized Normalized routing load is routing measured in packets, not load bytes, so the additional overhead resulting from source routing is not considered. 100 nodes, Packet 10, 20 & delivery 40 sources fraction Average end-to-end delay of packets Normalized routing load 100 nodes, Throughput 10 & 40 sources, Average zero pause delay time Routing Although the offered load load and throughput are measured in Kbits/sec, DSR's routing load does not include the additional bytes resulting from source routing. Table 5. Results of simulations presented in  comparing the performance of SMR-1 and SMR-2 to DSR, along with possible justifications for performance observed. Protocol Variable Metric Results / Observations SMR-1 Vs. Pause time Packet SMR-2 delivers the largest SMR-2 Vs. 0-300s [50 delivery number of packets, unipath nodes, ratio followed by SMR-1 then DSR. DSR 20 data (unipath) sessions, No of More packets are dropped  1000mx1000m, packets in DSR, followed by SMR-1 min (data and then SMR-2. speed=0m/s, control) max dropped speed=10m/s] Normalized DSR has the lowest routing routing load in static conditions, load but once nodes start to move its routing load increases. SMR-1 has the highest routing load, and SMR-2has the lowest except at zero mobility. Average SMR-2 has the lowest hop average hop distance at distance higher mobility, followed by SMR-1. DSR has the lowest hop distance at low to zero mobility Average DSR has the highest delay end-to-end throughout, except at zero delay mobility when its delay is lower than that of SMR-2. SMR-1 has the lowest delay throughout. Protocol Variable Metric Possible Justification SMR-1 Vs. Pause time Packet DSR, as implemented here, SMR-2 Vs. 0-300s [50 delivery stores only one path to unipath nodes, ratio the destination, when that DSR 20 data is invalidated a new route (unipath) sessions, No of has to be found. Also, DSR  1000mx1000m, packets is more likely to use min (data and stale routes to send data. speed=0m/s, control) Both factors cause delay max dropped and increase packet drops. speed=10m/s] The extra control overhead generated by SMR-1 as it sends more RREQs increases the load on the network, increasing packet drops. SMR-2 generates fewer route discoveries, reducing its packet drops. Normalized At zero mobility, DSR has routing the lowest routing load load because its aggressive caching is most useful and because intermediate nodes are allowed to reply to RREQs from cache. When nodes start moving the network topology changes more often and nodes are more likely to use stale routing data. SMR-1 has higher routing load than SMR-2 because the former generates more RREQs. Average At zero to low mobility, hop SMR routes are longer than distance DSR routes because the former protocols do not consider path length when selecting the alternative path, and because that is when DSR's aggressive caching is most useful. When packets have to travel through more hops, they are more likely to be dropped. Average Because SMR-1 always has end-to-end an alternative route to delay the destination (if one is available) it can quickly route data through an alternative path if the original path breaks. In SMR- 2 when no alternative path is stored an additional latency is introduced while a new route is found. DSR has lowest delay at zero mobility because its aggressive caching is most useful then, when nodes move network topology changes more often, introducing delay as data is routed through paths that are no longer valid. Table 6. Results of the first set of simulations carried out in  and possible justifications of these results. In these experiments, node speed is varied. Protocol Variable Metric Results / Observations SMS Vs. Mobility Goodput When nodes are static, SMR-2 Vs. (speed of (Packet although all 3 protocols DSR  nodes) delivery should have the same Mean fraction) goodput, DSR performs speed = slightly worse. As mean 0,1,2,4, speed increases, SMS has 6,8,10 significantly higher m/s, 50 goodput than SMR- 2, which nodes, 25 in turn has higher goodput sources, than DSR. pause time=30s, Average Again, even when nodes are 700x500m, end-to-end not moving, DSR has higher 4 delay delay than SMS and SMR-2. packets/s, (discovery When mobility is introduced, 512 bytes time, DSR exhibits the highest per packet buffer delay. With increasing mean waiting speed the gap between DSR time, and SMR-2 keeps getting length of wider. SMS exhibits lower routing delay than SMR-2. path) Normalized DSR has the lowest routing normalized routing load at load all mean node speeds. Next comes SMS, with slightly higher routing load than DSR, and less routing load than SMR-2. Packet At all node speeds, SMS loss exhibits the lowest packet loss. At speeds up to 2m/s, DSR has higher packet loss than SMR-2, but as the speed is increased beyond 2m/s, SMR-2 starts to lose more packets than both DSR and SMS. Protocol Variable Metric Possible Justification SMS Vs. Mobility Goodput At zero mobility, DSR has SMR-2 Vs. (speed of (Packet lower goodput because it DSR  nodes) delivery has no backup paths to use Mean fraction) in case of link failure, speed = and so has to initiate RREQs 0,1,2,4, more often. SMR-2 and SMS 6,8,10 are more likely to have m/s, 50 backup paths. In high nodes, 25 mobility situations DSR is sources, more likely to use stale pause routing information, time=30s, resulting in errors and 700x500m, retransmissions. If buffers 4 get full packets have to packets/s, be dropped. SMS has higher 512 bytes goodput because it is more per packet likely to have more paths to a destination, since it's partially disjoint criteria is less restrictive than SMR's maximally disjoint criteria. Also, because SMS stresses the selection of shorter paths more, it is less likely to drop packets. Average Again, at zero mobility, end-to-end DSR has higher delay because delay of the lack of alternative (discovery paths and its higher time, likelihood of generating new buffer RREQs. As node speeds waiting increase, DSR's delay time, remains higher because, length of despite its aggressive routing caching, cache information path) becomes less useful as mobility increases, since nodes move out of range etc. That, combined with a unipath approach and lack of specific policies to select shorter paths means DSR requires more route discoveries and may use non-optimal routes. SMS has lower delay than SMR-2 because SMR-2's maximally disjoint paths may not always be the shortest paths, which increases delay. Furthermore, SMS is more likely to have (more) alternative routes to a destination, which reduces delay when existing routes fail. Normalized DSR has lower routing load routing because of its aggressive load caching approach, whereby nodes gather a lot of information about the network, and save some RREQs. DSR also allows intermediate nodes to reply to RREQs, unlike SMS and SMR. SMS has lower overhead than SMR-2 because it finds more alternative routes in one route discovery process. An advantage of both SMS and SMR is that they repair links locally, which reduces control packets. Packet At higher mobility rates loss nodes are more likely to try to transmit packets on links they think are intact, when in fact they are broken. If packets are not retransmitted within specified timeouts or buffer capacity etc, they may be dropped. Since SMS is more likely to find (more) alternative paths to a destination, it is less likely to lose packets because it can route data through an alternative path quickly. Table 7. Results of the second set of simulations carried out in  and possible justifications of these results. In these experiments, network load is varied. Protocol Variable Metric Results / Observations SMS Vs. Offered Goodput At lower loads, SMR-2 SMR-2 Vs. load (Packet loses slightly more packets DSR  (number of delivery than SMS. When 30-40 are sources). fraction) used, SMR and DSR have 15, 20, nearly the same (low) 25, 30, goodput. SMS performs 35 and 40 significantly better than sources. both SMR and DSR, 50 nodes, particularly when the pause number of sources is time=30s, higher than 25. 700x500m, 4 Average DSR has higher average packets/s, end-to-end delay than both SMS and 512 bytes delay SMR-2. SMR-2 has higher per average delay than SMS, packet, with the gap between the mean speed two widening as load is random increases between 0-10m/s Normalized DSR has the lowest routing routing load throughout. SMS's load routing load is slightly higher than that of DSR, and lower than SMR-2's. Packet SMS has the lowest packet loss loss throughout. DSR loses slightly more packets than SMR-2 for up to 21 sources. For higher network load, SMR-2 has higher packet loss rates than DSR. Protocol Variable Metric Possible Justification SMS Vs. Offered Goodput With higher load, packets SMR-2 Vs. load (Packet are more likely to be DSR  (number of delivery dropped due to collisions sources). fraction) resulting from congestion 15, 20, than route breaks. After 25, 30, several unsuccessful 35 and 40 attempts, a new route sources. request is initiated. 50 nodes, Unipath DSR floods an RREQ pause every time a link is time=30s, broken. SMR-2 only stores 700x500m, 1 alternative route to the 4 destination, which makes packets/s, it more likely to initiate 512 bytes route discovery processes per than SMS. In addition to packet, being more likely to find mean speed alternative routes, SMS is random also emphasizes the between selection of shorter 0-10m/s routes more than DSR and SMR-2, shorter routes translate into a lower probability of unsuccessful transmission. Average As applied here, DSR end-to-end starts a new discovery delay process whenever a route breaks. This is aggravated by higher load, which results in the generation of more route requests causing further delay and packet losses. DSR has no specific strategy for favoring shorter routes. SMR-2, being a multipath protocol, can recover from route breaks quicker than DSR. SMS's ability to find more routes to the destination helps keep its delay lower. Also SMS's operation places higher emphasis on selecting the shortest paths. Normalized DSR's aggressive routing routing helps it make the most out load of control packets transmitted. Also, allowing intermediate nodes to send RREPs reduces the routing load. However, as offered load increases, collisions and congestion increase, requiring more control packets to be transmitted. By finding more alternative paths in one route discovery cycle, SMS keeps its routing load lower than that of SMR-2. Also, selecting shorter paths reduces the probability of collisions and congestion etc with increased network load, which might be another reason why SMS has lower routing load than SMR-2. Packet Being more likely to find loss (more) alternative paths to a destination means quicker recovery from route errors. SMS also selects the shortest paths, quicker data transmission reduces probability of packets being dropped. At lower loads, SMR-2's multipath approach helps it keep its packet loss rates slightly lower than DSR's. At higher loads, DSR's aggressive caching is quite effective in reducing packet loss. With higher network load, more transmission failures occur due to collision. After several unsuccessful retransmissions, new routes have to be found. DSR is often able to find routes in its routing cache, rather than launch route discovery requests. SMR-2 has to launch more route discoveries as it only maintains a maximum of two routes to each destination. Table 8. Results of the third set of simulations carried out in  and possible justifications of these results. In these experiments the network size is varied. Protocol Variable Metric Results / Observations SMS Vs. Network Goodput SMS has the highest SMR-2 Vs. size (no. (Packet goodput for all network DSR  of nodes, area delivery sizes. SMR-2 has higher keeping node fraction) goodput than DSR for density smaller network size. When constant) - 20 the no. of nodes exceeds sources 80, DSR outperforms SMR-2, (random) although they both deliver less than half of the packets only. Average SMS exhibits the lowest end-to-end average delay for all delay network sizes. DSR exhibits higher delay than SMS and SMR-2. Normalized DSR has the lowest routing routing load for all network load sizes. SMS manages to keep its routing load slightly higher than DSR, and significantly lower than SMR-2. Packet SMS has the lowest packet loss loss for all network sizes. Performance of DSR and SMR-2 is very close in terms of packet loss for different network sizes Protocol Variable Metric Possible Justification SMS Vs. Network Goodput Since node density is held SMR-2 Vs. size (no. (Packet constant, larger networks DSR  of nodes, area delivery mean longer paths, i.e. a keeping node fraction) higher probability of link density breakages. SMS is more constant) - 20 likely to select the sources shortest paths and find (random) more alternative paths. Intermediate nodes are more likely to be able to repair links locally (since they are more likely to have alternative routes) These factors enable it to deliver more packets. DSR has no clear strategy for favoring the use of shorter paths over longer ones, and it is more likely to start a new route request whenever a path breaks. SMR-2 selects the shortest path first, but the alternative path may be unnecessarily long (but maximally disjoint). These factors help it deliver more packets than DSR in smaller networks. Average SMS selects the shortest end-to-end paths. It is also more delay likely to find (more) alternative paths to the destination, which would help it recover quicker from route breaks. DSR has to initiate more route requests than both SMS and SMR-2, since it is implemented as a unipath protocol here. DSR does not specifically favor shorter paths, while SMR-2 does not consider the length of the alternative path it selects, as long as it is the maximally disjoint path. Normalized DSR's aggressive routing routing combined with the ability load of intermediate nodes to reply to RREQs helps minimize its routing load. By selecting shorter paths and finding more alternative paths in one route discovery cycle, SMS keeps its routing load lower than that of SMR-2. Packet SMS's selection of shorter loss alternative paths helps reduce probability of dropping packets as a result of transmission failure due to congestion, limited buffer capacity etc, and speeds up recovery when links are broken, thus reducing packet loss at different network sizes. DSR's lack of a specific approach to favor shorter paths makes it more likely to transmit data over unnecessarily long paths, increasing the probability of packet loss. Being implemented as a unipath protocol here makes DSR more likely to initiate new route discovery requests, despite its aggressive caching strategy. SMR-2 does not consider path length in selecting an alternative path; transmitting data over longer paths increases chances of packet loss.
|Printer friendly Cite/link Email Feedback|
|Author:||Zafar, Haseeb; Alhamahmy, Nancy; Harle, David; Andonovic, Ivan|
|Publication:||International Journal of Communication Networks and Information Security (IJCNIS)|
|Date:||Dec 1, 2011|
|Previous Article:||Message efficient global snapshot recording using a self stabilizing spanning tree in a MANET.|
|Next Article:||Survey on incremental approaches for network anomaly detection.|