Frequency assignment algorithms have relation with the use of a recently developed technique based on the theory of graph coloring.
Numerous algorithms exist for frequency assignment problems, it should be capable of accommodating as many users as possible with the limited frequency resource available.
We introduce a new algorithm for frequency assignment problem. First, we define the difficulty measure of nodes that is based on new definition of node subsets. Next, we attempt to classify four essential assignment methods.
By using the defined difficulty measure and assignment methods, we construct a new algorithm which include a new assignment concept, so called push-insert. In addition, we show that the algorithm is very useful in solving for the frequency assignment problem.
이동통신 서비스의 수요는 폭발적으로 증가하는데 반하여 이를 위해 할당된 주파수 자원은 한정되어 있으므로, 이같은 주파수자원의 효율적인 이용에 대한 관심이 증가하고 있다. 이러한 목적을 위해 셀룰러 이동통신시스템(cellular mobile telecommunications system)은 한정된 주파수 자원을 효율적으로 활용하여 가입자 용량을 극대화시키기 위해 셀분할(cell spliting)과 주파수 재사용(frequency reuse)이라는 두가지 중요한 개념을 도입하고 있다.
어떤 셀룰러 시스템에서 셀들이 주어져 있고, 셀들의 채널 수요가 주어져 있을 때 이러한 셀들이 적절한 주파수 간섭수준을 만족할 수 있도록 어떤 채널을 할당할 것인가 하는 것이 주파수 할당 문제(FAP)이다.
이러한 FAP는 최근에 발달된 그래프 칼라링 문제로 변화시킬 수 있다. 이에 근거한 많은 휴리스틱 해법이 제안되고 있지만 만족할 만한 결과를 항상 제공하지는 못하고 있다. 본 논문에서는 기존의 해법들의 문제점을 파악하고 새로운 해법을 제시하고 있는데 이를 push-insert 해법이라 한다. 이 해법은 먼저 전체 노드집합을 네개의 부분집합으로 하고, 이를 이용하여 각 노드간의 할당 순서를 정한다. 그리고 할당방법으로 네가지 분류하여 제시하고 있는데, 처음의 세가지는 기존의 해법들이 이용하고 있는 방법이며 나머지 하나는 처음으로 제시되고 있는 할당 방법인데 이를 push-insert방법이라고 한다.
그리고 push-insert해법을 이용하여 FAP문제들에 대한 계산결과를 보여주고 있는데, 이 결과에서 알 수 있듯이 이 해법이 기존의 해법에 비해 만족할 만한 결과를 제공함을 알 수 있다.
