Recently, the number of mobile communication subscribers has explosively increased. Because the electromagnetic spectrum for the mobile cellular communication is limited, it is necessary that cellular systems use their frequency channels as efficiently as possible. The lack of capacity is one of the most important problem among a number of cellular system problems. There has been a great deal of effort to increase the capacity of the cellular radio systems. Some techniques are developed for this purpose. They are digital multiple access technology : for example sectorization, cell splitting, power control etc. If wireless communication system cannot serve sufficient users, it is necessary to build additional base stations (BSs).
In this paper we consider a problem of minimizing the construction cost of the additional BSs to cover increased traffic. We call this problem cell planning with capacity expansion (CPCE). We divide the area to be covered into a number of subareas which are called traffic demand areas (TDAs). It is assumed that each TDA has traffic demand. The TDA should be connected a BS which is able to serve it with sufficient quality. We define the potential service area (PSA) of each BS and the capacity of each BS. We formulate this problem and convert it into a graph partitioning problem.
We devised a tabu-search based heuristic algorithm for this problem and tested the efficiency of the proposed algorithm with some randomly generated examples. We obtained near-optimal solutions with the proposed algorithm.
최근에 이르러 이동통신의 가입자 수는 폭발적으로 증가를 하고 있다. 이동통신을 위한 주파수 자원은 한정이 되어 있기 때문에, 셀룰라시스템은 주파수 채널을 가능한 효율적으로 이용해야만 한다. 여러 가지 셀룰라 시스템 문제들 중에서 용량의 부족을 해결하는 문제는 가장 중요하다. 그래서 셀룰라 시스템의 용량을 증대시키기 위해서 많은 노력과, 여러 가지 기술들이 개발되었다. 주로 디지털 다중접속에 관한 기술들이다. 예를 들어 셀 섹터화, 셀 분할, 출력조절 등이 있다. 그러나 이동통신시스템이 사용자들에게 충분한 서비스를 제공하지 못한다면, 새로운 기지국을 설치해야만 한다.
이 논문에서 우리는 증가된 수요를 감당하기 위해서 새로 설치해야 하는 기지국의 건설 비용을 최소화하는 문제를 생각해보았다. 이 문제는 "용량확대를 고려한 셀 계획" (CPCE : cell planning with capacity expansion)이라고 명칭 했다. 전체 서비스 지역을 TDA (traffic demand area)라고 불리는 작은 지역으로 나누고, 각 TDA는 수요를 가지고 있다. 또한 모든 TDA는 충분한 품질의 서비스를 제공하는 하나의 기지국에 연결되어야 한다. 각 기지국은 서비스 가능지역과 용량에 대한 제약을 가지고 있다. 우리는 이 문제를 공식화하고, 그래프 분할문제로 바꾸어서 풀었다.
타부서치(Tabu-Search)에 바탕을 둔 알고리즘을 제안하였고, 무작위로 만든 예제들을 사용해서 이 알고리즘을 효율성을 실험하였다. 우리는 최적에 가까운 해를 구할 수 있었다.
