Incremental Time-Slot Assignment in SS/TDMA Satellite Systems

Abstract

In this paper we investigate the problem of incremental time-slot assignment for a satellite switched time division multiple access (SS/TDMA) satellite system in an heterogeneous traffic environment. The traffic in this environment can be categorized into two types: a rapidly changing type composed of packet-switched data traffic, and a relatively static type composed of circuit-switched voice traffic. From the time-slot assignment viewpoint, the problem is to construct an “efficient” TDMA frame that permits the static voice traffic to be transmitted and then, on a frame-by-frame basis to attempt to insert the data packets into the slots that are unused by the voice traffic. We prove that the problem is NP-complete, even for very simple traffic configurations. Several suboptimal fast heuristic algorithms are presented and empirically compared by experiments on randomly generated traffic patterns. The experiments reveal that, on the average, the algorithms give close to the optimal performance. © 1991 IEEE