Real-time exact solution for Steiner Tree Problem in HAPS networks

High-Altitude Platform Stations (HAPSs), such as airships and balloons, operate in the stratosphere. By establishing wireless interconnections among multiple HAPS units, a HAPS mesh can be formed to cover a vast terrestrial area. The network can thus provide an ideal platform for broadcasting signals to large and geographically dispersed recipients. A service we call Selected Group Broadcasting (SGB) is for delivering messages to members of specific subscriber groups within these broad audiences. In essence, the routing problem underneath SGB is essentially a Steiner Tree Problem in Graphs (STPG). In this paper, we introduce a novel Cell-Expansion algorithm, a reduction-integration framework that offers a conditionally exact solution for STPG with a preset number of iterations. By leveraging the small-world network characteristics inherent in HAPS meshes, where the network diameter is naturally small, we further propose the Region-Cut-Split algorithm for merging inter-regional networks, along with a Regional-Cell-Inclusion test mechanism. The integration of these algorithms yields a provably optimal solution for SGB routing under HAPS topological conditions. The distributed and parallel nature of the algorithms enables the provision of feasible real-time QoS-assured SGB services for data delivery across HAPS mesh networks. Thorough simulations and verification confirm the effectiveness of our proposed designs in constructing SGB routing over arbitrary HAPS topologies. Our solution consistently outperforms state-of-the-art heuristics in both accuracy and efficiency, while surpassing exact solvers in real-time performance.