[논문]이동성 정보를 이용한 DTN 네트워크 라우팅 프로토콜

장덕현; 심윤보; 김길수; 최낙중; 류지호; 권태경; 최양희

이동성 정보를 이용한 DTN 네트워크 라우팅 프로토콜
Mobility Information based Routing for Delay and Disruption Tolerant Network 원문보기

정보과학회논문지. Journal of KIISE. 정보통신, v.36 no.2, 2009년, pp.130 - 136

장덕현 (서울대학교 전기컴퓨터공학부) , 심윤보 (한국전력공사) , 김길수 (대한민국 육군) , 최낙중 (서울대학교 전기컴퓨터공학부) , 류지호 (서울대학교 전기컴퓨터공학부) , 권태경 (서울대학교 전기컴퓨터공학부) , 최양희 (서울대학교 전기컴퓨터공학부)

초록
AI-Helper

Delay and Disruption Tolerant Network (DTN)은 지속적인 종단간 연결성이 보장되지 않는 상황으로 인해 store and forward 방식의 메시지 전달을 기본으로 하는 네트워크이다. 일반적인 네트워크와 달리 상대적으로 긴 전송 지연 시간, 불안정한 링크 연결성과 같은 특성으로 인해 기존 TCP/IP 기반의 라우팅 프로토콜은 정상적으로 동작하기 힘들다. 따라서 최근에 DTN을 위한 라우팅 프로토콜에 관한 많은 연구가 이루어지고 있다. 본 고에서는 이동 노드의 상대적인 방향차이 또는 이동 노드의 목적지 등과 같은 이동성 정보를 이용한 효과적인 메시지 전달방식을 통해 DTN의 특성을 잘 반영하면서도 기존에 제안된 기법에 비해 전송 확률과 지연 시간, 오버헤드 측면에서 향상된 라우팅 프로토콜을 제안하고 시뮬레이션을 통해 이를 검증한다.

Abstract ▼ AI-Helper

Delay and Disruption Tolerant Network (DTN) employs message delivery based on a store-and-forward method to conquer no guarantee of continuous end-to-end connectivity. Different from general networks, it is hard for the existing TCP/IP-based routing protocols to correctly work, due to the characteristics such as large latency and unstable link connectivity. Thus, many recent studies focus on routing protocols for DTN. In this paper, we propose a novel routing protocol for DTN with efficient message delivery utilizing mobility information such as direction or destination of mobile nodes. And this protocol is enhanced in terms of delivery ratio, decreases latency and overhead compared to the previously proposed solutions. Simulation results prove its superiority.

주제어

AI 본문요약
AI-Helper

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

문제 정의

하지만 DTN의 store & forward 개념을 받아들여 차량의 밀도가 작아 당장 전달할 이웃 차량이 없는 경우 메시지를 저장했다가 나중에 전달하는 접근 방식을 취하는 연구도 발표되었다[131. 그러나 이러한 기법의 경우 도로의 레이아웃과 교통 트래픽 패턴을 이용하여 정해진 장소에 메시지를 전달하는 것으로 호스트 간 전송을 목적으로 하는 본 연구와는 목적이 다르다.

가설 설정

이미 충분한 인프라가 갖춰져 있는 상황에서는 동일한 목표를 달성하기 위한 많은 대안 기술들이 존재하기 때문이다. 본고에서는 특별히 이러한 가정을 바탕으로 그림 1과 같이 두 개의 지역 사이를 오가는 이동 노드의 경우 이동 방향과 목적지 정보가 상대적으로 긴 시간 동안 유지될 수 있는 상황을 가정한다. 본 고에서 제시하는 기법은 기본적으로 epidemic routing이나 spray & wait, pro- phet과 같은 플러딩 기반의 메시지 전달 방식을 채택하고 있다.

제안 방법

또한 DTN을 위해 고안된 라우팅 프로토콜들도 Random Mobility 등과 같은 현실적이지 않은 가정을 기반으로 하여 실제의 상황에서 효율성이 떨어지는 문제점이 있다. 본 고에서 제시하고자 하는 라우팅 프로토콜은 DTN의 특성을 반영하여, 종단간 연결성이 보장되지 않을 경우 store and forward 방식으로 동작하고 현재 자신과 접촉이 있는 노드에게우선적으로 메시지를 전달하는 방식을 취하도록 하였다、 동시에 각 호스트의 이동성 정보, 즉 이동하는 노드 사이의 상대적인 방향각 차이, 노드의 목적지 정보, 그리고 이 두 가지 정보 모두와 노드의 상대적 속도 차이를 함께 고려한 값을 바탕으로 하여 기존 DTN 라우팅 프로토콜의 효율성을 향상시킬 수 있는 프로토콜을 제안하였다.
본 기법에서는 L값의 분배 시 각 노드의 목적지 정보를 참고하여 L값을 분배한다. 즉 임의의 두 노드가 만났을 경우 그림 3과 같이 서로의 목적지 정보를 비교하여 목적지 사이의 거리가 상대적으로 먼 노드에게 많은 L값을 할당한다.
본 기법에서는 L값의 분배 시 각 노드의 이동 방향을 참고하여, 서로 다른 방향으로 가는 노드에게 보다 많은 L값을 나눠주도록 한다. 이동 중인 임의의 노드가 다른 노드를 만났을 경우의 다음과 같이 동작한다.
진행하였다. 실험에서는 크게 3가지 측정 결과를 비교하였다. 첫 번째는 소스에서 전송된 전체 메시지의 몇 %가 목적지까지 도달하였는지를 알아보는 전송확률이고 두 번째는 이렇게 전송된 메시지가 평균적으로 도착하는 데까지 걸리는 지연 시간이다.
하이브리드 기법의 성능을 Spray & Wait과 비교한 결과이다. 이 실험에서는 100개의 이동 노드와 10개의 정지된 노드가 존재하도록 하고 각 노드의 이동 속도는 0〜L8m/s 사이에서 랜덤하게 결정되도록 하였다. 또한 이동성 모델은 랜덤 이동성 모델을 사용하였다.
L값의 분배는 표 1에서 보는 바와 같다. 즉 방향이 비슷하고 목적지 사이의 거리가 가까운 노드에게는 L값을 나눠주지 않고 방향이 비슷하고 목적지 사이의 거리가 멀거나 반대로 방향은 다르지만 목적지 사이의 거리가 가까운 경우에는 어느 정도의 L 값을 나눠주며 방향도 다르고 목적지 사이의 거리도 먼 경우에 L 값을 가장 많이 나눠주도록 하였다. 또한 평균적인 속도에 비해 빠른 속도를 가진 노드가 보다 상대적으로 네트워크 전체에 메시지를 고르게 전달할 확률이높으므로 속도가 빠른 노드에 가중치를 주었다.
향상을 위하여 우리는 위의 두 가지 기법을 결합한 기법을 제시하였다. L값의 분배는 표 1에서 보는 바와 같다.

이론/모형

이 실험에서는 100개의 이동 노드와 10개의 정지된 노드가 존재하도록 하고 각 노드의 이동 속도는 0〜L8m/s 사이에서 랜덤하게 결정되도록 하였다. 또한 이동성 모델은 랜덤 이동성 모델을 사용하였다. 실험 결과에서 y축은 전송확률과 오버헤드 비율을 모두 비교할 수 있도록 메시지 1000개의 오버헤드가 발생할 때 전송 성공된 메시지의 수를 비교한 것이다.
본 실험은 핀란드 헬싱키 대학에서 개발한 DTN 전용 시뮬레이터인 The Opportunistic Network Environ ment Simulator (The ONE)올 사용하여 진행하였다. 실험에서는 크게 3가지 측정 결과를 비교하였다.

성능/효과

것이다. Spray & Wait 기법파 큰 차이가 나지는 않지만 전체적으로 우리의 전송확률은 Spray & Wait보다 높고, D싢ay는 작으면서 오버헤드 비율은 크게 차이가 나지 않는 경향을 띄었다. 이렇게 큰 차이가 나지 않는 이유는 다음의 실험 결과를 통해 그 원인을 유주할 수 있다.
이러한 기존의 기법들이 대부분 노드의 랜덤한 이동성을 가정하고 있지만 실제로 대부분의 이동은 그 목적을 가지고 있으므로 어느 정도의 방향성과 목적지 정보를 가지고 있다. 따라서 각각의 노드가 GPS나 Navigator 시스템을 가지고 있어서 이러한 정보를 얻을 수 있다면 얻어진 정보를 기반으로 메시지의 전달 성공률, 지연 시간, 네트워크 상에서 전달되는 동일 메시지의 수(오버헤드)의 측면에서 향상된 결과를 보일 수 있다고 본다. 기존의 Spray & Wait 기법에서는 각각의 메시지가 전달될 수 있는 횟수가 정해져 있다.
효율적이지 않다. 따라서 본 고에서 제시하는 기법에서는 이러한 L값의 분배 시 각 노드의 이동성 정보를 고려하여 성능 향상을 도모한다.
즉 방향이 비슷하고 목적지 사이의 거리가 가까운 노드에게는 L값을 나눠주지 않고 방향이 비슷하고 목적지 사이의 거리가 멀거나 반대로 방향은 다르지만 목적지 사이의 거리가 가까운 경우에는 어느 정도의 L 값을 나눠주며 방향도 다르고 목적지 사이의 거리도 먼 경우에 L 값을 가장 많이 나눠주도록 하였다. 또한 평균적인 속도에 비해 빠른 속도를 가진 노드가 보다 상대적으로 네트워크 전체에 메시지를 고르게 전달할 확률이높으므로 속도가 빠른 노드에 가중치를 주었다. 임의의 두 노드가 만났을 경우의 동작은 다음과 같다.
실험 결과에서 y축은 전송확률과 오버헤드 비율을 모두 비교할 수 있도록 메시지 1000개의 오버헤드가 발생할 때 전송 성공된 메시지의 수를 비교한 것이다. 방향 정보 및 목적지 정보를 결합한 하이브리드 기법의 성능을 Spray & Wait과 비교한 결과 그림에서 볼 수 있는 바와 같이 Spray & Wait 기법에 비해 18% 많은 메시지가 전송에 성공한 것을 알 수 있다.
본 고에서는 이동하고 있는 노드의 방향과 목적지 정보를 사용하여 각각의 노드가 전송할 수 있는 메시지 개수를 적절히 조절함으로써 단순한 플러딩 기반의 Epidemic 라우팅이나, 특별히 정해진 경로로 이동을 반복하는 노드들이 존재할 때 유리한 Prophet에 비해 높은 전송 성공률과 작은 지연시간 그리고 작은 오버헤드 비율을 달성하였다. 뿐만 아니라 단순하게 전체 전달되는 메시지의 수를 조절하는 Spray & Wait에 비해서도 영리한 메시지 수 조절을 통해 전송확률 측면에서 좋은 결과를 보여주었다.
달성하였다. 뿐만 아니라 단순하게 전체 전달되는 메시지의 수를 조절하는 Spray & Wait에 비해서도 영리한 메시지 수 조절을 통해 전송확률 측면에서 좋은 결과를 보여주었다. 하지만 전체적으로 그 결과의 차이가 처음 예상했던 것보다 크지 않았는데, 이는 실험 시각 이동 노드들의 움직임이 시간이 흐를수록 랜덤화 되면서 단순한 플러딩 기반의 기법에 유리해지기 때문으로 판단된다.

후속연구

하지만 실제로 DTN이 사용될 수 있는 상황을 고려할 때 이동 노드들은 실제로 그렇게 랜덤하게 움직이지는 않을 것으로 예측된다. 따라서 앞으로 실제 DTN이 사용될 수 있는 상황을 보다 구체적으로 모델링하여 이에 적합한 이동성 정보에 기반한 알고리즘을 고안한다면 단순히 랜덤한 이동성을 가정한 기존의 기법들보다 더 좋은 성능을 달성할 수 있을 것으로 생각된다.

참고문헌 (13)

Delay tolerant networking research group http://www.dtnrg.org
S. Burleigh, A. Hooke, L. Torgerson, K. Fall. V. Cerf. B. Durst, and K. Scott. Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine. 41:128-136. 2003

상세보기
Luciana Pelusi. Andrea Passarella. and Marco Conti. Opportunistic Networking: data forwarding in disconnected mobile ad hoc networks. IEEE Communications Magazine issue on "Ad hoc and Sensor Networks," Vol.44. No.11. November 2006

상세보기
D. B. Johnson. D. A. Maltz. and J. Broch. Ad hoc networking. chapter 5 - DSR: the dynamic source routing protocol for multihop wireless ad hoc networks. Addison-Wesley. 2001
C. E. Perkins. E. M. Belding-Royer, and S. R. Das. Ad-hoc on-demand distance vector routing. IETF MANET DRAFT. 2002
C. Intanagonwisat. R. Govindan. and D. Estrin. Directed Diffusion: A Scalable and Robust Communication. In Proceedings of ACM MobileCom'00, August 2000
A. Vahdat and D. Becker. Epidemic Routing for Partially-connected Ad hoc Networks. Technical Report CS-2000-06, Duke University. July 2000
Sushant Jain, Kevin Fall, Rabin Patra. Routing in a Delay Tolerant Network. SIGCOMM 2004
Evan P. C. Jones, Lily Li, Paul A. S. Ward. Practical Routing in Delay-Tolerant Networks. WDTN 2005
Thrasyvoulos Spyropoulos, Konstantinos Psounis, Cauligi S. Raghavendra. Spray and wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks. SIGCOMM 2005
Tara Small et al. Probabilistic Routing in Intermittently Connected Networks. SIGCOMM'05 Workshops, August 2005
N. Sadagopan, F. Bai, B. Krishnamachari, and A. Helmy. Paths: analysis of path duration statistics and their impact on reactive manet routing protocols. In Proc. of MobiHoc'03, pages 245-256, June 2003
Jing Zhao, Guohong Cao. VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks. In Proceedings of INFOCOM'2006

저자의 다른 논문 :

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

연합인증