Journal of the Korea Academia-Industrial cooperation Society Vol. 16, No. 8 pp. 5559-5564, 2015 http://dx.doi.org/10.5762/kais.2015.16.8.5559 ISSN 1975-4701 / eissn 2288-4688 이동성모델에따른다중경로소스라우팅프로토콜의성능평가 김수선 1*, 김문정 2 1 한양여자대학교컴퓨터정보과, 2 영동대학교스마트 IT 학과 Performance Evaluation of Multi-path Source Routing Protocol according to Mobility Model Su-Sun Kim 1*, Moon Jeong Kim 2 1 Department of Computer Information, Hanyang Women's University 2 Department of Smart IT, Youngdong University 요약이동애드- 혹네트워크환경을위해다양한라우팅프로토콜이제안되고있다. 이동애드- 혹네트워크는기존유선하부구조에도움없이동작하는일시적으로구성되는임시적인네트워크이다. 제안된프로토콜은이동애드- 혹네트워크내에서이동호스트들간에끊김없는통신서비스를제공한다. 특히, 우리의프로토콜은각이동호스트에서다중경로를유지함으로써더빠른경로재설정이가능하도록해주고또한이프로토콜은신뢰할수있는통신환경을제공한다. 본논문에서는 RWP 모델과 LW 모델과의성능을비교한다. 본논문은단일경로와노드의중복을허용하는다중경로를사용하는경우의평균이동속도에따른전달률의변화를이동성모델에따라, 그리고노드의수에따라보인다. Abstract A variety of routing protocols targeted specifically at mobile ad-hoc network environments have been developed. Mobile ad-hoc network is a self-organizing temporary network, operating without the aid of any established wired infrastructure. The proposed protocol supports seamless communication services between the mobile hosts within a mobile ad-hoc network environments. In particular, our protocol makes faster route re-establishment possible by maintaining multiple paths in each mobile host, and also, the protocol provides reliable communication environments. We compare the performance of RWP model with that of LW model. This paper shows delivery ratio with single path and non-disjoint multiple path according to mobility model and node numbers. Keywords : Mobile Ad-Hoc Network, Multi-path Source Routing Protocol, Levy Walk Mobility Model, Random Way Point Mobility Model 1. 서론애드-혹네트워크 (MANET : Mobile Ad-hoc NETworks) 는기존의유선하부구조없이이동호스트들만으로구성되는일시적인네트워크를말한다. 이동애드- 혹네트워크에서는기존의유선하부구조를이용할수없기때문에, 이동호스트가스스로라우터의역할도수행해야한다는특성을갖는다 [1,2,8]. 본논문에서제안하는라우팅프로토콜은요구기반라우팅프로토콜로, 간단한알고리즘을이용하여링크또는중간호스트의중복을허용하는다중경로를설정및유지하는기법이다. 다중경로를유지함으로써경로가단절된경우빠른경로재설정을제공하여출발지와목적지간데이터패킷전송지연을줄이는기법을제안한다. 특히본논문에서는제안하는기법의성능평가를위해이동애드-혹네트워크환경에서가장많이사용하 본논문은한양여자대학교 2012년 2학기교내연구비로수행되었음 * Corresponding Author : Su-Sun Kim(Hanyang Women's University) Tel: +82-10-2290-2209 email: sskim@hywoman.ac.kr Received July 8, 2015 Accepted August 6, 2015 Revised July 20, 2015 Published August 31, 2015 5559
한국산학기술학회논문지제 16 권제 8 호, 2015 는이동성모델인 RWP 모델과최근가장인간의이동패턴과유사하다고인정되는 LW 모델을사용하였다. 본논문의 2절에서는이동애드-혹네트워크환경을위한라우팅프로토콜과이동성모델에대해소개하고, 3절에서는제안프로토콜의개요와기본동작을소개한다. 4절에서는제안기법에대한성능평가를보이며, 5 절에서결론을맺는다. 2. 라우팅프로토콜과이동성모델이동애드-혹네트워크환경을위한라우팅프로토콜과이동노드들의이동성모델에대해간단히소개한다. 2.1 라우팅프로토콜이동애드-혹네트워크를위한라우팅프로토콜을 Fig. 1에서와같이구분할수있다 [3,9]. [4,10]. DSR 프로토콜은라우팅정보를주기적으로방송하지않으므로네트워크의대역폭낭비를줄이며, 배터리전력이절약된다. 사용하지않는경로는계산하지않으며, 호스트간전송이양방향이어야할필요가없다. 또한, 네트워크변화에적응성을갖는다는장점을갖는다. 2.1.2 MDSR 프로토콜 MDSR(Multipath DSR) 프로토콜은 DSR 프로토콜의다중경로확장기법이다 [5,11]. 다중경로를설정하는경우목적지호스트는다중경로에대해응답한다. 소스호스트는처음도착한경로를주경로 (primary route) 로하여데이터를전송한다. 그외의경로는예비경로 (alternate route) 로유지하여주경로가단절되는경우에사용하게되며, 이는 Fig. 2에서보인다. alternate route Ad-Hoc Routing Protocol primary route Table Driven Source-Initiated On-Demand Driven S alternate route D DSDV WRP AODV DSR LMR ABR DSDV TORA SSR Fig. 1. Classification of Ad-hoc Routing 그림1에서보이는바와같이, 이동애드-혹네트워크를위한라우팅프로토콜은테이블기반라우팅프로토콜과요구기반라우팅프로토콜로구분된다. 본논문에서는이동애드-혹네트워크의특성상가장많이이용되는요구기반라우팅프로토콜중 DSR 프로토콜과다중경로로확장된 MDSR 프로토콜에대해간단히소개한다. 2.1.1 DSR 프로토콜 DSR(Dynamic Source Routing) 프로토콜은연결지향패킷포워딩기법을사용하며, 라우팅정보를주기적으로전달하지않는다. DSR 프로토콜의동작방법은크게경로설정단계와경로유지단계로구분될수있다 Fig. 2. Effect of Disjoint Route Fig. 2에서보이는바와같이, 목적지는전혀중복이없는 (disjoint) 경로를발견하는작업을수행해야한다. MDSR 프로토콜에서는선택되는다중경로의수를제한하고있지않으므로, 센서네트워크환경등노드들이밀집된환경에서는매우많은다중경로를유지하게되는단점을갖는다. 특히, 전혀중복이없는경로를선택하기위해중간호스트들은경로요청패킷의중복성을확인하지않기때문에매우많은네트워크오버헤드를초래하게된다. 본논문에서제안하는방법은 DSR에중간노드의중복을허용하는다중경로를유지하는기법으로, 다중경로수를제한함으로써네트워크의오버헤드를줄이는효과를가진다. 2.2 이동성모델현재, 이동애드- 혹네트워크에서인간이동성을시뮬레이션하기위해다양한모델에대한연구가진행되고 5560
이동성모델에따른다중경로소스라우팅프로토콜의성능평가 있다. 본논문에서는이동성모델중에서가장많이사용되는 RWP 모델과 LW 모델에대해소개한다 [6]. 2.2.1 RWP 모델 RWP(Random Way Point) 모델은기존이동애드-혹네트워크를위한라우팅프로토콜의성능분석에가장많이사용되는이동성모델이다. RWP 모델에서, 노드는특정장소에서얼마간의정지시간뒤에분포지역내임의의다음장소를선택한후임의로선택된속도에의해다음장소로이동한다. 2.2.2 LW 모델 LW(Levy Walk) 모델은최근에실제인간의이동패턴과가장유사하다고발표된모델이다. 자신의활동영역내에서반복적인생활을하는인간이동성패턴과유사한모델이다. LW 모델에서, 노드는일정한분포지역내에서임의로선택된초기위치에서분포지역에맞게선택된 flight length와 direction(θ) 을계산하여다음위치로이동한다. RWP 모델과 LW 모델의추적샘플을 Fig. 3에서보인다. Fig. 3. Sample Trajectories Fig. 3에서보이는바와같이, LW 모델에서는이동노드의확산패턴을다양하게생성해낼수있다. 3. 다중경로소스라우팅프로토콜본논문에서제안하는라우팅프로토콜의기본동작은경로설정단계와경로유지단계로구성되며, 경로설정단계는경로요청단계와경로응답단계로구성된다. 3.1 경로설정단계이동애드- 혹네트워크내의이동호스트가다른이동 호스트로데이터패킷을전송하고자하는경우, 우선경로요청단계를거치게된다. 이동호스트 S가이동호스트 D로데이터패킷을전송하기위해경로를요청하는과정을 Fig. 4에서보인다. S INs D broadcast a RQP re-broadcast a RQP unicast a RRP forward a RRP unicast data packets forward data packets Fig. 4. Route Discovery Process 이동애드-혹네트워크내에서데이터패킷을전송하고자하는출발지호스트 (S) 는경로요청단계에진입하여, 먼저자신의 RC(Routing Cache) 를확인한다. 만일자신의 RC 내에목적지호스트 (D) 로의경로가존재한다면해당경로를헤더에추가하여데이터패킷을 D로전송하게된다. 그렇지않다면, Fig. 4에서보이는바와같이, 자신의주소와제한된방송주소 (255.255.255.255) 를 IP 헤더에포함하고목적지호스트의주소를 Target Address에포함하는 RQP(Route request Packet, 경로요청패킷 ) 를생성하여이동네트워크를통해방송 (broadcast) 하게된다. 이를수신한중간호스트는자신이목적지호스트가아닌경우, 해당 RQP 헤더의끝에자신의주소를추가하여다시방송하게된다. 이때중간호스트들은수신 RQP 정보를일정시간동안유지하여중복처리를방지하게된다. 만일 RQP를수신한호스트가 D인경우라면경로응답단계에진입하게된다. 목적지호스트는동일한출발지호스트로부터여러개의 RQP를수신할수있으며, 이중도착한순서에따라해당프로토콜내에서제한하는수만큼의 RRP(Route Reply Packet, 경로응답패킷 ) 를생성하여전송할수있다. 3.2 경로유지단계이동애드-혹네트워크내에서능동경로및수동경로에포함되는각호스트들은경로상의인접호스트들과의연결상태를항시모니터링하게된다. 만일자신의 RC에유지하고있는경로중에자신과인접한호스트와의연결이단절된경우, 이를발견한호스트는자신의 5561
한국산학기술학회논문지제 16 권제 8 호, 2015 RC 정보를참조하여단절된방향과반대방향으로연결이단절되었음을알리는패킷 (REP) 을전달하고자신의 RC 정보에서해당경로를제거하게된다. 이와같은작업으로인해, 출발지호스트가가진 RC는항상최신정보를유지하게된다. 또한, 데이터패킷전송도중에연결이단절되었음이발견되는경우, 이를발견한호스트는데이터패킷의출발지호스트에게 REP를전달하게되며, 역시자신의 RC에서해당정보를제거하게된다. REP를수신한출발지호스트는자신의 RC를참조하여해당목적지로의다른수동경로가있는경우이를사용하여데이터패킷을재전송하게된다. 그렇지않은경우다시새로운 RQP를생성하여방송함으로써경로요청단계에다시진입하게된다. 4.1 시뮬레이션환경 4. 성능평가 본논문에서는 C 언어로구현된시뮬레이션라이브러리인 Simlib을사용하였다 [7]. 본논문에서제안하는프로토콜은이동애드-혹네트워크내에서이동호스트들의통신을위해 dynamic source routing 기법을사용하면서노드중복을허용하는다중응답을받고, 하나이상의경로를유지할수있는기법이다. 시뮬레이션을위한환경은 Table 1에서보이는바와같다. Table 1. Simulation Environment factor value Network size 1000 m * 1000 m Transmission range 250 m Data Sending Rate 250 = 4 packets/s Simulation time 1180000 ms Data Sending Time 180000 ms(3 min) Delay per one hop 30 ms Number of node 40, 80 nodes pause time 0 node speed 4, 8, 12, 16, 20 m/s bytes CBR(Constant Bit Rate) 로가정하였으며, 초당 4 개의패킷을전송하고, 홉간의전송지연시간은 30ms 라가정하였다. 성능평가분석을위한요소는다음과같다. 총수신데이터수 output = 시뮬레이션시간 총수신데이터수 delivery ratio = 총송신데이터수 총제어패킷수 overhead = 총수신데이터수 총송수신간지연시간 end-to-end delay = 총수신데이터수 본논문에서는 DSR 프로토콜과같이단일경로를사용하는경우와중복을허용하는다중경로를사용하는프로토콜의경우를 RWP 모델과 LW 모델을사용하여성능을평가하여비교하고자한다. 이를위해본논문에서는성능평가의요소중가장중요한요소인전달률 (delivery ratio) 에대한결과를비교분석하였다. 다른요소들에대해서는향후연구를진행하고자한다. 4.2 시뮬레이션결과 시뮬레이션을위한네트워크크기는 1000m * 1000m, 전송가능범위는 250m로가정하였다. 또한, 하나의출발지호스트가하나의목적지호스트로데이터를보내는것으로가정하였다. 각시뮬레이션은총 50회시행하여평균을계산하였다. 네트워크범위내에 40개의노드가있으며 DSR 프로토콜과같이단일경로를사용하는경우, 평균이동속도증가에따른전달률의변화를 Fig. 5에서보인다. 제안프로토콜의성능평가를위하여총시뮬레이션시간은 1180초로하고처음 1000초후에 180초동안데이터패킷을전송하였다. 본시뮬레이션을위해이동호스트들의이동모델은 RWP와 LW 모델을적용하였으며, pause time은 0 으로하였다. 데이터패킷은 512 Fig. 5. Delivery Ratio with Single Path 5562
이동성모델에따른다중경로소스라우팅프로토콜의성능평가 Fig. 5에서보이는바와같이, 단일경로를사용하는경우는노드들의평균이동속도가높아질수록 RWP 모델에비해 LW 모델의전달률이더급속히낮아짐을알수있다. 단일경로와노드중복을허용하는다중경로를사용하는경우, 평균이동속도에따른전달률의변화를 Fig. 6 에서보인다. (%) delivery ratio(node=40) 1 0.99 0.98 0.97 RWP path=1 0.96 RWP path=3 0.95 LW path=1 0.94 LW path=3 0.93 0.92 4 8 12 16 20 (m/s) Fig. 6. Delivery Ratio (40 nodes) (%) delivery ratio(node=10) 1 0.995 0.99 0.985 RWP path=1 0.98 RWP path=3 0.975 LW path=1 0.97 LW path=3 0.965 0.96 0.955 (m/s) 4 8 12 16 20 Fig. 8. Delivery Ratio (10 nodes) Fig. 8에서와같이, 네트워크내에노드의수가적은경우에는평균이동속도가높아질수록전달률이낮아지지만, 단일경로에비해다중경로를유지하는경우가전달률이높으며, RWP 모델에비해 LW 모델이다양한이동성향을만들어시뮬레이션결과가역시다양해지는것을알수있었다. Fig. 6에서보이는바와같이, LW 모델을이용하며다중경로를사용하는경우이동속도에따른변화가크지않음을알수있다. 네트워크내에 80개의노드가존재할때, 단일경로와노드중복을허용하는다중경로를사용하는경우, 평균이동속도에따른전달률의변화를 Fig. 7에서보인다. (%) delivery ratio(node=80) 1 0.99 0.98 RWP path=1 RWP path=3 0.97 LW path=1 0.96 LW path=3 0.95 0.94 (m/s) 4 8 12 16 20 Fig. 7. Delivery Ratio (80 nodes) Fig. 6과 Fig. 7에서, RWP 모델의경우는평균이동속도가높아질수록전달률이일정하게낮아지는반면, LW 모델의경우에는비교적전달률이일정함을보인다. 네트워크내에 10개의노드가존재할때의결과를 Fig. 8에서보인다. 5. 결론본논문에서는이동애드-혹네트워크를위해노드의중복을허용하는다중경로소스라우팅프로토콜을제안하며이동성모델중이동애드-혹네트워크환경에서가장많이사용하는 RWP 모델과최근인간이동패턴과가장유사하다고발표된 LW 모델을이용하여노드들의이동속도에따른전달률을비교하였다. 본논문에서시뮬레이션을통해, DSR 프로토콜과같이단일경로를유지하는경우보다다중경로를유지하는경우에성능이좋음을알수있었다. MDSR 프로토콜과같이노드의중복성을허용하지않는다중경로를유지하는경우보다노드의중복을허용하는다중경로를유지하는경우에보다좋은성능을보인다는것은이미연구된바있다. 본논문에서는 RWP 모델을적용한경우시뮬레이션결과가일관성을갖는반면, LW 모델을적용한경우는비교적일관성이없음을알수있었는데이는 LW 모델이보다다양한이동성향을만들기때문인듯하다. 본논문에서는노드의중복을허용하는다중경로라우팅프로토콜의성능을 RWP 모델과 LW 모델을이용하여비교하였다. 5563
한국산학기술학회논문지제 16 권제 8 호, 2015 References [1] G. H. Forman and J. Zahorjan, "The Challenges of Mobile Computing," IEEE Computer, Apr. 1994. DOI: http://dx.doi.org/10.1109/2.274999 [2] K. Weniger and M. Zitterbart, "Mobile Ad Hoc Networks - Current Approaches and Future Directions," IEEE, Network, Vol. 18, No. 4, pp. 6-11, Jul. 2004. DOI: http://dx.doi.org/10.1109/mnet.2004.1316754 [3] M. N. Mohamed, A. A. Ayoob, G. M. Abdulsahib, O. I. Khalaf, and H. A S. Ahmed, "A Comparative Performance Analysis of AODV and DSR Routing Protocol for Mobile Ad-hoc Network," International Journal of Digital Content Technology and its Applications(JDCTA), Vol. 9, No. 1, Feb. 2015. [4] D. Johnson, Y. Hu, and D. Maltz, " The Dynamic Source routing Protocol(DSR) for Mobile Ad Hoc Networks for IPv4," Internet Draft, Mar. 2001. [5] A. Nasipuri and S. R. Das, "On-Demand Multipath Routing for Mobile Ad Hoc Networks," International Conference on Computer Communications and Networks, Oct. 1999. DOI: http://dx.doi.org/10.1109/icccn.1999.805497 [6] S. I. Hong and S. J. Kim, "Human Mobility Model for Wireless Ad-Hoc Network Simulation," Information and Communications Magazine, vol. 30, No. 7, pp. 63-73, Jun. 2013. [7] M. Law, W. D. Kelton, Simulation Modeling and Analysis, 3rd ed. McGraw-Hill, 2000. [8] Hunju Lim, Sookyoung Joung, Sungwha Lee, Inkap Park, MAC Aware Multi-Channel Routing Protocol for Multi-Interface Ad-Hoc Wireless Networks, The Journal of The Institute of Internet, Broadcasting and Communication, Vol. 13, No. 5, pp. 249-258, October 2013. DOI: http://dx.doi.org/10.7236/jiibc.2013.13.5.249 [9] Sun-Jin Oh, Design and Evaluation of Fuzzy-Logic based Quorum System considering the Gravity of Locality of Mobile in MANETs, The Journal of The Institute of Webcasting, Internet Television and Telecommunication, Vol. 8, No. 2, pp. 9-14, 2008. [10] Xiao-Lei Zhang, Ye Wang, Jang-Geun Ki and Kyu-Tae Lee, Analysis of MANET Protocols Using OPNET, The Journal of The Institute of Webcasting, Internet Television and Telecommunication Vol. 9, No. 4, pp. 87-97, 2009. [11] Chan-Sook, Sung-Hyun Cho, Multipath Overlay Routing for Reliability, The Journal of The Institute of Webcasting Internet Television and Telecommunication, Vol. 7, No. 6, pp. 17-24, 2007. 김수선 (Su-Sun Kim) [ 정회원 ] < 관심분야 > 이동컴퓨팅, 모바일시스템, 멀티미디어 1984 년 2 월 : 서울과학기술대학교컴퓨터공학과 ( 공학사 ) 1986 년 8 월 : 한양대학교산업대학원컴퓨터공학과 ( 공학석사 ) 1997 년 2 월 : 아주대학교대학원컴퓨터공학과 ( 공학박사 ) 1991 년 3 월 ~ 현재 : 한양여자대학교컴퓨터정보과교수 김문정 (Moon Jeong Kim) [ 정회원 ] 1998 년 2 월 : 성균관대학교정보공학과 ( 공학사 ) 2000 년 2 월 : 성균관대학교전기전자및컴퓨터공학과 ( 공학석사 ) 2005 년 2 월 : 성균관대학교전기전자및컴퓨터공학과 ( 공학박사 ) 2006 년 7 월 ~ 2007 년 11 월 : 고려대학교정보보호대학원연구교수 2007 년 12 월 ~ 2009 년 2 월 : 성균관대학교정보통신공학부연구교수 2009 년 3 월 현재 : 영동대학교스마트 IT 학과교수 < 관심분야 > 이동컴퓨팅, 무선애드 - 혹네트워크, 유비쿼터스컴퓨팅 5564