Spatial Information Research

Korea Spatial Information Society (대한공간정보학회)
권호 표지

Efficient Processing of Aggregate Queries in Wireless Sensor Networks

무선 센서 네트워크에서 효율적인 집계 질의 처리

  • 김정준 (건국대학교 컴퓨터공학과) ;
  • 신인수 (건국대학교 컴퓨터공학과) ;
  • 이기영 (을지대학교 의료IT마케팅학과) ;
  • 한기준 (건국대학교 컴퓨터공학과)
  • Received : 2011.05.09
  • Accepted : 2011.06.27
  • Published : 2011.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

Recently as efficient processing of aggregate queries for fetching desired data from sensors has been recognized as a crucial part, in-network aggregate query processing techniques are studied intensively in wireless sensor networks. Existing representative in-network aggregate query processing techniques propose routing algorithms and data structures for processing aggregate queries. However, these aggregate query processing techniques have problems such as high energy consumption in sensor nodes, low accuracy of query processing results, and long query processing time. In order to solve these problems and to enhance the efficiency of aggregate query processing in wireless sensor networks, this paper proposes Bucket-based Parallel Aggregation(BPA). BPA divides a query region into several cells according to the distribution of sensor nodes and builds a Quad-tree, and then processes aggregate queries in parallel for each cell region according to routing. And it sends data in duplicate by removing redundant data, which, in turn, enhances the accuracy of query processing results. Also, BPA uses a bucket-based data structure in aggregate query processing, and divides and conquers the bucket data structure adaptively according to the number of data in the bucket. In addition, BPA compresses data in order to reduce the size of data in the bucket and performs data transmission filtering when each sensor node sends data. Finally, in this paper, we prove its superiority through various experiments using sensor data.

최근 무선 센서 네트워크에서 센서로부터 원하는 데이타를 가져오는 네트워크 내 집계 질의처리 기법에 대한 연구가 활발히 진행되고 있다. 기존의 대표적인 네트워크 내 집계 질의 처리 기법들은 집계 질의 처리를 위해 라우팅 알고리즘과 데이타 구조를 제안하고 있다. 그러나 이러한 기법들은 센서 노드들의 에너지 소모가 크고, 질의 처리 결과 정확도가 떨어지고, 또한 질의 처리 시간이 오래 걸리는 문제점들을 가지고 있다. 본 논문에서는 이러한 기존 집계 질의 처리 기법들의 문제점을 해결하고 무선 센서 네트워크에서 보다 효율적인 집계 질의 처리를 위해 BPA(Bucket-based Parallel Aggregation)를 제시하였다. BPA는 질의 영역을 센서 노드 분포에 따라 쿼드 트리로 구성하여 집계 질의를 병렬로 처리하고, 각 센서 노드로 하여금 데이타를 이중 전송하게 함으로써 전송 오류로 인한 데이타 손실을 줄인다. 또한, BPA는 집계 질의 처리시 버켓 기반의 데이타 구조를 이용하고 이러한 버켓 데이타 구조를 버켓내 데이타 개수에 따라 적응적으로 분할 및 합병한다. 특히 버켓내 데이타 크기를 줄이기 위해 데이타를 압축하고 데이타 전송 횟수를 줄이기 위해 필터링을 수행한다. 마지막으로 센서 데이타를 이용한 다양한 실험을 통해 본 논문에서 제안하는 BPA의 우수성을 입증하였다.

Keywords

Acknowledgement

Grant : 지능형국토정보기술혁신 사업과제

References

  1. J. Li, F. Considine, G. Kollios and J. Byers, 2004, "Approximate Aggregation Techniques for Sensor Databases," Proc. of the ICDE, pp.449-460.
  2. D. Culler and D. Estrin, 2004, "Overview of Sensor Networks," Journal of the IEEE Computer Magazine, Vol.37 No.8, pp.41-49.
  3. E. Fasolo, M. Rossi, J. Widmer and M. Zorzi, 2007, "In-network Aggregation Techniques for Wireless Sensor Networks: a Survey," Journal of the IEEE Wireless Communications, Vol.14 No.2, pp.77-87.
  4. J. J. Kim, H. K. Kang, D. S. Hong and K. J. Han, 2007, "An Efficient Compression Technique for a Multi-dimensional Index in Main Memory," Proc. of the Int. Conf. on Visual Information Systems, pp.336-346.
  5. S. Madden, M. Franklin, J. Hellerstein and W. Hong, 2002, "TAG: A Tiny Aggregation Service for Ad-hoc Sensor Networks," Proc. of the Symposium on Operating System Design and Implementation, pp.131-146.
  6. S. Motegi, K. Yoshihara and H. Horiuchi, 2006, "DAG Based In-Network Aggregation for Sensor Network Monitoring," Proc. of the IEEE SAINT, pp.292-299.
  7. D. Pendarakis, N. Shrivastava, L. Zhen and R. Ambrosio, 2007, "Information Aggregation and Optimized Actuation in Sensor Networks," Proc. of the IEEE Int. Conf. on Computer Communications, pp.2386-2390.
  8. S. Roy, M. Conti, S. Setia and S. Jajodia, 2009, "Secure Median Computation in Wireless Sensor Networks," Journal of the Ad Hoc Networks, Vol.7 No.8, pp.1448-1462. https://doi.org/10.1016/j.adhoc.2009.04.007
  9. Y. Xu, W. Lee, J. Xu and G. Mitchell, 2006, "Processing Window Queries in Wireless Sensor Networks," Proc. of the IEEE Int. Conf. on Data Engineering, pp.270-280.
  10. 강홍구, 김정준, 한기준, 2007, "데이타 중심 센서 네트워크에서 에너지 효율성을 고려한 비균등 네트워크 분할 기법," 한국공간정보시스템학회 논문지, 제9권 제3호, pp.35-50.
  11. 김정준, 심희정, 강홍구, 이기영, 한기준, 2009, "플래시 메모리 기반 효율적인 공간 인덱스," 한국공간정보시스템학회 논문지, 제11권 제2호, pp.133-142.