논문 12-37A-10-10 한국통신학회논문지 '12-10 Vol.37A No.10 http://dx.doi.org/10.7840/kics.2012.37a.10.876 무선센서네트워크에서지연에민감한정보의다중홉전송기법 차재룡, 김재현 Multi-hop Transmission Scheme for Delay-Sensitive Information in Wireless Sensor Networks Jae-Ryong Cha, Jae-Hyun Kim 요 약 본논문에서는무선센서네트워크 (wireless sensor network : WSN) 에서발생하는두가지지연요인인큐잉지연 (queueing delay) 과랜덤링크스케줄링에의한지연 (delay by random link scheduling) 을소개하고이를해결하기위한새로운순차적스케줄링기법을제안한다. 또한모의실험을통하여이용하여제안한다중홉전송기법의성능평가를수행하고, 이를기존의랜덤링크스케줄링기법의성능과종단간패킷전송지연의관점에서비교한다. 모의실험결과에따르면, 소스노드 (source node) 와목적지노드 (destination node) 사이의홉수 (hop distance) 가증가할수록제안한스케줄링기법과기존의랜덤링크스케줄링기법의지연성능차이가증가함을알수있었다. 소스노드와목적지노드사이의평균홉수가 2.66, 4.1, 4.75 및 6.3 일때, 제안한스케줄링기법은기존의랜덤링크스케줄링기법에비해 22%, 36%, 48% 및 55% 까지지연시간을줄일수있었다. Key Words : Multihop, Distributed, Sequential scheduling, WSN, 다중홉, 분산, 순차적스케줄링, 무선센서네트워크 ABSTRACT This paper introduces two multi-hop delay factors which can be caused by conventional TDMA scheduling; queueing delay and delay by random link scheduling, and proposes a new sequential scheduling scheme to resolve these two factors. We also simulate the TDMA network with the proposed link scheduling scheme and compare it with conventional(random) link scheduling scheme in terms of end-to-end packet transmission delay. From the simulation results, the more the average hop distance increases, the more the difference of the delay performance of both scheduling schemes increases. When the average number of hops is 2.66, 4.1, 4.75, and 6.3, the proposed sequential scheduling scheme reduces the average end-to-end delay by about 22%, 36%, 48%, and 55% respectively when compared to the random scheduling scheme. Ⅰ. 서론 무선센서네트워크 (wireless sensor network : WSN) 에서의대표적인매체접근제어 (medium access control : MAC) 프로토콜은비경쟁방식 (time division multiple access : TDMA) 과경쟁 " 본연구는지식경제부및정보통신산업진흥원의대학 IT 연구센터지원사업의연구결과로수행되었음 " (NIPA-2012-(H0301-12-2003)) " 본연구는방송통신위원회의방송통신인프라원천기술개발사업의연구결과로수행되었음 "(KCA-2012-08-911-05-001) 주저자 : 아주대학교전자공학과무선인터넷연구실, builder@ajou.ac.kr, 정회원 교신저자 : 아주대학교전자공학과무선인터넷연구실, jkim@ajou.ac.kr, 종신회원논문번호 :KICS2011-11-573, 접수일자 :2011 년 11 월 30 일, 최종논문접수일자 :2012 년 10 월 10 일 876
논문 / 무선센서네트워크에서지연에민감한정보의다중홉전송기법 For beacon... L frames = cycle L 1 2 3 4 5 Slot 1 2 3 4...... N-3 N-2 N-1 N time 그림 1. DCH 에서의 TDMA 프레임구조 Fig. 1. TDMA frame structure in DCH 방식 (carrier sensing multiple access : CSMA) 으로구분될수있다. 비경쟁기반의 MAC 프로토콜은각노드마다전송할타임슬롯 (time slot) 을미리할당하여해당슬롯에서전송을하는방식이다. 따라서, 경쟁기반의 MAC 프로토콜에비해충돌이적으며, RTS/CTS(Request to Send/Clear to Send) 와같은제어패킷이필요하지않아오버헤드가적다는장점이있다. 그러나, 분산되어있는노드의시간동기를유지해야한다는단점이있다. 경쟁기반프로토콜은매홉마다경쟁을통하여이웃노드에게패킷을전달하는방식이다. 그러나, 경쟁기반프로토콜은패킷충돌에의한재전송, 패킷중계를위해항상채널을감시하는오버히어링, 센서노드간정보공유와특정목적을위한제어패킷전송, 또는이웃노드로부터전송된데이터를수신하기위해항상수신모드를유지해야하는유휴청취등으로인하여무선센서네트워크와같은다중홉환경에서는 TDMA 기반프로토콜에비해더많은오버헤드가필요하여에너지소비가크다는단점이있다. 따라서, 본논문에서는비경쟁기반프로토콜중대표적인 TDMA 스케줄링기법을중점적으로다룬다. 기존의 TDMA 스케줄링관련연구 [1]-[4] 들의목적은네트워크내의노드들이충돌없이통신을하기위해가능한한작은프레임크기 ( 슬롯의수 ) 를갖도록하는스케줄링기법 (minimum length schedule) 을설계하는것이었다. 그러나, 다수의노드가하나또는소수의수신노드에게패킷을전송하는무선센서네트워크의설계목적이지연에민감한이벤트정보의다중홉전송일경우, 기존의 minimum length schedule은다음과같은두가지제약사항을가지고있다. 첫째, minimum length schedule은큐잉지연을발생시켜종단간패킷전송... 지연을증가시킬수있다. 둘째, minimum length schedule은할당된슬롯의순서가순차적이지못할수있기때문에랜덤링크스케줄에의한추가적인지연을경험할수있다. 다중홉환경에서홉수가길면길수록큐잉지연과랜덤링크스케줄에의한지연은종단간패킷전송지연에더큰영향을끼친다. 두가지제약사항에대한세부내용은 IV장에서설명한다. 따라서, 본논문에서는기존연구의두가지제약사항을해결하여지연에민감한이벤트정보의 QoS를보장하기위한다중홉전송기법을제안한다. 본논문의구성은다음과같다. 제 II장에서는 TDMA 스케줄링관련연구를설명하고 III 장에서제안하는다중홉전송기법을위한시스템모델을설명한다. 제 IV장에서는다중홉 TDMA 환경에서발생할수있는두가지지연요인을설명하고, 이러한문제를해결하기위하여 V장에서순차적인다중홉스케줄링기법이제안된다. VI장에서모의실험을통하여기존의랜덤스케줄링방식과제안한스케줄링방식을비교하고 VII장에서결론을맺는다. Ⅱ. 관련연구 TDMA 스케줄링기법은타임슬롯을각노드에할당하는방식과타임슬롯을각노드간링크에할당하는방식으로구분될수있다. 동일한채널을사용한다고가정할경우, 타임슬롯을노드에할당하는방식은 2 홉거리이내에있는노드들이같은슬롯을할당할수없다. 그러나, 타임슬롯이링크에할당된다면 2 홉거리에있는노드들도동시에패킷의전송또는수신이가능하다 [1]. 또한, 타임슬롯이노드에할당되면패킷을전송하는노드의모든이웃노드들은해당패킷을수신한후자신에게전송된것인지를판단해야하므로, 해당패킷을수신할필요가없더라도트랜시버를항상켜두어야한다. 그러나, 타임슬롯이노드간링크에할당되면한노드만그슬롯에서트랜시버를켜고패킷을수신하면되므로슬롯을노드에할당하는방식에비해상대적으로에너지를절약할수있다. 따라서, 본논문에서는타임슬롯을링크에할당하는방식을기반으로다중홉전송기법을제안한다. 일반적으로타임슬롯을링크에할당하는방식은그래프이론에서 edge coloring problem과밀접한연관성을가진다. Vizing 이론에따르면, 한그래프에서 877
한국통신학회논문지 '12-10 Vol.37A No.10 또한 Gandham 은 acyclic 그래프에대해서도최대 만큼의슬롯이필요하다는것을분석하였고모의실험을통하여검증하였다 [5]. 한편, Djukic는슬롯할당순서로인한스케줄링지연을줄이기위한순차적슬롯할당기법을제안하였다. 그러나, 중앙컨트롤러 ( 또는 base station) 가항상존재해야하고, 링크간전송순서가사전에결정되어야한다는가정을필요로한다 [8]. Trung가제안한기법은 Djukic의슬롯할당방식을멀티채널환경으로확장한것으로, 여전히중앙컨트롤러를필요로한다 [9]. 위에서언급한연구결과에서알수있듯이, 기 그림 2. 인바운드 / 아웃바운드링크의예 Fig. 2. Example of inbound/outbound links 유효한 edge coloring은최대 ( ) color가필요하다 [5]. 이때, 는그래프에서한노드의 maximum degree를의미한다. 즉, 한노드에연결된모든독립된 edge 개수를의미한다. 만일그래프에서유효한 edge coloring을 TDMA 스케줄링에적용하면, 센서노드를위한슬롯할당은그래프이론에서결정된 color에각각의타임슬롯을매핑하는것과등가로생각할수있다. 기존연구에서 Panconesi and Srinivasan은최대 ( ) 슬롯을갖는분산스케줄링알고리즘을제안하였고, 이후기존의알고리즘보다우수한성능을갖는향상된알고리즘을제안하였다 [2]. 기존의분산형알고리즘중가장좋은성능을보이는것은 Grable and Panconesi이제안한 randomized algorithm으로써최대 만큼의슬롯을이용하여네트워크의노드가충돌없이데이터를전송할수있다. 이때 은시스템입력파라미터이다 [3]. 그러나, Marathe 는모의실험을통하여 randomized algorithm이 값이작을경우스케줄링에실패할수도있다는것을검증하였다 [6]. Ramnathan은다중홉환경에서 TDMA, FDMA(frequency division multiple access) 및 CDMA(code division multiple access) 를위한프레임워크를제안하였다. Ramnathan이제안한스케줄링알고리즘은최대 O(θ) 만큼의슬롯이필요하며, 이때 θ는플래너그래프 (planar graph) 의최소개수를의미한다 [7]. Gandham은 distance-1 coloring을사용할때발생할수있는히든노드문제 (hidden node problem) 및노출노드문제 (exposed node problem) 를해결한알고리즘을개발하였고, Gandham이제안한스케줄링기법은 cyclic 그래프에대해최대 만큼의슬롯이필요하다. 존의 TDMA 스케줄링관련연구의목적은주로네트워크에존재하는모든노드들이충돌없이통신할수있도록하기위하여가능한한작은프레임크기를갖도록하는스케줄링기법을설계하는것이다. 또한순차적스케줄링기법의경우에도항상중앙컨트롤러가존재해야한다는가정을필요로한다. 본논문에서는, 기존의연구들이무선센서네트워크에적용될때두가지지연요인을발생시켜종단간패킷전송지연을증가시킬수있다는사실을보이고이를해결하기위하여분산환경에서라우팅과결합된순차적스케줄링기법을제안한다. Ⅲ. 시스템모델 본논문에서는무선센서네트워크를센서노드를의미하는점 (vertex) 과무선통신링크를의미하는에지 (edge) 로이루어지는방향성그래프 로모델링한다. 이때, 는무선센서네트워크내의모든노드의집합을의미하며 는모든방향성링크의집합을의미한다. 만일임의의두노드 와 가 이면두노드, 는이웃노드라고정의한다. 무선센서네트워크내에 개의플로우가존재하며각플로우는 으로정의된다. 이때, 이며, 은소스노드 (source node) 를, ( ) 는 Relay Node를, 는목적지노드 (destination node) 를각각의미한다. 본논문에서네트워크내에서사용되는채널 (channel) 은공용채널 (common channel : CCH) 과데이터채널 (data channel : DCH) 로구분되는데, 각노드는 CCH에서 CSMA를기반으로슬롯할당을수행하고슬롯할당이완료되면 DCH에서데이터를전 878
논문 / 무선센서네트워크에서지연에민감한정보의다중홉전송기법 송한다. 그림 1은 DCH에서의제안한스케줄링기법을위한 TDMA 프레임구조를나타낸다. DCH는 개의프레임으로구성되고, 각프레임은 개의슬롯으로구성된다. 각프레임에서첫번째슬롯은각노드가비컨 (beacon) 을전송하기위해사용된다. 비컨은다음과같은 3가지정보를포함한다. 은임의의노드가해당슬롯에서전송노드인지, 은임의의노드가해당슬롯에서수신노드인지, 그리고 은해당슬롯에서임의의노드의이웃노드가전송노드인지여부를나타낸다. 위의세가지값들을결정하는방법은다음과같다. - 노드 이슬롯 에서데이터를전송하면이값은 1, 아니면 0. - 노드 이슬롯 에서데이터를수신하면이값은 1, 아니면 0. - 노드 의이웃노드가슬롯 에서데이터를전송하면이값은 1, 아니면 0. 네트워크내의모든노드는주기적으로위의 3가지정보를교환함으로써서로의슬롯할당정보를알수있다. 각노드는슬롯을할당할때,, 및 값이 '0' 인슬롯을선택하여슬롯을할당하고슬롯할당이완료되면해당값들은 '1' 로설정한다. 노드는자신의이웃노드로부터비컨을수신할때마다자신의, 및 정보를업데이트한다. 처리율이높고패킷전송지연또한작아서효율적이다. 그러나, 무선센서네트워크와같은다중홉환경에서는중계노드가두개이상의인바운드링크와하나의아웃바운드링크 (outbound link) 를가지기때문에큐잉지연이발생하며소스노드와목적지노드사이의홉이증가하면할수록종단간패킷전송지연이증가한다. 이때, 인바운드링크란임의의노드가존재할때그노드와그노드에게패킷을전송할노드들사이의모든링크를의미하며, 아웃바운드링크란임의의노드가존재할때그노드와그노드가패킷을전송할모든노드들사이의링크를의미한다. 일반적으로무선센서네트워크는한 1개이상의인바운드링크가존재하고 1개의아웃바운드링크가존재한다. 그림 2는인바운드 (inbound)/ 아웃바운드링크의예를나타내고그림 3 은무선센서네트워크에서큐잉지연이발생하는네트워크구성의예이다. 그림 3에서노드 3과노드 8은두개의인바운드링크를가지고있고, 노드 4, 노드 6, 노드 7 및노드 SINK는하나의인바운드링크를가지고있다. 또한노드 SINK를제외한모든노드는하나의아웃바운드링크를가지고있다. 우선, 네트워크에서 minimum length schedule를이용하여슬롯을할당한다고가정하자. 또한, 그림 3의 Queueing point 1에서, 노드 1과노드 2는각각첫번째슬롯과두번째슬롯에서노드 3에게패킷을전송하고, 노드 3은노드 4에게 3 번째슬롯에서패킷을전송한다고가정하자. 만일 Ⅳ. 다중홉지연요인 본장에서는무선센서네트워크에서다중홉으로패킷을전송할때발생하는두가지지연요인들을설명한다. 우선임의의 Relay Node가두개이상의인바운드링크 (inbound link) 를가지고있을때발생하는큐잉지연을설명한다. 또한, 각노드가플로우내의슬롯을임의로할당할때발생하는랜덤링크스케줄링에의한지연을설명한다. 4.1. 큐잉지연무선센서네트워크에서기존논문 [1]-[4] 들의목적은네트워크내의노드가가능한한작은프레임크기를갖도록하기위하여슬롯을할당하는것이다. Minimum length schedule은단일홉통신에서 그림 3. 큐잉지연이발생하는네트워크구성 Fig. 3. Example network where queueing delay occurs 패킷이각프레임의시작과함께생성이된다고가정하면, 노드 3은 3번째슬롯의시작시점에서노드 1과노드 2로부터두개의패킷을수신한다. 그 879
한국통신학회논문지 '12-10 Vol.37A No.10 러나, 노드 3의아웃바운드링크가하나이고매프레임마다노드 3은노드 4에게슬롯 3에서패킷을전송하기때문에, 각노드가 FIFO(first in frist out) 큐를사용한다고가정하면, 노드 2로부터전송된패킷은현재프레임에서전송되지못하고다음프레임에서전송되어야한다. 직관적으로, 그림 3의 Queueing point 1에서노드 3의큐잉지연을해결할수있는방법은, 동일한프레임내에서노드 1 과노드 2가패킷을발생시키지않도록하는것이다. 즉, 첫번째프레임에서노드 1이패킷을생성하고두번째프레임에서노드 2가패킷을생성하면노드 3이노드 4에게두노드로부터수신된패킷을전송할때큐잉지연이발생하지않는다. 그러나, 이러한방식으로 Queueing point 1에서는큐잉지연을해결할수있지만, Queueing point 2에서또다른큐잉지연이발생할수있다. Minimum length schedule은종단간홉수가 2 홉이상이면큐잉지연이발생할수있고, 임의의중계노드에서인바운드링크의개수가많을수록또는소스노드에서생성되는패킷의수가많을수록큐잉지연에의한종단간패킷전송지연은증가하게된다. 따라서, 지연에민감한정보전송을목적으로하는무선센서네트워크에서는정보의 QoS를보장하지못할수도있다. 4.2. 랜덤링크스케줄링에의한지연본절에서는랜덤링크스케줄링과순차적링크스케줄링을설명하고, 두스케줄링방식의평가지표로써프레임지연을정의한다. 또한, 랜덤링크스케줄링이종단간지연에미치는영향을평가하기위하여랜덤링크스케줄링에의한종단간패킷전송지연을분석한다. 4.2.1. 랜덤및순차적링크스케줄링다중홉환경을특징으로하는무선센서네트워크는앞절에서설명한큐잉지연뿐만아니라한플로우에서할당된슬롯의순서가순차적이지못할경우추가적인패킷전송지연을경험할수있다. 그림 4는랜덤링크스케줄링과순차적링크스케줄링의예를보여준다. 그림 4( 가 ) 에서,,, 및 는한플로우에 4개의노드가존재한다는것을의미한다. 이때, 은소스노드, 및 은 Relay Node 는목적지노드를의미한다., 및 는각노드간링크를의미한다. 그림 4( 나 ) 처 ( 가 ) 4 개의노드로구성된네트워크 (A) Four-node network ( 나 ) 랜덤링크스케줄링을이용한패킷전송의예 (B) Example of packet transmission by random link scheduling ( 다 ) 순차적링크스케줄링을이용한패킷전송의예 (C) Example of packet transmission by random link scheduling 그림 4. 랜덤 / 순차적링크스케줄링을이용한패킷전송의예 Fig. 4. Examples of packet transmission by random/sequential link scheduling (i-1) th frame Packet arrival 0.5T M (S) p1-p2 i th frame TM (i+f h-1) th frame (D) (F h-1)t M 0.5T M TM pq-1-pq 그림 5. 랜덤링크스케줄링의지연요소 Fig. 5. Delay components of random link scheduling 럼임의의플로우에대한슬롯할당순서가 이라고가정하자. 소스노드 은 에대한슬롯할당이 이후에되었기때문에, 번째프레임에서패킷 은 까지밖에전송되지못한다. 결국, 패킷 은 번째프레임이되어야 까지전송이될수있다. 소스노드가목적지노드에게패킷한개를전송하기위해필요한프레임의개수를 프레임지연 ' 으로정의하면, 이경우의프레임지연은 2' 이다. 그러나, 그림 4( 다 ) 에서처럼, 만일 순으로슬롯이할당된다면 는 번째프레임에서패킷 을수신할수있다. 이때프레임지연은 '1' 이다. 따라서, 한플로우에대한슬롯할당을수행할때각링크에대한슬롯할당이랜덤할경우프레임지연이증가되어종단간패킷전송지연시간에큰영향을줄수있다. 4.2.2. 랜덤링크스케줄링에의한지연분석 본논문에서는, 랜덤링크스케줄링에의한종단간패킷전송지연을수학적으로분석하기위하여모든소스노드및목적지노드쌍 (pair) 사이의트 T time 880
논문 / 무선센서네트워크에서지연에민감한정보의다중홉전송기법 및 이다. 그러므로, 소스노드와목적지노드사이의홉수가 3일때의프레임지연 은 이다. 모든홉 ( ) 수에대하여프레임지연을나타내면식 (2) 와같다. 그림 6. 제안한다중홉전송기법을위한용어의예 Fig. 6. Some terminologies for proposed multihop transmission scheme. 래픽플로우는균등하고새로운패킷도착의프로세스는서로독립적이라고가정한다. 따라서, 본논문에서는한노드의특성에중점을두어종단간패킷전송지연분석을진행한다. 매프레임마다임의의슬롯에서패킷이도착한다고가정하면, 하나의패킷에의한종단간패킷전송지연은다음과같이 3가지요소로정의될수있다. ⑴ 한프레임내에서패킷의도착시간과그프레임의끝사이의시간. ⑵ 소스노드에서목적지노드까지하나의패킷을전송하기위해반복된프레임의수. ⑶ 하나의패킷을전송할때마지막프레임의시작시점과목적지노드에서해당패킷의수신시점사이의시간. 그림 5는랜덤링크스케줄링의종단간패킷전송지연요소를나타낸다. 먼저, 모든프레임길이가동일하고패킷이한프레임내에서임의로도착한다고가정하면, 첫번째구성요소는 이다. 이때, 은하나의프레임크기를의미한다. 다음으로한프레임내에서목적지노드의슬롯할당이랜덤하게수행된다면세번째구성요소의값은 이다. 이때, 는단위슬롯크기를의미한다. 마지막으로평균프레임지연 는식 (1) 과같이계산될수있다.. (1) 증명 : 슬롯할당이랜덤하게수행되고홉 ( ) 수가 3이면, 랜덤하게할당될수있는모든경우의수는 6( ) 이다. 모든경우의수에대하여프레임지연을나열하면프레임내에서각링크의할당순서에따라, (2) 따라서, 하나의패킷에의한종단간패킷전송지연시간 는식 (3) 과같이나타낼수있다. (3) Ⅴ. 제안하는다중홉전송기법 본절에서는무선센서네트워크에서발생할수있는두가지지연요인을해결하기위한순차적스케줄링기법을제안한다. 먼저, 네트워크내에존재하는모든노드의시간동기가일치한다고가정한다. 제안하는순차적스케줄링기법의두가지주요특징은다음과같다. 첫째, 제안하는스케줄링기법은아웃바운드링크로나가는플로우마다서로다른슬롯을할당한다. 이러한개별적인슬롯할당은프레임크기가증가한다는단점이있지만반대로큐잉지연을제거할수있다는장점이있다. 두번째, 제안하는스케줄링기법은라우팅과정에서라우팅테이블정보를기반으로목적지노드부터슬롯을할당하여한플로우내에있는노드들이그림 4(C) 의예와같이순차적으로슬롯을할당할수있도록해준다. 이러한슬롯할당은랜덤링크스케줄링에서발생하는프레임지연을최소화시켜종단간패킷전송지연을줄일수있다. 먼저, 초기프레임크기 ( 슬롯의수 ) 는네트워크내의모든노드가슬롯을할당할수있을정도로충분이크다고가정한다. 본논문에서는다중홉슬롯할당과정을수행하기위하여 SA-REQ(slot assignment request) 패킷과 SA-RES(slot assignment response) 패킷이이용되며다음과같은용어들이사용된다. - Froward/Reverse Path : 목적지노드 / 소스노드로의패스. - TN/RN : 할당된슬롯에서한노드와그노드의이웃노드사이에서전송노드 / 수신노드. 881
한국통신학회논문지 '12-10 Vol.37A No.10 Algorithm 1. Slot assignment in a destination node 1 if k = q then 2 p k reserves the slots for both p k-1and p k as a RN. 3 p k sends the SA-RES packet with Assigned Slot Index to p k-1. end if Algorithm 2. Slot assignment in an intermediate/a source node 1 if k = 1 then 2 Based on Assigned Slot Index, p 1 reserves the slots for both p 1 and p 2 as a TN. 3 p 1 begins to send data in the assigned slots. 4 else if 1< k< q then 5 Based on Assigned Slot Index, p k reserves the slots for both p k and p k+1 as a TN. 6 p k reserves the slots for both p k-1 and p k as a RN. 7 p k sends the SA-RES packet with Assigned Slot Index to p k-1. end if - Assigned Slot Index : DCH에서할당된슬롯인덱스. - Next Node : 임의의노드가 Reverse Path에서 SA-RES 패킷을전송할이웃노드, 또는 Forward Path에서데이터패킷을전송할이웃노드. - Previous Node : Forward Path에서자신에게 SA-REQ 패킷을전송한이웃노드. 그림 6은앞서언급한용어들중 Forward/Reverse Path에대한개념도를나타낸다. 예를들어그림 6의 Forward Path에서 일때, 임의의노드 에대해서 은 의 Previous Node이고 은 의 Next Node이다. 다중홉슬롯할당과정을설명하면다음과같다. 만일소스노드가전송할패킷이있으면 SA-REQ 패킷을브로드캐스팅 (broadcasting) 한다. SA-REQ 패킷전송방식은 IEEE 802.11s에서사용되는 PREQ(path request) 패킷의전송방식과동일하다 [10]. 만일임의의노드가 SA-REQ 패킷을수신하면, Reverse Path 테이블을생성한후해당패킷을브로드캐스팅한다. Reverse Path 테이블은소스노드주소, 목적지노드주소, Previous Node 주소를포함한다. Reverse Path 테이블에포함된 Previous Node 주소는노드가추후 Reverse Path로 SA-RES 패킷을전송할때 Next Node 주소로활용된다. 임의의 Relay Node는하나이상의 Previous Node가존재 할수있는데, Relay Node는자신에게가장먼저 SA-REQ 패킷을전송한 Previous Node의주소를추후 SA-RES 패킷을전송할때의 Next Node 주소로설정한다. SA-RES 패킷은 Assigned Slot Index와 Next Node 주소를포함한다. Algorithm 1 은 Forward Path에서임의의목적지노드가 SA-REQ 패킷을수신하였을때의다중홉슬롯할당과정을나타낸다. Algorithm 2는 Reverse Path 에서임의의소스노드또는 Relay Node가 SA-RES{Next Node 주소, Assigned Slot Index} 패킷을수신하였을때의다중홉슬롯할당과정을나타낸다. 임의의소스노드또는 Relay Node는이웃노드로부터 SA-RES 패킷을수신하면 Algorithm 2를실행하여슬롯을예약한다. 제안한슬롯할당방식은목적지노드가프레임내에서가용한슬롯중가능한한오른쪽슬롯을먼저할당하고, 이후 SA-RES 패킷을수신한노드들은 SA-RES 패킷내의 Assigned Slot Index 보다왼쪽에위치한슬롯을할당함으로써, 소스노드부터목적지노드로의슬롯할당이순차적이되도록한다. Ⅵ. 성능평가본장에서는제안한순차적스케줄링기법의성능을 OPNET 모의실험을통하여평가하고, 랜덤링크스케줄링방식과종단간패킷전송지연의관점에서비교한다. 6.1. 모의실험시나리오본절에서는제안한순차적스케줄링기법과기존의랜덤스케줄링기법의성능을평가하기위한모의실험시나리오를설명한다. 네트워크크기는가로, 세로각각 200미터이며총 100개의노드가임의로분포된다. 네트워크의밀집도 (density) 를변경하기위하여노드의통신거리를 60 미터에서 25 미터까지가변시킨다. 노드의통신거리가감소하면, 간섭노드의수가감소하고결과적으로프레임크기가작아진다. 표 1은통신거리에따른프레임크기를나타낸다. 네트워크내의모든노드가일정시간동한다중홉슬롯과정을모두완료하면, 하나의패킷을생성하여할당된슬롯에서패킷을전송한다. 만일 Relay Node가임의의플로우에대해 Previous Node로부터패킷을수신하면, 해당플로우를위해할당한슬롯에서수신한패킷을 Next Node에게전송한다. 본논문에서는, 랜덤 / 순차적스 882
논문 / 무선센서네트워크에서지연에민감한정보의다중홉전송기법 케줄링기법의성능평가를위하여 5종류의서로다른밀집도와 10개의서로다른랜덤한토폴로지를생성하여모의실험을수행하고, 도출된결과의평균값을성능지표로정한다. 6.2. 성능평가결과그림 7은소스노드와목적지노드사이의평균홉수가증가함에따라, 제안하는스케줄링기법과기존의랜덤스케줄링기법의종단간패킷전송지연을나타낸다. 그림 7에서 은프레임크기를의미한다. 모의실험결과에따르면, 평균홉수가 2.02 일때제안한기법이랜덤스케줄링기법보다더큰종단간평균지연을보임을알수있다. 제안한스케줄링기법은다중홉슬롯할당과정을수행할때순차적인슬롯할당을위해프레임의가장오른쪽에존재하는빈슬롯을우선적으로할당한다. 따라서, 평균홉수가 2.02홉일때랜덤스케줄링에의한지연영향이작아랜덤스케줄링기법의지연성능이더우수함을알수있다. 그러나, 평균홉수가증가함에따라랜덤스케줄링에의한지연이증가하기때문에제안하는스케줄링기법의종단간패킷전송지연성능이더우수함을알수있다. 한편, 그림 7에서평균홉수가증가함에따라제안하는스케줄링기법의종단간패킷전송지연이감소하는특징을보임을알수있다. 본논문에서는통신거리를감소시킴으로써소스노드와목적지노드사이의평균홉수를증가시킨다. 통신거리가감소하면노드의평균이웃노드의수가감소한다. 따라서, 간섭을주는노드의수가감소하게되므로프레임크기가감소한다. 랜덤스케줄링기법을사용할때도프레임크기가감소를하지만, 랜덤스케줄링기법은평균홉수가증가함에따라큐잉지연과랜덤스케줄링에의한지연영향이훨씬더크기때문에종단간패킷전송지연이증가하는특성을보인다. Ⅶ. 결론본논문에서는무선센서네트워크에서발생가능한두가지지연요인을해결하기위하여, 지연에민감한이벤트정보의다중홉전송을위한순차적링크스케줄링기법을제안하였다. 제안한기법은큐잉지연을해결하기위하여인바운드링크에존 Average end-to-end delay(slots) 450 400 350 300 250 200 150 100 Random link schedule(analysis) Random link schedule(simulation) Proposed sequential link schedule(simulation) N =164 N=156 N=136 N=122 2 2.66 3 4 4.75 5 6 6.3 Average number of hops N=115 그림 7. 평균홉수에따른종단간패킷전송지연 Fig. 7. End-to-end delay vs. average number of hops 표 1. 통신거리에따른프레임크기 Table 1. Frame sizes for communication ranges. Communication range (meters) 60 50 40 30 25 Avg. hop distance 2.02 2.66 4.1 4.75 6.3 One-hop degree 22.6 16.8 11.5 6.6 4.5 Frame size 164 156 136 122 115 재하는플로우개수만큼슬롯을할당하고, 랜덤스케줄링에의한지연을해결하기위하여라우팅정보를이용한다중홉슬롯할당과정을수행한다. 성능분석결과, 제안하는순차적스케줄링방식의종단간패킷전송은한프레임내에서가능하지만, 랜덤링크스케줄링기법은평균홉수가증가함에따라종단간패킷전송지연이증가함을알수있었다. 소스노드와목적지노드사이의평균홉수가 2.66, 4.1, 4.75, 및 6.3일때제안하는순차적스케줄링기법은랜덤스케줄링기법에비해종단간패킷전송지연이각각 22%, 36%, 48%, 및 55% 감소함을알수있었다. References [1] S. Gandham, M. Dawande, and R. Prakash, "Link scheduling in sensor networks: distributed edge coloring revisited," in Proc. INFOCOM, pp. 2492-2501, Mar. 2005. [2] A. Panconesi and A. Srinivasan, "Improved distributed algorithms for coloring and Network decomposition problems," in Proc. ACM Symposium on Theory of Computing, pp. 581-592, May 1992. [3] D. A. Grable and A. Panconesi, "Nearly optimal 883
한국통신학회논문지 '12-10 Vol.37A No.10 distributed edge colouring in O(log log n) rounds," in Proc. ACM SIAM symposium on Discrete algorithms, Jan. 1997. [4] K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, "Protocols for selforganization of a wireless sensor network," IEEE Personal Communications, vol. 7, no. 5, pp. 16-27, 2000. [5] J. Misra and D. Gries, "A constructive proof of vizing s theorem," Information Processing Letter, vol. 41, pp. 131-133, Mar. 1992. [6] M. V. Madhav, A. Panconesi, and L. D. Risinger, "An experimental study of a simple, distributed edge coloring algorithm," in Proc. 12th annual ACM symposium on Parallel algorithms and architectures, pp. 166-175, Oct. 2000. [7] S. Ramanathan, "A unified framework and algorithm for channel assignment in wireless networks," Wireless Networks, pp. 81-94, Apr. 1999. [8] P. Djukic and S. Valaee, "Delay aware link scheduling for multi-hop TDMA wireless networks," IEEE/ACM Trans. Netw., vol. 17, no. 3, Jun. 2009, pp. 870-883. [9] M. Trung and J. H. Mo, "A multichannel TDMA MAC protocol to reduce end-to-end delay in wireless mesh networks," ETRI Journal, vol. 32, no. 5, pp. 819-822, Oct. 2010. [10] IEEE 802.11s. Draft Amendment: ESS Mesh Networking, Nov. 2006. 차재룡 (Jae-Ryong Cha) 2004년아주대학교전자공학부졸업 2006년아주대학교전자공학부석사 2006년 3월~현재아주대학교전자공학과박사과정 < 관심분야 > RIFD, 네트워크코딩, WLAN, 무선망 QoS, Ad-hoc, WMN, WSN 등. 김재현 (Jae-Hyun Kim) 1987년~1996년한양대학교전산과학사및석 / 박사졸업 1997년~1998년미국UCLA 전기전자과박사후연수 1998년~2003년 Bell Labs, Performance Modeling and QoS Management Group, 연구원 2003년~현재아주대학교전자공학부교수 < 관심분야 > 무선인터넷 QoS, MAC 프로토콜, IEEE 802.11/15/16/20, 3GPP, 국방전술네트워크등. 884