논문 09-34-02-06 한국통신학회논문지 '09-02 Vol. 34 No. 2 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 준회원이치영 *, 정회원이신형 *, 종신회원유혁 * Mobile PULSE : A Routing Protocol Considering the Power and the Route Recovery Time in Sensor Networks with A Mobile Sink Node Chi-Young Lee* Associate Member, Shin-Hyoung Lee* Regular Member, Chuck Yoo* Lifelong Member 요 약 PULSE 프로토콜은센서노드의슬립을통해소모전력량을크게줄인다. 그러나이프로토콜은싱크노드의이동을고려하지않는문제가있다. 모바일싱크노드를가진센서네트워크를위한라우팅프로토콜은빠른경로복구와전력소모최소화를모두달성해야한다. 본논문은두목적을달성하기위해모바일 PULSE 프로토콜을제안한다. 또한, 실험을통해제안한프로토콜의경로복구능력과전력소모량을확인하였다. 이프로토콜은기존의 PULSE 프로토콜에비해약 40% 정도경로복구시간을단축하였고, 드롭되는패킷의양도약 1/2 수준으로줄였다. 전력소모량면에서는최대 0.8% 의증가만이나타남으로써, 기존의 PULSE 프토토콜의전력효율적인특징을그대로유지함을보였다. 본논문은모바일 PULSE 프로토콜의경로복구능력과전력소모량을확인함으로써모바일센서네트워크에적합한프로토콜로서의가능성을보여준다. Key Words : Mobile Sink, Routing Protocol, Sensor Networks, Power Saving, Route Recovery ABSTRACT The PULSE protocol can greatly reduce power consumption using a node's sleep state. But this protocol does not consider movement of a sink node in a sensor network. In the mobile sensor network, a routing protocol must recover path error by movement of a sink node as quickly as passible. Therefore we have to achieve fast path recovery and power saving to support movement of a sink node in a sensor network. This paper proposes the Mobile PULSE protocol which is a improved routing protocol for a mobile sink node. And we evaluate Mobile PULSE and show that the Mobile PULSE reduces the recovery time about 40% compared with original PULSE protocol. Mobile PULSE increases energy consumption than PULSE as a maximum of 0.8%, which means Mobile PULSE is similar to PULSE in energy consumption. This paper shows mobile PULSE's capability in the mobile sensor network through evaluation of path recovery time and power consumption. 이연구에참여한연구자는 2 단계 BK21 사업 의지원을받아연구를수행함. * 고려대학교컴퓨터학과운영체제연구실 ( {cylee, shlee, hxy}@os.korea.ac.kr ) 논문번호 :KICS2008-11-500, 접수일자 :2008 년 11 월 11 일, 최종논문접수일자 : 2009 년 2 월 10 일 151
한국통신학회논문지 '09-02 Vol. 34 No. 2 Ⅰ. 서론센서네트워크를구성하는각센서노드는일반네트워크에서의노드들과달리매우제한된전력을갖는다. 그러므로 PULSE [1], SMAC [2], STEM [2], PAMAS [3] 등과같은전력소모를최소화하는프로토콜에대한많은연구가있어왔다 [4]. 특히 PULSE 프로토콜은일부노드를절전모드로전환함으로써전력소모를크게줄일수있다. 그러나이프로토콜은모든노드가고정된위치에있고, 노드의전력부족으로인한토폴로지변화만을고려한다. 따라서노드가이동하는네트워크에는적합하지않다. 센서네트워크에서의노드이동은다양한서비스의제공으로이어진다. 다음은모바일싱크노드의이용예이다. 1) 병원에서센서네트워크와 PDA를이용하여언제어디서나환자의상태를체크할수있다. 2) 빌딩내에서화재가발생했을때건물관리자의위치와관계없이모바일장비를통해이를빠른시간내에인식할수있다. 3) 전쟁터에서부대는항상전선을따라이동하는중에적의위치등의정보를파악할수있다. 위와같은상황들은 PDA와같은모바일장비를이용하여이동중에센싱데이터를수집함으로써가능하다. 싱크노드의이동은라우팅경로의오류를발생시키고이로인해데이터손실이나타난다. 그러므로이런손실을최소화하기위해경로복구시간을줄이는방안이요구된다. 또한, 센서노드는한번설치되면전력공급이어렵기때문에각센서노드의전력소모를최소화해야한다. 그러므로싱크노드의이동을고려한센서네트워크는경로복구시간단축과전력소모량최소화의두목적을모두달성할수있어야한다. 이를위해전력소모를크게줄인기존의 PULSE 프로토콜을이용한다. PULSE 프로토콜은무선멀티- 홉인프라스트럭쳐엑세스네트워크 (Wireless Multi-hop Infrastructure Access Network) 을위한라우팅프로토콜 [5] 과무선애드- 혹네트워크 (Wireless Ad-hoc Network) 을위한라우팅프로토콜 [6] 로제안되었고, 이후센서네트워크을위한라우팅프로토콜로수정된버전이제안되었다 [1]. 본논문에서는순서대로인프라 PULSE(infra PULSE), 애드- 혹 PULSE(ad-hoc PULSE), 센서 PULSE(sensor PULSE) 로명명한다. 모든 PULSE 프로토콜은타이밍정보를이용해특정시간이되면모든노드가정해진행동을함으로써, 경로를생성하고유지한다. 이타이밍정보에 의해펄스패킷 (pulse packet) 이주기적으로전송된다. 이펄스패킷은새로운경로를생성하는데사용된다. 그러므로펄스패킷의전송주기를변화시켜경로생성주기를조절할수있다. 펄스패킷의전송주기가길어지면전송횟수가줄어들기때문에펄스패킷의브로드캐스트로인한전력소모는줄일수있다하지만펄스패킷전송횟수감소로경로의생성횟수가적어지므로경로복구에많은시간이걸린다. 즉, PULSE 프로토콜에서는전력소모량최소화와경로생성주기사이에는트레이드- 오프 (trade-off) 관계가성립한다. 그러므로본논문에서는싱크노드의이동을고려하여기존센서 PULSE를개선한다. 이를통해경로복구시간단축과전력소모량최소화라는두목표를모두달성하도록한다. 이논문의구성은다음과같다. Ⅱ장에서는기존센서 PULSE 프로토콜에서의소모전력감소방법을설명하고, Ⅲ장에서는싱크노드의이동을고려하여 PULSE 프로토콜을개선한모바일 PULSE (Mobile PULSE) 프로토콜을제안한다. Ⅳ장에서는 NS2를이용한실험을통해모바일 PULSE 프로토콜이기존 PULSE 와비교했을때전력감소와경로복구시간단축을모두달성했음을보인다. Ⅴ장에서는센서네트워크에서노드의이동을고려한연구들을소개한다. 마지막으로 Ⅵ장에서는결론을기술하며본논문을마무리한다. Ⅱ. 센서네트워크를위한 PULSE 프로토콜 : 전력소모량의감소센서 PULSE 프로토콜 [1] 은전력효율적인라우팅프로토콜로, 라우팅경로에포함되지않는노드를슬립 (sleep) 상태로전환함으로써전력소모를줄인다. 센서 PULSE 프로토콜은고정된펄스간격 (Pulse Interval) 으로펄스패킷을전송한다. 이펄스패킷은싱크노드에서생성되고네트워크전체로브로드캐스트된다. 이주기적인펄스패킷의전송은라우팅정보의갱신과전체네트워크의시간동기화를제공한다. 네트워크내의각노드는수신한펄스패킷을기억함으로써싱크노드를향한경로를생성한다. 중복된펄스패킷이수신되었을경우, 가장작은홉수 (hop count) 를가진펄스패킷을기억하여최선의경로를선택하게된다. 만약펄스패킷을수신한노드가전송하고자하는패킷이있다면, 수신한펄스패킷에대한응답으로싱크노드를향해예약패킷 (reservation packet) 을전송한다. 예약패킷은자신을 152
논문 / 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 알고리즘 1 PULSE 프로토콜의타이머핸들러 Algorithm 1 The Timer handler of PULSE protocol /* 시간간격정의 */ Time sync : Sync Error 시간간격. Time flood : Flood Propagation 시간간격. Time reserv : Reservation 시간간격. Time sleep : Sleep or Send Data 시간간격. Time pulse_interval : 타이머주기값을의미. 그림 1. 센서 PULSE 프로토콜의타이밍 [1] Fig. 1. The Timing of the sensor PULSE protocol [1] 생성한노드의주소와자신이거쳐간노드의주소를포함한다. 이정보를이용해싱크노드와소스 (source) 노드사이의역경로 (reverse route) 가생성한다. 이것은 AODV [7] 의 RREP 메세지를통한응답메커니즘과유사하다 [1][5][6]. 예약패킷의전송은매펄스패킷의수신이있을때마다이루어져야하고, 더이상보낼데이터가없다면펄스패킷에대해응답하지않는다. 센서 PULSE 프로토콜은그림 1과같은고정된시간동기화를이용한다. 네트워크내의모든노드는펄스주기 (Pulse Period) 동안활동 (Wake-up) 상태로존재한다. 이펄스주기는펄스패킷의송수신을위한펄스흐름전송 (Pulse Flood Propagation) 과예약패킷의송수신을위한예약시간 (Reservation Time) 으로구성된다. 이시간동안에는데이터패킷의전송이중지된다. 각각의펄스패킷과예약패킷은정해진펄스흐름전송시간또는예약시간내에수신된패킷만유효하다. 예약패킷을전송하지않은노드는다음펄스주기가시작될때까지슬립상태가된다. 이를통해전체네트워크의전력소모를줄이는효과를얻게된다. 이동작과정은다음의알고리즘 1에기술된 PULSE 프로토콜의타이머핸들러코드에의해구현된다. 센서 PULSE는인프라 PULSE, 애드-혹 PULSE 프로토콜과달리다음펄스주기가시작되기전에중간활성주기 (Intermediate Wake-up Period) 를둔다 [1]. 이기간에는펄스패킷을전송하지않고예약패킷만을전송하여경로를갱신한다. 이것은펄스패킷의브로드캐스트횟수를줄이기때문에브로드캐스트에의한전력소모를줄일수있다. 또한, 센서 PULSE 는모든 PULSE 프로토콜중가장긴펄스주기를갖기때문에펄스패킷의전송횟수가더욱줄어든다. 이런이유로센서 PULSE는 PULSE 프로토콜들 /* 현재시간모드정의 */ SYNC_TIME : Sync Error 시간에속함 FLOOD_PROPA : Flood Propagation 시간에속함 RESERVATION : Reservation 시간에속함 SLEEP_TIME : Sleep or Send Data 시간에속 함 /* 변수정의및초기화 */ integer timer SYNC_TIME integer role NODE integer oneperiod 0 // 타이머상태 // 노드의역할 // 타이머의한주기 /* 타이머인터럽트에의해주기적으로실행 */ PULSETimer_Handle (): if (timer = SYNC_TIME) if (oneperiod > Time pulse_interval) oneperiod 0 timer FLOOD_PROPA if (role = SINK) send_pulse_pkt() set_timer_interval (Time flood) else oneperiod oneperiod + Time sync timer RESERVATION set_timer_interval (Time reserv) else if (timer = FLOOD_PROPA) oneperiod oneperiod + Time flood if (role = NODE && EmptyQueue() = false) send_reservation_packet () set_timer_interval (Time reserv) else if (timer = RESERVATION) oneperiod oneperiod + Time reserv if (role = NODE && EmptyQueue() = false) send_data_packet() else if (role = NODE) go_to_sleep() set_timer_interval (Time sleep) else if (timer = SLEEP_TIME) oneperiod oneperiod + Time sleep timer SYNC_TIME wake_up_node () set_timer_interval (Time sync) END MPULSETimer_Handle () 중가장전력소모가적은특징을갖는다. 그러나센서 PULSE 프로토콜은센서네트워크가이동이거의없는특징을갖는고정네트워크이고, 배터리의소모와환경변화에따른변화만이존재한다 [1] 고가정한다. 즉, 싱크노드의이동을고려하지않기때문에노드의이동으로인한불규칙적인경로오류에취약하다. 이는경로오류를복구하기위해서는다음펄스주기에펄스패킷이새로전송될때까지기다려야하기때문이다. 본논문은경로복구시간을단축하기위한기법을추가하여취약점을극복 153
한국통신학회논문지 '09-02 Vol. 34 No. 2 그림 2. 싱크노드의이동과경로복구 Fig. 2. The route recovery in the sensor network with a mobile sink node 하고, 센서 PULSE의적은전력소모특징을그대로유지할수있도록한다. Ⅲ. Mobile PULSE 프로토콜 : 경로복구시간단축 3.1 센서네트워크내의노드이동일반적으로센서네트워크는이동이거의없는네트워크로여겨진다. 이는특정영역에많은수의센서노드를설치하므로센서노드의이동이불필요하기때문이다. 그러므로대부분의센서네트워크연구에서이동성은고려하지않는다. 센서 PULSE [1] 역시노드의이동은고려하지않고있다. 하지만센서노드들로부터데이터를수집하고이를분석해야하는싱크노드의경우는다르다. 싱크노드는수많은센서노드로부터수집된데이터를모두수용할수있어야하고, 이데이터를분석할수있는능력을가져야한다. 그러므로싱크노드는센서노드에비해고성능이어야한다. 이것은많은수의싱크노드를설치하는것은비용문제로인해어려움이많다는것을의미한다. 하지만싱크노드가이동을한다면, 적은비용으로여러개의싱크노드를설치한것과같은효과를얻을수있다. 또한, 싱크노드가분석한데이터를보고행동을취해야하는것은언제나사람이다. 다시말해, 센서로부터언제어떤정보를담고있는데이터가전달될지모르기때문에항상담당자가싱크노드앞에대기하고있어야한다. 반면, PDA, 랩톱컴퓨터등의휴대용단말기를이용한다면, 담당자는단말기를가지고이동하면서어디서든센싱데이터에대한확인이가능하다. 이런이유로센서네트워크에서싱크노드의이동을고려해야한다. 싱크노드가이동할수있는가능성에 대해서는앞서설명한두가지이유와서론의 3가지시나리오예로설명이가능하다. 서론에서언급한시나리오에서는그림 2와같이싱크노드는센서네트워크내의근거리를이동하게된다. 즉, 한번의이동으로수km ~ 수십km만큼의장거리를이동하지않는다. 이런근거리이동은싱크노드의이동으로인해영향을받게되는센서노드들을싱크노드의주변노드들로한정할수있게한다. 즉, 싱크노드의이동으로인한경로오류는싱크노드와가까운주변노드들과의경로에만한정된다 [8]. 그러므로그림 2와같이전체경로가아닌, 싱크노드와주변노드사이의경로에대한복구가필요하다. 여기서우리는 2가지의가정을정의할수있다. 첫째, 센서네트워크내에서싱크노드는이동할수있다. 둘째, 싱크노드의이동에영향을받는경로는싱크노드주변 2~3홉거리내에있는경로이다. 3.2 싱크노드의이동을고려한 PULSE 프로토콜의개선센서 PULSE 프로토콜에서각센서노드는펄스패킷을받게되면경로를새로생성한다. 즉, 싱크노드의이동이발생했을때, 펄스주기에따라경로복구시간이결정된다. 펄스주기가짧아지면빠른복구가가능하지만, 펄스패킷의잦은전송으로인해노드의전력소모가많아진다. 본논문에서는이단점을극복하고빠른복구가가능하도록센서 PULSE 프로토콜을개선하였다. 센서 PULSE 프로토콜은시간동기화에의해동작한다. 기존의센서 PULSE에서는펄스패킷의전송횟수를줄이기위해서펄스주기를길게하고중간에중간활성주기를두었다. 중간활성주기에는예약패킷만송수신하기때문에펄스패킷전송으로인한전력소모를줄이면서도경로를갱신할수있다. 그러나중간활성주기는기존의경로를갱신하는역할만하기때문에노드의이동에대처하기어렵다. 이동으로인해발생한경로오류를복구하려면새로운경로를생성하기위해긴펄스주기동안기다려야한다. 이를해결하기위해우리는싱크노드의이동으로인한경로오류의복구시간을단축할수있도록센서 PULSE의타이밍 (timing) 을수정하였다. 그림 3은수정된타이밍 [8] 을나타낸다. 수정된타이밍은기본적으로센서 PULSE 의타이밍과유사하다. 다만, 중간활성주기외에중간펄스주기 (Intermediate Pulse Period) 를추가한것이다르다. 중간펄스주기는앞서언급한두가정을기반 154
논문 / 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 알고리즘 2 모바일 PULSE 프로토콜의타이머핸들러 Algorithm 2 The Timer Handler of Mobile PULSE protocol /* 시간간격정의 */ Time inter_flood : Intermediate Flood Propagation 시간간격 /* 현재시간모드정의 */ INTER_FLOOD_PROPA : Intermediate Flood Propagation 시간에속함 /* 변수정의및초기화 */ /* 타이머인터럽트에의해주기적으로실행 */ MobliePULSETimer_Handle (): if (timer = SYNC_TIME) if (oneperiod > Time pulse_interval) oneperiod 0 timer FLOOD_PROPA if (role = SINK) send_pulse_pkt() set_timer_interval (Time flood) else if (one Period > Time pulse_interval / 2) oneperiod oneperiod + Time sync if (role = SINK) send_intermediate_pul se_pkt() set_timer_interval (Time inter_flood) else oneperiod oneperiod + Time sync timer RESERVATION set_timer_interval (Time reserv) else if (timer = FLOOD_PROPA OR timer = INTER_FLOOD_PROPA) oneperiod oneperiod + Time flood if (role = NODE && EmptyQueue() = false) send_reservation_packet () set_timer_interval (Time reserv) END MobilePULSETimer_Handle () 으로한다. 즉, 싱크노드의이동으로인한영향은싱크노드주변의노드에한정되므로, 이들노드에게만펄스패킷을전송함으로써경로의복구가가능해진다. 이를위해중간펄스주기는중간펄스흐름전송 (Intermediate Flood Propagation) 시간동안중간펄스패킷을전송한다. 중간펄스패킷은 2~3홉정도만전송하기때문에보통의펄스패킷전송에비해훨씬적은수의펄스패킷전송이발생한다. 즉, 적은컨트롤패킷으로도빠른경로복구를제공할수있다. 이것은중간펄스패킷의전송으로인한전력소모가크지않다는것을의미한다. 알고리즘 2 는 PULSE 프로토콜의타이머핸들러코드에경로복구시간단축을위해추가된부분을나타낸다. 이추가된부분에의해중간펄스패킷을전송함으로써다음펄스주기가시작되기전, 기존보다더빠른시점에서경로를복구할수있다. 중간펄스주기와중간활성주기를비교했을때, 그림 3. Mobile PULSE 프로토콜의타이밍 [8] Fig. 3. The timing of the Mobile PULSE protocol [8] 추가되는부분은중간펄스흐름전송시간뿐이다. 이시간은중간펄스패킷이적은홉거리만전송되기때문에매우짧다. 그러므로이기간으로인해센서노드들이추가로활성상태를유지해야하는시간도짧다. 또한, 싱크노드에서 2~3홉거리에있는노드들만중간펄스패킷의전송을하기때문에이전송을수행하는노드의수도적다. 그러므로기존의센서 PULSE에비해전력소모면에서도부담이크지않다. 즉, 싱크노드로부터 2~3홉의근거리에있는주변노드들에게추가펄스패킷을보내는간단한작업을통해싱크노드의이동으로인한데이터패킷의드롭 (drop) 을줄일수있다. 반면, 전력소모량은기존센서 PULSE 프로토콜과비슷한수준으로유지할수있어전력소모를줄이는효과도유지할수있다. Ⅳ. 실험 4.1 실험환경및시나리오기존의센서 PULSE 프로토콜과모바일 PULSE 프로토콜의성능비교를위해두프로토콜을 2.29 버전의 NS2 [9] 네트워크시뮬레이터를이용해구현하였다. 새로추가된중간펄스주기외의다른영향을배제하기위해타이밍부분을제외한나머지부분은동일하게구현하였다. 실험에서사용한시나리오는휴대용단말기를싱크노드로하는경우를가정한다. 이를위해, 4 km X 1 km의공간에 100개의센서노드를배치하였다. 싱크노드는왼쪽끝에서오른쪽끝으로 1.5m/s 의속도로이동한다. 이는사람의걷는속도와각노드의전송범위를고려한결과이다. 노드의이동속도가느리기때문에충분한데이터를얻기위해 1시간에걸쳐실험을진행하였다. 또한, 802.11 MAC 을사용하 155
한국통신학회논문지 '09-02 Vol. 34 No. 2 표 1. 802.11 무선랜전력소모량 Table 1. 802.11 WLAN Power Consumption 전압 Energy Mode 전류 Power Consumption Transmit 280 ma 1327 mw 4.74 V Receive 204 ma 966 mw Idle 178 ma 843 mw Sleep 14 ma 66 mw sensor PULSE Mobile PULSE sensor PULSE Mobile PULSE 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 CDF 0.2 여무선애드 -혹네트워크를구성하였다. 일반적으로센서에서는 802.11의 RTS/CTS 메커니즘이사용되지않기때문에해당기능을제거하였다 [1]. 본논문에서는센서노드가수집한데이터를일정주기마다전송한다고가정하고, 일정한주기에따라트래픽이벤트를발생하도록하였다. 하나의트래픽이벤트는 20ms 간격으로전송하는 5개의패킷으로구성하고, 이벤트의발생간격은 500ms, 600ms, 700ms, 800ms, 900ms, 1s, 10s, 60s로세분화하였다. 각센서노드의전력소모를측정하기위해서표 1과같은 802.11 무선랜의전압, 전류, 그리고이를바탕으로계산된전력을이용한다 [10]. 전력모드는 Idle, Transmit, Receive, Sleep의네가지모드로구성된다. Flood Propagation과 Reservation Time, Wake-up Period의수, Wake-up Interval 등의시간파라미터는 [1] 에나타난값을참고로결정하였다. 실험은기존의센서 PULSE와모바일 PULSE의비교를중심으로실행하였다. 먼저모바일 PULSE 와센서 PULSE의경로복구에걸리는시간과드롭되는패킷의양을측정하였다. 또한, 경로복구를위해프로토콜을수정함으로써나타나는전력변화를측정하기위해두프로토콜의평균전력소모량을측정하였다. 4.2 센서 PULSE와모바일 PULSE 성능비교모바일 PULSE 프로토콜의성능측정을위해기존의센서 PULSE 프로토콜과비교실험을진행하였다. 실험대상프로토콜중 1/2 PULSE 는센서 PULSE 의펄스주기를반으로줄인프로토콜을의미한다. 이절에서는모바일 PULSE와센서 PULSE의성능비교를다루고, Ⅳ장의 3절에서 1/2 PULSE 와의성능비교를다룬다. 본논문에서는 Ⅳ장의 1절에서언급한 7가지이벤트주기마다복구시간을측정하였다. 그림 4는경로복구에걸리는시간을측정한그래프이다. x축은경로복구에걸리는시간을의미한다. 왼쪽 y축은반복적인경로오류를발생시키고이를 0.0 0 10 20 30 40 50 60 70 80 90 100 Recovery Time (s) 그림 4. 경로복구시간 Fig. 4 The route recovery time 복구하는데걸리는시간을모두측정한후, 시간대별로구분하여해당시간범위안에경로복구를완료한사건의개수 (Frequency) 로나타낸다. 또한, 오른쪽의 y축은왼쪽의경우의수를모두합한누적분포 (CDF) 를의미한다. 경로복구에걸리는시간은데이터패킷이처음드롭된시점부터드롭이후싱크에서데이터패킷을수신한시점까지의시간으로정의하였다. CDF 결과에의하면, 모바일 PULSE는복구에걸리는시간이 50초이전에약 90% 가몰려있는반면, 센서 PULSE는약 60% 의경우만존재한다. 즉모바일 PULSE는대부분의경로오류를 50초이내에복구할수있다. 이결과는각복구시간별로복구된횟수를나타낸막대그래프에서도나타난다. 빗금친모바일 PULSE 의경우많은수가 50초이전에몰려있고, 50 초를초과하는경우는총 101가지경우의수중 8개로나타난다. 즉, 경로복구시간은모바일 PULSE 가센서 PULSE에비해약 1.5배정도빠르다. 이실험결과를통해, 모바일 PULSE가기존센서 PULSE에비해경로복구시간이더짧다는것을알수있다. 경로복구시간의단축은현저히데이터패킷드롭양의감소로도확인할수있다. 기존센서 PULSE 보다이른시기에경로가복구됨으로써이후의데이터패킷은드롭되지않게된다. 그림 5는네트워크전체에서드롭된패킷의양을측정한결과이다. 싱크노드이동으로인해발생하는드롭만을측정하기위해큐에서오버플러우가발생하지않도록하였다. 이를위해라우터의큐사이즈를충분히큰값으로결정하였다. 실험결과, 모바일 PULSE는모든이벤트발생간격에서드롭되는데이터패킷의양이크게줄었다. 특히, 그래프에서 600ms 구간을보면약 2배정도줄었음을확인할수있다. 드롭패킷의양감소 0.1 156
논문 / 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 Drop Packets 5000 4000 3000 2000 1000 sensor PULSE 1/2 PULSE Mobile PULSE Average Power Consumption (W) 600 500 400 sensor PULSE 1/2 PULSE Mobile PULSE 0 60 s 10 s 1 s 900 ms 800 ms 700 ms 600 ms 500 ms 0 60 s 10 s 1 s 900 ms 800 ms 700 ms 600 ms 500 ms Event Interval Event Interval 그림 5. 드롭되는패킷의양 Fig. 5. The number of drop packets 효과는이벤트간격이작을수록크게나타난다. 이벤트간격이작을수록데이터패킷전송의주기가짧아져전송하는데이터패킷의수가많기때문이다. 이것은단위시간동안더많은드롭이발생하게한다. 그러므로복구시간이단축되면더많은양의드롭을줄이는효과를얻을수있다. 한편, 센서네트워크에서는경로복구시간을단축하는하면서도전력소모가적어야한다. 모바일 PULSE 는중간펄스주기가추가되기때문에노드의전력소모량은증가할것으로예상할수있다. 이시간동안노드가활성상태로되어있어야하고, 추가적인중간펄스패킷의브로드캐스트를수행하기때문이다. 그러므로이에대한비교실험이요구된다. 이를위해센서 PULSE 와모바일 PULSE 의전력소모량을비교하는실험을진행하였다 [11]. 두프로토콜의타이밍파라미터값은동일하게하고, Ⅳ장 1절에서언급한네트워크토폴로지에서평균전력소모량을측정하였다. 전력소모량은노드마다차이를보이기때문에전체노드의평균전력소모량을측정하였다. 그림 6은각이벤트발생간격에따라평균전력소모량을측정할결과이다. 이실험결과를보면, 모바일 PULSE의평균전력소모량이센서 PULSE 에비해크게증가하지않는다는것을알수있다. 즉, 프로토콜의수정이전력효율에미치는영향은매우작다고할수있다. 이것은노드들이추가로활성상태를유지해야하는시간이 100ms로짧고, 중간펄스패킷의전송에관련된노드가싱크노드로부터 2~3홉거리에있는일부노드로한정되기때문이다. 즉, 중간펄스주기의추가로더많은펄스패킷이전송됨에도불구하고이로인한전력소모가매우적다. 이것은그림 7의실험결 그림 6. 평균전력소모량 Fig. 6. The average power consumption Total Sending Packets 80000 70000 60000 50000 40000 30000 20000 10000 0 sensor PULSE 1/2 PULSE Mobile PULSE 100 150 200 250 300 350 400 Total Nodes 그림 7. 전송된컨트롤패킷의수 Fig. 7. The number of transmitted control packets 과에잘나타난다. 그림 7은총노드수에따라전송된컨트롤패킷의양을측정한그래프이다. 컨트롤패킷의수만을측정했기때문에데이터패킷을생성하는이벤트간격과관계가없다. 반면, 전체노드의수에따라브로드캐스트되는패킷의양과패킷이전달되는홉수가달라지기때문에전체노드의수를변화시켰다. x 축은전체노드의수이고, y축은컨트롤패킷의전송량을의미한다. 이실험의결과에의하면, 모바일 PULSE 의컨트롤패킷전송량은센서 PULSE와거의비슷하다. 중간펄스패킷은싱크노드에서 2~3홉떨어진노드에게만브로드캐스트되기때문에전체컨트롤패킷수에비하면그양이매우적다. 그러므로중간펄스패킷의전송횟수증가는전체네트워크의전력소모량에거의영향을미치지않는다. 즉, 그림 6과그림 7의실험결과와같이모바일 PULSE 프로토콜은기존의센서 PULSE 프로토콜과비슷한수준의전력량감소효과를얻을수있다. 157
한국통신학회논문지 '09-02 Vol. 34 No. 2 이들실험을통해, 모바일 PULSE 는센서 PULSE 에비해더나은성능을보임을알수있다. 즉, 전력소모량에서기존센서 PULSE와거의대등한성능을보이면서싱크노드의이동으로인한경로오류를더빠르게복구할수있다. 이것은모바일 PULSE 가싱크노드의이동에대해서기존센서 PULSE 보다더나은성능을보임은물론, 고정된싱크노드를가진센서네트워크에서도별다른수정없이사용할수있다는것을의미한다. 4.3 펄스주기의단축과모바일 PULSE 프로토콜 PULSE 프로토콜은특성상펄스주기에따라경로갱신주기가달라진다. 그러므로싱크노드가이동하더라도이펄스주기를조절함으로써경로복구시간을단축할수있다. 이런경우에우리가제안한모바일 PULSE 프로토콜과비교하여어떤차이가있는지알아보기위해실험을진행하였다. 이를위해센서 PULSE의펄스주기를 1/2로줄여모바일 PULSE 와비슷한시간에경로복구가가능하도록수정하였다. 그리고역시같은네트워크토폴로지에서드롭된데이터패킷의양, 평균전력소모량을측정하였다. 각실험의결과는 Ⅳ장 2절의그래프에 1/2 PULSE 의이름으로포함되어있다. 모바일 PULSE와같아지도록펄스주기를수정한것이기때문에경로복구시간은따로측정하지않았다. 1/2 PULSE 는데이터패킷의손실면에서모바일 PULSE 와비슷한성능을보이고있다. 그림 5에나타난바와같이, 드롭된데이터패킷의양은센서 PULSE 보다 2배가까이줄었고모바일 PULSE와는거의비슷하다. 즉, 단순히펄스주기를줄이는것만으로도경로복구시간단축이가능하다. 그러나이방식에는전력소모량면에서큰단점이존재한다. 그림 6에의하면, 1/2 PULSE 는모든이벤트간격에서전력소모가더많은것을알수있다. 이것을수치로나타내면다음표 2와같은전력소모량의차이를보인다. 이결과에의하면 1/2 PULSE 는모바일 PULSE에비해최소 7.8W에서최대 13.9W의전력을더소모한다. 또한, 모바일 PULSE의경우중간펄스패킷을주변 2~3홉에만브로드캐스트하지만, 1/2 PULSE 은모든노드에게브로드캐스트한다. 이로인해, 전송하는컨트롤패킷의수에서그림 7과같은결과가나타난다. 특히, 전체노드수가증가함에따라컨트롤패킷의수는더큰폭으로증가한다. 모바일 PULSE 는싱크주변에위치한적은수의노드에게만 표 2. 프로토콜의전력소모량의차이 Table 2. The difference of the power consumption in protocols 모바일 PULSE 1/2 PULSE - 1/2 PULSE - - 센서 PULSE 센서 PULSE 모바일 PULSE 60 s 3.126 12.187 9.060 10 s 1.225 9.094 7.869 1 s -4.826 11.631 16.457 900 ms -3.720 7.639 11.360 800 ms -3.790 10.162 13.952 700 ms 3.636 10.300 6.663 600 ms -1.698 12.285 13.983 500 ms 4.046 17.570 13.524 펄스패킷을전송하므로컨트롤패킷의증가량이매우적다. 반면, 1/2 PULSE 는모든노드에게브로드캐스트하기때문에펄스패킷의수가크게증가한다. 이처럼 1/2 PULSE 는많은펄스패킷의전송으로전력소모량이증가한다. 그러므로노드수가많고전력소모를최소화해야하는센서네트워크에서 1/2 PULSE 는적합하지않다. 이와같이기존센서 PULSE의펄스주기단축은빠른경로복구가가능하지만, 잦은펄스패킷의전송으로인해전력소모가많아지는단점이있다. 하지만우리가제안하는모바일 PULSE 는기존센서 PULSE 와비슷한수의컨트롤패킷만으로경로복구시간을단축시킬수있다. 이것은전력소모량을기존센서 PULSE 와비슷한수준으로유지할수있게한다. 즉, 모바일 PULSE는경로복구시간단축과소모전력량감소의두목적을모두달성할수있다. 그러므로싱크노드의이동을고려한센서네트워크에서는단순히펄스주기를짧게하는방법보다모바일 PULSE를이용하는것이더효율적이다. Ⅴ. 관련연구 싱크노드의이동을고려한센서네트워크에서의라우팅프로토콜연구는싱크노드에서경로생성을시작하는방법과소스노드에서시작하는방법으로나뉜다 [12]. 싱크노드에서경로를생성하는프로토콜로는 Directed Diffusion [13], SAFE [14], MobiRoute [15] 등이있고, 소스노드에서경로를생성하는프로토콜에는 SEAD [16], TTDD [17], TTCG [18] 등이있다. MobiRoute는Berkeley MintRoute [19] 프로토콜을노드의이동을고려해확장한프로토콜이다. 두프로토콜모두거리- 벡터알고리즘 (distance-vector algorithm) 에기반한다. MobiRoute는싱크노드의이동을고려하여 158
논문 / 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 4가지상태정보 (pre-move, move, pre-sojourn, sojourn) 를정의한다. 싱크노드는상태를 sojourn에서 pre-move로변경하고비콘메시지를전송한다. 비콘메시지의전송이완료되면싱크노드는 move 상태로변환하고이동을시작한다. 각센서노드는첫비콘메시지를수신하면자신의상태를 sojourn 에서 move 상태로변환한다. 싱크노드는이동이멈추면, 자신의상태를 pre-sojourn으로변경하고더빠른전송빈도 (speed-up rate) 경로메시지 (route message) 를전송한다. 싱크노드로부터직접이메시지를받은노드는자신의상태를 pre-sojourn으로변경하고메시지를다른노드에게전송한다. 그후타이머에의해모든노드는 sojourn 상태가되고, 새로운경로를통해데이터전송을수행한다. 그러나싱크노드가계속해서이동하면데이터전달이어렵고, 싱크노드는자신이이동중인지멈춘상태인지를알아야하는단점이있다. TTDD는가상의좌표 (grid) 를이용해싱크노드까지데이터를전송한다. 보낼데이터를가진센서노드 (source) 는데이터알림메시지를자신이속한좌표셀의 4군데가상의전달지점 (dissemination point) 로전송한다. 이때, 이지점에가장가까운센서노드가전달노드 (dissemination node) 가된다. 전달노드는소스노드에대한정보를저장하고, 수신한알림메시지를다른셀의전달노드에게보낸다. 이과정은알림메시지안에있는지점에가장가까운전달노드에도달할때까지반복된다. 그후, 싱크노드는데이터가필요할경우데이터를요구하는쿼리를전송한다. 이쿼리는싱크노드에가장가까운전달노드에게전송된다. 전달노드는자신이가진소스노드의정보를통해원하는데이터를가진소스를찾고, 해당소스의알림메시지를전달해준인접셀의전달노드에게요청쿼리를전달한다. 이과정을반복하여소스까지도달하면, 소스는퀴리가전달된방향으로데이터를전송한다. 그러나싱크노드를제외한모든센서노드가자신의위치를알아야하는단점이있다. 또한, TTDD는여러영역에서 Interest 이벤트가빈번하게발생하는경우가상좌표계생성에요구되는패킷들의증가로전력효율성이떨어지는단점이있다. 이를해결하기위해 TTCG 프로토콜이제안되었다. 이프로토콜은하나의좌표계를더추가하여 3개의좌표계를이용한다. 추가된좌표계는모바일노드를위한것으로 TTDD에서생성한좌표계와동일한좌표계를이룬다. 이기법은 TTDD에서사용되던각각의전달노드들을고정된싱크노드로사용한다. 이들노드는자신의가상좌표셀안에포함된센서노드들로부터데이터를수집한다. 모바일노드는자신의셀안에있는고정싱크노드에게데이터를요청하여수집한다. 이때, 모바일노드는고정싱크노드의알림메시지 (Announcement message) 를주기적으로수신하여자신의위치를파악한다. 이방식은반복적인좌표계구성으로인한전력낭비를방지할수있지만, 고정된싱크노드에의존하기때문에이들노드의전력소모가크고이들의오류가데이터경로의오류로직결되는단점이있다. Ⅵ. 결론우리의연구는두가지가정에서출발한다. 첫번째는싱크노드가이동할수있다는것이고, 두번째는경로변화가생기는노드는싱크노드주변으로한정된다는것이다. 이두가정을통해싱크노드와 2~3홉떨어진노드와의경로만복구하면데이터전송이재개된다는것을유추할수있다. 이것이제안한모바일 PULSE 프로토콜의기본바탕이된다. 모바일 PULSE 프로토콜은기존의센서 PULSE 프로토콜에중간펄스주기를추가하는간단한작업으로경로복구시간을단축할수있다. 또한, 중간펄스패킷을싱크노드주변의 2~3홉범위안에만브로드캐스트하기때문에추가적인패킷전송이많지않다. 즉, 모바일 PULSE 프로토콜은센서네트워크내에서의싱크노드이동을가능하게하면서소모전력량의증가를억제할수있다. 이처럼프로토콜의수정으로인한영향이작기때문에고정된싱크노드를사용하는센서네트워크에서도기존센서 PULSE 와성능차이가적다. 이는모바일 PULSE 프로토콜은모바일싱크노드를가진센서네트워크와고정된싱크노드를가진센서네트워크모두에적합함을의미한다. 본논문은모바일 PULSE의경로복구능력과전력소모량을보임으로써모바일센서네트워크에모바일 PULSE가적합함을증명하였다. 제안하는모바일 PULSE는경로복구시간을단축하였으나전력소모량에서약간의증가를가져왔다. 향후중간펄스주기의실행시기와횟수에따른영향을고려한계속적인연구가진행된다면전력소모량을더욱감소시킬수있다. 본논문은모바일 PULSE 프로토콜을제안하고, 모바일센서네트워크환경에적합한프로토콜로서의가능성을제시하고있다. 159
한국통신학회논문지 '09-02 Vol. 34 No. 2 참고문헌 [1] Baruch Awerbuch, David Holmer, Herbert Rubens, Kirk Chang, and I.-J. Wang, The Pulse Protocol: Sensor Network Routing and Power Saving, In Proceedings of Military Communications Conference (MILCOM 2004), Nov. 2004. [2] W. Ye, J. Heidemann, and D. Estrin, An energy-efficient mac protocol for wireless sensor networks, In Proceedings of 21st International Annual Joint Conference of the IEEE Computer and Communications Societies, June 2002. [3] S. Singh and C. Raghavendra, Pamas: Power aware multi-access protocol with signaling for ad hoc networks, In ACM Computer Communications Review, 1999. [4] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, A Survey on Sensor Networks, In IEEE Communications Magazine, 40(8):102 116, August 2002. [5] Baruch Awerbuch, David Holmer, and Herbert Rubens, The Pulse Protcol: Energy Efficient Infrastructure Access, In Proceedings of The 23rd Conference of the IEEE Communications Society INFOCOM, 2004. [6] Baruch Awerbuch, David Holmer, and Herbert Rubens, The Pulse Protocol: Mobile ad hoc network performance evaluation, In Proceedings of Wireless On-demand Network Systems and Services 2005 (WONS 2005), January 2005. [7] C. E. Perkins and E. M. Royer, Ad-hoc On-Demand Distance Vector Routing, In Proceedings of 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999. [8] 이신형, 유혁, M-PULSE: 싱크노드의이동성지원을위한센서네트워크라우팅프로토콜, 한국정보과학회추계학술대회, 2003 [9] NS-2 Network Simulator, http://www.isi.edu/nsnam/ns/ [10] L.M. Feeney and M. Nilsson, Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, In Proceedings of INFOCOM, pp.1548-1557, April 2001. [11] 이치영, 이신형, 유혁, 모바일싱크노드를가진 센서네트워크를위한에너지효율적인라우팅기법, 한국정보과학회종합학술대회, 2008. [12] Kwang-il Hwang, and Doo-seop Eom, Adaptive Sink Mobility Management Scheme for Wireless Sensor Networks, In Proceedings of Ubiquitous Intelligence and Computing Third International Conference (UIC 2006), Lecture Notes in Computer Science, Vol. 4159, pp.487-487, 2006. [13] C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed diffusion for Wireless Sensor Networking, In IEEE/ACM Transaction on Networking, Vol. 11, 2003. [14] Sooyeon Kim, Sang H. Son, John A. Stankovic, Shuoqi Li, and Yanghee Choi, SAFE: A Data Dissemination Protocol for Periodic Update in Sensor Networks, In Proceedings of the 23rd International Conference on Distributed Computing Systems Workshops (ICDCSW 03), 2003. [15] Jun Luo, Jacques Panchard, Michal Piorkowski, Matthias Grossglauser, and Jean-Pierre Hubaux, MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks, In Proceedings of International Conference on Distributed Computing in Sensor Systems, June 2006. [16] Hyung Seok Kim, Tarek F. Abdelzaher, and Wook Hyun Kwon, Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks, In Proceedings of Embedded Networked Sensor Systems, 2003. [17] Haiyun Luo, Fan Ye, Jerry Cheng, Songwu Lu, and Lixia Zhang, TTDD: Two-Tier Data Dissemination in Large-Scale Wireless Sensor Netwokrs, In Wireless Networks, Volume 11, Issue 1-2, January 2005. [18] S. Sho, K. Kim, W. Jun, J. Kim, S. Kim, and J. Lee, TTCG: Three-Tier Context Gathering Technique for Mobile Devices, In Proceedings of the 5th international conference on Pervasive services, pp.152-162, 2008. [19] Alec Woo, Terence Tong, and David Cullar, Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks, In Proceedings of the 1st international conference on Embedded Networked Sensor Systems, 2003. 160
논문 / 모바일 PULSE : 모바일싱크노드를가진센서네트워크에서의경로복구시간과전력소모량을고려한라우팅프로토콜 이치영 (Chi-Young Lee) 준회원 2006년 2월충남대학교컴퓨터전공학사 2008년 2월고려대학교컴퓨터학과석사 2008년 3월 ~ 현재고려대학교컴퓨터학과박사과정 < 관심분야 > 전력관리, 센서네트워크라우팅프로토콜, 시스템가상화 이신형 (Shin-Hyoung Lee) 정회원 2001년 2월고려대학교지구환경과학과학사 2005년 2월고려대학교컴퓨터학과석사 2007년 3월 ~ 현재고려대학교컴퓨터학과박사과정 < 관심분야 > 센서네트워크, RFID, 네트워크프로토콜, 운영체제 유혁 (Chuck Yoo) 종신회원 1982년 2월서울대학교전자공학과학사 1984년 2월서울대학교전자공학과석사 1986년 8월 Univ. of Michigan 전산학석사 1990년 2월 Univ. of Michigan 전산학박사 1990년 ~1995년 Sun Microsystems 연구원 1995년 ~ 현재고려대학교컴퓨터학과교수 < 관심분야 > 운영체제, 시스템가상화, 네트워크, 멀티미디어스트리밍 161