Non-Contiguous Channel Allocation in Multi-Beam Satellites: Formulations, Upper Bounds and Cooperative Matheuristics
Abstract
Demand for wireless communication is growing, and commercial satellite services are expanding with it, increasing pressure on a finite radio spectrum. Allocation efficiency directly limits how many users a satellite can serve. We study how to assign frequency sub-channels to the carriers of a multi-beam satellite, maximising the total priority of admitted carriers while keeping each within its interference tolerance. Earlier work on this interference-limited channel allocation problem placed each carrier in a single continuous frequency block. Removing this restriction can admit more carriers, but a direct integer programming model cannot solve the largest test problems in practical time, so new methods are needed. We prove the problem computationally hard, reformulate it around how carriers share sub-channels, and derive three bounds on the optimum. We develop heuristics, including matheuristics combining local search with optimisation models, and an orchestrated portfolio that schedules them, recombines their solutions and stops early once its result is proven optimal or no longer improves. On 24 problems with up to 500 carriers, the best heuristics come within about 1% of the best known solution on average. The portfolio matches or exceeds the best heuristic for each problem on 23 of 24 with equal weights and 22 with priority weights, and is up to about 5% better on larger, more congested problems. It requires about a quarter of the time to run every heuristic and keep the best, and under half that of its heuristics run in a fixed order, which return slightly worse solutions on average.
Related
- Joint optimization of detection, task allocation, and path planning for multi-agent cooperative interception under partial observability
- Trajectory-Planning Attitude Control System for Satellites with Magnetic Attitude Control and One Reaction Wheel
- SateBeam: Beam-Aware Radio Map Estimation With Physics-Consistent Parametric Modeling for Unknown Multiple Satellites
- Geometric Analysis of Doppler-Based Navigation with Low Earth Orbit Satellites
- Satellites and invariants of links
BibTeX
@misc{gaudry2026noncontiguous,
title = {{Non-Contiguous Channel Allocation in Multi-Beam Satellites: Formulations, Upper Bounds and Cooperative Matheuristics}},
author = {Angus Gaudry and Vicky Mak-Hau},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17906},
eprint = {2610.17906},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17906},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Non-Contiguous Channel Allocation in Multi-Beam Satellites: Formulations, Upper Bounds and Cooperative Matheuristics
AU - Angus Gaudry
AU - Vicky Mak-Hau
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.17906
UR - https://arxiv.org/abs/2610.17906
AB - Demand for wireless communication is growing, and commercial satellite services are expanding with it, increasing pressure on a finite radio spectrum. Allocation efficiency directly limits how many users a satellite can serve. We study how to assign frequency sub-channels to the carriers of a multi-beam satellite, maximising the total priority of admitted carriers while keeping each within its interference tolerance. Earlier work on this interference-limited channel allocation problem placed each carrier in a single continuous frequency block. Removing this restriction can admit more carriers, but a direct integer programming model cannot solve the largest test problems in practical time, so new methods are needed. We prove the problem computationally hard, reformulate it around how carriers share sub-channels, and derive three bounds on the optimum. We develop heuristics, including matheuristics combining local search with optimisation models, and an orchestrated portfolio that schedules them, recombines their solutions and stops early once its result is proven optimal or no longer improves. On 24 problems with up to 500 carriers, the best heuristics come within about 1% of the best known solution on average. The portfolio matches or exceeds the best heuristic for each problem on 23 of 24 with equal weights and 22 with priority weights, and is up to about 5% better on larger, more congested problems. It requires about a quarter of the time to run every heuristic and keep the best, and under half that of its heuristics run in a fixed order, which return slightly worse solutions on average.
ER -