ISBN 9783843922449

978-3-8439-2244-9, Reihe Informationstechnik

Martin Kreißig
Effiziente Synthese konsistenter Graphen und ihre Anwendung in der Lokalisierung akustischer Quellen

154 Seiten, Dissertation Universität Stuttgart (2015), Softcover, A5

Zusammenfassung / Abstract

In dieser Arbeit wird das Problem der simultanen, akustischen Mehrquellenlokalisierung in echobehafteten Umgebungen genauer betrachtet und daran beispielhaft die Anwendungsmöglichkeit der Synthese konsistenter Graphen gezeigt und analysiert. Dafür werden die Grundlagen der akustischen Lokalisierung eingeführt und unterschiedliche Ansätze vorgestellt. Im Besonderen werden die laufzeitdifferenzbasierten Lokalisierungsverfahren betrachtet, die das Problem der uneindeutigen Zuweisung der Laufzeitdifferenzen zu den Quellen haben. Anhand dieses konkreten Anwendungsbeispiels der Lokalisierung wird die Problematik auf ein graphentheoretisches Problem abstrahiert. Deshalb werden zunächst die graphentheoretischen Grundlagen und bereits bekannte Algorithmen, wie die Tiefen- und Breitensuche eingeführt, die beide einen aufspannenden Baum suchen. Der aufspannende Baum ist notwendig, um die Menge der fundamentalen Maschen zu bestimmen. Die Synthese konsistenter Graphen erfolgt durch das Zusammenführen der konsistenten fundamentalen Maschen. Dabei unterscheidet man folgende Vorgehensweisen: die Synthese voll konsistenter Graphen, die jeder Kante des Eingangsgraphen ein konsistentes Kantengewicht zuweisen und die Synthese partiell konsistenter Graphen, die nur eine Teilmenge von Kanten beinhalten.

Beide Vorgehensweisen basieren auf den konsistenten fundamentalen Maschen, welche die Nullsummenbedingung erfüllen. Die Synthese voll konsistenter Graphen wird über ein Backtracking-Verfahren realisiert. Die Synthese partiell konsistenter Graphen wird aus dem Kompatibilitäts-Konflikt-Graph abgeleitet, der ein neuer Typus von Graph ist und die drei unterschiedlichen Zustände zwischen den konsistenten FM beschreibt: 1) zwei konsistente Maschen haben keine gemeinsame Kanten, 2) zwei konsistente Maschen haben gemeinsame Kanten und identische Kantengewichte (kompatibel) und 3) zwei konsistente Maschen haben gemeinsame Kanten und unterschiedliche Kantengewichte (Konflikt).

Um alle möglichen, partiell konsistenten Graphen zu synthetisieren, wird der neue Algorithmus CCGsearch eingeführt und auf Vollständigkeit bewiesen. Die Berechnungskomplexitäten der beiden Syntheseverfahren werden sowohl analytisch hergeleitet als auch durch Simulationen verifiziert.