Präsenzerkennung in mobilen Ad-Hoc-Netzwerken
Final Report Abstract
Mobile Ad-Hoc Netzwerke bestehen aus portablen Endystemen, die ohne zusätzliche Infrastruktur miteinander kommunizieren können. Die zentrale Idee mobiler Ad-Hoc-Netzwerke ist, dass die Endsysteme selbst für andere Endysteme Daten weiterleiten und somit eine Kommunikation zwischen Teilnehmern ermöglichen, die sich nicht in direkter Funkreichweite zueinander befinden. Beispiele für den Einsatz dieser Netzwerke sind die Kommunikation zwischen Fahrzeugen und der Datenaustausch in Katastrophenfällen. Bisher wurde in diesem Forschungsgebiet angenommen, dass vorab bekannt ist, welche Geräte an einem solchen Netzwerk beteiligt sind. Aufgrund der Portabilität der Endysysteme und der Möglichkeit, diese zu jedem beliebigen Zeitpunkt ein- oder auszuschalten, ist diese Annahme jedoch realitätsfern. Im Projekt „Präsenzerkennung in Mobilen Ad-Hoc- Netzwerken“ wurde daher untersucht, wie die Anwesenheit von Geräten in einem mobilen Ad-Hoc-Netzwerk in ressourcenschonender Weise überprüft werden kann. Ausgangspunkt unserer Arbeit war die Idee, Präsenzinformationen verlustbehaftet zu komprimieren, um den Ressourcenaufwand für die Präsenzerkennung stark zu reduzieren. Eine solche verlustbehaftete Kompression ist für den betrachteten Anwendungsfall legitim, wenn sie lediglich sogenannte „False Positives“ erzeugt, also Knoten als anwesend betrachtet, die in Wirklichkeit nicht im Netzwerk vorhanden sind: Der Irrtum wird spätestens bei einer fehlschlagenden Kontaktaufnahme bemerkt, der zu erwartende Aufwand für diesen Kontaktversuch ist in den (seltenen) Fällen, in denen er auftritt, nicht höher als er ohne Präsenzerkennungsmechanismen wäre. „False Negatives“ – das Nichterkennen der Anwesenheit eines präsenten Knotens – sind hingegen nicht akzeptabel, da dies den Versuch einer Kontaktaufnahme von vorneherein ausschließt. Im Rahmen des Projektes haben wir ein solches Verfahren entwickelt, über mehrer Schritte hinweg verbessert, analytisch und simulativ untersucht und schließlich auf realen Geräten implementiert und evaluiert. Wir konnten zeigen, dass unser Algorithmus zur Präsenzerkennung leichtgewichtig und für verschiedene Einsatzszenarien geeignet ist. Insbesondere wurden das Zusammenspiel mit Routingprotokollen für mobile Ad-Hoc-Netzwerke und der Einsatz als Teil eines infrastrukturlosen Instant-Messaging Systems untersucht. Neben den Kernbeiträgen des Projektes sind zwei zu Projektbeginn nicht geplante Beiträge entstanden. Zum einen konnte gezeigt werden, dass sich die Verfahren zur effizienten Verbreitung von Anwesenheitsinformationen verallgemeinern lassen und vor allem im Bereich der Fahrzeug-zu-Fahrzeug Kommunikation für den Austausch von Verkehrs- und Parkrauminformationen nutzbar sind. Zum anderen wurde für die Auswertung von Experimenten ein Verfahren entwickelt, mit dem sich die Zeitstempel in den Logdateien des Experiments synchronisieren lassen. Dies ist von grundsätzlicher Bedeutung für Experimente in Computernetzwerken, da im Allgemeinen alle beteiligten Systeme ihre Logdateien mit unsynchronisierten Uhren aufzeichnen. Durch die Ergebnisse dieses Projektes werden eine Reihe neuer Anwendungen ermöglicht und existierende Anwendungen in ihrer Effizienz verbessert. Viele Bestandteile mobiler Ad-Hoc-Netzwerke profitieren unmittelbar von dem hier entwickelten Dienst zur Präsenzerkennung. Hierzu gehören beispielsweise reaktive Routingprotokolle genauso wie die Dienstsuche in mobilen Ad-Hoc-Netzwerken. Zudem werden neue Anwendungen ermöglicht. So ist es nun sehr einfach, eine Anwendung zu entwickeln, die überprüft, ob sich ein Bekannter in einer vorgegebenen Reichweite aufhält oder nicht. Auch die Auswirkungen auf die Fahrzeug-zu-Fahrzeug Kommunikation sind bemerkenswert: Erstmalig können Daten wie etwa Informationen zu Parkplätzen oder zur Verkehrslage hierarchisch in effizienter Weise aggregiert werden. Dies kann zu einer Vielzahl interessanter Anwendungen beitragen, von neuartigen Navigationssystemen bis hin zu infrastrukturlosen Parkleitsystemen. Schließlich hat die nachträgliche Zeitsynchronisation von Logdaten ein sehr breites Anwendungsspektrum. Wenn ein Broadcast-Medium verwendet wird, können Netzwerkexperimente in Zukunft dieses Verfahren verwenden, um ohne Störungen während des Experimentes nachträglich die Logdaten auf eine gemeinsame Zeitbasis zu synchronisieren.
Publications
- Detecting the Presence of Nodes in MANETs. In: CHANTS ’07: Proceedings of the 3rd ACM MobiCom Workshop on Challenged Networks, 2007, S. 43–50
Tran, Thi Minh C. ; Scheuermann, Björn ; Mauve, Martin
- Near-Optimal Compression of Probabilistic Counting Sketches for Networking Applications. In: Dial M-POMC ’07: Proceedings of the 4th ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing, 2007
Scheuermann, Björn ; Mauve, Martin
- Probabilistic Aggregation for Data Dissemination in VANETs. In: VANET ’07: Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks, 2007, S. 1–8
Lochert, Christian ; Scheuermann, Björn ; Mauve, Martin
- Error Bounds and Consistency in Maximum Likelihood Time Synchronization / Department of Computer Science, Heinrich Heine University Düsseldorf, Germany. 2008 (TR-2008-001) Forschungsbericht
Scheuermann, Björn ; Kiess, Wolfgang ; Roos, Magnus ; Jarre, Florian ; Mauve, Martin
- Of?ine Time Synchronization for libpcap logs. In: WMAN-FG ’08: 1. GI/ITG KuVs Fachgespräch WMAN (Wireless Mobile Ad-Hoc Networks), 2008
Marks, Daniel ; Kiess, Wolfgang ; Scheuermann, Björn ; Roos, Magnus ; Mauve, Martin ; Jarre, Florian
- Node Presence Detection with Reduced Overhead. In: WONS ’09: Proceedings of the 6th Annual Conference on Wireless On-demand Network Systems and Services, 2009
Tran, Thi Minh C. ; Scheuermann, Björn ; Mauve, Martin
- On the Time Synchronization of Distributed Logfiles in Networks with Local Broadcast Media. In: IEEE/ACM Transactions on Networking 17 (2009), April, Nr. 2, S. 431–444
Scheuermann, Björn ; Kiess, Wolfgang ; Roos, Magnus ; Jarre, Florian ; Mauve, Martin
