The successful deployment of a cellular system depends greatly upon the cellular network planning process which includes such operations as transmission and radio propagation predictions, geographical and traffic parameters evaluation, optimal radio network design, and network resource allocation. Among them, the importance of optimal radio network design and network resource allocation is ever-increasing now. This thesis has dealt with some optimization models for radio network planning, especially related to radio network design and network resource allocation, in mobile cellular communication systems.
First, a radio network design problem is considered in a cellular CDMA system, in which blocking is enforced when the relative interference exceeds a certain threshold level. Given the data of call-traffic distributed over the service area and potential sites of base stations, the objective of the problem is to locate base stations so as to minimize the associated cost for establishing base stations while keeping the probability of blocking under control. An efficient algorithm for solving the design problem is developed. Computational experiments with real-world data are conducted to show both the efficiency and the practicality of the proposed design method. Computational results showed that the proposed algorithm consistently performed well both in solution quality and in speed as to be practicable.
The rapid growth of users and rising subscriber expectations have led cellular network operators to deploy microcells in the urban areas, especially in hot spots. Our second model deals with the so-called micro Base Station Location Problem (mBSLP) for the urban cellular environment, the objective of which to locate mBSs with minimum cost over a specified coverage region so that the signal at various mobile station locations is of sufficient intensity, while the overlapped areas are minimized. For the mBSLP, a heuristic algorithm was developed, and computer simulations were conducted by varing the parameters related to the mBSLP. By considering many kinds of circumstances, the results can be helpful to designers in making decisions for constructing an initial radio network in the urban cellular environment.
A robust operation of assigning frequencies to requirements in a TDMA (or FDMA) cellular system should cope with environmental changes such as short-term demand rises and long-term capacity expansions while always keeping the required realignment process as simple as possible. The Perturbation-Minimizing Frequency Assignment Problem (PMFAP) is considered, the objective of which is to assign the available frequencies for newly generated requirements with the minimum reassignment of the preassigned frequencies while meeting the interference-related constraints. For the PMFAP, a heuristic algorithm based on the rearrangement technique is proposed, which can also be applied to the Frequency Assignment Problem (FAP) with a slight modification. The effectiveness of the proposed algorithm was tested using randomly generated problems. Computational experiments show that algorithms of depth type, though with slight computational burden, perform much better in solution quality than algorithms of breadth type.
지속적인 이동통신 서비스 시장의 확대와 고품질 서비스에 대한 가입자의 욕구에 부응하기 위해 기존의 아날로그 시스템으로부터 디지털 시스템으로의 본격적인 대체가 이루어지고 있으며, 이러한 디지털 접속 기술은 가입자 용량 및 통화품질에 획기적인 향상을 가져올 것으로 예상된다. 또한 트래픽(traffic)이 밀집된 도심지역을 대상으로 반경 2~500m 내외의 마이크로셀(micro-cell)을 이용한 시스템이 제안되고 있으며, 향후 차세대 이동통신 시스템에서 이의 중요성은 더욱 증대될 것이다.
지금까지의 디지털 시스템에 관한 연구들은 상용 서비스를 제공하기 위한 H/W에 중점을 두고 이루어져 왔지만, 앞으로 이러한 H/W 기술 외에 초기 무선망 설계 및 환경 변화에 능동적인 대처가 가능한 이동통신 무선망 계획에 관련된 제반 연구의 중요성이 점차 부각되고 있다. 본 논문에서는 이러한 무선망 계획과 관련된 최적화 모형들을 소개하고, 이에 대한 해법을 제시하였다.
우선, 본 연구에서는 CDMA 시스템을 대상으로 상용 서비스를 제공하기 위해 필요한 최적 기지국의 수와 이의 위치를 결정하는 문제({\it Base station Location Problem}, BLP)를 다루었다. 서비스 지역에서의 트래픽 자료, 기지국 후보지(potential site)의 위치가 주어진 경우, 일정 수준의 통화품질을 보장하는 범위내에서 최소의 비용으로 서비스 가능한 기지국의 수 및 이의 위치를 결정한다. CDMA 시스템에서의 호 절단(call blocking)은 모든 채널(channel)이나 스롯(slot)이 사용자에 의해 점유되는 경우 발생하는 FDMA나 TDMA 시스템과는 달리, 일정 수준의 통화품질을 벗어나는 경우에 발생한다. 본 논문에서 사용한 통화품질에 관한 조건으로 역방향 링크(recerse link)상의 통화품질이 일정수준 이하가 될 확률로 정의하였으며, 이를 BLP의 제약조건으로 사용하였다. BLP에 관한 해법은 최소비용 치국문제({\it Minimum cost Location Problem}, MCLP)를 응용한 구축 휴리스틱(construction heuristic)과 개선 휴리스틱(improvement heuristic)으로 구성되어 있으며, 현실을 대상으로 한 문제와 여러 무작위(random)로 구성된 문제들에 대해 해법의 타당성을 검증하였다.
도심지역과 같이 트래픽이 집중되는 곳을 대상으로 마이크로셀 시스템의 구축이 예상되며, 매크로셀 시스템에 비해 다음과 같은 특징을 갖는다. 주위의 고층건물이나 빌딩들로 인해 전파전파(radio propagation)에 상당한 제약을 갖으며, 가시영역(Line-of-Sight area)의 제한으로 인한 음영지역(shadow area)의 발생 가능성이 높다. 또한 기지국 장비 크기의 제한으로 인해 안테나(antenna)에서의 송신출력(transmit power)이 낮게 되며, 이로 인해 순방향 링크(forward link)의 통화품질 저하가 예상된다.
초기 무선망을 구축하는 경우 음영지역으로 인한 통화호 단절은 심각한 문제를 야기하게 되므로 정확한 전파전파 예측을 통한 무선망 설계가 요구된다. 또한 CDMA 시스템은 소프트 핸드오프(soft-handoff)라는 특성으로 인해 겹쳐지는 영역(overlapped area)이 많으면 많을수록 전체 시스템의 용량(capacity)은 감소하게 된다. 즉, CDMA 시스템에서는 너무 많은 수의 기지국이 위치하게 되면 소프트 핸드오프 구간이 증가하며, 이로 인해 전체 시스템의 용량이 저하된다. 본 연구의 마이크로 기지국 치국문제(micro Base Station Location Problem, mBSLP)는 마이크로셀 시스템을 구축하는데 있어 도심환경이 갖는 복잡한 특성을 반영하는 동시에, 음영지역이 발생하지 않고 겹쳐지는 영역에 대한 제약(penalty)이 최소가 되도록 무선망을 구축하는 문제로 정의된다. 음영지역의 기준으로는 링크버짓 분석(link budget analysis)에 의한 최대 허용가능 경로손실값(maximal allowable path loss value)을 사용하였으며, 도심환경을 특수성을 반영한 Chang et al. 모형을 통해 얻은 후보지와 서비스 지역간의 경로손실값을 근거로 음영지역 여부를 판단한다. mBSLP와 P-median문제와의 유사성을 근거로 해법과정을 제시하였으며, 다양한 형태의 모수들에 대해 모의실험을 수행하였다.
FDMA와 TDMA 시스템에서는 기지국 수 및 이의 위치를 결정하는 문제 외에 주파수채널을 할당해야 하는 문제가 존재한다. 이에 관해서는 많은 연구들이 진행되어 왔으나, 본 논문에서는 수요증가 혹은 무선망 확장으로 인해 기지국에서 추가로 주파수채널을 필요로 하는 경우와 기지국이 증가된 경우를 대상으로 한다. 특히, 현재 FDMA와 TDMA를 사용하는 대부분의 국가에서 이미 운용되고 있는 시스템에 추가로 주파수채널을 할당하는 문제의 중요성은 증대되고 있다. 즉, 시스템 운용자의 입장에서는 주파수채널을 추가로 할당하는데 있어, 기존에 할당되어 있는 주파수할당상황을 되도록 변화시키지 않는 것이 비용이나 시간 측면에서 가장 바람직하다. 본 논문에서는 이러한 점에 근거하여 소위 최소변화 주파수할당문제OE(Perturbation-Minimizing Frequency Assignment Problem, PMFAP)를 정의, 모형화하였다. PMFAP는 사용 가능한 주파수채널(available frequency list)과 주파수간섭관계가 주어진 경우, 초기 할당상황의 변동을 최소화하는 문제로 정의되며, 이를 위해 재할당 기법(rearrangement technique)을 이용한 발견적 해법을 제시하였다. 본 논문에서 제시한 재할당 기법에 의한 Bυ-Dω휴리스틱의 효율성을 보이기 위해 두가지 방법에 대해 모의실험을 수행하였다.
본 논문에서는 무선망 계획과 관련된 최적화 모형들을 소개하고 이에 대한 해법을 제시하였으며, 다양한 모수들에 대해 모의실험을 수행하였다. 본 연구에서의 결과들은 무선망을 구축하기 전에 필요한 투자분석이나 초기 무선망에 대한 prototype을 제시하는데 사용 가능하며, 이 외에도 무선망 설계 담당자의 의사결정에 많은 도움을 주리라 예상된다.
