A wireless sensor network consists of a large quantity of small, low-cost sensor nodes that are limited in terms of memory, available energy, and processing capacity. Generally, these sensor nodes are distributed in space to obtain physical parameters such as temperature, humidity, vibration or light conditions, and transmit the measured values to a central entity. The measurements are tagged with the corresponding location of the nodes in the network and the time of sampling to enable a view of the value distribution in space and time later on. Positioning of wireless sensor nodes without dedicated hardware is an open research question. Especially in the domain of embedded networked sensors, many applications rely on spatial information to relate collected data to the location of its origin. As a first step towards localization, an estimation of the distance between two nodes is often carried out to determine their positions. So far, the majority of approaches therefore explore physical properties of signals such as the strength of a received signal or its arrival time. However, this is problematic since either the complexity on the software or the hardware is not adequate for embedded systems, or the approaches lack the required accuracy. This thesis presents two novel ad-hoc localization systems called FCH (Factor Correction per Hop) and PIV (Positioning Iterative Vector) based on the DIN algorithm (Distance by Intersection of Neighborhoods). The three algorithms are designed to work as distributed ad-hoc locate-sensing methods for indoor environments based solely on the investigation of local node densities. The FCH method is divided into two phases: the first phase obtains the node to landmark distances from which to later derived the node positions in the second phase using multilateration. Whereas the PIV algorithm has two operation modi either as an autonomous localization approach (where the first step is acquiring the local neighboring distances to subsequently discover the node position in a iterative manner) or working as an iterative refinement phase. To evaluate the accuracy of these algorithms, extensive simulations and experiments with diferent testbed setups using a maximal number of 108 real sensor nodes have been conducted. Finally is compared the proposed position-sensing algorithms to several distributed algorithms and two RSSI-based locate-sensing algorithms. The position accuracies achieved by applying these algorithms have reached an average position error up to 1.33 +/- 0.84 meters.
Ein drahtloses Sensor-Netzwerk besteht aus einer großen Anzahl von kleinen, Kostengünstigen Sensorknoten, die in Bezug auf Speicherplatz, verfügbare Energie und Rechnerleistung stark begrenzt sind. Typischeweise sind die Sensorknoten in einem bestimmten Raum verteilt, um Umgebungsparameter wie Temperatur, Feuchtigkeit, Erschütterungen oder Lichtverhältnisse zu messen. Die aufgenommenen Messdaten werden danach an einem zentralen Rechner per Funk übertragen. Die Messwerte werden im Netzwerk in Form von Tripeln übertragen. Die Tripel bestehen aus dem eigentlichen Messwert, dem Zeitpunkt der Messung und dem Ort an dem sich der Sensorknoten zur Messung befand. Auf diese Weise ist es möglich, die Verteilung der Messwerte relativ zu Raum und Zeit auszuwerten. Speziell im Bereich der eingebetteten vernetzten Sensoren basieren viele Anwendungen auf räumlichen Informationen, die in Relation mit den gesammelten Sensordaten gesetzt werden müssen. Als einen ersten Schritt zur Lokalisierung wird oft eine Schützung der Distanz zwischen zwei Knoten durchgeführt, um ihre Positionen annähernd zu bestimmen. Die meisten Lokalisierungsmethoden erforschen und verwenden daher die physikalischen Eigenschaften der Funksignale, wie zum Beispiel die Stärke eines empfangenen Signals oder seine Ankunftszeit. Allerdings sind diese Methoden nur bedingt für eingebettete Systeme geeignet, da entweder die Komplexität der Software die Grenzen der Rechenleistung eines Sensorknoten sprengt oder nicht genügend Speicher zur Verfügung steht. Diese Arbeit präsentiert zwei neue Systeme zur Ad-hoc Lokalisierung, im Folgenden genannt FCH (Factor Correction pro Hop) und PIV (Positionierung Iterative Vector). Beide Algorithmen basierten auf dem DIN-Algorithmus (Distance by Intersection of Neighborhoods). Alle drei Algorithmen sind so konzipiert, dass sie die Position von Knoten in einem Ad- hoc Netzwerk innerhalb von Gebäuden nur mittels des Parameters der lokalen Knotendichten bestimmen. Die FCH-Methode ist in zwei Phasen untergliedert: In der ersten Phase werden die Abstände zu den verschiedenen Referenzknoten anhand der lokalen Knotendichte geschützt. In der zweiten Phase werden diese Abstände für eine Multilateration verwendet, um die Position der Sensorknoten im Netzwerk zu berechnen. Der PIV Algorithmus hat zwei Betriebsmodi: Im ersten Modus wird er zur autonomen Lokalisierung eingesetzt. Hier ermittelt PIV die Abstände zur lokalen Nachbarschaft, um zu einem späteren Zeitpunkt die Position mit einem iterativen Algorithmus zu ermitteln. Im zweiten Modus wird der PIV verwendet um eine iterative Verfeinerung der berechneten Positionen vorzunehmen. Um die Genauigkeit der Algorithmen auszuwerten, werden verschiedene Simulationen und Real-World Experimente in unterschiedlichen Testumgebungen mit einer maximalen Anzahl von 108 Sensorknoten durchgeführt. Abschließend werden die neuen Algorithmen FCH und PIV mit mehreren verteilten Ad-hoc Methoden und zwei RSSI-basierten Lokalisierungsalgorithmen vergliechen. Unter Verwendung der oben genannten Algorithmen kann ein mittlerer Positionierungsfehler von 1.33 +/- 0.84 m erreicht werden.
