Journal of the Korea Academia-Industrial cooperation Society Vol. 16, No. 1 pp. 703-712, 2015 http://dx.doi.org/10.5762/kais.2015.16.1.703 ISSN 1975-4701 / eissn 2288-4688 차량이동방향과밀집도를고려한 UIGRP (Urban Intersection based Geographic Routing Protocol) 설계 이병관 1, 정은희 2* 1 가톨릭관동대학교컴퓨터학과, 2 강원대학교지역경제학과 Design of UIGRP(Urban Intersection based Geographic Routing Protocol) considering the moving direction and density of vehicles Byung-Kwan Lee 1, Eun-Hee Jeong 2* 1 Department of Computer, Cathoric Kwandong University, 2 Department of Regional Economics, Kangwon National University 요약본논문에서는도심교차로에서차량들의빈번한방향전환으로인해발생하는네트워크단절과패킷전송지연문제를해결할수있는 UIGRP 을제안한다. UIGRP는첫째, 차량의이동방향과목적지의위치를이용해 Direction 을산출하고, 둘째, RSU가도심교차로의밀집도를측정하도록설계한다. 그리고셋째, 목적지노드가위치한방향으로이동하는차량이면서밀집도가가장높은곳에위치하는노드를중간노드로선정하여데이터전송경로를선정하는 TGF 알고리즘을설계한다. TGF 알고리즘은이동방향과밀집도를이용해기존의 Greedy Forwarding 알고리즘이갖는 local maximum 문제들의발생을최소화시키거나제거한다. 시뮬레이션결과, UIGRP 는기존의 GPSR 과 GPUR보다 local maximum 문제발생횟수를평균 3회, 1회감소하고, 패킷전송시간도평균 6.12(ms), 2.04(ms) 단축시켰으며, 패킷전송성공률은 15%, 3% 증가하였다 Abstract This paper proposes the UIGRP, which can tackle the problem of the network disconnection and packet transmission delay caused by turning vehicles frequently in an urban intersection. The UIGRP was designed as follows. First, it calculates the direction of vehicles using the moving direction of vehicles and the location of a destination. Second, it makes the RSU measure the density of an urban intersection. Third, the TGF Algorithm in the UIGRP decides the data transmission paths by setting as an intermediate node, not only the vehicle that is moving in the direction where a destination node is located, but also the node that has the highest density. The TGF algorithm using a moving direction and density minimizes or removes the occurrence of local maximum problems that the existing Greedy Forwarding algorithm has. Therefore, the simulation result shows that UIGRP decreases the occurrence of local maximum problems by 3 and 1 times, and the packet transmission time by 6.12 and 2.04(ms), and increases the success rate of packet transmission by 15 and 3%, compared to the existing GPSR and GPUR. Key Words : Density, Direction, GPSR, Transformed Greedy Forwarding Algorithm, UIGRP 1. 서론최근자동차통신및이를활용한지능형자동차를위한 ITS(Intelligent Transportation System) 에관한연구가활발히진행되고있다. 특히, VANET(Vehicular Ad-hoc Network) 는 ITS 구현을위한핵심네트워크구조로써차량간무선통신을기반으로하는멀티홉방식의네트워크이다. VANET의목표는차량간또는인프라간의무선통신으로정보교환을하여교통흐름을파악하고, 도로에 * Corresponding Author : Eun-Hee Jeong(Kangwon National Univ.) Tel: +82-33-570-6646 email: jeongeh@kangwon.ac.kr Received August 8, 2014 Revised (1st September 26, 2014, 2nd September 30, 2014) Accepted January 8, 2015 703
한국산학기술학회논문지제 16 권제 1 호, 2015 서일어나는긴급상황에대처함으로써안전하고효율적인운행을가능하게하는것이다. 하지만, VANET은빈번한차량이동으로인한잦은토폴로지변동으로차량간메시지전송경로가빈번하게단절됨으로써데이터패킷도착율의저하로신뢰성문제등을갖고있다. 본논문에서는이러한데이터패킷전송경로의단절과데이터패킷의전송지연을방지하기위해차량의이동방향과교차로밀집도를이용하는 UIGRP(Urban Intersection based Geographic Routing Protocol) 을제안한다. UIGRP은목적지와동일한이동방향을갖는차량들을이웃노드로선정하고, 이이웃노드들과도로밀집도를이용하여데이터패킷전송경로를선정하는 TGF(Transformed Greedy Forwarding) 알고리즘을설계한다. 그리고 UIGRP는 TGF 알고리즘을이용하여목적지에신속하게데이터패킷을전달함으로써데이터패킷손실율을낮추고, VANET의신뢰성을향상시키고자한다. 본논문의구성은다음과같다. 2장에서관련연구인 Geographical Routing Protocol (GRP), Greedy 알고리즘을살펴보고, 3장에서본논문에서제안하는 UIGRP와 TGF을설계한다. 그리고 4장에서는 3장에서설계한 UIGRP를분석하고, 5장에서결론을맺는다. 드중에목적지가장가까이에위치한노드를선택하여데이터를전달하기때문에근원지노드와목적지노드사이에가장짧은경로를제공하는프로토콜이다. GPSR 에서각노드는주기적으로이웃노드정보를유지하기위해 Hello packet으로이웃노드의정보를수집하여이웃노드테이블을생성하고, 이테이블을이용하여데이터를전달할노드를선택한다. 이때, GPSR은 greedy mode과 perimeter mode로데이터를목적지에전달한다. Greedy mode는근원지노드가목적지노드에데이터를전달하기위해중간노드를선택하고, 데이터를전달하는동작을말한다. 그리고 Perimeter mode는근원지노드가선택한중간노드의이웃노드가존재하지않을경우새로운중간노드를선택하여데이터를전달하는동작을말한다 [6,7,8,9]. 2. 관련연구 2.1 Geographic Routing Protocol 무선애드혹네트워크에서는전통적인라우팅프로토콜로 On-Demand Routing Protocol이사용되어왔다. 이방법은 IP 기반라우팅프로토콜로라우팅경로결정을위해네트워크전체에경로요청메시지를플로딩한다. 따라서불필요한위치까지경로요청메시지가전달되는단점을가지게되며, 이러한단점을보완하기위해노드의위치정보를활용하는위치정보기반라우팅프로토콜이제안되었다 [1, 2]. 기존위치정보기반라우팅프로토콜은 Location-Aided Routing (LAR)[3] 와 Greedy Perimeter Stateless Routing (GPSR)[4,5] 이대표적이다 [6]. GPSR은위치정보를이용하여전송범위에있는노 [Fig. 1] GPSR protocol 그림 1은 GPSR의 Greedy mode와 Perimeter mode를설명한것이다. 근원지노드 A가목적지 D 노드로데이터를전송하고자할때, GPSR은 A 노드의이웃노드들중목적지노드 D와가장가까운노드인 B를중간노드로선정하고, 노드 B에게데이터를전송한다. 이때, 중간노드 B는이웃노드들중목적지노드 D와가장가까운중간노드를발견할수없는 local maximum 문제에직면하게되고, GPSR는 local maximum 문제를해결하기위해 Perimeter mode 로전환하여이목적지노드와반대되는방향으로전송을시도한다. 그리고목적지노드와가장근접한노드 H를중간노드를선정한후에, Greedy mode 로전환하여목적지노드 D에게데이터를전달하는중간노드를선정한후에데이터를전달한다.[6,10]. GPSR은전체네트워크의토폴로지정보가아닌전송 704
차량이동방향과밀집도를고려한 UIGRP(Urban Intersection based Geographic Routing Protocol) 설계 범위내에있는노드의정보만을구성하기때문에경로탐색시네트워크전체에라우팅메시지를전송하지않는것과 shortest path를설정한다는장점을갖는다. 하지만 GPSR은위치정보를저장하기위한데이터베이스관리로인한오버헤드가발생할수있고, 라우팅이이루어지지않는사각지대인 void zone이있을경우경로를탐색하지못하는단점이있다 [7,10,11,12]. 2.2 Greedy Forwarding 알고리즘무선 Ad Hoc 네트워크에서는네트워크수명을최대화하기위해서각노드들의제한된에너지를효율적으로사용하여야한다. GPSR(Greedy Perimeter Stateless Routing)[4,5] 프로토콜에서사용하는. Greedy Forwarding 은그림 2[4] 에서와같이항상목적지에가장가까운노드만을 Next-Hop 으로설정하여네트워크통신을행하므로인해, 특정노드의에너지소모가급격하게증가하는경향을가지고있다. 또한, MANET 을위한위치정보기반라우팅프로토콜들이제안되었으며이들프로토콜들은특정노드의에너지소모가집중된다는단점을가지고있다 RUS는교통센터로부터이웃 RSU의밀집도정보를제공받는다고가정한다. 3.1 Overview 본논문에서제안하는 UIGRP는그림 3에서전체적인흐름을설명하고있듯이, 차량에부착된 GPS로차량의위치를알수있으며, 이위치정보를이용하는지리기반프로토콜이다. 또한 UIGRP는차량이위치하고있는교차로의밀집도정보를 RSU로부터제공받는다. [Fig. 2] Greedy Forwarding 3. UIGRP 설계본논문에서는차량의위치, 이동방향, 이웃노드의수, 그리고교차로밀집도를이용하여데이터전송경로를설정함으로써 GPSR의 local maximum 문제의발생가능성을줄일수있는 UIGRP 를제안한다. 본논문에서제안하는 UIGRP 설계에서는네트워크내의모든노드들은첫째, GPS를장착하고있어위치정보를알수있으며, 둘째, 1홉단위내의이웃노드들의정보를 Hello message를통해수집할수있고, 셋째, 근원지노드는목적지노드의위치를알고있고, 넷째, 도로변에설치된 [Fig. 3] UIGRP Flowchart UIGRP는 Hello message를사용하여이웃노드의위치와이웃노드리스트를수집하여라우팅테이블을갱신한다. 그리고 UIGRP는라우팅테이블에저장되어있는이웃노드정보중에서목적지와같은방향으로이동하고, 이웃노드의수가 1이상인이웃노드들로만후보리스트를생성한다. UIGRP는이후보리스트중에서이웃노드가가장많고, 목적지노드에가장근접한곳에위치하고있는노드를중간노드로선정함으로써 local maximum 문제에직면할가능성을줄인다. 또한, 차량의이동으로인해중간노드의위치가변경되어 local maximum 문제에직면하였을때, UIGRP는교차로밀집도, 이동방향그리고이웃노드의수를이용하여 local maximum 문제를신속하게해결한다. 705
한국산학기술학회논문지제 16 권제 1 호, 2015 그결과, UIGRP 는짧은경로를이용하여신속하게데이터를목적지에전송함으로써데이터패킷전송지연율과데이터패킷손실율을줄여 VANET의신뢰성을향상시킬수있다. 3.2 UIGRP 라우팅설계 3.2.1 Hello Message UIGRP의모든노드들은 GPS가장착되어있기때문에자신의위치를파악할수있고, 모든노드들이노드의위치정보가포함되어있는 Hello Message를 1 홉단위의이웃노드들에게전달한다. 이때, 전달하는 Hello message의구조는표 1과같다. [Table 1] the structure of Hello message Field name Contents Node ID Identifier of Node Previous Position Previous position of Node Current Position Current position of Node Nlist Neighboring List Timestamp Transmission Time 3.2.2 라우팅테이블 UIGRP에서는 이웃 노드로부터 전달받은 Hello message의정보를라우팅테이블에저장하고, 이정보를 이용하여데이터패킷을전송할이웃노드를선정한다. 표 2는 UIGRP의라우팅테이블구조를설명한것이다. [Table 2] UIGRP Routing Table Field name Contents Node ID Identifier of neighboring node position Position of node direction Moving direction distance distance with destination node Nlist neighboring node list candidate candidate of intermediate node (1) Distance 계산 UIGRP의노드가라우팅테이블을갱신하는과정은 다음과같다. 그림 4는도심교차로에배치된노드들의 위치와방향, 그리고목적지노드의위치를예를들어설 명한것이다. [Fig. 4] located nodes in the urban intersection [1 단계 ] 노드 2 는이웃노드 1, 3, 4, 5 로부터아래 의 Hello message 를전달받는다. Node1 = {1, (30.9627, 30.1009), (30.9627, 30.1010), {2,4}, 10:00:05} Node3 = {3, (30.9624,30.1008) (30.9624,30.1009), {2,4,5,6,7}, 10:00:07} Node4 = {4, (30.9625,30.1012), (30.9625,30.1011), {1,2,7,8,9}, 10:00:06} Node5 = {5, (30.9625,30.1009), (30.9625,30.1008), {2,4}, 10:00:05} [2 단계 ] 노드 2는전달받은 Hello message로라우팅 테이블을갱신한다. [3 단계 ] 노드 2 는목적지의위치와이웃노드들의위 치정보를이용하여식 (1) 을이용하여거리를계산한다 [13]. Distance = 69.1 (180/π) arccos(sin(lat1) sing(lat2)+cos(lat2) cos(lat2) (1) cos(long2-long1)) 여기서, LAT1 와 LONG1 노드 2 의이웃노드의 ( 위도, 경 도 ) 이고, LAT2 와 LONG2 는목적지노드의 ( 위도, 경도 ) 를말한다. 예를들어, 그림 4 의목적지노드 D 가 (30.9623, 30.1006) 이고, 노드 2 는이웃노드들인 1,3,4,5 의위치 정보를이용하여 distance 를식 (1) 을이용하여계산한 후에라우팅테이블에저장한다. 706
차량이동방향과밀집도를고려한 UIGRP(Urban Intersection based Geographic Routing Protocol) 설계 [Table 3] the decision condition of moving direction Node ID Position Direction Distance(km) Nlist Candidate 1 3 4 5 30.9627, 30.1010 30.9624, 30.1009 30.9625, 30.1011 30.9625, 30.1008 2 2.185611 2,4-2 1.638909 2,4,5,6,7-1 2.731542 1,2,7,8,9-1 1.092807 2,4 - (2) Direction 결정 UIGRP에서는근원지노드가목적지노드에데이터패킷을전달하기위해이웃노드들의이동방향을결정하여라우팅테이블에저장한다. 그리고 UIGRP에서는이이동방향을이용하여데이터패킷을전달하는경로선정한다. UIGRP는식 (2) 와표 4를이용하여이웃노드의위치정보와목적지노드의위치정보를이용하여 Direction 을결정한다. position1(x,y)= 이전위치 (x,y)- 목적지위치 (x,y) position2(x,y)= 현재위치 (x,y)- 목적지위치 (x,y) MD(x,y)=position1(x,y)-position(x,y) [Table 4] the decision condition of moving direction Decision condition Direction MD=(-,-) 0 MD=(0,-), (-,0) 1 MD=(0,+), (+,0) 2 MD=(+,+) 3 즉, 노드 2는이웃노드들의이전위치 (previous position), 현재위치 (current position), 그리고목적지노드위치를식 (2) 에대입시켜 position1, position2를계산한다. 그리고노드 2는 Position2 에서 position1을뺀결과값의부등호를 MD( Moving Direction) 에저장한다. 그리고노드 2는표 4의조건에따라 direction을결정하고, 이 direction을라우팅테이블에저장한다. (2) [Fig. 5] the calculation procedure of Direction 3.2.3 Density 측정본논문에서제안하는 UIGRP는도로에설치된 RSU 와 RSU를관리하는 Traffic center의기존의인프라구조를사용한다. 그리고 UIGRP가 local maximum 문제에직면하였을때, UIGRP는 RSU가측정한밀집도를이용하여새로운중간노드를설정함으로써 local maximum 문제를해결하도록설계한다. 그림 6과같이 RSU는도로의 density 를측정한후에 Traffic center에전달하고, Traffic center는전달받은 RSU의근처에있는이웃 RSU들에게 density 를전달한다. 그결과, RSU는인근이웃 RSU의 density 정보를알게되고, 근원지노드가중간노드를선정할때활용할수있도록 RSU 전송범위내의모든노드들에게브로드캐스트한다. RSU는일정한시간단위를기준으로주기적으로 density 를측정한다. RSU가 density 를측정하는절차는다음과같다. [1 단계 ] RSU는자신의전송범위내에서진입하는노드들의 Hello message를수신한다. [2 단계 ] RSU는수신한 Hello message 의 timestamp 가유효한지를확인한다. 이때 Hello message의 timestamp 가유효하지않으면, RSU이 Hello message를버린다. 707
한국산학기술학회논문지제 16 권제 1 호, 2015 3.3 TGF 알고리즘설계기존의 Greedy Forwarding 알고리즘은목적지노드와의거리가가장가까운이웃노드를중간노드로선정는데, 이때중간노드의이웃노드가존재하지않으면 local maximum 문제에빠지게된다. 본논문에서는목적지까지의데이터를전송하기위해선정한중간노드의 local maximum 문제를최소화시키기위해방향과밀집도를고려한 TGF(Transformed Greedy Forwarding) 알고리즘을설계하였다. TGF알고리즘은 Transformed Greedy mode와 Transformed Perimeter mode로구성된다. [Fig. 6] the calculation procedure of density [3 단계 ] RSU는 Hello message의 Node ID가중복되는지를확인한다. 이때, Node ID가중복된다면, RSU는이 Hello message를버린다. [4 단계 ] RSU는 timestamp 가유효하고, Node ID가중복되지않는 Hello message를카운트한다. 즉, RSU는 density 를 1 증가시킨다. [5 단계 ] RSU는측정된 density 를 Traffic center에전달한다. [6 단계 ] Traffic center는 RSU로부터전달받은 density 를이웃 RSU에전달한다. [7 단계 ] Density 를전달받은 RSU는표 5의 RSU 테이블에저장하고, 자신의전송범위내의노드들에이웃 RSU의밀집도를브로드캐스트한다. 그리하여, UIGRP가 local maximum 문제에직면하였을때, 이밀집도를이용하여 local maximum 문제를신속하게해결할수있도록한다. [Table 5] RUS Table Field Contents RSU ID Identifier of RSU Densty density 3.3.1 Transformed greedy mode 설계본논문에서제안하는 TGF 알고리즘의 Transformed greedy mode 는다음과같은절차에따라중간노드를선정하도록설계하였다. 그림 7은 TGF 알고리즘의 Transformed greedy mode를설명한것이다. [1 단계 ] 근원지노드는 1홉단위내에위치하고있는이웃노드들로부터 Hello message를수신한다. [2 단계 ] 근원지노드는전달받은이웃노드리스트를이용하여라우팅테이블정보를 3.2.2절의표 3과같이갱신한다. [3 단계 ] 근원지노드는이웃노드가 1개이상존재하는이웃노드들로만후보리스트를생성한다. [4 단계 ] 근원지노드는후보리스트들의위치정보를이용해목적지노드간의거리를 3.2.2절의식 (1) 을이용하여산출한다. [5 단계 ] 근원지노드는후보리스트의이동방향을 3.2.3절의식 (2) 에의해측정하고, 후보리스트중에서목적지가위치한곳으로이동하는이웃노드를추출한다. [6 단계 ] 근원지노드는 5단계에서추출된이웃노드중에서아래의조건에맞는노드를중간노드로선정하고후보리스트를삭제한다. 조건 1) 이웃노드가가장많은노드조건 2) 목적지노드와가장짧은거리에위치한노드 708
차량이동방향과밀집도를고려한 UIGRP(Urban Intersection based Geographic Routing Protocol) 설계 X is Source Node D is Destination Node N is Neighboring node Nlist is Neiboring node List Hello message includes node ID, position, and Nlist. 1. Receives Hello message to N 2. Update routing table. 3. if(direction == 1) then 4. if (the number of Nilst >= 1) then 5. insert Candidate list 6. calculate distance 7. else 8. call perimeter mode 9. end if 10. if (Max(the number of Nlist) and Min(distance)) then 11. set intermediate node 12. if (next(intermediate node)!= D) 13. go to 1. 14. else 15. complete message transmission route. 16. end if 17. end if 18. end if [Fig. 7] TGF Algorithm : Transformed greedy mode 3.3.2 Transformed Perimeter mode 본논문에서제안하는 TGF 알고리즘의 Transformed perimeter mode는다음과같은절차에따라 local maximum 문제를해결하도록설계하였다. 그림 8은 TGF 알고리즘의 Transformed perimeter mode를설명한것이다. [1 단계 ] local maximum 문제에직면한중간노드는 RSU 로부터전달받은인근도로의 density 정보중에서가장높은 density 를갖는 RSU 가위치한방향을선택한다. [2 단계 ] 중간노드가선택한 RSU가위치한방향에위치한이웃노드를후보리스트로선택한다. [3 단계 ] 중간노드는후보리스트들의위치정보를이용해목적지노드간의거리를 3.2.2절의식 (1) 을이용하여산출한다. [4 단계 ] 중간노드는후보리스트와목적지노드의위치정보를이용하여 3.2.2절의식 (2) 를이용하여 direction을산출한다. [5 단계 ] 중간노드는아래의조건에맞는노드를중간노드로선정하고후보리스트를삭제한다. 조건 1) 이웃노드가가장많은노드조건 2) 밀집도가높은방향에위치하는노드조건 3) 목적지노드와가장짧은거리에위치한노드 I is Intermediate Node D is Destination Node N is Neighboring node Nlist is Neiboring node List Hello message includes node ID, position, and Nlist. 1. Receives the density of RSU. 2. if highest(density.rsu) then 3. select the node in the scope of RSU. 4. if (the number of Nlist)>=1) then 5. insert candidate list 6. calculate distance. 7. calculate direction. 8. end if 9. end if 10. if(max(the number of Nlist) and min(distance) then 11. set intermediate node 12. if (next(intermediate node)!= D) then 13. call greedy mode 15. else 14. complete message transmission route 15. end if 16. end if [Fig. 8] TGF Algorithm : Transformed perimeter mode 4. 성능분석 본논문에서제안하는 UIGRP과기존의 GPSR[4,5], GPUR[9] 의성능을 ns-2 시뮬레이터를이용하여비교분석한다. 성능분석을위한 ns-2 시뮬레이터의파라미터는표 6과같다. [Table 6] Simulation parameters Parameters simulation area 1500*1500 transmission range 100m MAC protocol IEEE 802.11 traffic type CBR the number of nodes 100~500 Simulation times 120 seconds packet size 32 bytes packet interval time 0.2 sec Values 709
한국산학기술학회논문지제 16 권제 1 호, 2015 성능분석은 100, 200, 300, 400, 그리고 500개의노드들을랜덤하게위치시키고, 20회반복실행하여산출된 local maximum 문제발생횟수, 패킷전송성공률, 그리고라우팅홉수를비교하였다. local maximum 문제발생횟수는노드의수에따라패킷을전달받은이웃노드중 local maximum 문제에직면하는횟수로측정하였고, 패킷전송성공률은식 (3) 에의해계산하고, 라우팅홉수는식 (4) 를이용하여산출하였다.... (3) 라우팅홉수 = 중간노드의수... (4) [Fig. 10] The comparison of packet transmission success ratio [Fig. 9] The comparison of local maximum problem occurrence 그림 9는노드의수에따라 local maximum 문제에직면하는횟수를설명한것이다. 그림 9에서설명하고있듯이노드수가증가할수록이웃노드가증가하므로 local maximum 문제발생횟수가감소하고있다. 본논문에서제안한 UIGRP와 GPSR, GPUR을비교해볼때 local maximum 문제발생횟수가평균적으로 3회, 1회감소하였다는것을알수있다. 그림 10은노드수의증가에따른패킷전송성공률을비교한것이다. 그림 10에서설명하고있듯이 GPSR와 GPUR보다패킷성공률이높은이유는 local maximum 문제발생횟수가적어 greedy mode와 perimeter mode 를반복하지않아도되므로패킷손실이감소하였다. 그결과. UIGRP의패킷전송성공률이높게나타났으며, 그림 11과같이패킷전송시간을 GPSR와 GPUR에비해평균적으로 6.12(ms), 2.04(ms) 줄일수있었다. [Fig. 11] The time comparison of packet transmission 그림 12는근원지노드에서목적지노드까지의중간노드의수를카운트한라우팅홉수를비교한것이다. GPSR은 greedy mode와 perimeter mode를반복하여중간노드를선정할때중간노드의이동방향을고려하지않기때문에라우팅홉수가증가한다. 하지만, 본논문에서제안하는 UIGRP는 greedy mode에서이동방향, 이웃노드수그리고목적지와의거리를고려하여중간노드를선정함으로써 local maximum 문제발생횟수를줄이고, perimeter mode에서밀집도와이동방향을고려하여중간노드를선정하기때문에라우터홉수를 GPSR보다평균적으로약 3 hop을줄일수있었으며, GPUR보다는평균적으로약 1hop을줄일수있었다. 710
차량이동방향과밀집도를고려한 UIGRP(Urban Intersection based Geographic Routing Protocol) 설계 [Fig. 12] The number comparison of routing hop 5. 결론본논문에서는이동방향, 이웃노드의수, 그리고밀집도를이용하여중간노드선정하는지리기반프로토콜인 UIGRP를제안하였다. 본논문에서제안하는 UIGRP의특징은다음과같다. 첫째, 차량의이동방향, 이웃노드의수를이용하여중간노드를선정함으로써 local maximum 문제발생횟수를기존의 GPSR와 GPUR로비교해볼때, 평균적으로각각 3회, 1회감소시켰다. 둘째, 중간노드가 local maximum 문제에직면하였을때, UIGRP는밀집도가곳에위치하고, 이웃노드수, 목적지와거리를고려하여중간노드를선정함으로써 local maximum 문제를신속하게해결할수있었다. 셋째, UIGRP는 local maximum 문제발생횟수를줄임으로써라우팅홉수를기존의 GPSR와 GPUR로비교해볼때평균적으로각각 3홉, 1홉줄였다. 그결과, UIGRP는패킷전송경로를줄여패킷전송시간을평균적으로 6.12(ms) 와 2.04(ms) 줄이고, 패킷전송성공률을평균적으로 15%, 3% 향상시킴으로써 VANET의신뢰성을향상시킬수있었다. References [1] Eun-Young Kang, Node ID-based Service Discovery for Mobile Ad Hoc Ketwork, Journal of The Korea Society of Computer and Information, Vol.14, No.12, pp.109-117, Dec. 2009 [2] Jae Soo Kim and Jeong Hong Kim, Distance Ratio based Probabilistic Broadcasting Mechanism in Mobile Ad Hoc Network, Journal of The Korea Society of Computer and Information, Vol.15, No.12, pp75-83, Dec. 2010 DOI: http://dx.doi.org/10.9708/jksci.2010.15.12.075 [3] Young-Bae Ko, Nitin H. Faiday, Location-aided routing (LAR) in mobile ad hoc networks, Wireless netowrks, Vol.6, No.4, pp307-321, 2000 [4] B. Karp and H. T. Kung, GPSR : Greedy Perimeter Stateless Routing for Wireless Network, in proc. of ACM/IEEE MOBICOM 2000, pp.243-254, Aug. 2000. DOI: http://dx.doi.org/10.1145/345910.345953 [5] B. Karp, Geographic Routing forwireless Networks, Harvard University, 2000 [6] JooSang Youn, "Virtual Location Information based Routing Scheme in Wireless Ad-Hoc Network," Journal of The Korea Society of Computer and Information, Vol.18, No.2, pp.77-85, Feb. 2013 DOI: http://dx.doi.org/10.9708/jksci.2013.18.2.077 [7] Dae-Hee Kim, Sun-Sin An, Research and Trends about VANET Routing, Korea Information and Communications Society(Information and Communications Magazine), Vol.30, No.5, pp.95-105, April 2013. [8] Sunghyun cho, Seokwoo Kim, "Routing Algorithm of VANET for an Efficient Path Management in Urban Intersections," Journal of Korea Information and Communications Society, Vol.38A, No.12, pp.1054-1060, Dec. 2013. DOI: http://dx.doi.org/10.7840/kics.2013.38a.12.1054 [9] Min-Woo Ryu, Si-Ho Cha, Kuk-Hyun Cho,, A Vehicle Communication Routing Algorithm Considering Road Characteristics and 2-Hop Neighbors in Urban Areas, Journal of Korea Information and Communications Society, Vol.36, No.5 pp.464-475, May 2011. DOI: http://dx.doi.org/10.7840/kics.2011.36b.5.464 [10] Min-Woo Ryu, Si-Ho Cha, Kuk-Hyun Cho, "An Enhanced Greedy Message Forwarding Protocol for Increasing Reliablity of Mobile Inter-Vehicle Communication", Journal of The Institute of Electronics Engineering of Korea, Vol.47-TC, No.4, pp.43-50, April 2010. [11] Witt, M. and V. Turau., The Impact of Location Errors on Geographic Routing in Sensor Networks, in Proc. of the International Multi-Conference on Computing in the Global Information Technology, pp.76, 2006. [12] Chia-Chang Hsu and Chin-Laung Lei, Firework Search for Location Aided Routing Enhancement in Mobile Ad-Hoc Networks, in Proc. of the 8th ACM International 711
한국산학기술학회논문지제 16 권제 1 호, 2015 Workshop on Mobility Management and Wireless Access, pp.121-124, 2010. DOI: http://dx.doi.org/10.1145/1868497.1868519 [13] Hexa Software Development Center, "Geographical Distance Calculations", Available From: http://www.zipcodeworld.com (accessed Jun., 30, 2014) 이병관 (Byung-Kwan Lee) [ 정회원 ] 1986 년 2 월 : 중앙대학교전자계산공학과 ( 공학석사 ) 1990 년 2 월 : 중앙대학교전자계산공학과 ( 공학박사 ) 1988 년 3 월 ~ 현재 : 가톨릭관동대학교컴퓨터학과교수 < 관심분야 > 네트워크보안, IoT, 빅데이터, 센서네트워크 정은희 (Eun-Hee Jeong) [ 정회원 ] 1998 년 2 월 : 관동대학교전자계산공학과 ( 공학석사 ) 2003 년 2 월 : 관동대학교전자계산공학과 ( 공학박사 ) 2003 년 9 월 ~ 현재 : 강원대학교삼척캠퍼스지역경제학과교수 < 관심분야 > 네트워크보안, 전자상거래보안, 빅데이터, 센서네트워크 712