Information Technology Reference
In-Depth Information
not affected by an operation. Neither the distance from the source nor the parent in
the shortest path tree changed. Red marked vertices increased their distance from the
source while the distance of the ones marked pink remained constant but it replaces
the old parent in the shortest path tree. Obviously, this approach also relies on global
knowledge about the graph topology and the operations on it.
[8] (S
EET
)and[9](G
RANELLI
) are both routing protocols for vehicular ad-hoc net-
works. Both implementations have to solve the single-source shortest path problem in
dynamic graphs having no knowledge about its topology by the very nature of their
application domain. The approach by [8] is to employ two graphs: One fixed, one dy-
namic. There exists a connection between the two in a way such that the topology of the
fixed graph correlates with the dynamic one. By solving the SSSP on the fixed graph
they try to approximate this path in the dynamic one. We adopt this idea but also take
local
information about graph operations into account allowing us to dynamically as-
sign lower weights to edges in the fixed graph for solving the SSSP. This allows our
algorithm to adapt the path on the static graph according to the locally known changes
in the dynamic one.
The key idea behind [9] is to estimate the topology of the dynamic graph by using
information about the neighboring vertices. More precisely they try to estimate the po-
sition of neighboring vehicles by using their respective velocity and direction vector.
Our approach also assumes certain knowledge, e.g. the route on the map a vehicle is
driving along, about the surrounding topology of a given vertex (see Section 3) thus
allowing us more accurate position information since we can also take the curvature of
a street into account by computing the position along it.
3
Shortest Path Computation under Unknown Global Graph
Operations
Let
G
=(
V,E
)
be a weighted, directed graph, which is fixed, i.e., no insertions and
deletions are allowed. The topology of
G
is known to the algorithm. Furthermore,
G
=(
V,E
)
denotes a fully dynamic graph.
N
is a list containing all vertices, which
are reachable from a vertex
v
G
with distance 1 (direct connection by one edge).
Only the vertices in
N
are known to the algorithm. The remaining topology of
G
is hid-
den: Neither the number of vertices is known nor the edges between them. In order to
give the reader a clear understanding of these notions, Figure 1 exemplifies these terms
when applied to the domain of vehicular ad-hoc networks: Our algorithm is running on
green Vehicle 1. Black points mark vertices
v ∈ G
, here: junctions. Connecting lines in
between mark edges
e ∈ G
(streets). All vehicles in light blue are located within trans-
mission range and thus are elements of list
N
. Vehicles form vertices of dynamic graph
G
. Dotted lines between them mark edges
e
∈
G
, e.g. wireless connections. Note, that
there is no (direct) edge between vehicle 1 and black vehicles 6,7 and 8 since they are
out of transmission range.
We define a set of functions that can be queried by every vertex in
G
:
∈
1. A function
f
:
V
G
to exactly one edge
e
+
maps a vertex
v
E
.
Moreover, it generates a virtual edge between the vertex
v
and the start vertex of
×
T
→
E
×
R
∈
∈
