서지주요정보
(An) efficient TDMA scheduling scheme for wireless sensor and actor networks = 무선 센서와 액터 네트워크를 위한 효율적인 TDMA 스케쥴링 기법
서명 / 저자 (An) efficient TDMA scheduling scheme for wireless sensor and actor networks = 무선 센서와 액터 네트워크를 위한 효율적인 TDMA 스케쥴링 기법 / Sang-Hun Chung.
저자명 Chung, Sang-Hun ; 정상훈
발행사항 [대전 : 한국과학기술원, 2008].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8019755

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 08012

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This thesis presents an efficient time slot assignment algorithm for a wireless sensor and actor network (WSAN), which consists of stationary sensors for detecting events and mobile actors for performing tasks. The stationary sensors are typically characterized by low-cost, low-power and tiny devices with limited sensing, computation, and wireless communication capabilities. On the other hands, the mobile actors have better processing capabilities, higher transmission powers and longer battery life. WSANs are expected to be an integral part of systems such as military application, environmental application, health application, and home application. These systems usually need to complete timely missions without human interventions. For example, intrusion detection system alarms the event to the police so that thieves are captured before they run away. Similarly, in a fire extinguishment system, actions should be initiated on the detected area as soon as possible. Due to timely tasks, sensors in WSANs relay the event to actors within given delay bounds. Therefore, the consideration of real-time communication is really necessary in WSANs. In wireless multi-hop network, MAC protocols have a major influence on the latency of packet delivery. Classical contention-based protocols are not suitable for real-time communication, since contention-based channel access requires random backoffs and handshakes (exchange of RTS, CTS and ACK) due to collisions and hidden terminals. Random backoffs and handshakes increase the latency of the data; moreover, it is difficult to estimate how long their duration is. In comparison, TDMA protocols are suitable for WSANs, because they can potentially reduce the delay and provide real-time guarantees by eliminating collisions and solving hidden terminal problems. Traditional TDMA protocols are based on centralized algorithms and their main concern is to reduce the number of assigned slots. Note that the problem of assigning time slots to each node with the minimum number of slots is equivalent to the distance-2 coloring problem, which is known to be NP-complete. However, WSANs require TDMA protocols to perform time slot assignment periodically due to the actor mobility. In order to improve the performance of TDMA protocols, a time slot assignment algorithm should generate not only efficient TDMA scheduling but also reduce periodic run-time overhead. The proposed algorithm offers O($\delta^2$) run-time in the worst case, where δ is the maximum number of one-hop and two-hop neighbors in the network. The average run-time in simulation results is far less than O($\delta^2$), however, while the maximum number of assigned slots is bounded by O($\delta$). In order to reduce the run-time further, we introduce two fundamental processes in the distributed slot assignment and design the algorithm to optimize these processes. We also present an analysis and verify it using ns-2 simulations. Although the algorithm requires time synchronization and prior knowledge of two-hop neighbors, simulation results show that it reduces the run-time significantly and has good scalability in dense networks.

본 학위 논문은 무선 센서와 액터 네트워크(Wireless Sensor and Actor networks; WSAN)을 위한 효율적인 타임 슬롯 할당 알고리즘을 제안한다. WSAN은 사건을 감지하기 위한 정적 센서와 작업(task)을 수행하는 동적 액터로 구성된다. 정적 센서는 보통 저비용(low-cost), 저전력(low-power), 그리고 작은 디바이스로 특징되어지는데, 감지 기능과 계산 기능과 무선 통신 기능에 있어서 한계를 지닌다. 반면에, 액터는 보다 좋은 계산 기능과 보다 높은 전송 기능과 보다 긴 배터리 기능을 지닌다. WSAN은 군사 어플리케이션, 환경 어플리케이션, 건강 어플리케이션, 그리고 홈 어플리케이션과 같은 통합 시스템의 핵심으로 쓰일 것으로 기대되어진다. 이런 시스템은 보통 사람의 개입없이 시간제약적인 임무를 완수해야할 필요가 있다. 예를 들어, 침입 감지 시스템은 도둑이 도망가기 전에 잡히도록 경찰에게 침입사건을 알려야 한다. 비슷하게, 소화 시스템은 화재 지역에 소화 작업을 최대한 빨리 시행해야 한다. 시간제약적인 작업으로 인해 WSAN의 센서는 주어진 제한 시간내에 액터에게 사건을 중계하여 전해야한다. 그러므로, 실시간 통신에 대한 고려는 WSAN에 있어 매우 필요하다. MAC 프로토콜은 무선 멀티홉 네트워크에서 패킷 전달에 걸리는 시간에 매우 큰 영향을 미친다. 전형적인 경쟁기반의 프로토콜은 실시간 통신에 적합하지 않다. 경쟁기반의 채널 액세스는 패킷 충돌과 히든 터미널(hidden terminals)로 인해 랜덤 백오프와 핸드쉐이크(RTS, CTS, ACK의 교환)를 요구하기 때문이다. 여기에서 랜덤 백오프와 핸드쉐이크는 데이터 지연 시간을 크게 늘릴 수 있다. 더욱이, 랜덤 백오프와 핸드쉐이크에 걸리는 시간을 예측하기도 어렵다는 문제점도 발생한다. 반면에, TDMA 프로토콜은 패킷 충돌을 제거하고 히든 터미널 문제를 해결함으로써 데이터 지연을 줄이고, 실시간 보장을 제공할 수 있으므로 WSAN에 적합하다. 전통적인 TDMA 프로토콜은 중앙처리 알고리즘에 기반하였고, 주관심사는 할당 슬롯 수를 줄이는 것이다. 노드는 TDMA 프로토콜을 사용하기 위해서, 두 홉이내의 노드들과 다른 슬롯을 할당받아야 한다. 만일 두 홉이내의 두 노드가 같은 슬롯을 할당받을 경우, 두 노드는 같은 타임 슬롯에 데이터를 전송하고 패킷이 충돌하게된다. 따라서 중간의 노드는 어떤 메세지도 받을 수 없게 된다. TDMA 프로토콜에서 슬롯 할당 문제는 투홉 컬러링(distance-2 coloring)문제와 동일한데, 최소의 슬롯으로 모든 노드에게 겹치지않는 슬롯을 할당하는 것은 NP-complete에 해당한다. 그러나, WSAN에서 TDMA 프로토콜이 액터의 이동때문에 시간 슬롯 할당을 주기적으로 수행해야한다. 다시말해서, TDMA 프로토콜의 성능을 향상하기 위해서, 시간 슬롯 할당 수뿐만 아니라 주기적인 실행 시간 오버헤드를 또한 줄여야한다. 본 학위 논문의 제안 알고리즘은 최악의 상황에서 O($\delta^2$)의 실행 시간 복잡도를 제공한다 (δ는 네크워크에서 한 홉과 두 홉 이웃 노드의 최대 수를 나타낸다). 그러나, 시뮬레이션 결과에서 평균 실행 시간은 O($\delta^2$)보다 훨씬 적게 걸리며, 동시에 최대 슬롯 할당수는 O($\delta$)에 제한된다. 저자는 실행시간을 더욱 향상시키기 위해서 분산 슬롯 할당 기법의 두 가지의 중요한 프로세스를 설명하고 이를 최적화하는 방법을 제안한다. 또한, 제안한 알고리즘의 성능을 분석하고 ns-2 시뮬레이션을 이용하여 이를 검증한다. 본 알고리즘은 시간 동기화(time synchronization)과 두 홉이내의 이웃 노드로 구성된 지역적 위상(local topology)를 필요로 하지만, 시뮬레이션 결과에 의하면 실행 시간을 현저히 줄이고 밀집도 높은 네트워크에도 좋은 확장성을 지닌다.

서지기타정보

서지기타정보
청구기호 {DCS 08012
형태사항 viii, 54 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 정상훈
지도교수의 영문표기 : Hyun-Soo Yoon
지도교수의 한글표기 : 윤현수
수록잡지정보 : "An Efficient TDMA Scheduling Scheme for Wireless Sensor and Actor Networks". IEICE Transactions on Communications, vol.E91-B, no.6, (June)
학위논문 학위논문(박사) - 한국과학기술원 : 전산학전공,
서지주기 References : p. 52-54
주제 wireless sensor and actor networks;wireless sensor networks;medium access control;TDMA protocols;
무선 센서와 액터 네트워크;무선 센서 네트워크;MAC;TDMA 프로토콜;
QR CODE qr code