Back
Texte intégral
Doctoral thesis

Optimization of anchor nodes placement in wireless localization networks

    28.02.2019

131 p

Thèse de doctorat: Università della Svizzera italiana, 2019

Optimization
Indoor localization
3D localization
Integer linear programming
Heuristics
Wireless networks
Fault tolerance
Time-of-flight based ranging
Multilateration
In-tunnel vehicle localization
English 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 5s 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.4s 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 6s for 250 candidate positions, for the problem instances we tested.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1319140
Statistics
Document views: 165 File downloads:
  • 2019INFO009.pdf: 148