Improvement of GPSR Protocol in Vehicular Ad Hoc Network
SPECIAL SECTION ON SECURITY AND PRIVACY FOR VEHICULAR NETWORKS
Received June 7, 2018, accepted June 30, 2018, date of publication July 12, 2018, date of current version August 7, 2018.
Digital Object Identifier 10.1109/ACCESS.2018.2853112
Improvement of GPSR Protocol in
Vehicular Ad Hoc Network
XIAOPING YANG1, MENGJIE LI 1, ZHIHONG QIAN1, AND TE DI2
1College of Communication Engineering, Jilin University, Changchun 130012, China
2Chang Guang Satellite Technology Co., Ltd., Changchun 130000, China
Corresponding author: Xiaoping Yang ( .cn)
This work was supported in part by the Jilin Province-College Collaboration Funding under Grant SXGJQY2017-9, in part by the
National Nature Science Foundation of China under Grant 61403159, and in part by the Jilin Province Science and
Technology Innovation Center under Project 20160623014TC.
ABSTRACT In a vehicular ad hoc network (VANET), vehicles always move in high-speed which may
cause the network topology changes frequently. This is challenging for routing protocols of VANET.
Greedy Perimeter Stateless Routing (GPSR) is a representative routing protocol of VANET. However, when
constructs routing path, GPSR selects the next hop node which is very easily out of the communication
range in greedy forwarding, and builds the path with redundancy in perimeter forwarding. To solve the
above-mentioned problems, we proposed Maxduration-Minangle GPSR (MM-GPSR) routing protocol in
this paper. In greedy forwarding ofMM-GPSR, by defining cumulative communication duration to represent
the stability of neighbor nodes, the neighbor node with the maximum cumulative communication duration
will be selected as the next hop node. In perimeter forwarding of MM-GPSR when greedy forwarding fails,
the concept of minimum angle is introduced as the criterion of the optimal next hop node. By taking the
position of neighbor nodes into account and calculating angles formed between neighbors and the destination
node, the neighbor node with minimum angle will be selected as the next hop node. By using NS-2 and
VanetMobiSim, simulations demonstrate that compared with GPSR, MM-GPSR has obvious improvements
in reducing the packet loss rate, decreasing the end-to-end delay and increasing the throughput, and is more
suitable for VANET.
INDEX TERMS Vehicular ad hoc network, routing protocols, GPSR, greedy forwarding, perimeter
forwarding, NS-2.
I. INTRODUCTION
Vehicular Ad hoc Network (VANET) is an application of
mobile ad hoc network in traffic. Compared with other
mobile ad hoc network, just as cellular networks that needs
to focus on reducing the consumption of both energy and
resource of mobile devices [1], VANET has the advantages,
such as sufficient node energy, strong computing and storage
capability, equipped with navigation system and movement
predictability, hence VANET is becoming more and more
popular in the intelligent transportation system [2]. The vehi-
cle nodes in the network move rapidly, with the network
topology changing frequently. When a node forwards pack-
ets, it often happens that the routing path is broken or recon-
structed, which seriously affects the overall communication
performance of VANET. Thus, the research on VANET is
crucial [3]. There have already been some achievementsmade
in vehicular networks. Some solutions and systems were pro-
posed and designed to resolve the defects of VANET [4], [5].
A CQS system in SIoVs was designed by focusing on
a reliability assurance and service quality promotion [6].
A SAGA framework was proposed to provide high link con-
nectivity and capacity [7].
Routing protocol is important for mobile networks. There
have already been many studies on routing protocol. Some
protocols were designed to provide higher QoS and save
more energy [8]–[11]. The representative routing proto-
col is Ad hoc On-demand Distance Vector (AODV) proto-
col which includes route discovery and route maintenance.
The source node broadcasts a routing request packet to
the destination node in the network. After receiving the
routing request packet, the intermediate node will forward
the packet until the destination node receives the routing
VOLUME 6, 2018
2169-3536
2018 IEEE. Translations and content mining are permitted for academic research only.
Personal use is also permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
39515
https://orcid.org/0000-0003-4078-0630
lenovo
高亮
在车辆自组织网络（VANET）中，车辆总是高速移动，这可能导致网络拓扑结构的频繁变化。这对VANET的路由协议来说是一个挑战。贪婪周边无状态路由（GPSR）是VANET的一种典型路由协议。然而
在构造路由路径时，GPSR选择下一跳节点，这很容易脱离通信
贪婪转发中的范围，并在周界转发中构建具有冗余的路径。为了解决上述问题，我们在年提出了Maxduration-Minangle GPSR（MM-GPSR）路由协议
这篇论文。在MM-GPSR贪婪转发中，通过定义累积通信持续时间来表示邻居节点的稳定性，得到具有最大累积通信持续时间的邻居节点
将被选为下一个跃点节点。在MM-GPSR的周长转发中，当贪婪转发失败时，引入最小角度的概念作为最佳下一跳节点的准则。通过考虑相邻节点的位置，计算相邻节点与相邻节点之间形成的角度
目的节点，选择角度最小的邻居节点作为下一跳节点。通过使用NS-2和VanetMobiSim，仿真结果表明，与GPSR相比，MM-GPSR在降低丢包率、降低端到端延迟和增加粗糙度方面有明显的改进，更适合于VANET。
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
request, while the repeated request packets will be dis-
carded. At the same time, AODV routing protocol also adds
sequence numbers to request packet in order to prevent
routing loops. However in the process of routing discov-
ery, AODV broadcasts the routing request packet by means
of flooding, and a lot of sending packets were eventually
abandoned, the excessive management load leads to a large
amount of energy being wasted. The network overload will
be augmented with the scale of the magnified network.
So AODV protocol is not suitable for large-scale vehicle
networks [12], [13].
DSDV (Destination-Sequenced Distance-Vector Routing)
is an active routing protocol [14]. For DSDV, each node saves
routing information to all other nodes and updates informa-
tion periodically. The mobile node monitors the movement
of other nodes in the network. When the network topology
changes, the nodes will periodically broadcast routing pack-
ets and send routing information to all other nodes in the
network, whether the communication is need or not. In this
way, each node can get the latest topology information. Since
all nodes need to maintain routing paths to the other nodes,
of which some are unnecessary, this protocol will consume a
great amount of resources and energy to maintain the normal
function. DSDV has some advantages, for example, each
node finds the built path directly in its own routing table
during packets transmission, so that network delay becomes
small.
ZRP (Zone Routing Protocol) is a hybrid routing
protocol [15]. This routing protocol contains two situations:
within one zone and across multiple zones. Within one zone,
it uses proactive routing mechanism to find a path and the
protocol is called intra-zone protocol. Across multiple zones,
the reactive routing mechanism, called inter-zone protocol,
is used to find a path. ZRP has a disadvantage: ZRP requires
excessive routing overhead in a large-scale vehicular Ad hoc
network.
DREAM (Distance Routing Effect Algorithm of Mobility)
is a flooding protocol [16]. Before forwarding data packets,
the source node obtains the position information of the desti-
nation node firstly; and then determines the forwarding direc-
tion and forwarding zone of packets based on the positions of
the source node and the destination node; finally, the source
node sends packets to the forwarding zone. Each intermediate
node repeats the same procedure until the destination node
receives packets successfully. DREAM can ensure packets
forwarding in the direction of the destination node, which
reduces the number of unnecessary forwarding and improves
the network performance. DREAMneeds timely and accurate
position information of nodes. When the speed of nodes is
low and the nodes are close to each other, resulting in low
the update frequency of the routing table and few requests of
position information, so the network load is low. The routing
protocol performs well under this circumstance. However,
in vehicular Ad hoc network with large number of high
speed nodes, the update frequencies of both node positions
and routing tables are fast, which forms large number of
position information requests, and further leads to network
failures [17].
Routing protocols for VANET are new extensions of the
protocols for mobile networks. GPSR is a representative
geographic routing protocol of wireless networks. For GPSR,
nodes obtain the position information through the position-
ing system and store the neighbor information in neigh-
bor lists. The forwarding methods of the GPSR protocol
include greedy forwarding and perimeter forwarding. The
node broadcasts its own position information to its neighbor
nodes periodically by GPSR. After receiving the information
of the new neighbor, the node will update its neighbor list.
In the process of transmitting packets, the node gets the
position of the destination node through position service,
and then builds a path by greedy forwarding and perimeter
forwarding. GPSR does not need to maintain the routing table
when transmitting packets, it has a good performance even
if topology changes frequently, hence GPSR is more suitable
for VANET [18], [19]. However, in a network which topology
changes frequently due of nodes with high speed, for GPSR,
the communication with neighbor nodes becomes extremely
unstable, the next hop node selected by greedy forwarding
may have moved out of the communication range before it
receives the packets. Perimeter forwarding will be used to
forward packets after greedy forwarding fails, quite possibly
with redundancy in building routing paths [20], [21].
To overcome the drawbacks of GPSR mentioned above,
there have been a lot of related improvements. In [22], by tak-
ing account of the influence of the neighbor number, data
deliver rate, driving direction and positions between two-
hops, the authors proposed the OinO strategy to make sure
the worst result acceptable. In [23], the improvement was
made on GPSR by estimating the future position of the par-
ticipating nodes and using the estimated information to select
adequate next hop node. In [24], based on street connectiv-
ity, a street-centric protocol was proposed to improve the
delivery ratio and reduce end-to-end delay for urban VANET.
In [25], by analyzing the endside-to-endside routing perfor-
mance, SRPMT protocol along the streets for VANET was
proposed to achieve higher data delivery rate and shorter
average end-to-end delay. In [26], based on predictions for
inter-vehicle encounters, the message forwarding metric is
designed, to characterize the capability of a vehicle to suc-
cessfully geocast the message. In [27], based on the mobility
dynamics of the nodes and the forwarding patterns, the Adap-
tive Position Update strategy was proposed to improve the
routing performance.
Aiming to solve the problems of GPSR on the instability of
communication due of the changeable positions of nodes in
greedy forwarding and the redundancy when building paths
in perimeter forwarding, MM-GPSR is proposed based on
maximum cumulative communication duration andminimum
angle in this paper.
The remainder of this paper is organized as fol-
lows. Section II describes the problem of GPSR proto-
col. Section III provides the improved methods of GPSR.
39516 VOLUME 6, 2018
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
Section IV presents the simulation and the experimental
results analysis. Finally, Section V draws the conclusion.
II. PROBLEM DESCRIPTION
The forwarding methods of the GPSR protocol include
greedy forwarding and perimeter forwarding, and GPSR need
not store or maintain the routing tables. Before transmitting
data packets by GPSR, each node needs to obtain the posi-
tion information of both the neighbor node and the desti-
nation node by beacon broadcasting in advance, and then
relies on the received position information to transmit data
packets. Greedy forwarding is the core of the GPSR routing
protocol. After the greedy forwarding fails, GPSR will use
perimeter forwarding to forward data packets. The detailed
process of GPSR: the source node invokes the greedy for-
warding to find the nearest node to the destination node in
the neighbor list and selects the nearest node as the next hop
node to forward packets, after receiving packets, the next hop
node repeatedly invokes the greedy forwarding to forward
the packet and go on; when routing holes appear in greedy
forwarding, this mid node will forward packets by perimeter
forwarding. Greedy forwarding or perimeter forwarding is
invoked until the data packets are sent to the destination node.
A. THE PROBLEM OF GREEDY FORWARDING
In greedy forwarding, GPSR always selects the node near-
est to the destination node in the neighbor list as the next
hop. However, the selected next hop node is usually at the
edge of the communication range. The position of neighbor
node is very easy to change because nodes move quickly,
which means that the next hop node is very likely to move
out of communication range of the current node before the
packet have been received by the next hop node. As shown
in Fig. 1, the current node is S, the destination node is D,
the node B is nearest node to D in the neighbor node of S.
The corresponding neighbor nodes after nodes moves: the
positions of S’, A’, B’ are after the movement; the positions
of S, A, B are before movement. In greedy forwarding,
S will select B as the next hop to forwarding packets. How-
ever, B has moved to the position of B’ which is out of the
communication range of S, making node B fail to receive
packets. In detail, after the neighbor list of S is updated,
B is no longer the neighbor node of S, but S has selected B as
the next hop to forward packets, which leads to greedy for-
warding failure and communication link broken, and finally
resulting in packet retransmission or loss, which degrades the
overall performance of the network.
B. THE PROBLEM OF PERIMETER FORWARDING
GPSR will turn into perimeter forwarding after greedy for-
warding fails. Perimeter forwarding uses the right-hand
rule to forward data packets, but there is redundancy in
building routing paths. As the solid lines shown in Fig. 2,
in the communication range of S, there is no neigh-
bor node that has shorter distance to D than S. So the
routing path is built as S→A→B→C→E→K→G by
FIGURE 1. Unstable next hop node in greedy forwarding.
FIGURE 2. Redundant path and the best path in perimeter forwarding.
perimeter forwarding. G→I→D is built by greedy forward-
ing, because the distance from G to D is shorter than the
distance from S to D.When the source node S selects the next
hop node from the neighbor nodes, as indicated by the dashed
lines in Fig. 2, it can be seen that K is preferable to be selected
as the next hop, and the path will be S→K→G→I→D.
By comparing the two links, it is found that the path redun-
dancy exists in perimeter forwarding.
III. IMPROVED METHOD OF GPSR PROTOCOL
Aiming at solving the problems of neighbor relationship
instability in greedy forwarding and path redundancy in
perimeter forwarding in GPSR protocol, this paper proposes
the following improvements.
A. THE IMPROVEMENT FOR THE INSTABILITY OF NEXT
HOP IN GREEDY FORWARDING
The improved greedy forwarding deals with the instability of
neighbor relationship by adding two parameters: the cumu-
lative communication duration, named T , and the allowed
communication area, named Q. As shown in Fig. 3, the small
circle, such as S, A, B, K, C, represents the vehicle node.
When S tries to send packets to D, S will find the nearest
vehicle node to destination node from the neighbor vehi-
cle nodes. The nearest node to the destination Fig. 3 is B.
The maximum allowed hop distance is calculated based on
the distance between B to D. By comparing the cumulative
communication duration and evaluating the communication
stability between all the neighbor vehicle nodes of S, the most
stable next hop node is selected.
In Fig 3, S sends packets to D, the coordinates of S
and D are set to (xS , yS ) and (xD, yD) respectively. When
transmitting packets in greedy forwarding, the source
VOLUME 6, 2018 39517
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
FIGURE 3. Improved greedy forwarding scene graph.
node S finds the nearest node to D in its own neighbor list,
and the nearest node is B, with the coordinates of (xB, yB). The
distance dBD from B to D and dSB from B to S are calculated
respectively in (1), (2). The allowed communication distance
dmax is calculated by (3). The overlapping area of two circles
that one with D as center and dmax as radius, and the other
with S as center and maximum communication distance as
radius, is defined as the allowed communication area, and
this allowed communication area is named asQ. Each node in
Q is not only close to the destination node D but also within
the communication range of node S, and is suitable to be
selected as the next hop node of S.
dBD =
√
(xD − xB)
2
+ (yD − yB)
2 (1)
dSB =
√
(xS − xB)
2
+ (yS − yB)
2 (2)
dmax = dBD + λ× dSB (3)
In (3), λ ∈ [0, 1]. Apparently, λ affects the size of Q.
When λ is too large, Q will become larger, then the node
near S is more easily selected as the next hop in Q, but
the number of hops for this node to D may increase. When
λ is too small, Q will become smaller, then the node near
D is more easily selected as the next hop in Q, the distance
from S to this node may go longer, and the link stability may
become worse, causing the packet loss increase. By conduct-
ing several experiments, it has a decent performance in greedy
forwarding when λ is set to 0.3.
In Fig. 3, Q contains A, B, K, and then the cumulative
communication duration between three neighbor nodes and
S, is calculated by (4).
Ti = Ti−1 + ti − ti−1 (4)
In (4), Ti is current cumulative communication duration,
Ti−1 is last cumulative communication duration, ti is the
current time of receiving hello, ti−1 is the time of receiving
the last hello. Here the initial conditions are set firstly, T1 = 0
and t1 is the moment of receiving the first Hello packet.
By comparing Ti of A, B, K, the node with maximum Ti is
steady to S and close to the destination, and will be selected
as the next hop node of S. By following this method when
forwarding packets, the probability of communication link
broken is greatly reduced.
B. THE IMPROVEMENT FOR PATH REDUNDANCY IN
PERIMETER FORWARDING
In order to resolve the path redundancy, the improved perime-
ter forwarding takes the positional relationship between
the neighbor nodes and the destination node into account.
As shown in Fig. 4, the neighbor nodes of S include A, B,
and K. S will selects a next hop by using the right hand
rule when greedy forwarding fails, which results in path
redundancy. So our purpose is to find a next hop node which
does not deviate from D. Draw a ray from S to D, and then
draw rays from S to any neighbor node of S, each ray through
neighbor node will form an angle with the ray through D, and
this angle is named as θ . By analyzing and comparing the
corresponding θ of all neighbor nodes of S, an optimal next
hop of S will be selected.
FIGURE 4. Improved perimeter forwarding scene graph.
In Fig. 4, the line that connects S and D divides the whole
plane into two parts, the left half-plane and right half-plane.
When forwarding packets in two part of the whole plane,
the neighbor node with the smaller θ can build a shorter rout-
ing path with less redundancy. Neighbor nodes are randomly
distributed on both the left half-plane and the right half-
plane. The coordinate plane is introduced to analyze neighbor
nodes. Based on the coordinates of each neighbor node, θ is
calculated.
As shown in Fig. 5, when the neighbor node N is in the
first quadrant, such as N1 with the coordinates of (xN1, yN1).
Determined by SD and SN1 as the solid line indicating
in Fig. 5, the θright is calculated by using (5), (6).
cos θright =
yN1 − yS√
(xN1 − xS)
2
+ (yN1 − yS)
2
(5)
θright = arccos
(
cos θright
)
(6)
When the neighbor node N is in the second quad-
rant, such as N2 with the coordinates of (xN2, yN2)
shown in Fig. 5. Determined by SD and SN2 as the
dashed line indicating in Fig. 5, the θleft is calculated by
using (7), (8).
cos θleft =
yN2 − yS√
(xS − xN2)
2
+ (yN2 − yS)
2
(7)
θleft = arccos
(
cos θleft
)
(8)
39518 VOLUME 6, 2018
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
FIGURE 5. Neighbor node N is in the first or second quadrant.
FIGURE 6. Neighbor node N is in the third or fourth quadrant.
As shown in Fig. 6, when the neighbor node N is in the
third quadrant, such as N3 with the coordinates of (xN3, yN3).
Determined by SD and SN3 as the dashed line indicating
in Fig. 6, the θleft is calculated by using (9), (10).
cosαleft =
yS − yN3√
(xS − xN3)
2
+ (yS − yN3)
2
(9)
θleft = π − arccos
(
cosαleft
)
(10)
When the neighbor nodeN is in the fourth quadrant, such as
N4 with the coordinates of (xN4, yN4) shown in Fig. 6. Deter-
mined by SD and SN4 as the solid line indicating in Fig. 6,
the θright is calculated by using (11), (12).
cosαright =
yS − yN4√
(xN4 − xS)
2
+ (yS − yN4)
2
(11)
θright = π − arccos
(
cosαright
)
(12)
The minimum θ is determined by comparing all the neigh-
bor nodes of S using (13).{
θ = θleft , when θleft ≤ θright .
θ = θright , when θleft > θright .
(13)
In the improved perimeter forwarding, the neighbor node
with minimum angle θ will be selected as the next hop node
for S, which eliminates the path redundancy to a great extent.
C. THE IMPROVED MM-GPSR PROTOCOL
As described in sections III.A and III.B, by improving both
greedy forwarding and perimeter forwarding of GPSR, this
paper proposes Maxduration-Minangle GPSR (MM-GPSR)
protocol. In greedy forwarding, the current node determines
the allowed communication area firstly, and then calculates
and compares the cumulative communication durations of
neighbor nodes and finally selects the neighbor with max-
imum duration as the next hop. In perimeter forwarding
when greedy forwarding fails, the current node calculates and
compares the angles of corresponding neighbor nodes at first,
and then selects the neighbor node with minimum angle as
the next hop to forward packets. Algorithm 1 describes the
procedure of MM-GPSR.
D. TIME COMPLEXITY ANALYSIS
As described in Algorithm 1, we assume that the number of
nodes in setC is n. When packet is forwarded using greedy
forwarding at C, for GPSR, C needs to calculate and compare
the distances of n nodes to find the neighbor node with the
shortest distance as the next hop node. So for each node,
the time complexity of greedy forwarding in GPSR is O(n).
For the whole network, the time complexity of greedy for-
warding in GPSR is O(n2). For MM-GPSR in greedy for-
warding, C needs to find the neighbor node with the shortest
distance as GPSR in greedy forwarding, and then determines
Q by calculating dmax. We assume that the number of nodes
inQ ism, obviously,m ≤ n. By calculating and comparing the
current cumulative communication durations ofm nodes inQ,
C selects the neighbor node with the maximum cumulative
communication duration as the next hop node to forward
packet. So for each node, the time complexity of greedy
forwarding in MM-GPSR is O(n). For the whole network,
the time complexity of greedy forwarding in MM-GPSR
is O(n2) too.
Packets will be forwarded using perimeter forwarding
at C when greedy forwarding fails. In perimeter forwarding
of GPSR, a no-crossing network based on the RNG or GG
needs to be constructed firstly, with the time complexity
O(n2) for each node [18], then C selects next hop node in
the no-crossing network by using right-hand rule. We assume
that the number of nodes in this no-crossing network is k ,
obviously, k ≤ n. So for each node, the time complexity
of perimeter forwarding in GPSR is O(n2). For the whole
network, the time complexity of perimeter forwarding in
GPSR is O(n3). As the same as GPSR, a no-crossing network
also needs to be constructed for MM-GPSR in perimeter
VOLUME 6, 2018 39519
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
Algorithm 1: Procedure for MM-GPSR
Initialization:
neighbor← NULL
dmin ← dC→D
neighbormin ← NULL
Tmax ← 0
dmax ← 0
nodenext ← NULL
θleft ← π
θright ← π
λ← 0.3
Note:
C : Current node.
p : Data packet.
D : Destination node.
setC : Set of neighbor nodes of C.
dneighbor→D : The distance from neighbor to D.
Tneighbor : The cumulative communication duration of
neighbor.
θneighbor : The corresponding angle of neighbor.
planeright−half : The right-half plane by connecting
C and D.
Q : The allowed communication area.
while (C receive p) do
if C == D then
Finish transmitting p ;
else
if C meet the greedy forwarding method then
for each neighbor ∈ setC do
Calculate dneighbor→D by (1);
if dneighbor→D < dmin then
dmin ← dneighbor→D;
neighbormin ← neighbor ;
end if
end for
Calculate dC→neighbormin by (2);
dmax ← dmin + λ× dC→neighbormin ;
Determine Q;
for each neighbor in Q do
Calculate Tneighbor by (4);
if Tneighbor > Tmax then
Tmax ← Tneighbor ;
nodenext ← neighbor ;
end if
end for
Update p and then forward p to nodenext ;
else
for each neighbor ∈ setC do
if neighbor in planeright−half then
Calculate θneighbor by (6) or (12);
if θneighbor < θright then
θright ← θneighbor ;
noderight ← neighbor ;
end if
else
Calculate θneighbor by (8) or (10);
if θneighbor < θleft then
θleft ← θneighbor ;
nodeleft ← neighbor ;
end if
end if
end for
if θleft ≤ θright then
nodenext ← nodeleft ;
else
nodenext ← noderight ;
end
Update p and then forward p to nodenext ;
end if
end if
end while
forwarding at first. Then C selects the neighbor node with
the minimum corresponding angle as the next hop node in
this no-crossing network. So for the whole network, the
time complexity of perimeter forwarding in MM-GPSR is
O(n3) too. The time complexity comparison of GPSR and
MM-GPSR is shown in TABLE 1.
TABLE 1. Time complexity comparison of GPSR and MM-GPSR.
IV. SIMULATION AND RESULTS ANALYSIS
The simulation experiments were conducted on NS-2.29.
Without available GPSR routing protocol in NS-2.29,
so GPSR routing protocol was transplanted to NS-2.29 at
first, and then the improved MM-GPSR routing protocol
was added in NS-2.29 [28], [29]. NS-2.29 only provides the
network simulation platform, IDM_LC model of VanetMo-
biSim was used to generate the tracefile as the simulation
mobile scenario [30]. The simulation of GPSR and MM-
GPSR was conducted with different numbers of nodes and
different maximum node speeds.
The performance metrics used in the simulation experi-
ments are as follows:
1) Packet loss rate: Packet loss rate metric represents the
ratio of the sum of the lost packets to the total number of
packets sent at the source node.
2) End-to-end delay: This metric represents the average
end-to-end delay measured by the ratio of the sum of the
transmission packet delays to the number of successfully
received packets.
3) Throughput: This metric represents the average amount
of data that is successfully transmitted over a unit of time
throughout the network.
We simulated 30, 50, 70, 90, 110 vehicle nodes with
the maximum node speed of 15m/s, and 50 vehicle nodes
with maximum node speeds of 5, 10, 15, 20, 25 m/s. All
other simulation parameters were set to constants as shown
in TABLE 2.
TABLE 2. Simulation parameters.
39520 VOLUME 6, 2018
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
A. PACKET LOSS RATE
Fig. 7(a) shows the comparison of packet loss rate between
GPSR and MM-GPSR with different number of nodes. It can
be seen from Fig. 7(a) that the packet loss rate of both
GPSR and MM-GPSR are decreasing with the increase of
the number of nodes. When there are only a few nodes in
mobile scenario, the distribution of nodes is relatively sparse,
both GPSR and MM-GPSR are not easy to find the next
hop forwarding node; when the number of nodes gradually
increases, the distance between the nodes becomes short,
resulting in significant decrease in packet loss rate. Compared
with GPSR, MM-GPSR has the smaller packet loss rate in
the whole process, and has better performance of avoiding
communication interruption with more nodes. This is due to
that MM-GPSR selects the neighbor node, which is more
steady and not easy to move out of the communication range
of the current node, as the next hop node when forwarding
data packets, and the communication link is more reliable
and robust; while GPSR selects the next hop node sometimes
nearer to the communication range edge of current node,
whichmakes the next hop nodemore likely to move out of the
communication range, leading to the link failure and packet
loss.
Fig. 7(b) shows the comparison of packet loss rate between
GPSR and MM-GPSR with different maximum node speeds.
As explained in Fig. 7(b), the packet loss rates of both GPSR
and MM-GPSR are increasing as the node speed increases.
The main reason is that the neighbor relationship is more
unstable with the higher node speeds, and the link interruption
is more likely to happen, thus the packet more tends to
lose. Overall, MM-GPSR has lower packet loss rate than
GPSR, because MM-GPSR takes the stability of neighbor
relationship fully into account when transmitting packets,
and the communication link is not easy to break, making the
packet loss rate reduced. In particular, the packet loss rate of
MM-GPSR is better than that of GPSRwhen the vehicle node
speed is very high (25m/s).
B. END-TO-END DELAY
Fig. 8(a) shows the comparison of end-to-end delay between
GPSR and MM-GPSR with different number of nodes. It can
be found from Fig. 8(a) that when the number of nodes is
small, the neighbor nodes of each node are less and the neigh-
bor relationship is unstable and unreliable. When packets
are transmitted, the perimeter forwarding needs to be started
more frequently, generatingmore path redundancy and longer
end-to-end delay; as the number of nodes increases, the stabil-
ity of the neighbor relationship between the nodes increases,
and the communication link is more steady and robust, so the
end-to-end delay is reduced. On the whole, the end-to-end
delay of MM-GPSR is shorter than that of GPSR, this is
because MM-GPSR chooses the more stable neighbor node
as the next hop node which reduces both the startup proba-
bility of the perimeter forwarding and the path redundancy
effectively when forwarding packets.
FIGURE 7. Packet loss rate via (a) number of nodes, (b) maximum node
speed.
Fig. 8(b) shows the end-to-end delay of GPSR and
MM-GPSR for the different maximum speed of the vehicle
nodes. Fig. 8(b) shows that when the speed of the vehicle
nodes is slow, the end-to-end delays of GPSR andMM-GPSR
are relatively small; as the node moves faster, the delays of
both GPSR and MM-GPSR are increasing, this is because
that the position information changes more frequently in
condition of higher maximum node speed, making the
end-to-end delay increase. Overall, the end-to-end delay of
MM-GPSR is lower than that of GPSR, this is due to that
MM-GPSR chooses the forwarding node with more stable
neighbor relationship and builds a more robust path.
C. THROUGHPUT
Fig. 9(a) shows the throughput of GPSR and MM-GPSR
under the different number of nodes. As shown in Fig. 9(a),
the throughput of both GPSR and MM-GPSR increases with
the increase of the number of nodes, this is due to that the
communication load capacity of the network is gradually
enhanced with more nodes participating in forwarding pack-
ets. In general, the throughput of MM-GPSR is larger than
VOLUME 6, 2018 39521
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
FIGURE 8. End-to-end delay via (a) number of nodes, (b) maximum node
speed.
that of GPSR, mainly because MM-GPSR builds more robust
and reasonable link which improves the communication per-
formance and makes the network throughput increase.
Fig. 9(b) shows the throughput of GPSR andMM-GPSR in
cases of the different maximum node speeds. It can be found
in Fig. 9(b) that the throughput of GPSR and MM-GPSR
decrease with the increase of node speed. This is because
that the communication links are easy to break and the load
capacity of the network is weakened when the node speed
is gradually getting higher. On the whole, the throughput
of MM-GPSR is larger than that of GPSR, this is due to
that MM-GPSR selects the next hop node with more stable
neighbor relationship and can build the more robust path
than GPSR.
From the simulation and result analysis of this section,
it can be seen that MM-GPSR performs better than GPSR
in the packet loss rate, end-to-end delay and the throughput
under the different number of nodes and maximum node
speed. Especially in larger number of nodes and higher node
speed, MM-GPSR has notable performance improvement.
FIGURE 9. Throughput via (a) number of nodes, (b) maximum node speed.
V. CONCLUSION
In VANET, nodes move quickly, and the topology changes
frequently, so the design of routing is challenging. In this
paper, we have made a deep study on GPSR which is more
suitable in VANET compared with other protocols such as
AODV. By discovering and considering the neighbor instabil-
ity in greedy forwarding and the path redundancy in perimeter
forwarding of GPSR, we have proposed MM-GPSR routing
protocol based onGPSR. Themain contributions of this paper
can be summarized as follows:
1) In greedy forwarding, we introduce the allowed com-
munication area and cumulative communication dura-
tion. By comparing the cumulative duration of neighbor
nodes in allowed communication area, the neighbor
nodes with maximum duration will be selected as the
next hop. This novel method can build steady path and
avoid the reconstruction of routing effectively.
2) In perimeter forwarding when greedy forwarding fails,
we introduce the minimum angle. By comparing the
angles of neighbor nodes, the neighbor node with
39522 VOLUME 6, 2018
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
minimum angle will be selected as the next hop. This
improved method can reduce the path redundancy
and build shorter path so that can save the network
resources and decrease the network delay.
3) According to the time complexity analysis, com-
pared with GPSR, MM-GPSR does not add the time
complexity.
Finally, experiments show that the proposed MM-GPSR
has a better performance than GPSR, and verify the superior-
ity of MM-GPSR.
REFERENCES
[1] J. Zhang et al., ‘‘Energy-latency trade-off for energy-aware offloading
in mobile edge computing networks,’’ IEEE Internet Things J., to be
published, doi: 10.1109/JIOT.2017.2786343.
[2] S. Biswas, R. Tatchikou, and F. Dion, ‘‘Vehicle-to-vehicle wireless com-
munication protocols for enhancing highway traffic safety,’’ IEEE Com-
mun. Mag., vol. 44, no. 1, pp. 74–82, Jan. 2006.
[3] S. Yousefi, M. S. Mousavi, and M. Fathy, ‘‘Vehicular ad hoc net-
works (VANETs): Challenges and perspectives,’’ in Proc. 6th Int. Conf.
ITS Telecommun., Chengdu, China, Jun. 2006, pp. 761–766.
[4] Z. Ning, F. Xia, N. Ullah, X. Kong, and X. Hu, ‘‘Vehicular social networks:
Enabling smart mobility,’’ IEEE Commun. Mag., vol. 55, no. 5, pp. 49–55,
May 2017.
[5] X. Hu, T. H. S. Chu, V. C. M. Leung, E. C.-H. Ngai, P. Kruchten,
and H. C. B. Chan, ‘‘A survey on mobile social networks: Applications,
platforms, system architectures, and future research directions,’’ IEEE
Commun. Surveys Tuts., vol. 17, no. 3, pp. 1557–1581, 3rd Quart., 2015.
[6] Z. Ning et al., ‘‘A cooperative quality-aware service access system for
social Internet of vehicles,’’ IEEE Internet Things J., to be published, doi:
10.1109/JIOT.2017.2764259.
[7] Z. Ning, X.Wang, X. Kong, andW. Hou, ‘‘A social-aware group formation
framework for information diffusion in narrowband Internet of Things,’’
IEEE Internet Things J., vol. 5, no. 3, pp. 1527–1538, Jun. 2018.
[8] K. Cengiz and T. Dag, ‘‘Energy aware multi-hop routing protocol for
WSNs,’’ IEEE Access, vol. 6, pp. 2622–2633, 2017.
[9] T. Abdelkader, K. Naik, A. Nayak, N. Goel, and V. Srivastava, ‘‘A per-
formance comparison of delay-tolerant network routing protocols,’’ IEEE
Netw., vol. 30, no. 2, pp. 46–53, Mar./Apr. 2016.
[10] A. Al-Saadi, R. Setchi, Y. Hicks, and S. M. Allen, ‘‘Routing protocol
for heterogeneous wireless mesh networks,’’ IEEE Trans. Veh. Technol.,
vol. 65, no. 12, pp. 9773–9786, Dec. 2016.
[11] H. Zhang, X. Wang, P. Memarmoshrefi, and D. Hogrefe, ‘‘A survey of ant
colony optimization based routing protocols for mobile ad hoc networks,’’
IEEE Access, vol. 5, pp. 24139–24161, 2017.
[12] C. E. Perkins and E. M. Royer, ‘‘Ad-hoc on-demand distance vector rout-
ing,’’ in Proc. 2nd IEEE Workshop Mobile Comput. Syst. Appl. (WMCSA),
New Orleans, LA, USA, Feb. 1999, pp. 94–95.
[13] R. Bala and C. R. Krishna, ‘‘Scenario based performance analysis of
AODV and GPSR routing protocols in a VANET,’’ in Proc. IEEE Int. Conf.
Comput. Intell. Commun. Technol. (CICT), Ghaziabad, India, Feb. 2015,
pp. 432–437.
[14] C. F. Xing, L. Yang, and Q. L. Han, ‘‘Development of a new routing
protocol based on GPSR for wireless sensor networks,’’ Appl. Mech.
Mater., vol. 644, pp. 2973–2977, Sep. 2014.
[15] N. Ramakrishnaiah, P. C. Reddy, and K. Sahadevaiah, ‘‘Performance anal-
ysis of dynamic addressing scheme with DSR, DSDV and ZRP routing
protocols in wireless ad hoc networks,’’ inProc. 1st Int. Conf. Inf. Commun.
Technol. Intell. Syst., vol. 1, Jul. 2016, pp. 41–50.
[16] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, ‘‘A distance
routing effect algorithm for mobility (DREAM),’’ in Proc. 4th Annu.
ACM/IEEE Int. Conf. Mobile Comput. Netw., Dallas, TX, USA, Oct. 1998,
pp. 76–84.
[17] G. Gokilavani, K. Sathyapriya, S. S. Suganya, and K. Hemalatha, ‘‘Design-
ing mobility using distance routing effect algorithm,’’ Int. J. Eng. Sci. Res.
Technol., vol. 3, pp. 647–655, Feb. 2014.
[18] B. Karp and H. T. Kung, ‘‘GPSR: Greedy perimeter stateless routing for
wireless networks,’’ in Proc. 6th Annu. Int. Conf. Mobile Comput. New.,
Boston, MA, USA, Aug. 2000, pp. 243–254.
[19] A. Setiabudi, A. A. Pratiwi, Ardiansyah, D. Perdana, and R. F. Sari,
‘‘Performance comparison of GPSR and ZRP routing protocols in
VANET environment,’’ in Proc. IEEE Region 10 Symp. (TENSYMP), Bali,
Indonesia, May 2016, pp. 42–47.
[20] Z. Cui, D. Li, G. Zhang, C. Guo, and Y. Sheng, ‘‘The next-hop node selec-
tion based GPSR in vehicular ad hoc networks,’’ J. Comput. Commun.,
vol. 4, pp. 44–56, Aug. 2016.
[21] R. Alsaqour et al., ‘‘Dynamic packet beaconing for GPSR mobile ad hoc
position-based routing protocol using fuzzy logic,’’ J. Netw. Comput. Appl.,
vol. 47, pp. 32–46, Jan. 2015.
[22] J. Li, P. Wang, and C. Wang, ‘‘Comprehensive GPSR routing in VANET
communications with adaptive beacon interval,’’ in Proc. IEEE Int. Conf.
Intenet Things (iThings) IEEE Green Comput. Commun. (GreenCom)
IEEE Cyber, Phys. Social Comput. (CPSCom) IEEE Smart
Data (SmartData), Chengdu, China, Dec. 2016, pp. 1–6.
[23] Z. S. Houssaini, I. Zaimi, M. Oumsis, and S. El Alaoui Ouatik, ‘‘Improve-
ment of GPSR protocol by using future position estimation of participating
nodes in vehicular ad-hoc Networks,’’ in Proc. Int. Conf. Wireless Netw.
Mobile Commun. (WINCOM), Fez, Morocco, Oct. 2016, pp. 87–94.
[24] Q. Ding, B. Sun, and X. Zhang, ‘‘A traffic-light-aware routing protocol
based on street connectivity for urban vehicular ad hoc networks,’’ IEEE
Commun. Lett., vol. 20, no. 8, pp. 1635–1638, Aug. 2016.
[25] X. M. Zhang, K. H. Chen, X. L. Cao, and D. K. Sung, ‘‘A street-centric
routing protocol based on microtopology in vehicular ad hoc networks,’’
IEEE Trans. Veh. Technol., vol. 65, no. 7, pp. 5680–5694, Jul. 2016.
[26] R. Jiang, Y. Zhu, T. He, Y. Liu, and L. M. Ni, ‘‘Exploiting trajectory-based
coverage for geocast in vehicular networks,’’ IEEE Trans. Parallel Distrib.
Syst., vol. 25, no. 12, pp. 3177–3189, Dec. 2014.
[27] Q. Chen, S. S. Kanhere, and M. Hassan, ‘‘Adaptive position update for
geographic routing in mobile ad hoc networks,’’ IEEE Trans. Mobile
Comput., vol. 12, no. 3, pp. 489–501, Mar. 2013.
[28] J. Chung and M. Claypool. (2002). NS by Example. [Online]. Available:
http://nile.wpi.edu/NS
[29] K. Fall and K. Varadhan. (2007). The Network simulator (NS-2). [Online].
Available: http://www.isi.edu/nsnam/ns
[30] J. Härri et al., ‘‘Vehicular mobility simulation with VanetMobiSim,’’
Simulation, vol. 87, pp. 275–300, Apr. 2011.
XIAOPING YANG received the B.Eng. degree
in detection technology and instrument and the
M.S.E. degree in communication and electronic
system from the Jilin University of Technology,
Changchun, China, in 1985 and 1988, respectively,
and the Ph.D. degree in control theory and con-
trol engineering from Jilin University, Changchun,
China, in 2007. She is a Professor at the College
of Communication Engineering, Jilin University,
China. She has been committed to teaching and
research, including communication, signal and information processing for
years. Her current research interests include optimization control of data
transmission, congestion control in wireless communication network, and
routing protocol of Ad hoc network.
MENGJIE LI received the B.S. degree from the
School of Information Science and Engineering,
Hebei North University, Hebei, China, in 2015.
He is currently pursuing the M.S. degree with
the College of Communication Engineering, Jilin
University. His major research interests include
wireless sensor networks and routing protocols.
VOLUME 6, 2018 39523
http://dx.doi.org/10.1109/JIOT.2017.2786343
http://dx.doi.org/10.1109/JIOT.2017.2764259
X. Yang et al.: Improvement of GPSR Protocol in Vehicular Ad Hoc Network
ZHIHONG QIAN received the M.S. degree in
communication and electronics systems from the
Jilin University of Technology in 1991 and the
Ph.D. degree in communication and information
systems from Jilin University, China, in 2001. He
was a Visiting Researcher with the University of
Massachusetts, USA, in 2001, the University of
Texas, USA, in 2005, and Virginia Tech, USA,
in 2006. He is a Professor of communication and
information systems with Jilin University and also
a Ph.D. Candidate Supervisor. His research interests include radio frequency
identification, wireless network, and communication system, including key
technologies of wireless sensor networks, Internet of Things, signal analysis
and process of wireless network system. He hosted CSIE 2011, ITA2013,
SECS-2013, AICE2014, 2nd SECS-2014, CNIS2015, CSMA 2015, and
CSA2015 as the General Chair, and moreover, he delivered keynote speech
for the U-World-2011, ISEEIP 2012, ITA2013, CNIS 2015, and CSMA2015,
respectively, in the latest six years. He has authored three monographs. He
has been granted four patents. He has completed 26 research projects with his
co-operators as a principal investigator or main co-operator. He has authored
and co-authored over 120 research papers in National or International Aca-
demic Journals and Conferences. He is one of the Editorial Board Member
of the Journal of Communications, the Journal of Electronics & Information
Technology, the Journal of Electronics (China), the China Communications,
and the Study on Optical Communications.
TE DI received the B.S. degree from the College
of Communication Engineering, Jilin University,
Jilin, China, in 2014, and the M.S. degree in elec-
tronics and communication engineering from Jilin
University, in 2017. He is the Executive of inte-
grated office at Chang Guang Satellite Technology
Co., Ltd., Jilin.
39524 VOLUME 6, 2018
INTRODUCTION
PROBLEM DESCRIPTION
THE PROBLEM OF GREEDY FORWARDING
THE PROBLEM OF PERIMETER FORWARDING
IMPROVED METHOD OF GPSR PROTOCOL
THE IMPROVEMENT FOR THE INSTABILITY OF NEXT HOP IN GREEDY FORWARDING
THE IMPROVEMENT FOR PATH REDUNDANCY IN PERIMETER FORWARDING
THE IMPROVED MM-GPSR PROTOCOL
TIME COMPLEXITY ANALYSIS
SIMULATION AND RESULTS ANALYSIS
PACKET LOSS RATE
END-TO-END DELAY
THROUGHPUT
CONCLUSION
REFERENCES
Biographies
XIAOPING YANG
MENGJIE LI
ZHIHONG QIAN
TE DI