Recent advances in ubiquitous computing have led to the emergence of wireless sensor networks. Wireless sensor networks enable continuous data collection on unprecedented scales and give us new opportunities for observing and interacting with the physical world. However, collecting data from wireless sensor networks is challenging because of limited resources of sensor nodes. Since the energy constraint is the most critical issue in wireless sensor networks, it is crucial to reduce the energy consumption for query processing. This dissertation deals with energy-efficient query processing problems in wireless sensor networks.
An wireless sensor network is usually deployed with static sensor nodes to collect sensor data in the region of interest. Nowadays, mobile wireless sensor networks have emerged with the advances in distributed robotics and low power embedded computing technologies. Mobile wireless sensor networks have similar characteristics to their static counterparts but they have more challenges because of the mobility of sensor nodes. In this dissertation, we focus on both static and mobile wireless sensor network environments.
First, we study the iceberg query processing problem in static wireless sensor networks. The iceberg query finds data whose aggregate values exceed a pre-specified threshold. This iceberg query can be used in various wireless sensor network applications such as environmental monitoring, industrial maintenance and battlefield surveillance to extract meaningful information from wireless sensor networks. To process an iceberg query in wireless sensor networks, all sensor data have to be aggregated and then sensor data whose aggregate values are smaller than the threshold are eliminated. Whether a certain sensor data is in the query result depends on the other sensor data values. Since sensor nodes are distributed, communications between sensor nodes are required to know the sensor data from the other sensor nodes. However, sensor nodes have limited energy resources and communication is a primary source of the energy consumption. Thus, reducing the communication overhead is the most critical issue in wireless sensor networks. In this dissertation, we propose an energy-efficient iceberg query processing technique in static wireless sensor networks. To compactly represent the data transmitted, a lossless sensor data compression method based on an established mathematical property is devised. To reduce the energy consumption caused by the number of data transmitted, a filtering based query processing method is devised. Using the temporal correlation of sensor data and the semantics of an iceberg query, a prediction model for the future query result is proposed. Based on the predicted future query result, sensor nodes effectively filter out unnecessary transmissions.
Second, we tackle the top-k query processing problem in mobile wireless sensor networks. A mobile wireless sensor network is a wireless sensor network in which sensor nodes are mobile. The mobile sensor nodes move around and explore their surrounding areas. Top-k queries are useful in many mobile wireless sensor network applications. However, the mobility of sensor nodes incurs new challenges in addition to the problem of static wireless sensor networks. Since mobile sensor nodes tend to move continuously, the network condition changes frequently and they consume considerably more energy than static sensor nodes. In this dissertation, we propose an efficient top-k query processing framework in a mobile wireless sensor network environment. To construct an efficient routing topology, we devise a mobility-aware routing method. Using the semantics of the top-k query, we develop a filter-based data collection method which can save the energy consumption and provide more accurate query results. We also devise a data compression method for disconnected sensor nodes to deal with the problem of limited memory space of sensor nodes.
Finally, we perform extensive experiments to evaluate the performance of the proposed approaches using both real and synthetic datasets. The experimental results confirm the energy-efficiency and the effectiveness of the proposed approaches. For the iceberg query processing problem in static wireless sensor networks, on the average, our approach consumes approximately 90% less energy than an existing approach while providing nearly 100% accurate query results. For the top-k query processing problem in mobile wireless sensor networks, our approach reduces energy consumption up to about 68% than other top-k query processing approaches and provides near 100% accuracy of the query results. In addition, on the average, our approach uses approximately 47.5% less memory than a compression method for low powered wireless sensor nodes.
유비쿼터스 컴퓨팅의 발전은 무선 센서 네트워크의 등장을 야기하였다. 무선 센서 네트워크는 베이스 스테이션과 센싱, 프로세싱, 통신 능력을 지닌 많은 수의 센서 노드들로 구성된다. 이러한 무선 센서 네트워크는 다양한 환경에 배치되어 유례없는 방대한 데이터의 수집을 가능하게 하였고 물리적 환경과 상호작용할 수 있는 기회를 제공해 주었다. 그러나 센서 노드의 제한된 자원은 무선 센서 네트워크에서 데이터를 수집하는 것을 어렵게 한다. 특히, 에너지는 무선 센서 네트워크에서 가장 중요한 자원이므로 질의 처리를 위한 에너지 소모를 줄이는 것은 무선 센서 네트워크에서의 주요한 이슈이다. 따라서 본 학위 논문에서는 무선 센서 네트워크에서의 에너지 효율적인 질의 처리 문제들에 관하여 논의하도록 한다.
무선 센서 네트워크는 대개 특정 지역에 고정 센서 노드를 배치하여 구성되었으나, 최근 분산 로보팅 기술과 저전력 컴퓨팅 기술의 발전으로 센서 노드에 이동성을 부여한 모바일 무선 센서 네트워크도 등장하고 있다. 모바일 무선 센서 네트워크는 고정 무선 센서 네트워크가 가지는 문제들에 더해 센서 노드의 이동성으로 인한 문제들도 가진다. 무선 센서 네트워크의 다양한 환경을 고려하기 위해서 본 학위 논문에서는 고정 및 모바일 무선 센서 네트워크 환경 모두에 초점을 맞추었다.
첫째, 고정 무선 센서 네트워크에서의 Iceberg 질의 처리 방법에 대해 연구하였다. Iceberg 질의란 집계 값(Aggregate Value)이 특정 한계 값(Threshold)을 초과하는 데이터를 찾는 것이다. 이러한 Iceberg 질의는 환경 모니터링, 산업 자원 관리 및 전장 모니터링과 같은 다양한 무선 센서 네트워크 응용에서 의미 있는 정보를 추출하기 위해 사용된다. 무선 센서 네트워크 환경에서 Iceberg 질의를 처리하기 위해서는 센서 노드에서 발생된 모든 센서 데이터를 집계한 뒤 한계 값보다 작은 집계 값을 가지는 센서 데이터를 제거해야 한다. 특정 센서 데이터가 질의 결과에 포함되는지 여부는 다른 센서 데이터 값에 따라 결정된다. 센서 노드들은 분산되어 있으므로 다른 센서 노드에서 발생된 센서 데이터를 알기 위해서는 통신이 필요하다. 그러나 센서 노드들은 제한된 에너지 자원을 가지며 무선 센서 네트워크에서의 에너지는 대부분 통신에 의해 소모되는 특성이 있다. 따라서 통신에 따른 오버헤드를 줄이는 것은 무선 센서 네트워크에서 대단히 중요한 문제이다. 본 학위 논문에서는 이러한 특성을 바탕으로 고정 무선 센서 네트워크 환경에서의 에너지 효율적인 Iceberg 질의 처리 기법을 제안하였다. 센서 노드의 통신에 따른 에너지 소모는 전송되는 데이터의 크기 및 수에 비례하므로 이 모두를 줄이는 것이 필요하다. 먼저, 전송되는 데이터의 크기를 줄이기 위해, 정수론에서의 산술의 기본 정리(Fundamental Theorem of Arithmetic)에 기반한 무손실 센서 데이터 압축 기법을 제안하였다. 이와 더불어, 전송되는 데이터의 수에 따른 에너지 소모를 줄이기 위해, 예측 모델을 사용한 필터링 기반 질의 처리 방법을 제안하였다. 예측 모델은 센서 데이터의 시간적 상관 관계(Temporal Correlation)와 Iceberg 질의의 의미적 특성을 사용하여 고안하였고, 예측 모델에 의한 질의 결과에 기반하여 센서 노드들은 불필요한 전송을 효과적으로 필터링 할 수 있도록 하였다.
둘째, 모바일 무선 센서 네트워크에서의 Top-k 질의 처리 방법에 대해 연구하였다. 모바일 무선 센서 네트워크는 센서 노드가 이동성을 갖는 무선 센서 네트워크이다. 모바일 센서 노드는 움직이면서 주변 지역에 대한 정보를 수집한다. Top-k 질의는 k개의 높거나 또는 낮은 값을 가지는 센서 데이터를 찾기 위한 것으로, 환경 모니터링, 재난 또는 응급 상황 관리 및 전장 모니터링과 같은 다양한 모바일 무선 센서 네트워크 응용에서 유용하게 사용된다. 그러나 센서 노드의 이동성은 고정 무선 센서 네트워크에서 발생하는 문제뿐만 아니라 새로운 문제들을 야기한다. 모바일 센서 노드는 계속해서 움직이므로 네트워크의 상태가 끊임없이 변하게 되고, 고정 센서 노드보다 더 많은 에너지를 소모하는 특성이 있다. 본 학위 논문에서는 이러한 문제들을 해결하기 위해 모바일 무선 센서 네트워크 환경에서 Top-k 질의를 에너지 효율적으로 처리할 수 있는 프레임워크를 제안하였다. 먼저, 네트워크 상태의 잦은 변경 및 센서 노드의 에너지 소모 문제를 해결하기 위해 이동성 인식(Mobility-aware) 라우팅 방법을 고안하였다. 또한, Top-k 질의의 의미적 특성을 사용하여 에너지 소모를 줄이면서도 정확한 질의 결과를 줄 수 있는 필터 기반 데이터 수집 방법을 제안하였다. 이와 더불어, 센서 노드의 네트워크 연결이 끊어진 경우, 메모리 제약으로 인해 센서 데이터를 저장할 수 없는 문제를 해결 하기 위한 데이터 압축 기법을 제안하였다.
마지막으로, 제안한 방법들의 성능을 평가하기 위해 다양한 실험들을 수행하였다. 실험 결과는 제안한 방법들의 에너지 효율성과 효용성을 입증하여 준다. 고정 센서 네트워크 환경에서의 Iceberg 질의 처리 문제에 대해서는, 제안한 방법이 비교 방법에 비해 평균적으로 약 90% 정도 에너지를 덜 사용하면서도 정확도가 거의 100%에 가까운 질의 결과를 생성하였다. 모바일 무선 센서 네트워크 환경에서의 Top-k 질의 처리 문제에 있어서는, 제안한 방법이 비교 방법에 비해 최대 약 68% 정도 에너지 소모를 줄이면서도 정확도가 거의 100%에 가까운 질의 결과를 생성하였다. 그리고 메모리 소모에 있어서도 제안한 방법이 비교 방법에 비해 약 47.5% 정도 메모리를 덜 사용함을 알 수 있었다.
