5. Research methodology used

Report
Mobility Adhoc Routing
Protocol
순천향대학교 정보보호연구실
김수현
[email protected]
2011. 4. 6.
Contents
1. Introduction
2. VANET system architecture
3. Application of VANET
4. Adhoc routing protocol
5. Research methodology used
6. Conclusion
모바일 임베디드 시스템
2
1. Introduction
 VANET(Vehicular Ad-hoc Network)이란?
 차량과 차량 사이 또는 차량과 RSU(Road Side Unit) 사이의 통신
을 위한 네트워크
 교통사고 발생, 갑작스런 기상 변화, 노면 결빙 상태 등의 정보
전달
 차량 내 단말기, 노트북, PDA 등 단말기들을 사용하여 이동 중에
도 멀티미디어 서비스 제공
 분류
 IVN (In-Vehicle Network) : 차량 멀티미디어 서비스 및 편의 서
비스 지원
 V2V (Vehicle-to-Vehicle) : 차량 추돌 경고, 차량간 그룹 통신
 V2I (Vehicle-to-Infrastructure) : 교통 및 안전 정보
모바일 임베디드 시스템
3
1. Introduction
 MANET과 VANET의 비교
구분
MANET
VANET
이동성
중/저속(보행속도)
고속(최대 200Km/h)
네트워크
토폴로지 변화
느림
빠름
노드의 밀도
낮고 변화가 느림
높고 변화가 빠름
메시지의 전송과
내용에 대한
신뢰성 요구도
중간
(어플리케이션에 의존)
매우 높음
(주로 안전과
관련된 메시지)
노드의 위치 획득 방법
라디오 신호
강도(RSSI) 및
초음파를 이용한
삼각측량기법
GPS
임의 위치로 이동
(random)
도로를 따라 정해진
이동경로를 가짐
(이동 방향 및 속도가
서로 연관되어지며, 예
측 가능함)
노드의 이동 패턴
(속도 및 방향)
모바일 임베디드 시스템
4
1. Introduction
 VANET 시스템 모델
모바일 임베디드 시스템
5
2. VANET system architecture
모바일 임베디드 시스템
6
3. Application of VANET
 Safety application
 Safety-critical
• 차량 운전자의 직접적인 위험 상황에 사용
• V2V, V2I 통신
모바일 임베디드 시스템
7
3. Application of VANET
 Safety-related
• 위험 경고 (커브 속도 경고) 등 다양한 서비스 제공
• V2V, V2I 통신
모바일 임베디드 시스템
8
3. Application of VANET
 Non-safety applications
 교통 정보 제공 및 편안한 운전 환경 제공
 Safety applications에 비해 낮은 우선순위 모드에서 통신
시스템의 채널에 접속
 Traffic optimization
• 교통 정보와 권장사항, 향상된 경로 안내 등을 제공
 Infotainment
• 인터넷 접속과 미디어 다운로드, 인스턴스 메시지 등을 제공
 Payment services
• 톨게이트 전자 지불, 주차관리 등의 서비스를 제공
 Roadside service finder
• 근처의 주유소, 음식점 검색
모바일 임베디드 시스템
9
4. Adhoc routing protocol
 라우팅 기법의 분류
 선행적(proactive) vs. 반응적(reactive) 라우팅
• 경로 설정 시점에 따른 분류
• 선행적 라우팅: 노드들은 주기적으로 라우팅 갱신 메시지를
보내며, 노드들은 이들을 이용하여 사전에 라우팅 테이블을
구축하고, 메시지 전송이 필요하면 이 테이블에 의존하여 전
송함
• 반응적 라우팅: 노드가 다른 노드와 통신이 필요한 시점에서
경로를 설정함
 위치기반
• 목적노드의 물리적 위치 정보를 이용하여 메시지를 전송함
• 소스노드는 목적노드의 물리적 위치 정보를 먼저 파악해야
함
모바일 임베디드 시스템
10
4. Adhoc routing protocol
모바일 임베디드 시스템
11
4. Adhoc routing protocol
Adhoc Routing Protocol
Flat Routing
Proactive
(Table driven)
FSR FSLS OLSR TBRPF
Hierarchical routing
Geographic position
Assisted routing
Reactive
(On demand)
AODV
DSR
HSR CGSR
ZRP LANMAR
모바일 임베디드 시스템
GeoCast LAR DREAM GPSR
12
4. Adhoc routing protocol
 Ad hoc On-Demand Distance Vector(AODV) Routing Protocol
 반응적 라우팅 프로토콜
 On Demand Routing 프로토콜로 데이터를 전달하지 않는 경우에는 사
용되지 않으므로 라우팅에 의한 오버헤드가 작아서 가벼움
 기본개념
• 소스 노드는 경로 탐색을 위해 RREQ(Route Request)를 이웃 노드에게
Broadcast하고 이웃 노드들은 다시 그 이웃 노드들에게 RREQ 메세지를
Broadcast하여 목적지까지 경로를 탐색 (플러딩)
• 목적노드까지의 최신 경로를 알고 있는 노드나 목적노드가 RREQ 메시지를
받으면 RREP(Route Response)를 회신하여 경로를 형성함 (유니캐스팅)
• 만약 중간 노드가 최종 목적지까지 경로를 이미 알고 있는 경우에 최종 목적
지 대신에 RREP를 보내기도 함
• 활성환된 경로가 끊기면 RERR 메시지를 통해 그 사실을 다른 노드들에게 알
림
모바일 임베디드 시스템
13
4. Adhoc routing protocol
 Ad hoc On-Demand Distance Vector(AODV) Routing Protocol
모바일 임베디드 시스템
14
4. Adhoc routing protocol
 Dynamic Source Routing(DSR)
 반응적 라우팅 프로토콜
 기본개념
• 애드혹망에서 목적노드까지의 경로를 모르면 RREQ 메시지를 통해 경로를
요청함
– RREQ가 전달되면서 경로를 축적함
– 중간노드들은 경로 정보를 라우팅 테이블에 캐시할 수 있음
• 목적노드까지의 최신 경로를 알고 있는 노드나 목적노드가 RREQ 목적노드
까지의 최신 경로를 알고 있는 노드나 목적노드가 RREQ 메시지를 받으면
RREP를 통해 경로를 알려줌
– AODV와 비교하여 소스 라우팅을 함 (소스가 전체 경로를 알고 있음)
• 알고 있는 경로를 통해 메시지 전달 중에 경로 오류가 발견되면 알고 있는
경로를 통해 메시지 전달 중에 경로 오류가 발견되면 출발노드에게 RERR를
전달함
모바일 임베디드 시스템
15
4. Adhoc routing protocol
 Optimized Link State Routing Protocol (OLSR)
 선행적 링크상태 기반 라우팅 프로토콜
 노드들은 자신의 이웃 정보를 전체 네트워크에 전달
• 플러딩 방식의 통신이 필요함
• 효과적인 플러딩을 위해 MPR(MultiPoint Relay) 기법을 사용
– MPR은 노드가 지정하는 중계 이웃으로 이들만 노드의 메시지를 중계
• MPR의 선정과 이웃 정보를 얻기 위해 각 노드는 자신의 이웃 정보
를 포함한 Hello 메시지를 주기적으로 방송함
– Hello 메시지에 포함되는 내용: 소스ID, 이웃 노드 목록, MPR 목록
– Hello 메시지가 새 이웃으로부터 왔을 경우에는 이웃 테이블을 갱신함
모바일 임베디드 시스템
16
4. Adhoc routing protocol
 MPR을 이용한 플러딩
모바일 임베디드 시스템
17
4. Adhoc routing protocol
 OLSR
• 자신의 이웃 정보를 알리기 위해 TC(Topology Control) 메시
지를MPR을 이용하여 전체 네트워크에 전달함
• 모든 노드가 이웃 정보를 전체 네트워크에 방송하면 효율적
이지 못하므로 MPR로 선정되는 노드들만 어떤 노드가 자신
을 MPR로 선정하였는지 전달함
모바일 임베디드 시스템
18
5. Research methodology used
 Simulation Tools Used
 Traffic simulator
 Network Simulator
 MObility model generator for VEhicular networks(MOVE)
 MOVE는 자바 기반의 응용 프로그램으로 SUMO 기반으로 작동
 MAP Editor
 Vehicle Movement Editor
 Simulation of Urban Mobility(SUMO)
 오픈소스로 독일 항공 우주 센터에서 교통 시스템의 연구소 직원에 의
해 개발
 많은 도시와 세계 도시의 지도 외에 사용자 정의로 도로 토폴로지를 구
축 가능
모바일 임베디드 시스템
19
5. Research methodology used
 Network Simulator(NS-2)
 콜롬비아 대학에 의해 개발된 시뮬레이션 테스트베드인 NEST를
기반으로 UC Berkeley에서는 1988년 REAL이라는 네트워크 시뮬
레이터를 개발
 1989년에 LBNL(Lawrence Berkeley National Laboratory)의 네트
워크 연구그룹은 이 REAL을 기반으로 연구를 시작하여 NS1(network simulator)라고 부르는 시뮬레이션 도구를 개발
 NS는 TCP, 라우팅 프로토콜, 멀티캐스트 프로토콜, RTP(Real
Time Protocol), SRM(Scalable Reliable Multicast) 등 다양한 인
터넷 프로토콜에 대한 시뮬레이션을 수행하기에 적절한 여러 환
경을 제공하고 있어 현재 널리 사용되고 있는 네트워크 시뮬레
이션 도구
모바일 임베디드 시스템
20
5. Research methodology used
모바일 임베디드 시스템
21
5. Research methodology used
 Simulation Scenario
 Urban Scenario
• Urban scenario and movement of Vehicles in Urban Scenario
모바일 임베디드 시스템
22
5. Research methodology used
 Simulation Scenario
 Highway Scenario
• Highway scenario and movement of Vehicles in Highway
Scenario
모바일 임베디드 시스템
23
5. Research methodology used
 Simulation Metrics used
 Packet Delivery Ratio (PDR)
 Average End to End Delay (Avg. E2E Delay)
 Simulation Result




VLD: Very Low Density
LD: Low Density
MD: Medium Density
HD: High Density
 Density(밀집도) = 차량 수(N) / 킬로미터 당 차량 단위(L)
모바일 임베디드 시스템
24
5. Research methodology used
 Urban Scenario
 Density and Connection pattern used
Urban
Scenario
Density
No of Nodes
Connections
VLD
20
8
LD
102
40
MD
254
100
HD
610
150
모바일 임베디드 시스템
25
5. Research methodology used
 Urban Scenario
 PDR vs. Node Density in Urban Scenario
모바일 임베디드 시스템
26
5. Research methodology used
 Urban Scenario
 Average End to End Delay (in ms) vs. Node Density in
Urban Scenario
모바일 임베디드 시스템
27
5. Research methodology used
 Highway Scenario
 Density and Connection pattern used
Highway
Scenario
Density
No of Nodes
Connections
VLD
150
60
LD
340
120
MD
767
160
HD
1216
220
모바일 임베디드 시스템
28
5. Research methodology used
 Highway Scenario
 PDR vs. Node Density in Urban Scenario
모바일 임베디드 시스템
29
5. Research methodology used
 Highway Scenario
 Average End to End Delay (in ms) vs. Node Density in
Urban Scenario
모바일 임베디드 시스템
30
5. Research methodology used
 Urban Scenario
 Highway Scenario
모바일 임베디드 시스템
31
6. Conclusion
Urban
Highway
AODV
OLSR
DSR
PDR
97%
65%
42.5%
E2E Delay(ms)
110
65
47.5
PDR
95%
72.5%
30%
E2E Delay(ms)
87.5
38.8
41.5
모바일 임베디드 시스템
32
Click to edit company slogan .
모바일 임베디드 시스템
33
참고문헌
 Pranav Kumar Singh, Kapang Lego, Dr. Themrichon Tuithung, “Simulation based
Analysis of Adhoc Routing Protocol in Urban and Highway Scenario of VANET”,
International Journal of Computer Applications, Volume 12– No.10, January 2011.
 C. Perkins, E. Belding-Royer, S. Das, “Ad hoc On-demand Distance Vector (AODV)
Routing”, IETF RFC 3561, Jul. 2003.
 D. Johnson, Y. Hu, D. Maltz, “The Dynamic Source Routing Protocol (DSR) for
Mobile Ad Hoc Networks for IPv4”, IETF RFC4728 F b 2007.
 T. Clausen, P. Jacquet, “Optimized Link State Routing Protocol (OLSR),” IETF RFC
3626, Oct. 2003.
모바일 임베디드 시스템
34

similar documents