Frequency assignment problem with net filter discrimination constraints

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.