Definition of a Common Formulation of Military Frequency Assignment Problems and the Application of Meta-Heuristic Algorithms

  • James Graham

    Student thesis: Doctoral Thesis


    The purpose of this research is to define a common formulation for military frequency assignment problems, in a form which allows the application of meta-heuristic algorithms. Currently different frequency assignment systems are in use in the four areas of the military, in the categories of land, air, maritime and satellite. The tasks are to define the common aspects of the relevant frequency assignment problems in the four areas and then to implement a piece of software that may tackle all of these problems with little or no loss in performance when compared to existing frequency assignment problem solving systems. Much work has been done over the years in developing new and more efficient techniques to solve military frequency assignment problems. It has never been attempted to create a generic system to handle all types of problems.

    This thesis contains a general background to military and terrestrial frequency assignment problems, with relevant literature referenced. The majority of military frequency assignment systems rely heavily on the solving of binary constraints as they have been proved to be extremely efficient. This research uses a combination of binary constraints and signal-to-interference calculations to solve frequency assignment problems. The signal-to-interference techniques are more accurate than the use of binary constraints only, as signal-to-interference considers interference from multiple sources while the binary constraints only handle single sources of interference. Although signal-to-interference techniques are slower than the use of binary constraints, this research has shown that, if used in the correct context, signal-to-interference techniques substantially improve network performance with acceptable performance. Appropriate propagation models have been used to generate test data; these models are presented in the thesis.

    The model presented in this research addresses the assignment of multiple carrier types. These carrier types consist of homogeneous narrow band carrier types, aggregated channel carriers, heterogeneous wide band carrier types, CDMA carriers, unsynchronised frequency hopping carriers and synchronised frequency hopping carriers. Test data has been generated that includes all of these carrier types in a frequency assignment problem. The model incorporates a weighted linear cost function consisting of binary constraint violations, signal-to-interference based cost, frequency hopping list costs,and costs associated with spurious emissions, spurious responses, and intermodulation products. The research focused on the use of the simulated annealing meta-heuristic algorithm to solve the frequency assignment problems presented here. The algorithm can use any linear combination of the first three components of the cost function as listed above, and could optionally include the last three.

    The experiments performed and presented in the thesis have shown that the assignment of multiple carrier types in a single frequency assignment problem solving system is possible. Signal-to-interference techniques can be employed to further improve network performance when combined with binary constraints and that, most importantly, a model of the common formulation of military frequency assignment can be implemented with acceptable performance. The experiments also show that signalto-interference techniques are best used in conjunction with binary constraints. The binary constraints should be used to create an initial assignment which can then be improved by signal-to-interference techniques. For this purpose it appears that binary constraints are best generated at a required signal-to-interference threshold 2-4dB higher than the threshold required for the network.

    This research, as described above, represents an original contribution in the area of military radio frequency assignment through the pursuit of a common formulation of the four military areas of frequency assignment. The merit of this approach is that advances in frequency assignment algorithms can be applied directly to all of the problems encompassed. This has clear advantages over the separate development of techniques for individual problem areas.
    Date of AwardApr 2005
    Original languageEnglish
    SupervisorDerek Smith (Supervisor) & Jim Moon (Supervisor)

    Cite this