Seminar: Eingebettete Systeme (SS2011)

In dieser Einführungsveranstaltung werden einige, für das Seminar wesentliche Begriffe (z.B. Eingebettetes System, Sensornetzwerk, ...) kurz erläutert (vgl. Thema "Begriffsklärung"), sowie die bereitgestellten Themen vorgestellt. Eine Themenreservierung ist ebenso möglich, wie die Erörterung des organisatorischen Ablaufs.

Was bedeutet eigentlich Selbstorganisation, Organic Computing, biologisch inspiriert, Emergenz? Welche Möglichkeiten bieten die o.g. Ansätze? Welche Fähigkeiten stecken in ihnen? Wie entwickelt und modelliert man ein selbstorganisiertes System (SOS)? Welchen Grenzen unterliegen sie? Wo sind ihre Einsatzgebiete?

Dieser Vortrag soll die obigen Fragen klären und außerdem einen genaueren Überblick über die Methoden der Selbstorganisation (Feedback, Interaktion, Wahrscheinlichkeit) liefern. Kronkete Beispiele runden diesen Vortrag idealerweise ab.

Nachdem die Begrifflichkeiten geklärt sind, will man diese "naturnahen" Techniken natürlich für verteilte, eingebettete Systeme, also etwa Sensornetze, verwenden. Dabei sind aber aufgrund des drahtlosen Kommunikationsmediums einige Besonderheiten zu beachten. Die Methodik der Selbstorganisation für Ad-hoc und Sensornetze läßt sich hauptsächlich durch eine horizontale und eine vertikale Dimension kategorisieren.

Dieser Vortrag soll nach einem kurzen Einstieg in das Thema die beiden MAC-Protokolle S-MAC und Power Control MAC detailliert vorstellen und vergleichen. Konkrete Anwendungsbeispiele runden auch diesen Vortrag ab.

Will man Daten gezielt über mehrere Stationen (sog. Hops) versenden, benötigt man entweder sog. Routing-Verfahren oder man wählt einen Datenzentrierten Ansatz. Bekannte (selbstorganisierte) Vertreter sind etwa Destination Sequenced Distance Vector (DSDV), Dynamic Source Routing (DSR), oder Ad-hoc On Demand Distance Vector (AODV).

In diesem Vortrag soll nach einem Einstieg in das Thema ein bis zwei (der o.g.) Routingverfahren detailliert vorgestellt und unterucht werden.

Müssen sich die Komponenten eines verteilten Systems irgendwie untereinander verständigen, da etwa nicht genügend Resourcen für alle zur Verfügung stehen, so stellt sich spätestens hier die Frage nach der Koordination. Da aber bei einem sehr dichten Netz nur eine kleine Auswahl der möglichen Netzwerkteilnehmer ausreicht, um die geforderte Aufgabe zu lösen, existieren Algorithmen, die eine derartige verteilte Koordination resourcen-schonend ermöglichen.

In diesem Vortrag soll nach einem Einstieg in das Thema der Ansatz Adaptive Self-Configuring Sensor Network Topologies (ASCENT) detailliert beschrieben und dessen Verhalten anhand von konkreten Beispielen veranschaulicht werden.

Soll das verteilte System eine gemeinsame Aufgabe erledigen, so bedarf es mehr, als bloße Koordination: die Komponenten müssen kollaborieren, d.h. sie müssen versuchen, sich gegenseitig aufgrund ihrer Fähigkeiten zu helfen. Ein daraus hergehendes Problem ist die adäquate Verteilung der einzelnen Teilaufgaben.

Dieser Vortrag spezifiziert das Problemgebiet und gibt dann einen Einblick in einen konkreten Ansatz zur sog. dynamischen Negotiation (z.B. MURDOCH). Eine Analyse des vorgestellten Algorithmus sowie konkrete Anwendungsbeispiele desselben vervollständigen diesen Vortrag. 

Um verläßlich Dienste in einem verteilten System wartungsfrei anbieten zu können, kann man im System redundante Resourcen vorhalten. Allerdings gibt es auch resourcen-schonendere, selbstorganisierte  Ansätze, die vor allem in der Resourcen(gleich)verteilung ihre Stärken haben.

In diesem Vortrag soll nach einem kurzen Üblerblick über das zugrundeliegende Systemmodell eine mathematische Analyse zur Partitionierung und zur "fairen" Auslastung der Hard-/Software der rekonfigurierbaren Sensorknoten erstellt werden.

Ein schon seit längerem aus der Biochemie bekanntes Konzept zur indirekten Kommunikation zwischen bestimmten Zellen eines Organismus sind Hormone. Dabei lösen diese (körpereigenen) Stoffe an speziellen Zielorganen bestimmte Funktionen aus. Diesen Mechanismus kann man - unter Duldung des erhöhten Kommunikationsaufwandes - nun auch zur Aufgabenallokation an dedizierte Komponenten des verteilten Systems (u.U. sogar in Echtzeit) verwenden.

Dieser Vortrag soll die dazu notwendigen Hormontypen vorstellen und daraus ein dezentralisiertes Hormon-System zur Aufgabenverteilung entwickeln. Neben der Angabe von oberen Schranken für das Echtzeitverhalten, soll auch der Kommunikationsaufwand für ein (konkretes) Hormonsystem abgeschätzt werden.

Ein ebenfalls aus der Biologie (vor allem von Vögeln oder Fischen) bekanntes Muster ist das Schwarmverhalten, bei dem sich trotz weniger, einfacher Regeln eine große Anzahl von Idividuen zu Aggregationen zusammenschließen. Dieses Konzept versucht man nun in verteilten Systemen zu verwenden, um die Anordnung der einzelnen Komoponenten selbstständig (Stichwort: self-deployment) durchführen zu lassen.

In diesem Vortrag soll nach einer Einführung in das Thema die konkrete Umsetzung eines solchen Algorithmuses anhand von mobilen Robotern erläutert und analysiert werden.

Um effektiv mit den Methoden der Selbstorganisation arbeiten zu können benötigen Wissenschaftler entsprechende Werkzeuge. Dafür müssen aber zunächst die Prinzipien der Selbstorganisation als zusammensetzbare Einheiten modellierbar gemacht werden.

Dieser Vortrag soll neben der Abstraktion des Amorphen Mediums auch die Beschreibungssprache Proto vorstellen und deren Einsatz anhand von konkreten Beispielen veranschaulichen.

Da die Implementierung und Beschreibung eines selbstorganisierten Systems (SOS) nicht trivial ist, gilt es noch, eine weitere Beschreibungssprache für solche verteilten und eingebetteten SOS zu untersuchen: SDL (Specification and Description Language).

In diesem Vortrag sollen die Möglichkeiten, Grenzen und Anwendung von SDL für SOS vorgestellt, sowie dessen Einsatz durch konkrete Beispiele veranschaulicht werden.

Was passiert eigentlich, wenn man zwei (oder mehrere dieser) biologisch-inspirierten Algorithmen miteinander kombiniert? Sind die jeweiligen Ansätze doch zu gegenläufig oder funktioniert das Ganze dann immer noch ohne zentrale Kontrolle?

Dieser Vortrag soll die oben genannten Fragestellungen anhand dem Verhalten von Glühwürmchen nachempfundenen Algorithmen analysieren und entsprechend beantworten. Dazu werden u.a. der Flock- und der Gossip-Algorithmus miteinander kombiniert. Die Evaluation dieser Kombination "der anderen Art" runden den Vortrag ab.

Ein oft notwendiger, aber bereits gut untersuchter (Netzwerk)Dienst ist die Zeitsynchronisation. Auch hier gibt es zahlreiche Algorithmen und Ansätze, die ihre Vorbilder in der Natur gefunden haben.

In diesem Vortrag soll ein dem Verhalten von Glühwürmchen nachempfundenes Zeitsynchronisationsprotokoll erläutert werden. Besonderes Augenmerk soll hier auf der Behandlung realistischer Radioeffekte, wie Dämpfung oder Interferenz, liegen. Außerdem soll untersucht werden, inwieweit Störungen durch fehlerhafte Knoten von einem solchen selbstorganisierten Synchronisationsansatz toleriert werden können.

Mit Techniken des Organic Computing kann man bereits viele Teilprobleme beim Einsatz vernetzter eingebetteter Systeme zufriedenstellend lösen, etwa Routing, MAC-Protokoll und Zeitsynchronisation. Aber sogar ein ganzes Betriebssystem läßt sich aufgrund von biologisch-inspirierten Algorithmen und Methoden entwerfen!

In diesem Vortrag soll eine Betriebssystem-Architektur diskutiert werden, die speziell für eingebettete Echtzeit-Systeme entwickelt wurde. Eine tiefgehende Analyse der Betriebssystem-Architektur u.a. bzgl. dessen Echtzeitfähigkeit sind hier ebenfalls verlangt.

Ein ebenfalls biologisch inspiriertes MAC-Protokoll versucht das bei japanischen Baumfröschen beobachtbare Verhalten des sog. desynchronisierten Quakens nachzubilden. Dabei versucht jeder Netzteilnehmer (Frosch) in selbstorganisierter Art und Weise, seine periodischen Nachrichten (Quaken) in einem zeitlich möglichst weiten Abstand vom periodischen Nachrichtenversand seiner direkten Nachbarn zu versenden. Durch eine geschickte Anpassung der individuellen Frequenz (im Nachrichtenversand) kann eine kollisionsfreie Übertragung aller erzeilt werden.

In diesem Vortrag soll zunächst o.g. MAC-Protokoll detailliert vorgestellt werden. Eine weitergehende Analyse möglicher Einsparmöglichkeiten im Energieverbrauch sollen hier ebenfalls untersucht werden.