1연구의 배경과 목적

무선통신 네트워크에서 이동체의 위치관리는 매우 중요 한 문제이고 이동체의 위치 정보의 효율적인 관리를 위해 Reporting cell과 Location area(LA) 셀 그룹핑 방법 등 이 동체 위치관리시스템 설계 방법에 대한 연구가 다양하게 진행되었다. 또한, 최근에도 이동체 위치관리 방법의 추가 적인 연구의 필요성이 계속해서 제기되고 있다[6, 17]. 이 연구를 통하여 유비쿼터스[4] 및 위치기반서비스[1]의 향 후 발전 방안 등을 모색할 수 있다.

본 논문에서 최적 설계하고자 하는 위치관리 LA 셀 그룹핑 방법은 무선 통신 네트워크 서비스가 도달 가능 한 범위를 LA로 분할하고 각각의 LA는 연속된 셀들로 구성 된다. 각 셀의 기지국은 각 셀이 어느 LA에 속하는 지를 식별한다. 그러므로 이동체가 새로운 LA에 속하는 셀로 이동할 때에 그 위치를 센터에 보고하고 업데이트 해야 한다. 이동 통신 사용자로부터 특정한 이동체로 연 결 요청이 들어오면 무선 통신 시스템은 이동체가 마지 막으로 업데이트된 위치를 중심으로 LA안에 있는 모든 셀을 탐색하여 이동체간의 통화를 연결하게 된다. LA 셀 그룹핑 방법에서 핵심문제는 총 위치관리 비용이 최소화 되는 LA그룹 수와 어떤 셀이 어떤 LA에 소속되어야 하 는지 결정해야 하는 것이다.

LA 위치관리 셀 그룹핑 문제는 NP-complete로 알려져 있고 최적해를 탐색해 내기 위한 휴리스틱 알고리즘은 다 양하게 적용되어 왔다. Merchant[13]는 가장 먼저 셀의 LA 할당 문제의 수리적 모델을 제시하였다. Bhattacharjee[2] 은 셀의 할당 문제를 각 LA 당 최적 셀의 수를 결정하고, 총비용을 최소화하기 위해 셀들을 어느 LA에 할당 할 것 인지 결정하였다. Demirkol[5]와 Taheri[18]는 LA그룹핑 문제를 simulated annealing(SA) 방법으로 Kim[11]은 생물 지리학적 최적화(biogeography based optimization) 방법으 로 가장 좋은 해를 탐색하고자 했다. Pierre[14]는 타부서치 를 Quintero[16]은 유전자 알고리즘을 적용하였다. Prajapati [15]는 Apriori 알고리즘을 사용하여 LA그룹핑 문제의 해 를 탐색하고자 했다. Kim[12]은 LA그룹핑 문제에 개미군 최적화(Ant colony optimization, ACO) 방법을 적용하였고 Byeon[3]은 파티클군집최적화(particle swarm optimization, PSO) 방법을 적용하여 최적설계 하였다. 이와 같은 기존 최적화 방법들은 파라미터 값들을 어떻게 설정하는가에 따라 수렴 및 최적해 탐색 결과가 매우 달라질 수 있다는 문제점이 있다. 그러나, 본 논문에서 제안하는 인공벌군집 (artificial bee colony, ABC)[7, 8, 9] 방법은 다른 휴리스틱 알고리즘과 비교하여 파라미터 수가 작아 파라미터 값에 민감하지 않고 상대적으로 안정적인 해 탐색이 가능하다 는 장점이 있다[10].

셀 그룹핑 문제는 이동체의 핸드오프 트래픽과 이동체 를 탐색하는 페이징 양의 변화와 환경(인구 밀집 지역 등) 에 따른 무선네트워크 운용정책에 맞는 최적해의 도출이 필요하다. 본 논문의 목적은 인공벌군집(ABC)을 적용하 여 위치관리 LA 셀 그룹핑을 설계하는 것이다. 본 논문의 제 2장에서는 LA 셀 그룹핑 문제를, 제 3장에서는 이 문제에 적용가능한 인공벌군집 방법을 설명하였다. 제 4장에서는 16, 36, 64개의 셀로 이루어진 예제 실험을 통하여 셀 그룹 핑 문제에 대한 ABC 방법의 성능을 분석하고 검증하였다.

2LA 셀 그룹핑 문제

기존 연구 [3, 12, 13]에서 이동체 위치관리를 위한 LA 셀 그룹핑 문제를 식 (1)~식 (6)과 같이 수리적 모델화하 고 체계화하였다. 본 논문의 제 3장에서 제안할 인공벌 군집(artificial bee colony, ABC)방법 적용 시 해의 평가 값을 계산할 때는 식 (1)을 사용하였고 식 (2)~식 (6)을 적용하여 가능해 인지를 검증하였다. 가능해는 항상 셀 간의 연결성을 보장해야 하는 것은 아니며 더 좋은 해를 탐색해 가는 과정에서 셀간의 연속성이 있는(핸드오프 비용이 작은) 해가 선택 가능하다.

식 (1)과 같이 총비용 함수로 공식화할 수 있다. 위치 업데이트 비용에 해당하는 핸드오프 비용(다른 LA에 할 당되어 있는 두 셀 간의 핸드오프 트래픽 비용)과 페이 징 비용(특정 통화요구에 대한 이동체를 탐색하기 위한 탐색 비용)으로 구성된다. 총비용함수를 최소화하기 위 해서 n개의 셀을 m개의 LA에 어떻게 할당해야 하는 가 를 의사결정 해야 한다.

목적식 : Minimize

y_ij는 셀 i 와 셀 j가 같은 LA에 할당되면 1의 값을 갖 고 그 외의 경우에는 0값을 갖는 이진변수 이고 식 (4)로 표현된다. h(i, j)는 셀 i 에서 셀 j로 이동하는 트래픽양 을 나타낸다. w_cj는 셀 j의 통화요구량을 나타내고 u_j는 셀 j가 LA k에 할당되었을 경우 LA k에 할당된 모든 셀의 수이고 u j = ∑ i = 1 n x i k , k = 1 , ⋯ , m (x_ik는 셀 i 가 LA k 에 할당되었을 경우는 1, 그렇지 않을 경우는 0으로 하 는 이진변수)로 나타낼 수 있는데, x_ik가 모두 결정되면 자동적으로 결정된다. C 는 위치 등록 업데이트 상수이다.

식 (2)는 모든 셀은 하나의 LA에만 할당될 수 있음을 나타낸다.

식 (3)에서 z_ijk는 셀 i와 셀 j가 같은 LA k에 할당되 었을 경우 1의 값을 갖고 그 외의 경우에는 0 값을 갖는 이진변수이다.

식 (5)는 각 LA의 수용할 수 있는 통화요구용량에 관 한 식이며 M_k는 LA k에서 수용할 수 있는 통화요구 최 대 용량을 나타낸다. 식 (6)은 각 LA에 포함될 수 있는 최대 셀의 수에 관한 식이며 N_k는 LA k에 포함될 수 있 는 최대 셀의 수를 나타낸다. M_k와 N_k는 시스템을 사용 하는 환경(평지 또는 산악 지역과 인구 밀집 또는 희소 지역)에 따라 운용자가 결정하여 적용할 수 있다.

3인공벌군집 방법의 적용

인공벌군집(artificial bee colony, ABC) 방법은 벌들이 꽃(Food source, FS)을 찾아 꿀을 채취하는 메커니즘을 알고리즘으로 개발한 것이다. 이 방법에서는 벌을 employed bee(EB), onlooker bee(OB), scout bee(SB)로 역할에 따라 구분한다. EB는 현재 위치의 꽃에서 가까이 있는 꽃을 탐색하여 더 많은 꿀을 가지고 있는 꽃을 찾아내듯이 현 재의 해의 이웃해를 탐색하여 더 좋은 해를 탐색 한다. OB는 각각의 EB들이 탐색하고 있는 꽃들의 위치 정보 를 참조하여 찾아낸 꽃의 꿀을 채취하듯이 여러 개의 해 들로부터 찾아낸 해를 탐색하여 더 좋은 해를 추가적으 로 탐색해 간다. SB는 EB와 OB가 더 이상 더 좋은(꿀이 많은) 꽃을 탐색해 내지 못할 때 새로운 위치의 꽃을 찾 아 꿀을 채취하듯이 기존의 해들과 다른 임의의 해를 탐 색하는 역할을 한다. 결과적으로 EB와 OB는 수렴성을 추구하여 더 좋은 해를 탐색하려고 하는 반면, SB는 다 양성을 추구하여 더 좋은 해를 찾을 수 있는 가능성이 있 는 새로운 해를 탐색하는데 ABC 알고리즘은 이러한 수 렴성과 다양성의 균형을 조절하여 최적화를 하는 방법이 다[7, 8, 9, 10].

본 절에서는 LA 셀 그룹핑 문제에 인공벌군집(ABC) 을 적용하여 보다 효율적인 설계를 하고자 한다. ABC의 해를 표현하고 ABC의 초기해 및 이웃해 생성 방법과 적 용단계별 메커니즘을 <Figure 1>과 같이 설명하였다. LA 셀 그룹핑 문제의 해 표현은 다음과 같이 나타낼 수 있다. <Figure 2>의 16개 셀 예제에서 3개의 LA그룹 1, 2, 3으 로 구성 된 해로 표현 가능하다. 즉, LA그룹 1(셀 번호 0, 1, 4, 5, 8, 9, 12), LA그룹 2(셀 번호 2, 3, 6, 7), LA 그룹 3(셀 번호 10, 11, 13, 14, 15) 로 표현된다. 즉, 16개 셀 번호(0~15)에 LA그룹 번호 1, 2, 3을 1차원으로 표시 할 수 있다.

ABC를 LA 셀 그룹핑 설계 문제에 적용 하여 최적해 를 탐색해 낼 수 있다[7, 8, 9, 10]. ABC 메커니즘은 각 해의 이웃 해를 찾는 역할을 하는 EB, 각 해의 평가값의 확률에 따라 추가적으로 이웃 해를 찾는 OB, 그리고 다 양한 해를 탐색하기 위한 SB로 작동된다. 모든 해의 평 가값을 계산할 때는 식 (1)을 사용하였고 식 (2)~식 (6)을 적용하여 초기해 및 이웃해 생성 시 가능해인지를 확인 하였다.

단계 1에서는 초기 해군의 해의 수를 SN 라 정하고 EB 의 수, OB의 수는 모두 해의 수와 같게 정한다. 또한, 각 해의 더 좋은 이웃해 탐색 최대 수(Limit), 종료 조건(세 대 수, 사용자가 제시한 시간제한 등)을 결정한다. 가장 중요하고 관리해야 할 파라미터는 Limit이다.

단계 2에서는 초기 가능해 군을 생성하기 위한 것이 다. 각 셀에 대하여 가능한 LA그룹을 랜덤하게 할당하여 해들을 생성하여 초기해 군을 탐색한다. 초기해는 가능 한 평가값이 좋은 해 생성을 위해 인접해 있는 셀과 트 래픽 유동량이 많은 셀을 LA그룹의 중심에 위치시킬 수 있도록 하였다. 트래픽 유동량이 많은 셀이 각 LA그룹에 중앙 부분에 위치함으로 해서 LA그룹간의 핸드오프 트 래픽 비용을 가능한 최소화 할 수 있기 때문이다.

단계 3에서는 각 초기 해에 대하여 EB를 결정하고 각 초기 해들의 지역탐색을 위하여 이웃 해를 탐색한다. 각 해에 대하여 더 좋은 해가 생성되면 더 좋은 해로 업데 이트 하고 이웃해 탐색 시도 횟수 카운터 Trial을 0으로 설정한다. 그렇지 않을 경우(더 좋은 해가 생성되지 않으 면), 해당 해의 Trial의 횟수를 증가시킨다.

단계 4에서는 단계 3의 EB에 의한 모든 해의 이웃해 탐색 후 갱신된 초기 해군의 모든 해를 사용하여 식 (1) 을 적용한 평가값(i번째 Food source의 평가값 f_i )에 비 례하는 확률 식 (7)로 해를 선택하여 이 해의 이웃해와 비교하여 더 좋은 해가 생성되면 더 좋은 해로 업데이트 하고 이웃해 탐색 시도 횟수 카운터 Trial을 0으로 설정 한다. 그렇지 않을 경우(더 좋은 해가 생성되지 않으면), Trial의 횟수를 증가 시킨다. 이와 같은 전역해 탐색은 OB가 수행한다. OB의 역할은 평가값이 우수한 해의 이 웃해를 추가적으로 더 세밀하게 해를 탐색하는 것이다.

해(Food source) i를 선택할 확률

단계 5에서는 이웃해 탐색 시도 횟수 카운터 Trial중 가장 큰 해의 Trial이 이웃해 탐색 최대수 Limit보다 같 거나 클 경우 해당 해는 더 이상 그 해의 이웃해를 탐색 하지 않고 탈락 시킨다. 탈락시킨 해 수만큼의 해들을 SB 를 통하여 임의적으로 생성하여 지역 해에 빠지지 않고 다양한 해 탐색을 추구함으로써 전역 해를 탐색할 수 있 도록 한다. 이 모든 단계 수행 후 종료 조건(세대 수, 사 용자가 제시한 시간제한 등)에 맞으면 종료하고 그렇지 않으면 단계 3의 EB의 이웃해 생성부터 다시 반복 수행 한다.

EB와 OB에 의한 이웃해 생성 시 하나의 셀에 대한 LA그룹 번호를 변경하는데 이 셀을 선택할 시에는 LA 그룹의 미세 조정을 통하여 해의 수렴이 가능할 수 있도 록 LA간의 경계면에 위치한 셀 중 하나를 선택하였다. <Figure 1>의 경우에는 셀 1, 2, 5, 6, 9, 10, 11, 12, 13이 경계면에 위치하므로 이 셀들 중에 하나의 셀을 랜덤하 게 선택할 수 있다.

본 논문의 목적인 LA 셀 그룹핑이 그룹화 문제이기 때문에 LA가 서로 다른 경계면의 셀을 선택하여 다양한 LA그룹화의 이웃해를 선택하여 탐색하는 것이 효율적이 다. 이렇게 선택된 셀과 LA그룹이 다른 인접한 셀의 LA 그룹 중 하나로 변경하며 트래픽 유동량(h(i, j)는 셀 i 에서 셀 j로 이동하는 트래픽양)이 많은 셀과 같은 LA 그룹이 될 확률을 높여 핸드오프 트래픽 비용을 가능한 최소화 하고자 했다. <Figure 1>의 셀 5를 선택 했을 경 우에는 LA그룹 2 혹은 LA그룹 3 중 하나로 할당가능 하 며, 그 확률은 아래와 같다.

셀 5가 LA그룹 2에 할당될 확률

= h ( 2 , 5 ) + h ( 5 , 2 ) + h ( 5 , 6 ) + h ( 6 , 5 ) h ( 2 , 5 ) + h ( 5 , 2 ) + h ( 5 , 6 ) + h ( 6 , 5 ) + h ( 5 , 10 ) + h ( 10 , 5 ) = 78.667 + 38.25 + 108.333 + 78.667 78.667 + 38.25 + 108.333 + 78.667 + 276.333 + 78.667 = 303.917 658.917 = 0.461237

셀 5가 LA그룹 3에 할당될 확률

= h ( 5 , 10 ) + h ( 10 , 5 ) h ( 2 , 5 ) + h ( 5 , 2 ) + h ( 5 , 6 ) + h ( 6 , 5 ) + h ( 5 , 10 ) + h ( 10 , 5 ) = 276 , 333 + 78.667 78.667 + 38.25 + 108.333 + 78.667 + 276.333 + 78.667 = 355 658.917 = 0.538763

즉, 셀 5가 LA그룹 3으로 그룹화되는 것이 평가함수 비 용을 줄일 수 있는 확률 53.8%로 LA그룹 2로의 확률 46% 보다 높을 것으로 분석할 수 있다. 이와 같이 EB와 OB에 의해 이웃해를 탐색하고 더 좋은 해를 탐색해 나간다.

일반적인 ABC는 단계 5에서 SB가 임의적인 방법으로 새로운 해를 탐색 하여 다양한 해 탐색을 할 수 있으나, 이러한 다양성 추구는 ABC 알고리즘을 적용하는데 있어 서 후반에는 해를 집중적으로 탐색하여 해를 수렴시키는 데 방해가 될 수 있다. 따라서, 본 연구에서는 이러한 문 제를 개선하기 위하여 단계 5를 적용하기 전에 랭킹 전 략을 추가 적용하였다. 랭킹전략에서는 <Figure 2>와 같 이 우수한 해들을 미리 정한 수만큼 선택하고 평가함수 값에 비례하는 확률을 적용하여 새로운 좋은 해를 생성 하여 투입하고 나쁜 해는 탈락시켜 수렴성을 가속시키는 역할을 수행한다. 즉, 새로운 해의 각 요소들은 평가값이 더 뛰어난 기존 해들의 요소들을 더 높은 확률로 선택하 여 새로운 해를 생성하기 때문에 더 좋은 해를 생성할 수 있는 가능성이 높다.

<Figure 3>에 (a)와 같이 4개의 해(Food source) 중 평 가값이 가장 나쁜 Food source 3이 탈락 되고 <Figure 3> 에 (b)의 과정으로 생성한 New Food source가 그 자리를 대신한다. 만약 평가값이 가장 좋은 2개의 Food source를 사용한다면 Food source 2, 4의 첫 번째 셀 “0”이 각각 LA 그룹 1과 그룹 2이므로 New food source의 첫 번째 셀 “0”은 LA그룹 1과 그룹 2에 할당될 수 있다. 첫 번째 셀 “0”이 각 LA그룹에 할당될 확률은 평가값이 작을수록 좋 은 해 이므로 각 Food source의 평가값에 반비례하여 다 음과 같이 계산한다.

셀 0이 LA그룹 1에 할당될 확률

= 1 16.4329 1 16.4329 + 1 16.7380 = 0.5046

셀 0이 LA그룹 1에 할당될 확률

= 1 16.7380 1 16.4329 + 1 16.7380 = 0.4954

즉, New food source의 첫 번째 셀 “0”은 50.46%로 LA그 룹 1에 49.54%로 LA그룹 2에 할당될 수 있는 해(Food source)를 생성하게 된다. 이와 마찬가지로 다른 셀(셀 1~ 15)도 Food source 2와 4를 사용하여 LA그룹을 생성하여 새로운 Food source를 만들어 해 군(Solution population)에 투입하여 더 좋은 해로 수렴시킨다.

4실험결과 및 분석

본 장에서는 LA 셀 그룹화 문제에 본 논문에서 개발한 인공벌군집 ABC 기법을 적용시킨 실험 결과에 대해 분석 하였다. 실험은 총 3개의 예제들(각각 16, 36, 64 셀 네트 워크)의 데이터를 사용하여 실험을 수행하였다. ABC 방법 을 적용시킨 실험 결과는 기존의 개미군최적화(ant colony optimization, ACO)와 파티클군집최적화(particle swarm optimization, PSO) 실험 결과와 비교 분석을 통하여 ABC의 효율성을 검증하였다.

ABC 적용을 위한 파라미터를 설정하는데 세대수는 16 개 셀은 100세대, 36개 셀은 500세대, 64개 셀은 1,500세 대로 세대가 모두 진행되면 종료되도록 하였다. 한 세대 당 해(Food source)의 개수인 SN 과 이웃해 탐색 최대수인 Limit의 파라미터 값은 다음과 같이 설정하였다. 16개 셀은 SN = 10, Limit = 400, 36개 셀은 SN = 330, Limit = 400, 64개 셀은 SN = 80, Limit = 400으로 설정하였다. 랭킹 전략에 사용되는 우수한 해의 수는 5로 설정하였다. 본 실험에서의 이와 같은 파라미터들은 다수의 반복적인 실 험을 통해 가장 효율적이라고 판단되는 수치를 적용하였 고 비교되는 ACO[12], PSO[3]와 동일한 환경 조건하에서 실험되었다.

<Figure 4>과 <Figure 5>는 식 (1)을 적용하여 평가값 을 계산하였고 (a)의 그래프는 ABC 알고리즘을 적용했 을 때 세대에 따라 콜 당 비용이 최적해로 수렴되는 경 향을 2차원 그래프로 보여주고 있다. (b)는 ABC 알고리 즘을 적용했을 때 세대에 따라 LA수 변화와 콜 당 비용 이 최적해로 수렴되는 경향을 3차원 그래프로 보여 주고 있다. (c)는 ABC 알고리즘을 적용했을 때 최적해 36개의 셀과 64개의 셀의 실험한 결과를 나타낸 것이다. 실험 결과에 따르면 36셀과 64셀 네트워크의 경우 각각 총 9개 와 15개의 LA그룹으로 구성되는 최적해가 도출되었고 각 문제에 대한 가장 좋은 콜 당 비용값은 11.094와 12.501 이다.

<Table 1>은 ACO[12]와 PSO[3] 기존 결과와 본 논문 에서 제안한 ABC의 실험결과를 비교한 것이다. ABC를 적용 했을 때 가장 좋은 결과를 산출할 수 있었다. 본 논문에서 제안하는 ABC 방법의 콜 당 비용 최적해 탐색 확률이 16, 36, 64개 셀 문제에 대하여 각각 100%, 93%, 13%로 기존 PSO 방법 100%, 79%, 5%보다 높은 것으로 분석되어 상대적으로 성능이 우수하고 안정적인 해 탐색 이 가능하였다. ABC와 PSO 방법의 최적해 탐색 평균계 산시간은 36셀 문제는 3.9~7.9초, 64개 셀 문제는 4.5~4.7 초로 두 방법이 유사하게 나타났다.

5결 론

무선네트워크에서 이동체의 효율적인 관리를 위해 Location area(LA) 셀 그룹화 설계가 필요한데, 이를 위하여 전체 셀에 대한 LA그룹 수를 정하고 어떤 LA에 어떤 셀 을 할당할 것인지를 결정해야 한다.

본 논문의 목적은 LA 위치관리시스템의 셀 그룹핑 문 제를 효율적으로 최적 설계할 수 있는 인공벌군집(artificial bee colony, ABC) 방법을 제안하는 것이다. 이를 위 해 LA 셀 그룹핑 문제에 적용할 수 있도록 제한된 자원 내에서 해를 찾아 LA 셀 그룹핑 문제의 총비용을 최소화 할 수 있는 ABC 탐색 방법을 개발하였다. 제안한 ABC 방법이 기존 개미군최적화방법(ACO)과 파티클군집최적화 방법(PSO)방법보다 우수하고 안정적인 해 탐색이 가능한 것으로 실험을 통하여 분석되었다.