A Scalable Algorithm for User Grouping in LEO-MEO-HEO Hybrid Very High Throughput Satellite Constellations

Satellite communications are transforming the when and how people can access broadband Internet, enabling connectivity in markets unreachable by terrestrial networks, such as isolated regions or connectivity on-the-go. Part of the new architectures' success relies on intricate hybrid constellation designs that combine multiple orbital shells at different altitudes, such as the SpaceX 4-shell LEO and the Boeing 10-shell LEO-MEO-HEO constellations. Under the new systems, satellite operators will need automated and scalable mechanisms able to efficiently group and distribute individual customers across satellites (the User Grouping problem) in order to maximize satellite utilization and achieve increased constellation capacity. While previous studies propose methods for single-altitude designs, algorithms for hybrid systems are yet to be developed. This work aims to breach this gap by 1) formulating the User Grouping problem for hybrid constellations as a Mixed Integer Linear problem, and 2) developing a scalable methodology tailored for high-dimensional scenarios. By using the SpaceX and the Boeing constellations as examples, this work demonstrates that the proposed approach can provide high quality solutions in feasible time for scenarios with up to 100,000 customers, which represents realistic operational conditions, with a minimum 77% reduction in maximum satellite load compared to methods for single-altitude designs.