ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
v € MẠNH CƯỜNG
M ANET- ĐỊNH TUYẾN DựA TRÊN TIÊN ĐOÁN VỊ TRÍ
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 GIA HÀ NÒI
TRUNG TAM THÒNG TIN THƯ VIỆN
' 1 / Á ỵ í • ỉ
HÀ NỘI 2006
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 toán phi tập trung và tính toá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 đoán vị trí
30
2.3.1 Giao thức cập nhật 31
2.3.2 Tiên đoá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
MỤC LỤC
MỤC LỤC 1
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 quá 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 AODV 51
3.5.3 DSR 51
3.5.4 TORA 52
3.5.5 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 ĐOÁ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 Thí nghiệm 1: sử dụng mô hình Random Waypoint 57
4.3.2 Thí nghiệm 2: sử dụng mô hình Random Walk 63
4.3.3 Thí nghiệm 3: Sử dụng mỏ hình Random Direction 67
4.3.4 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 KHẢ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
OLSR 24
Hình 2-3: Sự hình thành đường trong giao thức TORA

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 đoá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 Direction 47
Hình 3-6: Các mô hình thông lượng trong NS2

48
Hình 3-7: Tổng quan quá 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 tuyên chuẩn hoá 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 hoá trong mô hình Random
Walk 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 đoán vị trí và tiên đoá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ự đoá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
Waypoint 58
Bảng 4-2: Tải định tuyến chuẩn hoá của TORA trong mô hình Random
Waypoint 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 đoán vị trí—81
6
BẢNG K Ý H IỆU C Á C CH Ũ V IÉ T T Ả T
AODV
Ad hoc On-demand
Distance Vector
CBR
Constant Bit Rate
CSMA/CA Carrier Sense Multiple
Access with Collision
Avoidance

DARPA Defense Advanced
Research Projects
Agency
DSDV Destination-Sequenced
Distance Vector
DSR
Dynamic Source Routing
DV
Distance Vector
IEEE
Institute o f Electrical and
Electronic Engineering
IETF
Internet Engineering
Task Force
LAN
Local Area Network
LS
Link State
MAC
Medium Access Control
MAN ET
Mobile Ad hoc Network
MPR Multipoint Relay
NAM
Network Animator
NS2
Network Simulator 2
OLSR
Optimized Link Slate

Routing Protocol
PAN Personal Area Network
PDA Personal Digital
Assistant
PRnet
Packet Radio Network
QoS
Quality o f Service
RIP
Routing Information
Protocol
RREP
Route Reply
RJR.EQ Route Request
RTS Request To Send
TC
Topology Control
TORA
Temporally-Ordered
Routing Algorithm
WLAN Wireless LAN
WPAN
Wireless PAN
MỞ ĐẦU
Nhằm đạt tới sự giải phóng hoàn toà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 toá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 toá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 ngoà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 toá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 đoá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
nguyên 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ó yê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.
Ngoà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
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.
1.1.1 Sự phát triển của mạng
11
©
©
Đa chặng
, " ỉ đ 0
( • ( J r j VN.VỊ

\ y
® \ © o / ỵ o © ©
9 Nút nguòn
ặ ặ NÚI đích
Q Nứt ctiưyển tiép
© C ác nút khá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
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 toá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 soá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 hoá 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].
1.1.2 Các ngữ cảnh sử dụng mạng
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, hoàn toà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 toá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 toán khó.
1.2.1 Các thuật toá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 toán DV còn được gọi là thuật toán Bellman-
Ford, đượ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 toà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
toá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ị quá 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
Các giao thức định tuyến truyền thống nếu sử dụng cho MANET sẽ đặt quá
nhiều công việc tính toá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 nuôi. 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 quá hạn.
• Tính toá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 toá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
1.2.2 Bài toán định tuyến mạng MANET
• 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 toá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 toá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 yêu cầu;
trong đó đường tới đích không được tính toá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 toán phi tập trung và tính toán phân tán
Trong các giao thức dựa trên tính toán phi tập trung, mọi nút trong mạng
duy trì thông tin toàn cục hoàn chỉnh về cấu hình mạng để tính toá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 toán phi tập trung. Trong các giao
thức dựa trên tính toá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 toá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 (toàn cục, phi tập trung hay phân tán), sự lập lịch tính toá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 toá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 hoá 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 toà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 kct
Đ ịnh tuyến O LSR
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 toá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ó yê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 toà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ự hoà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 yê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 yô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