User Scheduling in Satellite Return Links - A Perfect Graph Paradigm

Abstract

Current satellite systems offer flexibility with respect to resources such as frequency and time. Building upon this flexibility the present paper investigates the general problem of scheduling users attempting to access a channel in a TDMA scheme. In particular, the MF-TDMA paradigm encountered in the DVB-RCS2 standard is examined, where different user terminals request access to the satellite return channel, for a given traffic demand. The problem is reduced to the maximum weight independent set problem for perfect graphs, demonstrating that the problem is solvable in polynomial time, by the ellipsoid method for linear programming techniques. This formulation of the problem allows the devise of efficient optimization algorithms tackling complex satellite resource allocation problems, while also attaining polynomial time solutions for the maximization of the aggregate traffic of users scheduled in a TDMA scheme.