Deutsch Intern
    Computer Engineering (1993-2023)

    Seminar: Eingebettete Systeme (SS2010)

    Ü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.

    Organisatorisches

    Das Seminar findet immer freitags um 13:30 Uhr in SE III statt. Als Vortragsthemen stehen dabei die nachfolgend aufgeführten Themen 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 einem der Betreuer) oder auch erst nach der Einführungsveranstaltung am 23.04.2010 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 zu halten. 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 stehen die Betreuer gerne zur Verfügung!

    Themen- und Terminübersicht

    Einführungsveranstaltung

    Termin: 23.04.2010
    Vortragende: C. Mühlberger, Ch. Appold, J. Bregenzer
    In dieser Einführungsveranstaltung werden einige, für das Seminar wesentliche Begriffe (z.B. Eingebettetes System, Systemverifikation, Model Checking, Virtualisierung, Sensornetzwerk, rhythmisch gekoppelte Oszillatoren, Desynchronisation, ...) erläutert, sowie die bereitgestellten Themen vorgestellt. Eine Themenreservierung ist ebenso möglich, wie die Erörterung des organisatorischen Ablaufs.

    Hardware-Unterstützung für Systemvirtualisierung 

    Betreuer: J. Bregenzer
    Termin: 09.07.2010 
    Um eingebettete Systeme kostengünstiger auf einem großen Rechner simulieren und testen zu können, bietet sich u.a. die Systemvirtualisierung an. Da aber der klassischen x86-Architektur die Voraussetzungen für eine effiziente Systemvirtualisierung fehlen, stellten Intel und AMD im Jahr 2005 mit Intel VT und AMD-V spezielle Hardware-Erweiterungen zur Virtualisierungs-Unterstützung vor.
    Nach einer kurzen Einführung in die Systemvirtualisierung soll dieser Vortrag einen Überblick über den Funktionsumfang dieser beiden o.g. Lösungen geben und dabei herausstellen, inwiefern diese Lösungen im Gegensatz zur klassischen x86-Architektur die formalen Voraussetzungen der Systemvirtualisierung erfüllen.

    Symmetrieausnutzung bei der Verifikation

    Betreuer: Ch. Appold
    Termin: 04.06.2010
    Eingebettete Systeme müssen im Produktiveinsatz möglichst langlebig und fehlerfrei funktionieren. Um dies nach Abschluß der Entwicklungsphase auch mehr oder minder garantieren zu können, versucht man solche Systeme (in Teilen) formal zu verifizieren. Durch die Ausnutzung von Symmetrien kann bei solchen zu verifizierenden Implementierungen - falls überhaupt Symmetrien vorhanden sind - der zu untersuchende Zustandsraum verkleinert werden. Symmetrien treten zum Beispiel häufig auf, wenn ein Programm aus mehreren gleichen Threads besteht. Ist dies der Fall, so können für die Verifikationsaufgabe symmetrische Zustände zusammengefasst werden, wodurch der zu untersuchende und abzuspeichernde Zustandsraum verkleinert wird.
    Dieser Vortrag soll die Grundlagen der Symmetrieausnutzung beim Model Checking vermitteln. Außerdem soll auf Probleme bei der Symmetriereduktion und konkrete Verfahren eingegangen werden.

    Vorstellung des Model Checkers Java Pathfinder 

    Betreuer: Ch. Appold
    Termin: 11.06.2010

    Die Programmiersprache Java ist nicht nur auf Desktoprechnern oder Servern sehr beliebt, sie ist mittlerweile auch in einigen Eingebetteten Systemen zu finden. Will man ein derartiges System verifizieren, so bietet sich Java Pathfinder als expliziter Software Model Checker für Java Bytecode an. Er ist speziell dafür konzipiert schwierig zu findende Fehler in Programmen mit mehreren Threads zu finden. Um die Verifikation von umfangreicheren Programmen zu ermöglichen, wurden im Tool eine Reihe von Heuristiken und Abstraktionsmethoden implementiert. Mit Java Pathfinder können Deadlocks und Exceptions (z.B. NullPointerException und AssertionError) erkannt werden. Außerdem kann der Nutzer selbst Eigenschaften angeben.
    In diesem Vortrag sollen die Konzepte von Java Pathfinder vorgestellt werden. Außerdem soll das Tool an einer Beispielverifikation eines Java Programms vorgestellt werden. Beim Vortrag soll auch auf die Anwendbarkeit von Java Pathfinder auf Programme reeler Grösse und Beschaffenheit eingegangen werden.

    Pulsgekoppelte Oszillatoren und Desynchronisation

    Betreuer: C. Mühlberger
    Termin: 23.07.2010 

    Sollen mehrere verteilte Eingebettete Systeme (z.B. in Form eines drahtlosen Sensornetzwerks) kooperativ eine gemeinsame Aufgabe erledigen, so müssen die einzelnen Elemente nicht nur miteinander interagieren, sondern sich auch synchronisieren können. In der Natur lassen sich zahlreiche Beispiele für Synchronizität verteilter Komponenten finden, z.B. der Sinusknoten im Herz, das rhythmische Flackern tropischer Leuchtkäfer oder das einstimmige Zirpen von Grillen. Ein vereinfachtes mathematisches Modell der synchronisierten,  biologischen Komponenten stellen so genannte pulsgekoppelter Oszillatoren dar.
    Einen anderen Aspekt verfolgt hingegen die Desynchronisation, bei der es nicht darum geht, dass alle Systemelemente synchron, zu einem bestimmten Zeitpunkt agieren, sondern im Gegenteil, dass ihre einzelnen Aktionen (zeitlich) möglichst weit voneinander stattfinden.
    In diesem Vortrag sollen die formalen und begrifflichen Grundlagen für andere Seminarthemen definiert werden. Daher soll zunächst das mathematische Konzept pulsgekoppelter Oszillatoren vorgestellt sowie die Probleme bei deren Analyse erörtern werden. Außerdem soll das Konzept der Desynchronisation in diesem Zusammenhang erläutert werden.

    Multi-Hop Desynchronisation mit M-DESYNC

    Betreuer: C. Mühlberger
    Termin:

    Damit sich mehrere, verteilte Eingebettete Systeme in einem Netzwerk mittels drahtloser Kommunikation (z.B. als Sensor- oder Ad-hoc-Netzwerk) nicht zu stark interferieren, bedarf es einem gemeinsamen Protokoll zur medienzugriffs-Steuerung (engl. medium access control, kurz: MAC). Soll das MAC Protokoll robust, skalierbar und adaptiv sein, so bieten sich selbst-organisierte Ansätze an. Ein derartiger, desynchronisierter und für Multi-Hop Topologien entworfener Vertreter ist das sog. M-DESYNC Protokoll, das nach einer Explorationsphase nur mittels ortsgebundener Information den Zugriff auf das geteilte Übertragungsmedium regelt.
    In diesem Vortrag soll das MAC Protokoll M-DESYNC analysiert werden. Etwaige Grundlagen, die durch vorhergehende Seminarthemen nicht abgedeckt wurden, müssen hier ebenfalls erklärt werden.

    "Sei kein Frosch" - oder lieber doch?

    Betreuer: C. Mühlberger
    Termin:

    Bei den bisher betrachteten Desynchronisationsverfahren haben die Teilnehmer des Netzwerks immer nur ihre Phase angepasst. Nun kann ein Teilnehmer auber auch seine Frequenz den lokalen Gegebenheiten entsprechend verändern. Diese Desynchronisationsmethode kommt in der Natur beim Quakverhalten japanischer Baumfrösche vor und bietet neben einem selbst-organisierten Mediumszugriff auch noch die Möglichkeit, durch eingestreute Schlafzyklen Energie zu sparen.
    In diesem Vortrag soll daher ein selbst-organisiertes MAC Protokoll analysiert werden, das dem Quakverhalten japanischer Baumfrösche nachempfunden ist.

    Desynchronisation - was ist theoretisch machbar? 

    Betreuer: C. Mühlberger
    Termin:

    Für Eingebettete Systeme existieren also zahlreiche Protokolle, die den kollisionsfreien Zugriff auf das geteilte Kommunikationsmedium kontrollieren. Einen fehlertoleranten Ansatz liefert die Desynchronisation. Aber wie "gut" ist sie? Welche Grenzen sind ihr gesetzt? Kann man durch das Einstreuen von Zufallskomponenten an geeigneten Stellen Verbesserungen erzielen?
    Dieser Vortrag soll anhand mathematischer und theoretischer Überlegungen obige Fragen beantworten und zeigen, wie weit sich bei Desynchronisation Fehler minimieren lassen, wie lange es bis zum Erreichen eines konvergenten Zustands dauern kann, und welche Auswirkungen eingestreuter "Zufall" hierbei hat.

    Gezielter Datenversand dank Routing

    Betreuer: C. Mühlberger
    Termin:

    Können verteilte Eingebettete Systeme miteinander kommunizieren, dann ist aber noch lange nicht sichergestellt, dass Daten, die für einen bestimmten Netzteilnehmer gedacht sind, diesen auch erreichen. Für genau dieses Problem gibt es Routingverfahren, die auf verschiedene Weise versuchen, Daten von A nach B zu schaffen. Je nach Untersuchungsgegenstand (Energieverbrauch, Packetlatenz, max. Hop-Count, etc.) gibt es verschiedene Ansätze, die die an diese Protokolle gerichteten Erwartungen mehr oder weniger gut erfüllen. 
    Da bereits bei einigen MAC Protokollen lokale Informationen über die Ein-Hop- bzw. sogar Zwei-Hop-Nachbarschaft gesammelt werden, sollen in diesem Vortrag Routingprotokolle vorgestellt werden, die von diesen bereits vorhandenen Informationen massiv Gebrauch machen. Der Vortragende soll sich daher zunächst einen Einblick in die Funktionsweise verschiedener Routingmechanismen verschaffen und anschließend einen Einblick in bestehende Routingverfahren mit lokaler Nachbarschaftsinformation erarbeiten.

    LMAC und CrankShaft

    Betreuer: C. Mühlberger
    Termin:

    Neben den auf Desynchronisation basierenden MAC Protokollen gibt es natürlich noch eine Vielzahl weiterer Protokolle. Je nach Anwendungsszenario oder Systemanforderungen sind die verschiedenen MAC Protokolle unterschiedlich gut geeignet... 
    In diesem Vortrag sollen daher nochmal zwei weitere MAC Protokolle vorgestellt und analysiert werden: L-MAC und CrankShaft. Von besonderem Interesse sind hier deren unterschiedlichen Stärken und Fähigkeiten. So soll der Vortrag auch eine Gegenüberstellung beider Protokolle enthalten.

    Emergentes Verhalten in Sensornetzen

    Betreuer: C. Mühlberger
    Termin: 16.07.2010 

    Gerade bei komplexen, eingebetteten Systemen kann man aufgrund der zahlreichen Nebenläufigkeiten manchmal nicht mehr aus dem Verhalten der einzelnen Systemkomponenten auf das Verhalten des Gesamtsystems schließen. Dieses sog. emergente Verhalten ("Das Ganze ist mehr als die Summe seiner Teile") kann man in der Natur an zahlreichen Stellen beobachten. Um sich aber als Vorgehensmodell im Bereich eingebetteter Systeme (und Sensornetze im Speziellen) zu etablieren, bedarf es formal definierter Vorgehensweisen und Entwicklungstechniken. 
    Dieser Vortrag soll daher zunächst durch eine Begriffsdefinition die Abgrenzung zur Selbstorganisation schaffen und dann bereits existierende Verfahren zum Modellieren emergenten Verhaltens in Sensornetzen vorstellen.