In this dissertation, we study the problem of processing continuous range queries in a hierarchical wireless sensor network. Recently, as the size of sensor networks increases due to the growth of ubiquitous computing environments and wireless networks, building wireless sensor networks in a \emph{hierarchical} configuration is put forth as a practical approach. Contrasted with the traditional approach of building networks in a ``flat`` structure using sensor devices of the same capability, the hierarchical approach deploys devices of higher-capability in a higher tier, i.e., a tier closer to the server. While query processing in flat sensor networks has been widely studied, the study on query processing in hierarchical sensor networks has been inadequate. In wireless sensor networks, the main costs that should be considered are the energy for sending data and the storage for storing queries. There is a trade-off between these two costs.
Based on this, we first propose a \emph{progressive processing} method that effectively processes a large number of continuous range queries in hierarchical sensor networks. The proposed method uses the query merging technique proposed by Xiang et al. as the basis. In addition, the method considers the trade-off between the two costs. More specifically, it works toward reducing the storage cost at lower-tier nodes by merging more queries and toward reducing the energy cost at higher-tier nodes by merging fewer queries (thereby reducing ``false alarms``). We then present how to build a hierarchical sensor network that is \emph{optimal} with respect to the weighted sum of the two costs. This allows for a cost-based systematic control of the trade-off based on the relative importance between the storage and energy in a given network environment and application. The simulation results show that the proposed method achieves a near-optimal control between the storage and energy and reduces the cost by 1.00 - 3.21 times compared with the cost achieved using the flat (i.e., non-hierarchical) setup as in the work by Xiang et al.
본 학위 논문에서는 계층적 무선 센서 네트워크에서의 연속 범위 질의 처리 문제를 다룬다. 최근 유비퀴터스 컴퓨팅 환경의 발전과 무선 네트워크 기술의 발전에 힘입어 센서 네트워크의 규모가 커짐에 따라, 무선 센서 네트워크를 계층적으로 구성하는 방법이 실용적인 대안으로 대두되고 있다. 이 방법은 동일한 능력을 가진 센서 장치들을 사용하여 네트워크를 구성하는 전통적인 방법인 평면적(flat) 네트워크 구성 방법과는 대비되는 방법으로, 서버에 더 가까운 층인 상위층일수록 더 큰 능력을 가진 센서 장치를 배치하는 방법이다. 현재 평면적인 센서 네트워크에서의 질의 처리 문제는 많은 연구가 이루어지고 있는 반면, 계층적 센서 네트워크에서의 질의 처리 연구는 미흡한 상황이다. 무선 센서 네트워크에서 주요하게 고려해야 할 두 가지 비용은 데이타를 전송하기 위해 필요한 에너지와 질의를 저장하기 위해 필요한 스토리지이다. 이 비용들은 서로 상반관계(trade-off)에 있다.
이를 기반으로, 본 학위 논문에서는 먼저 계층적 센서 네트워크에서 다수의 연속 범위 질의들을 효과적으로 처리하는 점진적 질의 처리 방법을 제안한다. 이 방법은 기본적으로는 Xiang et al.의 질의 병합 기술을 사용하되, 에너지와 스토리지의 상반관계도 고려한다. 즉, 하위층에서는 더 많은 개수의 질의들을 병합하여 스토리지 비용을 줄이고, 상위 층에서는 더 작은 개수의 질의들을 병합하여 착오 경보(false alarm)를 줄임으로써 에너지 비용을 줄인다. 다음으로, 에너지와 스토리지의 가중합(weighted sum)이 최소가 되도록하는 최적의 네트워크 구성 방법을 제시한다. 이 방법은 네트워크 환경이나 응용에 따라, 다른 중요도를 가지는 스토리지와 에너지를 기반으로 이들의 상반관계 비용을 체계적으로 조정할 수 있도록 한다. 마지막으로, 모의실험을 통해 제안한 방법이 스토리지와 에너지를 최적에 근사하도록 조정할 수 있음을 보인다. 그리고, 평면적인 센서 네트워크를 사용한 Xiang et al.의 방법에 비해 총비용이 1.00 - 3.21배 절감됨을 보인다.
