Information Technology Reference
In-Depth Information
PDT increases for G
RANELLI
but decreases for both S
EET
and our approach when
there are more vehicles on the graph. In this case both, S
EET
and our approach have an
increased number of vertices available for choosing the next vertex for the shortest path
and the probability of finding a suitable one also increases since re-computing time for
heuristics is lower than the re-scheduling interval PDT decreases in this case. Because
our approach considers local information about graph operations it supersedes S
EET
by
means of PDT over time which results in a lower number of re-schedules.
Figure 3 depicts voronoi visualizations for all three algorithms after a run with
n
=4
.
Black dots mark starting positions for shortest path computation. Enclosing colored
areas denote PDT to the centre of the map for an individual path in ms (more red areas
mark higher PDT). After a threshold of 15000 ms path computation was stopped and
marked as
failed
. One clearly recognizes short PDT of G
RANELLI
but low PDR: Paths
are found quickly or not at all. Re-scheduling in cases when no successor vertex for the
shortest path can be identified results in stepwise PDTs. Results of our approach reflect
high PDR even for large path lengths due to exploiting local information on dynamic
graph operations.
5
Conclusions
In this paper, we developed a combined uniform and heuristic search algorithm for
maintaining shortest paths in fully dynamic graphs. While other approaches assume
global knowledge on performed graph operations, we argued that there exist use cases
where this information is not available. Our approach shows that in those cases the algo-
rithms' performance can greatly benefit from considering domain specific knowledge.
In our example, we instantiated two graphs: A static and dynamic one. We exploited do-
main specific relations between these graphs in order to heuristically maintain a shortest
path in a dynamic graph. The used heuristics are also tailored to the domain.
We applied our approach to vehicular ad-hoc networks and integrated it into the
transportation layer of a network stack to use it for routing data packets between two
vehicles. Evaluation was performed against two other routing algorithm of this domain.
Due to re-scheduling when no neighboring vertex could be identified during shortest
path search, the approach of G
RANELLI
is superior to our implementation in means of
PDT. However, our approach outperformed S
EET
and G
RANELLI
in means of PDR.
6
Future Work
The algorithm presented in this work is able to maintain shortest paths on highly dy-
namic graphs. The goal of this paper was to solve DSSSP without global knowledge
of graph topology. We therefore made the assumption that the goal vertex is given to
the algorithm. In the future we plan to omit this assumption and enhance the algorithm
presented here in a way that the actual search for the goal vertex is part of the task.
Moreover, we want to discover the “least weighted circuit” between start and goal ver-
tex. This additional constraints are significantly more challenging than DSSSP since
topology is constantly changing. Most likely, the path back to the start vertex is not
