A sensor network is an ad hoc network composed of tiny sensor nodes having restricted battery, communication, and computation capabilities. These restrictions have made a sensor network system managed differently, compared with traditional mobile or distributed systems. A database community has viewed a sensor network as a virtual database system and has proposed various energy-efficient query processing algorithms. Recently, there has been much interest in the spatial query processing algorithms based on the locations of sensor nodes. The spatial query acquires sensor readings from sensor nodes inside specified geographical area of interests. The centralized approach which performs the spatial query at a server after acquiring all sensor readings, though simple, it incurs high wireless transmission cost in accessing all sensor nodes. Therefore, various in-network spatial query processing approaches have been proposed. They have focused on reducing wireless transmission cost in a sensor network. However, the existing in-network processing approaches may incur unnecessary wireless transmissions because of the dead space which is spatially indexed but does not contain real sensor nodes. In the first part of this dissertation, we propose a hybrid spatial query processing algorithm which can remove the unnecessary wireless transmissions. The main idea of the hybrid algorithm is to find intermediate results of a spatial query at a server in advance, and use the intermediate results when removing the unnecessary wireless transmissions at in-network query processing. Here, we assume that sensor nodes are placed at fixed locations and the server maintains the same index as the distributed spatial index built in a sensor network. We compare the existing in-network approach through extensive performance experiments and clarify our algorithm’s distinguished features.
Spatial join query as well as the in-network spatial search query has been studied in works of energy-efficient spatial join processing in a single sensor network. However, spatial join queries for two or more different sensor networks, which we call heterogeneous sensor networks, have not been much discussed. In the second part of this dissertation, we present an energy-efficient distributed spatial join algorithm on two heterogeneous sensor networks. Because the distributed spatial join processing causes much wireless transmission cost in accessing sensor nodes of two sensor networks, we propose two optimization schemes for performance improvement of the algorithm. They are a Grid-based Rectangle tree (GR-tree) and a grid-based approximation function. The GR-tree reduces the wireless transmission cost by supporting an efficient in-network spatial search for sensor nodes. The grid-based approximation function reduces the wireless transmission cost by reducing the volume of spatial query ranges which should be pushed down to sensor nodes. Through extensive performance experiments, we show our approach’s distinguished features compared with the $na\"{i}ve$ and existing approaches.
In the last part of this dissertation, we propose a distributed spatial query processor for heterogeneous sensor networks. The proposed query processor can supports various query types of snapshot, periodic, event, and spatial query, can group multiple sensor networks into a logical sensor network, and can support abstraction to various heterogeneous sensor networks. Through the implementation of a prototype application system, we finally show the distributed spatial query processor is applicable for a real sensor network application.
애드 혹 네트워크로 구성될 수 있는 센서 네트워크는 전력, 통신 그리고 컴퓨팅 능력이 제한된 작은 센서 노드들로 구성된다. 센서 노드의 이러한 제한성은 센서 네트워크 시스템이 기존의 모바일 및 분산 시스템과는 다른 방식으로 관리되도록 만들었다. 특히, 데이터베이스 커뮤니티는 이러한 센서 네트워크를 가상의 데이터베이스 시스템으로 간주하고, 센싱 데이터에 대하여 에너지 효율적으로 질의를 처리할 수 있는 다양한 방법들을 제안하여 왔다. 최근에는 입력으로 주어지는 공간영역과 특별한 관계를 가지는 센서 노드의 센싱 값만을 획득하기 위한 공간질의 처리와 관련하여 다양한 방법들이 발표되어 오고 있다. 이러한 공간질의를 처리하는 가장 기본적인 방법은 모든 센싱 값들을 서버로 읽어 들인 후에 서버에서 공간질의를 수행하는 Centralized 방법으로, 이 방법은 비록 단순하다는 장점은 있지만 모든 센서 노드를 접근해야 하기 때문에 많은 무선통신 비용을 소모하게 되는 큰 단점을 가지고 있다. 이러한 센서 노드 접근에 소요되는 무선통신 비용을 줄이기 위하여 In-network 에서 동작 가능한 다양한 공간질의 처리 방법들이 제안되어 왔으나, 이들 방법들도 Dead space에서 불필요한 무선통신을 야기시키는 문제점을 가지고 있다. Dead space는 센서 네트워크 환경에서 구축되는 분산 공간색인에서 센서 노드간의 무선통신 연결 정보로 인하여 공간색인 정보는 존재하나 실제로는 센싱 정보를 포함하는 센서 노드가 존재하지 않는 영역을 의미한다. 본 논문의 첫 번째 부분에서는 이러한 Dead space에서 발생하는 불필요한 무선통신을 제거할 수 있는 하이브리드 공간질의 처리 방법을 제안한다. 이 방법은 공간질의를 서버에서 미리 수행하여 중간결과인 센서 노드들을 검색하고 검색된 센서 노드 정보를 이용하여 In-network 공간질의 처리 과정에서 불필요한 무선통신을 제거하는 방식으로 동작한다. 여기서, 센서 노드들은 모두 위치가 고정되어 있고 센서 네트워크에 구축되어 있는 분산 공간색인 정보가 서버에도 동일하게 구축되어 있다고 가정한다. 성능평가 실험에서는 본 논문에서 제안된 하이브리드 방법과 기존 In-network 방법과의 다양한 성능 비교를 통하여 무선통신 비용 면에서의 효율성을 보여준다.
본 논문의 두 번째 부분에서는 공간질의 처리 방법 중에서도 둘 이상의 이질적인 센서 네트워크에 대하여 복잡한 연산을 필요로 하는 분산 공간조인질의를 에너지 효율적으로 처리할 수 있는 알고리즘을 제안한다. 특히, 본 논문에서는 분산 공간조인질의 처리 과정에서 둘 이상의 센서 네트워크를 접근하는데 소요되는 무선통신 비용을 줄이기 위하여 GR-tree (Grid-based Rectangle tree)의 분산 공간색인 방법과 그리드 기반의 공간객체 근사화의 방법을 제안하고 있다. 여기서, GR-tree는 에너지 효율적인 센서 노드 검색 방법을 제공하고 그리드 기반 공간객체 근사화는 센서 노드에 전송되어야 하는 공간질의 객체들의 볼륨을 줄인다. 성능평가 실험에서는 본 논문에서 제안된 방법과 Centralized 방법 그리고 기존의 다양한 분산 공간색인방법 기반의 공간조인질의 처리 방법과의 성능 비교를 통하여 무선통신 비용 면에서의 효율성을 보여준다.
본 논문의 마지막 부분에서는 이질적인 센서 네트워크들에 대하여 독립적으로 동작 가능한 분산 공간질의 처리 시스템을 제안한다. 제안되는 분산 공간질의 처리 시스템은 기본적으로 일시적, 주기적, 이벤트 그리고 공간질의와 같이 다양한 유형의 사용자 질의를 수행할 수 있는 특징을 가지고 있다. 이외에도 본 시스템은 두 개 이상의 이질적인 센서 네트워크들을 사용자 요구에 따라 하나의 가상 네트워크로 그룹화 할 수 있으며, 이질적인 센서 네트워크들에 대하여 기능적인 추상화를 제공할 수도 있다.
