1. 연구의 배경 및 목적

스마트폰 등 이동통신기기가 원활한 서비스를 받기 위 해서는 실시간으로 움직이는 사용자의 이동체 위치정보 를 효율적으로 관리하기 위해 리포팅 셀(Reporting Cell)과 위치구역계획(Location area planning) 관리시스템에 대한 연구가 진행되고 있다[13, 4, 5, 11]. 이동체를 효과적으로 관리하기 위한 리포팅 셀 방법에서는 리포팅 셀과 아닌 셀로 구별해서 관리한다. 이 시스템의 이동체 위치 업데 이트 과정은 이동체가 리포팅 셀로 들어오면서 위치를 등 록하는 과정이고, 페이징 과정은 이동체가 위치정보를 마 지막으로 등록한 리포팅 셀로부터 다른 리포팅 셀을 거치 지 않고 이동할 수 있는 셀들을 추적하여 이동체를 탐색 하는 과정이다. 이동체의 위치관리는 위치등록 업데이트 (Location update) 비용과 이동체가 현재 어디에 있는지 탐 색해야 하는 페이징(paging) 비용을 효과적으로 관리하는 것이 목적이다. 위치관리를 위한 위치 등록은 이동체가 리포팅 셀로 이동하여 위치를 업데이트하면서 비용이 발 생하고, 이동해 들어오는 이동체의 수가 증가할수록 비용 은 증가한다. 그리고 이동체를 추적하기 위한 페이징은 탐색하는 셀의 수와 통화 연결의 요구가 많을수록 페이징 비용이 증가한다. 이동체 위치 등록비용과 이동체 탐색 페이징 비용은 트레이드 오프(trade-off) 관계이고, 총비용 이 최소화할 수 있는 시스템 설계를 위해 적절한 리포팅 셀 수와 위치를 결정하는 것이 필요하다[1, 3, 4].

이동체 위치관리시스템을 효율적으로 설계하기 위해 유전자알고리즘(genetic algorithm, GA), 파티클군집최적화 (particle swarm optimization, PSO), 개미군알고리즘(ant colony optimization, ACO), 인공벌군집(artificial bee colony, ABC) 등 다양한 방법을 적용하여 연구가 계속되었고 추가 적인 연구의 필요성이 대두 되고 있다. Subrata and Zomaya [10]은 교배와 돌연변이를 적용한 GA 방법과 페로몬과 선호도에 따라 개미가 먹이(해)를 탐색하는 ACO로 해를 탐색하는 방법을 제안하였다. Byun and Kim[1]은 지역 탐색을 하는 파티클과 전역 탐색을 하는 파티클의 가중치 조합을 통한 해 탐색 PSO방법을 제안하였다. Kim and Byun[4]은 벌들이 꽃의 꿀을 채취하는 과정을 알고리즘 으로 개발한 ABC로 해를 탐색하는 방법을 제안하였다. 본 논문에서 이동체 위치관리시스템 설계를 위해 제안하는 생물지리학적 최적화(Biogeography based Optimization, BBO) 방법의 차별성은 해 탐색 시 해를 변화(change)시켜 탐색하지 않고 해를 적응(adaptation)시켜 간다는 것이다. 예를 들어, GA 방법의 교배율과 돌연변이율은 일정한 값 을 사용하여 해를 교배하고 돌연변이 시키는 반면, BBO는 해 평가값에 따라 이주와 돌연변이를 시킨다. 해가 좋을 수록 다른 해에 도움을 주기 위해 특성을 이주(emigration) 시키고 해가 나쁠수록 다른 좋은 해로부터 특성을 이주 (immigration) 받아 해를 개선 적응해 나간다. 돌연변이도 좋은 해 일수록 돌연변이율을 낮게 적용하여 현재까지의 좋은 특성을 잃지 않으면서 다양한 해 탐색을 추구한다 [1, 4, 10, 12]. 따라서, 본 연구의 목적은 비교적 최근에 개발된 컴퓨터 지능(Computational Intelligence)인 BBO를 적용하여 이동체의 리포팅 셀 위치관리시스템을 최적설 계하는 것이다. 제 2장에서는 리포팅 셀 이동체 위치관리 시스템 설계 문제에 대하여 설명하였다. 제 3장은 BBO 최적화 방법과 최근 동향을 간략히 소개하고, BBO 방법을 리포팅 셀 위치관리시스템 문제에 적용하기 위한 해 표현 을 설명하였다. 더불어서, 이 BBO 방법의 탐색 효율성을 극대화하기 위해 BBO 방법의 성능을 개선하였다. BBO1은 새로 만든 해를 항상 업데이트하는 표준 방법이고 BBO2 는 새로 만든 해가 좋을 경우에만 업데이트하는 것을 적 용한 방법이고 BBO3는 새로 만든 해가 이전해보다 좋고 현재 해 그룹 모든 해(서식지, habitat)와 평가값이 다를 경우 업데이트하고 평가값이 일정 수준 이상의 좋은 해에 서만 이주시키는 것을 적용하여 개선한 방법이다. 4절에 서는 제안하는 BBO 방법의 성능을 검증하기 위해 64개 셀 위치관리 네트워크에 대하여 최적해 결과를 제시하였 다. BBO2와 BBO3 방법의 성능 검증은 실험을 통하여 비 교 분석하였다.

2. 이동체 위치관리시스템 문제

리포팅 셀 시스템에서 이동체에게 통화요구가 발생하 면 통화연결을 위해 이동체의 위치를 추적해야 하는데, 이동체가 최종적으로 위치를 업데이트 한 리포팅 셀부터 페이징 영역을 계산 한다. <Figure 1>에서 이동체의 위치 를 리포팅 하는 셀은 2, 5, 9, 10, 11, 12, 15번 셀이라고 가정하고 이 셀에 진입할 때는 이동체의 현재의 위치를 관리 시스템에 리포팅 한다. 나머지 셀 0, 1, 3, 4, 6, 7, 8, 13, 14은 리포팅 셀이 아니므로 이 셀에 진입할 때는 이동체의 현재의 위치를 리포팅 하지 않는다. 만약, 이동 체(스마트폰 사용자 A라 하자)가 이동하면서 리포팅 셀 2번에 진입하면, A의 위치는 셀 2번이라고 관리시스템에 리포팅 하여 최종적으로 업데이트한다. A는 2번 셀을 포 함하여 0, 1, 2, 3, 4, 6, 7, 8번 셀이 새로운 위치 등록 없 이 이동할 수 있는 페이징(탐색) 영역이다. 8개의 셀 수 를 2번 리포팅 셀의 주변값(vicinity value)이라 하고 페이 징 비용을 계산하였다. <Figure 1>의 예에서 리포팅 셀이 아닌 8번 셀에 현재 있는 이동체는 리포팅 셀 2, 5, 9, 12 번 리포팅 셀 중에 한 개의 리포팅 셀에서 최종적으로 위치를 리포팅 한 경우이다. 다시 말해서, 2번 셀에서 최 종 리포팅 했을 경우는 주변값이 8개(0, 1, 2, 3, 4, 6, 7, 8번 셀), 5번 셀에서 최종 리포팅 했을 경우는 주변값이 8개(0, 1, 3, 4, 5, 6, 7, 8번 셀), 9번 셀에서 최종 리포팅 했을 경우는 주변값이 7개(0, 1, 4, 8, 9, 13, 14), 12번 셀 에서 최종 리포팅 했을 경우는 주변값이 7개(0, 1, 4, 8, 12, 13, 14)의 페이징 대상입니다. 즉, 8번 셀이 가질 수 있는 주변값들은 8, 8, 7, 7 이고, 이 중 가장 큰 값인 8 이 8번 셀의 주변 값이라고 Subrata and Zomaya의 논문 에서 정의하였다[1, 4, 10, 11, 12].

<Figure 1>의 업데이트와 페이징 비용으로 구성된 총 비용은 식 (1)과 같다[10]. 셀 k로 이동하는 트래픽 양 Wm_k, 셀 k의 통화 요구량 Wc_k, 그리고 위치등록 업데이트 상수 C를 나타내고, 업데이트 비용이 페이징 비용보다 상대적 으로 크다. 식 (1)에서 만약 셀 k가 리포팅 셀일 경우는 의 사결정 변수 X_k는 1이 되고, 리포팅 셀이 아닐 경우는 0이 된다. V_k는 k번 셀의 주변값이다.

Godim[2]과 Suburata 외 1인[10]은 C를 10으로 사용하 였다. 본 논문에서는 C값을 5 또는 10일 때로 가중치 값을 나누어 비교 분석하였다. 이동체 위치관리 시스템 설계 해 평가 함수(비용함수)는 식 (1)과 같이 정의할 수 있고 제안하는 BBO방법을 적용하여 이진 의사결정변수 X_k로 수학적 모델화한 이진정수화 문제를 최적화하고자 한다.

3. BBO 최적화 방법의 적용

본 장에서는 이동체 리포팅 셀 위치관리시스템 설계 에 어떻게 효율적으로 BBO를 적용할 수 있는지 서술하 였다. 제 3.1절에서는 BBO의 기존 연구와 동향에 대하 여 설명하고, 제 3.2절에서는 서식지(habitat)인 해의 표현 과 BBO의 적용단계를 설명하였다.

3.1 BBO의 최근 동향

Simon[7]은 BBO의 성능이 기존 다른 휴리스틱 알고리 즘에 비하여 우월함을 검증하였다. BBO는 해를 나타내는 서식지(habitat)들이 유입(immigration)과 유출(emigration) 로 이루어지는 이주(migration)와 돌연변이(mutation) 과정 을 통하여 더 좋은 해를 탐색하고 다양한 새로운 해를 생 성해 나가는 컴퓨터 지능(computational intelligence) 방법 이다.

BBO 엘리티즘[8] 논문에서 BBO가 유전자알고리즘(GA) 보다 성능이 우월하고 엘리티즘(elitism)을 적용할 때 성 능이 더 좋아진다는 것을 설명하였다. 엘리티즘이란 현재 까지의 가장 좋은 해들을 계속 유지하려는 것이다. 즉, 일 반적으로 서식지의 평가값이 좋을수록 유입 이주율 ⋋가 작아지는데, 가장 좋은 해 z개에 대해서는 유입 이주율 ⋋ 를 0으로 조정하여 해당 해들이 유입 이주 없이 계속 살 아남아 있을 수 있도록 한다. 최근에는 엘리티즘이 적용 된 생물지리학적 최적화 BBO를 그리드컴퓨팅 스케줄링 에 적용하였다[6].

Simon et al.[9]은 조합최적화 문제에 BBO와 GA를 적 용 비교 분석하였는데, BBO가 다차원적 문제에 좋은 성 능을 보였다고 서술하였다.

이와 같이 기존 연구에서 검증된 BBO를 어떻게 이동 체 리포팅 셀 위치관리 문제에 적용하여 최적설계를 할 것인지 다음 절에서 구체적으로 설명하고자 한다.

3.2 서식지 해의 표현과 BBO 적용 단계

이동체 리포팅 셀 위치관리시스템을 위한 BBO의 서 식지로 나타낼 수 있는 해의 표현은 전체 셀의 수 16개 (0~ 15)를 길이로 하는 1차원 행렬의 형태이고, 각각의 모든 셀에 대하여 리포팅 셀(2, 5, 9, 10, 11, 12, 15번 셀) 은 1또는 리포팅 셀이 아닌 셀은0의 값으로 결정하여 표 현한다. <Table 1>은 <Figure 1>의 16개 셀을 한 개의 서 식지 해로 나타낸 것이다.

BBO 방법은 특정 해가 다른 해와 비교했을 때, 상대 적으로 우월하면 작은 유입 이주율을 적용하여 덜 변화 시켜 우월한 해를 유지할 수 있도록 하고 상대적으로 큰 유출 이주율을 적용하여 우월한 해의 특성을 우월하지 않은 해에 이주시킴으로써 우월하지 않은 해를 개선시킨 다. 상대적으로 좋지 않은 반대의 경우에는 큰 유입 이주 율을 적용하여 현재 해의 많은 변화를 주어 더 좋은 해 로 변화시킬 수 있다.

좋은 평가값을 가진 서식지 해는 나쁜 평가값을 가진 서식지 해로부터의 유입 이주율 식 (2) ⋋_k가 낮게 되어 현 재의 좋은 상태를 유지할 수 있도록 하고, 나쁜 평가값을 가진 다른 서식지로 유출 이주율 식 (3) μ_k가 높게 되어 다른 나쁜 평가값의 서식지들이 더 좋은 상태가 될 수 있 도록 한다. 이와 같은 서식지 해 k의 유입 이주율 ⋋_k와 유 출 이주율 μ_k는 식 (2)와 식 (3)에 따라 결정된다. 상대적 으로 나쁜 해 서식지 1의 ⋋₁은 상대적으로 좋은 해 서식 지 2의 ⋋₂보다 높고, 반대로 서식지 1의 μ₁은 상대적으로 서식지 2의 μ₂보다 낮다. E는 최대 유출 이주율, I는 최대 유입 이주율을 나타낸다. s_k는 해 k의 종의 수를 나타내 는데 해의 종의 수가 많을수록 상대적으로 좋은 해를 나 타낸다. 종의 수가 많다는 것은 해를 나타내는 서식지에 좋 은 특성을 많이 보유하고 있다는 상징적인 의미이고 좋은 해 일수록 상대적으로 큰 수로 표시한다. s_max는 서식지 의 최대 종의 수를 표시하고 가장 좋은 서식지 해의 종의 수이다.

이주가 마무리되면 식 (4)를 이용하여 돌연변이를 실행 하는데, m_h는 서식지 H의 돌연변이율을 나타낸다. 본 논 문은 이동체 리포팅 셀 위치관리시스템 최적화를 위해 식 (1)을 최소화하는 것이 목적이므로 P_H는 서식지 H의 식 (1)을 이용한 평가값의 역수, P_SUM은 군집 내에 존재하는 모든 서식지의 P_H 를 합한 값을 나타낸다. m_max는 사용 자가 정의하는 파라미터로써 돌연변이 최대 확률치를 나 타내고, 식 (1)의 평가값이 작은 좋은 서식지 해 일수록 돌연변이율은 작아져 현재 해를 가능하면 유지하고, 식 (1)의 평가값이 높은 나쁜 서식지 일수록 돌연변이율이 높아져 다양한 해 변형을 통한 다양한 해 탐색이 이루어 진다.

이동체 리포팅 셀 위치관리시스템 설계 문제에 BBO 방 법을 다음과 같은 단계로 적용하였다. 단계 5의 서식지 이 주와 단계 7의 서식지 돌연변이 후 BBO1, BBO2, BBO3 방법으로 차별화하여 BBO 방법을 적용하였다.

4. 실험결과 및 분석

본 절에서는 리포팅 셀 위치관리시스템 최적설계 문제 에 BBO 방법을 적용시킨 실험 결과에 대해 분석 검증하 였다. Intel(R) Core(TM)2 Quad CPU 2.33GHz, 4.00GB RAM, 윈도우7 32비트 운영체제, Visual C++ 환경에서 실 험하였다. 종료 조건은 일반적으로 사용자가 제시한 계산 시간 한도 내 또는 일정 세대가 진행되어도 해 개선이 되 지 않을 경우 종료한다. BBO 방법의 파라미터 중에서 최 대 유입 이주율 I 가 0.25, 최대 유출 이주율 E는 1, 최대 돌연변이율 m_max은 0.05, 엘리티즘을 적용하기 위한 적정 엘리트 수 z는 1, 해군의 수 POP은 100으로 실험을 통하 여 설정하였다. 식 (1)에 따라 각 셀의 통화요구량 Wc_k, 셀 k로 이동하는 트래픽 Wm_k는 Suburata and Zomaya[10]은 사용한 64개 셀로 이루어진 데이터를 사용하였다. 업데이 트와 페이징 탐색 비용으로 이루어진 총비용을 가중치 C 값이 5 또는 10이라고 가정하고 실험하였다.

<Figure 2>는 평가함수 식 (1)에서 가중치 C값에 따른 64개 셀 네트워크 최적해의 BBO1, BBO2, BBO3 방법의 수렴 경향을 나타낸 것이다. 가중치 C값은 기존 연구에 서와 같이 C값을 10으로 한 경우 <Table 2>뿐만 아니라 C값을 5로 사용한 결과 <Table 3>을 산출하였다. 기존 연구 에서 사용한 알고리즘들 GA, ACO, PSO와 ABC 적용 결과 [1, 4, 10]와 본 논문에서 제안하는 BBO1, BBO2, BBO3 방법을 비교 분석하였다.

<Figure 3>(a)(b)는 실험 결과 중에서 가장 최선의 결 과를 제시 한 것인데, 64개 셀 최선해 통화요구량 1콜 당 비용과 최적설계 결과를 나타낸 것이다. <Figure 3(a)>와 같이 C 값이 10일 경우는 64개 셀 중에서 검은색으로 표 시된 리포팅 셀 39개, 흰색으로 표시된 리포팅 셀이 아 닌 셀로 나머지 25개 셀을 선택해야만 최적 위치관리시 스템을 설계할 수 있다. <Figure 3(b)>와 같이 C 값이 10 에서 5로 상대적으로 작아질 경우 업데이트 비용이 작아 지기 때문에 해에 리포팅 셀로 선택된 수가 45개로 커지 는 것을 알 수 있다.

<Table 2>와 <Table 3>은 해의 평가함수 식 (1)에서 기존 연구[1, 4, 10, 12]에서 업데이트 비용의 가중치 C로 사용한 10과 5를 사용하여 결과를 비교한 분석한 것이다. 본 논문에서 제안하는 BBO3가 GA, ACO, PSO보다는 월등히 우월하였고 ABC 방법과 비교했을 때는 성능이 비슷한 것으로 분석되었다. 단지, 가중치 C가 10인 경우 BBO3의 최적해 탐색률이 100%이고 ABC는 탐색률이 99%로 BBO3가 약간 우수하였다.

결론적으로 BBO3(새로 만든 해가 이전해보다 좋고 모 든 서식지와 평가값이 다를 경우 업데이트하고 일정 랭킹 이상의 서식지에서만 이주시키는 것을 적용한 BBO 방 법)가 가장 좋은 해를 탐색하고 편차 없이 안정적으로 해 를 탐색할 수 있고 최적해 탐색률도 매우 뛰어나 모든 면 에서 BBO3 최적화 방법이 우월한 것을 알 수 있다.

5. 결 론

본 논문에서는 이동체의 위치등록 업데이트와 현재의 위치 탐색을 위한 페이징 과정을 효율적으로 수행하기 위한 리포팅 셀 위치관리시스템 설계 방법을 제안 하고 그 성능 을 평가 분석하였다. 제안한 생물지리학적 최적화(BBO) 최적 설계 방법은 휴리스틱 알고리즘 중에서 최근에 개발된 최적화 방법으로써 다차원 문제와 조합최적화 문제에 장점 을 가지고 있어 리포팅 셀 위치관리시스템 설계에 유리하 다. 또한, 위치관리시스템 설계에 적합하도록BBO 방법을 개선 발전시키기 위하여 BBO1, BBO2, BBO3 차별화 방법 을 적용하여 서식지 이주와 돌연변이 후 우수한 해가 살아 남을 확률을 높여 BBO 방법의 성능을 향상시켰다.

BBO 방법의 우월성을 검증하기 위해 기존 연구에서 사 용한 64개 셀 네트워크 문제에 적용하여 실험 결과를 비교 분석하였다. 실험 결과에 따르면 제안한 BBO 방법이 GA, ACO, PSO 방법보다 성능이 우수하였고 ABC 방법과 비 교했을 때는 성능이 약간 우수한 것으로 분석되었다.