Technical Summary: A Metaheuristic Framework for Optimized HAPS-Aided Localization in Urban Areas

Problem Statement

High-altitude platform stations (HAPS), operating in the stratosphere (18–22 km), offer structured signals of opportunity (SoOP) to augment Global Navigation Satellite Systems (GNSS). While HAPS possess favorable line-of-sight (LOS) conditions and high elevation angles, dense urban environments introduce severe signal blockages and non-line-of-sight (NLOS) conditions that degrade GNSS accuracy. Traditional placement strategies based solely on geometric dilution of precision (GDOP) fail to account for these practical obstructions.

The core challenge is a multi-modal multi-objective optimization problem (MMOP): jointly determining the optimal number and spatial placement of HAPS to minimize the average 3D Position Error Bound (PEB) for a Region of Interest (ROI) while simultaneously minimizing the infrastructure cost (HAPS count). This problem is characterized by:

• Discrete variables: The HAPS count is an integer.
• Non-convexity: The objective function depends on complex, environment-specific LOS/NLOS conditions derived from 3D city models.
• Non-differentiability: Traditional closed-form or convex optimization techniques are inapplicable or yield suboptimal solutions due to the inability to guarantee exact relaxation of the non-convex constraints.

Methodology

The authors propose a metaheuristic framework that integrates high-fidelity simulation with three distinct optimization algorithms.

1. System Model and Simulation Framework

• 3D City Modeling: Utilizes detailed 3D city models (e.g., Wall Street, Lujiazui, Downtown Calgary) to define the ROI.
• Ray-Tracing and Skyline Masks: To manage computational complexity, a precomputed "skyline mask" is generated for each candidate receiver location using ray tracing. This classifies signals as LOS or NLOS without re-running ray tracing during the optimization loop.
• Error Modeling: Pseudorange errors are modeled using Gaussian Mixture Models (GMMs) to account for heavy-tailed and multi-modal distributions caused by multipath and NLOS effects. Four scenarios are tested: Baseline, Extreme Reflection, Extreme NLOS, and Low-End Receiver.
• Objective Function: The optimization minimizes two objectives: (1) the average 3D PEB (calculated via the Cramér–Rao Lower Bound, CRLB) over a full sidereal day, and (2) the number of HAPS.

2. Metaheuristic Algorithms

Three algorithms are adapted to handle the discrete HAPS count and non-convex search space:

• ASDNSGA-II (Adaptive Special-Crowding Distance NSGA-II): An extension of NSGA-II that introduces a Special Crowding Distance (SCD) considering both decision and objective spaces. It employs an adaptive crossover mechanism (switching between Simulated Binary Crossover and Blend Crossover) and a heuristic crossover-type assignment strategy since the true Pareto set is unknown.
• NSGA-III: Originally designed for many-objective optimization, it uses a reference-point-based selection strategy (perpendicular distance) instead of crowding distance. It is modified to incorporate the same adaptive crossover and heuristic assignment strategies as ASDNSGA-II to ensure fair comparison.
• MOPSO (Multi-Objective Particle Swarm Optimization): Modified with a stratified archive update mechanism to group non-dominated solutions by HAPS count, ensuring consistency during velocity updates. It also employs polynomial mutation to enhance diversity in the discrete decision space.

3. Key Algorithmic Modifications

• Decision-Space Diversity: Standard crowding distance is insufficient for variables with different cardinalities. The authors propose an Aggregated Nearest-Neighbor Distance (ANND) metric to fairly assess diversity between solutions with different numbers of HAPS.
• Heuristic Crossover Assignment: A strategy is developed to select crossover types based on solution rank and crowding distances, replacing the reliance on a known true Pareto set.
• Stratified Archive (MOPSO): Ensures that particles, their personal bests, and leaders maintain consistent HAPS counts during updates.

Key Contributions

1. Novel Optimization Problem: Formulation of a joint optimization problem for HAPS count and placement under practical constraints (PEB threshold, altitude, elevation mask).
2. High-Fidelity Framework: Development of a simulation environment integrating satellite orbit propagation, 3D city models, ray-tracing-based LOS/NLOS classification, and GMM-based error modeling.
3. Algorithmic Adaptation: Development of three tailored metaheuristic solutions (ASDNSGA-II, NSGA-III, MOPSO) capable of navigating the discrete, non-convex search space.
4. Diversity Metrics: Proposal of a decision-space crowding distance method based on ANND to evaluate solutions with varying HAPS counts.
5. Heuristic Strategies: Introduction of a heuristic crossover-type assignment for ASDNSGA-II and an adaptive perpendicular distance threshold for NSGA-III to maintain methodological consistency and diversity.

Results

The framework was evaluated across three urban regions (New York, Shanghai, Calgary) and four error scenarios.

• Performance vs. Baseline: All three metaheuristic algorithms consistently outperformed a Greedy-Add baseline (a fingerprinting-based sequential selection method), particularly in the low-to-moderate HAPS regime (2–6 HAPS).
• Optimal Configuration: For the tested dense urban scenarios, four HAPS were found to be sufficient to satisfy an 18-meter average 3D PEB threshold.
• Quantitative Gains: Compared to a satellite-only system, configurations with 2–5 HAPS achieved:
  • Over 50% reduction in mean and Root Mean Square (RMS) PEB.
  • Up to 94% reduction in standard deviation (STD).
  • Up to 87% reduction in Coefficient of Variation (CV).
• Diminishing Returns: Beyond six HAPS, performance gains diminished due to geometric redundancy and placement overlaps, indicating that adding more platforms yields limited additional benefit.
• Robustness: The framework demonstrated strong robustness across varying GMM parameters (simulating different urban propagation conditions) and different city morphologies.
• GDOP Limitations: The study highlights that minimizing GDOP alone is insufficient in urban settings, as it fails to capture environment-dependent blockages. Optimized placements often differ from pure geometric solutions.
• Runtime: While the Greedy-Add baseline required approximately 26 hours on a high-performance cluster, the metaheuristic approaches achieved comparable or superior solution quality in significantly less time (approx. 1 hour for Wall Street on a standard PC).

Significance and Claims

The paper claims to establish an effective and scalable solution for HAPS-assisted localization in realistic urban settings. Its primary significance lies in:

• Moving beyond Geometry: Demonstrating that practical urban constraints (blockages, NLOS) necessitate optimization frameworks that go beyond traditional geometric metrics like GDOP.
• Efficiency: Proving that metaheuristic approaches can efficiently navigate complex, non-convex design spaces to find near-optimal configurations with fewer resources than exhaustive search or greedy methods.
• Practical Deployment: Providing actionable insights that a small number of strategically placed HAPS (e.g., four) can significantly enhance GNSS reliability in dense cities, balancing performance with infrastructure costs.

The authors maintain a modest tone, acknowledging that global optimality cannot be guaranteed due to the metaheuristic nature of the framework, but emphasizing that the solutions are high-quality, near-optimal, and robust across diverse conditions. Future work is suggested to include multi-constellation GNSS, dynamic receiver trajectories, and practical system constraints like interference and power budgets.