Nghiên cứu và so sánh hiệu năng của một số giao thức định tuyến mạng vanet

`

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

TRƯƠNG THỊ PHƯƠNG CHI

NGHIÊN CỨU VÀ SO SÁNH HIỆU NĂNG

CỦA MỘT SỐ GIAO THỨC ĐỊNH TUYẾN

MẠNG VANET

Chuyên ngành: Hệ thống thông tin

Mã số: 61.49.01.04

TÓM TẮT LUẬN VĂN THẠC SĨ

HỆ THỐNG THÔNG TIN

ĐÀ NẴNG - NĂM 2017

Công trình được hoàn thành tại

TRƯỜNG ĐẠI HỌC SƯ PHẠM, ĐHĐN

Người hướng dẫn khoa học: PGS.TS. LÊ VĂN SƠN

Phản biện 1: PGS.TSKH. TRẦN QUỐC CHIẾN

Phản biện 2: PGS.TS. LÊ MẠNH THẠNH

Luận văn đã bảo vệ trước Hội đồng chấm Luận văn tốt

nghiệp thạc sĩ Hệ thống thông tin, họp tại Đại học Đà Nẵng

vào ngày 30 tháng 7 năm 2017.

Có thể tìm hiểu luận văn tại:

- Thư viện Trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Ngày nay công nghệ thông tin đã có những bƣớc tiến vƣợt bậc

và đƣợc áp dụng vào rất nhiều các mặt của đời sống xã hội nhƣ kinh

tế, giáo dục, y tế, quân sự,...và trong đó có giao thông và một số

lƣợng lớn các loại xe ô tô tham gia giao thông đã làm tăng lên sự

quan tâm trong việc phát triển các kỹ thuật truyền thông dành cho

các phƣơng tiện xe cộ, một vài dịch vụ di động mới hiệu quả kinh tế

và các ứng dụng cho các mạng giao thông đã đƣợc nghiên cứu, đặt

nền tảng cho hệ thống vận tải thông minh. Nhiều công nghệ đã đƣợc

đề xuất cho hệ thống vận tải thông minh nh m mục đ ch tăng sự an

toàn trên các tuyến đƣờng và vận tải hiệu quả và cung cấp kết nối

Internet không dây ở kh p m i nơi. Nhu cầu truyền thông ngày càng

lớn đ i h i những dịch vụ chất lƣợng cao, do đó cần phải có cơ sở hạ

tầng đáp ứng cho quá tr nh truyền thông trên nhiều môi trƣờng khác

nhau. ặc biệt sự ra đời mạng không dây đã đáp ứng một phần nhu

cầu truyền thông cho những nơi mà mạng có dây không thể thực

hiện tốt đƣợc Thêm vào đó là các ngh a truyền thông khác, ch ng

hạn các tài xế có thể nhanh chóng cập nhập thông tin giao thông nổi

bậc về các tuyến đƣờng với chi ph thấp. Với những lý do này,

truyền thông vô tuyến dành cho phƣơng tiện giao thông đã trở thành

một công nghệ rất quan tr ng.

Các mạng thông tin vô tuyến đƣợc chia thành hai dạng là các

mạng có cơ sở hạ tầng và các mạng Ad-hoc. Hầu hết các mạng thông

tin vô tuyến ngày nay là mạng có cơ sở hạ tầng, bao gồm các mạng

thông tin di động và mạng LAN không dây. Trong một mạng thông

tin vô tuyến có cơ sở hạ tầng, các trạm gốc sẽ quản l các thiết bị đầu

2

cuối di chuyển trong phạm vi vùng phủ của chúng. Mặt khác, các

mạng di động Ah-hoc (Mobile Ad-hoc Networks - MANETs) đƣợc

sử dụng và quản lý mà không có một cơ sở hạ tầng đƣợc thiết lập

trƣớc. Thực tế, trong mạng MANET, các thiết bị đầu cuối liên lạc

trực tiếp với các thiết bị khác mà không thông qua một thiết bị quản l

trung tâm.

Do MANET là một mạng mềm dẻo mà có thể đƣợc thiết lập

tại bất cứ đâu vào bất cứ thời điểm nào mà không cần đến cơ sở hạ

tầng hiện tại, bao gồm cả sự cấu h nh trƣớc đó và ngƣời quản trị, m i

ngƣời có thể nhận ra tiềm năng thƣơng mại và lợi thế của mạng ad

hoc có thể mang lại. MANET có thể đƣợc dùng trong quân sự, trong

các mạng cảm biến, các hoạt động cứu hộ, sử dụng để truyền thông

giữa các sinh viên trong khu trƣờng sở, trao đổi thông tin và dữ liệu

trong các khu thƣơng mại, tự do chia sẻ kết nối Internet, dùng trong

các buổi hội thảo,…

Các mạng MANET hiện tại đang nhận đƣợc sự quan tâm đặc

biệt trong cả l nh vực công nghiệp và giáo dục. Chúng là thành phần

quan tr ng của các mạng thế hệ kế tiếp. Trong khi MANETs ban đầu

đƣợc thiết kế cho mục đ ch quân sự, th hiện nay các lợi ch trong

các kỹ thuật vô tuyến, nhƣ mạng khu vực cá nhân (Personal Area

Network - PAN) (v dụ. Bluetooth 802.15.1, ZigBee) và mạng LAN

không dây (802.11), đã mang đến một sự thây thế trong việc s dụng

MANETs. Chúng cho phép hỗ trợ một phạm vi rộng của các ứng

dụng thƣơng mại mới trên MANETs. Bên cạnh các kỹ thuật đã kể

trên, truyền thông khoảng cách ng n (Dedicated Short Range

Communications - DSRC) đã làm cho việc thông tin liên phƣơng

tiện (Inter-Vehicular Communications - IVC) và thông tin phƣơng

3

tiện – tuyến đƣờng (Road-Vehicle Communications – RVC) trở nên

khả thi trong các mạng MANET. iều này đã khai sinh một dạng

mới của mạng MANET đƣợc biết đến nhƣ là mạng Vehicular Ad￾hoc Networks (VANETs) [2].

Mạng VANET là một trƣờng hợp đặc biệt của MANET.

Chúng giống với mạng MANET với sơ đồ mạng (topology) biến đổi

nhanh v sự di chuyển ở tốc độ cao của các phƣơng tiện. Tuy nhiên,

không giống nhƣ MANET, t nh di động của các phƣơng tiện trong

VANET bị ràng buộc chung bởi các tuyến đƣờng đƣợc định trƣớc.

Vận tốc của phƣơng tiện cũng đƣợc ràng buộc theo các giới hạn tốc

độ, mức độ t c nghẽn trên tuyến đƣờng, và các cơ chế điều khiển lƣu

lƣợng (nhƣ đèn giao thông). Thêm vào đó, các phƣơng tiện giao

thông có thể đƣợc trang bị thiết bị phát sóng khoảng cách xa hơn,

nguồn năng lƣợng có khả năng phục hồi, và khả năng lƣu trữ cao

hơn. Do đó, công suất x l và khả năng lƣu trữ không phải là vấn đề

trong mạng VANET nhƣ trong mạng MANET.

Cùng với sự phát triển hiện tại trong l nh vực VANET, một số

lƣợng các ứng dụng cho việc bố tr phƣơng tiện đã đƣợc đƣa ra. Các

ứng dụng VANET bao gồm các hệ thống an toàn hoạt động trên xe

để hỗ trợ các tài xế trong việc tránh va chạm và điều phối h tại các

điểm nóng nhƣ tại các giao lộ hay các lối vào đƣờng cao tốc. Các hệ

thống an toàn có thể phổ biến thông tin tuyến đƣờng một cách thông

minh, nhƣ các sự cố, t c nghẽn lƣu lƣợng thời gian thực, việc thu ph

đƣờng cao tốc, hay điều kiện mặt đƣờng đến các phƣơng tiện trong

lân cận vị tr đƣợc đề cập. iều này giúp tránh việc các phƣơng tiện

bị dồn ứ và theo đó cải thiện hiệu suất s dụng các tuyến đƣờng. Bên

cạnh các ứng dụng an toàn đã đƣợc đề cập, việc truyền thông liên

4

phƣơng tiện IVC có thể đƣợc s dụng để cung cấp các ứng dụng tiện

ch, ch ng hạn nhƣ thông tin thời tiết, vị tr các trạm xăng hay nhà

hàng, và các ứng dụng truyền thông tƣơng tác nhƣ truy cập Internet,

tải nhạc, và phân phối nội dung. Với những ứng dụng thiết thực và

t nh cấp thiết để triển khai các ứng dụng đó vào hệ thống giao thông

hiện nay nên em đã ch n thực hiện đề tài này.

Nội dung luận văn gồm 3 chƣơng:

Chƣơng 1. Nghiên cứu tổng quan về mạng không dây và mạng

VANET

Chƣơng 2. Nghiên cứu các giao thức định tuyến trong mạng

VANET

Chƣơng 3. Thực nghiệm so sánh hiệu năng và đánh giá kết quả

DSR, AODV, AOMDV và GPSR trong mạng VANET

2. Mục tiêu và nhiệm vụ đề tài

2.1. Mục tiêu

. Căn cứ vào mục đ ch chính của luận văn, tôi xin đƣa ra các

mục tiêu cụ thể nhƣ sau:

- Giới thiệu tổng quan về Mạng di động không dây đặc biệt

–VANET

- Nghiên cứu một số giao thức định tuyến không dây

sử dụng trong MANET: AODV, OLSR, DSR.

- Tìm hiểu khả năng mô ph ng các giao thức định tuyến

cũng nhƣ các mô h nh chuyển động khác nhau của bộ mô ph ng

mạng NS-2.

5

- ánh giá b ng mô ph ng một số giao thức định tuyến phổ

biến trong các ngữ cảnh chuyển động của các nút mạng khác nhau.

2.2 Nhiệm vụ

ể đạt đƣợc mục tiêu trên, nhiệm vụ của tôi là nghiên cứu,

thực hiện việc phân t ch, so sánh và đánh giá các giao thức theo các

tiêu ch về hiệu năng hoạt động của các giao thức này.

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tƣợng nghiên cứu

- Tổng quan về VANET.

- Vấn đề định tuyến trên VANET.

3.2. Phạm vi nghiên cứu

- Nghiên cứu giao thức định tuyến trong mạng VANET

- So sánh đánh giá các giao thức định tuyến

- Phần mềm mô ph ng NS2

- Phần mềm hổ trợ mô ph ng MOVE và SUMO

4. Phương pháp nghiên cứu

Phƣơng pháp nghiên cứu, chúng tôi đã sử dụng hai phƣơng

pháp ch nh là nghiên cứu lý thuyết và nghiên cứu thực nghiệm.

4.1. Phƣơng pháp nghiên cứu tài liệu

- T m hiểu, thu thập và phân t ch các tài liệu liên quan đến đề tài.

- Nghiên cứu các tài liệu mô tả đề tài và lựa ch n hƣớng giải quyết

vấn đề.

- Xây dựng chƣơng tr nh để kiểm nghiệm kết quả.

4.2. Phƣơng pháp thực nghiệm

- Sử dụng chƣơng tr nh mô ph ng trong môi trƣờng NS-2

- Kiểm tra và thực nghiệm chƣơng tr nh và đánh giá kết quả.

6

5. Ý nghĩa khoa học và thực tiễn đề tài

Về khoa học.

Về thực tiễn.

6. Kết quả dự kiến

6.1. Lý thuyết

6.2. Thực tiễn

7. Bố cục của luận văn

Báo cáo của luận văn dự kiến tổ chức thành 3 chƣơng ch nh nhƣ sau:

MỞ ẦU

CHƢƠNG 1: NGHIÊN CỨU TỔNG QUAN VỀ VANET

1.1. Giới thiệu về VANET

1.2. Các đặc điểm về VANET

CHƢƠNG 2: CÁC GIAO THỨC ỊNH TUYẾN TRONG

MẠNG VANET

2.1. CÁC THUẬT TOÁN ỊNH TUYẾN CƠ BẢN TRONG

MẠNG

2.2. YÊU CẦU ỐI VỚI THUẬT TOÁN ỊNH TUYẾN

TRONG MẠNG VANET

2.3. GIAO THỨC ỊNH TUYẾN TRONG MẠNG VANET

CHƢƠNG 3: MÔ PHỎNG CÁC GIAO THỨC AODV, DSR

VÀ OLSR TRONG MÔI TRƢỜNG NS-2

3.1. Giới thiệu môi trƣờng mô ph ng NS-2

3.2. Môi ph ng mạng không dây trong môi trƣờng NS-2

3.3. Phân t ch kết quả mô ph ng

7

CHƢƠNG 1:

TỔNG QUAN VỀ MẠNG KHÔNG DÂY VÀ

MẠNG VANET

1.1. GIỚI THIỆU VÀ PHÂN LOẠI KHÔNG DÂY

1.1.1. Giới thiệu

1.1.2. Phân loại mạng không dây

a. Phân loại theo định dạng và kiến trúc mạng

b. Phân loại theo phạm vi bao phủ truyền thông

c. Phân loại theo công nghệ truy cập đƣờng truyền

d. Phân loại theo các ứng dụng mạng

1.2. MẠNG KHÔNG DÂY ĐẶC BIỆT VANET

1.2.1. Giới thiệu về mạng VANET

1.2.2. ặc điểm mạng VANET

1.2.3. So sánh giữa mạng MANET và VANET

1.2.4. Mô h nh lớp trong mạng VANET

1.2.5. Ứng dụng và khó khăn

Ứng dụng

Khó khăn

8

CHƢƠNG 2

GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG VANET

2.1. CÁC THUẬT TOÁN ĐỊNH TUYẾN CƠ BẢN TRONG

MẠNG

2.1.1. Distance vector

2.1.2. Link State

2.1.3. Source routing

2.1.4. Kỹ thuật Flowding

2.2. YÊU CẦU ĐỐI VỚI THUẬT TOÁN ĐỊNH TUYẾN

TRONG MẠNG VANET

2.3. GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG VANET

2.3.1. Giao thức định tuyến DSR

Hoạt động của giao thức DSR bao gồm hai cơ chế ch nh: cơ

chế tạo thông tin định tuyến (Route Discovery) và cơ chế duy

trì thông tin định tuyến (Route Maintanance).

Cơ chế tạo thông tin định tuyến (Route Discovery):

Tiến tr nh tạo thông tin định tuyến sẽ phát gói tin Route

Request (RREQ) đến các node lân cận của nó trong mạng. Khi

một node nhận gói RREQ th nó sẽ tiến hành kiểm tra thông tin

trong RREQ nhƣ sau:

Bƣớc 1: Thông qua trƣờng request ID, nó sẽ kiểm tra xem

đã nhận gói tin này hay chƣa? Nếu đã tồn tại th nó sẽ loại b

gói tin đó và phản hồi RREP về nguồn. Ngƣợc lại th qua bƣớc

2.

9

Bƣớc 2: Nó kiểm tra trong Route Cache của nó có đƣờng đi

đến node đ ch mà c n hiệu lực hay không? Nếu có đƣờng đi

đến đ ch th nó sẽ phản hồi lại cho node nguồn b ng gói Route

Reply (RREP) chứa thông tin về đƣờng đi đến đ ch và kết thúc

tiến tr nh. Ngƣợc lại 8 th qua bƣớc 3.

Bƣớc 3: Nó kiểm tra địa chỉ đ ch cần t m có trùng với điạ

chỉ của nó hay không? Nếu trùng th nó gởi lại cho node nguồn

gói Route Reply (RREP) chứa thông tin về đƣờng đi đến đ ch

và kết thúc tiến tr nh. Ngƣợc lại th nó sẽ phát broadcast gói tin

RREQ đến các node láng giềng của nó. Các nút láng giềng sau

khi nhận gói tin RREQ sẽ thực hiện việc kiểm tra thông tin

(quay về bƣớc 1).

Nhƣ vậy, quá tr nh này cứ tiếp tục cho đến khi node nguồn

nhận đƣợc thông tin về đƣờng đi đến đ ch hoặc thông tin r ng

không thể định tuyến đến đ ch

Cơ chế duy tr thông tin định tuyến (Route Maintanance)

Route Maintanance cho phép các nút trong hệ thống mạng tự

động bảo tr thông tin định tuyến trong Route Cache. Trong

giao thức định tuyến DSR, các node khi chuyển gói tin trên

mạng đều phải có nhiệm vụ xác nhận r ng các gói tin đó đã

chuyển đến node kế tiếp hay chƣa (thông qua sự phản hồi thông

tin của node nhận)? Trong một trƣờng hợp nào đó mà node đó

phát hiện r ng gói tin không thể truyền đến node kế tiếp. Nó sẽ

gửi gói Route Error (RERR) cho node nguồn để thông báo t nh

trạng hiện thời của liên kết và điạ chỉ của node kế tiếp mà

10

không thể chuyển đi. Khi node nguồn nhận đƣợc gói RERR, nó

sẽ xóa con đƣờng đi mà liên kết bị h ng trong Route cache và

t m một đƣờng đi khác mà nó biết trong route cache hoặc sẽ

khởi động một tiến tr nh route discovery mới nếu nhƣ không

tồn tại đƣờng đi th ch hợp trong Route cache.

2.3.2. Giao thức định tuyến AODV

Quá tr nh định tuyến của AODV gồm 2 cơ chế ch nh: cơ chế

tạo thông tin định tuyến và cơ chế duy tr thông tin định tuyến.

Cơ chế tạo thông tin định tuyến (Route Discovery):

Tiến tr nh Route Discovery đƣợc khởi động khi nào một node

muốn trao đổi dữ liệu với một node khác mà trong bảng định

tuyến của nó không có thông tin định tuyến đến node đ ch đó.

Khi đó tiến tr nh sẽ phát broadcast một gói RREQ cho các node

láng giềng của nó. Thông tin trong RREQ ngoài địa chỉ đ ch,

địa chỉ nguồn, số hopcount (đƣợc khởi tạo giá trị ban đầu là

0),… c n có các trƣờng: số sequence number của node nguồn,

số broadcast id, giá trị sequence number đƣợc biết lần cuối

cùng của node đ ch. Khi các node láng giềng nhận đƣợc gói

RREQ, nó sẽ kiểm tra tuần tự theo các bƣớc:

Bƣớc 1: Xem các gói RREQ đã đƣợc xử lý chƣa? Nếu đã

đƣợc xử lý th nó sẽ loại b gói tin đó và phản hồi RREP về

nguồn. Ngƣợc lại chuyển qua bƣớc 2.

Bƣớc 2: Nếu trong bảng định tuyến của nó chứa đƣờng đi

đến đ ch, th sẽ kiểm tra giá trị Destination sequence number

trong entry chứa thông tin về đƣờng đi với số Destination