Inhaltsverzeichnis

1  Einleitung  1

2  Autonavigation  3

2.1  Grundlagen  4

2.2  Ortungs- und Navigationssysteme  5

2.2.1  Global Positioning System (GPS)  6

2.2.2  Differential Global Positioning System (DGPS)  8

2.2.3  Global Navigation Satellite System (GLONASS)  9

2.2.4  Galileo  9

2.2.5  Beidou Navigation System  11

2.3  Digitale Straßenkarte  11

2.3.1  Rolle und Anforderungen  11

2.3.2  Datenbeschaffung und Aktualisierung  12

2.3.3  Datenspeicherung im GDF-Format  16

3  Algorithmen der Routenplanung  25

3.1  Graphentheorie  25

3.2  Problemstellung der Routenplanung  26

3.3  Der Floyd-Warshall-Algorithmus  27

3.4  Der Dijkstra-Algorithmus  28

3.4.1  Beispiel  29

3.4.2  Korrektheit  32

3.4.3  Varianten und ihre Komplexität  33

3.5  Der A -Algorithmus  34

3.6  Der Ford-Bellmann-Algorithmus  36

4  Mobile Kommunikation  37

4.1  Mobile Ad-hoc Netzwerke (MANETs)  37

4.2  Routingprotokolle  40

4.2.1  Destination-Sequenced Distance-Vector Routing (DSDV)  42

4.2.2  Ad-hoc On-Demand Distance-Vector Routing (AODV)  42

4.2.3  Zone Routing Protocol (ZRP)  43

4.3  Technische Realisierung  43

4.3.1  Bluetooth  44

4.3.2  IEEE 802.11 und verwandte Standards  45

4.4  Sicherheit  47

4.4.1  Kommunikationssicherheit  48

4.4.2  Verkehrssicherheit  51

i

Inhaltsverzeichnis

5  Verteilte Wissensbasis  55

5.1  Ortsbezogene Wissensverteilung  55

5.2  Zeitbezogene Wissensverteilung  56

5.3  Testumgebung  56

5.4  Testergebnisse  59

6  Zusammenfassung und Ausblick  65

ii

Abkürzungs- und

Symbolverzeichnis

3M-Netze Mobile Multi-Hop Multimedia Ad-hoc Netzwerke ABS Antiblockiersystem ACC Automatic Cruise Control AI Artificial Intelligence AIS Autobahn Informations-System ANET Ad-hoc Netzwerk AODV Ad-hoc On-Demand Distance-Vector Routing APSP All-Pair Shortest-Path ARA Ant-Colony-Based Routing Algorithm ASR Antischlupfregelung ATKIS Amtlich-Topographisch-Kartographisches Informationssystem BMBF Bundesministerium für Bildung und Forschung BMVBW Bundesministerium für Verkehr, Bau- und Wohnungswesen BRP Bordercast Resolution Protocol C2CC Car to Car Communication CBRP Cluster Based Routing Protocol CSGR Clusterhead Gateway Switch Routing DDR Distributed Dynamic Routing

DEMETER Digital Electronic Mapping of European Territory DGPS Differential Global Positioning System DLR Deutsches Zentrum für Luft- und Raumfahrt e.V. DOD Department of Defence (US-Verteidigungsministerium)

iii

DSDV Destination-Sequenced Distance-Vector Routing DSR Dynamic Source Routing DSRC Dedicated Short Range Communication-Technologie e = [i, j) die gerichtete Kante e vom Knoten i zum Knoten j E(G) Kantenmenge des Graphen G

EDIGéO

EGNOS European Geostationary Navigation Overlay Service EHB Elektro-hydraulische Bremse EMB Elektro-mechanische Bremse ESP Elektronisches Stabilitätsprogramm FSR Fisheye State Routing γ([i, j)) Gewicht (bzw. Länge) der gerichteten Kante [i, j) G(V, E) Graph G mit der Knotenmenge V und Kantenmenge E GEO Geostationary Earth Orbit, Geostationärer Erd-Orbit GIOVE-A Galileo In-Orbit Validation Element GPS Global Positioning System

GLONASS

HRSC-A High Resolution Stereo Camera - Airborne IARP Intrazone Routing Protocol IERP Interzone Routing Protocol INS Inertial Navigation System ITS Intelligent Transportation Systems LADGPS Local Area Differential Global Positioning System LAR Location-Aided Routing MANET Mobiles Ad-hoc Netzwerk Mbps Megabit pro Sekunden MEO Medium altitude Earth Orbit, Bahnen mittlerer Flughöhe

iv

N ⁻ (v) Menge der Vorgängerknoten des Knotens v N ⁺ (v) Menge der Nachfolgerknoten des Knotens v NAVSTAR Navigation System with Timing And Ranging NIAM Nijsen Information Analysis Modell NNSS Navy Navigation Satellite System (TRANSIT) NTF National Transfer Format OLSR Optimized Link State Routing p ij ein Weg (Pfad) vom Knoten i zum Knoten j RDS Radio Data System SIG Bluetooth Special Interest Group SPSP Single-Pair Shortest-Path SSSP Single-Source Shortest-Path TORA Temporally-Ordered Routing Algorithm TPEG Transport Protocol Expert Group UMTS Universal Mobile Telecommunications System V(G) Knotenmenge des Graphen G WADGPS Wide Area Differential Global Positioning System WLAN Wireless Local Area Network WPAN Wireless Personal Area Network WRP Wireless Routing Protocol ZHLS Zone-based Hierarchical Link State Routing ZRP Zone Routing Protocol

v

Abbildungsverzeichnis

2.1 Herleitung der Raumkoordinaten eines Objektes mit Hilfe von vier Satelliten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Weltraumsegment des gps . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Funktionsweise des lokalen dgps . . . . . . . . . . . . . . . . . . . . 8 2.4 Fernerkundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Ebenen (Levels) des gdf-Formats . . . . . . . . . . . . . . . . . . . . 18 2.6 Elemente eines niam-Diagrammes . . . . . . . . . . . . . . . . . . . . 20 2.7 Datenmodell des gdf 4.0-Standards . . . . . . . . . . . . . . . . . . . 21 2.8 Struktur und Relationen ausgewählter Records-Typen einer gdf 3.0-Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.9 Beispiel eines Volume Header Records in einer gdf-Datei . . . . . . . 23 2.10 Beispiel für Definition eigener Elemente in einer gdf-Datei . . . . . . 23 2.11 Ausschnitt aus dem Rumpf einer gdf-Datei . . . . . . . . . . . . . . 23 3.1 Graph G mit Entfernungen als Kantengewichte . . . . . . . . . . . . 29 3.2 Dijkstra Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1 Arten der Klassifikation von Ad-hoc Netzwerken . . . . . . . . . . . . 39 4.2 Klassifikation von Routingalgorithmen . . . . . . . . . . . . . . . . . 41 4.3 Fahrerfehlverhalten bei Unfällen mit Personenschäden 2004 . . . . . . 52 5.1 Übersicht der Simulationsumgebung . . . . . . . . . . . . . . . . . . . 57 5.2 Aktive Fahrzeuge und deren Zielparkplatz . . . . . . . . . . . . . . . 57 5.3 Gesamtergebnisse bei Sperrung der Ampel A1 . . . . . . . . . . . . . 60 5.4 Gesamtergebnisse bei Sperrung der Ampel A2 . . . . . . . . . . . . . 61 5.5 Unfallähnliche Situation . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.6 Nicht angekommene Fahrzeuge bei Sperrung der Ampel A2 und ihre Ursachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

vii

1 Einleitung

Der Begriff Telematik entstand Anfang der 80er Jahre als Verknüpfung von Telekommunikation und Informatik. Ursprünglich lag sein Anwendungsschwerpunkt bei der Integration von Telefonsystemen mit pc-Funktionalitäten und anderen Büroanwendungen. Diese Bedeutung des Begriffes konnte sich im Zuge der Digitalisierung der Telefonnetze nicht durchsetzen. Seit Anfang der 90er Jahre wird der Ausdruck in Europa ausschließlich für das Anwendungsfeld Verkehrstelematik eingesetzt, welches im englischsprachigen Raum als Intelligent Transportation Systems (its) bekannt ist.

Die Verkehrstelematik umfasst alle Informations- und Kommunikationssysteme, welche dynamische Daten aus Verkehrsmitteln und Verkehrssystemen sammeln, bearbeiten und öffentlichen Institutionen sowie privaten Nutzern und Unternehmen bereitstellen. Sie zielt auf die Optimierung der Fahrzeugbewegungen, der Verkehrsströme, sowie auf die Erhöhung der Sicherheit ab (vgl. [Klaus 2004]). Die Verkehrstelematik kann sowohl die Verkehrsentstehung als auch den Verkehrsablauf beeinflussen. Die Entstehung des Verkehrs wird beeinflusst, wenn z.B. durch aktuelle Informationen über Staus, Unfälle oder Straßenzustände der Reiseantritt verschoben oder ein anderes Verkehrsmittel gewählt wird. Beispiel für ein derartiges System ist das seit 1998 in Deutschland flächendeckend verfügbare Radio Data System (rds). Das System informiert u.a. über Staus und warnt vor Gefahren. Der Verkehrsfluss wird auch durch den Einsatz von Ortungs- und Navigationssystemen beeinflusst. Sie ermitteln für den Fahrer die günstigste Route und führen ihn dementsprechend zum Ziel. Dabei kann ‘günstig’ viele Interpretationen haben: Vielleicht ist der kürzeste oder der schnellste Weg gesucht, vielleicht der billigste, vielleicht aber auch einer, auf dem man möglichst selten eine Radarstreife der Polizei antrifft (vgl. [Jungnickel 1994, S. 89]).

Intelligente Navigationssysteme gehen einen entscheidenden Schritt weiter und beziehen Informationen über die aktuelle Verkehrssituation in ihre Berechnungen mit ein. Die Gewinnung von Informationen über die Verkehrssituation erfolgt zentral durch Systeme wie das rds oder durch die dezentrale Kommunikation mit anderen Verkehrsteilnehmern. Zusätzlich ermöglicht die Fahrzeug-zu-Fahrzeug-Kommunikation die Unterstützung weiterer Fahrerassistenzsysteme. Ein Beispiel für den Austausch aktueller und unter Umständen lebenswichtiger Informationen ist die Benachrichtigung nachkommender Fahrzeuge über die eigenen Bremsvorgänge. Nachkommende Fahrzeuge können im Ernstfall automatisch in ihr Fahrwerk eingreifen und die Geschwindigkeit regulieren. Das Cooperative Adaptive Cruise Control (cacc) realisiert ein solches System.

1

Diese Diplomarbeit beschäftigt sich mit der Untersuchung der Fragestellung, inwiefern intelligente Navigationssysteme mittels Kommunikation im städtischen Bereich den Gesamtverkehr beeinflussen. Dazu wird zunächst die Funktionsweise der Ortungs- und Autonavigationssysteme beschrieben. Kapitel 3 behandelt die für die Navigation bedeutendsten Algorithmen. Kapitel 4 beschreibt Kommunikation in mobilen Netzwerken. In Kapitel 5 werden Überlegungen zur Verteilung der für die Kommunikation von einzelnen Fahrzeugen gespeicherten verkehrsrelevanten Informationenen angestellt. Einige dieser Überlegungen werden anhand einer agentenbasierten Verkehrssimulation umgesetzt und bewertet.

2

2 Autonavigation

Navigation umfasst alle Rechenvorgänge, um in einem geographischen Raum ein Objekt entlang des optimalen Weges zum Ziel zu führen. Der Begriff Autonavigation beschreibt die Navigation von Fahrzeugen im Straßenverkehr. Dazu gehören die Ortung, die Berechnung des optimalen Weges und die entsprechende Führung des Fahrzeuges zum Ziel. Fälschlicherweise wird unter Navigation häufig alleine die Zielführung verstanden. Obwohl sie unentbehrliche Bestandteile der Autonavigation darstellen, werden Ortung und digitale Straßenkarte selten thematisiert. Ortung ist die Ermittlung der Raumkoordinaten eines Objektes. Man unterscheidet zwischen Eigen- und Fremdortung. Während die Eigenortung von dem Objekt selbst durchgeführt wird, erfolgt die Fremdortung durch externe Systeme. Fremdortung kann durch Bodenortungs- oder durch Satellitenortungssysteme durchgeführt werden (vgl. [Mansfeld 1998, S. 1]).

Die ersten Satellitensysteme entstanden Ende der 50-er Jahre. Zu ihnen zählen das sowjetische cikada und das us-amerikanische Navy Navigation Satellite System (nnss). Diese Systeme wurden zu Global Navigation Satellite System (glonass) und Global Positioning System (gps) weiterentwickelt.

Die dreidimensionale Ortung erfordert mindestens vier Satelliten. Sollen die Signale des Satellitensystems auf der ganzen Erdoberfläche verfügbar sein, müssen deutlich mehr Satelliten zum Einsatz kommen. Aus diesem Grund besteht beispielsweise die gps-Konstellation aus mindestens 24 Satelliten. Es gibt jedoch Systeme, welche die Ortung mit weniger Satelliten realisieren wollen. Dazu gehört z.B. das chinesische Beidou-System. Seine Konstellation umfasst derzeit zwei Satelliten. Nach der Ermittlung des Standortes wird ein Fahrzeug entlang der optimalen Route zum Ziel geführt. Die Berechnung der optimalen Route erfordert das Vorliegen der relevanten Daten in Form einer digitalen Straßenkarte. Nach einer Beschreibung der Grundlagen werden in diesem Kapitel die Ortungspeziell gps, glonas, Beidou und das zukünftige europäische Navigationssystem Galileo - und digitale Straßenkarte behandelt.

3

2.1 Grundlagen

Immer mehr Menschen nutzen existierende Möglichkeiten, um ihr Ziel bequem und effizient erreichen zu können. Unter Navigation (im Straßenverkehr) versteht man im weiteren Sinne das Führen eines Fahrzeuges von einem Ausgangsort (ermittelt durch Ortung) auf bestimmten Wegen (gespeichert in einer digitalen Straßenkarte) zu einem Zielort einschließlich der erforderlichen Mess- und Rechenvorgänge (Routenplanung und -berechnung). Im engeren Sinne ist Navigation die Planung und Überwachung der Fahrzeugbewegung in möglichst optimaler Weise (vgl. [Bachmann 1993, S. 20]).

Man unterscheidet für die Autonavigationssysteme zwischen zwei Gruppen von Navigationsverfahren:

1. bordautonome Verfahren, welche vollständig auf eine Unterstützung von außen verzichten können und

2. satellitenbezogene Verfahren.

Die zur ersten Klasse gehörenden Autonavigationssysteme benötigen keine Informationen von außen und arbeiten mit Hilfe des so genannten Dead-Reckoning. Dieses Verfahren basiert auf einer ständigen Berechnung der aktuellen Position. Die Positionsberechnung erfolgt durch Abgleich der zurückgelegten Strecke mit den bekannten Distanzen der digitalen Kartengrundlage unter Betrachtung der Fahrtrichtung und Geschwindigkeit. Die zurückgelegte Strecke wird mit Hilfe von Radsensoren ermittelt. Die Richtung wird durch einen Kreiselkompass bestimmt. Ein Nachteil bordautonomer Verfahren liegt darin, dass die Genauigkeit der Positionsermittlung immer geringer wird, je größer die gefahrene Strecke ist (vgl. [May 2002, S. 21]). Im Gegensatz zu bordautonomen Verfahren lässt sich bei satellitenbasierten Verfahren die Position durchgehend mit einer großen Genauigkeit ermitteln. Die Messung der Koordinaten des navigierenden Objektes erfolgt hierbei durch Signale, welche vom Satellit erzeugt und vom Objekt empfangen werden. Aus der Geschwindigkeit und Laufzeit dieser Signale lässt sich die Entfernung vom Satellit ermitteln. Um die drei Raumkoordinaten des Objektes ermitteln zu können, muss das Objekt Signale von mindestens vier Satelliten empfangen (siehe Abb. 2.1). Die Genauigkeit der ermittelten Position hängt von der Genauigkeit der Laufzeitmessung ab (vgl. [Mansfeld 1998, S. 114ff]). Aus diesem Grund sind die Navigationssatelliten mit mindestens drei Atomuhren ausgestattet, deren Genauigkeit bei 10 ⁻¹³ Sekunden liegt. Störungen der Signale (z.B. in Städten durch Signalschatten) führen dennoch zu erheblichen, nicht tolerierbaren Ungenauigkeiten. Als Gegenmaßnahme werden korrigierende Verfahren (wie z.B. das dgps, siehe Abschnitt 2.2.2) angewendet.

4

2.2 Ortungs- und Navigationssysteme

Ortung ist ein Begriff für die Gesamtheit der Mess- und Rechenvorgänge zur Ermittlung des Standortes eines Objektes. Nach [Bachmann 1993, S. 20] versteht man unter Ortung im weiteren Sinne:

• Ermittlung der Lage (Position) von Objekten durch Angabe ihrer Koordinaten und

• Ermittlung der Bewegungsrichtung der Objekte, sowie ihrer Geschwindigkeit und Beschleunigung.

Die Ortung kann durch verschiedene Methoden erfolgen. Außer dem bereits erwähnten Dead-Reckoning kann sie unter anderem durch Funknavigation bzw. Satellitennavigation erfolgen. Bei der satellitengestützten Ortung wird die Position der Objekte, deren Koordinaten ermittelt werden sollen, mit Hilfe der Entfernung zwischen dem Objekt und den von ihm aus sichtbaren Satelliten ermittelt. Ein Objekt ist in Sichtweite eines Satelliten, wenn es Signale vom ihm empfangen kann. Mit Hilfe der empfangenen Signale wird die Entfernung d ^s 1 zwischen dem Satelliten s 1 , dessen Raumkoordinaten bekannt sind, und dem Objekt berechnet. Die Menge der Punkte mit dem Abstand d ^s 1 vom Satelliten s 1 bildet die Oberfläche einer Kugel mit dem Radius d ^s 1 und dem Mittelpunkt s 1 . Um die 3D-Koordinaten ermitteln zu können, muss das Objekt Signale von mindestens vier Satelliten empfangen. Durch den Abstand von einem Satelliten s 1 und die Koordinaten (x 1 , y 1 , z 1 ) desselben Satelliten lässt sich die Menge der möglichen Positionen p(x, y, z) durch folgende Gleichung darstellen: (x 1 − x) ² + (y 1 − y) ² + (z 1 − z) ² d(s 1 , p) = d ^s 1 ⇐⇒ d ^s 1 =

Das Empfangen der Signale von mehreren Satelliten führt zum Vorhandensein mehrerer quadratischen Gleichungen mit den selben Unbekannten x, y und z. Die Koordinaten lassen sich durch die Lösung des Gleichungssystems ermitteln, welches aus den jeweils durch die empfangenen Satellitensignale gewonnen Gleichungen entsteht:

Dabei sind d 1 , · · · , d 4 , x 1 , · · · , x 4 , y 1 , · · · , y 4 und z 1 , · · · , z 4 bekannt. Außerdem sind die Mittelpunkte aller Kugeln (die Satelliten) paarweise unterschiedlich, und damit auch die Kugeln selbst. In Abb. 2.1 ist dieser mathematische Sachverhalt graphisch dargestellt.

5

Abb. 2.1: Herleitung der Raumkoordinaten eines Objektes mit Hilfe von vier Satelliten

Aus der Geometrie ist bekannt, dass die Schnittpunktmenge der Oberflächen zweier unterschiedlicher Kugeln einen Kreis bildet. Ein Kreis schneidet die Oberfläche einer Kugel, in der er selbst nicht liegt, in höchstens zwei Punkten. Um aber den Punkt eindeutig zu bestimmen, wird ein vierter Satellit benötigt. Man könnte an dieser Stelle überlegen, ob ebenfalls die approximierte Kugelförmigkeit der Erde nicht genutzt werden kann? In dem Fall würden nur drei Satelliten benötigt, um die Position eines Objektes (den Schnittpunkt der vier Kugeln) zu bestimmen. Diese Überlegung ist zwar interessant, würde jedoch wegen der Geometrie der Erde sowie wegen der Unregelmäßigkeit der Erdoberfläche zu großer Ungenauigkeit führen. Aus diesem Grund erfolgt bei den Satellitensystemen gps, glonass und Galileo die Ortung mit Hilfe von vier Satelliten. Bei dem chinesischen Satellitensystem Beidou werden dagegen durch bestimmte Techniken nur zwei Satelliten eingesetzt. In den folgenden Abschnitten werden die Navigationssysteme gps, dgps, glonass, Beidou und Galileo behandelt.

2.2.1 Global Positioning System (GPS)

gps (navstar Global Positioning System) wurde 1978 vom US-Verteidigungsministerium (Department of Defence, kurz dod) als Nachfolger des ersten US-Satellitennavigationssystems nnss (transit) gestartet.

Explorer 1, der erste transit-Satellit wurde am 31.01.1958 ins All geschickt (vgl. [Kumar u. Moore 2002, S. 60]). transit bediente sich nur eines Satelliten. Dies hat

6

zur Folge, dass die Positionsermittlung 35 bis 45 Minuten dauerte. Die Positionsbestimmung für sich bewegende Objekte war nicht möglich. Durch den Einsatz des mit einer atomaren Uhr ausgestatteten Satelliten timation i konnte das transit- Systemab 1967 auch die Position beweglicher Objekte bestimmen. Danach folgten zahlreiche Verbesserungen, die immer mehr Genauigkeit und Verfügbarkeit garantieren konnten. Bereits im Jahr 2003 bestand die gps-Konstellation aus 24 Satelliten und ist mit einer hohen Ortungsgenauigkeit weltweit verfügbar.

Das gps-System setzt sich aus drei Segmenten zusammen: Weltraum-, Kontroll-und Benutzersegment. Das Weltraumsegment besteht aus mindestens 24 Satelliten mit einer Lebensdauer von zehn bis 15 Jahren. Diese schweben, wie in Abb. 2.2 modellhaft dargestellt, in insgesamt sechs gleichmäßig verteilten Bahnen in einer Höhe von ca. 20.200 km über der Erde und umkreisen diese zweimal täglich. Die Ausrichtung der Satelliten ermöglicht es, dass jedes Fahrzeug oder Objekt auf der Erde jederzeit von mindestens vier Satelliten erfasst wird. gps wurde ursprünglich für militärische Zwecke entwickelt. Seine vollständige Funktionsfähigkeit erreichte das System 1995. Seit 1990 wurde gps für zivile Nutzung eingeschränkt freigegeben. Die Einschränkungen der zivilen Nutzung werden mit dem Begriff Selective Availability (sa) umschrieben. Damit ist gemeint, dass für zivile Nutzer aus Sicherheitsgründen Verfälschungen der ermittelten Position vorgenommen wurden. Per Zufallsgenerator wurden Verzögerungen der Signallaufzeit verursacht. Dadurch verringerte sich die Ortungsgenauigkeit auf ca. 100 m. Zur Erreichung einer größeren Genauigkeit wurden Systeme, wie das im nächsten Abschnitt beschriebene dgps, eingesetzt. dgps ist eine Erweiterung des gps. Nach der Einstellung der sa am 1. Mai 2000 erreichte gps eine Genauigkeit von ca. 7 bis 20 m (vgl. [May 2002, S. 18]).

7