[논문]Zigbee 네트워크에서 Depth를 이용한 효율적인 중간 경로 감소 알고리즘

김덕영; 정우섭; 조성호

Zigbee 네트워크에서 Depth를 이용한 효율적인 중간 경로 감소 알고리즘
An Efficient Shortcut Path Algorithm using Depth in Zigbee Network 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스, v.34 no.12B, 2009년, pp.1475 - 1482

김덕영 (한양대학교 전자컴퓨터통신 공학부) , 정우섭 (한양대학교 전자컴퓨터통신 공학부) , 조성호 (한양대학교 전자컴퓨터통신 공학부)

초록
AI-Helper

ZigBee 네트워크에서 ZigBee 노드는 배터리로 동작하기 때문에 에너지의 효율적인 사용은 필수적이다. 에너지를 효율적으로 사용하기 위해서는 불필요한 네트워크 트래픽을 줄이는 것은 하나의 방법이다. 본 논문에서는 ZigBee 네트워크에서 목적지 노드의 depth를 이용한 효율적인 중간 경유지 감소 알고리즘을 제시한다. 기존 tree 라우팅에서는 각 노드가 오직 자신의 부모 노드 또는 자식 노드에게만 데이터를 전송하는 비효율적인 방식을 채택하고 있다. 마찬가지로 본 논문에서 제안하는 효율적인 중간 경로 감소 알고리즘도 tree 라우팅을 기반으로 하고 있다. 하지만 네이버 테이블과 목적지의 depth를 이용하여 부모나 자식노드만이 아닌 다른 이웃노드에게 전송 가능케 함으로서 그 동안 Tree 라우팅에서 발생했던 coordinator 데이터 병목 현상과 불필요 중간 경로를 최소화시킬 수 있는 알고리즘을 제안한다.

Abstract ▼ AI-Helper

In ZigBee network, using energy efficiently is necessary because ZigBee node works by battery. To use energy efficiently, it is one of the way to reduce unnecessary network traffic. In this paper, it presents efficient shortcut routing algorithm using depth of destination node in ZigBee network. In traditional tree routing, each node transfers data only to its own parent or child node, which is inefficient way. Efficient shortcut routing algorithm is also based on tree routing. However, we suggests the algorithm with using neighbor table and depth of destination that is able to transfer data to other neighbor node, not only to parent or child node. It minimizes coordinator bottleneck state and unnecessary intermediate routing path which happens in traditional tree routing.

주제어

AI 본문요약
AI-Helper

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

문제 정의

기존의 tree 라우팅 방식에서는 단순한 계산식만으로 목적지를 결정하는 방법을 사용 하지만 데이터 전송 경로가 오직 부모 노드나 자식 노드로 제한된다는 치명적인 약점이 존재한다. 따라서 본 논문에서는 분산주소할당 기법(Distributed Address Assignment Mechanism)^[3]에 의하여 목적지 노드의 depth를 미리 판단하고 또한 출발지 노드의 depth와 비교해 목적지 노드의 부모나 자식 노드가 나타날 때까지 최적의 경로로 데이터를 전송하는 알고리즘을 제시한다. 다시 말하면 본 논문에서 제시하는 알고리즘은 자신의 디바이스 주소와 목적지의 디바이스 주소를 이용해 방향을 결정하고 자신의 네트워크 depth와 목적지의 네트워크 depth를 이용해 이웃 노드로 전송하는 방식을 설명한다.
본 논문에서는 ZigBee 네트워크에서 기존 tree 라우팅의 단점을 보완하는 새로운 전송 경로 감소 알고리즘을 제안하였다. 기존 tree 라우팅 알고리즘은 간단한 수식만을 사용하여 라우팅을 한다는 장점이 있지만 오로지 자식과 부모 노드 사이끼리만 데이터 전송이 발생하는 비효율적인 데이터 전송이 빈번하게 일어났다.

가설 설정

DSA는 앞서 말한 데이터 전송 방향을 결정하는 알고리즘이다. 만약 그림 1의 네트워크의 66번 노드에서 50번 노드로 데이터를 전송하고 66번 노드는 네이버 테이블에 54, 55, 65번 노드가 이웃 노드로 설정되어 있다고 가정하자.

제안 방법

또한 Cm=4, Rm=4, Lm=4인 네트워크 환경의 노드 개수 30, 50, 70, 90인 네트워크에서 진행하였다. 각 네트워크당 소스 노드와 목적지 노드를 랜덤하게 선택하여 총 100,000번을 반복 전체 데이터가 전송된 경로의 홉수의 평균값을 산출하는 방법으로 진행하였다.
네트워크 크기에 따른 threshold 값을 측정하기 위하여 여러 가지 threshold depth를 설정하여 시뮬레이션을 진행하였다. 전송 경로 알고리즘은 네트워크의 규모에 따라 성능차이가 발생하기 때문에 네트워크 특성에 따라 threshold depth 값을 설정하여 알고리즘의 성능을 최적화해야 한다.
따라서 본 논문에서는 분산주소할당 기법(Distributed Address Assignment Mechanism)^[3]에 의하여 목적지 노드의 depth를 미리 판단하고 또한 출발지 노드의 depth와 비교해 목적지 노드의 부모나 자식 노드가 나타날 때까지 최적의 경로로 데이터를 전송하는 알고리즘을 제시한다. 다시 말하면 본 논문에서 제시하는 알고리즘은 자신의 디바이스 주소와 목적지의 디바이스 주소를 이용해 방향을 결정하고 자신의 네트워크 depth와 목적지의 네트워크 depth를 이용해 이웃 노드로 전송하는 방식을 설명한다.
본 논문에서 제시한 알고리즘의 성능 검증은 tree 라우팅과 비교하여 진행하였다. 또한 Cm=4, Rm=4, Lm=4인 네트워크 환경의 노드 개수 30, 50, 70, 90인 네트워크에서 진행하였다. 각 네트워크당 소스 노드와 목적지 노드를 랜덤하게 선택하여 총 100,000번을 반복 전체 데이터가 전송된 경로의 홉수의 평균값을 산출하는 방법으로 진행하였다.
제 2장에서는 기존 ZigBee 라우팅 알고리즘에 대하여 간략하게 설명하고 제 3장에서는 제안하는 효율적인 중간 경로 감소 라우팅 알고리즘에 대해 설명하였다. 또한 제안한 알고리즘에 포함되는 세부 알고리즘인 Depth Tracking Algorithm(DTA)와 Direction Selecting Algorithm(DSA)에 대해 설명하였다. 마지막으로 제 4장에서는 제안하는 알고리즘을 도입한 라우팅에 대한 시뮬레이션 자료를 분석 하였다.
하지만 coordinator 데이터 집중화 현상으로 네트워크에서 가장 중요한 역할을 하는 coordinator의 수명 단축 현상과 전송 경로가 오로지 부모나 자식 노드로 한정되는 전송 경로로 인해 불필요한 중간 경유지가 생기는 맹점이 존재한다. 본 논문에서 제안하는 알고리즘은 중간 경유지를 감소시키는 세부 알고리즘인 Depth Tracking Algorithm(DTA)와 Direction Selecting Algorithm(DSA)로 구성된다. 이하 편의상 DTA와 DSA로 대체하여 호칭하도록 하겠다.
본 논문에서 제안하는 전송 경로 감소 알고리즘은 DSA와 DTA로 구성되어있다. DSA 알고리즘은 부모 자식 노드가 아닌 네이버 테이블에 있는 노드들 중 목적지 노드에 근접한 노드들을 전송 가능 노드로 선택한다.
본 논문에서 제안한 중간 경로 감소 알고리즘과 tree 라우팅의 성능을 비교 분석하였다.
DTA는 최종 목적지 노드의 depth값을 참고로 하여 목적지 노드로 데이터를 전송하는 방식이다. 우선적으로 소스 노드는 DSA를 적용하여 데이터 전송 가능 경로를 설정한다. 여기서 설정된 전송 가능 경로 중 DTA를 적용하여 그 중 가장 효율적으로 전송할 수 있는 노드를 선택하여 전송하게 된다.
하지만 네트워크가 커질수록 threshold depth가 작아지는 것이 효율적인 측면에서 더 높게 나타났다. 이는 네트워크가 큰 경우 DTA 실행이 많아진다면 오히려 데이터 전송에 비효율적으로 작용하기 때문에 threshold depth를 조절하여 일정 depth이하에서만 DTA를 실행하도록 전송 경로 알고리즘을 제시하였다.
하지만 네트워크의 크기가 커질수록 단지 목적지의 depth만을 tracking하여 데이터를 전송하게 되면 효율이 다소 떨어지는 단점이 있다. 이를 보완하기 위하여 네트워크의 크기에 따라 DTA를 적용하는 부분을 조절하여 알고리즘을 효율적으로 제시하였다. 그림 4는 간단한 DTA의 흐름도이다.
이는 네트워크 크기에 따른 전송 경로 알고리즘의 효율이 달라지는 것을 말한다. 이를 해결하기 위해 네트워크의 크기에 따른 최적의 threshold depth 값을 시뮬레이션을 통하여 얻을 수 있다.
본 논문에서 제안하는 알고리즘은 중간 경유지를 감소시키는 세부 알고리즘인 Depth Tracking Algorithm(DTA)와 Direction Selecting Algorithm(DSA)로 구성된다. 이하 편의상 DTA와 DSA로 대체하여 호칭하도록 하겠다.

대상 데이터

따라서 네트워크의 크기에 따라 threshold값을 다르게 적용하여 전송 경로 감소 알고리즘을 설계해야 한다. 본 논문에서 시뮬레이션을 진행한 환경은 Cm=4, Rm=4, Lm=4의 노드 개수 30, 50, 70, 90인 네트워크이다.
본 논문에서는 Rm, Cm, Lm이 일정한 네트워크에서 시뮬레이션을 진행하였다. 향후 다양한 네트워크에서 시뮬레이션을 진행하고 다양한 시뮬레이션을 바탕으로 효율적인 threshold depth값을 설정하여 현재의 알고리즘보다 효율적인 전송 경로 감소 알고리즘의 연구를 수행할 것이다.

데이터처리

본 논문에서 제시한 알고리즘의 성능 검증은 tree 라우팅과 비교하여 진행하였다. 또한 Cm=4, Rm=4, Lm=4인 네트워크 환경의 노드 개수 30, 50, 70, 90인 네트워크에서 진행하였다.

성능/효과

그림 7에서 볼 수 있듯이 tree 라우팅 방식은 노드의 수가 증가 할수록 홉 카운트가 꾸준히 증가한다. 반면 전송 경로 감소 알고리즘은 노드의 수가 각각 30개, 50개, 70개, 90개일 때 각각 25.88%, 20.8%, 12.64%, 17.82%의 tree 라우팅 대비 성능향상을 보였다. 여기서 노드가 70개일 때 보다 90개일 때 성능이 더 개선된 것을 볼 수 있다.
이런 전송 가능 노드들 중 DTA를 사용하여 해당 노드의 depth에 따라서 가장 효율적인 전송 경로를 선택한다. 시뮬레이션 결과로부터 노드가 30개일 때 전송 경로 알고리즘은 25.88%, 50개일 때 20.8%, 70개일 때 12.64%, 90개일 경우 17.82%의 성능 향상을 보이는 것을 확인하였다.

후속연구

향후 다양한 네트워크에서 시뮬레이션을 진행하고 다양한 시뮬레이션을 바탕으로 효율적인 threshold depth값을 설정하여 현재의 알고리즘보다 효율적인 전송 경로 감소 알고리즘의 연구를 수행할 것이다. 또한 네이버 테이블을 수집하고 유지하는 비용에 대해서는 본 논문에서는 고려되지 않았기 때문에 이에 대한 연구 또한 향후 과제에 포함시킬 예정이다.
본 논문에서는 Rm, Cm, Lm이 일정한 네트워크에서 시뮬레이션을 진행하였다. 향후 다양한 네트워크에서 시뮬레이션을 진행하고 다양한 시뮬레이션을 바탕으로 효율적인 threshold depth값을 설정하여 현재의 알고리즘보다 효율적인 전송 경로 감소 알고리즘의 연구를 수행할 것이다. 또한 네이버 테이블을 수집하고 유지하는 비용에 대해서는 본 논문에서는 고려되지 않았기 때문에 이에 대한 연구 또한 향후 과제에 포함시킬 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	ZigBee란?	ZigBee는 IEEE 802.15.4 표준을 기반으로 하는 저속의 데이터 전송 기술로써 가격이 저렴하고 저전력의 특징이 있다. IEEE 802.
	ZigBee의 가장 중요한 문제는?	따라서 ZigBee 노드들은 장소와 시간의 제약 없이 통신이 가능해야 한다. 하지만 배터리를 사용하는 시스템적 특성 때문에 네트워크를 최대한 오래 유지하기 위해서 데이터 전송 시 전원 효율적인 측면을 고려하는 것이 가장 중요한 문제이다. 이런 문제들을 해결하기 위하여 여러 가지 연구가 진행되고 있다.
	ZigBee는 어떤 목적으로 만들어진 기술인가?	ZigBee는 시간과 장소에 구애 받지 않는 Ubiquitous 환경을 실현하고자 하는 목적으로 만들어진 기술 중 하나이다. 따라서 ZigBee 노드들은 장소와 시간의 제약 없이 통신이 가능해야 한다.

참고문헌 (10)

ZigBee Alliance, ZigBee-2006 Specification: ZigBee Document 053474r06, Version 1.0, Dec. 2004
ZigBee Alliance, ZigBee-2006 Specification: ZigBee Document 053474r13, Dec. 2006
ZigBee Alliance, ZigBee-2007 Specification: ZigBee Document 053474r17, Jan. 2007
최훈, 백윤주, “무선 센서 네트워크에서 중첩 방지를 고려한 효율적인 클러스터링 기법,” 한국통신학회논문지, 33(5), pp. 253-259, 2008
이유진, 안순신, '지그비 센서 네트워크에서의 에너지 효율적 라우팅을 고려한 비콘 전송 스케줄링 기법,' 한국정보과학회논문지, 33(2), pp.625-630, May 2008
K. Khamforoosh and H. Khamforoush, 'A New Routing Algorithm for Energy Reduction in Wireless Sensor Networks,' IEEE, pp. 505-509, 2009
K. T. Kim and H. Y. Youn, 'An Energy Efficient Routing Protocol in Wireless Sensor Networks,' IEEE Computer Society, pp.132-139, 2009
T. Kim and D. Kim, 'Shortcut Tree Routing in ZigBee Networks,; Int. Symposium on Wireless Percasive Computing, Feb. 2007
D. W. Seo, D. S. Yun, and S. H. Cho, 'A Network Performance Improvement for One-to-One and Many-to-One Communication Environment in ZigBee,' Internet Magazine ElectroScop, Nov. 2007
김두현, 조성호, 'Zigbee 네트워크에서 이동성노드를 이용한 효율적인 트리 라우팅 기법,', 제21회 신호처리합동학술대회, Sep. 2008.

저자의 다른 논문 :

표제어: 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

연합인증