Supervisor: Kaisa Sere
Classification of Ad Hoc Routing Protocols
Download 298.62 Kb.
|
- Navigate this page:
- 3.4 Ad hoc On-Demand Distance Vector (AODV)
- 3.4.1Route Discovery
- 3.4.2Path Maintenance
3.3 Classification of Ad Hoc Routing ProtocolsIn addition to proactive and reactive routing protocols there are several other more or less special types of protocols, some of which will not be considered further after this chapter. These include hierarchical, geographical and power aware type protocols as classified in [Ibáñez]. Hierarchical routing protocols divide the topology into zones or clusters, often with a cluster leader and different intra- and intercluster protocols. As an example of a hierarchical protocol we mention Zone Routing Protocol (ZRP), which partitions the network into zones and permits proactive routing inside a zone. When a route is needed to an outside node, a reactive route request message is broadcast. This limits the length that proactive updates travel (compare: autonomous systems and the backbone in the Internet). ZRP can also be called a hybrid protocol since it has both proactive and reactive features. When inter-zone route requests are sent, zones that have already been searched can stop the request message from entering it again, further reducing message complexity. Geographical protocols utilize location information that has to be acquired with Global Positioning Systems. In order for these protocols to become more common, GPS will still have to become more affordable. For example, a geographical protocol named, Distance Routing Effect Algorithm for Mobility (DREAM), maintains a complete list of node’s positions so that data packets can be flooded in the right direction. Location Aided Routing (LAR) is a reactive geographical protocol. This protocol also uses the information provided by GPS to send a limited route request to a so-called expected zone (Fig.3-1), which is formed as a circle area of where the destination is expected to be, based on the latest information about the location, direction and speed of the destination. There is also a limited request zone defined in LAR. The request reaches an area formed as a rectangle by a diagonal from the source to the expected zone. When the destination is to be found, a route discovery message is flooded only in the request zone and in the direction of the expected zone. 
Expected Zone Fig. 3 9: The zones of LAR. In power aware routing the protocol does not prioritize short routes anymore, but rather tries to select such routes that will optimize battery consumption in the network. If a route contains nodes with low battery levels, a longer route is chosen if available. In this attempt it is also important to minimize the amount of power that the transmission of a packet consumes. From a battery consumption point of view, it is not wanted that one node is responsible for forwarding packet between many source-destination pairs. Therefore, some sort of load balancing should be implemented. The Minimum Total Transmission Power Routing (MTPR) protocol for instance, prefers routes with more, shorter hops rather than those with fewer hops and longer transmission ranges. This is done because less power is required for shorter distances. Therefore, routes requiring least power are chosen. MTPR does not, however, take into account the remaining power levels of individual nodes, which is done in a protocol called Min-Max Battery Cost Routing (MMBCR). MMBCR considers the remaining battery level of every node and lets those with lower levels participate in forwarding more seldom. This is performed by MMBCR in the following way: Every route between a source and a destination has a node with the lowest battery power level (weakest node). Every weakest node is then compared and the route with the strongest weakest node is chosen. But as mentioned in [Kim+02], MMBCR does not guarantee that the total transmission power is minimal. MMBCR does, however, prolong the battery lifetime of the whole network. Conditional MMBCR (CMMBCR) considers both the total transmission power used by each route and the remaining power of nodes. CMMBCR first considers only routes where every node has a power level above a threshold and when the power level of every route between the source and destination is below the threshold, a route is chosen like MMBCR. This means that MMBCR first chooses routes that consume the least power from a set that still has a certain level of power left and then when these no longer exist, the route that contains the highest power capacity node of all minimum power level nodes is chosen (A summary of MTPR, MMBCR and CMMBCR can be found in [Kim+02]. 3.4 Ad hoc On-Demand Distance Vector (AODV)AODV [Perkins+99] is a reactive protocol that has evolved from Destination-Sequenced Distance-Vector Protocol (DSDV). DSDV is a proactive protocol (based on the Bellman-Ford algorithm) in which every node maintains routes to every other node all the time. The routing metric is hop counts and sequence numbers are used to discriminate older routes. AODV requires network wide broadcasts only when a route is acquired and the node has no previous knowledge of the topology. AODV also supports multicast and broadcast communication, which is extremely important when large pieces of data is to be transferred from one node to many nodes (i.e. multimedia such as motion pictures). AODV utilizes two routing tables, one for unicast routes and another for multicast routes. A route entry consists of destination, next-hop and distance (in hops, equals the amount of links between the source and destination). The route entries also have an age and a sequence number associated generated by the destination in order to prevent loops (no node is misinformed of old routes). The age is used to remove entries that have not been used for a while and therefore are likely to be ruined because of node movement. Each time an entry is used, the age is set to zero. When routes are used and found to be broken, these are maintained using a process described in section 3.1.2. 3.4.1Route DiscoveryWhen describing the route discovery process the node that initiates the process will be called the source and the node that the source tries to contact is the destination. When a source wants to send a message to a destination in a network running AODV and it does not have a route to the destination, the source has to initiate a “route discovery process”. The process is started by broadcasting a “route request” (RREQ) to its neighbors. The neighbors does the same, as do the neighbor’s neighbors and so on until the RREQ reaches the destination or a node with a “fresh enough” route to the destination that can send a “route reply” (RREP) to the source. The freshness is determined with sequence numbers that are coupled with every route and RREQ and route entry. The source node’s RREQ message contains the following fields:
The broadcast ID is incremented every time a node initiates a route discovery process and a timer is started when a RREQ is sent. Every intermediate node that receives the RREQ checks the broadcast ID and IP address combination (stored by every node) in order to see if the message has already been forwarded. From every unseen RREQ a reverse route entry is set up consisting of the sequence number, forwarding neighbor address (next hop back to the source) and the source of the RREQ is stored. Also, the intermediate node notes the number of hops to the source. On the other hand, if the message is identified as seen, it will be dropped. If a route is not used a specified amount of time it will be deleted from the routing table to prevent stale routes from being disseminated. When an intermediate node receives a RREQ and it has a fresh (the sequence number associated with the route in the intermediate node’s routing table is at least as great as the one found in the RREQ) route to the requested destination, the intermediate node can unicast a RREP back to the source. The role of the intermediate node can, of course, be handled by the destination if the message propagates that far. If the intermediate node’s route entry is not fresh enough it has to forward the RREQ to every neighbor and increment the message’s hop count. If the destination is not found (the source node’s timer expires), it can try again for a number of times before notifying the application of failure. Other than controlling the freshness property, the sequence numbers can also be used to prevent routing loops. The RREP contains the following fields:
As the RREP travels back to the source, every intermediate node updates pointers for the node from which the RREP came, the timer for the source and destination, and records the latest sequence number for the destination. If multiple RREQs are received by an intermediate node, copies that arrive after the first one are forwarded only if the hop count is smaller than previous copies. 3.4.2Path MaintenanceTo assert the symmetric condition of links between neighbors, hello messages can be used in case no other packets are sent to all active downstream neighbors during a specified interval. Hello messages have TTL value of 1 and are thus not allowed to be forwarded. The hello packet contains the sender’s id and its unincremented current sequence number. When a broken link is detected (i.e. failing to receive allowed_hello_loss consecutive hello messages) a specialized RREP message is sent to affected “active” neighbors by the node upstream of the break. The specialized RREP is unsolicited and contains a newer sequence number than that of the broken route, the hop count is set to . Every intermediate node’s routing table entry also contains a list of active neighbors. The active neighbors are neighbors of the intermediate node, but these send packets actively to the destination indicated by the entry. A neighbor is said to be active if it originates or forwards a packet for the destination during the last active_timeout period. When the active neighbors receive the RREP they also send a RREP to their active neighbors for that particular broken route and so on until the start nodes of every route are reached. 
Fig. 3 10: Link breakage between node 4 and 5. In figure 3-2, node 4 can check its routing table to see that node 2 has forwarded or originated a packet for node 5 in the last active_timeout period which causes an unsolicited RREP to be sent to node 2. Node 2 determines the same for node 3 and 1 and sends RREPs. After this every node that previously used node 4 as an intermediate node to the destination node 5, now knows that this path does not work anymore. If nodes 1, 2 or 3 still have packets to send to node 5 they must initiate a route discovery process. Because the RREPs are unicast back to the source, AODV has to be run in a network with symmetrical links [Toh02], in fact this condition is tested when a node is about to forward a message. The link over which a message should be forwarded is first checked to see if a hello message has been received over that link during the last allowed_hello_loss period. Asymmetric links can persist when two nodes are in the vicinity of each other, but only one of the node’s radio range reach the other node, due to nearly depleted batteries. In a most cases, the route discovery process will affect almost the whole AODV network and every node receives RREQ. Actually, the process can continue although the destination is found. To alleviate this problem, a so-called “expanding ring” search is implemented. This works by setting the “time to live” (TTL, decremented by each forwarder and the message is discarded when it reaches 0) value in the RREQ to something less than the network diameter (the longest path through the network). If no RREP is received by the source it will increase the TTL in the next RREQ. The TTL can be guessed quite accurately if the source has been in contact with the destination before, thus having the knowledge of the path length between them last time the route was functioning. It is questionable, however, whether this “remedy” is effective if educated guesses cannot be made. For instance, consider what happens when the TTL is estimated just a little too short. In that case the route discovery process is initiated again, meaning that message complexity for finding the destination is almost doubled. If the destination happen to be just outside the perimeter of the first message’s reach, it would have been more effective to let the message propagate further. In the case when there is a maximal length path between the source and destination and the destination does not have a clue where the destination is, there might be a multiple amount of message complexity if many RREQs are broadcast by the source. Download 298.62 Kb. Share with your friends:
|