Recently, in cellular mobile communication systems, the traffic demand has remarkably increased in spite of the limited radio frequency spectrum. Hence it is a very critical problem to use the limited spectrum in the most economical way. As an effort to solve this problem, this study investigates efficient algorithms for frequency assignment problem (FAP) in the cellular systems.
First, this study considers the FAP in a cellular system with a maximal distance of channel interference. This special structure is observed in most cellular systems. To handle the considered FAP, we use a new concept, the pattern approach which fits naturally to the problem. On the basis of this approach, we are able to formulate the considered FAP into a manageable optimization problem and propose a two phase heuristic algorithm for the problem. Computational experiments show that the two phase algorithm performs much better in both solution quality and computational time than the recently developed algorithms for the FAP. In addition, some theoretical results about the pattern approach are provided, which opens a meaningful viewpoint on the frequency assignment. That is, we can give explanations on the theoretical relationships between the two phase algorithm and the other algorithms for the FAP. Since the considered FAP well reflects most cellular systems, the two phase algorithm can be applied to many practical situations.
Second, this study proposes a new dynamic channel assignment (DCA) algorithm for microcellular systems. The microcells are indispensable to the future mobile communication systems under a huge communication traffic. In developing the algorithm, we provide a mathematical formulation of maximal packing (MP), which takes actual propagation conditions into account. Our algorithm is based on this formulation and adopts Lagrangean relaxation technique. This is, to our knowledge, the first mathematical programming approach in this area. Simulation results show that our algorithm greatly improves the DCA performance which has been worse in overload traffic conditions. Although our algorithm primarily targets the microcellular systems, it is also applicable to the conventional cellular systems with a highly nonuniform traffic distribution.
최근 들어 이동통신 수요는 급증하고 있다. 그러나 이동통신 시스템(cellular mobile communication system)이 사용할 수 있는 資源인 무선 주파수 대역은 법률적으로 제한되어 있어서, 지역에 따라서는 이미 가입자 용량의 부족 현상이 심화되고 있다. 따라서 제한된 주파수 대역을 어떻게 경제적으로 사용하느냐 하는 것은 상당히 중요한 문제가 된다. 이와 같은 문제를 해결하기 위하여 지금까지 많은 노력이 있었으며, 이는 다음의 두 가지로 크게 분류될 수 있다. 첫번째는 앞선 코딩(coding)기술을 이용하여, 주어진 무선 주파수 채널에 보다 많은 情報를 실어 보내려는 시도이다. 이는 時분할 다중접속 방식 (TDMA, time division multiple access)과 코드분할 다중접속 방식(CDMA, code division multiple access)을 기반으로 하는 디지탈 이동통신 시스템의 등장으로 구체화되고 있다. 두번째는 무선 주파수 채널이 어떻게 코딩되었는지에 관계 없이, 여러 무선 주파수 채널들을 最適으로 運用하여, 가입자에게 보다 效率的으로 채널을 할당하려는 시도이다. 이는 주파수 할당 문제(FAP, frequency assignment problem)로 요약되는데, 이 문제는 NP-complete라는 사실이 널리 알려져 있다. 이 연구에서는 주파수 할당 문제를 위한 효율적인 알고리듬(algorithm)을 개발하는 데 중점을 두고 있다. 첫번 째로, 이 연구는 현실에서 자주 발생하는 채널 할당 문제를 위한 알고리듬을 제시한다. 즉, 최대 채널 간섭 거리를 갖는 이동통신 시스템(cellular system with a maximal distance of channel interference)에서 발생하는 주파수 할당 문제를 고려하였다. 이 문제는 독특한 구조를 갖고 있음에도 불구하고, 현실에서 자주 발생되고 있다. 이 문제를 해결하기 위해서 패턴 접근 방법(pattern approach)이라는 새로운 개념을 도입하였다. 이 방법을 기반으로 하여 고려하는 채널 할당 문제를 새로운 최적화 문제(optimization problem)로 정식화 하였다. 그리고 이를 위한 효율적인 2 단계 알고리듬(two phase algorithm)을 제시하고 있다. 이 연구는 실험 결과를 통해서, 2단계 알고리듬이 기존의 알고리듬들과 비교해서 解의 質, 계산 시간 모든 측면에서 보다 우수하다는 것을 보여 주고 있다. 또한, 이 연구에서는 패턴 접근 방법에 관련된 몇가지 이론적인 결과들이 도출되었다. 우리는 이 결과들을 이용하여 2단계 알고리듬과 기존의 채널 할당 알고리듬들과 의 관계를 이론적으로 설명할 수 있는데, 이는 이동통신 시스템의 채널 할당을 위한 의미있는 觀點을 새롭게 제시한다고 할 수 있다. 마이크로 셀로 구성된 시스템은 次世代 이동통신에 적합한 시스템으로 알려져 있다. 이 연구에서는 두번째로, 마이크로 셀로 구성된 이동통신 시스템(microcellular system)을 위한 새로운 動的 채널 할당(DCA, dynamic channel assignment) 알고리듬을 제시하고 있다. 이 알고리듬을 개발하는 과정에서 maximal packing이라는 이미 존재하는 개념을 수리적으로 정식화(mathematical formulation)하였고, 제시된 알고리듬은 이 정식 (formulation)에 라그란지 이완 기법(Lagrangean relaxation technique)을 적용한 것을 기반으로 하고 있다. 이는 아마도 이 분야에서 수리계획법적 접근 방법(mathematical programming approach)이 최초로 시도된 경우라 판단된다. 컴퓨터 시뮬레이션 결과 제시한 알고리듬이 통신 수요의 로드(load)가 심한 상태에서도 좋은 성능을 갖는 것으로 나타났다. 이는 기존의 動的 채널 할당 알고리듬들이 갖고 있었던 약점들 중의 하나인 超過 로드(overload)상태에서 效率이 떨어지는 성질을 크게 보완한 것이라 할 수 있다. 여기서 제시된 動的 채널 할당 알고리듬은 근본적으로 마이크로 셀룰라 시스템을 위한 것이지만, 통신 수요의 변동이 상당히 심한 기존의 이동통신 시스템에도 적합하리라 판단된다.
