한국산학기술학회논문지 Vol. 10, o. 9, pp. 2340-2349, 2009 허석렬 1, 이완직 1, 장성식 2, 변태영 3, 이원열 4* 1 부산대학교바이오메디컬공학과, 2 영남이공대학모바일인터넷과, 3 대구가톨릭대학교정보통신공학과, 4 영산대학교사이버경찰학과 opping Routing Scheme to Resolve the ot Spot Problem of Periodic Monitoring Services in Wireless Sensor etworks Seok Yeol eo 1, Wan-Jik Lee 1, Seong-Sik Jang 2, Tae-Young Byun 3 and Won-Yeol Lee 4* 1 Department of Biomedical Engineering, Pusan ational University 2 Department of Mobile Internet, Yeungnam College of Science and Technology 3 School of Information Communication Engineering, Catholic University of Daegu 4 Department of Cyber and Police Science, Youngsan University 요약본논문에서는주기적모니터링센서네트워크의핫스팟문제를해결하기위한호핑라우팅기법을제안한다. 제안한호핑라우팅기법은네트워크의모든노드들의에너지소비형태가예측가능한부하균등경로를구성한다. 부하균등라우팅경로는동일한영역내노드들의부하균형을이루는수평호핑전송기법과서로다른영역에있는노드사이에부하균형을이루는수직호핑전송기법으로구할수있다. 수직호핑전송에필요한직접전송횟수는센서노드의에너지소비모델을통해서부하균형을이룰수있는값을도출하였다. 시뮬레이션을통해서제안한호핑라우팅기법이핫스팟문제를효과적으로해결함을보였으며기존라우팅기법중에서멀티홉전송방식과직접전송방식그리고클러스터링기법과비교평가를통해서호핑라우팅기법의효율성을제시하였다. Abstract In this paper we proposed a hopping routing scheme to resolve the hot spot problem for periodic monitoring services in wireless sensor networks. Our hopping routing scheme constructs load balanced routing path, where an amount of energy consumption of all nodes in the sensor networks is predictable. Load balanced routing paths can be obtained from horizontal hopping transmission scheme which balances the load of the sensor nodes in the same area, and also from vertical hopping transmission scheme which balances the load of the sensor nodes in the other area. The direct transmission count numbers as load balancing parameter for vertical hopping transmission are derived using the energy consumption model of the sensor nodes. The experimental results show that the proposed hopping scheme resolves the hot spot problem effectively. The efficiency of hopping routing scheme is also shown by comparison with other routing scheme such as multi-hop, direct transmission and clustering. Key Words : ot Spot Problem, opping Routing, Load Balanced Routing Path 1. 서론 센서네트워크는온도나습도, 대기오염측정서비스 와같이주기적으로센싱한데이터를싱크노드로전달하는응용분야, 침입탐지나경보서비스와같이정해진사건이발생할경우이를싱크노드에게알리는응용분 * 교신저자 : 이원열 (lumpen@ysu.ac.kr) 접수일 09 년 07 월 27 일수정일 09 년 09 월 11 일게재확정일 09 년 09 월 16 일 2340
야그리고싱크노드가관심데이터를요청할경우해당노드만데이터를전송하는응용분야로크게나눌수있다. 이중에서주기적으로상태를모니터링해서싱크노드로전달하는응용분야가센서네트워크응용의가장많은부분을차지하며사건발생형태의응용의경우에도센서노드의동작여부와데이터신뢰성이요구되는경우에는주기적인전송형태를가지는경우가많다. 센서네트워크가제공하는서비스종류가다양한만큼각서비스에따른적절한라우팅방식이필요하며, 지금까지이와관련된많은라우팅관련연구들이진행되었다 [1-3]. 지금까지제안된센서네트워크용라우팅기법들은대부분수시로전송경로가변화하는동적라우팅경로선택방식과지역정보를활용한분산알고리즘방식을채택하고있으며직접전송혹은멀티홉전송방식중에한가지전송방식만을취하는특징을가지고있다 [4-6]. 이러한특징을가진기존라우팅기법의가장큰문제는핫스팟 (hot spot) 문제해결이매우어렵다는것이다. 핫스팟이발생하면해당지역의센싱불능및연결성의소멸이라는치명적문제를일으킨다. 따라서핫스팟문제의해결은센서네트워크의라우팅에서매우중요하게다루어져야할부분이다. 핫스팟이발생하면그림 1에서보는바와같이비연결영역 (disconnected area) 의모든노드들은싱크노드까지의경로상의핫스팟으로인해연결이단절되어데이터전달이불가능함을알수있다. Disconnected Area Sense Field Sink ode Dead Sensor ode Live Sensor ode ot Spot (Communication ole) [ 그림 1] 핫스팟발생으로인한연결단절현상핫스팟문제는전송방식에따라나타나는형태가다양하다. 직접전송방식의경우, 싱크노드로부터먼거리의노드가먼저에너지가고갈되는형태로핫스팟현상이나타난다. 멀티홉전송의경우, 싱크노드와가까운노드가먼저에너지가고갈되는형태로핫스팟문제가발생한다. 그리고라우팅방식에따라나타나는핫스팟현상도다양하다. 즉, 타경로에비해더많은데이터전송 이이루어지는경로에서핫스팟이발생하는형태로나타난다. 본논문에서는센서네트워크에서가장많은적용분야를가지고있는주기적모니터링서비스환경에서핫스팟문제를해결하기위한호핑라우팅기법을제안한다. 제안하는호핑라우팅기법은모든센서노드의에너지소비를미리예측하여라우팅경로를만들고, 모든노드의전송에너지를거의동일하게소비하게하여센서노드들간에부하균형을이룬다. 이를위해서본논문에서는센서노드의에너지소비모델분석을통하여수평및수직호핑전송에필요한기본동작을정의하고이에필요한세부기능과전송파라미터를도출하였다. 그리고본논문에서제안한호핑라우팅기법의성능을시뮬레이션을통해기존라우팅프로토콜과비교분석하였다. 본논문의 2장에서는핫스팟문제해결을위한기존의연구에대하여언급하였으며, 3장에는본논문에서제안하는호핑라우팅기법에대하여설명하였다. 4장에는제안기법의성능평가결과에대하여나타내었고 5장에서결론및향후과제를다루었다. 2. 핫스팟해결을위한기존연구 2.1 기존연구 센서네트워크의생존시간을증가시키기위해제안된많은라우팅기법들은불균형한에너지소비패턴을조절할수있다고주장하였다 [4-10]. 그러나대부분의제안된기법들은편중된에너지소비패턴을일부개선할수있을뿐이다. LEAC(Low-Energy Adaptive Clustering ierarchy) 프로토콜의경우클러스터헤드노드의역할을클러스터의노드들이번갈아가며수행함으로써과도한에너지소비를필요로하는헤드노드의부하를분산하고자하였다 [6]. 그러나이기법은전체네트워크의에너지편중문제를완화시킴으로써부분적으로는핫스팟문제를해결할수있지만근본적인해결방안은되지못한다. UCS(Unequal Clustering Size) 기법 [11] 은클러스터헤드노드가정해진위치로이동할수있다는가정에서출발하였다. 그러나이러한가정은센서네트워크응용분야적용성이매우낮다. 그리고클러스터내부통신비용과클러스터간통신비용사이의관계즉, 비용비는감안하지않았다. 프로토콜마다클러스터간및클러스터내부통신비용에차이가있으므로 UCS 기법의적용가 2341
한국산학기술학회논문지제 10 권제 9 호, 2009 능성은매우낮다. Energy-Aware Routing 기법 [2] 은싱크노드로의경로를결정할때가장작은에너지가소비되는경로가항상가장좋은경로는아니라는기본아이디어로동작한다. 이기법에서는지속적으로경로를평가할수도있고변경도가능하다. 그러나패킷전송시마다경로결정을수행한다는것과이전노드의에너지상태등을지속적으로관리해야한다는것이에너지소비를증가시킬수있다. 2.2 핫스팟발생원인분석본논문에서는센서네트워크의핫스팟문제를해결할수있는방법을찾기위하여우선기존의라우팅프로토콜이가지고있는문제를분석한다. 1) 일정하지않은전송으로인한부하불균형 Directed Diffusion[12] 등과같은라우팅기법은에너지소모를줄이기위해전송경로가중첩될경우데이터병합을수행한다. 데이터병합을수행할경우송수신비율이일정하지않기때문에부분적으로핫스팟이발생할수있다. 2) 직접전송에의한부하불균형 LEAC 프로토콜과같이모든노드가싱크노드로직접전송을함으로써싱크노드로부터먼거리의노드에너지소비가상대적으로커진다. 그결과로싱크노드로부터먼거리에서핫스팟이발생한다. 3) 멀티홉전송에의한부하불균형멀티홉전송의경우싱크노드와가까운노드가상대적으로더많은횟수의릴레이전송을해야하므로싱크노드와가까운위치에서부터핫스팟이발생한다. 4) 동적인경로설정각각의센서노드로부터싱크노드로의경로가지속적으로변하는동적라우팅경로방식을취함으로써센서노드들의에너지소비가수시로변화하는문제가있다. 이러한경우네트워크의모든지역에서핫스팟이발생할수있다. 는것이비용이많이들었기때문에지역정보만을이용한라우팅프로토콜이대부분제안되었다. 이렇게지역정보만을이용함으로써전체노드의에너지잔량을감안한라우팅동작이불가능하고이로인한핫스팟문제는필연적으로발생한다. 2.3 핫스팟회피를위한라우팅기법설계방안 2.2절에서설명한것과같이핫스팟발생원인은라우팅에의한특정경로로의트래픽편중현상이다. 이같은현상이일어나는것은다중경로와동적경로설정, 분산라우팅기법등에그원인이있다. 핫스팟문제를해결하기위해서는일단이러한원인들부터제거해야하지만, 이러한원인들을제거하여도핫스팟문제를완전하게해결할수는없다. 왜냐하면핫스팟문제를해결하기위해서는트래픽흐름을모든경로에공평하게분배해야하기때문이다. 트래픽흐름을공평하게분배하려면모든센서노드의에너지소비가같아야하며이를위해서는트래픽흐름이예측가능해야한다. 트래픽흐름의예측가능여부는라우팅동작특성에의존적이기때문에지금까지분석한핫스팟문제의원인분석및해결방향을감안한센서네트워크라우팅설계방향을다음과같이제시한다. 1) 일정한송수신비율유지센서노드가처리하는송수신회수를일정하게유지하면센서노드가소비하는에너지를예측할수있다. 데이터병합이필요한경우에도 LEAC[6] 프로토콜처럼센서노드가균등하게이를처리한다면에너지균형을기대할수있다. 2) 정적라우팅사용동적라우팅은각노드의에너지소비량을예측할수없게만드는요소이다. 반면센서네트워크에서정적라우팅을사용한다면센서노드의에너지소비량을예측할수있다. 기존의라우팅기법은대부분지역적인정보만을이용하는동적라우팅방식을채택하고있다. 만일네트워크전체의위치정보를활용할수있다면동적라우팅보다더효율적인정적라우팅이가능하다. 5) 지역정보를이용함으로써발생하는부하불균형센서네트워크의라우팅동작은대부분지역정보즉, 인접노드정보만을이용해서이루어진다. 센서네트워크개발초기에는모든센서노드들의위치정보를파악하 3) 중앙집중형라우팅기법분산라우팅의경우네트워크전체노드의에너지를감안한라우팅경로계산이불가능하다. 분산라우팅은센서노드들의위치정보를중앙집중적으로관리할수 2342
없다는가정에서이루어졌다. 그러나현재센서노드의위치를추적할수있는많은기법들이제시되고있으며이를이용하여네트워크초기구성시에모든노드들이자신의위치정보를싱크노드로전송할수있다. 따라서전체네트워크의모든센서노드의위치정보를이용하면중앙집중형으로라우팅경로를계산할수있다. 4) 멀티모드전송방식센서네트워크의전송방식은직접전송방식과멀티홉전송방식으로나누어진다. 멀티홉전송의경우 1 홉거리의노드를제외하고는모든노드가멀티홉전송을수행한다. 즉기존의라우팅방식에서는직접전송과멀티홉전송중에한가지전송방식만을선택적으로사용한다. 이경우싱크노드와의거리에따른에너지소비차이를극복할수없게된다. 에너지소비를예측할수있으면직접전송과멀티홉전송을모두사용하여에너지소비를균등하게할수있다. 지금까지기존의라우팅방식이센서네트워크의부하를균등하게할수없게하는요인들을분석하였고이를해결할수있는방안을제시하였다. 본논문에서는이러한기존라우팅방식들의불필요한요소들을제거한새로운방식의라우팅기법및전송방식을제안한다. 3. 호핑라우팅기법 본논문에서제안하는호핑라우팅기법은핫스팟을해결하기위해부하균등라우팅경로를구성하고결정된경로상에서호핑전송을통해모든노드의송수신에너지소비를적절히배분하는것을목표로한다. 센서네트워크는제공하는서비스에따라라우팅동작에차이가많다. 본논문에서가정하는센서네트워크의특징은다음과같다. 모든센서노드는주기적으로센싱된데이터를싱크노드로전송한다. 모든센서노드와싱크노드는이동성이없다. 모든노드는멀티홉전송시고정전송반경을가진다. 데이터병합은수행하지않는다. 싱크노드는센서노드의위치를알수있다. 본논문에서제안하는호핑라우팅기법은고정라우팅경로, 멀티홉및직접전송을모두수행하는멀티모드전송방식과싱크노드가모든라우팅관련처리를수행하는중앙집중형라우팅기법을채택하고있다. 이동이없는노드사이의라우팅경로는정적으로구성하여 도효율성에서큰문제가없다. 따라서센서네트워크의큰단점인핫스팟문제를해결할수있다면정적라우팅경로를사용하는것이효율적이다. 분산형라우팅방식에서는모든노드가라우팅관련처리를수행해야한다. 센서네트워크의생존시간은센서노드의에너지소비와밀접한관계가있다. 따라서싱크노드가라우팅관련처리를수행하면센서네트워크의생존시간은그만큼연장될수있다. 본논문에서는멀티홉전송을기반으로하는센서네트워크를대상으로하기때문에모든노드의부하를균등하게하기위해우선네트워크를싱크노드와의거리를기반으로영역을설정한다. 동일영역노드들의부하균형은이전영역으로부터의릴레이전송요청부하를동일하게함으로써이룰수있다. 모든노드에서발생하는센싱데이터의양은같지만이전노드로부터수신하는릴레이전송요청횟수는서로다를수있다. 만일릴레이전송요청횟수를동일하게할수있으면동일영역의모든노드들의전송에너지는동일하게할수있다. 동일영역노드들의에너지소비크기를같게하여도다른영역노드들간의에너지소비는차이가발생한다. 서로다른영역노드들간의부하균형은직접전송과멀티홉전송을적절히배분하여수행함으로써얻을수있다. 먼거리의노드가멀티홉전송을하지않고직접전송을하면그만큼자신의에너지사용크기는증가하지만싱크노드와가까운노드의릴레이전송횟수는줄어들어에너지소비가줄어들것이다. 이러한특성을이용하여싱크노드로부터 2 홉이상의거리에있는모든노드는멀티홉전송과직접전송을번갈아수행함으로써전송에너지를거의동일한수준으로유지할수있다. 3.1 수평호핑전송을이용한부하균등라우팅경로구성부하균등라우팅경로는동일영역의모든노드가이전영역의노드로부터수신되는릴레이전송요구횟수가모두동일한라우팅경로를의미한다. 한영역의모든노드의릴레이요구횟수를동일하게하기위해서는각영역의노드개수에따라릴레이전송을적절하게분배하여야한다. 이러한조건을만족하기위해서는기존의방식과는다른방식의릴레이전송기법이필요하다. 본논문에서는한노드가다음영역의노드로릴레이전송을할때항상동일한노드로만하는것이아니라다수의노드로번갈아가며전송하는수평호핑전송기법을제안한다. 수평호핑전송동작을그림 2에나타내었다. 그림 2343
한국산학기술학회논문지제 10 권제 9 호, 2009 2(a) 에서영역 1(area 1) 의 1번노드는영역 2로부터 2회의릴레이전송요청을수신한다. 반면에 2번노드는 3회의릴레이요청을수신한다. 따라서 2번노드와 3번노드의에너지소비에차이가발생한다. 부하균등라우팅경로를구성하기위해필요한경우호핑노드를선택하여릴레이전송횟수를균등하게한다. 그림 2(b) 에서 3번노드가호핑노드역할을수행한다. 호핑노드는릴레이전송요청을한노드에게만하지않고정해진다수의노드에게번갈아가며요청한다. 만일그림 2(b) 에서영역 2의노드들이각각 10개의패킷을발생시키면총 50개의패킷이영역 1로전달되며영역 1의각노드는 25개씩의패킷을동일하게전달요청받는다. 으로써멀티홉전송에비해많은에너지를소비하지만, 직접전송횟수만큼싱크노드까지거쳐야할릴레이전송횟수가감소하기때문에릴레이경로상의노드들은에너지소비를절약할수있다. sink node sink node area 1 1 2 1 2 area 1 area 2 3 3 area 2 Vertical opping Transmission [ 그림 3] 수직호핑전송동작 sink node sink node area 1 1 2 1 2 area 1 area 2 3 3 area 2 orizontal opping Transmission designated node hopping node (a) 기존라우팅경로 (b) 부하균등라우팅경로 [ 그림 2] 수평호핑전송동작 3.3 직접전송횟수수평호핑은정해진노드만수행하는데반해수직호핑전송은싱크로부터 1 홉영역의노드들을제외한나머지모든노드가수행한다. 수직호핑전송으로타영역의노드들간의전송에너지를동일하게하기위해서는각영역노드별직접전송대멀티홉전송비를계산하여야한다. 그림 4에직접전송횟수계산을위한전송비용분석모델을나타내었다. 3.2 수직호핑전송을이용한부하균등라우팅수평호핑을통해동일영역의노드들간의릴레이전송요청횟수를동일하게함으로써전송에너지소비를동일하게할수있었다. 그러나서로다른영역간의에너지소비는여전히차이가난다. 이러한영역간의에너지소비차이를없애기위해서는거리가먼영역의노드는에너지소비를늘리고거리가가까운영역의노드는에너지소비를줄임으로써에너지소비균형을맞출수있다. 즉, 거리가먼영역의노드는자신이전송할패킷의일부를싱크노드로직접전송하도록함으로써에너지소비를늘리고거리가가까운영역의노드는릴레이패킷수를줄임으로써에너지소비를줄일수있다. 이와같이한노드가전송할패킷의일부는멀티홉전송을하고나머지패킷은싱크노드로직접전송하는동작을수직호핑이라고한다. 그림 3에수직호핑전송의동작을나타내었다. 수직호핑전송은서로다른영역의노드들간의부하균형을위한전송방식이다. 수직호핑전송은싱크노드로부터의거리가 2 홉이상인노드가멀티홉전송과싱크노드로의직접전송을번갈아가며함으로써타영역노드와에너지소비를균등하게하는동작이다. 먼거리의노드는직접전송을함 multi-hop transmission =-d_i= m_i ode i1: multi-hop transmission = + 2*m_i d_j ode j: direct transmission = d_i area j multi-hop transmission = m_i area i ode i2: direct transmission = d_j m_i: 노드 i 에서다음홉으로릴레이요구하는패킷수 d_i: 노드 i 의직접전송회수 direct transmission = d_i [ 그림 4] 직접전송회수를위한전송비용분석모델그림 4에서 m_j, m_i1, m_i2 는영역 j의노드 j와영역 i의 1번과 2번노드의멀티홉전송을위한릴레이전송횟수를의미하며 d_j, d_i1, d_i2 는각각영역 j의노드 j 와영역 i의 1번과 2번노드의직접전송횟수를나타낸다. 직접전송횟수 d_j 는노드 j가한라운드동안생성하는패킷중에서싱크노드로직접전송해야하는전송횟수를의미한다. 즉노드 j는한라운드동안자신이생성한패킷들과이전노드들로부터릴레이전송요청을받은패킷들이있다. 이패킷들중에서 d_j 만큼을직접전송으로보내고나머지는다음홉으로릴레이전송한다. 직접전송횟수 d_j, d_i1, d_i2 는네트워크전체의정보를알아야만결정할수있기때문에싱크노드에서결정 2344
하는것이효율적이다. 싱크노드는네트워크초기설정시에모든센서노드로부터직접전송회수결정에필요한정보를수신하기때문에부가적인오버헤더없이직접전송회수를결정할수있다. 그림 4는영역 i의두개의노드가영역 j의하나의노드로멀티홉전송을하는경우를보여준다. 영역 i의 1번노드는자신이보내야하는패킷들중에 m_i1 개는멀티홉전송을통해싱크노드로전송하고 d_i1 개는직접전송을통해싱크노드로전송한다. 노드 j의에너지소비량과노드 i1의에너지소비량을동일하게할수있는 d_j 와 d_i 를구하면수직호핑전송을통해타영역노드간의에너지소비를균등하게할수있다. 동일영역의노드들은수평호핑을통해동일한횟수의송수신을수행하므로가 m_i1 = m_i2 및 d_i1 = d_i2 가성립한다. 직접전송횟수계산을위해센서노드들의송수신에너지소비량이필요한데, 본논문에서는 [6] 에서적용한에너지소비패턴을사용하였다. 식 3과 4에 k 비트전송에필요한에너지 E T 와 k 비트수신에필요한에너지 E R 을나타내었다. E elec 은 1 비트를처리하는데필요한프로세싱에너지를나타내고 ε은전송시신호증폭에필요한에너지이다. E E T R 2 ( k, r) E k + k r = elec ε (1) ( k r) = E k, elec (2) 식 1과 2에서알수있듯이송신에너지에비해수신에너지는상대적으로매우작은값을가지게된다. 그리고송신에너지는전송반경의제곱에비례하므로전송반경이매우중요한요소임을알수있다. 본논문에서는직접전송횟수계산을위해모든송수신패킷크기를동일하다고가정하였으며송신에너지에비해상대적으로매우작은값을가지는수신에너지는고려하지않았다. 직접전송횟수계산에필요한파라미터들을표 1에나타내었다. [ 표 1] 직접전송횟수계산에사용되는파라미터파라미터의미 K 싱크노드로부터홉거리 최대홉거리 p_i 영역 i의노드개수 d_i 노드 i의직접전송횟수 r 영역별거리 D 부하균등라우팅경로구성후최대전송반경 E i i 영역노드의전송에너지거리 d 일경우전송에너지 E T_d 그림 4와같은모델을이용하여각영역별노드의에너지소비량을식 5, 6, 7에각각나타내었다. 식 5의 E 1 과식 6의 E 2 는각각영역 1과영역 2의한노드가소비하는에너지를나타내며, 식 7의 E k 는영역 k의한노드가소비하는에너지를나타낸다. E 1 = i= 1 i= 1 ( d _ i ) ET _ D ( d _ i ) i i E = 2 = 2 2 = ET _ D + d _ 2 ET _ 2r E k = ( d _ i ) i= k i= k ET _ D + d _ k E T _ k r (3) (4) (5) 위식 3, 4, 5를이용하여 E 1= E 2= = E k 를풀면 d_1, d_2,, d_k 를구할수있다. 이렇게구한직접전송회수는모든노드의소비에너지를동일하게할수있는수직호핑을위한직접전송횟수가된다. 식 6에영역 의직접전송횟수 d_ 를나타내었으며 d_ 를이용하여나머지직접전송횟수를모두구할수있다. d _ = p _1 E + 1 E T _ D d _ i i= 1 i= 2 p _1 ( ET _ D ET _ r ) p _ ET _ D T _ D (6) 3.4 호핑라우팅동작수평 / 수직호핑라우팅을수행하기위해서는싱크노드와센서노드는초기화, 부하균등라우팅그리고네트워크동작의 3단계로동작한다. 먼저센서노드와싱크노드는초기화단계를통해서네트워크정보를교환한다. 초기화ㆍ센서노드는자신혹은주위의정보를이용해서자신의위치를파악하고시스템동작에필요한초기화작업을수행한뒤싱크노드로부터전송되는 SYC 메시지를기다린다. 싱크노드가보낸 SYC 메시지가수신되면자신의위치정보를포함한상태메시지를싱크노드에게응답하고싱크노드의라우팅경로통보를기다린다. ㆍ싱크노드는 SYC 메시지를모든노드에게전송하 2345
한국산학기술학회논문지제 10 권제 9 호, 2009 고센서노드에서보내오는응답메시지를통해서전체네트워크토폴로지구성에필요한정보를수집한다. SYC 메시지는직접전송을이용하거나플러딩을이용할수있다. ㆍ센서노드로부터응답메시지가모두수신되면싱크노드는부하균등라우팅단계를수행한다. 부하균등라우팅ㆍ싱크노드는수신된센서노드의응답메시지를이용해서영역별노드수를결정하고인접한영역사이에분할가능한그룹수를설정한다. ㆍ영역별그룹이정해지면각영역별그룹에대해서호핑노드와일반노드를결정하고각노드별로릴레이라우팅경로를결정한다. 이때고정노드는다음릴레이노드로단일노드만지정되며호핑노드에대해서는다수의릴레이노드가할당된다. ㆍ릴레이라우팅경로설정을통해서부하균등라우팅경로를설정한뒤각영역별로수직호핑전송을위한직접전송회수를계산한다. 이때직접전송회수는실수값으로구해지는데실제전송회수는정수값만의미가있기때문에반올림한값을직접전송회수로정하며반올림오차를줄이기위해서라운드회수 ( 예를들면 100회 ) 를곱한수에대해서반올림을적용한다. ㆍ싱크노드는정해진라우팅경로와직접전송회수를직접전송 ( 유니캐스트전송 ) 을이용하여각센서노드에게통보한다. 부하균등라우팅단계를마친뒤에싱크노드와센서노드는네트워크동작단계를통해서센서네트워크가정상적으로동작하도록한다. 네트워크동작ㆍ싱크노드로부터부하균등라우팅경로와직접전송회수를통보받은센서노드는라우팅테이블을갱신하고직접전송회수를노드초기변수에저장한뒤싱크노드로부터노드시작을알리는 STARTUP 메시지를기다린다. ㆍ싱크노드는라우팅경로와직접전송회수를통보한뒤일정시간이경과한뒤네트워크에있는모든센서노드에게 STARTUP 메시지를전송함으로써전체네트워크를동기화하고동작하도록한다. 4. 성능평가 4.1 실험환경및평가모델 본논문에서제안한호핑라우팅기법이핫스팟을효과적으로해결할수있음을확인하기위하여시뮬레이션을이용한성능평가를수행하였다. 성능평가에서는호핑라우팅기법에대한라운드별생존노드수와영역별에너지잔량을측정하였으며기존라우팅기법과의비교성능평가를위해멀티홉전송기법과직접전송기법, 클러스터링기법과비교하였다. 본논문에서수행된성능평가환경을표 2에나타내었다. [ 표 2] 성능평가용네트워크모델 파라미터 내용 네트워크크기 x, y 축의거리가 100m인 90 o 각을가진원호형태 노드개수 100개 영역별거리 (r) 25 m 멀티홉전송거리 (D) Max_Tr( 부하균등라우팅경로구성후결정 ) 프로세싱에너지 (E elec) 2.5 μj/bit 증폭에너지 (ε) 1.8 μj/bit/m 2 노드초기에너지패킷크기 (k) 4.2 성능평가 15 kj 400 bit 그림 5에본논문에서제안한호핑라우팅기법의라운드별생존노드수를나타내었다. 그림 5에서대부분의노드가거의같은시간에에너지가고갈됨을볼수있다. 에너지가고갈되는첫번째노드발생시점은대략 2800 라운드정도된다. 그이후에센서노드들의에너지가가파르게고갈됨을보여준다. umber of sensors still alive 100 90 80 70 60 50 40 30 20 10 0 0 500 1000 1500 2000 2500 3000 3500 4000 Rounds [ 그림 5] 호핑라우팅기법의라운드별생존노드수 2346
그림 6은싱크노드와의홉거리에따른영역별노드에너지잔량을측정한결과이다. 결과에서모든영역에걸쳐서노드들의에너지잔량변화가거의같음을알수있으며영역별부하균형이잘이루어지고있음을확인할수있다. Residual energy (%) 100 90 80 70 60 영역 4 영역 3 50 영역 2 영역 1 40 30 20 10 0 0 500 1000 1500 2000 2500 3000 3500 Rounds [ 그림 6] 호핑라우팅기법의영역별노드에너지잔량그림 7은싱크노드의패킷수신율을보여준다. 싱크노드의패킷수신율은핫스팟발생으로연결이단절되는경우급격히떨어지는현상이발생한다. 멀티홉기법의경우싱크노드로부터가까운영역노드의에너지가일찍고갈되어핫스팟이발생함으로써패킷수신율이급격히감소하는것을볼수있으며, 직접전송의경우또한싱크노드로부터먼거리노드에너지가일찍고갈되어패킷수신율이낮아짐을알수있다. 클러스터링기법의경우멀티홉전송기법이나직접전송기법경우에비해더나은성능을보이지만핫스팟문제를회피할수는없다는것을알수있다. 반면에호핑라우팅기법의패킷수신율은핫스팟이발생하지않음으로각노드의에너지가고갈될때까지네트워크의서비스를지속적으로제공할수있음을보여준다. 센서네트워크의생존시간은센서네트워크가적용되는서비스에따라다르게정의될수있다. 본논문에서대상으로하는주기적모니터링응용서비스는모든노드가생존이가능할때정상적인서비스가가능한응용분야이다. 이경우에는 FD(First ode Dies) 가네트워크생존시간의기준점이된다. 그림 8은호핑라우팅기법과멀티홉전송기법, 직접전송기법, 클러스터링기법에대한네트워크생존시간을보여준다. 그림에서호핑라우팅기법이다른기법보다약 1.3 2배정도생존시간이더긴것을확인할수있다. umber of sensors still alive 100 90 80 70 60 호핑라우팅직접선송 50 멀티홉클러스트링 40 30 20 10 0 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 Rounds [ 그림 8] 라우팅기법별생존노드수그림 7과 8의결과는호핑라우팅기법이효과적인에너지균형을통해서핫스팟문제를해결하면서기존의방식에비해네트워크생존시간성능또한우수함을보여준다. 5. 결론및향후과제 본논문에서는주기적모니터링환경의센서네트워크 100 에서핫스팟문제를해결할수있는호핑라우팅기법을 umber of average connection to sink 90 80 70 60 50 40 30 20 10 호핑전송직접전송멀티홉전송클러스터링 제안하였다. 제안된호핑라우팅기법은네트워크의모든노드들의에너지소비패턴이예측가능하도록부하균등라우팅경로를구성한다. 수평호핑전송기법은고정된단일경로로전송하는일반 ( 지정 ) 노드외에여러개의경로로호핑전송하는호핑노드를통해서동일한영역내노드간의부하균형을이룬다. 수직호핑전송기법은전송할트래픽의일부를 0 릴레이전송이아닌싱크노드로직접전송함으로써서 0 1000 2000 3000 4000 5000 Rounds [ 그림 7] 싱크노드의패킷수신율 로다른영역의노드사이에부하균형을이룬다. 수평호핑전송시우려되는최대전송반경의증가는 2347
한국산학기술학회논문지제 10 권제 9 호, 2009 효율적인호핑노드의선정을통해피할수있었고, 수직호핑전송에필요한직접전송횟수는센서노드의에너지소비모델을통해서부하균형을이룰수있는값을도출하여수직호핑전송에적용하였다. 호핑라우팅경로및직접전송횟수등라우팅에필요한모든계산을싱크노드가담당하는중앙집중형라우팅결정알고리즘을사용함으로써센서노드에대한오버헤더를줄였다. 시뮬레이션을통하여본논문에서제안한호핑라우팅기법이핫스팟문제를효과적으로해결함을보였으며기존의라우팅기법중에서멀티홉전송방식과직접전송방식그리고클러스터링기법과의패킷수신율과생존시간을비교평가함으로써호핑라우팅기법의효율성을제시하였다. 본논문에서제시한호핑라우팅기법은가변전송반경을갖는센서네트워크에는적용하기어렵고대규모센서네트워크의경우에도적용이불가능하다. 이를위해서는가변전송반경을갖는네트워크를대상으로한부하균등라우팅모델링이필요하며대규모네트워크를위해서는계층적라우팅을이용한부하균등라우팅이필요하다. 향후, 이에대한연구가추가로이루어져야할것이다. 참고문헌 [1] olger Karl and Andreas Willing, Protocols and Architectures for Wireless Sensor etworks, pp. 290-330, WILEY, 2005. [2] I. F. Akyildiz et al., Wireless sensor networks: a survey, Computer etworks, Vol. 38, pp. 393-422, March 2002. [3] R. C. Shah and J. M. Rabaey, Energy Aware Routing for Low Energy Ad oc Sensor etworks, Proceedings of the IEEE Wireless Communications and etworking Conference (WCC), Vol. 1, pp. 350-355, Orlando, FL, Mar. 2002. [4] J. Gomez and A.T. Campbell, A case for variable-range transmission power control in wireless multihop networks, proc. of the 23rd International Annual Joint Conference of the IEEE Computer and Communications Societies (IFOCOM'04), pp. 1425-1436, 2004. [5] Y. Xu, J. eidemann and D. Estrin, Adaptive energy-conserving routing for multihop ad hoc networks, Research Report 527, USC/ISI, October 2000,URL. [6] W. einzelman, A. Chandrakasan, and. Balakrishnan, An application specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications, Vol. 1, o. 4, pp. 660-670, Oct. 2002. [7] Jing Deng, Yunghsiang S. an, Wendi B. einzelman and Pramod K. Varshney, Balanced-energy sleep scheduling for high density cluster based sensor networks, Computer Communications Vol. 28, pp. 1631-1642, September 2005. [8] M. Perillo, Z. Cheng and W. B. einzelman, On the problem of unbalanced load distribution in wireless sensor networks, GlobeCom Workshops 2004, IEEE, ov. 29 - Dec. 3, pp. 74-79, 2004. [9] M. Younis, M. Youssef and K. Arisha, Energy aware routing in cluster based sensor networks, Proceedings of the 10th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS2002), pp. 129-136, Fort Worth, TX, Oct. 2002. [10] Gao J. and Zhang L., Load-Balanced Short-Path Routing in Wireless etworks, IEEE Transactions on Parallel and Distributed Systems 17(4), pp. 377 388, April 2006. [11] Stanislava Soro and Wendi B. einzelman, Prolonging the Lifetime of Wireless Sensor etworks via Unequal Clustering, Proceedings of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad oc and Sensor etworks (IEEEWMA'05), pp. 236-243, April 2005. [12] Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin and John eidemann, Directed diffusion for Wireless Sensor etworking, IEEE/ACM Transactions on networking. Vol. 11, pp.2-16, Feb. 2003. 2348
허석렬 (Seok Yeol eo) [ 정회원 ] 변태영 (Tae-Young Byun) [ 정회원 ] 1986년 2월 : 경북대학교전자공학과학사 1991년 2월 : 경북대학교컴퓨터공학과석사 2009년 2월 : 경북대학교컴퓨터공학과박사 1992년 3월 ~ 2005년 2월 : 밀양대학교컴퓨터공학부교수 2006년 3월 ~ 현재 : 부산대학교바이오메디컬공학과교수 < 관심분야 > RFID/US, 컴퓨터네트워크, u-ealth 1994년 2월 : 경북대학교컴퓨터공학과학사 1997년 2월 : 경북대학교컴퓨터공학과석사 2000년 2월 : 경북대학교컴퓨터공학과박사 1998년 3월 ~ 2000년 2월 : ( 주 ) 새빛정보대표이사 2000년 3월 ~ 2003년 2월 : 경주대학교컴퓨터전자공학부조교수 2003년 3월 ~ 현재 : 대구가톨릭대학교컴퓨터정보통신공학부조교수 < 관심분야 > 이동인터넷, 무선인터넷, 유비쿼터스네트워킹 이완직 (Wan-Jik Lee) [ 정회원 ] 1992 년 2 월 : 경북대학교통계학과학사 1994 년 2 월 : 경북대학교컴퓨터공학과석사 2007 년 8 월 : 경북대학교컴퓨터공학과박사 1997 년 3 월 ~ 2006 년 2 월 : 밀양대학교정보통신공학부교수 2006 년 3 월 ~ 현재 : 부산대학교바이오메디컬공학과교수 < 관심분야 > 통신프로토콜, 프로토콜구현, 네트워크보안 장성식 (Seong-Sik Jang) [ 정회원 ] 이원열 (Won Yeoul Lee) [ 정회원 ] 1987 년 2 월경북대학교전자공학과학사 1993 년 2 월경북대학교컴퓨터공학과석사 2002 년 : 2 월경북대학교컴퓨터공학과박사 1997 년 3 월 ~ 2002 년 2 월 : 성심외국어대학교수 2002 년 3 월 ~ 현재 : 영산대학교공과대학사이버경찰학과교수 < 관심분야 > 이동통신망라우팅기술, VAET 통신기술, 센서네트워크라우팅기술 1987 년 2 월 : 경북대학교전자공학과학사 1989 년 2 월 : 경북대학교전자공학과석사 2005 년 8 월 : 경북대학교컴퓨터공학과박사 1994 년 2 월 ~ 2001 년 2 월 : 김천대학컴퓨터정보계열조교수 2002 년 3 월 ~ 현재 : 영남이공대학모바일인터넷과부교수 < 관심분야 > Mobile IPv6, 마이크로이동성, 핸드오버제어기술 2349