Fast and Energy Efficient Data Collection Schemes for Wireless Sensor Networks

Abstract

Data collection is an essential part of various applications for wireless sensor networks (WSNs). The most important issues in data collection are energy conservation and data delivery time minimization. This dissertation addresses two issues related to data collection based on the movement of the sink node: stop point selection, where the sink node stops to collect data from sensor nodes, and time slot assignment, how to relay data to the stationary sink node using time division multiplexing and contention-free communication. Stop point selection is the problem of selecting a set of stop points that results in low energy usage by the sensor nodes where a mobile sink is used to collect data from the sensor nodes in a WSN. This research assumes an approach in which a mobile sink travels along a fixed path and uses a stop-and-collect protocol. The problem of selecting an optimal set of stop points is shown to be an NP-hard problem. Then, an Integer Linear Programming formulation is used to derive an optimal algorithm that can be used for small problem instances. Next, a polynomial-time Tabu-search-based heuristic algorithm is proposed. Simulation results show that the proposed heuristic algorithm results in near-optimal energy usage values with low execution times, thereby making it suitable for large-sized WSNs. Convergecast, which is essentially the inverse of broadcast, can be used for data collection in a WSN. Time slot assignment is a problem for convergecast with minimum delay and minimum energy consumption in a WSN that uses time division multiplexing in order to schedule its node-to-node communication in a time-bounded manner. A realistic system model and problem is formulated for WSNs. Then, based on a detailed analysis of this problem, a heuristic solution based on time slot assignments is proposed. Simulation results are used to show that the proposed algorithm performs significantly better than alternative methods for this problem. The simulation results also show that the data delivery time of the proposed algorithm is close to the theoretical bound. Furthermore, total energy consumption is significantly reduced, when compared to the alternatives, due to the time slot assignment method used in the proposed algorithm.

무선 센서 네트워크는 목표 지역에서 자동적으로 데이터를 수집하기 위한 네트워크로 무선 통신이 가능한 센서 노드로 구성된다. 전원 공급 문제로 인해 무선 센서 네트워크는 센서 노드의 에너지 소모를 최소화 하는 방향으로 설계된다. 이 논문은 데이터 수집을 위한 무선 센서 네트워크에서 싱크 노드의 움직임에 따라 정지 지점 선택과 (어떤 위치에서 정지하여 데이터를 수집할 것인가) 타임 슬롯 분배의 (정지한 싱크 노드가 어떤 식으로 데이터를 수집할 것인가) 두 가지 주제에 대해 에너지 소모와 데이터 전달 시간을 최소화 하는 방식을 다루고 있다. 정지 지점 선택 문제는 싱크 노드가 센서 노드로부터 데이터를 수집하기 위해 이동하는 무선 센서 네트워크에서 에너지 소모를 최소화 할 수 있는 정지 지점의 집합을 찾는 문제이다. 본 연구에서는 모바일 싱크가 지정된 경로를 이동하며 정지 지점에서 멈추어 데이터를 수집하는 방식을 가정하고 이러한 조건에서 최적 정지 지점을 찾는 것은 NP-hard 문제임을 확인하였다. 이 문제에 접근하기 위해 Tabu search 를 기반으로 한 휴리스틱 알고리즘 TA-BU-PSP 를 제안하였다. 제안한 알고리즘의 성능을 평가하기 위해 모바일 싱크의 경로 길이, 센서 노드의 밀집도, 데이터 생성량 등을 변화시켜가며 다른 휴리스틱 알고리즘과 함께 시뮬레이션을 수행하였다. 다양한 조건에 대해 제안한 TABU-PSP 알고리즘은 다른 휴리스틱 알고리즘에 비해 적은 에너지를 소모하는 것으로 나타났으며, 적은 계산 시간만을 사용하여 linear integer programming 을 통해 얻은 최적 정지 지점을 사용한 것과 유사한 수준의 에너지를 소비하는 정지 지점을 찾을 수 있음을 확인하였다. 타임 슬롯 분배 문제는 무선 센서 네트워크가 센서 노드 사이의 통신을 위해 시분할 다중화 방식을 사용하는 환경에서 데이터 전달 시간과 에너지 소모를 최소화 하도록 타임 슬롯을 분배하는 문제이다. 본 연구에서는 센서 노드의 wake-up 지연 시간과 시간 동기화 에러 등을 고려한 현실적인 모델을 바탕으로 타임 슬롯 분배 문제를 정의하였다. 주어진 데이터 수집 트리에서 싱크 노드로부터 하나의 자식 노드를 갖는 subtree를 대상으로 “Dominant subtree” 를 선정하고 이 subtree의 빈 슬롯을 사용하는 방식으로 이론적으로 가능한 최소의 타임 슬롯 수를 유도하였다. 이러한 접근 방식을 바탕으로 최대 자손을 가진 서브트리에 우선적으로 타임 슬롯을 분배하는 알고리즘을 제안하여 시뮬레이션을 수행, 제안한 알고리즘을 통해 이론적으로 가능한 최소 타임 슬롯 수와 일치하는 타임 슬롯 분배가 가능하다는 것을 확인하였다. 또한 연속적인 타임 슬롯 사용을 최대화하기 위해 타임 슬롯 재배치 알고리즘을 제안하여 기존에 제안된 알고리즘에 비해 적은 에너지를 소모하여 짧은 데이터 전달 시간을 얻을 수 있음을 확인하였다.