Intern
    Technische Informatik (1993-2023)

    Seminar: Eingebettete Systeme (SS2011)

    Übersicht

    Ein eingebettetes System (engl. embedded system) ist ein informationsverarbeitendes System, das aus Hard- und Software besteht und in einen technischen Kontext eingebunden (eingebettet) ist.  Diese komplexen Systeme haben aufgrund ihrer hohen Integrationsdichte mittlerweile - und für den Benutzer weitestgehend unsichtbar - in zahlreiche Produkte des täglichen Bedarfs Einzug gehalten, etwa in Haushaltsgeräte, Automobile oder Unterhaltungselektronik. Ihr primärer Zweck liegt dabei aber meist nicht in der Verarbeitung und Aufbereitung von Information, sondern vielmehr sind diese "Kleinrechner" zuständig für die Steuerung, Regelung oder Überwachung des Systems, in dem sie eingebettet sind, oder sie sorgen für die Filterung und (De)Codierung von Daten bzw. Signalen.

    Aufgrund ihres zahlreichen Einsatzes und ihrer immer wichtiger werdenden Vernetzung (sowohl untereinander als auch mit ihrer Umgebung), kann die Entwicklung, Überwachung, Kontrolle und Anpassungsfähigkeit eingebetteter Systeme nicht nur sehr komplex, sondern mit bisherigen (analytischen) Methoden und Algorithmen sogar unmöglich werden. Daher versucht man aus der Natur bekannte Techniken und Verhaltensmuster von z.B. Staatenbildenden Insekten oder Vogelschwärmen unter den Begriffen Selbstorganisation und Organic Computing so zu adaptieren, dass die Probleme dieser vernetzten eingebetteten Systeme selbst mit einer großen Anzahl von Teilnehmern handhab- und lösbar werden. Zu den erhofften Fähigkeiten dieser naturnahen bzw. naturanalogen Verfahren gehören u.a. Skalierbarkeit, Adaptation, Fehlertoleranz und Robustheit.

    Organisatorisches

    Das Seminar findet immer freitags um 13:30 Uhr in SE III statt. Als Vortragsthemen stehen dabei die nachfolgend aufgeführten Themen ab sofort zur Verfügung. Wer Interesse an der Bearbeitung eines der angegebenen Themen hat, kann sich dieses bereits im Vorfeld (per Email oder persönlich bei Clemens Mühlberger) oder auch erst in der Einführungsveranstaltung am 06.05.2011 reservieren lassen.

    Zu jedem Thema soll in Einzelarbeit ein etwa 30- bis 45-minütiger Vortrag sowie eine schriftliche Ausarbeitung im Umfang von ca. 10 Seiten im LCNS-Format erstellt werden. Der Vortrag soll dann zu einem noch festzulegenden Termin vor den Teilnehmern des Seminars präsentiert werden. Bei den Vorträgen gilt i.Ü. Anwesenheitspflicht für alle Teilnehmer. Zudem ist spätestens eine Woche vor dem jeweiligen Präsentationstermin ein Probevortrag vor dem Betreuer verpflichtend. Der entsprechende Betreuer steht bei Fragen, die während der Einarbeitung und Vortragserstellung auftauchen, gerne zur Verfügung! Die Vorträge und Vorlagen zur Ausarbeitung stehen für die Seminarteilnehmer auf der WueCampus-Seite des Seminars bereit. Der dafür notwendige Zugangsschlüssel wird in der Einführungsveranstaltung bekannt gegeben.

    Um die Einarbeitung in die jeweiligen Vortragsthemen zu erleichtern, werden zusätzlich für jedes Thema Literaturvorschläge zur Verfügung gestellt. Allerdings müssen die Seminarteilnehmer auch eine eigene Literaturrecherche anstrengen! Neben der Uni-Bibliothek können dabei folgende Zitatsammlungen hilfreich sein:

    Die erfolgreiche Teilnahme (d.h. kontinuierliche Anwesenheit, Probevortrag, Vortrag und Ausarbeitung) wird durch einen Leistungsschein belohnt. Für weitere Auskünfte steht der jeweilige Betreuer gerne zur Verfügung!

    Themen- und Terminübersicht

    Einführungsveranstaltung

    Termin: 06.05.2011
    Vortragender: Clemens Mühlberger

    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.

    Begriffsklärung 

    Betreuer: C. Mühlberger
    Termin: 20.05.2011 

    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.

    Netzwerk und Selbstorganisation 

    Betreuer: C. Mühlberger
    Termin: 15.07.2011

    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.

    Ad-hoc Routing und Selbstorganisation 

    Betreuer: C. Mühlberger
    Termin: 01.07.2011

    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.

    Koordination und Kommunikation

    Betreuer: C. Mühlberger
    Termin: 10.06.2011  

    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.

    Kollaboration und Aufgabenverteilung

    Betreuer: C. Mühlberger
    Termin: 10.06.2011  

    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. 

    Selbstheilung und Selbstadaption

    Betreuer: C. Mühlberger
    Termin: 01.07.2011  

    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.

    Künstliche Hormone

    Betreuer: C. Mühlberger
    Termin: 03.06.2011  

    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.

    Partikelschwärme und Selbstanordnung

    Betreuer: C. Mühlberger
    Termin: 03.06.2011  

    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.

    Wie beschreibe ich "Emergenz"? 

    Betreuer: C. Mühlberger
    Termin: 24.06.2011  

    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.

    SOS mit SDL

    Betreuer: C. Mühlberger
    Termin: 24.06.2011  

    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.

    Schwätzen und Strömen 

    Betreuer: C. Mühlberger
    Termin: 22.07.2011  

    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.

    Zeitsynchronisation

    Betreuer: C. Mühlberger
    Termin: 22.07.2011  

    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.

    Organisches Betriebssystem

    Betreuer: C. Mühlberger
    Termin: 17.06.2011 

    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.

    Quakende Frösche

    Betreuer: C. Mühlberger
    Termin: 15.07.2011  

    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.