Wireless Routing Protocol

The Wireless Routing Protocol (WRP) [Citation
last1 = Murthy | first1 = Shree
author1-link =
last2 = Garcia-Luna-Aceves | first2 = J. J.
author2-link =
title = An efficient routing protocol for wireless networks
journal = Mobile Networks and Applications
volume = 1
issue = 2
pages = 183 - 197
publisher = Kluwer Academic Publishers
location = Hingham, MA
date = 1996-10-01
year = 1996
url = http://portal.acm.org/citation.cfm?id=272250
issn = 1383-469X ] is a proactive unicast routing protocol for mobile ad-hoc networks (MANETs). WRP uses an enhanced version of the distance-vector routing protocol, which uses the Bellman-Ford algorithm to calculate paths. Because of the mobile nature of the nodes within the MANET, the protocol introduces mechanisms which reduce route loops and ensure reliable message exchange.

The wireless routing protocol (WRP), similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. To counter the count-to-infinity problem and to enable faster convergence, it employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node. Since WRP, like DSDV, maintains an up-to-date view of the network, every node has a readily available route to every destination node in the network. It differs from DSDV in table maintenance and in the update procedures. While DSDV maintains only one topology table, WRP uses a set of tables to maintain more accurate information. The tables that are maintained by a node are the following: distance table (DT), routing table (RT), link cost table (LCT), and a message retransmission list (MRL).

The DT contains the network view of the neighbors of a node. It contains a matrix where each element contains the distance and the penultimate node reported by a neighbor for a particular destination. The RT contains the up-to-date view of the network for all known destinations. It keeps the shortest distance, the predecessor node (penultimate node), the successor node (the next node to reach the destination), and a flag indicating the status of the path. The path status may be a simple path (correct), or a loop (error), or the destination node not marked (null). The LCT contains the cost (e.g., the number of hops to reach the destination) of relaying messages through each link. The cost of a broken link is infinity. It also contains the number of update periods (intervals between two successive periodic updates) passed since the last successful update was received from that link. This is done to detect links breaks. The MRL contains an entry for every update message that is to be retransmitted and maintains a counter for each entry. This counter is decremented after every retransmission of an update message. Each update message contains a list of updates. A node also marks each node in the RT that has to acknowledge the update message it transmitted. Once the counter reaches zero, the entries in the update message for which no acknowledgments have been received are to be retransmitted and the update message is deleted. Thus, a node detects a link break by the number of update periods missed since the last successful transmission. After receiving an update message, a node not only updates the distance for transmission neighbors but also checks the other neighbors’ distance, hence convergence is much faster than DSDV.

Method

Each node implementing WRP keeps a table of routes and distances and link costs. It also maintains a 'message retransmission list' (MRL).

Routing table entries contain distance to a destination node, the previous and next nodes along the route, and is tagged to identify the route's state: whether it is a simple path, loop or invalid route. (Storing the previous and successive nodes assists in detecting loops and avoiding the counting-to-infinity problem - a shortcoming of Distance Vector Routing.)

The link cost table maintains the cost of the link to its nearest neighbors (nodes within direct transmission range), and the number of timeouts since successfully receiving a message from the neighbor.

Nodes periodically exchange routing tables with their neighbors via update messages, or whenever the link state table changes. The MRL maintains a list of which neighbors are yet to acknowledged an update message, so they can be retransmitted if necessary. Where no change in the routing table, a node is required to transmit a 'hello' message to affirm its connectivity.

When an update message is received, a node updates its distance table and reassesses the best route paths. It also carries out a consistency check with its neighbors, to help eliminate loops and speed up convergence.

Shortcomings

WRP has the same advantage as that of DSDV. In addition, it has faster convergence and involves fewer table updates. But the complexity of maintenance of multiple tables demands a larger memory and greater processing power from nodes in the ad hoc wireless network. At high mobility, the control overhead involved in updating table entries is almost the same as that of DSDV and hence is not suitable for highly dynamic and also for a very large ad hoc wireless network.

WRP requires large memory storage and resources in maintaining its tables. The protocol is not suitable for large mobile ad hoc networks as it suffers from limited scalability.

References