Overview
The Aidos algorithm is proposed for beam hopping (BH) scheduling in non-geostationary orbit (NGSO) mega-constellations. This algorithm addresses the challenge of real-time generation of beam hopping time plans (BHTP) in multi-satellite, multi-coverage scenarios. Aidos integrates traffic-aware random-key encoding into a multi-objective metaheuristic search and employs a sliding-window Beta resampling strategy during adaptive distribution evolution. This approach aims to enhance both the search efficiency and the solution quality of BHTP.
Research Context
The proliferation of NGSO mega-constellations necessitates beam hopping for resource scheduling. Beam hopping facilitates efficient spectrum utilization by dynamically adjusting spot beam power and pointing within individual time slots. A primary engineering challenge involves generating BHTPs in real-time. Traditional methods, such as the round-robin strategy, distribute beams uniformly across service cells. However, actual traffic exhibits a long-tail distribution, with approximately 10% of hotspot cells generating over 50% of the total demand, rendering uniform allocation insufficient.
Existing frameworks utilize genetic algorithms (GA) to address this issue, achieving approximately 80.7% higher throughput compared to traditional baselines. For operational satellite footprints comprising over 1,000 service cells, a GA requires 67.8 seconds to generate a BHTP for 1,127 cells. Given a 300-second visibility window for a 550 km Low Earth Orbit (LEO) satellite, multiple online recomputations using GA are impractical. State-of-the-art algorithms, such as multi-agent deep reinforcement learning (MADRL), encounter convergence issues when the cell count surpasses 200.
Approach
The Aidos algorithm is designed to overcome the limitations of existing BH scheduling methods. It incorporates two main components:
- Traffic-aware random-key encoding: This component is integrated into a multi-objective metaheuristic search to guide the optimization process.
- Sliding-window Beta resampling strategy: This strategy is applied during adaptive distribution evolution to improve search efficiency and the quality of the generated BHTPs.
Findings
Experiments with the Aidos algorithm demonstrated several performance improvements:
- Aidos improved throughput by 79.2%.
- The algorithm reduced latency by 99.45%.
- The average computation time for Aidos was 9.3 seconds.
This computation time is within the constraints of a 300-second satellite overpass window, enabling online replanning.
Why This Matters
The ability of Aidos to generate BHTPs within 9.3 seconds addresses the real-time constraints associated with LEO satellite visibility windows. This allows for online replanning, which is crucial for dynamically adjusting beam allocation based on varying traffic demands in NGSO mega-constellations. The improvements in throughput and reductions in latency facilitate more efficient spectrum utilization and resource management in complex multi-satellite, multi-coverage environments.