International Journal of Interactive Mobile Technologies (iJIM) – eISSN: 1865-7923 – Vol. 14, No. 8, 2020 Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction Parameters for Vanets https://doi.org/10.3991/ijim.v14i08.12695 Amina Bengag (), Asmae Bengag, Mohamed Elboukhari University Mohamed 1st, Oujda, Morocco bengag.amina@gmail.com Abstract—In the recent years, the study and developments of networks that do not depend on any pre-existing infrastructure have been very popular. Vehicular Ad Hoc Networks (VANETs) belong to the class of these networks, in which each vehicle participates in routing by transmitting data for other nodes (vehicles). Due to the characteristics of VANET (e.g. high dynamic topology, different communication environment, frequently link breakage), the routing process still one of the most challenging aspects. Hence, many routing protocols have been suggested to overcome these challenges. Moreover, routing protocols based on the position of vehicles are the most popular and preferred class, thanks to its many advantages like the less control overhead and the scalability. However, this class suffer from some problems such as frequent link breakages caused by the high-mobility of vehicles, which cause a low PDR and throughput. In this investigation, we introduce a novel greedy forwarding strategy used to create a new routing protocol based on the position of vehicles, to reduce the link breakages and get a stable route that improves the PDR and throughput. The proposed Density and Velocity (Speed, Direction) Aware Greedy Perimeter Stateless Routing protocol (DVA-GPSR) is based on the suggested greedy forwarding technique that utilizes the density, the speed and the direction of vehicles for selecting the most convenient relaying node candidate. The results of simulation prove that DVA-GPSR protocol outperforms the classical GPSR in all studied metrics like PDR, throughput, and the ratio of routing overhead by changing the quantity of vehicles in urban and highway scenarios. Keywords—VANETs, Routing protocol, GPSR, DVA-GPSR, direction, speed, density. 1 Introduction Vehicular ad-hoc networks or VANETs in short, are a kind of a self-structured network that are designed directly by a set of intelligent vehicles. Each vehicle is equipped with a wireless transceiver and considered as a router. Some VANETs’ features such as high link breakage, high dynamic topology and the high speed of vehicles make the task of routing data packets in the networks a very big challenge for researchers. Therefore, many researchers focus on designing the routing protocols, which are suitable for all vehicular scenarios and deal with those characteristics. 196 http://www.i-jim.org https://doi.org/10.3991/ijim.v14i08.12695 mailto:bengag.amina@gmail.com Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … Routing protocols in VAENTs could be categorized into four classes [1], but those that are based on the position of vehicles are the number one thanks to their scalability and less control overhead [2]. In this paper, a novel routing protocol based on the location of vehicles is proposed that is based on four parameters; the density, the speed, the direction and the distance between destination and the relaying candidate node. These parameters are combined and used to improve the classical greedy forwarding strategy of GPSR routing protocol, this combination will create a new routing protocol called Density-Velocity-Aware- GPSR (DVA-GPSR) that will affect and enhance the performance of VANETs in urban and highway scenarios. As mentioned above, DVA- GPSR protocol selects the best relaying node by considering three parameters other than the classical one of GPSR. The first parameter helps us to calculate the angle between the direction of the relaying candidate and the direction of the target vehicle, this parameter is the angle direction. In order to increase the link lifetime between two vehicles, the second parameter that is the speed variation between the target node and the relaying candidate vehicle will be used to look for the smallest variation. The density or the neighbors’ number of the relaying candidate vehicle is the third parameter, which helps to determine the connectivity mode in each path (sparse, medium or dense). These parameters are used to improve the PDR, the throughput and the routing overhead in the network for the classical GPSR in the proposed scenarios. We have split this paper into six sections and each one describes a part of the paper profoundly. The paper is organized as follows. The related works are presented in section II. The original GPSR routing protocol, its benefits and drawbacks are provided in detail in section III; after that in section IV, we present and explain the strategy of the proposed DVA-GPSR. Section V presents the performance evaluation of the proposed DVA-GPSR based on simulation tools, and then the result analysis will be compared with the original GPSR. In section VI, we conclude this paper and present some of our future works. 2 Related Works In this section, we are going to give an overview of some enhancements applied to the classical GPSR for VANETs. We will present mainly the most recent and cited papers. In [3], Bouras et al. proposed a modified GPSR routing that is based on three parameters direction information, the speed of vehicles and the link quality in addition to the location information to select the next hop. Mainly, by using those parameters the future positions of only the source and the destination vehicles could be predicted. The benefits of GPSR-Modif is that it has a high value of PDR compared to the traditional GPSR, while keeping the E2ED (end-to-end delay) at the same level as GPSR. In [4] Silva et al. propose an adaptive GPSR (AGPSR) to enhance both the GF strategy and the PM technique of the classical GPSR. The GF technique is improved by using a special parameter called trust status TS. Moreover, AGPSR improved the PM technique by replacing it with a continuous greedy strategy. The proposed protocol proves high performance, but only for static nodes. In [5], Tu et al. provided a new iJIM ‒ Vol. 14, No. 8, 2020 197 Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … modified GPSR based on Moving Vector, (GPSR-MV) to enhance both the GF and the PM techniques, by taking the vehicles’ fast moving and forwarding efficiency into consideration and combining it with a simplified perimeter forwarding to avoid loop problem. The results show that GPSR-MV has a significant enhancement compared to the classical GPSR. GPSR-2P[6] Zaimi et al. developed GPSR-2P protocol, to resolve the congestion and saturation problems. Actually, authors replace the GF technique by introducing the multipath strategy only if the same node transmits two successive packets to the same destination; otherwise, the simple GF will be applied. The proposed enhancement of GPSR has significant results in case of PDR end E2ED. GPSR-2P is not efficient in case of more than two packets. In another paper, Yang et al. proposed All the above papers do not clearly adopting the enhancement of GPSR protocol to be implemented in a highway environment or in real map scenario. Moreover, the proposed enhancements used very complex techniques and weighted functions to select the next hop node. This paper is farther enhancing the GPSR approach by adopting both the highway and the urban environments by using a real map scenario. Moreover, the proposed technique is based on a simple and novel mechanism to select a next-hop node in VANETs. 3 The Strategy of the Traditional Gpsr Protocol GPSR [7] is the most popular position-based routing protocol that relies on geographic location information. In GPSR, two methods are utilized to transfer packets. The greedy forwarding (GF) in which the source select the closest neighbor to the target node as next hop to relay packet this method will be replaced by the perimeter forwarding (PF) in case of the failure as shown in Figure 1. The strong point of GPSR is that each vehicle could have the exact neighbor’s information as the geographic location, the speed and the direction movement. However, in the classical GPSR only the location information is used in the selection of the next hop process that could be inaccurate. Furthermore, the use of the greedy forwarding technique reduces the number of hop from source to destination. However, the transmission quality of the connection link is totally ignored. This strategy causes a significant amount of packet drops that decreases the PDR and throughput. Moreover, for each link failure a new route has to be reestablished so the forwarded data will be suspended until a new relay node is found. As a result, the routing overhead is dramatically increased. Fig. 1. The mechanism of selecting the next hop for GPSR 198 http://www.i-jim.org Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … 4 The Strategy of the Proposed DVA-GPSR Our proposed scheme is built on top of the traditional GPSR protocol. It adopts that all vehicles in VANET have a GPS able to giving the accurate vehicle’s information and they are equipped with an On-Board Unit (OBU) wireless transceiver/receiver for connecting each other. Hence, our main involvement is that we suggest a Novel greedy forwarding mechanism. In fact, a simple weighted function is used to select the most convenient relaying vehicle; the function consists of the angle direction, the speed variation and the density of the relaying candidate node, in addition to the classical parameter of GPSR that is the distance between the relaying candidate vehicle and the target vehicle. Then an improved GPSR protocol called DVA-GPSR is provided based on our proposed strategy. 4.1 The novel greedy forwarding mechanism As mentioned previously, the Source vehicle starts gather the mobility parameters: velocity and the position of all its neighbors. These parameters are implicated in the proposed function to calculate the link weight of all its neighbors. • At first, we calculate the angle direction 𝜑 (Figure 3) between each next hop candidates and the destination node as according to formula (1). 𝜑𝑖𝑑 = cos −1 ((𝑖𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑥∗𝑑𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑥)+(𝑖𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑦∗𝑑𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑦)) ((√(𝑖𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑥²+𝑑𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑥²)∗√(𝑖𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑦2+𝑑𝑉𝑒𝑙𝑜𝑐𝑖𝑡𝑦.𝑦²)) (1) Where iVelocity is the velocity of the next hop candidate and dVelocity is the destination velocity. The rational between the concepts of the angle direction is to maintain the connection between vehicles as long as possible by choosing the small value of all calculated 𝜑𝑖𝑑 . • Secondly, the distance between the sender and the destination node is calculated according to formula (2). 𝐷𝑖𝑑 = √(𝑦𝑖 − 𝑦𝑑 ) 2 + (𝑥𝑖 − 𝑥𝑑 ) 2 (2) Where (𝑥𝑖 , 𝑦𝑖 ) signifies the location of the neighbor node called i and (𝑥𝑑 , 𝑦𝑑 ) denotes the destination location. • The third parameter is used to calculate the speed variation between the target node and the next hop candidate node. 𝑆𝑖𝑑 = |𝑆𝑖 − 𝑆𝑑 | (3) Where Si is the speed of the neighbor node called i and Sd denotes the speed of the destination node. The previously mentioned equations will be used to formulate the weighted function (4). The link weight is calculated for every neighbor of the source node. If one of the iJIM ‒ Vol. 14, No. 8, 2020 199 Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … neighbors vehicles have almost the same speed and direction as the destination as well as the calculated distance is reducing and the density of the neighbor is high or medium then the link connection is more stable. Hence, we will select vehicle that has the lowest weight value as the next-hop relay node. The formula (4) presents the weighted function of the next-hop candidate node called i. 𝐿𝑊𝐹 = 𝛼 ∗ 𝐷𝑖𝑑 + 𝛽 ∗ ( 1 𝑑𝑒𝑛𝑠𝑖𝑡𝑦𝑖 ) + 𝜃 ∗ 𝑆𝑖𝑑 + 𝛾 ∗ 𝜑𝑖𝑑 (4) Where the densityi is the number of neighbors for the next hop candidate i, used to determine the connectivity mode in each path (sparse, medium or dense) thus reduce the sparse connectivity problem; and 𝛼 + 𝛽 + 𝜃 + 𝛾 = 1, to choose the most accurate values of those factors several simulation had done. The problem of void area that often arises by using the classical GPSR, which lead to the local maximum issue, will be resolved by taking into account the density parameter in the novel greedy forwarding strategy to select the most suitable next hop. Indeed, the vehicle that has the high density (high number of neighbors) will be chosen as a relaying node; hence, the problem of local maximum is reduced. Moreover, the Figure 3 clearly explains the strategy, the source vehicle will choose A as a relaying vehicle since it has three neighbors while B has no neighbors. Fig. 2. The density of node A and B Fig. 3. The angle direction φ 4.2 The algorithm of DVA-GPSR The algorithm of Density-Velocity-Aware based on GPSR (DVA-GPSR) is as follow: 200 http://www.i-jim.org Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … Algorithm 1. The partial DVA-GPSR Strategy Read the neighbor table of node S; For i=1 to the end of neighbor table Wi = Calculate_weight(i); If Wi < Wi-1 Set node i as the best next hop; End if End for If i.addr->isValid() Transmit data to node i; Else recoveryMode(); End if End algorithm In this algorithm, S represented the source node and i presented the neighbor nodes. The source node gets all necessary information then calculates the proposed link weight formula between it and all its neighbors and put it in Wi. From the previous explanations, the neighbor that has the smallest value of Wi will be chosen as the next hop, otherwise the classical recovery process will be applied. Fig. 4. Hay Alquds Oujda map from OSM to SUMO 5 Simulation and Comparison In this section, we evaluate the performance of the proposed DVA-GPSR in terms of routing overhead, packets delivery ratio (PDR) and average throughput with different vehicles’ densities and number of destinations. The simulations are performed under NS3 and SUMO as network simulator and traffic simulator respectively. For urban simulations, we extracted the map of a part of Oujda city with 1.7 km * 1.5 km from OpenStreetMap For highway simulations, we are based on a highway scenario of 300 m * 1.5 km with four lanes in two opposite directions. The other different settings of simulation scenario are presented in Tableau 1. For DVA-GPSR, to find the most efficient values of α, β, γ iJIM ‒ Vol. 14, No. 8, 2020 201 Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … and θ of the proposed function, we done several simulations with different values. The different results are generated and drawn by using Gnuplot software. Table 1. Tableau 1 Simulation parameters Parameters Measures Number of nodes 20,30, 40, 50, 60, 70, 80, 90 Source/destination selection Random Destination number 10 Vehicles speed Max: 20 m/s Simulation time 200 s Transport protocol UDP 5.1 Impact of the number of vehicles in the network Packet Delivery Ratio (PDR): Figure 5-a shows the results in a highway scenario, in terms of PDR by varying the number of vehicles. The PDR for DVA-GPSR protocol increases when the number of vehicles increases up to 68% while the PDR for GPSR decreases down to 59%. Figure 5 -b presents the same comparison for an urban scenario. We note that for DVA-GPSR protocol, PDR stays stable between 30% and 31% when the number of vehicles increase while the PDR of GPSR decreases down to 24%. Fig. 5. Effect Change on density Respect to PDR in urban and highway scenarios Average throughput: Figure 6 - a shows the results for both protocols in a highway scenario, in terms of the average throughput by varying the number of vehicles. The average throughput for both protocols increases when the number of vehicles increases. However, for DVA-GPSR protocol the throughput is increased up to 14 kbps while for GPSR it does not exceed 13 Kbps. Figure 6-b presents the same comparison for an urban scenario. We notes that for DVA-GPSR protocol, the throughput stays stable between 6 kbps and 6.5 kbps when the number of vehicles increases while for GPSR the throughput decreases down to 4.8kbps. 202 http://www.i-jim.org Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … Fig. 6. Effect Change on density Respect to throughput in urban and highway scenarios Routing control overhead: Figure 7 shows that the DVA-GPSR performs better than GPSR during the simulation in both scenarios. Figure 7-a presents the results for a highway scenario, by varying the number of vehicles when we have 10 randomly selected destinations. We note that for both protocols the overhead decreases when the number of vehicles increases but DVA-GPSR has the low values of overhead down to 27.6% compared to GPSR. Figure 7-b presents the same comparison for an urban scenario in terms of routing overhead. The overhead for DVA-GPSR is low than the overhead for the classical GPSR and does not exceed 28.5%. Fig. 7. Effect Change on density Respect to overhead in urban and highway scenarios 6 Conclusion In this paper, we have proposed a novel greedy forwarding mechanism based on Density, Speed and Direction parameters for VANETs then we applied the proposed strategy on the classical GPSR routing protocol to be more convenient for VANETs scenarios. To prove the high performance of DVA-GPSR, we are based on a real urban environment, which is a part of Oujda (Al-Quds street). Simulation results demonstrate that the proposed DVA-GPSR outperforms the classical GPSR routing protocol in terms of better control packet overhead, PDR, and average throughput. For future works, we aim to take into account more impacting parameters to the routing protocol to support urban environment structures, and other performance metrics that related to QoS can be simulated and tested with different traffic scenarios. iJIM ‒ Vol. 14, No. 8, 2020 203 Short Paper—A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction … 7 References [1] A. Bengag and M. El Boukhari, “Classification and comparison of routing protocols in VANETs,” in 2018 International Conference on Intelligent Systems and Computer Vision (ISCV), 2018, pp. 1–8. https://doi.org/10.1109/isacv.2018.8354025 [2] B. Amina and E. Mohamed, “Performance Evaluation of VANETs Routing Protocols Using SUMO and NS3,” in Colloquium in Information Science and Technology, CIST, 2018, vol. 2018-Octob, pp. 525–530. https://doi.org/10.1109/cist.2018.8596531 [3] C. Bouras, V. Kapoulas, N. Stathopoulos, and A. Gkamas, “Mechanisms for Enhancing the Performance of Routing Protocols in VANETs,” 2016. https://doi.org/10.1145/2989293. 2989294 [4] A. Silva, K. M. N. Reza, and A. Oliveira, “An Adaptive GPSR Routing Protocol for VANETs,” Proc. Int. Symp. Wirel. Commun. Syst., vol. 2018-Augus, pp. 1–6, 2018https://doi.org/10.1109/iswcs.2018.8491075 [5] H. Tu, L. Peng, H. Li, and F. Liu, “GSPR-MV: A routing protocol based on motion vector for VANET,” in International Conference on Signal Processing Proceedings, ICSP, 2014.https://doi.org/10.1109/icosp.2014.7015415 [6] I. Zaimi, Z. S. Houssaini, A. Boushaba, and M. Oumsis, “An improved GPSR protocol to enhance the video quality transmission over vehicular ad hoc networks,” Proc. - 2016 Int. Conf. Wirel. Networks Mob. Commun. WINCOM 2016 Green Commun. Netw., no. Urac 29, pp. 146–153, 2016. https://doi.org/10.1109/wincom.2016.7777206 [7] B. Karp and H. Kung, “GPSR: Greedy Perimeter Stateless Routing for wireless networks,” ACM MobiCom, no. MobiCom, pp. 243–254, 2000. https://doi.org/10.21236/ada440078 8 Authors Amina Bengag Graduated from ENSAO with a degree of state engineer Telecommunication and Networks in 2016. She is currently a Ph.D. candidate at MATSI-Laboratory/ Mohammed 1st University of Oujda. Her research focus on VANET, Routing protocols, WBAN, Security and IDS. Email: bengag.amina@gmail.com Asmae Bengag is currently a Ph.D. candidate at MATSI-Laboratory/ Mohammed 1st University of Oujda. Her research focus on WBAN, Security, IDS and routing protocols. Mohamed Elboukhari is a Ph.D., Professor, MATSI-Laboratory, ESTO, University Med 1st, Oujda, Morocco. His research focus on Security, Mac layer and routing protocols. Article submitted 2019-12-12. Resubmitted 2020-02-25. Final acceptance 2020-02-25. Final version published as submitted by the authors. 204 http://www.i-jim.org https://doi.org/10.1109/isacv.2018.8354025 https://doi.org/10.1109/cist.2018.8596531 https://doi.org/10.1145/2989293.2989294 https://doi.org/10.1145/2989293.2989294 https://doi.org/10.1109/iswcs.2018.8491075 https://doi.org/10.1109/icosp.2014.7015415 https://doi.org/10.1109/wincom.2016.7777206 https://doi.org/10.21236/ada440078 mailto:bengag.amina@gmail.com