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 nodes 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. TORAs 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. TORAs 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 its a very effective routing algorithm for a large type of MANET. Here using position identifies the nodes. Here the node IDs 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{<v1ut,.<vnut), together with the destination node t.
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. 2132.
[2] C. E. Perkins and P. Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, Comp. Commun. Rev., Oct. 1994, pp. 23444.
Author: Balamurugan Balusamy
Article Source: EzineArticles.com
Provided by: Smart cooker
- Stop horse slaughter forever
- The Wanita Filgate Care Group / The Rachel Thomas Fund
- Route Marshal Volunteers Needed for the City of Sydney Spring Cycle 27/09/09
Related Posts -
Lawful Intercept in VoIP Network IntroductionLawful Intercept (LI) is a requirement placed upon service providers to provide legally sanctioned official access to private communications. In the existing Public Telephone Network, Lawful Intercept is performed by applying a physical 'tap' on the telephone line of the target in response to a warrant from a Law...... - IP Telephony - Now Make Calls Without Hassles It would not be a hyperbole to state that the IP-based telephony services have raised communication processes to their subsequent logical level. By looking at the altering behaviors of business and home consumers and their want for instantaneous access to information, it would not be wrong to say that......
- All About Wireless Routers It is an incomplete computer network without a router. So, what all it does within a network. A router actually transfers data packets along networks. It requires at least two networks for a router to connect, commonly it connects two LANs or WANs or a LAN and its ISP......
- Discussing the Advantages of VoIP VoIP services have taken the business world by storm, by giving them features which not only help them in cutting down their total call cost but also assists in increasing their overall productivity. The advantages of VoIP telephony are numerous, making it flexible enough to be adapted by all......
-
Zultys Announces MXmobile Unified Communications Client for Mobile Phones Sep 01, 2009 10:14 ET Zultys Announces MXmobile Unified Communications Client for Mobile Phones Extends Presence, Directory Access and PBX Functions to RIM and iPhone Devices Highlighted Links Zultys home page Business VoIP solutions LOS ANGELES, CA--(Marketwire - September 1, 2009) - ITEXPO -- Zultys Inc., an award-winning......
Related Websites - Microsoft announces partners for app store Microsoft Corp has signed up multiple software partners for its upcoming cellphone software marketplace, including Web music service Pandora, game publisher Electronic Arts Inc and social site Facebook. The software company said on Tuesday it plans to discuss those partnerships and conduct demonstrations of the software store -- set to......
-
AT&T halts online iPhone sales to New York City residents [/caption] Apple's exclusive U.S. iPhone wireless provider AT&T began halting online sales of the touch-screen device to residents of New York City and its surrounding areas this past weekend but has been unable to provide a reasonable explanation as to why. The matter was first brought to light by the...... -
How to Identify Antique Items You already know that an antique is something that is no less than 100 years old, but how exactly can you be certain that the particular piece you are looking at was truly crafted that long ago? Learning to identify antiques is not difficult, it just takes a little bit...... - Rocketinfo: Faster Than Google, Deeper Than Yahoo, More Specific Than a Speeding Bullet All of us are hip, on-line and Internet-savvy. But we don’t know the beast.
This is the core message of Bill Ganz, the president and CEO of next-step search engine ROCKETInfo Inc. (OTC:RKTI). It is a search technology company in the spirit of Google and Yahoo!, but with a new......
-
NBC facing long road back after Conan drama [/caption] LOS ANGELES, Jan 22 (Reuters) - NBC may have put a public relations nightmare behind it with the departure of "Tonight Show" host Conan O'Brien, but the network faces a long, costly road to revive its sagging fortunes, media analysts said. NBC's $45 million exit deal for O'Brien was......
Related posts:
