Cell-Expansion and Region-Cut-Split Algorithms for Steiner Tree Problem in HAPS Networks

The High Altitude Platform Station (HAPS) mesh network can cover a large surface area on Earth, making it an excellent choice for broadcasting signals to a vast number of recipients distributed across extensive regions simultaneously. Different applications may attract different sets of audiences, leading to various groups of recipients subscribing to different content services. We refer to data delivery among these subscribers as Selected Group Broadcasting (SGB). Essentially, SGB routing is a Steiner Tree Problem in Graphs (STPG). In this paper, we propose a Cell-Expansion algorithm that provides a generic exact solution for hop-constrained STPG and functions as a reduction-integration framework. The HAPS mesh follows the concept of a small-world network, characterized by its unique topological properties. Accordingly, we introduce the Region-Cut-Split algorithm for merging inter-regional networks. By combining these algorithms, we achieve an exact solution for SGB routing. The distributed parallel runtimes of our algorithms enable feasible real-time, QoS-assured SGB services for data delivery across a HAPS mesh network. Rigorous simulations and verification confirm the efficacy of our proposed mechanisms for constructing SGB routing on arbitrary random HAPS topologies. In HAPS mesh simulations, our solution consistently outperforms state-of-the-art heuristics in both accuracy and efficiency, and surpasses exact solvers in real-time performance.