Advanced
A Priority-based Time Slot Allocation Protocol for Hybrid MAC in WSNs
A Priority-based Time Slot Allocation Protocol for Hybrid MAC in WSNs
Journal of the Korea Institute of Information and Communication Engineering. 2014. Jun, 18(6): 1435-1440
Copyright © 2014, The Korea 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 : May 01, 2014
  • Accepted : June 09, 2014
  • Published : June 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
재현 남
jhnam@silla.ac.kr

Abstract
WSN내의 노드들은 한정된 에너지를 지녔다. 따라서 각 노드들의 채널에 대한 접근을 효율적으로 제어하는 것이 채널 활용성과 에너지 소모에 중요한 역할을 수행한다. 본 논문에서는 WSN에서 각 노드에서의 에너지 효율성을 높이기 위해 하이브리드 TDMA/CSMA MAC을 위한 우선순위 기반 타임 슬롯 할당 프로토콜을 제안한다. 제안된 프로토콜은 TDMA와 CSMA 기법의 장점을 활용함과 동시에 (m,k)-firm 기법을 이용하여 채널 접근의 우선권을 제공하였다. 성능 평가를 위해 다양한 노드 수의 변화에 따른 시뮬레이션을 수행하였고, S-MAC과 비교하여 평균 지연시간과 패킷 전송률에서 많은 향상을 보여주었다.
Keywords
Ⅰ. 서 론
무선 센서 네트워크 (Wireless Sensor Network : WSN)에서 구현의 단순함과 유연성 때문에 CSMA(carrier sense multiple access) MAC 프로토콜을 많이 사용된다. 하지만 CSMA는 둘 이상의 노드들이 동시에 목적지로 패킷을 전송할 경우 충돌(collision)이 발생하여 성능을 저하시킨다. 이러한 충돌 문제를 해결하기 위해 TDMA(time-division multiple access)를 이용하여 서로 다른 시간에 이웃 노드들로의 전송이 발생할 수 있도록 전송시간을 스케줄 한다. 하지만 TDMA는 전체 노드들 간에 충돌이 발생하지 않도록 효율적인 시간 스케줄을 작성하기 힘들다. 또한 시간 동기화 때문에 잦은 메시지 교환이 발생하고, 이는 결국 에너지 낭비를 초래한다.
WSN 내의 각 노드들은 제한된 에너지만을 소유하고 있기 때문에 WSN에서의 통신 프로토콜 설계에서 에너지 효율성 검증은 필수적인 요소가 되었다. WSN에서 각 노드는 충돌, 유휴 감지(idle listening), 다른 노드로 전송되는 패킷 엿듣기(packet overhearing) 들로 인해 에너지를 낭비하고 있다. 특히 유휴 감지로 인한 에너지 소모가 제일 크다. WSN에서 가장 많은 에너지를 소모하는 유휴 감지를 줄이기 위해 duty cycle 기법이 많이 사용된다 [1] . duty cycling 기법에서는 센서 노드의 상태가 주기적으로 active와 sleeping 상태로 변한다. active 상태일 경우 노드는 데이터를 송수신할 수 있지만 sleep 상태일 경우 에너지 절약을 위해 노드는 자체 radio를 꺼버린다. 하나의 노드에서 다른 노드로 패킷을 전송하기 위해서는 양쪽 노드 모두가 active 상태로 존재해야 하기 때문에 동기식 MAC 프로토콜이 필요하다. 이러한 동기식 프로토콜에는 S-MAC, T-MAC, RMAC 등이 있다. 하지만 동기식 MAC 프로토콜들은 에너지 소모는 줄일 수 있지만, 통신을 위해 sleeping 상태의 이웃 노드가 active 상태로 될 때까지 대기해야 하기 때문에 패킷 전송 시 부가적인 지연을 발생시킨다.
S-MAC은 전형적인 동기식 duty-cycling MAC 프로토콜이다 [1] . 하지만 통신에 참가하지 않는 노드들은 sleep 상태로 유지되기 때문에 패킷은 사이클마다 하나의 홉(hop)으로만 포워딩된다. S-MAC의 단점을 보완하기 위해 이후 적응적 listening 기능을 지닌 S-MAC을 발표했지만, 이 또한 패킷이 기껏해야 사이클 당 2개의 홉만 포워딩된다. 다중 홉 포워딩 환경에서 이와 같은 전송은 종단간의 긴 전송 지연을 유발하기 때문에 시간이 중요한 응용에서는 부적합하다. 따라서 지연시간을 고려해서 어플리케이션들은 노드들에게 파워관리를 하지 말고 항상 wake한 상태로 유지하거나 데이터 전송을 위해 충분히 긴 시간동안 wake 상태를 유지하도록 요구 할 수 있지만, 이는 에너지 효율 문제를 야기한다.
본 논문에서는 WSN에서 각 노드에서 우선순위에 기반한 채널 할당을 위해 TDMA와 CSMA 기법이 결합된 하이브리드 MAC을 위한 우선순위기반 타임 슬롯 할당 프로토콜을 제안한다. 제안된 프로토콜에서는 먼저 TDMA을 이용하여 노드들의 시간 스케줄을 할당하였고, 해당 시간에 이용하지 않는 채널 사용을 위해 적응적 우선순위 기법을 이용한 CSMA 기법을 사용하였다. 이때 우선순위를 결정하기 위해 (m,k)-firm 기법을 활용하였다. 성능평가를 위해 각 노드에서 데이터 패킷을 전송하는데 소요된 평균 지연시간과 패킷 전송률을 S-MAC과 적응적 MAC 프로토콜에 대해 시뮬레이션을 수행했다. 시뮬레이션 결과 제안된 기법이 기존 기법보다 성능이 향상되었음을 알 수 있다.
Ⅱ. 관련연구
TDMA와 CSMA 기법은 WSN에서 매체 접근을 위해 많이 사용하는 기법이다. TDMA는 동시에 채널을 접근하고자하는 노드들을 줄이기 위해 토폴로지 정보를 채널 접근 스케줄링의 기본으로 사용한다. TDMA는 노드들 간의 채널에 대한 경쟁이 많을수록 높은 성능을 나타낸다. 또한 TDMA는 충돌, 유휴 감지, 패키 엿듣기 등으로 인해 발생되는 에너지 낭비를 줄일 수 있기 때문에 CSMA보다 더 좋은 에너지 절약이 가능하다. 하지만 TDMA는 네트워크상의 모든 노드들의 전송 시간을 효과적으로 충돌 없이 스케줄할 수 있어야 한다. 하지만 센서 네트워크는 잦은 토폴로지 변화를 발생시키고 노드들 간의 간섭 관계를 변화시켜서 효율적인 스케줄을 어렵게 한다. 또한 채널에 대한 경쟁이 적을수록 TDMA는 CSMA보다 낮은 성능을 보이게 된다 [2] .
CSMA는 네트워크의 토폴로지를 이용하지 않기 때문에 네트워크의 변화에 대해 잘 동작한다. 하지만 토폴로지 정보를 이용하지 않기 때문에 매 데이터 전송마다 이웃 노드들간의 충돌문제를 해결해야 한다. 따라서 경쟁과 충돌 문제를 해결하는 비용이 많이 소요된다. 따라서 TDMA와 CSMA의 약점을 보완해 주는 동시에 장점을 결합한 하이브리드 기법이 필요하다.
S-MAC과 T-MAC [3] 은 패킷교환을 조정하고 유휴 감지를 줄이기 위해 지역적인 sleep-wake 스케줄을 사용하는 하이브리드 CSMA/TDMA 기법이다. 하지만 이 기법의 성능은 RTS와 CTS 패킷에 의해 영향을 받고, 네트워크 크기가 커지면 스케줄의 수 또한 증가한다.
RMAC [4] 과 DW-MAC [5] 은 멀티홉 포워딩에서 지연시간을 줄이는 방법을 제안했다. RMAC은 SLEEP 기간동안 패킷을 수신하기 위해 wakeup 할 시기를 목적지까지의 경로에 있는 노드들에게 알려주는 제어 프레임을 이용한다. DW-MAC은 SLEEP 기간 동안 충돌없는 데이터 전송을 보장하기 위해 RMAC 기법에 1대1 맵핑 기능을 추가하였다. 하지만 이 기법들은 비록 제어 프레임을 통해 노드들이 스케줄상으로 slot을 성공적으로 할당하여도 두 개의 hidden terminal 문제는 항상 데이터 전송시 충돌을 발생시키다.
HyMAC [6] 은 하이브리드 TDMA/FDMA 매체 접근 프로토콜이다. 이 기법은 실시간 음성 스트림과 같은 어플리케이션에 적합한 성능과 전송 지연시간을 제공한다. 하지만 네트워크 내의 모든 노드들을 동일한 우선순위로 간주하여 트래픽이 많이 발생하는 경우 지연시간을 증가시키는 문제가 있다.
Z-MAC [2] 은 setup과 transmission 두가지 모드로 동작하는 하이브리드 TDMA/CSMA 기법이다. setup 모드에서는 각 노드는 하나의 time slot을 할당받는다. 이때 하나의 주어진 slot에 대해 해당 slot을 할당받은 노드를 "owner"라고 부르고, 그렇지 못한 모드들을 "non -owners"라고 부른다. Z-MAC에서는 2-hop 이웃내에 있는 노드들이 동일한 slot을 할당받지 않도록 setup 모드내에서 스케줄한다. transmission 모드에서 각 노드는 전송하기 전에 채널이 clear되어 있는지 감지하여 clear 되어 있을 경우 데이터를 전송한다. 이때 해당 slot의 "owner"가 다른 노드들보다 채널 접근에 우선순위가 높다. 하지만 이 기법의 경우 우선순위를 결정하는 요소는 포워딩 부하상태, 남아있는 배터리 상태, 베이스 스테이션까지의 거리 등을 이용한 통계를 가지고 결정하였다.
Ⅲ. 우선순위기반 타임 슬롯 할당 프로토콜
WSN상의 트래픽은 센싱 어플리케이션에 따라 동적으로 변한다. 즉, 침입자를 감시하는 환경의 경우 평소에는 네트워크 상에 존재하는 트래픽의 양은 거의 없거나 적은 상태이다. 하지만 침입자가 나타날 경우 대상 추척이 시작되고 대상이 움직일 때마다 노드들은 이벤트를 감지하여 데이터를 생성하여 전달하여 버스트한 트래픽을 발생시킨다. 이러한 어플리케이션의 경우 모든 노드들을 항상 awake한 상태로 유지하는 것은 부적절하다. 감시 시스템은 몇 달 동안 지속적으로 유지되어야 하기 때문에 효율적인 에너지 관리 기법이 필요하다. 따라서 본 논문에서는 에너지 효율을 높이면서 낮은 데이터 전송 지연을 얻을 수 있는 적응적 우선순위 기반 타임 슬롯 할당 기법을 제안한다.
본 논문에서 제안한 적응적 우선순위 기반 타임 슬롯 할당 기법은 Z-MAC 기법을 이용한 하이브리드 TDMA /CSMA 기법이다. Z-MAC와 같이 setup과 transmission 두 가지 모드로 동작한다.
setup 모드에서는 이웃노드의 검출, TDMA 슬롯 할당 등을 수행한다. 먼저, 이웃 노드 검출과정에서는 각 노드에서 1-hop 이웃과 2-hop 이웃들로 구성된 리스트를 생성하여 slot 할당과정에서 이용한다.
각 노드가 one-hop 거리에 있는 노드들로부터 RTS/CTS 패킷를 수신하면 패킷를 전송한 노드들을 자신의 이웃 리스트(neighbor list)에 추가한다. 생성된 이웃리스트는 HELLO 메시지를 통해 인접한 이웃으로 전송된다. TDMA 슬롯 할당과정에서는 2-hop 거리 내에 있는 두 개의 노드가 동일한 time slot에 할당되지 않도록 각 노드에 time slot을 할당하는 과정이다. 이 과정은 Z-MAC에서 사용한 DRAND 기법 [7] 을 사용하였다.
각 노드에 대한 slot 할당 예는 그림 1 에 나타나 있다. 그림 1 의 상단은 네트워크 토폴로지를 나타내고 숫자는 각 노드의 id 를 의미한다. 하단의 그림은 모든 노드들에 대한 슬롯 스케줄을 나타낸다. 그림에서 보는 바와 같이 특정한 slot에 대해 2-hop 내의 두 노드가 동일한 slot을 할당받는 경우는 없다.
PPT Slide
Lager Image
시간 슬롯 할당 예 Fig. 1 Time slot assignment example
transmission 모드에서는 전송 전에 각 노드는 캐리어 센싱을 수행하고 채널이 clear 상태일 경우에만 패킷을 전송한다. 이 때 채널에 대한 접근은 우선순위 기법으로 제어된다.
본 논문에서 제안한 기법에서는 Z-MAC 기법과는 달리 우선순위를 결정하는 방법으로 (m,k)-firm 기법을 이용하였다 [8] . (m,k)-firm 기법으로 각 노드들을 우선 순위 그룹으로 분류하고 각 우선순위 그룹에 따라 충돌 윈도우(CW:contention window) 크기를 조절하여 우선 순위를 결정한다.
각 node j 는 자신의 slot을 결정하지 못한 one-hop 또는 two-hop 이웃들과 slot 할당 경쟁이 수행한다. 적응적 우선순위 MAC에서는 k 레벨의 우선순위를 사용한다. 각 노드의 우선순위는 (m,k)-firm 스케줄링 기법에서 우선순위를 결정하는 식 (1)을 이용한다 [8] . 이를 통해 k개의 우선순위 그룹이 형성된다.
PPT Slide
Lager Image
여기서 s 는 이전 k 개의 연속적인 시도의 상태이고, jl ( mj,s )는 s 내에서 m 번째 "meet"의 위치를 의미한다.
각 노드는 하나의 상태(state) 정보를 유지하고 있는데 이는 데드라인을 만족했는지 하지 않았는지에 대한 최근 히스토리를 담고 있다. 상태 정보는 데드라인 만족 여부에 따라 “miss"와 ‘meet" 로 저장된다. 즉, (m,k)-firm 기법은 k 번의 시도 중 m 번의 ”meet“ 조건을 만족해야 되기 때문에 채널 할당 경쟁에서 밀려서 "miss"가 발생할수록 다음 경쟁에서 채널을 할당받을 우선순위가 높아진다.
transmission 모드 동안 모든 노드들은 slot을 가지기 위해 서로 경쟁한다. slot의 "owner"는 다른 노드에 비해 채널 접근에 대한 우선권을 지닌다. 만약 slot이 "owner"에서 전송할 데이터가 없어서 사용되지 않거나 특정한 노드에 소유되지 않았을 경우 “non-owners"들은 해당 slot을 사용하기 위해 경쟁한다. "non-owners"가 해당 slot을 가질 확률은 (m,k)-firm 기법으로 결정된 우선순위 그룹에 따라 달라진다. "Owner"는 항상 먼저 채널을 가질 수 있도록 보장되어야 한다. 따라서 "owner"의 CW 값은 최소값으로 할당한다. "Nonowners" 들은 그들이 속한 우선순위 그룹에 할당된 CW 범위 내에서 랜덤한 값을 할당받는다. 결론적으로 "owner" 노드는 자신에게 할당된 slot에 대해 먼저 접근하기 때문에 충돌이 없는 형태로 데이터를 전송하고, "non-owners"들은 노드들이 속한 우선순위 그룹 내의 다른 노드들과 채널 접근에 대한 경쟁을 수행하기 때문에 충돌 확률을 낮출 수 있다. 이는 결국 에너지 소모를 줄일 수 있는 이점이 있다. “Non-owners" 그룹에 할당되는 CW 값의 범위는 그림 2 와 같다.
PPT Slide
Lager Image
적응적 우선순위 MAC에서 채널 접근 우선순위 그룹 Fig. 2 Priority groups based channel access in adaptive priority MAC
만약 노드 i 가 현재 slot의 “non-owner"일 경우 "owner”에 할당된 CW 0 만큼 대기 후 자신의 우선순위 그룹에 할당된 CW 값 내에서 랜덤한 백오프 값을 할당 받는다. 이후 백오프 타이머가 0이 되면 “non-owner" 노드는 채널이 busy 상태인지 확인하고 busy 상태가 아닐 경우 데이터를 전송한다. 만약 채널이 busy 상태이면 노드는 busy 상태가 안될 때까지 계속 반복하여 대기한 후 수행한다.
Ⅳ. 성능평가
제안된 프로토콜의 성능을 평가하기 위해 ns-2 시뮬레이터를 이용하여 시뮬레이션 하였다. 성능평가는 노드 수 변화에 따른 평균지연시간과 패킷 전송률을 측정 하였다. 시뮬레이션 파라미터와 우선순위 파라미터는 각각 표 1 표2 와 같다.
시뮬레이션 파라미터Table. 1Simulation parameters
PPT Slide
Lager Image
시뮬레이션 파라미터 Table. 1 Simulation parameters
우선순위 파라미터Table. 2Priority parameters
PPT Slide
Lager Image
우선순위 파라미터 Table. 2 Priority parameters
그림 3 은 각 노드에서 데이터 패킷을 전송하는데 소요된 평균 지연시간을 S-MAC과 제안된 MAC 프로토콜에 대해 나타낸 것이다.
PPT Slide
Lager Image
각 노드에서의 평균 지연시간 Fig. 3 Average delay of a node for various number of nodes
그림에서 보는 바와 같이 전송 노드의 수가 증가하면 S-MAC의 경우 트래픽의 양이 증가하기 때문에 지연시간 또한 증가하지만 제안된 MAC은 (m,k)-firm을 이용한 우선순위 기법 때문에 지연시간의 변화가 적다.
그림 4 는 패킷 전송률에 대해 S-MAC과 제안된 MAC 프로토콜을 비교하여 나타낸 것이다. 패킷 전송률은 식(2)와 같이 계산된다.
PPT Slide
Lager Image
노드 수 변화에 따른 패킷 전송률 Fig. 4 Packet delivery ratio with varying numbers of nodes
PPT Slide
Lager Image
그림에서 보는 바와 같이 전송된 패킷의 수가 증가하면 패킷 전송률은 체증 때문에 낮아지지만 제안된 MAC 프로토콜이 S-MAC보다는 성능이 좋은 것을 알 수 있다.
Ⅴ. 결 론
WSN 내의 각 노드들은 제한된 에너지만을 소유하고 여러 가지 요인들 때문에 에너지 낭비가 크기 때문에 WSN에서의 통신 프로토콜 설계에서 에너지 효율성 검증은 필수적인 요소이다. 본 논문에서는 각 노드에서 많은 에너지를 소모하는 유휴 감지를 줄이기 위해 (m,k)-firm 기법을 이용한 우선순위 기반의 타임 슬롯 할당 프로토콜을 제안했다. 제안된 프로토콜은 WSN에서 각 노드의 효율적인 채널 할당을 위해 TDMA와 CSMA 기법이 결합된 하이브리드 채널 접근 프로토콜을 이용하였고, 채널에 대한 접근 우선순위를 위해 (m,k)-firm 기법을 이용하였다.
제안된 기법의 성능을 평가하기 위해 각 노드에서 데이터 패킷을 전송하는데 소요된 평균 지연시간과 패킷 전송률을 S-MAC과 제안된 프로토콜에 대해 시뮬레이션을 수행했다. 시뮬레이션 결과 제안된 기법이 기존 기법보다 성능이 향상되었음을 알 수 있다.
BIO
남재현(Jae-hyun Nam)
1989 부산대 컴퓨터공학과(학사)
1992 부산대 컴퓨터공학과(공학석사)
2002 부산대 컴퓨터공학과(공학박사)
1993~2002 동주대학교 조교수
2002 ~ 현재 신라대학교 IT학과 부교수
※관심분야 : 무선센서네트워크, TCP/IP 프로토콜, 자동차네트워크
References
Ye W. , Heidemann J. , Estrin D. 2002 “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proceeding of the 21st Conference of the IEEE Computer and Commu-nications Societies New York 3 1567 - 1576
Rhee I. , Warrier A. , Aia M. , Min J. 2005 “Z-Mac: A Hybrid MAC for Wireless Sensor Networks,” IEEE/ACM Transactions on Networking 16 (3) 511 - 524
van Dam T. , Langendoen K. 2003 “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proceeding of the 1st ACM Conference on Embedded Networked Sensor Systems Los Angeles 171 - 180
Du S. , Saha A. K. , Johnson D. B. 2007 “Rmac: A routing-enhanced duty-cycle mac protocol for wireless sensor networks.” INFOCOM’07 1478 - 1486
Sun Y. , Du S. , Gurewitz O. , Johnson D. B. 2008 “Dw-mac: a low latency, energy efficient demand-wakeup mac protocol for wireless sensor networks.” MobiHoc’08 53 - 62
Salajegheh M. , Soroush H. , Kalis A. 2007 “HYMAC: hybrid TDMA/FDMA medium access control protocol for wirelessssensor networks,” Proceedings of the 18th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC ’07) Athens, Greece 1 - 5
Rhee I. , Warrier A. , Xu L. 2004 "Randomized dining philosophers to TDMA scheduling in wireless sensor networks", Technical report Computer Science Department, North Carolina State University Raleigh, NC
Hamdaoui M. , Ramanathan P. 1995 "A Dynamic Priority Assignment Technique for Streams with (m,k)-Firm Deadlines" IEEE Transactions on Computers http://dx.doi.org/10.1109/12.477249 44 (12) 1443 - 1451    DOI : 10.1109/12.477249