Advanced
An Energy and Delay Efficient Hybrid MAC Protocol for Multi-Hop Wireless Sensor Networks
An Energy and Delay Efficient Hybrid MAC Protocol for Multi-Hop Wireless Sensor Networks
Journal of the Korea Institute of Information and Communication Engineering. 2015. Feb, 19(2): 471-476
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : October 10, 2014
  • Accepted : November 24, 2014
  • Published : February 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
준헌 전
성철 김
sckim@smu.ac.kr

Abstract
본 논문에서는 멀티 홉 무선 센서 네트워크에서 에너지 효율적인 하이브리드(hybrid) MAC 프로토콜을 제안한다. 제안하는 MAC 프로토콜은 경쟁방식(CSMA) 방식과 비경쟁방식(TDMA) 방식을 혼합하여 사용한다. 싱크 노드로부터 멀리 떨어진 센서 노드들은 주로 데이터 측정 임무를 담당하기 때문에 데이터 발생 및 전송 트래픽이 적어 구현이 간단한 경쟁방식을 사용하는 것이 유리하다. 그러나 싱크 노드와 가까운 노드들은 데이터 측정 뿐 만 아니라 relay 노드로 동작하기 때문에 많은 데이터를 전송할 필요가 있으므로 경쟁방식을 사용하면 데이터 패킷의 충돌 및 전송지연이 증가하게 된다. 본 논문에서는 싱크 노드와 1홉 거리의 센서 노드들은 마치 비경쟁방식처럼 슬롯을 할당하여 데이터 패킷을 전송하는 메커니즘을 제안한다. 제안하는 메커니즘은 에너지 및 지연에 효율적인 장점을 가진다. 제안된 MAC 프로토콜은 유사한 다른 프로토콜에 비해 데이터 패킷 전송 지연에서 더 좋은 성능을 보였다.
Keywords
Ⅰ. 서 론
무선 센서 네트워크에서 센서 노드들은 해당 지역에 랜덤하게 분포된다. 이렇게 분포된 센서 노드들은 스스로 네트워크를 구성하여 동작한다 [1] . 따라서 센서 노드들은 환경 모니터링, 물체 검출 등 목적에 따라 수집된 데이터 패킷을 싱크 노드 방향으로 ad -hoc 방식으로 전송하게 된다. 센서 노드들은 데이터 패킷을 싱크 노드 방향의 노드로 전달하기 때문에 싱크 노드 가까이에 위치한 노드들은 많은 데이터를 처리해야한다. 이를 funneling effect라고 한다 [2] . 전송 트래픽의 증가는 funneling effect로 인하여 싱크 노드와 인접한 센서 노드 사이에는 데이터 패킷 충돌, 혼잡 및 손실이 발생이 심해질 수 있다 [3] . 기존 논문에서 이러한 문제를 해결하고자 경쟁방식(CSMA) 및 비경쟁방식(TDMA)의 MAC 프로토콜들이 제안되었다. 경쟁 방식 MAC 프로토콜들은 크게 동기식과 비동기식으로 구분될 수 있다 [1] . 대표적인 동기식 전송방식으로는 S-MAC [4] 과 T-MAC [5] 프로토콜이 있다. S-MAC 프로토콜은 고정적인 듀티 사이클로 sleep 구간을 두어 에너지 소모를 줄이는 방식이다. T-MAC 프로토콜은 S-MAC 프로토콜의 고정적인 듀티사이클의 단점을 해결하기 위해 time out를 사용하여 일정시간동안 데이터 패킷 전송이 없을 경우 sleeping 하여 에너지를 절약하는 방식이다. 대표적인 비동기식 전송방식으로는 B-MAC [6] 및 X-MAC [7] 프로토콜이 있다. B-MAC 프로토콜은 long preamble과 CCA를 통하여 데이터 패킷을 전송하는 방식이다. X-MAC 프로토콜은 B-MAC 프로토콜의 long preamble의 문제점을 해결하기 위해 shotted preamble를 사용하여 에너지 소모를 줄이는 방식이다. 비경쟁방식(TDMA)은 스케줄 방식이라고도 한다. 정해진 스케줄 또는 슬롯에 데이터 패킷을 전송하기 때문에 경쟁방식에 비해 충돌 및 손실이 적다. 그러나 데이터 트래픽이 적은 환경에서의 비경쟁 방식은 필요 없는 슬롯을 할당하여 에너지 손실 및 지연이 발생하는 문제점을 가지고 있다. 본 논문에서는 이러한 경쟁 방식의 장점과 비경쟁방식의 장점을 융합한 하이브리드 (hybrid) 전송방식을 제안하였다. Z-MAC [8] 은 전송할 데이터 트래픽이 적을 경우 CSMA 방식으로 전송하다가 트래픽이 증가할 경우 마치 TDMA 방식처럼 전송하는 방식이다. 또한 Funneling-MAC [9] 에서는 funneling effect를 고려하여 intensity region을 설정하여 이 영역 밖에서는 pure CSMA 방식을 사용하고, 이 영역 안에서는 하이브리드로 TDMA 및 CSMA 방식의 사용을 제안하였다. 그러나 Funneling-MAC 프로토콜은 intensity region을 설정하기 위해 싱크 노드에서 먼저 강한 제어 신호를 broadcast 하고, intensity region 안에서의 센서 노드들은 TDMA 방식 및 CSMA 방식을 동시에 사용하는 복잡한 알고리즘으로 되어있어 구현하는데 어려움을 가진다.
본 논문에서는 싱크 노드와 1홉 거리 밖에 존재하는 센서 노드들은 기존의 경쟁방식으로 전송하고, 1홉 거리 안의 싱크 노드와 인접한 센서 노드들은 비경쟁방식처럼 전송함으로서 데이터 패킷의 충돌, 지연 및 손실을 감소시킬 수 있는 하이브리드 방식을 제안한다.
Ⅱ. 제안된 하이브리드 MAC 프로토콜
앞서 설명처럼, 무선 센서 네트워크는 데이터 패킷이 싱크 노드로 집중되는 특성을 가지는데 이를 Funneling 효과라고 한다. 그림 1 은 이 효과를 보여준다 [9] .
PPT Slide
Lager Image
Funneling 효과 [9] Fig. 1 Funneling effect
- 2.1. 제안된 프로토콜 개요
본 논문에서 제안하는 메커니즘은 효율적인 데이터 패킷 전송을 위하여 싱크 노드와 1홉 거리의 인접한 센서 노드들 간에는 비경쟁방식처럼 데이터 패킷을 전송하고, 나머지 센서 노드들 간에는 기존의 경쟁방식을 통하여 데이터 패킷을 전송한다. 이는 싱크 노드와 멀리 떨어진 센서 노드들은 데이터 패킷 생성 및 전달에 있어서 충돌 발생 확률이 줄어들기 때문이다. 그림 2 는 제안하는 MAC 프로토콜의 동작을 보여준다.
PPT Slide
Lager Image
제안하는 MAC 프로토콜의 동작 Fig. 2 Operation of the Proposed MAC protocol
- 2.2. 싱크 노드 중심의 전송 메커니즘
그림 3 은 싱크 노드로부터 1홉 떨어진 송신노드들의 효율적인 데이터 패킷 프레임 전송 방법을 보여준다. 이를 위해 송신 노드는 Tx-beacon을 사용하고, 싱크 노드는 Rx-beacon을 사용한다. 이는 이전에 제안된 QAEE-MAC 프로토콜 [10] 의 비콘 프레임과 유사한 기능을 가진다. 본 논문에서 싱크 노드는 송신 노드들로부터 일정 샘플링 기간 동안 Tx-beacon 프레임을 수신하고, 그에 대한 Rx-beacon 프레임을 broadcast 한다. 송신 노드들은 Tx-beacon 프레임 전송 시간과 Rx-beacon 프레임 수신시간을 사용하여 송신 노드의 전송 시간을 결정한다. 송신 노드들은 매핑 함수에 의해 계산된 시간에 데이터 패킷을 전송함으로서 송신 노드들 간에 충돌을 최소화하여 전송할 수 있다.
PPT Slide
Lager Image
싱크 노드 전송 메커니즘 Fig. 3 Transmission mechanism of sink node
- 2.3. 스케줄 매핑 방식
앞서 설명한 것처럼, 제안하는 전송 메커니즘은 active 주기 동안의 Tx-beacon 및 Rx-beacon 프레임을 이용하여 sleep 주기 동안 데이터 패킷을 전송하는 방식이다.
그림 4 는 본 논문에서 제안하는 전송 메커니즘의 스케줄 매핑 방식을 보여준다. 그림에서 보듯이 송신 노드는 Tx-beacon 프레임을 싱크 노드로 전송한 후 싱크 노드의 Rx-beacon 프레임이 도착할 때 까지 작은 크기로 listen 과 sleep을 반복한다. sleep 간격은 싱크 노드의 Rx-beacon 프레임을 수신할 수 있을 정도로 충분히 작은 간격을 가진다. 이는 송신노드가 싱크 노드의 Rx-beacon 프레임을 기다리면서 발생하는 에너지 손실을 줄이기 위한 방법이다. 송신 노드는 다른 송신노드들과 충돌 없이 전송하기 위해 다음의 매핑 함수를 사용한다.
PPT Slide
Lager Image
스케줄 매핑 방식 Fig. 4 Mapping for Scheduling
  • TS: active time
  • TD: sleep time
  • TSi: i node의 Tx-beacon 프레임 전송 시작 및 active time 끝나는 시간의 차
  • TDi: i node의 데이터 패킷 프레임 전송 시작 및 sleep time 끝나는 시간의 차
PPT Slide
Lager Image
송신 노드는 sleep 구간 동안 수식 (1)의 매핑 함수를 사용하여 데이터 패킷 프레임을 전송한다. 데이터 패킷프레임을 수신한 싱크 노드는 응답신호를 전송함으로 이상 없이 전송되었음을 송신 노드에게 알린다.
그림 5 는 한 개 이상의 송신 노드로부터 데이터 패킷프레임을 전달 받을 경우를 보여준다. 그림에서 보듯이 2개의 송신 노드들은 매핑 함수를 사용하여 충돌 없이 데이터 패킷 프레임을 전송한다. 송신 노드2는 송신 노드1과 싱크 노드의 데이터 패킷 송수신이 완료할 때 까지 sleep 모드로 대기함으로서 에너지 소모를 줄인다. 각 송신 노드들의 wake up 시간은 다음과 같다.
PPT Slide
Lager Image
최적화된 다중 송신 노드의 패킷 전달 Fig. 5 Optimized multi-senders forwarding of packet
  • TACK: 응답 프레임 전송 시간
PPT Slide
Lager Image
수식 (2)에 의해 송신 노드들은 자신의 데이터 패킷프레임을 송신하기 전에 wake up 하여 자신의 정해진 시간에 데이터 패킷 프레임을 전송한다.
- 2.4. Algorithm
싱크 노드와 1홉 거리 송신 노드의 전송 알고리즘은 다음과 같다.
  • 1:SENDER: Data Generation & relay
  • 2:SENDER: Channel sensing
  • 3:SENDER: if channel == busy
  • { waiting }
  • 4:SENDER: else if channel == idle
  • { Tx-beacon frame transmission
  • TimeSenderNo = TxBeacon time }
  • { waiting Rx-beacon frame }
  • 5:SENDER: if ReceiveBuffer == TxBeacon
  • { waiting Rx-beacon frame }
  • 6:SENDER: else if ReceiveBuffer==RxBecon
  • { TimeSink = RxBeacon time
  • { WakeupTime =
  • (ActiveTime - TimeSenderNo) *
  • (SleepTime / ActiveTime) + AckTime) }
  • 7:SENDER: if Time ==WakeupTime+SIFS
  • { data packet transmission }
이 구간에서 송신 노드들은 비경쟁방식의 TDMA처럼 슬롯을 할당받아 데이터 패킷을 전송한다. 전송할 데이터 패킷을 가지고 있는 송신 노드들은 채널이 idle이면 Tx-beacon 프레임을 전송하고 싱크 노드로부터 Rxbeacon 프레임을 기다린다. 전송 노드들은 Tx-beacon 프레임 전송 시간과 Rx-beacon 프레임 전송 시간을 이용하여 전송할 시간을 계산하여 데이터 패킷을 전송한다. 싱크 노드의 데이터 수신 알고리즘은 다음과 같다.
  • 1:SINK: Periodic sampling
  • { received TxBeacon frames }
  • 2:SINK: if SamplingTime == null
  • { broadcast RxBeacon frame }
  • 3:SINK: Data periodic
  • { received Data packets }
  • { transfer ACK }
  • 4:SINK: Data periodic time out
싱크 노드는 항상 전원이 공급되는 노드이기 때문에 sleep 구간이 필요 없다. 제안하는 MAC 프로토콜에서는 sampling 구간에서 송신 노드들로부터 Tx-beacon 프레임을 수신 받고, Rx-beacon 프레임을 송신한다. sleep 구간에서 송신 노드들로부터 데이터 패킷을 전송받고 이에 대한 응답을 한다.
Ⅲ. 성능 분석
본 장에서는 제안하는 메커니즘과 기존의 X-MAC 프로토콜과 성능을 시뮬레이션을 통해 비교 분석한다. 본 논문의 성능 분석을 위해 다음과 같이 가정한다.
성능 분석은 싱크 노드와 1홉 거리의 센서 노드와의 데이터 패킷 통신만으로 한정한다. 이는 제안하는 메커니즘에서 싱크 노드와 1홉 거리 이상의 노드들은 기존의 경쟁방식을 사용하므로 성능평가에서 제외한다. 싱크 노드 1개와 1홉 거리의 센서 노드들은 10개를 임의로 분포하였으며, 센서 노드들의 데이터 패킷 생성은 70~100% 사이의 랜덤 값을 생성한다. 총 10회의 실험을 통해 평균값을 취한다. 본 논문에서 사용한 파라미터 [7 , 11 , 12] 표1 과 같다. 그림 6 는 송신 노드의 데이터 패킷의 수에 따른 평균 에너지 소모를 보여준다. 그림에서 보듯이 본 논문에서 제안된 메커니즘은 데이터 패킷을 증가함에 따라 X-MAC 프로토콜에 비해 약 18% 에너지가 절약되었다.
성능 분석에 사용된 파라미터Table. 1 Parameters used in performance evaluation
PPT Slide
Lager Image
성능 분석에 사용된 파라미터 Table. 1 Parameters used in performance evaluation
PPT Slide
Lager Image
데이터 패킷에 따른 평균 에너지 소모 Fig. 6 average power consumption vs. no. of packet
이는 경쟁기반의 MAC 프로토콜에서는 센서 노드들은 데이터 패킷 전송을 위해 wake up 모드로 대기를 하여야 하기 때문에 에너지 소모가 증가한다. 제안하는 메커니즘은 센서 노드들에게 데이터 패킷 전송 시간을 할당함으로서 대기 시간을 줄여 이에 소모하는 에너지를 절약할 수 있다. 그림 7 는 데이터 패킷 증가에 따른 지연을 보여준다.
PPT Slide
Lager Image
데이터 패킷에 따른 지연 Fig. 7 packet delivery latency vs. no. of packet
본 논문에서 제안하는 MAC 프로토콜에서는 앞서 설명한 것처럼 센서 노드들은 매핑 함수를 통해 전송에 참여할 시간을 계산한다. 이를 통해 센서 노드들은 데이터 패킷을 전송하기 때문에 X-MAC 프로토콜에 비해 약 12%의 지연이 감소되었다.
Ⅳ. 결 론
본 논문에서는 싱크 노드와 1홉의 인접한 센서 노드들을 위한 MAC 프로토콜을 제안하였다. 무선 센서 네트워크에서는 싱크 노드에 인접할수록 데이터 트래픽 부하가 증가한다. 본 논문에서는 싱크 노드와 1홉 거리의 센서 노드들의 전송방식을 마치 스케줄 방식처럼 전송하는 메커니즘을 제안하였다. 성능분석을 통하여 에너지 및 전송에 효율적임을 보였다. 제안하는 MAC 프로토콜은 트래픽 부하가 높은 환경일수록 더 효율적이다. 추후 싱크 노드와 1홉 거리 이상의 센서 노드들과 결합하는 환경에서 적합하고 효율적인 연구가 지속적으로 이루어질 예정이다.
Acknowledgements
본 연구는 2014년도 상명대학교 교내연구비를 지원받아 수행하였음
BIO
전준헌(Jun-Heon Jeon)
상명대학교 정보통신학과 석사
상명대학교 컴퓨터과학과 박사
※ 관심분야 : 무선 네트워크, 센서 네트워크, IoT, 유비쿼터스
김성철(Seong-Cheol Kim)
상명대학교 컴퓨터과학과 교수
※ 관심분야 : 무선 센서 네트워크, 무선랜, MAC 프로토콜, QoS, IoT, 초고속통신망, 멀티미디어통신
References
Huang P. , Xiao L. , Soltani S. , Mutka M. , Xi N. 2012 “The evolution of MAC protocols in wireless sensor networks: A survey” Communications Surveys & Tutorials, IEEE 15 (1) 101 - 120    DOI : 10.1109/SURV.2012.040412.00105
Wan C. Y. , Eisenman Shane E. , Campbell Andrew T. , Crowcroft John “Siphon: Overload Traffic Management using Multi-Radio Virtual Sinks” In Proc. of 3rd ACM Conference on Embedded Networked Sensor Systems (SenSys 2005) November 2005
Hull B. , Jamieson K. , Balakrishnan H. “Mitigating Congestion in Wireless Sensor Networks” In Proc. of 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys 2004) November 2004
Ye W. , Heidemann J. , Estrin D. “An energy-efficient MAC protocol for wireless sensor networks,” in Proc. INFOCOM 2002 1567 - 1576
van Dam T. , Langendoen K. “An adaptive energyefficient MAC protocol for wireless sensor networks,” in Proc. SenSys 2003 171 - 180
Polastre J. , Hill J. , Culler D. “Versatile Low Power Media Access for Wireless Sensor Networks,” ACM SenSys '04 Baltimore, Maryland, USA November 2004 95 - 107
Buettner M. , Yee G. V. , Anderson E. , Han R. “X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks,” ACM SenSys '06 October 2006 307 - 320
Rhee Injong , Warrier Ajit , Aia Mahesh , Min Jeongki “Z-MAC: a Hybrid MAC for Wireless Sensor Networks,” ACM SenSys’05 San Diego, California, USA November 2–4, 2005
Ahn G. “Funneling-MAC: a localized, sink-oriented MAC for boosting delity in sensor networks,” Proc. ACM Conf. Embedded Networked Sensor Systems (SENSYS '06) Nov. 2006 293 - 306
Kim S. C. , Jeon J.H. , Park H.J. “QoS Aware Energy-Efficient (QAEE) MAC Protocol for Energy Harvesting Wireless Sensor Networks,” Springer Convergence and Hybrid Information Technology 2012, LNCS 2012 vol. 7425 41 - 48
Sun Yanjun , Gurewitz Omer , Johnson David B. “RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks,” ACM SenSys '08 November 2008 1 - 14
Oak Jeong-Yeob. , Choi Young-June , Pak Wooguil 2012 “EP-MAC: Early Preamble MAC To Achieve Low Delay And Energy Consumption In Duty Cycle Based Asynchronous Wireless Sensor Networks,” KSII Transactions on Internet and Information Systems (TIIS) 6 (11) 2980 - 2991