IEEE Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice

These are the authors' versions of the work. The copyright is with ACM. They are posted here by permission of ACM for your personal use. Not for redistribution. See individual publication details for information on the publication of the definitive versions.

Springer-Verlag LNCS Copyright Notice

The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.

Work that appeared before the 1st of September 2003 was published while the authors were with the Lehrstuhl Praktische Informatik IV at the University of Mannheim.

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

Author(s): Wolfgang Kiess.
Title: On Real-World Experiments with Wireless Multihop Networks -Design, Realization, and Analysis
Published: PhD thesis, Heinrich Heine University, Düsseldorf, Germany, June 2008
Keyword(s): Wireless Multihop Network, Experiment, Real-World, Testbed, Timestamp Synchronization, Data Analysis, MANET, Mobile Ad-hoc Network, Repeatability, Ring Flooding, Time Synchronization, Pcapsync, EXC, EDAT
Abstract: In wireless multihop networks (WMN), nodes cooperate to forward datapackets 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, thisnetworking paradigm is also promising in the context of vehicularsafety and traffic efficiency applications. After years ofsimulation-based research, the next step in the development of thisparadigm is its evaluation under real-world conditions. However, dueto the distributed nature of such a network in combination with thecomplex effects of electromagnetic wave propagation, it is extremelydifficult to perform these experiments systematically. In this thesis,we tackle the fundamental problems of the control and analysis of suchexperiments.Our first step is to develop a guidebook of existing wireless multihopnetwork experimentation techniques. Furthermore, we present ourinitial experiments, among them the first large-scale real-world studyof ring flooding which reveals that even this simple algorithmexhibits complex, unexpected behavior in realistic settings. Theexperiences made during these evaluations as well as those made byother researchers are condensed into a description of requirements tobe fulfilled by an ideal WMN testbed. Repeatability, comprehension andcorrectness have been especially neglected so far and are crucialfor systematic experiments.With this knowledge, we develop the EXC testbed based onsemi-automatic experiment control. This control approach automatesmost actions while the experimenter still can supervise and flexiblysteer the experiment. EXC is a modular and highly portable softwaretoolkit allowing other researchers to create their own testbedinstallation and thus test their protocols in the very environment forwhich they are designed. Controlling and analyzing WMN experiments requires a timekeepingaccuracy that exceeds the quality of normal computer clocks. Thestandard solution, using online clock synchronization protocols likeNTP, cannot be applied as this requires a network connection to areference clock which would interfere with the experiment traffic. Tosupport the control of the experiment, we exploit the capability ofthe NTP daemon to correct clock speed when disconnected from thereference clock. We have performed a study of the timekeeping qualityachieved by this approach on devices typically used in WMNexperiments. It demonstrates that this increases clock precision bytwo orders of magnitude, reaching millisecond precision. However, forexperiment analysis this precision is not sufficient. Therefore wecreated a post-experiment timestamp synchronization algorithm bymeans of a maximum likelihood estimator (MLE) that is suited for allnetworks with local broadcast media. It estimates the clock deviationsbased on the recorded event log files of the single nodes andsynthesizes globally consistent timestamps for these events. In ourexperimental evaluation, it exhibits an error in microsecond range.The MLE approach is integrated in pcapsync, a tool to synchronizepacket 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 aflow-based, visual programming approach and produces graphs directlyusable in scientific publications, a large fraction of the graphs inthis thesis have been created with this tool.Combining EXC, pcapsync/MLE timestamp synchronization and EDAT, weperform the first systematic study on experimental repeatability inwireless multihop networks. Up to now, most often it was implicitlyassumed that if all devices perform the same actions in twoexperiments, also the outcome will be somewhat similar and cantherefore be compared or averaged. Due to the complex electromagneticwave propagation effects, this is a risky assumption. Therefore, wepropose to consider and verify repeatability on a topological levelbased on layer two information. We derive the AD metric to quantifythe topological similarity of experiments and show that it issensitive to both interference and changes in node movement. Thismetric is used to examine - in strictly controlled experiments -topology variance in real-world environments.
Bib entry: [XML] [BibTeX]
Download: [PDF]
Verantwortlich für den Inhalt: E-Mail sendenWE Informatik