Geographische Kommunikationsmechanismen auf Basis von feingranularen räumlichen Umgebungsmodellen

Abstract

Die immer weiter zunehmende Verbreitung von leistungsfähigen mobilen Kommunikationstechnologien und Positionierungssystemen ermöglicht die Realisierung neuartiger geographischer Kommunikationsmechanismen (kurz Geocast). Mit Hilfe von Geocast können Nachrichten an alle Endgeräte in einem bestimmten geographischen Zielgebiet gesendet werden, d.h. die Gruppe der Empfänger wird durch ihren geographischen Aufenthaltsort definiert. Die Anwendungen von Geocast sind vielfältig. So können mit Hilfe von Geocast zum Beispiel Stauinformationen gezielt an alle Fahrzeuge auf einem bestimmten Straßenabschnitt verteilt werden, Touristen können über Sehenswürdigkeiten in ihrer Umgebung informiert werden, oder es können Warnmeldungen oder ortsbezogene Werbeinformationen in bestimmten räumlichen Gebieten verteilt werden.

Im Mittelpunkt dieser Arbeit stehen Geocast-Verfahren, welche die feingranulare ortsbezogene Verteilung von Nachrichten erlauben. Die Hauptbeiträge dieser Arbeit sind zum einen ein feingranulares Lokationsmodell und Adressierungskonzept für Geocast, welche sowohl die Bestimmung und Adressierung von Lokationen durch geometrische Figuren als auch durch symbolische Bezeichner wie Raum- oder Stockwerksnummern ermöglichen. Die Hauptaufgaben des Modells sind neben der Definition der Zielgebiete von Nachrichten und der Empfängerpositionen der Vergleich von Zielgebieten und Empfängerpositionen zur Definition der Empfängermenge. Zum anderen werden skalierbare Geocast-Protokolle für die effiziente Verteilung von Nachrichten vorgeschlagen, welche die notwendige Skalierbarkeit sowohl für die Unterstützung einer großen Anzahl an Lokationen als auch großer Empfängermengen aufweisen.

Das vorgeschlagene Lokationsmodell verwendet ein hybrides Modellierungskonzept, das es ermöglicht, Lokationen sowohl mit symbolischen Bezeichnern als auch geometrischen Beschreibungen zu versehen. Geometrien können dabei sowohl durch zweidimensionale als 2,5-dimensional Figuren modelliert werden. Der symbolisch Teil des Modells basiert auf einer Hierarchie von Lokationen entsprechend der räumlichen Inklusionsbeziehung. Zusätzlich werden strukturelle Regeln für den Aufbau der symbolische Hierarchie eingeführt, die schließlich zu einem verbandsbasierten Modell führen, das im Gegensatz zu einfachen hierarchischen Modellen auch die Möglichkeit zur Definition überlappender Lokationen bietet. Ferner wird die Integration lokaler Lokationsmodelle unterstützt, welche gleichzeitig zur Definition mobiler Zielgebiete, z.B. eines bestimmten Wagens eines Zuges, verwendet werden. Durch die Unterstützung sowohl geometrischer als auch symbolischer Beschreibungen sind spezielle Konzepte zum Vergleich von Zielgebieten und Empfängerpositionen erforderlich. Das vorgeschlagene Modell ordnet hierzu symbolischen Lokationen geometrische Ausdehnungen zu, wobei auch die Approximierung symbolischer Lokationen durch unscharfe Lokationsangaben unterstützt wird.

Der zweite Teil dieser Arbeit widmet sich Ansätzen zur Vermittlung symbolisch adressierter Geocast-Nachrichten. Hier betrachtet die Arbeit zwei grundsätzliche Ansätze: Einen verzeichnisbasierten Ansatz und die Vermittlung von Nachrichten in einem der Internet-Infrastruktur überlagerten Overlay-Netz.

Der verzeichnisbasierte Ansatz bildet zunächst die symbolische Geocast-Adresse auf eine Menge von IP-Adressen ab, welche in einem zweiten Schritt für die Vermittlung genutzt werden. Im zweiten Schritt können die Nachrichten sowohl per IP-Unicast als auch IP-Multicast zugestellt werden. Insbesondere bei größeren Empfängergruppen bietet sich IP-Multicast für die effiziente Vermittlung an. Allerdings stellt Geocast aufgrund der großen Anzahl an notwendigen Multicast-Gruppen für ein feingranulares globales Lokationsmodell entsprechende Anforderungen an die verwendeten Multicast-Protokolle. Es wird daher die Verwendung von explizitem Multicast (Xcast) vorgeschlagen, das sich insbesondere für eine große Anzahl von Gruppen kleiner bis mittlerer Größe eignet.

Die vorgeschlagenen Geocast-Overlay-Netze bestehen aus einer Menge von Geocast-Routern, welche symbolische Adressen interpretieren und daraus die nächsten Router auf dem Weg ins Zielgebiet bestimmen können. Die Grundidee ist dabei die Abbildung des hierarchischen symbolischen Lokationsmodells auf eine entsprechende hierarchische Overlay-Netzstruktur. Entsprechend der vorgeschlagenen Lokationsmodelle wurde ein baumförmiges und eine verbandsbasiertes Geocast-Overlay-Netz entworfen, einschließlich der notwendigen Mechanismen zur Verwaltung (Hinzufügen/Entfernen von Geocast-Routern, Behandlung von Router-Fehlern) der Netze. Als Optimierung der grundsätzlich hierarchischen Netzstrukturen wurden verschiedene Strategien zur Ergänzung der hierarchischen Netze durch zusätzliche Direktverbindungen entworfen.

In der Evaluierung wurde die Effizienz der vorgeschlagenen Ansätze z.B. hinsichtlich der erzielten Nachrichtenpfadlänge nachgewiesen.

The proliferation of powerful mobile communication technologies as well as positioning technologies allows for the implementation of geographic communication mechanisms (geocast). Geocast allows for sending location-based information to all devices in a given geographic target area. This geographic communication paradigm has various application areas. In particular, it is well-suited for applications where polling location-based information would be inefficient. For instance, services for distributing warning messages in endangered areas or for sending location-based advertisements to devices close to a shop could be realized easily based on geocast. Moreover, geocast could also be used to realize a location-based instant messaging service, or to send traffic information to on-board car navigation systems, etc. In general, geocast could be a building block of a middleware or platform for location-based services.

The basic goal of this dissertation are concepts for the fine-grained and efficient geographic communication based on suitable geocast protocols. This overall goal can be further refined into two sub-goals, whose solutions are the main contributions of this work: (1) A fine-grained addressing concept and location model for geocast. (2) Scalable geocast routing protocols.

First, a fine-grained addressing concept and a suitable location model are designed to specify target locations and the locations of recipients, and to determine whether a recipient is located within the target area. In general, locations can be modelled in two ways. On the one hand, geometric models use geometric figures like points or polygons to define locations. These models are highly flexible since any area can be defined. However, they tend to lead to complex models if a fine-grained model is required or if three-dimenational coordinates are required, for instance indoors. On the other hand, symbolic models use symbolic identifiers like room or floor numbers to identify locations. These models are very intuitive to use since they are based on locations, addresses, and geographic relations of the physical world that we use everyday. However, they are not as flexible as geometric models since they are limited to a set of pre-defined locations.

Both types of addresses are relevant for geocast. Indoors, in particular symbolic locations like floors and rooms are often more intuitive to use than geometric addresses. Moreover, many positioning systems that are used especially indoors like RFID-based systems and bluetooth or infrared beacons are based on symbolic outputs. These outputs can be mapped easily to symbolic locations. Outdoors, geometric addressing is benefical, for instance, to address parts of a larger place. Moreover, geometric positioning systems like GPS are prevalent outdoors. Therefore, a hybrid location model is proposed in this dissertation combining symbolic and geometric information and the advantages of both basic types of models. Basically, this model consists of a hierarchical tree-based or lattice-based symbolic location model, where locations are associated with geometric coordinates. Besides stationary target areas like a building or room, this model also allows for the addressing of mobile target areas like a specific coach of a train. Since positioning systems typically output uncertain position information rather than perfectly precise positions, we will show how to consider these uncertainties using probabilistic models for comparing user positions and target areas.

Second, scalable geocast routing protocols are proposed in this dissertation. Since geocast routing protocols for geometric addressing are already well-covered by related work, this dissertation is focussed on geocast routing protocols for symbolically addressed messages. Two basic classes of approaches are considered: a directory based approach and symbolic routing in a dedicated geocast overlay network.

The directory-based approach uses a two-step process. It first determines the network addresses of all recipients in the target area. Then it forwards the message to this group using unicast or multicast protocols. For the latter, the untilization of an explicit multicast protocol (Xcast) is proposed in this dissertation to cope with the possibly large number of groups.

For forwarding symbolically addressed messages in an overlay network, special overlay network structures together with the mechanisms to maintain these structures and suitable routing algorithms are proposed. In particular, a tree-based overlay network and a lattice-based overlay network are proposed, depending on the underlying tree- or lattice-based location models that are proposed in the first part of this dissertation.