Allocation of QoS connections in MF-TDMA satellite systems: a two-phase approach

We address the problem of providing guaranteed quality-of-service (QoS) connections over a multifrequency time-division multiple-access (MF-TDMA) system that employs differential phase-shift keying (DPSK) with various modulation modes. The problem can be divided into two parts--resource calculation and resource allocation. We present algorithms for performing these two tasks and evaluate their performance in the case of a Milstar extremely high frequency satellite communication (EHF-SATCOM) system. In the resource-calculation phase, we calculate the minimum number of timeslots required to provide the desired level of bit-error rate (BER) and data rate. The BER is directly affected by the disturbance in the link parameters. We use a Markov modeling technique to predict the worst case disturbance over the connection duration. The Markov model is trained offline to generate a transition-probability matrix, which is then used for predicting the worst case disturbance level. We provide simulation results to demonstrate that our scheme outperforms the scheme currently implemented in the EHF-SATCOM system. The resource-allocation phase addresses the problem of allocating actual timeslots in the MF-TDMA channel structure (MTCS). If we view the MTCS as a collection of bins, then the allocation of the timeslots can be considered as a variant of the dynamic bin-packing problem. Because the this problem is known to be NP-complete, obtaining an optimal packing scheme requires a prohibitive amount of computation. We propose a novel packing heuristic called reserve channel with priority (RCP) fit and show that it outperforms two common bin-packing heuristics. Index Terms--Bin packing, Markov modeling, multifrequency time-division multiple-access (MF-TDMA), prediction, quality of service (QoS), resource allocation, satellite.