Routing Classification In Ad Hoc Networks Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

This chapter provides background and describes related research efforts and existing problems in ad hoc routing protocols. Section 5.1 gives a general introduction about ad hoc networks. Section 5.2 explains several important concepts, including proactive versus reactive routing approaches and hierarchical routing. Section 5.3 describes some typical ad hoc proactive routing protocols. Section 5.4 presents several typical ad hoc reactive routing protocols. Section 5.5 provides a review of current on-demand multipath routing protocols in wireless ad hoc networks. Section 5.6 describes existing problems of current multipath routing protocols.

5.1 Ad hoc Networks

There are two architectures that allow two wireless stations to communicate with each other. The first one relies on a third fixed party (a base station) that will hand over the offered traffic from a station to another, as illustrated in Figure 5.1. This same entity will regulate the allocation of radio resources. When a source node wishes to communicate with a destination node, the former notifies the base station, which eventually establishes the communication with the destination node. At this point, the communicating nodes do not need to know about the route from one to the other. All that matters is that both source and destination nodes are within the transmission range of the base station; if one of them loses this condition, the communication will abort.

The second approach, called ad-hoc, does not rely on any stationary infrastructure. All nodes in ad hoc networks are mobile and can be connected dynamically in an arbitrary manner. Each node in such networks behaves as a router and takes part in discovery and maintenance of routes to other nodes.

Figure 5.1 Illustration of the infrastructure network model

Untitled-2.jpg

Figure 5.2 Illustration of the infrastructure-less networks

Figure 5.2 illustrates a simple 3-node ad-hoc network. In this figure, a source node S wants to communicate with a destination node D. S and D are not within transmission range of each other. Therefore, they both use the relay node R to forward packets from one to another. R functions as a host and a router at the same time. By definition, a router is an entity that determines the path to be used in order to forward a packet towards its final destination. The router chooses the next node to which a packet should be forwarded according to its current understanding of the state of the network.

Research in ad hoc networking has been going on for some time. The history of wireless ad hoc networks can be traced back to the Defense Advanced Research Projects Agency (DARPA) packet radio network (PRNet), which evolved into the survivable adaptive radio networks (SURAN) program [42]. Ad hoc networks have played an important role in military applications and related research efforts, for example, the global mobile information systems (GloMo) program [43] and the near-term digital radio (NTDR) [44] program. Recent years have seen a new spate of industrial and commercial applications for wireless ad hoc networks, as many portable computers and personal digital assistants (PDAs) equipped with wireless ports are becoming more compact and inexpensive.

Ad hoc networks have numerous potential applications. For example, the IEEE 802.11 wireless LAN standard family [45, 46, 47, 48] and the European Telecommunications Standards Institute (ETSI) HIPERLAN/2 standard [49, 50], or even Bluetooth [51], support an ad hoc mode of operation for building simple ad hoc networks. Ad hoc networks are very useful in battle-field, disasters (such as flood, fire and earthquake) recovery, emergency search-and-rescue operations, home networking, meetings or conventions in which people wish to quickly share information [2].

Wireless ad hoc networks can be broadly divided into two categories: quasi-static and mobile. In a quasi-static ad hoc network, nodes are static or portable. However, due to power controls and link failures, the resulting network topology may be dynamic. A typical sensor network [52] is an example of a quasi-static ad hoc network. In mobile ad hoc networks (MANETs), the entire network may be mobile, and nodes may move quickly relative to each other. A major technical challenge in a MANET is the design of efficient routing protocols to cope with the rapid topology changes.

5.2 Routing Classification in Ad Hoc Networks

Routing in wireless ad hoc networks is clearly different from routing found in traditional infrastructure networks. Routing in ad hoc networks needs to take into account many factors including topology, selection of routing path and routing overhead, and it must find a path quickly and efficiently. Ad hoc networks generally have lower available resources compared with infrastructure networks and hence there is a need for optimal routing. Also, the highly dynamic nature of these networks means that routing protocols have to be specifically designed for them, thus motivating the study of protocols that aim at achieving routing stability.

Designing a routing protocol for ad hoc networks is challenging because of the need to take into account two contradictory factors:

a node needs to know at least the "reachability" information to its neighbors for determining a packet route; and

the network topology can change quite often.

Furthermore, as the number of network nodes can be large, finding a route to the destinations also requires large and frequent exchange of routing control information among the nodes. Thus, the amount of update traffic can be quite high, and it is even higher when the network includes high mobility nodes, which can impact the route overhead of routing protocols in such a way that there might be no bandwidth leftover for the transmission of data packets.

In wireless ad hoc networks, the communication range of a node is often limited and not all nodes can directly communicate with one another. Nodes are required to relay packets on behalf of other nodes to allow communication across the network. Since there is no pre-determined topology or configuration of fixed routes, an ad hoc routing protocol is used to dynamically discover and maintain up-to-date routes between communicating nodes.

5.2.1 Proactive versus Reactive Approaches

Ad hoc routing protocols may generally be categorized as being either proactive or on-demand (reactive) according to their routing strategy [2]. Proactive protocols require that nodes in a wireless ad hoc network should keep track of routes to all possible destinations so that when a packet needs to be forwarded, the route is already known and can be used immediately. Any changes in topology are propagated through the network, so that all nodes know of those changes in topology. Examples include "destination-sequenced distance-vector" (DSDV) routing [53], "wireless routing protocol" (WRP) [54], "global state routing" (GSR) [55], and "fisheye state routing" (FSR) [56].

On-demand protocols only attempt to build routes when desired by the source node so that the network topology is detected as needed (on-demand). When a node wants to send packets to some destination but has no routes to the destination, it initiates a route discovery process within the network. Once a route is established, it is maintained by a route maintenance procedure until the destination becomes inaccessible or until the route is no longer needed. Examples include "ad hoc on-demand distance vector routing" (AODV) [57], "dynamic source routing" (DSR) [58], and "Cluster Based Routing protocol" (CBRP) [59].

Proactive protocols have the advantage that new communications with arbitrary destinations experience minimal delay, but suffer the disadvantage of the additional control overhead to update routing information at all nodes. To cope with this shortcoming, reactive protocols adopt the inverse approach by finding a route to a destination only when needed. Reactive protocols often consume much less bandwidth than proactive protocols, but they will typically experience a long delay for discovering a route to a destination prior to the actual communication. However, because reactive routing protocols need to broadcast route requests, they may also generate excessive traffic if route discovery is required frequently.

5.2.2 Clustering and Hierarchical Routing

Scalability is one of the important problems in ad hoc networking. Scalability in ad hoc networks can be broadly defined as the network's ability to provide an acceptable level of service to packets even in the presence of a large number of nodes in the network. In proactive routing protocols, when the number of nodes in the network increase, the number of topology control messages increases non-linearly and they may consume a large portion of the available bandwidth. In reactive routing protocols, large numbers of route requests to the entire network may eventually become packet broadcast storms. Typically, when the network size increases beyond certain thresholds, the computation and storage requirements become infeasible. When mobility is considered, the frequency of routing information updates may be significantly increased, thus worsening the scalability issues.

One way to address these problems and to produce scalable and efficient solutions is hierarchical routing. Wireless hierarchical routing is based on the idea of organizing nodes in groups and then assigning nodes different functionalities inside and outside a group. Both the routing table size and update packet size are reduced by including in them only part of the network. For reactive protocols, limiting the scope of route request broadcasts also helps to enhance efficiency. The most popular way of building hierarchy is to group nodes geographically close to each other into clusters. Each cluster has a leading node (cluster head) to communicate with other nodes on behalf of these clusters.Examples of hierarchical ad hoc routing protocols include "zone routing protocol" (ZRP) [60] and "zone-based hierarchical link state" (ZHLS) routing protocol [61].

5.3 Review of Ad hoc Proactive Routing Protocols

This section presents brief descriptions for several existing proactive routing protocols.

5.3.1 Dynamic Destination-Sequenced Distance-Vector Routing

The Destination-Sequenced Distance-Vector (DSDV) Routing Algorithm [53] is a proactive hop-by-hop distance vector routing protocol, which is based on the idea of the classical Bellman-Ford Routing Algorithm with certain improvements. Every mobile station maintains a routing table that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from new ones to avoid the formation of loops. The stations periodically transmit their routing tables to their immediate neighbors. A station also transmits its routing table if a significant change has occurred in its table from the last update sent. The update is both time-driven and event-driven.

The routing table updates can be sent in two ways:

a "full dump" where the full routing table is sent to the neighbors

(which could span many packets); or

an incremental update where only those entries from the routing table

that have had a metric change since the last update are sent (and these

must fit in a single packet).

If there is space in the incremental update packet, then those entries whose sequence number has changed may be included. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dumps are relatively infrequent. In a fast-changing network, incremental packets can grow large so full dumps will be more frequent.

Each route update packet, in addition to the routing table information, also contains a unique sequence number assigned by the transmitter. The route labeled with the highest (i.e. most recent) sequence number is used. If two routes have the same sequence number then the route with the best metric (i.e. shortest route) is used. Based on past history, the stations estimate the settling time of routes. The stations delay the transmission of a routing update by settling time as to eliminate those updates that would occur if a better route were found very soon.

5.3.2 The Wireless Routing Protocol (WRP)

The Wireless Routing Protocol (WRP) [54] is a proactive distance-vector routing protocol. Each node in the network maintains a distance table, a routing

table, a link-cost table and a message retransmission list.

The distance table of a node x contains the distance of each destination node y via each neighbor z of x. It also contains the downstream neighbor of z through which this path is realized.

The routing table of node x contains the distance of each destination node from node x, the predecessor and the successor of node x on this path. It also contains a tag to identify if the entry is a simple path, a loop or invalid. Storing predecessor and successor in the table enables loops to be detected.

The link-cost table contains the cost of the link to each neighbor of the node and the number of timeouts since an error-free message was received from that neighbor.

The message retransmission list (MRL) contains information to let a node know which of its neighbors has not acknowledged its update message and to retransmit update message to that neighbor.

Nodes periodically exchange routing tables with their neighbors using update messages as well as on link changes. The nodes present on the response list for the update message (formed using the MRL) are required to acknowledge the receipt of the update message. If there is no change in the routing table since last update, the node is required to send an idle "Hello" message to ensure connectivity. On receiving an update message, the node modifies its distance table and looks for better paths using the new information. Information is sent back to the original nodes about any new paths found so that their tables can be updated. The routing table is also updated if the new path is better than the existing path.

5.3.3 Global State Routing (GSR)

Global State Routing (GSR) [55] is similar to DSDV in that it takes the idea of link state routing but makes an improvement by reducing the flooding of routing messages.

In this algorithm, each node maintains a neighbor list, a topology table, a next hop table and a distance table.

The neighbor list of a node contains the list of its neighbors (all nodes

that can be heard by it).

The link state information for each destination is maintained in the topology table together with the timestamp of the information.

• The next hop table contains the next hop to which the packets for each destination must be forwarded.

• The distance table contains the shortest distance to each destination node.

The routing messages are generated on a link change as in all link state

protocols. When it receives a routing message, the node updates its topology table if the sequence number of the message is newer than the sequence number stored in the table and it then reconstructs its routing table and broadcasts the information to its neighbors.

5.3.4 Fisheye State Routing (FSR)

Fisheye State Routing (FSR) [56] is an improvement of GSR. The large size of update messages in GSR wastes a considerable amount of network bandwidth, so to reduce this, FSR takes an approach where each update message does not contain information about all nodes. Instead, it exchanges information about closer nodes more frequently than it does about farther nodes, thus reducing the update message size. In this way, each node gets accurate information about near neighbors and accuracy of information decreases as the distance from the node increases.

Even though a node does not have accurate information about distant nodes, the packets are routed correctly because the route information becomes more and more accurate as the packet moves closer to the destination.

5.4 Review of Ad hoc Reactive Routing Protocols

Reactive protocols take a lazy approach to routing. In contrast to proactive routing protocols, all up-to-date routes are not maintained at every node, but instead the routes are created as and when required. When a source wants to send to a destination, it invokes the route discovery mechanisms to find the path to the destination. In this section several typical reactive (on-demand) routing protocols are introduced.

5.4.1 Ad Hoc On-demand Distance Vector Routing (AODV)

Ad hoc on-demand distance vector (AODV) routing [57] adopts both a modified on-demand broadcast route discovery approach used in DSR [58] and the concept of destination sequence number adopted from destination-sequenced distance-vector routing (DSDV)[53].

When a source node wants to send a packet to some destination and does not have a valid route to that destination, it initiates a path discovery process and broadcasts a route request (RREQ) message to its neighbors. The neighbors in turn forward the request to their neighbors until the RREQ message reaches the destination or an intermediate node that has an up-to-date route to the destination.

Figure 5.3(a) illustrates the propagation of the broadcast RREQs in an ad hoc network.

Destination

RREQ messages propagation

Destination

Source

(b) RREP message sent back to source

Figure 5.3 Route discovery in AODV

In AODV, each node maintains its own sequence number and a broadcast ID. Each RREQ message contains the sequence numbers of the source and destination nodes and is uniquely identified by the source node's address and a

broadcast ID. AODV utilizes destination sequence numbers to ensure loop-free routing and use of up-to-date route information. Intermediate nodes can reply to the RREQ message only if they have a route to the destination whose destination sequence number is greater or equal to that contained in the RREQ message.

So that a reverse path can be set up, each intermediate node records the address of the neighbor from which it received the first copy of the RREQ message, and additional copies of the same RREQ message are discarded. Once the RREQ message reaches the destination (or an intermediate node with a fresh route) the destination (or the intermediate node) responds by sending a route reply (RREP) packet back to the neighbor from which it first received the RREQ message. As the RREP message is routed back along the reverse path, nodes along this path set up forward path entries in their routing tables (Figure 5.3(b)).

When a node detects a link failure or a change in neighborhood, a route maintenance procedure is invoked:

If a source node moves, it can restart the route discovery procedure to find a new route to the destination.

If a node along the route moves so that it is no longer contactable, its upstream neighbor sends a link failure notification message to each of its active upstream neighbors. These nodes in turn forward the link failure notification to their upstream neighbors until the link failure notification reaches the source node.

5.4.2 Dynamic Source Routing (DSR)

Dynamic source routing (DSR) [58] is an on-demand routing protocol for wireless ad hoc networks. DSR is based on the concept of source routing, in which a source node indicates the sequence of intermediate routes in the header of a data packet. Like other on-demand routing protocols, the operation of DSR can be divided into two procedures: route discovery and route maintenance.

(a) Building Record Route

Destination

(a) RREP Propagation

Figure 5.4 Route discovery in DSR

Each node in the network keeps a cache of the source routes that it has learned. When a node needs to send a packet to some destination, it first checks its route cache to determine whether it already has an up-to-date route to the destination. If no route is found, the node initiates the route discovery procedure by broadcasting a route request message to neighboring nodes. This route request message contains the address of the source and destination nodes, a unique identification number generated by the source node, and a route record to keep track of the sequence of hops taken by the route request message as it is propagated through the network. When an intermediate node receives a route discovery request, it checks whether its own address is already listed in the route record of the route request message. If not, it appends its address to the route record and forwards the route request to its neighbors. Figure 5.4(a) illustrates the formation of the route record as the route request propagates through the network.

When the destination node receives the route request, it appends its address to the route record and returns it to the source node within a new route reply message. If the destination already has a route to the source, it can use that route to send the reply; otherwise, it can use the route in the route request message to send the reply. The first case is for situations where a network might be using unidirectional links and so it might not be possible to send the reply using the same route taken by the route request message. If symmetric links are not supported, the destination node may initiate its own route discovery message to the source node and piggyback the route reply on the new route request message. Figure 5.4(b) shows the transmission of route record back to the source node.

Route maintenance uses route error messages and acknowledgement messages. If a node detects a link failure when forwarding data packets, it creates a route error message and sends it to the source of the data packets. The route error message contains the address of the node that generates the error and the next hop that is unreachable. When the source node receives the route error message, it removes all routes from its route cache that have the address of the node in error. It may initiate a route discovery for a new route if needed. In addition to route error message, acknowledgements are used to verify the correct operation of links.

To reduce the route search overhead, an important optimization is allowing an intermediate node to send a route reply to the source node if it already has an up-to-date route to the destination.

5.4.3 Cluster based Routing Protocol (CBRP)

In Cluster Based Routing protocol (CBRP) [59], the nodes are divided into clusters. To form the cluster the following algorithm is used. When a node comes up, it enters the "undecided" state and broadcasts a Hello message. When a

cluster-head gets this hello message it responds with a triggered hello message immediately. When the undecided node gets this message it sets its state to "member". If the undecided node times out, then it makes itself the cluster-head if it has bi-directional link to some neighbor otherwise it remains in undecided state and repeats the procedure again. Cluster-heads are changed as infrequently as possible.

Each node maintains a neighbor table. For each neighbor, the neighbor table of a node contains the status of the link and the state of the neighbor (cluster-head or member). A cluster-head keeps information about the members of its cluster and also maintains a cluster adjacency table that contains information about the neighboring clusters. For each neighbor cluster, the table has entry that contains the gateway through which the cluster can be reached and the cluster-head of the cluster.

When a source has to send data to destination, it floods route request packets (but only to the neighboring cluster-heads). On receiving the request a cluster-head checks to see if the destination is in its cluster. If yes, then it sends the request directly to the destination else it sends it to all its adjacent cluster-heads. The cluster-heads address is recorded in the packet so a cluster-head discards a request packet that it has already seen. When the destination receives the request packet, it replies back with the route that had been recorded in the request packet. If the source does not receive a reply within a time period, it backs off exponentially before trying to send route request again.

In CBRP, routing is done using source routing. It also uses route shortening that is on receiving a source route packet, the node tries to find the farthest node in the route that is its neighbor and sends the packet to that node thus reducing the route. While forwarding the packet if a node detects a broken link it sends back an error message to the source and then uses local repair mechanism. In local repair mechanism, when a node finds the next hop is unreachable, it checks to see if the next hop can be reached through any of its neighbor or if hop after next hop can be reached through any other neighbor. If any of the two works, the packet can be sent out over the repaired path.

Table 5.1 shows and compares the unipath routing protocols for mobile ad hoc networks.

DSDV

WRP

GSR

FSR

AODV

DSR

CBRP

Routing Category

Proactive

Proactive

Proactive

Proactive

Reactive

Reactive

Reactive

Beaconing

Yes

Yes

Yes

Yes

Yes

Yes

Yes

Periodic Update

Yes

Yes

Yes

Yes

No

No

No

Flood Control

No

No

No

Yes

Yes

Yes

Yes

TTL Limitation

No

No

No

No

Yes

Yes

Yes

QoS Support

No

No

No

No

No

No

No

Multicast Support

No

No

No

No

Yes

No

No

Power Management

No

No

No

No

No

No

No

Security Support

No

No -

No

No

No

No

No

Table 5.1 Comparison of the unipath routing protocols

5.5 Ad Hoc On-demand Multipath Routing Protocols

Standard on-demand routing protocols in ad hoc wireless networks, such as AODV and DSR, are mainly intended to discover a single route between a source and destination node. When the route disconnects, nodes of the broken route simply drop data packets because no alternate path to the destination is available

until a new route is established. Multipath routing is useful for finding multiple paths between a source and destination in a single discovery. These multiple paths between source and destination can be used to compensate for the dynamic and unpredictable topology change in ad hoc networks. Recently, several different multipath routing mechanisms have been proposed. This section introduces some main characteristics of these multipath protocols. AOMDV [63] and AODVM [64] routing protocols are based on the AODV [57] routing protocol, whereas SMR [62] and MSR [64] are based on DSR [58]

5.5.1 Ad hoc On-demand Multipath Distance Vector (AOMDV)

Ad hoc On-demand Multipath Distance Vector (AOMDV) [63] is an extension to the AODV protocol for computing multiple loop-free and link-disjoint paths. The protocol computes multiple loop-free and link-disjoint paths. Loop-freedom is guaranteed by using a notion of "advertised hopcount". Link-disjointness of multiple paths is achieved by using a particular property of flooding.

To keep track of multiple routes, the routing entries for each destination contain a list of the next-hops together with the corresponding hop counts. All the next hops have the same sequence number. For each destination, a node maintains the advertised hop count, which is defined as the maximum hop count for all the paths. This is the hop count used for sending route advertisements of the destination. Each duplicate route advertisement received by a node defines an alternative path to the destination. To ensure loop freedom, a node only accepts an alternative path to the destination if it has a lower hop count than the advertised hop count for that destination. Because the maximum hop count is used, the advertised hop count therefore does not change for the same sequence number. When a route advertisement is received for a destination with a greater sequence number, the next-hop list and advertised hop count are reinitialized.

AOMDV can be used to find link-disjoint routes. To find disjoint routes, each node does not immediately reject duplicate RREQs. Each RREQ carries an

additional field called first hop to indicate the first hop (neighbor of the source) taken by it. Also, each node maintains a first hop list for each RREQ to keep track of the list of neighbors of the source through which a copy of the RREQ has been received. In an attempt to get multiple link-disjoint routes, the destination replies to duplicate RREQs regardless of their first hop. To ensure link-disjointness in the first hop of the RREP, the destination only replies to RREQs arriving via unique neighbors. The trajectories of each RREP may intersect at an intermediate node, but each takes a different reverse path to the source to ensure link-disjointness.

5.5.2 Split Multipath Routing (SMR)

Split Multipath Routing (SMR) proposed in [62] is an on-demand multipath source routing protocol that builds multiple routes using a request/reply cycle. SMR can find an alternative route that is maximally disjoint from the source to the destination. When the source needs a route to the destination but no route information is known, it floods the Route Request (RREQs) message to the entire network in order to find maximally disjoint paths, so the approach has a disadvantage of transmitting more RREQ packets. Because this packet is flooded, several duplicates that traversed through different routes reach the destination. The destination node selects multiple maximally disjoint routes and sends Route Reply (RREP) packets back to the source via the chosen routes. In order to choose proper maximally disjoint route paths, the destination must know the entire path of all available routes. Therefore, SMR uses the source routing approach where the information of the nodes that comprise the route is included in the RREQ packet.

SMR is similar to DSR, and is used to construct maximally disjoint paths. Unlike DSR, intermediate nodes do not keep a route cache, and therefore, do not reply to RREQs. This is to allow the destination to receive all the routes so that it can select the maximally disjoint paths. Maximally disjoint paths have as few links or nodes in common as possible. Duplicate RREQs are not necessarily

discarded. The algorithm only selects two routes. In the algorithm, the destination sends a RREP for the first RREQ it receives, which represents the shortest delay path. The destination then waits to receive more RREQs. From the received RREQs, the path that is maximally disjoint from the shortest delay path is selected. If more than one maximally disjoint path exists, the shortest hop path is selected. If more than one shortest hop path exists, the path whose RREQ was received first is selected. The destination then sends an RREP for the selected RREQ.

5.5.3 Multipath Source routing (MSR)

Multipath Source Routing (MSR) [64, 65] is an extension of the on-demand DSR [58] protocol. It consists of a scheme to distribute traffic among multiple routes in a network. MSR uses the same route discovery process as DSR with the exception that multiple paths can be returned, instead of only one.

When a source requires a route to a destination but no route is known (in the cache), it will initiate a route discovery process by flooding a RREQ packet throughout the network. A route record in the header of each RREQ records the sequence of hops that the packet passes. An intermediate node contributes to the route discovery by appending its own address to the route record. Once the RREQ reaches the destination, a RREP will reverse the route in the route record of the RREQ and traverse back through this route.

Each route is given a unique index and stored in the cache, so it is easy to pick multiple paths from there. Independence between paths is very important in multipath routing, therefore disjoint paths are preferred in MSR As MSR uses the same route discovery process as DSR, where the complete routes are in the packet headers, looping will not occur. When a loop is detected, it will be immediately eliminated.

Since source routing is used in MSR, intermediate nodes do nothing but forward the packet according to the route in the packet-header. The routes are all calculated at the source. A multiple-path table is used for the information of each different route to a destination. This table contains for each route to the destination: the index of the path in the route cache, the destination ID, the delay and the calculated load distribution weight of a route. The traffic to a destination is distributed among multiple routes. The weight of a route simply represents the number of packets sent consecutively on that path.

5.5.4 Ad hoc On-demand Distance Vector Multipath Routing

Ad hoc On-demand Distance Vector Multipath Routing (AODVM) [64] is an extension to AODV for finding multiple node disjoint paths. Instead of discarding the duplicate RREQ packets, intermediate nodes are required to record the information contained in these packets in the RREQ table. For each received copy of an RREQ message, the receiving intermediate node records the source that generated the RREQ, the destination for which the RREQ is intended, the neighbor that transmitted the RREQ, and some additional information in the RREQ table. Furthermore, intermediate relay nodes are precluded from sending an RREP message directly to the source.

When the destination receives the first RREQ packet from one of its neighbors, it updates its sequence number and generates an RREP packet. The RREP packet contains an additional field called "last hop ID" to indicate the neighbor from which the particular copy of RREQ packet was received. This RREP packet is sent back to the source via the path traversed by the RREQ. When the destination receives duplicate copies of the RREQ packet from other neighbors, it updates its sequence number and generates RREP packets for each of them. Like the first RREP packet, these RREP packets also contain their respective last hop nodes' IDs.

When an intermediate node receives an RREP packet from one of its neighbors, it deletes the entry corresponding to this neighbor from its RREQ table and adds a routing entry to its routing table to indicate the discovered route

to the originator of the RREP packet (the destination). The node, then, identifies the neighbor in the RREQ table via which, the path to the source is the shortest, and forwards the RREP message to that neighbor. The entry corresponding to this neighbor is then deleted from the RREQ table. In order to ensure that a node does not participate in multiple paths, when nodes overhear any node broadcasting an RREP message, they delete the entry corresponding to the transmitting node from their RREQ tables.

Intermediate nodes make decisions on where to forward the RREP messages (unlike in source routing) and the destination, which is in fact the originator of these messages, is unaware as to how many of these RREP messages that it generated actually made it back to the source. Thus, it is necessary for the source to confirm each received RREP message by means of a Route Confirmation message (RRCM). The RRCM message can, in fact, be added to the first data packet sent on the corresponding route and will also contain information with regards to the hop count of the route, and the first and last hop relays on that route.

5.6 Problem with Current Multipath Routing Protocols

Previous section introduces simply routing mechanisms and benefits of several existing multipath protocols. Although these protocols can build on demand multiple routing paths, all of them will encounter a broadcast storm of routing packets in the process of looking for multiple disjoint routing paths.

When a source in these multipath routing protocols needs a route to a destination but no route information is known, it floods the Route Request (RREQ) message to the entire network. In order to ensure that the destination can select disjoint paths, all the four multipath routing protocols do not discard duplicate RREQs at intermediate nodes. Also, they do not allow intermediate nodes, which know routing information to the destination, to reply the RREQ. These lead to dramatic increase of routing overhead in the ad hoc network.

Because bandwidth in wireless ad hoc networks is limited, how to reduce routing overhead has to be considered when designing a routing protocol.

Table 2.2 compares the main characteristics of existing multipath routing protocols.

AOMDV

SMR

AODVM

MSR

Routing Category

Reactive

Reactive

Reactive

Reactive

Loop-free Paths

Yes

Yes

Yes

Yes

Routing Overhead Control

No

No

No

No

Node-disjoint Paths

No

No

Yes

Yes

Complete Routes Known at Source

No

Yes

No

Yes

Paths Used Simultaneously

Yes

Yes

Yes

Yes

TTL Limitation

Yes

Yes

Yes

Yes

QoS Support

No

No

No

No

Multicast Support

No

No

No

No

Power Management

No

No

No

No

Security Support

No

No

No

No

Table 5.2 Comparison of the multipath routing protocols

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.