Quantum Annealing-Based Algorithm for Efficient Coalition Formation Among LEO Satellites

随着制造和发射成本的降低，低地球轨道（LEO）卫星的数量不断增加，对地球观测任务和低延迟互联网连接非常有价值。然而，随着卫星数量的增加，需要维护的通信链路数量也随之增加，使得管理这个庞大网络变得越来越具有挑战性，并突显出将卫星聚类成高效组的需求，作为一个有前途的解决方案。本文将LEO卫星聚类问题形式化为联盟结构生成（CSG）问题，并利用量子退火来解决它。我们将卫星网络表示为一个图，并使用名为GCS-Q的混合量子-经典算法来获得最佳分区。该算法采用自上而下的方法，通过使用二次无约束二进制优化（QUBO）公式在每个步骤上迭代地分割图。为了评估我们的方法，我们利用Celestrak的Starlink卫星的真实三行元素集（TLE/3LE）数据。我们使用D-Wave Advantage退火器和最先进的求解器Gurobi进行实验，结果表明，量子退火器在运行时间方面显著优于经典方法，同时保持解决方案的质量。量子退火器实现的性能超过了经典计算机的能力，突显了量子计算在优化大规模卫星网络管理方面的变革潜力。

论文旨在解决LEO卫星网络日益增长所带来的通信链路管理问题，提出了一种基于量子退火的卫星聚类算法。

论文将卫星网络表示成图的形式，使用量子退火算法进行卫星聚类，通过迭代分割图的方式进行优化。

论文使用实际的卫星数据进行了实验验证，结果表明量子退火算法在运行时间和解决方案质量上都优于经典算法。论文的方法具有实际应用价值，同时也展示了量子计算在优化大规模卫星网络管理方面的潜力。

近期相关研究包括：1. A Survey of Satellite Networks: Challenges and Opportunities；2. Satellite constellation design with evolutionary algorithms；3. A Game-Theoretic Approach to Satellite Constellation Optimization。