Information Technology Reference
In-Depth Information
N
from the previous step and computes
∀
v
∈
∀
v
∈
P
The code is executed for
G
to a vertex
v
the weight of an edge between a vertex
v
G
(line 4-7). We only
consider vertices up to a certain weight
w
max
. (lines 8-10). Heuristic 1 is then defined
as
m
1
=
α
∈
∈
w
w
max
)
(line 11). Remember, that higher values denote higher priority
in selecting the next vertex for
P
. Heuristic 1 is optimizing the stability of the path
P
∗
(1
−
Algorithm 2.
Heuristic 1: Edge weights between
v ∈ P
and
v ∈ N
1:
for all
(
v
∈ N
)
do
2:
w ←∞
3:
for all
(
v ∈ P
)
do
4:
if
(
w
(
v, v,t
)
<w
)
then
5:
w ← w
(
v, v,t
)
6:
end if
7:
if
(
w>w
max
)
then
8:
w ← w
max
9:
end if
10:
end for
w
w
max
)
11:
v.h
1
← α ∗
(1
−
12:
end for
Algorithm 3.
Heuristic 2: Mappings of
v ∈ N
with with edges in
P
1:
for all
(
v ∈ N
)
do
2:
currentScore ←
0
3:
for
(
i ←
0;
i<P.size−
2;
i
++)
do
4:
p
1
← P
[
i
]
5:
p
2
← P
[
i
+1]
if
(
edge
(
p
1
,p
2
)
∈ g
(
v
))
then
6:
currentScore ← currentScore
+
ω
7:
8:
else
9:
if
(
edge
(
p
2
,p
1
)
∈ g
(
v
))
then
10:
currentScore ← currentScore
+
τ
11:
end if
12:
end if
13:
end for
currentScore
score
max
14:
v.h
2
← β ∗
(
)
15:
end for
V
that are close to the path vertices in
P
. In vehicular
ad-hoc networks we can interpret this as preferring vehicles that are on street junctions
which form natural turning points in the street graph.
Heuristic 2: Mappings of
v
since it prefers vertices
v
∈
N
with Edges in
P
.
Heuristic 2 is computed as stated
in algorithm 3. As for heuristic 1, the code is executed
∈
N
. It scores vertices in
N
higher whose mappings to edges in
G
matches more edges in
P
over others. Fur-
thermore, we take the direction of the edge into account: An exact match gets assigned
ascoreof
ω
. If the mapped edge of
v
is the opposite of an edge in
P
we assign
τ
.
∀
v
∈
