셀룰러 네트워크에서의 셀-스위치 할당 문제 = (A) Cell-to-Switch Assignment Problem in Cellular Mobile Networks

다국어 초록 (Multilingual Abstract)

In designing and operating cellular networks, it is assumed that the area of coverage is geographically divided into cells. Among these cells, a certain number of cells are chosen to install switches that serve as relays for communications between any pair of cells. Then, each cell is assigned to switches to complete the cellular network. This decision regarding assignment of cells to switches is known as a CSA (Cell-to-Switch Assignment) problem. The problem is based on the minimization of communication link cost and handover cost. Since this problem is a so-called NP hard, many researches have proposed heuristic-based algorithms to provide near-optimal solutions within a reasonable computation time. Considering these characteristics of the CSA problem, this work develops a genetic algorithm and a local search algorithm. Throuout a number of experiments, the performance of the proposed algorithms are evaluated, and compared with exisisting heristic methods.

목차 (Table of Contents)

• Table of Contents = iii
• 1 서론 = 1
• 1.1 연구 배경 = 1
• 1.2 셀룰러 네트워크 구성 = 4
• 1.2.1 이동통신 시스템의 구성요소 = 4
• 1.2.2 핸드오버 (HANDOVER) = 12
• 1.2.3 셀룰러 패턴 = 16
• 2 CSA 문제 = 24
• 2.1 단순 호밍 CSA 문제 = 25
• 2.2 이중 호밍 CSA 문제 = 26
• 2.3 스위치 위치를 고려한 문제 = 28
• 3 CSA 문제 해결을 위한 경험적 방법 = 30
• 3.1 Heuristic 1-Single = 30
• 3.2 Heuristic 2-Single = 31
• 3.3 Heuristic 1-Dual = 32
• 4 유전자 알고리듬과 국부 탐색 알고리듬 = 34
• 4.1 CSA 문제에서의 유전자 알고리듬 = 34
• 4.1.1 경험적 방법의 해석이 필요한 순열 표현 방법 = 34
• 4.1.2 유전 연산자 = 40
• 4.1.3 유전자 알고리듬 = 42
• 4.2 국부 탐색 알고리듬 = 42
• 4.2.1 단순 호밍 문제를 위한 국부 탐색 방법 = 43
• 4.2.2 이중 호밍 문제를 위한 국부 탐색 방법 = 44
• 5 실험 및 분석 = 45
• 5.1 실험 데이터 = 45
• 5.2 단순 호밍 = 49
• 5.2.1 실험 결과 = 49
• 5.2.2 국부 탐색 알고리듬의 분석 = 55
• 5.3 이중 호밍 실험 결과 = 58
• 6 결론 = 65
• 참고 문헌 = 67
• 부록 = 69