Capacitated Beam Placement for Multi-beam Non-Geostationary Satellite Systems

Non-geostationary (NGSO) satellite communications systems have attracted a lot of attention, both from industry and academia, over the past several years. Beam placement is among the major resource allocation problems in multi-beam NGSO systems. In this paper, we formulate the beam placement problem as a Euclidean disk cover optimization model. We aim at minimizing the number of placed beams while satisfying the total downlink traffic demand of targeted ground terminals without exceeding the capacity of the placed beams. We present a low-complexity deterministic annealing (DA)-based algorithm to solve the NP-hard optimization model for near-optimal solutions. We further propose an extended variant of the previous model to ensure the traffic assigned to the beams is balanced. We verify the effectiveness of our proposed methods by means of numerical experiments and show that our scheme is superior to the state-of-the-art methods in that it covers the ground users by fewer number of beams on average.