[논문]불규칙적 무선센서네트워크에 강한 위치기반 다중경로 제공 방안

김성휘; 박호성; 이정철; 오승민; 김상하

doi:10.7840/kics.2012.37b.1.21

불규칙적 무선센서네트워크에 강한 위치기반 다중경로 제공 방안
A Robust Disjoint Multipath Scheme based on Geographic Routing in Irregular Wireless Sensor Networks 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스, v.37B no.1, 2012년, pp.21 - 30

김성휘 (충남대학교 컴퓨터공학과 컴퓨터네트워크 연구실) , 박호성 (충남대학교 컴퓨터공학과 컴퓨터네트워크 연구실) , 이정철 (충남대학교 컴퓨터공학과 컴퓨터네트워크 연구실) , 오승민 (충남대학교 컴퓨터공학과 컴퓨터네트워크 연구실) , 김상하 (충남대학교 컴퓨터공학과 컴퓨터네트워크 연구실)

초록
AI-Helper

무선센서네트워크는 전력 공급이 제한적인 대규모의 센서 노드들로 구성되어 있다. 에너지 비용의 최소화와 여러 홉을 거쳐 싱크 노드까지 안정적으로 데이터전송의 신뢰성을 높이는 것은 매우 중요한 요소이다. 데이터 전송의 신뢰성을 높이는 방안으로 다중경로 라우팅 방안이 제시되고 있다. 플러딩 기반의 다중경로 라우팅 방식은 불규칙적 무선센서네트워크에서도 효과적으로 다중경로를 구성할 수 있는 장점이 있지만 전원 공급에서 제약이 많은 무선센서네트워크에서는 적합하지 않은 라우팅 방식이다. 그러나 최소의 오버헤드를 가진 지역 위치정보를 이용하는 위치기반 라우팅 방식은 비플러딩 방식으로 무선센서네트워크에서 효율적인 방식이지만 다중경로 구성 시 데이터 패킷의 충돌을 유발할 수 있다. 패킷 충돌을 제어할 수 있는 방안으로 다중경로 파이프라인 개념을 도입하였지만 홀과 같은 불규칙적 네트워크에서는 파이프라인을 구성하기가 어렵다. 이러한 문제점을 해결하기 위하여 가상 그리드 좌표 상에서 위치기반 포워딩 방식과 다중경로 상의 홀 회피 알고리즘이 결합된 새로운 다중경로 라우팅 방식을 제안한다. 제안된 다중경로 방식은 불규칙적 무선센서네트워크에서 효율적이고 전송 신뢰성을 높일 수 있는 노드 분리된 다중경로(multipath) 파이프라인을 구성할 수 있는 방식이다. 시뮬레이션 결과는 이러한 주장의 타당성을 제공한다.

Abstract ▼ AI-Helper

Sensor networks are composed of a great number of sensor nodes with constrained battery. Disjoint multipath scheme based flooding method has a merit that efficiently construct multipath in irregular networks, but causes lots of energy consumption in networks. Flooding method is not a suitable technology in wireless sensor networks with constrained battery. We introduce energy-efficient geographic routing scheme considered as an efficient, simple, and scalable routing protocol for wireless sensor networks. The geographic routing scheme on multipath generates a problem with a congestion. So we introduce the concept of multipath pipeline as a congestion avoidance strategy. But multipath pipelines have a big problem on the boundary of holes under irregular networks. We propose a novel disjoint multipath scheme as combined method with geographic routing scheme and hole detouring algorithm on multipath. A novel disjoint multipath scheme constructs disjoint multipath pipelines efficiently for reliability without a collision in irregular wireless sensor networks. Simulation results are provided to validate the claims.

주제어

AI 본문요약
AI-Helper

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

문제 정의

다음은 이 논문에서 두 번째 핵심 개념인 소스 노드가 보낸 데이터 패킷을 이용하여 홀의 경계(boundary) 정보를 파악할 수 있는 홀 경계 감지 알고리즘(hole boundary detection algorithm)에 대해 설명하고자 한다.
몇몇 잘 알려진 다중경로 라우팅 방안^{[5][7][8][11]}들은 노드가 분리된 다중경로를 구성할 수 있으나 에너지측면에서 비효율적이고 에너지 효율적인 위치기반 라우팅 방식^[1]은 홀과 같은 불규칙적인 네트워크에서 명시적 분리된 다중경로를 구성하기 어렵다. 본 논문에서는 에너지 효율적 위치기반 라우팅 방식을 적용하여 불규칙적 센서네트워크에서 데이터 충돌과 간섭 없이 명시적 분리된 다중경로를 구성할 수 있는 방안을 제시하는 것에 그 목적이 있다. 그리고 홀(hole)이 있는 불규칙적 센서 네트워크에서 에너지 효율적인 위치기반(geographic) 포워딩(forwarding) 방식과 충돌 없이 다중경로 상에서 홀을 피할 수 있는 규칙(rule)을 포함하는 분리된(disjoint) 다중경로(multipath) 라우팅 방식을 제안한다.
두 방식 모두 다중경로의 수가 증가하면 오버헤드가 증가하거나 홀 주위의 노드에서 불필요한 데이터 충돌이 발생하여 에너지가 급속하게 증가되는 현상이 발생한다. 이 논문에서는 수많은 노드를 가진 대규모 센서네트워크에서 에너지 효율적인 위치기반 라우팅 방식과 다중경로에서 충돌 없이 효과적으로 피할 수 있는 새로운 홀 우회 규칙(rule)을 포함된 다중경로 라우팅 방식을 제안한다.
이 장에서는, 기존에 제안된 방식과 성능을 비교 분석하고 시뮬레이션 결과를 제시하고자 한다. 기존에 제안된 여러 방식 중 비교 대상인 방식은 플러딩 방식으로 다중경로를 구성하는 SMR(Split multipath routing)^{[4 ]}방식과 비플러딩 방식으로 가상 파이프라인을 이용하여 명백한 다중경로를 구성하는 EDM(Explicit Disjoint Multipath) 방식^[11]과 비교하 였다.

가설 설정

α는 정사각형 셀의 한 변의 길이로서 가상 그리드 구조에서 노드가 살포되는 면적과 노드의 수에 의해 초기에 결정되는 크기로 센서 노드의 전송 반경(R) 보다 작게 설정된다. 그리고 여기에 적용된 위치기반(geographic) 라우팅 방식은 세 가지 조건을 가정한다. 첫 번째, 각 노드는 GPS 또는 다른 위치서비스를 통해 자신의 위치정보를 알고 있다는 가정과 두 번째, 각 노드는 비컨 메시지를 통해 하나의 홉(one-hop) 이웃 노드의 위치를 알고 있다.
첫 번째, 각 노드는 GPS 또는 다른 위치서비스를 통해 자신의 위치정보를 알고 있다는 가정과 두 번째, 각 노드는 비컨 메시지를 통해 하나의 홉(one-hop) 이웃 노드의 위치를 알고 있다. 마지막으로, 소스 노드는 목적지 노드의 위치를 알고 있다는 가정이다. 위의 가정에서 모든 센서 노드가 자신의 위치 정보와 목적지의 위치를 안다.
소스 노드와 목적지 노드 사이에 홀이 존재하는 불규칙적 네트워크에서 다중경로를 구성한다고 가정한다. 단거리 경로인 P₀를 포함한 3개의 다중경로가 동시에 홀을 만날 경우 그림2의 (나)와 같이 홀 주위를 우회한다.
시뮬레이션을 수행하기 위한 무선센서네트워크 모델은 1000×1000 m2 영역에서 센서 노드 400개가 랜덤으로 분포되어 있다고 가정한다.
임의의 주어진 셀 면적 α2내에 최소 한 개 이상의 센서 노드가 존재한다고 가정한다.
그리고 여기에 적용된 위치기반(geographic) 라우팅 방식은 세 가지 조건을 가정한다. 첫 번째, 각 노드는 GPS 또는 다른 위치서비스를 통해 자신의 위치정보를 알고 있다는 가정과 두 번째, 각 노드는 비컨 메시지를 통해 하나의 홉(one-hop) 이웃 노드의 위치를 알고 있다. 마지막으로, 소스 노드는 목적지 노드의 위치를 알고 있다는 가정이다.

제안 방법

본 논문에서는 에너지 효율적 위치기반 라우팅 방식을 적용하여 불규칙적 센서네트워크에서 데이터 충돌과 간섭 없이 명시적 분리된 다중경로를 구성할 수 있는 방안을 제시하는 것에 그 목적이 있다. 그리고 홀(hole)이 있는 불규칙적 센서 네트워크에서 에너지 효율적인 위치기반(geographic) 포워딩(forwarding) 방식과 충돌 없이 다중경로 상에서 홀을 피할 수 있는 규칙(rule)을 포함하는 분리된(disjoint) 다중경로(multipath) 라우팅 방식을 제안한다.
이 장에서는, 기존에 제안된 방식과 성능을 비교 분석하고 시뮬레이션 결과를 제시하고자 한다. 기존에 제안된 여러 방식 중 비교 대상인 방식은 플러딩 방식으로 다중경로를 구성하는 SMR(Split multipath routing)^{[4 ]}방식과 비플러딩 방식으로 가상 파이프라인을 이용하여 명백한 다중경로를 구성하는 EDM(Explicit Disjoint Multipath) 방식^[11]과 비교하 였다.
목적지 노드는 두 경로 P₀, P₁ 양쪽에서 보내 온 홀의 위치 정보를 통해 홀 전체의 경계(boundary) 정보를 홀 주위 노드들을 포함하여 계산한 후 소스 노드에게 전달된 똑같은 경로를 경유하여 전송한다. 다음은 앞에서 설명한 다중경로 상에서 홀 우회 규칙과 홀 경계(boundary) 감지 알고리즘을 이용하여 가상 그리드 상에서 동시에 다중경로를 구성할 수 있는 다중경로 라우팅 방식을 설명하고자 한다.
두 번째 방식은 비플러딩 방식으로 센서네트워크에서 가장 매력적인 라우팅 방식으로 위치기반 라우팅 방식^[1]이 있으며 로컬 노드 정보를 이용하여 소스 노드와 목적지 노드 사이에 가장 단거리 경로인 주 경로를 찾은 다음 주 경로의 노드에 근접해 있는 이웃노드를 찾아 다중 경로를 구성한다. 그리고 소스가 주 경로와 분리된 대체 다중 경로를 설정한다.
우리는 제안한 다중경로 라우팅 방식의 성능을 분석하고 비교하기 위해 다음과 같은 세가지 성능 평가 항목을 사용한다.
제안된 방안은 다중경로 파이프라인 상에서 홀 회 =피 알고리즘과 결합된 불규칙적 센서네트워크에 강한 명시적(explicit) 분리된 다중경로(Robust Disjoint Multipath) 방식을 제안한다. 제안된 방식은 에너지 효율적인 위치기반 라우팅 방식이 다중경로 상에서 발생되는 문제점을 해소한 홀 우회 알고리즘과 결합된 방식으로 홀이 존재하는 불규칙적 네트워크에서 효과적으로 다중경로 파이프라인을 구성할 수 있는 방식이다.
제안된 방안은 다중경로 파이프라인 상에서 홀 회 =피 알고리즘과 결합된 불규칙적 센서네트워크에 강한 명시적(explicit) 분리된 다중경로(Robust Disjoint Multipath) 방식을 제안한다. 제안된 방식은 에너지 효율적인 위치기반 라우팅 방식이 다중경로 상에서 발생되는 문제점을 해소한 홀 우회 알고리즘과 결합된 방식으로 홀이 존재하는 불규칙적 네트워크에서 효과적으로 다중경로 파이프라인을 구성할 수 있는 방식이다.
홀의 사이즈가 1, 4, 9×α2로 구성하여 홀이 있는 불규칙적 네트워크로 모델화 하였다.

이론/모형

우리는 제안한 네트워크 모델링은 네트워크 시뮬레이터 Qualnet 4.0^[10]이용하여 구현하였다. 센서 노드들은 MICA2^[13]의 표준을 따른다.

성능/효과

그림8은 다중경로의 수에 따라 전체 다중경로 전송 시간을 보여준다. 다중경로의 수가 증가함에 따라 플러딩 방식의 SMR은 전송 시간이 급격하게 증가함을 볼 수 있었고 비플러딩 방식의 EDM과 제안된 RDM은 전송시간에 차이가 없음을 보여준다. 그림9는 홀의 사이즈에 따라 전체 에너지 소비량을 보여준다.
첫째로 다중경로 상에서 홀 우회 방식과 두 번째로 홀 경계(hole boundary) 감지 알고리즘이 있다. 두 방안을 통해서 홀(hole)을 피한 다중경로 파이프라인을 구성하여 신뢰성 있는 데이터 전송이 가능하다. 첫 번째 방식인 다중경로 상에서 홀 우회 방식에 대해 설명하고자 한다.
그리고 홀이 존재하는 불규칙 센서네트워크에서는 다중경로 파이프라인을 구성하지 못하고 홀 주위 노드에서 데이터 패킷의 충돌 현상이 발생하여 에너지의 고갈 현상이 나타난다. 이러한 문제점을 효과적으로 개선하기 위해 다중경로 파이프라인 상에서도 패킷 충돌 없이 홀 우회 알고리즘과 홀 영역 감지하는 홀 경계 감지 알고리즘을 이용하여 효과적으로 노드가 분리된 다중경로를 구성할 수 있었고 분리된 다중경로를 통해서 간섭 없이 신뢰있는 데이터 패킷 전송이 가능함을 실험 결과를 통해서 볼 수 있었다. 제안된 방식은 홀이 존재하는 불규칙 무선센서네트워크에서 명시적 노드가 분리된 다중경로를 구성할 수 있으며 데이터 패킷 충돌현상 없이 에너지 효율적이고 간섭이 적은 개선된 다중경로를 제공해 주는 라우팅 방식임을 보여준다.
그러나 비플러딩 방식의 EDM은 홀의 사이즈가 증가함에 따라 홀을 피하기 위해 홀 주위에서 충돌이 많이 발생하여 경로 재설정을 위한 에너지 소비량이 많아짐을 보여준다. 제안된 RDM 방식은 다중경로에서도 홀을 피할 수 있는 알고리즘과 홀의 정보를 수집하는 홀 경계 감지 알고리즘을 통해 홀을 피한 다중경로를 구성하기 때문에 홀에 의한 에너지 소비량이 과다하게 발생하지 않는 장점을 시뮬레이션을 통해 확인할 수 있었다.
이러한 문제점을 효과적으로 개선하기 위해 다중경로 파이프라인 상에서도 패킷 충돌 없이 홀 우회 알고리즘과 홀 영역 감지하는 홀 경계 감지 알고리즘을 이용하여 효과적으로 노드가 분리된 다중경로를 구성할 수 있었고 분리된 다중경로를 통해서 간섭 없이 신뢰있는 데이터 패킷 전송이 가능함을 실험 결과를 통해서 볼 수 있었다. 제안된 방식은 홀이 존재하는 불규칙 무선센서네트워크에서 명시적 노드가 분리된 다중경로를 구성할 수 있으며 데이터 패킷 충돌현상 없이 에너지 효율적이고 간섭이 적은 개선된 다중경로를 제공해 주는 라우팅 방식임을 보여준다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무선센서네트워크는 무엇으로 구성되어 있는가?	무선센서네트워크는 전력 공급이 제한적인 대규모의 센서 노드들로 구성되어 있다. 에너지 비용의 최소화와 여러 홉을 거쳐 싱크 노드까지 안정적으로 데이터전송의 신뢰성을 높이는 것은 매우 중요한 요소이다.
	플러딩 기반의 다중경로 라우팅 방식는 어떤 장점이 있는가?	데이터 전송의 신뢰성을 높이는 방안으로 다중경로 라우팅 방안이 제시되고 있다. 플러딩 기반의 다중경로 라우팅 방식은 불규칙적 무선센서네트워크에서도 효과적으로 다중경로를 구성할 수 있는 장점이 있지만 전원 공급에서 제약이 많은 무선센서네트워크에서는 적합하지 않은 라우팅 방식이다. 그러나 최소의 오버헤드를 가진 지역 위치정보를 이용하는 위치기반 라우팅 방식은 비플러딩 방식으로 무선센서네트워크에서 효율적인 방식이지만 다중경로 구성 시 데이터 패킷의 충돌을 유발할 수 있다.
	소스 노드에서 데이터 패킷을 목적지로 보내는 데 홀이 존재할 경우의 문제점을 해결하기 위한 연구들은 어떻게 분류할 수 있는가?	이러한 연구들은 크게 두 분류로 나눌 수 있다. 첫째는 FACE 라우팅[1]이 있고 두 번째로 배압(backpressure) 라우팅[12]이 있다. 먼저 FACE 라우팅은 홀의 경계를 따라 데이터 패킷을 라우팅하고 배압 라우팅은 목적지 노드로 가기 위해 막힘(stuck) 노드를 발견하면 다른 경로를 찾는 방법으로 소스 노드 방향으로 거슬러 데이터 패킷을 리턴한다.

참고문헌 (14)

B. Karp and H.T. Kung. "GPSR: Greedy perimeter stateless routing for wireless networks," In Proc. of the 6th Annual Int'l Conf. on Mobile Computing and Networking. Boston: ACM Press, 2000. pp. 243-254.
Q. Fang, J. Gao, and L. J. Guibas, "Locating and bypassing routing holes in sensor networks, " In Proc. of IEEE INFOCOM, vol. 4, pp. 2458-2468, March 2004.
D. Ganesan, R. Govindan, S. Shenker, D. Estrin, "Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks," Mobile Computing and Communications Review, Vol. 5, Nu. 4, pp10-24, 2004.
S. J. Lee and M. Geria, "Split Multipath with Maximally Disjoint Paths in Ad hoc Networks," IEEE ICC, pp.3201-3205, 2001.
X. Li and L. Cuthbert, "A Reliable Node-Disjoint Multipath Routing with Low Overhead in wireless Ad hoc networks", ACM MSWiM, pp. 230-233, Oct. 2004.
R. Xiuli and Y. Haibin, " A Novel Multipath Disjoint Routing to support ad hoc wireless sensor networks", IEEE ISORC, April 2006.
S. Waharte and R. Boutaba, "Totally Disjoint Multipath Routing in Multihop wireless networks", IEEE ICC, pp. 5576-5581, June 2006.
W. Lou, W. Liu, Y.Fang, "SPREAD: Enhancing Data Confidentiality in Mobile Ad Hoc Netwoks", IEEE INFOCOM, pp.2404-2413, 2004.
W Lou, "An Efficient N-to-1 Multipath Routing Protocol in wireless sensor networks", IEEE MASS, Nov. 2005.
Scalable Network Technologies, Qualnet, [online] available: http://www.scalable-networks.com.
H. W. Oh, J. H. Jang, K. D. Moon,, S. C. Park, E. S. Lee and S. H. Kim, "An Explicit Disjoint Multipath Algorithm for Cost Efficiency in wireless sensor networks," PIMRC, Sep. 2010.
T. He, J.A. Stankovic, C. Lu, and T.F. Abdelzaher, "A Spatiotemporal Communication Protocol for Wireless Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, Vol.16, No.10, October 2005, pp. 995-1006.

상세보기
I.F. Akyildiz, S. Weilian, Y. Sankarasubramaniam, and E. Cayirci, "A Survey on Seonsor Networks," IEEE Communications Magazine, Vol. 40, pp. 102-114, Aug. 2002.
S. J. Baek, G. d. Veciana, "Spatial Energy Balancing Through Proactive Multipath Routing in Wireless Multihop Networks," IEEE TRANSACTIONS ON NETWORKIG, Vol. 15, No.1, Feb. 2007

저자의 다른 논문 :

LOADING...

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

연합인증