섹터 간 간섭 정도를 이용한 최적의 주파수 할당 방법 document_id A220623014908

본 발명은 섹터 간 간섭 정도를 이용한 최적의 주파수 할당 방법에 관한 것으로, 더욱 상세하게는 섹터 간의 간섭(Interference)을 계산하여 임계치와 비교한 후 일 섹터를 기준으로 인접 섹터와 비인접 섹터를 구분하여, 인접 섹터에는 상기 일 섹터와 서로 다른 주파수를 할당하고, 비인접 섹터에는 임의의 사용 가능한 주파수를 할당함으로써, 짧은 수행시간 내에 각 섹터별로 최적의 주파수를 할당하기 위한, 섹터 간 간섭 정도를 이용한 최적의 주파수 할당 방법에 관한 것이다. 본 발명에서 기지국은 여러 개의 섹터를 포함하는 장비가 위치한 철탑이나 건물 등 위치를 나타내는 시설물들을 의미하며, 섹터는 실제로 서비스를 하기 위한 안테나 및 송수신 장치를 의미한다. GSM(Global System for Mobile communication) 시스템 등과 같이 FDMA(Frequency Division Multiple Access) 방식을 사용하는 통신 시스템에서, 주파수는 매우 중요한 자원이면서 한정된 자원이다. 따라서 급증하는 가입자를 지원하기 위해서는 기지국의 신설 또는 이동 등이 불가피한데, 이렇게 이동된 기지국의 위치 및 추가된 기지국들에 의해 네트워크의 간섭 상황이 변경된다. FDMA 통신 시스템은 각각의 사용자 신호를 각각 다른 주파수에 실어 송신함으로써, 여러 사용자가 동시에 통신할 수 있도록 하기 때문에, 같은 주파수 또는 인접 주파수에 의한 간섭은 통신 품질을 현저히 떨어뜨리는 가장 큰 요인으로 작용한다. 따라서 이러한 변화가 생기는 경우 네트워크 관리자는 주파수의 추가 또는 조정 등의 작업을 수행하여 동일 또는 인접 주파수에 의한 간섭을 최소화하여야 하는데, 이러한 작업을 주파수 플래닝(Frequency Planning)이라 한다. 그러나 성공적인 주파수 배치는 그다지 쉬운 작업이 아니다. 특히, 주파수가 한정되어 있으므로 주파수를 재사용하여야 하는데, 이를 위해서는 주변 기지국의 전파 세기, 할당된 주파수 등의 정보를 종합적으로 분석해야 한다. 이러한 분석결과를 토대로 수십에서 수천 개에 이르는 기지국에 간섭이 최소화되도록 주파수를 배정하는 과정은, 매우 반복적이고 복잡하여 쉽게 그 최적의 결과를 얻어낼 수 없다. 이러한 과정을 셀 플래닝 툴(Cell Planning Tool)에서 자동으로 수행하고자 하는 것이 자동 주파수 플래닝(Automatic Frequency Planning) 알고리즘이다. 자동적으로 주파수를 할당함에 있어서 최적의 해는 동일 또는 인접 주파수에 의한 간섭이 없도록 하거나 최소화하는 해를 의미하는데, 이러한 상황을 만족시킬 수 있는 해는 여러 개가 존재할 수 있어, 효율적으로 최적의 해를 찾는 것은 매우 어려운 일이다. 이와 같은 문제에 대한 해결 방법은 이전부터 많은 논의가 되어 왔는데, '외판원의 방문 문제'와 같은 것이 그 대표적인 예이다. 그러나 아직까지 이렇다 할 방법이 제시되지 못하고, 대체로 유전자 알고리즘(Genetic Algorithm)을 적용하여 '납득할 만한 근사의 최적'을 찾는 방법이 사용되고 있는 실정이다. 이러한 유전자 알고리즘(Genetic Algorithm)은 진화연산 알고리즘으로서, 자연계의 생명체 중 환경에 잘 적응한 개체가 좀더 많은 자손을 남길 수 있다는 자연선택 과정과 자연계의 생명체의 설계도와 같은 유전자의 변화를 통해서 좋은 방향으로 발전해 나간다는 자연진화의 과정을 모방하여 컴퓨터로 모의 수행을 하는 최적화 알고리즘의 하나이다. 즉, 실세계의 문제를 풀기 위해 잠재적인 해들을 컴퓨터상에서 코딩된 개체로 나타내고, 다수의 개체들을 모아 개체군을 형성한 뒤, 세대를 거듭하면서 이들의 유전 정보를 서로 교환하거나 새로운 유전 정보를 부여하면서 적자 생존의 법칙에 따라 모의 진화를 시킴으로써, 주어진 문제에 대한 최적의 해를 찾는 계산 모델이다. 이러한 진화연산 알고리즘의 장점은 목적 함수의 미분과정이나 특별한 수학적 연산을 필요로 하지 않고, 점에 의한 탐색이 아니라 개체들이 모여 이루는 개체군에 의한 병렬적인 탐색이라는 점을 들 수 있다. 특히, 한 세대의 개체군에 속한 개체들은 진화를 거듭하면서, 이전 세대까지 축적된 정보를 서로 교환하고 새로운 영역으로의 탐색을 시도함으로써, 최적의 값이 탐색의 방향이나 영역의 초기값에 의해서 결정되지 않고 세대마다 확률적으로 결정되므로, 지역 최소점에 빠질 가능성이 적어 전역 최적화가 가능한 알고리즘으로 알려져 있다. 그러나 진화연산 알고리즘은 반복(iteration) 과정에서 발생하는 비효율성 및 변수의 제한조건으로 인하여 해를 찾는데 많은 시간이 소요되므로, 사용자가 정해진 일정에 맞춰 결과를 얻어낼 수 없게 하는 문제점이 있다. 따라서 본 발명에서는 유전자 알고리즘(Genetic Algorithm)이 아닌 브루트-포스(Brute-force) 방식에 기반하여 자동 주파수 플래닝(Automatic Frequency Planning)의 해를 찾는 방법을 제안한다. 여기서, 브루트-포스(Brute-force) 방식은 주어진 상황에서 최적으로 예측되는 해를 택하고 이를 추후의 재고 없이 결정해 나가는 방식으로, 항상 최적의 해가 얻어지는 것은 아니지만 별도의 재고 과정 없이 한 번의 진행만으로 해를 얻을 수 있기 때문에, 중간 단계에서 최적의 해를 예측하기 쉬운 문제에서는 가장 효율적이며 시간을 절약할 수 있다. 이때, 브루트-포스(Brute-force) 방식만으로는 주파수 플래닝(Frequency Planning)의 최적의 해를 얻기 어렵기 때문에, 간섭 그래프(Interferer Graph)와 주파수 재사용(Frequency Reuse) 알고리즘을 함께 사용하여 최적에 가까운 결과를 얻는다.