Wireless sensor networks are composed of hundreds of tiny sensor nodes able to observe the environment, perform simple calculations and communicate with each other. Due to the desired node size of only a few cubic millimeters, the dimensions of the transceiver and the battery are critical. Consequently, the scarcest resource within a network is the available energy. Achieving a long lifetime of the sensor network therefore requires low power hardware as well as optimized algorithms.
After deploying the sensor network over a phenomenon, sensor nodes initially carry no position information. Sensor information is only useful if combined with a geographical position. Possible positioning technologies such as the Global Positioning System (GPS) or soon the European system Galileo are unsuitable for miniaturized sensor nodes. Due to the size of the hardware, the high prices and the high energy requirements, they are only feasible for a very small number of nodes (further called beacons). All remaining nodes may autonomously estimate their own position with measurements such as distances to these beacons.
If only low precision is required, approximative algorithms can be applied to estimate the position with only low power and hardware requirements. Thus, in this thesis, the approximative "Weighted Centroid Localization" algorithm was developed and optimized to achieve high precision with a low complexity of O(6n − 2).
The primary focus of this thesis was to distribute highly complex but also very precise exact algorithms. For this, a major result is the "Distributed Least Squares" algorithm (DLS), which reduces the complexity on the sensor nodes to only O(8n − 9) and features a very low algorithm error. To achieve this, DLS splits the complex least squares method into a central precalculation and a distributed subcalculation, which is computed on the resourcelimited sensor nodes. Analyses demonstrate that with DLS the complexity on every sensor node is reduced by more than 47% for the normal equation and 99% for orthogonalization methods. In addition, the proposed algorithm is robust with respect to high input errors and has low communication and memory requirements. Referring to simulations, DLS reduces the consumed network energy of a distributed multilateration by 86%. Moreover, the DLS algorithm was extended by a refinementphase, where all neighbor positions are also considered in the calculation process. Although the localization error can be reduced from 5,7% to 3%, this leads to a tradeoff between acceptable energy consumption and demanded precision. However, this "Iterative DLS" algorithm (iDLS) is highly scalable since every iteration requires exactly 50 floating point operations. Finally, this thesis adapts the DLS algorithm for different kinds of mobile networks while retaining the minimal resource requirements for every sensor node.
Further contributions of this thesis are (i) the development of the "Distributed Obstacle Localization" algorithm (DOL), (ii) the development of the simulation tool "RiSt" (Regarding defective obServations in simulations) and (iii) the extension of the already known packet simulator "JSim" with a more realistic energy model and several localization algorithms.
