Survey of reactive and hybrid routing protocols for Mobile Ad Hoc Networks.
1. IntroductionMobile 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 [4], 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 [4].
[FIGURE 1 OMITTED]
2.2 Structure
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 [4].
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 [4]. 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 [1]. 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) [1].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 [6] and HOPNET [7].
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 [8].
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 [8].
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 [8]. However, DSR does not require cache entries to expire, and so they may remain in the cache for a long time [3]. 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 [8].
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 [8]. 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 [8].
[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 [8].
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 [1].
* 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 [1].
* 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 [11]. 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 [11].
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 [11].
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 [11].
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 [11].
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 [11]. 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 [11].
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 [12].
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 [12].
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 [12].
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 [12].
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 [12].
3.3 Split Multipath Routing (SMR)
Split multipath routing, SMR, [13] 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 [13], 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 [13] 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" [14]. 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 [14], 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 [14].
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 [14].
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 [15], 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 [14].
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 [14] 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 [2]. 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 [16].
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 [16] 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 [16], [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 [16] [[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 [16], [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 [1] gather updated information about the status of the route to the destination and [2] 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 [16], [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 [16], 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 [16]) 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 [17]. 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 [16].
* Packet Loss: Packets that are transmitted by the source, but do not reach the destination, measured in/percent and used in [14] 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 [17] 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 [17] 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 [17]. 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 [11]. As reported in [17], 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 [11] 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 [17] 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 [10] the results of which are discussed in the next section.
4.1.3 Conclusion
The results of the simulations carried out in [17] 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 [10] 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 [10] 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 [10] build on the experiments presented in [17] 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 [17], 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.
4.2.2 Conclusion
The results presented in [10] 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 [13] 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 [13].
4.3.1 Notes on simulation results
DSR is implemented as a unipath protocol. It is also unclear from [13] whether any of its optimizations or extra features, such as expanding ring search or automatic route shortening, are implemented.
4.3.2 Conclusion
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 [13], 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 [14] and [15]. 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 [14]. 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 [14], SMR-2 was implemented in these simulations, since it outperformed SMR-1 in the experiments presented in [13]. As implemented here, DSR is a unipath protocol. Additional features like expanding ring search are not implemented, since [14] states that DSR floods RREQs through the network.
4.4.2 Conclusion
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 [10] and [17]. 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 [16]. 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 [16]. 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 [16] 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.
4.5.4 Conclusion
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) [18] 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]
References
[1] C.S. Murthy, B.S. Manoj, Ad hoc Wireless Networks Architectures and Protocols, Prentice Hall, NJ, USA, 2004.
[2] A. Boukerche, Algorithms and Protocols for Wireless and Mobile Ad Hoc Networks. John Wiley & Sons, Inc., Hoboken, New Jersey, 2009.
[3] S. Basagni, M. Conti, S. Giordano, I. Stojmenovic, Mobile Ad Hoc Networking, John Wiley & Sons, Inc., Hoboken, New Jersey, 2004.
[4] L.M. Feeney, "A Taxonomy for Routing Protocols in Mobile Ad hoc Networks", SICS Technical Report T99/07, October 1999.
[5] I. Chakeres, C.E. Perkins, "Dynamic MANET On-demand Routing Protocol (DYMO)", Internet Draft <draft-ietf-manet-dymo-21.txt>, July 2010.
[6] 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.
[7] 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.
[8] D.B. Johnson, Y. Hu, D.A. Maltz, "Dynamic Source Routing in Ad hoc Wireless Networks", RFC 4728, February 2007.
[9] 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.
[10] 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.
[11] C.E. Perkins, E.M. Royer, S. Das, "Ad hoc On-demand Distance Vector (AODV) Routing", RFC 3561, July 2003.
[12] C.E. Perkins, Ad hoc Networking, Addison-Wesley, 2001.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] S. Misra, I. Woungang, S.C. Misra (Eds.), Guide to Wireless Ad Hoc Networks, Springer, 2009.
[22] 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 haseeb@eee.strath.ac.uk
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 [17] 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 [17] (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 [17] (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 [17] (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 [10], with
possible justifications and comments
Protocol Variable Metric Results / Observations
DSR Vs. 50 nodes, Packet For 10 and 20 sources,
AODV [10] 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] 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] 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 [13] 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
[13] 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
[13] 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 [14]
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 [14] 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 [14] 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 [14]
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 [14] (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 [14] (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 [14]
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 [14] 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 [14] 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) |
| Article Type: | Report |
| Date: | Dec 1, 2011 |
| Words: | 17715 |
| 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. |
| Topics: | |