This thesis is concerned with the frequency assignment and the channel allocation for the design of cellular mobile communication systems. Our first model deals with frequency assignment problem (FAP) for a system with nonhomogeneous traffic distribution and channel interference conditions. The second model considers the prioritized channel allocation scheme for handoff calls.
For FAP, we provide general framework for connecting it to general graph coloring problem. Based on the lower and the upper bounds on the optimal solution of FAP, we suggest an approach to reduce the complexity of the problem. Then, FAP for ν-complete subset with two kinds of constraints, which in general consists of cells with the heaviest traffic distribution in cellular systems, is analyzed in detail. We show that the optimal frequency assignment to ν-complete subset depends on the relations between the total requirement, the maximum requirement, the number of nodes with the maximum requirement, and the ratio of the co-site and the adjacent channel constraint. Based on these observations, we provide the exact frequency assignment algorithms for all kinds of ν-complete subsets considered.
By utilizing the upper bound for the chromatic number of general graph coloring, we devise a new measure for assignment difficulty which can be applied to any of non-iterative heuristic frequency assignment algorithms. Besides, we suggest another heuristic procedure for general frequency assignment problem. Our algorithm exploits the observation that increasing the channel separation between frequencies than necessary may bring the decrease in the ultimate frequency span required. Computational experiment indicates that our algorithm performs better than existing ones in some problem setting.
Our second model considers the prioritized channel assignment for handoff calls. Handoff is peculiar to the cellular communication system and the failure of handoff critically degrades the service quality. In our model, cutoff priority scheme is incorporated into the allocation of channels to cells. We derive some properties of the blocking probabilities of the handoff and the ordinary calls under cutoff priority scheme. The dimensioning problems of allocating the prioritized channels in single cell system and in a multi-cell system are then respectively formulated as the discrete capacity allocation models. When the arrival rates of handoff and ordinary calls are given, our models determine the number of channels to be allocated for both types of calls and that to be prioritized for handoff calls.
Extending the existing marginal capacity allocation procedure, the exact incremental algorithms to solve these problems are devised by exploiting the properties of the blocking probabilities obtained. Computational experiment indicates that our algorithms can solve problems of practical size efficiently. Moreover, it suggests that, in order to give priority to handoff calls, proritizing only a few channel is sufficient and there is no need to allow handoff calls to be queued.
셀룰러 이동통신시스템의 설계를 위해 긴요한 채널배정 문제와 채널 용량결정문제에 대한 기존 연구는 주로 시뮬레이션이나 발견적기법 등에 의존해 왔다. 이 논문에서는 이러한 문제들에 대해 최적화이론을 적용한 접근 방법을 제시하였으며 주어진 문제를 최적화모형으로 정형화하고 각 문제의 특성을 고려하여 해를 얻을 수 있는 해석적인 해법을 개발하였다. 이를 위해 먼저 지역간의 불균등한 수요와 주파수 간섭제약을 고려한 채널배정문제 (Frequency Assignment Problem, FAP)를 다루고, 다음으로 셀룰러 이동통신시스템에서의 핸드오프호에 대해 우선순위를 부여할 수 있는 채널용량 할당문제(Prioritized Channel Allocation, PCA)를 다루었다.
FAP는 그래프채색문제(Graph Coloring Problem, GCP)와 동일하며 이들 문제는 모두 NP-complete 임이 알려져 있다. 본 연구에서는 동일채널 사용제약만을 고려하는 기존의 단순채널배정문제(SFAP)를 확대하여, 이동통신시스템의 설계에 직접 사용할 수 있도록 모든 형태의 채널사용제약을 반영하는 일반적인 채널배정문제(GFAP)를 취급하여 다음과 같은 결과를 얻었다.
첫째, 비교적 많은 연구가 이루어진 GCP에 대한 기존 해법으로 부터 GFAP에 대한 해를 얻을 수 있는 절차를 명시적으로 제시하였다. 또한 GCP와 GFAP의 최적해에 대한 하한과 상한을 활용하여 주어진 GFAP의 문제규모를 줄일 수 있는 축소절차(Reduction Procedure)를 제안하였다.
둘째, GFAP의 특수한 경우인 ν-완전집합(υ-complete Set)에 대한 채널배정문제를 분석하였다. ν-완전집합의 특성은 이를 이루는 노드들의 전체 채널수요, 최대 채널수요, 최대수요를 갖는 노드의 수 및 간섭 제약식등에 의해 결정됨을 밝혀내고, 이를 바탕으로 υ-완전집합을 세가지 유형으로 분류하여 이들 각 유형에 대한 최적 채널배정 절차를 개발하였다. 일반적으로 ν-완전집합은 이동통신시스템에서 채널수요가 가장 많고 간섭제약이 심한 기지국들에 대응되므로 이 결과는 보다 일반적인 GFAP의 해법개발에 효과적으로 활용될 수 있다.
셋째, GFAP에 대한 발견적 해법을 제시하였다. 이를 위해 노드에 대한 채널배정 순서를 결정하기 위한 배정난이도에 대한 발견적 척도를 제안하였다. 또한 기존의 발견적 배정기법의 장단점을 분석하고 υ-완전집합에 대한 최적 채널배정 절차를 응용하여 새로운 채널배정절차를 제시하였다. 모든 유형의 GFAP에 대해 전반적으로 좋은 해를 제공하는 해법은 아직 개발되어 있지 않으므로 본 연구에서 제시된 발견적 기법들은 실제 시스템의 설계과정에 유용하게 이용될 수 있다.
본 연구의 두번째 모형은 이동통신시스템의 기지국에 대한 채널용량을 이산용량할당문제(Discrete Capacity Allocation Problem)로 정형화하고 이의 최적해를 결정하는 절차를 다루었다. 핸드오프호를 보호하기 위한 우선순위부여방안으로는 통화가 도중에 단절될 수 없다는 음성호의 특성을 반영하여 Cutoff Priority Scheme(CPS)을 고려하였다. CPS하에서의 채널용량할당문제는 일반호와 핸드오프호의 호손실율을 일정수준으로 유지하면서 핸드오프호의 호손실율을 최소화하는 핸드오프호 전용채널(가드채널)의 수를 결정하는 문제로 정형화될 수 있다. 호의 도착률이 포아송분포를 따르고 접속시간이 지수분포를 따른다는 가정하에 CPS하에서의 핸드오프호와 일반호의 호손실율은 출생사망과정(Birth-Death Process)을 이용하여 구할 수 있다. 이 모형을 통해 얻어진 주요 결과는 다음과 같다.
첫째, 트래픽모형에 대한 분석을 통해 CPS하에서 일반호와 핸드오프호의 호손실율과 가드채널 수간의 관계를 밝혀냈다. 이 결과 얻어진 호손실율들의 특성은 정형화된 모형의 최적해를 구하는 절차에 유용하게 활용될 수 있다.
둘째, 이동통신시스템의 단일기지국에 대한 PCA문제를 고려하였다. 단일기지국의 채널용량 결정문제로는 기지국에 배정될 채널의 수가 주어졌을 때 그중에서 핸드오프호 전용으로 사용하는 가드채널의 수를 결정하는 문제와, 핸드오프호와 일반호에 대한 호손실율 기준치가 주어졌을 때 이를 충족하기 위해 필요한 가드채널 및 일반채널의 수를 결정하는 문제가 있다. 본 연구에서는 이러한 문제들을 비선형 정수계획문제(Non-linear Integer Program)로 정형화하고 앞서 구한 핸드오프호와 일반호의 호손실율간의 특성을 활용하여 점차적 용량할당절차(Incremental Capacity Allocation Procedure)에 의해 최적해를 쉽게 구할 수 있는 절차를 제시하였다.
셋째, 단일기지국에 대한 모형을 복수의 기지국으로 구성된 이동통신 시스템에 대한 채널용량결정문제로 확대하여 정형화하고, 핸드오프호 호손실율의 볼록성(Convexity)에 착안하여 이 문제에 대해서도 최적해를 쉽게 구할 수 있는 점차적 용량할당절차를 제시하였다. 실제 규모의 문제에 대한 사례연구를 통해 제안된 해법이 매우 빠른 시간안에 최적해를 제시해 줌을 입증함으로써 제안된 모형이 실제 시스템에서의 적응식 가드채널결정에 활용될 수 있음을 보였다.
