ĐỒ ÁN TỐT NGHIỆP

GIAO THỨC ĐỊNH TUYẾN TRONG
VANETs


DANH MỤC CÁC TỪ VIẾT TẮT
Adhoc

Wireless ad-hoc network

AODV

Ad Hoc On – Demand Vector Routing

AU

Application unit

BSS

Basic service set

CCH

Control channel

DSR

Dynamic Source Routing

DTN

Delay Tolerant Network

EDCA

Enhanced Distributed Channel Access

FSR

Free Spirit Rap

GPRS

General Packet Radio Service

GPS

Global Positioning System

GPSR

Greedy Perimeter Stateless Routing

GSM

Global System for Mobile Communications

GW


Gateway

HSDPA

High-Speed Downlink Packet Access

Non-DTN

Non-Delay Tolerant Network

OBU

On board unit

OFDM

Orthogonal frequency-division multiplexing

RSU

Road Side Unit

SCH

Service channel

SME

Station management entity


Sumo

Simulation of Urban Mobility

TA

Timing Advertisement

UMTS

Universal Mobile Telecommunications Service

V2B

Vehicle to base station

V2I

Vehicle to infrastructure


V2V

Vehicle to vehicle

VANETs

Vehicular Ad Hoc Network

WAVE


Wireless Access in Vehicular Environments

WiMax

Worldwide Interoperability for Microwave Access

WSA

WAVE Service Advertisement

WSM

WAVE Short Message

WSMP

WAVE Short Message Protocols


ĐỒ ÁN TỐT NGHIỆP
Trang 1/60

CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
1.1 Giới thiệu đề tài:
1.1.1 Thực trạng:
Trong 6 tháng đầu năm 2018 có đến gần 9.000 vụ tai nạn giao thông là một con
số không hề nhỏ. Trong đó có đến một nửa là do ý thức của người tham gia giao
thông và các sự cố cơ sở vật chất giao thông gây ra. Các vụ tai nạn giao thông làm
ảnh hưởng nghiêm trọng đến kinh tế và sự mất mát cho gia đình người bị tai nạn,

đồng thời cũng là gánh nặng cho nền kinh tế nước nhà.
Ở các đô thị lớn của nước ta đặc biệt TP. Hồ Chí Minh và Hà Nội tình hình ùn
tắc giao thông thường xuyên xảy ra hằng ngày ở các tuyến đường do lưu lượng xe
tăng quá nhanh cơ sở vật chất giao thông không theo kịp, các tuyến đường thường
xuyên bị ngập úng do triều cường và các con đường thường xuyên được sửa chữa.
Người dân chủ yếu còn xem thường luật giao thông, ra đường thường xuyên
không tuân thủ luật giao thông nên đây cũng là một nguyên nhân quan trọng làm ùn
tắc giao thông và gây ra các tai nạn giao thông đây cũng là một hình ảnh xấu làm
ảnh hưởng đến bộ mặt của đất nước trong hình ảnh của các du khách nước ngoài.
1.1.2 Tình hình nghiên cứu
Trên thế giới hiện nay xuất hiện giải pháp về công nghệ trong lĩnh vực giao
thông để hạn chế các vấn đề giao thông nan giải hiện nay. Công nghệ này không chỉ
là hữu ích trên thế giới mà còn có thể ứng dụng ở nước ta hiện nay đó chính là
VANETs (mạng giao thông thông minh).
Do nước ta là nước đang phát triển cơ sở vật chất khoa học kĩ thuật còn kém, các
nghiên cứu khoa học về lĩnh vực này còn ít cần phải có những nghiên cứu thêm và
để đảm bảo tính chắc chắn trong việc triển khai dự án này. Để đất nước phát triển
giảm thiểu các vấn đề về giao thông hiện nay đề tài giao thức và định tuyến trong

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 2/60

VANETs là một nghiên cứu về cơ sở lý thuyết và mô phỏng góp phần giúp ích cho
sự nghiên cứu để hình thành một mạng VANETs áp dụng được vào thực tế.
1.2 Mục tiêu đề tài
Nghiên cứu và thực hiện mô phỏng đánh giá hai giao thức định tuyến AODV và
DSDV trong môi trường mạng VANETs từ đó đưa ra kết luận triển khai mạng trên

thực tế.
1.3 Nội dung nghiên cứu
Nghiên cứu các lý thuyết về VANETs:
• Tìm hiểu tổng quan về mạng VANETs: Đặc điểm, cấu trúc, ứng dụng và
cách thức giao tiếp dữ liệu trong mạng.
• Các giao thức định tuyến trong VANETs.
Thực hiện mô phỏng đánh giá:
• Tìm hiểu phần mềm mô phỏng NS3, cách thức mô phỏng mạng lưới
VANETs.
• Thực hiện mô phỏng và đánh giá 02 giao thức định tuyến AODV và
DSDV.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 3/60

CHƯƠNG 2. VANETs
2.1 Giới thiệu mạng VANETs
VANETs (Vehicular Ad Hoc Network) là một hệ thống mạng di động trong đó
các xe sẽ được trang bị các thiết bị thu phát, chúng tạo thành các node như trong
mạng ad-hoc vì vậy không cần dùng đến cơ sở hạ tầng mạng. Các node mạng có thể
liên lạc, chia sẻ và trao đổi thông tin cho nhau. Các xe có thể đi ra khỏi vùng phủ
sóng, thoát khỏi mạng ngược lại có những xe khác đi vào vùng phủ sóng và kết nối
với mạng tạo nên một hệ thống internet di động. Các thông tin được vận chuyển
trong mạng VANETs là lưu lượng xe, tình trạng kẹt xe, tai nạn giao thông, những
nguy hiểm có trên con đường và các dịch vụ đa phương tiện.
Mạng VANETs không chỉ liên lạc giữa các xe cộ ở gần nhau mà chúng còn liên
lạc giữa các xe với các trạm cố định RSU (Road Side Unit) ở trên đường [1,2].


Hình 2-1: Mô hình mạng VANETs[1]

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 4/60

2.2 Mục đích của mạng VANETs
Mục đích của mạng VANETs là đưa ra các thông tin cảnh báo an toàn cho khách
hàng và các dịch vụ tiện ích đi kèm. Các thiết bị đặt bên trong xe cung cấp kết nối
mạng kiểu Adhoc cho khách hàng. Ưu điểm của mạng này là chúng hoạt động
không cần cơ sở hạ tầng như các mạng khác. Mỗi thiết bị đầu cuối trong mạng
VANETs được xem như là một node có thể gửi, nhận hoặc làm trung gian để truyền
nhận dữ liệu cho các node khác thông qua mạng không dây. Nếu có các sự cố giữa
các phương tiện trên đường, các tín hiệu cảnh báo sẽ được chuyển đi trên mạng
VANETs đến các xe khác cùng với các dịch vụ khác để giải quyết sự cố. Ngoài ra
mạng VANETs có thể kết nối internet cho người dùng sử dụng các dịch vụ internet
như: đa phương tiện, hình ảnh, âm thanh, video. Ngoài ra còn có các dịch vụ khác
như là: trả phí giao thông, phí gửi xe và kiểm soát các phương tiện tham gia giao
thông [1].
2.3 Đặc điểm của mạng VANETs
Mạng VANETs có đặc điểm riêng, nó không yêu cầu cơ sở hạ tầng mạng như
các mạng vô tuyến khác như là: Trạm Base Station của mạng GSM, 3G, 4G và
không cần Access Point cho hệ thống Wifi hay Wimax. VANET có thể khắc phục
được nhược điểm của truyền dẫn vô tuyến về khoảng cách nhờ vào các node trung
gian. Nhưng nhược điểm của VANETs cũng chính là do không có cơ sở hạ tầng, sử
dụng biến đổi định tuyến qua nhiều tầng nên tính bảo mật không cao có khả năng bị
lấy cấp thông tin và thông tin có thể bị lỗi hoặc bị nghẽn. Việc truyền thông tin về

giao thông qua các xe là rất cần thiết, phản ánh đúng tình hình giao thông trên giao
lộ nhưng nếu có sai lệch thì gây thiệt hại rất lớn vì thông tin sẽ được truyền đi đến
toàn bộ hệ thống [1,3].

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 5/60

Hình 2-2: Mô hình ứng dụng hệ thống VANETs [1]

Ngoài ra mạng VANETs còn có các đặc điểm khác như là:
• Node mạng di chuyển với tốc độ cao: Do các node mạng nằm trên xe có thể
di chuyển với tốc độ cao vì vậy thời gian kết nối giữa chúng tương đối ít. Giả
sử hai xe đi ngược chiều nhau với vận tốc là 90km/h và phạm vi truyền dẫn
giữa hai node là 250m thì hai xe có 5s để liên lạc với nhau.
• Thường xuyên ngắt kết nối và kết nối mạng giữa các node: Khi hai xe đi xa
nhau vượt quá khoảng cách kết nối của thiết bị trên xe thì mạng mất kết nối
và phải kết nối với xe khác ở trong phạm vi hoạt động. Nếu ở khu có mật độ
xe thấp thì việc kết nối với điểm chuyển tiếp là giải pháp tối ưu.
• Dự đoán chuyển động của node: Để cho mạng hoạt động hiệu quả thì chúng
ta cần thuật toán giúp xác định và chuẩn đoán hướng chuyển động của xe để
xác định vị trí của node.
• Môi trường truyền thông tin: Nếu các node trên xe chuyển động trên đường
cao tốc một chiều thì rất dễ dự đoán, nếu các node di chuyển trên phố với
mật độ xe, sự cản trở của các toà nhà và cây cối thì có thể gây cản trở lớn cho
quá trình truyền dữ liệu.
• Hạn chế độ trễ: Do các vấn đề an toàn trên đường nên dữ liệu về tai nạn,
phanh xe… cần được truyền cho các node khác với tốc độ nhanh nhất. Vì


Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 6/60

vậy trong mạng VANETs cần khắc phục hạn chế này giúp an toàn cho người
tham gia giao thông.
• Tương tác với onboard cảm biến: Cảm biến onboard giúp cung cấp vị trí
node và tình trạng của xe để liên kết truyền dữ liệu hiệu quả va chính xác
nhất.
2.4 Cấu trúc hệ thống mạng VANETs

Hình 2-3: Mô hình ứng dụng hệ thống VANETs

Một mạng VANETs gồm có ba thành phần cơ bản: thiết bị trong xe, kết nối
Adhoc và cơ sở hạ tầng bên đường như hình 2-3.
Thiết bị trong xe: Trong xe gồm có một OBU và nhiều AU. Các AU là những
ứng dụng trên xe sử dụng khả năng truyền nhận dữ liệu từ OBU. OBU trang bị ít
nhất một thiết bị kết nối không dây tầm ngắn an toàn và có khả năng lựa chọn các
thiết bị liên lạc an toàn hay không an toàn. AU và OBU khác nhau về mặt chức
năng logic tuy nhiên có thể thiết kế chúng trên một đơn vị vật lý.
Adhoc: Mạng Adhoc được tạo nên từ các kết nối giữa các OBU trên các xe trong
phạm vi kết nối V2V (vehicle to vehicle) và kết nối giữa xe với thiết bị bên đường

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP

Trang 7/60

là RSU thông qua kết nối V2I (vehicle to infrastructure) để tạo thành một mạng
VANETs có thể chuyển tiếp thông tin giữa các node mà không cần thiết bị điều
khiển. Các OBU thực hiện kết nối không dây và chuyển tiếp dữ liệu cho nhau và sử
dụng phương pháp multi-hop để truyền dữ liệu đi xa tạo thành mạng Adhoc
Cơ sở hạ tầng: Cơ sở hạ tầng của mạng VANETs bao gồm các RSU và các điểm
truy cập không dây HS. RSU được kết nối internet thông qua sự quản lý của cơ
quan công quyền, các điểm nóng về giao thông hoặc ở các tuyến đường tư nhân
thường thiết lập thêm HS chúng ít kiểm soát hơn. Nếu trong trường hợp RSU và HS
đều không cung cấp internet thì OBU có thể truy cập các mạng vô tuyến công cộng
như: (GSM, GPRS, UMTS, HSDPA, WiMax, 4G) nếu chúng được tích hợp trong
OBU [1,6].
Các khối phần cứng cần có trong mạng VANETs:
• Application Units (AU): là một thiết bị trong xe có thể được thiết kế vật lý
chung hoặc riêng với OBU. Các AU cung cấp các dịch vụ an toàn cho người
dùng được cài đặt từ trước. AU kết nối với OBU để truyền và nhận dữ liệu
thực hiện các tác vụ trên xe.
• On-board Unit (OBU): Có chức năng truy cập vô tuyến, định tuyến, kiểm
soát tắc nghẽn mạng, chuyển tin nhắn tin cậy, bảo mật dữ liệu, hỗ trợ truy
cập internet và các chức năng khác. OBU chịu trách nhiệm kết nối với các
OBU khác trên các xe khác (V2V) và kết nối với các cơ sở hạ tầng bên
đường (V2I). OBU được trang bị ít nhất một thiết bị mạng để tạo thành một
mạng Adhoc.
• Road-side unit (RSU): là một thiết bị vật lý được đặt cố định trên đường
hoặc các vị trí công cộng như: trạm xăng, bãi đỗ xe nhà hàng. Một RSU
được trang bị ít nhất là một thiết bị mạng không dây tầm ngắn. RSU cũng có
thể trang bị thiết bị mạng khác để liên lạc với mạng cơ sở hạ tầng khác. Chức
năng chính của RSU là:
o


Mở rộng phạm vi của mạng Adhoc. Lấy thông tin từ RSU và truyền
cho RSU khác.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 8/60

Hình 2-4: RSU mở rộng phạm vi mạng

o Được cài đặt các ứng dụng an toàn, cảnh báo V2I như: cảnh báo về cơ
sở hạ tầng giao thông.
o Cung cấp dịch vụ internet cho OBU.

Hình 2-5: RSU cảnh báo về cơ sở hạ tầng giao thông

Hình 2-6: RSU cung cấp dịch vụ internet cho OBU

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 9/60

2.5 Ứng dụng hệ thống mạng VANETs
Hệ thống RSU bên đường có thể được xem là điểm truy cập, bộ định tuyến hay
là điểm trung gian có thể lưu trữ và cung cấp dữ liệu khi cần. Tất cả dữ liệu ở RSU
được lấy từ các xe có thể phục vụ các ứng dụng khác nhau. Các ứng dụng car to

car(V2V), car to Infrastructure(V2I), Car to Home và các ứng dụng dựa trên định
tuyến được chia thành các nhóm khác nhau là: Ứng dụng an toàn cứng, ứng dụng an
toàn mềm và ứng dụng di động truy cập internet.

Hình 2-7: Ứng dụng mạng VANETs

2.5.1 Ứng dụng an toàn cứng (hard)
Các ứng dụng an toàn cứng có nhiệm vụ làm tránh các sự cố sắp xảy ra hoặc
giảm thiểu tối đa thiệt hại với các sự cố không thể tránh được. Ứng dụng này đạt
chuẩn truyền thông nghiêm ngặt để hạn chế tối đa độ trễ nhằm mục đích cung cấp
cho người nhận thông tin chính xác với độ tin cậy cao nhất cho người nhận có đủ
thời gian thực hiện hành động cần thiết.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 10/60

2.5.2 Ứng dụng an toàn mềm (soft)
Ứng dụng an toàn mềm ít ưu tiên hơn ứng dụng an toàn cứng, thời gian truyền đi
với độ trễ cao hơn. Ứng dụng này cũng làm tăng sự an toàn cho người lái xe nhưng
không cần thiết người lái xe phải tiếp nhận và có hành động ngay lập tức. Các ứng
dụng cụ thể tiêu biểu là: cảnh báo thời tiết, đường xá, khu vực có công trình đang
xây dựng, ùn tắc giao thông… Từ đó người lái xe có thể lựa chọn các hành động là
đi thận trọng hay di chuyển qua các tuyến đường thay thế khác.

2.5.3 Ứng dụng di động, tiện ích và internet
Các ứng dụng di động này giúp cải thiện lưu lượng tham gia giao thông như:
điều hướng, chỉ dẫn đường, bản tin giao thông, hỗ trợ và điều phối giao thông. Các

ứng dụng tiện ích và truy cập internet giúp cho người tham gia giao thông giải trí
phục vụ công việc. Các dịch vụ này sẽ có độ trễ cao hơn các dịch vụ an toàn cứng
và mềm.
2.6 Chuẩn truy cập dữ liệu trong hệ thống mạng VANETs
Mạng VANETs được phân bố 75MHz trong phổ tần số 5,850-5,925GHz cho các
giao tiếp V2V và V2I. Tiêu chuẩn truyền dữ liệu V2V trong VANETs gọi là WAVE.
WAVE trong V2V gồm giao thức WSMP (WAVE Short Message Protocols) và gói
tin quản lý WSA (WAVE Service Advertisement) dựa trên nền tảng của hai chuẩn
là: 802.11p và IEEE 1609.
2.6.1 Chuẩn 802.11p trong mạng VANETs
802.11p được đưa ra vào năm 2010 phát triển dựa trên chuẩn 802.11a. 802.11p
giúp đảm bảo khả năng tương tác giữa các thiết bị có thể thay đổi môi trường giao
tiếp nhanh. Giúp giảm thời gian truyền dữ liệu và hạn chế độ trễ thiết lập BSS
(Basic service set) cho phép các thiết bị giao tiếp trực tiếp với nhau. Một bộ tham số
EDCA (Enhanced Distributed Channel Access) được tối ưu hoá và sử dụng cho các

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 11/60

tin nhắn ngắn. Tiêu chuẩn này còn có một khung quản lý mới là Timing
Advertisement (TA) sửa lại các khung hành động cụ thể của nhà cung cấp (VSA)
với bộ định danh (OID). 802.11p sử dụng công nghệ ghép kênh tần số trực giao
(OFDM) và băng thông kênh là 10MHz.
2.6.2 Chuẩn IEEE 1609 trong mạng VANETs
Các chuẩn 802.11 phải mất nhiều thời gian để hình thành kết nối khi nhận khung
thông tin đầu tiên và đặc biệt khi hai xe di chuyển ngược chiều nhau rất khó để hình
thành kết nối trao đổi dữ liệu từ hai xe. Để khắc phục điều này ta cần một trạm quản

lý trung gian SME (Station management entity) hoặc tìm giao thức cấp cao hơn.
Việc truyền dữ liệu từ xe đến trạm cố định thì sử dụng giao thức chuẩn IEEE 1609.
Các chuẩn IEEE 1609 hỗ trợ việc truyền dữ liệu cần thiết cao hơn giới hạn của
khung dữ liệu 802.11p. Chức năng của các lớp IEEE 1609:
• IEEE 1609.1 Phục vụ lớp ứng dụng giúp định nghĩa quản lý tài nguyên cho
phép các ứng dụng trên các đơn vị bên đường để giao tiếp với các đơn vị gắn
trên phương tiện.
• IEEE 1609.2 Giúp định nghĩa dịch vụ bảo mật, chức thực và mã hoá thông
điệp trạm.
• IEEE 1609.3 Quy định cụ thể các dịch vụ mạng cụ thể cho truyền dữ liệu
VANETs và giao thức sử lý WSM (WAVE Short Message).
• IEEE 1609.4 Định nghĩa các hoạt động của các kênh như CCH và SCH và có
mối quan hệ với cơ chế EDCA.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 12/60

CHƯƠNG 3. CÁC GIAO THỨC ĐỊNH TUYẾN TRONG VANETs
3.1 Định tuyến
Định tuyến là một quá trình chọn lựa đường đi trên mạng máy tính. Định tuyến
giúp tìm ra đường thích hợp nhất, từ tuyến đường đó ta có thể gửi gói dữ liệu trên
mạng đến máy tính đích một cách tối ưu nhất có thể. Định tuyến có mặt ở rất nhiều
loại mạng điển hình như: mạng internet, mạng điện thoại, mạng VANETs…Thực
chất định tuyến là tìm ra đường đi từ node truyền dữ liệu đến node đích thông qua
các node trung gian. Việc định tuyến thực hiện được chủ yếu là dựa vào bảng định
tuyến. Định tuyến chủ yếu được chia làm hai loại: định tuyến tự động là định tuyến
thủ công, tuỳ vào tính chất của mạng ta có thể thực hiện kết hợp hai loại định tuyến

cùng nhau.
Giao thức định tuyến dùng để thi hành thuật toán định tuyến tự động cho việc
trao đổi thông tin và tìm đường định tuyến cho các node trong mạng. Giao thức
định tuyến giúp xây dựng một bảng định tuyến một cách tự động theo các thuật toán
định tuyến
Có nhiều loại thuật toán định tuyến trong đó có hai loại cơ bản là: Thuật toán
vector (distance-vector routing protocols) và Thuật toán trạng thái kết nối (Linkstate routing protocols):
• Thuật toán vector: Dùng thuật toán Bellman-Ford phương pháp chỉ định
một số cho mỗi liên kết giữa các node trong mạng. Các node truyền từ
node nguồn đến node đích cho một số thấp nhất và số đó là tổng các kết
nối đi qua các node trung gian.
• Thuật toán trạng thái kết nối: Mỗi node sử dụng cơ sở dữ liệu của mạng
được xem như là bảng đồ của mạng với dạng một đồ thị. Mỗi node trong
mạng phát một luồng thông tin về các node mà nó có thể trực tiếp kết nối
được cứ như vậy từng node trong mạng góp phần tạo ra một bảng đồ

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 13/60

mạng một cách độc lập. Từ bảng định tuyến do con router quản lý sẽ
quyết định tuyến đường tốt nhất từ nó đến mọi node.
Đối với mạng VANETs mỗi node đều có thể là một thiết bị đích, không có thiết bị
router nên việc định tuyến của mạng có một yêu cầu và thách thức riêng, đặc biệt là
đặc đính các node di chuyển linh động cấu trúc liên kết mạng rất dễ bị phá vở nên
đòi hỏi phải có các giao thức định tuyến riêng.
3.2 Tổng quan về định tuyến trong VANETs


Hình 3-1: Tổng quan về các giao thức định tuyến trong VANETs

Mục đích chính của mạng VANETs là cho phép các node truyền một thông điệp
khẩn cấp đến các phương tiện gần đó. Các node thường gửi broadcast đến các node
gần đó còn với các tin nhắn đối với ứng dụng không an toàn có thể chọn kiểu gửi
unicast. Do đặc thù của mạng VANETs các node không chỉ là node nguồn và node
đích mà còn là node chuyển tiếp các gói dữ liệu vì vậy việc định tuyến cho mạng là

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 14/60

rất cần thiết. Việc định tuyến đường truyền có thể chia theo cách thức truyền tin:
broadcast, unicast, multicast. Ở mỗi cách thức truyền tin ta lại chia định tuyến theo
cấu trúc liên kết và vị trí như hình 3-1[5].
• Broadcast: Định tuyến theo broadcast chủ yếu dùng để truyền các tin nhắn về
điều kiện giao thông, các cảnh báo khẩn cấp giữa các phương tiện. Nó có thể
định tuyến nhiều bước để truyền các thông điệp quan trọng đến người gửi
vượt xa ngoài phạm vi kết nối trực tiếp. Để làm được việc này các node nhận
tin nhắn phải phát lại một gói tin như vậy điều này làm cho overhead của
mạng lớn. Hầu hết các giao thức phát sóng broadcast tập trung giảm thiểu
overhead bằng cách phân loại các node, chỉ cho một số node phát sóng lại.
• Multicast: Dùng để định tuyến gửi từ một node đến một nhóm các node.
Giao thức Multicast cũng được phân chia theo vị trí và cấu trúc liên kết. Một
thông điệp được gửi cho một node thuộc một vùng cụ thể.
• Unicast: Mục tiêu của nhóm giao thức này là gửi từ một nguồn đến một đích
duy nhất. Giao thức này cũng được chia thành vị trí và cấu trúc liên kết. Giao
thức theo cấu trúc liên kết được chia bị động va chủ động.


Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 15/60

3.3 Tổng quan định tuyến theo Unicast trong VANETs
Định tuyến theo unicast được chia thành cấu trúc liên kết và vị trí liên kết như
hình 3-2.

Hình 3-2: phân chia các giao thức định tuyến trong mạng VANETs theo unicast

3.4 Giao thức định tuyến dựa trên cấu trúc liên kết theo unicast
Giao thức định tuyến dựa trên cấu trúc liên kết (Topology-Based Routing
Protocols) sử dụng các bảng định tuyến để lưu trữ thông tin liên kết làm cơ sở
chuyển tiếp từ nguồn đến đích. Giao thức này phân loại dựa trên kiến trúc mạng là
Proactive và Reactive.
3.4.1 Nhóm Giao thức định tuyến Proactive
Giao thức định tuyến Proactive còn được gọi là giao thức hoạt động dựa trên
bảng định tuyến để nhận biết thông tin các node còn lại. Vì vậy mỗi node có thể biết
được kiến trúc tổng thể của mạng. Ưu điểm của các giao thức này là không cần phải
tìm tuyến đường vì tuyến đường được lưu trữ trong bảng định tuyến nhưng để duy

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 16/60


trì các tuyến đường không sử dụng làm cho băng thông của mạng sẽ bị giảm đây là
nhược điểm của các giao thức này. Điển hình của giao thức Proactive là giao thức
định tuyến vector (DSDV) và giao thức định tuyến trạng thái (FSR).
3.4.2 Nhóm Giao thức định tuyến Reactive
Đây là giao thức định tuyến theo yêu cầu, đường đi chỉ được xác định khi một
node có nhu cầu truyền gói tin. Nó chỉ duy trì liên kết với các tuyến đường đang
được sử dụng. Phương pháp này làm giảm gánh nặng trong mạng hạn chế sử dụng
băng thông. Nhóm giao thức định tuyến Reactive gồm các giai đoạn phát hiện tuyến
đường khi các gói truy vấn tuyến đường được phát cho toàn bộ các node lân cận cho
đến khi tới được node cần truyền. Nhưng nhược điểm là gây trễ lớn cho các khung
truyền dẫn đầu tiên và thời gian chọn đường truyền dẫn chậm. Các giao thức
Reactive điển hình là AODV (On – Demand Vector Routing) vector khoảng cách
theo yêu cầu và giao thức định tuyến nguồn động DSR (Dynamic Source Routing).
Khi xảy ra lỗi tại một node trên quá trình truyền dữ liệu các giao thức định tuyến
thường khôi phục đường truyền bằng cách tạo tuyến đường mới. Sử dụng thông tin
phản hồi đến các node nguồn nhằm để khởi tạo tuyến đường mới nếu kích thước
mạng lớn thì lưu lượng gói tin tăng lên rất nhanh nhất là đối với nhóm giao thức
định tuyến proactive. Kích thước mạng tăng lên thì đồng nghĩa với việc hiệu năng
mạng bị giảm do hiện tượng trễ của thủ tục định tuyến.
3.5 Giao thức định tuyến dựa trên vị trí theo unicast
Đối với nhóm giao thức này các node khi muốn truyền dữ liệu không cần tìm
tuyến đường hay duy trì tất cả tuyến đường như các giao thức định tuyến dựa trên
cấu trúc dữ liệu. Khi một node muốn truyền dữ liệu nó sẽ tự xác định vị trí của nó
cũng như vị trí của node cần truyền đến bằng cách dựa trên sự hỗ trợ của công nghệ
định vị toàn cầu như GPS. Các giao thức định tuyến này khắc phục nhược điểm của
các giao thức định tuyến dựa trên cấu trúc liên kết mạng vì xe di chuyển liên tục và
tốc độ thay đổi, các xe di chuyển ngược chiều nhau thì khoảng cách của chúng cũng

Giao thức định tuyến trong VANETs



ĐỒ ÁN TỐT NGHIỆP
Trang 17/60

thay đổi rất nhanh trong khoảng thời gian rất ngắn nên tốc độ thay đổi cấu trúc liên
kết mạng thường rất cao và băng thông cần thiết để duy trì tuyến đường rất lớn để
các tuyến đường luôn được cập nhật. Các giao thức định tuyến dựa trên vị trí được
chia thành 3 loại là: DTN (Delay Tolerant Network), Non-DTN (Non-Delay
Tolerant Network) và Hybrid.
3.5.1 Nhóm giao thức định tuyến Non-Delay Tolerant Network (Non-DTN)
Non-DTN là giao thức định tuyến cho thời gian đưa gói tin từ nguồn đến đích
một cách nhanh nhất. Nhóm giao thức này phù hợp với các ứng dụng an toàn yêu
cầu truyền gói tin sớm nhất. Thời gian trễ khi truyền dẫn trong giao thức này là
quan trọng nhất và phương pháp được áp dụng đó là tìm con đường dẫn ngắn nhất.
Giao thức này có hạn chế là ở các vùng có mật độ xe thưa thớt đường định vị ngắn
nhất có thể không kết nối được với điểm đích. Điển hình của nhóm này là giao thức
GPSR (Greedy Perimeter Stateless Routing) khi không thể kết nối tiếp trên con
đường đến đích giao thức này sử dụng kĩ thuật mô hình nhóm cho dự đoán di động
trong bán kính node đó.
3.5.2 Nhóm giao thức định tuyến Delay Tolerant Network (DTN)
Là các giao thức mạng giải quyết các vấn đề kĩ thuật liên quan đến việc mạng
không đồng nhất. Đặc trưng là các vấn đề về độ trễ, băng thông, xác suất lỗi và độ
ổn định đường dẫn. Khi một node không thể liên lạc với các node khác giao thức sẽ
lưu lại gói và chuyển tiếp khi đường truyền dữ liệu được kết nối trở lại.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 18/60


3.6 Giao thức định tuyến AODV
AODV (Adhoc On-demand Distance Vector ) là một giao thức định tuyến
khoảng cách theo yêu cầu, dùng để truyền thông điệp gián tiếp từ node này đến
node khác ở một khoảng cách xa thông qua các node lân cận. Giao thức chỉ tìm
kiếm đường truyền khi có nhu cầu gửi các gói dữ liệu từ nguồn đến đích. Giao thức
phân phối các gói yêu cầu định tuyến chỉ khi được yêu cầu. Giao thức AODV sử
dụng bảng định tuyến truyền thống để lưu trữ thông tin định tuyến. AODV không sử
dụng định tuyến nguồn mà chỉ cần quan tâm đến các node láng giềng của nó,
AODV dựa trên các entry của bảng định tuyến để phát gói RREP để gửi về cho
node nguồn [8].

Hình 3-3: Các thông báo định tuyến trong AODV

Các node lân cận liên lạc thông tin hello với nhau để giữ liên lạc, khi một node
muốn truyền dữ liệu cho node khác nó sẽ gửi một thông điệp RREQ cho các node
lân cận và các node lân cận sẽ truyền cho các node lân cận khác đến khi tìm đến
node đích. Khi tìm được node nhận, node kết nối trực tiếp với node nhận sẽ truyền
thông điệp về cho node nguồn, thiết lập kết nối. Sau đó dữ liệu được truyền theo
tuyến đường vừa được tìm kiếm. Do đặc tính di động của mạng nên có thể kết nối

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 19/60

tại một số node nào đó trong tuyến đường có thể bị mất kết nối, lúc này node không
gửi dữ liệu đi tiếp đến node đích sẽ gửi về node nguồn một thông điệp RRER.
Để đảm bảo thông tin trong bảng định tuyến là mới nhất thì AODV sử dụng khái

niệm destination sequence number để cập nhật các tuyến đường mới nhất vào trong
bảng định tuyến. Request ID đánh số thứ tự các gói tin định tuyến tránh việc một
node gửi một thông điệp định tuyến nhiều lần và tránh gửi vòng lặp trong mạng.
• Cơ chế Router Discovery:
Một node có hai bộ phận đếm (counter): Bộ đếm số sequence và bộ đếm
broadcast ID. Các số sequence được tăng lên khi:
o Trước quá trình Router Discovery (khám phá định tuyến) để chống
xung đột với các gói RREP trước đó.
o Trước khi node đích gửi gói RREP để trả lời gói RREQ nó sẽ nhập
các giá trị số sequence để định hướng đường đi cho gói RREP.
o Khi có sự thay đổi mạng cục bộ nó sẽ tăng số sequence giúp di
chuyển đến các node láng giềng giúp cho quá trình truyền tiếp tục.
o Số request ID được tăng khi node khởi động quá trình Router
Discovery mới.
Khi một node nguồn muốn gửi dữ liệu cho node đích đầu tiên nó kiểm tra trong
bảng định tuyến xem có tuyến đường chưa. Nếu có thì thực hiện gửi theo tuyến
đường đó ngược lại thì bắt đầu quá trình tìm kiếm tuyến đường gửi dữ liệu bằng
cách phát thông điệp RREQ gồm: Địa chỉ node nguồn, địa chỉ node đích, ID
request, số sequence, số hop-count. Quá trình Router Discovery thực hiện như sau:
Bước 1: Node nguồn gửi thông điệp RREQ cho các node lân cận. request ID
tăng lên, số sequence tăng lên để xác định gói tin và tránh xung đột với gói tin
trước.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 20/60

Bước 2: Node nhận được thông điệp RREQ sẽ kiểm tra số Request ID xem node

đó đã xử lý gói RREQ đó chưa. Nếu rồi thì loại bỏ còn chưa thì qua bước 3.
Bước 3: Tìm xem vùng lân cận có node nào đúng với địa chỉ ID của node đích
không nếu không thì sẽ chuyển RREQ đến node lân cận và tăng hop-count lên 1 và
tự động thiết lập một tuyến đường ngược về node nguồn bằng cách ghi lại địa chỉ
node truyền gói RREQ cho nó lần đầu tiên. Entry này tồn tại trong một khoảng thời
gian đủ để RREQ tìm được node đích và truyền gói RREP về cho node nguồn sau
đó nó được xoá đi. Nếu node này có thể kết nối với node đích thì chuyển đến bước
4.
Bước 4: Khi node nhận RREQ, tìm được node lân cận có địa chỉ ID là node đích
và nếu số Sequence trong RREQ lớn hơn hoặc bằng thì so sánh số hop-count nhỏ
nhất thì node đó sẽ tăng số sequence lên và trả về thông điệp RREP. Thông điệp
RREP gồm: Địa chỉ nguồn, địa chỉ đến, số sequence vừa mới làm mới, hop count.
Gói tin RREP được truyền về node nguồn theo entry đã được thiết lập ở bước 3.
Trong quá trình truyền gói tin RREP về một node có thể nhận nhiều gói RREP gói
RREP được sử dụng cập nhật bảng định tuyến là gói có số Sequence lớn nhất, nếu
số Sequence bằng thì so sánh số hop-count nhỏ nhất. Như vậy khi gói tin RREP
truyền qua một node nó sẽ cập nhật thông tin tuyến đường đi tìm được vào bảng
định tuyến quá trình này liên tục diễn ra đến khi gói tin RREP đến node nguồn.

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 21/60

Hình 3-4: Quá trình truyền thông điệp RREQ trong giao thức AODV

Hình 3-5: Quá trình truyền thông điệp RREP trong giao thức AODV

• Cơ chế tìm đường mới khi bị mất kết nối:

Nếu trong quá trình truyền dữ liệu một node có thể di chuyển do cơ chế di động
của mạng và làm mất kết nối với node khác làm cho đường đi truyền dữ liệu bị mất
kết nối. Trong trường hợp này tại node bị mất kết nối với node khác trên đường đi
truyền dữ liệu sẽ gửi một thông điệp RRER về các node đang truyền dữ liệu và
thông báo về cho node nguồn, tại đây node nguồn thực hiện cơ chế router discovery
mới để có thể thiết lập lại tuyến đường khác và truyền dữ liệu tiếp tục. Thông điệp
RRER chứa IP node bị lỗi và số hop-count node bị lỗi.
Bảng định tuyến của giao thức AODV:

Giao thức định tuyến trong VANETs


ĐỒ ÁN TỐT NGHIỆP
Trang 22/60

Bảng định tuyến của giao thức AODV rất quan trọng, đây là cơ chế chính giúp định
tuyến được đường đi truyền dữ liệu. Bảng định tuyến chứa thông tin địa chỉ node kế
tiếp node nguồn node đích, số hop-count, request ID, số sequence. Mỗi một node
trong mạng đều có một bảng định tuyến.
Bảng 3-1: Ví dụ về bảng định tuyến giao thức AODV

Node nguồn
10.0.0.1
10.0.0.1
10.0.0.1
10.0.0.1

Node đích
10.0.0.10
10.0.0.11

10.0.0.8
10.0.0.5

Node kế tiếp
10.0.0.2
10.0.0.2
10.0.0.3
10.0.0.4

Hop-count
4
5
2
2

Request ID
1
1
2
3

sequence
2
2
4
6

Số Sequence giúp cập nhật bảng định tuyến. Sau khi RREP được gửi về nguồn
sẽ phân tích dữ liệu Số Sequence nếu lớn hơn Số Sequence của bảng định tuyến thì
cập nhật tuyến đường đó vào bảng định tuyến. Bảng định tuyến chỉ lưu bước tiếp

theo của tuyến đường chứ không lưu toàn bộ cấu trúc liên kết.
Hình 3-6 là giải thuật định tuyến tìm đường đi của giao thức định tuyến AODV.

Giao thức định tuyến trong VANETs