This thesis considers a BSC location problem in a wireless communication network, where the locations of MSC and Cells are fixed, and the possible locations of BSCs and traffic arrival rate are also given. In the problem, the three issues of (i) constructing BSCs among possible locations, (ii) connecting BSCs to MSC (iii) connecting each BTSs to BSC are jointly determined to minimize the sum of the average queueing delay cost and the cabling cost and the setup cost of BSC. The proposed problem is formulated as a nonlinear binary integer optimization problem, which is NP-complete. A heuristic solution algorithm based on the Lagrangian relaxation and subgradient optimizations method is developed. To test the performance of the heuristic algorithm, a computational experiment is performed with randomly-generated numerical problems. The results show that the Lagrangian heuristic gives good solutions within a reasonable amount of computational time, and so it may be used effectively for practical problems.
이 논문은 이동전화국과 기지국의 위치는 사전에 결정되어 있고, 그리고 기지국제어기의 가능한 위치와 각 트래픽의 발생률도 미리 알고 있다는 가정하에서 무선통신 네트웍에서의 기지국 제어기 디자인 문제를 고려하였다. 이때, 이 논문은 평균 지연 비용과 연결 비용 및 기지국제어기 설치비용의 합을 줄이는 방향으로 가능한 위치들 중에서 기지국제어기를 설치하고 이 기지국제어기를 이동전화국과 연결하고 또한 이 기지국제어기를 셀들과 연결한다.
이와같이 제안된 문제는 비선형 바이너리 정수형 최적화 문제로 정의되었는데 직접적으로 풀기가 어려운 문제에 속한다. 따라서, 이 논문에서는 라그랑지안 방법에 의한 휴리스틱 알고리즘을 제안하였다. 이 알고리즘의 적합성을 보이기 위해 검증용 문제를 랜덤하게 만들어서 테스트를 해 보았다. 그 결과 라그랑지안 휴리스틱은 현실적인 문제에 대해 상당히 효율적인 결과와 합리적인 수행시간을 보여주었다.
