In recent years, rapid advances in sensing and wireless communication technologies have resulted in the availability of wireless sensor networks. Consisting of several micro-electronic sensor devices, which can collect information of surrounding areas and communicate with each other through radio waves, these networks are widely used in a variety of monitoring applications such as habitat monitoring, environmental observation, and military surveillance. In these applications, small and battery-powered sensor devices are distributed into the environment, periodically sensing and reporting relevant data to the base station to answer continuous monitoring queries submitted by the users. While these applications require highly accurate query results and long-term performance of the network, wireless sensor networks suffer from the energy limitation that do not appear in traditionally wired computing environments.
In this dissertation, we study the processing of three representative types of monitoring queries so that the energy at sensor devices is used as efficient as possible. First of all, top-k monitoring queries are investigated due to their usefulness in many practical monitoring situations. A query of this type continuously returns a list of k ordered sensor nodes with the highest (or lowest) sensor readings to the base station. To process these queries, a well-known approach is to install a filter at each sensor node to avoid unnecessary transmissions of the sensor readings. Based on this approach, we propose a new top-k monitoring method, named Distributed Adaptive Filter-based Monitoring. In this method, we first propose a new query reevaluation algorithm that works distributedly in the network to reduce the communication cost of sending probe messages. Then, we present an adaptive filter updating algorithm which is based on predicted benefits to lower down the transmission cost of sending updated filters to the sensor nodes. Experimental results on real data traces show that our proposed method performs much better than other existing methods in terms of both network lifetime and average energy consumption.
After top-k, we examine Reverse Nearest Neighbor (RNN) monitoring queries. Although RNN monitoring queries are useful in many object tracking scenarios using wireless sensor networks, there is still no research work addressing them in this environment. Meanwhile, even though some algorithms have been proposed to process RNN monitoring queries in other environments, they are not quite appropriate for wireless sensor networks. The reason is that these algorithms all adopt centralized processing which requires all object locations sent to a central server to be processed further, thus exhausts quickly the sensor nodes` limited power. Therefore, we study the problem of processing RNN monitoring queries in wireless sensor networks. We consider both two cases of RNN monitoring queries, namely monochromatic and bichromatic, and develop for each case a localized and incremental monitoring algorithm. Our main ideas are to localize the searching task to only relevant sensor nodes near the query point and to establish and incrementally maintain some restricted monitoring areas for each query. During the major part of the query lifetime, only object location updates from these areas instead of the whole space need to be collected and processed. Experimental results show that the proposed algorithms are scalable and an order of magnitude more efficient than the centralized ones in terms of energy consumption.
Finally, we study lifetime-constrained selection monitoring queries. In some monitoring applications, the user needs the network to be alive and runs for at least a specific amount of time. However, due to limited sources of battery power, sensor nodes often cannot operate long enough to satisfy the network lifetime designated by the user. Hence, we propose a new approach to process lifetime-constrained monitoring queries in wireless sensor networks. The basic idea of our approach is to tune the query`s filtering condition adaptively to control the amounts of energy used for message transmissions at the sensor nodes. We propose for lifetime-constrained selection monitoring queries a query condition tuning algorithm. When this algorithm runs, the query`s filtering condition is adjusted adaptively so that the required network lifetime can be satisfied and the amount of information reported to the user is as high as possible. Experiments on real data traces show two important results. First, our proposed algorithm always guarantees the network lifetime requirements. Second, the query`s filtering conditions obtained by our algorithm are very close to those obtained by the offline optimal algorithm in which all sensor readings are assumed to be known a priori.
최근 센서와 무선 통신 기술의 발전에 힘입어 무선 센서 네트워크를 많은 분야에서 활용할 수 있게 되었다. 무선 센서 네트워크는 주변의 여러 가지 정보를 모을 수 있는 센서가 탑재된 작은 전자 기기들로 구성되고, 이들은 무선 통신을 통해 서로 정보를 교환한다. 현재 무선 센서 네트워크는 동식물의 서식지 관찰, 주변 환경 관측, 군사 상황 감시 등 여러 분야에서 사용되고 있다. 이런 응용 분야에서 사용되는 센서 노드는 주로 크기가 작고 배터리를 전력 공급원으로 사용하며, 관찰하려는 환경에 설치된 후에는 베이스스테이션이 사용자의 연속 질의에 답할 수 있도록 주기적으로 유용한 정보들을 베이스스테이션에게 보고한다. 이런 응용에서는 질의의 결과 값이 매우 정확해야 하고 네트워크를 오랜 기간 동안 사용할 수 있어야 한다. 하지만, 기존 유선 네트워크 환경에서는 문제가 되지 않았던 제한된 에너지 양 때문에 이런 요구 조건을 만족시키기가 쉽지 않다.
본 논문에서는 몇 가지 대표적인 질의 종류에 대해 센서 장비들의 에너지를 최대한 효율적으로 사용할 수 있는 방법들을 제시한다. 먼저, 모니터링 응용에서 가장 많이 사용 중인 top-k 질의에 대해 다룬다. Top-k 질의는 센서 노드들이 베이스스테이션에게 가장 높은 (혹은 낮은) k개의 센서 값들을 연속적으로 알리는 질의다. 널리 알려진 top-k 질의 처리 방법은 센서 노드들이 필요 없는 값을 전송하지 않도록 각 센서 노드에 필터를 설정해두는 것이다. 본 논문에서는 이 방법을 개선시킨 Distributed Adaptive Filter-Based Monitoring (DAFM) 방법을 제안한다. DAFM에서는 기존 방법의 탐색 메시지 (probe message)에 필요한 메시지 전송 비용을 줄이기 위해 새로운 질의 재평가 방법을 제안한다. 그 후, 센서 노드에 새로운 필터를 전송하는 데 필요한 비용을 줄이기 위해 기대 이익 정보를 활용하는 적응적 필터 갱신 기법을 소개한다. 실험에서는 실제 데이터를 사용하여 본 논문에서 제안한 방법이 기존 방법들에 비해 수명이나 평균 에너지 소모 측면에서 훨씬 높은 성능을 나타냄을 보인다.
두 번째로 Reverse Nearest Neighbor (RNN) 질의에 대해 다룬다. RNN 질의가 객체 추적 응용에서 유용하긴 하지만 아직 무선 센서 네트워크에 최적화된 방법은 제안된 것이 없다. 또한, 다른 환경에서 RNN 모니터링 질의를 처리하기 위해 제안된 방법들은 무선 센서 네트워크에 적합하지 않다. 기존 방법들은 모든 객체들의 정보를 중앙 서버에 보내는 중앙집중식 처리 방법을 사용하기 때문에 센서 노드의 제한된 에너지를 매우 빨리 소모한다. 따라서, 본 논문에서는 무선 센서 네트워크에 적합한 RNN 질의 처리 방법을 제안한다. 본 논문에서는 monochromatic RNN질의와 bichromatic RNN질의를 모두 고려하고, 각 질의 형태에 대해 분산처리가 가능하고 점진적으로 결과 갱신이 가능한 알고리즘을 제안한다. 제안하는 방법에서는 질의 지점에 가까운 센서 노드에게만 검색을 요청하여 작업을 지역화시키고 각 질의에 대해 제한된 영역을 유지함으로써 점진적으로 결과를 갱신한다. 질의 수명의 대부분 시간 동안 객체 위치의 갱신은 위의 제한된 영역에서만 발생하기 때문에 모든 객체들의 위치를 베이스스테이션에 전송하여 새로운 결과를 만들어내는 작업을 피한다. 실험에서는 제안된 방법이 중앙집중식 방법보다 확장성이 뛰어나고 에너지 소비 측면에서 훨씬 높은 성능을 나타냄을 보인다.
마지막으로 최소 수명이 주어진 질의 형태에 대해 다룬다. 몇 가지 응용 분야에서는 질의에 네트워크가 적어도 특정 시간 동안 작동 가능해야 한다는 조건이 주어진다. 하지만 센서 노드의 에너지 양은 제한적이기 때문에 사용자가 원하는 시간 동안 네트워크가 작동하기 어려운 경우가 많다. 본 논문에서는 수명이 주어진 질의를 처리할 수 있는 방법을 제안한다. 제안하는 방법은 센서 노드에서 메시지 전송에 사용하는 에너지 양을 제어하기 위해 질의의 필터 조건을 적응적으로 조절한다. 제안하는 방법이 실행되면 사용자가 기술한 네트워크의 최소 수명과 요구한 정보의 양에 대한 조건을 만족시킬 수 있도록 질의의 필터 조건을 적응적으로 조절한다. 실험에서는 실제 데이터를 사용하여 본 논문에서 제안한 방법이 네트워크 수명에 대한 조건을 항상 만족함을 보이고, 적응적으로 조절된 질의의 필터 조건이 모든 데이터를 미리 알고 있다는 가정 아래 도출한 최적의 필터 조건에 매우 근접함을 보인다.
