Column Generation for Action-Based Group Handover Optimization in Large-Scale LEO Satellite Networks

Low Earth orbit (LEO) satellite constellations are an important component of non-terrestrial networks (NTNs) in future sixth-generation (6G) systems, owing to their wide coverage and low propagation delay. However, due to the high-speed orbital movement of LEO satellites, the serving satellites of massive ground terminals change frequently, resulting in frequent and highly concurrent handover requests. Existing group handover methods usually follow a two-stage paradigm that first forms terminal groups according to similarity features and then performs target satellite selection or handover scheduling for the pre-formed groups. Such a grouping-first strategy may restrict the group handover action space and exclude potentially better terminal-satellite-slot combinations from consideration. To address this issue, this paper proposes an executable-action-based group handover paradigm, where terminal grouping, target satellite selection, and handover-slot assignment are unified in the action construction process. Based on this formulation, the group handover problem is modeled as a large-scale combinatorial optimization problem. To solve it efficiently, this paper proposes a Group Handover Action Column Generation (GHACG) algorithm. In the column generation framework, the algorithm starts from a restricted set of executable actions and iteratively solves the corresponding restricted master problem. The obtained dual prices are then used to guide heuristic pricing to generate high-value executable action columns, and an integer action recovery procedure is designed to obtain a feasible group handover scheme. Simulation results show that GHACG outperforms representative single-user and group handover baselines in terms of handover success rate, signaling overhead, number of group handover actions, handover rate, and handover objective value J. Under the largest simulated terminal scale of 1.2 × 105, GHACG improves the handover success rate by 11.17% compared with the best-performing baseline.