|
A Slot Allocation Algorithm for Survivability of Tactical TDMA Networks
April 2011
Jack Shaio, The MITRE Corporation
Jessica R. Piper, Stanford University
Jon Barto, The MITRE Corporation
ABSTRACT
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.
Additional Search Keywords
network survivability, combinatorial optimization, network optimization, slot allocation algorithm, tactical
networks, mathematical programming, simulated annealing
|
