Applied Intelligence

https://doi.org/10.1007/s10489-018-1368-y

Novel self-adaptive routing service algorithm for application in VANET

Degan Zhang 1,2,3 & Ting Zhang 1,2,3 & Xiaohuan Liu 1,2,3

# Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract
As a special MANET (mobile ad hoc network), VANET (vehicular ad-hoc network) has two important properties: the network
topology changes frequently, and communication links are unreliable. Both properties are caused by vehicle mobility. To predict
the reliability of links between vehicles effectively and design a reliable routing service protocol to meet various QoS application
requirements, in this paper, details of the motion characteristics of vehicles and the reasons that cause links to go down are
analyzed. Then a link duration model based on time duration is proposed. Link reliability is evaluated and used as a key parameter
to design a new routing protocol. Quick changes in topology make it a huge challenge to find and maintain the end-to-end optimal
path, but the heuristic Q-Learning algorithm can dynamically adjust the routing path through interaction with the surrounding
environment. This paper proposes a reliable self-adaptive routing algorithm (RSAR) based on this heuristic service algorithm. By
combining the reliability parameter and adjusting the heuristic function, RSAR achieves good performance with VANET. With
the NS-2 simulator, RSAR performance is proved. The results show that RSAR is very useful for many VANET applications.

Keywords Vehicular ad-hoc networks . Reliability . Routing service . End-to-end . Self-adaptive . Heuristic algorithm

1 Introduction projects in these fields have been launched [1, 2]. According
to WHO reports, the number of deaths caused by traffic acci-
With the development of communication technology, the dents is 1.24 million worldwide every year. World Bank statis-
VANET (vehicular ad-hoc network) has become the most im- tics show that the world economic loss caused by traffic acci-
portant part of building an intelligent city and an intelligent dents is $500 billion per year [3]. With greater numbers of
transportation system (ITS). Because it is an extension of tradi- vehicles in cities, solving traffic congestion has become a
tional MANETs (mobile ad-hoc networks), VANET has elicited worldwide problem. Traffic congestion can cause time delay,
much interest from automobile manufacturers, governments, wasted fuel consumption, and unnecessary environmental pol-
and research institutions to provide services such as traffic lution. At the same time, with the development of a social
warning, information consulting, and entertainment; many vehicle network, in-car entertainment and communication be-
tween vehicles have become necessary functions that automo-
bile manufacturers provide to customers [4]. In VANETs, wire-
* Xiaohuan Liu
less communication can be divided into two types: vehicle-to-
815215568@qq.com infrastructure (V2I) and vehicle-to-vehicle (V2V). V2V is fa-
vored by many researchers because communication does not
Degan Zhang
gandegande@126.com
rely on infrastructure and its deployment is flexible. However,
VANET has some characteristics that are different from tradi-
Ting Zhang tional MANETs [5]. First, in VANETs, the network nodes (cars)
873432318@qq.com
move at high speed, which will cause frequent changes in net-
1
Key Laboratory of Computer Vision and System (Tianjin University work topology. The short link time maintained between nodes
of Technology), Ministry of Education, Tianjin 300384, China makes the links unreliable, and network performance varies
2
Tianjin Key Lab of Intelligent Computing & Novel software greatly with vehicle distribution. Second, vehicle nodes are re-
Technology, Tianjin University of Technology, Tianjin 300384, stricted to roads and are affected by many factors like speed
China limits and traffic signals. Third, vehicles can provide enough
3
School of Electronic and Information Engineering, University of power and computing ability for themselves, meaning that the
Sydney, Sydney NSW 2006, Australia energy limitations of MANET are no longer an important factor.
 D. Zhang et al.

As an important support technology to realize an intelligent a reliable model of a link between nodes by a detailed study of
transportation system, the design of an efficient routing protocol the motion properties of vehicles. Once the probability of link
has become an important step in implementing VANET applica- reliability has been calculated, it can be used as a parameter in
tions. Because the VANET topology changes frequently and the the Q-Learning algorithm to design the RSAR algorithm.
links are unreliable, traditional routing algorithms based on This paper is organized as follows. In the second section,
MANETs, such as the Ad-hoc On-demand Distance Vector the routing algorithm is simply classified and partly analyzed.
(AODV)[6]andDynamicSourceRouting(DSR)[7],aredifficult In the third section, the development of a reliable link evalu-
to use with VANETs. These algorithms have a lower delivery ratio ation model is described. The fourth section presents the main
and a longer transmission delay because they do not consider concept of the RSAR algorithm and the development of the
rapid topology changes. To overcome this problem, some routing model. The fifth section describes the simulation and analysis
algorithms based on geographic location, such as TFOR [8] and performed. The sixth and final section provides a summary
GyTAR [9], have been proposed recently [10]. These routing and suggestions for future work.
algorithms are designed based on traffic flow estimation, use
GPS to locate the destination node, and ignore topology changes,
but they do not consider link reliability between nodes. Some 2 Related work
reliable routing algorithms have been proposed, such as SLBF
[11] and EG-RAODV [12]. These algorithms were designed by 2.1 Routing protocol classification
adding parameters such as link reliability between nodes and
packet error rate. This approach can improve the packet delivery In VANETs, the routing algorithms can be divided into two
ratio to a certain extent, but cannot guarantee the time delay. In main types: one based on topology, the other based on
VANETs, a rapid change in velocity is the main cause of topology geographical location. Routing algorithms based on topol-
changes and unreliable links. Only a full understanding of vehicle ogy can be divided into reactive (on-demand) routing al-
motion characteristics can lead to effective evaluation of link re- gorithms and active (table-driven) routing algorithms. In a
liability and efficient routing algorithm designs. reactive routing protocol, nodes establish the route accord-
Assuming that vehicles are moving on a fixed route, various ing to their requirements and maintain an end-to-end path.
factors can break the link between two nodes, such as the trav- Representative routing algorithms include AODV and
eling direction of the two vehicles, the distance between vehi- DSR. Some algorithms like EG-RAODV [12] and
cles, speed, and acceleration. To evaluate link reliability between QLAODV [15] have been derived on this basis and are
nodes effectively, these factors should be fully considered, es- more suitable to VANETs. In an active routing algorithm
pecially given the low-density, high-speed environment. The like DSDV and OLSR [16], nodes maintain the topology of
distance between vehicles plays an important role in ensuring the whole network through exchanging the routing table.
traffic safety and evaluating link reliability. Many models of In a rapidly changing VANET, a fast change in topology is
distance between vehicles have been proposed, such as the ex- the only factor that affects the active routing algorithm. In a
ponential distribution model, the normal distribution model, and protocol based on geographical location, a GPS is provided
the lognormal distribution. In [13], the authors proved by exper- for each vehicle so that its coordinates, speed, and direc-
iments that the distance between vehicles can be more consistent tion can be accurately determined. The vehicle does not
with real traffic flow and safe distances when it follows a log- need to maintain the path from the source to the destination
normal distribution. A full understanding of the traffic flow node, and each node maintains only one neighbor table to
model and the motion characteristics of vehicles can help eval- record the location and speed of neighbor nodes. Routing
uate link reliability between nodes effectively. With ongoing algorithms based on geographical location can be divided
studies of routing algorithms in recent years, some intelligent into two kinds. Algorithms in which the sending node
algorithms [14] have been applied to VANETs and have yielded makes the routing decision actively are called sending
better results than traditional routing algorithms. As a self- node-based forwarding (SBF). Algorithms in which the
learning algorithm, the Q-Learning algorithm [15] can find the receiving node determines whether it can be the next seg-
shortest path from a source node to a destination node through ment of a link are called receiving node-based forwarding
constant interaction with its environment. Based on this idea, in (RBF). Among SBF-based routing mechanisms, the most
this paper, a reliable adaptive routing algorithm (RSAR) is pro- representative is the GPSR [17] routing. In [18], the STAR
posed by improving the Q-Learning algorithm. It can adaptively algorithm is proposed. These are both SBF-based routing
adjust the Q-table while ensuring the reliability of each hop link algorithms. In RBF-based routing, sending nodes send data
to adapt to a dynamic network topology such as VANET. packets by broadcasting them. When receiving nodes re-
The main purpose of this paper is to propose a reliable and ceive broadcast data packets, they compete for the right to
adaptive routing algorithm. The reliability of an entire link forward them. The nodes that obtain the forwarding right
depends on the links between each hop. This paper establishes become the next hop in a link and suppress other nodes
Novel self-adaptive routing service algorithm for application in VANET

from forwarding packets. SLBF [11] is a typical RBF al- dynamic topology changes. References [29–32] proposed a
gorithm that uses node locations to calculate waiting time; QGrid algorithm based on Q-Learning; they divided the entire
the nodes that have the shortest waiting time have the right region into grid cells and selected the next hop forwarding node
to forward packets. Vegni [19] proposed a clustering-based by calculating the Q-value from both macro and micro aspects.
RBF algorithm that reduces the number of forwarding In addition, recent related studies are described in [33–39].
nodes to suppress redundant packets. For example, reference [33] investigated a centralized model
and a heuristic algorithm for solving the multi-depot logistics
2.2 Link evaluation algorithm delivery problem, including depot selection and shared com-
modity delivery. Reference [37] concentrated on introducing
According to routing algorithm classification research, many an adaptive cooperative caching strategy with novel cache
routing algorithms for VANETs have been proposed, but algo- replacement and prefetching policies, which divided the net-
rithms that predict link reliability according to motion character- work into non-overlapping clusters. Reference [39] proposed
istics of vehicles are rare. In VANETs, it is necessary to ensure link a novel filter model based on a hidden Markov model (HMM)
reliability, which guarantees the entire path’s validity. In [20], the (FM-HMM) for an intrusion detection system to reduce the
authors predicted link reliability and routing path according to overhead and time required for detection without impairing
signal strength. In [21], the authors developed a mobile model the detection rate. Moreover, relative comparisons of results
to estimate the duration of an n-node path, in which they consid- among these methods have been done.
ered speed, but not acceleration. The MORP [22] algorithm based
on motion prediction has also been proposed. MORP predicts the
future position of the vehicle and the stability of the link. By using 3 Link reliability model
location, direction, and speed to predict link state, MORP selects
the most stable end-to-end routing path. A prediction-based On a highway, the fast movement of vehicles makes links very
routing algorithm [23] has been proposed for VANETs and ad- unreliable. Designing a reliable routing algorithm is a chal-
justs the routing path by predicting the life cycle of the link, which lenging task. The movement of vehicles is the main factor that
is predicted by communication range, vehicle position, and cor- makes the links unreliable. To evaluate link reliability between
responding speed. Considering that the routing path consists of nodes effectively, a capable system model and link duration
many links, the minimum-duration link determines the maximum model must be developed. The first step is to develop the
survival time of the whole link, so that the maximum link duration system model based on vehicle motion characteristics; then
of the path can be effectively predicted. the duration of links between nodes can be evaluated, leading
to construction of a reliable link model.
2.3 Q-learning algorithm
3.1 System model
The Q-Learning algorithm [24] is a reinforcement learning al-
gorithm, which is proposed in a machine learning context. The
To evaluate link quality between nodes effectively, assuming
learning process is such that in different states, the agent finds a
that the highway is generally a straight road as in [40, 41] and
path to reach the destination node with the maximum return
that the broadcasting distance is much longer than the width of
value by periodically updating its state-activity value (Q-
the road, it can be further assumed that the width of the road
Value). Q-Learning is an unsupervised active learning algo-
has a very small influence on selecting the next hop
rithm, which does not require a specific system model and can
forwarding node, and therefore the width of the road can be
adapt to different environments by interacting with its surround-
ignored. Figure 1 shows the highway model used. It can fur-
ings. In the Q-Learning algorithm, the Q-value Q(s, a)(s ∈ S, a ∈
ther be assumed that acceleration, deceleration, changing
A) represents a reward value that a learning agent converted
lanes, overtaking, and other maneuvers are taking place on
from state s to another state through an activity a, where s
the road. Besides, the distance between vehicles is log-
represents a state and a represents an activity. Because a state
normally distributed [16], that is, Xi ∈ log N(μi, δi). As shown
closer to the destination will receive a higher reward value, the
in Fig. 1, Xi = {Xi(m), m = 0, 1, 2, ⋯} is a random variable that
distance between the state and the destination can be effectively
is log-normally distributed. Xi represents the distance between
determined according to the reward value. As the agent contin-
uously converts activities to find the path to the destination node
in different states, it can ultimately find the shortest path from
the source node to the destination node. This intelligent algo-
rithm is beginning to be used in VANETs. Some researchers
[25–28] have proposed an algorithm by combining fuzzy logic
with Q-Learning (FQ-OPP); this algorithm can be adapted to Fig. 1 Road model
 D. Zhang et al.

vehicles i and i + 1, and Xi(m) is a random variable that repre- a b

sents the distance between node i and other nodes at time m. In
Fig. 1, if node Vs is regarded as the reference node, then X
represents the distance between Vs and any other node, where
m
X ¼ ∑ X i , so X is also log-normally distributed [42].
i¼1

Lemma 1 Assuming that X ∈ log N(μ, δ), the random variable

pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
T ¼ aX þ b þ c is log-normally distributed, where a, b,
c ∈ R, a, b, c ≠ 0 and aX + b ≥ 0. Fig. 2 Two cases of link breakage

Proof Let GT be the probability distribution function of T. For

Assuming that the vehicles are moving on a fixed road, there are
every positive t, GT(t) = Pr[{T ≤ t}]. Obviously, because T is
twomainconditions(showninFig.2)underwhichthelinkbetween
continuous,
two nodes becomes disconnected. In Figure Ba^, two vehicles are
GT ðt Þ ¼ Pr½fT ≤ t g moving in the same direction, and in Figure Bb^, two vehicles are
hnpffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi oi moving in opposite directions. Consider vehicle i as the reference
¼ Pr aX þ b þ c ≤ t nodeandvehiclejasthetransmissionnode.Inothercases,vehiclesi
hn oi and j have the longest link communication time. The next step is to
¼ Pr aX ≤ ðt−cÞ2 −b analyze the link duration in detail in these two cases.
8 ! Asshown in Fig. 2a, assume that at time t0 = 0, vehicle i is within
>
> ð t−c Þ 2
−b
>
> F when a > 0 the one-hop communication range of vehicle j and that vehicle i is
>
< X a located in front of vehicle j. The initial distance between vehicles X
¼ !
>
> ð Þ 2
−b
is a random variable. The maximum communication radius of ve-
>
> t−c
> 1− F X
: when a < 0 hicle R is a fixed constant. At the initial moment, X satisfies
a
0 ≤ X < R:
where FX is the probability distribution function of X. When
a > 0, it is clear that T is log-normally distributed. When a < 0, According to the system model, there will be acceleration,
  deceleration and overtaking of vehicles on a highway. The
according to [13], F ðzÞ ¼ 12 þ 12 erf σ pzffiffi2 , and letting z = ((t
z−μ
z maximum speed limit on the road is set to vm, i.e., all vehicles
− c)2 − b/a), should move at a speed less than or equal to vm. Assume that
! the vehicle’s acceleration is a(0) and that its speed is v(0).
1 1 lnz−μðX Þ When t ≥ 0, the acceleration is defined as a(t), and the speed
1−F X ðzÞ ¼ − erf pffiffiffi
2 2 σð X Þ 2 is defined as v(t). At time t, the acceleration is as follows:
!
a 1) If a(0) = 0, for all t ≥ 0,
¼ FY
ðt−cÞ2 −b
aðt Þ ¼ 0: ð1Þ
where Y is a log-normal random variable with parameters −μ(X)
2) If a(0) > 0,
and σ(X). Note that the fact that − erf (x) = erf (−x) is used.
8
Hence, T obeys a log-normal distribution, completing the proof. < a ð 0Þ vm −vð0Þ
t≤
að t Þ ¼ a ð 0Þ : ð2Þ
Lemma 2 Assuming that X ∈ log N(μ, σ), the random variable :
0 otherwise
T = aX + b is log-normally distributed, where a, b, c ∈ R and a,
b, c ≠ 0. 3) If a(0) < 0,
This lemma can be easily proved using the arguments ad-
8
duced in the proof of Lemma 1. < a ð 0Þ −vð0Þ
t≤
að t Þ ¼ a ð 0Þ : ð3Þ
3.2 Link duration model :
0 otherwise

In Fig. 2, Ba^ shows two vehicles moving in the same direc- From the above analysis, it can be assumed that when t0 = 0, if
tion, and Bb^ shows two vehicles moving in opposite direc- the acceleration a(0) at this time is also 0, then the instantaneous
tions, where the black arrows indicate the direction of motion. acceleration is also 0, i.e., a(t) = 0. For Eqs. (2) and (3), if the
Novel self-adaptive routing service algorithm for application in VANET

speed is below the maximum speed limit or is reduced to 0, it is The next step is to analyze the link duration in Fig. 2b,
assumed that the acceleration is still a(0); otherwise, it is changed where two vehicles are moving in opposite directions. When
to 0. Taking the initial speed v(0) into account,at time t, the two vehicles meet:
instantaneous speed v(t) is defined by the following formula:
S j ðt Þ þ S i ðt Þ þ X ¼ R: ð9Þ
t
vðt Þ ¼ vð0Þ þ ∫ aðuÞdu; ð4Þ The maximum link duration t can now be calculated. By
0
assuming that S j ðt Þ þ S i ðt Þ ¼ 12 ar t 2 þ vr t, where ar = ai + aj
where u ∈ [0, t], a(u) is the acceleration at time u. and vr = vi + vj, and by substituting this into Eq. (9), the max-
Now Eqs. (1–4) can be combined to calculate the instanta- imum link duration t can be obtained as:
neous speed: pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
−vr þ v2r þ 2ar ðR−X Þ
t¼ : ð10Þ
1) If a(0) = 0, for all t ≥ 0, ar

v ð t Þ ¼ v ð 0Þ When two vehicles are moving in the same direction, as

shown in Fig. 2a, during acceleration, deceleration, and over-
2) If a(0) > 0, taking, it is critical to determine whether vehicle i or j is in
8 front. When Sj(t) − Si(t) + X > 0, vehicle j is located in front of
< vð0Þ þ að0Þt vm −vð0Þ
t≤ vehicle i; otherwise, vehicle i is located in front of vehicle j. To
vð t Þ ¼ a ð 0Þ ð5Þ
: express effectively which vehicle is in front, a symbolic func-
vm else tion was defined as follows:

3) If a(0) < 0, 1 S j ðt Þ−S i ðt Þ þ X > 0
I ði; jÞ ¼ : ð11Þ
8 −1 otherwise
< vð0Þ þ að0Þt −vð0Þ
t≤
vð t Þ ¼ a ð 0Þ ð6Þ When the link is in a critical state of disconnection,:
:
vm else
S j ðt Þ−S i ðt Þ þ X ¼ R⋅I ði; jÞ: ð12Þ
According to the above definition, the distance that any
vehicle moves at speed v(x) in time interval [0, t] is defined as: At this point, two cases must be considered to calculate the
link duration.
t
When I(i, j) = 1, vehicle j is located in front of vehicle i.
S ðt Þ ¼ ∫ vðxÞdx: ð7Þ
0 From Eq. (12), Sj(t) − Si(t) + X = R. Similarly to Eq. (10), be-
cause S j ðt Þ−S i ðt Þ ¼ 12 ar t 2 þ vr t, where ar = aj − ai and vr = vj
Again according to the above definition, as Fig. 2 shows, − vi, the time t can be determined as:
the distance between vehicles i and j at time t can be calculat- pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ed. Assuming that the initial speed and acceleration of vehi- −vr þ v2r þ 2ar ðR−X Þ
cles i and j are ai(0), vi(0), aj(0), and vj(0) respectively, the t¼ : ð13Þ
ar
instantaneous speed and acceleration of vehicles i and j at time
t are ai(t), vi(t), aj(t), and vj(t). According to Eqs. (1–7), the Similarly, when I(i, j) = − 1, vehicle i is located in front of
distance between vehicles i and j in time interval [0, t] can be vehicle j. From Eq. (15), Sj(t) − Si(t) + X = − R, and the link
calculated as follows: duration t can be determined as:
pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
t −vr − v2r −2ar ðR þ X Þ
S i ðt Þ ¼ ∫ vi ðxÞdx; t¼ ð14Þ
0 ar
t
Equations (10), (13), and (14) can be used to calculate the
S j ðt Þ ¼ ∫ v j ðxÞdx:
0 link duration of the sending node and an arbitrary node within
one hop range.
When the initial distance between vehicles i and j is X, the
distance di, j between i and j at time t is: Lemma 3 Assuming that the communication link between two
 vehicles i and j breaks at time t, the link duration time is either
S j ðt Þ þ S i ðt Þ þ X same direction
d i; j ¼ : ð8Þ a linear function of X or a square root function of X.
S j ðt Þ−S i ðt Þ þ X opposite direction

From Eq. (8), it is obvious that when di, j > R, the link is Proof When the link disconnects at time t, by the definition of
t
disconnected. Si(t) according to Eq. (7), it is known that S i ðt Þ ¼ ∫0 vi ðxÞdx is a
 D. Zhang et al.

linear function of t when the speed vi is constant, i.e., vi = vm. 4 RSAR algorithm
Let Si(t) = at + b. Similarly, if vj is a constant, it can be conclud-
ed that Sj(t) = ct + d is also a linear function of t. Obviously, In VANETs, the fast motion of the nodes makes the network
according to Eq. (8), when the two vehicles are moving in topology change frequently. It is difficult for a simple
opposite directions, (a + c)t + b + d + X = R. The link duration forwarding strategy to find an efficient routing path in this
time t ¼ R−b−d−X
aþc is a linear function. Similarly, when a link has rapidly changing network environment. Related studies have
been established between codirectional vehicles i and j, the link presented the Q-Learning algorithm as an unsupervised self-
duration time is also a linear function according to the equation learning algorithm. Through continuous interaction with the
(c − a)t − b + d + X = R ⋅ I(i, j). Hence, the link duration t is a external environment, it can adaptively adjust its value to find
linear function when both vi and vj are constant. If either vi(t) the optimal path to the destination. Hence, it is well suited to
or vj(t) are not constant, then the distance function will be a dynamic VANETs. This section will describe the routing and
quadratic polynomial. Without loss of generality, let vi(t) = v- forwarding strategy of the Q-Learning algorithm in VANETs.
i(0) + ait. By definition, the distance function is:

t
4.1 Idea of Q-learning algorithm in VANET
S i ð t Þ ¼ ∫ v i ð 0Þ þ ai
0 : Standard Q-Learning is a heuristic learning method based on a
1
¼ vi ð0Þt þ ai t 2 learning agent. Generally, in the standard Q-Learning algo-
2
rithm, the learning process of the agent is composed of a 3-
As shown in Eqs. (9) and (12), S j ðt Þ  S i ðt Þ ¼ 12 ar t 2 þ vr t tuple {S, A, R}, where S = {s1, s2, ⋯, sn} represents the state
and a ≠ 0. Therefore, the solution must be a square root func- space; A = {a1, a2, ⋯, an} represents the activity space, and
tion of X. moving from one state to another is regarded as an effective
activity; R represents the immediate reward for an activity;
Theorem 1 The duration T of the link between vehicles i and j and the closer the agent is to the destination, the higher the
is log-normally distributed. reward obtained for the activity. The following subsections
will present a few related definitions first and then describe
Proof By Lemma 3, the link duration can be expressed as the learning process in detail.
pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
either aX + b or aX þ b þ c. By Lemma 1, the expression
pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
aX þ b þ c is log-normally distributed. By Lemma 2, 4.1.1 Related definitions
aX + b is log-normally distributed. Hence, in all cases, the
duration time of the link has a log-normal distribution. This Definition 1 Basic components.
completes the proof of the theorem. Learning environment: The whole VANET environment as
the learning environment of the agent;
3.3 Link reliability model Agent: Each vehicle node is a learning agent;
State space S: The state space of a given agent is composed
Based on the link duration between nodes, the link duration of of all other nodes except for this agent;
vehicles i and j is log-normally distributed as T ∈ log N(μt, σt), Activity space A: A beacon packet is transmitted from one
where the expectation is μt and the variance is σt. Link reli- vehicle to another, which is defined as an activity;
ability can then be evaluated according to duration. Link reli- Immediate reward R: obtained when an agent carries
ability is defined as the probability of direct communication out an activity.
between two vehicles in time period Tp. Assuming that the
communication link between any two vehicle nodes is l, when Definition 2 Reward value: According to Definition 1, the
t = t0, the link reliability between nodes is: reward that an agent receives for carrying out an activity is
  called the immediate reward, and its range is [0, 1]. Because
rðl Þ ¼ P t 0 þ T p jt 0 ∈M ; the destination node can directly reach the destination node, its
reward value is 1. Formula (16) defines the initial value R of
where M is the starting time for the connection between the
the entire network as follows:
two vehicles. Hence, the link reliability is:

8 1 s ∈ Nd
> t þT
<0 p R¼ : ð16Þ
0 else
r t ðl Þ ¼ ∫ f ðT ÞdT T p > 0 ð15Þ
>
:
t0
0 else where Nd represents the one-hop neighbor node set of desti-
nation node D. The reward value of an activity for all the
where f(T) is the probability function of the time interval T. neighbor nodes of the destination node is 1. In the learning
Novel self-adaptive routing service algorithm for application in VANET

process, the reward value that may be obtained from a transi- Table 2 Network parameter settings
tion from one state to another is indicated by the Q-value Q(s, Parameter Value
a)(s ∈ S, a ∈ A), which lies in the range [0, 1].
Size of topology (m) 1500 × 1500
Definition 3 Q-table: Each learning agent maintains a two- MAC standard IEEE 802.11 MAC (2 Mbps)
dimensional table, which is used to record the Q-values of Transmission range (m) 250
the reachable destination node and its one-hop neighbor Propagation model Two-ray ground
nodes. This two-dimensional table is called the Q-table Simulation time (s) 300
(shown in Table 1). CBR packet size (bytes) 512
In the Q-table, the first line contains the IDs of all possible Data rate (packets/s) 10
destination nodes, which are expressed as Di. The first column
contains the IDs of the one-hop neighbor nodes, which are
expressed as Ni. Q(D1, N1) represents the Q-value between Q-value, Q(s, a)(s ∈ S, a ∈ A). The standard Q-Learning func-
the node and the neighbor node N1 when it reaches the desti- tion is given as Eq. (17):
nation node D1. As shown in Table 1, the Q-table is a two-  
dimensional table, its size is determined by the number of Qs ðd; xÞ←Qs ðd; xÞ þ R þ γ⋅ max Qx ðd; yÞ ; ð17Þ
y∈N x
neighbor nodes and the number of destination nodes. It is
obvious that it has good scalability. The values in the Q- where Qs(d, x) is the Q-value to be updated, S is the node, x is its
table are updated by periodically exchanging beacon packets neighbor node, Nx is x‘s neighbor node, D is the destination
between nodes. The learning task is distributed to each node, node, R is the reward value, and max Qx ðd; yÞ is the maximum
which makes the algorithm quickly converge to the optimal y∈N x

path, and adjustments to changes in network topology can be Q-value between x and its neighbor node to the destination node
made in a timely manner. D. The discount factor γ is an important parameter because it
affects the reward that a node obtains for carrying out an activity
4.1.2 Learning process according to Eq. (17). Considering that link stability is an im-
portant parameter, the link reliability r(l) between nodes, which
The above definitions establish that every vehicle node is de- was calculated according to Eq. (15), was used as a discount
fined as a learning agent. Unlike traditional ways of learning, factor, that is, γ = r(l). In VANETs, the available bandwidth, as
each vehicle node has a Q-table. Nodes complete the task of an important parameter, determines the rate of packet transmis-
learning by exchanging beacon information and updating their sion. As defined in [28], the bandwidth BW can be calculated as:
Q-tables. The beacon packet sent by each node contains not n  SB  8
only its own speed, location, and other information, but also BW ðbpsÞ ¼ ; ð18Þ
T
the maximum Q-value of the neighbor nodes to the destination
node, i.e., the maximum value in a column (as shown in where n represents the number of packets that the node sends
Table 2). Assume that there is a VANET topology G = {V, and receives, SB is the size of the packet in bytes, and T is the
E} as shown in Fig. 2, where V = {A, B, C, ⋯, H} represents time interval. Assuming that the maximum available bandwidth
the set of vehicle nodes, and that for node A, its state space SA of the node is a fixed value defined as maxBW, the bandwidth
is the set of all nodes that do not contain A. Edge set E repre- factor can be calculated as:
sents a collection of nodes that can communicate directly in maxBF −BW
one hop range. Assume that as in Fig. 3, A is the source node, BF ¼ : ð19Þ
maxBF
and G is the destination node. Now the challenge is to find an
optimal path from the sending node A to the destination node
G using the self-learning approach.
Learning tasks are assigned to each vehicle node agent, and
the learning process is mainly updating the Q-table in the
agent and meanwhile updating the state activity pair of the

Table 1 Q-table
D1 D2 ...

N1 Q(D1,N1) Q(D2,N1) ...

N2 Q(D1,N2) Q(D2,N2) ...
... ... ... ...
Fig. 3 Model of the learning process
 D. Zhang et al.

As the factor that affects learning speed, the bandwidth beacon packet sent from node D, it forwards the maxi-
factor varies with changes in effective bandwidth and deter- mum Q-value and carries on the computation to update
mines the learning progress of each vehicle node. Equation QA(G, D). The same procedure will be performed when it
(17) can be modified to obtain a new heuristic function: receives beacon packets from other nodes. Through con-
  stant exchange of data packets, the results shown in Fig. 4
Qs ðd; xÞ←ð1−BF Þ⋅Qs ðd; xÞ þ BF⋅ R þ γ⋅ max Qx ðd; yÞ : ð20Þ will finally be obtained.
y∈N x
According to Fig. 4, the optimal path from A to G is easily
According to Eq. (20), the greater the number of hops, the found, i.e., the path with the biggest Q-value of its nodes is the
smaller the reward value. Hence, the final reward value is optimal path. As Fig. 4 shows, A → B → E → G is the path
based on the number of hops, the link reliability, and the with the maximum Q-value and therefore is the optimal path.
bandwidth. By adding bandwidth and link state, the optimal The dynamic update-and-save of the Q-table makes the algo-
path from source node to destination node can be obtained in rithm respond to dynamic changes in topology quickly and
the dynamic network. In Fig. 3, nodes E and F are one-hop with good reliability as well as robustness.
neighbor nodes of destination node G. According to Eq. (20),
the reward values from nodes E and F to destination node G 4.2 Description of the RSAR algorithm
can be represented as QE(G, G) and QF(G, G), respectively.
Considering the effects of link quality and bandwidth, it can This subsection describes the basic process of data packet
be determined that the final Q-values of QE(G, G) and QF(G, forwarding in the RSAR algorithm and then provides a de-
G) are 0.7 and 0.8, respectively. The neighbor nodes of D are tailed description of each stage.
A, B, C, E, F, and H. When D receives the beacon packets sent
from any neighbor, the data packets are parsed, and the max- 4.2.1 Basic transmission process
imum Q-value to the destination node G is extracted, taking F,
max Q F ðG; Y Þ. According to Eq. (20), calculate the corre- When the RSAR algorithm routes data packets, it performs the
y∈N F following three steps:
sponding Q-value, i.e., QD(G, F), and update the Q-table.
Obviously, QF(G, G) is the largest, and its value is 1, which 1. When a source node sends a data packet, it checks its
will be recorded in the beacon packet. A similar procedure own Q-table to see whether its first entry is the next
will be performed with data packets from other nodes; then hop node to the destination. If so, then it selects the
one particular column in the Q-table is updated. Considering neighbor node with the largest Q-value; if not, then it
bandwidth and link reliability and assuming that QD(G, F) = starts the route development process, which is de-
0.5 according to Eq. (20), the Q-tables of the other neighbor scribed in subsection 4.2.2.
nodes are updated, as shown in Fig. 4. As neighbor data 2. After the route has been developed, a basic path from the
packets are continually received, node D constantly modifies source node to the destination node has been obtained,
the maximum Q-value between node D and its neighbor nodes and the learning of some vehicle nodes is complete. To
in the Q-table. Similarly, when node D sends a beacon packet, find the optimal path of the whole network topology and
it traverses a particular column in the Q-table, finds the max- solve the network segmentation problem, the route main-
imum Q-value among node D and its neighbor nodes, and tenance process is started to maintain the end-to-end path
records and sends the Q-value. When node A receives the dynamically. The route maintenance process is described
in subsection 4.2.3.
3. Through the processes described above, the optimal path
of the entire network topology is established. When a
vehicle node receives/sends data packets, it implements
the first step; otherwise, it will implement the second step.

4.2.2 Route development process

At the beginning, when the source node sends a data packet to

the destination node, it checks the Q-table to see whether there
is a next-hop node to the destination node. It then finds a
neighbor node with the maximum Q-value to the destination
node and forwards the data packet to it. If there is no such
Fig. 4 Q-values to the destination node G as saved by each node node, it starts the route discovery process. The source node
Novel self-adaptive routing service algorithm for application in VANET

sends an R _ req data packet by broadcasting to the entire 5 Experimental tests

network and starts a path request timer, where R _ req records
the IDs of all the nodes that it passed through in the routing NS-2 was used to verify the performance of the RSAR algo-
process. When the destination node receives the first R _ req rithm proposed in this paper. The simulation environment
packet from the source node, it saves the packet, and subse- (scenario and parameter setting) will first be described,
quently received packets will be discarded. From the R _ req followed by a detailed analysis of the experimental results.
data packet, the destination node extracts the ID information
that it recorded and flips it, then generates an R _ rep data 5.1 Simulation environment settings
packet and writes the flipped path information into R _ rep.
After waiting for a time slot, it broadcasts the R _ rep data NS-2 was used to simulate the expe rimen t, a nd
packet to the nodes recorded in the flipped path. When a VanetMobiSim was used to generate a 1500 × 1500 square
recorded node receives the data packet, it modifies the next- topology, as shown in Fig. 5. The topology consisted of inter-
hop address, updates its Q-table, and sends out the packet sections and straight roads, where each road was set to two
through single-hop broadcast. Other non-destination nodes two-way lanes, traffic lights were set at three intersections, and
only modify their Q-tables and drop the packet when they the change time of traffic lights was 5 s. To highlight the
receive it. Until R _ rep is sent to the destination node, i.e., authenticity of the simulation, in the network environment,
the source node of R _ req, the source node cancels the request every vehicle node used an intelligent driving model (IDM),
timer while updating its Q-table. At this time, a path has been including changing lanes, overtaking, avoiding, and waiting.
found from the source node to the destination node, and the Q- The generated mobility model was added to NS-2. Table 2
tables of the nodes on the first path from source node to des- shows the basic NS-2 parameter settings. Over the whole net-
tination node are updated for the first time; their initial values work, 10 pairs of CBR data streams were randomly generated
in the Q-table are 0. to send packets with a size of 512 bytes, and the transmission
layer used UDP. The size of each beacon packet was calculat-
ed according to the transmitted information. To verify the
4.2.3 Route maintenance process performance of the RSAR algorithm effectively, two situa-
tions were set up to simulate the scenario in Fig. 5. In the first
When the first route path is established, the Q-table values situation: the number of nodes in the entire network was set to
of some nodes adjacent to the path are also updated. To a fixed value of 80, and the maximum speed of the vehicles
ensure that the path remains effective with dynamic ranged from 30 km/h to 90 km/h. In this situation, the discus-
changes in the network, it is important to start the route sion will focus on the effect of vehicle speed on the routing
maintenance process. The main purpose of the route protocol. The second situation can be described as follows: the
maintenance process is to maintain the Q-tables dynami- maximum speed of the vehicles was set to a constant 40 km/h,
cally and to solve the network segmentation problem. and the number of nodes varied from 60 to 120. In this situa-
Each node periodically broadcasts beacon packets to up- tion, the discussion will focus on the effect of vehicle density
date the Q-tables of neighbor nodes, where the beacon on the routing protocol. At the beginning of the experiment,
data packet is mainly composed of the position, speed, the nodes were randomly dispersed on different roads and
and max(Q − Value) of the node. max(Q − Value) was de- moved on a fixed route. Each simulation time was set to
scribed along with the learning process. To ensure update 300 s, each situation was run 20 times, the average value
effectiveness, the transmission delay of the beacon packet was taken, and the simulation results were compiled.
in the experiment was set to a random number in the
interval [0.5, 1]. The effective time of the destination node 5.2 Experimental results
is specified for the Q-table. If the time of a destination
node is longer than the specified time because it has not The RSAR algorithm proposed in this paper was compared
been updated, the destination node is considered invalid, with the GPSR algorithm [17], the SLBF algorithm [11], the
and the corresponding column of data is deleted. When a QLAODV algorithm [14], and the methods outlined in [22,
network partition emerges due to vehicle movement, 24, 26, 33, 37, 39]. These algorithms are all representative
RSAR uses a store-and-forward strategy and starts the routing algorithms. This comparison makes it possible to eval-
path request timer to broadcast an R _ req data packet. If uate the advantages and disadvantages of RSAR. In different
it does not receive the R _ rep data packet sent from the scenarios, through comparisons of packet delivery ratio, end-
destination node until the timer has expired, the destina- to-end delay, and number of hops, the results shown in Figs. 5,
tion node is considered to be unreachable, and the source 6, 7, 8, 9, 10, 11, and 12 were obtained. Figures 5, 6, and 7
node is informed to cancel the transmission; otherwise, show the comparisons in the first test case, and Figs. 8, 9, and
the routing path will be reestablished at the breakpoint. 10 show the comparisons in the second one.
 D. Zhang et al.

Fig. 5 Simulation topology

Figure 6 compares the relationship between packet delivery

ratio and speed. The packet delivery ratio is the ratio of the Fig. 7 End-to-end time delay versus speed
number of data packets received by the destination node to the
number of data packets sent by the source node. Figure 6 because of the need for maintenance of an end-to-end reli-
shows that, with increasing speed, the RSAR proposed in this able path, QLAODV must repair the path continuously
paper achieved a high and stable packet delivery ratio, with an with increasing speed, leading to a decline in the ratio.
average ratio greater than 90%. The packet delivery ratios of The packet delivery ratio of SLBF also declined because
the other three routing algorithms examined showed a sharp it is affected by topology changes and link stability is not
downward trend with increasing speed. This improvement fully considered. Due to its use of a greedy approach, it
was achieved because RSAR fully considered the influence was closer to the GPSR algorithm.
of speed changes on link reliability. By evaluating the links Figure 7 shows the relationship between end-to-end time
between nodes, the reliability of these links was determined, delay and speed, where the time delay is calculated only as the
and this information was used in routing decisions as a learn- average time taken by the destination node to receive valid
ing parameter of the Q-Learning algorithm. The packet deliv- data packets. Figure 7 shows that with increasing speed of the
ery ratio of GPSR declined most quickly due to its selection of vehicle nodes, the time delays of the four algorithms all pre-
the next hop node without considering link reliability and due sented a rising trend. The time delay of the RSAR algorithm
to its greedy mechanism. When the speed was less than proposed in this paper was between those of GSPR and SLBF
54 km/h, the packet delivery ratio of QLAODV was also and was relatively stable. When the maximum speed exceeded
greater than 90%, but when the speed exceeded 54 km/h, the 60 km/h, time delay of SLBF increased rapidly and became
ratio dropped sharply. Although it uses the Q-Learning model, greater than that of RSAR. This trend was caused by the

Fig. 6 Packet delivery ratio versus speed Fig. 8 Routing length versus speed
Novel self-adaptive routing service algorithm for application in VANET

Fig. 9 Packet delivery ratio versus number of nodes

Fig. 11 Average route length versus number of nodes

influence of topology changes and the need for recalculation

the average number of hops taken for valid data packets to
of the effective forwarding area or re-transmission mecha-
reach the destination. Figure 8 shows that the route length in
nism. Although RSAR was less affected by topology changes,
RSAR was less than that of QLAODV because it does not use
the path with maximum Q-value is bound to have the largest
the path transformation mechanism to maintain the whole
bandwidth, the most reliable link, and the shortest routing
path, and the forwarding decision is used only to choose the
length in this algorithm. The time delay of GPSR was the
node with maximum Q-value, so that its time delay is much
shortest because it only uses the greedy forwarding mode.
shorter than that of QLAODV, as shown in Fig. 7. Figure 8
The packet delivery ratio of GPSR had the lowest value be-
also shows that the RSAR proposed in this paper has a stable
cause it only uses the greedy mechanism, so that it immedi-
route length. This can be achieved because of the store-and-
ately drops packets when they fail to arrive. QLAODV also
forward mechanism and the maximum Q-value selection
uses the Q-Learning model, but increasing speed made it
mechanism, which ensures that each path selected is the
switch paths frequently to maintain the effective routing path.
shortest one. SLBF and GPSR both use a greedy approach
This meant that the time delay of packet delivery was greatly
to forward packets, but when the speed exceeds 60 km/h,
increased. From Fig. 7, the packet delivery ratio of RSAR was
under the influence of topology changes, the route length of
between 0.1 and 0.2 under the rapidly changing topology en-
SLBF increases; although GPSR does not use a reliable mech-
vironment. From Fig. 6, its packet delivery ratio was greater
anism, the number of hops reached the minimum value.
than 90%. It is necessary for these applications to transfer
large amounts of data.
Figure 8 shows the relationship between average route
length and speed, where the route length was calculated by

Fig. 12 NTO comparison among different methods: a the method

Fig. 10 End-to-end time delay versus number of nodes proposed here, b [22], c [24], d [26]
 D. Zhang et al.

Figure 9 shows the relationship between the packet de- computational complexity of the proposed method can be de-
livery ratio and the number of nodes. As the number of termined as O(n):
nodes increases, the packet delivery ratio in all four algo-
MC MC  
rithms shows a rising trend. When the number of nodes is NTO ¼ ∑ ∑ ξOcgði; jÞ þ ϖO t
ði; jÞ þ ð 1−ξ−ϖ ÞC ði; jÞ ;
de
ð21Þ
90, the packet delivery ratio of RSAR is greater than 90%, i¼1 j¼1

whereas that of QLAODV is 85%. Although these two

where MC is the number of vehicle nodes in each evaluation
algorithms are both based on the idea of Q-Learning,
group in VANET, such as MC = 10, 20, 30, 40, 50, or 60, which
RSAR fully considers link stability between nodes so that
means that there is a related number of vehicle nodes in a
the packet delivery ratio is greatly increased. Due to the
certain evaluation group in VANET. The integer parameters i
store-and-forward mechanism, the packet delivery ratio of
and j are the node indices of each evaluation group in VANET.
RSAR is much higher than that of SLBF and GPSR as the
Parameters ξ, ϖ are real weighting values, ξ, ϖ∈ [0, 1] and ξ +
number of nodes increases. Because SLBF uses the re-
ϖ ≤ 1, such that the default real values are ξ = 0.6, ϖ =
transmission mechanism, its packet delivery ratio is greater
than that of GPSR; but because it is greatly affected by 0.4.Ocg
ði; jÞ ; Oði; jÞ ; C ði; jÞ are the normalized real overhead values
t de

topology and the vehicle and the sending node are usually of vehicle nodes i and j for each evaluation group in VANET.
not on the same path, its packet delivery ratio is seriously Based on Eq. (21), from the relative results comparison of
affected and becomes lower than that of RSAR. existing methods and the method proposed here as shown in
Figure 10 shows the relationship between end-to-end Fig. 12 ((a) the proposed method, (b) [22], (c) [24], (d) [26]), it
time delay and the number of nodes. The packet delivery is evident that the method proposed here has better perfor-
ratio of RSAR gradually draws close to that of GPSR. The mance than those proposed in Refs. [22, 24, 26]. This guaran-
reason for this is that as the number of nodes increases, the tees high QoS (such as lower overhead, less complexity,
number of learning nodes in RSAR also increases, so that shorter delays, and transmission reliability) of VANET.
the path to the destination node is shorter and the time Therefore, according to the above results, the method pro-
delay is less. As the number of nodes increases, the time posed here has certainly improved on routing overhead, trans-
delay of QLADOV gradually draws close to that of RSAR, mission delays, rate of packet delivery, rate of losing packets,
but with fewer nodes, it is much larger than that of RSAR. throughput, and other performance metrics for VANET.
This behavior occurs because QLAODV spends much In addition, many relative comparisons have been per-
time on route maintenance. As the number of nodes in- formed with the methods proposed in [33, 37, 39]. These
creases, SLBF decreases slowly because it uses a timed relative comparison figures were not reported in this paper
broadcast mechanism that increases time delay. The time because the effects were similar to those shown in Fig. 12.
delay of all four algorithms shows a downward trend as
the number of nodes increases.
Figure 11 shows the relationship between the average route 6 Conclusions
length and the number of nodes. As the number of nodes
increases, the average route length of all four algorithms The routing service algorithm is a very important part of
shows a downward trend. This occurs mainly because the VANET. An efficient routing algorithm can greatly improve
number of effective forwarding nodes increases. The length the data transmission rate, so that many applications can be
of the path found by RSAR is shorter than that of QLAODV. run in VANET. To overcome the problems of dramatic topol-
The path lengths of RSAR, SLBF, and GPSR are close be- ogy changes and unreliable links caused by fast vehicle move-
cause SLBF and GPSR both use a greedy approach. As the ments in VANET, a reliable adaptive routing service algorithm
number of nodes increases, the next hop selected by RSAR is is proposed in this paper. First, the properties of vehicle mo-
closer to the farthest node. tion and the factors that make links unreliable were studied,
To show comprehensive comparative results for recent al- and the duration of a link was proved to have a log-normal
gorithms, extensive simulations and experiments have been distribution. Second, on the basis of this, a link reliability
conducted in this study to examine the performance of the calculation model was developed. The link reliability between
proposed method. The Normalized Transmission Overhead nodes was evaluated as a parameter and applied in the Q-
(NTO) was defined to analyze the complexity of the proposed Learning algorithm, following which the RSAR algorithm
method and its cost. The metrics for the degree of complexity was proposed. Finally, simulation experiments were conduct-
of the proposed method include context gathering overhead ed to evaluate the performance of four routing algorithms,
(Ocg) for VANET, transmission overhead (Ot) of data packets including packet delivery ratio, end-to-end time delay, and
among VANET nodes, and others. According to classical number of hops. The results showed that RSAR had a higher
computational complexity analysis methods [29–31], from packet delivery ratio under various conditions and a low trans-
the equations previously given in this paper, the degree of mission time delay. RSAR can effectively solve the problems
Novel self-adaptive routing service algorithm for application in VANET

caused by changes in topology through self-learning. 17. Song XD, Wang X (2015) New agent-based proactive migration
method and system for big data environment (BDE). Eng Comput
However, because the learning process is a kind of local dif-
32(8):2443–2466
fusion and there can be very many nodes participating in 18. Zhang DG, Wang X, Song XD (2014) A novel approach to mapped
selecting the route, the routing expense in a large network correlation of ID for RFID anti-collision. IEEE Trans Serv Comput
environment will be enormous. Hence, future work by the 7(4):741–748
19. Wang X, Song XD, Zhang T (2015) New clustering routing method
authors will be focused on the problem of routing expense.
based on PECE for WSN. EURASIP J Wirel Commun Netw
2015(162):1–13. https://doi.org/10.1186/s13638-015-0399-x
Acknowledgements This research work is supported by National Natural 20. Zheng K, Zhao D-x (2016) Novel quick start (QS) method for
Science Foundation of China (Grant No. 61571328), Tianjin Key Natural optimization of TCP. Wirel Netw 22(1):211–222
Science Foundation (No.13JCZDJC34600), CSC Foundation (No. 21. Wang X, Song XD, Li J, Chen YJ (2017) A kind of novel VPF-
201308120010), Major projects of science and technology in Tianjin based energy-balanced routing strategy for wireless mesh network.
(No.15ZXDSGX 00050), Training plan of Tianjin University Int J Commun Syst 30(6):1–15. https://doi.org/10.1002/dac.2889
Innovation Team (No.TD12-5016, No.TD13-5025), Major projects of 22. Zhu YN, Liu S (2016) Multi-radio multi-channel (MRMC) re-
science a nd technology for t heir services in Ti an jin source optimization method for wireless mesh network. J Inf Sci
(No.16ZXFWGX00010, No.17YFZC GX00360), the Key Subject Eng 32(2):501–519
Foundation of Tianjin (15JCYB JC46500), Training plan of Tianjin 131 23. Niu HL, Liu S (2017) Novel PEECR-based clustering routing ap-
Innovation Talent Team (No.TD2015-23). proach. Soft Comput 21(24):7313–7323
24. Hamed F (2018) Hybrid cost and time path planning for multiple
autonomous guided vehicles. Appl Intell 48(2):482–498
25. Zhou S, Tang YM (2018) A low duty cycle efficient MAC protocol
References based on self-adaption and predictive strategy. Mobile Netw Appl
23(4):828–839
1. Zhang DG, Li G (2014) An energy-balanced routing method based 26. Ma Z (2017) Shadow detection of moving objects based on multi-
on forward-aware factor for wireless sensor network. IEEE Trans source information in internet of things. J Exp Theor Artif Intell
Ind Inf 10(1):766–773 29(3):649–661
2. Zhang DG, Liu S (2017) Novel unequal clustering routing protocol 27. Chen J-q, Mao G-q (2018) Capacity of cooperative vehicular net-
considering energy balancing based on Network Partition & works with infrastructure support: multi-user case. IEEE Trans Veh
Distance for Mobile education. J Netw Comput Appl 88(15):1–9. Technol 67(2):1546–1560
https://doi.org/10.1016/j.jnca.2017.03.025 28. Zhang DG (2012) A new approach and system for attentive mobile
3. Zhao CP (2012) A new medium access control protocol based on learning based on seamless migration. Appl Intell 36(1):75–89
perceived data reliability and spatial correlation in wireless sensor 29. Zhang T, Zhang J (2018) A kind of effective data aggregating
network. Comput Electr Eng 38(3):694–702 method based on compressive sensing for wireless sensor network.
4. Seredynski, M., and P. Bouvry (2011) "A survey of vehicular-based EURASIP J Wirel Commun Netw 2018(159):1–15. https://doi.org/
cooperative traffic information systems". Conference Record - 10.1186/s13638-018-1176-4
IEEE Conference on Intelligent Transportation Systems:163–168 30. Zhang D-g, Ge H, Zhang T (2018) New multi-hop clustering algo-
5. Al-Sultan S (2014) A comprehensive survey on vehicular ad hoc rithm for vehicular ad hoc networks. IEEE Trans Intell Transp Syst
network. J Netw Comput Appl 37(1):380–392 7. https://doi.org/10.1109/TITS.2018.2853165
6. Zhang XD (2012) Design and implementation of embedded un- 31. Zhang T, Dong Y (2018) Novel optimized link state routing proto-
interruptible power supply system (EUPSS) for web-based mobile col based on quantum genetic strategy for Mobile learning. J Netw
application. Enterp Inf Syst 6(4):473–489 Comput Appl 2018(122):37–49. https://doi.org/10.1016/j.jnca.
7. Johnson DB (2002) DSR: the dynamic source routing protocol for 2018.07.018
multi-hop wireless ad hoc networks. Ad Hoc Netw:139–172 32. Asmae EG (2018) Energy efficient teaching-learning-based optimi-
8. Abbasi IA (2014) A traffic flow-oriented routing protocol for zation for the discrete routing problem in wireless sensor networks.
VANETs. EURASIP J Wirel Commun Netw 2014(1):1–14 Appl Intell 48(9):2755–2769
9. Jerbi M (2009) Towards efficient geographic routing in urban ve- 33. Sujoy R, Andrei S (2014) The multi-depot split-delivery vehicle
hicular networks. IEEE Trans Veh Technol 58(9):5048–5059 routing problem: model and solution algorithm. Knowl-Based
Syst 71(11):238–265
10. Liu J (2015) A survey on position-based routing for vehicular ad
34. Ma Z (2016) A novel compressive sensing method based on SVD
hoc networks. Telecommun Syst:1–16
sparse random measurement matrix in wireless sensor network. Eng
11. Li C (2015) A self-adaptive and link-aware beaconless forwarding
Comput 33(8):2448–2462
protocol for VANETs. Int J Distrib Sens Netw 2015(2):21–31
35. Liu S, Liu XH (2018) Novel dynamic source routing protocol
12. Eiza MH, Ni Q (2013) An evolving graph-based reliable routing (DSR) based on genetic algorithm-bacterial foraging optimization
scheme for VANETs. IEEE Trans Veh Technol 62(4):1493–1504 (GA-BFO). Int J Commun Syst 9. https://doi.org/10.1002/dac.3824
13. Yan G, Olariu S (2011) A probabilistic analysis of link duration in 36. Niu HL, Liu S (2017) Novel positioning service computing method
vehicular ad hoc networks. IEEE Trans Intell Transp Syst 12(4): for WSN. Wirel Pers Commun 92(4):1747–1769
1227–1236 37. Ahmed LS (2017) An adaptive cooperative caching strategy
14. Toutouh J (2012) Intelligent OLSR routing protocol optimization (ACCS) for Mobile ad hoc networks. Knowl-Based Syst 120(15):
for VANETs. IEEE Trans Veh Technol 61(4):1884–1894 133–172
15. Zhu YN (2012) A new constructing approach for a weighted topol- 38. Chen C, Cui YY (2018) New method of energy efficient subcarrier
ogy of wireless sensor networks based on local-world theory for the allocation based on evolutionary game theory. Mobile Netw Appl 9.
internet of things (IOT). Comput Math Appl 64(5):1044–1055 https://doi.org/10.1007/s11036-018-1123-y
16. Ke Z, Ting Z (2015) A novel multicast routing method with mini- 39. Liang JW, Ma MD (2018) A filter model for intrusion detection
mum transmission for WSN of cloud computing service. Soft system in vehicle ad hoc networks: a hidden Markov methodology.
Comput 19(7):1817–1827 Knowl-Based Syst 9. https://doi.org/10.1016/j.knosys.2018.09.022
 D. Zhang et al.

40. Abboud K, Zhuang W (2014) Stochastic analysis of a single-hop Technology, Tianjin, 300384, China; He is a visiting professor of
communication link in vehicular ad hoc networks. IEEE Trans School of Electronic and Information Engineering, University of
Intell Transp Syst 15(5):2297–2307 Sydney, Sydney, NSW 2006, Australia; His research interest includes
41. Liang YP (2013) A kind of novel method of service-aware comput- service computing, etc.
ing for uncertain mobile applications. Math Comput Model 57(3–
4):344–356 Ting Zhang (M’03) Born in 1973, Ph.D. candidate, a Member (M) of
42. Song XD, Wang X (2015) Extended AODV routing method based IEEE in 2003. Now he is a researcher of Tianjin University of
on distributed minimum transmission (DMT) for WSN. Int J Technology, Tianjin, 300384, China. Her research interest includes
Electron Commun 69(1):371–381 WSN, etc.

Xiaohuan Liu (M’12) Born in 1988, Ph.D. candidate, a Member (M) of

Degan Zhang (M’01) Born in 1970, Ph.D. Graduated from Northeastern IEEE in 2012. Now she is a researcher of Tianjin University of
University, China. Now he is a professor of Tianjin Key Lab of Intelligent Technology, Tianjin, 300384, China. Her research interest includes
Computing and Novel software Technology, Key Lab of Computer WSN, mobile computing, etc.
Vision and System, Ministry of Education, Tianjin University of