[논문]AODV 라우팅 프로토콜에서 재전송률을 낮추기 위한 ERS 알고리즘의 노드순회시간 계산방법

선창윤; 강승호; 임형석

doi:10.3745/kipstc.2006.13c.4.447

초록
AI-Helper

에드 혹 네트워크에 사용되는 라우팅 프로토콜인 AODV(Ad hoc On-demand Distance Vector)는 ERS(Expanding Ring Search) 알고리즘으로 경로설정 과정에서의 라우팅 패킷 재전송을 제어한다. 그러나 기존의 ERS는 라우팅 패킷 재전송의 기준이 되는 NTT(Node Traversal Time) 계산에 이동성이 높은 네트워크 상황을 적절하게 반영하지 못한다. 본 논문은 NTT 계산에 RREP(Route Reply) 패킷을 사용하고 출발지 노드와의 인접도에 따라 각 노드의 NTT에 가중치를 달리 적용함으로써 라우팅 패킷의 재전송률을 낮추는 방법을 제안하고 ns2를 이용하여 기존의 ERS와 성능을 비교한다.

Abstract ▼ AI-Helper

An ad-hoc network routing protocol, AODV(Ad-hoc On-demand Distance Vector) initially uses ERS(Expanding Ring Search) algorithm to control the RREQ(Route Request) retransmission in the route discovery process. Because ERS uses the fixed NTT(Node Travesal Time), it does not reflect accurately ad-hoc n...

An ad-hoc network routing protocol, AODV(Ad-hoc On-demand Distance Vector) initially uses ERS(Expanding Ring Search) algorithm to control the RREQ(Route Request) retransmission in the route discovery process. Because ERS uses the fixed NTT(Node Travesal Time), it does not reflect accurately ad-hoc network environment. In this paper, we propose an improved ERS algorithm which lowers the retransmission rate. It uses RREP(Route Reply) and gives different weights in NTT of each node in accordance with the adjacency to an originating node. To show the effectiveness of the proposed algorithm, we perform a simulation using ns2. The simulation results showed that the proposed algorithm has better performance than existing algorithms.

주제어

AI 본문요약
AI-Helper

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

문제 정의

ERS 알고리즘은 처음 유선 멀티 캐스팅에서 사용되었다. ERS의 중요한 목적은 RREQ가 처음부터 넓은 네트워크에 플러딩 되는 것을 방지하고, 점진적으로 범위를 넓게 확장 하여 목적지 노드를 찾는데 발생하는 불필요한 RREQ (Route Request)를 제한하고자 함이다.
본 논문에서는 AODV 라우팅 프로토콜의 RREP를 이용 해 목적지노드에서 소스노드까지의 시간차를 구하고 이에 소스노드와의 인접도를 고려해 가중치를 달리 부여하여 타 임아웃에 반영하는 개선된 ERS알고리즘을 제시하였다. 네 트워크의 현재 상황을 적극 반영하여 경로설정 과정상의 RREQ의 재전송률을 낮추어 네트워크 대역폭의 낭비를 줄 일 수 있다.
본 논문에서는 노드들이 불규칙적으로 이동하는 무선 네 트워크에서 목적지 노드로부터 전송되는 RREP(Route Reply) 의 소요시간을 중간노드들과 소스노드까지 각각 측정하고 소스노드와의 인접도에 따라 각 노드의 NTT에 가중치를 달리 부여하여 이를 타임아웃에 반영하는 알고리즘을 제안 한다. 이렇게 함으로써 라우팅 제어 패킷을 감소시켜 전체 네트워크 성능을 높인다.

제안 방법

본 논문에서 제안하는 방법들은 AODV나 KERS와는 달리 (그림 4)에서 보듯이 목적지노드(D)에서 RREP를 출발지 노드(S)로 전송할 때 홉 간의 시간차를 이용해 NTT를 계 산한다. 우선 D는 RREP에 현재시각을 기록하여 다음 노드 에 전송한다.
본 논문에서는 AODV의 ERS와 KERS, 제안한 알고리즘을 각각 실험하여 전체 패킷 발생량, 에러 발생량 등을 비교 분석하였다. 실험은 버클리(Berkeley) 대학의 Network simulator 2.
본 실험에서는 노드 50개와 100개를 가지고 AODV의 ERS와 KERS 그리고 제안한 알고리즘들을 속도를 증가시 켜 가며 전체 패킷 발생량과 에러 발생량을 측정하였다. 실험 결과는 속도를 lm/s에서 20m/s까지 증가 시키면서 각 속도에 대해 20번씩 실행 시켜 평균치를 구한 것이다.
본 장에서는 RREQ대신 RREP를 사용하고 각 노드로 이 동할 때 마다 시간을 측정해서 출발지 노드와의 인접성에 따라 가중치를 달리 부여하는 방법들을 제시한다.
따라서 라우팅 패킷인 RREQ의 재전송률을 낮추는 방법은 AODV 라우팅 프로토콜에게는 중요한 의미를 갖는다. 실험은 AODV의 ERS와 KERS 그리고 제안한 방법들을 전체 패킷 발생량과 에러 발생량에 대해 실행하였다. 실험 결과는 AODV의 ERS나 KERS 보다 제안한 알고리즘들이 패킷 발생량이나 에러 발생량 측면에서 성능향상을 보였다.

대상 데이터

일 단 소스노드와 목적지노드가 연결되어지면 ftp로 IMbytes를 전송하고 연결을 해제한다. 실험에 사용된 MAC layer는 ns-2.26에 포함되어 있는 IEEE 802.11을 사용하였다.
26[16]를 사용하였다. 실험환경은 무선 애드 혹 망을 기본으로 하고 최대 20m/s의 속도의 이동성을 가지는 50개의 노드들이 최대 3000m X 3000m의 지역 내에서 이 동하는 경우와 100개의 노드들이 최대 3000m X 3000m의 지역 내에서 이동하는 경우로 하였다. 각 노드의 속도는 lm/s에서 20m/s까지 변화를 주었고 소스노드와 목적지노드 는 임의로 선택되어 100개의 연결이 만들어 진다.

데이터처리

본 실험에서는 노드 50개와 100개를 가지고 AODV의 ERS와 KERS 그리고 제안한 알고리즘들을 속도를 증가시 켜 가며 전체 패킷 발생량과 에러 발생량을 측정하였다. 실험 결과는 속도를 lm/s에서 20m/s까지 증가 시키면서 각 속도에 대해 20번씩 실행 시켜 평균치를 구한 것이다.

이론/모형

목적지노드(。나 목적지까지의 경로를 알 고 있는 중간 노드는 RREP에 RREQ의 출발시간을 복사하여 단일 경로를 따라 소스노드에 전송한다. RREP를 수신한 소스노드는 식(1)과 같이 소스노드의 현재시간과 RREP에서 얻은 RREQ를 전송할 당시의 시간차를 구하고 이를 홉 수 로 나눈 평균값을 ERS 알고리즘의 NTT로 사용한다.
본 논문에서는 AODV의 ERS와 KERS, 제안한 알고리즘을 각각 실험하여 전체 패킷 발생량, 에러 발생량 등을 비교 분석하였다. 실험은 버클리(Berkeley) 대학의 Network simulator 2.26[16]를 사용하였다. 실험환경은 무선 애드 혹 망을 기본으로 하고 최대 20m/s의 속도의 이동성을 가지는 50개의 노드들이 최대 3000m X 3000m의 지역 내에서 이 동하는 경우와 100개의 노드들이 최대 3000m X 3000m의 지역 내에서 이동하는 경우로 하였다.
그런데 목적지노드가 멀리 있거나 없는 경우엔 목적지 노드를 찾기 위한 라우팅 패킷 이 급격하게 증가하고 이로 인해 네트워크의 성능이 크게 저하된다. 이러한 문제점을 해결하기 위해 불필요한 RREQ (Route Request)를 제어하는 ERS 알고리즘을 사용한다. 하지만 유선 멀티 캐스팅에서 유래한 ERS 알고리즘은 애드 혹 네트워크 상황에서 수시로 변하는 NTT(Node Traversal Time)를 적절히 고려하지 못하는 문제가 있다.

성능/효과

(그림 5, 6)은 전체 패킷 발생량을 (그림 7, 8)은 에러 발 생량을 나타낸 것이다. (그림 5, 7)에서 알 수 있듯이 노드 가 50개일 때의 전체 패킷 발생량이나 에러 발생량을 보면 제안한 알고리즘들이 AODV의 ERS나 KERS 보다 약 5% 정도의 개선이 있는 것으로 나타났다. (그림 6, 8)은 노드가 100개일 때의 패킷 발생량과 에러 발생량을 나타낸 그림인 데 노드 50개일 때와 비슷한 수준의 성능 향상을 보였다.
실험은 AODV의 ERS와 KERS 그리고 제안한 방법들을 전체 패킷 발생량과 에러 발생량에 대해 실행하였다. 실험 결과는 AODV의 ERS나 KERS 보다 제안한 알고리즘들이 패킷 발생량이나 에러 발생량 측면에서 성능향상을 보였다.

후속연구

향후 연구로는 지수적 또는 선형적 가중치 부여 방법이 외에 피보나치 순열 둥 여러가지 가중치 부여 방법을 고안 하여 각각의 방법들이 어떤 네트워크 환경에 보다 나은 성능을 보이는 지를 측정하는 것이다. 또한 이러한 가중치 부 여 방법과 RREP의 선택이 각각 어느 정도 성능향상에 기 여하는지도 분석이 필요할 것으로 생각된다.
향후 연구로는 지수적 또는 선형적 가중치 부여 방법이 외에 피보나치 순열 둥 여러가지 가중치 부여 방법을 고안 하여 각각의 방법들이 어떤 네트워크 환경에 보다 나은 성능을 보이는 지를 측정하는 것이다. 또한 이러한 가중치 부 여 방법과 RREP의 선택이 각각 어느 정도 성능향상에 기 여하는지도 분석이 필요할 것으로 생각된다.

참고문헌 (16)

E. M. Royer and C. K. Toh, 'A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,' IEEE Personal Communications, pp.46-55, Apr., 1998

상세보기
C. K. Toh, 'Ad Hoc Mobile Wireless Networks Protocols and System,' Prentice Hall PTR, pp.13-25, 2002
C. E. Perkins and P. Bhagwat, 'Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers,' Computer Communication, pp.234-244, Oct., 1994
S. Murthy and J. J. Garcia-Luna-Aceves, 'An Efficient Routing Protocol for Wireless Networks,' ACM Mobile Networks and Applications Journal, Special issue on Routing in Mobile Communication Networks, pp.183-197, Oct. 1996

상세보기
D. Johnson and D. Maltz, 'The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,' IETF MANET Working Group, Internet Draft, http//www-2.cs.cmu.edu/~dmaltz/intemet-drafts/draft-ietf-manet-dsr-09.txt, 15. Apr., 2003
C. E. Perkins and E. M. Royer, 'Ad-hoc On-demand Distance Vector Routing,' Mobile Computing Systems and Applications, Proceedings WMCSA '99. Second IEEE Workshop on, pp.90-100, Feb., 1999
RFC 3561 - Ad hoc On-demand Distance Vector(AODV) Routing, http://www.faqs.org/rfcs/rfc3561.html
C. K. Toh, 'Associativity-Based Routing For Ad-Hoc Mobile Networks,' University of Cambridge Computer Laboratory Cambridge CB2 3QG, United Kingdom, Prentice Hall PTR, pp.79-95, Nov., 1999
V. D. Park and M. S. Corson, 'A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,' IEEE INFOCOM '97 Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE, Vo1.3, pp.1405-1413, Apr., 1997
Zone Routing Protocol (ZRP), http://www.tct.hut.fi/opetus/s38030/k02/ Papers/08-Nicklas.pdf
김종천, 김영용, 'Ad Hoc 통신망 프로토콜 개발동향', Telecommunication Review 제12권3호, pp.298-311, 2002
김현창, 'Ad Hoc 네트워크에서 Timestamp를 이용한 AODV 프로토콜의 최적화', 연세대학교 대학원 전기전자공학과, http://nasla.yonsei.ac.kr/publications/hpmn_papaers/ms/2002/AdHoc 네트워크에서 Timestamp를 이용한 AODV프로토콜의최적화.pdf, 2002
K. Carlberg and J. Crowcroft, 'Building Shared Trees Using a One-to-Many Joining Mechanism,' ACM Computer Communication Review, Vol.27, No.1, pp.5-11, 1997

상세보기
RFC 793-TCP(Transmission Control Protocol), http://www.faqs.org/rfcs/rfc793.html
S. Das, C. E. Perkins, and E. M. Royer, 'Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks,' In Proc. of INFOCOM-2000, pp.3-12, Mar., 2000
The networks simulator - ns2, http://www.isi.edu/nsnam/ns

이 논문을 인용한 문헌

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

AODV 라우팅 프로토콜에서 재전송률을 낮추기 위한 ERS 알고리즘의 노드순회시간 계산방법
Computing Methods of Node Traversal Time of ERS Algorithm to Reduce the Retransmission Rate in AODV Routing Protocol 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

AODV 라우팅 프로토콜에서 재전송률을 낮추기 위한 ERS 알고리즘의 노드순회시간 계산방법 Computing Methods of Node Traversal Time of ERS Algorithm to Reduce the Retransmission Rate in AODV Routing Protocol 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

임형석 (24)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

AODV 라우팅 프로토콜에서 재전송률을 낮추기 위한 ERS 알고리즘의 노드순회시간 계산방법
Computing Methods of Node Traversal Time of ERS Algorithm to Reduce the Retransmission Rate in AODV Routing Protocol 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper