Frequency allocation problem with generalized interference conditions
- 1 Head of Group, Geyser-Telecom LLC
Keywords:
frequency assignmentinterference conditionsNP-completenesstravelling salesman problempriority-basedheuristicsfrequency allocation
Abstract
The analysis of the publications concerned the frequency assignment problem shows that this problem is explored only with a special type of the interference conditions, which depends on the distance between frequencies. We consider the problem of frequency allocation while conflicts may take place on arbitrary frequency combinations. In this paper this problem is shown to be NP-complete. We present the heuristic polynomial time frequency allocation algorithm which assigns frequencies to high priority radioelectronic facilities first.
How to cite
Силин Д.М. Задача назначения частот с условиями взаимных влияний общего вида // Успехи современной радиоэлектроники. 2018. № 1. С. 28–35.
References
- Audrey D., Andréa L., Christian A., Dominique F., Philippe M., Michel V. The Dynamic Frequency Assignment Problem // European Journal Of Operational Research. Elsevier. 2008. URL: https://hal-univ-tlse3.archives-ouvertes.fr/hal-00119537/document.
- Solov'ev V.V. Metody optimal'nogo prisvoeniya chastot. M.: Izd-vo «NPF «Gejzer». 2000.
- Koster A.M.C.A. Frequency Assignment. Models and Algorithms // Proefschrift Universiteit Maastricht. 1999. URL: https://www.math2.rwthaachen.de/files/mitarbeiter/koster/Koster1999.pdf.
- Akho A., Khopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nykh algoritmov. M.: Mir. 1979.
- Kharari F. Teoriya grafov, M.: Mir. 1972.
- Kormen T.Kh., Lejzerson Ch.I., Rivest R.L., Shtajn K. Algoritmy. Postroenie i analiz. M.: Vil'yams. 2005.
- Kristofides N. Teoriya grafov (algoritmicheskij podkhod). M.: Mir. 1978.
- Korbut A.A., Fil'kenshtejn Yu.Yu. Diskretnoe programmirovanie. M.: Nauka. 1969.
- Gerardo M., Cristian P., Lucas R., Sergio N. A Parallel Evolutionary Algorithm applied to the Minimum Interference Frequency Assignment Problem // Workshop on Agents and Intelligent Systems. 2006. URL: https://www.fing.edu.uy/~sergion/ PEA_MIFAP.pdf.
- Karen I. Aardal, Stan P.M. Van Hoesel, Arie M.C.A. Koster, Carlo Mannino, Antonio S. Models and Solution Techniques for Frequency Assignment Problems // Konrad-Zuse-Zentrum für Informationstechnik Berlin. 2001. URL: http://home.deib.polimi.it/capone/radiomobili/materiale/frequency-assignment2.pdf.