센서 네트워크에서 시놉시스와 인코딩을 이용한 에너지 효율적인 인-네트워크 조인 질의 처리 An Energy-Efficient In-Network Join Query Processing using Synopsis and Encoding in Sensor Network원문보기
최근 많은 연구자들은 서로 다른 영역에 저장된 센서 데이터를 이용한 조인 질의에 관심을 갖고 있다. 기존 기법은 예비 조인 조정자가 센서 노드로부터 시놉시스를 수집하고, 조인 질의 처리에 필요한 센서 데이터를 결정한다. 기지국은 전체 데이터를 수집하는 대신 일부 센서 데이터를 수집하여 최종 조인 처리를 수행한다. 하지만, 예비 조인을 수행하는 과정에서 통신 오버헤드를 발생시키는 단점을 가지고 있다. 본 논문에서는 이와 같은 문제점을 해결하는 새로운 에너지 효율적인 인-네트워크 조인 기법을 제안한다. 제안하는 기법은 네트워크 내부에서 예비 조인 조정자를 선정한다. 예비 조인 조정자는 조인의 초기 단계에서 조인 결과에 포함되지 않는 데이터를 제거하고 센서 데이터의 압축을 수행한다. 기지국은 압축된 데이터의 일부와 데이터 압축을 위한 인코딩 테이블을 수집하고 조인 결과를 결정한다. 그 결과, 제안하는 기법은 예비 조인 처리를 위한 통신 비용을 줄이고 네트워크 수명을 연장시킨다.
최근 많은 연구자들은 서로 다른 영역에 저장된 센서 데이터를 이용한 조인 질의에 관심을 갖고 있다. 기존 기법은 예비 조인 조정자가 센서 노드로부터 시놉시스를 수집하고, 조인 질의 처리에 필요한 센서 데이터를 결정한다. 기지국은 전체 데이터를 수집하는 대신 일부 센서 데이터를 수집하여 최종 조인 처리를 수행한다. 하지만, 예비 조인을 수행하는 과정에서 통신 오버헤드를 발생시키는 단점을 가지고 있다. 본 논문에서는 이와 같은 문제점을 해결하는 새로운 에너지 효율적인 인-네트워크 조인 기법을 제안한다. 제안하는 기법은 네트워크 내부에서 예비 조인 조정자를 선정한다. 예비 조인 조정자는 조인의 초기 단계에서 조인 결과에 포함되지 않는 데이터를 제거하고 센서 데이터의 압축을 수행한다. 기지국은 압축된 데이터의 일부와 데이터 압축을 위한 인코딩 테이블을 수집하고 조인 결과를 결정한다. 그 결과, 제안하는 기법은 예비 조인 처리를 위한 통신 비용을 줄이고 네트워크 수명을 연장시킨다.
Recently, many researchers are interested in using join queries to correlate sensor readings stored in different regions. In the conventional algorithm, the preliminary join coordinator collects the synopsis from sensor nodes and determines a set of sensor readings that are required for processing t...
Recently, many researchers are interested in using join queries to correlate sensor readings stored in different regions. In the conventional algorithm, the preliminary join coordinator collects the synopsis from sensor nodes and determines a set of sensor readings that are required for processing the join query. Then, the base station collects only a part of sensor readings instead of whole readings and performs the final join process. However, it has a problem that incurs communication overhead for processing the preliminary join. In this paper, we propose a novel energy-efficient in-network join scheme that solves such a problem. The proposed scheme determines a preliminary join coordinator located to minimize the communication cost for the preliminary join. The coordinator prunes data that do not contribute to the join result and performs the compression of sensor readings in the early stage of the join processing. Therefore, the base station just collects a part of compressed sensor readings with the decompression table and determines the join result from them. In the result, the proposed scheme reduces communication costs for the preliminary join processing and prolongs the network lifetime.
Recently, many researchers are interested in using join queries to correlate sensor readings stored in different regions. In the conventional algorithm, the preliminary join coordinator collects the synopsis from sensor nodes and determines a set of sensor readings that are required for processing the join query. Then, the base station collects only a part of sensor readings instead of whole readings and performs the final join process. However, it has a problem that incurs communication overhead for processing the preliminary join. In this paper, we propose a novel energy-efficient in-network join scheme that solves such a problem. The proposed scheme determines a preliminary join coordinator located to minimize the communication cost for the preliminary join. The coordinator prunes data that do not contribute to the join result and performs the compression of sensor readings in the early stage of the join processing. Therefore, the base station just collects a part of compressed sensor readings with the decompression table and determines the join result from them. In the result, the proposed scheme reduces communication costs for the preliminary join processing and prolongs the network lifetime.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 각 영역의 전체 시놉시스의 크기를 고려하여 예비 조인 조정자를 선정하는 방법과 최종 데이터를 싱크 노드로 전송하는 비용을 줄이기 위한 기법을 제안한다. 기존 기법의 경우, 예비 조인 조정자를 선정하기 위해서 영역간 거리와 시놉시스 크기, 네트워크 밀도, 메모리 저장 공간 등을 동시에 고려하여 예비 조인 조정자가 존재할 수 있는 영역을 설정한다.
본 논문에서는 기존에 제안된 시놉시스 조인의 문제점을 제시하고 에너지 효율적인 예비 조인 조정자 선정 기법과 최종 조인을 수행하기 위해 데이터를 기지국으로 전송하는 비용을 줄이기 위한 기법을 제안하였다. 시놉시스가 다중 홉으로 전달된다는 점에 착안하여 시놉시스의 크기에 따라 지연시간을 설정하고, 매 전송 홉마다 지연시간을 가지고 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 하였다.
본 장에서는 시놉시스 전송 과정에서 시놉시스의 크기를 고려하여 예비 조인 조정자를 선정하는 방법과 최종 데이터를 싱크 노드로 전송하는 비용을 줄이기 위한 기법을 제안한다. 싱크 노드로 요청된 조인 질의는 다음과 같은 순서에 의해 처리되며, 각 단계별 상세한 처리 과정은 다음절에 기술한다.
제안 방법
조인 질의를 요청 받은 각 영역의 센서 노드들은 센서 데이터의 시놉시스를 생성하고, 시놉시스를 중간 지점의 예비 조인을 수행하는 센서 노드로 전달한다. 그 다음, 예비 조인을 통해 조인에 실제 참여하는 데이터를 결정하고, 각 영역의 센서 노드들은 해당 데이터만을 싱크 노드로 전달하고, 싱크 노드가 최종 조인을 수행한다. 즉, 예비 조인을 네트워크 내부에서 수행하고, 싱크 노드로 전달되는 최종 데이터의 수를 줄임으로써 통신 비용을 감소시킨다.
001으로 다양하게 변화시키면서 실험 하였다. 그리고 RL과 RE의 동일한 조인 선택도와 비동일한 조인 선택도 환경에서 실험하였다.
이 영역 상에 400개의 센서 노드들이 균등하게 분포되어 있고 40m의 통신 반경을 가지고 있다. 그리고 시놉시스 조인을 기초로 하여 성능을 평가하였다. 이 성능평가에서는 조인 선택도를 0.
같은 방법으로 RE의 root(RE)도 시놉시스를 전송한다. 그리고 시놉시스를 받은 예비 조인 조정자는 질의에 참여하지 않는 각 영역의 튜플들에 대한 정보를 획득하기 위해서 예비 조인연산을 수행한다.
시놉시스가 다중 홉으로 전달된다는 점에 착안하여 시놉시스의 크기에 따라 지연시간을 설정하고, 매 전송 홉마다 지연시간을 가지고 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 하였다. 또한, 예비 조인 후 조인에 참여하는 속성들을 포함하는 참조 테이블을 싱크 노드로 전송함으로써 각 영역의 최종 데이터 전달시 데이터 압축을 수행하였다. 성능 평가 결과, 동일한 조인 선택도 환경에서는 시놉시스 조인과 유사한 결과를 보이면서도, 점점 조인 선택도가 늘어나면서 전송 데이터 전송량이 줄어드는 것을 확인 할 수 있었다.
기존의 시놉시스 조인은 예비 조인 조정자에서 예비 조인 후, 다시 질의를 받은 센서영역으로 예비 조인 결과를 전송한다. 반면에 제안하는 기법은 예비 조인 결과를 비트코드로 전달하고, 별도의 참조테이블을 통해서 싱크 노드에서 최종 조인을 한다. 따라서, 조인 선택도가 커짐에 따라 성능이 향상된다.
본 절에서는 RL과 RE의 비동일한 조인 선택도 환경에서 실험 하였다. [그림 14]는 RL을 0.
본 논문에서는 기존에 제안된 시놉시스 조인의 문제점을 제시하고 에너지 효율적인 예비 조인 조정자 선정 기법과 최종 조인을 수행하기 위해 데이터를 기지국으로 전송하는 비용을 줄이기 위한 기법을 제안하였다. 시놉시스가 다중 홉으로 전달된다는 점에 착안하여 시놉시스의 크기에 따라 지연시간을 설정하고, 매 전송 홉마다 지연시간을 가지고 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 하였다. 또한, 예비 조인 후 조인에 참여하는 속성들을 포함하는 참조 테이블을 싱크 노드로 전송함으로써 각 영역의 최종 데이터 전달시 데이터 압축을 수행하였다.
하지만, 영역에 포함된 센서노드로부터 해당 정보를 획득하기 위해서는 추가적인 통신이 필요하다는 문제점을 가지고 있다. 제안하는 기법은 시놉시스가 다중 홉으로 전달된다는 점에 착안하여 시놉시스의 크기에 따라 지연 시간을 설정하고, 매 전송 홉마다 지연시간을 가지고 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 한다. 또한, 예비 조인 후조인에 참여하는 속성들을 포함하는 참조 테이블을 싱크 노드로 전송함으로써 각 영역의 최종 데이터 전달시 데이터 압축을 수행한다.
기존 기법은 RL과 RE 두 영역의 시놉시스 크기, 네트워크 밀도, 메모리 저장 공간를 동시에 고려하여 예비 조인 조정자를 선정하는 방법을 제안하지만 실제 응용에서는 추가적인 통신없이 RL과 RE 영역에 대한 정보를 획득하기 어렵고, 센서 노드의 분포가 균일하지 않기 때문에 기존 예비 조인 조정자 위치 선정 기법은 실제 응용에 적합하지 않다. 제안하는 기법은 시놉시스는 예비 조인 조정자까지 다중 홉으로 전달된다는 점에서 착안하여 식(1)과 같이 시놉시스의 크기에 따른 지연시간(Td)을 결정하고, 매 전송 홉마다 지연 시간동안 머무른 후 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 한다. 즉, 시놉시스 크기가 크다면 전송지연시간은 길어져 전송홉수가 작아지고, 시놉시스 크기가 작다면 전송지연시간은 짧아 전송홉수가 많아진다.
최소의 통신 비용으로 질의를 수행하기 위해 RL과 RE의 각 센서들에서 생성한 시놉시스를 최종조인의 관련 있는 데이터로 수집하기 위해 예비 조인한다. 예비 조인을 하기 위하여 적절한 위치에 있는 예비 조인 조정자에서 시놉시스를 수집해야 한다.
성능/효과
제안하는 기법에서는 데이터 크기를 고려하여 예비 조인 조정자를 선정하기 때문에 균등한 에너지 소비가 이루어진다. 그래서 제안하는 기법이 보다 우수한 성능을 보이고, 기존의 기법보다 데이터 전송량이 평균 30% 감소하였다. [그림 15]는 RL과 RE의 조인 선택도가 비동일한 환경에서 제안하는 기법의 네트워크 메시지 비용 분석한 결과를 나타낸다.
예를 들어, [그림 8] 과 같이 예비 조인 조정자는 각 영역 RL={(POL001,3),(TAXI001,2),(BUS001,1), (BUS002,1)}과 RE={(POL002, 1), (POL003, 1), (TAXI001, 2), (TAXI002, 1), (BUS001, 1), (BUS002, 1)}의 시놉시스들을 받는다. 그리고 예비 조인 연산을 통해, RL과 RE의 {TAXI001, BUS001, BUS002}가 조인 결과에 포함되고, {POL001, POL002, POL003, TAXI002}는 조인 결과에 포함되지 않는다는 것을 알수 있다. 즉, 예비 조인 조정자는 RL의 시놉시스에 대해 ‘0x0111’의 비트열을 만들고, RE의 시놉시스에 대해 ‘0x001011’의 비트열을 만든다.
성능 평가 결과, 동일한 조인 선택도 환경에서는 시놉시스 조인과 유사한 결과를 보이면서도, 점점 조인 선택도가 늘어나면서 전송 데이터 전송량이 줄어드는 것을 확인 할 수 있었다. 또한 비동일한 조인 선택도 환경에서는 시놉시스 조인 보다 우수한 성능을 보이며, 데이터 전송량이 약 30% 감소하였다.
또한, 예비 조인 후 조인에 참여하는 속성들을 포함하는 참조 테이블을 싱크 노드로 전송함으로써 각 영역의 최종 데이터 전달시 데이터 압축을 수행하였다. 성능 평가 결과, 동일한 조인 선택도 환경에서는 시놉시스 조인과 유사한 결과를 보이면서도, 점점 조인 선택도가 늘어나면서 전송 데이터 전송량이 줄어드는 것을 확인 할 수 있었다. 또한 비동일한 조인 선택도 환경에서는 시놉시스 조인 보다 우수한 성능을 보이며, 데이터 전송량이 약 30% 감소하였다.
X축은 조인 선택도를 나타내고 Y축은 송/수신된 메시지의 수를 나타낸다. 실험 결과로 기존의 시놉시스 조인보다 우수한 성능을 보였다. 기존의 시놉시스 조인은 예비 조인 조정자에서 예비 조인 후, 다시 질의를 받은 센서영역으로 예비 조인 결과를 전송한다.
제안하는 기법은 시놉시스는 예비 조인 조정자까지 다중 홉으로 전달된다는 점에서 착안하여 식(1)과 같이 시놉시스의 크기에 따른 지연시간(Td)을 결정하고, 매 전송 홉마다 지연 시간동안 머무른 후 시놉시스를 다음 노드로 전달함으로써 시놉시스 라우팅의 에너지 소모를 균등하게 한다. 즉, 시놉시스 크기가 크다면 전송지연시간은 길어져 전송홉수가 작아지고, 시놉시스 크기가 작다면 전송지연시간은 짧아 전송홉수가 많아진다.
질의응답
핵심어
질문
논문에서 추출한 답변
TinyDB는?
대표적인 센서 데이터베이스 연구로는 TinyDB[4][5]가 있다. TinyDB는 SQL 형태의 질의 언어를 제공하며, 인네트워크(In-network) 처리 기법을 통해 SUM, AVG, COUNT와 같은 병합 질의를 효율적으로 처리하기 위한 방법을 제공한다.
시놉시스 조인의 방식은?
보다 효율적으로 조인 질의를 처리하기 위한 방법으로 시놉시스 조인(Synopsis join)[6]이 있다. 조인 질의를 요청 받은 각 영역의 센서 노드들은 센서 데이터의 시놉시스를 생성하고, 시놉시스를 중간 지점의 예비 조인을 수행하는 센서 노드로 전달한다. 그 다음, 예비 조인을 통해 조인에 실제 참여하는 데이터를 결정하고, 각 영역의 센서 노드들은 해당 데이터만을 싱크 노드로 전달하고, 싱크 노드가 최종 조인을 수행한다. 즉, 예비 조인을 네트워크 내부에서 수행하고, 싱크 노드로 전달되는 최종 데이터의 수를 줄임으로써 통신 비용을 감소시킨다.
무선 센서 네트워크는 어느 분야에서 사용 중인가?
최근 반도체 기술과 무선 통신 기술 그리고 센서 기술이 발전함에 따라 무선 센서 네트워크에 대한 관심도 크게 증가하고 있다. 무선 센서 네트워크는 환경 감시, 군사적, 의학적, 재난 방재 등 많은 분야에서 널리 사용되고 있다[1]. 센서 네트워크는 수 백～수 천개의 센서 노드로 구성되며, 센서 노드는 센싱을 위한 센서 모듈, 데이터 처리를 위한 CPU, 데이터 저장을 위한 메모리, 무선 통신을 위한 통신 회로로 구성된다[2].
참고문헌 (9)
C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks", In proceedings of the 6th annual international conference on Mobile computing and networking, pp.56-67, 2000(8).
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey", Computer Networks, Vol. 38, No. 4, pp.393-422, 2002(3).
S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, "TAG: A tiny aggregation service for ad-hoc sensor networks", In proceedings of the 5th symposium on Operating systems design and implementation, pp.131-145, 2002(12).
S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, "TinyDB: an acquisitional query processing system for sensor networks”, ACM Transactions on Database Systems, Vol.30, No.1, pp.122-173, 2005(3).
H. Yu, E. P. Lim, and J. Zhang, “On in-network synopsis join processing for sensor networks", In proceedings of the 7th International Conference on Mobile Data Management, pp.32-40, 2006(5).
S. Nath, P. B. Gibbons, S. Seshan, and Z. R. Anderson, "Synopsis diffusion for robust aggregation in sensor networks", ACM Transactions on Sensor Networks, Vol.4, No.2, pp.1-40, 2008(3).
D. J. Abadi, S. R. Madden, and W. Lindner, "REED: Robust, Efficient Filtering and Event Detection in Sensor Networks," In proceedings of the 31st international conference on Very large data bases, pp.769-780, 2005(8).
B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," In Proceedings of the 6th annual international conference on Mobile computing and networking, pp.243-254, 2000(8).
※ AI-Helper는 부적절한 답변을 할 수 있습니다.