Radio Resource Allocation for Beam Hopping Scheduling in LEO Satellite Communications: A Spatio-Temporal Perspective

Technical Summary: Radio Resource Allocation for Beam Hopping Scheduling in LEO Satellite Communications

Problem Statement
Low Earth Orbit (LEO) satellite networks face significant challenges in radio resource allocation due to dynamic traffic demands and stringent interference constraints. Beam hopping (BH) technology offers a solution by enabling dynamic beam resource allocation across spatial and temporal domains. However, the BH scheduling problem is fundamentally a high-dimensional discrete combinatorial optimization task. It requires jointly optimizing beam activation sequences and managing interference under constraints of transmit power, bandwidth, and quality of service (QoS). Existing approaches face practical limitations:

• Greedy Heuristics: While low-complexity, they rely on fixed neighborhood designs and are prone to local optima, often failing to balance throughput, fairness, and interference in multimodal landscapes.
• Evolutionary Algorithms: Methods like Genetic Algorithms (GA) offer global search capabilities but can be computationally intensive and may struggle with convergence speed.
• Learning-Based Approaches: Deep Reinforcement Learning (DRL) and other intelligent algorithms require extensive training data, high computational budgets, and often lack interpretability and generalization under environmental shifts (e.g., orbital dynamics or traffic model changes).

Methodology
The paper proposes a Tabu Search (TS)-based spatio-temporal BH resource allocation strategy that integrates a two-stage generate-evaluate framework with Simulated Annealing (SA) acceptance criteria. The core components of the methodology include:

1. Problem Formulation: The BH scheduling problem is modeled to maximize user demand satisfaction by minimizing the squared gap between total supplied capacity and user demand over a scheduling period, subject to interference distance constraints and a limit on the number of simultaneously active beams ($N_b$).
2. Two-Stage Solution Framework:
   • Stage 1 (Feasibility & Initialization): An initial feasible solution is constructed using a greedy heuristic. This process prioritizes cells with higher residual traffic demand while strictly enforcing intra-satellite interference-distance constraints (ensuring active beams are separated by at least a threshold $D_{thr}$).
   • Stage 2 (Effectiveness & Optimization): The algorithm performs neighborhood exploration and selection tailored to specific optimization targets (e.g., coverage-throughput-fairness trade-offs).
3. Key Algorithmic Innovations:
   • Adaptive Tabu Tenure Control: Unlike fixed-parameter tabu lists, the tenure length ($L_{tabu}$) is dynamically configured based on problem dimensionality ($N_b \times N_m$). This allows search intensity to scale with the problem size, balancing exploration and exploitation.
   • Probabilistic Acceptance (Simulated Annealing): To prevent premature convergence and search stagnation, the method incorporates an SA acceptance criterion. This allows the algorithm to probabilistically accept "worse" solutions, facilitating escape from local optima and improving the balance between user coverage and time-varying traffic demand.
   • Neighborhood Move Strategy: The algorithm employs a random beam count and random beam index strategy, guided by priority-based and interference-avoidance heuristics to generate candidate solutions.

Key Contributions
The paper claims three primary contributions:

1. Spatio-Temporal Resource Allocation Scheme: The introduction of a problem-size-adaptive tabu tenure control mechanism that scales search intensity with problem dimensionality, reducing reliance on manual parameter tuning.
2. Two-Stage Generate-Evaluate Framework: A structured approach that separates feasibility (interference-aware initialization) from effectiveness (objective-aware neighborhood exploration), ensuring a balance between local search efficiency and global searchability.
3. Robustness and Interpretability: The proposed approach is designed to be more robust to environmental shifts (orbital dynamics, traffic changes) and offers clearer decision logic compared to black-box learning models, while reducing data and computation requirements relative to end-to-end learning.

Results
Extensive simulations were conducted comparing the proposed Tabu Search + Simulated Annealing (TS+SA) method against Greedy Beam Hopping with/without Interference Control (GBH-AIC/GBH-WIC) and a Genetic Algorithm (GA) baseline. The results indicate:

• Throughput: The proposed method improves system throughput by 17.2% compared to GBH-AIC and 6.5% compared to GA.
• User Satisfaction: Service satisfaction increased by 11.7% over GBH-AIC and 4.4% over GA.
• Link Quality: The method achieved a higher average SINR (10.2 dB vs. 9.7 dB for GA) and reduced the outage rate to 2.3%, significantly lower than the baselines.
• Robustness: The performance gap between the proposed method and greedy baselines widened under skewed traffic distributions (e.g., Pareto 80/20 rule), where the proposed method showed a 36.7% throughput improvement over the greedy baseline, demonstrating superior handling of heterogeneous demands.
• Complexity: The algorithm maintains reasonable computational overhead (approx. 5 seconds per scheduling period on a standard CPU), making it suitable for offline computation with 40 ms time slots.

Significance
The paper positions this work as a practical solution for dynamic resource allocation in interference-limited LEO satellite networks. It addresses the trade-offs between the simplicity of heuristics, the global search capability of evolutionary algorithms, and the data-hungry nature of learning-based methods. By combining the memory mechanisms of Tabu Search with the probabilistic escape capabilities of Simulated Annealing, the proposed framework offers a scalable, robust, and interpretable approach to BH scheduling. The authors conclude that this strategy effectively balances local optimization efficiency with global searchability, providing a viable alternative for future intelligent BH control systems without the high computational and data costs associated with deep learning.