# An Improved Greedy Forwarding Routing Protocol for Cooperative VANETs

Huaqing Wen, Kyung-Hyune Rhee

► To cite this version:

Huaqing Wen, Kyung-Hyune Rhee. An Improved Greedy Forwarding Routing Protocol for Cooperative VANETs. 1st International Conference on Information and Communication Technology (ICT-EurAsia), Mar 2013, Yogyakarta, Indonesia. pp.502-506, 10.1007/978-3-642-36818-9_57. hal-01480257

HAL Id: hal-01480257

https://inria.hal.science/hal-01480257

Submitted on 1 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Improved Greedy Forwarding Routing Protocol for Cooperative VANETS*

Huaqing Wen and Kyung-Hyune Rhee**

Department of IT Convergence and Application Engineering,
Pukyong National University.
599-1, Daeyeon3-Dong, Nam-Gu, Busan 608-737, Republic of Korea
{wenhuaqing, khrhee}@pknu.ac.kr

**Abstract.** Most researches in the VANETS domain concentrate on the development of communication routing protocols. However, it is not effective to apply the existing routing protocols of MANETs to those of VANETS. In this paper, we propose a new greedy forward routing protocol which leverages real time traffic flow information to create a routing policy. Based on this routing policy, the proposed protocol alleviates the influence of high dynamic topology and decreases the average delivery delay on VANETS.

## 1 Introduction

Several routing protocols have been presented by many researchers for vehicular ad hoc networks (VANETS) [1, 7]. One of the best known position-based routing is GPSR [3]. GPSR works better in open space scenarios such as highways with evenly distributed nodes. In the condition of cities, GPSR suffers from many problems, because it does not consider some obstacles such as the movement of high-speed vehicles. In GPSR, when a node receives a Hello Message from its neighbors, it sets the Hello lifetime for each of its neighbors to prepare the next reception of this Hello Message. If it does not receive the Hello Message from its neighbor when the Hello lifetime expires, it decides that the neighbor has gone out of range. Due to the high mobility, a node may not receive updated location information from its neighbor since the neighbor has gone out of range [4]. Hence, when a node has data to forward, it may make a wrong decision which, in turn, leads to the packet loss. In order to provide a reasonable forwarding decision for nodes, we propose an improved greedy forwarding protocol based on the road traffic to alleviate the impact of vehicle mobility and enhance the stability of the routing link. We adopt both the fluid traffic model (FTM) [5] and intelligent driver model (IDM) [6]. FTM describes the speed as a monotonically decreasing function of the vehicle density and the speed of vehicle is calculated by means of the following equation:

* This research was supported by the National Research Foundation of Korea Grant funded by the Korean Government (NRF-2011-013-D00121).

** Corresponding author
$$S = \max\{S_{min}, S_{max}(1 - k/k_{jam})\} \qquad (1)$$

where S is the output speed, $S_{min}$ and $S_{max}$ are the minimum and maximum speed, respectively. $k_{jam}$ is the vehicular density for which a traffic jam is detected. This last parameter is given by $k = n/l$, where n is the number of cars on the road and l is the length of the road segment itself. According to the equation (1), we can estimate the current flow speed S. Before we explain the protocol, in our system model, we assume that: (1) Each vehicle is equipped with Onboard Unit (OBU) and GPS device, which enable themselves to acquire their own positions and movement directions. (2) The source node already knows the current position of the destination node before transmission based on the location service. (3) All nodes are aware of the street-level information of the area where they are currently positioned.

# 2 Proposed Protocol

## 2.1 Neighbors Classification Phase

Each vehicle exchanges the information of the neighboring vehicles and updates the neighboring list table by Hello Messages. In order to improve the stability of the route, unlike the traditional neighbors selection that is based on the distance radius regardless of driving directions, in our approach, vehicles only with the same moving direction in both each road section and transmission range are set as one-hop neighbors or simply “Geographic Neighbors”. In order to identify geographic neighbors for each vehicle, we insert vehicle’s current speed and driving direction in Hello Message.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Group Classification of Neighbors.</figcaption></figure>

Once each vehicle gets its geographic neighbor list, the node needs to calculate the current distance between geographic neighbors and itself. We define two preset parameters $D_n$ and $D_m$ to decide which group vehicles will belong to. If the distance D between vehicle and its neighbor is larger than the preset threshold $D_m$ ($D_m \le D$), this node will be classified into Far Group as shown in
<table><caption>**Table 1.** Example of Neighbor List Table.</caption><thead><tr><th rowspan="2">Node ID</th><th rowspan="2">Position x</th><th rowspan="2">Position y</th><th colspan="3">Neighbor List</th></tr><tr><th>Current Speed</th><th>Group Tag</th><th>Time Stamp</th></tr></thead><tbody><tr><td>1</td><td>1234.56</td><td>4567.89</td><td>12m/s</td><td>N</td><td>3.0</td></tr><tr><td>2</td><td>1250.89</td><td>4564.12</td><td>9m/s</td><td>F</td><td>3.5</td></tr></tbody></table>

Figure 1. If $D_n \le D < D_m$, neighbors in this area will be classified into Middle Group. If $D \le D_n$, neighbors in this area will be classified into Near Group. After calculating this, vehicle attaches a group tag with each neighbor in the group list table. Every vehicle maintains a neighbor list table as shown in Table 1 and updates periodically.

## 2.2 Forwarding Policy and Packet Forwarding Phase

In equation (1), the number of node $k$ is determined by information gathered from one-hop Geographic Neighbors. Because nodes are aware of the street-level information of the area where they are currently positioned, the length $l$ of street can be measured. $k_{jam}$ is available via a commercial navigation service, similar to the one currently provided by Garmin Traffic [8]. With the density information of the path, the traffic flow speed can be roughly estimated based on equation (1). We set a routing policy to determine which group will be chosen as the next hop candidate first. The priority level of each group is decided by the current speed as shown in Table 2.

<table><caption>**Table 2.** Routing Policy.</caption><thead><tr><th>Output Speed</th><th colspan="3">Priority Level (from high to low)</th></tr></thead><tbody><tr><td>Slow</td><td>F</td><td>M</td><td>N</td></tr><tr><td>Medium</td><td>M</td><td>F</td><td>N</td></tr><tr><td>Fast</td><td>N</td><td>M</td><td>F</td></tr></tbody></table>

If the current flow speed $S$ around the node is bigger than a preset $S_{fast}$, we will assign the Near Group as the first priority candidate and the Far Group as the last priority candidate. When the opposite happens, $S < S_{slow}$, the Far Group will be the first priority by reverse. For medium scenarios, $S_{slow} \le S < S_{fast}$, we set the priority level from high to low as following: Middle Group, Far Group and Near Group. In the packet forwarding phase, the difference between the proposed greedy forwarding and GPSR is that we use a routing policy to choose the next hop so that the stability can be improved. When node $S$ needs to send the first data packet of the event message, it will choose one which is the closest to the destination from the first priority group as the next hop forwarding packet. If the first priority group of the present node is empty, the node will check the second priority group. This process is repeated until all groups have been
checked. In the worst case, when node reaches a local maximum, the right hand rule to forward packets should be used.

<table><caption>**Table 3.** Analysis Parameters.</caption><thead><tr><th>Parameters</th><th>Measures</th></tr></thead><tbody><tr><td>Road</td><td>Length: 1000m<br>Width: 6m</td></tr><tr><td>Transmission Range</td><td>250m</td></tr><tr><td>Number of Nodes</td><td>30</td></tr><tr><td>Number of Nodes in Traffic Jam</td><td>300</td></tr><tr><td>Node Speed</td><td>30km/h - 120km/h</td></tr><tr><td>Hello Message Interval</td><td>2.5s</td></tr><tr><td>Packet Traffic</td><td>1 packet/0.5s</td></tr><tr><td>S<sub>slow</sub></td><td>45km/h</td></tr><tr><td>S<sub>fast</sub></td><td>85km/h</td></tr></tbody></table>

## 3 Analysis

Based on simulation result in [3], the routing overhead of GPSR is determined by Hello Message period. If we set long Hello Message exchange period, routing overhead will be decreased. However, with a long Hello Message interval packet, delivery ratio will be reduced because a next hop may go out of the communication range during a data packet transmission. The improved greedy forwarding routing protocol can compromise these two metrics when we set long exchange period. By using Matlab, we assume 30 nodes moving same direction are randomly distributed in one segment. Each node starts moving with a velocity ranges from 30km/h to 120km/h randomly and knows its current position as shown in Table 3. We compared 10 scenarios between GPSR and the proposed protocol performances. Figure 2 shows the data delivery ratio obtained for GPSR and the proposed protocol during one Hello Message interval. It is clearly shown that the proposed protocol guarantees a better delivery ratio compared to GPSR. Although the proposed protocol increases the hop from the source to destination, it avoids the case when a next hop goes out of the communication range during a data packet transmission and finally decreases the data loss and the resulting delay time, which can increase the routing performances.

## 4 Conclusion

In this paper, we proposed an improved greedy forwarding routing protocol. To design an efficient routing protocol for dynamic environment, the proposed protocol leverages real time vehicular traffic information to classify vehicle's neighbors and create a routing policy. Based on this routing policy, vehicles can
<figure><img src="image_3.png" /><figcaption>Fig. 2. Data Delivery Ratio.</figcaption></figure>

select a reasonable node as the next hop. When density of traffic flow is low which indicates the speed in an area is high, and the topology changes frequently, a vehicle should forward packets to the neighbor which is near to avoid the case when a next hop goes out of the communication range during a data packet transmission. It enhances the stability of the routing link and decreases the average delay, which finally alleviates the influence of high dynamic of topology on VANETS.

References

1. I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks, pp. 393-422, 2002.

2. A. Boukerche, H. Oliveira, E. Nakamura, A. Loureiro, "Vehicular ad hoc networks: A new challenge for localization-based systems," Computer Communications, Vol. 31, no. 12, pp. 2838-2849, 2008.

3. B. Karp, and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," in Proc. of MOBICOM'00, pp. 243-254, Aug. 2000.

4. S-A. Rao1,M. Boussedjra, J. Mouzna2, "GPSR-L: Greedy Perimeter Stateless Routing with Lifetime for VANETS,"
In Proc. of 8th International Conference on ITS, pp 299-304 Oct. 2008.

5. I. Seskar, S. Maire, J. Holtzman, J. Wasserman, "Rate of Location Area Updates in Cellular Systems," in Proc. of IEEE Vehicular Technology Conference, Vol.2, pp. 694-697, May 1992.

6. M. Treiber, D. Helbing, "Congested traffic states in empirical observations and microscopic simulation," in Proc. of Statistical Mechanics, Physical Review E62,pp. 1805-1824, 2000.

7. J. Zhao, G. Cao, "VADD: Vehicle-Assisted Data Delivery in vehicular ad hoc networks,"
in Proc. of the 25th INFOCOM, pp. 1-12, 2006,

8. Garmin Ltd., "Garmin Traffic," http://www8.garmin.com/traffic.