Sensor positioning in distributed sensor networks

Abstract

In the thesis, it is shown how sensor placement problems (SPPs) can be stated and solved. New techniques to model these problems and to find approximate solutions are presented. Their evaluation is conducted for real world environments using the properties of a self-build positioning system. Nine methods are presented to search for an optimal sensor placement in a discrete or continuous environment. Two global optimization models, two greedy heuristics, two nonlinear optimization models, two decomposition based optimization models and one approximate optimization model. All of these methods serve the same goal, to minimize the number of sensors while serving the positioning constraint that a minimum positioning quality based on the sensor geometry is provided in the environment. Two of the methods also introduce secondary goals that become active if the primary goal is fulfilled. One maximizes the qualities in the environment and one increases the area that is covered with a minimum quality. The global optimization models are used solve discretized SPP. To state them, a customized sampling scheme is presented that allows a linear increase in sampled workspace position and sensor pose for an environment. In contrast to the global optimization models, the approximate optimization model and the greedy heuristics solve a simplified discretized problem with decreased complexity. Finally, the decomposition based optimization models separate the input environment into multiple small models. Therefore, their solution to the SPP is a combination of all independently calculated solutions. To state the decomposition based models, a convex polygon decomposition algorithm is introduced. It has a polynomial complexity and separates an input polygon into convex pieces with additional Steiner points that are only created on the polygon boundary. For the approximate optimization model the estimation of its solution quality is derived. The derivation introduces properties of approximate SPP solutions that can be exploited to improve them using an iterative problem specific search heuristic. All algorithms are validated using the digitalization of four real world input environments of different sizes and the properties of a custom developed indoor positioning system. Each environment is solved with an extensive set of varying discretization exactness, leading to more than 15,000 solved or improved SPP for each environment. The most important findings of the evaluation are the good performance of the Greedy Single Sensor Selection algorithm over the other approximation algorithms and the negligible influence of the sensor pose discretization exactness for the smaller environments. In addition, it could be shown that the worst case approximation ratio tends to be too pessimistic for larger problems. At last, it was shown that the iterative improvement of approximate solutions by the search heuristic can significantly increase the solution goodness.