Dokument: A Rank 1 SDP Approach for the Sensor Network Localization Problem

Titel:	A Rank 1 SDP Approach for the Sensor Network Localization Problem
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=10074
URN (NBN):	urn:nbn:de:hbz:061-20090113-092917-6
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Lopez, Ania [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 3,22 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 08.01.2009 / geändert 08.01.2009
Beitragende:	Prof. Dr. Jarre, Florian [Betreuer/Doktorvater] Prof. Dr. Ratschek, Helmut [Gutachter]
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibungen:	This thesis analyzes the problem of localizing sensors in wireless ad hoc networks. Wireless ad hoc networks can be found in several practical applications, among which the most known is the climatic monitoring. Every sensor in such a network has the ability to register specific factors. These can be forwarded (if necessary) to other sensors within the network until reaching a so-called anchorpoint. Due to this special form, these networks are applied for example to predict forest fires, earthquakes or climatic changes. The Sensor Network Localization Problem (SNLP) is a NP-hard problem and is solved by the approximate solution of a non-linear least squares problem in practice. Leaning on the work of Ye et al. [5] a semidefinite program (SDP) formulation is proposed: \begin{equation*} \min \{ C\bullet X \mid \mathcal{A} (X) =b,\; X\in \mathcal{S}^n_{+} \}, \end{equation*} where the variable is $X\in \mathcal{S}^n$, the space of real symmetric matrices of dimension $n$. The vector $b\in\R^m$, the linear mapping $\mathcal{A}:\mathcal{S}^n\to \R^m$ and the matrix $C\in \mathcal{S}^n$ are given. The cone $\mathcal{S}^n_+$ is the set of all real symmetric positive semidefinite matrices of dimension $n$, i.e. $\mathcal{S}^n_+ := \{ M\in \mathcal{S}^n \mid S\succeq 0\}$. The notation $C\bullet X$ denotes the inner product of the symmetric matrices $C$ and $X$ and is given by $$ C\bullet X = tr(C\, X) = \underset{i=1}{\overset{n}{\sum}}\, \underset{j=1}{\overset{n}{\sum}} \, C_{ij}\, X_{ij}. $$ This SDP formulation is a relaxation of the original problem (in the model proposed in this thesis, the exact solution of the original problem has to fulfil additionally a rank 1 condition). The great advantage of employing SDPs is their good numerical treatment via interior point methods. For special cases (so-called "uniquely'' localizable networks) is shown, that the presented SDP provides the exact solution for the SNLP. The interesting problem variant, which is common in practice, incorporates measurement errors due to interferences between the sensors in a network. This yields a disturbed localization problem. In this context a local error bound for the disturbed solution is presented. To improve the solution of the relaxed problem, several heuristics are presented and compared numerically. The so-called Curvature Descent method achieves global and local quadratic convergence. In dieser Arbeit wird das Problem der Lokalisierung von Sensoren in drahtlosen (Ad Hoc) Netzwerken untersucht. Drahtlose Ad Hoc Netzwerke finden sich in sehr vielen Anwendungen. Die bekann- testen sind die klimatischen Beobachtungen. Dabei hat jeder Sensor die Möglichkeit bestimmte Bedingungen zu registrieren und diese bei Bedarf an weitere Sensoren (bis zum Erreichen eines sog. Ankerpunktes) weiterzugeben. So werden solche Netzwerke z.B. zur Vorhersagung von Waldbränden, Erdbeben oder zur allgemeinen Registrierung klimatischer Veränderungen eingesetzt. Das SNLP (Sensor Network Localization Problem) ist NP-vollständig und wird in der Praxis über die Annäherung an die Lösung des zugehörigen nicht-linearen least squares Problems gelöst.\\ Anlehnend an die Arbeit von Ye et al. [5] wird eine Modellierung als Semidefinites Programm (SDP) der Form \begin{equation*} \min \{ C\bullet X \mid \mathcal{A} (X) =b,\; X\in \mathcal{S}^n_{+} \}, \end{equation*} beschrieben. Hierbei ist die Variable $X\in \mathcal{S}^n$, dem Raum der reellen symmetrischen Matrizen der Dimension $n$. Der Vektor $b\in\R^m$, die lineare Abbildung $\mathcal{A}:\mathcal{S}^n\to \R^m$ und die Matrix $C\in \mathcal{S}^n$ sind gegebene Parameter. Der Kegel $\mathcal{S}^n_+$ ist der Raum aller reellen symmetrischen positiv semidefiniten Matrizen der Dimension $n$, d.h. $\mathcal{S}^n_+ := \{ M\in \mathcal{S}^n \mid S\succeq 0\}$. Die Notation $C\bullet X$ bezieht sich auf das innere Produkt von den symmetrischen Matrizen $C$ und $X$ und ist gegeben durch $$ C\bullet X = tr(C\, X) = \underset{i=1}{\overset{n}{\sum}}\, \underset{j=1}{\overset{n}{\sum}} \, C_{ij}\, X_{ij}. $$ Diese SDP Formulierung ist eine Relaxierung des ursprünglichen Problems, dessen exakte Lösung (bei der in dieser Arbeit vorgeschlagenene Modellierung) noch zusätzlich eine Rang 1 Bedingung erfüllen muß . Der Vorteil von Semidefiniten Programmen ist ihre gute Lösbarkeit mit Innere-Punkte-Verfahren. Für spezielle Fälle (sog. "uniquely" lokalisierbare Netzwerke) wird gezeigt, daß das vorgeschlagene SDP die exakte Lösung des SNLP liefert. Die interessantere Problemvariante resultiert durch die Miteinbeziehung von Meßfehlern, was zu einem gestörten Lokalisierungsproblem führt und dem Fall entspricht, der in der Praxis normalerweise eintritt (z.B. durch Störungen des Signals zwischen den Sensoren durch evtl. topographische Gegebenheiten). In diesem Zusammenhang wird eine lokale Fehlerschranke für die gestörte Lösung hergeleitet. Um die Lösung des relaxierten Problems zu verbessern, werden mehrere Heuristiken vorgestellt und numerisch verglichen. Für die sog. Curvature Descent Methode wird globale und lokal quadratische Konvergenz erreicht.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Mathematische Optimierung
Dokument erstellt am:	13.01.2009
Dateien geändert am:	08.01.2009
Promotionsantrag am:	13.10.2008
Datum der Promotion:	12.12.2008