Qualifikationsarbeiten

Display-Controller wie der SSD1309 beherrschen Hardware-Scrolling, Teil-Updates und Parameter, die sich zur Laufzeit ändern lassen. Gängige Bibliotheken nutzen davon kaum etwas: Sie behandeln den Controller als reinen Framebuffer und übertragen bei jeder Änderung das komplette Bild. Wer die Sonderfunktionen trotzdem nutzen will, schreibt fehleranfällige Hex-Sequenzen von Hand.

In dieser Arbeit betrachtest du den Kommandosatz des Controllers als eigene ISA und entwickelst dafür eine domänenspezifische Assembler-Sprache, mit der sich der volle Funktionsumfang lesbar und sicher ansprechen lässt. Ein Assembler in Python prüft die Programme statisch gegen die Vorgaben des Datenblatts und erzeugt Code für STM32-Mikrocontroller.

Aufgaben

• Entwurf der Sprache: Mnemonics, Grammatik, parametrisierte Makros
• Assembler mit statischer Prüfung (Wertebereiche, Konsistenz, Zustands-Constraints)
• Evaluation auf dem Nucleo-F411RE: Busverkehr, CPU-Zeit und Framerate im Vergleich zu einer Standardbibliothek sowie Fehlererkennung per Fault Injection

Umfang

Das Thema ist als Bachelor- oder Masterarbeit möglich. Im Master kommt ein zweiter Controller hinzu, den eine maschinenlesbare ISA-Beschreibung abdeckt.

Voraussetzungen

Erfolgreiche Teilnahme an der Vorlesung „Eingebettete Systeme“, sowie Python- und Grundkenntnisse in C. Alternativ sind die Voraussetzungen für diese Arbeit auch gegeben, wenn man anderweitig erworbene Kenntnisse zu hardwarenahem Programmieren auf Mikrocontrollern, Werkzeuggestütztes Messen von Performance und Kenntnisse zum Umgang mit Datenblättern nachweisen kann.

Kleine Monochrom-Displays mit Controllern wie dem SSD1309 sind in eingebetteten Systemen weit verbreitet. Verbreitete Treiber-Libraries sind aber meist auf Einfachheit ausgelegt, nicht auf Effizienz. Alle Grafikoperationen laufen über eine einzelne Pixelfunktion, obwohl der Speicher des Controllers in Pages organisiert ist (ein Byte = 8 vertikale Pixel). Fonts werden zur Laufzeit transponiert, und der Framebuffer wird blockierend und ohne DMA übertragen. Wie viel CPU-Zeit, Busverkehr und Energie bessere Strategien in dieser Domäne tatsächlich sparen, ist kaum systematisch untersucht.

In dieser Arbeit entwickelst du eine effiziente Grafik-Library für den SSD1309 und vergleichst sie messtechnisch mit verbreiteten Libraries.

Aufgaben

• Analyse bestehender Libraries: z. B. stm32-ssd1306 und u8g2
• Byte-orientierte Algorithmen: Linien, Rechtecke, Kreise, Fonts und Sprites mit Maskierung, direkt im Page-Format des Controllers; Fonts und Sprites werden beim Build per Konverter-Tool ins Page-Format umgewandelt
• Optimierte Übertragung: DMA, Double Buffering, Dirty Regions, zusammengefasste Transaktionen
• Evaluation auf dem Nucleo-F411RE: fester Benchmark-Satz an Operationen; gemessen werden CPU-Zyklen (DWT), Busverkehr (Logic Analyzer) und Energiebedarf

Umfang

Das Thema ist als Bachelor- oder Masterarbeit möglich. Im Master kommen die Verallgemeinerung auf weitere page-orientierte Controller (z. B. SSD1306, SH1106, ST7565) und eine systematische Untersuchung des Entwurfsraums hinzu.

Voraussetzungen

Erfolgreiche Teilnahme an „Eingebettete Systeme“, sichere C-Kenntnisse, Freude an hardwarenaher Optimierung und präzisem Messen. Alternativ sind die Voraussetzungen für diese Arbeit auch gegeben, wenn man anderweitig erworbene Kenntnisse zu hardwarenahem Programmieren auf Mikrocontrollern, Werkzeuggestütztes Messen von Performance und Kenntnisse zum Umgang mit Datenblättern nachweisen kann.

CubeMX legt den Clock Tree eines STM32 zur Designzeit fest. Wer zur Laufzeit Frequenz und Spannungsbereich wechseln will, um Energie zu sparen, muss PLL-Parameter neu berechnen und strikte Reihenfolgen einhalten (Spannungsbereich, Flash-Wait-States, PLL-Neustart). Außerdem müssen alle taktabhängigen Peripherien angepasst werden, von der UART-Baudrate über Timer bis zur Zeitbasis des Systems. Für die Peripherie gibt es zwei bekannte Strategien: Bei Veto blockieren aktive Peripherien den Wechsel (so macht es ESP-IDF). Bei Notify werden die Peripherien benachrichtigt und passen ihre Teiler an (so macht es das Linux-Clock-Framework). Für STM32 gibt es bisher keine verbreitete Lösung. Offen ist außerdem, wann sich Heruntertakten auf einer MCU gegenüber „schnell rechnen und schlafen“ (Race-to-Idle) überhaupt lohnt.

In dieser Arbeit entwickelst du ein leichtgewichtiges C-Framework für solche Umschaltungen, setzt beide Strategien für die Peripherie um und vergleichst sie experimentell.

Aufgaben

• Modellierung des Clock Trees und Berechnung der PLL- und Prescaler-Werte zur Laufzeit
• Sichere Umschaltsequenz als Zustandsautomat gemäß Reference Manual, mit einer Zeitbasis, die den Wechsel übersteht
• Veto- und Notify-Strategie für taktabhängige Peripherie (UART, SPI, Timer)
• Evaluation auf dem Nucleo-F411RE:
  - Umschaltlatenz und Störungen während des Wechsels (z. B. verlorene UART-Bytes)
  - Stromaufnahme
  - Vergleich mit Race-to-Idle

Umfang

Das Thema ist als Bachelor- oder Masterarbeit möglich. Im Master kommen hinzu:

• eine zweite STM32-Familie (z. B. L4 oder U5) über eine tabellengesteuerte Beschreibung des Clock Trees
• die formale Prüfung der Umschaltsequenz (z. B. Model Checking)
• optional die Integration als P-State-Treiber in das CPU-Frequency-Scaling-Subsystem von Zephyr

Voraussetzungen
Erfolgreiche Teilnahme an „Eingebettete Systeme“, sichere C-Kenntnisse, Freude an Datenblättern und präzisem Messen. Alternativ sind die Voraussetzungen für diese Arbeit auch gegeben, wenn man anderweitig erworbene Kenntnisse zu hardwarenahem Programmieren auf Mikrocontrollern, Werkzeuggestütztes Messen von Performance und Kenntnisse zum Umgang mit Datenblättern nachweisen kann.

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.

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.

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.

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 und Herrn Böhmer.

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.

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.

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.

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.