Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
Vol
.
5
,
No
. 3,
J
une
2
0
1
5
,
pp
. 59
9~
61
0
I
S
SN
: 208
8-8
7
0
8
5
99
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Probabilistic Road-Aware Geocast In VANETs
Zu
b
a
ir A
m
j
a
d
*
, Wa
ng
-C
heo
l
So
ng
**
Departement of
Computer Engin
eer
ing
,
Je
ju Na
ti
onal Univ
ersit
y
Jeju, South
Korea
Email: *xubair
amja
d@gmail.co
m, **philo@jeju
nu.ac.kr
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
Ja
n 19, 2015
Rev
i
sed
Ap
r
22
, 20
15
Accepte
d
May 8, 2015
Geocast is a co
mmunication technique to
disseminate information in specific
geographic regions instead of node addr
esses. Traffic cong
estio
n, acciden
ts,
loca
l haz
a
rds
and digit
a
l co
ntent s
h
aring
are pot
enti
al u
s
e cas
es
of
inform
ation s
h
ar
ing in VANETs
. Recen
tl
y, s
e
v
e
ral approa
ches
f
o
r geocas
t
routing hav
e
been proposed to
achieve
h
i
gh deliv
er
y
ratios.
These approaches
consider a
cen
ter point and r
a
diu
s
to defi
ne
the d
e
s
tinat
ion reg
i
on
als
o
ca
ll
ed
geocast reg
i
on.
They
fo
cus only
on rou
ting scheme to enhance the deliver
y
ratio and delay
s
. However, these approach
es
do not cons
ider the t
a
rget reg
i
on
selection problem in the ge
ocast routing
.
In this
paper, w
e
prop
ose a novel
appli
cat
ion-lev
e
l
m
echanis
m
for s
h
aring road c
o
nditions
, s
u
ch
a
s
accid
e
nts
,
detours and congestion in VANETs thr
ough probabilist
i
c road-
a
ware geocas
t
routing. W
e
assign probabilit
ies to the roads around each int
e
rse
c
tion in th
e
neighborhood ro
ad network of th
e source
vehicle. We then build
a spanning
tree of roads (from graph representation of
the road network) with
information source as th
e root node
. Nodes
below the roo
t
represent
junctions and edges represent
inter-
connecting
road segments. Messages
propagate along
the bran
ches
of the spannin
g
tree. The sp
anning tr
ee
repres
ents
the
geocas
t reg
i
on.
As
the information propag
a
tes down the
branches,
proba
bilit
y of
road a
s
geocas
t reg
i
o
n
decre
a
ses. Inf
o
rm
ation is
propagated until a threshold pro
b
ability
is reach
ed. Our method
also ensures
that messages
are not d
e
live
red
to irr
e
levant v
e
hicles irr
e
spective of
their
proximity
to th
e source. We
evaluate
our app
lication
through ex
tensive
and
real
istic sim
u
lat
i
ons in ns-3 si
m
u
lator using IDM car following a
nd MOBIL
lane
ch
ange m
o
d
e
ls for
rea
listi
c
modeling of v
e
h
i
cle mobility
.
Keyword:
Geoca
s
t
Location Se
rvice
Prob
ab
ility
Ro
ad d
a
ta
Tree
VA
NET
Copyright ©
201
5 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
W
a
ng-
Ch
eo
l So
ng
,
Depa
rt
em
ent
of C
o
m
put
er
En
gi
nee
r
i
n
g,
Jeju
Natio
n
a
l Un
i
v
ersity,
10
2 J
e
j
u
daeha
k
-
r
o
,
Je
j
u
-si
,
Je
ju
S
p
eci
al
Sel
f
-G
ov
er
ni
n
g
P
r
ovi
nce, R
e
p
ubl
i
c
of
K
o
rea
,
69
0-
7
5
6
Em
a
il: p
h
ilo
@j
ejun
u.ac.k
r
1.
INTRODUCTION
Recently, Vehicular Ad-Hoc
Networks (VANE
Ts)
ha
ve
receive
d m
u
ch interest from
autom
o
tive
industry and the researc
h
comm
unity
. VANETs are actively being used a
s
a
m
e
di
u
m
for
shari
n
g i
n
fo
r
m
at
i
on
am
ong
ve
hi
cl
es. A
d
di
t
i
onal
l
y
, V
A
N
ETs
ha
ve al
so
em
erged as
pract
i
cal
ap
pl
i
cat
i
on m
odel
fo
r
resear
ch a
n
d
devel
opm
ent
in t
h
e fi
el
d of
M
obi
l
e
Ad
-
h
o
c
Net
w
o
r
k
s
(
M
ANET
s
). M
a
jo
ri
t
y
of t
h
e wo
rk
do
ne f
o
r
M
ANET
s
can easily be
carried
over t
o
VAN
ETs
due to t
h
e similar im
ple
m
enta
t
i
on sce
n
ari
o
s of t
h
e t
w
o.
Som
e
VANETs a
p
plications addres
s issues of roa
d
safety
and im
proving drivi
ng e
x
peri
enc
e
because of accidents
,
hazardous conditions an
d c
o
nge
stion relate
d issues
while
othe
rs
a
r
e
built for e
n
tertai
nm
ent purpose
s
, e.g.
m
u
l
t
i
m
ed
ia co
n
t
en
t sh
aring
in
clud
ing
g
a
m
e
co
n
t
en
t fo
r entertain
m
en
t. [1
-4
] sho
w
works fo
r
d
e
liv
eri
n
g
safety
related
inform
a
tio
n
o
r
t
r
affic co
ng
estion
i
n
fo
rmatio
n
to
d
r
i
v
ers to
let t
h
em
d
r
iv
e m
o
re safely o
n
th
e
ro
ad
s,
an
d
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
59
9 – 6
1
0
60
0
[5-8
]
p
r
ov
id
e an
en
tertainmen
t b
y
en
ablin
g
in
teractive g
a
m
e
s, co
nten
t sh
aring
an
d d
i
ssem
i
n
a
tio
n
o
f
ad
v
e
rtisem
en
ts
to
in
terested clien
t
s.
For s
h
ari
ng r
o
ad i
n
f
o
rm
at
i
on wi
t
h
ot
her
ve
hi
cl
es, ge
ocast [9] is conside
r
ed be
ne
ficial
as it enables
t
h
e ve
hi
cl
es t
o
sen
d
i
n
f
o
rm
ati
on t
o
s
p
eci
fi
c
ge
og
ra
phi
c a
r
eas. Si
m
p
l
e
fl
oo
di
n
g
i
s
use
f
ul
as i
t
se
n
d
s
geoca
s
t
packet to eve
r
y node irrespe
c
tive of
target
region and receiver ve
hicl
es check whet
her they are in the
dest
i
n
at
i
o
n are
a
or n
o
t
.
I
n
di
r
ect
ed fl
o
odi
ng
[1
0]
, a ge
ocast
regi
o
n
(
G
R
)
i
s
defi
ne
d
wi
t
h
a cent
e
r p
o
i
n
t
and a
radi
us as t
h
e t
a
rget
regi
on. Packet
s ar
e f
l
ood
ed tow
a
rd
GR th
ro
ugh
fo
rw
ard
i
ng
zo
n
e
w
h
ich
h
a
s forw
ard
i
ng
n
o
d
e
s in
it.
In [1
1
-
1
4
]
aut
h
ors ha
ve pr
op
o
s
ed geoca
s
t
ro
ut
i
n
g
p
r
ot
ocol
s
t
o
di
ssem
i
nat
e
i
n
f
o
rm
at
i
on i
n
VA
NET
s
.
Howe
ver, thes
e prot
ocols sel
ect the GR as
a circular
or r
ect
ang
u
l
a
r re
gi
on
wi
t
h
a pre
d
efi
n
e
d
cent
e
r
poi
nt
.
Target re
gion s
e
lection affects
the
inform
ation availability am
ong all candi
date nodes as the distance bet
w
een
in
tersection
s
is v
e
ry sh
ort in
u
r
b
a
n
areas and
it is
to
o
large in
th
e h
i
g
h
ways. Using
a circular
or recta
n
gula
r
geoca
s
t
regi
on
wi
t
h
a fi
xed c
e
nt
er
poi
nt
an
d
radi
us can
affect th
e d
e
liv
ery ratio
in
h
i
g
h
way VANETs
d
u
e
t
o
t
h
e l
a
r
g
er
r
o
a
d
segm
ent
l
e
ngt
hs.
H
o
weve
r, i
t
can
be
ve
ry
usef
ul
i
n
t
h
e
u
r
ba
n
V
ANE
Ts
. It
i
s
i
m
port
a
nt
t
o
dissem
i
nate th
e releva
nt roa
d
inform
ation
a
m
ong all
nodes whic
h are
directed t
o
wa
rds haza
rdous
roa
d
s.
Selectin
g
a circu
l
ar reg
i
on
as GR in
creases th
e p
r
ob
ab
ility o
f
m
i
ssin
g
ou
t so
m
e
v
e
h
i
cles who
are d
i
rected
towa
rds
the
re
gion
whic
h
has
accident
or c
o
nge
stion.
In
ge
ocast
r
o
u
t
i
ng,
vehi
cl
es
br
oa
dcast
m
e
ssages t
o
wa
rds
GR
t
o
pr
opa
gat
e
i
n
f
o
rm
at
ion
.
I
n
m
a
ny
p
r
op
o
s
ed
g
e
o
c
ast rou
ting
pro
t
o
c
o
l
s [11
-
1
4
], th
e po
sitio
n in
fo
rm
atio
n
is u
s
ed
fro
m
GPS and
n
a
v
i
g
a
tion
syste
m
. The source ve
hicle sends the ge
oc
ast packet to
w
a
rds a
geo
g
r
ap
hi
c regi
on a
n
d
vehi
cl
es i
n
si
d
e
t
h
at
regi
on save that packet upon
receivi
ng. However, we believe
that
road inform
at
ion can
be
used, such as
num
ber o
f
l
a
n
e
s and
roa
d
I
D
s i
n
or
der t
o
p
r
o
v
i
d
e a
n
ef
fi
ci
ent
roa
d
-a
war
e
geocast
sc
he
m
e
. Num
b
er o
f
l
a
nes
o
n
a ro
ad
can b
e
u
s
efu
l
in
o
r
d
e
r to
fi
nd
p
r
ob
ab
ility o
f
cars on
a ro
ad g
o
i
ng
to
ano
t
h
e
r ro
ad
. Sin
c
e th
is
inform
ation can easily be available to all vehicles th
ro
u
gh
di
gi
t
a
l
m
a
ps, we pr
o
p
o
s
e a geoca
s
t
schem
e
whi
c
h
m
a
kes use
of
i
t
.
As
ve
hi
cl
es m
a
y
usual
l
y
ha
ve a
navi
gat
i
o
n sy
st
em
t
h
ese day
s
, i
t
i
s
assu
m
e
d t
h
at
ve
hi
cl
es can
figure
out thei
r roa
d
inform
a
tion as well as drivi
ng
information based
on their cu
rre
nt location recei
ved
by
GPS. Direction of
vehicles can be
c
o
nsidered
as
a
para
m
e
ter for t
h
is m
echanism
because
whe
n
som
e
in
fo
rm
atio
n
is g
e
n
e
rated
at a
p
a
rticu
l
ar po
int o
n
th
e ro
a
d
,
out
goi
ng
ve
hi
cl
es usual
l
y
hav
e
no i
n
t
e
rest
i
n
i
t
but
incom
i
ng ve
hicles can be i
n
terested in t
h
at inform
ati
on. E
v
ery inc
o
m
i
ng vehicle s
h
oul
d
recei
ve the relevant
inform
ation in
order to a
v
oi
d t
h
e
hazardous
s
cenari
o
s.
In
t
h
is ro
ad
-aware app
r
o
a
ch
,
we
p
r
op
o
s
e a prob
ab
ilit
y b
a
sed efficien
t g
e
o
cast tech
n
i
q
u
e
for
VA
NETs
. I
n
o
r
de
r t
o
a
ppl
y
t
h
e r
o
a
d
i
n
f
o
rm
at
i
on we
ha
ve
prese
n
t
e
d
r
o
ad
s as a spa
nni
ng
t
r
ee an
d de
fi
n
e
d h
o
w
an
d
wh
o
m
to
d
e
liv
er t
h
e info
rm
atio
n
in
the tree. Geo
cas
t region c
onsi
s
ts of
roa
d
s
directed towards the
inform
ation source
point s
u
c
h
as
an accide
nt or c
o
nge
sti
o
n
on
t
h
e roa
d
. In our work
we ha
ve
treat
ed
the
inform
ation source
point a
s
a
fixe
d
geogra
phical location
because
we e
xpect that ou
r propose
d
system can
be
pos
si
bl
y
use
d
fo
r i
n
f
o
rm
ati
on sha
r
i
n
g i
n
sa
fet
y
rel
a
t
e
d
cases and/
or
di
sa
st
er si
t
u
at
i
ons
onl
y
,
a
nd
we do
no
t
consider a situation where a
n
inform
ation s
o
urce m
a
ypersistently
m
ove
as
in the case of m
u
ltimedia
or gam
e
cont
e
n
t
s
h
ari
n
g
.
As real world VANET
exp
e
ri
m
e
n
t
atio
n
is proh
ib
itiv
ely exp
e
nsiv
e, we use NS-3
[15
]
si
m
u
la
tio
n
as
t
h
e fi
rst
st
ep t
o
eval
uat
e
ou
r s
o
l
u
t
i
o
n. N
S
-
3
pr
o
v
i
d
es real
i
s
t
i
c
im
pl
em
ent
a
t
i
on o
f
net
w
or
k pr
ot
ocol
st
ack base
d
on Li
n
u
x
ke
rn
el
im
pl
em
ent
a
t
i
on of t
h
e
pr
ot
oc
ol
st
ack. Furt
herm
ore,
wi
rel
e
ss m
odel
s
i
n
NS-3 a
r
e
m
o
re
realistic. It is
easy to
furth
e
r im
p
r
o
v
e
th
e
realis
m
b
y
i
n
co
rp
orat
i
n
g
ap
pl
i
cat
i
on,
p
r
ot
oc
o
l
st
ack
or
net
w
o
r
k
interface le
vel e
m
ulation by l
e
vera
ging its Direct Co
de Execution
(DCE) capa
b
ility. As NS-3 is
not t
a
ilore
d
for
VANET mo
b
ility scen
ario
s, we h
a
v
e
in
t
e
g
r
ated
ID
M
car fo
llowing
an
d MOB
I
L lane ch
ang
e
m
o
d
e
ls th
at
realistically
mi
mic
m
o
b
ility o
f
v
e
h
i
cles.
W
e
test th
e
work
in
g and
p
e
rfo
r
man
ce of
W
i
-Fi b
a
sed
i
n
fo
rmatio
n
shari
n
g
m
echani
s
m
over a
r
o
ad
net
w
or
k t
y
p
i
cal
of m
ode
rn
ur
ba
n ce
nt
er.
Th
e p
a
p
e
r
is org
a
n
i
zed
as fo
llo
ws: Sectio
n
2
in
trodu
ces t
h
e
rel
a
t
e
d
wo
r
k
a
n
d
Sect
i
o
n
3
d
e
scri
bes t
h
e
m
echani
s
m
pr
op
ose
d
i
n
t
h
i
s
pape
r.
I
n
Se
ct
i
o
n
4
,
we
prese
n
t
t
h
e
eval
uat
i
o
n
t
o
sh
o
w
t
h
e
pe
rf
orm
a
nce
of
o
u
r
syste
m
. W
e
con
c
lud
e
th
e paper in Section
5
.
2.
RELATED WORK
VA
NETs
are
d
i
ffere
nt
f
r
o
m
ot
her
ki
n
d
s
o
f
a
d
hoc
net
w
o
r
k
s
by
s
o
m
e
char
act
eri
s
t
i
c
s, suc
h
as
hy
bri
d
net
w
or
k arc
h
i
t
ect
ures,
no
de
m
ovem
e
nt
s and ne
w ap
pl
i
cat
i
on sce
n
ari
o
s [
1
6]
. VA
NE
T ro
ut
i
ng
pr
ot
oc
ol
s
can be
classified int
o
five cate
g
ori
e
s as follows
[17]: cluste
r b
a
sed ro
ut
i
n
g, ad-
h
oc
r
o
ut
i
n
g
,
b
r
oa
dcast
ro
ut
i
n
g
,
p
o
s
ition
b
a
sed rou
tin
g, and
g
e
o
c
ast rou
ting
.
In
v
a
ri
o
u
s
asp
ects,
VANETs h
a
v
e
sim
i
lar ch
aracteristics to
M
ANET
s
.
So
m
e
of t
h
e e
x
i
s
t
i
ng
pr
ot
oc
ol
s
o
f
M
A
NETs
are a
p
pr
op
ri
a
t
e fo
r
VA
NE
Ts b
u
t
m
o
st
o
f
t
h
es
e
achi
e
ve l
o
w pe
rf
orm
a
nce resu
l
t
s
due t
o
hi
ghl
y
dy
nam
i
c charact
eri
s
t
i
c
s of
VA
NETs
. B
r
o
a
dcast
r
out
i
n
g
i
s
t
h
e
m
o
st
used
pr
ot
ocol
i
n
VA
NE
Ts [
1
7]
b
u
t
i
t
causes
ba
nd
wi
dt
h
pr
o
b
l
e
m
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Prob
ab
ilistic Ro
ad-Awa
r
e Geo
c
ast In
VANETs
(Wa
ng-
Ch
eo
l Son
g
)
60
1
M
u
l
t
i
cast
i
s
a ro
ut
i
n
g sch
e
m
e
use
d
t
o
se
n
d
pack
et
s t
o
ra
n
dom
gr
ou
p
of
no
des
,
e.
g. al
l
no
des
w
ho
have
su
bsc
r
i
b
ed f
o
r a
part
i
c
ul
ar se
r
v
i
ce
[9]
.
Ge
ocast
can
be
defi
ne
d
by
a m
u
l
t
i
cast
gr
o
u
p
ha
vi
n
g
a
g
e
ograph
i
cal area as d
e
stin
atio
n
b
ecau
s
e
g
e
o
cast is a
sub
c
lass o
f
m
u
ltica
s
t. In
VANETs, g
e
o
cast sen
d
s d
a
ta
packets from
a
single source
vehicle to
all v
e
h
i
cles resid
i
ng
in
th
e d
e
stin
a
tion area called geocast re
gion (GR)
[18
,
1
9
]
. Targ
et v
e
h
i
cles v
a
ry d
u
e
to
t
h
eir mo
b
ility wh
ile th
e targ
et area re
m
a
in
s th
e same. Directed
Flo
o
d
i
ng
[1
0]
i
s
a
pr
o
p
o
se
d
geocast
pr
ot
oc
ol
t
h
at
al
l
o
ws
pac
k
et
f
o
r
w
ar
di
n
g
i
n
t
h
e
re
gi
o
n
whi
c
h i
s
cl
ose
r
t
o
t
h
e
dest
i
n
at
i
o
n t
h
a
n
t
h
e se
nde
r.
D
i
rect
ed fl
o
o
d
i
n
g n
o
t
o
n
l
y
defi
nes ge
ocast
re
g
i
on as t
a
r
g
et
re
gi
o
n
b
u
t
al
so d
e
fi
nes
fo
rwa
r
di
n
g
re
g
i
on
whi
c
h i
s
u
s
ed by
t
h
e
ve
hi
cl
es t
o
f
o
r
w
ard t
h
e pac
k
et
s. Ve
hi
cl
es can o
n
l
y
br
oa
dc
ast
t
h
e
m
e
ssages i
n
t
h
e f
o
r
w
ar
di
n
g
z
one
.
UG
A
D
[
12]
i
s
an ada
p
t
i
v
e
de
l
a
y
based
geoc
ast
pr
ot
oc
ol
de
si
gne
d f
o
r u
r
b
a
n en
vi
r
o
nm
ent
s
. Ve
hi
cl
es
br
oa
dcast
m
e
ssages i
n
t
w
o di
f
f
ere
n
t
fo
r
w
ar
di
ng m
odes de
pe
ndi
ng
on t
h
ei
r
l
o
cat
i
on.
Ve
hi
cl
es on i
n
t
e
rs
ect
i
o
n
s
h
a
v
e
h
i
g
h
e
r
p
r
io
rity o
f
reb
r
oad
casting
as co
m
p
ared
t
o
o
t
h
e
r
v
e
h
i
cles.
Th
ese
p
r
i
o
rities are assi
g
n
ed du
e t
o
bui
l
d
i
n
g
s
w
h
i
c
h bl
o
c
k t
r
a
n
sm
i
ssi
ons. T
h
e
du
al
m
ode hy
b
r
i
d
app
r
oac
h
i
s
ve
ry
effect
i
v
e i
n
ur
ba
n scena
r
i
o
s bu
t
it is no
t ro
ad
-aware lik
e
ou
r propo
sed so
lu
tio
n an
d lack
s
the
prob
ab
ilistic
efficien
cy wh
ich
we h
a
v
e
p
r
ov
id
ed.
Thi
s
schem
e
onl
y
foc
u
ses o
n
ur
ba
n scena
r
i
o
s and m
a
y
not
be effect
i
v
e i
n
hi
g
h
way
r
o
a
d
net
w
or
ks. T
h
e
t
a
rget
regi
on i
s
sel
ect
ed as a ci
rc
ul
ar
regi
on
w
h
i
c
h i
s
n
o
t
sui
t
a
bl
e
f
o
r s
h
a
r
i
n
g i
n
fo
rm
ati
on i
n
b
o
t
h
u
r
ban a
n
d
hi
gh
way
scenari
o
s.
Geo
SPI
N
[1
1]
i
s
an ap
pr
oa
ch f
o
r
ge
ocast
ro
ut
i
n
g base
d
on s
p
at
i
a
l
i
n
f
o
rm
at
i
on i
n
V
ANE
Ts.
It
pr
o
v
i
d
es a
geo
cast
ro
ut
i
ng m
e
t
h
o
d
ba
sed
o
n
dai
l
y
m
ovem
e
nt
s of
vehi
c
l
es. Eve
r
y
veh
i
cl
e keeps i
t
s
past
ra
w
d
a
ta of traj
ectories to
p
e
rf
orm clu
s
terizatio
n
tech
n
i
qu
e and
g
e
ts th
e
p
r
ob
abilit
ies o
f
it go
in
g
t
o
d
i
fferen
t
ro
ad
s.
These
probabil
ities are then
use
d
to
select the best relaye
r am
ong the c
a
ndi
date ve
hicles. Relayer vehicles
forward
th
e messag
e
wh
en
ever th
ey find
a v
e
h
i
cle w
ith
h
i
g
h
e
r prob
ab
ility o
f
go
ing
to
ward
s
g
e
o
c
ast reg
i
on
.
Thi
s
ap
p
r
oac
h
sho
w
s
ve
ry
eff
ect
i
v
e res
u
l
t
s
;
ho
we
ver
,
t
h
i
s
m
e
t
hod i
n
creas
es t
h
e com
put
a
t
i
ons a
nd
re
qui
res t
h
e
d
a
ily traj
ectori
e
s wh
ich m
a
y
n
o
t
b
e
av
ailab
l
e fo
r all the
v
e
h
i
cles in
an
y
particu
l
ar city.
Dy
nam
i
c Tim
e
-St
a
bl
e
Ge
ocas
t
R
out
i
n
g i
n
V
e
hi
cul
a
r
A
d
H
o
c
Net
w
or
ks
(
D
TS
G)
[
2
0]
ha
s p
r
o
p
o
se
d a
geoca
s
t
r
out
i
n
g sc
hem
e
t
o
i
n
f
o
rm
vehi
cl
e
s
o
n
a
pa
rt
i
c
u
l
ar hi
gh
way
a
b
o
u
t
ce
rt
ai
n e
v
ent
s
. G
T
S
G
assum
e
s
v
e
h
i
cles m
o
v
e
with
th
e sa
me v
e
lo
city wh
ich
is n
o
t
th
e case in
reality.
DTSG tak
e
s ad
v
a
n
t
ag
e
o
f
h
e
lpi
ng
vehi
cl
es (
V
ehi
c
l
e
s
m
ovi
ng i
n
t
h
e op
posi
t
e
d
i
rect
i
on) t
o
se
n
d
t
h
e m
e
ssage
t
o
di
ffe
re
nt
ve
hi
cl
es. The
r
e are t
w
o
p
h
a
ses in th
is
ap
pro
ach,
p
r
e-stab
le p
e
riod
an
d stab
le
p
e
riod.
In
pre
-
stabl
e
phase, ve
hicl
es broa
dcast
message
until it reache
s
at the end
region. Sta
b
le pha
se allows
t
h
e prot
oc
ol stabilization wit
h
in the
regi
on. These
pr
o
pose
d
geoc
ast
schem
e
s [11-
1
4
]
onl
y
f
o
c
u
s o
n
r
o
ut
i
ng
and
d
o
n
o
t
co
nsi
d
e
r
t
h
e
nec
e
ssary
r
o
ad at
t
r
i
b
ut
es
l
i
k
e di
rect
i
o
n a
nd l
a
nes
on t
h
e
roa
d
whi
c
h ar
e pi
v
o
t
a
l
fo
r r
e
duci
ng
si
g
n
i
f
i
c
ant
t
r
ansm
i
ssi
on o
v
e
r
hea
d
on
basi
s
of
rel
e
va
ncy
.
As ve
hi
cl
es g
o
i
ng i
n
op
p
o
si
t
e
di
rect
i
o
n ha
ve
no
need
o
f
t
h
i
s
i
n
f
o
rm
at
i
on, t
h
ese schem
e
s do
n
o
t
t
a
ke r
o
a
d
-a
war
e
ap
pr
oac
h
f
o
r
i
n
f
o
rm
at
i
on sh
ari
n
g i
n
V
A
N
E
T
.
In t
h
i
s
pa
pe
r,
we t
r
y
t
o
o
v
er
com
e
t
h
e abo
v
e
m
e
nt
i
oned p
r
obl
em
of
geoc
ast
regi
on
sel
ect
i
on.
In
o
u
r
sch
e
m
e
, ro
ad
s
are selected
as
g
e
o
c
ast reg
i
ons b
a
sed
on
th
e
p
r
ob
ab
ility o
f
t
h
e cars
o
n
a road
g
o
i
n
g
toward
s the
hazardous
roa
d
s. We descri
be the
eval
uation of
ou
r application in
Section 4 and s
h
ow t
h
e
results.
3.
PROB
ABILI
S
TIC RO
A
D
-
A
W
ARE GE
OC
AST
I
N
V
ANETS
Ex
istin
g
wo
rk ab
ou
t g
e
o
cast
in
VANETs
co
nsid
er
s only a center point and a ra
dius
as geocast
regi
on
. C
o
nsi
d
eri
n
g di
ffe
rent
roa
d
sce
n
a
r
i
o
s suc
h
as
u
r
ba
n,
hi
g
h
w
ay
o
r
m
ount
ai
no
us
r
o
ad
s, t
h
e
fi
x
e
d
radi
us
circle as geoca
s
t region is not
good approac
h
. In case
of a
n
accide
nt on the roa
d
,
every
car going towa
rds t
h
e
accident roa
d
shoul
d
get
the
inform
ation while for
t
h
e othe
r vehicles
going
a
w
ay
from
the accident, t
h
e
i
n
f
o
rm
at
i
on i
s
i
rrel
e
va
nt
. H
o
weve
r, o
p
p
o
s
i
t
e
di
rect
i
on ve
hi
cl
es can be use
d
t
o
fo
rwa
r
d t
h
e pack
et
s t
o
wa
r
d
s
t
h
e ge
ocast
re
gi
o
n
s.
A ci
rc
ul
ar ge
ocast
regi
on
ap
pr
oac
h
c
a
n
be i
n
e
ffect
i
v
e
on t
h
e
roa
d
s w
h
ere i
n
t
e
rs
ect
i
ons
have l
a
rge se
p
a
rat
i
on
di
st
anc
e
s.
W
i
t
h
t
h
e
s
e
consi
d
erat
i
o
ns
i
n
m
i
nd, i
n
t
h
i
s
pape
r,
we p
r
o
p
o
se a n
o
v
el
roa
d
-
aware
ge
ocast
mechanism
to shar
e ro
ad
inform
at
io
n
in VANETs.
We ass
u
m
e
that every
ve
hicle is equippe
d
with a
na
vi
gat
i
on
sy
st
em
. As t
h
ese
day
s
m
a
ny
ve
hi
cl
es
are eq
ui
p
p
e
d
wi
t
h
navi
gat
i
o
n sy
st
em
, we t
h
i
n
k t
h
i
s
as
su
m
p
ti
on i
s
re
as
ona
bl
e.
Fo
r t
h
e sake
of
si
m
p
l
i
c
i
t
y
,
we
consider t
h
e s
cenari
o
of an
accident
on a
roa
d
,as s
h
own in figure
1.
Obviously, ac
cident inform
a
tion is
releva
nt only to the
ve
hicles trave
lling in t
h
e
direction of the accident
poi
nt and shoul
d
be delivere
d
t
o
those
vehicles
only.
In our m
echanism
,
a vehicle
having the
informatio
n
,
b
r
o
a
d
c
asts it to
th
e neig
hb
oring
v
e
hicles.
Vehicles which receive
the
i
n
form
ati
on ca
n
discard t
h
at
inform
ation if th
ey
do not
reside in the
geocast
regi
on.
W
e
assign
priorities to differe
n
t sce
n
ari
o
s e.g.
if a
n
accide
nt occ
u
rs
on th
e roa
d
, inform
ation about it
g
e
ts th
e h
i
g
h
e
st p
r
iority wh
ile in
case o
f
co
ng
estion
on
th
e
ro
ad
, th
e
p
r
i
o
ri
ty o
f
th
is in
fo
rmatio
n
is lo
wer. In
case
th
e
m
e
ssag
e
b
u
ffer o
f
a v
e
h
i
cle
is fu
ll, in
fo
rm
a
tio
n
wi
th
h
i
g
h
pro
b
a
b
i
lity is g
i
v
e
n
h
i
g
h
priority.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
59
9 – 6
1
0
60
2
Fi
gu
re 1.
A
n
A
cci
dent
Occ
u
r
r
e
d On
A
R
o
a
d
Whe
n
inform
a
tion is ge
nerat
e
d due
to
proble
m
s
like traffi
c accidents,
it is relevant to
all vehicles
travelling
on t
h
at roa
d
. So,
all vehicles on the road
where an accide
nt takes place
need to re
ceive the
in
fo
rm
atio
n
with
ou
t ex
cep
tion
.
If a ro
ad
is
v
e
ry lon
g
witho
u
t
d
i
v
e
rg
en
ce lik
ero
a
d
s
in
mo
un
taino
u
s areas, th
e
i
n
f
o
rm
at
i
on sh
oul
d
be
del
i
v
e
r
ed
t
o
al
l
ve
hi
c
l
es rega
r
d
l
e
ss
of
t
h
e
di
st
ance
. I
n
ur
ba
n a
r
e
a
s, r
o
a
d
s
fre
q
u
ent
l
y
meet a junction after a s
h
ort distance;
there
f
ore the roa
d
inform
ation can be
sha
r
ed
onl
y in a s
m
all local area.
As a
special
case,
whe
n
a
traffic acci
dent occurs i
n
a
m
u
ltiple-level com
p
lex in
terchange, the ac
cide
nt
i
n
f
o
rm
at
i
on sh
oul
d
be
del
i
v
e
r
ed
t
o
al
l
ve
h
i
cl
es onl
y
o
n
t
h
e r
o
a
d
s
w
h
e
r
e t
r
a
ffi
c ca
n
be a
ffect
e
d
by
t
h
e
accident.
Our
geoca
s
t m
echanism
works as
follows. First, inform
ation is deliv
ered to all
vehicles
on the
sam
e
ro
ad
as th
e accid
e
n
t
with pro
b
ab
ility o
f
1
.
The
n
, we de
fi
ne ho
w
t
h
e
i
n
f
o
rm
at
i
on
can
be
s
h
ar
ed am
ong ve
hicles
on other
roads
c
o
nnected
via
in
tersection
s
.
As th
e nu
m
b
er o
f
lan
e
s
of road
s is
d
eci
de
d
base
d
on
t
h
e
expect
e
d
t
r
a
ffi
c load at the time of
th
eir con
s
tru
c
tio
n, we can
est
i
m
a
te th
e p
r
obab
ility o
f
wh
ich
ro
ad
a v
e
h
i
cle will select i
n
an
i
n
tersecti
o
n
b
y
usi
n
g t
h
e
num
ber
o
f
l
a
ne
s.
Let u
s
ex
p
l
ai
n
h
o
w to
calcu
late th
e p
r
ob
ab
ility
to
select a r
o
ad
after a j
unctio
n
u
s
i
n
g
fi
gu
re
2
as an
exam
ple. Four roa
d
s connect
ed to a junction
ha
ve diff
erent num
b
er of lanes res
p
ectively. If a
n
ac
cident
occurs
on roa
d
(1) a
n
d accide
nt inform
at
ion
is transm
itted,
all vehicles
he
ading to the ac
cident locati
o
n on the
sam
e
ro
ad
shou
ld
g
e
t th
e accid
en
t info
rm
ati
o
n with pro
b
a
bilit
y 1
,
b
u
t
fo
r
v
e
h
i
cles
on
o
t
her ro
ad
s
we
n
e
ed
to
k
now th
eir prob
ab
ilities o
f
enterin
g
in
t
o
ro
ad
(1
) acro
ss the j
u
n
c
tion
.
W
e
p
r
o
p
o
s
e to
cal
cu
late th
e p
r
obab
ility
u
s
ing
nu
m
b
er o
f
lan
e
s fo
r th
e ro
ad
.
As m
e
n
t
io
n
e
d
b
e
fore,
wh
en
a ro
ad
is b
e
ing
bu
ilt, its ex
p
ected
traffic load
is esti
m
a
ted
and
is tran
slated
to
th
e nu
m
b
er o
f
lanes.
S
o
,
w
e
pr
op
ose t
o
u
s
e t
h
e n
u
m
b
er o
f
lanes in
th
e
ro
ad,
an
d equ
a
tion
1 can
b
e
u
s
ed
to calcu
late th
e
p
r
ob
ab
ility.Equ
atio
n 1 expresses a sim
p
le ratio
of th
e
num
b
e
r o
f
lan
e
s fo
r a ro
ad
th
at a car sel
ects o
v
e
r all
po
ssib
l
e
ro
ad
s i
n
to
wh
ich
a car will en
ter from
th
e cu
rren
tly-rid
i
ng
roa
d
.
(1
)
In
figu
re
2
,
prob
ab
ility for a car to
en
ter
from ro
ad
(2
) i
n
to ro
ad
(1) can
be esti
m
a
ted
b
y
d
i
v
i
d
i
n
g
th
e
n
u
m
b
e
r
o
f
lan
e
s of ro
ad
(1)
by th
e nu
m
b
er
of to
tal lan
e
s
o
f
ro
ad
s
(1
), (3
),
(4
) and
(5), no
t
in
ro
ad
(2).
,
,
3
323
3
8
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Prob
ab
ilistic Ro
ad-Awa
r
e Geo
c
ast In
VANETs
(Wa
ng-
Ch
eo
l Son
g
)
60
3
Fi
gu
re
2. C
a
l
c
u
l
at
i
ng Pi
fo
r R
o
ad
s
Fi
gu
re
3.
A
Spa
nni
ng
Tree
R
e
prese
n
t
i
n
g R
o
a
d
s a
n
d J
unct
i
o
ns
The
n
, we can
say that the vehicles on roa
d
(1
) can receive
the inform
at
ion with proba
b
ilityp
1
= 1,
and
ve
hicles on roa
d
(2)
ca
n receive
it with probability
p
2
=
3/8.
I
n
t
h
e
s
a
m
e
w
a
y
,
p
3
=
1/
2 a
n
dp
4
=
3/7 ca
n
be calc
u
lated.
The
n
,
we ca
n
know that
whe
n
a
n
acci
dent
o
ccurs on
ro
ad (1
), v
e
h
i
cles o
n
ro
ad
s (2), (3
) an
d
(4
) are exp
ected
to
go
to ro
ad
(1) with
p
r
ob
ab
ilities 3
/
8
,
1
/
2
an
d
3
/
7
resp
ectiv
ely. Th
erefore, wit
h
tho
s
e
p
r
ob
ab
ilities,
we can
rep
r
esen
t th
e ro
ad
s u
s
in
g
th
e sp
ann
i
n
g
tree
in
fi
g
u
re
3
.
Also
,
we can
ex
ten
d
th
e t
r
ee
b
y
calcu
latin
g
p
r
ob
ab
ilities in
the sam
e
way.
Now
we
nee
d
t
o
c
onsi
d
er the
range t
o
s
h
are
the
i
n
fo
rm
at
i
o
n
by
ext
e
ndi
ng
t
h
e s
p
an
ni
ng t
r
ee t
o
m
o
re
in
tersection
s
.
As m
e
n
tio
n
e
d
,
we
n
e
ed
to
specify it in
term o
f
related ro
ad
p
r
o
b
a
b
ilities
p
i
. When we
c
a
lculate
it, we can
calcu
late ho
w m
u
ch
v
a
lid
informatio
n
is
p
r
esen
t
on
a
ro
ad
.
When
a
ro
ad
is
far fro
m
th
e ro
ad
wh
ere
t
h
e i
n
f
o
rm
at
i
on i
s
gene
rat
e
d
(we can cal
l
i
t
a source r
o
ad
) by
cr
ossi
ng m
a
ny
ju
nc
t
i
ons,
val
i
d
i
t
y
of t
h
e
in
fo
rm
atio
n
also
essen
tially d
ecreases. It can b
e
ex
presse
d
as a p
r
ob
ab
ility
fro
m
a
so
u
r
ce
ro
ad
to
a ro
ad
an
d
it
is co
m
p
u
t
ed
b
y
m
u
lt
ip
lyin
g
al
l
p
i
f
r
o
m
a sou
r
ce r
o
ad
t
o
a
cu
rre
nt
r
o
a
d
usi
n
g e
quat
i
o
n
2.
_
(2
)
We can say that vehicles on
a road
k
h
a
v
e
th
e p
r
o
b
a
b
ility
p
road_k
=
p
1
x…
x
p
k
whi
c
h i
s
pr
od
uct
of
p
r
ob
ab
ilities
p
i
o
f
ro
ads along
th
e p
a
t
h
f
r
o
m
t
h
e
r
o
o
t
to node
k
in t
h
e s
p
a
n
ning tree
. T
h
e
dept
h
of the t
r
ee can
b
e
un
limited
,
b
u
t
we li
m
i
t
i
t
u
sing
a thresho
l
d
p
r
ob
ab
ility. In
t
h
is p
a
p
e
r, we co
n
s
i
d
er
th
e ro
ad
s as
geo
cast
regi
on havi
n
g
p
road_k
> 0.0
5
f
o
r t
h
e s
a
ke
o
f
si
m
p
l
i
c
i
t
y
,
but
i
t
m
a
y
be deci
de
d di
f
f
e
r
ent
l
y
base
d
on i
t
s
im
port
a
nce
an
d em
ergency
.
As
we ca
n
see,
p
road_k
itself is
relev
a
n
t
to
t
h
e
g
e
n
e
rated so
urce in
fo
rm
atio
n
.
In
o
u
r
m
echani
s
m
,
we use i
t
t
o
c
o
nt
rol
ho
w m
u
ch
i
n
f
o
rm
at
i
on can
be s
h
are
d
t
o
nei
g
hb
o
r
ve
hi
c
l
es. A
ve
hi
cl
e hav
i
n
g
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
59
9 – 6
1
0
60
4
roa
d
i
n
fo
rm
at
ions
ha
res i
t
by
peri
odi
cal
l
y
b
r
oa
dcast
i
n
g i
t
.
W
h
e
n
a
ve
hi
cl
e
A
m
eet
s
anot
her
ve
hi
cl
e
B
,
A
will
g
e
o
c
ast ite
m
I
to
B
with prob
ab
ility
p
r
(
k
):
p
r
(
k
) =
p
road_k
(3
)
The
vehicles t
h
at ha
ve receive
d t
h
e information decide
s whethe
r it will be stored or
droppe
d
depe
nding upon its status such as
available me
m
o
ry in the receive buff
er.
W
e
defi
ne the deletion probability
p
d
(
k
) in
a sim
i
lar
way
:
p
d
(
k
)
= 1 -
p
road_k
(4
)
Whe
r
e
k is t
h
e road num
b
er, t
h
e re
plicated info
rm
atio
n
can
b
e
assign
ed a
p
r
i
o
rity lev
e
l using
p
r
ob
ab
ility an
d h
a
n
d
l
ed
acco
r
d
i
ng
ly.
In t
h
is
way,
we
have
creat
ed a
ne
w m
e
thod t
o
s
p
ecify a ge
ocast region
with the road-awa
re
approachi
n
a VANET
by taki
ng
in
to
accou
n
t
ro
ad
in
fo
rmatio
n
rath
er
t
h
an
distance from
the source. As an
exam
ple, we c
onsi
d
er t
h
e cas
e in figure 4.
As the acci
de
nt
occurs in t
h
e
center
of a
roa
d
, a
n
alert s
h
ould
be
delivere
d
to all the ve
hicles coming towards t
h
e accide
nt
point
from
both sides. We
ca
n c
a
lculate proba
b
ility
p
i
of t
h
e roa
d
s with
respect to the
accide
nt
poi
nt. Fi
gure
5 showsproba
bility pi for
eac
h roa
d
i in fi
gure
4.
Fig
u
re 5
also sh
ows assumed
p
r
o
b
a
b
ilities assig
n
e
d
to
ex
tend
ed
ro
ads in
ord
e
r to
d
e
m
o
n
s
trate th
e
com
put
at
i
on o
f
p
road_k
. Th
e final p
r
ob
ab
ility
t
r
ee is sh
own
i
n
Figu
re 6. The d
e
p
t
h
o
f
th
e
tree is li
mi
ted
b
y
th
e
t
h
res
hol
d 0.
05
i
.
e., pr
oad
_
k
> 0.
05
.
T
h
e dept
h
ca
n be
i
n
c
r
ea
sed or dec
r
eas
ed by
ch
o
o
si
n
g
a
di
f
f
ere
n
t
val
u
e
f
o
r
th
e thr
e
sho
l
d dep
e
nd
ing
on
the application s
cenari
o
.
Fi
gu
re
4.
A
n
E
x
am
pl
e Whe
n
an
Accide
nt Occurs
on
A R
o
ad
Fi
gu
re
5.
pi
C
a
l
c
ul
at
ed f
o
r R
o
ads i
n
Fi
gu
re
4
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Prob
ab
ilistic Ro
ad-Awa
r
e Geo
c
ast In
VANETs
(Wa
ng-
Ch
eo
l Son
g
)
60
5
Figure 7 s
h
ows the selected geoc
a
s
t regi
on after an accident as
shown i
n
figure 4. Me
ssages a
r
e
pr
o
p
agat
e
d
al
on
g t
h
e s
p
an
n
i
ng t
r
ee
w
h
i
c
h i
s
l
i
m
i
t
e
d b
y
t
h
e t
h
re
sh
ol
d. T
h
e sel
ect
e
d
geocast
re
gi
on
i
s
highlighte
d
as
well as the accident point.
Our roa
d
-a
wa
re geoca
s
t approach is
di
ffe
re
nt from
other
geoca
s
t
m
e
t
hods i
n
t
e
r
m
of sel
ect
i
on
of t
h
e
GR
.
As
i
t
can be
cl
earl
y
seen f
r
o
m
t
h
e fi
g
u
re
7
,
t
h
at
o
n
l
y
rel
e
va
nt
roa
d
s
are being selec
t
ed for the m
e
ssage ge
ocasti
ng. Roa
d
s
going a
w
ay from
the accide
nt are excluded from the
geoca
s
t
re
gi
o
n
.
Fi
gu
re
6.
p
r
oa
d
_
k
i
n
a
S
p
an
ni
ng
t
r
ee
fo
r
pr
o
a
d_
k>
0.
0
5
Fi
gu
re
7.
Sel
e
c
t
ed Ge
ocast
R
e
gi
o
n
a
f
t
e
r S
p
a
n
ni
n
g
T
r
ee C
a
l
c
ul
at
i
o
n
4.
E
X
PERI
MEN
T
ATION
In
out sim
u
lations
, we
have
assum
e
d the situa
tion
of a
traffic accide
nt where acci
dent ve
hicle
ori
g
inates the
messages. Ot
her ve
hicles accept these m
e
ss
ages accordi
ng to their ro
a
d
proba
b
ility and forwa
r
d
it to
th
eir
n
e
igh
bors.
Veh
i
cles with
prob
ab
ility less th
an
th
e thresh
o
l
d
valu
e do
no
t accep
t th
e m
e
ssag
e
s as
t
h
ey
d
o
n
o
t
re
si
de i
n
t
h
e ge
ocast
re
gi
o
n
.
I
f
a
vehi
cl
e ca
nn
ot
fi
nd
a ne
i
g
h
b
o
r
t
o
f
o
r
w
ard t
h
e m
e
ssage, i
t
di
scar
ds t
h
e m
e
ssage a
f
t
e
r i
t
s
l
i
f
e t
i
m
e
defi
ne
d
by
t
h
e
so
urce
ve
hi
cl
e.
The s
o
urce
ve
hicle ge
nerates
a warning m
e
ssage
with a lifetim
e (TTL).
The m
e
ssage is sta
m
ped
with
its tim
e
o
f
creation
and
is i
d
en
tified b
y
a un
iqu
e
I
D
.
Ve
hi
cl
es c
ont
i
n
u
o
u
s
l
y
se
nd
nei
g
hb
or
di
sco
v
ery
beacons
or hel
l
o m
e
ssages to discove
r
nei
g
hbors.
When
e
v
er
a vehicle discovers
a
nei
g
hbor, it forwards the
av
ailab
l
e
m
e
ssag
e
to
th
at v
e
h
i
cle d
e
p
e
nd
ing
on
th
e ro
ad
p
r
o
b
a
b
ility o
f
th
e n
e
igh
bor v
e
h
i
cle. Ro
ad
in
fo
rm
atio
n
o
f
n
e
ig
hbo
r
v
e
h
i
cle is av
ailab
l
e in
h
e
llo
m
e
ss
ag
es. If n
e
i
g
hbo
r
v
e
h
i
cle h
a
s
p
r
ob
ab
ility les
s
th
an
t
h
e t
h
res
hol
d, t
h
e
nei
g
h
b
o
r
i
s
not
i
n
si
de
t
h
e
geoca
s
t
re
gi
o
n
.
The
m
e
ssages are
n
o
t
f
o
r
w
a
r
ded
t
o
t
h
e
ve
hi
cl
es
outsi
de GR. T
h
e
se
nding ve
hicle
prioritizes the order
in
which m
e
ssages a
r
e s
h
are
d
according t
o
a
re
plication
pol
i
c
y
.
The re
pl
i
cat
i
on p
o
l
i
c
y
det
e
r
m
i
n
es in w
h
i
c
h o
r
de
r
m
e
ssages are repl
i
cat
ed w
h
e
n
t
w
o ve
hi
cl
es
com
e
wi
t
h
i
n
t
h
e ra
d
i
o ra
nge
o
f
ea
ch ot
her
.
B
u
ff
er o
n
eac
h ve
hi
cl
e i
s
peri
od
i
cal
l
y
eval
uat
e
d t
o
det
e
rm
i
n
e t
h
e
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
59
9 – 6
1
0
60
6
messag
e
s to
delete. Th
is is to
p
r
ev
en
t bu
ffers
fr
om
fi
l
ling
u
p
. Del
e
t
i
on
fu
nct
i
o
n d
e
pen
d
s
on t
h
e
roa
d
p
r
ob
ab
ility. Hig
h
ro
ad
(rep
licatio
n
prob
ab
ility)
m
ean
s less
d
e
letio
n
p
r
o
b
a
b
ility an
d
is co
m
p
u
t
ed
as 1
-
P
road_k
w
h
er
e
ro
a
d
is
n
u
m
b
e
r
of
th
e r
o
ad
and
P
(
P
r
o
ad_k
)
∈
[0, 1]. The buffer
is
a
l
so
e
v
aluate
d upon each enc
o
unter
with
an
o
t
h
e
r
no
d
e
and
if t
h
ere is still a n
eed
to
free
t
h
e
bu
ffer, th
e
o
l
d
e
st
m
e
ssag
e
s are d
i
scard
e
d
.
M
e
ssag
e
s
are delete
d followi
ng one
of the follo
wing
policies. 1) Mes
s
age
d
lifetim
e
as suggest by
TTL e
xpire
s 2) Node
b
u
ffer
b
e
co
m
e
s fu
ll 3) Prob
ab
ility o
f
th
e v
e
h
i
cle is less th
an
thresh
o
l
d
p
r
ob
ab
ility.
4.
1.
Simulati
on E
n
vironment
We e
v
al
uat
e
p
e
rf
orm
a
nce o
f
roa
d
-a
wa
re
ge
ocast
ove
r a
st
reet
m
a
p t
y
pi
cal
of
r
o
a
d
s i
n
a m
e
t
r
opol
i
s
.
Ro
ad
s con
s
ist o
f
m
u
lti-lan
e
directio
n
a
l h
i
g
h
ways with
turns an
d
i
n
tersecti
o
n
s
.
W
e
g
e
n
e
rate realistic
mo
b
ility
p
a
ttern
of v
e
h
i
cles u
s
ing
In
tel
lig
en
t Driv
er
Mo
d
e
l
(IDM)
[2
1
]
car fo
llo
wi
n
g
and
MOB
I
L (Min
im
iz
in
g Ov
eral
l
B
r
aki
n
g I
n
duc
ed by
Lane c
h
ange
) [
22]
l
a
n
e
chan
ge m
odel
s
. IDM
i
s
a t
r
affi
c fl
o
w
m
odel
and t
h
e deci
si
on o
f
any vehicle dri
v
er to accelera
t
e or to bra
k
e depe
nds
only on
his or he
r own speed, and on the position and
spee
d
of
t
h
e
"l
eadi
n
g
ve
h
i
cl
e" im
m
e
di
at
el
y
ahead.
H
o
we
ve
r l
a
ne
chan
gi
n
g
deci
si
ons
de
pe
nd
o
n
al
l
neighboring ve
hicles. Vari
ous
IDM param
e
ters
s
u
c
h
as
de
s
i
red velocity, maxim
u
m
acceleration a
n
d
braking,
m
i
nim
u
m
gap,
and
t
h
e m
i
nim
u
m
t
i
m
e
headway, etc
., ca
n be c
u
stom
ized
th
ro
ugh
an
XML co
nfigu
r
atio
n
file.
During eac
h st
ep, t
h
e
Highwa
y object
p
a
sses in
fo
rm
atio
n
to th
e
IDM m
o
del ab
ou
t the
v
e
h
i
cle in
fron
t an
d th
e
m
odel determ
ines
what the c
u
rrent acc
elera
tion s
h
oul
d
be.
High
way
related
d
e
tails su
ch as h
i
g
h
way id, nu
m
b
er
of lan
e
s,
d
i
rection
,
len
g
t
h, turn
v
e
lo
cities etc.,
are s
p
ecified
using
XML. Hi
ghway c
o
nn
ect
ions a
r
e c
r
eated
by de
fining
asso
ci
at
ed
fr
o
n
t
, bac
k
, l
e
ft
a
n
d ri
ght
h
i
gh
ways. Vehicle are g
e
n
e
rated
(acco
r
d
i
ng
t
o
th
e
d
e
si
red
den
s
ity) b
y
d
e
fin
i
ng
starting
h
i
g
h
way and
m
u
ltip
le
destination hi
ghways.
Weight can
be ass
i
gne
d to distri
bute
perce
n
ta
ges of
gene
rate
d ve
hicles on each
d
e
stin
ation
ro
ad
.
Figu
re 8 shows the ro
ad
n
e
twork we used in
th
e sim
u
latio
n
s
.
We ha
ve im
pl
em
ent
e
d ou
r r
o
a
d
-a
ware
geoca
s
t
m
echani
s
m
for V
A
N
ETs
us
i
ng N
S
-
3
. Ve
hi
cl
es are con
f
i
g
ure
d
t
o
m
ove wi
t
h
40
-1
2
0
km
/
h
speed t
o
war
d
s ran
dom
l
y
chos
en
dest
i
n
at
i
ons
usi
n
g sh
ort
e
st
pat
h
w
h
i
c
h i
s
cal
cul
a
t
e
d usi
ng
di
j
k
st
ra'
s
al
go
ri
t
h
m
.
W
e
devel
ope
d a
roa
d
-a
ware
g
e
ocast
ap
pl
i
cat
i
on t
h
at
creat
es an
d
peri
odi
cal
l
y
br
oadca
s
t
s
m
e
ssages. Eac
h
m
e
ssage co
nsi
s
t
s
of
m
e
ssage ID, T
TL, t
i
m
e
st
am
p
,
sou
r
ce ve
hi
cl
e ID
,
coo
r
di
nat
e
s
of
t
h
e s
o
urce
ve
hi
cl
e,
geo
g
ra
p
h
i
c
re
gi
o
n
i
n
f
o
rm
ati
on
(GR
r
o
ad
I
D
s
)
a
n
d
a m
e
ssage.
We al
s
o
i
m
p
l
e
m
en
ted
a g
e
o
cast rou
t
er
ap
p
lication
th
at i
m
p
l
e
m
en
ts b
r
o
a
d
cast an
d deletio
n
po
licies.
Fig
u
re
8
.
Ro
ad Network Used in
Sim
u
latio
n
s
We create two v
e
h
i
cle m
o
b
ility scen
ario
s as sh
own
in
Tab
l
e 1
.
We use OFDM 6
M
bp
s data rate for
wi
rel
e
ss
l
i
n
ks (
W
i
-
Fi
a
d
h
o
c m
ode)
an
d radi
o
t
r
a
n
sm
i
t
pow
er
as 2
1
dB
m
wi
t
h
Naka
gam
i
cha
nnel
fa
di
n
g
.
B
o
t
h
t
r
ansm
i
t
and re
cei
ve ant
e
n
n
a
gai
n
s are
fi
xe
d
at
2 dB
i
.
Ener
gy
det
ect
i
on t
h
resh
ol
d i
s
set
t
o
-1
0
1
dB
m
.
Tabl
e 1
sho
w
s t
h
e si
m
u
l
a
t
i
on pa
ram
e
t
e
rs use
d
i
n
o
u
r
sim
u
l
a
t
i
ons.
We use f
o
ur
ve
hi
cl
e densi
t
y
scenari
o
s nam
e
ly
sm
all
(2
0
0
vehi
cl
es)
,
m
e
di
u
m
(35
0
vehi
cl
es)
,
l
a
r
g
e
(
5
0
0
ve
hi
cl
es)
an
d
very
l
a
r
g
e
(
7
0
0
ve
hi
cl
es)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Prob
ab
ilistic Ro
ad-Awa
r
e Geo
c
ast In
VANETs
(Wa
ng-
Ch
eo
l Son
g
)
60
7
Tabl
e 1. Si
m
u
lat
i
on
Sce
n
a
r
i
o
s
Scenario 1
Speed (KPH
)
Nu
m
b
er
of vehicles
70
200
350
500
700
100
200
350
500
700
Scenario 2
Nu
m
b
er
of vehicles
Speed (KPH
)
350
40
70
100
120
500
40
70
100
120
Tabl
e 2. Si
m
u
lat
i
on param
e
t
e
rs
Co
m
m
unication
Si
m
u
lator NS
3
M
odulation schem
e
OFDM
T
r
ans
m
ission power
21 dB
m
T
r
ans
m
ission r
a
te
6 M
bps
E
n
er
gy
detection thr
e
shold
-
101 dB
m
Vehicular T
r
af
f
i
c
Mobility Model
IDM
L
a
ne Change M
odel
M
O
BIL
Road Scenario
Highway
Nu
m
b
er
of lanes
Rando
m
Vehicular
Density
10 to 50 vehicle/k
m
Vehicle Speed
40 to 120 km
/h
We sim
u
late a
single source
point. The accident ve
hicle ge
nerates and broa
dca
s
ts warning m
e
ssage
every
seco
n
d
. Al
l
vehi
cl
es br
oadca
s
t
1 ho
p hel
l
o
m
e
ssages every second. Hello
m
e
ssages signal a vehicle
'
s
prese
n
ce a
n
d
d
e
si
re t
o
get
a c
opy
of
wa
rni
n
g m
e
ssages bei
n
g
sha
r
e
d
i
n
i
t
s r
o
ad
w
h
i
c
h c
a
n
be ge
ocast
r
e
gi
o
n
of
t
h
e war
n
i
n
g m
e
ssage.
4.
2.
E
val
u
a
ti
on
In t
h
e fi
rst
se
ri
es of
si
m
u
l
a
ti
ons,
we si
m
u
l
a
te ou
r a
p
p
r
oac
h
fo
r t
w
o di
ffe
r
e
nt
spee
ds a
n
d
4 di
ffe
rent
vehicle de
nsities.
W
e
eval
uate feasibility an
d success
of
road-a
ware ge
ocast for di
ffe
re
nt roa
d
levels. Roa
d
levels are de
fi
ned as t
h
e roa
d
s after t
h
e intersecti
ons
. F
o
r exam
pl
e, 3r
d r
o
ad
le
vel means there a
r
e two
intersections between the source vehicl
e roa
d
and the curre
n
t roa
d
.
W
e
us
e
ro
ad
lev
e
ls fro
m
the spanning tree
and e
v
aluate the success
f
ul message
delivery ratio for eac
h
road le
vel. Fi
gure 9 a
n
d 10
show that
our
schem
e
successfully delivers the m
e
ssages to ve
hi
cles on th
e roads usi
ng the
proba
b
ility b
a
sed ge
ocast region
selectio
n
.
In
bo
th
th
e scen
ario
s, d
e
liv
ery ratio
is ar
ou
nd
40% f
o
r t
h
e
4t
h l
e
vel
of
r
o
ad
s. As we
use t
h
e
th
resh
o
l
d
p
r
obab
ility 0
.
0
5
,
on
ly first 4
ro
ad
lev
e
ls ar
e selected
as g
e
ocast reg
i
on
s.
Ro
ad
s after the 4
t
h
intersection are excluded
from the ge
o
cast
reg
i
on
d
u
e
to th
e th
resh
o
l
d
.
Deliv
ery rati
o
in
creases wi
th
th
e
increase in
ve
hicle density. Whe
n
the
vehi
cle traffic is
sp
arse, th
e d
e
li
v
e
ry ratio
is decreased
beca
use there
are fewe
r ve
hicles to forward the m
e
ssages. Sim
ilarly,
t
h
e d
e
liv
ery ratio
d
ecreases
with
th
e in
crease in
vehicle s
p
ee
ds.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
59
9 – 6
1
0
60
8
Fig
u
r
e
9
.
D
e
liver
y Ratio
w
i
t
h
7
0kp
h Sp
eed
Fig
u
r
e
10
. D
e
liv
er
y
Ratio
w
i
t
h
1
00k
ph
Sp
eed
In the second
scenari
o
we si
m
u
la
te our
roa
d
-a
ware
ge
oca
s
t
m
echanism
for 4
differe
n
t
speeds of
vehi
cl
es as i
n
Tabl
e 1
.
Fi
g
u
r
e 11
an
d
12 s
h
ow t
h
e res
u
l
t
s
of
our sim
u
lations
and it can
be clearly seen that
increasing
the spee
d while keeping
t
h
e vehicle
density
con
s
tan
t
, d
e
crease th
e
d
e
liv
ery
ratio
.
In
Fi
g
u
re 11
d
e
liv
er
y r
a
tio
o
f
d
i
f
f
e
r
e
n
t
v
e
h
i
cle sp
eeds with
3
5
0
v
e
h
i
cles is d
e
scr
i
b
e
d
.
O
u
r
app
r
o
a
ch
d
e
liv
er
s ar
ound
30
%
w
a
rn
ing
m
e
ssag
e
s to th
e
4
t
h
lev
e
l o
f
ro
ad
s
f
r
o
m
th
e sp
ann
i
ng
tr
ee. Ratio
o
f
d
e
liv
er
ed m
e
ssag
e
s is ar
ound
8
0
% for th
e
first lev
e
l o
f
ro
ad
s wh
ich
sh
ows th
at our ro
ad
-aware
geo
cast m
ech
a
n
ism
ex
h
i
b
its h
i
g
h
per
f
o
r
m
a
nce i
n
hi
g
h
w
ay
V
A
N
ET.
Fi
gu
re 1
1
. Del
i
v
ery
R
a
t
i
o
wi
t
h
35
0 Ve
hi
cl
es
Evaluation Warning : The document was created with Spire.PDF for Python.