Verteilte Selbstlokalisierung im selbstorganisierenden Netz

In vielen Anwendungen von kommerziellem oder öffentlichem Interesse ist die Kenntnis der genauen Position ein essentielles Erfordernis, das in Zukunft noch an Bedeutung gewinnen wird. Die präzise und verlässliche Lokalisierung und Verfolgung mobiler Netzknoten (also dynamische Selbstlokalisierung) kann selbst das Ziel sein oder eine notwendige Voraussetzung für eine sinnvolle Interpretation anderer Messdaten. Methoden zur Selbstlokalisierung müssen selbst unter schwierigen Bedingungen wie dezentrale Netzarchitekturen, eingeschränkte Kommunikation zwischen den Netzknoten und Mobilität der Knoten zuverlässig funktionieren. Wesentliche Probleme der meisten derzeitigen drahtlosen Netze komplexe zentrale Steuerung und damit verbundener zusätzlicher Kommunikationsaufwand sowie Mangel an Skalierbarkeit werden durch das neuartige Konzept der Selbstorganisation vermieden. In selbstorganisierenden Netzen ist nur lokale Kommunikation erlaubt, und jeder Knoten adaptiert seine Prozesse aufgrund von eigenen Messungen und Informationen seiner Nachbarn. Gemäß diesem Konzept hat das beantragte Projekt zum Ziel, kooperative und vollständig verteilte Algorithmen für die dynamische Selbstlokalisierung von Sensornetzen zu entwerfen. Anstatt eine zentrale Verarbeitungs- oder Steuerungsinstanz zu verwenden, stützen sich diese Algorithmen auf Informationsaustausch zwischen benachbarten Knoten, selbst wenn diese ihre eigene Position nicht genau kennen. Der Rechenaufwand sowie die erforderliche Kommunikation sollen so gering wie möglich gehalten werden. Derzeitige Selbstlokalisierungsmethoden sind in der Regel nicht verteilt oder nicht dynamisch oder zu aufwendig hinsichtlich der erforderlichen Berechnungen und Kommunikation. Im beantragten Projekt sollen zwei neuartige Ansätze verfolgt und verglichen werden. Der eine Ansatz benützt Markov-Chain-Monte-Carlo-Methoden, genauer gesagt Gibbs Sampling und Partially Collapsed Gibbs Sampling. Der andere Ansatz benützt die Verteilte Total-Least-Squares-Methode. Weitere zu untersuchende Aspekte sind dezentrales Scheduling, verteilte kombinierte Synchronisierung und Lokalisierung, die Wahl der Methode zur Abstandsmessung und ein Vergleich mit zentralisierten Algorithmen hinsichtlich der Leistungsfähigkeit. Die geplanten Forschungsarbeiten sollen innerhalb der "Circuits and Systems"-Gruppe an der Technischen Universität Delft durchgeführt werden, die über beträchtliches Expertenwissen zu verschiedensten Aspekten selbstorganisierender Netze und kooperativer Selbstlokalisierung verfügt.

Das wichtigste Ergebnis des Projekts ist die Entwicklung eines gemeinsamen Konzepts und einer Methode für folgende zwei Aufgaben: optimale Datenreduktion und Ausschluss grob gestörter Daten. Diese beiden Aufgaben sind von großer Bedeutung für Anwendungen wie Lokalisierung in großen Sensornetzen, aber auch für zahlreiche andere Anwendungen mit großen Datenmengen. Datenreduktion ist oft eine Voraussetzung, um Informationen aus riesigen Mengen von Daten oder Messungen zu gewinnen. Mithilfe eines geeigneten Entscheidungskriteriums werden die verfügbaren Daten auf eine kleinere Menge aussagekräftiger Daten reduziert, die dann zur weiteren Analyse verwendet werden (z.B. zur Schätzung der Position). Das Kriterium beruht typischerweise auf statistischen Annahmen über die Prozesse, welche die Daten generieren, also auf einem stochastischen Datenmodell. Oft entsprechen aber Teile der Daten nicht dem Modell, sondern sind grob gestört. Das Erkennen und Aus schließen solcher gestörten Daten ist die zweite Aufgabe. Bisherige Methoden zur Datenreduktion sind nicht für Fälle mit solchen Störungen geeignet, während Methoden zum Ausschluss grob gestörter Daten nicht auf eine optimale signifikante Reduktion der Daten ausgelegt sind. Im Zuge des Projekts wurde ein gemeinsames Konzept für beide Aufgaben entwickelt: robuste Datenreduktion. Wir verwenden die Likelihood-Funktion aus dem angenommenen störungsfreien Datenmodell, um zu bestimmen, wie aussagekräftig eine Teilmenge der Daten ist, während gleichzeitig grob gestörte Daten ausgeschlossen werden. Wir formulieren das Problem als nicht-konvexe Optimierungsaufgabe. Als Lösung wurde eine Metropolis-Hastings (MH)-Methode entwickelt, die mit kleinen Teilmengen der Daten arbeitet und dadurch die rechnerische Komplexität in Grenzen hält. Der MH-Algorithmus ist eine anpassungsfähige iterative Methode zur Lösung von Problemen, die für klassische Schätzmethoden zu komplex sind. Seine konkrete Implementierung ist allerdings dahingehend anspruchsvoll, dass erst Konvergenz innerhalb einer angemessenen Zahl von Iterationen sichergestellt werden muss. Eine solche Implementierung wurde von uns für das Problem der robusten Datenreduktion entwickelt. Unsere Lösung ist allgemein anwendbar und nicht auf bestimmte Datenmodelle beschränkt. Neben diesem Hauptergebnis konnten noch Fortschritte in drei weiteren Gebieten gemacht werden. Das erste Gebiet ist die Schätzung der Parameter von autoregressiven Prozessen (AR-Prozessen), wenn das AR-Signal selbst nicht direkt zur Verfügung steht, sondern nur eine komprimierte Version. Für dieses Problem wurde eine neuartige Methode auf Grundlage von MH-within-Gibbs-Sampling entwickelt. Zweitens wurde für die Anwendung Cognitive Radio eine innovative Strategie für kooperatives Spectrum Sensing entwickelt, die bestehende Methoden in Hinsicht auf Datenrate und Energieeffizienz übertrifft. Dies wurde durch ein neuartiges Optimalitätskriterium mit zusätzlichen Freiheitsgraden erreicht. Drittens wurde eine Methode für Bayessche blinde Entfaltung einer spärlich besetzten Folge mit einem unbekannten Impuls entwickelt, wobei die spärlich besetzte Folge durch einen vorgeschriebenen Minimalabstand zwischen den Impulspositionen eine zusätzliche Struktur erhält.