A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks:
Table-Driven Routing Protocols
Table-driven routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. These protocols require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network in order to maintain a consistent network view. The areas in which they differ are the number of necessary routing-related tables and the methods
by which changes in network structure are broadcast. The following sections discuss some of the existing table-driven ad hoc routing protocols.
Destination-Sequenced Distance-Vector Routing — The Destination-Sequenced Distance-Vector Routing protocol (DSDV) described in [2] is a table-driven algorithm based on the classical Bellman-Ford routing mechanism [3]. The improvements made to the Bellman-Ford algorithm include freedom from loops in routing tables. Every mobile node in the network maintains a routing
table in which all of the possible destinations within the network and the number of hops to each destination are recorded. Each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, thereby avoiding the formation of routing loops. Routing table updates are periodically transmitted throughout the network in order to maintain table consistency. To help alleviate the potentially
large amount of network traffic that such updates can generate, route updates can employ two possible types of packets. The first is known as a full dump. This type of packet carries all available routing information and can require multiple network protocol data units (NPDUs). During periods of
occasional movement, these packets are transmitted infrequently.
Smaller incremental packets are used to relay only that information which has changed since the last full dump. Each of these broadcasts should fit into a standard-size NPDU, thereby decreasing the amount of traffic generated. The mobile nodes maintain an additional table where they store the data sent in the incremental routing information packets.
New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination,
as well as a new sequence number unique to the broadcast [2]. The route labeled with the most recent
sequence number is always used. In the event that two updates have the same sequence number, the route with the smaller metric is used in order to optimize (shorten) the path.
Mobiles also keep track of the settling time of routes, or the weighted average time that routes to a destination will fluctuate before the route with the best metric is received (see [2]). By delaying the broadcast of a routing update by the length of the settling time, mobiles can reduce network traffic
and optimize routes by eliminating those broadcasts that would occur if a better route was discovered in the very near future.
Clusterhead Gateway Switch Routing — The Clusterhead 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 multihop mobile wireless network with
several heuristic routing schemes [4]. The authors state that by having a cluster head controlling a group of ad hoc nodes, a framework for code separation (among clusters), 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. The disadvantage of having a cluster head scheme is that frequent cluster head changes can adversely affect routing protocol performance since nodes are busy in cluster head selection rather than packet 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 node moves out of contact of all other cluster heads.
CGSR uses DSDV as the underlying routing scheme, and hence has much of the same overhead as DSDV. However, it modifies DSDV by using a hierarchical cluster-head-to-gateway routing approach to route traffic from source to destination. Gateway nodes are nodes that are within communication
range of two or more cluster heads. A packet sent by a node is first routed to its cluster head, and then the packet is routed from the cluster head to a gateway to another cluster head, and so on until the cluster head of the destination node is reached. The packet is then transmitted to the destination.
Figure 2 illustrates an example of this routing scheme. Using this method, each node must keep a “cluster member table” where it stores the destination cluster head for each mobile node in the network. These cluster member tables are broadcast by each node periodically using the DSDV algorithm. Nodes update their cluster member tables on reception of such a table from a neighbor.
In addition to the cluster member table, each node must also maintain a routing table which is used to determine the next hop in order to reach the destination. On receiving a packet, a node will consult its cluster member table and routing table to determine the nearest cluster head along the route to the destination. Next, the node will check its routing table to determine the next hop used to reach the selected cluster head. It then transmits the packet to this node.
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 caches that contain the source routes of which the mobile is aware. Entries in the route cache are continually updated as new routes are learned. 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. If it has an unexpired route to the destination, it will use this route to send the packet. On the other hand, if the node does not have such a route, it initiates route discovery by broadcasting a route request packet. This route request contains the address of the destination, along with the source node’s address and a unique identification number. Each node receiving the packet checks whether it knows of a route to the destination. If it does not, it adds its own address to the route record of the packet and then forwards the packet along its outgoing links. To limit the number of route requests propagated on the outgoing links of a node, a mobile only forwards the route request if the request has not yet been seen by the mobile and if the mobile’s address does not already appear in the
route record.
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 unexpired route to the destination [9]. By the time the packet reaches either the destination or such an intermediate node, it contains a route record
yielding the sequence of hops taken. Figure 4a illustrates the formation of the route record as the route request propagates through the network. 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. To return the route reply, the responding node must have a route to the initiator. If it has a route to the initiator in its route cache, it may use that route. Otherwise, if symmetric links are supported,
the node may reverse the route in the route record. If symmetric links are not supported, the node may initiate its own route discovery and piggyback the route reply on the new route request. Figure 4b shows the transmission of the route reply with its associated route record back to the source node.
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. This feature, although useful for datagram traffic, incurs substantial signaling traffic and power consumption. Since both bandwidth and battery power are
scarce resources in mobile computers, this becomes a serious limitation.
Table 3 lists some of the basic differences between the two classes of algorithms. 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. Applications and Challenges Akin to packet radio networks, ad hoc wireless networks have an important role to play in military applications. Soldiers equipped with multimode mobile communicators can now communicate in an ad hoc manner without the need for fixed wireless base stations. In addition, small vehicular devices equipped with audio sensors and cameras can be deployed at targeted regions to collect important location and environmental information which will be communicated back to a processing node via ad hoc mobile communications. Ship-to ship ad hoc mobile communication is also desirable since it provides
alternate communication paths without reliance on ground or space-based communication infrastructures. Commercial scenarios for ad hoc wireless networks include:
• Conferences/meetings/lectures
• Emergency services
• Law enforcement
People today attend meetings and conferences with their laptops, palmtops, and notebooks. It is therefore attractive to have instant network formation, in addition to file and information sharing without the presence of fixed base stations and systems administrators. A presenter can multicast slides and audio to intended recipients. Attendees can ask questions and interact on a commonly shared whiteboard. Ad hoc mobile communication is particularly useful in relaying information (status, situation awareness, etc.) via data, video, and/or voice from one rescue team member to another over a small handheld or wearable wireless device.
Again, this applies to law enforcement personnel as well.
Current challenges for ad hoc wireless networks include:
•Multicast [21]
•QoS support
•Power-aware routing [22]
•Location-aided routing [23]
As mentioned above, multicast is desirable to support multiparty wireless communications.
Since the multicast tree is no longer static (i.e., its topology is subject to change over time), the multicast routing protocol must be able to cope with mobility, including multicast membership
dynamics (e.g., leave and join). In terms of QoS, it is inadequate to consider QoS merely at the network level without considering the underlying media access control layer [24]. Again, given the problems associated with the dynamics of nodes, hidden terminals, and fluctuating link characteristics, supporting end-to-end QoS is a nontrivial issue that requires in-depth investigation. Currently, there is a trend toward an adaptive QoS approach instead of the “plain” resource reservation method with hard QoS guarantees. Another important factor is the limited power supply in handheld devices, which can seriously prohibit packet forwarding in an ad hoc mobile environment. Hence, routing traffic based on nodes’ power metrics is one way to distinguish
routes that are more long-lived than others. Finally, instead of using beaconing or broadcast search, location aided routing uses positioning information to define associated regions so that the routing is spatially oriented and limited.
This is analogous to associativity-oriented and restricted broadcast in ABR.
DOWNLOAD LINK:
CLICK ME
Table-Driven Routing Protocols
Table-driven routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. These protocols require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network in order to maintain a consistent network view. The areas in which they differ are the number of necessary routing-related tables and the methods
by which changes in network structure are broadcast. The following sections discuss some of the existing table-driven ad hoc routing protocols.
Destination-Sequenced Distance-Vector Routing — The Destination-Sequenced Distance-Vector Routing protocol (DSDV) described in [2] is a table-driven algorithm based on the classical Bellman-Ford routing mechanism [3]. The improvements made to the Bellman-Ford algorithm include freedom from loops in routing tables. Every mobile node in the network maintains a routing
table in which all of the possible destinations within the network and the number of hops to each destination are recorded. Each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, thereby avoiding the formation of routing loops. Routing table updates are periodically transmitted throughout the network in order to maintain table consistency. To help alleviate the potentially
large amount of network traffic that such updates can generate, route updates can employ two possible types of packets. The first is known as a full dump. This type of packet carries all available routing information and can require multiple network protocol data units (NPDUs). During periods of
occasional movement, these packets are transmitted infrequently.
Smaller incremental packets are used to relay only that information which has changed since the last full dump. Each of these broadcasts should fit into a standard-size NPDU, thereby decreasing the amount of traffic generated. The mobile nodes maintain an additional table where they store the data sent in the incremental routing information packets.
New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination,
as well as a new sequence number unique to the broadcast [2]. The route labeled with the most recent
sequence number is always used. In the event that two updates have the same sequence number, the route with the smaller metric is used in order to optimize (shorten) the path.
Mobiles also keep track of the settling time of routes, or the weighted average time that routes to a destination will fluctuate before the route with the best metric is received (see [2]). By delaying the broadcast of a routing update by the length of the settling time, mobiles can reduce network traffic
and optimize routes by eliminating those broadcasts that would occur if a better route was discovered in the very near future.
Clusterhead Gateway Switch Routing — The Clusterhead 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 multihop mobile wireless network with
several heuristic routing schemes [4]. The authors state that by having a cluster head controlling a group of ad hoc nodes, a framework for code separation (among clusters), 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. The disadvantage of having a cluster head scheme is that frequent cluster head changes can adversely affect routing protocol performance since nodes are busy in cluster head selection rather than packet 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 node moves out of contact of all other cluster heads.
CGSR uses DSDV as the underlying routing scheme, and hence has much of the same overhead as DSDV. However, it modifies DSDV by using a hierarchical cluster-head-to-gateway routing approach to route traffic from source to destination. Gateway nodes are nodes that are within communication
range of two or more cluster heads. A packet sent by a node is first routed to its cluster head, and then the packet is routed from the cluster head to a gateway to another cluster head, and so on until the cluster head of the destination node is reached. The packet is then transmitted to the destination.
Figure 2 illustrates an example of this routing scheme. Using this method, each node must keep a “cluster member table” where it stores the destination cluster head for each mobile node in the network. These cluster member tables are broadcast by each node periodically using the DSDV algorithm. Nodes update their cluster member tables on reception of such a table from a neighbor.
In addition to the cluster member table, each node must also maintain a routing table which is used to determine the next hop in order to reach the destination. On receiving a packet, a node will consult its cluster member table and routing table to determine the nearest cluster head along the route to the destination. Next, the node will check its routing table to determine the next hop used to reach the selected cluster head. It then transmits the packet to this node.
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 caches that contain the source routes of which the mobile is aware. Entries in the route cache are continually updated as new routes are learned. 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. If it has an unexpired route to the destination, it will use this route to send the packet. On the other hand, if the node does not have such a route, it initiates route discovery by broadcasting a route request packet. This route request contains the address of the destination, along with the source node’s address and a unique identification number. Each node receiving the packet checks whether it knows of a route to the destination. If it does not, it adds its own address to the route record of the packet and then forwards the packet along its outgoing links. To limit the number of route requests propagated on the outgoing links of a node, a mobile only forwards the route request if the request has not yet been seen by the mobile and if the mobile’s address does not already appear in the
route record.
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 unexpired route to the destination [9]. By the time the packet reaches either the destination or such an intermediate node, it contains a route record
yielding the sequence of hops taken. Figure 4a illustrates the formation of the route record as the route request propagates through the network. 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. To return the route reply, the responding node must have a route to the initiator. If it has a route to the initiator in its route cache, it may use that route. Otherwise, if symmetric links are supported,
the node may reverse the route in the route record. If symmetric links are not supported, the node may initiate its own route discovery and piggyback the route reply on the new route request. Figure 4b shows the transmission of the route reply with its associated route record back to the source node.
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. This feature, although useful for datagram traffic, incurs substantial signaling traffic and power consumption. Since both bandwidth and battery power are
scarce resources in mobile computers, this becomes a serious limitation.
Table 3 lists some of the basic differences between the two classes of algorithms. 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. Applications and Challenges Akin to packet radio networks, ad hoc wireless networks have an important role to play in military applications. Soldiers equipped with multimode mobile communicators can now communicate in an ad hoc manner without the need for fixed wireless base stations. In addition, small vehicular devices equipped with audio sensors and cameras can be deployed at targeted regions to collect important location and environmental information which will be communicated back to a processing node via ad hoc mobile communications. Ship-to ship ad hoc mobile communication is also desirable since it provides
alternate communication paths without reliance on ground or space-based communication infrastructures. Commercial scenarios for ad hoc wireless networks include:
• Conferences/meetings/lectures
• Emergency services
• Law enforcement
People today attend meetings and conferences with their laptops, palmtops, and notebooks. It is therefore attractive to have instant network formation, in addition to file and information sharing without the presence of fixed base stations and systems administrators. A presenter can multicast slides and audio to intended recipients. Attendees can ask questions and interact on a commonly shared whiteboard. Ad hoc mobile communication is particularly useful in relaying information (status, situation awareness, etc.) via data, video, and/or voice from one rescue team member to another over a small handheld or wearable wireless device.
Again, this applies to law enforcement personnel as well.
Current challenges for ad hoc wireless networks include:
•Multicast [21]
•QoS support
•Power-aware routing [22]
•Location-aided routing [23]
As mentioned above, multicast is desirable to support multiparty wireless communications.
Since the multicast tree is no longer static (i.e., its topology is subject to change over time), the multicast routing protocol must be able to cope with mobility, including multicast membership
dynamics (e.g., leave and join). In terms of QoS, it is inadequate to consider QoS merely at the network level without considering the underlying media access control layer [24]. Again, given the problems associated with the dynamics of nodes, hidden terminals, and fluctuating link characteristics, supporting end-to-end QoS is a nontrivial issue that requires in-depth investigation. Currently, there is a trend toward an adaptive QoS approach instead of the “plain” resource reservation method with hard QoS guarantees. Another important factor is the limited power supply in handheld devices, which can seriously prohibit packet forwarding in an ad hoc mobile environment. Hence, routing traffic based on nodes’ power metrics is one way to distinguish
routes that are more long-lived than others. Finally, instead of using beaconing or broadcast search, location aided routing uses positioning information to define associated regions so that the routing is spatially oriented and limited.
This is analogous to associativity-oriented and restricted broadcast in ABR.
DOWNLOAD LINK:
CLICK ME
No comments:
Post a Comment