네트워크 분야에서 데이터 압축은 네트워크 트래픽을 줄이기 위한 전통적이고 효과적인 방법 중 하나이다. 센서 네트워크의 데이터는 시/공간적인 연관성을 가지고 있으며, 이러한 특성을 이용한 데이터 압축 기법들이 많이 연구되고 있다. 센서 노드는 제한된 범위내의 통신이 가능하며, 자신의 통신 반경내의 데이터만을 활용한다. 만약 네트워크의 전체 데이터 분포 특성을 활용할 수 있다면, 데이터 압축의 효율을 증가시킬 수 있다. 본 논문에서는 네트워크 전체 데이터 분포 특성을 활용하기 위한 새로운 접근의 피드백 배포 기법을 통한 데이터 압축 기법을 제안한다. 제안하는 기법은 기지국 혹은 슈퍼 노드에 의해 수집된 데이터의 빈도를 이용하여 허프만 코드를 생성하고, 배포함으로써 네트워크 전체의 데이터 압축을 용이하게 한다. 본 논문의 우수성을 보이기 위해서 시뮬레이션을 통해 성능 평가를 수행하였으며 그 결과 네트워크의 수명이 약 30% 증가하였다.
네트워크 분야에서 데이터 압축은 네트워크 트래픽을 줄이기 위한 전통적이고 효과적인 방법 중 하나이다. 센서 네트워크의 데이터는 시/공간적인 연관성을 가지고 있으며, 이러한 특성을 이용한 데이터 압축 기법들이 많이 연구되고 있다. 센서 노드는 제한된 범위내의 통신이 가능하며, 자신의 통신 반경내의 데이터만을 활용한다. 만약 네트워크의 전체 데이터 분포 특성을 활용할 수 있다면, 데이터 압축의 효율을 증가시킬 수 있다. 본 논문에서는 네트워크 전체 데이터 분포 특성을 활용하기 위한 새로운 접근의 피드백 배포 기법을 통한 데이터 압축 기법을 제안한다. 제안하는 기법은 기지국 혹은 슈퍼 노드에 의해 수집된 데이터의 빈도를 이용하여 허프만 코드를 생성하고, 배포함으로써 네트워크 전체의 데이터 압축을 용이하게 한다. 본 논문의 우수성을 보이기 위해서 시뮬레이션을 통해 성능 평가를 수행하였으며 그 결과 네트워크의 수명이 약 30% 증가하였다.
Data compression technique is traditional and effective to reduce network traffic. Generally, sensor data exhibit strong correlation in both space and time. Many algorithms have been proposed to utilize these characteristics. However, each sensor just utilizes neighboring information, because its co...
Data compression technique is traditional and effective to reduce network traffic. Generally, sensor data exhibit strong correlation in both space and time. Many algorithms have been proposed to utilize these characteristics. However, each sensor just utilizes neighboring information, because its communication range is restrained. Information that includes the distribution and characteristics of whole sensor data provide other opportunities to enhance the compression technique. In this paper, we propose an orthogonal approach for compression algorithm based on a novel feedback diffusion algorithm in sensor networks. The base station or a super node generates the Huffman code for compression of sensor data and broadcasts it into sensor networks. Every sensor that receives the information compresses their sensor data and transmits them to the base station. We define this approach as feedback-diffusion. In order to show the superiority of our approach, we compare it with the existing aggregation algorithms in terms of the lifetime of the sensor network. As a result, our experimental results show that the whole network lifetime was prolonged by about 30%.
Data compression technique is traditional and effective to reduce network traffic. Generally, sensor data exhibit strong correlation in both space and time. Many algorithms have been proposed to utilize these characteristics. However, each sensor just utilizes neighboring information, because its communication range is restrained. Information that includes the distribution and characteristics of whole sensor data provide other opportunities to enhance the compression technique. In this paper, we propose an orthogonal approach for compression algorithm based on a novel feedback diffusion algorithm in sensor networks. The base station or a super node generates the Huffman code for compression of sensor data and broadcasts it into sensor networks. Every sensor that receives the information compresses their sensor data and transmits them to the base station. We define this approach as feedback-diffusion. In order to show the superiority of our approach, we compare it with the existing aggregation algorithms in terms of the lifetime of the sensor network. As a result, our experimental results show that the whole network lifetime was prolonged by about 30%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 기본적으로 센서 데이터의 빈도를 기반으로 한 피드백 정보 생성 기법을 제안한다. 일반적으로 센서 데이터는 시공간적 연관성을 가지고 있으므로동일한 시공간에서 발생하는 데이터는 거의 동일하다.
본 논문에서는 기지국(혹은 슈퍼노드)과 센서 네트워크의 상호작용을 통해 데이터 압축을 수행하는 방법을 제안한다. 그림 2(b)와 같이 수집된 데이터를 이용하여 데이터 압축에 참조가 되는 정보(이하 “피드백”)를 센서 네트워크로 배포함으로써 센서 노드들은 자신의 데이터를 효과적으로 압축한다.
피드백 배포를 통해 효율적인 데이터 압축을 수행하기 위해서는 피드백 배포 시 소요되는 통신 비용을 줄이고, 피드백 정보를 통한 데이터 압축 효율을 높이는 것이 중요하다. 본 논문에서는 센서 데이터의 특성을 고려하여 효과적으로 피드백 정보의 크기를 줄이고, 일정 이상의 압축 효율을 유지하기 위해서 피드백 정보의 재배포 시점을 결정하는 기법을 제안한다. 제안하는 기법의 우수성을 보이기 위해서 시뮬레이션을 통해 성능 평가를 수행하였으며, 센서 데이터가 약 40% 압축되었고, 이를 통해 전체 네트워크의 수명이 약 30% 연장되었다.
데이터 전송에 발생하는 에너지의 크기는 데이터를 전송/수신하는 횟수, 전송하는 데이터의 크기, 전송하는 거리 등의 다양한 요소가 복합적으로 작용한다. 본 논문에서는 이러한 데이터 전송에서 발생하는 에너지 소모의 특징을 고려한 데이터 압축기법을 제안한다. 기본적으로 센서 네트워크에서 발생하는 데이터는 환경적 특성으로 인해 발생하는 데이터가 급격히 변화하지 않는다.
본 논문에서는 전역적인 데이터 분포 특성을 데이터 압축에 활용하기 위한 피드백 배포 기법을 제안한다. 피드백 배포 기법이란 센서 네트워크로부터 수집된 데이터를 기반으로 압축에 활용될 정보를 생성하고, 센서 네트워크로 그 정보를 배포하는 기법이다.
본 논문은 센서 데이터를 효율적으로 압축하기 위한허프만 코딩 기반의 피드백 배포 기법을 제안한다. 공간적인 특성을 이용한 대부분의 압축 기법은 통신 범위의 제약으로 인해 지역적인 데이터 특성만을 반영하는 단점이 있다.
본 장에서는 피드백 배포 기법을 효율적으로 사용하기 위해서 피드백 정보의 크기를 줄이고, 배포 횟수를 줄이기 위한 방법을 기술한다. 피드백 배포 기법은 센서 데이터를 비트로 표현하여 데이터의 크기를 줄인다.
각 센서 노드들은 이 피드백 정보를 저장하고 있으며 그림 5의 과정 2를 수행한다. 센서 자신이 측정한 센서 데이터가 피드백 정보를 이용해 압축 가능 여부를 판단한다. 만약 측정 데이터가 피드백 정보에 포함되어 있는 값과 I 이내의 오차를 가지는 경우, 피드백 정보에 있는 압축 정보를 기지국으로 전송한다.
피드백 배포 기법을 효율적으로 설계하기 위해서 압축 기법의 수집 이득 Cfc(Tc) 을 증가시키고, 순수 피드백 정보 배포 비용 C'a (Tf, F)을 감소시켜야 한다. 순수 피드백 정보 배포 비용은 F와 7}에 비례하므로 본 논문에서는 피드백 정보의 크기를 줄이기 위한 기법과 피드백 정보의 배포 횟수를 줄이기 위한 기법을 연구한다.
가설 설정
N개의 센서 노드로 구성된 TAG기법[13]을 기반으로 트리 형태로 연결된 센서 네트워크가 있다고 가정하자. 각 센서 데이터 u 는 압축 알고리즘에 의해 / 로 압축되고, 기지국으로 데이터를 전송하는 통신 비용은 식(1)과 같다.
예제의 응용 분야는 ±1의 오차허용 범위를 가지고 있고, 3개 미만의 측정 빈도를 보이는 측정값을 허프만 코드 작성에 제외한다고 가정하자. 기지국은 센서 노드 S1~S7으로부터 측정값을 수집하였다.
시간적인 특성을 이용한 압죽 기법은 센서 노드에서 마지막으로 보고된 데이터를 기준으로 현재 데이터의 변화가 발생한 경우 싱크 노드로 데이터를 전송하는 기법이다. 이때, 기지국은 보고되어지지 않은 데이터의 경우 이전과 변화가 없다고 가정한다. [5]에서 제안하는 시간적인 제한 기법은 센서 데이터의 오차 허용치를 미리 정하고, 수집한 데이터의 변화가 허용치보다 큰 경우만 데이터를 기지국으로 전송한다.
제안 방법
시뮬레이션에서 사용된 데이터는 미국 워싱턴주의 온도 데이터를 활용하였으며, 그림 8과 같은 온도 분포를 보인다[9]. 공간적인 연관성을 만들기 위해서 데이터 모델의 위상차를 두어 각 센서 노드가 서로 다른 데이터를 수집하도록 설정하였으며, 센서 노드는 그림 7과 같은 형태의 네트워크 토폴로지를 형성한다. 라우팅 트리의 레벨이 커짐에 따라 네트워크를 구성하는 센서 노드 의수는 24개~440개로 변경된다.
그림 5는 기지국에 수집된 데이터를 바탕으로 만든 피드백 정보를 배포하고, 피드백 정보를 이용해 수집된 데이터를 압축하여 수집하는 과정의 예를 나타낸다. 먼저 기지국에서 앞서 설명한 피드백 정보 생성 알고리즘을 이용해 센서 네트워크에서 수집된 데이터를 바탕으로 피드백 정보를 생성하고, 그림 5의 과정 1과 같이 센서 네트워크로 피드백 정보를 배포한다. 각 센서 노드들은 이 피드백 정보를 저장하고 있으며 그림 5의 과정 2를 수행한다.
기지국은 센서 노드 S1~S7으로부터 측정값을 수집하였다. 먼저, 오차허용범위를 이용하여 측정값을 {10.5, 21.5, 1000}으로 그룹화하고, 특정 임계치 이하의 측정값을 제외한 나머지를 이용하여허프만 코드를 작성한다.
하지만, 허프만 코딩을 위하여 코드 테이블을 센서 네트워크로 배포하는 것은 많은 통신 비용을 필요로 한다. 본 논문에서는 피드백 정보의 크기를 줄이기 위해서 먼저 센서 데이터의 특징을 분석하고, 이를 고려하여 피드백 정보의 크기를 줄인다. 또한, 수집된 데이터의 압축되는 정도를 이용하여 피드백 정보의 갱신 시점을 결정한다.
그 다음, 허프만 코딩을 이용하여 비트로 변환하고, (센서 데이터값, 비트값丿으로 구성된 허프만 코드 테이블 (Huffman Code Table)을 생성한다. 성능 파라미터인 e 와 feu嚙은 응용 분야가 요구하는 정확도 레벨 또는 데이터 분포의 특성에 따라 정의될 수 있으며, 성능 평가의 실험 모델에서 최적의 파라미터를 찾기 위해서 값을 변화시키면서 실험을 수행하였다.
메시지 수신에 소모되는 에너지 모델은 (메시지 크기} 乂 {수신 비용} 이며, 수신 비용은 50nJ/b으로 설정하였다[10, 11]. 수집된 센서 데이터의 정확성을 보장하기 위해서 피드백 정보를 이용할 수 없는 데이터의 경우 양자화되지 않은 본래 데이터를 그대로 수집하는 정책을 사용하였다.
제2장에서는 관련 연구로 센서 네트워크의 특성을 이용한 데이터압축 기법과 본 논문에서 활용 하고자 하는 허프만 코딩의 특성을 살펴본다. 저)3장에서는 본 논문에서 제안하는 피드백 배포 기법을 정의하고, 피드백 정보를 이용한 데이터 압축 및 수집기법을 산술적으로 분석한다. 저)4장에서는 본 논문에서 제안하는 허프만 코딩 기반 데이터 압축 기법의 특징과 상세한 과정을 기술한다.
공간적인 특성을 이용한 대부분의 압축 기법은 통신 범위의 제약으로 인해 지역적인 데이터 특성만을 반영하는 단점이 있다. 제안하는 기법에서 기지국(혹은 슈퍼 노드) 에 의해 생성된 피드백 정보는 센서데이터의 전역적인 분포 특성을 반영하고 있기 때문에 효율적인 데이터 압축을 수행한다. 시뮬레이션을 통한 실험 결과, 기존 데이터 수집 기법에 비해 네트워크의 수명이 약 30% 향상되었고, 기존 압축 기법과 병행 사용함으로써 에너지사용의 효율을 더욱 높일 수 있었다.
반대로 피드백 정보를 갱신하지 않으면, 압축 효율이 저하되는 문제점을 가지고 있다. 제안하는 피드백 배포 기법은 적절한 갱신 시점을 찾기 위해서 기지국에서 수집되는 데이터의 수를 계산한다. 이때, 양자화된 데이터의 수집하는 정도를 “Hit율”이라고 정의한다.
피드백 기법은 본 논문에서 처음 제안되는 기법이기 때문에, 고정된 크기의 비트를 이용하여 센서 데이터를 압축하는 기법을 Naive 기법이라고 정의하고, 본 논문에서 제안하는 허프만 코딩 기법과 성능을 비교하였다. 그림 8 의 결과와 같이 Naive 기법을 사용하는 피드백 기법의 경우 네트워크의 규모가 커짐에 따라 발생하는 표본이 증가하여 피드백 정보 배포비용은 급격히 증가한다.
대상 데이터
예제의 응용 분야는 ±1의 오차허용 범위를 가지고 있고, 3개 미만의 측정 빈도를 보이는 측정값을 허프만 코드 작성에 제외한다고 가정하자. 기지국은 센서 노드 S1~S7으로부터 측정값을 수집하였다. 먼저, 오차허용범위를 이용하여 측정값을 {10.
센서 노드의 메시지 전송에 소모되는 에너지 모델은 (메시지 크기} x( {전송 비용} + (증폭 비용} Wa리力 이며, 전송 비용은 50nJ/b, 증폭 비용은 lOOpJ/b/m?으로 설정하였다. 메시지 수신에 소모되는 에너지 모델은 (메시지 크기} 乂 {수신 비용} 이며, 수신 비용은 50nJ/b으로 설정하였다[10, 11]. 수집된 센서 데이터의 정확성을 보장하기 위해서 피드백 정보를 이용할 수 없는 데이터의 경우 양자화되지 않은 본래 데이터를 그대로 수집하는 정책을 사용하였다.
표 1은 시뮬레이션에 사용된 환경 변수이다. 시뮬레이션에서 사용된 데이터는 미국 워싱턴주의 온도 데이터를 활용하였으며, 그림 8과 같은 온도 분포를 보인다[9]. 공간적인 연관성을 만들기 위해서 데이터 모델의 위상차를 두어 각 센서 노드가 서로 다른 데이터를 수집하도록 설정하였으며, 센서 노드는 그림 7과 같은 형태의 네트워크 토폴로지를 형성한다.
데이터처리
제안하는 기법의 우수성을 보이기 위해 일반적인 데이터 수집 기법과 시뮬레이션을 통해 성능을 비교 평가하였다. 표 1은 시뮬레이션에 사용된 환경 변수이다.
이론/모형
기존 압축 기법의 병행 사용 가능함을 평가하기 위해서 [5]에서 사용된 압축 기법을 적용하였다. X축의 값은 라우팅 트리의 레벨을 의미한다.
반면에 나머지 영역의 값들은 발생 하지 않거나 발생 빈도가 현저히 낮다. 이러한 특성을 반영해 효과적으로 데이터를 압축할 수 있는 방법으로 본 논문에서는 허프만 코딩 기법을 이용한다. 앞서 설명한 바와 같이 허프만 코딩은 데이터의 발생 반도에 따라 가변 길이의 코드를 반환한다.
성능/효과
그 이유는 빈도수가 낮은 데이터들을 배제시켜 피드백 정보를 생성하기 때문이다. 그림 8에서는 기존의 연구와 제안하는 기법의 피드백 정보를 통해 전송되는 데이터량을 비교한 결과 제안하는 기법을 사용했을 경우 약 40%의 데이터 전송량을 줄어드는 것을 확인할 수 있다. 이는 허프만 코딩의 이점에 의해 발생빈도가 높은 데이터에 비트수가 적은 코드를 할당하였기 때문이다.
시뮬레이션을 통한 실험 결과, 기존 데이터 수집 기법에 비해 네트워크의 수명이 약 30% 향상되었고, 기존 압축 기법과 병행 사용함으로써 에너지사용의 효율을 더욱 높일 수 있었다. 또한, 센서 네트워크의 오류와 센서 데이터의 오차 범위를 이용하여 에너지 효율적인 데이터 수집이 가능함을 확인하였다. 향후 연구는 제안하는 기법을 센서 네트워크 응용 시스템에 적용하는 것이다.
제안하는 기법에서 기지국(혹은 슈퍼 노드) 에 의해 생성된 피드백 정보는 센서데이터의 전역적인 분포 특성을 반영하고 있기 때문에 효율적인 데이터 압축을 수행한다. 시뮬레이션을 통한 실험 결과, 기존 데이터 수집 기법에 비해 네트워크의 수명이 약 30% 향상되었고, 기존 압축 기법과 병행 사용함으로써 에너지사용의 효율을 더욱 높일 수 있었다. 또한, 센서 네트워크의 오류와 센서 데이터의 오차 범위를 이용하여 에너지 효율적인 데이터 수집이 가능함을 확인하였다.
Hit율을 높게 설정하면 정확한 양자화 정보를 활용할 수 있지만 양자화 정보의 배포가 빈번하게 발생하고, Hit율을 낮게 설정하면 양자화 정보는 최신 정보를 반영하지 못하지만 배포의 빈도가 낮아지게 된다. 실험 결과 약 83% 근처에서 가장 좋은 성능을 보였고, 그보다 더 높게 설정하면 양자화 정보의 배포가 크게 증가하여 오히려 네트워크 수명에 악영향을 미치는 것을 확인하였다. 이때, 센서 네트워크에 포함된 모든 센서 노드로부터 데이터를 수집하는 것을 1주기라고 정의한다.
X축의 값은 라우팅 트리의 레벨을 의미한다. 실험결과 FM 에 비해 제안하는 기법이 약 30%( ((제안하는 기법의 네트워크 수명}-{FM 기법의 네트워크 수명})/{제안하는 기법의 네트워크 수명}*100)의 네트워크 수명 향상을 보였으며, 각 기법에 압축기법을 적용한 경우 추가적인 에너지 사용의 효율이 발생하였다. 이는 제안하는 기법의 특성상 기존 압축 알고리즘과 병행 사용이 가능하다는 것을 의미하며, 전체적으로 피드백 배포를 통한 압축을 수행함으로써 데이터 전송에 소모되는 에너지 소모가 크게 줄었다는 것을 보여준다.
실험결과 FM 에 비해 제안하는 기법이 약 30%( ((제안하는 기법의 네트워크 수명}-{FM 기법의 네트워크 수명})/{제안하는 기법의 네트워크 수명}*100)의 네트워크 수명 향상을 보였으며, 각 기법에 압축기법을 적용한 경우 추가적인 에너지 사용의 효율이 발생하였다. 이는 제안하는 기법의 특성상 기존 압축 알고리즘과 병행 사용이 가능하다는 것을 의미하며, 전체적으로 피드백 배포를 통한 압축을 수행함으로써 데이터 전송에 소모되는 에너지 소모가 크게 줄었다는 것을 보여준다.
본 논문에서는 센서 데이터의 특성을 고려하여 효과적으로 피드백 정보의 크기를 줄이고, 일정 이상의 압축 효율을 유지하기 위해서 피드백 정보의 재배포 시점을 결정하는 기법을 제안한다. 제안하는 기법의 우수성을 보이기 위해서 시뮬레이션을 통해 성능 평가를 수행하였으며, 센서 데이터가 약 40% 압축되었고, 이를 통해 전체 네트워크의 수명이 약 30% 연장되었다.
후속연구
또한, 센서 네트워크의 오류와 센서 데이터의 오차 범위를 이용하여 에너지 효율적인 데이터 수집이 가능함을 확인하였다. 향후 연구는 제안하는 기법을 센서 네트워크 응용 시스템에 적용하는 것이다.
참고문헌 (13)
D. Estrin, L. Girod, G. Pottie and M. Srivastava, "Instrumenting the World with Wireless Sensor Networks," Proc. of International Conference Acoustics, Speech, and Signal Processing, pp. 2033- 2036, 2001.
G. J. Pottie and W. J. Kaiser, "Wireless Integrated Network Sensors," Proc. of Comm. ACM, pp. 51- 58, May 2000.
I.F. Akyildiz, W. Su, Y. Sankarasubramanism and E. Cayirci, "A Survey on Sensor Networks," Proc. of IEEE Communications Magazine, 2002.
M. H. Yeo, M. S. Lee, J. G. Park, S. J. Lee, J. S. Yoo, "A Data-Centric Algrithm for Reducing Network Traffic in Wireless Sensor Networks," Journal of KIISE: Information Networking, vol.35, no.2, pp.139-148, Apr. 2008. (in Korean)
M. Sharaf, J. Beaver, A. Labrinidis, P. Chryanthis, "Tina: A scheme for temporal coherency-aware in-network aggregation," Proc. of the 2003 ACM Workshop on Data Engineering for Wireless and mobile Access, Sep. 2003.
X. Meng, L. Li, T. Nandagopal, S. Lu, "Event contour: An efficient and robust mechanism for tasks in sen-sor networks," Proc. of Technical report, 2004.
S. Pattem, B. Krishnamachari, R. Govindan, "The impact of spatial correlation on routing with compression in wireless sensor networks," Proc. of International Conference on Information Processing in Sensor Networks, pp.28-35, 2004.
D. Petrovic, R. Shah, K. Ramchandran, J. Rabaey, "Data funneling: Routing with aggregation and compression for wireless sensor networks," Proc. of the 2003 IEEE Sensor Network Protocols and Applications, pp.156-162, May 2003.
Live from Earth and Mars (LEM) Project, http://www-k12.atmos.washington.edu/k12/grayskies/, 2006.
W. Heinzelman, "Application-Specific Protocol Architectures for Wireless Networks," PhD dissertation, Massachusetts Inst. Of Technology, 2000.
X. Tang, J. Xu, "Extending Network Lifetime for Precision-Constrained Data Aggregation in Wireless Sensor Networks," Proc. IEEE INFOCOM, pp.1-12, Apr. 2006.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proc. of the I.R.E., pp.1098-1102, 1952.
S. Madden, M.J. Franklin, J.M. Hellerstein, and W. Hong, "TAG: A Tiny Aggregation Service for Ad Hoc Sensor Networks," Proc. Usenix Fifth Symp. Operating Systems Design and Implementation, pp.131-146, Dec. 2002.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.