연속 질의는 센서 네트워크에서 일반적으로 사용되는 질의로서, 한 번 요청되면 일정한 주기로 여러 번 실행되어 그 질의의 결과를 베이스 스테이션으로 모은다. 이것은 지속적으로 많은 메시지 전송을 유발시키므로 베이스 스테이션으로 데이타를 모으는 데 드는 통신 비용을 줄이는 것이 중요하다. 센서 네트워크에서 네트워크내 프로세싱 기법은 중간 노드에서 집계 질의의 결과 데이타들에 대해 부분 집계를 수행하거나 그 데이타들을 하나의 메시지에 담아 보냄으로써 메시지 전송 횟수를 줄이며, 이것은 결국 통신 비용을 줄인다. 본 논문에서는 질의별로 구성되는 라우팅 트리인 질의 기반 라우팅 트리(Query Specific Routing Tree: QSRT)를 제안한다. QSRT의 핵심 아이디어는 네트워크내 프로세싱의 기회를 최대화하는 것이다. QSRT는 질의가 전달되는 과정을 통해 생성되며, 질의의 결과들이 베이스 스테이션으로 전달되는 도중 가능한 한 빨리 서로 만나게 만들어 부분 집계 및 패킷 합병의 기회를 최대화시킨다. 수행된 실험의 결과는 제안된 QSRT가 기존의 라우팅 트리보다 메시지 전송 횟수를 18% 이상 줄일 수 있음을 보여 준다.
연속 질의는 센서 네트워크에서 일반적으로 사용되는 질의로서, 한 번 요청되면 일정한 주기로 여러 번 실행되어 그 질의의 결과를 베이스 스테이션으로 모은다. 이것은 지속적으로 많은 메시지 전송을 유발시키므로 베이스 스테이션으로 데이타를 모으는 데 드는 통신 비용을 줄이는 것이 중요하다. 센서 네트워크에서 네트워크내 프로세싱 기법은 중간 노드에서 집계 질의의 결과 데이타들에 대해 부분 집계를 수행하거나 그 데이타들을 하나의 메시지에 담아 보냄으로써 메시지 전송 횟수를 줄이며, 이것은 결국 통신 비용을 줄인다. 본 논문에서는 질의별로 구성되는 라우팅 트리인 질의 기반 라우팅 트리(Query Specific Routing Tree: QSRT)를 제안한다. QSRT의 핵심 아이디어는 네트워크내 프로세싱의 기회를 최대화하는 것이다. QSRT는 질의가 전달되는 과정을 통해 생성되며, 질의의 결과들이 베이스 스테이션으로 전달되는 도중 가능한 한 빨리 서로 만나게 만들어 부분 집계 및 패킷 합병의 기회를 최대화시킨다. 수행된 실험의 결과는 제안된 QSRT가 기존의 라우팅 트리보다 메시지 전송 횟수를 18% 이상 줄일 수 있음을 보여 준다.
Once a continuous query, which is commonly used in sensor networks, is issued, the query is executed many times with a certain interval and the results of those query executions are collected to the base station. Since this comes many communication messages continuously, it is important to reduce co...
Once a continuous query, which is commonly used in sensor networks, is issued, the query is executed many times with a certain interval and the results of those query executions are collected to the base station. Since this comes many communication messages continuously, it is important to reduce communication cost for collecting data to the base station. In sensor networks, in-network processing reduces the number of message transmissions by partially aggregating results of an aggregate query in intermediate nodes, or merging the results in one message, resulting in reduction of communication cost. In this paper, we propose a routing tree for sensor nodes that qualify the given query predicate, called the query specific routing tree(QSRT). The idea of the QSRT is to maximize in-network processing opportunity. A QSRT is created seperately for each query during dissemination of the query. It is constructed in such a way that during the collection of query results partial aggregation and packet merging of intermediate results can be fully utilized. Our experimental results show that our proposed method can reduce message transmissions more than 18% compared to the existing one.
Once a continuous query, which is commonly used in sensor networks, is issued, the query is executed many times with a certain interval and the results of those query executions are collected to the base station. Since this comes many communication messages continuously, it is important to reduce communication cost for collecting data to the base station. In sensor networks, in-network processing reduces the number of message transmissions by partially aggregating results of an aggregate query in intermediate nodes, or merging the results in one message, resulting in reduction of communication cost. In this paper, we propose a routing tree for sensor nodes that qualify the given query predicate, called the query specific routing tree(QSRT). The idea of the QSRT is to maximize in-network processing opportunity. A QSRT is created seperately for each query during dissemination of the query. It is constructed in such a way that during the collection of query results partial aggregation and packet merging of intermediate results can be fully utilized. Our experimental results show that our proposed method can reduce message transmissions more than 18% compared to the existing one.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
. 네트워크 크기 실험: 센서 네트워크의 크기 변화에 따른 두 라우팅 트리의 성능 변화를 알아 본다. 좁은 지역에 센서 노드들이 배치된 경우(빌딩 내어〕서부터, 넓은 지역에 센서 노드들이 배치된 경우(동물들의 서식지)까지, 센서 네트워크의 크기를 변화시키며 두 라우팅 트리의 성능 변화를 알아 본다.
. 질의 선택도 실험: 질의 선택도의 변화에 따른 두 라우팅 트리의 성능 변화를 알아 보는 실험이다, 본 실험에서는 두 라우팅 트리의 성능에 질의 선택도가 미치는 영향을 알아 본다.
성능을 비교하였다. 네트워크 크기 실험은 센서 노드들이 배치된 지역의 크기가 변함에 따라 두 라우팅 트리의 성능이 어떻게 변하는지를 알아 본다. 그림 10은 네트워크 크기 실험의 결과를 보여준다.
QSRT는 질의의 결과 데이타들이베이스 스테이션으로 전송되는 도중 가능한 한 서로 빨리 만나게 만들어, 부분 집계 및 패킷 합병의 수행 시점을 앞당기고 그 기회를 최대화시킴으로써 메시지 전송 비용을 줄인다. 본 논문에서는 시뮬레이션 실험을 통해 QSRT의 우수성을 보였다. 질의 선택도 실험 결과는 센서 노드들 중 일부 노드들의 정보를 알아 보고자 하는 일반적인 형태의 질의 처리에 QSRT가 기존의 라우팅 트리보다 특히 효과적으로 사용될 수 있음을 보여 준다.
본 논문에서는 질의별로 구성되는 라우팅 트리인 QSRT를 제안하였다. QSRT는 질의의 결과 데이타들이베이스 스테이션으로 전송되는 도중 가능한 한 서로 빨리 만나게 만들어, 부분 집계 및 패킷 합병의 수행 시점을 앞당기고 그 기회를 최대화시킴으로써 메시지 전송 비용을 줄인다.
본 논문에서는 질의별로 구성되는 라우팅 트리인 질의 기반 라우팅 트리 (Query Specific Routing Tree: QSRT)를 제안한다. QSRT는 결과 데이타들이 베이스 스테이션으로 전송되는 도중 가능한 한 서로 빨리 만나게 만들어 부분 집계 및 패킷 합병의 수행 시점을 앞당기고 그 기회를 최대화시킴으로써 전송되는 메시지 횟수를 더욱 줄인다.
본 논문에서는 집계 질의의 결과 데이타들을 에너지 효율적으로 베이스 스테이션으로 모올 수 있는 라우팅 트리 구성 방안에 대해 논의한다. 추가적으로 본 논문에서는 집계 질의들 중에서도 고정 값을 가지는 애 트리 뷰트가 조건절에 하나 이상 포함되는 질의 처리를 논의한다.
본 절에서는 질의 메시지가 전달되는 과정을 통해 QSRT를 구성하는 절차를 설명한다. 각 질의에 대한 QSRT는 다음 두 단계를 통해 구성된다.
질의 Qie 6 층에 있는 센서 노드들을 방별로 그룹 짓고 방별 평균 음량 값이 threshold를 넘는 방을 보고한다. 여기서 정적 애트리뷰트인 floor 애트리뷰트에 대한 조건을 만족하는 6 층에 위치한 센서 노드들이 질의 Qi 후보 노드가 된다.
가설 설정
질의 선택도 파라미터는 전체 노드들 중에서 질의의 결과 데이타를 생성하는 노드들이 몇 퍼센트가 있는지를 지정한다. 본 실험에서는 질의 Q 후보 노드들이 모두 결과 데이타를 생성한다고 가정한다. 센서 네트워크 크기 파라미터는 센서 네트워크의 가로 .
통신반경 파라미터는 센서 노드들의 통신 반경을 지정한다. 센서 노드들은 통신 반경 내의 이웃 노드들과 서로 통신 할 수 있으며 통신은 무손실(ios이ess) 통신을 가정한다. 밀도 파라미터는 센서 노드의 통신 반경 내에 몇 개의 센서 노드가 존재하는지 지정한다.
온도 애트리뷰트와 같이 그 값이 시간에 따라 변하는애트리뷰트를 동적 애트리뷰트(dynamic (기:tribute)라고 하고 위치 애트리뷰트와 같이 고정된 값을 가지는 애 트리 뷰트를 정적 애트리뷰트constant attrubute)라고 한다 어떤 질의 q의 WHERE 절은 정적 애트리뷰트를하나 이상 포함한다고 가정한다. 召의 Q 후보 노드는 질의 Q WHERE 절의 정적 애트리뷰트에 대한 조건을 만족하는 노드다.
데이타 수집 단계에서는 네트워크내 프로세싱이 수행된다. 이때 각 센서 노드는 결과 데이타들에 대해 부분 집계 또는 패킷 합병하고 그 결과를 하나의 메시지로 전송한다고 가정한다.
제안 방법
. 다양한 실험을 통해 기존의 라우팅 트리와 QSRT의성능을 비교하였다. 실험의 결과는 QSRT를 사용할 경우 기존 라우팅 트리보다 메시지 전송 횟수를 18% 가까이 줄일 수 있음을 보여 주며, 센서 노드들이 조말하게 배치된 센서 네트워크 환경에서는 메시지 전송 횟수를 28% 이상 줄일 수 있음을 보여준다.
・ 질의별로 구성되는 라우팅 트리인 QSRT를 제안한다. QSRT는 결과 데이타들이 베이스 스테이션으로 전송되는 도중 가능한 한 서로 빨리 만나게 만들어 부분집계 및 패킷 합병의 수행 시점을 앞당기고 그 기회를 최대화시킨다.
생성 노드까지의 거리 정보이다. 각 노드는 이 거리 정보를 바탕으로 자신의 결과 데이타를 가장 빨리 다른 결과 데이타 생성 노드까지 전송해 줄 수 있는 부모 노드를 선택하여 QSRT를 구성한다.
각 센서 노드는 질의 분배 단계에서 질의 메시지를 이웃 노드에게 전달할 때 자신을 통해 결과 데이타를 루트 노드 쪽으로 전달할 경우(즉 자신을 부모 노드로 선택할 경우) 그 결과 데이타가 몇 홉 이후에 다른 결과 데이타 생성 노드와 만나는지에 대한 정보를 질의 메시지에 기록하여 전달한다. 각 센서 노드는 질의 메시지에 기록된 정보를 바탕으로 이웃 노드들 중에서 자신의 결과 데이타를 가장 빨리 다른 결과 데이타와 만나도록 전송해 주는 센서 노드를 자신의 부모 노드로 선택하여 QSRT를구성한다.
사용하였다. 각 실험에서는 주어진 센서 네트워크 환경에서 각 라우팅 트리를 사용할 때 데이타 수집단계에서 질의의 결과 데이타들을 한 번 모으는 데 필요한 메시지 전송 횟수를 세었다. 데이타 수집 단계에서는 네트워크내 프로세싱이 수행된다.
루트 노드를 제외한 각 센서 노드는 레벨이 정해지지 않은 상태에서 이웃 노드로부터 라우팅 트리 구성 메시지를 받으면, 라우팅 트리 구성 메시지의 level 필드의 값에 1을 더한 값을 자신의 레벨로 설정하고 라우팅 트리 구성 메시지를 보낸 센서 노드를 자신의 부모 노드로 선택한다. 그리고 라우팅 트리 구성 메시지의 s厂와 level 필드를 각각 자신의 아이디와 레벨로 설정한 후 이 메시지를 이웃 노드들에게 방송한다. 이러한 과정은 모든 센서 노드들의 레벨과 부모 노드가 정해질 때까지 계속된다.
그림 4는 그림 3에 이어 각 센서 노드가 부모 노드를 선택하여 구성된 질의 Q에 대한 QSRT Tq 를 보여준다. 그림에서 5 번 센서 노드는 2 번과 3 번 후보 부모 노드 중에서 MD 값이 작은 2 번 노드를 부모 노드로 선택하였고, 7 번 센서 노드는 5 번과 6 번 센서 노드 중에서 MD 값이 작은 6 번 센서 노드를 부모 노드로 선택하였다. □
네트워크 크기 실험에서는 센서 네트워크의 크기를 120x120부터 1080x1080까지 변화시켜가며 두 라우팅 트리의 성능을 비교하였다. 네트워크 크기 실험은 센서 노드들이 배치된 지역의 크기가 변함에 따라 두 라우팅 트리의 성능이 어떻게 변하는지를 알아 본다.
그림 10의 그래프에서 가로 축의 수치는 센서 네트워크의 가로 길이를 나타내며, 센서 네트워크의 세로 길이는 가로 길이와 동일하다. 네트워크 크기 실험은 다른 두 실험 파라미터 (질의 선택도, 밀도)를 고정한 상태에서 실행하였다. 따라서 센서 네트워크의 크기가 커질수록 센서 노드의 개수가 많아지고 라우팅 트리의 레벨이 커진다, '
두 라우팅 트리의 성능 비교 실험을 동일한 센서 네트워크 상에서 수행하기 위해 센서 네트워크 구성 정보를 일단 파일에 기록한 후 실험 시에 파일로부터 동일한 센서 네트워크 구성 정보를 읽어 들여 실험을 수행하였다. 서로 다른 10 개의 센서 네트워크를 생성하고 각 실험을 이 10 개의 센서 네트워크에 대해 반복적으로 수행하였으며 실험의 결과 값으로 10 번의 반복 실험 수행에서 나온 결과 값들의 평균 값을 사용하였다.
루트 노드는 라우팅 트리 구성 메시지의 와 level 필드를 각각 자신의 야이디와 레벨 (루트 노드의 레벨은 0)로 설정하고, destjd 필드를 방송 주소、broadccsst address')로 설정한 후 이 메시지를 이웃 노드들에게 방송한다. 루트 노드를 제외한 각 센서 노드는 레벨이 정해지지 않은 상태에서 이웃 노드로부터 라우팅 트리 구성 메시지를 받으면, 라우팅 트리 구성 메시지의 level 필드의 값에 1을 더한 값을 자신의 레벨로 설정하고 라우팅 트리 구성 메시지를 보낸 센서 노드를 자신의 부모 노드로 선택한다. 그리고 라우팅 트리 구성 메시지의 s厂와 level 필드를 각각 자신의 아이디와 레벨로 설정한 후 이 메시지를 이웃 노드들에게 방송한다.
밀도 실험에서는 밀도 값을 6에서부터 20까지 증가시켜가며 두 라우팅 트리의 성능을 비교하였다. 그림 11은 밀도 실험의 결과를 보여준다.
본 논문에서는 시뮬레이션 실험을 수행하여 데이타수집 단계에서 QSRT와 FRT를 사용하였을 때의 성능 차이를 비교하였다. 성능 비교에 사용된 수치는 데이타수집 단계에서 질의의 결과 데이타들을 한 번 모으는데 필요한 메시지 전송 횟수이다.
본 실험에서는 두 라우팅 트리의 성능 비교를 위해 센서 네트워크 환경을 시뮬레이션하였다. 센서 네트워크는 가로 길이 w 미터, 세로 길이 h 미터인 사각형의 형태를 가진다.
밀도 실험: 밀도 변화에 따른 두 라우팅 트리의 성능변화를 알아 보는 실험이다. 센서 노드들이 드문드문 배치된 센서 네트워크에서부터 조밀하게 배치된 센서 네트워크까지, 밀도 값을 변화시켜 가면서 두 라우팅 트리의 성능 변화를 알아 본다.
FRT는 각 노드가 자신에게 가장 먼저 질의 메시지를 전달한 노드를 부모 노드로 선택하여 구성된다. 실험에서는 네트워크의 상황에 따라 이웃 노드들 중 가장 먼저 질의를 전달하는 노드가 달라질 수 있다는 사실을 반영하기 위해 센서 노드가 자신의 레벨 값 보다 하나 작은 레벨 값을 가지는 이웃 노드들 중에서 무작위로 한 노드를 부모 노드로 선택하게 하였다.
실험에서는 다음의 두 라우팅 트리의 성능을 비교 평가한다.
네트워크 크기 실험: 센서 네트워크의 크기 변화에 따른 두 라우팅 트리의 성능 변화를 알아 본다. 좁은 지역에 센서 노드들이 배치된 경우(빌딩 내어〕서부터, 넓은 지역에 센서 노드들이 배치된 경우(동물들의 서식지)까지, 센서 네트워크의 크기를 변화시키며 두 라우팅 트리의 성능 변화를 알아 본다.
질의 선택도 실험에서는 질의 선택도를 1%부터 100%까지 변화시켜가며 두 라우팅 트리의 성능을 비교하였다. 그림 9는 질의 선택도 살험의 결과를 보여 준다.
대한 QSRT가 구성된다. 질의 전달 및 QSRT 구성 단계에서는 질의 메시지가 센서 네트워크 전체로 전달되는 과정을 통해 각 센서 노드의 MD 값이 계산되어질의 메시지에 기록되어 전달되고, 각 센서 노드는 후보 부모 노드들 중에서 가장 작은 MD 값을 가지는 노드를 부모 노드로 선택하여 라우팅 트리를 구성한다. 질의 메시지의 포맷은 다음과 같다(질의 전달 및 QSRT 구성단계의 수행 절차를 기술하는데 관련 없는 필드들은 표시하지 않았음.
질의마다 질의의 조건에 따라 결과 데이타 생성 노드들의 위치가 달라질 수 있으므로, 질의별로 서로 다른 QSRT가 구성되고 각 센서 노드는 질의별로 서로 다른 부모 노드 쪽으로 해당 질의의 결과 데이타를 전송한다. 기존의 라우팅 트리는 여러 질의 처리에 동일하게 사용되는 것으로서 질의별로 서로 다른 부모 노드 쪽으로 결과 데이타를 전송하여 부분 집계 및 패킷 합병의 기회를 증대시킬 수 있는 기회를 얻지 못한다.
구성 방안에 대해 논의한다. 추가적으로 본 논문에서는 집계 질의들 중에서도 고정 값을 가지는 애 트리 뷰트가 조건절에 하나 이상 포함되는 질의 처리를 논의한다. 고정 값을 가지는 애트리뷰트들의 예로는 센서 노드의 아이디, 센서 노드의 위치(X, y 축 정보), 고도(층수) 등이 있다.
후보 부모 집합 결정 단계를 통해 각 센서 노드의 후보 부모 집합이 결정된 상태에서, 질의 요청이 들어왔을 때 질의 전달 및 QSRT 구성 단계가 수행되어 해당 질의에 대한 QSRT가 구성된다. 질의 전달 및 QSRT 구성 단계에서는 질의 메시지가 센서 네트워크 전체로 전달되는 과정을 통해 각 센서 노드의 MD 값이 계산되어질의 메시지에 기록되어 전달되고, 각 센서 노드는 후보 부모 노드들 중에서 가장 작은 MD 값을 가지는 노드를 부모 노드로 선택하여 라우팅 트리를 구성한다.
데이터처리
서로 다른 10 개의 센서 네트워크를 생성하고 각 실험을 이 10 개의 센서 네트워크에 대해 반복적으로 수행하였으며 실험의 결과 값으로 10 번의 반복 실험 수행에서 나온 결과 값들의 평균 값을 사용하였다.
이론/모형
질의의 결과 데이타들을 베이스 스테이션으로 모으기 위해 베이스 스테이션을 루트로 하는 라우팅 트리 (routing tree)가 사용된다. 라우팅 트리는 라우팅 트리 구성 메시지가 베이스 스테이션으로부터 센서 네트워크 전체로 전달되는 과정을 통해 구성된다.
성능/효과
QSRT는 질의 분배 단계를 통해 구성된다. 각 센서 노드는 질의 분배 단계에서 질의 메시지를 이웃 노드에게 전달할 때 자신을 통해 결과 데이타를 루트 노드 쪽으로 전달할 경우(즉 자신을 부모 노드로 선택할 경우) 그 결과 데이타가 몇 홉 이후에 다른 결과 데이타 생성 노드와 만나는지에 대한 정보를 질의 메시지에 기록하여 전달한다. 각 센서 노드는 질의 메시지에 기록된 정보를 바탕으로 이웃 노드들 중에서 자신의 결과 데이타를 가장 빨리 다른 결과 데이타와 만나도록 전송해 주는 센서 노드를 자신의 부모 노드로 선택하여 QSRT를구성한다.
두 그래프 간의 기울기의 차이를 통해 알 수 있듯이, 밀도가 커짐에 따라 QSRT와 FRT의 성능 차이는 더욱 커진다. 그림 11의 밀도 실험 결과 그래프는 밀도 값이 20일 때 QSRT가 FRT에 메시지 전송 횟수를 28% 가까이 줄일 수 있음을 보여 주며, 추가적인 실험을 통해 밀도가 20 이상인 경우 둘 간의 성능 차이가 더욱 커짐을 확인하였다
네트워크 실험 결과 그래프는 QSRT가 FRT에 비해 최고 18% 정도까지 메시지 전송 횟수를 줄일 수 있음을 보여준다. 네트워크 실험결과를 통해 센서 노드들이 한 건물 내에 설치되어 빈방 여부를 알아 보는 센서 네트워크 응용에서부터 넓은 지역에 배치되어 동물들의 서식지를 관찰하는 웅용까지 다양한 환경에서의 질의처리에 QSRT가 기존의 라우팅 트리보다 효과적으로 사용될 수 있다는 것을 알 수 있다.
네트워크 실험 결과 그래프에서 네트워크 크기가 증가함에 따라 두 라우팅 트리의 성능 차이는 점점 증가하다가 네트워크 크기가 480 이상이 될 때부터는 그 차이가 더 증가하지 않고 16%에서 18%에 머무른다(네트워크 크기 1080 이상의 실험에서도 마찬가지임). 네트워크 480 이하에서 네트워크 크기가 증가함에 따라 두 라우팅 트리의 성능 차이가 커지는 이유는 QSRT에서는결과 데이타들이 곧 서로 만나 무임승차의 효과를 얻는 반면, FRT에서는 결과 데이타들이 다른 결과 데이타를만나지 못하고 전달되어 그만큼의 전송 비용이 더 들기 때문이다.
보여준다. 네트워크 실험결과를 통해 센서 노드들이 한 건물 내에 설치되어 빈방 여부를 알아 보는 센서 네트워크 응용에서부터 넓은 지역에 배치되어 동물들의 서식지를 관찰하는 웅용까지 다양한 환경에서의 질의처리에 QSRT가 기존의 라우팅 트리보다 효과적으로 사용될 수 있다는 것을 알 수 있다.
질의 선택도 실험 결과는 센서 노드들 중 일부 노드들의 정보를 알아 보고자 하는 일반적인 형태의 질의 처리에 QSRT가 기존의 라우팅 트리보다 특히 효과적으로 사용될 수 있음을 보여 준다. 또한 네트워크 실험 결과는 작은 규모의 센서 네트워크 (빌딩 내)에서뿐만 아니라 큰 규모의 센서 네트워크(동물의 서식지)에서의 질의 처리에도 QSRT가 기존의 라우팅 트리보다 효과적으로 사용될 수 있음을 보여 준다. 마지막으로 밀도 실험은 센서 노드들이 드문드문 배치된 센서 네트워크에서의 질의 처리에 QSRT가 기존의 라우팅 트리에 비해 효과적으로 사용될 수 있을뿐만 아니라 센서 노드들이 조밀하게 배치된 센서 네트워크에서의 질의 처리에는 더욱 효과적으로 사용될 수 있음을 보여 준다 QSRT를 데이타 수집에 사용할 경우 기존의 라우팅 트리에 비해 메시지 전송 횟수를 18%까지 줄일 수 있고 센서 노드들이 조밀하게 배치된 센서 네트워크에서는 28% 이상도 줄일 수 있다.
또한 네트워크 실험 결과는 작은 규모의 센서 네트워크 (빌딩 내)에서뿐만 아니라 큰 규모의 센서 네트워크(동물의 서식지)에서의 질의 처리에도 QSRT가 기존의 라우팅 트리보다 효과적으로 사용될 수 있음을 보여 준다. 마지막으로 밀도 실험은 센서 노드들이 드문드문 배치된 센서 네트워크에서의 질의 처리에 QSRT가 기존의 라우팅 트리에 비해 효과적으로 사용될 수 있을뿐만 아니라 센서 노드들이 조밀하게 배치된 센서 네트워크에서의 질의 처리에는 더욱 효과적으로 사용될 수 있음을 보여 준다 QSRT를 데이타 수집에 사용할 경우 기존의 라우팅 트리에 비해 메시지 전송 횟수를 18%까지 줄일 수 있고 센서 노드들이 조밀하게 배치된 센서 네트워크에서는 28% 이상도 줄일 수 있다.
밀도 실험의 결과는 QSRT가 센서 노드들이 드문드문 배치된 센서 네트워크에서뿐만 아니라 센서 노드들이 조밀하게 배치된 센서 네트워크까지 다양한 환경에서의 질의 처리에 좋은 성능을 낸다는 것을 보여준다.
같다고 하자. 센서 노드 i가 4 번 질의의 결과 데이타들에 대해 부분 집계 또는 패킷 합병을 수행한 결과를 메시지에 담아 전송하고자 할 때 라우팅 테이블 RTi 로부터 4 번 질의에 대한 메시지는 5 번 노드로 보내야 한다는 것을 알 수 있다. 따라서 센서 노드 느 5 번 노드를 타켓으로 하여 메시지를 전송한다.
다양한 실험을 통해 기존의 라우팅 트리와 QSRT의성능을 비교하였다. 실험의 결과는 QSRT를 사용할 경우 기존 라우팅 트리보다 메시지 전송 횟수를 18% 가까이 줄일 수 있음을 보여 주며, 센서 노드들이 조말하게 배치된 센서 네트워크 환경에서는 메시지 전송 횟수를 28% 이상 줄일 수 있음을 보여준다.
한 결과 데이타가 결과 데이타를 생성하는 노드까지 도달하는데 걸리는 홉 수를 확률 변수 X 로 두면, X는 기하분포(geometric distribution)를 따르고 평균 E(X)는 1/p이다. 즉, FRT에서 한 결과 데이타가 결과 데이타를 생성하는 노드까지 도달하는데 걸리는 평균 홉 수는 라우팅 트리의 레벨과 무관하게 1/p라는 고정값을 가진다. 네트워크 크기가 480 이하일 때는 FRT의 레벨이 1/p보다 작아 한 결과 데이타가 다른 결과 데이타를 만나지 못하고 진행할 수 있는 홉 수는 최대 FRT의 레벨만큼이다.
예를 들어, 센서 노드 i의 결과 데이타가 센서 노드 j에 이르러 부분 집계 및 패킷합병에 참여하였다고 하면, 그곳에서부터는 센서 노드 丿 의 결과 데이타와 합쳐져 센서 노드, 부터는 하나의 메시지로 전송된다. 즉, 센서 노드, 의 결과 데이타는 센서 노드 丿에서 전송될 메시지에 무임승차하는 효과를 얻을 수 있다. 여기서 센서 노드 i는 무임승차 효과로 인해 자신의 결과 데이타를 루트 노드까지 전송하는데 드는 메시지 전송 횟수 중에서 센서 노드 丿의 메시지가 루트 노드까지 전송되는 데 드는 메시지 전송 횟수만큼, 즉 센서 노드 j의 레벨 수만큼을 절약할 수 있다.
본 논문에서는 시뮬레이션 실험을 통해 QSRT의 우수성을 보였다. 질의 선택도 실험 결과는 센서 노드들 중 일부 노드들의 정보를 알아 보고자 하는 일반적인 형태의 질의 처리에 QSRT가 기존의 라우팅 트리보다 특히 효과적으로 사용될 수 있음을 보여 준다. 또한 네트워크 실험 결과는 작은 규모의 센서 네트워크 (빌딩 내)에서뿐만 아니라 큰 규모의 센서 네트워크(동물의 서식지)에서의 질의 처리에도 QSRT가 기존의 라우팅 트리보다 효과적으로 사용될 수 있음을 보여 준다.
그 이유는 큰 질의 선택도에서는 대부분의 노드가 질의의 결과 데이타를 생성하므로 QSRT와 FRT 간에 부분 집계 또는 패킷 합병의 수행 횟수의 차이가 크지 않기 때문이다. 질의 선택도 실험의 결과 그래프는 QSRT가 FRT에 비해 최고 18% 정도까지 메시지 전송 횟수를 줄일 수 있음을 보여준다.
질의 선택도 실험의 결과는 질의 선택도가 1%에 가깝거나 100%에 가까운 경우를 제외하고는 QSRt의 성능이 FRT에 비해 우수함을 보여준다. 일반적으로 사용자는 질의를 통해 관심 있는 센서 노드들의 데이타들만을 선택적으로 알아 보고자 할 것이므로 질의 선택도는 양 극단의 값을 가지지는 않을 것이다.
참고문헌 (13)
J. Hill and D. Culler, 'Mica: a wireless platform for deeply embedded networks,' IEEE Micro 22(6):12-24, 2002
A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, 'Habitat monitoring: Application driver for wireless communications technology,' In ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, 2001
P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, 'Energe-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet,' In Proc. of ACM ASPLOS Conf., 2002
D. Pescovitz. Smart Buildings Admit Their Faults. Lab Notes, http://www.coe.berkeley.edu/labnotes/1101smartbuildings.html
S. R. Madden, M. J. Franklin, and J. M. Hellerstein, 'TinyDB: an acquisitional query processing system for sensor networks,' ACM Trans. on Database Systems, Vol. 30, No. 1, 122-173, 2005
V. Shnayder, M. Hempstead, B. Chen, G. W. Allen, and M. Welsh, 'Simulating the Power Consumption of Large-Scale Sensor Network Applications,' In Sensys, 2004
S. Madden, M. Frankln, J. Hellerstein, and W. Hong, 'TAG: a tiny aggregation service for ad-hoc sensor networks,' In Proc. of OSDI, 2002
Y. Yao and J. Gehrke, 'Query processing for sensor networks,' In Proc. of CIDR Conf., 2003
A. Woo, T. Tong, and D. Culler, 'Taming the underlying challenges or reliable multihop routing in sensor networks,' In SenSys, 2003
A. Woo and D. Culler, 'A transmission control scheme for media access in sensor networks,' In Proc. of ACM MobiCom Conf., 2001
C. Intanagonwiwat, R. Govindan, and D. Estrin, 'Directed diffusion: a scalable and robust communication paradigm for sensor networks,' In Proc. of ACM MobiCom Conf., 2000
M. A. Sharaf, J. Beaver, A. Labrinidis, and P.K. Chrysanthis, 'Balancing energy efficiency and quality of aggregate data in sensor networks,' The VLDB Journal, Vol. 13, No. 4, 384-403, 2004
※ AI-Helper는 부적절한 답변을 할 수 있습니다.