A Novel Frequency Allocation Algorithm for Limited Radio Resource Environments

In this paper, we investigate a frequency assignment problem from graph theory for military communications. We propose an algorithm based on the graph coloring theory and confirm that we utilize 0.77 times lower number of frequencies. We also propose a hybrid algorithm that facilitates a trade-off between the range and the spectrum utilization gain. I. 서 론 지휘체계와 타격체계간의 원활한 통신을 지원하는 전술통신망은 다수의 장비를 동시에 운용하기 때문에 주파수 자원이 부족하다. 또한 실시간으로 전장을 지 원하기 때문에 장비에 주파수를 배정하는 시간이 제 한된다. 따라서 이러한 전술통신망에서는 다수의 장비 들이 상호 간섭을 피하도록 주파수를 배정하면서, 배 정에 필요한 시간을 단축하고 주파수 재사용 효율을 높이기 위한 알고리즘이 필요하다. 기존의 연구에서는 주파수 지정을 위해 그래프 이론으로 접근하여, 탐욕 알고리즘과 유전자 알고리즘으로 해결하였다 . 탐욕 알고리즘은 계산량이 적은 장점을 가지고 있었지만, 주파수 효율을 보장하지 못 하는 하나의 해만을 도출 하였다. 유전자 알고리즘은 시간이 지날수록 주파수 효율이 더 나은 해를 찾을 수 있으나 소요시간이 대폭 증가하였다. 본 논문에서 제안하는 색칠 기반 알고리 즘은 사용하는 주파수의 개수를 이론적 최솟값에 가 깝게 단축함으로써 주파수 사용 효율을 극대화한다. 그러나 이때 주파수 사용 범위가 늘어나는 손해가 생 기므로 이를 보완하기 위해 탐욕 알고리즘과 색칠기 반 알고리즘을 복합적으로 사용하는 기법을 제안한다.