Dynamic Balance-Based Clustering in Ultra-Dense LEO Satellite Networks

Ultra-dense LEO satellite networks (UDLSNs) have become a possible solution to achieve global coverage for highspeed data services. However, the high density of satellites results in severe inter-satellite interference, significantly affecting the network capacity. To tackle this problem, dividing numerous satellites into multiple clusters enables cooperative satellite management. For such highly dynamic networks, existing clustering methods deal with the problem separately for each snapshot, leading to the instability of the clusters and additional handover latency. This paper proposes a clustering algorithm based on multi-snapshot processing, i.e., spectral clustering with weighted bipartite graph matching and handover occasion decision algorithm (SCWB-HODA), to reduce the total network latency. In detail, the SCWB method realizes low complexity clustering while promising load balancing and interference avoidance. Due to the disorganized handovers of satellites between clusters, the method of judging whether to execute a handover based on a single snapshot will lead to frequent cluster variations. To enhance the cluster stability and suppress handover latency, the HODA method determines multiple candidate snapshots based on predictable satellite trajectories and selects the suitable snapshot for each satellite to achieve handover synchronization. Compared with baseline algorithms, the proposed SCWB-HODA can reduce the handover latency and improve the cluster stability by about 20%, which benefits from multi-snapshot processing