A Survey of Unipath Routing Protocols for Mobile Ad Hoc Networks

Published Online December 2013 in MECS DOI: 10.5815/ijitcs.2014.01.07

A MANET (Mobile Ad hoc NETwork) is an interconnection of mobile devices such as laptop, PDA, etc. by wireless links forming a dynamic topology without much physical network infrastructure. The main characteristics of MANET are i) Dynamic topologies ii) Bandwidth constrained links iii) Energy constrained operation and iv) Limited physical security [1, 5].

Unipath routing protocols are classified as: (i) proactive, (ii) reactive, and (iii) hybrid.

Fig 1: Classifications of unipath routing protocols for ad hoc networks

• 1.1.    Unipath Routing Protocols for Ad Hoc Networks

Even if several equally good paths are available, the unipath routing protocols use only one path at a time to a given destination. Most routing protocols are unipath or have a unipath mode of operation. A commonly used routing protocol called Open Shortest Path First (OSPF) operates in a unipath mode equal-cost multipath routing is enabled or turned on in the protocol [1]. Route discovery and route maintenance are the two steps followed by each protocol. Route discovery: Source node first finds a route or several routes to the destination, when it needs to send packets to a destination. This process is called route discovery. Route maintenance: The source transmits packets with the route. The route may be broken during the transmission of packets, because the node on the route move away or go down. The broken route will be reconstructed. The process of detecting route breakage and rebuilding the route is called route maintenance.

The rest of this paper is organized as follows: In Section 2, Working principles advantages and disadvantages of proactive routing protocols are discussed; in section 3, Working principles advantages and disadvantages of reactive routing protocols illustrated; in section 4, Working principles advantages and disadvantages of hybrid routing protocols are described; and finally in section 5 the conclusion is given.

• II.    Table–Driven (Proactive) Routing Protocols

• 2.1    Destination Sequenced Distance-Vector Routing Protocol

Table driven routing protocols are also called proactive routing protocols. Each and every node maintains the global topology information in the form of tables. The details of source, destination and intermediate nodes are consisted in these tables. To maintain consistent and accurate network state information these tables are updated frequently. In a table –driven routing protocol the routes to all destinations readily exist at every node at all times. Some of the examples of table driven routing protocols are DSDV, WRP. Each proactive routing protocol is used in different ways.

Working Principles

Distributed Bellman-Ford algorithm is used in Destination Sequenced Distance Vector (DSDV) Routing Protocol. The main contribution of the algorithm was to solve the Routing Loop problem. In DSDV each node maintains a table that has the shortest distance as well as the first node in the network. Routes to all destinations are readily available at every node at all times [1, 2, 3, 6]. Route discovery and route maintenance processes are used in this protocol. The next hop link of Host A for the required destination is active, and then it uses the conventional DSDV Protocol. The incoming packet is discarded in case if any outgoing link breaks, and there is no capacity in the buffer. Otherwise the packet is buffered. The Host A broadcasts one-hop Route Request packet to its neighbors. If A is not the Next –Hop, the neighbor sends Route Acknowledgement message with its Host ID, the destination, the hop count metric , the last updated time for the destination. The Host A chooses the best neighbor, based on the least number of hops to the destination. Host A selects the host with the latest routing update time when there is more than one node having the same number of hops. The packets are forwarded to the destination.

Advantages of DSDV

• 1.    Less delay is involved in the route setup process because of the availability of routes to all destinations at all times.

• 2.    The existing wired network protocols are adaptable to ad hoc wireless networks because they can be made

• 3.    To continue an up-to-date view of the network topology at all the nodes the updates are propagated throughout the network.

• 4.    Loop free paths are guarantee in this protocol [4].

• 5.    We can avoid traffic with incremental updates [4].

• 6.    DSDV maintains only the best path so the amount of space in routing table is reduced.

by the mechanism of incremental updates, by using sequence number tags.

Disadvantages

• 1.    Heavy control overhead because of the updates due to broken links.

• 2.    A node has to wait for a table update message to obtain information about a particular destination node.

• 3.    It is not suitable for highly dynamic networks.

• 4.    It is difficult to fix a time delay [4].

• 5.    A routing table should be maintained by each and every host in the network for advertising. It consumes more bandwidth [4].

• 6.    DSDV is inefficient due to the requirement of periodic update transmissions [5].

• 2.2 Wireless Routing ProtocolWorking Principles

Wireless Routing Protocol (WRP) differs from DSDV in table maintenance and in the update procedures. A set of tables are used in WRP to maintain more accurate information. A node maintains distance table (DT), routing table (RT), link cost table (LCT) and a message retransmission list (MRL) [1, 6, 7]. WRP is the vector distance algorithm [21]. A node sends update message when it detects a neighbor link state change or receives the update message from its neighbor. The recipient modifies its distance and seeks the best route at the time of message receiving. The MRL list is needed to be updated. Each mobile computer agrees to transmit data packets to its neighbor. An update message contains the destination, the distance to the destination, and the predecessor of the destination and a list of responses are sent only between neighboring nodes. The nodes learn of the existence of their neighbors from the receipt of acknowledgments and other messages.

Advantages of WRP

• 1.    It has faster convergence and involves fewer table updates.

• 2.    WRP sending hello message to disallow a node to enter sleep mode.

• 3.    It keeps away from the problem of creating temporary routing loops through the verification of predecessor information.

Disadvantages

• 1.    Large memory required to store the information of four tables when the nodes are linked in the network.

• 2.    The complexity of maintenance of multiple tables demands a larger memory and greater processing power from nodes in the ad hoc wireless network.

• 3.    It is not suitable for highly dynamic and also for very large ad hoc wireless networks.

• 4.    The hello packets consume bandwidth and do not allow a node to enter sleep mode.

• 2.3 Cluster- Head Gateway Switch RoutingProtocol

  Working principles

Cluster-Head Gateway Switch Routing (CGSR) Protocol uses a flat topology. CGSR classifies nodes into clusters. Cluster-head in each cluster is a special nodes coordinating the members of the clusters .A least cluster change (LCC) algorithm is used to elect cluster –head dynamically [1, 8]. This protocol achieves a distributed processing mechanism in the network by establishing several clusters. It modifies DSDV by using a hierarchical cluster-head-to-gateway routing methodology to route traffic from source to destination [6] .Gateway nodes are nodes that are within the communication ranges of two or more cluster heads. A node is first sending a packet to its cluster head, and it sent from the cluster head to a gateway to other cluster head, and till the process continues up to the cluster head of the destination node is reached. Lastly the packet is transmitted to the destination.

Advantages of CGSR

• 1.    Better bandwidth utilization is possible because CGSR uses a partial coordination between nodes by electing cluster –heads.

• 2.    Implementation of priority scheduling schemes with token scheduling and gateway code scheduling is easy.

Disadvantages

• 1.    Increases in path length and instability in the system at high mobility when the rate of change of cluster –heads is high.

• 2.    More resources are required to avoid conflicts of gateway.

• 3.    Multiple path breaks due to changes in the cluster head.

• 4.    A cluster head scheme affects routing protocol performance when nodes are busy to select the cluster head rather than transmits the packet.

• 2.4 Source-Tree Adaptive Routing Protocol (STAR)Working principles

Source-Tree Adaptive Routing Protocol (STAR) is suggested by Garcia-Luna_Aceves and Spohn. It uses the least overhead routing approach (LORA) as the key concept rather than the optimum routing approach (ORA). ORA were hired by earlier table-driven routing protocols. Every node in STAR protocol, broadcasts its source-tree information. A node chose a path to destination. Every node, builds a partial graph of the topology using its adjacent links as well as the sourcetree broadcast by its neighbors [1, 9].

Fig. 2: State Diagram of STAR Bridge Protocol

Fig. 3: (a) Good Replacement Location

Fig. 3: (b) Bad Replacement Location

MPRs (Multipoint relays) which are responsible for spreading control traffic to the whole network through transmission of TC (Topology Control) messages [13].

Fig. 5: An example of network topology illustrating the MPR selection process: nodes E and F are MPRs for node B

Advantages of STAR

• 1.    STAR has very low communication overhead.

• 2.    It reduces the average control overhead by using the approach of LORA.

• 3.    This protocol does not require backbones.

Disadvantages

• 1.    This protocol has high memory overhead [6].

• 2.    STAR has high processing overhead [6].

• 2.5 Optimized Link State RoutingWorking principles

Multipoint transmissions are achieved by using link state packet forwarding mechanism in Optimized Link State Routing (OLSR).This protocol optimizes the pure link state routing protocol. Optimizations are done through reducing the size of the control packets and reducing the number of links that are used for forwarding the link state packets [1, 10, 11]. OLSR protocol receives the stability of link state algorithm [12]. This protocol performs hop-by-hop routing. When a node moves, its packets can be sent effectively to it. This protocol significantly reduces the retransmissions in a flooding or broadcast procedure.

Packet Length (0-15)	Reserved for future use (16-31)
Msg Type 1 Reserved	Message Size
Message

Fig. 4: Packet format in OLSR

Advantages of OLSR

• 1.    OLSR reduces the routing overhead

• 2.    Connection setup time is less as well as control overhead is minimized.

• 3.    Each node broadcasts from time to time Hello messages which containing the list of neighbors known to the node and their link status.

• 4.    MPRs are used to reduce the number of control packets required for transmitting the data.

Disadvantages

• 1.    The information of two hop neighbor is essential for this protocol [6].

• 2.    The Hello messages are not sent but received by all one-hop neighbors.

• 2.6 Fisheye State Routing ProtocolWorking principles

The fisheye technique is used to represent graphical data along with routing overhead which reduce the information needed in the Fisheye State Routing (FSR) Protocol. This protocol maintains the topology at each node. It does not overflow the whole network with the information. Every node exchanges topology information only with its neighbors. Each update message does not contain information about all nodes, so it reduces the amount of traffic for transmitting the update messages. Each node can have accurate and exact information about its own neighboring nodes [1, 6].

Advantages of FSR

• 1.    FSR is suitable for large and highly mobile ad hoc wireless networks because it reduces the bandwidth consumed by link state update packets by using multilevel scopes.

• 2.    It reduces Control Overhead.

Disadvantages

• 1.    The number of hops linked with each scope level should be chosen carefully. Otherwise the performance of the protocol will be affected.

• 2.    High memory overhead.

• 3.    The avoidance of farthest nodes information will reduce the accuracy.

• 2.7 Hierarchical State Routing ProtocolWorking principles

A coherent clustering scheme has been proposed in Hierarchical State Routing (HSR) [1,  14].It is a distributed multi-level hierarchical routing protocol with efficient membership management at every level of clustering. HSR combines the technique of distributed multilevel hierarchical clustering. Each cluster head sum up its own cluster information and using gateways it passes to the neighboring cluster heads. Any node, after running the algorithm at any level, can flood the obtained information to its lower level nodes. To convey data successfully to any part of the network the hierarchical structure used in HSR is efficient enough [6].

Advantages of HSR

• 1.    The routing table size reduced by using the hierarchy information.

• 2.    The storage required in HSR is O(n * m) compared to O(n^m) that is required for a flat topology link state routing protocol (n is the average number of nodes in a cluster and m is the number of levels).

Disadvantages

• 1.    Multiple levels of hierarchy causes overhead in exchanging packets.

• 2.    The protocol is too expensive in the ad hoc wireless networks framework.

• III. On-Demand (Reactive) Routing Protocols

• 3.1    Ad hoc On-Demand Distance Vector Routing Protocol

The routes are established when needed by a source node to transmit the data to the destination. This process is called on-demand routing protocols. They do not need the topological information periodically.

Working principles

Ad hoc On-Demand Distance Vector (AODV) protocol uses a reactive methodology which finds a route when it is required by a source node for transmitting data packets to the destination. To identify the most recent path it uses the destination sequence numbers created by the destination [1, 15, 16].But DSR uses source routing to carry the complete path. AODV has no multiple routes and not support to asymmetric type of nodes. The routing structure of this protocol is flat. Route information is updated by a node if only the current received packet’s destination sequence number is greater than the destination sequence number stored at the node. AODV uses broadcast identifier number to prevent multiple broadcast of the same packet. The source broadcasts a Route Request (RREQ) packet to find a path to the destination. This packet contains the fields of the source identifier, the destination identifier, the source sequence number, the destination sequence number, the broadcast identifier and the time to live. The RREQ packet is received by the destination node or a node which has a fresh route to the destination. Then send RREP to the source node. Once the source node receives a RREP it can begin using the route to send data packets to the destination. The source node rebroadcasts the RREQ, if it does not receive a RREP before the timer expires. If one of the intermediate nodes moves then the neighbor node of moved node realizes the link failure and sends a link failure report to its upstream neighbors and so on till it reaches the source upon which the source can reinitiate route discovery if needed [15].

Advantages of AODV

• 1.    To find the latest route to the destination this protocol is used the destination sequence numbers [1, 17].

• 2.    Instead of the shortest route it favors the least congested route.

• 3.    AODV supports both unicast and multicast packet transmissions. [18].

• 4.    Since the source node is initiating path discovery request, the connection setup delay is less.

• 5.    When compared with DSDV it is highly scalable because of the minimum space complexity and broadcasts avoided.

• 6.    It uses dynamic topologies.

• 7.    AODV packets contain only the destination address. So it has low overhead.

• 8.    Because of reactive nature, this protocol can handle highly dynamic behavior of Vehicle Ad-hoc networks.

Disadvantages

• 1.    If the source sequence number is very old and the intermediate nodes have a higher but not the latest destination sequence number, intermediate nodes can lead to unreliable routes.

• 2.    Heavy control overhead because of multiple RouteReply packets in response to a single RouteRequest packet.

• 3.    Unnecessary bandwidth consumption because of the periodic beaconing.

• 4.    Adding of nodes cause large delay and scalability.

• 5.    This protocol supports to symmetric links only. When symmetric links are not available AODV cannot utilize asymmetric links.

• 3.2 Dynamic Source Routing ProtocolWorking Principles

Dynamic Source Routing (DSR) protocol is designed to check the bandwidth consumed by control packets in ad hoc wireless networks. It is beacon-less and doesn’t require periodic hello packet broadcasts, which are used by a node to tell its neighbors of its presence [1, 10, 19]. It allows nodes in the Mobile Ad hoc NETwork to dynamically discover a source route through multiple network hops to any destination. The nodes are required to maintain route caches. If any new route is known for a particular entry in the route cache then it is updated. This protocol also uses route discovery and route maintenance phases. If a node wants to send data to a destination it first consults its route cache to check there is any route to the destination or not. If an entry already exists, the source node uses that route to transmit the packet. Otherwise it initiates a route request broadcast with destination address, source address, and a unique identification number. Every intermediate node checks whether it knows about the destination address or not. If the intermediate node does not know about the destination address, it again forwards the packet and finally reaches the destination. When the destination or any intermediate node knows about the destination address a route reply is generated. Route cache updated with new routes.

Advantages of DSR

• 1.    When symmetric links are not supported, the node may initiate its own route discovery and route reply on the new route request.

• 2.    It eliminates the need to periodically flood the network with table update message because it is a reactive approach

• 3.    It reduces the control overhead the route cache information is utilized by the intermediate nodes.

• 4.    It saves bandwidth and reducing power consumption.

Disadvantages

• 1.    More storage needed because of packet must carry full routing information in DSR.

• 2.    Broken link doesn’t locally repair.

• 3.    The connection setup delay is higher than in table-driven protocols.

• 4.    The performance reduces on increasing the mobility.

• 5.    Source-routing mechanism is used in DSR leads to routing overhead

• 3.3 Associativity-Based RoutingWorking principles

The routes are selected based on the stability of the wireless links in Associativity-Based Routing (ABR). A connection is classified as stable or unstable based on its temporal stability which is determined by counting the periodic beacons that a node receives from its neighbors [1, 20]. ABR using the phases of Route discovery, Route reconstruction, and Route deletion. When a source node wants to send data to a destination, it sends the query. All other nodes in the network receiving the query add their addresses and their associativity ticks with their neighbors along with QoS information to the query packet. A downstream node erases its immediate upstream node’s associativity tick entries and preserves only the entry concerned with itself and its upstream node. This process continues and finally the packet reaches the destination. The destination chooses the best route and sends the REPLY packet using that path. The route with the minimum number of hops is selected when there are multiple paths with same overall degree. Route reconstruction process is needed when any path becomes invalid or broken for the mobility or failure of any intermediate node. If any discovered route is no longer needed then, route deletion broadcast is done in the network [21].

Advantages of ABR

• 1.    Higher preference for stable routes.

• 2.    ABR reduces the extent of flooding due to reconfiguration of paths in the network.

• 3.    It is guaranteed to be free of packet duplicates because the best route is selected.

Disadvantages

• 1.    Because of the preference given to stable paths the chosen path between the source and destination may be longer than the shortest path.

• 2.    High delays because of broadcasts LQ more times during route repairs.

• 3.    Route caches do not used in this protocol.

• 4.    Additional power consumption due to beaconing requirement.

• 3.4 Signal Stability-Based Adaptive RoutingProtocol

  Working Principles

Signal Stability-Based Adaptive (SSA) Routing Protocol uses signal stability for finding stable routes. The signal strength is used to classify a link as stable or unstable [1, 22]. SSA detects weak and strong channels in the network based on the signal strength. Dynamic

Routing Protocol (DRP) and the Static Routing Protocol (SRP) are the two cooperative protocols of SSA. Signal Stability Table (SST) and Routing Table (RT) are used in DRP. The signal strengths of the neighboring nodes are stored in SST. DRP passes this information to SRP. SRP transmits the packet to the destination. If there is no entry in the routing table for the destination node, it initiates the route-finding process. After getting the request, the destination node chooses the first arriving request packet and sends back the reply to other node. Route reply message sends back to the initiator by DRP where route is requested. If there is a link failure, an error message is sent to the source by the intermediate nodes. The source will initiate a new route to the destination.

Advantages of SSA

• 1.    Stable routes are found by this protocol.

• 2.    A link, stable or weak can be classified by using beacon counts.

Disadvantages

• 1.    Route Request failures occur due to strong RouteRequest forwarding.

• 2.    A new path process can be done for a failed RouteRequest without seeing the stability principle.

• 3.    Path setup time is increased and consumes bandwidth because of multiple flooding of RouteRequest packets.

• 4.    Shorter paths are ignored and the path length is increased because of strong links principle.

• 5.    Intermediate nodes cannot reply to route request. It leads to long delays.

• 3.5 Flow-Oriented Routing ProtocolWorking Principles

Time-sensitive traffic supported by multi-hophandoff mechanism in ad hoc wireless networks works in Flow-Oriented Routing Protocol (FORP). Quality of Service (QoS) needs, for IPv6-based ad hoc wireless networks. FORP is suggested for this purpose. To improve the effect of path breaks, multi-hop-handoff is used. After discovering the link break, the intermediate node initiates the process route maintenance [1, 23].

Advantages of FORP

• 1.    Reduction in path break and packet delivery by using LET (Link Expiration Time) and RET (Route Expiry Time) estimation.

• 2.    When the topology is highly dynamic, the mechanism of route reconfiguration works well.

Disadvantages

• 1.    The control overhead is increased because of time synchronization requirements.

• 2.    Non availability of GPS infrastructure this protocols operability will affect.

• 3.6 Preferred Link-Based Routing (PLBR) ProtocolWorking principles

The preferred link approach is used in SSA. The lack of topology information, link characteristics changing continuously, broadcast nature of the radio channel, and nodes mobility are the reason for not suitable to use the single preferred link model in ad hoc networks. Sisodia et al proposed two algorithms known as Preferred LinkBased Routing (PLBR) protocols. In this protocol a node selects a subset of nodes from the list of its neighbor node [1, 24].

Advantages of PLBR

• 1.    On-demand routing protocols have the problem of broadcast minimized in this protocol.

• 2.    Decrease in the number of collisions as well as improvement in the efficiency of the protocol leads to reduction in control overhead.

Disadvantages

• 1.    More complex for computation of NDPL (Neighbor Degree-based preferred Link algorithm) and WBPL (Weight-Based Preferred Link algorithm) than other forwarding schemes of RouteRequest.

• IV. Hybrid Routing Protocols

• 4.1    Core Extraction Distributed ad hoc RoutingProtocol

  Working Principles

The feature of a particular routing protocol of reactive and proactive routing protocol is inadequate. A mixture can produce better result. Some of the characteristics of proactive protocols as well as some of the characteristics of reactive protocols are included in the hybrid routing protocols.

Core Extraction Distributed ad hoc Routing (CEDAR) Protocol [1, 25] incorporates routing and support for QoS. Core nodes in the network are extracted in this protocol. At least one core node exists within three hops. A virtual link is the path between two core nodes. In the unicast mode Core broadcast mechanism is used to transmit data. CEDAR used slow-moving increase waves and fast-moving decrease wave to propagate link information. Increase wave carrying update message of increase in threshold. The reduction in available bandwidth of the neighbor nodes are noticed by fastmoving decrease waves. This protocol is carried out two phases. A core path is found between the sources to destination in the first phase, a QoS feasible path is found in the second phase. If the destination node is not in the local topology table of its core node, a node initiates a RouteRequest. RouteRequest is sent to all neighbor nodes. If the required bandwidth is available on the path, the connection is established; otherwise, the core path is rejected. CEDAR attempts to repair a broken route locally when a path break occurs.

Advantages of CEDAR

• 1.    CEDAR is very efficiently performs routing as well as QoS path computation.

• 2.    Increase waves are helped in appropriate propagation of the stable high-bandwidth link information and decrease waves are helped in appropriate propagation of the unstable low-bandwidth link information.

• 3.    A reliable mechanism for establishing paths with QoS support is provided by core broadcasts.

Disadvantages

• 1.    The movement of the core nodes will affect the performance of the protocol.

• 2.    Control overhead will occur because of the update information of the core node.

• 4.2 Zone Routing ProtocolWorking Principles

Zone Routing Protocol (ZRP) is a hybrid routing protocol. This protocol effectively combines the best features of both proactive as well as reactive routing protocols [1, 2, 6, 26, 27]. Proactive routing scheme is used within a limited zone and reactive routing scheme is used in beyond this zone. Intra-zone routing protocol (IARP) is used to proactive routing, inter-zone routing protocol (IERP) is used to reactive routing. Route creation is done in this protocol by using a query-reply mechanism. To create different zones, a node must know about its neighbors. A node identifies whether it is received from its neighbor node or not when forwarding of the query packet. If it is received from that node, then it marks all neighboring nodes which are in its same zone. The query is transmitted till it reaches the destination node. A reply message sends back by the destination node through the reverse path and creates the route. If there is a path break between intermediate nodes local path reconfiguration is performed and connects the alternate path. This update information sends to the source node.

Fig 7: The different components of ZRP

Advantages of ZRP

• 1.    ZRP reduces the control overhead by joining the best features of proactive and reactive routing schemes.

• 2.    Up-to-date topology of network is maintained by ZRP.

• 3.    Less time needed to send messages

• 4.    Everybody can use easily.

• 5.    The mechanism of ZRP can easily understand.

• 6.    Less band width is needed.

Disadvantages

• 1.    Higher control overhead will occur when nonappearance of a query control.

• 2.    Message hacking can be taken place.

• 3.    Any information can’t receive by the person who is not in the area of zone.

• 4.    This protocol works in Linux platform only.

• 5.    When new routes are found, short potential will be occur.

• 4.3 Zone-Based Hierarchical Link State routing Protocol

Working Principles

To form non-overlapping zones, the geographical location information of the nodes is used in Zone-Based Hierarchical Link State (ZHLS) [1, 6, 28]. Zone ID and a node ID is used in hierarchical addressing. Every node needs its location information. Inter-zone routing is achieved by maintaining high-level hierarchy. Shortest path algorithm is used to update the intra-zone routing table. If a node wants to transmit a packet to the destination, it verifies whether the destination node resides in its own zone or resides in other zone. If it is in the same zone, the packets are delivered as intra – zone routing table. Else, the source node originates a location request packet and forward to every zone. The gateway node verifies and replies to source node. Multiple gateway nodes between zones are making easy to maintain the route.

Advantages of ZHLS

• 1.    Storage requirement is less.

• 2.    Zone-level topology is robust.

• 3.    Network-wide control packet transmissions do not generated by the topology changes in intra-zonal.

Disadvantages

• 1.    Zone-level topology can be created additional overhead.

• 2.    The created path to the destination node is suboptimal.

• 3.    All environments do not have the geographical information for creating zone level topology.

• V. Conclusion

In this paper, we described the working principles, advantages and disadvantages of table-driven, on-demand and hybrid unipath routing protocols of

MANET. Among these unipath routing categories, on-demand routing category performs well even in different mobility models and traffic patterns.