The increased demand for wireless mobile communications is confronted by the limitation posed by finite available bandwidth such as signaling traffic in mobile system. So, many researches have been done in order to solve bandwidth limitation of large-scale mobile communication systems by mobility management. Generally, mobility management problems are summarized into two grand categories, one is radio mobility problem which is related with handover process and the other is network mobility problem well known as a cell clustering problem. Location area problem is to divide the coverage area into many location areas (LAs) which are sets of adjacent cells. So, in many cases, location area problem can be considered as a node clustering problem that arises in designing network communication system. Various constraints such as connectivity requirement for physical structures of mobile system on the LA problem need to be considered. The primary issue in this problem is how to construct the cost-effective system by grouping the cells into the location areas. In this thesis, we show the formal definition and solve the problem by using the 0-1 integer programming formulation by decomposing the entire problem into a master problem and a column generation problem. The master problem is solved by a column generation technique and column generation problem is solved by a branch and cut algorithm. And then we will show an optimized LA clustering solution.
이동 통신망에서 이동 단말기들은 위치 추적을 받고 이에 따른 등록이 필요하다. 현재 이동단말 이용자들의 위치 등록은 IS-41 표준안을 따르고 있다. 이를 위한 많은 방법들이 있는데 본 논문에서는 location area단위로 위치등록을 하는 방법을 고려하였다. 즉, 이동 단말기가 다른 기지국에 들어갈 때마다 위치등록을 하고, 해당 기지국은 단말기를 전화가 걸려 올 때 호출하는 방식은 그 비용이 너무 많이 들고 시스템에 너무 많은 부하를 주게 되어 비효율적이다. 그래서 일반적으로 Location area (LA) 단위로 단말기의 위치를 등록하는 방법이다. LA라는 것은 몇 개의 셀 묶음을 말하는데, 즉 셀을 옮길 때마다 기지국에 자신의 위치를 알리지 말고, 하나의 cell의 group인 LA를 벗어날 때만 알리자는 것이다. 이런 방법을 쓸 경우, 이 LA크기의 결정이 paging 시의 cost와 tradeoff 가 있다는 것을 고려하여 이에 따라 LA의 크기를 결정해야 한다. 이는 총 LA의 비용은 위치를 update 하는 비용과 단말기의 호출 비용의 합으로 주어지기 때문이다. 이러한 LA의 특징을 바탕으로 본 논문에서는 cell을 clustering하는데 있어서 비용을 최소화하는 것을 목적으로 하였다. 본 논문에서는 이 문제를 풀기 위해서 0-1 정수계획문제로 모형화 하였고 많은 수의 cluster들의 패턴을 다루기 위하여 열생성기법을 사용하여 해결하였다. 또한 정수해를 찾아내기 위하여 특정 변수를 정수로 고정하여 푸는 방안을 사용하였다.
실험 결과는 paging과 관련된 비용과 update와 관련된 비용을 parameter로 고려하여 산출하였는데, paging관련 비용이 높을수록 LA에 포함되어 있는 cell의 수가 적었고 (즉, 전체 system에서의 LA의 수가 많아졌고) update비용이 높아질수록 LA에 포함되어 있는 cell의 수가 많아졌다(즉, 전체 system에서의 LA의 수가 적어졌다).
