Reliability Analysis of Multi-hop Routing in Multi-tier LEO Satellite Networks

Ruibo Wang, Mustafa A. Kishk, Mohamed-Slim Alouini

Abstract

This article studies the reliability of multi-hop routing in a multi-tier hybrid satellite-terrestrial relay network (HSTRN). We evaluate the reliability of multi-hop routing by introducing interruption probability, which is the probability that no relay device (ground gateway or satellite) is available during a hop. The single-hop interruption probability is derived and extended to the multi-hop interruption probability using a stochastic geometry-based approach. Since the interruption probability in HSTRN highly depends on the priority of selecting communication devices at different tiers, we propose three priority strategies: (i) stationary optimal priority strategy, (ii) single-hop interruption probability inspired strategy, and (iii) density inspired strategy. Among them, the interruption probability under the stationary optimal priority strategy can approach the ideal lower bound. However, when analyzing an HSTRN with a large number of tiers, the stationary optimal priority strategy is computationally expensive. The single-hop interruption probability inspired strategy is expected to be a low-complexity but less reliable alternative to the stationary optimal priority strategy. In numerical results, we study the complementarity between terrestrial devices and satellites. Furthermore, analytical results for reliability are also applicable to the analysis of satellite availability, coverage probability, and ultra-reliable and low latency communications (URLLC) rate. Finally, we extend our original routing strategy into a multi-flow one with dynamic priority strategy.

Introduction

As mega-constellations like Starlink and OneWeb populate the skies, we are moving toward a "network of networks" where data must hop across multiple satellites at different altitudes (tiers) and ground stations to reach its destination. Traditional routing analysis often relies on deterministic models, which are computationally exhausting for thousands of moving parts. Furthermore, satellite routing faces unique physical hurdles: Earth blockage, signal attenuation over long distances, and varying constellation heights. This research provides a rigorous mathematical framework using stochastic geometry to calculate the reliability of multi-hop paths in such dynamic, multi-tiered environments.

System Model and Methodology

The authors employ Stochastic Geometry to treat satellite locations as a Binomial Point Process (BPP) on concentric spherical surfaces. This allows for the calculation of the probability of finding a relay within a specific "constraint region."

Geometric model of the multi-tier satellite-terrestrial network showing tiers and dome angle constraints.

As shown in the figure above, the network is divided into tiers: Tier 1 (Ground), and Tiers 2 and 3 (Satellite). The constraints for a valid next hop include:

  1. Direction Angle ($\theta_r$): Ensuring the next hop moves toward the destination.
  2. Minimum Dome Angle ($\theta_s$): Preventing inefficiently small hops.
  3. Maximum Dome Angle ($\theta_{i,j}$): Accounting for signal decay and Earth blockage.
  4. Maximum Communication Distance ($d_{th}$): Ensuring link reliability.

To analyze multi-hop paths, a Markov Chain-based framework is used. A Transition Probability Matrix (TPM) is defined where each state represents a satellite tier, with an "absorbing state" representing a routing interruption (failure).

Priority Strategies for Routing

The reliability of the network is highly dependent on how relays are selected across different tiers. The paper proposes three strategies:

  • Stationary Optimal Priority Strategy (SOPS): Uses the "steady-state" distribution of the network to minimize overall interruption probability.
  • Single-hop Interruption Probability (SHIP) Inspired Strategy: A lower-complexity alternative prioritizing tiers based on individual hop reliability.
  • Density Inspired Strategy: A naive approach prioritizing tiers with the highest satellite density.
Multi-hop routing process illustrating the direction angle $\theta_r$ and relay selection between ground and satellite tiers.

Key Insights and Results

The mathematical models were validated using Monte Carlo simulations based on real-world LEO parameters (e.g., Kepler and OneWeb constellations). Key findings include:

  • The "Inverted Pyramid" Advantage: Reliability improves when more satellites are deployed in higher altitude tiers. Higher satellites have a wider field of view, increasing the likelihood of finding a valid next hop.
  • Satellites vs. Gateways: Increasing satellite count is significantly more effective at boosting reliability than increasing ground gateways.
  • Convergence: Regardless of the starting point, the probability of data being at a certain tier quickly converges to a "stationary distribution" after a few hops, simplifying long-distance calculations.
  • Strategy Performance: SOPS approaches the ideal lower bound for interruption probability. While SHIP is slightly less reliable, it offers a significant reduction in computational complexity ($O(K^3)$ vs $O(K^3 \cdot K!)$ for $K$ tiers).

Conclusion

This study presents the first comprehensive reliability analysis for multi-hop routing in multi-tier LEO networks. Future work will address network congestion using Marked Poisson Point Processes (MPPPs) and integrate more precise orbital mechanics to capture "street-of-coverage" patterns.

Summary updated

Abstract

This article studies the reliability of multi-hop routing in a multi-tier hybrid satellite-terrestrial relay network (HSTRN). We evaluate the reliability of multi-hop routing by introducing interruption probability, which is the probability that no relay device (ground gateway or satellite) is available during a hop. The single-hop interruption probability is derived and extended to the multi-hop interruption probability using a stochastic geometry-based approach. Since the interruption probability in HSTRN highly depends on the priority of selecting communication devices at different tiers, we propose three priority strategies: (i) stationary optimal priority strategy, (ii) single-hop interruption probability inspired strategy, and (iii) density inspired strategy. Among them, the interruption probability under the stationary optimal priority strategy can approach the ideal lower bound. However, when analyzing an HSTRN with a large number of tiers, the stationary optimal priority strategy is computationally expensive. The single-hop interruption probability inspired strategy is expected to be a low-complexity but less reliable alternative to the stationary optimal priority strategy. In numerical results, we study the complementarity between terrestrial devices and satellites. Furthermore, analytical results for reliability are also applicable to the analysis of satellite availability, coverage probability, and ultra-reliable and low latency communications (URLLC) rate. Finally, we extend our original routing strategy into a multi-flow one with dynamic priority strategy.
BibTeX
@article{wang2024reliability,
  author = {Ruibo Wang and Mustafa A. Kishk and Mohamed-Slim Alouini},
  title = {{Reliability Analysis of Multi-hop Routing in Multi-tier LEO Satellite Networks}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2024},
  doi = {10.1109/twc.2023.3293467},
}
Figure