Frequency allocation problem in a SDMA satellite communication system

Spatial Division Multiple Access (SDMA) is a principle of radio resource sharing that relies on the division of the space dimension into separated communication channels. SDMA basically relies on adaptive and dynamic beam-forming associated to a clever algorithm in charge of resource allocation. As satellite communication systems move towards an increasing number of users and a larger throughput for each of them, SDMA is one of the most promising techniques that can reach these two goals. This paper studies static Frequency Assignment Problems (FAP) in a satellite communication system involving a gateway connected to a terrestrial network and some user terminals located in a service area. Two scenarios are considered: one based on SDMA and the other based on usual spot coverage. We propose original integer linear programming formulations and greedy allocation algorithms for the FAP which involves unusual cumulative interference constraints. By considering the link budget of each user, the objective is to maximize the number of users that the system can serve. We show through computational experiments on realistic data that the FAP associated with the SDMA system can be solved efficiently, yielding substantial improvement compared to the traditional system.