Journal Achievements of Modern Radioelectronics №1 for 2018 г.
Article in number:
Frequency allocation problem with generalized interference conditions
Type of article: scientific article
UDC: 004.021
Keywords: frequency assignment; interference conditions; NP-completeness; travelling salesman problem; priority-based; heuristics; frequency allocation.
Authors:

D.М. Silin – Head of Group, Geyser-Telecom LLC  E-mail: dsln@mail.ru

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.

Pages: 28-35
References
  1. 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. 
  2. Solov'ev V.V. Metody optimal'nogo prisvoeniya chastot. M.: Izd-vo «NPF «Gejzer». 2000.
  3. 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.
  4. Akho A., Khopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nykh algoritmov. M.: Mir. 1979.
  5. Kharari F. Teoriya grafov, M.: Mir. 1972.
  6. Kormen T.Kh., Lejzerson Ch.I., Rivest R.L., Shtajn K. Algoritmy. Postroenie i analiz. M.: Vil'yams. 2005.
  7. Kristofides N. Teoriya grafov (algoritmicheskij podkhod). M.: Mir. 1978.
  8. Korbut A.A., Fil'kenshtejn Yu.Yu. Diskretnoe programmirovanie. M.: Nauka. 1969.
  9. 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.
  10. 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.

 

Date of receipt: 8 ноября 2017 г.