Aktuell verfügbare Bachelor- und Master-Arbeiten

Entwicklung eines verteilten Verfahrens zu RSSI-gestütztem Flocking und Evaluation des Verfahrens mittels Crazyflies

In dieser Arbeit untersuchen wir Schwärme verteile miniatur-Drohnen, welche Indoors autonom als Formation auf Basis von Flocking agieren. Konkret arbeiten wir mit der Crazyflie Plattform der Firma Bitcraze. Zur Organisation des Schwarmes stehen auf dieser Plattform unterschiedliche Sensorwerte zur Verfügung. Dies sind zum einen Abstandsmessungen zu großen Objekten auf der horizontalen Ebene und zur Decke hin. Des Weiteren werden auch Informationen über aktuelle Fluggeschwindigkeit und relative Bewegung anhand von Sensoren in Richtung Boden ermittelt. Eine weitere in dieser Arbeit vorliegenden Messgröße sind Signalstärkewerten (sog. RSSI-Werte) der Kommunikationskanäle zwischen Benachbarten Drohnen. Diese ermöglichen verrauschte relative Messungen zwischen den Drohnen untereinander. Durch Fusion der Sensordaten soll der Schwarm durch einen verteilten lokalen Algorithmus als Formation hinsichtlich des Kommunikationsnetzes zusammenhängend bleiben und zudem das Netz auch hinsichtlich Abdeckung und Qualität des drahtlosen Netzes optimieren. Zur Evaluation steht ein Positionierungssystem zur Verfügung, anhand dessen absolute Positionen mit hoher Genauigkeit ermittelt werden können. Dies dient als Referenz zur Messung der Güte der Verfahren und dient der Visualisierung von Versuchen.

Ansprechpartner Danier Schneider: (


Lokale Strukturierung von drahtlosen Netzen anhand von RSSI-Werten

Unsere aktuellen algorithmischen Arbeiten zur Strukturierung von drahtlosen Netzen basieren auf gegebener Positions- oder Abstandsinformation. Hierbei werden Euklidisch kürzere Kanten gegenüber längeren Kanten bevorzugt, d.h. im wesentlichen langen Kanten gelöscht. Die Verfahren garantieren den Graphzusammenhang und erzeugen planare Zeichnungen, die als Grundbaustein für lokale Kommunikations- und Regelungsverfahren von Interesse sind.

In dieser Arbeit untersuchen wir unsere Algorithmen unter Anwendung von Signalstärkemessungen (sog. RSSI-Messungen), die einen ungefähren Aufschluss über Distanzen gegeben können. Hierbei ist eine genaue Bestimmung von Abstand gar nicht erforderlich. Hingegen dient die Signalstärke unmittelbar als Kostenfunktion, um Kanten des Graphen gegenüber anderen Kanten zu priorisieren. Die Verwendung von sogenannten RSSI-Messungen zur unmittelbaren lokalen Strukturierung von drahtlosen Netzgraphen ergibt folgende Fragen die in mehreren Arbeiten untersucht werden sollen.

Es sollen lokale Verfahren (Algorithmus und Protokoll) entwickelt werden, bei denen Nachrichten zum Austausch von Nachbarinformation in der Größe konstant bleiben. Hierbei ist bei Austausch über die aktuellen Nachbarn eine Einschränkung auf die besten 5 bis 6 Nachbarn eine mögliche vielversprechende Herangehensweise.

Es soll untersucht werden inwieweit die Tatsache, dass RSSI-Messungen lediglich eine sehr grobe Abschätzung von Distanzen ermöglichen, die Algorithmen nach wie vor mit hoher Wahrscheinlichkeit Graphzusammenhang erhalten und beispielsweise Grapheigenschaften wie Planarität erzeugen. Hierbei steht auch die Frage im Vordergrund inwieweit besonders lange Kanten (d.h. Kannten mit sehr schlechtem Signalstärkewert) vorab entfernt werden können.

Die Strukturierung von Graphen anhand von Signalstärkemessungen ist ein vielversprechender Ansatz zur Festlegung bzw. dynamischen Anpassung des sogenannten Alpha-Lattice im Flocking (vgl. Schwarmverhalten). Ein solches Alpha-Lattice legt fest, anhand welcher unmittelbaren Nachbarn die eigene Entscheidung über Bewegungsrichtung gefällt werden soll. Untersucht werden soll unter anderem der Vorteil von Strukturierung anhand von RSSI-Werten gegenüber Schwarmverfahren auf Basis eines unstrukturierten Netzes bei denen alle und somit auch sehr entfernten Nachbarn mit in die Flocking-Entscheidung mit einfließen.

Kontaktperson: Steffen Böhmer ()


Simulative Untersuchung von Planarisierungsalgorithmen in Kommunikationsgraphen mit Redundanz- und Koexistenzeigenschaft

Die Konstruktion von schnittfreien Teilgraphen ist von besonderem Interesse für lokale Datenkommunikation in drahtlosen vernetzten Systemen. Ein Verfahren ist hierbei lokal, wenn das globale Ziel anhand von lokalen Entscheidungen über die aktuell erreichbaren Nachbarn gefällt wird.

Unter der vereinfachten Graphstrukturannahme der sog. Unit-Disk-Graphen existieren einige lokale Verfahren zur Konstruktion von schnittfreien Teilgraphen. Die Unit-Disk Eigenschaft besagt, dass zwei Knoten miteinander verbunden sind, genau dann, wenn ihr Euklidischer Abstand kleiner gleich einem bestimmten festen Wert entspricht. Dies ist eine sehr starke Bedingung, die in drahtlos vernetzten Systemen nur unter starker Einschränkung des Sendebereichs eines Knotens erreichbar ist. Hier besteht jedoch die Gefahr, dass der Netzgraph nicht mehr zusammenhängend ist.

Mit der Redundanz- und Koexistenz-Eigenschaft wurden zwei Eigenschaften untersucht, die schwächer sind als die Unit-Disk-Eigenschaft, aber immer noch die Existenz von lokalen Algorithmen zur Konstruktion schnittfreien Teilgraphen garantieren. Die Redundanz Eigenschaft ist dabei erfüllt, wenn für zwei schneidende Kanten, immer mindestens einer der Endknoten einer schneiden Kanten mit beiden Endknoten der anderen schneidenden Kante verbunden ist. Die Koexistenz Eigenschaft ist dabei erfüllt, wenn ein Knoten innerhalb eines Dreiecks mit den drei Knoten des Dreiecks verbunden ist.

Theoretische Untersuchungen haben gezeigt, dass es generell nicht möglich ist, diese Eigenschaften noch signifikant abzuschwächen, da ansonsten Graphen existieren, für die keine Korrektheit der Algorithmen mehr möglich ist. Diese Gegenbeispiele existieren in realistischen Drahtlos-Netzwerken, sind jedoch nicht sehr wahrscheinlich, da hierfür einige kurze Kanten nicht existieren dürften, während längere Kanten existieren müssen.

Es soll mithilfe von Simulation untersucht werden, inwiefern die beiden Eigenschaften Redundanz und Koexistenz direkt verwendet oder sogar abgeschwächt werden können und dabei die Korrektheit der Algorithmen weiterhin mit einer hohen Wahrscheinlichkeit garantiert ist. Mithilfe theoretischer Analysen und weiteren Simulationen kann untersucht werden, durch welche alternativen bzw. abgewandelten Eigenschaften eine Korrektheit der Algorithmen noch gewährleistet ist.

Ansprechpartner: Lucas Böltz ()


Visualisierung von werkzeugbasierten ermittelten Graphgegenbeispielen im Kontext lokaler Verfahren in Drahtlosnetzmodellen

In einer gemeinsamen Arbeit mit der AG Formale Methoden und Theoretische Informatik erarbeiten wir aktuell Werkzeuge, um Eigenschaften von Graphen, die aus verteilten Netzwerkalgorithmen in drahtlosen Netzen resultieren, formal nachweisen zu können. Hierbei werden Enthaltenseinsrelationen zwischen logisch beschriebenen Graphklassen untersucht. Im Falle von nicht erfüllter Grapheigenschaft, ermitteln die eingesetzten Werkzeuge (hier konkret Werkzeuge, welche aus H-Pilot aufgerufen werden) entsprechende textuell codierte Gegenbeispiele. Im Rahmen dieser Arbeit sollten als Erweiterung der entwickelten Tool-Kette Methoden zur Visualisierung von Graphgegenbeispielen realisiert werden. Hierbei sind die Gegenbeispiele entweder als euklidische Graphen oder lediglich als topologische Graphinformation gegeben. Im letzteren Fall ist entsprechend auf eine geeignete Bibliothek der Graphvisualisierung zurückzugreifen.

Im Rahmen der Arbeit ist die Visualisierung in die Tool-Kette zu implementieren bzw. textuelle Ausgaben der verwendeten Werkzeuge zu parsen und in eine Visualisierung zu übersetzen. Die Darstellung wäre auf einem Web-Frontend, über welches auch die übrigen Verifikationswerkzeuge erreichbar sein werden.

Kontaktperson: Lucas Böltz ()


Simulation von Planarisierungsalgorithmen auf Graphen mit azyklischer Redundanz

Bei der Erarbeitung lokaler Routing-Strategien in drahtlosen Ad-Hoc-Netzwerken ist eine gängige Voraussetzung, dass der zugrunde liegende Kommunikationsgraph plan, d.h. schnittfrei ist. Viele Planarisierungs-Strategien basieren auf der Annahme, dass diesem Graph ein Unit-Disk-Graph zugrunde liegt. In der Praxis ist diese Annahme aber in der Regel nicht gegeben. Daher sind andere Planarisierungs-Methoden und Graph-Eigenschaften, die deren Korrektheit garantieren zu entwickeln.

Eine solche Eigenschaft stellt die azyklische (k-Hop-)Redundanz dar. Dabei muss es für mindestens eine Schnittkante eines jeden Schnittes eine Umgehung aus (höchstens k) kürzeren Kanten geben. Eine zugehörige Planarisierungs-Strategie ist unter dieser Voraussetzung trivial: Wann immer eine solche Umgehung gefunden wird, kann eine Kante entfernt werden.

Die Frage die sich hierbei stellt ist, in welchem Umfang diese Eigenschaft in der Praxis erfüllt ist. Reduziert auf einen Schnitt (k=2) wurde dies bereits theoretisch und numerisch untersucht. Offen ist jedoch:
- Wie häufig ist dies im Gesamtgraphen der Fall?
- Wie verhält es sich bei k>2?
- Kann die zugrunde liegende Eigenschaft abgewandelt werden?
- Wie häufig gelingt die Planarisierung, wenn man azyklische Redundanz nicht voraussetzt?

Die Fragen können in der Arbeit analytisch, numerisch, simulativ und experimentell untersucht werden.

Ansprechpartner: Steffen Böhmer ()


Digitalisierung und Gamification in der universitären Lehre zu Themen der Rechnernetze und Rechnerarchitektur 

Es sind mehrere Arbeiten zum Thema Digitalisierung und Gamification in der universitären Lehre geplant. Im Rahmen der Arbeiten soll je ein ausgewähltes in sich abgeschlossenes Thema aus den Bachelor-Vorlesungen der AG UniKoRN „Grundlagen der Rechnerarchitektur“ (GdRA) oder „Grundlagen der Rechnernetze“ (GdRN) als interaktive Lerneinheit umgesetzt werden. Wahl des passenden Abschnittes sowie sammeln von Ideen zur kreativen Umsetzung erfolgt am Anfang der Arbeit in enger Zusammenarbeit mit Herrn Frey.

Inhaltlich ist auf Basis von Lernzielen zunächst ein Skript zur digitalen Umsetzung zu erstellen. Hierbei werden Film, Audio, Animation und interaktive Elemente zu einer in sich abgeschlossenen Einheit zusammengebracht (beispielsweise mit Stilelementen wie Quests, Adventure-Game, Story-Telling, Highscores, Programming-Challenges etc.).

Technisch ist die erforderliche Voraussetzung an Equipment und Software zur Umsetzung des Projektes zu planen. Diese steht teilweise zur Verfügung und kann im Rahmen von Projektgeldern beschafft werden. Zur Planung gehört auch die Recherche aktuell verfügbarer professioneller digitaler universitärer Lerneinheiten anderer Einrichtungen (also alles was über einfache Vorlesungsmitschnitte und Screen-Casts hinaus geht).

Das Ziel der Umsetzung ist der langfristige Einsatz der Lerneinheiten ohne erforderlichen semesterweisen technischen Wartungsbedarf von Seiten der AG UniKoRN. Das digitale Material soll auf hohem technischem Niveau ansprechen. Es sind entsprechende Umsetzungsmöglichkeiten über die verfügbaren Ressourcen zur digitalen Lehre der Universität Koblenz als auch über verfügbare außeruniversitäre Ressourcen zu eruieren. Zudem ist bei der Umsetzung die Lerneinheit als Teil einer gesamten digital umgesetzten Vorlesung zu betrachten. Langfristig sollen die Lerneinheiten technisch wie auch inhaltlich modular zu einer gesamten digitalen „Vorlesung 2.0“ zusammenfügbar sein.

Als Voraussetzung muss die Vorlesung zu der das Digitalisierungsprojekt umgesetzt werden soll (also GdRA oder GdRN) gehört und mit Erfolg und guter Note abgeschlossen worden sein. Als Voraussetzung sollte man Spaß an und Fähigkeiten in der kreativen und technischen Umsetzung von Multimedia-Inhalten mitbringen. Vorkennnisse zum Umgang mit entsprechender Software bzw. Ausrüstung, sowie Ressourcen wie Film, Musik, Animation sind von Vorteil aber kein Muss.

Interessenten melden sich direkt bei Herrn Frey (), um gemeinsam eine mögliche umzusetzende Lerneinheit zu besprechen. Es können gerne Themen und Umsetzungsideen vorgeschlagen werden. Keine eigene Idee aber großes Interesse kreativ zu werden? Auch gerne melden.