A Complete Analysis of Current Routing Protocols in Mobile Adhoc Networks

The wireless networks are playing a vital role for the world of technology. The wireless networks are also called as mobile network. In mobile networks are basically classified into two main categories. The first is known as the “infrastructure networks”.

These types of networks are fixed and wired gateways. The bridges for these networks are known as “base station”. A mobile unit with in these networks connects to, and communicates with, the nearest base station that is within its communication radius. As the mobile travels out of range of one base station and into the range of another, a “handoff” occurs from the old base station to the new, and the mobile is able to continue communication seamlessly throughout the network.

The second type of mobile wireless network is the infrastructure less mobile network, commonly known as an “ad hoc network ”. Infrastructure less networks has no fixed routes; all nodes can travel throughout the network and can communicate dynamically. The mobile nodes are working as network routers, which discover and maintain routes to other nodes in the network.

This article I discussed the routing protocols designed for these ad hoc networks by first describing the operation of each of the protocols and then comparing their various characteristics. The next section presents a discussion of two subdivisions of ad hoc routing protocols. Another section discuss current table-driven protocols, while a later section describes those protocols which are classified as on-demand protocols, followed by demand-driven and on-demand protocols.

Cluster head Gateway Switch Routing

The Cluster head Gateway Switch Routing (CGSR) protocol differs from the previous protocol in the type of addressing and network organization scheme employed. Instead of a “flat” network, CGSR is a clustered multi hop mobile wireless network with several heuristic routing schemes [4]. In this method a cluster head controlling a group of ad hoc nodes, a framework for code separation, channel access, routing, and bandwidth allocation can be achieved. A cluster head selection algorithm is utilized to elect a node as the cluster head using a distributed algorithm within the cluster. In cluster head method we are having one main disadvantage, because frequently the nodes change the cluster head this will adversely affect routing protocol performance. The nodes are busy in cluster head selection rather than relaying. Hence, instead of invoking cluster head reselection every time the cluster membership changes, a Least Cluster Change (LCC) clustering algorithm is introduced. Using LCC, cluster heads only change when two cluster heads come into contact, or when a nodes moves out of contact of all other cluster heads.

The Wireless Routing Protocol

The Wireless Routing Protocol (WRP) described in [5] is a table-based protocol with the goal of maintaining routing information among all nodes in the network. Each node in the network is responsible for maintaining four tables.

• Distance table

• Routing table

• Link-cost table

• Message retransmission list (MRL) table.

Each entry of the MRL contains the sequence number of the update message, a retransmission counter, an acknowledgement-required flag vector with one entry per neighbor, and a list of updates sent in the update message. The MRL records which updates in an update message need to be retransmitted and which neighbors should acknowledge the retransmission [5]. Mobiles inform each other of link changes through the use of update messages. An update message is sent only between neighboring nodes and contains a list of updates, as well as a list of responses indicating which mobiles should acknowledge (ACK) the update. Mobiles send update messages after processing updates from neighbors or detecting a change in a link to neighbors.

Source-Initiated On-Demand Routing

Source-Initiated on-demand routing is a different approach compare to table-driven routing. In this method the path will be created by source it self. If a node wants to send message means, first it will find the path for communication. This process will be completed once a route is found or all possible route permutations have been examined. Once a route has been established, this route will be maintained until the destination becomes inaccessible.

Ad Hoc On-Demand Distance Vector Routing

The Ad Hoc On-Demand Distance Vector (AODV) routing protocol described in [7] builds on the DSDV algorithm previously described. AODV is an improved algorithm from DSDV because it typically minimizes the number of required broadcasts by creating routes on a demand basis, as opposed to maintaining a complete list of routes as in the DSDV algorithm.

When a source node desires to send a message to some destination node and does not already have a valid route to that destination, it initiates a path discovery process to locate the other node. It broadcasts a route request (RREQ) packet to its neighbors, which then forward the request to their neighbors, and so on, until either the destination or an intermediate node with a “fresh enough” route to the destination is located. AODV utilizes destination sequence numbers to ensure all routes are loop-free and contain the most recent route information. Each node maintains its own sequence number, as well as broadcast ID. The broadcast ID is incremented for every RREQ the node initiates, and together with the node’s IP address, uniquely identifies an RREQ.

Routes are maintained as follows. If a source node moves, it is able to reinitiate the route discovery protocol to find a new route to the destination. If a node along the route moves, its upstream neighbor notices the move and propagates a link failure notification message to each of its active upstream neighbors to inform them of the erasure of that part of the route [7]. These nodes in turn propagate the link failure notification to their upstream neighbors, and so on until the source node is reached. The source node may then choose to reinitiate route discovery for that destination if a route is still desired.

Dynamic Source Routing

The Dynamic Source Routing (DSR) protocol presented in [8] is an on-demand routing protocol that is based on the concept of source routing Mobile nodes are required to maintain route catches that contain the source routes of which the mobile is aware. The protocol consists of two major phases: route discovery and route maintenance. When a mobile node has a packet to send to some destination, it first consults its route cache to determine whether it already has a route to the destination, it will use this route to send the packet. The protocol consists of two major phases: route discovery and route maintenance. When a mobile node has a packet to send to some destination, it first consults its route cache to determine whether it already has a route to the destination, it will use this route to send the packet. On the other hand, if the node doses not have such a route, it initiates route discovery by broadcasting a route request packet.

A route reply is generated when the route request reaches either the destination itself, or an intermediate node which contains in its route cache an un expired route to the destination or such an intermediate node, it contains a route record yielding the sequence of hops taken. If the node generating the route reply is the destination, it places the route record contained in the route request into the route reply. If the responding node is an intermediate node, it will append its cached route to the route record and then generate the route reply. Route maintenance is accomplished through the use of route error packets and acknowledgments.

Temporally Ordered Routing Algorithm

The Temporally Ordered Routing Algorithm (TORA) is a highly adaptive loop-free distributed routing algorithm based on the concept of link reversal [10]. TORA is proposed to operate in a highly dynamic reply is the destination, mobile networking environment. It is source-initiated and provides multiple routes for any desired source/destination pair. The key design concept of TORA is the localization of control messages to a very small set of nodes near the occurrence of a topological change. To accomplish this, nodes need to maintain routing

information about adjacent (one-hop) nodes.The protocol performs three basic functions:

• Route creation

• Route maintenance

• Route erasure

During the route creation and maintenance phases, nodes use a “height” metric to establish a directed a cyclic graph (DAG) rooted at the destination. Thereafter, links are assigned a direction (upstream or downstream) based on the relative height metric of neighboring nodes. This process of establishing a DAG is similar to the query/reply process proposed in Lightweight Mobile Routing (LMR) [11]. In times of node mobility the DAG route is broken, and route maintenance is necessary to reestablish a DAG rooted at the same destination. As shown in Fig. 5b, upon failure of the last downstream link, a node generates a new reference level which results in the propagation of that reference level by neighboring nodes, effectively coordinating a structured reaction to the failure. Links are reversed to reflect the change in adapting to the new reference level. TORA’s metric is a quintuple comprising five elements, namely:

• Logical time of a link failure

•The unique ID of the node that defined the new reference level

•A reflection indicator bit

•A propagation ordering parameter

•The unique ID of the node

The first three elements collectively represent the reference level. A new reference level is defined each time a node loses its last downstream link due to a link failure. TORA’s route erasure phase essentially involves flooding a broadcast clear packet (CLR) throughout the network to erase invalid routes. In TORA there is a potential for oscillations to occur, especially when multiple sets of coordinating nodes are concurrently detecting partitions, erasing routes, and building new routes based on each other. Because TORA uses internodes coordination, its instability problem is similar to the “count-to-infinity” problem in distance-vector routing protocols, except that such oscillations are temporary and route convergence will ultimately occur.

Source-Initiated On-Demand Routing Protocols

Table 2 presents a comparison of AODV, DSR, TORA, ABR, and SSR. AODV employs a route discovery procedure similar to DSR; however, there are a couple of important distinctions. The most notable of these is that the overhead of DSR is potentially larger than that of AODV since each DSR packet must carry full routing information, whereas in AODV packets need only contain the destination address. Similarly, the route replies in DSR are larger because they contain the address of every node along the route, whereas in AODV route replies need only carry the destination IP address and sequence number. Also, the memory overhead may be slightly greater in DSR because of the need to remember full routes, as opposed to only next hop information in AODV. The DSR algorithm is intended for networks in which the mobiles move at moderate speed with respect to packet transmission latency [8]. Assumptions the algorithm makes for operation are that the network diameter is relatively small and that the mobile nodes can enable a promiscuous receive mode, whereby every received packet is delivered to the network driver software without filtering by destination address. An advantage of DSR over some of the other on demand protocols is that DSR does not make use of periodic routing advertisements, thereby saving bandwidth and reducing power consumption. On the other hand, because of the small diameter assumption and the source routing requirement, DSR is not scalable to large networks. Furthermore, as previously stated, the need to place the entire route in both route replies and data packets causes greater control overhead than in AODV.

TORA is a “link reversal” algorithm that is best suited for networks with large dense populations of nodes [10]. One of the advantages of TORA is its support for multiple routes. TORA and DSR are the only on demand protocols considered here which retain multiple route possibilities for a single source/destination pair. Route reconstruction is not necessary until all known routes to a destination are deemed invalid, and hence bandwidth can potentially be conserved because of the necessity for fewer route rebuilding. Another advantage of TORA is its support for multicast. Although, unlike AODV, TORA does not incorporate multicast into its basic operation, it functions as the underlying protocol for the Lightweight Adaptive Multicast Algorithm (LAM), and together the two protocols provide multicast capability [18]. ABR is a compromise between broadcast and point-to point routing, and uses the connection-oriented packet forwarding approach. Route selection is primarily based on the aggregated associatively ticks of nodes along the path. Hence, although the resulting path does not necessarily result in the smallest possible number of hops, the path tends to be longer lived than other routes.

A long-lived route requires fewer route reconstructions and therefore yields higher throughput. Another benefit of ABR is that, like the other protocols, it is guaranteed to be free of packet duplicates. The reason is that only the best route is marked valid, while all other possible routes remain passive. ABR, however, relies on the fact that each node is beaconing periodically. The beaconing interval must be short enough to accurately reflect the spatial, temporal, and connectivity state of the mobile hosts. This beaconing requirement may result in additional power consumption. However, experimental results obtained in [19] reveal that the inclusion of periodic beaconing has a minute influence on the overall battery power consumption. Unlike DSR, ABR does not utilize route caches.

Table-Driven vs. On-Demand Routing

As discussed earlier, the table-driven ad hoc routing approach is similar to the connectionless approach of forwarding packets, with no regard to when and how frequently such routes are desired. It relies on an underlying routing table update mechanism that involves the constant propagation of routing information. This is not the case, however, for on-demand routing protocols. When a node using an on-demand protocol desires a route to a new destination, it will have to wait until such a route can be discovered. On the other hand, because routing information is constantly propagated and maintained in table-driven routing protocols, a route to every other node in the ad hoc network is always available, regardless of whether or not it is needed. Another consideration is whether a flat or hierarchical addressing scheme should be used. All of the protocols considered here, except for CGSR, use a flat addressing scheme. In [20] a discussion of the two addressing schemes is presented. While flat addressing may be less complicated and easier to use, there are doubts as to its scalability.

Localized Position-Based Routing Algorithms

This will be new algorithm for routing and also it’s a very effective routing algorithm for a large type of MANET. Here using position identifies the nodes. Here the node ID’s are constructed by using some position related parameters. Here we are going to discourse various type of position based routing algorithms. Localized position-based routing algorithms [25] are distributed algorithms. Each host makes the routing decision solely based on the location information of itself, its neighbors, the source and the destination. Let u be the current node, (v1,….,vn) be the 1-hop neighboring nodes of u, s be the source node and t be the destination node. The hop counts of the path discovered by the algorithm between the nodes s and t is denoted by NL(s, t). The hop counts of the shortest path between the nodes s and t is denoted by ND(s, t). We define the hop stretch factor as SF(s, t) = NL(s,t)/ND(s,t) . We now specify four well-known routing algorithms that are used for a comparison with the routing algorithm proposed in this paper.

Compass Routing [26]

The current node u selects its neighboring node that forms the smallest angle, min{
Greedy Routing [27]

The current node u selects its neighboring node that is the closest, min{d(v1, t),…., d(vn ,t)}, to the destination node t.

Ellipsoid Routing [28]

The current node u selects its neighboring node that gives the smallest sum of distances, min{d(v1; u) + d(v1; t),….,d(vn; u) + d(vn; t)}, from itself to the neighboring node and then to the destination.

Most Forward Routing [29]

Let (v1,….,vn ) be the nodes projected on the line ut respectively. The current node u selects its neighboring node whose projected node is the closest, min{d(v1 ; t),…., d(vn ; t)}, to the destination node.

Projective Face Routing

Face routing [30,31], by using the right-hand rule, guarantees the delivery on a 2-D geometric planar graph. The line st that connects the source and destination nodes determines the 2-D faces to be traversed. However, this line does not determine these faces in a 3-D graph. This algorithm is thus not directly applicable on a 3-D graph. We propose a heuristic using the projective approach to deal with the problem described above. Although this approach does not guarantee the delivery, as a planar graph cannot be extracted from the projected graph using only its local information before projection, our experiments show that the delivery rate is significantly better than the other routing algorithms. By delivery rate, we mean the percentage of successful deliveries to the destination. The algorithm is as follows. The face routing is performed on this projected graph. If the routing fails, the points are then projected onto the second plane that is orthogonal to the first plane and also contains the line st. The face routing is again performed.

Parameters DSDV CGSR WRP

Time complexity (link addition/failure) O(d) O(d) O(h)

Communication complexity (link addition/failure) O(x=N) O(x=N) O(x=N)

Loop free Yes Yes Yes, but not instantaneous

Multicast capability No No** No

Number of required tables Two Two Four

Frequency of update transmissions Periodically and as needed Periodically Periodically and as needed

Updates transmitted to Neighbors Neighbors and cluster head Neighbors

Utilizes sequence number Yes Yes Yes

Utilizes hello messages

Yes No Yes

Critical nodes

No Yes (cluster head) No

Routing metrics

Shortest path Shortest path Shortest path

Table 1. Comparison of the characteristics of Table-driven routing protocols.

Abbreviations:

N-Number of nodes in the networks
d- Network diameter
h-Height of routing tree
x- number of node affected in network topological change

** - the protocol itself currently does not support multicast; however, there is a separate protocol described in [16], which runs on top of CGSR and provides multicast capability.

Performance parameter AODV DSR TORA ABR SSR

Time complexity (postfailure) O(2d)

O(2d)

O(2d)

O(d + z)

O(d + z)

Time complexity (postfailure) O(2d)

O(2d) or 0*

O(2d)

O(l + z)

O(l + z)

Communication complexity (initialization) O(2N)

O(2N)

O(2N)

O(N + y)

O(N + y)

Communication complexity (postfailure) O(2N)

O(2N)

O(2x)

O(x + y)

O(x + y)

Routing philosophy

Flat

Flat Flat Flat Flat

Loop-free

Yes Yes Yes Yes Yes

Multicast capability

Yes

No

No**

No

No

Beaconing requirements No No No Yes Yes

Multiple route possibilities No Yes Yes No No

Routes maintained in

Route table Route cache

Route table Route table Route table

Utilizes route cache/table expiration timers Yes No No No No

Route reconfiguration methodology

Erase route;

notify source

Erase route;

notify source

Link reversal;

route repair

Localized

broadcast query

Erase route;

notify source

Routing metric

Freshest and

shortest path Shortest path

Shortest path

Associativity and shortest path and others*** Associativity and stability

Table 2. Comparisons of the characteristics of source-initiated on-demand ad hoc routing protocols.

Abbreviations:

l = Diameter of the affected network segment

y = Total number of nodes forming the directed path where the REPLY packet transits

z = Diameter of the directed path where the REPLY packet transits

* Cache hit.

** Like CGSR, TORA also does not support multicast; however, there is a separate protocol, LAM [18], which runs on top of ORA and provides multicast capability.

*** ABR also uses the route relaying load and cumulative forwarding delay as routing metrics.

Parameters On-demand Table driven

Availability of routing information

Available when needed Always available regardless of need

Routing philosophy

Flat

Mostly flat, except for CGSR

Periodic route updates

Not required

Required

Coping with mobility

Use localized route discovery as in ABR and SSR

Inform other nodes to achieve a consistent routing table

Signaling traffic generated

Grows with increasing mobility on of active routes (as in ABR) Greater than that of demand routing

Quality of service support

Few can support QoS, although most support shortest path Mainly shortest path as the QoS metric

Table 3. Overall comparisons of on-demand versus table-driven routing protocols.

Conclusion

In this article we provide descriptions of several routing schemes proposed for ad hoc mobile networks. We also provide a classification of these schemes according to the routing strategy (i.e., table-driven and on-demand). We have presented a comparison of these two categories of routing protocols, highlighting their features, differences, and characteristics. Finally, we have identified possible applications and challenges facing ad hoc mobile wireless networks. While it is not clear that any particular algorithm or class of algorithm is the best for all scenarios, each protocol has definite advantages and disadvantages, and is well suited for certain situations. The field of ad hoc mobile networks is rapidly growing and changing, and while there are still many challenges that need to be met, it is likely that such networks will see widespread use within the next few years.

References

[1] J. Jubin and J. Tornow, “The DARPA Packet Radio Network Protocols,” Proc. IEEE, vol. 75, no. 1, 1987, pp. 21–32.

[2] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Comp. Commun. Rev., Oct. 1994, pp. 234–44.

Article Source: http://www.content.onlypunjab.com

Worked as a Software Professional more than 2 years and have very good knowledge in Software System analysis, design, and development and Testing of Business applications. Worked on System Installation, configuration and trouble shooting of Windows 98/NT/2000 and UNIX environments. Educational Qualifications: B.E - Computer Science and Engineering - 61% - 2002 at J.J.College of Engg & Tech, Trichy M.E – Computer Science and Engineering – 71% -2004 at Raja College of Engg & Tech ,Madurai

Please Rate this Article

5 out of 54 out of 53 out of 52 out of 51 out of 5 

Not yet Rated