Channel management is one of the most important problems in the design of cellular mobile systems. Several channel management models have been suggested in the literature. Using fixed channel assignment (FCA), to reuse radio spectrum efficiently, frequency planning considering traffic demands is required. We describe two representative channel assignment problems MSP (minimum span problem) and MBP (minimum blocking problem) for frequency planning and suggest efficient solving procedures for these problems. As a cellular mobile system evolves, cells will become smaller. Decreasing cell size exacerbates the spatial and temporal volatility of traffic and makes optimal frequency planning infeasible. Dynamic channel assignment (DCA), which is more flexible than FCA, will play a more important role in such a system. We suggest an efficient borrowing channel assignment (BCA) model which is a kind of DCA.
For MSP, we suggest an efficient general heuristic algorithm which uses a GOS updating scheme. This scheme generates a sequence of target GOSs that converges to the required GOS in a self-adjusting manner. We also suggest a simple procedure to further improve the channel allocation solution obtained by the algorithm. Computational experiments show that our algorithm provides solutions with much smaller span than existing other ones.
MBP is mathematically formulated as a nonlinear combinatorial problem. Using the piecewise linearization technique for convex functions, MBP can be converted into a linear combinatorial problem. To begin with, we deal with the simple minimum blocking problem (SMBP) considering only the co-channel interference constraint. To treat SMBP more conveniently, we introduce the concept of pattern and reduce the problem. Using Lagrangean relaxation and subgradient optimization techniques, we obtain high-quality solutions with information about their deviations from true optimal solutions. Computational experiments also show that our method is very powerful tool for solving SMBP.
For general MBP, we suggest two heuristic algorithms: Lagrangean relaxation based algorithm and GOS updating algorithm. The Lagrangean relaxation based algorithm provides heuristic solutions with information about their deviations from true optimal solutions. This algorithm works well for systems with special compatibility matrices. The GOS updating algorithm uses a GOS updating scheme, which generates a sequence of target GOSs decreasing in a self-adjustment manner. Computational experiments show that the GOS updating scheme is an efficient tool.
Finally, we suggest an efficient BCA scheme which consists of two phases. The first ordinary channel allocation phase borrows a channel from neighboring cells by an impact-based borrowing strategy. The second channel reallocation phase has a reallocation procedure for locked-channel utilization and a reallocation procedure for efficient channel reuse. Simulation results show that in both uniform and nonuniform traffic cases, our schemes significantly reduce the system blocking probability over existing other schemes. Furthermore, one of our schemes has much smaller number of reallocations than other compared schemes.
채널운용은 셀룰라 이동통신시스템의 설계에 있어서 가장 중요한 문제 중의 하나이다. 지금까지 제시된 여러 가지 형태의 채널운용모형은 크게 고정채널할당 (FCA: fixed channel assignment)모형과 동적채널할당 (DCA: dynamic channel assignment) 모형으로 구분할 수 있다. FCA를 사용하는 경우에는, 라디오 스펙트럼의 효율적인 운용을 위해서 통신수요를 고려하는 사전주파수계획이 필요하게 된다. 본 논문에서는, 사전주파수계획을 위한 두가지 대표적인 채널할당문제인 최소 스팬 문제 (MSP: minimum span problem) 와 최소 호손실율 문제 (MBP:minimum blocking problem) 를 설명하고, 각 문제에 대한 효율적인 알고리즘을 제시하였다. 그런데, 셀룰라 이동통신시스템이 진전하게 되면 셀의 크기가 점점 작아지게 된다. 이러한 시스템에서는, FCA 보다 통신수요의 변화에 좀 더 유연하게 대처할 수 있는 DCA 가 더 중요한 역할을 담당하게 될 것이다. 본 논문에서는 DCA 의 일종인 2 단계로 구성된 차용채널할당 (BCA: borrowing channel assignment) 모형을 개발하였다.
MSP 에 대해서, GOS (grade of service) 개선체계를 사용하는 효율적인 범용 휴리스틱 알고리즘을 제시하였다. 이 개선체계는 자동적응방식에 의해 요구되는 GOS 수준에 수렴하는 목표 GOS 들의 순열을 생성한다. 또한 이 알고리즘에 의해 얻어진 해를 좀 더 개선할 수 있는 체계를 제시하였다. 실험을 통해서 우리의 방법이 기존의 다른 방법들에 비해 훨씬 적은 스팬을 가진 해를 구한다는 것을 보였다.
MBP 는 비선형 조합문제 (nonlinear combinatorial problem) 로 정형화되어진다. 볼록함수에 대한 piecewise linearization 기법을 이용하여, MBP는 선형조합문제 (linear combinatorial problem) 로 변형될 수 있다. 우선, 동일채널 간섭제약만을 고려하는 단순 최소 호손실율 문제 (SMBP) 를 다루었다. SMBP 를 좀 더 용이하게 다루기 위해서, 패턴 (pattern) 의 개념을 도입하여 문제를 변형시켰다. 라그랑쥐 이완과 서브그래디언트 최적화 기법을 이용하여, 최적해와의 차이에 관한 정보를 가진 양질의 해를 얻을 수 있다. 또한, 실험을 통해서 우리의 방법이 SMBP 를 풀기 위한 매우 효율적인 툴임을 보였다.
일반적인 MBP 문제에 대해서, 라그랑쥐 이완에 기초한 알고리즘과 GOS 개선체계에 기초한 알고리즘을 제시하였다. 라그랑쥐 이완에 기초한 알고리즘은 최적해와의 차이에 관한 정보를 가진 해를 제공한다. 이 알고리즘은 특수한 형태의 주파수간섭행렬 (compatibility matrix) 를 갖는 시스템에 대해서 좋은 해를 제공한다. GOS 개선체계에 기초한 알고리즘은 자동적응방식에 의해 점차 감소하는 목표 GOS 들의 순열을 생성한다. 실험을 통해 이 GOS 개선체계가 효율적인 툴임을 보였다.
마지막으로, 2단계 차용채널할당방식을 제시하였다. 처음 단계인 통상적인 채널할당단계에서는 이용 가능한 채널이 없을 경우에 인접한 셀들로부터 최소영 향차용전략 (impact-based borrowing strategy)에 의해 채널을 차용하게 된다. 두 번째 단계는 재할당 단계로 locked-channel 이용을 위한 재할당 절차와 효율적인 채널 재사용을 위한 절차로 구성된다. 시뮬레이션을 통해서 통신수요의 균등 및 불균등성에 관계없이 기존의 다른 방법들에 비해 우리의 방법들이 시스템 호손실율을 현저하게 감소시킴을 보였다. 또한 우리의 한 가지 방법은 비교한 다른 방법들에 비해 훨씬 적은 재할당 횟수를 필요로 하였다.
