Project Outline

Project Focus
We want to investigate various algorithmic aspects of sensor-actuator networks within the scope of subproject K5. Our main focus is on algorithms that help to minimize the energy consumption of sensor-networks. Generation and storage of energy is still not solved efficently on a small scale such as on a sensor node. Thus, we have to treat the available energy as a scarce resource and try to optimize the usage of the remaining energy to extend the lifetime of the network for as long as possible.
With in this large topic we have selected two sub-topics that we will investigate more thoroughly in the next years, lifetime optimization and routing.

Lifetime Optimization. The nodes of a sensor-network perform their task alone or in concert with other nodes. Usually, not all nodes are required to be active all the time. Therefore, it is reasonable to provide an individual operation schedule for each node. Thus, while still retaining the full functionality of the sensor network, its energy consumption can be minimized, or in other words, the lifetime of the network can be maximized.

Routing. Communication between sensor nodes is one of the most energy-consuming activities of a sensor-actuator-network. Thus, it is important to use preferably short and energy-efficient transmission paths for the sensor messages. But one has also to guarantee that no single node is overstressed when compared to the others. Furthermore, the ensuing communication patterns are usually application-dependent. Thus, they should also be taken into account when designing a communication structure.

A fast adaptability to changing topologies (i.e. nodes break done or move) and a distributed planning of activities are of great importance for almost all aspects of sensor-actuator-networks. Both are desirable properties that usually do not arise in classic scenarios or are only of little importance there. Thus, they have to be newly developed for our needs.


State of the Art
There already exists a lot of work in the field of sensor scheduling and routing with focus on energy-efficiency and therefore with the goal to optimize the lifetime of sensor networks. Most often the presented algorithms either are ad-hoc solutions, that have only been evaluated empirically without any theoretical guarantees or they are purley theoretical works, that base their solutions on models that are to simple to function in real-world scenarios. This lack of overlap between theory and practice can be found throughout this entire field of research.

Theoretical research on optimizing the lifetime of sensor networks used for area monitoring has beeen done e.g. by Calinescu et al.. The problem is formulated as linear program and an approximation algorithm is given. Unfortunately there are no general complexity analyses. Only Cardei et al. proved the NP-hardness for a special case of this covering problem. Most of these works only apply a very simple unit-disc-model to describe the network topology, which is required e.g. as basis for routing algorithms. This very abstract model but also more realistic models can only describe the chaotic conditions of reality very insufficiently. But there also exist interesting algorithms that do not need any initial assumptions on the network topology. Here, we refer to the routing algorithm GLIDER. This algorithm is very interesting, since it takes approaches from classic routing algorithms like landmarks and hierarchies and adapts them for sensor networks.

To shorten the gap between theory and practice, there are several sophisticated simulators (ns-2) and emulators (CMUlab) that can be used by the community to analyse their proposed algorithms. These applications cannot entirely replace a real testbed, but they can provide realistic results for a lot of applications.


Goals
The research in this subproject concentrates on algorithms for lifetime optimization of sensor networks and on algorithms for routing in these networks. Several use-case scenarios will be identified and analyzed for both topics. We aim at evaluating and improving existing solutions as well as developting new and innovative algorithms. We want to develop efficient algorithms that provide good theoretical performance guarantees. Furthermore, we want to provide robust algorithms for real or at least for realistic scenarios that not only provide good results on a simplified simulator.

The realization of these goals involves the development of adequate models and the mathematical formulation and complexity analysis of the studied problems. Starting from the theoretical results, algorithms for finding exact or approximative solutions with good performance guarantees will be developed according to the methods of algorithm engineering. We will focus on both, centralized and distributed algorithms. The solutions are to be evaluated theoretically and in experiments.