Qualifikationsarbeiten

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.

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.

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.

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.

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 (frey at uni-koblenz.de), 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.

Ziel dieser Arbeit ist die visuelle Aufbereitung von formalen Beweisen bzw. mathematischer Herleitungen aus den Vorlesungen „Lokale Netzstrukturen“, „Zufällige Kommunikationsnetze“, „Leistungsbewertung von drahtlosen Netzen“ oder „Drahtlose Kommunikation“. Hierbei soll ausschnittsweise ein Vorlesungsinhalt, welcher bisher als Live-Videomitschnitt vorliegt bzw. live in der Vorlesung an Tafel bzw. Touch-Screen entwickelt wird in einzelnen Schritten didaktisch gegliedert in einer graphisch ansprechenden Form als Videomaterial über Panopto oder YouTube ersetzt oder ergänzt werden.
Die Auswahl eines passenden Abschnittes aus einer der genannten Vorlesungen erfolgt in Rücksprache mit Hannes Frey. Voraussetzung ist, dass man die entsprechende Vorlesung gehört und bestanden hat und einem die Vorlesung auch Spaß gemacht hat.

Zur praktischen Umsetzung ist wie oben genannt Manim vorgesehen. Manim ist eine Python Bibliothek, mit derer hochwertige 2D Animationsvideos zu mathematischen Sachverhalten programmiert und gerendert werden können. Die Bibliothek existiert in zwei Varianten, als persönliches Projekt des Autors von 3Blue1Brown, der diese Entwickelt hat und eine daraus abgeleitete Community-Edition. Wir nutzen die Community-Edition. Die Implementation wird in einem Git-Repository archiviert.

Nach Rücksprache kann alternativ z.B. für 3D Animationen zu Sachverhalten aus der Vorlesung „Drahtlose Kommunikation“ ggf. auch Blender eingesetzt werden, sofern man selbst hinreichend Kenntnisse zu Blender mitbringt.

Mit dieser Arbeit soll die besehende Reihe von digitalen Übungen zur Vorlesung Grundlagen der Rechnernetze um eine konkrete weitere Online-Übung ergänzt werden. Hierbei soll in einer virtuellen Umgebung (VirtualBox) ein Netzwerk von Rechnern eingerichtet werden, auf denen konkrete Aufgaben zu IP-Routing und Adressierung an konkreten installierten Routern durchgeführt werden sollen. Die Umgebung soll von Studierenden lokal nutzbar sein. In der Umgebung sollen per geeignetem integriertem User-Interface die Aufgaben durchführbar sein. Das Ergebnis der Aufgaben wird durch automatisierte Tests überprüft, z.B. durch automatisiertes versenden von Testnachrichten, mit denen die korrekte Konfiguration von Routern getestet wird. Des Weiteren ist eine Integration der Online-Übung über die LTI-Schnittstelle umzusetzen, sodass das Ergebnis des Tests über die LTI-Schnittstelle nach OLAT kommuniziert werden kann.

Voraussetzung für diese Arbeit sind Linux-Kenntnisse sowie die Fähigkeit möglichst minimale Linux-Installationen auf den eingerichteten vernetzten Maschinen in der Virtuellen Box einzurichten. Des Weiteren soll die Vorlesung Grundlagen der Rechnernetze schon gehört und abgeschlossen worden sein.

Ausgangspunkt dieser Arbeit ist eine Kette von äquidistanten vernetzten Fahrzeugen, die sich als Kolonne fortbewegen; z.B. eine Folge von autonom fahrenden LKWs. Hierbei sendet zur Koordination der Kolonne das vorausfahrende Fahrzeug periodisch eine Nachricht aus, die von allen nachfolgenden empfangen werden soll. Aufgrund begrenzter Sendereichweite kann das vorausfahrende Fahrzeug nicht alle nachfolgenden Fahrzeuge erreichen, sodass Fahrzeuge, welche die Nachricht von einem Vorgänger empfangen als mögliche Relays agieren und diese Nachricht reübertragen. Die Nachricht kann so über mehrere Weiterleitungsschritte auch das letzte Fahrzeug erreichen.

Bei dem in dieser Arbeit zu untersuchenden Verfahren soll für das Forwarding von Nachrichten keine weitere Kontrollnachricht versendet werden. Ein solches nachrichtensparendes Verfahren lässt sich hierbei aufgrund der Broadcast-Eigenschaft des drahtlosen Mediums wie folgt realisieren.

Das vorausfahrende Fahrzeug bzw. ein Relay-Knoten sendet die Nachricht zunächst ohne bestimmte Zieladresse an alle Fahrzeuge, die in seinem Kommunikationsbereich liegen. Jedes der nachfolgenden Fahrzeuge, welches die Nachricht erhält, setzt einen Timeout zufällig in einem bestimmten Zeitintervall, an dem die Nachricht reübertragen werden soll. Hört ein potentieller Relay jedoch, dass schon ein anderer die Nachricht reübertragen hat, dann verwirft er seinen Timeout wieder.

Die Performance des Verfahrens im Sinne von z.B. der Erfolgsrate alle Fahrzeuge zu erreichen, der Auslieferungsgeschwindigkeit sowie dem Nachrichtenaufwand (d.h. wie viele Reübertragungen fanden statt, bis alle erreicht wurden) hängt davon ab, wie man die Zeitintervalle zum Setzen des zufälligen Timeouts wählt. Hierbei ist es sinnvoll, die Distanz zum vorgehenden Sender bei der Wahl des passenden Zeitintervalls mit zu berücksichtigen.

In dieser Arbeit soll die Wahl von geeigneten Zeitintervallen zum Schedulen solcher Reübertragungs-Timeouts in einer Simulation experimentell untersucht werden. Hierbei soll der Grad der Simulationsabstraktion paketbasierte Nachrichteübertragung, physikalische Eigenschaft des drahtlosen Kanals, sowie auch das Medienzugriffsverfahren mitberücksichtigen, da alle diese Faktoren einen Einfluss auf die Performance und damit insbesondere auch die sinnvoll zu wählenden Zeitintervallgrößen haben. Die Studie wird in einem passsenden Netzwerksimulator wie zum Beispiel Omnet++ implementiert und durchgeführt.

Ausgangspunkt der Arbeit ist eine Reihe an linear angeordneten drahtlosen Netzknoten. Es ist angenommen, dass sich alle Knoten unmittelbar untereinander erreichen können. Für jede empfangene Nachricht gibt es einen Signalstärkewert, der genutzt werden soll, die Reihenfolge der Knoten in der linearen Anordnung zu bestimmen. Hierzu sendet jeder Knoten eine Nachricht an alle übrigen Knoten. Das bedeutet, dass für jedes Knotenpaar ein oder bei wiederholtem Senden mehrere Signalstärkewerte vorliegen. Da Signalstärken nicht deterministisch nur von der Distanz zwischen Knoten abhängen, sondern zufälligen Signalstärkeschwankungen aufgrund der Umgebung unterliegen, ist das Bestimmen der Knotenreihenfolge anhand der ermittelten Werte nicht trivial.

Im Rahmen der Arbeit soll untersucht werden, inwieweit geeignete Verfahren des maschinellen Lernens zum Beispiel vorab durch eine hinreichend große Menge an apriori Daten eingelernt werden können, sodass aus den Momentaufnahmen der vorliegenden Signalstärkewerten die tatsächliche Reihenfolge mit hoher Treffergenauigkeit gefunden werden kann.

Zur genannten Problemstellung sind geeignete Verfahren aus dem Bereich maschinellen Lernens zu recherchieren, exemplarisch anhand von Simulationsdaten einzulernen und zu testen. Hierbei sollen aufwand der Lösungen sowie die Treffergenauigkeit unter anderem Untersucht werden. Voraussetzung für die Arbeit sind Kenntnisse aus dem Bereich des maschinellen Lernens, z.B. hier an der Universität im Rahmen einer Vorlesung gehört.

In dieser Arbeit werden Einfluss und lokale Anpassung von Kommunikationsgraphen auf die Qualität von verteilten Regelungsverfahren für drahtlos vernetzte autonome Roboter-Teams untersucht. Ein Beispiel für ein solches System sind vernetze Unterwasserdrohnen, die kollaborativ den Ursprung einer Leckage entlang einer Pipeline auffinden. Die verteilten Regelungsverfahren sind hierbei vorgegeben und werden nicht weiter untersucht. Aufgabe ist es vielmehr zu untersuchen, inwieweit unzuverlässige drahtlose Kommunikation (Nachrichtenverluste oder verfälschte Nachrichteninhalte) die Güte der verteilten Regelung beeinflusst und durch geeignete Anpassung des Kommunikationsgraphen die Regelungsgüte verbessert werden kann.

Zur Bewertung der Regelungsgüte sind Kostenfunktionen auf Seiten der Regelung vorgegeben, die auf algebraischen Eigenschaften des Kommunikationsgraphen basieren. Algebraische Eigenschaften lassen sich im Wesentlichen aus den Eigenwerten der Adjazenzmatrix des Kommunikationsgraphen ablesen.

Im Rahmen der Arbeit sollen typische Kommunikationsgraphen auf Basis geeigneter Drahtlosmodelle betrachtet und deren Eigenwerte bestimmt sowie daraus Messdaten zur Regelgüte systematisch im Rahmen von Simulationen abgelesen werden. Des Weiteren sollen lokale Heuristiken entwickelt werden, anhand derer man durch Anpassung von Sendeleistung oder durch Streichen von unzuverlässigen Kanten die algebraischen Grapheigenschaften und damit die Regelungsgüte verbessern kann.

Die Regelungsverfahren sind in Matlab vorgegeben. In der gegenwärtigen Implementation wird auf ein Basis-Graphenmodell ohne Topologiekontrolle zugegriffen. Hier wäre im Rahmen der Arbeit eine geeignete Schnittstelle/Basisklasse in die Implementation zu integrieren, sodass der zugrundeliegende Netzwerkgraph durch Topologiekontrolle modifiziert werden kann.

Ausgangspunkt bilden eine Reihe von lokalen Topologiekontrollverfahren, wie diese in der Vorlesung Lokale Netzstrukturen behandelt werden. Des Weiteren sollen lokale Topologiekontrollverfahren speziell unter dem Aspekt der algebraischen Grapheigenschaften zur Performanceverbesserung verteilter Regelung entwickelt werden.

Für diese Arbeit ist es sinnvoll, die Vorlesung Lokale Netzstrukturen gehört zu haben, in der lokale Topologiekontrollverfahren behandelt werden. Auch sind Basiskenntnisse zu einfachen Modellen zur Beschreibung von drahtlosen Kommunikationsgraphen, z.B. gehört in einer der Master-Veranstaltungen der AG UniKoRN, sinnvoll. Kenntnisse in Verteilter Regelung sind nicht erforderlich. Es stehen vier fertige Beispielimplementationen zur Verfügung, die als Testfälle dienen. Eine Matlab-Umgebung wird im Rahmen der Arbeit bereitgestellt. Auf Basis der vorhandenen Implementation ist eine Einarbeitung in die Matlab-Programmierung (objektorientierte, imperative Programmiersprache) recht einfach. Vorkenntnisse in Matlab sind demnach nicht erforderlich. Lediglich das Konzept Objektorientierter Programmierung sollte man z.B. aus einer anderen Programmiersprache kennen.

Drahtlose Kommunikation unterliegt unter anderem Pfadverlust und Abschattung, welche dazu führen, dass die Empfangssignalstärke variabel mit der Distanz abnimmt. Dies ist zum einen bedingt durch die bei wachsender Distanz abnehmende Leistungsdichte pro Flächeneinheit und zum anderen durch Objekte in der Nähe des Übertragungsweges, welche das Signal beinträchtigen können. Mit dem sogenannten Log-Normal Shadowing-Modell sind diese Effekte in einem einfachen mathematisch kompakten Modell beschrieben. In diesem Modell, welches die Leistung bzw. Leistungsabnahme logarithmisch (in dBm und dB) darstellt, ist der Pfadverlust über die Parameter Pfadverlust an einer Referenzdistanz und Pfadverlustkoeffizient festgelegt. Die Variation durch Abschattung ist durch eine normalverteilte Zufallsvariable beschrieben. Die Stärke der Variation durch Abschattung ist durch die Varianz (bzw. Standardabweichung) dieser normalverteilten Zufallsvariablen parametrisiert.

Das genannte Modell ist sinnvoll einsetzbar, wenn man einen Kommunikationskanal mathematisch beschreiben oder in einer Simulation verwenden möchte. Werden mehrere räumlich nahe beieinander liegende Kommunikationskanäle betrachtet, ist die Modellierung beider Kanäle jeweils über zwei unabhängige Shadowing-Kanäle insofern unpräzise, dass beide Kanäle ähnliche räumliche Gegebenheiten und insbesondere abschattende Hindernisse vorfinden, sodass die normalverteilten Zufallsgrößen des einen und des anderen Kanals miteinander korreliert sind.

Zur Beschreibung solcher Korrelation wurde vor einigen Jahren in der Literatur das sogenannte Joint-Path-Loss-Modell eingeführt. Dieses Modell erlaubt es, den Korrelationskoeffizienten zu zwei gegebenen Kanten numerisch zu berechnen. Hierbei hängt das Ergebnis einzig von einem Parameter (der sogenannten Raumkonstante) ab. Ein Nachteil dieses Modells ist jedoch, dass dieses nur sinnvoll einsetzbar ist, wenn die beiden Kanten relativ zur Raumkonstanten eine gewisse Länge haben. Diese Einschränkung lässt sich jedoch durch eine Modifikation des Modells beheben. Die AG hat hierzu eine Modifikation aus dem Original Joint-Path-Loss-Modell hergeleitet.

Offen ist jedoch, in welchem Maße diese Modifikation reale drahtlose Kommunikationskanäle auch besser beschreibt. Hierzu sind Messungen in einem realen drahtlos-Setup erforderlich. In dieser Arbeit sollen solche Messungen implementiert, durchgeführt und statistisch hinsichtlich Korrelation im Log-Normal-Shadowing-Modell ausgewertet werden. Dabei sind aus den gewonnenen Messdaten die Parameter Pfadverlust an der Referenzdistanz, Pfadverlustkoeffizient, sowie Shadowing-Variation für beide Modelle durch Least-Squares-Estimates zu bestimmen. Anschließend sind für beide Korrelationsmodelle jeweils die Raumkonstante zu bestimmen. Mit diesen gewonnen Parametern ist sodann die Beschreibungsgenauigkeit der Modelle zu quantifizieren.

Voraussetzung für diese Arbeit ist Interesse an Mikrocontrollerprogrammierung (hier MSP430 der TMoteSky Plattform). Des Weiteren sollte Interesse an empirischen Versuchsdurchführungen im Feldversuch sowie dessen statistische Auswertung bestehen. Des Weiteren soll die Vorlesung Drahtlose Kommunikation bei der AG gehört worden sein.

Viele lokale Verfahren zur Kommunikation in und zur Strukturierung von drahtlosen Netzen erfordern, dass der zugrunde liegende Netzwerkgraph eine planare Zeichnung ist. Hierbei ist angenommen, dass die Netzknoten im Wesentlichen auf einer zweidimensionalen Ebene liegen. Zur Strukturierung von Netzgraphen als planare Zeichnung kann dabei auf Positionsinformation der Netzknoten zugegriffen werden.

In der Regel finden sich in nicht weiter strukturierten drahtlosen Netzgraphen schneidende Kanten. Solche Schnitte können durch entfernen von Kanten eliminiert werden, jedoch kann damit der Graph in Partitionen auseinanderfallen. Schnittfreiheit durch entfernen von Kanten sowie Graphzusammenhang können in beliebigen Graphen konfliktbehaftete Ziele sein. Somit sind in der Regel Heuristiken gefragt, welche beide Ziele mit einer hohen Erfolgsrate erreichen können.

Eine generelle Vorgehensweise zur Planarisierung ist es, den zugrunde liegenden Netzgraphen zunächst in eine sogenannte Overlay-Graphstruktur zu überführen und die Planarisierung dieser Overlay-Struktur anstatt die Planarisierung des darunter liegenden Graphen zu betrachten. Overlay bedeutet hierbei, dass nach einem geeigneten Verfahren Netzknoten in Gruppen zusammengefasst jeweils einen virtuellen Knoten bilden. Die Kanten zwischen den virtuellen Knoten werden durch den darunter liegenden Graphen definiert. Zwei virtuellen Knoten sind durch eine virtuelle Kante verbunden, wenn mindestens ein Knoten einer Gruppe mit einem Knoten der anderen Gruppe verbunden ist.

Zusammenfassen von Knoten in einer Gruppe kann auf geographischer Knotenposition oder auf graphtopologischer Information basieren. Im ersten Fall dem sogenannten geographischen Clustering ist die Ebene in ein reguläres Raster (Quadrate oder Hexagone) unterteilt. Knoten innerhalb eines Clusters bilden jeweils einen Knoten des Overlay-Graphen. Im zweiten Fall dem sogenannten topolgischen Clustering werden Knoten die maximal k Kommunikationsschritte voneinander entfernt sind, mittels sogenanntem k-Hop-Clustering zu Knoten des virtuellen Overlay-Graphen zusammengefasst.

Der Vorteil der Planarisierung über Ovlerlay-Graphen ist, dass sich die Overlay-Struktur unter Umständen gutmütiger bezüglich Planarisierbarkeit und gleichzeitigem Graphzusammenhang verhalten kann. Dies liegt daran, dass alle Kanten zwischen Knoten aus einer Gruppe zu einem virtuellen Knoten zusammenfallen und damit bezüglich Schnitte keine Relevanz mehr haben. Schnitte können jedoch zwischen den Kanten des Overlay-Graphen entstehen, sodass diese Schnitte auf der Ebene der Overlays behandelt werden müssen. Jedoch sind dies deutlich weniger Kanten und die Schnitte von Kanten folgen hier einer reguläreren Struktur, als es bei Betrachtung der Schnitte des zugrunde liegenden Graphen der Fall wäre. Dies kann zur lokalen Planarisierbarkeit ein Vorteil sein.

Das vorliegende Thema umfasst mehrere Teilthemen. Im Wesentlichen kann beispielsweise in einer Arbeit Planarisierung auf Basis von geographischem Clustering sowie einer anderen Planarisierung auf Basis von geographischen Clustering betrachtet werden. In allen Fällen können bestehende lokale Verfahren im Kontext der Overlay-Graphen simulativ und ggf. auch in Teilen formal untersucht werden, sowie spezielle auf die Overlays angepasste neue Verfahren entwickelt werden. In allen Fällen ist die Voraussetzung für dieses Thema, dass man die Vorlesung "Lokale Netzstrukturen" gehört hat.

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.

Diese Arbeit befasst sich mit der praktischen Realisierung von verteilten Algorithmen auf Miniaturdrohnenschwärmen. Der Einsatz solch verteilter Robotik ist vielfältig in Exploration, Überwachung oder Wartung und umfasst viele Anwendungsbereiche beispielsweise in Medizin, Gebäudetechnik, Logistik, Verkehr, Umweltüberwachung oder Landwirtschaft.

Im Rahmen der Arbeit soll ein verteilter Algorithmus wie das verteilte Aufsuchen einer (simulierten) physischen Messgröße auf Miniaturdrohen umgesetzt werden. Hierbei liegt der Fokus auch auf die Umsetzung eines allgemeineren Softwarerahmens, sodass auf einfache Weise weitere verteile Algorithmen auf der Plattforum untersucht werden können. Des Weiteren soll hier auch Evaluation und Demonstration von Miniaturdrohnenschwärmen mitberücksichtigt werden. Über einen digitalen Zwilling sollen aktuelle Daten zum Drohnenschwarm in Echtzeit parallel auf einem Display nachverfolgbar sein. Hier sollen unter anderem die Position und der aktuelle Zustand des verteilen Algorithmus der jeweiligen Drohnen auf dem Display nachvollziehbar sein.

Die Basis der Arbeit bildet die CrazyFlie-Plattform in der aktuellen Firmwareversion 2.0 (https://www.bitcraze.io/products/crazyflie-2-1). Die Positionierung erfolgt über VIVE-basierte Laserpositionierung (https://www.vive.com/de/accessory/base-station2). Die Hardware steht hierzu im Labor bereit.

In der Arbeit soll ein kleiner Mikroprozessor entworfen werden, der für Lehrzwecke geeignet sein soll. Dies umfasst die Gestaltung einer kleinen RISC-Instruktionssatzarchitektur auf 8-Bit-Basis und deren Codierung, den konzeptuellen Entwurf in einer Digitalschaltungssimulation (https://github.com/hneemann/Digital), Recherche und Zusammenstellung einer Liste kostengünstiger Logik-ICs (z.B. https://www.reichelt.de/logik-ics-c8701.html?&nbc=1) auf Basis der 74er Reihe (u.a. Logik-Gatter, Multiplexer, D-Flip-Flops, 64K-RAM, 64K-ROM) jeweils in Rücksprache mit dem Betreuer.

Des Weiteren ist Teil der Arbeit die exemplarische Realisierung von Teilkomponenten auf Prototypenplatinen für Komponenten wie beispielsweise Clock, Program-Counter und Anzeige der aktuellen Instruktion, die aus einem vorher bespielten ROM schrittweise ausgelesen werden. Die hierzu ausgewählten Logik-ICs werden zur Arbeit zur Verfügung gestellt.

Zur Durchführung des praktischen Teils ist Laboreinrichtung vorhanden. Voraussetzung der Arbeit ist, dass man die Vorlesung „Grundlagen der Rechnerarchitektur“ gehört und bestanden hat und an den Vorlesungsinhalten Prozessoraufbau und Assembler Spaß hatte. Kenntnisse in Elektrotechnik werden nicht vorausgesetzt. Jedoch sollte man Interesse an hardwarenahem Arbeiten haben und bereit sein, sich ein wenig Basiswissen zur Umsetzung des praktischen Teils der Arbeit (Schaltungen auf Prototypen Board, in Datenblätter von einfachen Logik-IC Informationen suchen, Löten, Testen) in Rücksprache mit dem Betreuer anzueignen.