An Optimum Time Slot Assignment Algorithm for an SS/TDMA System with Variable Number of Transponders

In this paper we consider an SS/TDMA system with M uplink beams, N downlink beams, and K, 1 ≤ K ≤ min (M, N) transponders. An optimal time slot assignment algorithm for any M, N, K, and any traffic matrix is presented, where optimality means achieving the minimal possible total duration for the given traffic matrix. The number of switching matrices generated by the algorithm is bounded above by N2 — N + 1 for K = M = N and MN + K + 1 otherwise. Extensive simulation results on randomly generated matrices are carried out, showing that the average number of switching matrices generated is substantially lower than the bounds. Copyright © 1981 by The Institute of Electrical and Electronics Engineers, Inc.