미비사항 : 7P 오른쪽끝부분아래 < 표 4> 로돼있는데 < 표 4> 는 8P 있음. 8j1-067R 무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 1 DOI: 10.3745/KIPSTA.2009.16-A.3.1 무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 이좌형 조영태 정인범 요 약 무선센서네트워크에서데이터수집을담당하는싱크를일정한장소에고정시켜놓는것은데이터수집의안정성을보장할수있지만싱크노드주변으로집중되는네트워크트래픽이에너지를과도하게소모시켜네트워크의수명을단축시키는문제점이있다. 이러한문제를해결하기위해싱크에이동성을부여하여싱크주변노드로집중되는네트워크트래픽을분산시키는모바일싱크기법이새로운대안으로제시되고있다. 하지만모바일싱크를사용하면네트워크트래픽의집중화문제는해결할수있으나이동성으로인하여데이터수집의안정성이떨어지는문제점이발생할수있다. 데이터를안정적으로수집하기위해서는센서노드와모바일싱크간통신가능한시간안에각센서노드들로부터균등하게데이터를수집할수있는데이터수집스케줄링에대한고려가필요하다. 본논문에서는모바일싱크에기반한센서네트워크에서센서노드들로부터균등하게데이터를수집하기위한센서노드의가용성기반스케줄링기법인 ASF(Availability based Scheduling scheme for Fair data collection) 를제안한다. ASF는모바일싱크의이동경로와센서노드간의거리를기준으로판단되는센서노드의가용성에따라스케줄링의우선순위와타임슬롯을할당한다. 모바일싱크의이동경로와멀리떨어져있어데이터수집의가용성이낮은센서노드에높은우선순위와긴타임슬롯을할당함으로써노드간데이터수집의균등성을보장한다. 실험을통하여제안된기법이기존의다른기법들에비해무선센서노드들로부터의데이터수집에있어서가장균등하게데이터를수집함을보인다. 키워드 : 모바일싱크, 무선센서네트워크, 통신에러율, ASF Availability based Scheduling Scheme for Fair Data Collection with Mobile Sink in Wireless Sensor Networks Joa Hyoung Lee Young Tae Jo In Bum Jung ABSTRACT With fixed sinks, the network stability could be improved while the network life time could be decreased by the rapid energy dissipation around the fixed sink because of the concentrated network traffic from sensor nodes to the fixed sink in wireless sensor network. To address this problem, mobile sinks, which decentralize the network traffic, has received a lot of attention from many researchers recently. Since a mobile sink has a limited period to communicate with each sensor nodes, it is necessary for a scheduling algorithm to provide the fairness of data collection from each sensor nodes. In the paper, we propose the new scheduling algorithm, ASF(Availability based Scheduling scheme for Fair data collection), for the fair data collection by a mobile in the sensor networks. The ASF takes account of the distance between each sensor nodes and the mobile sink as scheduling metric, as well as the amount of collected data from each sensor nodes. Experiment results shows that the ASF improves the fairness of data collection among the sensor nodes, comparing to existing algorithm. Keywords : Mobile Sink, Wireless Sensor Network, Communication Error, ASF 1. 서론 1) 최근 MEMS, 마이크로프로세서그리고무선통신기술의 준회원 : 강원대학교컴퓨터정보통신공학과박사수료 준회원 : 강원대학교컴퓨터정보통신공학과석사과정 종신회원 : 강원대학교컴퓨터정보통신공학전공교수논문접수 : 2008 년 11 월 6 일수정일 :1 차 2009 년 1 월 22 일, 2 차 2009 년 2 월 19 일심사완료 : 2009 년 3 월 1 일 발전으로센서노드들을이용하여넓은지역에걸쳐정확한정보를얻고자하는센서네트워크에대한연구가활발히진행되고있다 [1]. 이러한센서네트워크는일상환경이나재난현장과같은특정환경등에서다양한정보를수집하는것을목적으로한다 [2, 3, 4]. 센서네트워크에는주변환경으로부터데이터를수집하는일반센서노드와측정된데이터를모으는하나이상의싱크로구성된다. 이러한환경에서센서노드들이수집한정보를싱크로효율적으로전송하
2 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) 는방법을매우중요한연구과제들중하나이다. 초기의센서네트워크에관한연구에서는고정된싱크를위한라우팅기법이연구되었다. 하지만고정싱크를사용한센서네트워크는싱크의주변에배치된센서노드의에너지소모가극심해지는문제가있다. ( 그림 1) 의 (a) 와같이고정싱크주변의센서노드는자신이수집한데이터뿐만아니라싱크에서멀리떨어져있는센서노드들이수집한데이터까지모두싱크로전송하여야하기때문이다. 싱크주변센서노드들이전송하는데이터양이증가함에비례하여에너지소모가급증하면싱크주변센서노드들부터에너지가빠르게소모된다. 이러한에너지소모는싱크로데이터를전송할수없게만들고, 이는전체센서네트워크의수명을짧아지게만드는원인이된다. 이러한문제를해결하려면싱크주변센서노드의에너지소모를다른센서노드들에게분산시켜야한다. 이를위해최근모바일싱크를적용한에너지소모분산연구가활발히진행되고있다 [5, 6]. ( 그림 1) 의 (b) 와같이모바일싱크는각센서노드로부터데이터를수집하는싱크가이동하는것으로센서네트워크전체를이동하며각센서노드들로부터데이터를수집하는노드를말한다. 모바일싱크는이동중각센서노드로부터데이터를균등하게수집해야한다. 일부의센서노드로부터는많은데이터를수신하고다른센서노드로부터는데이터를전혀수신하지않는다면해당센서가위치한지역의정보는얻을수없고센서네트워크를이용한환경모니터링과같은어플리케이션에서는큰문제로작용할수있다. 이러한문제점을해결하기위하여모든센서노드들로부터균등하게데이터를수집하기위한데이터수집스케줄링이필요하다. 모바일싱크를이용하여데이터를수집하는경우센서노드가모바일싱크의통신범위안에머무르는시간이제한되어있고센서노드의위치에따라모바일싱크와통신가능한최대시간도모두다르다. 또한모바일싱크가지속적으로이동하기때문에센서노드와모바일싱크간통신에러율도시시각각으로변한다. 이러한환경에서노드별로균등하게데이터를수집하기위해서는노드별통신순서와시간을효율적으로스케줄링할필요가있다. 통신에러율이높고모바일싱크와통신가능한시간이짧은센서노드는높은우선순위와긴시간을할당하여데이터를수신해야할것이다. 반면모바일싱크와가까워에러율이낮고모바일싱 (a) 고정싱크 (b) 모바일싱크 ( 그림 1) 센서네트워크구성도 크와통신가능한시간이긴센서노드는짧은시간동안만데이터를수신해도될것이다. 본논문에서는이러한모바일싱크의가변적인통신환경을고려하여센서노드로부터균등하게데이터수집을할수있는센서노드의가용성기반스케줄링기법인 ASF(Availability based Scheduling scheme for Fair data collection) 를제안한다. ASF는모바일싱크의이동경로와센서노드사이의거리값을센서노드의가용성으로판단하여가용성에따라스케줄링의우선순위와타임슬롯할당을조절한다. 모바일싱크의이동경로에서거리가멀어에러율이높은센서노드를고려하여우선순위선정에반영하고동적으로타임슬롯을할당한다. 또한센서노드로부터이전에전송된데이터를가중치로적용하여중복전송을방지하여균등한데이터수집을보장한다. ASF 스케줄링은우선순위선정과, 타임슬롯할당부분으로구성된다. 우선순위선정은모바일싱크의통신범위안에있는센서노드중가장적은데이터를모바일싱크로전송하였고모바일싱크에게데이터를전송할수있는확률이가장적어가용성이제일낮은센서노드를우선적으로선정한다. 이러한센서노드는모바일싱크로데이터를전송할수있는기회가적기때문에우선적으로선정하여균등한데이터를수신하기위해서이다. 선정된센서노드는타임슬롯할당을통해모바일싱크로데이터를전송할수있는시간을부여받는다. 센서노드는부여받은시간동안만모바일싱크로데이터를전송할수있다. 본논문의구성은다음과같다. 2장에서는균등성을위한기존의스케줄링기법과모바일싱크를사용한센서네트워크의연구동향을살펴본다. 3장에서는본논문에서사용된센서네트워크의배치모델과통신모델, 모바일싱크의이동모델에대해설명한다. 4장에서는모바일싱크와센서노드간통신특징에대해알아보고 5장에서는본논문에서제안하는균등한데이터수집을위한스케줄링기법인 ASF 에대해설명한다. 6장에서는 ASF의모의실험과성능평가를기술하고 7장에서는결론및향후계획을제시한다. 2. 관련연구 2.1 스케줄링기법기존의스케줄링기법중네트워크사용자에게균등성을제공하는방법에는여러가지가있다. GPS(Generalized Processor Sharing) 알고리즘은라운드로빈형식으로패킷을보내는알고리즘이다 [7]. 다만패킷을매우작은양으로나누어큐마다동등하게보내기때문에, 이론적으로이상적인균등성을제공하지만, 실현될수없는단점이있다. 이를보완한패킷단위스케줄링기법으로 WFQ(Weighted Fair Queuing) 알고리즘이제시되었다 [8]. 이스케줄링은 PGPS(packet-bypacket GPS) 로도알려져있다. 이알고리즘은각각의큐에가중치를정의하고해당가중치가높은큐부터서비스를제공한다. 각큐간의균등성을보장하기위한시스템에서많이활용되고있는스케줄링기법이다.
무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 3 큐잉정책을이용한알고리즘과는달리라운드로빈정책을이용한스케줄링이있다. PBRR(packet Based Round Robin) 알고리즘은패킷단위로큐들을순서대로돌아가면서서비스한다. 구현이용이하고같은패킷사이즈의전송에는균등성이보장되지만다양한패킷사이즈의전송에는큐들간의데이터처리에대한균등성보장이힘들다. 2.2 모바일싱크센서네트워크에모바일싱크를적용시킨연구분야는크게센싱데이터를모바일싱크로전송하기위한라우팅기법연구와모바일싱크의움직임제어연구를들수있다. 기존의고정된싱크로데이터를전송하는라우팅기법은모바일싱크에적용하기힘들다. 모바일싱크는지속적으로움직이고센서노드에서데이터를전송해야할경로도바뀌게되며모바일싱크의이동에따라각센서노드의라우팅테이블을변경해야하기때문이다. 지속적인라우팅테이블의변경은센서노드의부하를증가시키게되고이것은센서노드의에너지소모증가로이어진다. 이러한라우팅문제를해결하기위해모바일싱크에적합한라우팅기법또한최근활발히연구되고있다 [9, 10]. 센서네트워크에모바일싱크를적용하기위해서는모바일싱크의움직임을컨트롤하는방법이센서네트워크의성능을향상시키기위한중요한요소로작용한다. 각센서노드의상태에따라모바일싱크의속도나방향을제어함으로써센서네트워크의상태에적응적으로데이터를전송받을수있다 [11]. 만약각센서노드마다모바일싱크로전송해야하는데이터양이다르다면모바일싱크에게전송해야할데이터양이많은센서노드가분포된곳에서는오랜시간을할당하여데이터를수집하고데이터양이적은센서노드가분포된곳에서는짧은시간을할당하여데이터를수집하면똑같은시간을할당한경우보다전체데이터수집시간을단축시킬수있다. 이는일정한조건하에서빠른데이터수집을해야하는시스템에서는보다효율적데이터수집이가능하게한다. [10] 에서는큐잉이론을이용하여모바일싱크에서의데이터수집에관한연구를진행하였다. 이연구에서는모바일싱크의범위에들어오는노드들을큐잉모델에따라처리하는개념을도입하였다. 정립된큐잉모델을기반으로센서노드로부터모든데이터를수신하기위한센서노드의 RF 라디오범위를제시하였다. 이연구에서는하나의센서노드가가지고있는모든데이터를수신하는것이중요하며데이터를모두수신하지못하고범위밖으로밀려나는것은데이터가손실되는것으로간주하고있다. 하지만이럴경우일부의노드로부터는데이터를전혀수신하지못하는문제점이발생하여노드에서의센싱작업이무의미해지는결과를초래할수있다. 또한모바일싱크의통신범위에있는노드들중에서어떠한노드로부터데이터를수신할것인가라는스케줄링에관하여서는언급하지않고있다. 이러한문제점을해결하기 위하여본논문에서는노드별로균등한데이터를수신할수있도록하여노드들이센싱한데이터를최대한이용할수있도록하는것을목표로하고있다. 또한여러노드들이모바일싱크의통신범위에속하는경우스케줄링기법에따라성능에많은차이가날수있으므로이에대한연구가이루어져야한다. 모바일싱크에관한이전논문 [14] 에서우리는센서네트워크에서의균등한데이터수집에관하여분석하고이를위한데이터가중치기반스케줄링기법을제안하였다. 하지만 [14] 논문에서는노드간통신에에러가없는것으로가정하여현실에적용하기에미흡한점이있어본논문에서노드간통신에발생할수있는에러를고려한스케줄링기법을제안하고자한다. 3. 시스템모델 이장에서는본논문에서사용된센서네트워크동작환경과모바일싱크에대해설명한다. 모바일싱크와센서노드의배치상태와모바일싱크가센서네트워크에서이동하는패턴에대해설명하고모바일싱크와센서노드간통신모델과큐잉모델에대해알아본다. 전체센서노드는독립적이고랜덤하게분포하며평면에배치된다. 센서노드의전송데이터양은노드별로동일하다. 모바일싱크와센서노드간데이터전송률또한동일하다. 모바일싱크는랜덤하게분포된센서들사이로고정된직선경로를가진다. 본논문에서사용되는모바일싱크의이동경로는다음과같은특징을가진다. 모바일싱크는연속적으로움직인다. 모바일싱크의이동경로는이동중수정되지않는다. 모바일싱크의수는단일싱크로이루어진다. 모바일싱크와센서노드간네트워크연결모델은다음과같은특징을가진다. 모바일싱크의이동경로상에존재하는모든센서노드는모바일싱크의통신범위안에들수있다. 모바일싱크와센서노드는싱글홉으로통신한다. 노드에서전송하는라디오의전파모델로는 Shadowing Model을가정한다. Shadowing model은전파가여러경로로전달되기때문에특정거리에서수신하는전파의세기가임의의변수가되는 Fading effect를반영한다. Shadowing model 은크게두부분으로구성된다. 첫번째부분은 d만큼떨어진거리에서의평균수신전파세기를예측하는경로손실모델 (Path loss model) 로서초기기준값인 d0 와의상대적인값을아래와같이계산한다 [15, 16].
4 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) < 표 1> 환경에따른경로손실지수의예 Environment β Outdoor In building Free Space 2 Shadowed urban area 2.7 to 5 Line-of-sight 1.6 to 1.8 Obstructed 4 to 6 β는경로손실지수 (Path loss exponent) 로서주로필드상에서의실험으로구해지며일반적으로 < 표 1> 에명시된값을사용한다. Pr(d0) 는 Free space상에서거리에따른수신전파세기를계산하는다음수식으로구할수있다. ( 그림 2) 거리에따른신호세기와 SNR 에따른패킷수신성공율 Pt는전송시전파세기를나타내며, Gt와 Gr은각각전송자와수신자의안테나이득을, L은시스템손실을나타내고 λ는전파의파장을나타낸다. 일반적으로 Gt와 Gr그리고 L 값은 1로설정된다. 경로손실은일반적으로 db로측정되며위의경로손실모델은아래와같이정리될수있다. Shadowing model의두번째부분은특정한거리에서수신된전파세기의변화를반영하는 log-normal random variable을적용하는것이다. log-normal random variable은가우시안분포를따른다. 전체적인 shadowing model은아래수식과같다. Xdb는평균값과표준편차를 0으로하는가우시안랜덤변수로서 shadowing deviation이라불리며필드상에서의실험으로구해진값을사용할수있다 < 표 2>. < 표 2> 환경에따른 shadowing deviation예 Environment XdB Outdoor 4 to 12 Office, hard partition 7 Office, soft partition 9.6 Factory, line-of-sight 3 to 6 Factory, obstructed 6.8 ( 그림 3) 노드간거리에따른통신에러율및패킷수신율 Shadowing model 에기반하여거리에따른신호세기와신호대잡음비 (SNR) 에따른패킷수신성공률을 ( 그림 2) 에간략히나타내었으며위에서설명한 shadowing model 에기반하여거리에따른패킷수신성공률과패킷수신에러율을 ( 그림 3) 에나타내었다. 경로손실지수인 β 는 2.0 으로, shadowing deviation 인 XdB 는 4 로하였으며기준거리인 d0 는 1 로하였다. [17]. ( 그림 2) 에 (A) 에서보듯이거리가길어질수록신호세기가급격히감소하는데 ( 그림 2) 의 (B) 에서 SNR 이감소하면패킷수신성공률도급격히감소하는것을볼수있다. ( 그림 3) 에서거리에따라패킷수신성공률이급격히감소하고패킷수신에러율이급격히증가하는것은 ( 그림 2) 에나타난거리에따른신호세기의변화에기반하는것을알수있다. 4. 모바일싱크의특성 모바일싱크는연속적으로이동하므로고정싱크를사용한센서네트워크보다다양한특성을가진다. 고정싱크를사용한센서네트워크에는싱크주변센서노드와통신할수있는시간이제한되어있지않다. 하지만모바일싱크는각각의센서노드와통신할수있는시간이제한되어있다. 또한모바일싱크의이동에의해센서노드와의통신거리가시시각각변하게되고이러한통신거리의변화는통신에러율및패킷수신율의변화를가져오는특징이있다. 4.1 제한된통신시간 ( 그림 4) 는모바일싱크와센서노드 A, B의관계를나타
무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 5 ( 그림 4) 모바일싱크와센서노드의경로 낸그림이다. 그림과같이모바일싱크는제한된통신범위를가지고있다. 따라서센서노드 A와 B는모바일싱크의통신범위안으로접근하는시점인 IN과통신범위밖으로벗어나는시점인 OUT 사이에서만통신이가능하다. 그외의시점에서는모바일싱크의통신범위가아니기때문에통신이불가능하다. 즉센서노드는모바일싱크가이동할때통신할수있는특정시간이있고그때반드시통신을해야한다. 만약통신을하지못한다면해당지역의정보를얻지못할것이고이러한결과는환경모니터링과같은어플리케이션에서는치명적오류로작용할수있다. 이러한제한된통신시간은모바일싱크의이동경로와센서노드간거리에따라변화하는또다른특징을가진다. 모바일싱크의통신범위는 ( 그림 4) 과같이원의형태를가지고있다. 따라서센서노드는모바일싱크의이동경로에서멀어질수록통신할수있는시간이짧아진다. ( 그림 4) 에서센서노드 A는센서노드 B보다모바일싱크의이동경로에서더멀리있기때문에모바일싱크와통신할수있는시간이더짧은것을볼수있다. 4.2 통신에러의변화모바일싱크는연속적으로움직이므로센서노드와싱크간통신거리가변하는특성이있다. 예를들어, ( 그림 5) 와같이센서노드 A와 B는모바일싱크의통신범위안으로들어오는시점인 IN에서가장긴통신거리를가진다. 이때모바일싱크가이동할수록센서노드 A와 B는모바일싱크와가까워진다. ( 그림 5) 의 (a) 와같이모바일싱크의바로위에위치할때가장짧은통신거리를가지게되고다시멀어지기시작하여 OUT시점에서다시 IN시점과같은가장긴통신거리를가진다. 통신거리가증가하면그만큼패킷수신율이감소하므로 ( 그림 5) 의 (b) 와같이패킷수신율은통신에러율의분포와반대로패킷수신율이증가하다가다시감소하는분포를그린다. ( 그림 5) 모바일싱크의이동에따른거리변화와패킷수신성공률변화 5. ASF(Availability based Scheduling scheme for Fair data collection) 모바일싱크기반센서네트워크를위한스케줄링은각센서노드에게균등한전송기회를부여할수있어야한다. 본논문에서는이러한요구사항을만족시키기위한균등한데이터전송스케줄링기법인 ASF를제안한다. ASF는모바일싱크의특징인제한된전송시간과통신에러에적응적으로각센서노드에게균등한전송기회를부여한다. ASF 스케줄링은우선순위선정과, 시간할당부분으로구 성된다. 우선순위선정은모바일싱크의통신범위안에있는센서노드중가장적은데이터를모바일싱크로전송하였고모바일싱크에게데이터를전송할수있는확률이가장적은센서노드를우선적으로선정한다. 이러한센서노드는모바일싱크로데이터를전송할수있는기회가적기때문에우선적으로선정하여균등하게데이터를수신하기위해서이다. 선정된센서노드는시간할당을통해모바일싱크로데이터를전송할수있는시간을부여받는다. 센서노드는부여받은시간동안만모바일싱크로데이터를전송할수있다. 5.1 우선순위선정모바일싱크는이동중자신의통신범위안에하나이상의센서노드를가지게될것이고이센서노드들중어느센서노드로부터데이터를전송받을지우선순위를선정해야한다. 우선순위선정시모바일싱크는현재자신의통신범위안에있는센서노드들에게균등한데이터전송기회를부여할수있어야한다. 이를위해 ASF는식 (1) 을이용한다.
6 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) (1) P : 우선순위 RD : 수신한데이터양 RA : 식 (1) 은 ASF 스케줄링에서우선순위를계산하는식으로 RA는해당센서노드와모바일싱크간패킷수신율의양이다. RA식의 은우선순위를계산하는시점의시각을의미하고 은센서노드가모바일싱크의통신범위를벗어나는시점의시각을말한다. 앞서 3장에서살펴보았듯이패킷수신성공률은라디오전파세기와연관이있기때문에본논문에서는 Shadowing model에기반하여패킷수신성공률을계산한다. 센서노드와모바일싱크간패킷수신율의양은해당센서노드가모바일싱크의통신범위밖으로벗어날시간동안의패킷수신율의적분을의미한다. RA는모바일싱크로데이터를전송할확률이가장낮은센서노드를선정하기위해사용된값이다. 센서노드는모바일싱크에서멀수록통신에러로인해데이터를전송할확률이낮아지는특징을가진다. 이러한특징을반영하기위해센서노드와모바일싱크간패킷수신율의양을사용한다. RD는해당센서노드가모바일싱크로전송한패킷의수를의미한다. RD의값을이용하는이유는이전에데이터를전송한센서노드보다전송하지못한센서노드에게우선권을부여하기위해서이다. 결과적으로식 (1) 은모바일싱크의통신범위안의센서노드중모바일싱크로데이터를가장적게전송하였고전송할확률이가장낮은센서노드를선정한다. ( 그림 6) 은모바일싱크와센서노드의구성도로모바일싱크는 MS1 위치에서 MS3 위치까지이동하고있다. MS1 위치일때는자신의통신범위안에센서노드가없지만 MS3 위치에서는자신의통신범위안에 A, B, C, D 4개의센서노드를가지고있다. ( 그림 7) 은모바일싱크가 ( 그림 6) 의 MS3 위치에있을때센서노드 A, B, C, D의패킷수신율과수신율의양을나타낸것이다. ( 그림 7) 의 은 time축에서모바일싱크가 MS3 위치에있을때의시각을의미하고 은각센서노 ( 그림 7) 패킷수신율의양 드가모바일싱크의통신범위밖으로벗어나는시각을말한다. A, B, C, D 노드가모바일싱크의통신범위안에머무를수있는시간은각각 AR, BR, CR, DR 이다. MS3 위치에서센서노드 A, B, C, D의패킷수신율의양인 RA는각포물선의적분값이되므로 ( 그림 7) 의 AD, BD, CD, DD 가된다. A 센서노드가패킷수신율의양이가장적으므로가장높은우선순위를가질수있고 B, D, C의순서로우선순위가정해질것이다. 하지만만약 A 센서노드가모바일싱크로전송한데이터가존재하여식 (1) 에의해계산된값이 B 센서노드보다크다면 B 센서노드가가장높은우선순위를가지게될것이다. 5.2 타임슬롯할당모바일싱크의통신범위안에있는센서노드중가장높은우선순위를가지는센서노드가선정되면해당센서노드에게데이터를전송할수있는타임슬롯을할당해주어야한다. 타임슬롯할당은선정된센서노드의통신에러율의양을고려하여할당된다. 에러율의양이많으면긴타임슬롯을할당하고에러율의양이적으면짧은타임슬롯을할당한다. 하지만통신에러율의양이많다고무조건긴타임슬롯을할당하는것은문제가있다. 모바일싱크의통신범위안에있는전체센서노드에게균등하게전송기회가부여될수있도록적절한타임슬롯할당이필요하다. 이를위해 ASF는식 (2) 의시간할당방식을이용한다. (2) T : 할당시간 RT : UT : 최대시간 ET : ( 그림 6) 모바일싱크와센서노드의구성도 식 (2) 에서 UT는센서노드에게할당될수있는최대시간을의미한다. 센서노드는 UT 시간보다긴시간동안데이터를전송할수없다. RT는 UT시간동안해당센서노
무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 7 ( 그림 9) 실험환경 ( 그림 8) 통신에러율의양드의통신에러율의양이다. RT의 은시간할당을계산하는시점의시각이고 는 에 UT를합한시각이다. ET는모바일싱크의통신범위안에있는센서노드전체의 RT 값을합한값이다. ET의 은시간할당을하는시각에모바일싱크의통신범위안에있는센서노드의수이다. ( 그림 8) 은모바일싱크가 ( 그림 4) 의 MS3 위치에있을때센서노드 A, B, C, D의통신에러율과에러율의양을나타낸것이다. AE, BE, CE, DE 는센서노드 A, B, C, D 의통신에러율의양을말한다. 만약우선순위선정에서센서노드 A가가장높은우선순위를가지는센서노드로선정되었다면데이터수신시간을계산하기위해우선통신에러율의양 ( 식 (2) 의 RT) 인 AE를계산한다. AE는식 (2) 에의해 과 시간동안 A 센서노드의에러율을적분한값이된다. ET 값을계산하기위해나머지 B, C, D 노드의 BE, CE, DE도같은방식으로계산한다. 식 (2) 에의해계산된 T시간동안 A센서노드는모바일싱크에게데이터를전송할수있다. 해당시간이지나게되면모바일싱크는다시자신의통신범위내에있는모든센서노드의우선순위를다시계산하고시간할당을하여데이터수신작업을반복한다. 6. 성능평가 6.1 실험환경제안하는 ASF 기법을평가하기위해센서네트워크를위한컴포넌트기반운영체제인 TinyOS와시뮬레이터인 TOSSIM, Tinyviz를이용하여실험하였다 [12]. 또한모바일싱크의움직임제어를위해 Tython을사용하였다 [13]. Tython은 TOSSIM을위한 Java와 Python으로구성된스크립트언어로 TOSSIM과연동하여센서노드를움직이거나노드에게패킷을전송하는등다양한기능을제공해준다. 실험환경은 ( 그림 9) 와같이랜덤하게배치한 50개의센서노드와 1개의모바일싱크로구성하였다. 센서노드는 (25, 11) 에서 (71, 38) 사이에분포하고모바일싱크는 (5, 25) 에서 (87.5, 25) 위치로 82.5 pixel을이동하며센서노드로부터데이터를전송받는다. < 표 3> 은실험을위한파라 이동싱크의속도 이동싱크의통신범위 센서노드의수 노드당전송할패킷수 파라미터 센서노드의패킷전송율 UT(ASF) 한주기당전송시간 ( PBRR, WFQ(T), WFQ(D) ) 경로손실지수 ( β ) Shadowing deviation ( XdB ) 기준거리 ( d0 ) < 표 3> 파라미터테이블 값 1 pixel/sec 15 pixel 50 100 packets 40 packets/sec 1 sec 1 sec 2.0 4 1 미터테이블이다. 모바일싱크의이동속도는초당 1 pixel 이고통신범위는 15 pixel이다. 각센서노드당전송해야할총패킷수는 100패킷이고초당 40패킷의전송률로데이터를전송한다. ASF에서센서노드에게시간할당시최대전송시간인 UT( 식 (2) 의 UT) 는 1초이고 PBRR과 WFQ(T), WFQ(D) 의전송주기역시 1초이다. 라디오전파모델의경로손실지수인 β는 2.0으로, shadowing deviation인 XdB는 4로하였으며기준거리인 d0는 1로하였다. 본논문에서제안하는스케줄링기법인 ASF와성능비교를하기위해 WFQ(T) 와 WFQ(D), PBRR의성능을측정하였다. WFQ(T) 는모바일싱크의통신범위안에머무르는시간을가중치로적용한 WFQ스케줄링기법으로그시간이짧은센서노드를우선시한다. WFQ(T) 는 1초를주기로재스케줄링을수행한다. WFQ(D) 는모바일싱크가센서노드로부터수신한데이터양을가중치로적용한 WFQ스케줄링기법이다. WFQ(D) 는모바일싱크로전송한데이터양이적은센서노드부터전송기회를부여한다. WFQ(D) 역시 WFQ(T) 와마찬가지로 1초를주기로재스케줄링을수행한다. PBRR은모바일싱크의통신범위안에있는센서노드들로부터순차적으로데이터를수신한다. WFQ와마찬가지로 1초를주기로재스케줄링을수행한다. 아래 < 표 4> 는싱크에서수신한패킷에대한전파수신세기를구하는소스코드이다. 앞서 3장에서설명한 Shadowing model을구현한부분으로서노드간거리에따른전파세기를계산한다. 실험에서는아래의소스코드로구해진전파세기를이용하여스케즐링시우선순위를결정한다.
8 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) < 표 4> 전파수신세기를구하기위한코드 6.2 실험결과및분석구축된실험환경에서 WFQ(T), WFQ(D), PBRR, ASF 스 Shadowing::Pr(Packet, Sender, Receiver) 케줄링의성능을측정하였다. 성능측정의척도로센서노 {double L = getl(); // system loss 드별로얼마나균등하게데이터를전송받았는지측정하기 double lambda = getlambda(); // wavelength 위해센서노드별수신패킷수를측정하였고통신에러를 double Xt, Yt, Zt; // loc of transmitter 고려해전체센서노드에게서얼마나효율적으로데이터수 double Xr, Yr, Zr; // loc of receiver getloc(sender, &Xt, &Yt, &Zt); 신을했는지측정하기위해총수신패킷수를측정하였다. getloc(receiver, &Xr, &Yr, &Zr); 또한, 총수신패킷수와각센서노드별수신패킷수를이용해각스케줄링기법별성능평가의기준값을계산하기위해 Fairness Index를측정하였다. double dx = Xr - Xt; double dy = Yr - Yt; 6.2.1 센서노드별수신패킷수 double dz = Zr - Zt; ( 그림 10) 은스케줄링기법에따른센서노드별수신패 double dist = sqrt(dx * dx + dy * dy + dz * dz); 킷수를나타낸것이다. WFQ(T) 는 WFQ(D) 나 PBRR, ASF double Pr; 에비해데이터수신양이상대적으로상당히적은결과를 // get antenna gain 나타내고있다. 또한 1번과 2번센서노드는자신이전송해 double Gt =getantenna()->gettxgain(dx, dy, dz, lambda); 야하는전체패킷수인 100개의패킷을전송하는데비해 double Gr = getantenna()->getrxgain(dx, dy, dz, lambda); 그외센서노드들은거의데이터를전송하지못하고있다. // calculate receiving power at reference distance 1번과 2번센서노드만많은데이터를전송한이유는 ( 그림 double Pr0 = Friis(t->getTxPr(), Gt, Gr, lambda, L, dist0_); 8) 에서보듯이모바일싱크가가장처음만나는센서노드 // calculate average power loss predicted by path loss model 가 1번과 2번센서노드이기때문이다. double avg_db = -10.0 * pathlossexp_ * log10(dist/dist0_); WFQ(T) 는모바일싱크의통신범위안에머무르는시간 // get power loss by adding a log-normal random variable (shadowing) 이짧은센서노드를우선시하므로 1번과 2번센서노드는 // the power loss is relative to that at reference distance dist0_ 다른센서노드들이모바일싱크의통신범위안으로접근하 double powerloss_db = avg_db + ranvar->normal(0.0, std_db_); 기전에상당히많이중복적으로전송할기회가주어지기 // calculate the receiving power at dist 때문이다. 이렇게몇몇노드에게중복적으로데이터전송 Pr = Pr0 * pow(10.0, powerloss_db/10.0); 기회를부여하는것은균등한데이터전송기회를부여한다 return Pr; 고볼수없다. 또한 1번과 2번센서노드외에다른노드 } 들은거의데이터를전송하지못하고있다. WFQ(T) 는모바일싱크의통신범위안에머무르는시간 ( 그림 10) 센서노드별수신패킷수
무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 9 이짧은센서노드를우선시하는데모바일싱크의통신범위안에머무르는시간이짧은센서노드는모바일싱크와거리가먼센서노드를의미하고그만큼통신에러도높다. 결과적으로모바일싱크는자신과거리가먼센서노드들만데이터전송요청을하게되고높은에러율로인해수신되는데이터의양은적게되는문제가발생한다. WFQ(T) 는몇몇센서노드로부터중복전송을받는문제점이있고모바일싱크와거리가먼센서노드들로부터만데이터를수신하려고하는문제가있어균등한데이터수집을위한스케줄링으로볼수없다. WFQ(D) 는 WFQ(T) 와같이몇몇센서노드는자신이전송해야할데이터의 100% 를전송하고나머지노드는전혀데이터를전송하지못하는문제는발생하지않는다. 하지만 28번, 31번센서노드와같이다른센서노드에비해상당히적은양의데이터를전송한노드가존재한다. 이러한노드가발생하는이유는 WFQ(D) 는단순히센서노드로부터수신한데이터가적은센서노드를우선시하기때문에한센서노드에게서중복전송을하지않지만모바일싱크의이동경로로부터먼곳에존재하는 ( 모바일싱크에머무르는시간이짧은센서노드 ) 센서노드를고려하지않기때문에해당센서노드는데이터를전송할수있는기회가적어지기때문이다. PBRR은단순히모바일싱크의통신범위안에존재하는센서노드들을순서대로돌아가며데이터를전송받는다. 따라서, 모바일싱크의통신범위안에머무르는시간이짧은센서노드를고려해주지않기때문에해당센서노드는그만큼패킷을전송할수있는기회가적어지고이전에전송한데이터를고려하지않아몇몇센서노드로부터중복전송이일어날수있다. 이러한현상은 ( 그림 8) 에서 34번~ 50번센서노드사이에서극심하게발생한다. 34번~50번사이의센서노드를보면 30 패킷이상을전송한센서노드가 11개가존재하는반면 5개센서노드는 15패킷도전송하지못하였다. ASF는전체적으로 15패킷이상의전송율을보이고있다. 또한 WFQ(T) 와같이다른센서노드에비해많은패킷 (100패킷) 을전송한센서노드도존재하지않는다. ASF는우선순위선정시통신에러가많은센서노드를우선시하기때문에모바일싱크로부터먼거리에있는센서노드가데이터를전송기회를부여받지못하는문제가없다. 또한센서노드가전송한데이터양을우선순위선정시가중치로사용하기때문에몇몇노드로부터중복적으로데이터를전송받는문제도발생하지않는다. 또한우선순위선정시선정된센서노드의에러율을파악해에러율이낮은센서노드는그만큼짧은시간을부여하고에러율이높은센서노드는긴시간을부여해균등한데이터수집을이루어낸다. ( 그림 10) 의센서노드 28번은모바일싱크가이동하는이동경로와먼거리에위치한다. 따라서, 에러율이다른노드에비해높게되고데이터를전송할수있는기회가적다. WFQ(T) 와 WFQ(D), PBRR는각각 0개, 2개, 10개의데이 터를전송한데반해 ASF는 20패킷을전송한것을볼수있다. 이것은 ASF가전송기회가적은센서노드를고려하여균등한데이터수집을하고있음을보여준다. ( 그림 10) 의 38번센서노드는모바일싱크의이동경로와가까운곳에위치한다. 따라서에러율이낮아모바일싱크와거리가먼센서노드에비해전송할수있는데이터양이많아질수있다. 또한에러율이낮기때문에한번이라도중복전송이일어나면다른센서노드에비해많은데이터를전송하게된다. 하지만 ( 그림 9) 과같이 ASF는 38번센서노드로부터상대적으로많은데이터를전송받지않았다. WFQ(T) 나 WFQ(D), PBRR은상대적으로많은데이터를전송받은것을알수있다. PBRR은 40패킷이상을수신한것으로보아중복전송까지일어난것을알수있다. 이것으로 ASF는전송기회가많고중복전송이일어날수있는센서노드를고려하여균등한데이터수집을하고있음을알수있다. 6.2.2 총수신패킷수모바일싱크로부터거리가먼센서노드는에러율이높기때문에가능하면해당센서노드가최대한모바일싱크와가까워졌을때데이터요청을하는것이효율적이다. 모바일싱크로부터거리가멀어졌을때아무리많은시간을할당하여전송기회를부여해도에러율로인해수신되는데이터양은많아지지않을것이다. 즉센서노드가최대한에러율이낮을때데이터전송기회를부여하고에러율이낮을때전송기회를부여하지못하였다면에러율이높더라도조금더많은시간을할당하면패킷수신율은올라가고전체센서노드로부터수신한패킷수도증가할것이다. ( 그림 11) 은각스케줄링기법에따라총수신패킷수를측정한것이다. WFQ(T) 는모바일싱크로부터거리가먼센서노드들로부터만데이터를전송받으려하기때문에 300 패킷정도밖에수신하지못한것을알수있다. WFQ(D) 와 PBRR은 WFQ(T) 보다는많은데이터를수신했지만전송기회가적은센서노드와전송기회가많은센서노드를적절히고려하여데이터를수집하지않기때문에 ASF에비해적은 1000패킷이하의데이터를수신한것을알수있다. ( 그림 11) 스케줄링기법별총수신패킷수
10 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) ASF는전송기회가적은센서노드는많은시간을할당해주고에러율이낮아짧은시간만데이터를수신받아도많은데이터를수신할수있는센서노드는짧은시간을할당하기때문에전체적으로균등한데이터를수집할수있다. 결과적으로전체센서노드로부터수신한총수신패킷수도증가한다. 이러한결과로 ASF가다른스케줄링기법에비해효율적으로데이터를수집하고있음을알수있다. 6.2.3 Fairness Index 제안하는 ASF의균등한데이터수집정도를측정하기위해식 (3) 의 Fairness Index를사용하였다. 는각센서노드가모바일싱크로전송한패킷의수이고 은전체센서노드의수이다. Fairness Index = (3) ( 그림 12) 의 Fairness Index는전체센서노드로부터수신한총데이터양이많고균등한전송을보일수록그값이높게나타난다. ( 그림 12) 에서 WFQ(T) 는 0.1 이하의 Fairness Index를보이고있다. 이러한값은다른 WFQ(D) 나 PBRR, ASF에비해현저히낮은값인데이것은 ( 그림 10) 과 ( 그림 11) 에서확인할수있듯이수신한데이터양도적을뿐만아니라몇몇센서노드로부터는센서노드가전송해야하는데이터전체 (100패킷) 를수신하는반면하나도데이터를전송하지못한센서노드가있기때문이다. WFQ(D) 는가중치로수신데이터양을사용하기때문에중복전송이일어나지않아 WFQ(T) 나 PBRR에비해높은 Fairness Index를보이고있다. 하지만전송기회가적은센서노드를고려하지않아 ASF에비해낮은 Fairness Index를보이고있다. PBRR 은중복전송이나전송기회가적은센서노드를고려하지않아 WFQ(D) 나 ASF에비해낮은 Fairness Index를보인다. ( 그림 12) 의결과로 ASF가균등한데이터수집을보이고있음을알수있다. 7. 결론및향후계획고정싱크를사용한센서네트워크의수명을증가시키기위해최근모바일싱크를이용한데이터수집방법이크게증가하고있다. 모바일싱크는싱크주변노드가계속해서변화되기때문에싱크주변센서노드의에너지소모를분산시켜전체센서네트워크의수명을증가시킨다. 모바일싱크를사용한센서네트워크에서는각센서노드로부터균등한데이터를수집하는것이중요하다. 균등하게데이터를수집하지못하고몇몇센서노드로부터는많은데이터를수집하고몇몇센서노드에서는데이터를수집하지못한다면데이터를수집하지못한센서노드가위치한지역의정보는얻을수없는문제가생긴다. 본논문에서는균등한데이터수집을위해모바일싱크의통신환경을고려한 ASF를제안하였다. ASF는모바일싱크의이동성과센서노드와의통신에러율및패킷수신율등을고려하여균등한데이터수집을보장한다. ASF와의성능비교를위하여스케줄링기법중균등성을위한스케줄링기법인 WFQ 와 PBRR과성능평가를수행하였다. WFQ는센서노드가모바일싱크의통신범위안에머무르는시간을가중치로설정한 WFQ(T) 와모바일싱크로전송한데이터양을가중치로적용한 WFQ(D) 로나누어서실험하였다. 실험결과 WFQ(T) 는몇몇센서노드에서는많은데이터를수신하는데이터집중현상이발생하였고몇몇센서노드를제외하고대부분의센서노드가데이터를전송하지못하는문제가발생하였다. WFQ(T) 는센서노드가모바일싱크로전송한데이터양을고려하지않기때문에중복된전송이일어나기때문이다. WFQ(D) 는 WFQ(T) 처럼중복된전송은일어나지않지만모바일싱크로부터거리가먼센서노드 ( 통신에러율이높은센서노드 ) 를고려하지않기때문에해당센서노드로부터데이터를수신하지못하는문제가있다. PBRR은 WFQ(T) 처럼몇몇센서노드로부터만많은데이터를수신하는문제는발생하지않지만모바일싱크와통신가능한시간이나전송한데이터를고려하지않기때문에전체적으로균등한데이터수집이이루어지지않았다. 본논문에서제안한 ASF는 WFQ(T) 에서발생한데이터중복현상이발생하지않았다. 또한 WFQ(D) 나 PBRR와같이모바일싱크의통신범위안에머무르는시간이짧은센서노드에게전송기회를많이부여하지못하는문제도없었다. 실험결과 ASF는다른스케줄링기법에비해전체센서노드에서균등한데이터수집을보였다. 향후에는각센서노드별전송데이터양, 모바일싱크의이동경로, 속도등이변화될때를고려한균등한스케줄링기법에대하연구할계획이다. ( 그림 12) 스케줄링기법별 Fairness Index
무선센서네트워크에서모바일싱크를통한데이터수집의균등성보장을위한가용성기반스케줄링기법 11 참고문헌 [1] H. Karl and A. Willing, A short survey of wireless sensor networks, TKN Technical Report TKN-03-18 October, 2003. [2] N. Xu, S. Rangwala, K. Chintalapudi, D. Ganesan, A. Broad, R. Govindan, and D. Estrin, A Wireless Sensor Network for Structural Monitoring, in Proceedings of the ACM Conference on Embedded Networked Sensor Systems, November, 2004. [3] A. Basharat, N. Catbas, M. Shah, A Framework for Intelligent Sensor Network With Video Camera for Structural Health Monitoring of Bridges, in Proceedings of Third IEEE International Conference on PerCom, March, 2005. [4] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, J. Anderson, Wireless sensor networks for habitat monitoring, in Proceddings of the 1st ACM international workshop on Wireless sensor networks and applications, pp.88-97, September, 2002. [5] J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser, and J. P. Hubaux, MobiRoute: Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks, International Conference on Distributed Computing in Sensor Systems, 2006. [6] S. R. Gandham, M. Dawande, R. Prakash and S. Venkatesan, Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations, Global Telecommunications Conference, 2003. [7] A. K. Parekh and R. G. Gallager, A Generalized Processor Sharing Approach to Flow Control in integrated services networks: The single node case, IEEE/ACM Transactions on Networking, June, 1993. [8] A. Demers, S.Keshav, and S. Shenker, Analysis and Simulation of a Fair Queueing Algorithm, ACM SIGCOMM, pp.3-12, Sept., 1989. [9] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, ATwo-Tier Data Dissemination Model for Largescale Wireless Sensor Networks, ACM International Conference on Mobile Computing and Networking (MOBICOM 02), pp.148-159, 2002. [10] A. Chakrabarti, A. Sabharwal and B. Aazhang, Data Collection by a Mobile Observer in a Single-hop Sensor Network, ACM Transactions on Sensor Networks, 2005. [11] A. Somasundara, A. Ramamoorty, and M. Srivastava, Mobile element scheduling for efficient data collection in wireless sensornetworks with dynamic deadlines, in The 25th IEEE International Real-Time Systems Symposium (RTSS), 2004. [12] P. Levis, N. Lee, M. Welsh, and D. Culler, Tossim: accurate and scalable simulation of entire tinyos applications, in Proceedings of the first international conference on Embedded networked sensor systems (SenSys). ACM Press, pp.126-137, 2003. [13] M. Demmer and P. Levis, Tython scripting for TOSSIM, Network Embedded Systems Technology Winter, 2004. [14] 조영태, 박총명, 이좌형, 정인범, 모바일싱크기반무선센서네트워크에서균등한데이터수집을위한데이터가중치기반스케줄링기법, 정보과학회, 제35권, 제1호, PP.21-33, 2008년 2월. [15] H. T. Friis. A note on a simple transmission formula, Proc. IRE, 34, 1946. [16] T. S. Rappaport, Wireless communications, principles and practice, Prentice Hall, 1996. [17] Bae, K. Kim, Analysis of Wireless Link for Mobile Sensor Network, ICEE2006, YongPyong Resort, Korea, July, 9-13, 2006. [18] Tal Rusak, Philip Alexander Levis, Investigating a physically-based signal power model for robust low power wireless link simulation, MSWiM 2008: 37-46. 2006. 이좌형 e-mail:jinnie4u@kangwon.ac.kr 2003년강원대학교정보통신공학과 ( 공학사 ) 2005년강원대학교컴퓨터정보통신공학과 ( 공학석사 ) 2005년~현재강원대학교컴퓨터정보통신공학과 ( 박사수료 ) 관심분야 : 멀티미디어시스템, 센서네트워크 조영태 e-mail:ytjoe@snslab.kangwon.ac.kr 2007년강원대학교정보통신공학과 ( 공학사 ) 2007년~현재강원대학교컴퓨터정보통신공학과 ( 석사과정 ) 관심분야 : 센서네트워크, 멀티미디어시스템
12 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) 정인범 e-mail:ibjung@kangwon.ac.kr 1985년고려대학교전자공학과학사. 1985년~1995년삼성전자컴퓨터시스템사업부선임연구원. 1994년한국과학기술원정보통신공학과석사 2000년한국과학기술원전산학과박사 2001년~현재강원대학교컴퓨터정보통신공학전공교수관심분야 : 운영체제, 멀티미디어시스템, 센서네트워크