K2.1: Algorithmische Aspekte der Clusterbildung, Topologiekontrolle und Lokalisierung
- Ansprechpartner:
Motivation
Sensor-Aktor-Netzwerke unterliegen in der Regel engen Limitierungen hinsichtlich des zur Verfügung stehenden Energiebudgets bzw. der zur Verfügung stehenden Kommunikationskapazität. Eine fundamentale Fragestellung im Themenfeld der Sensor-Aktor-Netzwerke ist deshalb die Frage nach der Kapazität dieser drahtlosen Netzwerke, d.h. welches Datenvolumen kann in einem Sensor-Aktor- bzw. Ad-Hoc Netzwerk durch „Multi-Hop-Kommunikation“ transportiert werden? Ausgehend von bestehenden Ergebnissen sollen weitere Teilaspekte betrachtet werden, etwa die Frage, inwieweit Mobilität der Knoten die Kapazität erhöhen kann, wie für ein konkretes Netzwerk eine obere Schranke für die Kommunikationskapazität berechnet werden kann oder inwiefern alternative Kapazitätsdefinitionen sinnvoll sind. Insgesamt zeichnet sich hier die Entwicklung eines Forschungsgebiets „Netzwerkinformationstheorie“ für drahtlose Netzwerke ab. Dieses Forschungsgebiet muss in engem Zusammenhang mit Protokollen und Architekturen betrachtet werden, die in diesem Teilprojekt ebenfalls eine wichtige Rolle einnehmen. So tauchen bei Sensor-Aktor-Netzwerken neue Fragestellungen hinsichtlich des zuverlässigen und qualitätsbehafteten (z.B. Rechtzeitigkeit) Transports von Daten auf. Durch das „In-Network-Processing“ ist zuverlässiger Transport neu zu definieren, die klassischen Sichtweise wie beispielsweise Ende-zu-Ende Zuverlässigkeit bei TCP sowie die strikte Schichtentrennung können also nicht mehr direkt angewandt werden. Hier gilt es, geeignete Protokolle und Architekturen zu entwerfen, die es dann erlauben, die theoretisch ermittelte Kapazität auch in der Praxis möglichst gut auszunutzen.
Stand der Forschung
Die Arbeit von Gupta und Kumar im Jahre 2000 hat eine erste wichtige asymptotische Aussage (beliebig große Netzwerke, Weitverkehrskommunikation) zur Kommunikationskapazität in drahtlosen Netzwerken treffen können. Grossglauser et al. haben gezeigt, dass Mobilität die Kapazität erhöhen kann; allerdings wird hier die Dienstgüte „Rechtzeitigkeit“ geopfert. Des Weiteren wurden andere Kapazitätsdefinitionen vorgeschlagen, etwa die der „bits-per-joule capacity“ (Rodoplu und Meng [K1.3]), welche insbesondere für Sensor-Aktor-Netzwerke mit sehr beschränkten Energiereserven wichtig ist. Peschlow et al. geben ein Schätzverfahren für die Kommunikationskapazität für konkrete Netzwerke basierend auf Färbungsverfahren an [K1.4]. Alle diese Arbeiten stellen interessante Ansätze dar, die sich allerdings entweder nur auf Teilaspekte der Netzwerkmodellierung oder nur auf ausgewählte Qualitätsparameter beziehen. In [K1.12] wird auf die Wichtigkeit zuverlässiger Datenübertragung in Sensor-Aktor-Netzwerken hingewiesen. [K1.13] erwähnt explizit die Notwendigkeit der Untersuchung von Transportprotokollen in diesem Kontext. In [K1.14] wird zwar die Verteilung von Daten betrachtet, allerdings ohne explizite Berücksichtigung fehlerloser Übertragung. Ein erster Ansatz in dieser Richtung ist in [K1.15] zu finden, wobei allerdings beispielsweise „In-Network Processing“ nicht explizit beachtet wird. Eigene Vorarbeiten Die Arbeitsgruppe von Prof. Zitterbart befasst sich seit vielen Jahren mit Protokollen und Architekturen für Internet-basierte Kommunikation, wobei sowohl Festnetze als zunehmend auch Mobilnetze im Mittelpunkt des Interesses stehen. Aktuelle Arbeiten im Bereich mobiler Ad-hoc Netzwerke befassen sich u.a. damit, wie Daten möglichst effizient an eine Gruppe von Teilnehmern ausgeliefert werden können [K1.8]. Hierzu werden teilweise so genannte Overlay-Netzwerke eingesetzt. Inwiefern sich solche Ansätze auch in Sensor-Aktor-Netzwerken eignen, muss untersucht werden. Hinsichtlich Dienstgüte wurden Untersuchungen hinsichtlich geeigneter Architekturen und Protokolle vor allem im Kontext des Internet durchgeführt, die teilweise in Internet-RFCs resultierten [K1.9], [K1.10]. Darüber hinaus wurden Dienstgüte und Mobilität untersucht [K1.11], was insbesondere bei mobilen Sensor-Aktor-Knoten ebenfalls relevant sein wird, allerdings aufgrund der veränderten Systemeigenschaften nicht direkt angewendet werden kann. Die Arbeitsgruppe von Prof. Hartenstein beschäftigt sich vornehmlich mit mobilen Ad-Hoc Netzwerken, insbesonders für die Kommunikation zwischen Fahrzeugen (BMBF-Projekte FleetNet und NOW: Network on Wheels), sowie mit Overlay-Netzwerken. Dabei stehen Protokollentwicklung und –bewertung sowie mathematische Modellierung im Vordergrund. Aktuelle Arbeiten behandeln beispielsweise die Themen Zuverlässigkeit und „broadcast capacity“ [K1.5], Topologieausprägung in drahtlosen Netzwerken [K1.6] und Mobilität [K1.7].
Ziele
Die in diesem Teilprojekt durchgeführten Forschungsarbeiten sollen unter Anderem eine umfassende Betrachtung des Themas „Kapazität“ und damit eine möglichst konkrete Bewertung des Potentials von drahtloser „Multi-Hop-Kommunikation“ für verschiedenste Einsatzgebiete ermöglichen. Darüber hinaus sollen Protokolle und Architekturen zur Bereitstellung von Dienstgüte untersucht werden. Besonderer Wert wird hier zunächst auf die Zuverlässigkeit gelegt und deren Auswirkungen hinsichtlich des in Sensor-Aktor-Netzwerken nicht mehr vorhandenen Ende-zu-Ende Paradigmas. Der rechtzeitigen Auslieferung der Daten wird darüber hinaus Aufmerksamkeit gewidmet. Bei der Kapazitätsbetrachtung sollen die vorliegenden Teilergebnisse in Beziehung zueinander gestellt und weiterentwickelt werden. Ziel dabei ist es, Kapazitätswerte für konkrete Netzwerke sowie theoretische obere Schranken für die Leistungsfähigkeit drahtloser Netzwerke zu ermitteln. Dabei sollen insbesonders Mobilität und Radiokanalschwankungen sowie unterschiedliche Datenverkehrsmuster und Dienstgüteparameter einbezogen werden. Darüber hinaus werden Datenaggregation sowie „cross-layer design“ sowohl bei der Entwicklung von Protokollen und Architekturen als auch bei der Kapazitätsberechnung berücksichtigt. In diesem Zusammenhang soll hinsichtlich der Zuverlässigkeit untersucht werden, wie ein zuverlässiger Ende-zu-Ende Transport von Daten bewerkstelligt wird. Dabei ist zu beachten, dass die Daten typischerweise im Netzwerk aggregiert und verarbeitet werden („In-Network-Processing“). Trotzdem muss letztendlich sichergestellt werden, dass die Daten bzw. deren Semantik korrekt beim Zielsystem angelangen. Es sollen geeignete Architekturen entwickelt werden, die eine solche Zuverlässigkeit bereitstellen können. Dabei sind schichtenübergreifende Aspekte mit zu betrachten. Die Verteilung von Daten in Sensor-Aktor-Netzwerken unterscheidet sich signifikant von traditionellen Fest- und Mobilnetzen. Daten werden typischerweise regelmäßig von Sensoren geliefert und gemäß eines Push-Verfahrens im Netzwerk weitergeleitet. Hier ist zu untersuchen, welche Kommunikationsformen gut geeignet sind. Kandidaten sind Multicast-, Anycast- und Broadcast-Kommunikation. Die traditionelle Punkt-zu-Punkt Kommunikation dürfte eher eine untergeordnete Rolle spielen. Ebenfalls untersucht werden soll der bereit zu stellende Dienst. Traditionell wird zwischen verbindungsorientierten und verbindungslosen Diensten unterschieden. Es bleibt zu analysieren welche dieser Formen in welcher Ausprägung wann in einem Sensor-Aktor-Netzwerk sinnvoll zum Einsatz kommen. Eng damit verbunden ist der Aspekt der Zustandshaltung. Aufgrund der potenziellen Unzuverlässigkeit von Sensor-Aktor-Netzwerken müssen geeignete Verfahren bei der Zustandshaltung berücksichtigt werden, um eine Kommunikation mit den gewünschten Dienstgüteparametern zu ermöglichen.