Book contents
- Frontmatter
- Contents
- Contributors
- Introduction
- I NUMBER THEORETIC ASPECTS OF CRYPTOLOGY
- II CRYPTOGRAPHIC DEVICES AND APPLICATIONS
- 7 Security in telecommunication services over the next decade
- 8 Linear feedback shift registers and stream ciphers
- 9 Applying randomness tests to commercial level block ciphers
- 10 Pseudo-random sequence generators using structured noise
- 11 Privacy for MACNET
- 12 Authentication
- 13 Insecurity of the knapsack one-time pad
- 14 The tactical frequency management problem: heuristic search and simulated annealing
- 15 Reed-Solomon coding in the complex field
- PART III DIOPHANTINE ANALYSIS
14 - The tactical frequency management problem: heuristic search and simulated annealing
Published online by Cambridge University Press: 05 May 2013
- Frontmatter
- Contents
- Contributors
- Introduction
- I NUMBER THEORETIC ASPECTS OF CRYPTOLOGY
- II CRYPTOGRAPHIC DEVICES AND APPLICATIONS
- 7 Security in telecommunication services over the next decade
- 8 Linear feedback shift registers and stream ciphers
- 9 Applying randomness tests to commercial level block ciphers
- 10 Pseudo-random sequence generators using structured noise
- 11 Privacy for MACNET
- 12 Authentication
- 13 Insecurity of the knapsack one-time pad
- 14 The tactical frequency management problem: heuristic search and simulated annealing
- 15 Reed-Solomon coding in the complex field
- PART III DIOPHANTINE ANALYSIS
Summary
The Tactical Frequency Management Problem is an example of the general Consistent Labelling Search Problem where frequencies and other communications data need to be assigned to mobile radio users in a dense deployment on a daily basis, such that the resulting mutual Electromagnetic Interference is minimised. This paper presents a qualitative description of three quite different methods for solving this problem. The first is based on the manual procedure historically used by communications planners. The second is based on a classical heuristic search algorithm employing backtracking and forward checking—a typical Artificial Intelligence approach. The third approach uses an algorithm which is a mathematical analogue to the physical process of annealing a molten metal—heating it and then cooling it so as to let it crystallise into its lowest energy state.
Introduction
The Frequency Management Problem is a special case of a general NP-Complete problem called the ‘Consistent Labelling Problem” [8] or the ‘Constraint Satisfaction Problem’ [3], in either case abbreviated as CLP. This problem consists of a list of N units (or ‘variables’), U = (u1, u2,…,uN), each unit having a set L = (L1,L2,…,LM) of M possible labels (or ‘values’). A consistent labelling f is a relation f: U → L such that for each pair of units and assigned labels, the required constraints are satisfied.
- Type
- Chapter
- Information
- Number Theory and Cryptography , pp. 165 - 174Publisher: Cambridge University PressPrint publication year: 1990