셀룰러 네트워크에서의 채널 할당 문제의 향상된 하한 값 분석

급격히 증가하고 있는 무선 통신에 대한 수요의 증가는 제한된 주파수 자원을 효과적으로 이용하여 수요 증가를 수용하기 위한 방안이 필요하게 되었고 이를 위해 진행되는 여러 가지 연구 중에 주파수 채널 할당 (frequence channel assignment) 문제가 더욱 중요하게 고려되어 이 문제에 대한 연구가 여러 가지 각도에서 활발하게 진행되고 있다[1, 2].
셀룰러 네트워크에서는 지리적인 영역을 나누어서 서비스를 하고 있는데 이 서비스 영역은 종종 육각형의 셀룰러 영역(셀이라 부름)으로 표시되어진다. 각 셀은 그 셀 내에 위치하는 이동 통신 클라이언트들의 통신을 관리하는 기본 스테이션(base station)을 가운데 가지고 있으며 이 기본 스테이션은 다른 셀에 있는 스테이션과의 통신을 통하여 자신의 서비스 영역의 클라이언트가 적은 파워의 단말기를 가지고도 먼 곳의 다른 사용자와의 통화를 가능하게 해준다. 각각의 클라이언트의 호출(call)이 있을 때 관계하는 기본 스테이션이 특정 주파수 채널을 할당시키는데, 인접한 셀 간에 같은 채널을 할당시킨 경우 채널 간섭(interference)을 야기 시킬 수 있다. 주파수의 대역폭(bandwidth)을 효과적으로 공유하기 위해서 채널들은 가능한 한 재사용 되어야 하며 채널들을 선택할 때에는 상호-채널 간섭(co-channel interference)이나 이웃 채널 간섭(adjacent channel interference)이 일어나지 않도록 해야 한다. 채널 재사용가능 거리(L)이란 셀 간의 거리가 적어도 L이라면 두 셀 간에 채널 간섭을 초래하지 않고 채널이 재사용 될 수 있는 거리를 말한다. 여러 가지 채널 간섭을 고려한 채널 할당 문제들은 그래프 이론의 컬러링 문제로 생각할 수 있는데 이때 문제에 따라 주어지는 조건이 다르고 그에 맞는 컬러링을 찾아야 한다[3, 4].