This thesis is concerned with some optimization models for frequency resource management in a cellular system. Frequency resource management includes frequency channel assignment and operation.
First, we consider the Frequency Assignment Problem (FAP) for a system with nonhomogeneous traffic distribution and the interference-related constraints. Most of the heuristic algorithms for the FAP have adopted sequential assignment algorithms developed for the Graph Coloring Problem (GCP). In this study, we consider two representative frequency assignment strategies, the frequency exhaustive strategy (FES) and the requirement exhaustive strategy (RES), which are adopted by most of such heuristic algorithms for the FAP. We first show that there always exists an order of the requirement list which provides an optimal assignment with the FES, while the RES doesn't always have such an order. We will also present two polynomial time heuristic algorithms, one for each strategy.
Our second model deals with the so-called Perturbation-Minimizing Frequency Assignment Problem (PMFAP), the objective of which is to assign the available frequency channels for newly generated channel requirements at the minimum reassignment of the preassigned frequencies while meeting the compatibility constraints. For developing the heuristic algorithm for the PMFAP, we adopt the rearrangement technique, which rearranges some of the already assigned frequencies in order to assign frequencies into some more of the new requirements.
Generally, subscriber mobility in cellular mobile system is controlled through location updating based on the so-called location area (LA), the basic area unit for paging which consists of a number of cells. There is a tradeoff relation between the two kinds of signalling traffic: paging and location updating. As LAs become bigger consisting of a larger number of cells, the traffic volume for paging increases while that for location updating decreases. This realization motivates us to consider the so-called Location Area Partitioning Problem (LAPP), which aims at minimizing the total signalling traffic by optimally partitioning the whole service area into location areas. In this study, we show that the LAPP can be transformed to a combinatorial optimization problem, the so-called Clique Partitioning Problem (CPP), for which an efficient cutting plane solution method is available. By a test run with mostly real input data, we demonstrate how effectively the proposed method can be utilized in determining LAs for real cellular networks.
이동통신시스템에 셀룰러방식이 도입된 이래 이동통신서비스에 대한 수요는 해를 거듭할수록 급격하게 증가하고 있는 추세이다. 반면에, 이동통신시스템에 할당된 주파수자원은 제한되어 있기 때문에, 이러한 수요의 증가를 수용하기 위한 용량확보 방안으로 셀의 소형화, 디지털화, 음성신호의 협대역화 등 여러 가지 기술들이 연구ㆍ개발되고 있으며, 이와 함께 가용 주파수채널들을 효율적으로 관리ㆍ운용하여 그 이용률을 최대화시키려는 연구들도 계속되고 있다. 본 논문에서는 이러한 주파수채널의 관리 및 운용과 관련된 문제들을 최적화기법을 이용하여 모형화하고, 각 문제의 특성을 고려한 발견적해법 (heuristic algorithms)을 제시하였다.
본 연구에서 첫 번째로 다룬 문제는 주파수할당문제(Frequency Assign- ment Problem, FAP)이다. 이미 알려진 바와 같이 FAP는 그래프채색문제(Graph Coloring Problem, GCP)와 밀접한 관계가 있으며, 따라서 기존에 개발된 대부분의 주파수할당기법들은 GCP에서 개발된 순차적(sequential) 채색기법들을 응용ㆍ확장한 것이다. 즉, 시스템의 모든 채널수요(channel requirement)들에 대하여 사전에 할당순위(assignment order)를 결정한 후, 이 순위에 근거하여 각 채널수요에 순차적으로 주파수채널을 할당한다. 결국, 이러한 그래프채색기법에 기초한 해법들은 할당순위의 결정방법과 이를 이용하여 직접 주파수를 할당하는 주파수할당전략에 따라 여러 가지 해법들로 구분되어 진다.
본 논문에서는 지금까지 개발된 주파수할당전략들 중에 가장 대표적인 두 가지 전략인 주파수소진법(frequency exhaustive strategy)과 채널수요소진법(requirement exhaustive strategy)을 대상으로 몇 가지 이론적인 결과들을 도출하였다. 첫째, 주파수소진법의 경우는 각 문제에 대하여 최적해를 주는 주파수할당순위가 적어도 하나는 존재하는데 반해, 채널수요소진법의 경우는 그렇지 않다. 즉, 채널수요소진법으로는 최적해를 구할 수 없는 문제가 존재한다. 둘째, 두 가지 전략 모두 GCP에서와 동일하게 O($n^2$)의 시간으로 계산이 가능하다.
처음 셀룰러방식을 도입한 80년대와는 달리 현재는 대부분의 국가에서 셀룰러방식에 의한 이동통신서비스를 이미 제공하고 있으며, 따라서 이미 운용되고 있는 시스템에 추가로 주파수채널을 할당하는 문제가 중요하게 되었다. 즉, 시스템운용자의 입장에서는 주파수채널을 추가로 할당하는 데 있어, 기존에 할당되어 있는 주파수할당상황을 되도록 변화시키지 않는 것이 비용이나 통화품질의 측면에서 가장 바람직할 것이다. 본 논문에서는 이러한 점에 근거하여 소위 최소변화주파수할당문제(Perturbation-Minimizing Frequency Assignment Problem, PMFAP)라 불리는 새로운 문제를 정의, 모형화하였다. 이 문제는 FAP와는 달리 최초의 주파수할당상황이 중요한 입력자료가 되며, 따라서 이러한 특성을 적절히 반영한 해법이 필요하다. 본 연구에서는 체계적인 탐색(search) 방법을 이용하여 기존의 할당상황을 최소로 변화시키며 채널을 할당하는, 소위 재할당기법(rearrangement technique)을 이용한 발견적해법을 개발하였다. 한편, 이 문제를 다룬 연구들이 아직 없었던 관계로 제시한 해법의 성능을 직접 비교, 평가하기가 불가능하였고, 따라서 본 논문에서는 재할당기법의 효율성을 보이기 위해 기존에 제시된 대표적인 FAP해법들과 이들에 재할당기법을 추가로 도입한 새로운 해법을 개발하여 그 성능을 비교하였다.
현재의 셀룰러시스템은 물론 향후 구현될 개인통신망(Personal Commu- nication Network)에서는 그 제공하는 서비스의 특성상 가입자의 이동성을 보장하고 관리하는 기능들이 반드시 필요하다. 현재 가장 많이 사용되고 있는 가입자 위치관리전략은 위치영역(location area)에 기초한 방법으로, 전체 서비스지역을 몇 개의 위치영역들로 분할한 후, 사전에 각 가입자의 위치정보를 위치영역 단위로 데이터베이스에 등록하고 착신호의 연결 시에 해당 이동국이 위치한 위치영역내의 기지국에서만 페이징(paging)하는 방법이다. 이 전략에 의하면 이동통신망은 각 가입자의 정확한 위치를 계속 추적해야 하는데 이를 위치등록(location registration)이라 하고, 특히 위치영역이 변경될 때 데이터베이스의 해당 위치정보를 갱신하는 절차를 위치갱신(location updating)이라 한다. 이러한 위치등록 및 위치갱신 기능은 착신호의 연결 시에 해당 위치영역 내의 기지국에서만 페이징하게 하므로, 페이징에 필요한 신호트래픽을 대폭 감소시키지만 위치갱신 트래픽이라는 새로운 신호트래픽을 유발한다. 결국 이 전략에 의하면, 페이징 트래픽과 위치갱신 트래픽간에는 trade-off가 존재한다. 따라서 이와 같이 상충되는 두 신호트래픽에 의한 무선자원의 총 비용이 최소화되도록, 위치영역의 layout을 설정하는 것이 중요하다.
본 논문에서는 이러한 문제를, 서비스지역 내의 모든 셀들을 몇 개의 위치영역으로 분할한다는 의미에서, 위치영역분할문제(Location Area Partitioning Problem, LAPP)라 부른다. 이러한 위치영역분할문제는 클릭분할문제(Clique Partitioning Problem, CPP)와 동일한 형태로 모형화될 수 있고, 이는 곧 그 문제를 풀기 위해 CPP해법을 이용할 수 있음을 의미한다. 이를 보이기 위하여 가장 현실적인 데이터를 이용하여 시험하였고, 그 결과 최적해를 빠른 시간 안에 얻을 수 있었다. 앞으로 구현될 개인통신망의 경우, 시스템의 차이로 인해 비용 및 트래픽 관련 파라미터 값들을 구하는 방법에 있어 약간의 차이는 있겠지만, 기본적인 분석 및 해법 적용방법에서는 동일하다.
