The frequency assignment problem belongs to the class of NP-complete. Therefore it is necessary to use more time efficient algorithms which cannot guarantee optimal solution. Thus, if we can find more time efficient method to obtain a lower bound which is closer to the optimum, a lower bound obtained by this method can be a good information on how far away a feasible solution is from the optimum and on what heuristic approach is effective for a frequency assignment problem with specific structure.
The objective of this thesis is to suggest a new lower bounding method for the frequency assignment problem by using frequency-insert concepts such as natural insert and push-insert. In natural insert scheme, requirements can be assigned to the unused frequencies without increasing the span. However, push-insert can assigns the unused frequencies to requirements only with increasing the current span. A lower bound is obtained by solving simple maxinmal flow problems to find out upper bounds on the number of frequency-inserts and natural inserts.
Compared with some of lower bounds suggested by Gamst, the new lower bound obtained by this method is proved to be closer to the optimum. And it can be seen easily that this method is more time efficient.
최근 주파수에 대한 수요는 급속도로 증가하고 있으나 주파수사용에 대한 획기적인 기술적 발전이 없는 한 주파수자원은 제한되어 있다. 따라서 주파수의 할당은 셀룰라시스템의 효율성을 좌우하는 개발과 설계의 중요한 단계로 인식되고 있다.
주파수할당문제(Frequency Assignment Problem)는 최소한의 서비스품질을 보장하기 위한 각 셀에 필요한 주파수의 수와 두 셀에 할당되는 주파수간의 최소한의 간격이 주어져 있을 때, 이를 만족하기 위해 최소한 몇 개의 주파수가 필요하며 실제 할당은 어떻게 해야 하는가를 구하는 것이다. 주파수할당문제는 그래프채색문제(Graph Coloring Problem)와 동일하며 이 들은 모두 NP-complete임이 알려져 있다. 그러므로 일반적인 주파수할당문제의 최적해는 수리적으로 구하기는 어려우며, 따라서 최적은 보장되지 않더라도 짧은 시간에 최적에 가까운 해를 구하는 휴리스틱 알고리즘들이 제시되어 있을 뿐이다. 또한 이러한 알고리즘은 실행가능한 해가 최적해에 얼마나 가까운가에 대한 정보는 전혀 제공하지 못하고 있다.
Gamst는 이러한 정보의 기준을 제공하기 위하여 주파수할당문제에 있어서 최소필요 주파수의 수(하한)를 주파수할당문제의 특성을 이용하여 이론적으로 제시하였다. 여기에서 고려하는 하한은 셀들의 υ-완전부분집합(υ-complete subset, Q)에 속한 수요들을 가장 효율적으로 주파수를 할당했을 때 이 들이 차지하는 span을 하한으로 정의한다. Gamst가 제시된 한 하한을 검토해 본 결과 가정을 만족시키는 과정에서 많은 계산량이 요구되고 최적해에서 많은 차이가 있음을 확인할 수 있었다.
본 논문은 이 하한을 구하는 과정에서 설정한 가정을 완화하여 보다 일반적인 경우에 적용가능하고, 가정을 만족시키는 셀들의 집합을 구하는 데 필요한 계산량을 줄이고자 하였다. 또한 Frequency-insert라는 개념을 도입하여 보다 최적해에 가까운 하한을 정의하고자 하였다. Frequency-insert는 두가지로 분류될 수 있다. 이 중 natural insert는 셀의 υ'-완전부분집합(R, 여기서 $\nu = k\nu + \nu_0 , 0<\nu_0\le \nu$)에 이미 할당된 주파수들 사이의 사용되지 않은 주파수를, Q|R의 아직 할당받지 않은 수요에, 현재까지의 할당이 차지하는 span을 늘리지 않고도 가능한 할당을 일컫는다. 반면, push-insert는 현재까지의 할당이 차지하는 span을 $\nu-\nu_0$ 만큼 늘려야만 가능한 할당을 말한다. Frequency -insert로써 불가능한 수요는 부득이 span을 $\nu$만큼 늘이면서 할당하는 수 밖에 없다. 따라서 natural insert를 통한 할당의 수를 최대한으로 하고 다음으로 push-insert를 통한 할당을 최대한 많이 하는 것이 유리하다. 그러나 R에 속한 수요들에 주파수를 어떻게 할당하느냐에 따라 가능한 frequency-insert, natural insert의 수가 달라지므로 이 들을 정확히 구할수는 없다. 이러한 문제점을 해결하기 위하여 이들 값의 상한들을 최대흐름문제(Maximal flow problem)로 구하여 실제 가능한 수보다 많은 수요가 frequency-insert로 할당되었다고 가정하면 원래문제의 하한을 정의할 수 있다.
실제 예를 들어 비교해 본 결과, 실제로 가능한 frequency-insert의 수와 이의 상한과는 큰 차이가 없었고 새로운 하한의 계산상의 개선과 최적해에 보다 근접함을 확인할 수 있었다.
