The growing demand and diversity of mobile communication services present an array of technical challenges which must be met in order to provide high quality service to users. Among them, call control and frequency assignment have been standard and critical procedures in the design and operation of the mobile communication system. This thesis is concerned with some optimization models for the call control and frequency assignment in cellular radio networks.
Call control, for the systems which have a variety of call types with the different characteristics, is the problem of, when a certain call is generated, determining whether to accept that call or not. Many priority-oriented strategies have been reported in the literature, which can be assorted into several categories according to the way how limit entrance of non-prioritized calls and how handle the rejected calls at their first attempts.
Representative mobile communication systems on whose performances the call control strategies play a great role are the dual-mode TDMA system and the system with handoff calls.
The dual-mode TDMA system has to support both analog and digital calls. According to the current establishments every one analog call consume radio resources upto six times than digital calls. Therefore, some priority should be given to the digital calls over the analog calls for optimizing the system performances such as average blocking probability.
The threshold type strategy without queueing is adopted in this study, which limits the number of active analog calls in a cell within a given value and allows neither of calls to be queued. After analyzing mathematically relationships between blocking probabilities, we formulate two non-linear integer problems for single and multi-cell systems. One of them is to determine the number of required channels, and the other is to find out the threshold value for each cell which optimizes the performance criterion, while satisfying the prespecified GOS for each call type.
Handoff attempts which fail result in forced termination of call and are perceived by users to be interruption of service. The phenomenon is considerably more obstructive than new call blocking. Most of existing strategies protect handoff calls by limiting channel allocation for entering new calls and by allowing handoff calls to be queued when no channel is available.
These strategies have possibility of overprotecting handoff calls, and thus may result in waste of resources. Furthermore, handoff calls are very sensitive to the processing delay, we therefore handle the priority of handoff calls by the policies without queueing, which simply allocates sufficient number of channels to them. Instead, we allow the finite number of new call requests rejected at their first attempts to be queued. This study is to obtain an optimal control policy among the class of such policies which optimizes adopted performance measures satisfying the prescribed GOS for each call type.
Finally, we propose a new lower bound for the frequency assignment problem(FAP). NP-completeness of FAP makes use more time-efficient algorithms which, however, cannot guarantee optimal solutions. Lower bounds on the number of frequencies needed for a whole system, providing criteria for checking the qualities of solutions obtained by these algorithms, plays an important role in the frequency assignment procedure.
Of our particular interest is generating a new lower bound, from relaxing the condition of the Lemma 9 of Gamst's paper [7], which is considered to be a little impractical due to the difficulty of locating the area in a real cellular system where its prerequisite condition is met. We extend this work by introducing the procedure of frequency insertion. And we show that the new lower bound thus obtained not only broadens the applicability and but also is tighter than its previous counterpart.
이동통신 서비스 수요의 기하급수적 증가로 현재의 아날로그 시스템은 용량의 한계에 이르렀고 따라서 한정된 무선자원을 효율적으로 활용하여 시스템의 성능을 제고하는 노력이 요구되고 있다. 또한, 음성, 데이터, 비디오정보 전송 등 다양한 종류의 서비스를 지원하는 것이 차세대 이동 및 개인통신 시스템(Personal communication system)의 필수조건이다. 이러한 요구 서비스의 질적, 양적 팽창으로 사용자에게 우수한 품질의 서비스를 제공하기 위해서는 몇 가지의 S/W 기술적 요건들이 만족해야 한다. 그 중에서도 호제어(Call Control)와 주파수할당(Frequency Assignment)은 이동통신 시스템의 성능을 좌우하는 설계(Design)와 운용(Operation)에서의 아주 중요한 단계로 인식되어 왔다.
이동통신 시스템에서 다른 특성과 요구조건을 가진 트래픽(신규호 vs. 핸드오프호, 음성 vs. 데이터, 아날로그 vs. 디지털 등)을 서비스해야 하는 서비스의 다양성의 증가로 호제어 전략(Call control strategy)의 개발과 모형화는 이동통신 시스템의 성능을 평가하고 개선하기 위한 중요한 과제이다. 호제어는 특정한 종류의 호가 발생하였을 때 이에 채널을 할당하여 서비스해 줄 것인가에 대한 여부를 결정하는 문제이다. 서로 다른 특성을 지닌 다양한 종류의 호를 제어하기 위한 호제어 전략에 대한 연구는 유ㆍ무선망 시스템을 대상으로 많이 이루어졌다. 이러한 전략들은 특정 호에 우선권을 부여하는 전략으로 간주할 수 있는데, 일반적으로 대기를 허용하는 것과 허용하지 않는 것으로 구분된다.
본 연구의 첫 번째 목적은 이동통신 시스템에서 호제어를 위하여 사용될 수 있는 최적화문제를 제시하고 이의 해법을 제시하는 것이다. 시스템의 성능이 호제어 전략에 많은 영향을 받는 시스템중의 하나는 이중모드(dual-mode) TDMA 시스템이다. 디지털 시스템으로의 자연스러운 전환을 위하여 필수적으로 거쳐야 하는 중간단계로서 이중모드 TDMA 시스템에서는 아날로그호와 디지털호를 동시에 서비스해야 한다. 즉, 한 가입자가 아날로그 장비를 지니고 있으면 시스템 운용자는 가입자에게 아날로그 채널을 할당해 주고 디지털 가입자에게는 디지털 채널을 할당해야 한다. 현재 개발되고 있는 시스템의 표준안에 따르면 하나의 아날로그 채널은 3개 또는 6개의 디지털 가입자를 수용할 수 있다. 아날로그와 디지털 호는 동일한 시간동안 채널을 점유하는 반면 아날로그호는 디지털의 최고 6배정도의 무선자원을 사용하므로 시스템의 성능을 향상시키기 위해서는 디지털 호에 대하여 어느 정도의 우선권을 부여하여야 한다.
본 연구에서는 이중모드 TDMA 시스템에서의 호제어를 위하여 대기를 허용하지 않고 진행중인 아날로그호의 수가 일정 수준 이상이면 아날로그호를 서비스하지 않는 임계형식(Threshold type)의 호제어 전략을 채택한다. 기존의 이중모드 TDMA 시스템을 대상으로 하는 호제어에 대한 연구는 모의실험(Simulation)을 통한 결과의 해석이었지만, 본 연구는 임계형식의 호제어 전략의 수리적 모형화(Mathematical modeling)를 통하여 수리적 분석을 도출한다. 또한 이러한 수리적 분석을 통하여 아날로그 및 디지털호의 손실율(Blocking probability)에 대한 제약조건을 만족하기 위하여 필요한 채널의 수와 채널의 수가 주어져 있을 때 가중평균호손실율 (Average blocking probability) 등의 목적함수를 최적화는 문제를 단일셀 시스템과 다중셀 시스템에게 적용한다.
호제어 전략이 시스템의 성능에 많은 영향을 주는 다른 시스템으로서는 신규호(New call)와 더불어 핸드오프호 (Handoff call)를 서비스해야 하는 시스템이다. 핸드오프호는 통화의 지속상태를 나타내므로 핸드오프호의 단절은 신규호의 단절보다 가입자가 느끼는 불쾌감은 더욱 클 것이다. 따라서 일반적으로 핸드오프호에 우선권을 부여하여야 한다는데 인식을 같이 하고 있다.
기존의 많은 연구들이 핸드오프호를 보호하기 위하여 초기진입단계에서 신규호의 진입을 제한하고 동시에 핸드오프호의 대기상태를 허용하는 전략에 대한 연구가 많이 진행되었다. 그러나, 핸드오프호를 보호하기 위하여 신규호의 진입을 제한하는 만큼 채널이용률(Channel utilization) 등의 시스템 성능은 저하된다. 또한, 핸드오프호가 대기상태에 머무를 수 있는 시간적 여유는 신규호보다 적은 것이 일반적인 현상이다. 따라서 본 연구에서는 초기진입단계에서 신규호에 대한 채널할당을 제한하는 대신, 핸드오프호에 대한 대기상태는 허용하지 않고 신규호의 대기상태를 허용함으로서, 서로 상충관계에 있는 시스템 성능과 핸드오프호 보호간의 적정한 절충수준을 찾고 핸드오프호의 대기상태에 대한 어려움을 극복하고자 한다. 호제어 전략은 신규호 및 핸드오프호가 발생했을 때 채널을 할당할 확률과 대기중에 있는 호에게 채널을 할당할 확률로 표현된다. 본 연구의 목적은 신규호와 핸드오프호의 손실율과 신규호의 평균대기시간에 대한 제약조건을 만족하면서 다양한 형태로 표현되는 목적함수를 최적화하는 채널할당확률을 구하는 것이다.
채널할당 문제(Frequency assignment problem)는 전체 시스템을 커버하기 위해서는 몇 개의 채널(또는 주파수)이 필요로 하고 구체적으로 어떠한 채널들을 할당할 것인가를 결정하는 문제이다. 각 셀의 통화품질(Voice Quality)과 서비스품질(Grade of Service, GOS)을 고려하여 각 셀(기지국 또는 섹터)에서 할당되어야 할 채널의 수와 셀에 할당되는 채널간 최소한 떨어져야 할 주파수 간격이 채널할당문제의 입력요소로 주어진다.
채널할당문제는 실제 시스템을 설계하고 확장하고자 할 때 적용될 수 있는 아주 중요하고 응용성이 높은 문제이기 때문에 많은 연구가 진행되어 왔지만 아직 만족스런 결과를 제시하지 못하고 있다. 이는 채널할당문제가 NP-complete 문제이고 따라서 많은 기지국과 채널을 고려해야 하는 현실적 문제의 최적해를 구하기 위해서는 엄청난 계산량을 요구하기 때문이다. 실제로 채널할당문제는 그래프 이론에서 NP-complete문제의 대표적인 것으로 간주되는 그래프채색문제 (Graph coloring problem)의 일반화된 형태이다. 따라서, 기존의 연구는 단시간 내에 결과를 제시하는 휴리스틱 알고리즘(heuristic algorithm)개발에 주력하였지만, 이들은 최적할당은 보장하지 못하고 최적할당(Optimal assignment)보다 많은 수의 채널을 요구하는 것이 일반적이다. 또한, 이러한 알고리즘들은 결과가 최적할당과 얼마나 차이가 있는가에 대한 정보를 전혀 제시하지 못하고, 우연하게 최적해를 찾았다 하더라도 이를 확인할 수가 없다. 그러므로, 전체 시스템이 요구하는 채널수의 하한(Lower bound)은 이러한 알고리즘으로 찾은 해의 품질을 평가하기 위한 기준을 제시함으로서 채널할당과정에서 중요한 역할을 한다. 채널할당문제의 하한에 대한 연구는 Gamst(1986)에 의하여 처음 이루어졌는데, 본 연구는 Gamst가 제시한 하한 중에서 하한을 제시하는 셀의 부분집합을 찾기가 어려워 현실성이 떨어진다고 평가되는 하나의 하한에 대한 정리의 조건을 완화하여 새로운 하한을 제시한다.