논문 08-33-01-?? 한국통신학회논문지 '08-01 Vol. 33 No. 1 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 정회원김대영 *, 조진성 * A Method to Support Mobile Sink Node in a Hierarchical Routing Protocol of Wireless Sensor Networks Dae-Young Kim*, Jinsung Cho* Regular Members 요 약 센서네트워크는수많은센서노드로구성되어있으며, 주변환경을감시하는용도로사용된다. 현재까지수행되어온센서네트워크에대한연구는대부분고정된상태의싱크노드를고려하고있기때문에, 싱크노드의이동성을바탕으로한유비쿼터스응용에서는센서필드에서수집된데이터가이동싱크노드까지끊김없이전송되는데어려움이존재한다. 센서데이터가손실되지않고이동싱크노드에전달되기위해서는라우팅경로가싱크노드의이동에따라갱신되어야하는데, 본논문에서는센서네트워크의계층적멀티홉라우팅프로토콜에서이동싱크노드로향한라우팅경로가손실되지않고계속해서갱신되도록하는방안을제안한다. 컴퓨터시뮬레이션을통해제안한방안의우수성을검증하였으며, 위치기반라우팅프로토콜을사용하여이동싱크노드로향한경로를갱신하는기존방법과성능을비교하여제안된방안이기존방안보다우수함을보였다. Key Words : Wireless sensor networks, Hierarchical routing protocol, Mobile sink node ABSTRACT Wireless sensor networks are composed of a lot of sensor nodes and they are used to monitor environments. Since many studies on wireless sensor networks have considered a stationary sink node, they cannot provide fully ubiquitous applications based on a mobile sink node. In those applications, routing paths for a mobile sink node should be updated while a sink node moves in order to deliver sensor data without data loss. In this paper, we propose a method to continuously update routing paths for a mobile sink node which can be extended on hierarchical multi-hop routing protocols in wireless sensor networks. The efficiency of the proposed scheme has been validated through comparing existing method using a location based routing protocol by extensive computer simulation. Ⅰ. 서론 무선센서네트워크의센서노드들은제한된컴퓨팅리소스와충분하지못한에너지를가지고있 기때문에, 무선센서네트워크시스템을설계하기위해서는에너지효율적인특성이반드시고려되어야한다. 특히센서네트워크에서 RF 통신은센서노드에서소비되는전체에너지중에서가장큰비 이논문은 2005 년도정부 ( 교육인적자원부 ) 의재원으로한국학술진흥재단의지원을받아수행된연구임 (KRF-2005-003-D00205) * 경희대학교컴퓨터공학과모바일및임베디드시스템연구실 ({kimdy,chojs}@khu.ac.kr) 논문번호 :KICS2007-11-495, 접수일자 :2007 년 11 월 8 일, 최종논문접수일자 : 2007 년 12 월 10 일 48
논문 / 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 율을차지하고있기때문에에너지효율적인라우팅프로토콜이필요하다. 현재무선센서네트워크를위한많은라우팅프로토콜들이제안되어있으며, 이라우팅프로토콜들은계층적라우팅프로토콜, 평면기반라우팅프로토콜, 그리고위치기반라우팅프로토콜로분류된다 [1]. 평면기반라우팅프로토콜과위치기반라우팅프로토콜은데이터중심적인특성에기반으로하는라우팅기법을사용하며전체네트워크로부터데이터를수집하고자할경우에는데이터전송에참여하는센서노드의수를증가시켜많은에너지소비를유발하므로적합하지않다. 반면에계층적라우팅프로토콜은클러스터를구성하고각클러스터의대표노드인클러스터헤드에서클러스터내부로부터수집된정보를통합하여싱크노드로전달한다. 이러한계층적라우팅프로토콜은싱크노드로의데이터전송에비교적적은수의센서노드들필요로하기때문에일반적으로다른두프로토콜보다에너지효율적이다 [2,3]. 그러나이러한센서네트워크의라우팅프로토콜은고정된싱크노드를가진정적인환경만을고려하고있기때문에이동성이강조되는유비쿼터스환경의다양한응용을제공할수없다. 비록 MANET(Mobile Ad-hoc Network) 에서는개별노드의이동을고려하는라우팅프로토콜이있지만 [4], 센서네트워크가 MANET과다른특성을가지고있기때문에이들은무선센서네트워크에적합하지않다 [5]. 무선센서노드는제한된컴퓨팅리소스와에너지를가지기때문에 MANET처럼센서노드스스로이동성을가질수없다. 하지만, 센서노드보다좀더많은컴퓨팅자원과에너지를가지고있고기지국 (Base Station) 의역할을수행하는싱크노드라면이동성을고려할수있으며, 무선센서네트워크의라우팅프로토콜이이동싱크노드를지원하면다양한유비쿼터스서비스가가능하게된다. 현재이동싱크노드지원을위한몇가지방안들이존재하지만, 위치기반프로토콜에의존하는방안들은센서노드의위치인식을위한에너지소모가많고센싱정보의수집면적이커질수록데이터전송에많은에너지를소비하게되며, 노드의위치정보에의존하지않는방안은싱크노드가정지된상태에서싱크노드로의데이터전송이가능하기때문에다양한서비스의제공에어려움이따른다. 본논문에서는계층적멀티홉라우팅프로토콜에적용할수있는이동싱크노드지원기법을제시하며컴퓨터시뮬레이션을통해이에대한성능을검증 한다. 일반적으로센서네트워크의계층적라우팅프로토콜은클러스터링과데이터전송을위해단일홉전송을사용한다. 따라서센서네트워크의계층적라우팅프로토콜을현실환경에적용하기위해서는반드시멀티홉전송방안이존재해야한다. 센서노드가멀티홉전송을수행하기위해서는홉수와같은정보를이용하여라우팅테이블을구성해야하고각센서노드는이라우팅테이블을사용하여클러스터헤드또는싱크노드로멀티홉을통해데이터를전송할수있다. 이렇게멀티홉전송이가능한계층적라우팅프로토콜을위해제안된이동싱크노드지원기법은 GPS 정보를사용하지않고싱크노드가이웃노드에대한테이블을유지하여이동하면서이웃노드의라우팅테이블을갱신하도록메시지를보냄으로써싱크노드가이동하는동안싱크노드를향한경로를유지하도록한다. 본논문의구성은다음과같다. Ⅱ절에서는관련연구로서무선센서네트워크에서의이동성지원기법에대한내용을기술하고, Ⅲ절에서는센서네트워크의계층적멀티홉라우팅프로토콜을간략히소개한후, Ⅳ절에서이러한계층적멀티홉라우팅프로토콜에적용시킬수있는싱크노드의이동성지원방안을설명한다. Ⅴ절에서는성능평가를보이고, 마지막 Ⅵ절에서본논문의결론을맺는다. Ⅱ. 관련연구현재무선센서네트워크의라우팅프로토콜들은정적인네트워크환경을고려하고있으며, 일부의 GPS 정보를이용하는라우팅프로토콜과제약된환경에서동작하는 GPS-less 라우팅프로토콜들이이동싱크노드를지원하기위한방안을제공한다. GPS 정보를이용하지않는프로토콜에는 MobiRoute가있다 [6]. MobiRoute는싱크노드의이동이멈추었을때토폴로지컨트롤메시지를브로드캐스트함으로써네트워크의모든노드가변경된싱크노드의위치로데이터를전송할수있도록라우팅테이블을변경한다. 이때전체토폴로지의변경을위해많은시간이필요하며많은데이터들은부분적으로최적화된경로를이용하게된다. 또한싱크노드가이동하는동안싱크노드주변의노드들이싱크노드로전송되는데이터를버퍼링하여데이터손실을방지한다. 그러나이러한방법은센서노드의데이터전송률이아주작다는가정아래 49
한국통신학회논문지 '08-01 Vol. 33 No. 1 에서가능하며실제센서노드는제한된버퍼크기를가지기때문에유비쿼터스센서네트워크의다양한응용분야에적용하는데어려움이있다. TTDD(Two-tier Data Dissemination Model) 는각각의데이터소스가격자 (grid) 를구축한다. 그후싱크노드는자신이속해있는격자내부에질의 (query) 를플러딩 (flooding) 하여가장가까운격자의교차점 (dissemination 노드 ) 에자신의정보를등록한다 [7]. 이렇게함으로써소스노드와싱크노드사이의연결 (connection) 은유지되고, 싱크노드는이동하더라도데이터를계속수신할수있다. TTDD는 GPSR(Greedy Perimeter Stateless Routing) 프로토콜 [8] 을기반으로하여이동중인싱크노드로데이터를전달하며이때격자의교차점을경유하여목적지로향한다. TTDD는소스노드가격자를구축하는데오버헤드가발생하기때문에단일소스노드가아닌경우에는사용하기힘들다. 또다른라우팅프로토콜로이동싱크노드를위한비동기적데이터전송을다루는 SEAD(Scalable Energy-efficient Asynchronous Dissemination protocol) 가있다 [9,10]. SEAD에서는싱크노드가소스노드로질의를보내기위해이웃노드중하나를액세스노드로선택한다. 이액세스노드가싱크노드의이동을추적한다. 만약싱크노드가액세스노드로부터멀리떨어지게되면싱크노드는이동한위치의이웃노드중하나를새로운액세스노드로선정한다. SEAD는별도의격자를구성할필요가없기때문에 TTDD 보다우수한성능을보인다 [9]. 그러나 TTDD와 SEAD는데이터전송을위해사용되는라우팅프로토콜로 GPSR을사용한다. 대표적인위치기반프로토콜인 GPSR은센서노드의위치인식을위하여에너지소모가많은 GPS 장치를사용한다. 비록 Bulusu et al. [11] 처럼 GPS 장치없이도노드의위치를예측하는방안들이존재하지만, GPSR은라우팅경로로써목적지와가장가까운좌표를가진이웃노드를선택해야하기때문에노드의위치를정확히알아야한다. 따라서 TTDD 와 SEAD는 GPS 장치를사용하지않는다른라우팅프로토콜과비교하였을때네트워크생존시간에대한성능을보장할수없게된다. 네트워크생존시간측면에서는무선센서네트워크의라우팅프로토콜중에서적은데이터전송으로통신비용을줄인계층적라우팅알고리즘을사용하는프로토콜들이보다효율적이며 [2,3], 대표적인계층적라우팅프로토콜로는 LEACH(Low-Energy Adaptive Clustering Hierarchy) [12] 가있다. 계층적라우팅프로토콜들은주기적으로클러스터를재구성하고라우팅테이블을갱신하는것에의해서부분적으로는싱크노드가이동하더라도프로토콜이이동성을지원하게되지만, 현존하는계층적라우팅프로토콜의이러한점이싱크노드에대한완전한이동성제공하는것은아니다. 싱크노드가이동하고나면싱크노드가다시 interest 메시지를플러딩하기전까지는라우팅경로가변경되지않아싱크노드까지의데이터전송은불가능하게된다. 이러한계층적라우팅프로토콜에이동성을지원하고자하는여러가지방안들이있다. Liu et al. [13] 은 LEACH 프로토콜을사용하는센서노드들이 GPS 모듈을탑재하고있어서센서노드가이동하더라도위치정보를이용하여최단거리에있는클러스터헤드에멤버노드로참여한다. 그러나클러스터구축을위해제한된자원을가진센서노드가 GPS 모듈을사용하는방안은적합하지않다. 또한 Yang et al. [14] 는여러개의셀을만들고각셀의경계를라우팅경로로설정한다. 노드가이동할때, 단지이동하는노드의인접셀이재구성되고라우팅경로는변경된다. 이때각노드는셀내부의모든노드들에대한위치와전송지연시간의정보를알고있어야한다. 현재까지무선센서네트워크에서이동싱크노드를지원하는방법들은앞에서언급한것처럼위치기반프로토콜을사용하는경우, 정보수집의범위가커질수록센서노드들의에너지소모는더커지게되고센서데이터수집에따른전송지연시간도더길어지게된다. 그렇지않은경우는이동중인싱크노드가정지한상태에서싱크노드로의데이터전송이가능하다. 한편, 무선센서네트워크의계층적라우팅프로토콜은평면기반라우팅프로토콜보다에너지측면에서효율적이지만이동싱크노드를지원할수없기때문에싱크노드에전달되는데이터손실이자주발생한다. 따라서본논문에서는멀티홉전송을기반으로하는계층적라우팅프로토콜에서싱크노드의이동에따른데이터손실률을최소화하는방안을제안한다. Ⅲ. 계층적멀티홉라우팅프로토콜 무선센서네트워크의계층적라우팅프로토콜들의동작은클러스터링단계와데이터통신단계로구분되며, 데이터통신단계는다시클러스터의멤 50
논문 / 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 그림 1. 계층적멀티홉라우팅버노드와클러스터헤드그리고클러스터헤드와싱크노드가직접통신하는형태로데이터전송이이루어진다. 그러나 IEEE 802.15.4를기반으로하는무선센서노드는짧은데이터전송거리 (POS 1) ) 를가지고있으며극히제한된에너지를포함하고있기때문에이러한현실적인상황에서직접통신에의해서는원거리의싱크노드까지데이터를전송할수없게된다. 따라서계층적라우팅프로토콜은원거리의목적지까지멀티홉통신에의한데이터전송이가능해야한다. 그림 1은계층적멀티홉라우팅프로토콜에서의데이터통신을보여준다. 점선으로나타난클러스터내부의통신과실선으로나타난클러스터헤드와싱크노드사이의통신은모두멀티홉라우팅에의해이루어진다. 한편, 몇개의클러스터들이단일홉클러스터를구성하게되면모든클러스터가센서필드를포함하기위해서센서노드의데이터전송거리가길어져야하지만, 현실적인환경에서센서노드는 POS 를가지기때문에클러스터들이센서필드를포함하기위해설정된클러스터의수보다더많은수의클러스터가형성되는문제점이발생할수있다. 이는클러스터헤드에서싱크노드로의데이터전송에많은노드를참여시키기때문에전체네트워크에서의에너지소비를가중시킨다. HSHR(Hierarchical Shortest Hop Routing) [3] 은노드의잔존에너지와연결도를이용한분산적인방법에의해클러스터헤드를효율적으로선택하며, 주어진클러스터헤드의비율을유지하기위해클러스터의범위를확장함으로써적절한수의클러스 1) POS: Personal Operating Space, 전방향최대 10m, IEEE 802.15.4는 POS에초점을맞추고있다. 터를구성하여싱크노드로의데이터전송에참여하는클러스터헤드의수를효율적으로관리할수있다. 그리고홉수와노드의잔류에너지를이용한라우팅테이블을구성하여멀티홉라우팅을수행하기때문에클러스터내부의멤버노드와클러스터헤드사이와클러스터외부의클러스터헤드와싱크노드사이가 POS 이상의거리에위치하더라도중계노드를이용하여데이터를전송할수있다. 그러나대표적인계층적라우팅프로토콜인 LEACH [12] 는확률을기반으로한분산적인방법에의해서클러스터를구성하고각클러스터헤드가수집한데이터를싱크노드로전송하지만, POS 환경에서클러스터헤드가싱크노드까지데이터를전송하기위해서 LEACH의클러스터링부분을제외한데이터통신부분을멀티홉전송이가능하도록수정하여야한다. 본논문에서는이를 LEACH2 로정의한다. LEACH2는싱크노드에서플러딩되는 interest 메시지가전달되는홉수를이용하여라우팅테이블을구성하고이테이블을사용하여멀티홉통신을수행하게된다. Ⅳ절에서소개될이동싱크노드지원방안은 HSHR이나 LEACH2처럼라우팅테이블을기반으로한계층적멀티홉라우팅프로토콜에적용가능하도록설계된다. Ⅳ. 이동싱크노드지원방안고정된싱크노드를고려한계층적라우팅프로토콜들은현실적인환경에서전통적인센서네트워크서비스만가능하기때문에다양한센서네트워크서비스를위해서이동싱크노드를지원하기위한방안이필요하다. 이를위해라우팅프로토콜은싱크노드의이동에의해링크가단절되는것과같은데이터전송경로의변화에대응할수있어야한다. 본논문에서는라우팅테이블을기반으로하는계층적멀티홉라우팅프로토콜에이동성지원모듈 (mobility module) 을탑재하여이동싱크노드를지원하기위한센서네트워크의프레임워크를제안한다. 네트워크필드에서클러스터가구축된후클러스터헤드에서수집한데이터는싱크노드에이웃하는센서노드 (neighbor) 를경유하여싱크노드로전달된다. 클러스터헤드에서싱크노드로의데이터전송이동성지원모듈이제공되지않으면클러스터헤드로부터의데이터는이웃노드까지전달될뿐이동중인싱크노드로완전하게전달되지 51
한국통신학회논문지 '08-01 Vol. 33 No. 1 그림 2. 이동성지원모듈을탑재한계층적센서네트워크프레임워크 그림 3. 이동싱크노드의 SNT 못한다. 이동성지원모듈에서는그림 2처럼싱크노드에서이웃노드테이블 (SNT: Sink-Neighbors Table) 을관리함으로써싱크노드가이동할때마다컨트롤 (CTRL) 메시지를통해서이웃노드에서싱크노드로향하는경로를갱신하여클러스터헤드에서전송되는데이터가전송과정에서손실되지않고싱크노드로전달될수있도록한다. 여기서 SNT는싱크노드가이웃노드에대한식별을위해사용하는테이블로센서노드의라우팅테이블과는다르다. 싱크노드가관리하는 SNT의동작은그림 3에서자세히설명된다. 이동싱크노드를향한라우팅경로를유지하기위해서, 싱크노드는가장먼저현재자신의이웃노드를탐색하여 SNT에등록하고다른곳으로이동하기전에탐색된이웃노드를 O(Original) 타입으로설정한다. 그후싱크노드가이동하면서주기적으로이웃노드를탐색하여새로발견되어 SNT에추가된노드를 N(New) 타입으로설정한다. 이때중복탐색된노드는 D(Duplicate) 타입으로설정한다. SNT의갱신이완료되고나면, 싱크노드는현재이웃노드의라우팅경로를갱신하기위해서 CTRL 메시지를발송한다. 이메시지는 D와 N타입의이웃노드에게전달되며, O타입노드의식별자를포함하기때문에이메시지를수신한 D타입노드는 O타입노드에이메시지를전달하여라우팅테이블이갱신되도록한다. 예를들면, 그림 3의가운데그림의경우, 노드 3, 4, 5는싱크노드로부터질의메시지를수신하게된다. N 타입노드인노드 5는라우팅테이블에싱크노드를추가하고, D타입노드 3과 4는자신의라우팅테이블에있는 O타입노드에게질의메시지를포워 딩한다. 노드 3으로부터질의메시지를전달받은노드 1은라우팅테이블에있는노드 3의홉수를 2로설정하고나머지노드들의홉수를 1증가시킨다. 노드 4로부터질의메시지를전달받은노드 2도같은방법으로라우팅테이블을갱신한다. 싱크노드에서질의메시지의전송이끝난후, SNT에서 O타입의노드는제거되고 D와 N타입의노드는 O타입으로재설정된다. 만약싱크노드가이동한후 D타입의노드가 SNT에존재하지않으면, 이전의 O타입노드에질의메시지가전달될수있도록하기위해서 N타입의노드는이메시지를 k홉까지지역적플러딩을수행한다. k는임의로설정될수있으며, k가증가하면싱크노드가빠르게이동하더라도싱크노드로의데이터전송이가능하지만질의메시지플러딩에대한오버헤드가발생한다. 일반적으로싱크노드를추적하는방안에서는싱크노드가이동할수록라우팅경로가길어짐으로써비효율적인데이터라우팅이발생한다. 따라서주기적으로전체센서노드의라우팅테이블에대한갱신이필요한데, SEAD는일정홉이상이동할때마다새로운액세스노드를선정하고라우팅테이블갱신을위한메시지를브로드캐스트한다. 제안된방안은 SNT에변화가있다면 SEAD와비슷하게이동싱크노드가일정시간마다라우팅테이블갱신을위한메시지를브로드캐스트함으로써라우팅경로가비효율적으로길어지는것을피할수있다. 그림 4는이동성지원모듈의의사코드를보여준다. 롱텀 (LT: Long-Term) 타이머를사용하여네트워크전체에대한라우팅테이블갱신이이루어지고, 52
논문 / 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 1: If LT timer is not expired 2: If ST timer is expired 3: If Movement of sink node is detected 4: Update SNT 5: Send CTRL message 6: Compensate SNT 7: Else 8: Keep current status 9: Else 10: flood CTRL message 그림 4. 이동성지원모듈의의사코드숏텀 (ST: Short-Term) 타이머를사용하여주기적으로싱크노드가이동하는지검사한다. 이동이발생하면그림 3처럼 4, 5, 6번줄의동작이수행되고그렇지않으면 8번줄처럼현재상태를유지하게된다. 이렇게제안된방안으로부터, 클러스터가재구성되기전에싱크노드가이동하더라도싱크노드의 SNT를이용하여이웃노드의라우팅경로를갱신하는것에의해서싱크노드를추적할수있고따라서싱크노드로끊김없는데이터전송이가능해진다. 또한, 제안된방안은싱크노드의 SNT와싱크노드의이웃노드에서작용하기때문에모든테이블기반의계층적멀티홉라우팅프로토콜에서쉽게적용할수있다. 실제로 HSHR과 LEACH2에서라우팅테이블갱신을위한 CTRL메시지의내용만차이가날뿐, 이동성지원모듈의그외다른부분은모두동일하게적용된다. Ⅴ. 성능분석 Ⅳ절에서제안된방안은 GPS를사용하지않는무선센서네트워크의계층적멀티홉라우팅프로토콜에서이동중인싱크노드로향하는패킷의손실을줄이기위해고안되었다. 이절에서는 HSHR [3], LEACH [12], SEAD [9,10] 와의컴퓨터시뮬레이션결과의비교를통해서성능분석을수행한다. 시뮬레이션은싱크노드가주기적으로보내는 interest 메시지를수신한센서노드들이데이터전송프레임에따라수집한정보를싱크노드에전송하는구조로이루어지며계층적멀티홉라우팅프로토콜에서의클러스터는 interest 메시지가수신될때마다구축된다. 컴퓨터시뮬레이션을위해서 C++ 를 이용하여시뮬레이션프로그램을제작하고 5.1절의시뮬레이션환경아래에서시뮬레이션을하였다. 4.1 시뮬레이션환경 100m x 100m의사각형네트워크필드에 300개의센서노드를랜덤하게분포시켰으며, 0m/s, 2m/s, 5m/s, 8m/s 그리고 10m/s의이동속도를가진싱크노드는센서필드의중앙에서부터설정된이동속도로센서필드내부에서랜덤한방향으로이동한다. 센싱정보는전체센서필드에서발생되는글로벌상태정보 (global state information) 로가정하였으며, 모든센서노드는초기에너지로 10Joule을가진다. 계층적라우팅프로토콜에서클러스터헤드선정을위한확률 p는 LEACH [12] 에서사용한것처럼 0.05로, HSHR의클러스터확장범위 d는 HSHR [3] 에의해계산되는 4홉으로설정하였다. 또한싱크노드로부터의 interest 메시지는평균이 5초인포아송 (Poisson) 분포를따르고, interest 메시지를수신한후계층적라우팅프로토콜에서의데이터전송은 4개의데이터전송프레임으로이루어지며비교적긴데이터전송시간을가진평면라우팅프로토콜에서는 2개의데이터전송프레임을사용하여데이터전송이이루어지도록하였다. 센서노드의에너지소비를나타내기위해서무선채널로써식 (1), (2) 와같은 LEACH [12] 의전파모델을사용하였으며무선채널에서발생하는에러는고려하지않았다 E TX(n,l)=E elec n+ε amp n l 2 (1) E RX(n)=E elec n. (2) nbits 메시지와거리 l이주어지면, 전파는이메시지를전송하기위해서송신노드에서식 (1) 과같이에너지를소비하고, 이메시지를수신한노드에서는식 (2) 와같이에너지를소비한다. 여기서 E elec 는신호의디지털코딩, 변조, 필터링을위해서전자회로에서소비되는에너지이고 ε amp 는송신기의증폭기를위한상수값이다. 표 1은에너지소비모델을위해본논문에서사용한시뮬레이션매개변수들을나타낸다. 성능분석을위해서, 클러스터헤드에서싱크노드로직접전송에의해데이터를전송하는 LEACH 를대신하여 Ⅲ절에서언급했던것처럼멀티홉전송이가능하도록수정한 LEACH2를사용한다. 또 53
한국통신학회논문지 '08-01 Vol. 33 No. 1 표 1. 성능분석을위한환경변수 Parameters Value Network size 100m x 100m Data packet size 100 bytes Query packet size 25 bytes Packet header size 25 bytes E elec 50 nj/bit ε amp 10 pj/bit/m2 E init 10 J # of nodes 300 p 0.05 d 4 Energy consumption for GPS No consideration 한위치기반라우팅알고리즘을사용하는 SEAD에서는글로벌상태정보를수집하는경우많은에너지소비가예상되기때문에데이터라우팅에필요한 GPS 정보를수신하기위한에너지소모는고려하지않는다. 4.2 시뮬레이션결과본논문은싱크노드가이동하는환경의무선센서네트워크에서끊김없이싱크노드로데이터가전송되는것을목적으로하고있기때문에성능측정기준 (metrics) 으로싱크노드에서수집된데이터패킷의수, 패킷손실률, 소비된에너지평균그리고평균전송지연시간을사용하였으며, 제안된싱크노드의이동성지원방안을적용한 mleach2 (mobile LEACH2) 와 mhshr(mobile HSHR), 적용하지않은 LEACH2와 HSHR, 그리고 SEAD의시뮬레이션결과로성능비교를수행하였다. LEACH2와 HSHR에서소비되는에너지는클러스터내부에서소비되는에너지와클러스터외부에서소비되는에너지로구분되며식 (3), (4) 와같이나타낼수있고, SEAD에서는클러스터없이개별노드가싱크노드와통신하므로소비에너지는식 (5) 처럼표현할수있다 E HSHR=n p t+(1-p) n d (3) E LEACH2=(n p+α) t+(1-p) n-α (4) E SEAD=n t. (5) 여기서 n은전체노드의수, t는싱크노드까지의평균홉수, d는 HSHR에서클러스터의범위에대한 홉수, p는클러스터헤드의비율이며, α는 LEACH2 에서 np만큼의클러스터헤드가결정된이후, 클러스터범위에들어가지못한센서노드들에의해재결성되는클러스터헤드의수를나타낸다. p=0.05, t=8, d=4이면, n α 이므로네트워크에서의소비에너지는 E LEACH2<E HSHR<E SEAD 로예측할수있다. 그림 5는네트워크필드에서센서노드가싱크노드로수집된데이터를전송하는데소비되는평균에너지를나타내며에너지소비의예측결과와시뮬레이션결과가일치함을확인할수있다. 클러스터기반의계층적라우팅프로토콜인 mleach2와 mhshr이평면기반라우팅프로토콜을사용하는 SEAD 보다훨씬적은에너지를소모함을볼수있다. 계층적라우팅프로토콜은클러스터링에의해데이터전송에참여하는노드가줄어들기때문에글로벌상태정보를수집하는경우에너지측면에서높은효율을나타낸다. mleach2와 mhshr 사이에서 mhshr의에너지소모가조금더큰이유는클러스터를확장하면서발생하는메시지전송과확장된범위에서의데이터전송에의한것이다. SEAD는라우팅프로토콜로써위치기반의 GPSR을사용하는데, GPSR은 GPS 정보를이용하여데이터를라우팅하는데, 일반적으로센서노드에장착될수있는작은 GPS 모듈은위치정보수신시 65mA 의전류를소비하며 [15], 센서노드의 RF 모듈은데이터수신시 19.7mA의전류를소비한다 [16]. 즉, 센서노드에서 GPS 정보수신시 RF 데이터수신하는경우보다약 3배정도의더많은에너지소비가발생하게된다. 시뮬레이션에서는이러한 GPS 수신시발생하는에너지를고려하지않았음에도 SEAD의평균소비에너지가높게나타났다. 만약 SEAD에 GPS 수신에너지를더하게되면그림 5 에서보여주는소비에너지보다더큰에너지를소모하게된다. 그림 6은평균데이터전송지연시간을보여준다. 데이터전송지연시간은싱크노드와의데이터통신과관련이있으며식 (3), (4), (5) 를통해서싱크노드와의데이터통신에참여하는노드수를예측할수있다. HSHR에서는 np개, LEACH2에서는 np+α개, SEAD에서는 n개의노드가데이터전송에참여한다. SEAD는싱크노드를향한데이터전송을위해많은센서노드를전송에참여시키기때문에긴전송지연시간이발생하고그림 5처럼많은에너지가사용된다. mhshr은클러스터를확장하는것으로써클러스터의수를적절하게유지하기 54
논문 / 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 그림 5. 평균소비에너지 그림 6. 평균전송지연시간 그림 7. 패킷손실률때문에싱크노드로데이터를전송해야하는클러스터헤드의수는 mleach2보다적다. 따라서 mhshr에서는클러스터헤드에서싱크노드로의전송횟수가줄어들기때문에전체전송지연이 mleach2보다줄어든다. 그림 7은싱크노드의이동속도에따른패킷손실률을나타낸다. 싱크노드가이동하더라도끊김없는서비스를제공하기위해서는낮은패킷손실률을유지해야한다. 싱크노드의이동성을지원하기위한방안을적용한 mleach2와 mhshr에서는이동성을지원하지않는 LEACH2와 HSHR보다패킷손실률이크게줄어들었으며 mhshr은 SEAD 보다낮은패킷손실률을제공하였다. 특히 SEAD 의경우싱크노드가이동하지않으면싱크노드의주변의노드에데이터트래픽이집중되면서빠른에너지소비로인해싱크노드와연결되는노드들 그림 8. 수집된데이터양의기능이정지하게되고, 이로인해데이터패킷의손실이발생하게된다. 0m/s에서 SEAD의패킷손실률이높은것은이러한이유에서비롯된다. 또한제안된이동성지원방안은 HSHR외에도 LEACH2 와같이다른계층적멀티홉라우팅프로토콜에적용시킬수있지만, HSHR에서가장좋은성능을보였다. 그림 8은싱크노드에서최종적으로수집된데이터패킷의수를나타낸다. 평면기반의프로토콜을사용하는 SEAD는긴전송지연시간으로인해싱크노드가수집하는데이터의양이아주적다. 그러나계층적멀티홉라우팅프로토콜인 mleach2와 mhshr을사용하는경우싱크노드는 SEAD보다많은데이터를수집하였으며, mleach2와 mhshr 중에서는 mhshr이더많은데이터를수집하였다. 55
한국통신학회논문지 '08-01 Vol. 33 No. 1 이렇게이동싱크노드를지원하기위한기존방안인 SEAD는낮은패킷손실률을제공하여끊김없는서비스가가능하지만평면라우팅기반이기때문에에너지소비, 전송지연시간, 수집된데이터패킷수에서한계를드러낸다. 그러나계층적멀티홉라우팅프로토콜에적용한제안된방안은낮은소비에너지와짧은전송지연시간을가지면서많은데이터를수집할수있음에도 SEAD보다낮은패킷손실률을제공할수있다. Ⅵ. 결론무선센서네트워크의계층적라우팅프로토콜들이일반적으로많은장점을가지고있지만, 데이터전송에대한비현실적인가정으로인해실제환경에적용하는데문제가있다. 또한이동성을고려하지않고있기때문에센서네트워크의다양한응용분야를제공하지못하였다. 본논문은짧은데이터전송거리를가지는노드들로구성된센서네트워크에서요구되는현실적인계층적멀티홉라우팅프로토콜에서이동싱크노드를추적하는방안을제시하고, 클러스터헤드와싱크노드사이에끊김없는통신서비스가가능함을시뮬레이션을통해검증하였다. 본논문에서제안한이동싱크노드지원방안을탑재한계층적멀티홉라우팅프로토콜 (mleach2, mhshr) 은싱크노드의이동속도가증가하더라도패킷손실률을줄일수있었으며, 평균소비에너지, 평균전송지연시간. 수집된데이터의양에대한측면에서 SEAD보다우수한성능을보였다. 특히 mhshr은 SEAD와비슷하거나보다낮은패킷손실률을제공하였고, 가장많은양의데이터수집이가능함을보여주었으며, 평균소비에너지가 mleach2보다조금많음에도불구하고평균전송지연시간을 mleach2의 1/2로줄였다. 따라서향후계층적라우팅프로토콜을사용하는무선센서네트워크의다양한응용분야에본논문에서제안한이동싱크노드지원방안이적용될수있다. 참고문헌 [1] K. Akkaya and M. Younis, A Survey on Routing Protocols for Wireless Sensor Networks, Journal of Ad Hoc Networks, Vol.3, pp.325-349, 2005. [2] H. Karl, Protocols and architectures for wireless sensor networks, John Wiley & Sons, May 2005. [3] D. Y. Kim, J. Cho and B. S. Jeong, A Practical Algorithm for Clustering and Routing in Hierarchical Sensor Networks, submitted to IEICE Trans. on Communications, 2007. [4] http://www.ietf.org/html.charters/manet-charter. html [5] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, A Survey on Sensor Networks, IEEE Communications Magazine, Vol.40, pp.102-114, August 2002. [6] J. Luo, J. Panchard and M. Piorkowski, MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks, International Conference on Distributed Computing in Sensor Systems, pp.480-497, June 2006. [7] F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, A Two-tier Data Dissemination Model for Large-scale Wireless Sensor Networks, Proc. of International Conference on Mobile Computing and Networking, pp.148-159, September 2002. [8] B. Karp and H. Kung, Greedy Perimeter Stateless Routing, Proc. of International Conference on Mobile Computing and Networking, pp.243-254, August 2000. [9] H. S. Kim, T. F. Abdelzaher and W. H. Kwon, Minimum-Energy Asynchronous Dissemination to Mobile Sinks in Wireless Sensor Networks, Proc. of International Conference on Embedded Networked Sensor Systems, pp.193-204, November 2003. [10] S. Bhattacharya, H. Kim, S. Prabh and T. Abdelzaher, Energy-Conserving Data Placement and Asynchronous Multicast in Wireless Sensor Networks, Proc. of International Conference on Mobile Systems, Applications and Services, pp.173-185, May 2003. [11] N. Bulusu, J. Heidemann and D. Estrin, GPS-less Low-Cost Outdoor Localization for Very Small Devices, IEEE Personal 56
논문 / 무선센서네트워크를위한계층적라우팅프로토콜에서의이동싱크노드지원방안 Communications, Vol.7, No.5, pp.28-34, October 2000. [12] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proc. of the Annual Hawaii International Conference on System Sciences, pp.1-10, January 2000. [13] C. Liu, C. Lee and L. Wang, Power-Efficient Communication Algorithms for Wireless Mobile Sensor Networks, Proc. of International Workshop on Performance Evaluation of Wireless Ad hoc, Sensor and Ubiquitous Networks, pp.121-122, October 2004. [14] Y. Yang, D. Y. Lee, M. S. Park and H. P. In, Dynamic Enclose Cell Routing in Mobile Sensor Networks, Proc. of the 11th Asia-Pacific Software Engineering Conference, pp.736-737, December 2004. [15] Leadtek GPS 9546 Module Technical Specification : http://www.leadtek.com. [16] CC2420 Specification : http://focus.ti.com/ docs/prod/folders/print/cc2420.html. 김대영 (Dae-Young Kim) 정회원 2004년 2월경희대학교전자공학과졸업 2006년 2월경희대학교컴퓨터공학과 ( 석사 ) 2006년 3월~현재경희대학교컴퓨터공학과박사과정 < 관심분야 > 모바일네트워크, 센서네트워크, 임베디드시스템조진성 (Jinsung Cho) 정회원 1992년 2월서울대학교컴퓨터공학과졸업 1994년 2월서울대학교컴퓨터공학과 ( 석사 ) 2000년 2월서울대학교컴퓨터공학과 ( 박사 ) 1997년 4월 ~8월 IBM T.J. Watson Research Center Visiting Researcher 1999년 9월 ~2003년 2월삼성전자책임연구원 2003년 3월 ~ 현재경희대학교컴퓨터공학과조교수 < 관심분야 > 모바일네트워크, 센서네트워크, 임베디드시스템 57