[논문]센서 네트워크에서 최소 경계 다각형을 이용한 에너지 효율적인 군집 이벤트 탐지 기법

권현호; 성동욱; 유재수

doi:10.5392/jkca.2010.10.12.101

센서 네트워크에서 최소 경계 다각형을 이용한 에너지 효율적인 군집 이벤트 탐지 기법
Energy Efficient Cluster Event Detection Scheme using MBP in Wireless Sensor Networks 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.10 no.12, 2010년, pp.101 - 108

권현호 (충북대학교 정보통신공학과) , 성동욱 (충북대학교 정보통신공학과) , 유재수 (충북대학교 정보통신공학과)

초록
AI-Helper

센서네트워크에서 노드의 에너지 제약 특성을 고려하여 군집 이벤트를 위한 에너지 효율적인 탐지 기법에 대한 다양한 연구들이 진행되고 있다. 기존에 제안된 군집 이벤트 탐지 기법들은 이벤트를 탐지한 센서 중 군집의 경계에 위치한 노드의 정보만을 추출하여 기지국으로 전송하는 방식을 취한다. 하지만 군집 이벤트의 범위가 넓어지고 센서의 배포 밀도가 높아지면 이벤트 경계에 위치한 노드들의 수 또한 증가하여 많은 전송 비용을 필요로 한다. 본 논문에서는 이벤트 경계 노드들의 정보를 압축/요약하여 나타낼 수 있는 인-네트워크 최소 경계 다각형을 이용한 에너지 효율적인 군집 이벤트 탐지 기법을 제안한다. 제안하는 기법은 대규모 센서 네트워크 환경에서 MBP 생성기법을 통해 군집 이벤트의 경계 정보를 표현한다. 제안하는 기법의 우수성을 보이기 위해 제안하는 기법과 기존 기법과의 성능평가를 수행하였다. 성능평가 결과, 최대 92%이상의 정확도를 유지하며 80.13% 에너지 소모량이 감소하였다.

Abstract ▼ AI-Helper

Many works on energy-efficient cluster event detection schemes have been done considering the energy restriction of sensor networks. The existing cluster event detection schemes transmit only the boundary information of detected cluster event nodes to the base station. However, If the range of the cluster event is widened and the distribution density of sensor nodes is high, the existing cluster event detection schemes need high transmission costs due to the increase of sensor nodes located in the event boundary. In this paper, we propose an energy-efficient cluster event detection scheme using the minimum boundary polygons (MBP) that can compress and summarize the information of event boundary nodes. The proposed scheme represents the boundary information of cluster events using the MBP creation technique in the large scale of sensor network environments. In order to show the superiority of the proposed scheme, we compare it with the existing scheme through the performance evaluation. Simulation results show that our scheme maintains about 92% accuracy and decreases about 80% in energy consumption to detect the cluster event over the existing schemes on average.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

센서 네트워크를 통해 감지한 군집 이벤트의 크기가 커지고 이벤트의 둘레가 길어질 경우 이를 표현하기 위한 경계노드의 수도 급격히 증가하게 된다. 따라서 본 논문에서는 군집 이벤트의 크기와 모양을 MBP를 이용하여 정보를 축약시키는 기법을 고안하였다. 실제 군집 이벤트의 모양은 다양한 형태의 곡선들로 표현된다.
즉, 자신과 자신의 이웃노드들의 정보만을 이용하여 군집 이벤트 전체를 포함하는 MBP를 산출하기는 더욱 어렵다. 따라서 본 논문에서는 앞서 제안한 단일 경계 노드 선정 기법을 통해 선정된 경계노드들을 대상으로 MBP 메시지를 전달해 가며 점진적으로 MBP 정보를 완성해 나가는 기법을 제안한다.
본 절에서는 제안하는 군집 이벤트 탐지기법에서 군집 이벤트를 높은 정확도로 요약하기 위한 군집 이벤트 경계 노드 선정 및 인-네트워크 최소 경계 다각형(MBP) 생성 기법을 설명한다. 또한 이를 이용한 에너지 효율적인 군집 이벤트 탐지 및 전송에 대하여 기술한다.
본 논문에서는 군집 이벤트를 에너지 효율적으로 검출하기 위하여 이벤트를 표현하기 위해 이용되는 경계노드들의 정보를 바탕으로 최소 경계 다각형(MBP)를 생성하여 기지국으로 전송한다. 최소 경계 다각형은 특정 군집 이벤트의 영역과 크기를 나타내기 위해 최소의 잉여 공간만을 포함하는 최소의 다각형을 의미한다.
본 논문에서는 에너지 효율적인 최소 경계 다각형을 이용한 군집 이벤트 탐지 기법을 제안하였다. 이를 위해 기존에 제안된 경계 정보 기반 군집 이벤트 탐지 기법들의 문제점을 분석하였다.
이 경우 이벤트의 크기가 커지거나, 둘레의 길이가 길어질 경우 혹은 배포된 센서의 밀도가 높은 경우 경계에 포함되는 노드들의 수가 증가하여 이를 나타내기 위한 정보의 양이 크게 증가한다. 본 논문에서는 이러한 문제점을 해결하기 위해 인네트워크 최소 경계 다각형 생성 기법을 기반으로 경계 노드들의 정보를 압축/요약하여 군집 이벤트 탐지에 소모되는 에너지를 줄이는 기법을 제안한다.
본 논문에서는 이벤트 경계 노드들의 정보를 압축/요약하여 나타낼 수 있는 인-네트워크 최소 경계 다각형을 이용한 에너지 효율적인 군집 이벤트 탐지 기법을 제안한다. 제안하는 기법은 대규모 센서 네트워크 환경에서 연속적이고 광범위한 영역에 걸쳐 발생하는 군집 이벤트의 경계 정보를 최소 경계 다각형(MBP) 생성 기법을 통해 표현한다.
제안하는 MBP 생성기법은 인-네트워크 방식으로 처리되므로 MBP 생성을 시작하기 위한 트리거 노드 선정을 노드들이 자체적으로 처리해야 한다. 본 절에서는 노드들이 자체적으로 트리거 노드를 선정하기 위한 랜덤 대기 트리거 노드 선정 기법과 이로 인해 생성되는 MBP 세그먼트에 대하여 기술한다.
본 절에서는 제안하는 군집 이벤트 탐지기법에서 군집 이벤트를 높은 정확도로 요약하기 위한 군집 이벤트 경계 노드 선정 및 인-네트워크 최소 경계 다각형(MBP) 생성 기법을 설명한다. 또한 이를 이용한 에너지 효율적인 군집 이벤트 탐지 및 전송에 대하여 기술한다.
[4]는 [3] 기법을 이용하여 판단한 전체 경계 노드들을 지역적으로 클러스터를 구축하고, 헤더를 선출하여 경계 정보를 취합하여 기지국으로 전송한다. 이 기법은 변화하는 군집 이벤트를 효과적으로 탐지하기 위해 군집 이벤트의 경계 정보 변화를 클러스터 단위로 업데이트 시키는 방식을 제안한다.

제안 방법

MBP를 생성하기 위해 군집 이벤트의 가장자리 영역에 위치한 센서 노드들이 경계 노드임을 판단했을 때 동시에 모든 경계 노드들이 트리거 노드로써 동작하는 것을 방지하기 위해 CSMA(Carrier Sense Multiple Access) 프로토콜[8]에서 다중 접근 충돌방지를 위해 사용하는 랜덤 대기 기법을 변형하여 적용하였다. 각 경계 노드들은 0~1범위의 값을 무작위로 선정하여 선결정된 최대 대기시간 δ와 곱하여 자신의 대기시간을 결정한다.
Naive 기법과 CODA 기법은 4개의 클러스터로 구성된 네트워크에서 실험되었으며, MBP 검출기법은 4개의 트리거 노드로 이루진 경우가 비교되었다. 각 기법에서 이벤트 검출시 소모하는 에너지를 측정하기 위해 타원형의 군집 이벤트의 크기를 변경해가며 실험을 진행하였다. Naïve 방식의 경우 이벤트를 감지한 모든 센서 노드의 데이터를 수집하므로 가장 큰 에너지 소모를 보인다.
[그림 7]은 군집 이벤트 탐지 기법 별 탐지 정확도에 대한 성능평가 결과이다. 군집 이벤트를 센싱한 모든 노드들의 개수와 각 기법에 의해 측정된 경계 노드 안쪽에 포함되는 노드들의 개수 비로 정확성을 평가하였다. 그 결과 제안하는 기법이 군집 이벤트의 경계 정보를 요약/압축하여 전송하지만 naïve 방식과 CODA 방식의 이벤트 경계노드들의 모든 정보를 전송하는 방식과 대비하여 약 92.
본 논문에서는 에너지 효율적인 최소 경계 다각형을 이용한 군집 이벤트 탐지 기법을 제안하였다. 이를 위해 기존에 제안된 경계 정보 기반 군집 이벤트 탐지 기법들의 문제점을 분석하였다. 기존의 경계 정보 기반 군집 이벤트 탐지 기법들은 군집 이벤트의 크기가 커지거나 센서 노드의 배포밀도가 높아질 경우 이벤트 경계 노드의 수가 증가하여 탐지를 위한 에너지 소모가 증가하는 문제점이 발생한다.
하지만 이러한 경우 [그림 2](a) 와 같이 가장자리 영역에서 다수의 노드가 자신을 경계 노드로 판단하여 불필요하게 두꺼운 가장자리 정보를 형성하게 된다. 이를 해결하기 위하여 본 논문에서는 감지 반경 내의 이웃노드 끼리 최소 크기를 갖는 삼각형을 형성하여 자신과 가장 가까운 이웃 노드만을 판별할 수 있는 기법을 이용한다[7]. 최근접한 이웃 노드만을 이용해 경계를 선정하기 때문에 두껍게 선정된 경계노드를 단일경계 형태로 산출해내고 각 경계 노드는 단일 경계에 포함되는 이웃 노드의 정보를 알 수 있다.
제안하는 MBP 생성기법은 인-네트워크 방식으로 처리되므로 MBP 생성을 시작하기 위한 트리거 노드 선정을 노드들이 자체적으로 처리해야 한다. 본 절에서는 노드들이 자체적으로 트리거 노드를 선정하기 위한 랜덤 대기 트리거 노드 선정 기법과 이로 인해 생성되는 MBP 세그먼트에 대하여 기술한다.
[그림 4]는 제안하는 랜덤 대기 기반 트리거 노드 선정 기법에 따라 선정된 트리거 노드에 의해 MBP를 생성하는 과정을 나타낸다. 제안하는 기법에서는 두 가지 형태의 트리거 노드를 가진다. 첫 번째 트리거 노드는 랜덤 대기 기법을 기반으로 초기 MBP 메시지를 생성 하는 초기 트리거 노드(Initial Trigger Node)가 있고, MBP 메시지 전송 과정에서 가상 폴리라인에서 폴리곤 계수 β보다 멀게 위치하여 선정되는 정점 트리거 노드(Vertex Trigger Node)가 있다.
본 논문에서는 이벤트 경계 노드들의 정보를 압축/요약하여 나타낼 수 있는 인-네트워크 최소 경계 다각형을 이용한 에너지 효율적인 군집 이벤트 탐지 기법을 제안한다. 제안하는 기법은 대규모 센서 네트워크 환경에서 연속적이고 광범위한 영역에 걸쳐 발생하는 군집 이벤트의 경계 정보를 최소 경계 다각형(MBP) 생성 기법을 통해 표현한다. 제안하는 기법의 우수성을 보이기 위해 제안하는 기법과 기존 기법과의 성능평가를 수행한다.
제안하는 기법은 대규모 센서 네트워크 환경에서 연속적이고 광범위한 영역에 걸쳐 발생하는 군집 이벤트의 경계 정보를 최소 경계 다각형(MBP) 생성 기법을 통해 표현한다. 제안하는 기법의 우수성을 보이기 위해 제안하는 기법과 기존 기법과의 성능평가를 수행한다. 본 논문의 구성은 다음과 같다.
제안하는 랜덤 대기 기법을 기반으로 트리거 노드를 선정하게 되면 다수개의 초기 트리거 노드가 발생하고, 이들에 의해 다수의 MBP 세그먼트가 생성된다. [그림 4](c)는 초기 트리거 노드 n3와 n13에 의해 생성된 두 개의 MBP 세그먼트와 각 세그먼트에 저장된 MBP 정점을 나타내기 위한 정보들을 보여준다.
제안하는 기법은 이러한 문제점을 해결하기 위하여 경계 정보를 요약/압축하는 최소 경계 다각형을 이용하였다. 최소 경계 다각형을 생성하기 위하여 MBP 메시지 릴레이를 통해 인-네트워크 방식으로 최소 경계 다각형을 생성하고, 생성된 MBP 세그먼트들을 기지국으로 전송한다. 기존 기법과 성능평가 결과, 92%이상의 정확도를 유지하며, 80.

데이터처리

제안하는 기법의 우수성을 보이기 위해 기존 기법들과 시뮬레이션을 통해 성능을 비교 평가 하였다. 비교한 기법은 이벤트를 탐지한 모든 노드들의 정보를 전송하는 Naïve 기법, 단일 경계 노드를 선출하여 군집 이벤트를 탐지하는 CODA 기법 그리고 제안하는 기법이다.

이론/모형

기존의 경계 정보 기반 군집 이벤트 탐지 기법들은 군집 이벤트의 크기가 커지거나 센서 노드의 배포밀도가 높아질 경우 이벤트 경계 노드의 수가 증가하여 탐지를 위한 에너지 소모가 증가하는 문제점이 발생한다. 제안하는 기법은 이러한 문제점을 해결하기 위하여 경계 정보를 요약/압축하는 최소 경계 다각형을 이용하였다. 최소 경계 다각형을 생성하기 위하여 MBP 메시지 릴레이를 통해 인-네트워크 방식으로 최소 경계 다각형을 생성하고, 생성된 MBP 세그먼트들을 기지국으로 전송한다.

성능/효과

[그림 6]은 발생된 군집 이벤트의 크기에 따른 탐지에 소모되는 에너지양에 대한 성능평가 결과이다. Naive 기법과 CODA 기법은 4개의 클러스터로 구성된 네트워크에서 실험되었으며, MBP 검출기법은 4개의 트리거 노드로 이루진 경우가 비교되었다. 각 기법에서 이벤트 검출시 소모하는 에너지를 측정하기 위해 타원형의 군집 이벤트의 크기를 변경해가며 실험을 진행하였다.
그 결과 제안하는 기법이 군집 이벤트의 경계 정보를 요약/압축하여 전송하지만 naïve 방식과 CODA 방식의 이벤트 경계노드들의 모든 정보를 전송하는 방식과 대비하여 약 92.31%의 높은 정확도를 보임을 확인하였다.
최소 경계 다각형을 생성하기 위하여 MBP 메시지 릴레이를 통해 인-네트워크 방식으로 최소 경계 다각형을 생성하고, 생성된 MBP 세그먼트들을 기지국으로 전송한다. 기존 기법과 성능평가 결과, 92%이상의 정확도를 유지하며, 80.13% 에너지 소모량이 감소하였다.
제안하는 기법의 경우 경계 정보를 요약/압축한 MBP 정보를 기지국에 전송함으로써 타 알고리즘들에 비해 에너지 소모가 크게 감소하는 것을 확인할 수 있다. 비교 결과, 군집 이벤트 탐지에 소모되는 에너지량이 CODA에 비해 제안하는 기법이 약 80.13%감소하였다.
CODA 방식의 경우 단일 경계노드만을 선정하여 기지국으로 전송하지만 군집 이벤트의 크기가 커짐에 따라 경계 노드의 수도 증가하여 높은 에너지 소모를 보인다. 제안하는 기법의 경우 경계 정보를 요약/압축한 MBP 정보를 기지국에 전송함으로써 타 알고리즘들에 비해 에너지 소모가 크게 감소하는 것을 확인할 수 있다. 비교 결과, 군집 이벤트 탐지에 소모되는 에너지량이 CODA에 비해 제안하는 기법이 약 80.
즉, 센서노드들의 대기시간을 δ 만큼의 시간 범위 이내로 균일하게 분산시켜 동시에 다수의 트리거 노드가 발생하는 것을 방지할 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대규모 무선 센서 네트워크는 무엇으로 구성되는가?	최근 무선 통신 기술과 MEMS(Micro Electro Mechanical Systems) 기술의 발전으로 초소형, 고성능의 저렴한 스마트 센서가 개발 되었고 이는 대규모 무선 센서 네트워크의 설계와 운용을 가능하게 하였다. 대규모 무선 센서 네트워크는 수천 ~ 수만 개의 센서 노드들로 구성 된다. 각 센서 노드들은 적재된 센서 모듈의 기능에 따라 온도, 습도, 조도와 같은 다양한 환경 정보를 수집하고, RF 통신을 이용해 다른 센서 노드와 센서 네트워크를 구축하고 있다.
	센서 네트워크에서 발생하는 이벤트를 응용의 형태에 따라 어떻게 구분할 수 있는가?	센서 네트워크에서 발생하는 이벤트는 응용의 형태에 따라 전체 이벤트, 지점 이벤트 및 군집 이벤트로 구분할 수 있다. [그림 1](a)의 전체 이벤트는 센서 네트워크가 배포된 전체 영역의 상태정보를 모니터링 하는 응용에서 모든 센서로부터 수집된 가공되지 않은 데이터를 이용할 때 사용된다.
	센서 노드가 다양한 응용 분야에서 사용되고 있는 이유는?	각 센서 노드들은 적재된 센서 모듈의 기능에 따라 온도, 습도, 조도와 같은 다양한 환경 정보를 수집하고, RF 통신을 이용해 다른 센서 노드와 센서 네트워크를 구축하고 있다. 별도의 통신 인프라를 사용하지 않기 때문에 설치가 쉽고, 광범위한 영역의 환경정보를 수집할 수 있기 때문에 다양한 응용 분야에서 사용되고 있다. 일반적으로 센서 노드는 내장된 배터리로 작동하며, 배터리를 모두 소모하게 되면 더 이상 기능을 수행하지 못한다.

참고문헌 (9)

R. Szewczyk, A. Mainwaring, J. Polastre, and D. Culler, “An Analysis of a Large Scale Habitat Monitoring Application,” Proc. ACM Conf. Embedded Networked Sensor Systems (SenSys‘04), pp.214-226, 2004.
R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring, and D. Estrin, “Habitat Monitoring with Sensor Networks,” Comm. ACM, Vol.47, No.6, pp.34-40, 2004.

상세보기
K. K. Chintalapudi and R. Govindan, "Localized Edge Detection in Sensor Fields," Proc. the 1st IEEE Sensor Network Protocols and Applications, pp.59-70, 2003.
X. Ji, H. Zha, J. J. Metzner, and G. Kesidis, "Dynamic Cluster Structure for Object Detection and Tracking in Wireless Ad-Hoc Sensor Networks,” Proc. the IEEE International Conference on Communications, Vol.7, pp.3807-3811, 2004.
W.-R. Chang, H.-T. Lin, and Z.-Z. Cheng, "CODA: A Continuous Object Detection and Tracking Algorithm for Wireless Ad Hoc Sensor Networks,” Proc. the 5th IEEE Consumer Communications and Networking Conference, pp.168-174, 2008.
Joseph O'Rourke, Computational Geometry in C (2nd Edition), Cambridge Univ. Press, 1998.
J. Liebeherr, M. Nahas, and W. Si, "Application-layer multicasting with delaunay triangulation overlays," IEEE Journal on Selected Areas in Communications, pp.1472-1488, 2002.

상세보기
Andrew S. Tanenbaum, Computer Networks, Prentice Hall, pp.892, 2003.
X. Tang and J. Xu, “Extending Network Lifetime for Precision-Constrained Data Aggregation in Wireless Sensor Networks,” Proc. IEEE INFOCOM, pp.1-12, 2006.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증