There are diverse applications in Wireless Sensor Networks (WSN) which require real-time communication. Factory automation, process automation, intelligent traffic system, and real-time location tracing system are representative real-time WSN applications. Messages in such applications need to be communicated in given deadlines or periods. To implement these applications, real-time communication protocols and real-time message scheduling algorithms are inevitable. In order to support real-time communication, MAC (Medium Access Control) layer is relying on TDMA scheme which avoids packet collision and provides a deterministic packet transmission time. For TDMA scheme allocates a time slot to each node, and only the owners of a time slot are communicate at the time slot. Most research on TDMA are focusing on fairly distribution of time slots and minimization of the length of TDMA schedule. However, this dissertation proposes a real-time message scheduling algorithm which is allocating time slots to each message to meet the deadline constraints.
This dissertation studies a real-time communication scheme based on IEEE 802.15.4 beacon enabled mode, first. IEEE 802.15.4 standard defines a superframe structure in beacon enabled mode. The superframe structure is specified by a beacon frame transmitted by a network controller called PAN (Personal Area Network) Coordinator. The duration of superframe is determined by BO (beacon order) and divided into an active region and an inactive region. The active region consists of CAP and CFP and is divided into 16 equally sized slots. IEEE 802.15.4 allows allocations of GTS (Guaranteed Time Slot) in CFP, and the owner of GTS is allowed to access the wireless channel. We extend our previous study on a real-time message scheduling for IEEE 802.15.4. The proposed off-line scheduling algorithm is evaluated extensively and the limitations of the standard are analyzed. In addition, a guaranteed time service is implemented in a wireless sensor network platform, T-Sensor/Sink node to demonstrate the feasibility of real-time communication based on IEEE 802.15.4.
The other part of this dissertation is motivated by the study of the first part of the dissertation about real-time communication with IEEE 802.15.4 and proposes a multi-channel real-time MAC (MR-MAC) to support real-time communication more efficiently. Major frame (i.e. repeated schedule) of MR-MAC consists of minor frames, and each minor frame starts with SP (Synchronization Period). For multi-hop time synchronization and minor frame management, beacon frames are transmitted in SP. SP is followed by GP (Guaranteed time period), and CP (Contention Period) is located after GP. TDMA is used to access GP and real-time messages are exchanged in this period. CP is accessed with slotted CSMA/CA. Before the next SP, explicit IP (Inactive Period) may exist after CP. In start topology, MR-SA shows 13% of 100% schedulable utilization while IEEE 802.15.4 schedules 100% of messages with up to 7% utilization. Based on MR-MAC, we study real-time message scheduling for tree topology and propose a single-channel multi-hop real time scheduling algorithm (MR-Schedule-S) and a multi-channel real-time scheduling algorithm (MR-SA). MR-Schedule-S checks the schedulability using X2STAR transformation. MR-SA allocates time and frequency slots to meet the deadline constraints of the given message set avoiding the primary interference. The proposed scheduling algorithms with MR-MAC are evaluated in schedulability view point, and the feasibility of MR-MAC and MR-SA is demonstrated with implementation of MR-MAC in Exata, a well qualified network simulator. Even in multi-hop network, the schedulability is better than that in star network.
무선센서네트워크에서 실시간 통신을 필요로 하는 응용은 공장자동화나 프로세스 자동화, 지능형 교통 시스템, 실시간 위치추적, 등 매우 다양하다. 이러한 응용에서 각 메시지는 데드라인 혹은 주기를 가지며 주어진 데드라인 내에 최종 목적지까지 도달해야 한다. 이러한 요구사항을 만족시키기 위해서는 실시간 통신 프로토콜과 실시간 메시지 스케쥴링 알고리듬이 필수적이다. 실시간 통신을 지원하기 위해서 MAC계층은 패킷 충돌을 피할 수 있고 패킷 송수신 시간을 예측할 수 있는 TDMA기법에 의존한다. TDMA기법은 대역폭을 time slot단위로 나누어서 각 노드에게 할당하며, 특정 time slot시간에 그 슬롯을 소유한 노드만이 통신에 참여하도록 하는 다중접속 방식이다. TDMA에 대한 대부분의 연구는 각 노드에게 대역폭을 공평하게 분배하거나 전체 스케쥴의 길이를 최소화하는 것에 초점을 맞추고 있다. 하지만 본 연구에서는 무선센서네트워크에서 메시지의 실시간성을 만족할 수 있도록 타임슬롯을 할당하는 실시간 메시지 스케쥴링 알고리듬을 제안한다.
본 연구는 먼저 무선센서네트워크 분야의 대표적인 표준으로 자리매김하고 있는 IEEE 802.15.4의 beacon-enabled 모드 기반으로 실시간 통신을 지원하는 방안을 고찰한다. IEEE 802.15.4표준은 beacon-enabled 모드에서 수퍼프레임 구조를 정의한다. 이 수퍼 프레임 구조는 PAN Coordinator라 불리는 네트워크 컨트롤러로부터 주기적으로 전송되는 beacon 프레임에 의해서 정의된다. 수퍼 프레임의 길이는 beacon order에 의해서 결정되며 active구간과 inactive구간으로 나눠진다. Active구간의 길이는 SO (Superframe Order)에 의해서 결정되며, Active 구간은 CAP (Contention Access Period) 영역과 CFP (Contention Free Period) 영역으로 구성되며 16개의 동일한 크기의 슬롯으로 나눠진다. IEEE 802.15.4표준은 CFP영역에 Guaranteed Time Slot(GTS)을 할당할 수 있도록 하며 GTS를 할당받은 노드들만 해당 GTS슬롯에 패킷을 송수신할 수 있다. 본 연구는 기존에 제안된 GTS 스케쥴링 알고리듬의 성능을 다양한 측면에서 분석하며, 실시간 통신 측면에서 IEEE 802.15.4의 제약사항을 분석한다. 또한 무선센서네트워크 프로토타입 플랫폼인 T-Sensor/Sink 노드에 Guaranteed Time Service를 구현하여 IEEE 802.15.4기반의 실시간 통신의 가능성을 평가한다.
본 연구의 두 번째 부분은, IEEE 802.15.4에 기반한, 첫 번째 연구에서 얻게 된 결과를 바탕으로 무선센서네트워크에서 실시간 통신을 보다 효율적으로 지원하는 multi-channel real-time MAC(MR-MAC)을 먼저 제안한다. MR-MAC 의 메이저 프레임 (즉, 반복되는 전체 스케쥴)은 여러 개의 마이너 프레임으로 구성되는데, 각 미이너 프레임은 SP (Synchronization Period)로 시작한다. 멀티홉 시각동기 및 마이너 프레임 관리를 위하여 비컨 프레임이 TDMA기반으로 SP구간에서 전송된다. SP 다음에는 GP (Guaranteed Period)가 뒤따르며 CP (Contention Period)는 GP다음에 위치한다. 실시간 메시지는 TDMA방식을 따르는 GP구간을 통해 전송되며 그 외의 패킷들은 CSMA/CA방식으로 CP구간을 통해 송수신된다. CP와 다음 SP 사이에 명시적인 IP (Inactive Period)가 있을 수 있다. Star topology에서 IEEE 802.15.4는 7%까지의 utilization을 갖는 message set들만 100%스케쥴 할 수 있는 반면 MR-MAC은 13%의 100% schedulable utilzation을 보여준다. 본 연구는 MR-MAC을 기본으로 line topology, multi-line topology, 그리고 tree topology를 가정하여 single channel multi-hop scheduling 알고리듬 (MR-Schedule-S) 그리고 multi channel(frequency) real-time message scheduling 알고리듬 (MR-SA) 을 제안한다. 제안된 스케쥴링 알고리듬은 primary/secondary interferences를 고려하여 실시간 메시지를 타임 및 주파수 슬롯에 할당한다. 본 연구는 제안된 스케쥴링 알고리듬을 schedulability측면에서 그 성능을 평가하며, 네트워크 시뮬레이터를 통해서 네트워크 측면의 성능 및 실제 구현 가능성을 평가한다
