Not set pdfsubject - AG Digital Humanities

Transcrição

Friedrich Alexander Universität Erlangen Nürnberg
Technische Fakultät
Lehrstuhl für Künstliche Intelligenz
Prof. Dr.-Ing. Günther Görz
Autarke mobile
Echtzeit-Fahrplannavigation
Studienarbeit
Eingereicht von
Matrikelnummer
Studiengang
Betreuer
Christian Schmidt
15. August 2007
21104300
Informatik (Dipl.)
Prof. Dr.-Ing. Günther Görz
Dr.-Ing. Bernd Ludwig
I
Ich versichere, dass ich die Arbeit ohne fremde Hilfe und ohne Benutzung anderer als der
angegebenen Quellen angefertigt habe und dass die Arbeit in gleicher oder ähnlicher Form
noch keiner anderen Prüfungsbehörde vorgelegen hat und von dieser als Teil einer Prüfungsleistung angenommen wurde. Alle Ausführungen, die wörtlich oder sinngemäß übernommen
wurden, sind als solche gekennzeichnet.
Erlangen, den 15. August 2007
Inhaltsverzeichnis
1 Einleitung
1
1.1 Zielsetzung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Gliederung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2 Analyse
2
2.1 Anforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2 Existierende Lösungsansätze . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.1
Online . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.1.1
Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.1.2
Wireless Application Protocol - WAP . . . . . . . . . . . . .
3
2.2.1.3
Short Message Service - SMS . . . . . . . . . . . . . . . . .
3
2.2.1.4
Diplomarbeit von Tobias Schwab . . . . . . . . . . . . . . .
3
2.2.2
Offline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.3
Navigationsgeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3 Lösungsansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3.1
Vorteile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3.2
Nachteile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3 Entwurf
5
3.1 Routensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1
5
Arten von Kanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3.1.1.1
5
Busverbindungen . . . . . . . . . . . . . . . . . . . . . . . .
Inhaltsverzeichnis
III
3.1.1.2
Fußverbindungen . . . . . . . . . . . . . . . . . . . . . . . .
5
3.1.1.3
Strafverbindungen . . . . . . . . . . . . . . . . . . . . . . .
6
Arten von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1.2.1
Einfache Graphen . . . . . . . . . . . . . . . . . . . . . . .
6
3.1.2.2
Straf-Graphen . . . . . . . . . . . . . . . . . . . . . . . . .
6
Vergleich von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1.3.1
Normaler Graph ohne Fußverbindungen . . . . . . . . . . .
7
3.1.3.2
Normaler Graph mit Fußverbindungen . . . . . . . . . . . .
7
3.1.3.3
Strafgraph ohne Fußverbindungen . . . . . . . . . . . . . . .
8
3.1.3.4
Strafgraph mit Fußverbindungen . . . . . . . . . . . . . . .
8
3.2 Visualisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.2
3.1.3
4 Verwendete Technologien
4.1 Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1
9
9
Java 2 Micro Edition . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4.2 Bluetooth - BT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4.2.1
Sicherheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4.3 Global Positioning System - GPS . . . . . . . . . . . . . . . . . . . . . . . .
10
4.3.1
Messgrößen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.3.2
Satelliten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.3.3
Genauigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.3.3.1
Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Funktionsweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.4 KML - Keyhole Markup Language . . . . . . . . . . . . . . . . . . . . . . .
12
4.5 Bezug der Technologien zur Arbeit . . . . . . . . . . . . . . . . . . . . . . .
12
4.3.4
5 Implementierung
13
5.1 Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1
13
Visualisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
5.1.1.1
14
MapProducer . . . . . . . . . . . . . . . . . . . . . . . . . .
Inhaltsverzeichnis
5.1.2
IV
Routensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.2 Systemanforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
5.2.1
Vorteile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
5.2.2
Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.3 Verwendete Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.3.1
Dijkstra-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.3.1.1
Arbeitsprinzip . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.3.1.2
Rekonstruktion des Pfades . . . . . . . . . . . . . . . . . . .
17
5.3.1.3
Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
5.3.1.4
Prioritätswarteschlange . . . . . . . . . . . . . . . . . . . .
17
5.3.1.5
Psudocode . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
5.3.1.6
Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5.3.2
Damerau-Levenshtein-Stringabstand . . . . . . . . . . . . . . . . . .
21
5.3.3
Darstellung der Zeit . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.3.4
Fahrpläne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.3.5
Kartendaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.3.5.1
Referenzsystem . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.3.6
Entwicklungsumgebung . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3.7
Probleme der J2ME API . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3.8
Objektorientierung vs. Performance . . . . . . . . . . . . . . . . . . .
24
5.3.9
Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.3.10 Zugriff auf externe Daten . . . . . . . . . . . . . . . . . . . . . . . . .
26
5.3.10.1 Dateien im Dateisystem . . . . . . . . . . . . . . . . . . . .
26
5.3.10.2 Gefahren und Probleme bei externen Daten . . . . . . . . .
26
5.3.10.3 Struktur im Dateisystem . . . . . . . . . . . . . . . . . . . .
29
5.3.10.4 Recordstores . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Inhaltsverzeichnis
V
6 Evaluierung
30
6.1 Routensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
6.1.1
Fall 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
6.1.2
Fall 2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
6.1.3
Fall 3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
6.1.4
Fall 4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
6.1.5
Fall 5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
6.1.6
Zusammenfassung - Routensuche . . . . . . . . . . . . . . . . . . . .
33
6.2 Interaktivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
6.2.1
Routensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
6.2.2
Damerau-Levenshtein . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
6.2.3
Zusammenfassung - Interaktivität . . . . . . . . . . . . . . . . . . . .
34
6.3 Bildschirmausschnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
6.4 Kritische Betrachtung der Arbeit und Ausblick . . . . . . . . . . . . . . . . .
35
6.4.1
Lösungsansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.2
Hardwareanforderungen . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.3
Modellierung der Fahrpläne . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.3.1
Verspätungen . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Erreichte Ziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.4.1
Zielführung . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.4.2
Parametrierung . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.4.3
Suchalgorithmen . . . . . . . . . . . . . . . . . . . . . . . .
35
6.4.5
Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.4.6
GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.4.7
Analyse und Design . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.4.4
7 Ausblick und Zusammenfassung
37
7.1 Mögliche Erweiterungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
7.2 Persönliches Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
7.3 Anhang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Literatur
39
1. Einleitung
In Zeiten des Klimawandels und steigender Kraftstoffkosten geht die Entwicklung der individuellen Mobilität früher oder später wieder in Richtung der öffentlichen Verkehrsmittel. Da
diese aber nicht so flexibel sind wie das eigene Kraftfahrzeug und die Auskunft per Internet,
Taschen- oder Aushängefahrplan umständlich oder bei Bedarf nicht verfügbar ist, besteht
meine Idee darin, eine Fahrplanauskunft für Mobiltelefone zu entwickeln. Dieses soll jederzeit
ohne laufenden Kosten einsatzbereit sein und dem Benutzer Hilfestellung bei der Zielsuche
und Positionsbestimmung geben.
1.1
Zielsetzung der Arbeit
Das Ziel dieser Arbeit ist das Konzept, der algorithmische Hintergrund und letztendlich
ein lauffähiges Implementierungsgerüst einer selbständig, das heißt ohne Netzwerkanbindung
und Server, operierenden Fahrplanauskunft für mobile Geräte.
1.2
Gliederung der Arbeit
Diese Studienarbeit ist in folgende Kapitel gegliedert
• Konzept und Grobentwurf
• Feinentwurf
• Algorithmische Details
• Probleme in mobiler Umgebung
2. Analyse
Das zu lösende Problem besteht darin, den Benutzer des Systems, unter bestmöglicher Erfüllung von Randbedingungen, von einem gewünschten Startpunkt mit Hilfe von öffentlichen
Verkehrsmitteln und zu Fuß zu einem Ziel zu führen.
Diese Randbedinungen sind vor allem:
• frühestmögliche Ankunftszeit
• spätestmögliche Abfahrtszeit
• wenige Umstiege
• geringer Fahrpreis durch Wahl weniger Tarifzonen
Dabei soll für die Benutzung öffentlicher Verkehrsmittel auf parametrierbare Fahrplandaten
zurückgegriffen werden.
Für die Wege zu Fuß sollen zusätzlich geographische Daten (unter anderem Haltepunkte
öffentlicher Verkehrsmittel) berücksichtigt werden. Zur erweiterten Benutzerführung ist ein
Bluetooth-(BT)-GPS-Empfänger vorgesehen. Der Benutzer soll Point of Interests (POI)1
angezeigt bekommen, um zu diesen navigieren zu können und sich an deren Position zu
orientieren.
2.1
Anforderungen
Das Programm soll dem Benutzer interaktiv helfen, sein Ziel zu erreichen, das heißt das Programm soll auf die Aktionen des Benutzers reagieren (Anzeige von Position und Richtung).
Die Grundfunktionalität soll ohne Benutzung eines Kommunikationsnetzes, wie Mobilfunknetz oder Internet, zugänglich sein.
1
Point Of Interest - Punkt des Interesses / interessanter Punkt
2.2. Existierende Lösungsansätze
2.2
3
Existierende Lösungsansätze
Es gibt schon einige ähnliche Ansätze zur mobilen Navigation in Echtzeit. Jedoch unterscheiden sich diese von der hier aufgeführten Aufgabenstellung, wie im folgenden zu sehen
ist.
2.2.1
Online
Alle hier aufgeführten Lösungen arbeiten nicht autark, sondern benötigt ein Netzwerk und
einen Server.
2.2.1.1
Internet
Im Internet sind viele lokale Auskunftssysteme der einzelnen Verkehrsbetriebe vorhanden,
jedoch gibt es auch deutschlandweite Suchen [DB07]. Trot der Fähigkeit HTML darzustellen, steht diese Möglichkeit nicht auf allen mobilen Geräten zur Verfügung, da Provider den
Zugriff meist auf bestimmte Seiten begrenzen.
Desweiteren habe ich persönlich die Erfahrung gemacht, dass einige Wege nicht angezeigt
werden, obwohl diese vorhanden und besser sind als die angebotenen Ergebnisse.
2.2.1.2
Wireless Application Protocol - WAP
Die meisten öffentlichen Verkehrsbetriebe bieten heutzutage eine Weboberfläche für mobile
Geräte an, welche aber oft nur eine abgespeckte Version des Internet-Frontends ist. Meist ist
der Zugriff vom Mobilgerät auf das WAP mit laufenden Providerkosten verbunden. [VGN07]
2.2.1.3
Short Message Service - SMS
Diese Variante ist ähnlich der WAP Veriante, nur dass hier keine Oberfläche angeboten wird,
sondern es werden Textnachrichten mit spefizischer Syntax übertragen. Auch diese Variante
ist in den meisten Fällen mit Kosten verbunden. [VGN07]
2.2.1.4
Diplomarbeit von Tobias Schwab
Im Rahmen der Aufgabenstellung dieser Studienarbeit wurde eine Diplomarbeit von Tobias
Schwab angefertig, welche die Aufgabenstellung etwas anders auslegt als diese Studienarbeit.
Dazu benutzt er ein Client-Server-Konzept, wobei der Server für die Routensuche und der
Client für die Darstellung und Zielführung zuständig ist.
Diese Konzept ist von einem Server und der Kommunikationsverbindung zu diesem abhängig.
2.2.2
Offline
Inzwischen gibt es einige Offline-Versionen für PDAs2 .
Wie zum Beispiel
2
Personal Digital Assistant - tragbarer Minicomputer
2.3. Lösungsansatz
4
• VRS - Verkehrsverbund Rhein-Sieg [VRS07]
• VBB - Verkehrsverbund Berlin-Brandenburg [VBB07]
Ein Vergleich oder weitere Aussagen sind mir nicht möglich, da es an einem entsprechenden System zum Ausführen fehlt. Laut Betreiber handelt es sich um System zum offline
Planen der Fahrten. Diese Systeme scheinen teilweise autark zu arbeiten, jedoch sind sie in
gewünschtem Funktionsumfang nur für spezielle PDAs verfügbar.
2.2.3
Navigationsgeräte
Navigationsgeräte sind meist kleine Computer, welche sich zur Navigation auf Strassenkarten
eignen. Inzwischen gibt es auch Varianten für PDA und Mobiltelefon. Es sind keine Informationen über Navigationssysteme auffindbar, welche öffentliche Verkehrsmittel einbeziehen[Tom07].
2.3
Lösungsansatz
Bei dieser Arbeit werden alle Daten im mobilen Gerät gespeichert:
• das komplette Benutzerinterface und Logik in einem Programm
• Fahrplandaten in parametrierbare Dateien
• Geographische Informationen zu Haltestellen und POIs
• Kartendaten zur Visualisierung
2.3.1
Vorteile
• keine laufenden Kosten durch WAP- oder WWW-Verbindung
• Unabhängigkeit von Onlinediensten
• Unabhängigkeit von Serverlast und Netzgeschwindigkeit
2.3.2
Nachteile
• regelmäßige Aktualisierung nötig (vor allem der Fahrpläne)
• alle Berechnungen werden lokal durchgeführt, was eventuell zu hohen Rechenzeiten und
damit hohen Reaktionszeiten auf Benutzereingaben führt
• mobiles Gerät muss recht hohe Mindestanforderungen(Speicher, Rechenleistung, Display) erfüllen, damit das Programm überhaupt lauffähig ist
2.4
Zusammenfassung
Das Ziel der Studienarbeit ist ein Fahrplanauskunftssystem für öffentliche Verkehrsmittel. Die
Zielgruppe dieses Systems sind Fahrgäste lokaler öffentlicher Verkehrsmittel mit Mobilgerät.
Die Benutzung erfolgt (vorwiegend) offline auf Mobilgeräten, wie Handys oder PDAs.
3. Entwurf
3.1
Routensuche
Als Abstraktion des Problems der Verbindungssuche von einem Startpunkt zu einem Zielpunkt auf vorgegebenen Strecken bieten sich Graphen im Kontext der Graphentheorie[Gra07]
an. Das ermöglicht die Benutzung gründlich erforschter Algorithmen.
Dabei werden die geographischen Punkte(zum Beispiel Haltestellen) durch Knoten, die Verbindungen zwischen diesen durch Kanten und die zeitliche Entfernung durch die Gewichte
des Graphen abgebildet.
Da bei Benutzung von öffentlichen Verkehrsmitteln im Allgemeinen die Ankunftszeiten zwischen zwei Punkten nicht symmetrisch sind, wird ein gerichteter Graph abstrahiert. Zwischen zwei Punkten können mehrere Verbindungen in jede der beide Richtung existieren.
Im Gegensatz zu üblichen Graphen, sind die Gewichte der Kanten zum Teil abhängig vom
Zeitpunkt ihrer Betrachtung, da zu unterschiedlichen Zeitpunkten die Verweildauer zwischen
zwei Knoten aufgrund der Fahrpläne variiert.
3.1.1
Arten von Kanten
3.1.1.1
Busverbindungen
Bei öffentlichen Verkehrsmitteln gibt es Kanten, welche Verbindungen repräsentieren. Deren
Gewichte sind abhängig vom Zeitpunkt ihrer Betrachtung. Sie bilden das Herzstück der
Routenplanung.
3.1.1.2
Fußverbindungen
Es ist auch möglich, zwei Punkte mit Fußverbindungen zu verbinden, wobei das Gewicht
dieser Kante nicht vom Zeitpunkt abhängig ist, sondern nur vom geographischen Abstand
der zwei Punkte und von der Schrittgeschwindigkeit des Benutzers. Diese Daten müssen
nicht explizit im Graph gespeichert werden, sondern können zur Laufzeit berechnet werden
3.1. Routensuche
6
um Speicherplatz zu sparen. Da jeder Punkt mit jedem verbunden werden müsste, würde
dies einen Aufwand von
N = n(n − 1) ∈ O(n2 )
bedeuten, das heißt bei Verdoppelung der Knoten würde sich die Anzahl der Kanten näherungsweise vervierfachen.
Die Geographische Entfernung ist gerade für städtische Gebiete nicht ideal, da der Benutzer kaum auf direktem Wege gehen kann. Da viele Städte rechteckig angelegt sind, ist als
Entfernungsmaß die Manhatten-Distanz sinnvoll. Sie addiert einfach die rechtwinklig aufeinander stehenden Komponenten. Wenn man davon ausgeht, dass diese Komponenten von Ost
nach West und Nord nach Süd verlaufen addiert man einfach geographische Längen- und
Breitenänderung.
3.1.1.3
Strafverbindungen
Um bei der Routensuche Umstiege einzuschränken, müssen die Umstiege mit Strafen belegt
werden (siehe: 3.1.2.2). Umstiege gibt es nur innerhalb der gleichen Bushaltestelle zwischen
unterschiedlichen Linien.
Da die geographische Entfernung zwischen zwei Bushaltestellen immer 0 ist, würde ein Fußmarsch mit der Entfernung 0 und damit der Zeitdauer 0 die Strafverbindungen zunichte
machen.
3.1.2
Arten von Graphen
3.1.2.1
Einfache Graphen
Bei dieser Art von Graphen sind zwei Haltestellen durch alle Linien miteinander verbunden, die zwischen ihnen verkehren. Abhängig von ihrer Entfernung und dem Wunsch nach
Betrachtung von Fußverbindungen gibt es noch eine Fußverbindung zwischen den beiden
Haltestellen.
3.1.2.2
Straf-Graphen
In einem Graphen gibt es nur Gewichte an Kanten und nicht an Knoten. Da Strafen für
das Umsteigen innerhalb einer Haltestellen und damit an Kanten erfolgen müßten, werden
Knoten in diesem Fall als 2er-Tupel (Haltestelle, Buslinie) modelliert. Somit wird beim Umsteigen eine Kante zwischen Knoten mit der selben Haltestellen aber unterschiedlichen Linien
durchlaufen. Diese Kante (und damit der Umstieg) läßt sich wie gewünscht gewichten.
Dies lässt die Anzahl der Knoten und Kanten im Graph jedoch enorm ansteigen.
3.1.3
Vergleich von Graphen
Um sich die Größe der einzelnen Typen von Graphen (normaler Graph/Strafgraph, mit/ohne Fußverbindungen) besser vorstellen zu können, zeigt der folgende Abschnitt ein simples
Beispiel mit drei Knoten und 2 Linien zwischen diesen Knoten.
Zahlen an den Kanten stehen für die Buslinie.
F steht für Fußmarsch mit der Zeit in Klammern.
P steht für Strafkante mit der Zeit in Klammern.
Gut zu erkennen ist die Symmetrie bei Strafkanten und Fußmärschen.
3.1. Routensuche
3.1.3.1
7
Normaler Graph ohne Fußverbindungen
Erlangen Altstadtmarkt
293
Erlangen Martin-Luther-Platz
293287
Erlangen Schlachthof
Der Graph mit den Buslinien Erlangens, ohne Nightliner und Überlandbusse, hat 160 Knoten
und 1758 Kanten.
3.1.3.2
Normaler Graph mit Fußverbindungen
Erlangen Schlachthof
F(12 min)
293
287
F(12 min)
Erlangen Martin-Luther-Platz
F(5 min)
F(18 min)
F(18 min)
293 F(5 min)
Erlangen Altstadtmarkt
Der Graph mit den Buslinien Erlangens, ohne Nightliner und Überlandbusse, hat 160 Knoten
und 5578 Kanten, wobei einzelne Fußmärsche kleiner als 5000m sind.
3.2. Visualisierung
3.1.3.3
8
Strafgraph ohne Fußverbindungen
[Erlangen Martin-Luther-Platz,287]
P(2 min)
[Erlangen Altstadtmarkt,293]
P(2 min)
293
287
293
[Erlangen Schlachthof,293]
P(2 min) P(2 min)
3.1.3.4
Strafgraph mit Fußverbindungen
F(18 min)
F(18 min)
[Erlangen Altstadtmarkt,293]
P(2 min)
F(12 min)
F(5 min)
F(12 min)
F(18 min)
F(5 min)
F(5 min)
F(18 min)
F(5 min)
F(12 min)
293
F(12 min)
293 P(2 min)
F(12 min)
F(12 min)
F(12 min)
F(12 min)
P(2 min)
P(2 min)
287
Die Anzahl der Kanten wächst in dieser Konfiguration extrem an.
Knoten, zwischen denen es Strafkanten gibt, besitzen keine Fußmärsche, da diese das Kantengewicht 0 hätten und damit die Strafkanten immer unterbieten würden.
3.2
Visualisierung
Da graphische Visualisierung zumeist intuitiver ist als textuelle Ausgabe und die meisten
modernen Mobilgeräte hochauflösende, farbige Grafikausgabe unterstützen, werden die Ergebnisse graphisch dargestellt.
Das Herzstück bildet eine (Stadt-) Karte, welche zur Orientierung und Visualisierung dient.
Alle anderen geographischen Darstellungen bauen auf diese Karte und deren Koordinatensystem auf.
4. Verwendete Technologien
4.1
Java
Das Projekt Java wurde von Sun Microsystems Anfang der 1980er Jahre ins Leben gerufen.
Dabei bezeichnet Java sowohl eine Technologie als auch eine Programmiersprache, welche eng
an diese Technologie geknüpft ist. Ziele dieses Projektes waren eine Sprache zu erschaffen,
welche leichte Erlernbarkeit (durch Ähnlichkeit der Syntax zu C/C++) bot, und eine virtuelle Maschine1 , welche eine abstrakte Plattform für Java-Programme bietet. Dabei wird der
Quellcode nicht wie üblich in Maschinencode umgewandelt, sondern in ByteCode, welcher
von der virtuellen Maschine ausgeführt wird. Die virtuelle Maschine bietet Plattformunabhängigkeit, da nicht das Programm auf die Maschine, sondern nur die virtuelle Maschine
auf die reale Maschine angepasst werden muss. Des weiteren bietet diese virtuelle Maschine
den Vorteil, Zugriffe nach Außen überwachen und reglementieren zu können, auch bekannt
als sogenanntes Sandbox-Prinzip. Neben der Programmiersprache bietet Java eine API2 für
Grundfunktionalitäten und häufig verwendete Strukturen. Seit Java2 wird Java in 3 verschiedene Bereiche aufgeteilt:
• J2EE (Enterprise Edition) Java für das Serverumfeld
• J2SE (Standard Edition) Java für Desktop Rechner
• J2ME (Micro Edition) Java für Kleingeräte
Dabei stellt J2EE die größte und J2ME die kleinste API zur Verfügung.
1
2
Auch Virtual Machine im Englischen; eine Plattform, welche in Software statt in Hardware existiert
Application Programming Interface = Programmierschnittstelle
4.2. Bluetooth - BT
4.1.1
10
Java 2 Micro Edition
Diese Variante von Java ist speziell für eingebettete Systeme (embedded systems) gedacht.
Diese Systeme zeichnen sich im Allgemeinen durch geringe Ressourcen (Rechenleistung, Arbeitsspeicher, usw.) aus. Ursprünglich war J2ME für den Einsatz in unterschiedlichsten Kleinund Kleinstgeräten gedacht, jedoch beschränkt sich die weite Verbreitung auf Geräte mit hoher Software-Wiederverwendung durch hohe Stückzahlen, insbesondere Mobiltelefone und
PDAs.
Innerhalb von J2ME gibt es die Konfiguration“, welche vor allem Hardwareanforderun”
gen festlegt und Profile“, welche die Benutzung zusätzlicher Funktionen wie Dateisystem,
”
Adressbuch und Low-Level Funktionalität beschreibt. Konfigurationen und Profile sind abwärtskompatibel.
4.2
Bluetooth - BT
Bluetooth ist eine funkbasierte Netzwerktechnologie, welche Mitte der 1990er Jahre entwickelt wurde. BT ist im Gegensatz zu Wireless LAN3 (WLAN) für kurze Distanzen und
geringere Geschwindigkeiten ausgelegt. Jedoch besitzt BT verschiedene vordefinierte Funktionsschemata (BT-Profile), welche die Kommunikation zwischen verschiedenen Geräten normiert und vereinfacht.
BT-Netzwerke sind ad-hoc Netzwerke, das heißt sie arbeiten dezentral und müssen nicht
administriert werden, sondern administrieren sich selbst, wenn durch mehrere Geräte eine
Kommunikation zustandekommt. Der Name leitet sich vom dänischen König Harald Blauzahn ab, welcher einst für Einigkeit und Verbundenheit in Skandinavien sorgte. BT-Geräte
haben meist eine sehr geringe elektrische Leistung, was sie sparsam macht und dazu führt,
dass sie durch einen Akku für längere Zeit elektrisch unabhängig sind. BT kommt heutzutage vor allem in Mobiltelefonen, kabellosen Headsets, USB-Adaptern, Eingabegeräten und
GPS-Empfängern zum Einsatz. Andere Einsatzmöglichkeiten wie in Spielzeug, Haustechnik
und in industrieller Anwendung gibt es auch in Ansätzen.
4.2.1
Sicherheit
Wie bereits erwähnt werden BT-Netzwerke nicht verwaltet und es können sich verschiedene
Geräte zu einem Netzwerk zusammenschließen um miteinander kommunizieren. Das bietet
auch Raum für unerwünschten Datenzugriff von außerhalb. Aus diesem Grund gibt es die
Möglichkeit einer PIN4 -Authentifizierung der Teilnehmer untereinander. Zur Kommunikation
ist das Wissen über die ID5 im Netzwerk von Nöten, welche sich jedoch Erfragen lässt, solange
diese Funktion nicht ausgeschaltet ist.
4.3
Global Positioning System - GPS
GPS ist ein satellitengestütztes Ortungssystem. Entwickelt und anfänglich eingesetzt wurde GPS vom US-amerikanischen Militär. Anfangs wurde das Signal künstlich verfälscht um
3
Local Area Network - Netzwerktechnologie für kurze Distanzen
Personal Identification Number - Geheimzahl
5
Eindeutiger Bezeichner
4
4.3. Global Positioning System - GPS
11
feindliche und zivile Nutzung unpräzise zu machen. Diese Verfälschung wurde im Jahr 2000
aufgehoben. Damit lassen sich bei günstigen Bedingungen für jedermann Genauigkeiten von
10m erreichen.
Von großer Bedeutung ist GPS seit langem in der Schifffahrt. Durch immer kleinere Empfänger und größere Stückzahlen ist der Markt für die Nutzung von GPS in den letzten Jahren jedoch sehr stark angewachsen. Vor allem der Markt der Navigationssysteme für Autos
boomt.
4.3.1
Messgrößen
GPS ist sowohl in der Lage sphärische Koordinaten6, als auch Höhenangaben, Geschwindigkeit, Kurs und Uhrzeit bereitzustellen. Voraussetzung dafür ist, dass genügend Satelliten
sichtbar“ sind.
”
4.3.2
Satelliten
Zur Bestimmung der Koordinaten reichen 3 Satelliten aus, zur Bestimmung der Höhe ist ein
weiterer nötig. Insgesamt umkreisen die Erde 24 Satelliten von denen maximal 12 sichtbar“
”
sind. Die Bahnen sind nicht geostationär7 .
4.3.3
Genauigkeit
In der Regel kann eine Genauigkeit von wenigen Metern erreicht werden. Jedoch hängt dies
stark von Umwelt- und Umgebungseinflüssen ab. So ist in einer engen Straße mit hohen Häusern die Sicht auf die Satelliten begrenzt. Auch kann das Signal durch Reflexion an den Mauern verfälscht werden. Ebenso beeinflussen Gebirge, Wald und Niederschlag, sowie starker
Nebel die Qualität des Empfangs und damit die Genauigkeit. Die Genauigkeit ist desweitern
von der entsprechenden Hardware (und damit eingesetzten Technologie) abhängig. So erzielen sehr teure, professionelle Geräte weit aus höhere Genauigkeiten als Consumer-Produkte.
Außerdem sind nicht immer gleich viele Satelliten zu sehen, was zu einer Beeinflussung der
Genauigkeit führt. In Gebäuden ist der Empfang nur unter sehr günstigen Umständen, wie
zum Beispiel bei gutem Wetter am Fenster möglich.
4.3.3.1
Ausblick
Es gibt inzwischen erste Ansätze, Unterbrechungen der Satellitenverbindung auszugleichen.
Voraussetzung dafür ist, dass Position und Geschwindigkeit schon einmal bestimmt wurden.
Danach kann man mit Hilfe von Beschleunigungssensoren die Geschwindigkeit aktualisieren
und mit dieser wiederum die Position. Voraussetzung dafür wären zum Beispiel faseroptische
Miniaturkreisel zur Beschleunigungsmessung.
6
7
geographische Länge und Breite
geostationär= von der Erde aus betrachtet, ändert sich die Position am Himmel nicht
4.4. KML - Keyhole Markup Language
4.3.4
12
Funktionsweise
Die Satelliten kennen ihre Position und sind jeweils mit einer Atomuhr ausgerüstet, welche
untereinander synchronisiert wird. Jeder von ihnen sendet zyklisch ein Signal mit der Uhrzeit
und der Position aus. Der Empfänger empfängt diese Signale, kann die Laufzeitunterschiede
messen und damit die Entfernungen von den Satelliten berechnen. Nun kann der Empfänger
durch Trilateration8 seine Position auf der Erdoberfläche oder bei genügender Anzahl von
Satelliten auch im Raum bestimmen.
4.4
KML - Keyhole Markup Language
KML ist eine auf XML9 basierende Sprache zum Austausch geographischer Informationen.
In dieser Arbeit wird KML dazu eingesetzt um geographische Punkte, wie Bushaltestellen
und POIs zu speichern.
J2ME besitzt im Gegensatz zu J2SE keine Unterstützung für XML. Aus diesem Grund mußte
ein eigener Parser10 geschrieben werden, welcher aber keine Syntaxüberprüfung durchführt
und nur Placemark -Tags11 herausfiltert.
”
”
4.5
Bezug der Technologien zur Arbeit
Zur Positionsbestimmung des Benutzers wird ein GPS-Empfänger verwendet, welcher über
BT mit dem Mobilgerät kommuniziert. Die eigentliche Anwendung mit Visualisierung, Routenberechnung und GUI12 wird in Form eines Java MIDLets implementiert.
8
Entfernungsmessung im Dreieck
Extensible Markup Language grammatikalisch wohldefinierte Strukturbeschreibungssprache hierarchisch
strukturierter Informationen
10
Programm für wohldefinierte Zerlegungen einer Eingabe
11
Erkennungsmarke
12
Graphical User Interface = Grafische Benutzeroberfläche
9
5. Implementierung
Dieses Kapitel beschäftigt sich mit der Entwicklung von der Idee zum lauffähigen Programm.
5.1
Architektur
Das Programm besteht aus zwei Hauptkomponenten, der Routensuche und der Visualisierung. Eine weitere Komponente wird diese beiden zusammenführen und als GUI dienen.
5.1.1
Visualisierung
javax.microedition.lcdui
map.painting
map.producer
MapGrid
Canvas
protected void paint(Graphics g)
public void centerTo(double longitude, double latitude)
<<realize>>
<<interface>>
0..*
CommandListener
0..*
<<interface>>
1
0..*
KMLPainter
<<realize>>
MapProducer
public MapImage getMap(double x, double y, int zoom, boolean async)
public MapImage getMap(int x, int y, int zoom, boolean async)
public int getWidth()
public int getHeight()
0..*
<<realize>>
<<realize>>
<<interface>>
CoordinatePainter
<<realize>>
public void paint(Graphics g, MapGrid mg)
GoogleFileReader
<<interface>>
coordinates
RepaintListener
<<realize>>
<<interface>>
<<realize>>
CoordinateTransformer
public double deg2CoordX(double x)
public double deg2CoordY(double y)
public double coord2DegX(double x)
public double coord2DegY(double y)
0..*
VariantCoordinatePainter
MapImage
<<realize>>
public Image getImage()
public void setImage(Image image)
public MapImage getRelative(int x, int y)
<<realize>>
LinePainter
private CoordinatePainter painter
public void setPainter(VariantCoordinatePainter painter)
0..*
Mercator
graph
0..*
Google
Edge
SourceEdge
public Node getSink()
public Node getSource()
Node
Dabei ist die Klasse MapGrid die zentrale Komponente der Darstellung. Sie ist ein Canvas[Can07],
das heißt ein Element für Low-Level-Darstellung und Low-Level-Tastatur-Handling. Der
Grundgedanke besteht darin, mehrere Kartenstücke nahtlos miteinander zu verknüpfen, so
dass der Eindruck einer großen Karte entsteht. Diese Kartenstücke liefert der MapProducer,
5.1. Architektur
14
welcher zu jedem MapGrid gehört. Scrollt der Benutzer per Tastatur, so werden die Karten
verschoben gezeichnet, solange bis Karten aus der Anzeige herausfallen“ und neue Karten
”
angefodert und gezeichnet werden müssen.
5.1.1.1
MapProducer
Der MapProducer ist ein Interface zum Einlesen von Kartenmaterial. Er gibt jeweils eine Karten zu bestimmten Koordinaten und Zoomstufe zurück, und kann Karten aus dem zugrundeliegenden Raster-Koordinatensystem adressieren um benachbarte Kartenstücke schneller
zu erhalten.
Google
Diese Klasse ist eine Implementierung des Interface MapProducer und beruht auf den Karten
von Google Maps[GMa07]. Diese benutzen eine Variante der Mercator-Projektion, dabei
handelt es sich um eine winkeltreue Projektion des Globus auf eine ebene Karte. Der Ort
der Bilddateien wird in einem parametrierten Pfad hinterlegt.
MapImage
MapImage enthält die gegebenenfalls vorhandenen Bilddaten des Kartenrechtecks sowie deren Koordinaten und Koordinatentransformation. Um eventuelle Ladezeiten zu verkürzen,
ist es dem MapProducer beim Erzeugen eines MapImages erlaubt, das Bildmaterial nach
dem Laden (aysnchron) zu setzen.
Zusätze - Plugins
Mit dem Interface CoordinatePainter lassen sich zusätzliche Grafische Komponenten, wie Anzeige von Koordinaten und ähnliches einbinden. VariantCoordinatePainter und LinePainter
sind die Schnittstellen zur Darstellung von Routen.
KMLPainter Mit der Klasse KMLPainter lassen sich Dateien im Keyhole Markup Language (KML) Format, wie sie zum Beispiel Google Earth benutzt, anzeigen. Somit lassen
sich POIs einfach importieren und mit externen Programmen, wie zum Beispiel Google Earth
bearbeiten.
5.1.2
Routensuche
Wie bereits erwähnt, basiert die Routensuche auf einer Graphensuche in einem Graphen mit
zeitabhängigen Kantengewichten.
5.2. Systemanforderungen
15
graph
Graph
<<interface>>
Edge
Node
public Node[] getNodes()
public Edge[] getOutgoingEdges(Node node)
public void addEdge(SourceEdge edge)
public Node getNode(Busstop busstop, Line line)
protected Node buildNode(Busstop busstop, Line line)
private Busstop busstop
public Line line
graph.fibonacci
public Node getSink()
public long getArrivalTime(long time)
<<realize>>
FootpathEdge
public int timeNeeded
MultistationGraph
FibonacciHeap
public void decreaseKey(HeapData hd, long key)
public void insert(HeapData hd)
public HeapData deleteMin()
<<realize>>
<<interface>>
SourceEdge
PenaltyEdge
HeapData
public Node getSource()
protected Node buildNode(Busstop busstop, Line line)
public Edge[] getOutgoingEdges(Node node)
private final Node n
private long key
<<realize>>
BusstopEdge
<<realize>>
private Line line
private Node source
private Node sink
WrapperEdge
public Line getLine()
public WrapperEdge(Edge e, Node source)
database
<<interface>>
Line
Busstop
public long nextDepartureTime(long time, Busstop busstop)
private String name
Dijkstra
<<realize>>
<<interface>>
PathFinder
public void findShortestPath(long now)
public Object[] trace()
private long[] d
private java.util.Vector nodes
private FibonacciHeap q
private int[] previous
private java.util.Vector lineused
public java.util.Vector hd
coord
<<realize>>
LineImpl
GpsCoordinate
public final double latitude
public final double longitude
public Dijkstra(Graph g, Node start, Node end)
Das Herzstück der Suche ist die Klasse Graph. Dieser ist aus expliziten Kanten von Buslinien und Knoten (Bushaltestellen) aufgebaut. Des weiteren gibt es implizite Kanten zwischen
den Knoten, welche Fußmärsche darstellen. Diese sind jedoch nicht zeitabhängig. Eine Abwandlung des Graphen ist der MultistationGraph, welcher zusätzlich Strafen bei Umstiegen
modelliert. Dies geschieht durch zusätzliche Kanten zwischen Knoten zweier gleicher Bushaltestellen unterschiedlicher Linien.
Eine Linienkante wird aus einer Linie gewonnen, welche wiederum Informationen über die
einzelnen Abfahrtszeiten an den Bushaltestellen hat.
Auf die unterschiedlichen Graphen können Suchalgorithmen angewendet werden, um Routen zu finden. In meiner Studienarbeit wurde nur der Dijkstra-Algorithmus implementiert,
jedoch ist eine Erweiterung um andere Algorithmen, wie zum Beispiel dem A*-Algorithmus
dank Verwendung eines Interfaces kein Problem.
5.2
Systemanforderungen
Da sich Java ME (J2ME) in den letzten Jahren als Standard bei Mobilgeräten durchgesetzt
hat, wird die Implementierung des Programmes als Java MIDlet erfolgen. Als Mindestanforderung der Mobilgeräte wird Connection Limited Device Configuration 1.1 (CLDC 1.1) und
Mobile Information Device Profile 2.0 (MIDP 2.0)[MID07] vorausgesetzt. Für die Benutzung
von Bluetooth muss das Mobilgerät die Java Bluetooth API (JSR-82[JSR07]) unterstützen.
5.2.1
Vorteile
Java MIDlets bieten unter anderem folgende Vorteile:
• weite Verbreitung von Java
• gut dokumentierte API
• “write once run everywhere”-Prinzip
5.3. Verwendete Methoden
16
• aus Software-Engeneering-Sicht gute Sprachkonstrukte (Objektorientierung, keine Sprungmarken, alle Variablen haben expliziten Datentyp)
• freie Entwicklungs- und Testumgebung vorhanden
5.2.2
Probleme
Java MIDlets auf Mobilgeräten bringen jedoch auch einige Probleme mit sich,
zum Beispiel:
• teilweise sehr begrenzte Resourcen auf Mobilgeräten, vor allem auf Mobiltelefonen
• teilweise anderes Verhalten in der Testumgebung als auf Mobilgerät, unter anderem
dadurch, dass auf Emulator mehr Resourcen zur Verfügung stehen
• hardwarebedingt unterstützen nicht alle Geräte alle APIs von Java ME
• herstellerspezifische APIs schränken Portabilität ein
• Security Architecture schützt zwar gegen Schadprogramme, stellt aber Barriere für
vollen Funktionsumfang dar, da der Benutzer durch häufige Sicherheitsabfragen gestört
wird
5.3
Verwendete Methoden
5.3.1
Dijkstra-Algorithmus
Der Klassiker“ unter den Graphensuchalgorithmen ist Dijkstra’s Algorithmus.
”
Prinzipiell sucht er von einem gegebenen Startknoten den kürzesten Pfad zu allen Knoten
in einem gewichteten (und gerichteten) Graphen. Wenn man den Pfad zu einem Zielknoten
sucht, lässt sich die Suche jedoch abkürzen. Kantengewichte und Entfernungen können unendlich groß sein. Wenn es negative Kantengewichte im Graphen gibt, ist nicht garantiert,
dass Dijkstra’s Algorithmus den kürzesten Pfad findet. Wenn es Zyklen mit negativen Kosten
gibt, könnten diese beliebig oft Durchlaufen werden und die Kosten würden immer weiter
abnehmen, was dazu führt, dass es kein Optimum (Minimum) gibt.
5.3.1.1
Arbeitsprinzip
Am Anfang werden alle Knoten, außer der Startknoten mit maximalen (unendlichen) Erreichbarkeitskosten vorbelegt. Der Startknoten ist ohne Kosten (0) erreichbar. Im nächsten
Schritt werden alle Knoten des Graphen mit ihren Erreichbarkeitskosten in eine Prioritätswarteschlange1 eingefügt.
Nun beginnt die Iteration: es wird der Knoten mit den geringsten Erreichbarkeitskosten aus
1
Datenstruktur, in der die Reihenfolge der gespeicherten Elemente durch Prioritäten vorgegeben ist; im
Englischen: Priority Queue
17
der Warteschlange geholt (beim 1. mal wird dies der Startknoten sein) und all seine ausgehenden Kanten betrachtet. Jetzt wird betrachtet, ob der jeweilige Weg über diese Kanten zu
den Senken2 -Knoten kürzer ist, als die schon ermittelteten Erreichbarkeitskosten zu diesem
Senken-Knoten. Wenn ja werden die Erreichbarkeitskosten des Senkenknotens aktualisiert, so
dass sich die Erreichbarkeitskosten als Summe der Kosten vom Quellknoten und dem Kantengewicht zum Senkenknoten zusammensetzt. Anschließend wird die Warteschlange mit dem
neuen Wert des Senkenknotens aktualisiert und der Vorgänger des Senkenknotens im Pfad,
also der Quellknoten wird der Senke als Vorgänger zugeordnet. Enthält die Prioritätswarteschlange als kleinsten Wert das Gewicht zum Knoten unendlich, so lässt sich die Schleife
am Anfang abbrechen, da alle weiteren Werte auch unendlich sind, und unendlich nicht zu
einer kürzeren Route führt. Ist der Senkenknoten der Zielknoten, so lässt sich die Schleife
abbrechen, da es keinen kürzeren Weg zum Zielknoten geben wird. Der ermittelte Weg vom
Startknoten ist eine Struktur, bei der jeder Knoten seinen Vorgänger auf dem kürzesten Pfad
zu ihm gespeichert hat.
5.3.1.2
Rekonstruktion des Pfades
Ausgehend vom letzten Zielknoten sucht man sich den Vorgänger des jeweils betrachteten
Knoten, bis man beim Startknoten angelangt ist.
Falls der Zielknoten im Graphen nicht erreichbar ist (Graph ist nicht zusammenhängend bzw.
Kanten haben Gewicht von ∞), hat der Zielknoten keinen Vorgänger und es gibt keinen Pfad.
5.3.1.3
Probleme
Die einzige Aussage, die sich über den Pfad treffen läßt, ist die dass es keinen anderen Pfad
gibt, der kürzer ist. Wenn das Benutzen einer Linie durch eine andere Linie unterbrochen
wird, kommt es zum Problem. Man kommt zum gleichen Zeitpunkt an, wie wenn die Linie
nicht durch eine andere unterbrochen worden wäre. Dieses Verhalten ist jedoch unerwünscht.
Zur Behebung dieses Problems müsste man den Pfad rückwärts durchlaufen und jedes mal
vom Anfang aus schauen, ob die Linie bereits benutzt wurde und dann den Pfad so abkürzen,
dass man die Linie nicht wechselt.
5.3.1.4
Prioritätswarteschlange
Eng im Zusammenhang mit dem Dijkstra-Algorithmus steht die Prioritätswarteschlange. Sie
sorgt dafür, dass die Gewichte der Knoten gespeichert, aktualisiert und der Knoten mit dem
kleinsten Gewicht abgerufen werden kann. Würde man stattdessen eine Liste zur Verwaltung
der Gewichte benutzen, käme man auf eine Laufzeit von O(n2 + m), wobei n die Anzahl der
Knoten und m die Anzahl der Kanten ist. Verwendet man eine Binäre Halde (Binaryheap),
welche die Befehle insert, remove, pop, und decreasekey in logarithmischer Zeit ausführt,
kommt man auf eine Laufzeit von O((m+n) log(n)). Benutzt man eine Fibonacci-Halde, so
verringert sich die Laufzeit für Befehle bei insert und decreasekey auf ein konstantes Maß
und der Dijkstra-Algorithmus hat dann den Aufwand von O(m + n log(n)).
2
Gegenteil einer Quelle
5.3.1.5
18
Psudocode
Hier der Pseudocode für den Dijkstra-Algorithmus mit zeitbehafteten Graphen:
// i n i t
f o r ( Node n : graph . getNodes ( ) ) {
i f ( n == s t a r t N o d e ) {
c o s t s [ n ] = st a r t Time ;
} else {
c o s t s [ n ] = MAX VALUE ;
}
prev [ n ] = n u l l ;
queue . enqueue ( n , c o s t s [ n ] ) ;
}// end f o r
// queue a b a r b e i t e n
w h i l e ( ! queue . isEmpty ( ) ) {
Node c u r r e n t = queue . r emo veF ir st Element ( ) ;
f o r ( Edge edge : graph . getOutgoingEdges ( c u r r e n t ) ) {
// V o r z e i t i g e r Abbruch
i f ( edge . s i n k == endNode | | c o s t s [ edge . s o u r c e ] == MAX VALUE) {
return ;
}
// g e t c o s t s from o b s e r v e d timestamp with c e i l bound
edg eCo st s = edge . g e t C o s t s (
c o s t s [ edge . s o u r c e ] , c o s t s [ edge . s i n k ] )
i f ( edg eCo st s < c o s t s [ edge . s i n k ] ) {
//we found a s h o r t e d path t o t he s i n k Node
c o s t s [ edge . s i n k ] = edg eCo st s ;
prev [ edge . s i n k ] = edge . s o u r c e ;
queue . decr ea seK ey ( edge . s i n k , edg eCo st s ) ;
}// e n d i f
}// e n d f o r
}// e n d w h i l e
5.3.1.6
19
Beispiel
Dieser Abschnitt zeigt die Arbeitsweise des Dijkstra-Algorithmus an einem kleinen Beispiel.
Ausgehend vom Altstadtmarkt um 10:35 soll der Schlachthof erreicht werden.
Schritt 1
Vorher:
Queue
Altstadtmarkt=10:35
Schlachthof=∞
Martin Luther Platz=∞
Kosten
Altstadtmarkt=10:35
Schlachthof=∞
Martin Luther Platz=∞
Vorgänger
Schlachthof: Martin Luther Platz: Altstadtmarkt: Martin Luther Platz
Fussmarsch(5min)
293(10:53-10:54)
287
293
Altstadtmarkt
10:35
Fussmarsch(20min)
Schlachthof
Es wird der Startknoten betrachtet, und alle seine Kanten werden traversiert.
Schritt 2
Vorher:
Queue
Martin Luther Platz=10:40
Schlachthof=10:55
20
Kosten
Altstadtmarkt=10:35
Schlachthof=10:55
Vorgänger
Schlachthof: Altstadtmarkt(Fussmarsch)
Martin Luther Platz: Altstadtmarkt(Fussmarsch)
Altstadtmarkt: 10:40
Martin Luther Platz
Fussmarsch(5min)
10:54
287(10:45-10:47) 293(10:54-10:56)
293(10:53-10:54)
Altstadtmarkt
10:35
Fussmarsch
{20min}
Schlachthof
10:55
Es wird der Knoten mit dem geringsten Gewicht aus der Queue geholt, und alle seine Kanten
werden traversiert.
Schritt 3
Vorher:
Queue
Schlachthof=10:47
Kosten
Altstadtmarkt=10:35
Schlachthof=10:47
Vorgänger
Schlachthof: Martin Luther Platz(287)
Martin Luther Platz: Altstadtmarkt(Fussmarsch)
Altstadtmarkt: -
21
10:40
Martin Luther Platz
Fussmarsch(5min)
10:54
287(10:45-10:47)
293(10:54-10:56)
293(10:53-10:54)
Altstadtmarkt
10:35
Fussmarsch
{20min}
10:47
Schlachthof
10:56
10:55
Es wird der Knoten mit dem geringsten Gewicht aus der Queue geholt. Da dieser Knoten
der Zielknoten ist, terminiert der Algorithmus hier und alle Gewichte und Vorgängerknoten
sind ermittelt.
5.3.2
Damerau-Levenshtein-Stringabstand
Um bei der Eingabe von Haltestellen tolerant gegenüber Eingeabefehlern und Unwissenheit des Benutzers bezüglich vollständiger Haltestellennamen zu sein, wurde der DamerauLevenshtein-Abstand benutzt um die Ähnlichkeit zwischen Eingabe zu Haltestellennamen
zu vergleichen. Der Algorithmus vergleicht zwei Zeichenketten miteinander und ist Ähnlichkeitsmaß für diese. Im Gegensatz zum einfachen Levenshtein-Algororithmus werden Vertauschungen mit berücksichtigt. Bei diesem Algorithmus lassen sich die Kosten für die einzelnen
Operationen unterschiedlich gewichten. Diese Operationen sind Einfügen, Löschen und Vertauschen. Da Haltestellen meist aus einem Ortsnamen bestehen, welche der Benutzer eventuell vergisst, wäre es von Nutzen, diesen Algorithmus so zu erweitern, dass es gesonderte
Kosten für das Entfernen eines Teilwortes gibt, welche geringer sind als die Kosten für das
Entfernen jedes einzelnen Zeichens dieses Teilwortes. Bei zwei großen Strings(Zeichenketten)
wächst der Speicheraufwand der Implementierung recht stark an O(n ∗ m). Doch könnte dieser reduziert werden auf O(Min(m, n)) wobei m und n die Längen der beiden Strings sind.
Der Algorithmus wird dazu benutzt, Haltestellen nach ihrem Stringabstand zu sortieren und
in einer Liste anzuzeigen.
5.3.3
Darstellung der Zeit
Da die Graphensuche auf zeitvarianten Graphen beruht, ist die interne Darstellung der Zeit
ein Thema. J2ME benutzt einen Zeitstempel, welcher die Anzahl der Millisekunden seit
1.1.1970 0:00Uhr UTC repräsentiert. Für Fahrpläne benötigt man jedoch Zeitdaten wie Uhrzeit und Wochentag. Diese Umrechnung ist möglich - jedoch auf Kosten der Performance.
Aus diesem Grund wurde anfangs versucht, Uhrzeit und Datum zu trennen. Das macht in der
Praxis wenig Sinn, da es zum Beispiel auch Routen über einen Tag hinaus gibt. Außerdem
ist es bei vielen Fahrplänen der Fall, dass Uhrzeiten kurz nach 0:00Uhr dem vorherigen Tag
zugeordnet werden. Aus diesem Grund ist die Entscheidung letztendlich für den Zeitstempel
gefallen, welcher im Bedarfsfall in Uhrzeit und Tag zerlegt wird.
5.3.4
22
Fahrpläne
Ein wichtiger Teil der öffentlichen Verkehrsmittel sind die Fahrpläne. Um Auskünfte über Abfahrtszeiten geben zu können muss das System diese Fahrpläne kennen. Da es nicht möglich
war, Fahrplandaten der Stadt Erlangen in maschinenlesbarer Form zu bekommen, mussten
diese manuell in diese Form gebracht werden, was viel Zeit in Anspruch nimmt und sehr
fehleranfällig ist.
5.3.5
Kartendaten
Karten sollen zur Orientierung des Benutzers und zur graphischen Veranschaulichung ortsbezogener Sachverhalte dienen. Wenn man einen Atlas oder eine herkömmliche Straßenkarte
benutzt, erkennt man mit etwas Übung sofort, welche Wege geeignet, und welche eher ungeeignet sind. Würde man einem Computer diese Aufgabe stellen aus einem solchen Bild Wege
und Straßen zu finden, könnte er diese Aufgabe nur mit großem Aufwand lösen. Als Alternative gibt es die Möglichkeit, Straßen und Wege explizit zu speichern. Solche Straßenkarten
gibt es, im Allgemeinen sind diese aber nicht frei erhältlich. Somit werden rein bildbasierte
Karten zur Veranschaulichung benutzt. Eine simple Möglichkeit für eine lokale Nutzung einer
Karte wäre zum Beispiel das Einscannen eines Atlas. Diese Idee ist jedoch sehr unpraktisch,
da zusätzlich ein recht genaues (globales) Koordinatensystem innerhalb der Karte benötigt
wird. Eine weitere Möglichkeit an elektronisches Bildmaterial für Karten gelangen, sind die
vielen Online-Routenplaner, welche in den letzten Jahren im Internet entstanden sind.
Zum Beispiel
• Google Maps http://maps.google.de/
• Yahoo!Maps http://maps.yahoo.com/beta/
• Ask.com http://maps.ask.com/maps
Diese Karten bieten den Vorteil, dass sie in verschiedenen Maßstäben vorhanden sind. Um
diese Karten offline benutzen zu können, müssen sie runtergeladen und dem Mobilgerätes zur Verfügung gestellt werden. Diese oben genannten Systeme benutzen eine MercatorProjektion. Somit braucht man noch eine Umrechnung von betreiberinternen Koordinaten
auf Mercator-Koordinaten, welche durch ein wenig Analysieren herauszubekommen sind.
Diese Bilder liegen im .png-Dateiformat vor und sind je nach Inhalt wenige bis einige Kilobyte groß und bilden in der Regel 256x256 Pixel ab. Zu Demonstrationszwecken wird auf die
Karten von Google Maps zurückgegriffen.
5.3.5.1
Referenzsystem
Da es ein Vielzahl von Mobilgeräten gibt, welche wie gesagt teilweise anderes Verhalten
zeigen, lege ich mich auf zwei Referenzsysteme fest, welche mir zum Testen zur Verfügung
stehen:
• K750i der Firma Sony Ericsson[K7507]
• K800i der Firma Sony Ericsson[K8007]
5.3.6
23
Entwicklungsumgebung
Sun[Sun07] sowie viele Hersteller von Mobilgeräten bieten eine komplette Test- und Entwicklungsumgebung für Mobilgeräte unter dem Namen WTK (Wireless Toolkit) an. Die
Entwicklungsumgebung ist für das Entwickeln von größeren Projekten ungeeignet, hierzu
empfiehlt sich die Benutzung der Entwicklungsumgebung Eclipse[Ecl07a] mit dem Plugin
EclipseME[Ecl07b]. In dieser findet sich von der Versionsverwaltung über Codedokumentation mit JavaDoc bis hin zur Codevervollständigung eine Vielzahl von Funktionen, welche dem
Entwickler das Leben leichter machen. Um das kompilierte Programm auf dem Mobilgerät
zum Laufen zu bringen, muss das Programm erst kompiliert, dann in ein Archiv gepackt ,
und zum Schluss an das Mobilgerät übertragen werden (per Datenkabel, BT, Infrarot oder
über ein drahtloses Netzwerk). Das EclipseME-Plugin ermöglicht in Zusammenarbeit mit
dem WTK von SonyEricsson das sogenannte Debug On-Device“ also das Ausführen und
”
Debuggen3 des Programmes auf dem Gerät.
5.3.7
Probleme der J2ME API
Im Vergleich zur API von J2SE hat J2ME eine recht eingeschränkte API.
Mathematische Funktionalität
Zum Beispiel sind die mathematischen Funktionen begrenzt, so gibt es beispielsweise keinen
Arcustangens. Die Lösung für diesen Fall ist eine Reihenentwicklung, was sich jedoch negativ
auf die Ausführungsgeschwindigkeit auswirkt.
Datenstrukturen
Des weiteren sind Strukturen wie die verkettete Listen nicht vorhanden. Jedoch kann man in
den meisten Fällen den Quellcode aus den J2ME-Bibliotheken kopieren und anpassen. Das
ganze funktioniert nicht bei nativen Implementierungen.
Klassenversion
J2ME unterstützt nur Java 1.3 Klassen und somit keine Features wie Generics, das heißt
Parametrisierung von Klassen wie ArrayList<Node> (ArrayList von Nodes). Das führt dazu,
dass man entweder für jeden parametrisierten Typ eine eigene Klasse schreiben muss oder
man übergeordnete Datentypen, im Extremfall Object (die Oberklasse aller Java-Objekte)
benutzt.
Reflections
Reflections heißt im Java-Umfeld Eigenschaften von Klassen zur Laufzeit analysieren und
manipulieren zu können. Somit ist es möglich ein Objekt vom gleichen Typ wie der des Referenzobjektes zu erstellen. Dies ist in J2ME nicht möglich, somit müssen alle Eigenschaften
zur Kompilezeit bekannt sein.
3
Auffinden und Beheben von Softwarefehlern
5.3.8
24
Objektorientierung vs. Performance
Eine der großen Stärken von Java ist das überwiegend objektorientierte Konzept (alle Datentypen außer Zahlen und Zeichen sind Objekte). Dieses Konzept führt bei guter Anwendung
zu besserer Verständlichkeit, Übersichtlichkeit und Wartbarkeit der Software, da sich Klassen
mit einem bestimmten Verhalten (aus der realen Welt) abstrahieren lassen. Jedoch ist das
Erzeugen und Verwerfen von Objekten in Java zeitintensiv.
Objekt Recycling
Um sich das Verwerfen eines veralteten Objektes und das Erstellen eines neuen Objektes
zu ersparen, kann man sich die Möglichkeit offen halten, das alte Objekt zu modifizieren
und damit aktuell zu halten. Das kann aber zu ungewünschten Seiteneffekten führen, da das
Objekt möglicherweise noch an anderen Stellen benutzt wird, wobei dort evtl. von der alten
”
Version“ des Objektes ausgegangen wird.
Primitive Datentypen
Da primitive Datentypen nicht erzeugt und verworfen werden müssen, sondern einfach existieren, bis sie aus dem Scope4 fallen, ist dieses Vorgehen in manchen Fällen eine Alternative
zu Objekten mit geringer Funktionalität.
Zum Beispiel gab es eine Klasse Point mit den Eigenschaften x und y für die Koordinaten sowie die toString()-Methode welche das ganze leserlich formatiert. Da im Rahmen der
Koordinatentransformation viele dieser Points erzeugt, ausgelesen und neu erzeugt werden,
wurde diese Vorgehen einfach ersetzt durch unterschiedliche Behandlungsroutinen für die xund die y-Werte und eine externe Funktionalität zur leserlichen Formatierung der Werte.
Damit brauchte man keine Objekte.
Strings
Obwohl Strings in Java ein wenig besonders behandelt werden (konstante Strings ”Text”,
Konkatenation mit Infixoperator +“), sind sie trotzdem Objekte. Besonders tückisch ist die
”
Konkatenation, wie folgendes Beispiel zeigt:
S t r i n g s = ”a ”
s = s + ”b ”
Man könnte meinen, dass der String verändert worden ist, jedoch existiert der String ”a”
weiterhin, und es wird ein neues String-Objekt erzeugt und die Referenz darauf gesetzt. In
einem solch einfachen Beispiel ist das nicht weiter tragisch, jedoch wenn man das ganze in
einer Schleife macht
4
Gültigkeitsbereich des Programms
25
S t r i n g t o S t r i n g ( O bj ect [ ] oa ) {
S t r i n g s = ””;
f o r ( i n t i = 0 ; i < oa . l e n g h t ; i ++) {
s += oa [ i ] . t o S t r i n g ( ) ;
}
return s ;
}
wird in jedem Schleifendurchlauf ein neues Objekt erstellt, welches im nächsten Schleifendurchlauf wieder verworfen wird. Für solche Fälle ist es ratsam die Klasse StringBuffer zu
benutzen
S t r i n g t o S t r i n g ( O bj ect [ ] oa ) {
S t r i n g B u f f e r sb = new S t r i n g B u f f e r ( ) ;
f o r ( i n t i = 0 ; i < oa . l e n g t h ; i ++) {
sb . append ( oa [ i ] . t o S t r i n g ( ) ) ;
}
r e t u r n sb . t o S t r i n g ( ) ;
}
Diese Klasse benutzt einen internen Puffer, welcher nur bei Bedarf vergrößert (also neu
erzeugt und kopiert) wird.
90/10 Regel
Diese Faustregel besagt, dass ein Programm zirka 90% der Zeit in zirka 10% des Codes
verbringt. Somit ist es am effektivsten diese 10% des Code zu finden und zu optimieren
und dabei die restlichen 90% des Code sauber und verständlich zu halten. Zur Analyse des
Laufzeitverhaltens und Speicherverbrauchs liefert das WTK ein Profiling- und EmulationsTool mit, mit dem sich Flaschenhälse“ im Programm auffinden lassen.
”
5.3.9
Optimierung
Reduktion der Linien
In der Realität werden gleichnamige Linien teilweise durch Varianten unterschiedlicher Streckenführung zusammengefasst. Im Gegensatz zu unterschiedlichen Linien fahren die Varianten jedoch nicht gleichzeitig und sind damit zeitlich disjunkt. Bei der bisherigen Implementierung wird der einfacheren Parametrierung halber für jede Variante eine Linie modelliert.
Diese Tatsache führt im erzeugten Graphen dazu, dass dieser unnötig anwächst. Für spätere Implementierung und Parametrierung sollten die Varianten einer Linie zu einer Linie
verschmelzen.
26
Optimierung des Suchalgorithmus
Wie bereits erwähnt, wurde als Graphensuchalgotithmus nur der Dijkstra-Algorithmus implementiert. Eine informierte Suche, wie mit A* (A Stern) ist jedoch noch effektiver. Da
als Anhaltspunkte geographische Distanzen und Richtungen vorhanden sind, sollte eine gute
Heuristik gegeben sein. Der A* hat im klassischen Fall eines Graphen (mit kostanten Kantengewichten) einen großen Overhead, jedoch werden weniger Knoten besucht. Damit ist der
Aufwand vergleichbar mit dem des Dijkstra-Algorithmus.
Da in unserem Fall jedoch keine konstanten Kantengewichte vorhanden sind, sondern es
schon bei der Ermittlung der Gewichte ein Overhead gibt, sollte der Overhead des A* nicht
mehr so stark ins Gewicht fallen und damit sollte A* einen Vorteil erlangen.
Optimierung im Suchalgorithmus
Der Flaschenhals des Dijkstra-Algorithmus ist die Suche nach dem kleinsten Element und die
Verringerung des Wertes eines Elements in der Fibonacci-Heap. Im Vergleich zu den meisten
Graphen gibt es viele Kanten zwischen zwei Knoten, damit kann man die Suche abkürzen,
indem man den neuen Wert des Zielknotens erst dann ändert, sobald man alle Kanten eines Knotens traversiert hat, welche zu dem selben Zielknoten führen. Bei diesem speziellen
zeitbehafteten Graphen überwiegt die Suche nach Abfahrtszeiten, also die Kantengewichte.
Die Suche nach der nächsten Abfahrtszeit läßt sich abkürzen, indem man eine maximale Zeit
vorgibt, in welcher eine Abfahrt sinnvoll ist. Dafür kann die momentane Ankunftszeit am
Zielknoten benutzt werden.
5.3.10
Zugriff auf externe Daten
Da eine Trennung zwischen Programmlogik und Daten (Bilddaten, Fahrplandaten, geographische Daten) erfolgen soll, müssen die Daten außerhalb des Programmes zur Verfügung
gestellt werden.
5.3.10.1
Dateien im Dateisystem
Die meisten modernen Mobilgeräte besitzen einen internen Flash-Speicher sowie Erweiterungsmöglichkeiten für Festspeicher in Form von Speicherkarten. Diese Form des Speichers
ist vergleichbar mit einer Festplatte oder einem Memorystick am PC. Der Zugriff aus diesen
Speicher erfolgt entweder intern im Handy, per Bluetooth/Infrarot oder per Datenkabel und
Software am PC.
5.3.10.2
Gefahren und Probleme bei externen Daten
Da Java-MIDlets eher eine Art plattformunabhängige Plugins sind, welche prinzipiell von
jedermann geschrieben werden können, steckt in ihnen ein Gefahrenpotenzial bezüglich Missbrauch des Mobilgerätes, Spionage und Zerstörung von Daten. Aus diesem Grund wird ein
MIDlet in einer Art Sandbox“ ausgeführt, in der es keinen Zugriff auf die Funktionalität
”
des Handys hat. Bald wurde erkannt, dass das zu einer sehr eingeschränkten Funktionalität führt und das Sandbox-Prinzip“ insofern erweitert, dass der Benutzer jede potentiell
”
unsichere Aktion bestätigen muss.
27
Probleme
Allein die Bilddaten der Karten umfassen für ein Ballungszentrum mehrere tausend Dateien,
von denen immer ca. neun Stück geladen werden. Des weiteren wird bei der aktuellen Implementierung für jede Buslinie und Variante eine eigene Datei benutzt. Somit kommt man
schnell auf einige dutzend Sicherheitsabfragen an den Benutzer. Dies macht das Programm
langsam und vor allem ist es dem Benutzer nicht zumutbar.
Rechtevergabe Der Benutzer kann dem MIDlet jedoch Rechte für bestimmte Klassen von
Operationen gewähren, und entscheiden, ob:
• kein Zugriff gewährt wird
• jedesmal eine Sicherheitsabfrage für diese Operationsklasse gestellt wird
• einmalige Sicherheitsabfrage für diese Operationsklasse gestellt wird
• der Zugriff auf diese Operationsklasse immer (ohne Frage) gewährt wird
Bei den meisten Mobilgeräten wird für die Rechtevergabe eine gültige Lizenz benötigt, mit
welcher das MIDlet signiert sein muss und das Mobilgerät muss diese als Java-Lizenz bereits
kennen. Es gibt auf den Mobilgeräten schon einige Lizenzen kommerzieller Anbieter. Diese
Lizenzen sind aber an recht hohe und laufende Kosten gebunden und sind für die Entwicklung
unflexibel, da jede Version der jar-Datei vom Lizenzgeber auf Sicherheitslücken untersucht
und lizensiert wird.
Lösungsansätze
Erhöhung der Kopplung Entgegen der eigentlichen Zielsetzung kann man zumindest
die Kartendaten und das Programm koppeln, indem man alles in eine jar-Patei packt, und
damit Sicherheitsabfragen verhindern, da das MIDlet nur auf eigene Dateien zugreift und
nicht aus der Sandbox“ heraus operiert. Fahrplandaten lassen sich prinzipiell auch in einer
”
Datei zusammenfassen, was die Anzahl der Zugriffe stark verringert. Das Problem bei diesem
Ansatz ist, dass die jar-Datei exterm aufgebläht wird. Somit ist die Größe des internen
Speicher des Mobilgerätes ein Problem, und einige Hersteller erlauben aus Sicherheitsgründen
nur eine MIDletgröße von 300Kilobyte.
Externes Archiv Da jar-Dateien prinzipiell nichts anderes als zip-Dateien sind, liegt der
Ansatz nahe, externe jar- und zip-Dateien auszulesen. Ein einziges Archiv bringt auch den
Vorteil mit sich, dass bei vielen kleinen Dateien nicht so viel Speicherplatz verschwendet
wird, da die Dateien im Archiv nicht in Zuordnungseinheiten abgelegt werden.
Die J2ME API bietet jedoch keine Möglichkeit solche Archive auszulesen.
28
Eigene Implementierung Der Großteil der externen Dateien besteht aus Kartendaten
in Form von .png-Dateien. Diese sind bereits komprimiert und somit bringt eine erneute
Zip-Kompression - wenn überhaupt - nur geringe Vorteile.
Ein Zip-Archiv läßt sich auch ohne Kompression mit Dateien füllen.
Eine eigene Implementierung ist daran gescheitert, dass innerhalb der Archiv-Datei gesprungen werden muss und bei jedem Zugriff wieder eine Sicherheitsabfrage stattfindet.
Eigene Zertifikate Java liefert ein Tool zur Erstellung eigener Zertifikate mit. Mit diesen lassen sich die MIDlets auch signieren. Das Problem bei diesem Ansatz ist, dass das
Mobilgerät das Zertifikat nicht kennt.
Senden des Zertifikates Es ist möglich, das eigene Zertifikat per BT an das K800i zu
senden. Es wird dort als Zertifikat erkannt und behandelt. Jedoch nicht als Java-Zertikat
sondern nur als Zertifikat für sichere Internetverbindungen.
Herstellersupport Der Hersteller Sony Ericsson verweist auf seiner Entwicklerseite auf die
J2ME-Spezifikation, welche besagt, dass der Benutzer keine eigenen Zertifikate installieren
darf. Zertifikate werden bei der Herstellung und Anpassung an Kundenwünscheauf( Customization“)
”
das Handy installiert [Zit07]. Somit ist vom Hersteller keine Möglichkeit des Zertifikateimports auf das Handy gegeben.
Customization Durch eine weite Verbreitung von Mobilgeräten und eine große Stückzahl
gibt es heutzutage viele externe Tools zum Zugriff auf Mobilgeräte. Die Funktionalität dieser geht vom Verwalten von Kontaktdaten, bis hin zur Dateiverwaltung. Einige Programme
gehen sogar noch weiter und bieten Individualisierung von Oberflächen und Verhalten des
Mobilgerätes an, was im Endeffekt eine Umprogrammierung bedeutet. Dabei wird direkt auf
das interne Dateisystem des Mobilgerätes zugegriffen und dieses manipuliert. Mit diesem Ansatz läßt sich das eigene Zertifikat problemlos auf das K750i kopieren und installieren. Dieses
Vorgehen ist jedoch nicht im Interesse des Herstellers, wahrscheinlich weil er selbst einen
Markt für Customization und Verträgen mit den Zertifizierungsstellen sieht. Deshalb wird in
jeder Generation von Mobiltelefonen ein neueres und komplizierteres Komunikationsprotokoll
implementiert um externe Programme wenigstens für eine gewisse Zeit auszutricksen. Aus
diesem Grund ist das Vorgehen wie bei dem K750i auf dem K800i nicht möglich. Inzwischen
haben auch Fremdanbieter einen Markt zum Customizen“ entdeckt und bieten kommerzielle
”
Programme mit mehr Know-How an, welche Lücken zum Zugriff auf das Dateisystem bieten.
So gibt es eine Möglichkeit, dass beim Neustarten des K800i Daten aus dem externen Dateisystem in das interne Dateisystem kopiert werden und verschiedene Befehle, wie einbinden
von Zertifikaten möglich sein sollten.
Diesen Ansatz habe ich bis jetzt nicht weiter verfolgt, da durch ein Firmware-Update des
K800i die Möglichkeit besteht auch ohne Zertifizierung Rechte zu gewähren. Somit ist das
Problem zumindest während der Entwicklung gelöst.
29
Alle hier genannten Verfahren führen zum Verlust von Garantie und Gewährleistung des
Händlers und Herstellers und sind somit auf eigene Gefahr durchzuführen. Die Recherche
und die Versuche haben sehr viel Zeit in Anspruch genommen und einige Situationen herbeigeführt, in denen das Mobiltelefon defekt zu sein schien.
Kommerzielle Zertifikate Für später Nutzung steht einem Erwerb von kommerziellen
Zertifikaten nichts im Wege.
5.3.10.3
Struktur im Dateisystem
Es werden abhängig von der Größe der zur Verfügung stehenden Karte sehr viele Bilddateien
benötigt. Das führt einerseits zu hohen Zugriffszeiten bei Verzeichnissen mit vielen Dateien,
was aber durch geschicktes Hashing5 umgangen werden kann.
Andererseits kommt es bei Verwendung vieler kleiner Dateien zu Platzverschwendung, da
Dateien im Normalfall in Zuordnungseinheiten abgelegt werden, wobei jede Zuordnungsdatei nur zu maximal einer Datei gehören kann. Wenn jedoch die Zuordnungsdatei wesentlich
größer als die Datei ist, wird ein Teil dieser Zuordnungseinheit verschenkt. Die Größe der
Zuordnungseinheiten lässt sich beim Formatieren des Datenträgers in einem betimmten Rahmen festlegen.
Wählt man die Zuordnungseinheiten jedoch zu klein, kommt es bei großen Dateien zu einem größeren Overhead im Dateizuordnungskatalog, da mehr Zuordnungseinheiten pro Datei
benötigt werden.
5.3.10.4
Recordstores
Um Daten speichern zu können bietet J2ME die Möglichkeit von sogenannten Recordstores,
das sind externe Objekte zum Speichern von Byte-Feldern. Der Zugriff auf diese ist jedoch
sehr beschränkt und die Größe sehr klein, damit eignen sie sich zum Speichern von Benutzereingaben.
Recordstores sind in etwa vergleichbar mit der Windows-Registry.
5
Zusammenfassung aufgrund von Streuwerten
6. Evaluierung
6.1
Routensuche
Die Hauptaufgabe des Programmes ist es, den Benutzer zwischen zwei Punkten so gut wie
möglich zu navigieren. Um einen Qualitätsvergleich zu bekommen, werden einige Beispielrouten mit denen des VGN verglichen.
Als Marschgeschwindigkeit(Luftlinie) wird eine Geschwindigkeit von 0.9 ms angenommen.
6.1.1
Fall 1
20.7.2007 11:49Uhr Erlangen Eskilstunastrasse - Erlangen Technische Fakultät
Studienarbeit
Time needed: 0.688sec
free:3217304
=========================================
Tracing:
time:12:16
time:12:15 Edge: graph.Node(Erlangen Stettiner Str.)-graph.Node(Erlangen Technische Fakultät) Line 293_1
time:12:14 Edge: graph.Node(Erlangen Theodor-Heuss-Anlage)-graph.Node(Erlangen Stettiner Str.) Line 293_1
time:12:12 Edge: graph.Node(Erlangen Sebaldusstr.)-graph.Node(Erlangen Theodor-Heuss-Anlage) Line 293_1
time:12:11 Edge: graph.Node(Erlangen Schenkstr.)-graph.Node(Erlangen Sebaldusstr.) Line 293_1
time:12:9 Edge: graph.Node(Erlangen Luise-Kiesselbach-Str.)-graph.Node(Erlangen Schenkstr.) Line 293_1
time:12:6 Edge: graph.Node(Erlangen Doris-Ruppenstein-Str.)-graph.Node(Erlangen Luise-Kiesselbach-Str.) Line 293_1
time:11:56 Edge: graph.Node(Erlangen Berufsschulzentrum)-graph.Node(Erlangen Doris-Ruppenstein-Str.)Fussmarsch
time:11:54 Edge: graph.Node(Sieglitzhof Markuskirche)-graph.Node(Erlangen Berufsschulzentrum) Line 284_2
time:11:53 Edge: graph.Node(Sieglitzhof Schronfeld)-graph.Node(Sieglitzhof Markuskirche) Line 284_2
time:11:52 Edge: graph.Node(Sieglitzhof Theresiakirche)-graph.Node(Sieglitzhof Schronfeld) Line 284_2
time:11:51 Edge: graph.Node(Sieglitzhof Rennesstr.)-graph.Node(Sieglitzhof Theresiakirche) Line 284_2
time:11:49 Edge: graph.Node(Sieglitzhof Eskilstunastr.)-graph.Node(Sieglitzhof Rennesstr.) Line 284_2
VGN
12:05
12:16
12:18
12:29
Uhr
Uhr
Uhr
Uhr
ab
an
ab
an
Sieglitzhof Eskilstunastr. Stadtbus 294
Erlangen Langemarckplatz Eltersdorf Volckamerstr.
Erlangen Langemarckplatz Stadtbus 287
Erlangen Technische Fakultät Erlangen Sebaldussiedlung
Auswertung
Da ein zehnminütiger Fußmarsch eingelegt wird, findet der Suchalgorithmus einen besseren
Weg als der Betreiber VGN.
6.1. Routensuche
6.1.2
31
Fall 2
20.7.2007 12:20Uhr Erlangen Eskilstunastrasse - Erlangen Technische Fakultät
Studienarbeit
free:3073108
=========================================
Tracing:
time:12:36
time:12:35 Edge: graph.Node(Erlangen Stettiner Str.)-graph.Node(Erlangen Technische Fakultät) Line 293_1_2
time:12:34 Edge: graph.Node(Erlangen Theodor-Heuss-Anlage)-graph.Node(Erlangen Stettiner Str.) Line 293_1_2
time:12:32 Edge: graph.Node(Erlangen Sebaldusstr.)-graph.Node(Erlangen Theodor-Heuss-Anlage) Line 293_1_2
time:12:31 Edge: graph.Node(Erlangen Schenkstr.)-graph.Node(Erlangen Sebaldusstr.) Line 293_1_2
time:12:29 Edge: graph.Node(Erlangen Luise-Kiesselbach-Str.)-graph.Node(Erlangen Schenkstr.) Line 293_1_2
time:12:28 Edge: graph.Node(Erlangen Doris-Ruppenstein-Str.)-graph.Node(Erlangen Luise-Kiesselbach-Str.) Line 293_1_2
time:12:27 Edge: graph.Node(Erlangen Siemens Med)-graph.Node(Erlangen Doris-Ruppenstein-Str.) Line 293_1_2
time:12:27 Edge: graph.Node(Erlangen Hartmannstr.)-graph.Node(Erlangen Siemens Med) Line 293_1_2
time:12:26 Edge: graph.Node(Erlangen Berufsschulzentrum)-graph.Node(Erlangen Hartmannstr.) Line 284_2
time:12:20 Edge: graph.Node(Sieglitzhof Eskilstunastr.)-graph.Node(Sieglitzhof Rennesstr.) Line 284_2
VGN
12:20
12:31
12:38
12:49
Uhr
Uhr
Uhr
Uhr
ab
an
ab
an
Sieglitzhof Eskilstunastr. Stadtbus 284
Erlangen Langemarckplatz Bruck/ER Eichendorffschule
Erlangen Langemarckplatz Stadtbus 287
Erlangen Technische Fakultät Erlangen Sebaldussiedlung
Auswertung
Obwohl der Suchalgorithmus diesmal keinen Fußmarsch vorschlägt, braucht der vom VGN
errechnete Pfad wieder länger. Das Problem ist ein geänderter Fahrplan der VGN, die Linie
293 fährt an der Hartmannstraße 12:26 statt 12:27 ab
6.1.3
Fall 3
20.7.2007 8:54Uhr Erlangen Technische Fakultät - Erlangen Eskilstunastrasse
Studienarbeit
free:431056
=========================================
Tracing:
time:9:31
time:9:28 Edge: graph.Node(Sieglitzhof Im Heuschlag)-graph.Node(Sieglitzhof Eskilstunastr.) Line 294_1
time:9:19 Edge: graph.Node(Erlangen Gedelerstr.)-graph.Node(Sieglitzhof Im Heuschlag)Fussmarsch
time:9:18 Edge: graph.Node(Sieglitzhof Markuskirche)-graph.Node(Erlangen Gedelerstr.) Line 285_1
time:9:16 Edge: graph.Node(Erlangen Berufsschulzentrum)-graph.Node(Sieglitzhof Markuskirche) Line 285_1
time:9:15 Edge: graph.Node(Erlangen Hartmannstr.)-graph.Node(Erlangen Berufsschulzentrum) Line 285_1
time:9:14 Edge: graph.Node(Erlangen Zollhaus)-graph.Node(Erlangen Hartmannstr.) Line 285_1
time:9:13 Edge: graph.Node(Erlangen Stubenlohstr.)-graph.Node(Erlangen Zollhaus) Line 285_1
time:9:11 Edge: graph.Node(Erlangen Langemarckplatz)-graph.Node(Erlangen Stubenlohstr.) Line 285_1
time:9:10 Edge: graph.Node(Erlangen Siemens-Verwaltung)-graph.Node(Erlangen Langemarckplatz) Line 287_1_2
time:9:9 Edge: graph.Node(Erlangen Mozartstr.)-graph.Node(Erlangen Siemens-Verwaltung) Line 287_1_2
time:9:8 Edge: graph.Node(Erlangen Anton-Bruckner-Str.)-graph.Node(Erlangen Mozartstr.) Line 287_1_2
time:9:7 Edge: graph.Node(Erlangen Berliner Platz)-graph.Node(Erlangen Anton-Bruckner-Str.) Line 287_1_2
time:9:6 Edge: graph.Node(Erlangen Röthelheimbad)-graph.Node(Erlangen Berliner Platz) Line 287_1_2
time:9:5 Edge: graph.Node(Erlangen Gleiwitzer Str.)-graph.Node(Erlangen Röthelheimbad) Line 287_1_2
time:9:4 Edge: graph.Node(Erlangen Görlitzer Str.)-graph.Node(Erlangen Gleiwitzer Str.) Line 287_1_2
time:9:3 Edge: graph.Node(Erlangen Theodor-Heuss-Anlage)-graph.Node(Erlangen Görlitzer Str.) Line 287_1_2
time:8:59 Edge: graph.Node(Erlangen Thomaskirche)-graph.Node(Erlangen Theodor-Heuss-Anlage) Line 287_1_2
time:8:54 Edge: graph.Node(Erlangen Technische Fakultät)-graph.Node(Erlangen Thomaskirche)Fussmarsch
6.1. Routensuche
32
VGN
09:12
09:23
09:26
09:33
Uhr
Uhr
Uhr
Uhr
ab
an
ab
an
Erlangen Technische Fakultät Stadtbus 293
Erlangen Hartmannstr. Büchenbach/ER Mönaustr.
Erlangen Hartmannstr. Stadtbus 294
Sieglitzhof Eskilstunastr. Sieglitzhof Eskilstunastr.
Auswertung
VGN benutzt einen anderen Bus, zu einem späteren Zeitpunkt und ist effektiv zur gleichen
Uhrzeit am Ziel. Desweiteren wird es wohl von den meisten Menschen nicht als besonders
effektiv angesehen die erste Station zu laufen statt am Startpunkt auf den Bus zu warten.
Beiden Varianten lassen sich Vor- und Nachteile abgewinnen.
6.1.4
Fall 4
20.7.2007 8:54Uhr Erlangen Technische Fakultät - Steudach Westfriedhof
Studienarbeit
free:490464
=========================================
Tracing:
time:9:53
time:9:16 Edge: graph.Node(Erlangen Am Hafen)-graph.Node(Steudach Westfriedhof)Fussmarsch
time:9:13 Edge: graph.Node(Erlangen Bayernstr.)-graph.Node(Erlangen Am Hafen) Line 289_2
time:9:12 Edge: graph.Node(Erlangen Äußere Brucker/P.-Gossen-Str.)-graph.Node(Erlangen Bayernstr.) Line 289_2
time:9:11 Edge: graph.Node(Erlangen Wichernstr.)-graph.Node(Erlangen Äußere Brucker/P.-Gossen-Str.) Line 289_2
time:9:10 Edge: graph.Node(Erlangen Forschungszentrum)-graph.Node(Erlangen Wichernstr.) Line 289_2
time:9:9 Edge: graph.Node(Erlangen Wehneltstr.)-graph.Node(Erlangen Forschungszentrum) Line 289_2
time:9:8 Edge: graph.Node(Erlangen Gebbertstr.)-graph.Node(Erlangen Wehneltstr.) Line 289_2
time:9:4 Edge: graph.Node(Erlangen Görlitzer Str.)-graph.Node(Erlangen Gebbertstr.)Fussmarsch
time:9:3 Edge: graph.Node(Erlangen Theodor-Heuss-Anlage)-graph.Node(Erlangen Görlitzer Str.) Line 287_1_2
time:8:59 Edge: graph.Node(Erlangen Thomaskirche)-graph.Node(Erlangen Theodor-Heuss-Anlage) Line 287_1_2
time:8:54 Edge: graph.Node(Erlangen Technische Fakultät)-graph.Node(Erlangen Thomaskirche)Fussmarsch
VGN
09:20 Uhr ab Erlangen Technische Fakultät Stadtbus 287
10:07 Uhr an Steudach Westfriedhof Steudach Westfriedhof
Auswertung
Die Route des VGN berechnet zwar einen Pfad mit kürzerer Verweildauer im Bus, jedoch ist
die Ankunftszeit der Studienarbeit früher und damit scheinbar optimal.
6.1.5
Fall 5
20.7.2007 9:05Uhr Erlangen Rennesstraße - Bruck/Erlangen Am Anger
Studienarbeit
free:2429812
=========================================
Tracing:
time:9:27
time:9:26 Edge: graph.Node(Erlangen Zentralfriedhof)-graph.Node(Erlangen Am Anger) Line 294_2
time:9:25 Edge: graph.Node(Erlangen Baumwollspinnerei)-graph.Node(Erlangen Zentralfriedhof) Line 294_2
time:9:21 Edge: graph.Node(Erlangen Hauptpost)-graph.Node(Erlangen Baumwollspinnerei) Line 294_2
time:9:20 Edge: graph.Node(Erlangen Bahnhofplatz)-graph.Node(Erlangen Hauptpost) Line 289_2
time:9:18 Edge: graph.Node(Erlangen Hugenottenplatz)-graph.Node(Erlangen Bahnhofplatz)Fussmarsch
time:9:16 Edge: graph.Node(Erlangen Obere Karlstr.)-graph.Node(Erlangen Hugenottenplatz) Line 294_2
time:9:15 Edge: graph.Node(Erlangen Langemarckplatz)-graph.Node(Erlangen Obere Karlstr.) Line 294_2
time:9:13 Edge: graph.Node(Erlangen Stubenlohstr.)-graph.Node(Erlangen Langemarckplatz) Line 294_2
time:9:12 Edge: graph.Node(Erlangen Zollhaus)-graph.Node(Erlangen Stubenlohstr.) Line 294_2
time:9:11 Edge: graph.Node(Erlangen Hartmannstr.)-graph.Node(Erlangen Zollhaus) Line 294_2
time:9:10 Edge: graph.Node(Erlangen Berufsschulzentrum)-graph.Node(Erlangen Hartmannstr.) Line 294_2
6.2. Interaktivität
33
VGN
09:06 Uhr ab Sieglitzhof Rennesstr. Stadtbus 294
09:26 Uhr an Erlangen Am Anger Eltersdorf Volckamerstr.
Auswertung
Die Studienarbeit findet einen Pfad mit gleicher Endzeit wie der VGN, jedoch wird der
Benutzer sinnloserweise einmal aufgefordert umzusteigen.
6.1.6
Zusammenfassung - Routensuche
Die zentrale Routensuche hat bei allen Tests gezeigt, dass die gefundenen Routen den gesetzten Anforderungen genügen.
6.2
Interaktivität
Der Benutzer soll nicht all zu lang auf das Ergebnis von Berechnungen warten müssen, und
erst recht nicht glauben, die Anwendung würde überhaupt nicht mehr reagieren. In diesem
Abschnitt werden die Mobiltelefone K750i, K800i und der Emulator auf dem PC (AMD
Athlon 1.8GHz beziehungsweise 0.5GHz) verglichen
6.2.1
Routensuche
Der wichtigste und in den meisten Fällen aufwändigste Teil der Berechnung ist die Routensuche. Sie ist abhängig von der Größe (wieviele Linien/Haltestellen) und Art des Graphen(mit/ohne Fußmärschen/Umsteigestrafen), wobei sich die Variante ohne Umsteigestrafen und mit Fußmärschen bewährt hat.
Benchmark
Bei allen Routen wird ein Startzeitpunkt von 20.7.2007 9:05Uhr und eine Marschgeschwindigkeit(Luftlinie) von 0.9 ms angenommen. Strafzeiten sind deaktiviert.
Die folgenden Werte sind in Sekunden(sek) zu verstehen.
Route
K750i K800i [email protected] [email protected]
Rennesstrasse-Am Anger
1.673 0.372
0.406
1.75
Techn. Fakultät-St.Johann
3.244 0.609
0.735
3.625
Waldkrankenhaus-Am Hafen 3.076 0.645
0.75
3.437
6.2.2
Damerau-Levenshtein
Wenn der Benutzer die Eingabe einer Haltestelle verändert, soll sich die Liste mit ähnlichen
Haltestellen aktualisieren. Um die Ähnlichkeit der Haltestellennamen zu vergleichen wird der
Damerau-Levenshtein-Abstand benutzt.
Nachfolgender Test zeigt die benötigte Zeit zum Testen aller Haltestellen mit einem vogegebenen Wort.
6.3. Bildschirmausschnitte
34
Benchmark
Die folgenden Werte sind in Millisekunden(ms) zu verstehen.
Wort
K750i K800i [email protected] [email protected]
’a’
100
17
32
125
’Heuschlag’
267
94
313
828
’Erlangen Eskilstunastrasse’
568
281
516
2672
6.2.3
Zusammenfassung - Interaktivität
Die beiden Mobiltelefone unterscheiden sich in ihrer Rechenleistung deutlich. Jedoch besitzt selbst das K750i Rechenleistung, um hohe Interaktivität zu gewährleisten. Ein noch
leistungsschwächeres Mobiltelefon ist jedoch nicht zu empfehlen.
6.3
Bildschirmausschnitte
Das Linke Bild zeigt einen Ausschnitt aus der Visualisierung, das rechte Bild einen Ausschnitt
aus der GUI.
6.4. Kritische Betrachtung der Arbeit und Ausblick
6.4
35
Kritische Betrachtung der Arbeit und Ausblick
6.4.1
Lösungsansatz
Der betrachtete Ansatz eines Offline-Systems wird in Zukunft immer mehr an Vorteilen
verlieren, da Kosten für mobiles Internet immer weiter sinken und inzwischen sogar Flatrates1
angeboten werden.
6.4.2
Hardwareanforderungen
Zu Beginn der Arbeit wurde nur das K750i benutzt, dabei kamen schon Sorgen auf, dass
Rechenleistung und Speicher für große Ballungsräume ein Problem darstellen.
Da der Sprung von einer Mobiltelefongeneration zur nächsten anscheinend so groß ist, wird
die Hardware in Zukunft ausreichend sein um mit solchen Problemen zurechtzukommen.
6.4.3
Modellierung der Fahrpläne
Die Modellierung der Fahrpläne ist noch nicht optimal, unter anderem dadurch, dass Ankunftszeit und Abfahrtszeit als identisches Punktereigniss betrachtet werden. Des weiteren
werden nur Fahrpläne betrachtet und keine zyklisch operierenden Verkehrsmittel, wie sie in
einigen Städten zu finden sind.
6.4.3.1
Verspätungen
Eine Erweiterung des Modells ist die Betrachtung von Verspätungen zu Hauptverkehrszeiten.
So kann man die Strafzeiten abhängig von der Uhrzeit machen, um so eine Veränderung des
Risikos beim Umsteigen zu modellieren.
6.4.4
Erreichte Ziele
Die meisten der Anfangs gesteckten Ziele wurden erreicht, jedoch nicht alle Ziele konnten
aufgrund des Umfangs in einer Studienarbeit verwirklicht werden.
6.4.4.1
Zielführung
Die Zielführung beschränkt sich darauf, die aktuelle Position, Start-, Zwischen- und Endpunkte anzuzeigen, jedoch wäre eine Übersichtliche Anzeige zum Beispiel in Form eines
Kompass wünschenswert.
6.4.4.2
Parametrierung
Die Datenstrukturen für Persistenz2 sind vorhanden, jedoch sind Parametrierungen für Art
des Graphen sowie freie Wahl von Start und Zielkoordinaten nicht ausreichend implementiert.
6.4.4.3
Suchalgorithmen
Ein Vergleich mit anderen Suchalgorithmen wäre wünschenswert gewesen.
1
2
Volumen- und Zeitunabhängige Nutzung
Dauerhafte Speicherung von Daten
6.4. Kritische Betrachtung der Arbeit und Ausblick
36
Suche nach Ankunftszeit
Die Suche nach der spätest möglichen Abfahrtszeit bei vorgegebener Ankunftszeit wurde
nicht implementiert, jedoch sollte sie sich nur unwesentlich von der bereits vorhandenen
Suche unterscheiden.
6.4.5
Tests
Diese Arbeit hat sich als Ziel gesetzt, plattformunabhängig zu sein. Es wurde zwar versucht, gegen Schnittstellen und nicht gegen Implementierungen zu schreiben, jedoch ist ein
Test immer notwendig um die Funktion zu zeigen. Aus diesem Grund wären weitere Geräte unterschiedlicher Hersteller nötig um die Funktionsfähigkeit zu testen und Anpassungen
durchzuführen, die das System implementierungsunabhängig zu machen.
6.4.6
GPS
Zum Benutzen des GPS wurde teilweise eine externe Bibliothek verwendet. Diese bietet
einen zu großen Funktionsumfang. Desweiteren konnte kein interner GPS-Empfänger getestet
werden.
6.4.7
Analyse und Design
Software-Entwicklung sollte in der Regel so ablaufen, dass man sich einen Plan über den
Funktionsumfang der Software macht. Darauf hin fertigt man einen Grobentwurf an, welcher
die Architektur und das grobe Klassengeflecht beschreibt. Danach kommt der Feinentwurf
und schlußendlich die Implementierung.
Da diese Studienarbeit teilweise aus einem Seminar und dessen Code heraus gewachsen ist,
war die Herangehensweise eine andere, d.h. der Entwurf ist parallel zum Code entstanden.
Außerdem waren Probleme und deren Lösungen anfangs nicht bekannt und somit sind Teile
des Designs und Code aus Trial-and-Error“3 heraus entstanden.
”
3
Problemlösung durch Ausprobieren
7. Ausblick und Zusammenfassung
7.1
Mögliche Erweiterungen
Optimierung
Für die Routensuche sind weitere Optimierungskriterien vorstellbar, wie z.B.
• so wenig Umstiege wie möglich
• so geringe Tarifkosten wie möglich
• eine gewichtete Kombination aus Kriterien
Jedoch wird eine zu große Auswahl von Kriterien den nicht-ambitionierten Benutzer mit
hoher Wahrscheinlichkeit vor Verständnisprobleme stellen, weshalb er nur grobe Parametrierungen vornehmen können sollte.
Updates
Um die Fahrpläne und POIs auf aktuellem Stand zu halten, wäre ein Online-Update denkbar.
Diese ließen sich z.B. über ein externes Programm am PC oder direkt über eine WAPVerbindung realisieren. Dies setzt einen laufenden Dienst voraus und braucht eine meist
kostenpflichtigen Verbindung.
Alternative Abfahrzeiten und Routen
Bei Online-Auskünften ist es möglich, sich mehrere Verbindungen zu leicht voneinander abweichenden Zeitpunkten anzeigen zu lassen. Bei entsprechender Ausführungsgeschwindigkeit
der Routensuche wäre eine solche Option denkbar.
7.2. Persönliches Fazit
38
Filter
Bei Übersichtsbetrachtung der Karten werden zum Beispiel die POIs so nahe bei einander
dargestellt, dass jede Übersichtlichkeit und damit auch Information verlorengeht. Deshalb
ist eine intelligente Darstellung oder eine Filteroption durch den Benutzer notwendig.
7.2
Persönliches Fazit
Ich habe dieses Thema für meine Studienarbeit vorgeschlagen und ausgewählt, da ich persönliches Interesse am Thema Busfahren“ habe.
”
Ein weiterer Ansporn für mich war, die Programmierung von mobilen Geräten näher kennenzulernen.
Die Arbeit hat viel Kreativität und selbstständiges Arbeiten erfordert.
Viele Ziele wurden erreicht und das Resultat kann sich meiner Meinung nach durchaus sehen
lassen.
Ich würde mich freuen, wenn das Ergebnis zum praktischen Einsatz kommt.
7.3
Anhang
Zu dieser Studienarbeit gehört ein Datenträger mit dem Quellcode und der Schnittstellendokumentation der Arbeit.
Literatur
[Can07] J2ME Java Doc API
Version: Juli 2007
http://java.sun.com/javame/reference/apis/jsr037/javax/microedition/lcdui/Canvas.html
[CP06]
C.S.R. Prabhu, Prathap A. R.: Bluetooth Technology and Its Applications with
JAVA and J2ME. Prentice-Hall of India Pvt.Ltd, 2006. – ISBN 8120324439
[DB07]
Internetseite der Deutschen Bahn AG
Version: Juli 2007
http://www.db.de/site/bahn/de/start.html
[Ecl07a] Eclipse - an open development platform
Version: Juli 2007
http://www.eclipse.org/
[Ecl07b] EclipseME
Version: Juli 2007
http://eclipseme.org/
[GMa07] Google Maps
Version: Juli 2007
http://maps.google.de/maps
[Gra07]
Wikipedia Graph
Version: Juli 2007
http://de.wikipedia.org/wiki/Graph (Graphentheorie)
[JSR07] Java Bluetooth API Online
Version: Juli 2007
http://jcp.org/aboutJava/communityprocess/mrel/jsr082/index.html
Literatur
40
[K7507] Sony Ericsson Entwickler Seite
Version: Juli 2007
http://developer.sonyericsson.com/site/global/products/phonegallery/k750/p k750.jsp
[K8007] Sony Ericsson Entwickler Seite
Version: Juli 2007
http://developer.sonyericsson.com/site/global/products/phonegallery/k800/p k800.jsp
[Kow07] Weiter Informationen Zum Thema GPS und Navigations
Version: Juli 2007
http://www.kowoma.de/gps/
[Lev66]
Levenshtein, V.I.: Binary codes capable of correcting deletions,insertions, and
reversals. Soviet Physics Doklady, 1966. – ISBN 0
[MID07] Wikipedia Mobile Information Device Profile
Version: Juli 2007
http://de.wikipedia.org/wiki/MIDP#Low-Level-API
[Sch06]
Schmatz, Klaus-Dieter: Java Micro Edition. Entwicklung mobiler Anwendungen
mit CLDC und MIDP. Dpunkt Verlag, 2006. – ISBN 3898644189
[Sun07]
Sun Developer Network
Version: Juli 2007
http://java.sun.com/products/sjwtoolkit/download-2 5 1.html
[THC01] Thomas H. Cormen, Ronald L. R. Charles E. Leiserson L. Charles E. Leiserson:
Introduction to Algorithms. B&T, 2001. – ISBN 0262531968
[Tom07] Internetseite der TomTom International BV
Version: Juli 2007
http://www.tomtom.com/products/
[VBB07] Verkehrsverbund Berlin-Brandenburg
Version: Juli 2007
http://www.vbb-fahrinfo.de/hafas/help.exe/dn?tpl=vbb software
[VGN07] Internetseite des Verkesverbund Großraum Nürnberg
Version: Juli 2007
http://www.vgn.de/komfortauskunft/
Literatur
41
[VRS07] Internetseite des Verkehrsverbund Rhein-Sieg
Version: Juli 2007
http://www.vrsinfo.de/1 2.php
[Zit07]
Sony Ericsson Developer World Zitat1
Version: Juli 2007
http://developer.sonyericsson.com/entry.jspa?externalID=380&categoryID=9

Not set pdfsubject - AG Digital Humanities

Transcrição

Documentos relacionados

Kunena - AntonForster.com

GoToDevice Remote Control mit G/On

Stadt Erlangen

Kundenberater (m/w) Vermögensberatung – Private Banking und

Anfahrtsbeschreibung LGL-Standort Erlangen

Anfahrtsbeschreibung zur WTS Erlangen

Spiegel und Bildentstehung - qoqi.physik.uni

20 Jahre Ronald McDonald Haus Erlangen

Fluval Edge I – Das Nano Lifestyle Aquarium der

Vorgehensweise bei einer Nutzwertanalyse (Quelle: Burghardt