Frequency assignment problem with net filter discrimination constraints

H. Birkan Yilmaz, Bon Hong Koo, Sung Ho Park, Hwi Sung Park, Jae Hyun Ham, Chan Byoung Chae

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Managing radio spectrum resources is a crucial issue. The frequency assignment problem (FAP) basically aims to allocate limited number of frequencies to communication links in an efficient manner. Geographically close links, however, cause interference, which complicates the assignment, imposing frequency separation constraints. The FAP is closely related to the graph-coloring problem and it is an NP-hard problem. In this paper, we propose to incorporate the randomization into greedy and fast heuristics. As far as being implemented, the proposed algorithms are quite straight forward and are unencumbered by system parameters that need to be tuned whenever the system changes. The proposed algorithms significantly improve, quickly and effectively, the solutions obtained by greedy algorithms in terms of the number of assigned frequencies and the range. The enhanced versions of the proposed algorithms perform close to the lower bounds while running in a reasonable duration. Another novelty of our study is its consideration of the net filter discrimination effects in the communication model. Performance analysis is done by synthetic and measured data, where the measurement data includes the effect of the real 3-dimensional (3D) geographical features in the Daejeon region in Korea. In both cases, we observe a significant improvement by employing randomized heuristics.

Original languageEnglish
Article number8036656
Pages (from-to)329-340
Number of pages12
JournalJournal of Communications and Networks
Issue number4
Publication statusPublished - 2017 Aug

Bibliographical note

Publisher Copyright:
© 2011 KICS.

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Frequency assignment problem with net filter discrimination constraints'. Together they form a unique fingerprint.

Cite this