Efficient time-slot assignment algorithms for SS/TDMA systems with variable-bandwidth beams
S. Chalasani, A. Varma · 1991
The authors present efficient sequential and parallel algorithms for computation of time-slot assignments in SS/TDMA (satellite-switched/time-division multiple-access) systems with variable-bandwidth beams. These algorithms are based on modeling the time-slot assignment (TSA) problem as a network-flow problem. If M(N) is the number of uplink (downlink) beams, L is the length of any optimal TSA, and alpha is the maximum bandwidth of an uplink or downlink beam, the sequential algorithm takes O((M+N)/sup 3/ min (M N alpha , L)) time to compute an optimal TSA, when the traffic-handling capacity of the satellite is of the same order as the total bandwidth of the links. The parallel algorithm uses L/2 processors and has a time-complexity of O((M+N)/sup 3/ log L) on a probabilistic random access machine (PRAM) model of parallel computation. The authors then generalize this algorithm to P>