S. Chalasani et A. Varma, EFFICIENT TIME-SLOT ASSIGNMENT ALGORITHMS FOR SS TDMA SYSTEMS WITH VARIABLE-BANDWIDTH BEAMS/, IEEE transactions on communications, 42(2-4), 1994, pp. 1359-1370
In this paper, we present efficient sequential and parallel algorithms
for computation of time-slot assignments in SS/TDMA (satellite-switch
ed/time-division multiple-access) systems with variable-bandwidth beam
s. These algorithms are based on modeling the time-slot assignment(TSA
) problem as a network-flow problem. Our sequential algorithm, in gene
ral, has a better time-complexity than a previous algorithm due to Gop
al, et al. [4] and generates fewer switching matrices. 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, ou
r sequential algorithm takes O((M + N)3 min(MNalpha,L)) time to comput
e an optimal TSA when the traffic-handling capacity of the satellite i
s of the same order as the total bandwidth of the links. Our parallel
algorithm uses L/2 processors and has a time-complexity of O((M + N)3
log L) on a PR AM model of parallel computation. We then generalize th
is algorithm to P less-than-or-equal-to L/2 processors and describe an
efficient implementation of the algorithm on a hypercube multiprocess
or with P processors. A massively-parallel version of the algorithm ru
ns in O((M+N)2 log(M+N)logL) time on (M+N)L/2 processors.