Stateless Routing In Vehicular Ad Hoc Networks Computer Science Essay

Published: Last Edited:

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

Greedy Perimeter Stateless Routing is a Position-Based Routing Protocol for Wireless Networks that uses the Position of routers. GPSR makes greedy forwarding decision by using closest neighbor's information of destination. In GPSR each node has the knowledge of its current physical position and also the neighbor node, this knowledge about node provides better routing. When a packet reaches a region where there is no closest node to the destination then greedy forwarding is impossible, the algorithm recover by using perimeter forwarding. By Studying GPSR, we find that Greedy part of GPSR is not always finding the most optimized route. In this paper we investigated about different forwarding method of GPSR in wireless network and also find out the problems and their solutions. The main aim of our study was to identify which routing method has better performance in highly mobile environment of VANET.

In recent years Wireless Networks have seen tremendous advancements in design and applications. VANET is a technology to integrate the capabilities of new generation wireless networks to vehicle. VANET different from MANET by its highly dynamic topology. By using 802.11 WLAN technologies VANET have recently received considerable attention. Blind crossing, traffic monitoring, collision prevention, control of traffic flows and real time detour routes computation are the variety of VANET applications. VANET provides internet connectivity to vehicular nodes, so the user can download music, play games or send e-mails. High nodes mobility and unreliable channel conditions are the characteristics of VANET, which poses many challenging issues like data sharing, data dissemination and security issues. Minimum communication time with minimum consumption of network resources is the main requirement of routing protocol. Some routing protocol like DSR (Dynamic Source Routing) and AODV (Ad-Hoc On-Demand Distance Vector) which are developed for MANETs (Mobile Ad-Hoc Networks) are directly applied to VANETs. Due to high mobility of nodes where network can be dense or sparse such phenomenon is not suitable. Route repairs and failures notification overheads increases significantly leading to low throughput and long delay. In wireless networks consist number of mobile stations, finding paths from source to a destination through intermediate nodes is challenging. When node move, the topology of the network changed rapidly. Such networks required responsive routing algorithm that finds valid routes as the topology changes and old routes break. To simulate and compare the performance of routing protocol in VANET a number of studies has been done[4][6][7][8][9] and the simulation result shows that because of the characteristics of dynamic information exchange, fast vehicle's movement and relative high speed of mobile nodes suffers from poor performances. So in VANET finding and maintaining routes is a very challenging task. The position - based routing protocols have been brought forward. GPSR (Greedy Perimeter Stateless Routing) [1] is one of the best known position based routing protocols. GPSR is a responsive and efficient routing protocol for mobile wireless network. GPSR exploits the correspondence between geographic position and connectivity in a wireless network by using the position of nodes to make packet forwarding decision. Operation and management of large number of real vehicular nodes is expensive hence simulators are involved for evaluation. The performance result of ad hoc networks depends on the mobility model. Vehicular movements are based on the same random model with higher maximum node speed. Increasing the number of nodes in the network and increasing mobility rate is the aim of every researcher.

In scaling of a routing algorithm the dominant factors are:

The number of routers in routing domain.

The rate of change of the topology

GPSR will allow the building of networks that cannot scale using prior routing algorithms for wired and wireless network. Networks that push on mobility and number of nodes include:

Rooftop network: fixed, dense deployment of vast number of nodes.

Sensor network: mobile, potentially great density, vast number of nodes, impoverished per node resources.

Ad hoc network: mobile, no fixed infrastructure and varying density.

Vehicular network: mobile, non-power-constrained and widely varying density.

The network, either a randomly generated network based on a random speed provided by the user, or a ring or star topology will construct its connections from a simple, beaconing protocol wherein each node broadcasts an empty packets, So that all nodes in radio range will store the information of node in their routing table.

This paper presents a through survey of the existing work on Greedy Perimeter Stateless Routing (GPSR) in Wireless Networks. The main purpose of this paper is to provide understanding of the GPSR protocol and to stimulate new research directions in this area.

The remainder of the paper is organized as follows: Section II describes the Forwarding Methods (Algorithm) of GPSR. In Section III we describe the problems occurs in GPSR. Finally Section IV concludes the paper.


Greedy Perimeter stateless Routing algorithm consists two methods for forwarding packets: greedy forwarding and perimeter forwarding. In the GPSR algorithm if the packets moving in Perimeter mode across the same edge that was first crossed on the packet's current face, then made a complete tour of the face without any progress, GPSR drops the packets. When the first edge crossed after a face changes ends at a node with only one edge the right hand rule chooses that same edge in the other direction, as the next edge and it is dropped. In simple term we can say that if the packet is being crossed in the same direction then that packet will be dropped. There is finite number of faces along the path to the destination or more specifically a finite number of face changes made during the packet journey. These are the reasons that shows that in each face either the packet would leave the face, the destination would be dropped if the first edge traversed would be traversed a second time. Thus any edge that is two directional on a face that was traversed first by a packet entering that face will be traversed in the same direction unless the packet leaves the face.

Greedy Forwarding

A node which forwards a packet to the neighbor that is closer to the packet destination is called greedy forwarding [14].

Fig.1 Greedy Forwarding. x want to sent a packet to D and it forward it greedily to y.

The Greedy Forwarding algorithm looks at the Euclidean distances from each to the packet destination and picks the one with smallest distance. After finding the closest neighbor the packet is forwards to that network. But, if none of the neighbors are closer to packet destination than it, then the algorithm returns failure. This is the main drawback of Greedy Forwarding.

Fig.2 Greedy Forwarding failure. x want to sent a packet to D but none of its neighbor are closer to D than x.

The forwarding decision can not be made without knowledge of the topology one or more hops away. When a forwarding node does not receive beacon from its neighboring node with in a specific time period, then a GPSR router assumes that the neighbor has failed or gone from the radio range, and deletes the neighbor from its table. The major advantage of Greedy forwarding is that it holds current physical position of forwarding node, thus by using this strategy total distance to destination becomes less and packets can be transmitted in short time period. Advanced Greedy Forwarding technique improves the effectiveness of greedy forwarding.

During the process of greedy forwarding local Maximum happens and the node would switch to perimeter routing that attempts to route the packet along the perimeter of the local maximum region in a clockwise diection. There is no guarantee that a node could always find a suitable neighbor to forward its packet, i.e local maximum happens. To recover from this situation, Geographic Source Routing (GSR) implement one of the following schemes:

Buffer the Packet: The forwarding node could buffer the packet, check periodically and later if possible, forward it again.

Switch to Greedy Forwarding: Since the packet could not be forwarded through the computed sequenceof junction, the forwarding node could choose to forward the packet greedly towards the destination


Recalculate the shortest path: The forwarding node could calculate a new sequence of junction from its current position to the destination and use this new path for forwarding the packet.

Perimeter forwarding

Perimeter Forwarding is used where greedy forwarding fails. Its means when there is no closest neighbor to the destination is available then Perimeter Forwarding is used. Perimeter Forwarding uses the right-hand rule[1]. According to

this rule each node involved to forward packet around the void region and each edge that is traversed are called Perimeter.

Edges may cross when right hand rule find perimeter that are enclosed in the void by utilizing "Heuristic approach". Besides it provide maximum reach ability to destination, heuristic has some drawback that it removes without consideration of those edges which are repeated and this may cause the network partitions

Fig.3 Perimeter Forwarding. x is the node where Greedy Forwarding failed. Algorithm uses right hand rule to forwars packet.

In case of city scenario Perimeter mode approach suffers from several problems:

Network Disconnection: Due to buildings and trees in city area Greedy position-based routing and its recovery mechanisms to not fully applicable[3]. Nodes that directly connect in free space cannot communicate in city area due to radio obstacles.

Too many hops: A planarized connectivity graph for vehicles along a single street essentially lead to a graph where a vehicle no longer send packets to the neighbor with the largest forward progress. In city area, planarized connectivity graph can increase delay due to large number of nodes [3].

Routing loops: Routing loop can be occurred in packets while using perimeter method due to mobility [3]. The traversed of the initial face would be used to determine a face loop but it is never traversed again, the packet is circle until the max hop count is reached. In city area when there are many nodes participating in the communication at the same time there are more chances of routing loops.

Incorrect route selection: In high mobility and too many hops, perimeter routing method can select a long route using a right hand rule [3]. The possibility of selecting and longer than necessary route is increased when there is more than one route available. High mobility and too many hops in city area may lead to incorrect route selection.

Planarized Graph

A graph in which no two edges cross is known as planar and the graph whose edges are dictated by threshold distance between vertices are termed as unit graph. A planar graph has two types of faces:

Interior face: The closed polygonal regions bounded by graph's edge are called interior faces.

Exterior face: The unbounded face outside the boundary of the graph is called exterior face.

There are two types of planar graph [13][16] used to remove the crossing edges:

Relative Neighborhood Graph (RNG): RNG is defined, when two edges intersect with radio range of each other and share the same area.

Fig.4 Example of RNG

In figure 4, x and y are the two edges that share the area of two vehicles x and y. The edge x, y are removed by using RNG, because another edge from x towards v is already available. When we begin with a connected unit graph and remove edges not part of RNG, then we cannot disconnect the graph. (x,y) is only eliminated from the graph when there exists a v within range of both x and y. eliminating an edge requires an alternate path through a witness exist.

Gabrial Graph (GG): Graph is used to remove only those crossing edges which are in between the shared area of two nodes having the same diameter as the other nodes have.

Fig.5 Example of GG

This figure shows that the midpoint diameter is less than the diameter of node x or y. Thus the edges from the x, y cannot be removed. So there is less network disconnection in the GG as compared to RNG. In literature [1] it has been shown that the RNG is a subset of the GG. It has been noted that the RNG and GG offer different densities of connectivity by eliminating different number of links.

Combining Greedy and Planar Perimeter

This section present the full Greedy Perimeter Stateless Routing Algorithm, which combines the greedy forwarding with the perimeter forwarding to provide better routing decision on both full and planarized network graph where greedy forwarding is not possible. All the nodes maintain a neighbor table, which stores the address and location of their single hop radio neighbor. GPSR uses a packet header field in perimeter mode forwarding. To indicate whether the packet is in greedy mode or perimeter mode GPSR packet header includes a flag-field.




Destination Location


Point on Packet Entered Current Face


Location Packet Entered Perimeter mode


First Edge Traversed on Current Face


Packet Mode: Greedy or Perimeter

Table 1. GPSR Packet header field used in perimeter mode forwarding.

Packet sources also include the geographic location of the destination packet. Once a packet's source set the location destination field; then it is not changed as the packet is forwarded through the network. When a greedy mode packet for forwarding is received then a node searches its neighbor table for the neighbor that is closest to the packet's destination and if there is a neighbor close to the destination then the node forwards the packet to that neighbor. When no neighbor is closer, then the node marks the packet enters perimeter mode.

GPSR Performance problem in VANET

This section reviews performance related problem of GPSR. When evaluating GPSR in VANETs, we observe that inconsistency of neighbor table's information leads to many problems and low throughput. Outdated information in the neighbor tables can be healed with the more frequent beaconing; this would certainly increase the congestion and the potential for collisions. We may add information about the node's speed and direction to improve the accuracy of neighbor tables. The neighbor table is not always up-to-date, so the selected neighbor may not be optimal or even may not be a neighbor any more. Experimental study of GPSR in VANET defines that when the node picks a neighbor to forward the packet, only in 20-35% of the cases the chosen node is really the closest one to the destination. When the position of the destination is updated only at the last hop, then the improvement still is noticeable, about 50% of the data are delivered.

Besides GPSR has several characteristics, it suffers from several drawbacks:

Greedy Forwarding is unsuitable for the vehicular network where the nodes are highly mobile and the node may not be able to maintain it next hop neighbors information as the other node may gone out of range due to high mobility. This can lead to data packet loss.

The beacon may lost due to channel destruction or bad signal. This problem can lead to removal of neighbor information from location table

Both the recovery strategries of GPSR i.e Perimeter mode and GSR i.e Switch back to greedy are insufficient in city environment. To handle forwarding failure the Ordered Pair Greedy perimeter Stateless Routing protocol is used and the simulation results shows that on static sensor network, Order Pair GPSR packet transmission ratio is higher than GPSR.

So, there is a need of such routing algorithms, which merges position information with the road topological structure in order to make possible vehicular communication in presence of radio obstacle. Presently many researchers are engaged to solve the problems occurred in forwarding algorithms that fulfill the various requirements, and numerous algorithms related to finding routes and forwarding packet have been proposed.


This paper outlined the routing algorithms that use geography to achieve small per-node routing state, small routing protocol message cost and extremely robust packet delivery on wireless network. VANET provides an interesting and challenging environment for ad hoc networks. GPSR, a routing protocol for wireless network uses the position of routers and a packet's destination to make packet forwarding decision. GPSR is not always finding the most optimized route, especially in the denser scenario. To solve this problem new mechanism are proposed and evaluated. However there are still more work to be done, so that the best route is optimized in both the denser and sparse environment.