Information Technology Reference
In-Depth Information
Ta b l e 1 .
High level steps and actions of the search algorithm
#
Step
Action(s)
Check if a
v ∈ N
is a destination. Add
v
to
P
and terminate if true or continue
otherwise
1
Check
necessity
of
Single
Source
Shortest Path computation
2
Solve single-source shortest path prob-
lem on
G
Change weights of edges in
G
accord-
ing to number of mappings of vertices
∈ N
to edges
∈ G
. Use Dijkstra's Al-
gorithm to compute the shortest path
from source to destination
Calculate estimated weights
∀v ∈ N
to
the start vertex of their mapped edges in
G
3
Update neighbor weights
4
Calculate edge weights between
v ∈ P
and
v ∈ N
Prefer vertices with minimal edge
weight between virtually drawn edges
between vertices
v ∈ P
and vertices
v ∈ N
. Weight the result with prede-
fined
α
Calculate mappings of
v ∈ N
with with
edges in
P
Prefer vertices whose mapping by
f
is
close to edges in
P
over others. Weight
the result with predefined
β
5
6
Calculate edge weights along
P
Prefer vertices in with larger sum
of edge weights on
P
before others.
Weight the result with predefined
γ
Update
P
Select a vertex
v ∈ N
according to
computedheuristicsinsteps4-6and
add it to
P
or wait until next update
from
f
to
N
if no vertex can be se-
lected. Repeat steps 1 - 7 until destina-
tion reached
7
density of mappings is higher. This is done before every vertex decision for
P
to ac-
commodate fast topology changes within the graph.
We then estimate future edge weights of all vertices in
N
to the start vertices of their
mapped edge in
G
. This is especially necessary at low update rates by
f
to the vertices
in
N
. Since our application domain are vehicular ad-hoc networks we have to consider
this fact. A car traveling by 36 m/s on a motorway covers a substantial amount of a car's
transmission range between two position updates. Hence an update by
f
could delete
an edge in
G
.
The following three steps are crucial for the algorithm since the decision on next
vertex for
P
depends on them. Every vertex in
N
gets assigned three heuristics within
the interval of
[0
,
1]
where higher values denote higher priority in selecting the next
vertex for
P
. The three heuristics are given in Table 1, rows 4 - 6.
Each heuristic is multiplied by a weight of
α
,
β
and
γ
respectively. The computations
of the three heuristics are described in detail below. The final step is to select a vertex
