Sensor resource management with evolutionary algorithms applied to indoor positioning

Abstract

This thesis contributes to the current research in the field of sensor resource management of indoor positioning systems. Sensor resource management deals with sensor placement and sensor scheduling, although this thesis focuses only on the former. We use an indoor positioning system based on infrared signals with phase-difference of arrival measurements. These phase measurements are subsequently converted to distance-differences; hence, our problem becomes hyperbolic trilateration with range-difference of arrival measurements. We include a model of the error of range-difference measurements with an infrared system, though we can omit the fact that we work with an infrared system and think only on range-difference measurements which have a Gaussian distribution with a variance calculated by the model. As a matter of fact, the work described in this thesis can be applied to other positioning systems using a model of the measurement errors, even when performing spherical trilateration or angulation. Most of the proposals that place sensors to improve the estimation accuracy optimize metrics of the Cramer-Rao lower bound, as we do in this work. The thesis contains a chapter ´ that reviews the existing contributions on sensor placement for target localization, which concludes stating our own contributions to the current literature. To summarize, we can classify the different approaches in three categories. The first group deals with the determination of an optimal configuration of sensors to locate a target, they usually optimize the determinant of Fisher information matrix or the dilution of precision. These methods obtain analytical expressions that provide explanations of the effect of different elements of the positioning system on the final accuracy. However, they cannot be applied to real situations. To the second group belong the approaches that focus on sensor deployment to cover a whole area or multiple targets. This thesis belongs to this category. Finally, there are methods that use techniques of sensor selection to obtain optimal configurations. Among these three kinds of proposals we can find the following drawbacks: the simplification of the measurement model to obtain mathematically tractable expressions, consideration of a single accuracy performance measure, placement of a fixed amount of sensors, or sensor deployment in simple areas without non-line-of-sight problems. Our first contribution aims to overcome the consideration of a single accuracy criterion, which is usually the determinant or trace of the covariance or information matrix of the estimation. Each metric of these matrices has its own practical meaning; hence, considering only one of them provides solutions which are not optimal regarding other metrics. For instance, we can get a solution with a low mean squared error but a high elongation of the error ellipsoids. Our proposal involves the use of multi-objective evolutionary algorithms that optimize several metrics of the covariance of the estimation, such as average mean squared error in the area, isotropy of the solution, or the maximum deviation of a point of the region of interest. This optimization provides a Pareto front with a set of solutions reflecting the trade-off among different metrics. The resource manager can use this set to choose a desired solution according to current needs. This approach also allows us to improve the performance of some estimators. The second contribution of the thesis involves sensor placement in complex zones, where there are obstacles that cause occlusions to some sensors. Thus, we can introduce the problem of trying to cover as many points of the area as possible with the minimum amount of sensors needed to estimate the position of a target. Not only increases such amount the percentage of covered area and the obtained accuracy, but it also increases the cost of the system. As a consequence, the number of deployed sensors must also be optimized together with the coverage of the area and the uncertainty of the estimated position. In order to achieve this goal, we propose a modification of the previous algorithm based on the use of subpopulations and genetic operators that allow us to place and remove sensors from an existing set according to current coverage and saturation of the region of interest. Each one of the chapters that describes those contributions provides results and conclusions that confirm the suitability of the proposed methods. Finally, the thesis ends with some proposals about future improvements to the work