Existing Routing Schemes In Vanets Computer Science Essay

Published:

Chapter 2

Chapter 2

Review of the Existing Routing Schemes in VANETs

2.1 Introduction

Routing of data in VANETs is a challenging task due to highly dynamic topology of the network. This causes routing complexity in these networks. This Chapter gives a survey of existing routing schemes in vehicular networks.

2.2 GSR (Geographic Source Routing)

Initially, GSR [10] was developed to be used in MANET. Later on some improvements were made to use it in VANET scenario. It was modified by incorporating greedy forwarding of messages toward the destination in it. GSR utilizes a recovery strategy if there are no nodes in the direction of destination at any hop. This strategy is known as perimeter mode. This mode has two components. One is known as distributed polarization algorithm. This makes local conversion of connectivity graph into planar graph by removing redundant edges. Second component is known as online routing algorithm. This component operates on planer graphs.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

In VANETs perimeter mode of GSR is used. It starts sending the message to intermediate neighbor rather than to farthest node. This method introduces long delays due to greater number of hop counts. Rapid movement of vehicles introduces routing loops which causes dissemination of messages to long path. It uses static street map and location information about each node. It does not consider vehicle density. So it is not an efficient method.

Drawbacks

Long delays due to greater number of hops.

Tries to establish end-to-end connections which are difficult at low traffic density. Further, end-to-end connection scheme doesn't work in a highly dynamic environment.

2.3 GPCR (Greedy Perimeter Coordinator Routing)

Lochert et al. designed GPCR [11] in an attempt to deal with the challenges of city scenarios. This protocol makes use of a restricted greedy forwarding procedure along a preselected path. When next hop is chosen, a coordinator (the node on a junction) is preferred to a non coordinator node. The preferred coordinator may not the geographically closest node to the destination.

Drawbacks

cannot work without static street maps

Establishes end-to-end connections which are difficult when traffic density is low.

2.4 A-STAR (Anchor-based Street and Traffic Aware Routing)

This protocol was proposed by Seet et al. The proposed A-STAR [12] was an attempt to guarantee end-to-end connection in a vehicular network when traffic density is low.

In A-STAR [12], the number of junctions to reach the destination is computed. This protocol also uses traffic information and street awareness in path finding. It uses street awareness to get the anchor information according to the street map. This makes use of dynamically and statically rated maps to find the number of junctions. In statistically rated maps, A-STAR uses schedule of buses to ensure high connectivity. For example, some streets are served by regular city buses and their connectivity can be high due to presence of buses. In dynamically rated maps, the protocol collects the latest traffic information in order to find the anchors/junctions to compute the path. Some roads are wider than other and have more traffic. That is why connectivity is high on wider roads with high traffic (more vehicles). Using such type of traffic information, A-Star assigns the weight to the street. This is a dynamic process that helps this protocol to calculate anchors more accurately.

Drawbacks

Establishes and uses routing paths. This approach for packet forwarding cannot work in a frequently changing network topology. Further, the routing paths established are not optimal and result in delay of packet transmission.

2.5 MDDV (Mobility-Centric Data Dissemination Algorithm for Vehicular Networks)

This protocol was proposed by Wu et al. MDDV [13] tries to achieve reliable and efficient routing. It combines opportunistic forwarding, trajectory-based forwarding and geographical forwarding. This protocol takes into account the traffic density. It specifies a forwarding trajectory that extends from the source to the destination (trajectory-based forwarding). A message will move along this trajectory and will get geographically closer to the destination (geographical forwarding). The forwarding trajectory is selected based upon the geographical knowledge and traffic density. In MDDV it is assumed that traffic density is static. Forwarding trajectory is used to forward the messages through intermediate nodes which are used to store and forward messages.

Drawbacks

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Main drawback of this approach is that it uses trajectory-based forwarding which fails when mobility of vehicles is very high.

2.6 VADD (Vehicle-Assisted Data Delivery)

This protocol [14] was proposed by Zhao and Cao .The aim of this protocol was to guarantee an end-to-end connection in a sparse network with low delay. This protocol is based upon the idea of carry and forward by using predicable mobility specific to sparse network. The protocol does not use any pre-defined path for routing. It chooses next hop based on the some pre-defined direction priority by selecting the closest one to destination. This protocol does not predict the environment change in the future.

Drawbacks

Enough time required for connection setup & route establishment.

Intermediate nodes can lead to inconsistency in the route if they contain old entries.

Because of periodic beaconing it consumes extra bandwidth.

Fails to work at high mobility.

2.7 DGRP (Directional Greedy Routing Protocol)

It’s a position based greedy routing protocol [15]. It uses the two forwarding strategies greedy and perimeter. It predicts the nodes positions within the beacon interval whenever a data packet needs to be forwarded. This prediction is done using previous knowledge about position, speed, and direction of motion of node. If link between the forwarding node and its neighbor node is not stable, possibility of packet loss is high in DGRP. Further the prediction of position information is not always reliable.

Drawbacks

packet delivery ratio is very low

large delay at high traffic density

uses to many hops to reach the destination

2.8 Greedy Perimeter Stateless Routing (GPSR)

GPSR [16] is a routing protocol for mobile wireless networks. Many other routing algorithms before GPSR used graph-theoretic notions of shortest paths and transitive reachability to find routes. GPSR however exploits the correspondence between geographic position and connectivity in a wireless network. For this purpose it uses positions of nodes to make packet forwarding decisions. It uses greedy forwarding to forward packets to nodes that are closer to the destination. In some regions of the network, a greedy path may not exist. In this case, GPSR recovers by forwarding in perimeter mode. In this mode a packet traverses successively planar sub-graph of the full radio network connectivity graph until a node closer to the destination is reached. Here greedy forwarding resumes.

Drawbacks

It uses a longer path to the destination causing more transmission delay. Further, it can work when network is dense enough and may fail otherwise.

2.9 PDGR (Predictive Directional Greedy Routing)

In PDGR [17] the weighted score is calculated for current neighbors and possible future neighbors. In PDGR, the weighted scores for immediate nodes 2-hops away are also calculated. Here next hop selection is made based upon the prediction and it is not reliable in all situations. It does not provide guarantee that the delivery of packet to the node present in the edge of the transmission range of node considered as next hop. In high dynamics of vehicles, this has low packet delivery ratio, high delay and an increased routing overhead.

Drawbacks

large delay when traffic density is high.

low packet delivery ratio and increased routing overhead.

2.10 Potential Edge Node Based Greedy Routing Algorithm (EBGR)

Potential Edge Node Based Greedy Routing Algorithm (EBGR) [18] is a uni-cast and position based greedy routing algorithm. It was designed for sending messages from a node to any other node in a vehicular ad hoc network (VANET). The aim of the EBGR algorithm is to optimize the packet behavior for VANETs with high mobility and deliver messages with high reliability. The algorithm for EBGR has six basic functional units. (1) Neighbor Node Identification (NNI), (2) Distance Calculation (DC) (3) Direction of Motion Identification (DMI), (4) Reckoning Link Stability (RLS), (5) Potential score calculation (PS) and (6) Edge Node Selection (ENS).

The NNI is used for collecting information of all neighbor nodes present within the transmission range of source/forwarder node at any time. The DC is responsible for calculating the closeness of the next hop using information from GPS system. DMI is responsible to identify the direction of motion of neighbor nodes which is moving towards destination. The RLS is responsible for identifying link stability between the source/packet carrier node and its neighbor nodes. The PS is responsible to calculate potential score and it also identifies the neighbor node having a higher potential for further forwarding of a particular packet to the destination. The ENS is responsible to select an edge node having higher potential score in different levels of transmission range.

Drawbacks

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Its ENS unit tries to identify edge nodes that more likely to be out of a node's range. This scheme fails when there are vehicles moving with variable speeds.

2.11 Fisheye state routing (FSR)

In FSR [19], a topology table (TT) is used. This table is maintained by a node based upon the latest information received from neighbors. Table information is periodically exchanged with local neighbors. In the case of large networks size of message should be reduced. For this purpose, FSR uses the different exchange period for different entries in routing tables. The problem with the FSR routing is that size of routing table increases with the increase in network size. With the increase in mobility, route to remote destination also become less accurate.

Drawbacks

Size of routing table increases with the increase in network size

With the increase in mobility, route to remote destination also become less accurate.

It has very poor performance in large ad hoc networks.

Less or no knowledge about distant nodes.

With the increase in network, the processing overhead of routing table also increases.

Information for route establishment is not sufficient.

2.12 Temporally Ordered Routing Algorithm (TORA)

In TORA [20] , routing is based on directed acyclic graphs. These graphs direct the flow of packets and ensure its reachability to all nodes. A node constructs the directed graph by broadcasting query packets. On receiving a query packet, node having a downward link to destination broadcasts a reply packet. Otherwise packet is simply dropped. TORA has the advantage that it gives a route to all the nodes in the network. The problem for TORA is that maintenance of all these routes is very difficult in VANETs.

Drawbacks

Maintenance of all routes is very difficult in VANETs.

It is not scalable.

2.13 Greedy Traffic Aware Routing protocol (GyTAR)

Greedy Traffic Aware Routing protocol [21] has given a new concept of intersection-based routing protocol. The main purpose of this protocol was to reduce the control message overhead & end-to-end delay with low packet loss.

Drawbacks

This depends upon roadside units which have their own drawbacks.

2.14 CAR (Connectivity-Aware Routing)

For city and highway environment Connectivity-Aware Routing (CAR) [22] has been designed. It is based on AODV for path discovery but uses Preferred Group Broadcasting (PGB) for data dissemination mode.

Drawbacks

Path discovery process used by AODV cannot be used in VANETs.

Unnecessary nodes can be selected as anchor nodes.

Path discovery process does not work in a rapidly changing network topology.

2.15 Street Topology Based Routing (STBR)

The proposed protocol Street Topology-Based Routing (STBR) [23] is based upon the following idea. Elucidate a given street map as a planar graph which has three valid states (1) master (2) slave (3) forwarder for a node. In this protocol, one node is selected as a master on a junction and other nodes act as slaves. The intermediate nodes between junctions serve as forwarders.

Drawbacks

In STBR complexity increases due to some special cases. For example, transferring the neighbor table to new master when old master leaves the junction.

2.16 Greedy Routing with Abstract Neighbor Table (GRANT)

GRANT [24] applies an extended greedy routing algorithm concept. Abstract Neighbor Table of GRANT performs division of the plane into areas and includes only one representative neighbor per area.

Drawbacks

Performance evaluation of GRANT has been done on static traces but VANET has a high mobility characteristics.

There is overhead of beacons. Further the inaccuracy in packet delivery has not been measured.

2.17 Direction-based AODV routing protocol (DAODV)

Working of this protocol [25] is as follows.

1- Discovers paths to the destination using route request message (RREQ). Sender multi-casts RREQ to the nodes selected based upon their position and direction.

2-Uses routing tables for packets forwarding.

4- Performs route maintenance.

5- Routing tables are frequently updated due to change in network topology.

The approach used in DAODV is similar to that used in AODV. The only difference between this scheme and AODV is that DAODV uses position and direction during path discovery process.

Like AODV, Route discovery process of DAODV uses RREQ (route request) message.

When a source node wants to communicate destination node, DAODV multi-casts RREQ message to selected neighbor nodes. This selection is made upon their position and direction. Neighbors receiving the request (RREQ) forward RREQ further and so on. The source acquires route reply (RREP) message when route is successfully discovered.

Packets are forwarded to the destination using routing tables. When routing error occurs during packet forwarding, route error message (RERR) is sent back to the sender. The sender then initiates route discovery process again.

Drawbacks

1- It uses path discovery process as used in AODV routing protocol.

2 â€" Like AODV, it uses routing tables which fail to update a high frequency of link breakages.

3- Parameters used for next hop selection are not sufficient to select best next hops.

4- It fails to work when mobility of nodes is high. At high mobility, frequency of change in topology is too high to determine a reliable path to the destination.

2.18 Cluster Based Location Routing (CBLR)

CBRL [26] is a reactive and cluster based routing protocol. During cluster formation every node broadcasts a hello message and then waits for a predefined time. When the node receives a reply from a cluster header before the timer expires, it becomes a cluster member. It becomes a cluster header, otherwise.

Each cluster header maintains a table which contains the addresses and geographic locations of cluster members and gateways nodes. It also maintains a Cluster Neighbor Table to store the information about the neighboring clusters. When a source wants to send data packet to a destination, it first checks whether the destination is in same cluster. If destination is in same cluster, the source sends the packet to the neighbor closest to the destination. Otherwise, data packet is stored in the buffer of source which starts a timer and broadcasts Location Request (LREQ) packets. In order to minimize number of transmissions, only gateways and cluster-heads can retransmit the LREQ packet.

After receiving a request, each cluster-head checks whether the destination is member of its own cluster or not. If destination is a cluster member, then cluster header sends a Location Reply (LREP) packet to the sender based upon the information present in LREQ packet and cluster neighbor table.

Otherwise it retransmits LREP to adjacent cluster-headers. CBLR is more suitable for networks having high mobility because the location of the source and destination is updated every time before data transmission starts.

Drawbacks

Use flooding. This results in wastage of bandwidth.

Cluster-head may be a single point of failure.

2.19 Robust Vehicular Routing (ROVER)

ROVER [27] is a geographical multicast protocol where control packets are broadcasted and the data packets are uni-casted in the network. The purpose of this protocol is to send messages to all other vehicles within a specified Zone of Relevance (ZOR). Zone of Relevance is defined as a rectangular area specified by its corner coordinates. A message is defined by the [A, M, Z] triplet which indicates the specified application, message and identity of a zone respectively. When a vehicle receives a message, it will accept message if it is within the ZOR. Robust Vehicular Routing protocol also defines a Zone of Forwarding (ZOF). This zone includes the source and the ZOR. All nodes in ZOF are used in the routing process. The protocol uses a reactive route discovery process within a ZOR. This creates lot of redundant messages in the network which leads to wastage of bandwidth, congestion and high delay in data transfer. To overcome this issue, two Zone Dissemination Protocol for VANETs was proposed. This protocol uses hop-count in packet. The counter is decremented when the packet is forwarded. When the hop-count counter reaches to zero, the packet is discarded. This may cause the nodes near to the sender forward same packet multiple times. This problem is avoided by introducing sequence number for every packet to find whether a packet has been already received or not.

Drawbacks

Use flooding which results in wastage of bandwidth.

Zone of Relevance (ZOR) and Zone of Forwarding (ZOF) change very soon when vehicles are moving at high speed. This requires new specifications of these zones. Re-specification of these zones at a high frequency may be problematic.

There are many other protocols proposed for VANETs. But all of them have one or more deficiencies. For example the proposed protocols in [28, 29, 30] are based on static map of cities and their function is restricted by knowledge of road topology. These protocols have poor performance in terms of one or more performance metrics also.

2.20 Summary

VANETs have a highly dynamic network topology. This makes routing a challenging task in VANETs. Due to routing complexity in VANETS, none of the proposed protocol can be considered as ideal one. Every protocol has one or more drawbacks associated with it.