Department of Computer Science

Algorithms and Complexity

Christian Schindelhauer



I have moved to Freiburg: My new homepage
  • Smart Team, SPP 1183 Organic Computing
  • DELIS: Dynamically Evolving Large-scale Information Systems
  • Sensor networks in super markets, research award Universität Paderborn 2004
  • DFG Collaborative Research Center SFB 376, sub-project C6: Mobile ad-hoc Networks (German)
  • COST action 295, DYNAMO, Dynamic Communication Networks

Mobile Ad Hoc Networks

This research is embedded in the sub-project C6 Mobile Ad-hoc-Networks of CRC 376 (Massively Parallel Systems). Within this project we cooperate with the Electrical Engineering Department’s research group of Prof. Dr. Ulrich Rückert (System and Circuit Technology). We are interested in development, analysis and implementation of method for network management and communication in wireless mobile ad hoc networks (MANET). These methods are adaptiv, can adapt to high dynamics, are resource effiecien regarding energy and time.

In cooperation with Prof. Franz Rammig’s group (Design of Parallel Systems) and Prof. Stefan Böttcher (Databases and E-Commerce) we currently work on scalable MANETs for connection laptops with W-LAN technology. We aim at an prototypical implementation which is able to connect hundreds of computers over W-LAN with and without the Internet

Sensor Networks

New hardware technology has made wireless sensor networks possible. So, it is no longer necessary to use kilometers of cable to connect sensor technology in houses. Nowadays, little devices can measure temperature, light, sound, motion, etc. and can transmit this information to a central station. Even mult-hop communication is possible and the current trend is to further minituriaze this hardware. We see our contribution in this ares in minituriazing the software to the bare minimum such that communication can be made with a minimum amount of  energy, memory, and time. This project won the research award of the University of Paderborn. We are cooperating with the research group of Prof. Ulrich Hilleringmann (Sensor Technology) of the Electrical Engineering Department and with the  group of Holger Karl (Computer Networks).


Within the workpackage 6.2, Enhanced Distributed Hash Tables for Keyword Search of the Integrated-Project DELIS (Dynamically Evolving, Large-scale Information Systems) we are cooperating with  Prof. Dr. Gerhard Weikum, Max-Planck-Institute of Computer Science, Saarbrücken, German. Within this project we design and analyze distributed algorithms and peer-to-peer-networks for a Peer-to-Peer based World-Wide-Web-search engine. Our contribution to this project is the design of a locality based peer-to-peer-network which reflects information and network locality. For this we investigate random graph transformations by Markov processes which uphold graph properties like connectivity, expansion.

Competitive Routing

For position-based routing nodes are identified by their unique geographical positions. The task is to deliver a message from a source node to a target node identified by its position in an unknown wireless ad hoc network.  We try to optimize the number of messages and the time to perform this task in a worst case setting. One obstacle for efficient position based routing is the lack of knowledge about the network structure available at the beginning. In particular, reactive routing protocols that do not know any network structure in advance fail to solve this problem efficiently.

As complexity measures we consider time and traffic for delivering the message from source to target cell. Time is the number of rounds until the message reaches the destination if the node is accessible. Traffic is the total number of messages sent between cells. We investigate the time and traffic under a competitive measure. This research nicely extends to robot motion planning if we restrict ourselves to a single message

Smart Teams

In this project we aim at laying the algorithmic foundations for a scenario where an exploration team of robots - we call it a smart team -  has to organize itself in order to fulfill tasks like exploring an unknown terrain  and  executing work in this terrain. This research is funded as a sub-project in SPP 1183 (Organic Computing).

The tasks of such a smart team are similar to the fundamental challenges of all social life forms: Explore, (self-)organize, communicate, and jointly act.  Examples for robotic applications are rescue expeditions in dangerous areas or expeditions in the oceans or on planets. The work of such a smart team has to be guided by strategies for exploration, for finding important objects, and for assigning to such an object a subgroup of robots that jointly have the capabilities necessary to process the object.

We use state-of-the-art algorithmic techniques to tackle these problems. The challenge is that all these tasks have to be executed by local, distributed strategies that act on the mobile network of the moving robots, and have to result in a robust, effective self-organization of the team. None of these robots will ever have more than very restricted, local knowledge about the global state of the system. Their decisions are solely based on their own observations and findings, from which a globally good behavior of the whole team has to emerge.

Created 2005-10-02
Last Change 2005-10-02
Copyright Christian Schindelhauer