Performance Analysis of Greedy Perimeter Stateless Routing based Vehicular Ad Hoc Network Protocols

DOI : 10.17577/IJERTV12IS040189

Download Full-Text PDF Cite this Publication

Text Only Version

Performance Analysis of Greedy Perimeter Stateless Routing based Vehicular Ad Hoc Network Protocols

Sayantan Paul

Department of Electronics and Communication Engineering SRM Institute of Science and Technology

Kattankulathur, India

Sarthak Chaturvedi

Department of Electronics and Communication Engineering SRM Institute of Science and Technology

Kattankulathur, India

Silvi Bakhshi

Department of Electronics and Communication Engineering SRM Institute of Science and Technology

Kattankulathur, India

M.K. Srilekha

Department of Electronics and Communication Engineering SRM Institute of Science and Technology

Kattankulathur, India

AbstractThis review paper offers a comparative analysis of three routing protocols: Greedy Perimeter Stateless Routing (GPSR), Maxduration-Minangle Greedy Perimeter Stateless Routing (MM-GPSR), and Position-Aware Greedy Perimeter Stateless Routing (PA-GPSR). The evaluation is based on three performance metrics: Packet Loss Rate (PLR), End-to-End Delay (E2ED), and Network Yield (NY). GPSR is a widely employed Distance Vector Routing (DVR) protocol in Vehicular Ad-Hoc Networks (VANET). MM-GPSR, an enhanced version of GPSR, uses two additional parameters to eliminate routing loops and node placement sensitivity. PA-GPSR is a further improvement that incorporates several parameters from two additional extension tables to prevent packet retransmission to the same neighbor in Recovery Mode. The network performance of these protocols was compared using Simulation of Urban MObility (SUMO) and Network Simulator version 3 (NS-3) under various configurations of nodes and source-destination pairs. Simulation results reveal that PA-GPSR outperforms both GPSR and MM- GPSR in all metrics. GPSR and MM-GPSR have no definitive winner, as each performs better in different scenarios. This review paper offers valuable insights into the network performance of GPSR, MM-GPSR, and PA-GPSR protocols and serves as a helpful resource for researchers and practitioners seeking to choose the most appropriate routing protocol for their wireless sensor network applications, including VANETs.



    Vehicular Ad-Hoc Network (VANET) is a protocol based on the 'IEEE 1609' standard and the 'IEEE 802.11p' Wireless Local Area Network (WLAN). It is an infrastructure-less network that enables inter-vehicular communication without a central base station or controller. VANETs are particularly useful in emergency situations where information must be transmitted without relying on pre-existing network infrastructure. However, many VANET protocols are derived from Mobile Ad-Hoc Networks (MANET), which often fail to account for the high speed of vehicles and their rapid changes

    in position, rendering them unsuitable for vehicular implementation. GPSR was proposed for use with dynamic nodes, where data packets are forwarded to the nearest node based on next-hop distance estimation. This approach makes the protocol highly scalable and energy-efficient, but it suffers from inferior network performance and lacks support for modern standards. MM-GPSR introduces two additional constraints, 'Maxduration' and 'Minangle', which define the time a packet can remain in the network and the angle between the current, next-hop, and destination nodes, respectively. While MM-GPSR offers improved network performance and support for modern QoS standards, it sacrifices scalability and efficiency. Path-Aware GPSR (PA-GPSR) aims to address these limitations using extension tables that include additional parameters such as IP addresses, coordinates, timestamps, and vectors. PA-GPSR improves upon previous protocols by employing entry-based Greedy Forwarding and an upgraded Recovery Mode. Furthermore, it mitigates the impact of path redundancy and packet routing loops.


    1. Greedy Perimeter Stateless Rouitng

      The GPSR protocol combines Greedy forwarding and Perimeter forwarding, and as a stateless protocol, it does not require the storage or maintenance of routing tables. The source node employs Greedy forwarding to identify the closest node to the destination and selects it as the next-hop node for forwarding data packets. Upon receiving the data packets, the next-hop node becomes the source node, and the process continues until the destination node is reached.

      Fig. 1. Nodes move out of communication range in Greedy Forwarding

      If the network encounters routing holes, Perimeter forwarding takes over from Greedy forwarding until the data packets successfully reach their intended destination node. GPSR tends to favor a next-hop node that is close to the destination node within the neighbor list. As a result, the next- hop node is often located near the edge of the communication range.

      Fig. 2. Formation of Redundant Paths in Greedy Forwarding

      Due to the rapid movement of nodes in vehicular networks, the next-hop node is likely to move out of the current node's communication range before receiving the data packets. This leads to a disrupted communication link and the failure of greedy forwarding, ultimately resulting in packet loss or retransmission and negatively impacting the network's overall performance. In such a situation, the GPSR protocol switches to perimeter forwarding after greedy forwarding fails to transmit data packets. When using Perimeter forwarding, the protocol constructs a planar network graph of a node's neighbors and applies the right-hand rule to avoid any empty areas.

    2. Maxduration-Minangle GPSR

      The instability in neighbor relationships within Greedy Forwarding can be mitigated by introducing two parameters: the cumulative communication range (T) and the allowed communications area (Q). By comparing the cumulative communication durations and evaluating the communication stability among all neighboring vehicle nodes of the source node, the most stable next-hop node can be determined. Enhanced perimeter forwarding considers the positional relationship between the neighbor nodes and the target node to tackle path redundancy. This is achieved by analyzing and comparing the respective angles of all source node's neighbor nodes, after which an optimal next-hop node is chosen.

      Fig. 3. Greedy Forwarding with Cumulative Communication Range

      In the greedy forwarding process, the current node initially establishes the permissible communication region, calculates, and contrasts the cumulative communication durations of its neighbors. Subsequently, the neighbor with the longest cumulative communication duration is selected as the next-hop node.

      Fig. 4. Perimeter Forwarding using Cumulative Communications Area

      When greedy forwarding is unsuccessful, the current node employing perimeter forwarding calculates and compares the angles of its associated neighbor nodes before selecting the neighbor node with the smallest angle as the next hop for forwarding data packets.

    3. Position-Aware GPSR

    Although MM-GPSR addresses some limitations of the GPSR protocol, it presents its own set of challenges. MM- GPSR is particularly sensitive to parameter values, and inaccurate estimations can lead to suboptimal routing paths and diminished network performance, sometimes even worse than GPSR. The integration of extra parameters in the decision- making algorithm heightens the system's overall computational complexity, potentially resulting in extended routing times and increased energy consumption ifnot properly optimized. Furthermore, MM-GPSR may not always efficiently scale to accommodate expansive network topographies, as the 'Minangle' parameter demands extended computation times in densely trafficked areas. PA-GPSR, a position-based routing protocol leveraging Vehicle-to-Vehicle (V2V) communication standards, seeks to overcome the limitations of both GPSR and MM-GPSR protocols. It enhances greedy forwarding and perimeter forwarding protocols by incorporating Deny Tables (DT) and Recently Sent Tables (RST) into the packet forwarding decision policy. These tables can be seen as extensions of the pre-existing Neighbor's Table (NT) present in

    both GPSR and MM-GPSR protocols. This allows the algorithm to dynamically adapt to changes in topology and network conditions. If an entry in the NT expires, the corresponding entries in the DT and RST also become invalid, making the system self-adjusting. Additionally, PA-GPSR improves upon the recovery mode in GPSR and MM-GPSR by employing both the 'Left-Hand Rule' and 'Right-Hand Rule' through packet duplication.


    As mentioned earlier, the Deny Table (DT) and the Recently Sent Table (RST) serve as extensions to the existing Neighbor's Table (NT). The NT consists of individual entries for each neighboring node, generated by transmitting 'hello' packets within a one-hop distance. These entries contain information such as the node's IP address, its x and y coordinates within the functional topology, and a timestamp for the response. The DT extends the NT and is employed to bypass routes that are unsuitable for a specific destination. To assess such situations, the DT relies on two parameters: the IP address of the neighbor and a vector containing the IP addresses of the intended destinations. Similarly, the RST is composed of two fields: the neighbor's IP address and a vector of three-element tuples (F, I, D), where 'F' represents the forwarding type, 'I' denotes the packet identification element (IPv4), and 'D' refers to the destination node's IP address. The 'F' category can be divided into three types: 'G' for Greedy Forwarding, 'R' for Right-Hand Forwarding, and 'L' for Left-Hand Forwarding.

    1. Greedy Forwarding in PA-GPSR

      In this strategy, a next-hop node is selected for forwarding a packet only under certain conditions, specifically when the destination is not present in any of the DT entries or if the packet has never been sent to another node before. When a node receives a packet while in Recovery mode, its IP address is added to the DT entries, ensuring that the packet is not sent to this particular node again until the DT entries are refreshed or expired.

      Fig. 5. Greedy Forwarding in PA-GPSR leading to a local Maxima

      Moreover, if a node is closer to the destination and there is no existing entry for the packet in the DT, the system will then check the RST entries to verify if that packet has already been sent to a neighboring node. If the packet has not been sent to a neighboring node previously, the packet will be forwarded to that neighbor node. However, if an RST entry is found to match, the system will proceed to examine the next nearest neighbor node, applying the same method. In the event that neither a DT entry nor an RST entry is found for that packet,

      the algorithm transitions to Recovery Mode, an action that bears similarity to what is found in GPSR and MM-GPSR based protocols. This situation can also arise if the node nearest to the destination cannot be reached within a one-hop distance.

    2. Recovery Mode in PA-GPSR

      The PA-GPSR protocol employs an enhanced version of the Recovery Mode present in GPSR and MM-GPSR, sending redundant packets through both Right-Hand and Left-Hand Forwarding simultaneously.

      Fig. 6. Left Hand Rule in PA-GPSR Recovery Mode

      Fig. 7. Right Hand Rule in PA-GPSR Recovery Mode

      By utilizing both rules concurrently, the system aims to optimize performance as each rule can yield superior results depending on the network topology. This approach effectively addresses the issue of path redundancy found in earlier protocols. Nonetheless, sending duplicate packets may raise network overhead, which the algorithm mitigates by not forwarding packets that have a corresponding RST entry. Consequently, a node designated to relay packets using the Right-Hand Rule will refrain from forwarding those transmitted via the Left-Hand Rule.


    The objective of this project is to compare the PA-GPSR protocol with the likes of GPSR protocol and MM-GPSR protocol. These three protocols have been benchmarked against each other on the basis of the following three network metrics:

      1. Packet Loss Rate (PLR): A ratio of the total number of packets lost to the total number of packets sent from the source node.

      2. End-to-End Delay (E2ED): The average of all delays associated with a data packet received successfully at a node.

      3. Network Yield (NY): A ratio of the total number of packets received at the destination to the total number of packets sent by all the nodes present on the network.

    1. Setup

      The experiment was carried out to simulate automobiles in a region measuring not less than a square kilometer that included nine junctions and twelve two-way roads. The starting position of the vehicles were arbitrarily allocated, and their movement was controlled using the Krauss model that was limited to the streets.


      TABLE 1


      The automobiles were not allowed to exceed a speed of fifty kilometers per hour. To create a less dense topology, an odd multiple of nodes ranging from thirty, fifty, seventy, ninety and one hundred ten were utilized to establish an interval rate of 1000 millisecond. Every automobile was outfitted with an antenna propagating omnidirectionally within a communications range of a quarter kilometers possessing a data rate of 3000 Megabits per second. The access control sublayer was modeled after the IEEE 802.11p WAVE standard, and in order to evaluate the fading characteristics of the wireless channel, the Two-ray Ground Reflection model was implemented in this test. The creation of packets for a static size of half a Kilobyte in the nodes required the application of Constant Bit Rate (CBR). These CBR links were varied over a spectrum of five to twenty connections at a time as a means to quantify the influence of network traffic.

      The source-destination pairs were selected haphazardly for every set of emulations wherein their locations were acquired through a positioning service. However, even though haphazardly oriented, the same set of randomly generated pairs are employed to compute other CBR links so as to maintain consistency across the results.

    2. Packet Loss Rate

      On average, under common circumstances, a reduction in PLR can be observed for all the three DVR protocols. This can be attributed to a surge in the number of automobiles/nodes which in turn enhances the connectivity of the network and diminishes the likelihood of encountering a partition in it. One plausible explanation for the superior performance of PA- GPSR over GPSR and MM-GPSR is the inclusion of a loop control system that is used in the former protocol. Packet loops are known to arise in topologies that are deficit of mobile nodes. Without loop control in place, it can be assumed that any routing algorithm will undergo a rise in the PLR because every data packet has been set with a specific time limit beyond which it cannot remain and function in the network.

      1. 5 CBR

      2. 10 CBR

      3. 15 CBR

      4. 20 CBR

        Fig. 8. Average Packet Loss Rate for varying number of nodes

        In the given plots, PA-GPSR is shown to have a lower average PLR value when compared to the plots of GPSR and MM-GPSR protocols over the entire range. This can be attributed to the fact that PA-GPSR incorporates several node pairs which reduces the chances of a packet moving through a lengthier path due to an flawed recovery choice. However, it can also be observed in figures 8a. and 8b. that beyond the count of 90 automobiles, MM-GPSR has a lower PLR value than that of PA-GPSR. But at the end, the difference accounts only for less than 3-5% of the average rate, which is insignificant to have any adverse impact on the network parameters. MM-GPSR seems to perform better in this range because of its ability to use redundant tracks to arrive at the required destination.

    3. End-to-End Delay

      Generally, a decrease in the end-to-end delay of MM-GPSR and GPSR protocols can be seen when the number of nodes goes up in the topology. Analyzing the given outputs, PA-GPSR can be concluded to have a lower end-to-end delay across all the varied CBR links. It also turns out to be the only protocol showing a persistent stability across the E2ED values unlike MM-GPSR and GPSR which keep on fluctuating with a rise in the number of vehicles.

      1. 5 CBR

      2. 10 CBR

      3. 15 CBR

      4. 20 CBR

        Fig. 9. Average End-to-End Delay for varying number of nodes

        The recovery process in PA-GPSR uses both the left and right hand rules to select the most efficient route which promotes its superiority over the other two protocols. MM-GPSR increases the delay because of its tendency to create surplus paths due to the use of Minangle function in its recovery system. Additionally, E2ED can be computed only if the packet is successfully received at the destination without being dropped from the network. This refers to a cross correlation between E2ED and packet loss. Hence if an algorithm has a stunted value of E2ED and is shown to deliver more packets to the destination than the other protocols, it can be safe to assume that it has an equally lower latency when compared to the others.

    4. Network Yield

      The network yield is a measure of the efficiency of the network in terms of the percentage of packets that are successfully transmitted between the source and destination vehicles. It considers both the routing performance in terms of packet delivery ratio and as well as the overall network throughput. It is equivalent to the concept of application-level throughput in communication systems.

      1. 5 CBR

      2. 10 CBR

        (d) 20 CBR

        Fig. 10. Average Network Yield for varying number of nodes

        A small number of CBR links can lead to an unsteady network yield. However, as the number of nodes and CBR links increases, the network yield of all three routing protocols is also demonstrated to increase. Since, all the protocols are based on DVR and are using Greedy forwarding as their default scheme, the network connectivity increases with an increase in the number of vehicles on the network. In actuality, implementation of such forwarding is also the reason behind an improved Packet Delivery Ratio (PDR) as it reduces the hop distance. In the plots above, PA-GPSR produces an overall better value of network yield except for a singular exception where GPSR has a larger yield because the extension tables are of no use under certain rare configurations with nodes greater than 90 vehicles. The improved performance of PA-GPSR over the GPSR protocols can be attributed to the duplication of packets in the recovery system wherein it reaches the destination node with minimal hops when compared to the latter. MM-GPSR is also inferior to the PA-GPSR protocol as the former suffers from a higher PLR and E2ED values, which is jointly responsible for its lower network yield.

      3. 15 CBR


Designing a routing algorithm for VANET can be challenging due to the rapid movement of nodes and the frequent changes in topology. The algorithm must be capable of dynamically updating itself to adapt to the current network topography. Greedy Perimeter Stateless Routing (GPSR) is an attempt to create a VANET protocol that identifies the next hop to the destination based on neighboring nodes' distances to the destination. However, it suffers from routing loops and is sensitive to node placements. Maxduration-Minangle GPSR (MM-GPSR) is an improvement proposed to address GPSR's drawbacks by including two additional parameters that set a time limit for packet distribution and calculate an angle between the source-destination nodes through the next-hop nodes. However, it falls short in terms of scalability and efficiency. Position- Aware GPSR (PA-GPSR) is another improvement over GPSR that utilizes two additional extension tables from the neighbor

table to include more parameters for increased routing accuracy through next-hop nodes. It outperforms the previous protocols when measured against network metrics such as Packet Loss Rate, End-to-End Delay, and Network Yield. This survey paper offers valuable insights into the network performance of GPSR, MM-GPSR, and PA-GPSR protocols and serves as a helpful guide for researchers and practitioners when selecting the most suitable routing protocol for their wireless sensor network applications, including VANETs.


[1] Zhang, Jiao, Xiping Hu, Zhaolong Ning, Edith C-H. Ngai, Li Zhou, Jibo Wei, Jun Cheng, and Bin Hu. "Energy-latency tradeoff for energy-aware offloading in mobile edge computing networks." IEEE Internet of Things Journal 5, no. 4 (2017): 2633-2645.

[2] Ranjan, Prabhakar, and Kamal Kant Ahirwar. "Comparative study of vanet and manet routing protocols." In Proc. of the International Conference on Advanced Computing and Communication Technologies (ACCT 2011), no. Acct, pp. 978-981. 2011.

[3] Cengiz, Korhan, and Tamer Dag. "Energy aware multi-hop routing protocol for WSNs." IEEE access 6 (2017): 2622-2633.

[4] Zhang, Xin Ming, Kai Heng Chen, Xu Lei Cao, and Dan Keun Sung. "A street-centric routing protocol based on microtopology in vehicular ad hoc networks." IEEE Transactions on Vehicular Technology 65, no. 7 (2015): 5680-5694..

[5] Hu, Lili, Zhizhong Ding, and Huijing Shi. "An improved GPSR routing strategy in VANET." In 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1-4. IEEE, 2012.

[6] Al-Saadi, Ahmed, Rossitza Setchi, Yulia Hicks, and Stuart M. Allen. "Routing protocol for heterogeneous wireless mesh networks." IEEE Transactions on Vehicular Technology 65, no. 12 (2016): 9773-9786.

[7] Zhang, Xinming, Xulei Cao, Long Yan, and Dan Keun Sung. "A street- centric opportunistic routing protocol based on link correlation for urban VANETs." IEEE Transactions on Mobile Computing 15, no. 7 (2015): 1586-1599.

[8] Perkins, Charles, Elizabeth Belding-Royer, and Samir Das. Ad hoc on- demand distance vector (AODV) routing. No. rfc3561. 2003.

[9] Ali, Awos Kh, Iain Phillips, and Huanjia Yang. "Evaluating VANET routing in urban environments." In 2016 39th International Conference on Telecommunications and Signal Processing (TSP), pp. 60-63. IEEE, 2016.

[10] Nebbou, Tawfiq, and Mohamed Lehsaini. "Greedy curvemetric-based routing protocol for VANETs." In 2018 International Conference on Selected Topics in Mobile and Wireless Networking (MoWNeT), pp. 1- 6. IEEE, 2018.

[11] Xing, Cui Fang, Lin Yang, and Qing Long Han. "Development of a New routing protocol based on GPSR for wireless sensor networks." In Applied Mechanics and Materials, vol. 644, pp. 2973-2977. Trans Tech Publications Ltd, 2014.

[12] Li, Ning, Jose-Fernan Martinez-Ortega, Vicente Hernandez Diaz, and Jose Antonio Sanchez Fernandez. "Probability prediction-based reliable and efficient opportunistic routing algorithm for VANETs." IEEE/ACM Transactions on Networking 26, no. 4 (2018): 1933-1947.

[13] Basagni, Stefano, Imrich Chlamtac, Violet R. Syrotuk, and Barry A. Woodward. "A distance routing effect algorithm for mobility (DREAM)." In Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, pp. 76-84. 1998.

[14] Suthaputchakun, Chakkaphong, and Zhili Sun. "Multihop broadcast protocol in intermittently connected vehicular networks." IEEE

Transactions on Aerospace and Electronic Systems 54, no. 2 (2017): 616-


[15] Dahmane, Sofiane, and Pascal Lorenz. "Weighted probabilistic next-hop forwarder decision-making in VANET environments." In 2016 IEEE global communications conference (GLOBECOM), pp. 1-6. IEEE, 2016.

[16] Karp, Brad, and Hsiang-Tsung Kung. "GPSR: Greedy perimeter stateless routing for wireless networks." In Proceedings of the 6th annual international conference on Mobile computing and networking, pp. 243- 254. 2000.

[17] Akabane, Ademar T., Richard W. Pazzi, Edmundo RM Madeira, and Leandro A. Villas. "Carro: A context-awareness protocol for data dissemination in urban and highway scenarios." In 2016 8th IEEE Latin- American Conference on Communications (LATINCOM), pp. 1-6. IEEE, 2016.

[18] Cui, Zhaoyuan, Demin Li, Guanglin Zhang, Chang Guo, and Yong Sheng. "The next-hop node selection based GPSR in vehicular Ad Hoc networks." Journal of Computer and Communications 4, no. 10 (2016): 44-56.

[19] Tonguz, Ozan K., Nawaporn Wisitpongphan, and Fan Bai. "DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks." IEEE Wireless Communications 17, no. 2 (2010): 47-57.

[20] Silva, Andrey, KM Niaz Reza, and Aurenice Oliveira. "An adaptive GPSR routing protocol for VANETs." In 2018 15th International Symposium on Wireless Communication Systems (ISWCS), pp. 1-6. IEEE, 2018.

[21] Alsaqour, Raed, Maha Abdelhaq, Rashid Saeed, Mueen Uddin, Ola Alsukour, Mohammed Al-Hubaishi, and Tariq Alahdal. "Dynamic packet beaconing for GPSR mobile ad hoc position-based routing protocol using fuzzy logic." Journal of Network and Computer Applications 47 (2015): 32-46.

[22] Khan, Ajmal, Jae-Choong Nam, and You-Ze Cho. "Beacon-less broadcast protocol for vehicular ad hoc networks." In 2013 19th Asia-Pacific Conference on Communications (APCC), pp. 153-154. IEEE, 2013.

[23] Ding, Qing, Bo Sun, and Xinming Zhang. "A traffic-light-aware routing protocol based on street connectivity for urban vehicular ad hoc networks." IEEE Communications Letters 20, no. 8 (2016): 1635-1638.

[24] Houssaini, Zineb Squalli, Imane Zaimi, Mohammed Oumsis, and Saïd El Alaoui Ouatik. "GPSR+ Predict: An enhancement for GPSR to make smart routing decision by anticipating movement of vehicles in VANETs." Adv. Sci. Technol. Eng. Syst. J 2, no. 3 (2017): 137-146.

[25] Zhou, Peng, Xiaoqiang Xiao, Wanbin Zhang, and Weixun Ning. "An improved GPSR routing algorithm based on vehicle trajectory mining." In Geo-Spatial Knowledge and Intelligence: 5th International Conference, GSKI 2017, Chiang Mai, Thailand, December 8-10, 2017, Revised Selected Papers, Part II 5, pp. 343-349. Springer Singapore, 2018.

[26] Zhang, Xin Ming, Kai Heng Chen, Xu Lei Cao, and Dan Keun Sung. "A street-centric routing protocol based on microtopology in vehicular ad hoc networks." IEEE Transactions on Vehicular Technology 65, no. 7 (2015): 5680-5694.

[27] Lochert, Christian, Martin Mauve, Holger Füßler, and Hannes Hartenstein. "Geographic routing in city scenarios." ACM SIGMOBILE mobile computing and communications review 9, no. 1 (2005): 69-72.

[28] Jiang, Ruobing, Yanmin Zhu, Tian He, Yunhuai Liu, and Lionel M. Ni. "Exploiting trajectory-based coverage for geocast in vehicular networks." IEEE Transactions on Parallel and Distributed Systems 25, no. 12 (2014): 3177-3189.

[29] Lee, Kevin C., Jérôme Härri, Uichin Lee, and Mario Gerla. "Enhanced perimeter routing for geographic forwarding protocols in urban vehicular scenarios." In 2007 ieee globecom workshops, pp. 1-10. IEEE, 2007.

[30] Krajzewicz, Daniel, Jakob Erdmann, Michael Behrisch, and Laura Bieker. "Recent development and applications of SUMO-Simulation of Urban MObility." International journal on advances in systems and measurements 5, no. 3&4 (2012).