Technical Reports 2008

14 Publikation(en)

MAC Protocols for Low-latency and Energy-efficient WSN Applications

Pardeep Kumar, Mesut Günes

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-12

tr-b-08-18.pdf

Most of medium access control (MAC) protocols proposed for wireless sensor networks (WSN) are targeted only for single main objective, the energy efficiency. Other critical parameters such as low-latency, adaptivity to traffic conditions, scalability, system fairness, and bandwidth utilization are mostly overleaped or dealt as secondary objectives. The demand to address those issues increases with the growing interest in cheap, low-power, low-distance, and embedded WSNs. In this report, along with other vital parameters, we discuss suitability and limitations of different WSN MAC protocols for time critical and energy-efficient applications. As an example, we discuss the working of IEEE 802.15.4 in detail, explore its limitations, and derive efficient application-specific network parameter settings for time, energy, and bandwidth critical applications. Eventually, a new WSN MAC protocol Asynchronous Real-time Energy-efficient and Adaptive MAC (AREA-MAC) is proposed, which is intended to deal efficiently with time critical applications, and at the same time, to provide a better trade-off between other vital parameters, such as energy-efficiency, system fairness, throughput, scalability, and adaptivity to traffic conditions. On the other hand, two different optimization problems have been formulated using application-based traffic generating scenario to minimize network latency and maximize its lifetime.

7 Types of Cooperation Episodes in Side-by-Side Programming

Lutz Prechelt, Ulrich Stärk, Stephan Salinger

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-12

7 Types of Cooperation Episodes in ...

In side-by-side programming, two programmers (typically working on related aspects of a project) move their computers so close to one another that they can effortlessly change between working alone and working together, where working alone is the primary mode. The technique was proposed in order to obtain some of the advantages of pair programming at much lower overhead. As a first step towards understanding how and when to use side-by-side programming, the present study aims at describing when and for what purpose side-by-side programmers get together to cooperate. The main result is a classification of the cooperation episodes by purpose and content into different types: Exchange project details, Exchange general knowledge, Discuss strategy, Discuss step, Debug work product, Integrate work products, and Make remark. These types were derived via the Grounded Theory method and are described conceptually in terms of the types of events of which they consist. All concepts used in these descriptions are grounded in actual observations.

Thema: pair programming, collaboration, process, qualitative research, grounded theory

Maschinelles Spielen im Klassiker Asteroids

Paul Czerwionka, Marco Block, Maro Bader, Raul Rojas

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-10

tr-b-08-16.pdf

Das Ende der 80er Jahre veröffentlichte, auf Reaktion und Planung basierende Spiel Asteroids, gilt inzwischen als eines der erfolgreichsten Computerspiele aller Zeiten. Es eignet sich hervorragend als Testplattform für die verschiedensten KI-Konzepte, die anhand erreichter Punktezahlen verglichen werden können. In der vorliegenden Arbeit wird ein adaptives physikalisches Weltmodell eingeführt, mit dessen Hilfe eine optimale Verhaltensstrategie gefunden werden kann. Mittels einer heuristischen Suche wird eine Aktionsfolge gefunden, die in minimaler Zeit versucht, die Punkte zu maximieren. Die hier vorgestellten Ideen wurden im Programm Asteroids realisiert, welches erfolgreich am Wettbewerb der Computerzeitschrift c’t 2008 teilnahm und in fünf Minuten eine Spitzenpunktezahl von 85.000 erreichte.

Proceedings of 7. GI/ITG KuVS Fachgespräch “Drahtlose Sensornetze”

Hartmut Ritter, Kirsten Terfloth, Georg Wittenburg, and Jochen Schiller, editors

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-09

tr-b-08-12.pdf

Thema: Wireless Sensor Networks

Scalable Adaptive Group Communication on Bi-directional Shared Prefix Trees

Matthias Wählisch

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-09

tr-b-08-14.pdf

Efficient group communication within the Internet has been implemented by multicast. Unfortunately, its global deployment is missing. Nevertheless, emerging and progressively establishing popular applications, like IPTV or large-scale social video chats, require an economical data distribution throughout the Internet. To overcome the limitations of multicast deployment, we introduce and analyze BIDIR-SAM, the first structured overlay multicast scheme based on bi-directional shared prefix trees. BIDIR-SAM admits predictable costs growing logarithmically with increasing group size. We also present a broadcast approach for DHT-enabled P2P networks. Both schemes are integrated in a standard compliant hybrid group communication architecture, bridging the gap between overlay and underlay as well as between inter- and intra-domain multicast.

Entzerrung von Textdokumenten unter Verwendung von Thin-Plate-Spline

Marco Block, Raul Rojas

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-09

tr-b-08-13.pdf

Viele Verfahren identifizieren zunächst Textzeilen und ermitteln anschließend über die Dokumentrandeigenschaften die notwenige Korrekturtransformation. Das in dieser Arbeit vorgestellte Verfahren benötigt keine Dokumentrandeigenschaften, sondern ermittelt die Dokumentorientierung anhand der Buchstabenausrichtungen. Als Interpolationmethode wird Thin-Plate-Spline verwendet.

The ScatterWeb MSB-A2 Platform for Wireless Sensor Networks

Michael Baar, Heiko Will, Bastian Blywis, Thomas Hillebrandt, Achim Liers, Georg Wittenburg, Jochen Schiller

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-09

tr-b-08-15.pdf

Wireless sensor networks (WSN) are in a transition from research to real world applications. Robust and efficient hardware platforms are needed. These have to offer sufficient processing power and memory while retaining energy efficiency. In this technical report we present the newest ScatterWeb hardware platform that fits the needs of research and prototyping applications of the near future.

Concept and Design of the Hybrid Distributed Embedded Systems Testbed

Mesut Günes, Bastian Blywis, Felix Juraschek

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-08

tr-b-08-10.pdf

Wireless mesh networks are an emerging and versatile communication technology. The most common application of these networks is to provide access of any number of users to the world wide Internet. They can be set up by Internet service providers or even individuals joined in communities. Due to the wireless medium that is shared by all participants, effects like short-time fading, or the multi-hop property of the network topology many issues are still in the focus of research. Testbeds are a powerful tool to study wireless mesh networks as close as possible to real world application scenarios. In this technical report we describe the design, architecture, and implementation of our work-in-progress wireless testbed at Freie Universität Berlin consisting of 100 mesh routers that span multiple buildings. The testbed is hybrid as it combines wireless mesh network routers with a wireless sensor network.

Practical Issues of Implementing a Hybrid Multi-NIC Wireless Mesh-Network

Mesut Günes, Bastian Blywis, Felix Juraschek, Phillip Schmidt

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-08

tr-b-08-11.pdf

Testbeds are a powerful tool to study wireless mesh and sensor networks as close as possible to real world application scenarios. In contrast to simulation or analytical approaches these installations face various kinds of environment parameters. Challenges related to the shared physical medium, operating system, and used hardware components do arise. In this technical report about the work-in-progress Distributed Embedded Systems testbed of 100 routers deployed at the Freie Universität Berlin we focus on the software architecture and give an introduction to the network protocol stack of the Linux kernel. Furthermore, we discuss our first experiences with a pilot network setup, the encountered problems and the achieved solutions. This writing continues our first publication and builds upon the discussed overall testbed architecture, our experiment methodology, and aspired research objectives.

Towards Corporate Semantic Web: Requirements and Use Cases

Gökhan Coskun, Ralf Heese, Markus Luczak-Rösch, Radoslaw Oldakowski, Ralph Schäfermeier and Olga Streibel

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-08

tr-b-08-09.pdf

In this report, we introduce our initial vision of the Corporate Semantic Web as the next step in the broad field of Semantic Web research. We identify requirements of the corporate environment and gaps between current approaches to tackle problems facing ontology engineering, semantic collaboration, and semantic search. Each of these pillars will yield innovative methods and tools during the pro ject runtime until 2013. Corporate ontology engineering will improve the facilitation of agile ontology engineering to lessen the costs of ontology development and, especially, maintenance. Corporate semantic collaboration focuses the human-centered aspects of knowledge management in corporate contexts. Corporate semantic search is settled on the highest application level of the three research areas and at that point it is a representative for applications working on and with the appropriately represented and delivered background knowledge. We propose an initial layout for an integrative architecture of a Corporate Semantic Web provided by this three core pillars.

Abort and Blocking Risks of Atomic Transactions in Mobile Ad-Hoc Networks

Joos-Hendrik Boese

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-06

tr-b-08-07.pdf

It is generally known that in the presence of multiple node or communication failures atomic commit protocols cannot avoid blocking. While in fixed wired networks such situations are rare because of low failure probabilities, mobile ad-hoc networks (MANETs) are considered to be a more challenging environment. In this technical report I present a probabilistic model to predict the abort and blocking risk of distributed atomic transactions for arbitrary MANET scenarios. The model presented is applied to a standard MANET scenario to demonstrate the dimensions of blocking risks to be expected in MANETs.

Implementation and Evaluation of a SWARMLINDA System

Daniel Graff

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-06

tr-b-08-06.pdf

In the middle 80s David Gelernter from the Yale University developed a programming language called LINDA. It is applied in the field of distributed environment development. Moreover, LINDA also describes a coordination model which is fully distributed in space and time. Based on its characteristic, although being used in parallel computing, it is restricted to a certain amount of servers while it cannot cope with adaptiveness and scalability in an open environment. As a solution SWARMLINDA is proposed based on a decentralized multi-agent system which got its inspiration by nature in the field of swarm intelligence. The ability of the architecture is characterized by a very scalable behavior. The system can grow to enormous size while still be very effective since the principle is based on only local interaction with the surrounding neighborhood. The behavior patterns are observed from natural individuals (aka swarms) like ants, birds, termites and bees. Each agent is characterized by simplicity, dynamism and locality. The research for the report has been performed in evaluating as well as examining properties, problems, behavior pattern and advantages of swarm intelligence used in a SWARMLINDA system. In particular, the work discusses involved mechanisms and describes the development of a SWARMLINDA. Further on, it defines different metrics being used in the system. A main part is based on the distribution of information objects in a 2D environment by forming clusters which hold similar objects. The cluster itself is defined by a spatial region containing several associative memories. Finally, the report closes by presenting plenty of test runs that have been executed on the SWARMLINDA system. In order to rate the performance an evaluation metric has been developed defining the spatial network entropy.

Information Management as an Explicit Role in OSS projects: A Case Study

Christopher Oezbek, Robert Schuster, and Lutz Prechelt

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-04

tr-b-08-05.pdf

Globally distributed teams of volunteers and electronic means of communication are at the core of Open Source Software development. To aid projects in managing their information, we defined a light-weight, role-based process improvement and observed its use in a longitudinal case study. Results gathered by mailing-list analysis give insights into the different types of information managed and their relative importance: While technical content such as how-tos and to-dos is most frequent, the amount of information regarding decision making is surprisingly low.

Social Editing of Video Recordings of Lectures

Margareta Esponda, Benjamin Jankovic

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2008-01

tr-b-08-04.pdf

In this paper we show how video recordings of lectures can be enhanced through “social editing”, a special sort of “human computation”. We record lectures using six cameras arranged to produce a panoramic view (360 degrees) of the classroom. After recording, viewers can replay the lectures on a computer and can navigate through them tilting and zooming a virtual camera. All user interactions are recorded by the system, and are later used to decide which views should be stored and their zoom level. The result is an automatically edited video as a result of the social navigation of the first few initial viewers of the lecture.

Thema: Automatic video editing, social navigation, virtual videography, human