In sensor networks, summarized data are often more interested
than raw, detailed data. Since sensor nodes have
limited power, it is important to process aggregation queries
energy efficiently to prolong the lifetime of sensor networks.
In this dissertation, we are concerned with energy efficient
aggregation query processing in sensor networks.
In-network processing of aggregation queries
is a widely accepted technique to reduce energy consumption
for wireless communication, which is a main source of energy
consumption in sensor nodes.
The main idea of in-network processing is that
aggregates are processed in the network as data flow
through the sensor nodes. Unnecessary data are discarded
and relevant sensor readings are combined into
a more compact form whenever possible.
How to deliver sensor readings to the base station, where
the user requests a query and receive the answer of the query,
is important for energy efficient in-network processing.
Since an efficient routing structure for in-network processing
may be different query by query, a routing method should
consider query-specific cost reduction for energy efficient
in-network processing of aggregation queries.
Most of the existing routing methods, however, do not consider
queries when deciding how to route sensor readings.
Although there is some work that considers query-specific cost reduction,
the applicability of their work is limited. In other words,
their methods are designed either for specific queries or
for particular sensor network environments.
In this dissertation, we propose a query-specific routing approach to
energy efficient in-network processing of aggregation queries
in sensor networks.
Aggregation queries either have grouping conditions or not.
For aggregation queries without grouping, any two sensor readings
can be merged into a small partial aggregate; on the other hand,
for grouped aggregation queries, only those sensor readings
in the same group can be merged. Because of this difference,
the two types of aggregation queries should be dealt with
differently for energy efficient in-network processing.
In the first part of the dissertation, we consider
aggregation queries without grouping.
We propose a query-specific routing tree called the early merging tree (EM-tree).
EM-trees are constructed separately for each query
and are built by using a simple but novel distance
measure called the minimum mergeable distance.
The idea of the EM-tree is that direction of
message transmissions is decided in such a way
that the chances of in-network processing are increased.
We show by performance evaluation that the EM-tree
outperforms existing routing trees over a variety of
sensor network environments.
In the second part of the dissertation,
we focus on query processing of grouped aggregation queries.
We propose a multipath routing approach,
called Content-based Multipath Routing (CMR),
for energy efficient in-network processing of grouped aggregation queries.
In CMR, a node forwards tuples of
partially computed aggregates of different groups
to different nodes such that in-network processing
can accomplish more data reduction.
The experimental study shows that CMR outperforms
the existing tree-based routing methods for
grouped aggregation queries in various sensor
network environments.
센서 네트워크에서는 보통 가공되지 않은 상세한 데이터보다 요약된 데이터에 더 관심이 많다.
센서 노드는 쓸 수 있는 에너지가 제한적이므로 센서 네트워크의 수명을 늘이기 위해서는
집계 질의를 에너지 효율적으로 처리하는 것이 중요하다. 이 논문에서는 센서 네트워크에서
집계 질의를 에너지 효율적으로 처리하는 방법을 다룬다.
센서 노드에서 주로 에너지를 소모하는 무선 통신에 쓰이는 에너지를 줄이기 위해서
집계 질의를 네트워크 내부에서 처리하는 기법이 널리 쓰인다. 네트워크 내부 처리 기법의
핵심 아이디어는 데이터가 센서 노드를 통해 흘러갈 때 네트워크 내부에서 집계 값을 미리
계산하자는 것이다. 여기서 불필요한 데이터는 버려지고 관련 있는 센서 값들은
더 간결한 형태로 병합된다.
사용자가 질의를 요청하고 결과를 받아보는 베이스 스테이션으로 센서 값을 전달하는 방법은
에너지 효율적인 네트워크 내부 처리를 위해서 중요하다. 네트워크 내부 처리에 효율적인
라우팅 구조는 질의마다 다르다. 따라서, 집계 질의의
에너지 효율적인 네트워크 내부 처리를 위해서 질의에 특화된 라우팅 기법이 요구된다.
하지만 기존 기법들은 대부분 센서 값을 라우팅할 때 질의의 특성을 고려하지 않는다.
질의에 특화된 라우팅 기법을 제안한 연구가 있지만 몇 가지 제약을 가지고 있다.
즉, 기존 기법은 특정한 종류의 질의에만 사용할 수 있거나 특정한 센서 네트워크
환경에서만 사용할 수 있다.
본 논문에서는 센서 네트워크에서 집계 질의를 네트워크 내부에서 에너지 효율적으로
처리하기 위한 질의에 특화된 라우팅 기법을 제안한다. 집계 질의는 그룹 조건이 있는 경우와
없는 경우로 나뉜다. 그룹이 없는 집계 질의에 대해서는 아무 두 센서 값이나 하나로
합쳐질 수 있지만 그룹이 있는 집계 질의에 대해서는 같은 그룹에 있는 값만 합쳐질 수 있다.
이러한 차이점 때문에 에너지 효율적인 네트워크 내부 처리를 위해서는 이 둘을 다르게
처리해야 한다.
본 논문의 앞 부분에서는 그룹이 없는 집계 질의를 다룬다.
여기서는 EM-tree(Early Merging tree)라고 부르는 질의에
특화된 라우팅 트리를 제안한다. EM-tree는 질의별로 따로 구축되고
최소 집계 거리라고 부르는 간단하지만 새로운 거리 측정값에 기반하여
생성된다. EM-tree는 네트워트 내부 처리 기회가 높아질 수 있게
메시지 전송 방향을 정한다. 실험을 통해서 다양한 센서 네트워크 환경에서
EM-tree가 기존 라우팅 트리보다 더 좋은 성능을 낸다는 것을 보인다.
본 논문의 뒷 부분에서는 그룹 있는 집계 질의를 다룬다. 여기서는 그룹 있는 집계 질의를
네트워크 내부에서 에너지 효율적으로 처리하기 위한 CMR(Content-based Multipath Routing)이라고
부르는 다중경로 라우팅 기법을 제안한다. CMR에서 각 노드는 네트워크 내부 처리가 더 많은
데이터를 줄일 수 있도록 서로 다른 그룹에 속한 부분 집계 값을 서로 다른 노드로 전송한다.
실험을 통해 다양한 센서 네트워크 환경에서 CMR이 기존 라우팅 트리 기반 기법보다
더 좋은 성능을 낸다는 것을 보인다.