A sensor network is a network of many small wireless sensor device nodes (called nodes, for short) embedded in the physical world. Owing to the dramatic advances of related technologies, sensor nodes themselves become smaller and cheaper as well as stronger in the aspect of computing power. As a result, sensor networks can be applied to diverse application areas demanding various query capabilities.
Continuous query processing has been extensively discussed in many papers because the most common function of sensor networks is to report continuously sensed values through successive monitoring of environmental phenomena. Performance improvement for continuous query processing is important because continuous queries are processed many times, e.g., hundreds of thousands of times.
In sensor networks, continuous query processing consists of two phases; $\It{query transmission and routing tree construction}$ and $\It{query result transmission}$. In the former, a user query is transmitted to all nodes in the region specified by the query, and, at the same time, each nodes select its parent node to report its data. In this manner, both query transmission and routing tree construction are performed simultaneously. In the latter, each node in the routing tree periodically reports its result to its parent in a bottom up fashion. Generally, query transmission and routing tree construction is performed once while query result transmission is perform repeatedly.
In this dissertation, we propose efficient methods for above both phases. For query transmission and routing tree construction phase, we considers a continuous query whose query region is specified by a KNN(K Nearest Neighbor) predicate. We proposed an efficient method to find the region specified by KNN predicate and to construct a more message-efficient routing tree.
For query result transmission phase, we propose an efficient method to process continuous aggregation queries with tolerable error thresholds. continuous aggregation queries with tolerable error thresholds have many applications in sensor networks. In previous methods, the error threshold in each node periodically adjusted based on the global statistics collected in the central site that are obtained from all nodes in the network. These methods requires that users specify a few parameters, e.g., adjustment period. However, determination of these parameters by users, in practice, is very difficult and undesirable for sensor network applications demanding unattended operations in dynamically changing environments. We propose a new in-network data aggregation protocol, called Distributed Adaptive Filtering(DAF) protocol. It performs data aggregation an error threshold adjustment simultaneously, and works in a distributed manner and proceeds adaptively in the sense that the filtering condition in each node is adaptively changed by using only local information. It dose not requires user parameters that are used in the previous methods. We show through various experiments that the proposed method outperforms other existing methods.
We also propose a new method to process continuous aggregation queries with $\It{tolerable relative error thresholds}$. In previous work, tolerable relative error thresholds have been considered less than absolute ones. Our method transforms a query with a relative error threshold into a query with absolute one, and achieve adaptive adjustment by using DAF protocol.
최근의 전자통신기술의 발전으로 인해, 작은 무선 센서 장치들로 구성된 센서 네트워크를 실제 환경에 배치하여 사용하는 것이 가능하게 되었다. 많은 연구에서 센서 네트워크를 활용할 수 있는 다양한 응용들과 함께, 각 응용의 지원을 위해 센서 네트워크를 효과적으로 이용하는 방법들이 제안되었다. 센서 네트워크 응용에서 흔히 요구되는 기능은 모니터링(monitoring) 기능으로, 주어진 시간 동안 주기적으로 결과값을 돌려주는 연속 질의(continuous query) 형태를 가진다. 연속 질의는 수백에서 수천번 이상 반복해서 수행되기 때문에, 성능의 개선이 특히 중요하다.
센서 네트워크에서 연속 질의가 처리되는 방법은 2단계로 이루어진다. 첫번째는 $\bf{질의 전달 단계}$로 사용자가 요청한 질의를 센서 네트워크 내의 관련 센서 노드들에게 전달하는 단계이고, 두번째는 $\bf{질의 결과 전달 단계}$로 주기적으로 관련 센서 노드들에서 생성된 질의 결과를 사용자에게 전달하는 단계이다. 일반적으로 연속 질의의 질의 전달은 한번만 수행되고, 질의 결과 전달은 주기적으로 반복적해서 수행된다. 따라서 질의 결과 전달 단계에 대해 많은 연구가 되어왔다. 본 논문은 앞서 설명한 연속 질의 처리 방법의 두 단계에 대해 각각 효율적인 방법을 제안한다.
우선, 주기적으로 반복적으로 수행되는 질의 결과 전달 단계에서는 오차를 허용하는 연속 집계 질의에 대한 효율적인 처리 방법을 제안한다. 오차를 허용하는 연속 집계 질의는 많은 센서 응용에 적용 가능하다. 기존 연구는 크게 $\bf{절대 허용 오차}$를 고려한 연구와 $\bf{상대 허용 오차}$를 고려한 연구로 구분된다. 절대 허용 오차에 대한 연구에서는 주기적으로 모든 노드의 상태 정보를 수집하여, 각 노드의 허용 오차를 중앙집중적으로 조정하는 방법이 제안되었다. 하지만, 이 방법을 이용하기 위해서는 사용자가 조정 주기 등을 직접 지정해 주어야 한다. 이런 특징은 사용자의 개입없이 동작해야 하는 센서 응용에서는 적합하지 않을 뿐만 아니라, 동적으로 변하는 센서 네트워크 환경에서 사용자가 조정 주기를 적절히 지정해 주는 것은 실질적으로는 어렵다. 본 논문에서는 새로운 네트워크 내 집계(in-network aggregation) 방법인 분산 적응 필터링(distributed adaptive filtering) 프로토콜을 제안한다. 제안된 프로토콜은 집계와 각 노드의 절대 허용 오차 조정을 동시에 수행하기 때문에, 기존 방법들에서 요구되던 조정 주기 등의 정보가 요구되지 않는다. 또한, 각 노드의 절대 허용 오차를 노드 내의 정보만을 이용하여 동적으로 조정한다는 점에서 분산적이고 적응적이다. 다양한 실험을 통하여 제안된 프로토콜이 기존 방법에 비해 성능이 뛰어남을 보였다.
상대 허용 오차에 대해서는 허용 오차를 조정하지 않는 정적인 방법만이 제안되어 있다. 기존 연구들은 주로 절대 허용 오차를 고려하였고, 상대 허용 오차에 대한 연구가 부족하다. 본 논문에서는 상대 허용 오차가 주어진 질의를 절대 허용 오차가 주어진 질의로 변경한 후에, 절대 허용 오차에 대한 적응적 필터링 방법들을 이용해서 필터링을 수행함으로써 상대 오차에 대한 적응적 필터링을 구현하였다. 그리고, 다양한 실험을 통하여 제안된 프로토콜이 기존 방법에 비해 성능이 뛰어남을 보였다.
마지막으로, 본 논문에서는 질의 전달 단계가 여러 번 수행되는 질의를 제안하고, 이를 효율적으로 처리하는 방법을 제안하였다. 제안된 질의는 $\bf{제한조건이 있는 KNN(K Nearest Neighbor) 질의}$로 특정 지점 p를 중심으로 제한조건을 만족하면서 가장 가까운 k개의 센서 노드를 찾는 질의이다. 본 논문에서 고려한 제한 조건은 센서 노드의 측정값에 대한 제한 조건으로, '현재 노드를 중심으로 배터리가 50%이상 남아있는 가장 가까운 k개의 노드를 찾아라' 또는 '특정 지점 p를 중심으로 온도가 50도 이상인 가장 가까운 k개의 노드를 찾아라'같은 질의가 있을 수 있다. 센서 노드의 측정값은 시간에 따라 변경되기 때문에, 질의를 만족시키는 노드들의 집합도 시간에 따라 변경된다. 기존 KNN 질의 처리 방법들은 고정적인 질의 영역을 지정한 후 질의 전달 단계를 한 번만 수행하기 때문에, 이런 질의를 효과적으로 처리하지 못한다. 본 논문에서는 점진적인 원형 포워딩(incremental circular forwarding) 방법을 제안한다. 검색 영역을 점진적으로 확장하면서, 관련 노드들을 효율적으로 찾아낸다.
