Self-localization in sensor networks using nonparametric belief propagation

Abstract

Drahtlose Sensornetze haben in den letzten Jahren, erheblich an Attraktivität gewonnen. Solche Sensornetze, bestehen typischerweise aus einer großen Anzahl von billigen Sensoren die in der Lage sind sowohl Daten zu erfassen als auch diese entsprechend zu verarbeiten. Die Applikationen von Sensornetzen sind vielseitig. Von Überwachung über Objektverfolgung, vieles läßt sich mit Sensornetzen realisieren. Jedoch ist für viele der Applikationen, die Position der Sensoren von wesentlicher Bedeutung. Manchmal könnte sich eine manuelle Konfiguration der Sensoren im Vornherein schwierig oder gar unmöglich erweisen. In solchen Fällen sollte das Sensornetz in der Lage sein, sich selbst zu lokalisieren. In dieser Arbeit verwende ich einen dezentralen statistischen Algorithmus unter dem Namen nonparametric belief propagation (NBP), der von A. Ihler in seiner Dissertation [4] entwickelt wurde. Dieses dezentrale Verfahren kommt ohne zentrale Recheneinheit aus. Er beruht auf sogenannten Graphischen Modellen, ein Rahmenwerk das es erlaubt statistische Bezüge graphisch zu modellieren.<br />Der NBP Algorithmus wird implementiert und unter verschiedenen Voraussetzungen getestet. Außerdem wird ein mögliches Protokoll vorgeschlagen welches die Kommunikationsreihenfolge von "Messages", die im Rahmen des Algorithmus berechnet werden, regelt. Im Letzten Kapitel der Arbeit werden die daraus folgenden Resultate analysiert und Schlussfolgerungen gezogen.<br />

Wireless sensor networks have gained considerable attention in recent years. Typically, such networks consist of a large number of low-cost sensors that are capable of sensing and processing data. More importantly, the sensors are able to network with each other via low power wireless communications.<br />Possible applications of sensor networks are environmental monitoring, object tracking, etc. Oftentimes, sensor networks are application specific, i.e., they are designed and deployed for spe- cial purposes.<br />For some of the applications the sensor positions are of essential importance for the success of the task. Localization, i.e., determining the position, of sensors in a sensor network, is an important step to be performed prior to the actual application of a sensor network. Depending on the specific application, manual calibration/localization of the sensors may be financially pro- hibitive or dangerous. Hence self-localization of the sensor network is desirable, i.e., the sensors perform the localization task themselves without an external fusion center. Additionally, for the generally self-powered sensors, energy consumption is one of the most important design param- eters, since replacing batteries may be difficult or impossible in many applications.<br />Thus, the sensor network, as well as the algorithms performed by it, must be designed in a way to extend the network lifetime.<br />In this thesis, I will employ a decentralized stochastic algorithm, proposed by A. Ihler in [4]. The so-called nonparametric belief propagation (NBP) algorithm is based on the framework of graphical models, which has been shown to be very useful for describing statistical structures in sensor networks. The main reason for the attractiveness of the graphical model framework is the intuition that comes with them, as a sensor network naturally gives rise to such graphical models. The algorithm performance will be analyzed and verified with different network parameters. Also, a communication "protocol" is proposed that may help to save valuable energy. In the last chapter of the thesis, the conclusions from the simulations of the NBP algorithms is presented.