다목적 무선 네트워크 설계를 위한 최적화 모델 및 알고리즘

다목적 무선 네트워크 설계를 위한 최적화 모델 및 알고리즘 조동원 조수연 이영해 현광남 한양대학교 산업경영공학과 An Optimization Mode and Agorithm for Designing Muti-obective Wireess Network Dong Won Cho Su Yeon Cho Young Hae Lee Mitsuo Gen Dept. of Induria and Management Engineering, Hanyang University Abract Recenty due to increasing smart phones users, the wireess network is one of the important infraructures in a ubiquitous society. In the ubiquitous environment, the core of the wireess network service competition is to provide cuomers with reiabe internet access and fa data transmission. To meet these situations in the wireess network, cuomers shoud be aocated to access point with appropriate baance whie data transmission speed between cuomers need to be improved. In this paper, to sove the baanced aocation minimum spanning tree (BA-MST) probem, we propose muti-obective integer programming mode with quaity of service, and then genetic agorithm with fuzzy ogic to sove it.. In addition, the proposed mode and agorithm demonrated the effectiveness by using numerica experiment. The experiment resuts show that the proposed GA agorithm produces high-quaity soutions in reasonabe computation time. 퓨터와 각종 센서를 통해 원하는 정보를 얻는 유비쿼터스 사회로 진입하게 된 것이다. 유비 쿼터스 사회에서 무선 네트워크는 가장 중요한 인프라 기술이다. 또한, 기기들이 PC화 되면서 넷북, 노트북, 테블릿 PC등을 통한 무선 인터 넷 접속이 증가했고 스마트 폰 확산으로 데이 터 트래픽이 급증하면서 모바일 데이터 시장이 급속히 성장 했다. 이동통신 사업자는 급증하 는 트래픽에 대응하기 위해 우회망(e.g. Wi-Fi) 으로 트래픽을 분산하고 있다. <Figure 1> 는 무선 네트워크에서 고객과 access point(ap) 사 이의 접속 환경을 나타낸다. Keywords: Minimum Spanning Tree, Baanced Aocation, Quaity of Service, Muti-obective, Genetic Agorithm, Wireess Network 1. 서론 1.1 연구배경 및 연구목적 최근 스마트 폰 사용자가 급속하게 증가하면 서 위치기반 서비스, 증강현실 등이 큰 화제가 되고 있다. 주변 환경을 인식하는 네트워크 컴 Fig. 1 The ructure of wireess network 연락저자: TEL: +82-31-400-5262, E-mai: yhee@hanyang.ac.kr 536

무선 네트워크 서비스 경쟁의 핵심은 안정적 인 인터넷 접속과 빠른 데이터 전송 환경을 고 객에게 제공하는 것이다. 이를 위해 혼잡으로 인한 비효율을 피하는 것이 필수이며 설비와 고객 사이의 균형적인 할당은 안정적인 인터넷 접속과 빠른 데이터 전송을 보증하고 혼잡으로 인한 비효율을 최소화 할 수 있다. 1.2 문제설명 이 논문에서 우리는 용량 제약이 있는 균형 할당 문제(Capacitated Baanced Aocation Probem, CBAP)를 이용해 무선 네트워크 문제 를 공식화 하고 서비스 품질(Quaity of Service) 측정을 위해 용량 제약이 있는 minimum spanning tree(capacitated Minimum Spanning Tree, CMST)문제를 이용한다. 또한, 위 두 문 제를 이용해 무선네트워크에 총 통신 비용과 데이터 총 평균 지연을 평가하는 다목적 최적 화 모델을 공식화 하였다. 우리는 이런 무선 네트워크 문제를 균형할당 minimum spanning tree(baanced Aocation Minimum Spanning Tree, BA-MST) 문제로 정의한다. BA-MST 문제 는 일반 할당 문제 (Generaized assignment probem)와 minimum spanning tree 문제를 결 합 한 것이다. 우리는 BA-MST 문제를 풀기 위 해 Prim-Pred 기반 인코딩, Prim 기반 교차, 최저 비용 돌연변이, 이민 연산자 그리고 자동 조정 파라미터를 이용하는 유전자 알고리즘을 제안한다. 이 논문에서 정의하는 BA-MST 문제 는 Min[8] 그리고 Lin과 Gen[6]이 소개한 수리 모형을 기본으로 공식화 한다. Min[8]은 용량 제약을 가진 다수의 설비에 고객을 균형 할당 하는 문제를 풀기 위해 CBAP에 정수 계획법을 이용한 수리 모형을 제시하고 유전자 알고리즘 을 통해 수치 실험이 효율적임을 보여준다. Lin과 Gen[6]은 차세대 통신망에 대한 서비스 품질을 측정하기 위해 CMST 문제를 적용하고 새로운 인코딩 교차와 돌연변이 연산자를 이용 하는 유전자 알고리즘을 개발해 차세대 통신망 QoS 성능을 측정 한다. 이 논문의 구성은 본론 에서 수리모델을 정의하고 BA-MST 문제를 풀기 위한 유전자 알고리즘을 설명한 후 수치실험을 통한 결과를 제시한다. 마지막으로 결론과 향 후 연구를 제시한다. 2. 본론 2.1 기호정의 이 논문 수리모형에 사용하는 인덱스, 파라 미터, 결정변수는 다음과 같다. <Indices> i = 1, 2,..., n: 고객, k = 1, 2,..., m: AP = 1, 2,..., : 통신 서비스 유형 <Parameters> V ={1, 2,..., n, n+1, n+2,..., n+m}: 고객과 AP를 포함한 모든 노드 집합 e= E : 고객과 AP에 연결된 호 집합 v i =각 고객 수요 q =각 AP 용량 w W: 고객과 AP 사이의 통신비용 q Q: 통신 서비스 유형 의 요구 u U: 고객과 AP에 연결 된 호의 용량 w W: 통신 서비스 유형 의 가중치 d D: 고객과 AP에 연결 된 호의 지연(또는 네트워크 QoS에 대한 성능측정으로 정의), d = w Γ(q - u ) Γ (q - u ): 서비스 유형에 따라 고객과 AP 사 이의 지연을 정의하는 함수 <Decision variabes > x : 0-1 결정 변수(만일 고객이 AP에 할당되면 x =1, 그렇지 않으면 x =0) y : 고객과 AP에 연결 된 호의 서비스 요구 z : 0-1 결정변수(만일 y >0면 z =1, 그렇지 않 으면 z =0) 2.2 수리모형 우리는 n+m개 노드와 e개 호로 구성된 무방 향 그래프 G=(V, E, Q, U)로 네트워크를 모형화 한다. 수리모형의 목적은 총 통신 비용과 총 평균 지연을 최소화 하는 것이다. 제안하는 수 리모형은 다음과 같다. min max n vw i x (1) 1,..., m i1 L (, i ) E 1 min w min 0, ( y u ) (2) subect to n vx q, 1, 2,..., m i i1 m x 1, i 1, 2,..., n 1 nm nm (3) (4) z nm1 (5) i1 1 nm nm z S 1 for any set S of nodes (6) i1 1 537

q, i s nm nm y 0, ' {, }, y i V s t ki 1 k1 q, i t (, ) source node and sink node of q, x 0 or 1, i, y 0, i, z 0 or 1, i, (7) 위 수리모형의 목적식(1)은 AP와 고객 사이 에 가능한 균등하게 수요를 할당하면서 총 통 신 비용을 최소화하는 의미이다. 식(2)는 네트 워크 QoS에 대한 성능 측정에 하나로 정의 되 며 총 평균 지연을 최소화하는 의미이다. 식 (3)은 고객의 총 수요는 주어진 AP의 용량을 초과하지 못함을 의미한다. 식(4)는 모든 고객 은 오로지 하나의 AP에서 서비스를 제공 받는 것을 나타낸다. 식(5)는 호의 개수가 n+m-1 이라는 것을 나타내고 식(6)은 연결 된 호는 순환로를 만들지 않음을 의미한다. 식(7)은 소스 노드(source node) s와 싱크노드(sink node) t 를 제외한 각 노드 통신 요구에 대한 유량보존의 법 칙을 나타낸다. <Figure 2>는 12개 노드를 가지 는 무선 네트워크를 보여준다. 3.2.1 PrimPred 기반 유전자 표현 염색체를 이용한 네트워크 설계 문제에서 해 를 인코딩하는 방법은 유전자 알고리즘의 핵심 문제이다. 그래프에서 spanning tree를 인코딩 하는 것은 유전자 알고리즘 개발에서 매우 중 요하고 그것을 표현하는 것은 쉽지 않다. 기존 연구는 일반적으로 Dengiz[1]의 호 기반 인코 딩 방법(이진 인코딩, 인접행렬)을 이용해 염 색체를 네트워크 후보해로 표현한다. 우리는 무선 네트워크 설계 문제의 해를 찾기 위해 Lin과 Gen[5]이 소개한 PrimPred 기반 인코딩 방법을 적용한다. PrimPred 기반 인코딩은 이 전세대 기반 인코딩을 향상 시킨 방법으로 기 본적으로 초기해는 랜덤 spanning tree 알고리 즘에 따라 달라진다. PrimPred 기반 인코딩과 디코딩에 대한 자세한 절차는 Lin 과 Gen[5]의 연구에서 소개한다. 3. 유전자 알고리즘 3.1 유전자 알고리즘 정의 Gen[2]은 유전자 알고리즘(GA: Genetic Agorithms) 이란 생물학의 유전 메커니즘, 즉 생물 진화 (자연도태, 교차, 돌연변이)현상을 컴퓨터 시 뮬레이션으로 모방한 확률적 탐색, 최적화 학 습의 한가지 수법이라 정의한다. GA는 자연도 태와 유전 현상을 단순화한 발견적 기법(meta heuriics)의 하나이며, 개체라 불리는 염색 체(대상 문제의 후보해)의 집합이 외부환경(대 상문제의 평가함수)에 적응하듯이 다음에 나타 내는 규칙 (1), (2)에 근거하는 집단의 구성을 세대마다 생성시키는 것이다. (1)적합성이 높 은 개체일수록 생존 확률이 높다(자연도태). (2)이전세대의 개체를 이용한 유전 조작으로 다음 세대의 새로운 개체를 생성시킨다(유전현 상). GA를 조합한 최적화 문제의 한가지 해법 으로 규칙(1)을 확률적 탐색법, 또 규칙(2)을 경험적 탐색법이라 볼 수 있으며 GA는 두 개의 측면을 갖는 발견적 기법의 하나이다. 3.2 세부 알고리즘 (a) baanced aocation of network (b) a capacitated minimum spanning tree Fig.2 The wireess network with 12 nodes 538

3.2.2 유전 연산자 무선 네트워크에 동적인 환경을 고려하기 위 해서 해를 찾는 검색기능의 속도와 계산시간 단축이 필요하다. 우리는 해의 정확성을 향상 시키고 수렴 속도를 높이기 위해 Lin과 Gen[6] 의 유전 연산자를 적용한다. 교차 연산자(Crossover Operator) 교차 연산자는 주요 유전 연산자이다. 좋은 상속성을 위해 부모세대 호 대부분을 자식세대 spanning tree로 만들어야 한다. 우리는 그래 프 = (V, T 1 T 2 )에 Prim 알고리즘 인코딩을 이용한 Prim 기반 교차를 적용한다. 여기서 T 1, T 2 는 부모세대에서 선택된 호의 집합이다. 돌연변이 연산자(Mutation Operator) 돌연변이 연산자는 자발적으로 랜덤 변화를 만드는 연산자이다. 돌연변이 후에 자식세대 상속성 향상과 실행 가능 해를 얻기 위해 우리 는 최소 비용 돌연변이 연산자를 적용한다. 최 소 비용 돌연변이 연산자는 먼저 무작위로 선 택된 호를 제거한 후 분리된 구성요소에 최저 비용을 가지는 호를 다시 연결 한다. 그리고 동적으로 변화하는 서비스 요구에 대응하기 위 해 현재 세대를 개선한다. 이민 연산자(Immigration Operator) 이민 연산자는 각 세대에 이민 절차를 포함 하도록 수정한다. 먼저 세대를 생성하고 popsi ze p I 를 가지는 랜덤 염색체를 평가한 후 현재 세대에서 가장 나쁜 popsize p I 를 갖는 염색체 를 교체한다(여기서, popsize는 세대크기, p I 는 이민확률을 나타냄). 3.2.3 자동조정기법(Auto-tuning Scheme) 교차와 이민 확률 p C, p I 는 검색공간에 대한 활용(expoitation) 가중치로 결정된다. 메인 기법은 두 가지 퍼지 논리 제어(Fuzzy Logic Contro)이다. T[p M (p C p I )]의 활용과 탐색 (exporation)에 대한 자동 조정과 T[p C p I ]의 유전자 탐색 및 랜덤 탐색은 유전자 탐색 과정 에서 유전자 파라미터의 적응형 통제를 위해 독립적으로 구현한다. 자세한 기법은 Gen[2]에 저서에서 소개한다. 4. 수치실험 이 장에서 우리는 GA를 사용해 다목적 최적 화 모델을 해결하고 그 실험 결과를 분석한다. 제안된 PrimPred 기반 GA는 Gouveia[4]가 연구 한 논문의 데이터를 사용해 전통적인 Prim 알 고리즘과 비교한다. 무선 네트워크 구조는 3가 지 유형(유형1: 영상, 유형2: 음성, 유형3: 텍 스트)의 서비스를 가진 12개 노드로 구성된다. 각 호의 용량은 균일분포 runif(m, 100, 1000) 를 가진 확률 변수로 나타낸다. 노드 s에서 노 드 t까지 서로 다른 서비스 유형의 요구는 분 포 함수(유형1: 지수분포 rexp( Q, 0.03); 유 형2: 대수정규분포 0.1*rnorm( Q, 0.1, 0.1); 유형3: 정규분포 rnorm( Q, 0.01,0.001))를 가 진 확률 변수로 나타낸다(여기서, Q = 100). 3 가지 서비스 유형의 가중치(우선순위)는 각각 0.60, 0.30 그리고 0.10 이다. 초기 GA 파라미터는 다음과 같다: popsize(세대크기) = 20, pc(교차 확률) = 0.50, pm(돌연변이확률) = 0.50, maxgen(최대세대수) = 1000. <Figure 3>은 실 험 결과에 대한 파레토 해를 나타낸다. Tota average deay Tota communication co ( 10 5 ) Fig. 3 Comparisons resuts of Pareto soutions for PrimPred-based GA and Prim s Agorithm 539

5. 결론 이 논문은 무선 네트워크에서 QoS를 측정하 는 BA-MST 문제에 대한 다목적 최적화 모델을 공식화한다. BA-MST 문제를 풀기 위해 Prim-Pred 기 반 인코딩, Prim 기반 교차, 최저 비용 돌연변 이, 이민 연산자 그리고 자동 조정 파라미터를 이용하는 유전자 알고리즘을 제안한다. 그리고 수치실험을 통해 제안된 유전자 알고리즘이 효 율적임을 보여준다. 향후 연구는 문제 크기가 클 경우와 실제 데이터를 연구에 적용하는 것 이다. 참고문헌 [1] Dengiz, B., Atiparmak, F. and Smith, A. E., Efficient optimization of a-termina reiabe networks using an evoutionary approach, IEEE Trans. Reiabiity, Vo. 46 (1997), pp. 18 26. [2] Gen, M., Cheng, R., and Lin, L., Network modes and optimization: Mutiobective genetic agorithm approach, Springer, London, 2008. [3] Gong, D., Gen, M., Yamazaki, G., Xu, W., Hybrid evoutionary method for capacitated ocationaocation probem, Computers and Induria Engineering, Vo. 33, No. 3 4 (1997), pp. 577 580. [4] Gouveia, L., A comparison of directed formuations for the capacitated minima spanning tree probem, Teecommunication Syems, Vo. 1 (1993), pp. 51-76. [5] Lin, L., and Gen, M., Node-based genetic agorithm for communication spanning tree probem, IEICE Transactions on Communications, Vo. 89 (2006), pp. 1091-1098. [6] Lin, L., and Gen, M., An evoutionary agorithm for improvement of QoS of next generation network in dynamic environment, Inteigent Engineering syems through Artificia Neura Networks, Vo. 17 (2007), pp. 201-206. [7] Lin, L., and Gen, M., Auto-tuning rategy for evoutionary agorithms: Baancing between exporation and expoitation, Soft Computing, Vo. 13 (2007), pp. 157-168. [8] Min, H., Zhou, G., Gen, M., and Cao, Z., A genetic agorithm approach to the baanced aocation of cuomers to mutipe warehouses with varying capacities, Internationa Journa of Logiics: Research and Appications, Vo. 8 (2005), pp. 181-192. [9] Zhou, G., Min, H., Gen, M., The baanced aocation of cuomer to mutipe diribution centers in the suppy chain network: a genetic agorithm approach, Computers and Induria Engineering, Vo. 43, No. 1-2 (2002), pp. 251-261. [10] Zhou, G., Min, H., Gen, M., A genetic agorithm approach to the bi-criteria aocation of cuomers to warehouses, Internationa Journa of Production Economics, Vo. 86, No. 1 (2003), pp. 35-45. 540