Optimization of Anchor Nodes Placement in Wireless Localization Networks

Staff - Faculty of Informatics

Date: 28 February 2019 / 15:30 - 17:00

USI Lugano Campus, room A-23, Red building (Via G. Buffi 13)

You are cordially invited to attend the PhD Dissertation Defense of Katarina Balac on Thursday February 28th, 2019 at 15:30 in room A-23 (Red building).

This work focuses on optimizing node placement for time-of-flight-based wireless localization networks. Main motivation are critical safety applications. The first part of my thesis is an experimental study on in-tunnel vehicle localization. In-tunnel localization of vehicles is crucial for emergency management, especially for large trucks transporting dangerous goods such as inflammable chemicals. Compared to open roads, evacuation in tunnels is much more difficult, so that fire or other accidents can cause much more damage. We provide distance measurement error characterization inside road tunnels focusing on time of flight measurements. We design a complete system for in-tunnel radio frequency time-of-flight-based localization and show that such a system is feasible and accurate, and that few nodes are sufficient to cover the entire tunnel. The second part of my work focuses on anchor nodes placement optimization for time-of-flight-based localization networks where multilateration is used to obtain the target position based on its distances from fixed and known anchors. Our main motivation are safety at work applications, in particular, environments such as factory halls. Our goal is to minimize the number of anchors needed to localize the target while keeping the localization uncertainty lower than a given threshold in an area of arbitrary shape with obstacles. Our propagation model accounts for the presence of line of sight between nodes, while geometric dilution of precision is used to express the localization error introduced by multilateration. We propose several integer linear programming formulations for this problem that can be used to obtain optimal solutions to instances of reasonable sizes and compare them in terms of execution times by simulation experiments. We extend our approach to address fault tolerance, ensuring that the target can still be localized after any one of the nodes fails. Two dimensional localization is sufficient for most indoor applications. However, for those industrial environments where the ceiling is very high and the worker might be climbing or be lifted from the ground, or if very high localization precision is needed, three-dimensional localization may be required. Therefore, we extend our approach to three-dimensional localization. We derive the expression for geometric dilution of precision for 3D multilateration and give its geometric interpretation. To tackle problem instances of large size, we propose two novel heuristics: greedy placement with pruning, and its improved version, greedy placement with iterative pruning. We create a simulator to test and compare all our proposed approaches by generating multiple test instances. For anchor placement for multilateration-based localization, we obtain solutions with below 2 % anchors overhead with respect to the optimum on average, with around 5 s average execution time for 130 candidate positions. For the fault-tolerant version of the same problem, we obtain solutions of around 1 % number of anchors overhead with respect to the optimum on average, with 0.4 s execution time for 65 candidate positions, by using greedy heuristic with pruning. For 3D placement, the greedy heuristic with iterative pruning produced results of 0.05 % of optimum on average, with average execution time of around 6 s for 250 candidate positions, for the problem instances we tested.

Dissertation Committee:
- Prof. Miroslaw Malek, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Mauro Prevostini, Università della Svizzera italiana, Switzerland (Research co-Advisor)
- Prof. Cesare Alippi, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Antonio Capone, Politecnico di Milano, Italy (External Member)
- Prof. Hans-Peter Schwefel, Aalborg University, Denmark (External Member)