센서 네트워크에서 비트 벡터를 이용한 효율적인 레코드 필터링 인-네트워크 조인 전략 = Efficient Record Filtering In-network Join Strategy using Bit-Vector in Sensor Networks

국문 초록 (Abstract)

본 논문에서는 센서 네트워크에서 효율적인 조인 처리를 수행하여 통신비용을 최소화할 수있는인-네트워크 조인 전략인 RFB(Record Filtering using Bit-vector) 조인 전략을 제안하였다. 제안하는 조인 전략은 통신비용을 감소하기 위하여 데이터의 크기를 줄이기 위해 비트 벡터(Bit-vector)를 이용한다. 또한, 센서 네트워크의 특성상 조인을 위해 중앙의 서버로 모든 데이터를 전송하기가 어렵기 때문에 본 논문의 조인 전략은 조인 처리의 이른 단계에서 조인 결과에 해당되지 않는 데이터를 제거하여 불필요한 통신비용을 감소시켜 통신비용을 최소화하기 위한 네트워크 내에서 효율적인 조인 질의 수행 전략이다. 본 논문에서는 시뮬레이션을 통하여 기존의 대표적인 조인 전략인 시놉시스를 전송하여 조인을 수행하는 시놉시스 조인(Synopsis Join, SNJ)과 비교하여 통신비용 효율적임을 보였다.

다국어 초록 (Multilingual Abstract)

The paper proposes RFB(Record Filtering using Bit-vector) join algorithm, an in-network strategy that uses bit-vector to drastically reduce the size of data and hence the communication cost. In addition, by eliminating data not involved in join result prior to actual join, communication cost can be minimized since not all data need to be moved to the join nodes. The simulation result shows that the proposed RFB algorithm significantly reduces the number of bytes to be moved to join nodes compared to the popular synopsis join(SNJ) algorithm.

참고문헌 (Reference)

1 김회복, "무선 센서 네트워크에서 정보 보호를 위한 키 분배 기법" 한국컴퓨터정보학회 14 (14): 51-58, 2009

2 김용태, "무선 센서 네트워크 환경에 대한 센서 웹 서비스 프레임워크의 설계" 한국컴퓨터정보학회 14 (14): 123-131, 2009

3 P.A.Bernstein, "Using Semi-Joins to Solve Relational Queries" 28 (28): 25-40, 1981

4 P.Bonnet, "Towards Sensor Database Systems" 1987 : 3-14, 2001

5 Z.Zhang, "Three Approximation Algorithms for Energy-Efficient Query Dissemination in Sensor Database System" 5690 : 807-821, 2009

6 I. Greenberg, "The Three Factory Problem" 38 (38): 67-72, 1965

7 Z.Li,, "PERF Join:An Alternative to Two-way Semijoin and Bloomjoin" 137-144, 1995

8 A. Coman, "On Join Location in Sensor Networks" 190 (190): 2007

9 A.Broder,, "Network Applications of Bloom Filters:A Survey" 1 : 485-509, 2004

10 H. Yu, "In-Network Join Processing for Sensor Networks" 3841 : 263-274, 2006

11 B. Karp, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks" 243-254, 2000

12 A.Pandit, "Communication-Efficient Implementation of Range-Joins in Sensor Networks" 859-869, 2006

13 J. Z. Sun, "An Energy-Efficient Query Processing Algorithm for Wireless Sensor Networks" 5061 : 373-385, 2008

14 W.B.Heinzelman, "An Application-Specific Protocol Architecture for Wireless Microsensor Networks" 1 (1): 660-670, 2002

15 A. Coman, "A Distributed Algorithm for Joins in Sensor Networks" 27-, 2007