Effiziente Synthese konsistenter Graphen und ihre Anwendung in der Lokalisierung akustischer Quellen

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 fundamentalen Maschen 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.

This thesis revises the engineering problem of locating many acoustic sources simultaneously in a reverberant environment and applies the synthesis of consistent graphs to solve this problem. Therefore we give an introduction to the different methods and principles of acoustic source localization. Especially, the time difference of arrival (TDOA) based localization, that has the ambiguity of assigning the correct TDOA to the corresponding source, is discussed in detail. Based on this example we further introduce the mathematical framework of graph theory and provide the algorithms commonly known and used throughout this thesis. This includes algorithms like depth-first-search and breadth-first-search to find a spanning tree in a given graph. The spanning tree is necessary to determine the set of fundamental loops, that form the smallest set of loops. The synthesis of consistent graphs is then performed by merging the consistent fundamental loops in a bottom-up way. Therein, two options turn out to be useful: the synthesis of fully consistent graphs which returns a set of consistent graphs that have a valid consistent edge weight on all edges and the synthesis of partially consistent graphs that may lack some weights. Both options are based on determining the subsolutions of consistent fundamental loops in the sensor graph. The first option is then solved by a backtracking algorithm. The second option is derived by introducing a new type of graph, the compatibility-conflict-graph, that is able to express three different types of relations between the subsolutions of consistent loops: 1) two consistent loops do not intersect with their edges, 2) two consistent loops do intersect with common edge weights (compatible) and 3) two consistent loops do intersect with different edge weights (conflict). In order to synthesize all partially consistent graphs we introduce a new algorithm called CCGsearch whose correctness is proven in this thesis. The computational complexities of both synthesis approaches are verified analytically and by simulations.