ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

v € MẠNH CƯỜNG

M A N E T- Đ ỊN H T U Y Ế N DựA T R Ê N T IÊ N Đ O ÁN V Ị T R Í

Ngành:
Công nghệ Điện tử - Viễn thông.
Chuyên ngành: Kỹ thuật vô tuyến điện tử và 'lĩiône tin liên lạc
Ma so:
2.07.00

LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS TS Nguyẻn Viết Kính
(Trường ĐHCN - ĐHQG Hà Nội)

ĐAI H Ọ C ý ƯỚC G IA HÀ NÒI
TRUNG TAM THÒNG TIN THƯ VIỆN

'1

HÀ NỘI 2006

/ Á ỵí •ỉ


MỤC LỤC

M Ụ C L Ụ C ................................................................................................................................1

TÓM TẮT........................................................................................................................... 3

DANH MỤC HÌNH VẼ.............................................................................................. 4
DANH MỤC BẢNG B lỂ ư .........................................................................................6
BẢNG KÝ HIỆU CÁC CHỮVIÊT TẮT..................................................................7

MỞ ĐẦU.................................................................................................... 8
CHƯƠNG I: GIỚI THIỆU....................................................................................10 •
1.1 Mạng di động Ad hoc (MANET)....................................................................10
1.1.1 Sự phát triển của mạng...................................................................................11
1.1.2 Các ngữ cảnh sử dụng mạng......................................................................... 13
1.1.3 Các đặc điểm mạng........................................................................................14
1.2 Vấn đề định tuyến..............................................................................................15
1.2.1 Các thuật toán định tuyến truyền thống...................................................... 15
1.2.2 Bài toán định tuyến mạng MANET............................................................. 17
CHƯƠNG 2: GIAO THỨC ĐỊNH TUYẾN MANET....................................... 19
2.1 Các kỹ thuật định tuyến MANET....................................................................19
2.1.1 Định tuyến L S v à D V ....................................................................................19
2.1.2 Định tuyến chủ ứng và định tuyến phán ứng.............................................. 19
2.1.3 Cập nhật định kỳ và cập nhạt theo sự k iệ n ................................................ 20
2.1.4 Cấu trúc phẳng và cấu trúc phân cấp........................................................... 20
2.1.5 Tính tốn phi tập trung và tính tốn phân tán.............................................20
2.1.6 Định tuyến nguồn và định tuyến theo chặng.............................................. 21
2.1.7 Đơn đường và đa đường................................................................................. 21
2.2 Phân loại các giao thức định tuyến MANET................................................21
2.2.1 Giao thức DSDV.............................................................................................22
2.2.2 Giao thức OLSR............................................................................................. 23
2.2.3 Giao thức AODV............................................................................................24

2.2.4 Giao thức DSR................................................................................................ 25
2.2.5. Giao thức TOR A ........................................................................................... 26
2.2.6 So sánh các giao thức..................................................................................... 27
2.3 MANET- Định tuyến dựa trên tiên đốn vị trí............................................ 30
2.3.1 Giao thức cập nhật..........................................................................................31
2.3.2 Tiên đốn.........................................................................................................34
2.3.3 Định tuyến ỌoS.............................................................................................. 36
CHƯƠNG 3: MƠ PHỊNG CÁC MẠNG DI ĐỘNG AD HOC.......................39
3.1 Mơ hình các MANET........................................................................................39
3.2 Bộ mô phỏng NS2............................................................................................. 39


3.3 Thiết lập MANET dùng mô phỏng trong NS2.......................................... 40
3.3.1 Mơ phịng mạng khơng dây di độno,........................................................ 40
3.3.1.1 Nút di động mơ phỏng...............................................................................40
3.3.1.2 Mơ hình phương tiện chia sẻ..................................................................42
3.3.1.3 Hoạt động của nút di động..................................................................... 43
3.3.2 Tạo ngữ cảnh......... ..................................................................................... 43
3.3.2.1 Các mơ hình chuyển động.........................................................................44
a.Mơ hình Random Waypoint............................................................................... 44
b. Mơ hình Random Walk................................................................................. 45
c. Mơ hình Random Direction...............................................................................47
3.3.2.2 Các mơ hình thơng lượng..........................................................................48
3.4 Tổng quan q trình mơ phỏng.......................................................................49
3.5 Mô phỏng các giao thức định tuyến............................................................... 50

3.5.1 DSDV.T..... .7............... ........ ...............................................................50
3.5.2
3.5.3
3.5.4

3.5.5

AODV..............................................................................................................51
DSR..................................................................................................................51
TORA.............................................................................................................. 52
OLSR...............................................................................................................53

CHƯƠNG 4: ĐÁNH GIÁ HIỆU SUẤT CÁC GIAO THỨC ĐỊNH TUYẾN
VÀ ĐỊNH TƯYẺN QOS D ựA TRÊN TIÊN ĐỐN VỊ
TRÍ................................ ... ............................................ ......... 54
4.1 Các tham số của mơi trường............................................................................ 54

4.2 Các độ đo hiệu năng............................................................................55
4.3 Các thí nghiệm mơ phỏng................................................................. 56
4.3.1
4.3.2
4.3.3
4.3.4

Thí nghiệm 1: sử dụng mơ hình Random Waypoint................................57
Thí nghiệm 2: sử dụng mơ hình Random W alk........................................63
Thí nghiệm 3: Sử dụng mỏ hình Random Direction.................................67
Thí nghiệm 4 : So sánh mơ hình thơng lượng TCP và CBR
trong giao thức định tuyến DSR và DSDV....................... 71
4.4 Nhận xct về hiệu năng của các giao thức..................................................... 77

4.5 Thí nghiệm 5: Đánh giá định tuyén ỌoS dựa trên tiên đoán vị tri'..............80

K ẾT LUẬN....... :..................................................................................................85
TÀI LIỆU THAM K H Ả O ................................................................................. 87


2


DANH MỤC HÌNH VẼ

Hình 1-1: MANET................................................................................................. 10
Hình 1-2: Hoạt động của mạng đơn chặng và đa chặng............................... 12
Hình 1-3: Mạng WPAN với các kết nối Internet............................................ 14
Hình 2-1: Phân loại các giao thức định tuyến mạng MANET.....................22
Hình 2-2: Định tuyến trạng thái liên kết và định tuyến cải tiến trong
O L SR ..................................................................................................... 24
Hình 2-3: Sự hình thành đường trong giao thức T O R A ............................... 26
Hình 2-4: Tần suất cập nhật loại 1 phụ thuộc vận tốc của nút................... 32
Hình 2-5: Cập nhật loại 2 ..................................................................................... 32
Hình 2-6: Tiên đốn vị trí, sử dụng cập nhật loại 2....................................... 35
H ình 3-1: Mơ phỏng /?út di động trong NS2 ..................................................... 41
Hình 3-2: Mơ hình phương tiện chia sẻ trong NS2.........................................42
Hình 3-3: Di chuyển của một nút theo mơ hình Random Waypoint..........45
Hình 3-4: Di chuyển của một nút theo mơ hình Random Walk.................. 46
Hình 3-5: Sự di chuyển của một nút theo mơ hình Random D irection...47
Hình 3-6: Các mơ hình thơng lượng trong NS2.............................................. 48
Hình 3-7: Tổng quan q trình mơ phỏng........................................................49
Hình 4-1: So sánh kết quả phân phát gói tin trong mỏ hình Random
Waypoint................................................................................................ 59
Hình 4-2: So sánh trẻ đầu cuối trung bình trong mơ hình Random
Waypoint............................................................................................... 60
Hình 4-3: So sánh tải định tun chuẩn hố trong mơ hình Random
Waypoint................................................................................................63
Hình 4-4: So sánh kết quả phân phát gói tin trong mơ hình Random

W alk........................................................................................................ 65
Hình 4-5: So sánh thời gian trẻ trung bình trong mó hình Random
W alk......................................................................................................66
4


Hình 4-6: So sánh tải định tuyến chuấn hố trong mơ hình Random
W alk....................................................................................................... 67
Hình 4-7: So sánh kết quả phân phát gói tin trong mỏ hình Random
Direction...............................................................................................69
Hình 4-8: So sánh thời gian trễ trung bình trong mơ hình Random
Direction...............................................................................................69
Hình 4-9: So sánh tải dịnh tuyến chuẩn hoá trong mỏ hình Random
Direction............................................................................................... 70
Hình 4-10: So sánh tỉ lệ phát gói tin thành cơng TCP và CBR trong
giao thức DSDV............................................................................... 72
Hình 4-11: So sánh tải định tuyến chuẩn hóa của TCP và CBR trong
giao thức DSDV............................................................................... 73
Hình 4-12: So sánh phần trăm gói tin phát thành cơng của TCP và CBR
trong giao thức DSR........................................................................ 74
Hình 4-13: Trễ đầu cuối trung bình cüa TCP và CBR trong giao thức
DSR.................................................................................................. 75
Hình 4-14: So sánh tải định tuyến chuẩn hóa TCP và CBR trong giao
thức DSR..........................................................................................76
Hình 4-15: Phần trăm lỗi của tiên đốn vị trí và tiên đốn vị trí kết hợp
trễ đầu cuối.......................................................................................81
Hình 4-17: Sự chính xác của vị trí dự đốn trế vói cập nhật loại 1..........82
Hình 4-17: Tổng số lỗi của khoảng lỗi tăng dần........................................... 82
Hình 4-18: số lượng gói tin trung bình cập nhật loai 1 của nút/giây.......83


5


DANH MỤC BẢNG BíỂU

Bảng 2-1: So sánh độ phức tạp của các giao thức...........................................28
Bảng 2-2: So sánh giữa các giao thức................................................................ 29
Bảng 2-3: So sánh giữa các giao thức................................................................ 30
Bảng 3-1: Các tham số cua mơ hình Random Waypoint..............................45
Bảng 3-2: Các tham số của mơ hình Random Walk......................................46
Bảng 3-3: Các tham số của mơ hình Random Direction...............................47
Bảng 3-4: Các tham số

hoạt động của DSDV trong NS2............................50

Bảng 3-5: Các tham số

hoạt động của AODV trong NS2...........................51

Bảng 3-6: Các tham số hoạt động của DSR trong NS2................................. 52
Bảng 3-7: Các tham số hoạt động của TORA trong NS2............................... 52
Bảng 3-8: Các tham số

hoạt động của OLSR trong mô phỏng................. 53

Bảng 4-1: Cấu hình các mạng mơ phỏng theo mơ hình Random
W aypoint................................................................................................ 58
Bảng 4-2: Tải định tuyến chuẩn hoá của TORA trong mơ hình Random
W aypoint................................................................................................ 62
Bảng 4-3: Cấu hình các mạng mó phỏng theo IĨ1Ơ hình Random Walk...65

Bảng 4-4: Cấu hình các mạng mỏ phỏng theo mơ hình Random
Direction................................................................................................. 68
Bảng 4-5: c ấ u hình mơ phỏng đẻ so sánh CBR, TCP trong giao thức
DSR và DSDV....................................................................................... 71
Bảng 4-6: c ấ u hình mơ phỏng định tuyến QoS dựa trên tiên đốn vị trí—81

6


B Ả N G K Ý H IỆ U C Á C C H Ũ V I É T T Ả T
AODV

Ad hoc On-demand
Distance Vector

CBR

Constant Bit Rate

CSMA/CA

Carrier Sense Multiple

NAM

Network Animator

NS2

Network Simulator 2


OLSR

Optimized Link Slate
Routing Protocol

Access with Collision
Avoidance
DARPA

Defense Advanced

PAN

Personal Area Network

PDA

Personal Digital

Research Projects
Agency
DSDV

PRnet

Packet Radio Network

QoS


Quality o f Service

RIP

Routing Information

Destination-Sequenced
Distance Vector

DSR

Dynamic Source Routing

DV

Distance Vector

IEEE

Institute o f Electrical and
Electronic Engineering

IETF

Assistant

Internet Engineering
Task Force

Protocol

RREP

Route Reply

RJR.EQ

Route Request

RTS

Request To Send

TC

Topology Control

TORA

Temporally-Ordered

LAN

Local Area Network

LS

Link State

MAC


Medium Access Control

WLAN

Wireless LAN

MAN ET

Mobile Ad hoc Network

WPAN

Wireless PAN

MPR

Multipoint Relay

Routing Algorithm


MỞ ĐẦU

Nhằm đạt tới sự giải phóng hồn tồn của mạng di động không dây vào các
cơ sở hạ tầng mạng cố định, nhiều hướng nghiên cứu, nhiều mơ hình kiến trúc
hoạt động mới đã được dưa ra. Một trong những hướng được đánh giá cao là
mạng di động Ad hoc. Đây là mạng kết nối các thiết bị tính tốn di động như
các máy tính Laptop, PDA hay điện thoại cầm tay ở trong cùng một khu vực
mà không cần tới các cơ sở hạ tầng mạng cố định hay đơn vị quản trị trung
tâm hỗ trợ [20].

Đặc trưng của truyền thông trong MANET là đa chặng, giữa nút nguồn và
nút đích có thể đi qua nhiều nút trung gian. Với cấu hình tế bào chuẩn, định
tuyến mỗi gói tin chỉ thông qua một chặng từ cơ sở tới nút di động. Nhưng
trong MANET các gói tin có thể được định tuyến thơng qua nhiéu chặng. Mặt
khác MANET có cấu hình hết sức phức tạp do sự di chuyển của các nút, băng
thông liên kết không dây hạn chế, khả năng tính tốn và dung lượng bộ nhớ
của các nút bị giới hạn. Để phát triển MANET trong thực tế cần phải phát
triển các giao thức làm việc hiệu quả trong môi trường khá đặc biệt này.
Luận văn này nghiên cứu các giao thức định tuyến MANET và đánh giá hiệu
năng làm việc của chúng về lý thuyết và thơng qua các thí nghiệm mơ phỏng
mạng. Các nội dung nghiên cứu cụ thể bao gồm:
❖ Nghiên cứu môi trường làm việc và các đặc điểm của mạng
❖ Xem xét bài toán định tuyến trong mạng và các giải pháp có thể.
❖ Phân loại các giao thức định tuyến.
❖ Phân tích và so sánh các giao thức trên cơ sở lý thuyết về độ phức
tạp và các đặc tính hoạt động.
❖ Xây dung mơi trường mơ phỏng và tích hợp một số giao thức
định tuyến cho MANET trong bộ mô phỏng mạng NS2.
❖ Đánh giá các giao thức định tuyến trong các ngữ cảnh với các
tham số khác nhau có ảnh hưởng nhất tới hiệu suất của các giao


thức định tuyến như kích thước mạng, tải mạng, tốc độ thay đổi
hình trạng mạng và mơ hình di chuyển.
Luận văn bao gổm 4 chương chính ngồi chương giới thiệu và kết luận:
Chương I: Giới thiệu về mạng MANET và bài tốn định tuyến trong
mạng.
Chương II: Trình bày về các giao thức định tuyến trong mạng MANET,
phân loại về các giao thức, mô tả chi tiết về một số giao thức tiêu biểu
và so sánh giữa các giao thức.

Chương III: Trình bày về việc mơ phỏng MANET bằng bộ mơ phỏng
NS2
Chương IV: Nghiên cứu đánh giá hiệu suất các giao Ihức định tuyến với
các độ đo hiệu năng cụ thể để so sánh giữa giao thức trong các điểu
kiện mạng thay đổi. So sánh MANET dùng mơ hình thơng lượng TCP
và CBR. Đánh giá MANET sử dụng định tuyến dựa trên tiên đốn vị trí.

9


CHƯƠNG I: GIỚI THIỆU

1.1 Mạng di động Ad hoc (MANET)
MANET (Mobile Ad hoc NETwork) là mạng không dây đặc biệt gồm tập
hợp các thiết bị di động với giao tiếp khơng dây có khả năng truyền thơng trực
tiếp với nhau khi nằm trong vùng thu/phát sóng của nhau hoặc thơng qua các
nút trung gian làm nhiệm vụ chuyển tiếp hình 1-1. Trong MANET, các nút
vừa đóng vai trị truyền thơng vừa đóng vai trị như thiết bị định tuyến. Với
ngun tắc hoạt động như vậy, MANET không bị phụ thuộc vào các cơ sở hạ
tầng cố định và các đơn vị quản trị trung tâm như các mạng tế bào và WLAN
truyền thống.

Hình 1-1: MANET
MANET có độ linh hoạt cao với khả năng hoạt động độc lập với cơ sở hạ
tầng mạng cố định [14]:
•

Triển khai nhanh khi có u cầu

•


Tin cây và mạnh mẽ do hoạt động phân tán và khả năng tự

động cấu hình lại mạng khi có các thay đổi liên kết.
•

Kết nối khơng giới hạn.

•

Chi phí triển khai và hoạt động thấp.

Ngồi ra, MANET có ý nghĩa đặc biệt trong quân sự, chống khủng bố, trong
các trường hợp tìm kiếm và cứu hộ khẩn cấp và trong việc xây dựng các mạng
cảm biến ở các khu vực con người không thể truy cập được.

10


1.1.1 Sự phát triển của mạng
Hỗ trợ đầu tiên cho sự phát triển MANET là việc triển khai mạng ALOHA
nãm 1968 [20]. Mục tiêu cuả mạng này là kết nối các cơ sở giáo dục ở
Hawaii. Mặc dù các trạm làm việc là cố định, giao thức ALOHA đã thực hiện
việc quản lý truy cập kênh truyền dưới dạng phân tán, do đó đã cung cấp cơ sở
cho sự phát triển về sau của các lược đồ truy cập kênh phân tán cho phép sự
hoạt động của MANET.
Khởi nguồn từ các mạng ALOHA và những phát triển ban đầu của mạng cố
định chuyển mạch gói, tổ chức DARPA đã bắt đầu làm việc trên các mạng vơ
tuyến gói tin PRnet (Packet Radio network) vào năm 1973 [16]. Đây là mạng
vô tuyến gói tin đa chặng đầu tiên. Trong ngữ cảnh này, đa chặng có nghĩa là

các nút hợp tác để chuyển tiếp truyền thông cho các nút ở xa nằm ngoài vùng
truyền thống của một nút. PRnet đã cung cấp cơ chế cho việc quản lý hoạt
động trên cơ sở tập trung cũng như phân tán.
Người ta cũng bắt đầu nhận thấy nhiều lợi điểm của làm việc đa chặng so
với đơn chặng. Triển khai đa chặng tạo điều kiện thuận lợi cho viộc dùng lại
các tài nguyên kênh truyền về cả không gian và thời gian và làm giảm năng
lượng phát cần thiết. Trong khi đó, làm việc đơn chặng chỉ chia sẻ các tài
nguyên kênh về thời gian và yêu cầu năng lượng cao hơn để có thể giao tiếp
được với các nút ở xa. Hình 1-2 thể hiện sự can nhiễu về không gian trong các
ngữ cảnh đa chặng và đơn chặng [20]. Trong cả hai trường hợp, ngữ cảnh
mạng là hoàn toàn giống nhau về sự phân bố của các nút, nguồn phát và đích.
Trong trường hợp đa chặng, các gói tin được định truyền thơng qua nhiều
điểm chuyển phát. Tuy nhiên, trong mạng đơn chặng, gói tin được gửi trực
tiếp từ nguồn tới đích. Các vòng tròn thể hiện mức năng lượng phát cần thiết
của mỗi nút để có thể giao tiếp với nút đích.

11


a chng

â

,( " ã ( J r j V0N.V

â
\
đ\ â

o


/

y

o

â

9

Nỳt n g u ị n

ặặ
Q

NÚI đích
Nứt ctiưyển tiép

©

C ác nút k h ác

©

Hình 1-2: Hoạt động của mạng đơn chặng và đa chặng
Mặc dù nhiều mạng vơ tuyến gói tin đã được phát triển sau đó, các hệ thống
khơng giây này vẫn chưa bao giờ được đưa vào phục vụ người sử dụng thông
thường. Khi chuẩn IEEE 802.11, một chuẩn cho mạng cục bộ không đây được
phát triển, viện IEEE đã thay thế khái niệm mạng vơ tuyến gói tin thành

MANET. Các mạng vơ tuyến gói tin do đó thường gắn với các mạng đa chặng
rộng lớn trong quân sự. IEEE hy vọng loại mạng mới này sẽ được triển khai
rộng rãi trong thực tế.
Một số công nghệ không dây hiện tại hỗ trợ sự làm việc của MANET là
Bluetooth và IEEE 802.11. Trong đó, IEEE 802.11 là chuẩn cục bộ khơng dây
có sơ sở hạ tầng được bổ sung chức năng hỗ trợ làm viêc MANET [11]. Mạng
IEEE 802.1 lb làm việc ở dải băng tần 2.4GHz với tốc độ dữ liệu 11 Mbps và
hiện tại đã đạt tới 20 Mbps. Chuẩn IEEE 802.1 la tiếp theo hoạt động ở giải
băng tần 5GHz và tốc độ dữ liệu đạt tới 54Mbps. Trong khi đó, Bluetooth là
kiến trúc làm việc của MANET khơng dây dải sóng ngắn cho các mạng cá
nhân WPAN. Mạng này nhằm mục đích kết nối các thiết bị cá nhân di động
như các máy tính laptop, PDA, các thiết bị ngoại vi, điện thoại cầm tay, các
máy quay kỹ thuật số, các đầu nghe và các thiết bị điện tử khác. Vùng hoạt
động của mạng do vậy rất nhỏ, thường dưới 10m xung quanh cá nhân và
thường được gọi là không gian hoạt động cá nhân - POS (Personal operating
Space).

12


1.1.2 Các ngữ cảnh sử dụng mạng
Các ứng dụng đầu tiên của mạng vơ tuyến gói tin MANET là trong quân sự,
trong đó sự hoạt động phi tập trung của mạng là một nhu cầu cần thiết. Ngày
nay, các thiết bị tính tốn khơng dây, di động vẫn có mức gía rất cao. Tuy
nhiên, khả năng của các máy tính di động sẽ tàng lên và nhu cầu làm việc với
mạng khơng dây sẽ ngày càng tăng. MANET có thể được dùng trong các tình
huống khi khơng có cơ sở hạ tầng mạng cố định hoặc mạng tế bào.
MANET có thể được triển khai trong truy cập công cộng không dây ở các
khu vực thành phố, trường học giúp thực hiện nhanh các cuộc truyền thông và
mở rộng diện hoạt động. Các điểm truy cập có thể dùng như các trạm tiếp

sóng cố định thực hiện việc định tuyến giữa chúng và giữa các nút người dùng.
Một số điểm truy cập có thể dùng như gateway cho phép người dùng kết nối
tới mạng xương sống cố định.
Ở mức cục bộ, MANET liên kết các máy tính sách tay hoặc các máy tính để
bàn để phân phát và chia sẻ thơng tin giữa những người tham gia một hội nghị
hay lớp học. MANET cũng thích hợp cho các ứng dụng trong mạng gia đình.
Trong đó, các thiết bị có thể truyền thông trực tiếp với nhau để trao đổi thông tin
dữ liệu như âm thanh, hình ảnh, báo thức và các cập nhật cấu hình.
Một dạng đặc biệt của MANET là mạng cảm biến (sensor network) được
triểt khai trong các ứng đụng về kiểm sốt mơi trường. Các mạng này có thể
được dùng để dự báo những ô nhiễm về nguồn nước hoặc những cảnh báo sớm
về lũ lụt hoặc sóng thần.
MANET dải sóng ngắn làm đơn giản hố truyền thơng của các thiết bị di
động khác nhau như điện thoại tế bào và PDA bằng việc hình thành các mạng
WPAN và loại bỏ sự kết nối bằng cáp. Mạng có thể giúp chia sẻ khả năng truy
cập Internet và các tài nguyên trong mạng như máy in giữa các thiết bị. Khả
năng này giúp mở rộng tính di động của người dùng. Hiện nay, Bluetooth là
công nghệ hứa hẹn nhất trong ngữ cảnh làm việc mạng cá nhân hình 1-3 [20].

13


Hình 1-3: Mạng WPAN với các kết nối Internet
Kết hợp với truyền thông vệ tinh, công nghệ MANET sẽ rất linh động cho
việc thiết lập các truyền thông được triển khai nhanh, hồn tồn khơng phụ
thuộc vào các cơ sở hạ tầng truyền thông cố định.
1.1.3 Các đăc điểm mạng
Trong MANET, các nút là di động và được trang bị các bộ phát và nhận tín
hiộu khơng dây sử dụng các loại ăng-ten khác nhau. Tại một thời điểm, phụ
thuộc vào vị trí của nút và dạng bao phủ của bộ nhận và phát tín hiệu, mức năng

lượng phát và mức độ giao thoa cùng kênh,kết nối không dây giữa các nút có
dạng ngẫu nhiên và là hình đa chặng. Cấu hình này thay đổi theo thời gian do các
nút di chuyển hoặc điều chỉnh các tham số phát và nhận sóng.
Từ đó, có thể nhận thấy một số đặc điểm nổi bật của M ANET có ảnh hưởng
tới thiết kế và hiệu suất của các giao thức trong mạng [24]:
• Cấu hình mạng động: Do sự di chuyển của các núi, mạng thơng
thường là đa chặng, có thể thay đổi một cách ngãu nhiên và nhanh chóng tại
bất kỳ thời điểm nào có thể chứa các liên kết hai chiều cũng như một chiều.
• Băng thơng hạn chế, khả năng của các liên kết có th ể biến đổi: Các liên
kết khơng dây có băng thơng thấp hơn đáng kể so với các đường truyền cáp.
Thêm vào đó, thơng lượng của các đường truyền thông không dây do ảnh hưởng

14


của đa truy cập, sự suy giảm, nhiễu và các điều kiện giao thoa thường nhỏ hơn
tốc độ truyền lớn nhất của sóng vơ tuyến.
• Các nút cố năng lượng thấp: Một số hoặc tất cả các nút trong mạng
MANET dùng pin để cung cấp năng lượng hoạt động cho các thành phần
trong thiết bị. Do vậy các nút trong MANET thường bị hạn chế về khả năng
tính tốn của CPU, kích thước bộ nhớ, khả năng xử lý tín hiệu và mức năng
lượng phát và nhận sóng.
• Bảo mật vật lý có giới hạn: Do việc truyền qua khơng khí, các mạng
khơng dây tiềm ẩn nhiều về nguy cơ bảo mật hơn các mạng cáp. Nhiều khả
năng tấn công bảo mật như nghe trộm, giả mạo và từ chối dịch vụ (DoS) có
thể xảy ra. Các kỹ thuật bảo mật cần được triển khai trên nhiêu tầng giao thức
để làm giảm các nguy cơ đe doạ việc bảo mật.
1.2 Vấn đề định tuyến
Định tuyến mạng là việc tìm đường đi từ nguồn tới đích qua hệ thống mạng.
Giao thức định tuyến có chức năng chính là lựa chọn đường cho các cặp

nguồn - đích và phân phát gói tin tới đích chính xác. Truyền thơng trong
MANET dựa trên các đường đi đa chặng, do vậy định tuyến các gói tin là hoạt
động quan trọng. Khác với các mạng cố định có cấu hình ít thay đổi hoặc gần
như khơng thay đổi, do truyền tin khơng dây và có tính chất động của
MANET khiến cho các giao thức định tuyến được thiết kế cho mạng cố định
không thể áp dụng hoặc gần như thất bại trong MANET. Viộc thiết kế một
giao thức định tuyến làm việc hiệu quả trong MANET là một bài tốn khó.
1.2.1 Các thuật tốn định luyến truyền thống
Để tìm đường đi cho các gói tin qua hệ thống các bộ định tuyến (router)
trong mạng, các giao thức định tuyến truyền thống thường sử dụng giải thuật
vectơ khoảng cách (Distance Vector Routing-DV) hoặc trạng thái liên kết
(Link State Routing-LS) thuật tốn DV cịn được gọi là thuật toán BellmanFord, được dùng trong mạng ARPANET lúc mới ra đời và được sử dụng trong
mạng INTERNET với tên gọi là giao thức thông tin định tuyến RIP (Routing

15


Information Protocol). Thuật toán LS được sử dụng trong giao thức OLSF
(Open Shortest Path First) của Intemet[3].
Trong giải thuật DV, mỗi router quảng bá một cách định kỳ tới các hàng
xóm thơng tin khoảng cách từ nó tới tất cả các router khác. Bằng việc so sánh
các khoảng cách từ mỗi hàng xóm tới một đích nào đó, router có thể quyết
định hàng xóm nào sẽ là chặng tiếp theo trong trường hợp đi tới đích để đường
đi là tối ưu nhất. Bảng định tuyến các router do đó lưu trữ các thơng tin về các
đích trong mạng (các router khác trong mạng), chặng tiếp theo và khoảng
cách tới đích. Vấn đề với DV là khả năng hội tụ chậm và sự hình thành các
vịng lặp định tuyến.
Trong giải thuật LS, mỗi router duy trì thơng tin đầy đủ về cấu hình của tồn
bộ mạng. Để làm được điều này, mỗi router quảng bá định kỳ các gói tin LSP
(Link State Packet) có chứa thơng tin về các hàng xóm và giá tới các hàng

xóm. Các thơng tin này sẽ được truyển tới tất cả các router trong mạng, từ
thông tin về giá của các liên kết trong toàn bộ mạng, các router có thể tính
tốn đường đi ngắn nhất tới các đích có thể.
Việc sử dụng các giao thức truyền thống trong MANET với việc xem mỗi
nút như một router dẫn tới một loạt các vấn đề [21]:
• Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho các cập
nhật định kỳ.
• Các nút bị phá vỡ chế độ tiết kiệm năng lượng do liên tục phải nhận
và gửi thơng tin.
•

Mạng có thể bị q tải với các thơng tin cập nhật khi số nút trong
mạng tăng,do đó làm giảm tính khả mở của mạng.

• Các đường đi dư thừa được tích luỹ một cách khơng cần thiết.
•

Hệ thống không thể phản hồi đủ nhanh với các thay đổi thường
xuyên trong cấu hình mạng.

16


1.2.2 Bài toán định tuyến mạng MANET
Các giao thức định tuyến truyền thống nếu sử dụng cho MANET sẽ đặt q
nhiều cơng việc tính tốn và truyền thơng lên các nút di động trong mạng.
Yêu cầu về tính hội tụ của các giao thức sẽ không thể thực hiện trong MANET
với tính chất động của mơi trường. Mặc dù tốc độ hội tụ có thể cải thiộn bằng
cách gửi các thông điệp cập nhật thường xuyên hơn nhưng điều này sẽ làm
tiêu tốn thêm băng thông và năng lượng nguồn ni. Hơn nữa, khi cấu hình

mạng ít thay đổi việc gửi thường xuyên các cập nhật sẽ rất lãng phí.
Các giao thức định tuyến trong MANET cần giảm tổng phí cho việc định
tuyến, thích ứng nhanh và tự động với các điều kiộn thay đổi của mạng. Giao
thức phải đảm bảo thực hiện hiệu quả trong môi trường khi các nút đứng yên,
băng thông là không giới hạn và đủ hiệu quả khi băng thông tồn tại giữa các
nút thấp và mức độ di chuyển và thay đổi cấu hình cao.
Do đó, khi nghiên cứu thiết kế các giao thức định tuyến trong MANET,
người ta thường phải xcm xét một số yếu tố sau [24]:
• Hoạt động phân tán: Cách tiếp cận tập trung sẽ thất bại đo sẽ tốn rất
nhiều thời gian để

tập hợp thông tin trạng thái hiện tại và phát tán lại nó.

Trong thời gian đó, cấu hình mạng có thể đã thay đổi.
• Khơng có lặp định tuyến: Hiện tượng xảy ra khi một phần nhỏ các
gói tin quay vịng trong mạng trong một khoảng thời gian nào đó. Một giải
pháp có thể là sử dụng giá trị thời gian q hạn.
• Tính tốn đường dựa trên yêu cầu: Thay thế việc duy trì định tuyến
tới tất cả các nút tại tất cả các thời điểm bằng việc thích ứng với dạng truyển
thơng. Mục đích là

tận dụng hiệu quả năng lượng và băng thông, mặc dù độ

trễ tăng lên do sự phát hiện đường.
• Tính tốn đường trước: Khi độ trễ có vai trị quan trọng và băng
thơng cũng như năng lượng cho phép, việc tính toán đường trước sẽ làm giảm
độ trễ phân phát.

________ rr— _____ —
OAI H Ọ C Q U Ố C GIA HÀ NÔI


TRƯNG TÂf>/ TH Ồ VS TIN THƯ VIỀN


• Bảo mật: Giao thức định tuyến MANET có khả năng bị tấn công dễ
dàng bằng một số dạng như xâm nhập truyền thông, phát lại, thay đổi các tiêu đề
gói tin, điều hướng các thơng điộp định tuyến. Do vậy, cần có các phương pháp
bảo mật thích hợp để ngăn chặn việc sửa đổi hoạt động của giao thức.
• Hoạt động nghỉ: Giao thức định tuyến cần cung cấp yêu cầu bảo tồn
năng lượng của các nút khi có thể. Hỗ trợ liên kết đơn hướng, hỗ trợ trường
hợp khi các liên kết đơn hướng tồn tại trong MANET.

18


CHƯƠNG 2: GIAO THỨC ĐỊNH TUYÊN MANET

2.1 Các kỹ thuật định tuyến MANET
Thiết kế của các giao thức định tuyến MANET bao gồm các lựa chọn vẻ
thông tin định tuyến được trao đổi, chiến lược phát các thông tin định tuyến và
cách tính tốn đường đi của gói tin. Các kỹ thuật định tuyến khác nhau được
áp dụng trong các giao thức định tuyến MANET có thể được thống kê như sau
[18,32].
2.1.1 Định tuyến LS và D V
Một số giao thức định tuyến MANET dựa trên các kỹ thuật định tuyến trong
mạng có dây LS và DV để xây dựng các giải thuật thích ứng với MANET.
Vấn đề định tuyến LS là tổng phí định tuyến tăng cao khi mạng có nhiều thay
đổi; đối với định tuyến DV đó là vấn đề hội tụ chậm và khuynh hướng tạo ra
các vòng lặp định tuyến. Các giao thức định tuyến MANET tìm cách khắc
phục các hạn chế này bằng một số sửa đổi. Một số ví dụ về các giao thức nay

là DSDV,OLSR,...
2.1.2 Định tuyến chủ ứng và định tuyến phản ứng
Định tuyến chủ ứng (Proactive) là phương pháp định tuyến của các giao thức
truyền thống; trong đó đường tới tất cả các đích được tính tốn trước, các
íhơng tin định luyến được cập nhật định kỳ hoặc bất cứ khi nào cấu hình mạng
thay đổi. Ưu điểm của phương pháp định tuyến này là độ trễ phát gói tin thấp.
Tuy nhiên, một số đường không cần dùng đến và việc truyền thông điộp định
kỳ tiêu tốn băng thông khi mạng thay đổi nhanh.
Định tuyến phản ứng (Reactive) là phương pháp định tuyến theo u cầu;
trong đó đường tới đích khơng được tính tốn trước mà chỉ được xác định khi
cần đến. Quá trình phát hiện liên kết bị hỏng và xây dựng lại đường được gọi
là quá trình bảo dưỡng đường. Ưu điểm của định tuyến phản ứng là hạn chế
được băng thơng do chỉ cần đường tới các đích cần thiết và loại bỏ các cập

19


nhật định kỳ. Tuy nhiên, vấn đề với phương pháp định tuyến này là độ trễ lớn
trước khi phát do phải thực hiện phát hiện đường.
2.1.3 Cập nhật định kỳ và cập nhật theo sự kiện
Cập nhật định kỳ thực hiện bằng việc phát các gói tin định tuyến một cách
định kỳ. Kỹ thuật này làm đơn giản hoá các giao thức và cho phép các nút học
được cấu hình và trạng thái của của toàn bộ mạng. Tuy nhiên, giá trị quãng
thời gian cập nhật là một tham số quan trọng.
Cập nhật theo sự kiộn diễn ra khi có sự kiện xảy ra trong mạng như liên kết
hỏng hoặc liên kết mới xuất hiện. Khi đó, gói tin cập nhật sẽ được quảng bá và
trạng thái cập nhật được truyẻn trong toàn bộ mạng. Nhưng khi mạng thay đổi
nhanh, số lượng gói tin cập nhật sẽ lớn và có thể gây ra các dao động về đường.
2.1.4 Cấu trúc phẳng và cấu trúc phân cấp
Trong cấu trúc phẳng, tất cả các nút trong mạng ở cùng mức với nhau và có

chức năng định tuyến như nhau. Cấu trúc phẳng đơn giản và hiệu quả với các
mạng nhỏ. Tuy nhiên, đối với các mạng lớn, lượng thông tin định tuyến cũng
sẽ lớn và mất nhiều thời gian hơn để thông tin định tuyến có thể tới được các
nút ở xa.
Đối với các mạng lớn, định tuyến phân cấp được áp dụng để giải quyết vấn
đề trên. Trong định tuyến phân cấp, các nút được tổ chức động thành các phân
hoạch gọi là cụm (cluster), sau đó các cluster được kết hợp lại thành các phân
hoạch lớn hơn gọi là các siêu cụm (supercluster),

V .V ..

Việc tổ chức mạng

thành các cluster giúp duy trì cấu hình mạng tương đối bền vững. Tính chất
động cao của các thành viên và cấu hình mạng được giới hạn trong cluster.
Chỉ có thơng tin mức cao, ổn định như mức cluster hoặc supercluster được
truyén qua khoảng cách xa do đó truyền thơng điều khiển hay tổng phí định
tuyến được giảm đáng kể.
2.1.5 Tính tốn phi tập trung và tính tốn phân tán
Trong các giao thức dựa trên tính tốn phi tập trung, mọi nút trong mạng
duy trì thơng tin tồn cục hồn chỉnh về cấu hình mạng để tính tốn các


đường đi ngay khi cần. rinh toán đường trong các giao thức sử dụng trạng
thái liên kết (Link State) là ví dụ của tính tốn phi tập trung. Trong các giao
thức dựa trên tính tốn phân tán, mọi nút trong mạng duy trì thơng tin cục bộ
về cấu hình mạng. Khi một đường cần được tính tốn trong giao thức sử dụng
véc-tơ khoảng cách (Distance vector) và phát hiện đường trong giao các thức
theo yêu cầu thuộc vào tiếp cận này.
2.1.6 Định tuyến nguồn và định tuyến theo chặng

Trong định tuyến nguồn, nút nguồn đặt toàn bộ đường trong tiêu đề của gói
tin dữ liệu, các nút trung gian chuyển tiếp các gói tin theo đường trong đề. Các
giao thức này loại bỏ nhu cầu quảng bá đường định kỳ và các gói tin phát hiện
hàng xóm. Vấn đề lớn nhất với định tuyến nguồn là khi mạng lớn và đường đi
dài, viộc đặt toàn bộ đường trong tiêu đề gói tin sẽ làm tăng lãng phí băng
thơng.
Trong định tuyến theo chặng, đường tới đích được phân tán theo các chặng.
Khi một nút nhận được gói tin cần di động chuyển tới đích, nút chuyển tiếp gói
tin theo chặng tiếp theo tương ứng với đích. Vấn đẻ là tất cả các nút duy trì
thơng tin định tuyến và có khả năng tránh được việc hình thành lặp định tuyến.
2.1.7 Đơn đường và đa đường
Một số giao thức định tuyến tìm một đường duy nhất từ nguồn tới đích. Do
đo, giao thức trở nên đơn giản và tiết kiệm được không gian lưu trữ. Tuy
nhiên, một số giao thức khác lại áp dụng việc tìm nhiều đường. Mục tiêu của
các giao thức này là sự tin cậy và mạnh mẽ.
2.2 Phân loại các giao thức định tuyến MANET
Với các kỹ thuật định tuyến được trình bày, có thể có nhiều cách phân loại
các giao thức định tuyến MANET như dựa trên cấu trúc (phẳng hay phân cấp),
thơng tin trạng thái (tồn cục, phi tập trung hay phân tán), sự lập lịch tính tốn
đường (chủ ứng hay phản ứng). Hình 2-1 là một sơ đồ phân loại các giao thức
định tuyến MANET dựa trên cách tính tốn các đường đi [9,32]. Theo phương
pháp này, các giao thức định tuyến MANET được chia thành lớp các giao thức

21


chủ ứng, phản ứng và các giao thức lai sử dụng kết hợp hai cơ chế. Sơ đồ phân
loại còn thể hiên các quan hệ giữa các giao thức.

Hình 2-1: Phân loại các giao thức định tuyến mạng MANET


2.2.1 Giao thức DSDV
DSVD là giao thức định tuyến chủ ứng dựa trên vectơ khoảng cách theo
chặng [5]. Mỗi nút trong mạng duy trì một bảng định tuyến có chứa chặng
tiếp theo và số chặng tới mỗi đích trong mạng. Để giữ cho các bảng định
tuyến được cập nhạt, DSDV yêu cầu mỗi phút phát quảng bá định kỳ các cập
nhật định tuyến tới các hàng xóm và phát ngay các cập nhật khi có các thay
đổi quan trọng xảy ra trong mạng.
Để tránh lặp định tuyến, DSDV sử dụng số thứ tự gắn với mỗi đường. Số thứ
tự cho thấy độ mới của đường. Đường có số thứ tự cao hơn được xem là tốt
hơn. Tuy nhiên, hai đường có cùng số thứ tự nhưng đường nào đó có số đo tốt
hơn thì sẽ tốt hơn. Số thứ tự này được khởi tạo ban đầu bởi nút đích. Mỗi nút
trong mạng quảng bá bằng việc tăng đều đặn số thứ tự của mình theo số chẵn.
Số thứ tự này được tăng lên một (trở thành số lẻ ) bởi nút phát hiện đường tới
đích có liên kết hỏng do khơng nhận được các cập nhật định kỳ. Trong lần

22


quảng cáo đường sau, nút phát hiện liên kết hỏng sẽ quảng bá đường tới đích
có số chặng vơ hạn và số thứ tự đường mới (số thứ tự lể).
Ngoài ra, để tránh sự bùng nổ các cập nhật định tuyến tại các thời điểm cấu
hình mạng thay đổi nhanh, DSDV cũng áp dụng cơ chế hãm các cập nhật tức
thời khi có các thay đổi xảy ra trong mạng bằng việc ghi nhận các quãng thời
gian xảy ra những thay đổi về đường, DSDV làm trễ các cập nhật tức thời theo
thời gian đó.
Nhằm làm giảm hơn nữa lượng thơng tin trong các gói tin cập nhật,
DSDV sử dụng hai loại thông điệp cập nhật là: cập nhật đầy đủ {full dump)
và cập nhật bổ sung (incremental dump). Cập nhật đầy đủ mang tất cả
thơng tin định tuyến có trong nút và cập nhật bổ sung chỉ mang các thông

tin từ những thay đổi từ lần cập nhật đầy đủ gần nhất. Để làm được điều
này, DSDV lưu trữ hai bảng khác nhau, một dùng để chuyển tiếp các gói
tin, một dùng để phát các gói tin cập nhật bổ sung. Cập nhật đầy đủ được
truyền tương đối ít thường xuyên khi ít cộ sự di chuyển của nút. Khi các nút
mạng di chuyển thường xuyên, cập nhật đầy đủ được phát để các cập nhật
bổ sung sẽ nhỏ hơn. Tuy nhiên, khi có các thay đổi trong mạng, nút thông
thường chỉ phát cập nhật bổ sung.
2.2.2 Giao thức OLSR
OLSR là giao thức định tuyến chủ ứng dựa trên trạng thái liên kết [26]. Sự
khác nhau giữa OLSR và định tuyến theo trạng thái liên kết trong mạng có
dây là OLSR dựa trên các chuyển phát đa điểm MPR hình 2-2. Các điểm
chuyển phát MPR là số tối thiểu các nút trong số các hàng xóm trực tiếp có
thể chuyển tiếp các gói tin của nút tói nút xa hơn. Ý tưởng của chuyển phát đa
điểm là tối thiểu hố việc làm tràn ngập các thơng điệp quảng bá trong mạng.
OLSR sử đụng hai loại thông điệp điều khiển HELLO và TC (Topology
Control). Thông điệp HELLO được phát định kỳ để cảm nhận trạng thái liên
kết với các hàng xóm và xây dựng lên tập MPR. Thơng điệp HELLO chỉ được
gửi đi một chặng nhưng thông điệp TC được quảng bá trong tồn mạng. Các
thơng điệp TC dùng để quảng bá thông tin về danh sách các MPR của mỗi nút


và được phát định kỳ. Tuy nhiên, chỉ các núl trong tập MPR là chuyển tiếp các
thông điệp TC.
Đ ịnh tu vén
irạn£ Uiiỉi liCn k ct

Đ ịnh tu y ến O L S R

A


Nút chuyển phát

ìhiiO' lập MPR

Hình 2-2: Định tuyến trạng thái liên kết và định tuyến cải tiến trong
OLSR
Mỗi nút duy trì một khoảng định tuyến được xây dựng từ thơng tin cấu hình
trong các thơng điệp TC và thông tin liên kết cục bộ trong các thông điệp
HELLO. Khi có bất cứ thay đổi nào trong các thơng tin này, bảng định tuyến
được tính tốn lại. Do OLSR là giao thức chủ ứng, bảng định tuyến có chứa
đường đi tới tất cả các nút trong mạng. Các đường trong bảng định tuyến được
tính dựa trên giải thuật đường đi ngắn nhất.
2.2.3 Giao thức AODV
AODV là giao thức phản ứng dựa trên bảng [4,25]. Mỗi nút duy trì một bảng
định tuyến chứa đường đi tới những đích mà nút giao tiếp. Mỗi đường được lưu
với các thông tin về địa chỉ đích, số chặng, chặng tiếp theo, thời gian tồn tại của
đường, trạng thái đường, thống tin ghi nhận các yêu cầu đã được xử lý.
AODV sử dụng các thông điệp khác nhau để phát hiện và duy trì các liên
kết. Khi có u cẩu vé đường, nếu đường chưa biết được hoặc đã quá hạn, nút
quảng bá thông điệp yêu cầu đường RREQ ( Route REQuest) tới tất cả các
hàng xóm. RREQ được phát đi tồn mạng cho tới khi đến được đích hoặc một
nút có dường đi tới đích. Trcn đường đi qua mạng. RREQ khởi tạo đường

24


quay trở về nguồn tạm thời tại các nút đi qua. Nút cũng lưu trữ định danh của
các RREỌ đã nhận đổ loại bỏ các RREQ được nhận lại.
Khi RREQ tới đích hoặc nút có đường hợp lệ tới đích, gói tin trả lời RREP
(Route REPLY) được khởi tạo và gửi quay trở lại nút nguồn qua đường đi đã

được thiết lập bởi RREQ. Trong qúa trình đó RREP thiết lập đường hướng tới
đích tại các nút chuyển tiếp. Khi RREP tới được nguồn, đường từ nguồn tới
đích đã được thiết lập. Nếu nút nguồn không nhận được RREP trong khoảng
thời gian nào đó, nút sẽ gửi lại RREQ hoặc giả thiết là khơng có đường tới đích.
Để cảm nhận liên kết, AODV sử dụng các thông điệp HELLO được quảng
bá định kỳ tới các hàng xóm. Thơng điệp HELLO cho biết về sự tồn tại của
nút và liên kết với nút vẫn hoạt động. Khi thông điệp HELLO không đến từ
một hàng xóm trước đó, nút đánh dấu liên kết tới hàng xóm đó là hỏng và
thơng báo cho các nút bị ảnh hưởng bằng việc gửi thồng báo lỗi đường RERR
(Route ERRor). Trong cài đặt, việc phát hiện liên kết lỗi có thể thực hiện bởi
lớp vật lý hoặc lớp liên kết.
2.2.4 Giao thức DSR
DSR là giao thức phản ứng dựa trên định tuyến nguồn [7,8]. Mỗi gói tin
mang trong tiêu đẻ một danh sách có thứ tự và đẩy đủ về các nút cần đi qua để
tới đích. Do đó, các nút trung gian chỉ cần duy trì các liên kết với các hàng
xóm để chuyển tiếp các gói tin. Tuy nhiên, nút nguồn cần biết thứ tự hồn
chỉnh các chăng tới đích.
Mỗi nút duy trì một bộ nhớ đường đi - Route Cache có chứa các đường đi
đã biết. Khi đường được cần đến khơng có trong Route Cache, quá trình phát
hiện được khởi tạo bằng việc phát gói tin yêu cầu đường Route Request. Khi
một nút nhận được gói tin u cầu đường nút tìm trong Route Cache đường tới
đích được yêu cầu. Nếu đường trong Route Cache khơng tìm thấy, nút chuyển
tiếp gói tin u cầu đường cho các hàng xóm sau khi bổ sung địa chỉ vào thứ
tự các chặng được lưu trong gói tin yêu cầu đường. Gói tin yêu cầu đường
được truyền qua mạng cho tới khi đến đích hoặc nút có đường đi tới đích, nếu

25