Design and Implementation of Fisheye Routing Protocol for Mobile Ad Hoc Networks by

1.5Summary

Conventional routing protocols for wired networks are ill-suited for ad-hoc wireless networks. Table-driven routing such as distance vector and link state have high overhead traffic caused by periodic exchange of control messages. On-Demand Routing suffers high initial latency hits and adds size to each packet to contain the source route. It does not scale well with traffic source/destination pair density and mobility. Clearly, new mechanisms must be introduced for effective ad hoc wireless routing.

2. Ad Hoc Routing Protocols

Since the advent of the Defense Advanced Research Projects Agency(DARPA) packet radio networks in the early 1970s [JT87], numerous protocols have been developed for ad hoc mobile networks. These routing protocols must deal with the typical limitations of these networks, which include low bandwidth and high error rates.

The following is a list of desirable properties for an ad hoc wireless routing protocol:

• 
  Distributed operation: The protocol should be distributed, meaning that it should not be dependent on a centralized controlling node. This makes the system more robust to failure and growth.
  

• 
  Fast convergence: Routes should be quickly determined in the presence of network changes. This means that when topology changes occur, the protocol should be able to quickly determine optimal new routes.
  

• 
  Loop free: To have good overall performance, the routing protocol should supply routes that are loop-free. This avoids wasting bandwidth and CPU resources.
  
• 
  Optimal routes: It is important for the protocol to find routes with the least number of hops. This reduces bandwidth and CPU consumption. In addition, it leads to lower overall routing delay.
  
• 
  Low overhead control traffic: Bandwidth in a wireless network is a limited resource. The protocol should minimize the amount of overhead control messages for routing.
  

• 
  Dynamic Destination-Sequenced Distance Vector (DSDV)
  
• 
  Wireless Routing Protocol (WRP)
  
• 
  Clusterhead Gateway Switch Routing (CGSR)
  
• 
  Zone-based Hierarchical Link State (ZHLS)
  
• 
  Ad Hoc On Demand Distance Vector (AODV)
  
• 
  Temporally-Ordered Routing Algorithm(TORA)
  
• 
  Dynamic Source Routing (DSR)
  
• 
  Associativity-Based Routing (ABR)
  
• 
  Signal Stability Routing (SSR)
  

1.6Destination Sequenced Distance Vector – DSDV

1.6.1Description

DSDV[Per94] is a hop-by-hop distance vector routing protocol where each node has a routing table that stores next-hop and number of hops for all reachable destinations. Like distance-vector, DSDV requires that each node periodically broadcast routing updates. The advantage with DSDV over traditional distance vector protocols is that DSDV guarantees loop-free routes.

To guarantee loop-free routes, DSDV uses a sequence number to tag each route. The sequence number shows the freshness of a route and routes with higher sequence numbers are favorable. A route R is considered more favorable than S if R has a greater sequence number, or, if the routes have the same sequence number, but R has a lower hop count. The sequence number is increased when node A detects that a route destination D has broken. So the next time node A advertises its routes, it will advertise the route to D with an infinite hop-count and a sequence number that is larger than before.

DSDV basically is distance vector with small adjustments to make it better suited for ad-hoc networks. These adjustments consist of triggered updates that will take care of topology changes in the time between broadcasts. To reduce the amount of information in these packets, there are two types of update messages defined: full and incremental. The full broadcast carries all available routing information and the incremental broadcast only carries the information that has changed since the last broadcast.

1.6.2Properties

Because DSDV is dependent on periodic broadcasts, it needs some time to converge before a route can be used. This convergence time can probably be considered negligible in a static wired network, where topology changes are infrequent. However, in an ad-hoc network, the topology is expected to be very dynamic, thus causing a slow convergence of routes as packets are dropped and nodes move about. Periodic and triggered broadcasts also add a large amount of overhead into the network, especially when there is high mobility in the network.

1.7The Wireless Routing Protocol- WRP

1.7.1Description

The Wireless Routing Protocol (WRP) [MG96] is a table-based 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 y 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 is beneficial in detecting loops and avoiding counting-to-infinity problems. The Link-Cost table contains cost of 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 neighbor has not acknowledged its update message and to retransmit update message to that neighbor.

Node exchange routing tables with their neighbors using update messages periodically as well as on link changes. The nodes present on the response list of update message (formed using MRL) are required to acknowledge the receipt of update message. If there is no change in 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 new information. Any new path so found is relayed back to the original nodes so that they can update their tables. The node also updates its routing table if the new path is better than the existing path. On receiving an ACK, the mode updates its MRL. A unique feature of this algorithm is that it checks the consistency of all its neighbors every time it detects a change in link of any of its neighbors.

1.7.2Properties

Part of the novelty of WRP stems from the way in which it achieves loop freedom. In WRP, routing nodes communicate the distance and second-to-last hop information for each destination in the wireless networks. It avoids the “count-to-infinity” problem by forcing each node to perform consistency checks of predecessor information reported by all its neighbors. This eliminates looping situations and provides faster route convergence when a link failure event occurs. However, to achieve this loop freedom, WRP suffers from high overhead control traffic caused by the periodic and triggered exchange of routing tables and the reliance on ACK and HELLO responses (caused by spurious retransmission of route tables if ACKs or HELLOs are lost).

Directory: profit -> htdocs -> thesis
thesis -> Contemporary Bank Check Alternatives
profit -> Extra Titles
profit -> P. O. Box 210108 Tucson, az 85721-0108
profit -> Three Trends Dealerships Must Not Ignore in 2016

Download 268.85 Kb.

Share with your friends: