In recent years, rapid advances in sensing and wireless communication technologies have resulted in the availability of wireless sensor networks. Consisting of several small micro-electronic devices which can collect information of surrounding areas and communicate with each other through radio wave, these networks are widely used in a variety of monitoring applications such as habitat monitoring, environmental monitoring, and military surveillance. In these applications, sensor devices are distributed in the environment, periodically sensing and reporting relevant data to the base station to answer queries submitted by the users. While these applications require high accuracy query results and long-term performance of the network, they suffer from resource constraints that do not appear in more traditional wired computing environments.
To save energy and prolong the network lifetime, a common approach, which is called in-network filtering, is often used. The basic idea of the approach is to install a filter at each sensor node to suppress newly observed values at the node from being sent to the base station if the values satisfy some certain conditions that guarantee the required precision of the query results. In this thesis, I study in-network filtering in the context of two popular types of queries, namely approximate aggregation queries and exact top-k queries. For the first type of queries, I propose an effective filter setting method that can improve the performance of filters when sensor readings periodically show similar change patterns. Unlike the previous methods, the proposed method dynamically adjusts the filters by predicting the change of sensor readings in the near future based on historical sensor data. In the second type of queries, I propose two improvements on an already well-known approach, called FILA, to make its filter setting strategy more efficient. I customize the centralized query reevaluation process in FILA so that it can work in a distributed manner and propose a more effective filter updating method. Experimental results with real data traces show that my proposed in-network filter setting and processing methods can really improve the performance of the networks in real-life.
센서의 측정 값들을 네트워크 내에서 필터링하는 테크닉은 통신 비용을 줄여 센서 네트워크의 수명을 늘릴 수 있는 효과적인 방법 중의 하나이다. 이 테크닉은 센서의 측정 값이 센서 노드에서 베이스 스테이션으로 전송될 필요가 없을 때, 이를 방지하여 센서 네트워크 내의 데이터 통신 횟수를 줄인다. 이 테크닉에서는 각 센서 노드에 필터를 두어, 이들의 범위를 동적으로 조절함으로써 질의의 결과를 오차 범위 내에서 사용자에게 주기적으로 전달한다.
본 논문에서는 근사 집계 질의와 정확 top-k 질의 처리를 위한 네트워크 내 필터링 방법에 대해 연구한다. 근사 집계 질의에 대해서는 센서 네트워크를 사용하는 모니터링 응용에서 흔히 관찰되는 특성을 이용하는 새로운 필터 설정 방법을 제안한다. 제안하는 제안하는 방법의 핵심 아이디어는 최근에 측정된 센서 측정 값들을 이용하여 가까운 미래에 대한 센서 측정 값을 예측하는 것이다. 제안하는 방법은 두 부분으로 구성된다. 첫째, 매 센서 측정 주기마다, 최근에 측정된 센서의 측정 값들을 사용하여 각 센서의 새로운 측정 값을 예측하고 이 값을 필터의 중앙 값으로 설정한다. 둘째, 각 센서의 최근 측정 값들의 표준 편차를 각 센서 노드의 변동성으로 추정하고, 이를 기반으로 총 허용 오차를 각 센서 노드에 주기적으로 재할당한다.
정확 top-k 질의에 대해서는 FILA라고 불리는 기존의 고급 방법에 대한 두 가지 개선 방안을 제안한다. 기존의 방법은 질의의 재평가 과정과 필터 설정 방법에서 개선의 여지를 가지고 있으며, 본 논문에서는 각각에 대한 개선 방안을 제안한다. 첫 번째 개선 방안은 기존 FILA의 질의 재평가 과정을 중앙 집중식 처리 방식에서 분산 처리 방식으로 변환하는 것이다. 센서 노드들이 탐색이 필요한 센서의 측정 값을 네트워크 내에서 조기에 탐색함으로써 분산된 형태의 처리가 가능하다. 두 번째 개선 방안은 센서 측정 값의 증가 혹은 감소여부를 고려하지 않던 기존 FILA의 필터 설정 방법을 선형 회귀 모델을 사용하는 방법으로 바꾸는 것이다. 이 모델은 필요시 관련된 필터의 범위를 조절하기 위해 센서 노드 내에서 구축된다.
제안하는 방법의 성능을 평가하기 위해서 현실 데이터를 사용한 다양한 실험을 수행하였다. 첫 번째 질의 형태에 대해서, 실험 결과는 제안하는 방법이 기존의 방법에 비해 좋은 성능을 가지고 있음을 보여주고 있다. 두 번째 질의 형태에 대해서, 실험 결과는 제안하는 두 가지 개선 방안이 기존 방법의 성능을 실제로 개선하고 있음을 보여준다.
