Dokument: On Real-World Experiments with Wireless Multihop Networks - Design, Realization, and Analysis

Titel:	On Real-World Experiments with Wireless Multihop Networks - Design, Realization, and Analysis
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=8077
URN (NBN):	urn:nbn:de:hbz:061-20080609-101549-4
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Kiess, Wolfgang [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 6,69 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 06.06.2008 / geändert 06.06.2008
Beitragende:	Prof. Dr. Mauve, Martin [Betreuer/Doktorvater] Prof. Dr. Conrad, Stefan [Gutachter]
Stichwörter:	wireless multihop networks, experiments, real-world experiments, testbed, time synchronization, WLAN, IEEE 802.11
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke
Beschreibungen:	In drahtlosen Multihop-Netzwerken (engl. WMN) kooperieren die beteiligten Knoten um füreinander gegenseitig Datenpakete weiterzuleiten. Die Weiterleitung erfolgt dabei ohne Infrastruktur, was einen großen Vorteil darstellt, wenn eine solche beispielsweise nach einer Naturkatastrophe nicht verfügbar ist. Daneben kann dieses Netzwerkparadigma auch im Kontext von fahrzeugbasierten Verkehrsicherheits- und Verkehrseffizienzanwendungen genutzt werden. Nach Jahren der simulationsbasierten Forschung ist der nächste Schritt in der Entwicklung dieses Paradigmas dessen Bewertung und Erforschung unter realistischen Bedingungen. Da es sich bei WMNs um verteilte Netzwerke handelt die zudem den komplexen Effekten der elektromagnetischen Signalausbreitung unterworfen sind, ist es äußerst schwierig solche Experimente systematisch durchzuführen. In dieser Arbeit werden Lösungen für die bei der Durchführung und Analyse solcher Experimente auftretenden fundamentalen Probleme untersucht und präsentiert. Im ersten Schritt entwickeln wir dazu ein Handbuch das existierende Techniken zur Durchführung und Bewertung solcher Experimente behandelt. Daneben präsentieren wir eigene Experimente, darunter die erste großflächige experimentelle Studie über das Verhalten von Ringfluten. Diese Studie demonstriert, dass selbst dieser einfache Algorithmus unter realistischen Bedingungen ein komplexes, unerwartetes Verhalten zeigt. Die dabei gewonnen Erfahrungen werden mit denen anderer Wissenschaftler zu einem Anforderungskatalog für ein WMN Testbett verdichtet. Dabei zeigt sich, dass besonders Wiederholbarkeit, Verständnis und Korrektheit bisher vernachlässigt wurden und einen integralen Bestandteil von systematischen Experimenten bilden. Basierend auf diesem Wissen wurde das EXC-Testbett entwickelt, welches auf einer halbautomatischen Kontrolle von Experimenten beruht. Dieser Ansatz für die Experimentdurchführung automatisiert die meisten Aktionen der beteiligten Geräte und erlaubt es dennoch, das Experiment zu überwachen und flexibel zu steuern. EXC ist ein modulares, hochportierbares Software-Werkzeug das es anderen Wissenschaftlern ermöglicht ein eigenes Testbett aufzubauen und neue Algorithmen in genau der Umgebung zu testen für die diese entwickelt wurden. Die Durchführung und Analyse von WMN-Experimenten erfordert Uhrgenauigkeiten, die die von normalen Computeruhren weit überschreiten. Der Standardansatz, die Synchronisation der Uhren über eine Netzwerkverbindung mittels des NTP-Protokolls, ist hierbei nicht anwendbar da die dabei ausgetauschten Datenpakete das Experiment stören können. Um die Durchführung von Experimenten zu unterstützen nutzen wir deshalb die Fähigkeit des NTP-Deamons zur Korrektur der Uhren ohne bestehende Netzwerkverbindung. In Messungen mit bei WMN Experimenten oft eingesetzter Hardware zeigt sich, dass die Uhrgenauigkeit damit um zwei Größenordnungen verbessert werden kann, im aktuellen Fall betragen die Unterschiede nur noch wenige Millisekunden. Dennoch ist diese Genauigkeit für die Analyse von Experimenten nicht ausreichend. Deswegen wurde von uns ein auf der Maximum-Likelihood-Methode (engl. MLE) basierendes Verfahren zur nachträglichen Synchronisation von Zeitstempeln entwickelt, das für alle Netzwerke mit lokalen Broadcasteigenschaften eingesetzt werden kann. Dieses Verfahren schätzt die Uhrenfehler mittels der aufgezeichneten Logdateien und erzeugt basierend auf dieser Schätzung global konsistente Zeitstempel für die aufgetretenen Ereignisse. In einer experimentellen Auswertung hat dieses Verfahren einen Fehler im Mikrosekundenbereich. Dieses Verfahren ist auch in pcapsync integriert, einem Werkzeug zur Synchronisation von Paketlogdateien im weit verbreiteten libpcap-Format. Um ein Experiment nach dessen Ende einfach und gleichzeitig flexibel analysieren zu können, wurde im Rahmen dieser Arbeit das modulare Datenanalysewerkzeug EDAT entwickelt. Es nutzt einen datenflußbasierten, visuellen Ansatz und kann direkt in wissenschaftlichen Publikationen verwendbare Diagramme erzeugen. Dies wird auch durch die Tatsache unterstrichen, dass ein Großteil der in dieser Arbeit gezeigten Diagramme mit diesem Werkzeug erstellt wurden. Durch die Kombination von EXC, pcapsync/MLE-Zeitstempel-Synchronisation und EDAT konnten wir die erste systematische Studie zur Wiederholbarkeit von WMN Experimenten durchführen. Bisher wurde meist implizit davon ausgegangen, dass identisches Knotenverhalten in zwei Experimenten auch zu identischen Ergebnissen führt. Aufgrund der komplexen Effekte elektromagnetischer Signalausbreitung ist dies jedoch eine riskante Annahme. Deswegen betrachten wir Wiederholbarkeit auf der Ebene der Netzwerktopologie. Mittels der neu entwickelten AD-Metrik ist es möglich, die Ähnlichkeit zweier Topologien quantitativ zu bestimmen. Wir zeigen, dass diese Metrik sowohl mit Interferenzen als auch mit Änderungen in den Knotenbewegungen umgehen kann. In streng kontrollierten Experimenten wird untersucht wie groß die tatsächlich auftretenden Topologieänderungen in realistischen Umgebungen sind. In wireless multihop networks (WMN), nodes cooperate to forward data packets for each other. This forwarding works without infrastructure, being a huge advantage if no such infrastructure is available, e.g. because it has been destroyed by a disaster. Furthermore, this networking paradigm is also promising in the context of vehicular safety and traffic efficiency applications. After years of simulation-based research, the next step in the development of this paradigm is its evaluation under real-world conditions. However, due to the distributed nature of such a network in combination with the complex effects of electromagnetic wave propagation, it is extremely difficult to perform these experiments systematically. In this thesis, we tackle the fundamental problems of the control and analysis of such experiments. Our first step is to develop a guidebook of existing wireless multihop network experimentation techniques. Furthermore, we present our initial experiments, among them the first large-scale real-world study of ring flooding which reveals that even this simple algorithm exhibits complex, unexpected behavior in realistic settings. % It shows that flooding with the network diameter \emph{d} is not % enough if all nodes should be reached and that the often used term % of an \emph{n}-hop neighborhood must be revised. % The second evaluation was performed with a propagation estimation % toolkit designed to survey the radio propagation characteristics in % an experimentation area. The experiences made during these evaluations as well as those made by other researchers are condensed into a description of requirements to be fulfilled by an ideal WMN testbed. Repeatability, comprehension and correctness have been especially neglected so far and are crucial for systematic experiments. With this knowledge, we develop the EXC testbed based on semi-automatic experiment control. This control approach automates most actions while the experimenter still can supervise and flexibly steer the experiment. EXC is a modular and highly portable software toolkit allowing other researchers to create their own testbed installation and thus test their protocols in the very environment for which they are designed. Controlling and analyzing WMN experiments requires a timekeeping accuracy that exceeds the quality of normal computer clocks. The standard solution, using online clock synchronization protocols like NTP, cannot be applied as this requires a network connection to a reference clock which would interfere with the experiment traffic. To support the control of the experiment, we exploit the capability of the NTP daemon to correct clock speed when disconnected from the reference clock. We have performed a study of the timekeeping quality achieved by this approach on devices typically used in WMN experiments. It demonstrates that this increases clock precision by two orders of magnitude, reaching millisecond precision. However, for experiment analysis this precision is not sufficient. Therefore we created a post-experiment timestamp synchronization algorithm by means of a maximum likelihood estimator (MLE) that is suited for all networks with local broadcast media. It estimates the clock deviations based on the recorded event log files of the single nodes and synthesizes globally consistent timestamps for these events. In our experimental evaluation, it exhibits an error in microsecond range. The MLE approach is integrated in pcapsync, a tool to synchronize packet trace files in standard libpcap format. To cope with the need of flexible data analysis after an experiment, we have developed the modular data analysis tool EDAT. It follows a flow-based, visual programming approach and produces graphs directly usable in scientific publications, a large fraction of the graphs in this thesis have been created with this tool. Combining EXC, pcapsync/MLE timestamp synchronization and EDAT, we perform the first systematic study on experimental repeatability in wireless multihop networks. Up to now, most often it was implicitly assumed that if all devices perform the same actions in two experiments, also the outcome will be somewhat similar and can therefore be compared or averaged. Due to the complex electromagnetic wave propagation effects, this is a risky assumption. Therefore, we propose to consider and verify repeatability on a topological level based on layer two information. We derive the AD metric to quantify the topological similarity of experiments and show that it is sensitive to both interference and changes in node movement. This metric is used to examine -- in strictly controlled experiments -- topology variance in real-world environments.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	06.06.2008
Dateien geändert am:	06.06.2008
Promotionsantrag am:	03.04.2008
Datum der Promotion:	03.06.2008