A Slot Allocation Algorithm for Survivability of Tactical TDMA Networks

TDMA architecture is the basis for many frontline tactical networking systems. TDMA provides predictable throughput and quality of service but, being based on static time slot assignments, is inflexible when communication requirements change. Changes can arise from unexpected data exchange requirements between participants or from platform failures during operation. This paper develops an incremental time slot allocation algorithm for Link 16, an advanced class of tactical TDMA network in widespread use. The algorithm finds the minimum cost change to an existing slot allocation that allows the new requirements to be met; a key feature is that it takes advantage of the existing time slot assignments to select changes that repair the network while minimizing the disruption experienced by network participants. The combinatorial optimization algorithm presented here, based on Lagrangean relaxation and simulated annealing, produced feasible solutions within 3% of optimal, on average. This approach may prove effective in other combinatorial optimization problems where the complexity of the problem constraints makes it difficult to find even a single feasible solution.